这应该是SQL查询编译的一篇经典文章了，作者是著名的Thomas Neumann，主要讲解了TUM的HyPer数据库中对于CodeGen的应用。

在morsel-driven那篇paper 中，介绍了HyPer的整个执行框架，会以task为单位处理一个morsel的数据，而执行的处理逻辑（一个pipeline job）就被编译为一个函数。这篇paper则具体讲如何实现动态编译。

背景

Volcano的经典模型虽然简单且易于扩展，但很明显在它那个时代，查询执行主要是IO bound，而CPU的代价影响很小，但对于main-memory的数据库系统，这种针对iterator反复调用next函数的模式，其中包含了很多低效的操作，包括频繁的函数调用（虚函数call，引发分支错误预测），tuple的格式解析代码，而这些由于是tuple-at-a-time，导致操作成本被放大了很多。

基于此，很多”新”系统开始偏离iterator这种执行模式，例如一次处理一个data block来均摊函数调用的成本，但这也削弱了volcano模型自身的一大优势，身的一大优势，也就是数据pipeline的能力，一般情况下一个tuple可以无需进行拷贝可以一直保持在register中被各个算子处理。而一次处理一批数据，意味着数据需要“保存”在某个位置，使下一个算子可以继续处理，在paper那个年代也许cpu cache还不足够大因此会产生memory store/load，即使可以在cpu cache中但也无法做到tuple-at-a-time那种始终保持在register中，一批数据一定会存在register <-> cache的数据IO。

上图摘自MonetDB/X100的paper，可以看到hand-coded代码具有最好的执行性能，而MonetDB这种vectorized的思路，就是为了减少函数频繁调用的开销，同时利用批量连续数据做loop-pipelining，提高CPU的执行效率，但正是由于存在"物化"数据的IO操作，导致从register <-> cache/memory的多余交互。而编译执行的目标是为了追求达到理想的Hand-coded程序的性能。

注：关于MonetDB/X100和向量化执行

基本概念

本paper提出的compilation framework，包括几个方面：

1. 处理以data为中心，而不以operator为中心，模糊掉operator之间的调用边界，尽量将data保持在cpu register中尽可能长的时间，目标就是为了data/code的locality最大化！
   
2. 数据流不再是iterator pull的模式，而是push的模式
   
3. 使用LLVM来做代码的生成
   

为了追求最优性能，paper考虑的角度就是最大化data/code的locality，因此提出了pipeline-breaker的概念。这里的pipeline-breaker是指一个operator，如果在处理input data时，需要将data移出register，放入memory中，则它就是一个pipeline breaker，而我们传统意义上理解的pipeline-breaker这里成为full pipeline-breaker，是指要获取到所有的数据后，才能开始处理的operator。

可以看到，这里pipeline breaker的定义比传统定义要更加严格，而HyPer就是希望找到这种数据的流动边界，基于观察：

• 函数的调用会有register的失效，压栈，入参等等操作，就导致data无法始终在register当中，形成pipeline breaking，因此iterator的这种pull的模式下，是有频繁的函数调用的，无法满足严格意义上的(register)的pipeline
  
• 向量化的处理方式虽然减少了函数调用次数，但很明显批量的数据无法始终存在于register中，也不是严格意义上的(register)的pipeline
  

因此这里使用了相反的数据流方向，不再pull数据，而是将数据"push"到下一个算子，这个push一直进行直到下一个pipeline-breaker。因此数据总是从一个pipeline breaker push到另一个pipeline breaker，其中可能经历多个operators的处理逻辑，而最理想的情况下，在两个物化点之间的所有处理逻辑，能够compile到一个code fragment(function)中，这样每个tuple，在load到register之后，流水线的完成所有可能的处理，再store到目标pipeline breaker中，每个tuple都是如此，这样就使得数据最大程度留在register当中，最小化memory access的次数。

这样说可以有点抽象，让我们看个例子：

这个语句及其算子树结构是比较典型的，可以看到右侧就是按照pipeline-breaker进行切分后的4个计划片段，每一个内部可以做到完全的流水线：

1. R1 每行tuple扫描出来后做过滤，然后将结果物化在hash table中
   
2. R2每行tuple扫描后过滤，然后执行分组聚集操作，结果也需要物化到hash table中(hash aggregation）
   
3. 对第2步物化的hash table，其中读取每行tuple，插入到一个build side hash table中，用来与R3做join
   
4. R3的每行tuple扫描后完成与2个hash table的probe操作，如果可以probe上则输出
   

即使是iterator的执行模式，这4步中的3个物化点也是不可避免的，通过push的方式可以更好的利用这3个pipeline-breaker，让数据的"register <-> memory"只发生这3个点 + 重新读取新tuple时，这样效果岂不是最好？可以写出类似下面的伪代码：

可以看到4段紧凑的代码片段对应了上面的4个操作，当然这只是示意代码，但思路就是这样，每个code fragment已经融合了多个operator的执行逻辑，且都不大，这种“紧凑代码片段 + 大量数据”的模式具有最好的code locality。

代码编译

从上面的代码片段可以看到，每一个片段中，执行的操作都不仅限于一个算子，而是混合了多个算子的计算，这也就是作为的data-centric，而不再是operator-centric，每个代码片段不再针对算子，而是针对当前数据所能完成的最长流水线操作！

每个算子的操作各有不同，如何“识破”算子的内部执行方式以及算子间的数据流转关系，来实现把多个算子的处理逻辑混合起来，形成类似上面Figure 4的伪代码呢？paper中给出了一种标准的描述方式：

每个算子提供2个标准接口：

• Produce
  

Produce接口描述一个算子如何从下层输入算子中获取数据的逻辑

• Consume(attributes, source)
  

Consume接口描述对下层传递的数据（Produce），本算子的计算逻辑，以及如何将结果传递给上层算子的consume函数的逻辑

以Join/Selection/Scan算子为例：

仔细观察上图以及对Produce/Consume的描述，注意它们并不是像next()函数那样的实际计算接口，而是一种概念上的“描述”接口。也就是说，它们描述的是不同算子间的数据流转的依赖关系，计算逻辑哪些是耦合的，编译器就是基于这些信息，来将不同算子的实际计算逻辑打散，“拼接”成不同的代码执行片段（类似上面Figure 4)。

例如上面这个例子中的top join操作，查询的处理流程是

[Join a=b].produce
  -> [Selection x=7].produce
    -> [Scan R1].produce    /* 获取R1中的数据 */
      ->  [Selection x=7].consume /* 执行过滤操作 */
         -> [Join a=b].consume  /* 获取left side数据，放入hash table */
  ->  [Join c=z].produce
    ...

当编译器处理这样的query，通过produce中描述的执行依赖关系以及算子是否是pipeline-breaker的特性，它就可以把Join左侧各个算子的consume部分串联起来，形成一个scan -> select -> build hash的流水线。这2个接口只被编译器用来做动态编译。

注：为了方便理解，可以把produce想象成“函数调用”，而consume想象成“函数实现 + return 结果”，这样等于是告诉了编译器函数间的调用逻辑，以及每个函数的具体实现！编译器看到这些就和看到我们编写的code没啥区别，正常编译即可。

func1 {
  /* consume描述 */
  ....
  func2()
  return到func0
}
func2 {
  /* consume描述 */
  ....
  func3()
  return到func1
}
func3 {
  ...
}
整体流程：
func0 -> func1 -> func2 ...

代码生成

考虑到动态编译的效率，HyPer中使用了LLVM来生成可以跨平台的IR code，为了降低难度，使用了LLVM提供的API来生成IR code而不是完全手动编写，然后在运行中通过JIT compiler将IR code编译为针对运行平台的machine code。

选择LLVM的原因是它的编译速度很快，而且具有很好的代码优化能力，并且可以和C++做最原始的交互（直接内存访问，函数调用）。

在实际应用LLVM时，很难去描述针对复杂的数据结构的操作或者复杂的运算逻辑，因此在整个执行流程中，在处理复杂逻辑(merge sort)，或访问复杂数据结构(Btree index…）的地方，还是要使用C++的，而LLVM的作用主要是执行紧凑的密集计算，且计算逻辑不复杂，此外也可以作为串联多个复杂计算的流程性代码。

而在LLVM中，data天生就是保存在register当中的，如果需要store到memory反而需要调用特定的指令才行。

从性能最优化的角度，最好将hot code path中重复度很高的逻辑（表达式计算/tuple格式解析/predicate过滤….）用LLVM来编译执行，LLVM code与C++ code可以任意交互，没有额外成本。

上图中是tablescan算子的produce函数（注意它没有consume函数），其中描述了算子的计算逻辑，并使用了CodeGen/Context，都是LLVM提供的接口类，调用对应的接口方法(CreateICmpULT…）就可以生成相应的IR code。

这个代码片段是针对示例中的scan -> selection -> aggregation这个pipeline所生成的汇编代码，用红框标注的是对C++的数据结构的访问(hash table)和函数调用(@_ZN12Hash...)。可以看到这么一小段代码看起来以及挺复杂了，并不便于理解和调试。

其他优化

• 如果将push one tuple at a time改变为一次一批tuple，可以利用现代CPU的SIMD指令 + 寄存器实现更高效的处理，在LLVM中，有原生的类型(vector）对SIMD的支持。
  
• 如果想做算子内的并行，其实对CodeGen这部分逻辑没有什么影响，因为每段pipeline job本身也是基于一个data fragment(物化点）开始处理，这个data fragment就可以是一个morsel。
  

总结

这篇文章从一个比较high level的层面描述了在query processing中应用动态编译技术所能带来的好处，并描述了HyPer中这种data-centric + push的执行模型所基于的基本思想：最大化pipeline执行中数据维持在cpu register的时间，从而最小化memory access的次数与代价。这种思路也确实启发了后续很多业界系统做查询优化的思路。

但这种方案并没有解决一些基本的弊端：

• 每个tuple做完一条pipeline，就无法利用多个tuple的loop-pipelining来最大化现代cpu的并行能力。
  
• 查询编译本身的启动成本还是较高的，即使是LLVM大概也要在ms级别（取决于优化等级），Neumann后续的研究提出了一种自适应的动态编译策略，用来解决这个问题。