近日，OceanBaseCTO杨传辉解读HTAP的文章《真正的HTAP对用户和开发者意味着什么？》介绍了OceanBase对HTAP的理解和技术思路，在读者中引发了广泛讨论。
OceanBase认为，真正的HTAP要求先有高性能的OLTP，然后在OLTP的基础上支持实时分析。OceanBase通过原生分布式技术提供高性能的OLTP能力，真正通过“一个系统”同时提供事务处理和数据实时分析能力，“一份数据”用于不同的工作负载，从根本上保持数据的一致性并最大程度降低数据冗余，帮助企业大幅降低总成本。
要让OLTP数据库具备OLAP的能力，尤其是大数据量OLAP的能力，除原生分布式架构、资源隔离，还需要给复杂查询和大数据量查询找到最优解。高效执行的向量化引擎，就是解决这个问题的核心技术之一。
曲斌花名：鲁信
OceanBase技术专家。数据库领域多年经验，曾从事列式数据库，时序时空数据库内核开发。目前在OceanBaseSQL执行引擎组，主要方向是向量化引擎开发，OceanBaseTPC-H攻坚项目组成员。
今天，我们邀请了OceanBase技术专家曲斌为大家分享OceanBase对向量化引擎的观点，并详细介绍我们应用向量化引擎的场景价值、设计思路与技术方案：
我们为什么要做向量化引擎；向量化引擎有哪些技术价值和特点；OceanBase向量化引擎的设计实现。
为什么要做向量化引擎
与Oracle和SQLServer等数据库系统类似，OceanBase的用户场景除了OLTP类的简单查询，还有报表分析、业务决策等复杂OLAP查询。很多用户希望在完成在OLTP联机事务处理的同时，提供连接查询、聚合分析等OLAP分析能力。而OLAP查询具有数据处理量大、计算查询复杂、耗时高的特点，对数据库的SQL执行引擎的执行效率要求较高。
早期我们通过并行执行技术将数据均匀分摊到分布式系统中多个CPU上，通过降低每个CPU处理的数据量实现查询响应时间（RT）降低。随着用户数据量的不断增多，在不增加计算资源的前提下，每个CPU计算数据的量也不断增大。我们在客户现场发现，OLAP场景下部分特殊情况的CPU利用率接近%。这在聚合分析、连接查询等大数据量分析查询中变得尤为明显。
如何提高数据库单核计算性能，降低查询响应时间（RT）对客户至关重要。为帮助客户解决HTAP混合负载下数据查询效率难的问题，OceanBase引入向量化技术，并完全自主设计了向量化查询引擎，极大地提高了CPU单核处理性能，实现了HTAP场景下复杂分析查询性能的10倍提升，并在TPC-H测试（数据分析型基准测试，业界公认衡量数据库数据分析能力的权威标准）中得到了充分验证。
在TPC-H30TB测试场景下，OceanBase向量化引擎的性能是非向量化的3倍。对于Q1这种聚合分析且计算密集的SQL查询，性能提升约10倍。测试结果可以证明，向量化引擎对提升SQL执行效率、降低用户的查询响应时间具有相当明显的效果。
图1TPC-H测试结果
(向量化引擎vs.非向量化引擎)
向量化引擎有哪些技术价值和特点
传统火山模型存在的问题
在详细介绍向量化引擎特点前，我们先了解一下火山模型以及火山模型存在的典型问题。在数据库发展早期，由于IO速度低下、内存和CPU资源非常昂贵，为了避免爆内存的情况出现，每次只计算一行数据的火山模型成为了经典的SQL计算引擎。火山模型又叫迭代器模型，正式提出是在年论文《Volcano—AnExtensibleandParallelQueryEvaluationSystem》。早期很多关系型数据库都在使用火山模型，如Oracle、Db2、SQLServer、MySQL、PostgreSQL、MongoDB等。
火山模型应用十分广泛，但这种设计并没有充分利用CPU的执行效率，进行Joins、Subqueries、OrderBy等复杂查询操作时也经常会产生阻塞。论文《DBMSsOnAModernProcessor:WhereDoesTimeGo?》在微观层面分析了数据库系统在现代CPU框架下的主要消耗细节。数据库在顺序扫描、索引扫描和连接查询三个典型查询场景下，可以很明显的看到CPU真正用在计算上的占比不超过50%。相反，等待资源（Memory/ResourceStalling）占比非常高（平均50%）。加上分支预测失败的代价，很多场景下CPU真正用来计算的比率往往大幅低于50%。例如IndexScan索引扫描下CPU计算最低占比小于20%，无法真正发挥CPU的最大能力。
图2SQL执行CPU耗时细节
向量化引擎理论的诞生
年，一篇题为《MonetDB/X:Hyper-PipeliningQueryExecution》的论文首次提出“向量化引擎”的概念。不同于传统的火山模型按行迭代的方式，向量化引擎采用批量迭代方式，可以在算子间一次传递一批数据。换句话说，向量化实现了从一次对一个值进行运算，到一次对一组值进行运算的跨越。
向量化引擎的技术价值
一、批量返回数据，函数调用少，提升Cache友好性
为了更好地提高CPU利用率，减少SQL执行时的资源等待（Memory/ResourceStall)，向量化引擎被提出并应用到现代数据库引擎设计中。
与数据库传统的火山模型迭代类似，向量化模型也是通过PULL模式从算子树的根节点层层拉取数据。区别于next调用一次传递一行数据，向量化引擎一次传递一批数据，并尽量保证该批数据在内存上紧凑排列。由于数据连续，CPU可以通过预取指令快速把数据加载到level2cache中，减少memorystall现象，从而提升CPU的利用率。其次由于数据在内存上是紧密连续排列的，可以通过SIMD指令一次处理多个数据，充分发挥现代CPU的计算能力。
向量化引擎大幅减少了框架函数的调用次数。假设一张表有1亿行数据，按火山模型的处理方式需要执行1亿次迭代才能完成查询。使用向量化引擎返回一批数据，假设设置向量大小为，则执行一次查询的函数调用次数降低为小于10万次（1亿/=），大大降低了函数调用次数。在算子函数内部，函数不再一次处理一行数据，而是通过循环遍历的方式处理一批数据。通过批量处理连续数据的方式提升CPUDCache和ICache的友好性，减少CacheMiss。
二、减少分支判断提升CPU流水处理能力
论文《DBMSsOnAModernProcessor:WhereDoesTimeGo?》还介绍了分支预测失败对数据库性能的影响。由于CPU中断了流水执行，重新刷新流水线，因此分支预测失败对数据库处理性能的影响很大。SIGMOD13的论文《MicroAdaptivityinVectorwise》也对分支在不同选择率下的执行效率有详细论述（下图）。
图3分支对执行的影响
由于数据库SQL引擎逻辑十分复杂，在火山模型下条件判断逻辑往往不可避免。但向量引擎可以在算子内部最大限度地避免条件判断，例如向量引擎可以通过默认覆盖写的操作，避免在for循环内部出现if判断，从而避免分支预测失败对CPU流水线的破坏，大幅提升CPU的处理能力。
三、SIMD指令加速计算
由于向量引擎处理内存连续数据，因此向量引擎可以很方便的把一批数据装载到向量寄存器中。然后通过SIMD指令，替换传统的标量（scalar）算法，进行向量（Vector）计算。需要说明的是SIMD指令CPU架构密切相关，在X86，ARM，PPC上都有相应的指令集。目前以Intelx86架构指令最为丰富，下图4给出了x86下各个SIMD指令的推出时间和其支持的数据类型。更详细的信息可以查看Intel的官方手册。
图4IntelIntrinsic指令支持的数据类型
OceanBase向量化引擎的设计实现
上文介绍了向量化引擎的技术原理和特点，本节将详细阐述OceanBase向量化引擎的实现细节，主要包括存储和SQL两大方面。
存储的向量化实现
OceanBase的存储系统的最小单元是微块，每个微块是一个默认64KB（大小可调）的IO块。在每个微块内部，数据按照列存放。查询时，存储直接把微块上的数据按列批量投影到SQL引擎的内存上。由于数据紧密排列，有着较好的cache友好性，同时投影过程都可以使用SIMD指令进行加速。由于向量化引擎内部不再维护物理行的概念，和存储格式十分契合，数据处理也更加简单高效。整个存储的投影逻辑如下图：
图5OceanBase向量化存储引擎VectorStore
SQL向量引擎的数据组织
内存编排
SQL引擎的向量化先从的数据组织和内存编排说起。在SQL引擎内部，所有数据都被存放在表达式上，表达式的内存通过DataFrame管理。DataFrame是一块连续内存（大小不超过2MB）,负责存放参与SQL查询的所有表达式的数据。SQL引擎从DataFrame上分配所需内存，内存编排如图6。
图6OceanBaseSQL引擎内存编排
在非向量化引擎下，一个表达式一次只能处理一个数据（Cell）（图6左）。向量化引擎下，每个表达式不再存储一个Cell数据，而是存放一组Cell数据，Cell数据紧密排列（图6右）。这样表达式的计算都从单行计算变成了批量计算，对CPU的cache更友好，数据紧密排列也非常方便的使用SIMD指令进行计算加速。另外每个表达式分配Cell的个数即向量大小，根据CPULevel2Cache大小和SQL中表达式的多少动态调整。调整的原则是尽量保证参与计算的Cell都能存在CPU的level2cache上，减少memorystalling对性能的影响。
过滤标识设计
向量引擎的过滤标识也需要重新设计。向量引擎一次返回一批数据，该批数据内有的数据被删除掉，有的数据需要输出。如何高效的标识需要输出的数据，是一个重要的工作。论文《FilterRepresentationinVectorizedQueryExecution》中介绍了目前业界的两种常用方案：
通过BitMap标记删除行：创建bitmap，bitmap中bit个数和返回数据向量大小相同。当对应bit为1时，该列需要输出，bit为0时，该列被标记删除；
通过额外数组SelectVector记录输出行。需要输出的行的下标存在SelectVector中。
OceanBase采用bitmap方案描述数据过滤，即每个算子都有一个Bitmap，filter过滤掉的数据，通过bitmap标识删除。使用Bitmap的一大优势是内存占用小，可以在查询算子过多或者查询向量size过大时，避免出现内存使用过多的情况。
另外当数据的选择率很低时，可能会出现bitmap标识的数据过于稀疏，性能不佳的情况。一些数据库通过增加整理方法，使数据稠密排列来避免上述情况。但我们在实践中发现，HTAP场景下SQL执行往往会出现阻塞算子（Sort,HashJoin,HashGroupby）或Transmit跨机执行算子，而这些算子本身具备数据整理让稠密输出的特点，额外的数据整理反而会出现不必要的开销。因此OceanBase向量化引擎没有提供单独的方法改变bitmap数据排列。
SQL引擎的算子实现
算子的向量化是OceanBase向量化引擎的重要工作。在向量化引擎中，所有查询算子都按照向量化引擎的特点进行了新的设计实现。按照向量化引擎的设计原则，每个算子都通过向量接口向下层算子拿一批数据，每个算子内部最大限度地按照branchless编码、内存预取、SIMD指令等指导原则进行工程化编码，并取得大幅性能收益。由于算子实现众多，这里重点介绍HashJoin和SortMergeGroupBy2个典型实现，其它算子不再一一赘述。
HashJoin
HashJoin通过Hash表的构建和探测，实现两张表(R表和S表)的hash查找。当hash表的大小超过CPU的level2cache时，hash表随机访问会引起memorystall，大大影响执行效率。Cache的优化是HashJoin实现的一个重要方向，HashJoin的向量化实现重点考虑了cachemiss对性能的影响。
值得一提的是，OceanBase的向量化HashJoin算子没有实现RadixHashJoin等HashWareconcious的Join算法，而是通过向量计算hashvalue和内存prefech预取的方式避免cachemiss和memorystalling。
RadixHashJoin可以有效降低cache和TLB的missrate，但是它需要两次扫描R表数据，并引入了创建直方图信息和额外的物化代价。OceanBase的向量化HashJoin实现更为简洁，先通过partition分区，构建hash表。在探测hash表阶段，首先通过批量计算的方式，得到向量数据的hash值。然后通过prefetch预取，把该批数据对应的hashbucket的数据装载到CPU的cache中。最后按照join连接条件比较结果。通过控制向量的大小，保证预取的一批数据可以装载到CPU的level2cache中，从而最大程度的避免数据比较时的cachemiss和memorystalling，进而提升CPU的利用率。
SortMergeGroupBy
SortMergeGroupBy是一个常见的聚合操作。SortMergeGroupBy要求数据有序排列，groupby算子通过比较数据是否相同找到分组边界，然后计算相同分组内的数据。例如下图c1列数据有序排列，在火山模型下，由于一次只能迭代一行数据对于分组1需要比较8次，sum(c1)也需要累加8次才能得到计算结果。在向量化引擎中，我们可以把比较和聚合分开计算，即先比较8次，找到分组1的所有数据个数(8)。由于分组内数据相同，针对sum/count等聚合计算还可以做进一步优化，例如sum(c1)可以直接通过1*8，把8次累加变成1次乘法。count则可以直接加8即可。
另外向量化实现还可以通过引入二分等方法，实现算法加速。例如下图向量的大小是16，通过二分的方法，第一次推进行的step大小为8，即比较c1列的第0行和第7行数据。数据相等，则直接对c1列的前8个数据求和。第二次推进的step大小为8，比较第7行和第15行数据，数据不相等，回退4行再比较数据是否相同，直到找到分组边界。然后再通过二分进行进行下一个分组的查找。通过二分的比较方式，可以在重复数据较多的场景下跳过重复数据的比较，实现计算的加速。当然该方案在数据重复数据较少的场景下，存在badcase。我们可以通过数据NDV等统计信息，在执行期决定是否开启二分比较。
图7SortMergeGroupBy向量化实现
本文介绍了OceanBase的向量化引擎的设计思路和实现方案。需要指出的是向量化引擎设计和实现是一个庞大的系统工程，同时也是一个不断优化的过程。随着硬件技术的不断进步和新的算法的提出，向量化引擎在年提出后也在不断演进和发展。
我们很高兴地看到，向量化引擎可以极大地帮助用户提升CPU单核处理性能，HTAP场景下复杂分析查询性能得到10倍的提升，并在TPC-H数据分析型基准测试（业界公认衡量数据库数据分析能力的权威标准）中得到了充分验证。
OceanBase的向量化引擎在不断演进中，例如当前OceanBase的SIMD计算加速都是针对X86架构下AVX指令集进行编写的,后续随着ARM架构下的应用场景增多，会增加对ARM的SIMD支持。另外算子在向量化引擎下，都可以进行大量的算法优化，OceanBase在这些方向都会持续提升，未来会引入更多的新算法实现和技术方案到向量化引擎中，更好的服务用户在HTAP场景下TP、AP混合负载查询。