Vectorization vs. Compilation in Query Execution

随着现代CPU的发展特性不断变化，近些年数据库系统为了提升系统执行性能也做出了相应的改进，最为常见的2种系统性的优化策略就是向量化和编译执行。

关于向量化和编译执行各自的特点和优势，可以看下以下2篇文章的介绍：

henry liang：MonetDB/X100: Hyper-Pipelining Query Execution​zhuanlan.zhihu.com

henry liang：Efficiently Compiling Efficient Query Plans for Modern Hardware​zhuanlan.zhihu.com

这篇paper则是对2套体系进行了一系列的对比，并给出了一些有启发性的结论。这样的对比在 其他文献[1]中也有过，但这篇paper比较有意义的一点是，它基于VectorWise（MonetDB X100的商业化版本）现有的向量化执行引擎进行扩展改造，并在Select/Project/Hash join 3个具体的场景中，进行了比对和分析，使读者可以更有实感的去思考2者各自的特点和优劣。

SQL 语言声明性的特点和数据库执行引擎的通用性可以说是传统的解析执行模式存在的根本原因。而最为流行的volcano执行模型虽然有利于模块化和扩展性，却在现代硬件和大数据的环境下，引入了不可接受的解析和调用成本。Tuple-at-a-time的执行模式，使得现代CPU的并行pipelining，SIMD指令优化都很难派上用场。因为这些优化有2个基本要求：

1. 流水线的指令应该是紧邻的 -- 频繁函数调用违背这点
2. 并行处理的数据需要是逻辑上相互独立的 -- 每次一行数据违背这点

为此才引入了如下2个优化：

• 向量化执行

以MonetDB X100为例，数据处理以block为单位，结合列式的存储格式，每列数据是连续的内存数组，这样带来2个好处：

1. 解析执行成本被块处理的方式均摊掉了，如果1个block有n行，1个tuple的解析cost就变为了原来的 1/n
2. 数据的计算变为对于连续内存的紧凑loop，更有利于SIMD指令的优化或者CPU的并行pipelining，使得多个循环同时执行，更充分利用cpu计算能力

编译的主要意义是为了去除不必要的解析代码，从而减少实际要执行的指令数。编译的策略可以是holistic的 (HIQUE为代表），或者只针对性能核心的代码片段做编译，HyPer则是对可以流水线起来的算子合并编译，某种意义上也可以算holistic。这和向量化执行那种，每个算子内部拆分成若干step，每个step利用对应的原语进行计算，这种step after step的方式形成了明显的对比。

本文对比的也正是这种holistic的编译方案与向量化的step by step的执行方案。

向量化执行每个step时，都要涉及到从input array做load，结果在store到output array中，即使可以保证数据是cache resident的，对应的load/store指令却不可避免。

编译执行则相反，在load到input data后，完成一系列的计算，将结果store到output中，最小化了load/store指令的数量。

paper认为这编译执行其实是一种通用的优化策略，与向量化执行是正交的，因此两者可以结合起来互相弥补。而这也是这篇paper的主要结论，通过结合获取最好的性能。

下面通过3个具体的算子场景来看下对比分析：

Projection

先给出结论：

当compilation结合以block为单位的计算方式时，可以获得最佳的效果。tuple-at-a-time的执行方式通过编译可以获得一些提升，但效果没有那么明显。

使用了如下SQL来做micro-benchmark

SELECT l_extprice*(1-l_discount)*(1+l_tax) FROM lineitem;

语句中，decimal的精度是2，因此VectorWise会使用整形来存储这些值，最后再除以100。

基本原则是尽量使用最小宽度整数来描述目标值域，放置overflow同时可以节省内存，本例中

l_discount/l_tax都是1个字节，2者相乘的结果是2个字节，l_extprice则是4个字节。

• 向量化执行

在VectorWise中，使用了预生成的向量化原语(map_xxx)，这种原语会组合各种operation/data types/parameter modes，生成大量(3000~)的静态函数。

可以看到，每个map_函数的计算都是极简的，针对连续内存数据，因此可以很好地利用SIMD的编译器优化来大量减少执行的指令数。（文中用上述SQL中的表达式做了个实际执行指令数的计算，这里就不赘述了）

上图中则是同样表达式的编译版本，可以看出以及没有了类型解析之类的代码，同时这里的计算是针对1个block的，也就是向量化结合的产物。

前面已经提到，对于编译执行来说，最大好处是最小化了load/store的次数（没有中间step)，但丢弃了多行数据并行SIMD/Pipelining的机会，通过与向量化结合，这点得到了补强，因此它的效果应该优于单纯的向量化。这点在下图中得到证实。

Compiled, SIMD-sht是向量化+编译的结果， Vectorized, SIMD-sht则是单纯向量化的结果。

• tuple-at-a-time编译执行

上图中黑星(Comp. per tuple)是tuple-at-a-time的原始编译，而Iterpreted是原始解析。

可以看到单纯的编译方式确实产生了效果，但有没有无法做到SIMD的优化（没有tight loop)，也无法做到pipeling（不停的next函数调用切割了对tuple的计算，计算指令并不相邻），因此无法产生足够大的提升。因此对于像MySQL/Postgres这样的传统执行引擎，单纯引入编译策略是无法产生令人满意的效果的。

Selection

先给出结论：

完全的编译执行由于受到分支预测的影响，无法做流水线并行，非常影响性能。而向量化的执行在计算每个step时，可以将control-dependancy的分支预测，转换为data-dependancy来避免if条件判断，来实现一定的流水线能力。

文中采用了如下filter condition:

WHERE col1 < v1 AND col2 < v2 AND col3 < v3

• 向量化执行

这里会有对多列的判断，一般的向量化引擎（包括VectorWise)会采用保持原始数据不变+利用selection_vector将多个conjunctive谓词的计算串联起来。如下图所示：

可以看到，这里用了sel_lt_xx的一系列原语，同时用sel1/sel2作为selection_vector。每个condition作为1个单独的step。

每个condition step的计算有2个方式：branch / non-branch

non-branch版本将if条件去掉，变为了数据的计算，这样允许了在1个循环内的流水线。

branch版本在分支的true/false概率接近时，预测效果是最差的，应该避免使用。

VectorWise在实现中会根据实际观察到的选择率，在不同实现原语间动态切换。

编译执行可以有多种模式，比如将部分if条件转换为data-dependancy或者完全不转换或者完全转换，如下图：

最后的“compute-all”是完全转换的版本，这里存在1个trade-off:

对每1条tuple，执行的计算量和分支条件的判断量。

分支条件判断的少，则更有利于pipelining，但要执行的数值计算就会变多，反之判断的多，则可以避免掉不必要的计算（条件不满足）。

实验的结论如下：

可以看到，对比"compute-all"的编译执行和纯粹的non-branch向量化执行，后者会更好些。

Hash join

这里只考量了hash probe的部分，且为了简化问题，只考虑主外键等值join的情况，也就是说只要probe到第1个match，就可以结束probe。

先给出结论：

完全的编译执行在顺着link-list做fetch时会产生cache miss而造成的memory stall，通过与向量化的结合，可以将多行的fetch并行起来，提升内存访问的吞吐。

VectorWise中的hash table是最为传统的link-list实现，如下图：

V是实际的数据部分，可以用DSM（列存），也可以是NSM（行存）。

文中采用了如下SQL:

SELECT build.col1, build.col2, build.col3
FROM probe, build

WHERE probe.key1 = build.key1 AND probe.key2 = build.key2

• 向量化hash probing

1.hash bucket计算

针对多列probe的情况，需要通过hash -> rehash的方式对每一列迭代进行，最后通过

bitmap and的方式：H&(N-1)，来缩减到N个hash bucket中。

2.第1次lookup

通过ht_lookup_initial这个原语来定位到目标bucket list。

lookup的结果产生一对向量(match, pos)，match中计算所有后续next指针不为NULL的位置，pos向量和data vector完全对应，具体存储了每个value目前所对应到的bucket list中的位置，如果为0，则list已经到头，否则指向某个link list上的数据（可能是命中，或没命中的），如下图：

在定位到link list后，要执行check计算，也就是判断指针指向的list中的值，与data vector中的执行是否一致，由于有多列，这个操作也是迭代进行的：

可以看到，通过map_check -> map_recheck的过程，最终可以得到一个向量，这个向量类似于selection_vector，其中为1的，表示没有match的data。利用sel_nonzero这个原语，将其中非1的序号提取出来，这样就可以覆盖掉原来的Match向量，这样就变成了如下情况：

Match向量中指向的pos中的位置，都是没有命中且有后续next指针（可以继续考察），没有执行的pos的位置，如果为NULL则是到达link list尾部，因此没有join match，不为NULL则是match的build侧value的指针。

对于Match中仍然指向的Pos位置，可以基于前面图中的ht_lookup_next这个原语继续找下去，并继续做check，直到match向量为空。这时Pos中不为0的位置，就是最终join上的build value。

• Partial Compilation

对如上的向量化算法，可以用编译策略进行进一步优化，其中有几个点：

1. 对于hash -> rehash -> bitmap and，也就是hash value计算+bucket定位，可以融合在一个loop中，编译执行
2. check -> recheck，这个过程，可以融合起来编译成1个函数，反复调用执行

第1个点和projection的分析类似。

第2个点和selection的分析类似

3.根据最终的Pos向量做数据的fetch，这部分的编译。

这个点和之前的分析有所不同：

如果是向量化执行，数据的fetch是column-at-a-time，这样如果数据是NSM（行存），每列的访问会跨越多行，很可能会有cache-miss和TLB-miss。但如果在block内采用编译执行，就会对每行的多列先获取完，再处理下一行，从而利于了data locality和多行间的并行memory access，效果会更好。

可以看到 Compiled NSM效果是最好的。（data locality + loop pipelining)

• Full Compilation

完全的编译执行代码如下：

并行的内存访问问题：

memory access的延迟并没有随着硬件发展有太大改进(~100ns)，而cpu cache line尺寸则维持在64 bytes，但由于现代cpu引入了parallel memory access的能力，使得memory访问的吞吐得到了很大的提升，这种并行access来源有2种：

1. prefetch，来源于连续内存区域的访问
2. pipelining，当多个流水线可以同时执行时，指令中的load/store也可以并行完成

对于上面讨论的random access的情况，很明显prefetch 是利用不上了，但向量化的执行方式使得loop-pipelining仍然可行。但上图中的full compiled方式，则在每个V[pos]的计算和下一个pos的计算之间完全无法并行（有pos = V.next[pos] 是否为null这个条件）。

上图从左 -> 右依次是改变

1. hash table size，可以看到，随着hash table变大，cache/TLB miss也会增大，导致性能下降。
2. selectivity，随着选择率增大，probe时命中的会变多，因此fetch的成本也会变高。
3. bucket chain的长度，长度越长，full compiled的方案受到影响的越大，因为它在前后的link跳转间完全不能并行。

总体来说最佳的方案就是partial compiled + NSM的方式，因为有data locality + loop pipelining。

这篇paper通过基于常见场景的分析，给出了一些非常有意义的参考结论，在做执行引擎系统设计时很值得参考：

如果执行层原始是tuple-at-a-time的处理方式，做向量化改造成本是很高的，很可能设计到每一个算子的内部实现，但为了达到深度的性能优化，这种改造不可避免，单纯的表达式编译（如Postgres那样）无法获得很理想的性能提升。

将向量化+编译执行两者结合起来，可以获得更好的效果。纯粹的编译执行由于缺乏

1. 1. SIMD优化机会
   2. branch错误预测的避免（control -> data)
   3. parallel memory access

这些能力，导致效果会不如向量化。

因此更好的方式是将编译的大循环拆解，转换为多个小循环，在循环间物化中间结果，其实也就是在向量化的内部使用编译技术。这样每个算子仍然保持模块化，便于进行维护和扩展。同时大循环的编译方式会把代码固化，导致无法做一些自适应的执行机制（例如根据选择率调整condition计算顺序），通过多个step的小循环则可以避免这一问题。

之前TiDB的CEO黄东旭在阿里内部的一个分享中抛出一个问题，为什么现代数据库系统越来趋向选择向量化而不是编译执行，我想这篇文章从技术角度，给出了很好地解答。

1. ^Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask http://www.vldb.org/pvldb/vol11/p2209-kersten.pdf