写点什么

向量化引擎对 HTAP 的价值与技术思考

  • 2022 年 7 月 21 日
  • 本文字数:5823 字

    阅读完需:约 19 分钟

近日,OceanBase CTO 杨传辉解读 HTAP 的文章《真正的 HTAP 对用户和开发者意味着什么?》介绍了 OceanBase 对 HTAP 的理解和技术思路,在读者中引发了广泛讨论。


OceanBase 认为,真正的 HTAP 要求先有高性能的 OLTP,然后在 OLTP 的基础上支持实时分析。OceanBase 通过原生分布式技术提供高性能的 OLTP 能力,真正通过“一个系统”同时提供事务处理和数据实时分析能力,“一份数据”用于不同的工作负载,从根本上保持数据的一致性并最大程度降低数据冗余,帮助企业大幅降低总成本。


要让 OLTP 数据库具备 OLAP 的能力,尤其是大数据量 OLAP 的能力,除原生分布式架构、资源隔离,还需要给复杂查询和大数据量查询找到最优解。高效执行的向量化引擎,就是解决这个问题的核心技术之一。

关于作者

曲斌

花名:鲁信


OceanBase 技术专家。数据库领域多年经验,曾从事列式数据库,时序时空数据库内核开发。目前在 OceanBase SQL 执行引擎组,主要方向是向量化引擎开发,OceanBase TPC-H 攻坚项目组成员。


今天,我们邀请了 OceanBase 技术专家曲斌为大家分享 OceanBase 对向量化引擎的观点,并详细介绍我们应用向量化引擎的场景价值、设计思路与技术方案:


我们为什么要做向量化引擎;向量化引擎有哪些技术价值和特点;OceanBase 向量化引擎的设计实现。

为什么要做向量化引擎

与 Oracle 和 SQL Server 等数据库系统类似,OceanBase 的用户场景除了 OLTP 类的简单查询, 还有报表分析、业务决策等复杂 OLAP 查询。很多用户希望在完成在 OLTP 联机事务处理的同时,提供连接查询、聚合分析等 OLAP 分析能力。而 OLAP 查询具有数据处理量大、计算查询复杂、耗时高的特点,对数据库的 SQL 执行引擎的执行效率要求较高。


早期我们通过并行执行技术将数据均匀分摊到分布式系统中多个 CPU 上,通过降低每个 CPU 处理的数据量实现查询响应时间(RT)降低。随着用户数据量的不断增多, 在不增加计算资源的前提下,每个 CPU 计算数据的量也不断增大。我们在客户现场发现,OLAP 场景下部分特殊情况的 CPU 利用率接近 100%。这在聚合分析、连接查询等大数据量分析查询中变得尤为明显。


如何提高数据库单核计算性能,降低查询响应时间(RT)对客户至关重要。为帮助客户解决 HTAP 混合负载下数据查询效率难的问题,OceanBase 引入向量化技术,并完全自主设计了向量化查询引擎,极大地提高了 CPU 单核处理性能,实现了 HTAP 场景下复杂分析查询性能的 10 倍提升,并在 TPC-H 测试(数据分析型基准测试,业界公认衡量数据库数据分析能力的权威标准)中得到了充分验证。


在 TPC-H 30TB 测试场景下,OceanBase 向量化引擎的性能是非向量化的 3 倍。对于 Q1 这种聚合分析且计算密集的 SQL 查询,性能提升约 10 倍。测试结果可以证明,向量化引擎对提升 SQL 执行效率、降低用户的查询响应时间具有相当明显的效果。



图 1 TPC-H 测试结果(向量化引擎 vs. 非向量化引擎)

向量化引擎有哪些技术价值和特点

传统火山模型存在的问题

在详细介绍向量化引擎特点前,我们先了解一下火山模型以及火山模型存在的典型问题。在数据库发展早期,由于 IO 速度低下、内存和 CPU 资源非常昂贵,为了避免爆内存的情况出现,每次只计算一行数据的火山模型成为了经典的 SQL 计算引擎。火山模型又叫迭代器模型,正式提出是在 1994 年论文《Volcano—An Extensible and Parallel Query Evaluation System》。早期很多关系型数据库都在使用火山模型,如 Oracle、Db2、SQLServer、MySQL、PostgreSQL、MongoDB 等。


火山模型应用十分广泛,但这种设计并没有充分利用 CPU 的执行效率,进行 Joins、Subqueries、Order By 等复杂查询操作时也经常会产生阻塞。论文《DBMSs On A Modern Processor: Where Does Time Go?》在微观层面分析了数据库系统在现代 CPU 框架下的主要消耗细节。数据库在顺序扫描、索引扫描和连接查询三个典型查询场景下,可以很明显的看到 CPU 真正用在计算上的占比不超过 50%。相反,等待资源(Memory / Resource Stalling) 占比非常高(平均 50%)。加上分支预测失败的代价,很多场景下 CPU 真正用来计算的比率往往大幅低于 50%。例如 Index Scan 索引扫描下 CPU 计算最低占比小于 20%,无法真正发挥 CPU 的最大能力。



图 2 SQL 执行 CPU 耗时细节

向量化引擎理论的诞生

2005 年,一篇题为 《MonetDB/X100: Hyper-Pipelining Query Execution》的论文首次提出“向量化引擎”的概念。不同于传统的火山模型按行迭代的方式,向量化引擎采用批量迭代方式,可以在算子间一次传递一批数据。换句话说,向量化实现了从一次对一个值进行运算,到一次对一组值进行运算的跨越。

向量化引擎的技术价值

一、批量返回数据,函数调用少,提升 Cache 友好性

为了更好地提高 CPU 利用率,减少 SQL 执行时的资源等待(Memory/Resource Stall) ,向量化引擎被提出并应用到现代数据库引擎设计中。


与数据库传统的火山模型迭代类似,向量化模型也是通过 PULL 模式从算子树的根节点层层拉取数据。区别于 next 调用一次传递一行数据,向量化引擎一次传递一批数据,并尽量保证该批数据在内存上紧凑排列。由于数据连续, CPU 可以通过预取指令快速把数据加载到 level 2 cache 中,减少 memory stall 现象,从而提升 CPU 的利用率。其次由于数据在内存上是紧密连续排列的,可以通过 SIMD 指令一次处理多个数据,充分发挥现代 CPU 的计算能力。


向量化引擎大幅减少了框架函数的调用次数。假设一张表有 1 亿行数据,按火山模型的处理方式需要执行 1 亿次迭代才能完成查询。使用向量化引擎返回一批数据 ,假设设置向量大小为 1024,则执行一次查询的函数调用次数降低为小于 10 万次( 1 亿/1024 = 97657 ),大大降低了函数调用次数。在算子函数内部,函数不再一次处理一行数据,而是通过循环遍历的方式处理一批数据。通过批量处理连续数据的方式提升 CPU DCache 和 ICache 的友好性,减少 Cache Miss。

二、减少分支判断提升 CPU 流水处理能力

论文《DBMSs On A Modern Processor: Where Does Time Go?》还介绍了分支预测失败对数据库性能的影响。由于 CPU 中断了流水执行,重新刷新流水线,因此分支预测失败对数据库处理性能的影响很大。SIGMOD13 的论文《Micro Adaptivity in Vectorwise》也对分支在不同选择率下的执行效率有详细论述(下图)。



图 3 分支对执行的影响


由于数据库 SQL 引擎逻辑十分复杂,在火山模型下条件判断逻辑往往不可避免。但向量引擎可以在算子内部最大限度地避免条件判断,例如向量引擎可以通过默认覆盖写的操作,避免在 for 循环内部出现 if 判断,从而避免分支预测失败对 CPU 流水线的破坏,大幅提升 CPU 的处理能力。

三、SIMD 指令加速计算

由于向量引擎处理内存连续数据,因此向量引擎可以很方便的把一批数据装载到向量寄存器中。然后通过 SIMD 指令,替换传统的标量(scalar)算法,进行向量(Vector)计算。需要说明的是 SIMD 指令 CPU 架构密切相关,在 X86,ARM,PPC 上都有相应的指令集。目前以 Intel x86 架构指令最为丰富,下图 4 给出了 x86 下各个 SIMD 指令的推出时间和其支持的数据类型。更详细的信息可以查看 Intel 的官方手册。



图 4 Intel Intrinsic 指令支持的数据类型

OceanBase 向量化引擎的设计实现

上文介绍了向量化引擎的技术原理和特点,本节将详细阐述 OceanBase 向量化引擎的实现细节,主要包括存储和 SQL 两大方面。

存储的向量化实现

OceanBase 的存储系统的最小单元是微块,每个微块是一个默认 64KB(大小可调)的 IO 块。在每个微块内部,数据按照列存放。查询时,存储直接把微块上的数据按列批量投影到 SQL 引擎的内存上。由于数据紧密排列,有着较好的 cache 友好性,同时投影过程都可以使用 SIMD 指令进行加速。由于向量化引擎内部不再维护物理行的概念,和存储格式十分契合,数据处理也更加简单高效。整个存储的投影逻辑如下图:



图 5 OceanBase 向量化存储引擎 VectorStore

SQL 向量引擎的数据组织

内存编排

SQL 引擎的向量化先从的数据组织和内存编排说起。在 SQL 引擎内部,所有数据都被存放在表达式上,表达式的内存通过 Data Frame 管理。Data Frame 是一块连续内存(大小不超过 2MB), 负责存放参与 SQL 查询的所有表达式的数据。SQL 引擎从 Data Frame 上分配所需内存,内存编排如图 6。



图 6 OceanBase SQL 引擎内存编排


在非向量化引擎下,一个表达式一次只能处理一个数据(Cell)(图 6 左)。向量化引擎下,每个表达式不再存储一个 Cell 数据,而是存放一组 Cell 数据,Cell 数据紧密排列(图 6 右)。这样表达式的计算都从单行计算变成了批量计算,对 CPU 的 cache 更友好,数据紧密排列也非常方便的使用 SIMD 指令进行计算加速。另外每个表达式分配 Cell 的个数即向量大小, 根据 CPU Level2 Cache 大小和 SQL 中表达式的多少动态调整。调整的原则是尽量保证参与计算的 Cell 都能存在 CPU 的 level2 cache 上,减少 memory stalling 对性能的影响。

过滤标识设计

向量引擎的过滤标识也需要重新设计。向量引擎一次返回一批数据,该批数据内有的数据被删除掉,有的数据需要输出。如何高效的标识需要输出的数据,是一个重要的工作。论文《Filter Representation in Vectorized Query Execution》中介绍了目前业界的两种常用方案:


通过 BitMap 标记删除行:创建 bitmap, bitmap 中 bit 个数和返回数据向量大小相同。当对应 bit 为 1 时,该列需要输出,bit 为 0 时,该列被标记删除;


通过额外数组 Select Vector 记录输出行。需要输出的行的下标存在 Select Vector 中。


OceanBase 采用 bitmap 方案描述数据过滤,即每个算子都有一个 Bitmap , filter 过滤掉的数据,通过 bitmap 标识删除。使用 Bitmap 的一大优势是内存占用小,可以在查询算子过多或者查询向量 size 过大时,避免出现内存使用过多的情况。


另外当数据的选择率很低时,可能会出现 bitmap 标识的数据过于稀疏,性能不佳的情况。一些数据库通过增加整理方法,使数据稠密排列来避免上述情况。但我们在实践中发现, HTAP 场景下 SQL 执行往往会出现阻塞算子(Sort, Hash Join, Hash Group by)或 Transmit 跨机执行算子,而这些算子本身具备数据整理让稠密输出的特点, 额外的数据整理反而会出现不必要的开销。因此 OceanBase 向量化引擎没有提供单独的方法改变 bitmap 数据排列。

SQL 引擎的算子实现

算子的向量化是 OceanBase 向量化引擎的重要工作。在向量化引擎中,所有查询算子都按照向量化引擎的特点进行了新的设计实现。按照向量化引擎的设计原则,每个算子都通过向量接口向下层算子拿一批数据,每个算子内部最大限度地按照 branchless 编码、内存预取、 SIMD 指令等指导原则进行工程化编码,并取得大幅性能收益。由于算子实现众多,这里重点介绍 Hash Join 和 Sort Merge Group By 2 个典型实现,其它算子不再一一赘述。

Hash Join

Hash Join 通过 Hash 表的构建和探测,实现两张表 ( R 表和 S 表)的 hash 查找。当 hash 表的大小超过 CPU 的 level2 cache 时, hash 表随机访问会引起 memory stall,大大影响执行效率。Cache 的优化是 Hash Join 实现的一个重要方向,Hash Join 的向量化实现重点考虑了 cache miss 对性能的影响。


值得一提的是,OceanBase 的向量化 Hash Join 算子没有实现 Radix Hash Join 等 HashWare concious 的 Join 算法,而是通过向量计算 hash value 和内存 prefech 预取的方式避免 cache miss 和 memory stalling。


Radix Hash Join 可以有效降低 cache 和 TLB 的 miss rate,但是它需要两次扫描 R 表数据,并引入了创建直方图信息和额外的物化代价。OceanBase 的向量化 Hash Join 实现更为简洁,先通过 partition 分区,构建 hash 表。在探测 hash 表阶段,首先通过批量计算的方式,得到向量数据的 hash 值。然后通过 prefetch 预取,把该批数据对应的 hash bucket 的数据装载到 CPU 的 cache 中。最后按照 join 连接条件比较结果。通过控制向量的大小,保证预取的一批数据可以装载到 CPU 的 level 2 cache 中,从而最大程度的避免数据比较时的 cache miss 和 memory stalling,进而提升 CPU 的利用率。

Sort Merge Group By

Sort Merge Group By 是一个常见的聚合操作。Sort Merge Group By 要求数据有序排列,group by 算子通过比较数据是否相同找到分组边界,然后计算相同分组内的数据。例如下图 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 行再比较数据是否相同,直到找到分组边界。然后再通过二分进行进行下一个分组的查找。通过二分的比较方式,可以在重复数据较多的场景下跳过重复数据的比较,实现计算的加速。当然该方案在数据重复数据较少的场景下,存在 bad case。我们可以通过数据 NDV 等统计信息,在执行期决定是否开启二分比较。



图 7 Sort Merge Group By 向量化实现


本文介绍了 OceanBase 的向量化引擎的设计思路和实现方案。需要指出的是向量化引擎设计和实现是一个庞大的系统工程,同时也是一个不断优化的过程。随着硬件技术的不断进步和新的算法的提出,向量化引擎在 2004 年提出后也在不断演进和发展。


我们很高兴地看到,向量化引擎可以极大地帮助用户提升 CPU 单核处理性能,HTAP 场景下复杂分析查询性能得到 10 倍的提升,并在 TPC-H 数据分析型基准测试(业界公认衡量数据库数据分析能力的权威标准)中得到了充分验证。


OceanBase 的向量化引擎在不断演进中,例如当前 OceanBase 的 SIMD 计算加速都是针对 X86 架构下 AVX512 指令集进行编写的, 后续随着 ARM 架构下的应用场景增多,会增加对 ARM 的 SIMD 支持。另外算子在向量化引擎下,都可以进行大量的算法优化,OceanBase 在这些方向都会持续提升,未来会引入更多的新算法实现和技术方案到向量化引擎中,更好的服务用户在 HTAP 场景下 TP、AP 混合负载查询。

用户头像

企业级原生分布式数据库 2020.05.06 加入

github:https://github.com/oceanbase/oceanbase 欢迎大家

评论

发布
暂无评论
向量化引擎对HTAP的价值与技术思考_oceanbase_OceanBase 数据库_InfoQ写作社区