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