向量化执行从理论到实现，仅需五步！ | DB·洞见

随着硬件技术的不断发展，数据库系统也需要进行相应的优化，以便可以充分发挥出底层硬件提供的能力。

以查询计划执行为例。原有的数据库执行一个查询计划，往往采用火山模型的方式。这种上层算子递归调用下层算子获取并处理元组的方式，存在虚函数调用次数较多、指令或数据cache miss率高的缺陷，并且这种一次处理一个元组的方式无法使用CPU的SIMD指令进行优化，从而造成查询执行效率低下的问题。向量化执行就是解决上述问题的一种有效手段。

探索前沿研究，聚焦技术创新。本期DB·洞见由腾讯云数据库高级工程师胡翔为大家介绍向量化执行的基本原理、技术创新以及向量化引擎的相关实现。

点击观看讲师完整版分享

论文解读

1.1 论文简介

经研究，论文作者发现数据库系统的CPU使用率(IPC 0.7)较低。原因在于，火山模型的一次处理一个元组的执行方式，导致了较高的解释执行代价，阻止了可以允许CPU并行执行的编译优化，这对性能的影响至关重要。

而MonetDB/MIL使用一次处理一个列的执行方式，避免了上述问题，但是数据的全部物化导致内存带宽受限，进而影响CPU效率。

最终作者在两个模型之间找到了一个折中点，为MonetDB设计实现一个新的执行引擎MonetDB/X100，使用向量化执行的方法，提高CPU使用率，在实际验证中性能提升较为明显。

下图为该论文的目录：

1.2 CPU是怎么样工作的？

本论文发表于2005年，它列举了10年内CPU的发展状态，具体如下图右上角的折线图所示。我们可以看见CPU的发展速度越来越快，CPU晶体管数目每隔两年会增加一倍，在当时是符合摩尔定律的。

下方的点线相当于晶体管的长度，每隔两年有1.4倍的减少，相当于整个容积提升了两倍。中间的虚线表示的是使用了pipeline技术的CPU，它具体指的是把一个指令划分成多个阶段，多个阶段之间可以并行，带来了较为可观的性能提升。

下图中的左下图描述的是一个简单的pipeline，它划分成了5个阶段，中间指令执行的时候，不同指令的不同stage可以并行执行。

Pipeline的运行会受某些条件约束，最主要的两个影响因素是依赖关系和分支预测。

依赖关系是指如果一个指令依赖前一个指令，就必须等待前一个指令执行结束之后才能放入pipeline。相当于两个指令并不是独立的，必须有一个多余的等待动作，因此并发粒度会降低。分支预测指的是CPU会预测程序将要执行的分支，并将其放入到pipeline中，但是如果预测失败，之前执行的pipeline都会废弃，因此会对pipeline的效率有较大影响。

另外，超标量pipeline提供多个pipeline，允许多个指令并行，从而使IPC大于一。具体示例如下方右下图所示。

我们编程时不需要特别关注哪些指令是独立的或是相关的，实际上这些工作是通过编译优化自动实现的。编译优化中有一个比较重要的技术，即loop pipeline，可以把一个循环里的多次迭代进行pipeline，从而允许并发执行，可以极大提高循环的执行效率。

下图左下角是执行一个循环的示例，该循环有3次迭代，顺序执行则需要消耗9个circle（假设1个stage执行时间为1个circle）。通过编译优化将其组成pipeline形式后（假设指令之间相互独立），就可以在5个circle内完成整个三次迭代，提升了将近一半的效率。

有些特定的CPU也会做一些特定的优化，如下图所示的这款CPU Itanium2，它会主动将指令进行划分，再将相互依赖的指令拆解到不同的pipeline里，这样就可以分别进行并发执行。而其他CPU使用较多的是乱序执行，即CPU自己需要承担部分调度任务，需要将某些独立的指令拆分出来，再放到pipeline里。但Itanium2使用了指令划分，这样可以减轻自身负担，因此可以把更多精力投入到pipeline中，提高了pipeline的运行能力。同时Itanium2对分支预测也做了对应优化，把 if then else中的then和else这两个分支都执行一遍。在后续执行时，会根据if的结果来确定抛弃对应分支获得的结果。这是较早的CPU处理方式，但应用较为广泛，目前某些硬件CPU上也会有类似的应用。

上图右上表研究了分支预测对性能的影响。一个带Filter条件查询的两种不同实现在两种不同CPU的执行时间对比，其中，数据列均匀分布在0~100区间内，故可以根据X来表示查询筛选率。带分支的实现将满足条件的数据放到结果数组里面，而不带分支的实现先把条件赋给一个布尔值，然后将数据放到结果数组里面，但是结果数组序号由自增变成对布尔值做加法，从而把条件去除，但指令数会增加。

可以看出，针对于CPU Athlon，使用带分支的实现，在选择率较低或筛选率较高时，执行时间较短，表明分支预测误判率较低时执行效率较高，而在中间位置筛选率中等时耗时较长，表明分支预测误判率较高时执行效率较低。使用不带分支的实现，执行时间比较稳定，因为没有分支，不受分支预测的影响，所以是一条比较直的线。

而针对于CPU Itanium，无论使用带分支或者不带分支的实现，执行时间都比较稳定，表明其CPU独有的优化生效，但是带分支的实现性能更好，而不带分支的实现由于指令数更多性能变差。

此外，CPU芯片上的cache对CPU性能影响较大。部分研究表明cache miss对数据库系统影响非常大。一些cache对齐的btree，或者列式内存数据结构，以及限定cache上的算法也有助于提高性能。

从上图右下角可以看出，距离CPU越近计算速度越快，主存延迟是cache的20倍到200倍。如果将计算都集中在cache，则有利于发挥CPU的实际算力。

总的来看，对CPU性能影响较大的主要是cache命中率、分支数目、分支预测是否成功，还有指令之间是否独立。数据库系统的CPU使用率接近0.7，低于其他系统，比如科学计算相关的系统的CPU使用率可以达到2。数据库系统不应该有如此的表现，特别是针对数据量和计算量都特别大的分析型任务。作者指出，需要充分利用好CPU的pipeline并行能力来提高CPU的利用率，这也是论文的主要优化目标。

1.3 TPC-H Query 1 Benchmark

论文选取TPC-H作为测试集，将Query 1作为研究对象，进行profile性能测试，深入研究定位性能瓶颈。

Query 1扫描了几乎所有的数据，同时包含多种计算，分别为列与常量减法2个、列与常量加法1个、列与列乘法3个、聚集函数8个（sum 4个、avg 3个、count 1个）。此外，比较特殊的是分组键为两个单字节的字符。论文逐个分析了在传统关系型数据库、MonetDB/MIL以及手写程序上Query 1的性能。

作为传统的关系型数据库，查询执行严格按照关系代数来实现，具体的执行过程，则按照火山模型pipeline的处理方式。因为其关系代数自由度较高，带的参数比较多，需要实现一个可以处理表达式所有情形的解释执行器，这个会更加复杂。

论文对MySQL进行了性能 profile，第二列表示当前函数占用的百分比（除去调用的部分），第一列是第二列累积的百分比，第三列是调用次数，第四列是每次函数调用执行的指令数，第五列是IPC。论文发现，所有的实际工作只占了整个语句执行时间的一小部分。实际的计算只占了10%，而28%用来创建探测哈希表，其他62%消耗于元组解析、数据拷贝等，锁和buffer管理等其他因素的影响很小。另外，实际计算的效率与CPU能力差异大，主要原因是一次处理一个tuple，无法进行loop pipeline优化，从而增加函数调用次数，进而降低了CPU执行效率。其他数据库也出现了类似的问题。

论文接着对MonetDB/MIL 执行引擎进行了 benchmark。

MonetDB是一个列存数据库，相当于将数据进行垂直划分再逐列存储，每列存储形式为BAT形式。其使用的代数查询语言叫做MIL，可以列式地处理输入的多个BAT，并输出一个BAT。另外，MonetDB的自由度较低，针对特定的数据类型进行区分实现，而不是通用的实现，从而减少部分解释代价。

Benchmark结果如右图所示。前四列是不同数据量的对比，包括执行时间和带宽。第五列是内存占用情况，以1M为单位。第六列是结果集大小。

可以看到，MonetDB/MIL 解决了执行率低的问题，20个调用执行占比达到99%，比其他数据库都要高。但与此同时，每个调用也都变成了内存密集型。前述提到在MonetDB/MIL中会将数据全部物化，物化的数据量太大，导致内存带宽受限，进而影响CPU效率。

作者还使用MonetDB的UDF获取性能的基准。基准程序把涉及的列都作为参数，以BAT形式的数组表示，添加restrict关键字，用来告诉编译器这个数组里的元素都是独立不相关的，以便进行编译优化。作者还利用了 group 列的特征，即单字节字符，直接按照bit位组合来获取数组的序号，避免创建一个复杂的哈希表。另外，还有部分子表达式的优化。

1.4 X100: A Vectorized Query Processor

作者在前述优化的基础上再进行优化，提出了MonetDB/X100。测试显示，其性能更强，超过基准性能。本部分将详细介绍MonetDB/X100的有关细节。

其设计目标是：能够在执行大量的查询时达到较高的CPU使用率；可以扩展到其他应用领域，如数据挖掘和多媒体检索，并实现同样的高效率可扩展性代码；还能根据底层存储规模大小进行伸缩。

为了达到性能目标，作者梳理了计算机架构中可能出现的瓶颈点。

• 磁盘：ColumnBM I/O子系统面向高效的顺序数据访问来进行设计，同时采用列式存储，解决多余的数据存储代价，减少带宽压力。另外，基于列式存储还可以做一些轻量级压缩，进一步减少带宽压力。
• 内存：设计跟磁盘类似，也采取了列式存储的组织形式，目的也是为了减少内存占用和带宽压力。
• Cache：把数据组织成vector形式，再把vector完全放入cache中，使得计算都在cache内进行，这样可以减少数据到内存的换入换出，从而提高计算效率，而不必考虑内存带宽问题。
• CPU：操作或算子都使用向量化原语，目的是便于编译器优化成loop pipeline的高效代码。

右下图为架构示意图，上半部分是MonetDB/X100与原先的MonetDB、MonetDB/MIL之间的依赖关系，下半部分是更直观的整体结构。可以看到，执行引擎部分，处理单元都是一个方块，即代表一个向量，按向量力度来进行处理。这些向量能够直接放到 cache里进行计算。

在查询语言方面，MonetDB/X100与MonetDB/MIL不同，可以生成多个列向量（仍然是BAT形式），以作为其他操作或上层算子的输入。具体语法如右上角图所示，上面是标准的SQL语句，这实际上是Q1的简化版本，而下面是MonetDB/X100代数的形式。执行流程仍然按照火山模型pipeline的方式，但是以vector为粒度。

右下角的图是简化版本的TPC-H Q1在MonetDB/X100的执行流程。图中包含了4个算子，即Scan、Select、Project和Aggregate。

Scan每次从MonetDB BATs中获取多个列对应的vector，图中有三列。Select创建一个selection-vector，在满足谓词条件的元组位置进行标记。这个数组在后面的计算过程中也同样会用到。引入selection-vector的好处在于，不必将筛选出来的数据进行拷贝和重新编排，允许在原来的输入向量上直接计算，效率会更高。

Project主要是完成表达式计算并为最终聚集计算做准备。Project时会使用selection-vector跳过之前被筛选掉的元组，避免不必要的计算。Aggregate计算主要包含两部分：计算每个元组在HashTable中的位置，计算聚集函数并将结果更新到对应的位置。新的位置需要在HashTable中创建。所有下层算子执行结束，不再生产新的vector后，遍历HashTable获取最终结果。Aggregate时也会使用selection-vector。

以上就是MonetDB/X100的查询执行流程，整体流程类似于原来的火山模型，主要区别在于执行粒度从原来的一个元组变成一个vector，函数调用次数大幅减少，同时对一个vector进行循环计算时可以用编译优化来提高CPU运行效率。另外，具体实现时需要增加一些辅助数组，以及对原有的执行逻辑的改造等。

与标准的SQL语言相比，MonetDB/X100的代数形式是比较特殊的。它包含两种数据输入，Dataflow表示在pipeline中流转的元组，Table是特殊的Dataflow，表示物化的表。

MonetDB/X100的向量化原语部分，主要用来进行批量快速计算。以右图为例，这是一个double类型的数据在做加法。函数的参数包括一些输入和输出的向量化，还包括一个类似于section-vector的辅助数组。如果selection-vector不为空，就需要参考数组得到有效元组的位置，然后进行计算，而如果为空，就直接计算即可。每个输入都是向量，可以完全放入到cache里面进行计算。批量处理的循环可以进行loop pipeline的优化，提高CPU的使用效率。另外，MonetDB/X100针对每个数据类型都有单独的实现，可以避免元组解析的代价。按照原语模板自动生成的方式，MonetDB/X100包含了上百个向量化原语。

MonetDB/X100还运用到组合向量化原语，它也可以进一步提高执行效率。以做加法为例，以往可能需要两个操作数先读取数据，最后写入数据，中间才是一条加法的指令，数据的读写代价太高，就导致了实际计算工作占比较小。MonetDB/X100对向量化原语进行组合后，一次执行中实际工作做的更多，这样就均摊了数据读写的代价。

在数据存储方面，MonetDB/X100采用列式存储。但每列单独存储的方式一般会有更新删除等代价，比如更新一行可能会涉及修改多个列文件。MonetDB/X100通过经典的delta结构来解决列存更新/删除代价增加的问题。

比如Delete直接使用deletion list来记录tupleid；Insert并没有在原来的数据上增加，而是直接放在另一个delta结构区域，用行存方式进行存储；Update采用delete+insert的执行方式；Delta Merge则是将delta结构区域合并到原列存上。另外，还有一些索引信息用于汇总局部的最大值和最小值，从而可以用于数据筛选。这些都是比较通用的列存实现方式。

1.5 TPC-H实验

作者在论文中将MonetDB/X100和MonetDB/MIL进行对比，在不同的处理器、不同的数据量上，MonetDB/X100的性能都明显更优。

作者还在Q1上做了性能profile测试。在内存带宽上，MonetDB/X100的带宽比较高，内存占用较少，另外有些列也采用enum类型进行了优化。

作者还对向量大小进行测试，即不同向量大小对性能的影响，从上图中可知，大小适中时性能最优。过大过小都不是最优结果。过大无法放入cache，会有额外的从内存读写数据的代价。过小则类似于原来的火山模型，无法做编译优化，无法使用CPU并发能力的优化，而且函数调用次数增加，实际的工作占比则会变小。

1.6 论文总结

这篇论文基于经典火山模型和MonetDB/MIL的列式查询执行模型做了进一步优化，从而得到性能极大提升。

以往的火山模型一次处理一个tuple的方式造成过大的解释执行代价，阻止了对性能影响极大的编译优化。MonetDB/MIL不存在上述问题，它可以让CPU高效运行，但是全部物化的执行方式会造成内存密集型的问题，内存带宽会受限。通过向量化执行方式，使用较小数量的可放入cache的列式数据，即vector，进行批量计算，则可解决上述两个问题。验证结果显示，性能与其他相比有两个数量级的提升。

向量化执行引擎实现详解

2.1 如何实现向量化执行引擎

我们结合TDSQL的具体实现，来详细介绍向量化的实现过程。如何实现向量化执行引擎，其核心工作主要包括四个部分：

• 向量化执行框架：向量化执行计划的生成和执行以及与非向量化执行计划的兼容。
• 向量化数据结构：合理设计向量的内存组织形式，尽可能使用cache资源，减少内存拷贝。
• 向量化算子实现：批量计算改造，拆分成小的循环来执行简单的操作，便于编译优化成高效程序。
• 向量化函数实现：与算子实现类似，还需要对表达式计算框架进行调整，简单的计算函数可以通过SIMD显式向量化。

2.2 向量化执行框架

向量化计划生成的方式，采用贪婪的方式，尽可能将计划路径中涉及的算子转换成向量化执行的方式。不支持向量化的计划节点，可以通过在其上添加一个行转向量的算子，相当于把输出从行元组变成了向量，从而支持上层算子的向量化执行。我们以一个简单的SQL为例，原有的火山模型执行流程和向量化模型执行流程如右图所示。

2.3 向量化执行数据结构

向量化执行数据结构的原则有两个：一个是尽可能将数据连续存储在更靠近CPU的位置，如cache；另一个则是列式组织形式，方便对单个列进行快速计算。

在以往，一个元组用一个TupleTableSlot来表示。为了便于向量化计算，我们把它改造成一个包含多个元组的结构，通过VectorTableSlot来表示。它实际上不是简单地把元组合并起来，而是对数据进行垂直划分，每列数据放在一起。

相同列的数据组织在一起就称为列向量，通过ColumnVector来表示，为实际计算的操作数。具体包括：元数据，如行数、列表示信息等；标记数组flags，如标记null信息等；值数组vals；内存挂载位置bufs。

数据则区分为定长和非定长存储。定长数据直接存储在vals数组中。变长数据因为不能直接存在上面，需要分配非固定大小的内存，挂载在bufs上，并把地址存在vals数组中，内存可以快速复用。

2.4 向量化算子实现

向量化算子实现也有类似的原则：一个是尽可能地将复杂的循环处理过程拆解成多个简单的小循环，以便批量地对同种类型的数据进行快速循环处理；另一个是减少分支以及数据依赖等。

我们以HashAgg算子、HashJoin算子为例，来介绍如何实现向量化改造。下图实际上是一个简化版的Query 1 ，两列做分组，再分别进行HashAgg操作。

具体改造过程分为五步：

1. 对输入的元组向量在分组列上批量计算hash值；根据计算的hash值批量计算hash bucket值。

2. 构建hash table，采用Open-addressing的冲突处理方式，记录元组对应的hash entry；如果内存占用超过内存限制，元组则需要下盘。

3. 计算聚合结果，并将其更新到对应的hash entry上。

4. 遍历hash table，拼接成向量输出。

5. 如果存在下盘的数据，重新构建hash table并执行上述步骤。

我们以下图为例来介绍HashJoin算子向量化的过程。

具体改造过程分为五步：

1. 对Scan内表得到的元组向量进行批量计算，得到hash值和hash bucket值。

2. 对内表构建hash table。

3. 对Scan外表得到的元组向量批量计算hash值和hash bucket值。

4. 使用外表元组向量探测内表构建的hash table，再进行批量的匹配操作，如果匹配则进行标记，如果不匹配就去找下一个位置进行匹配。

5. 根据标记数组将匹配成功的行进行对应的Proj列输出。

2.5 向量化函数实现

我们具体实现时没有增加新的类型，只是对原有版本的函数进行改造，支持各种通用的数据类型。在具体执行时需要进行函数的替换。

以右图为例，这是一个intel4类型的判断，左边是比较简单的判断，右边的输入则是列向量。需要注意的是，左边的判空逻辑实际上是在函数外面，右边因为要对每行进行判空，所以这里涉及的函数比较多。

总结和展望

本期分享中，我们通过一篇有关向量化执行的经典论文介绍了向量化的基本原理，并结合TDSQL的实现详细阐述了向量化的实现过程。

为了进一步提升查询执行效率，我们正在对算子的向量化算法进行更加深入的优化，尽可能方便编译器对程序自动地进行向量化编译。另外还通过SIMD显式指令进一步提高向量化的粒度。编译执行也是解决类似问题的有效手段，特别是对于表达式计算、元组解析等通用模块尤为有效，该部分工作也正在进行中。未来我们会带来更多的优化，以轻松应对各种不同复杂业务的需求。

﹀

﹀

﹀

-- 更多精彩 --

↓↓点击阅读原文，了解更多优惠