近日,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混合负载查询。