概述

当我们的逻辑计划引擎把SQL生成了逻辑计划后，后端的物理计算引擎接收到逻辑计划生成物理执行计划，便可以开始去真正执行计算作业了。在关系数据库发展的早期，受制于计算机IO能力的约束，数据库通常的物理执行引擎采用的是火山模型的设计方式。因为火山模型每次只处理一行数据，大大的节约了内存的使用量。

数据库物理计算引擎通常分为二类，一类是以火山模型(Volcano Model)为代表的拉取模型。另一类是以Pipeline为代表的推模型。本文主要讲述的是第一种火山模型(Volcano Model)。了解火山模型前，我们了解一下数据库的一些基本算子。

算子介绍

先简单介绍数据库中基本的算子。

  1. Scan算子，作用是读取数据源的具体数据。例如: select * from t 就是读取t表中的数据。<br />    Selection算子，作用是处理Sql中的谓词条件。例如: select xxx from t where xx = 5 里面的 where 过滤条件就是Selection算子处理的。<br />    Projection算子，作用是物理执行器计算出的数据传递给外部。例如: select c from t 中 Projection算子是输出C列中的数据。<br />    Join算子，作用是计算两个表的连接后的数据。例如: select xx from t1, t2 where t1.c = t2.c 就是把 t1 t2 两个表做 Join。

image.png

火山模型

火山模型又叫迭代器模型, 最早于1990年Goetz Graefe在Volcano, an Extensible and Parallel Query Evaluation System这篇论文中提出(参考资料中有论文链接)，在90年代早期，计算机的内存资源十分昂贵，相对于CPU的执行效率，IO效率要差得多，因此运算符和存储之间的IO交换是影响查询效率的主要因素（IO墙效应），火山模型将更多的内存资源用于IO的缓存设计而没有优化CPU的执行效率是在当时的硬件基础上很自然的权衡。

火山模型其基本思路十分简单：将关系代数当中的每一个算子抽象成一个迭代器。每个迭代器都带有一个 next 方法。每次调用这个方法将会返回这个算子的产生的一行数据（或者说一个 Tuple）。程序通过在 SQL 的计算树的根节点不断地调用 next方法来获得整个查询的全部结果。比如 SELECT col1 FROM table1 WHERE col2 > 0;这条 SQL 就可以被翻译成由三个算子组成的计算树。如下图所示，我们也可以使用伪代码将这三个算子的执行逻辑表示出来。

image.png

通过上图可以看到，Volcano 模型是十分简单的，而且他对每个算子的接口都进行了一致性的封装。也就是说，从父节点来看，子节点具体是什么类型的算子并不重要，只需要能源源不断地从子节点的算子中 Fetch 到数据行就可以。

上面的例子简单的说明了下火山模型的工作原理，下面我们举一个稍微复杂点的例子了解一下物化的这个概念，有一个 JOIN 算子，因此在生成的执行方案树当中会有一个分叉。我们假定 RIGHT_TABLE 表的行数远小于 LEFT_TABLE 表，这样一个合理的执行方案可能是先将 RIGHT_TABLE 表的所有数据读出来构造一个 Hash 表，再将 LEFT_TABLE 表当中的每一行读出并通过 Hash 表查询获得结果。此时的 Volcano 模型的执行要更复杂些。JOIN 算子为了向上封装这些细节，需要在内部不断调用 RIGHT_TABLE 表的 next 方法直到将其内容全部读取出来。

SQL如下:

图片.png

因此，对于这样一条 SQL，他的执行树表示成下图的样子。

image.png

如上图所示，我们将 RIGHT_TABLE 的内容读入 Hash 表，构建 RIGHT_TABLE.C1 -> RIGHT_TABLE.C2 的映射。之后再逐一读入 LEFT_TABLE 表的内容，对于 LEFT_TABLE 表的每一行，我们使用它的 C1 列在 Hash 表中进行查询，从而得到 JOIN 之后的结果。

JOIN 算子的执行分为两个部分。第一个部分它会在内部不断调用 RIGHT_TABLE.next() 函数构建 Hash 表，之后调用 LEFT_TABLE 的 SCAN 算子一次以便返回第一行结果。之后对 JOIN 的调用就只会读取 LEFT_TABLE 的内容进行并在 Hash 表里探查（Probe）。这一方式实现的 Hash 表是一个带有内部状态的算子，与其他的算子大不相同。而它构建内部 Hash 表的过程可以被认为是一种物化（Materialization）。

火山模型痛点

火山模型简单明了，也非常灵活。但是在当代CPU的硬件环境与大数据场景下，性能表现却差强人意。究其原因。主要有如下几点：

一、虚函数的开销

next函数通常是一次虚函数调用。在Java中，为了支持多态，所有的非静态方法与非final方法本质上都是动态绑定的虚函数，在JVM层依赖于invokevirtual和invokeinterface这两个方法指令。虚函数调用与普通函数的调用的区别在于后者是一次直接调用，直接调用的跳转地址在编译时是确定的。而虚函数调用是一次间接调用，需要在运行时才能从虚表获取地址再跳转。所以，虚函数首先会多一次寻址的时间开销；其次，虚函数是无法在编译期做内联优化的，所以运行时会实实在在多一次函数调用开销。对于Java来说，方法调用会在运行时会多一次栈桢入栈出栈操作；最后，也是最重要的一点，虚函数的间接调用本身会导致分支预测。据统计，间接分支预测的失败率在25%左右。一旦分支预测失败，将会导致流水线被冲刷，进而需要重新获取指令、译码，对性能造成严重的影响。

二、Cpu Cache的利用率

这种风格对代码和数据的局部性并不友好。它不能很好的利用CPU的缓存机制。由于CPU的各级Cache都是从下一级存储按特定长度单位对齐取数的，且取到的数据也是连续的，所以每次取到的连续的数据如果能被集中充分处理，将会得到最大的收益。但next调用每次只处理一条记录，而且火山模型是个拉取的模型，即下游什么时候拉取并不随当前算子控制，所以当前算子刚刚cache的数据在只取用了一部分就很有可能马上被其他算子的next调用获取的数据给冲掉(evict)了。而当前算子再次调用next时又会冲掉别人的cache，重新将之前被人冲掉的未处理的数据从较慢的存储中读取来给CPU处理。这样的周而复始，造成了不必要的开销。而且拉取模型也要求严格以算子为界进行物化，其实很多物化点是可以避免的。

大数据时代的体量放大了1和2的问题。如果数据量不多，那么1和2的问题并不明显。但是在大数据时代，我们需要处理的数据量从百万到数十亿是家常便饭。每条记录都会经历next的调用，所以性能问题将被放大百万倍、数十亿倍以至更甚。从而警醒我们不容忽视。

那么有没有一种解决方案处理虚函数的问题呢？火山模型影响的是执行流程的代码布局，但只要是解释执行，就无法避免运算符之间的虚函数调用。随着计算机硬件的发展，内存变得越来越大，这意味着越来越多的数据可以直接cache在内存中，而访问磁盘的频率被大幅度的降低，这个时候“IO墙”的效应被削弱，而由于解释执行无法感知CPU寄存器，高频的内存访问，使CPU和内存之间形成了“内存墙”效应，为了解决这个问题，越来越多的内存数据库开始使用Llvm编译执行的技术来优化自己的查询效率，例如HyPer、MemSQL、Hekaton、Impala、Spark Tungsten等，参考资料中给出了impala中的使用编译执行的论文。

那么有没有一种解决方案处理CPU Cache的问题呢？答案是显而易见的，我们可以通过批量处理的方式来优化处理。之前提到，在火山模型中，next方法是一次处理一条记录，而我们知道next的调用开销是挺高的，而一次处理一条记录对于代码和数据的局部性都不是很友好。所以，如果能next方法改善为例如nextBatch方法，让每次能在算子里一次性处理的数据与CPU的Cache Line对齐，那将在局部性这块上得到最大化的收益。当然，batch不宜过大，正好能放入Cache Line为佳。批处理计算还为进一步的优化（如 SIMD 指令执行）提供了有利条件。

结论

本文介绍了物理计算引擎的Pull模型是实现之一的火山模型。火山模型是一种简单的计算模型，把各个的物理算子抽象成一个个迭代器。每一个算子只关心自己内部的逻辑即可，让各个算子之间的耦合性降低。但是同样火山模型也带来的虚函数开销和CPU Cache不友好的问题。下一节中带来物理计算引擎Push模型的Pipeline设计方式。敬请期待。