文章转自ruanxi

前言

    在《数据库系统中的Code Generation技术介绍》一文中，我们阐述了代码的CPU执行效率对于大规模分布式OLAP系统的重要性。现在简单总结如下：

1. OLAP系统中查询往往比较复杂，比如多表Join, 各种聚合函数以及窗口函数，其中涉及大量的Hash计算（比如采用Hash Join, Hash Aggregation），排序（比如采用Merge-Sort Join）操作，CPU开销比较大。
2. SSD等高性能存储硬件的使用，以及内存计算的普及（比如Spark中利用RDD来Cache部分数据）大大提高了I/O性能，使得CPU日益成为计算的瓶颈。
3. 在大规模分布式OLAP系统中（比如MaxCompute），因为需要实现分布式Join，聚合以及窗口函数，一个作业可能会由多级Task组成，Task与Task之间可能会有大量的Shuffle/Sort操作，这其中包含的大量的Hash/Compare可能占据作业执行的大量时间。

   面对日益提高的执行效率述求，除了利用Code Generation等技术为SQL Query生成定制化的执行代码以外，整个执行引擎在设计上也需要有相应的考虑和改变。

Volcano Model：Row to Batch

    传统的关系型数据库基本采用Volcano Model来实现SQL执行引擎。这个模型比较好理解，查询计划中的各个算子（如SELECT, FILTER, JOIN等）实现成一个基类Operator的子类，算子和算子之间根据在查询计划中的数据传输关系形成一个有向无环图（绝大多数时候是一棵树）。除了直接与数据源打交道的算子（如从Storage读数据的TableScan）以外，每个算子都从一个或者多个其他算子读取数据，这些算子成为其“孩子”，这个算子也就是其“孩子”们的“父亲”。Operator基类有如下三个接口： 

1. Open()：做一些初始化工作，包括调用其“孩子”算子的Open()。
2. Next()：调用“孩子”算子的Next()方法获取数据，完成自身的计算逻辑。构造输出数据。
3. Close()：做一些清理工作，包括调用“孩子”算子的Close()方法。

   Volcano Model类型的执行引擎在这行过程中，数据以Record的形式在各个算子之间流动。一个Record即代表从存储层读出的一个数据行，或者某个算子计算过程中产生的中间数据行（下图描述了在Volcano Model中执行“SELECT t1.a + t2.b FROM t1 JOIN t2 ON t1.c = t2.c”中可能出现的Record）。如下图所示：

   Volcano Model的优点在于比较简单直观，SQL的执行流和查询计划对应比较紧密。因为各个算子之间都以固定的接口传递数据，因此相互之间耦合比较低，较容易应对SQL中众多算子复杂组合的场景，因此得到广泛引用。
   在执行效率方面，Volcano Model有明显缺陷。在执行过程中，算子之间通过Next()方法传递数据，而Next()方法往往实现为虚函数（或函数指针），这意味着执行过程中的Function Call的次数与Record数量呈正比，这极大影响了代码的instruction cache performance。此外，在Volcano Model中，需要沿着整个Operator Tree自底向上完成一遍执行，代码的Footprint较大，因此导致代码的 instruction locality 较低，当CPU的 instruction cache较小的时候，在执行过程中可能出现“Cache 颠簸”现象（不同算子之间反复将彼此的指令集从cache中刷出），大大降低代码的执行效率。

   一些改良过的Volcano Model，算子与算子之间以“Batch of Records”传输数据，如下图所示。以Batch的方式传递数据，一方面减少了算子之间的函数调用开销（由Record级别降低为Batch级别），也提高了指令和数据的局部性，有利于程序性能 的提升（靖人在这个方面还发表过一篇Paper, 有兴趣的同学可以参阅（传送门））。

Vectorized Execution

   上面讲到的“Batch Based Volcano Model”采用了行式的内存布局，即同一个Record中的不同列在内存中连续存放，不同行的同一列在内存中是离散的。 这在关系型计算的场景中，常常不是最优的选项。举一个例子，在一个“SELECT”算子当中，输入数据有“t1.a”和“t1.c”两列，SELECT算子从中取出"t1.a"这一列,  若采用行式的内存布局，那么需要从每一个输入Record中摘出a列来构造新的Record，事实上需要大量的内存拷贝。另一方面，在做类似“SELECT t1.a + 1”这样的表达式计算时，虽然“t1.c”这一列并没有用到，但是仍然会被Laod到CPU Cache当中，事实上降低了"t1.a"这一列的Cache命中率。


   MaxCompute 2.0在基于“Batch of Records”的Volcano Model基础上，引入了列式数据库的思想，数据在算子之间传递，处理的时候，相同列的数据在内存中地址连续。如下图所示。
       
基于列式的内存布局在上面提到的场景下有更好的性能。在“SELECT t1.a FROM t1”的场景中，我们只需要做一次指针赋值就可以完成投影操作，而不需要大量的内存拷贝，而在“SELECT t1.a +1”这种表达式计算场景下，我们也避免了Load冗余数据进CPU Cache，从而提高了CPU的Cache命中率。
   此外，列式的执行框架使得我们能够更好的提高CPU Pipeline效率，以及利用SIMD技术进行计算优化。这个我们会在后续的文章中更深入的介绍。

Vectorized Execution Engine in MaxCompute 2.0简介