简介
本文主要参考论文《MonetDB/X100: Hyper-Pipelining Query Execution》，来解释传统执行引擎 tuple-at-a-time 的缺陷，以及为什么向量化执行引擎能够解决这些问题。
其实传统执行引擎的问题说起来很简单，主要包括以下几个方面：
一是传统火山模型每次 next() 调用只获取一个元组导致了大量的虚函数调用；
二是tuple-at-a-time 的方式在执行过程中造成了巨大的解释开销(interpretation overhead)；
三是每次调用仅进行一次计算，导致无法利用 loop pipelining；且频繁的数据类型判断会导致分支预测失败，造成 CPU 流水线失效，导致 IPC (instructions per cycle）进一步降低；
还有一些改进，比如说延迟物化，SIMD 指令，这都属于在向量化引擎上的进一步改进方向。
之前也看了很多文章来解释传统火山模型的弊端，也基本提到了这几个问题。但是，对于虚函数调用、解释开销、分支预测这些名词的解释并不明确，导致看的云里雾里，似懂非懂。 于是想写一篇文章，来解释清楚这些问题，因为参考资料比较少，如果有理解不对的地方，麻烦指出。
首先来解释第一个问题，什么是虚函数调用？
虚函数调用
在中文资料里很难找到标准的定义，在此引用一段英文资料。
A method that can be overridden by a derived class is called a virtual method. Virtual method invocation is the invocation of the correct overridden method, which is based on the type of the object referred to by an object reference and not by the object reference itself. It’s determined at runtime, not at compilation time.
“被派生类重写的方法称为虚函数。虚函数调用是对正确的重写方法的调用，是基于对象的实际类型而非引用对象的类型。它是在运行时确定的，而不是在编译时。”
由于虚函数执行的具体方法是在运行时确定，这导致CPU无法进行分支预测（下面会讲），从而对性能产生影响。StackOverflow一个答主的测试中，虚函数调用会造成 7ns 的损耗，而一个直接（非虚函数）调用仅仅会 0.5 ns 的调用。
接下来解释为什么火山模型会产生大量的虚函数调用。
火山模型将整个查询构建为一个 Operator 树，从根节点到叶子节点自上而下地递归调用 next() 函数，数据则自底向上地被拉取处理，每次返回一个元组，如下图所示。
需要注意的是，图中是一个逻辑计划，具体的执行算子需要根据优化器确定。如 Aggregation 算子可能是个 HashAggregation，也可能是个 MergeSortAggregation 等，而这些实际执行的算子实际上都继承自 Aggregation 算子，于是它们调用的 next() 方法实际上就是虚函数的调用。
因为火山模型下一次调用仅返回一个元组，于是每个元组都会导致一整条调用链的虚函数调用，在元组数量较多的情况下，会导致大规模的虚函数调用，严重影响性能。
搞懂了为什么火山模型会产生大量的虚函数调用，现在来讲为什么向量化模型能够解决这个问题。
思考这么一个问题，大量的虚函数调用是因为每次调用仅仅返回一个元组，那我每次返回一个数组，调用开销不就减少了吗？假如说数组的大小是1024，那也就是说每1024条元组才会产生一次调用链，开销一下子缩小到原来的 1/1024。
向量化引擎就采用了这种思路，每次返回一个数组进行处理。当然，每次返回一个数组并不仅仅是为了减少虚函数的调用，这个我们接下来会讲。
其实向量化模型并不能够从根本上解决虚函数调用的问题，而只能减小虚函数调用的数量，从而减轻它的影响。想要根本解决这个问题，需要解决掉这种基于 next() 调用的 Pull 模型，也就是采用 Push 模型，当然这不在本文的讨论范围内。
接下来解释第二个问题，什么是解释开销？
解释开销
这个找了很多资料都没找到非常标准的定义，只能根据我自己粗浅的理解解释一下。
比如说进行一个表达式计算 colA * 0.8 + colB，在指令层面，除了真正的计算过程，还需要进行诸如堆栈检查、函数调用、操作数获取等等操作，这些除了 "real work" 之外的操作统一称为解释开销。
在论文的测试中，在MySQL上执行 TPC-H Query 1，真正执行计算的指令耗时（加粗的部分，第二列是执行耗时）仅占不到10%，其余的90%均为解释开销。
在 TiDB 的一个测试中得到了相似的结论，这里引用博客中的原文。
builtinArithmeticMultiplyRealSig 函数实现2个浮点数相乘。下面的代码块描述了这个函数的实现。右边的数组表示对应行的汇编指令数，是代码汇编后得到的。要注意，此块仅包含在正常条件下迭代的行，并忽略错误处理的逻辑：
每次这个函数执行乘法时，82条指令中仅有8条在执行“真正的”乘法，这仅占总指令的10%左右，其他90% 均被视为解释开销！一旦将这个函数向量化，它的性能提高了近9倍。 向量化一次处理并返回一批数据，减少了表达式计算过程中的解释开销。假设一批数据有1024行，优化后每次调用一个函数处理这1024行数据，然后返回。函数调用的解释开销变成原来的1/1024.
最后解释第三个问题，什么是CPU流水线和分支预测，这些技术如何对执行引擎产生影响？
CPU流水线与乱序执行
CPU 指令可以划分为一系列小的阶段（Stage），每个阶段都由不同的单元负责执行不同的任务。比如说，最基础的CPU流水线可以划分为：
- Fetch unit 负责取指令（Fetch Instruction）
- Decode Unit 负责指令解码（Decode Instruction）
- Execute Unit 负责执行指令（Execute Instrcution）
- Write Unit 负责将结果写回寄存器或内存（Write back）
假如说不使用流水线技术，那第二个指令只能等待第一个指令的结果写回后再进行，这样执行两个指令就需要8个时钟周期。但是实际上，当指令 1 进行 Decode 操作时，CPU 的Fetch unit 已经处于空闲阶段了，这时如果指令 1 和指令 2 不存在依赖关系的话，可以直接开始对指令 2 来进行 Fetch 操作。通过采用这种流水线处理的方式，只需要使用5个时钟周期就可以执行完成两个指令，如下图所示。
随着执行指令数的不断增加，流水线的吞吐优势也会更加明显。为了更好地利用流水线，有两种改进方式：
Intel Itanium2 处理器有 6 条 pipeline ，每条 pipeline 被划分为 7 个阶段，也就是同时最多允许 7 * 6 =42 条指令并行执行。Pentium4 处理器有 3 条 pipeline，每条 pipleine 有长达 31 个阶段，同时允许 3 * 31 = 93条指令并行执行。但是，并不总是能够找到那么多独立的指令来同时并行执行。
由于大多数编程语言都不要求编程人员规定哪些指令（或表达式）是独立的，此时编译器的优化就显得至关重要。其中最重要的技术称为 loop pipelining.
对一个数组 A 的所有元素（元素之间相互独立）的两个计算操作 F(), G()，且F()的执行需要2个cpu cycle，则 loop pipelining 可以将
F(A[0]),G(A[0]), F(A[1]),G(A[1]),.. F(A[n]),G(A[n])
转换为
F(A[0]),F(A[1]),F(A[2]), G(A[0]),G(A[1]),G(A[2]), F(A[3]) ...
这样当G(A[0])开始执行时，F(A[0])的结果刚好已经得到了！
有些 CPU 更复杂，可以在运行时找到可以并行执行的指令，这种技术称为乱序执行（Out-of-order execution）。主要指的是 CPU 在执行时，为了最大程度的利用流水线，如果它在缓存中没有找到下一条指令，就会选择其他与 missing 指令无关的指令执行，从而避免CPU处于空闲状态。
火山模型每次调用仅进行一次计算，导致无法很好地利用 loop pipelining。论文中提到了一个实验现象，在测试机器上，一个 +(double src1, double src2) 方法在 RISC 指令中包括四个指令：
LOAD src1,reg1
LOAD src2,reg2
ADD reg1,reg2,reg3
STOR dst,reg3
其中，测试机器上的 MIPS R12000 CPU 每个时钟周期可以执行三次计算指令和一次 Load/Store 指令，平均指令延迟是5个周期。因此，对于这个方法，瓶颈主要在这三次 Load/store 指令，也就是每三个时钟周期就可以执行一次 plus 操作。但是，在 MySQL 上的实验中，Item func plus::val 方法用时 38 个指令，其中 IPC = 0.8，也就是用时 38/0.8 = 49 个时钟周期！
对于这个现象的解释是：MySQL 每次调用只计算一次 add 操作，而不是一组 add 操作，导致编译器无法利用 loop pipelining. 因此，这四个指令必须互相等待，每个指令5个周期，一共耗时20个周期。剩下的部分都花在了 jump into the routine（不懂，照抄了），压栈和弹出栈上。
分支预测
分支预测，其实就是字面意思，比如在遇到 if...else 的时候，预测接下来是走 if 分支，还是走 else 分支。
关键的问题是，为什么要进行分支预测？
- 因为 CPU 为了能够流水线执行，必须知道接下来要执行哪条指令，不然流水线就只能空缺等待。
怎么进行分支预测？
-
一般基于模式匹配，比如说之前是“真假真假真”，下一个你猜什么？“假”对吧。或者同时执行真假两个分支，等确定方向了，再抛弃其中一个。但是这个问题不在本文探讨的范围内。
分支预测失败怎么办？
- 需要把当前 CPU 流水线中安排的指令全部清掉，重新组织流水线。因此分支预测失败会导致严重的性能损失。
那为什么火山模型会产生大量的分支预测？
首先是大量的虚函数调用会导致分支预测，在上文中我们已经提到过。
其次，火山模型是按行进行迭代，行中的每一列数据类型可能不同，因此在对每一列进行具体处理时，都要先判断其数据类型，频繁的数据类型判断导致了大量的分支代码。假如说每行有 N 列，那 1000 行的数据就会导致 1000 * N 次数据类型判断。
而向量化模型每次处理一批数据，在对这批数据进行处理时，是以列为单位进行处理。也就是说，一列的数据类型只需要判断一次，接下来就可以对这一列中的所有数据进行处理。假如一批数据有1000行，就可以将 1000 * N 次的数据类型判断减少到 N 次。
下一步改进
除了对火山模型的原有缺陷进行改进外，在向量化模型的基础上，还有诸如数组大小的选择、延迟物化、SIMD指令等优化，之后可以再开一篇文章讲这些问题。
参考
MonetDB/X100: Hyper-Pipelining Query Execution
知乎：MonetDB/X100: Hyper-Pipelining Query Execution
每次都需要解释大量指令？使用 PolarDB-X 向量化引擎
【数据库内核】物理计算引擎Push模型之编译执行
A Beginner’s Guide to Overriding Methods
What is the performance cost of having a virtual method in a C++ class?
How Pipelining Improves CPU Performance
Loop Pipelining
TiDB：向量化执行使表达式性能提升10倍成为可能
