文章转自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中刷出），大大降低代码的执行效率。