读后感：Volcano-An Extensible and Parallel Query Evaluation System

能写、能存、能读是数据库三大基本功能，而查询引擎就是完成数据库读的重要模块，显然应该位列数据库核心组件列表。查询引擎没有精确的形式化定义，但是Volcano模型[1]却影响了非常多的关系数据库查询引擎的设计，学习一下。

Volcano模型的提出者是Goetz Graefe，其1904年发表此文，并于2017年获得Edgar F. Codd（关系模型奠基人）创新奖[2]，也算是此生贡献给数据库了。

从文章标题看得出来，Volcano重点关注的是扩展性和并行性。扩展性的意思是，查询引擎可以比较容易的应用在不同的数据库系统里面，通过简单的修改就可以适配新数据类型，新算法，新算子。并行性的意思是不同的算子可以很方便的并行运行，不同的数据分片可以很方便的被并行处理。据作者论文中写，Volcano是第一个融合扩展性和并行性的查询引擎。如果我们想一下10年前出现的Map-Reduce编程模型，以及近几年很火的各种SQL-On-Hadoop方案的竞争和演化，会发现Volcano的思想仍然闪耀光芒。

Volcano将系统设计分为两个部分，见图1，下面的模块是文件系统，上面模块是查询处理系统。笔者个人理解文件系统模块的存在更多的是为了说明整个系统的完整性，不是文章重点，因此会简单介绍，重点介绍其查询处理系统部分。

Volcano的文件系统部分包括缓存管理，文件记录，B树索引等。以缓存管理为例，作者认为缓存模块应该提供若干种不同的替换策略，但是具体使用哪一种需要上层应用决定（不是业务应用，是说查询处理系统），并指出当前数据库系统中缓存模块自己决定替换策略是不太合理的。上面这种思想贯穿在整个论文中，即底层模块提供机制，上层调用指定策略决定如何组合底层的机制来解决问题，这也是扩展性的一个方面。

Fig 2. Linux文件系统简略结构

下面重点介绍其查询处理系统。作者首先提到了文件系统里面有很灵活的机制来增强文件系统的扩展性，这句话作者一笔带过未加详细说明。个人理解可能类似Linux内核中虚拟文件层对各个具体的文件系统提出的接口要求，只要符合这个要求的文件系统都可以被内核有效识别。虚拟文件系统规定文件系统必须提供一系列的文件操作指针，比如open/seek/read/format等，有了这个约定我们自己要写一个实验性质的文件系统对接到Linux内核中并非难事，这样一些新的文件系统就可以出现，从而推动整个体系的演进[3]。从面向对象语言的角度，VFS有点像接口声明，而各个具体的文件系统就是不同的实现类，接口指针可以被任何模块使用，只要符合这个接口约束的实现都可以填充进去。作者提出的查询处理系统基本思想与此类似，其认为每个算子都应该实现成一个iterator，有三个接口，分别是open/next/close，其中open可以做一些资源初始化，比如打开文件，next将游标向前推进返回Next-Record（由ID和指向buffer的数据指针组成；为了性能，可以返回一批记录），close负责销毁资源。

Fig 3. iterator 示例

图3展示了iterator体系的基本思想，很容易看到每个iterator都实现了相同的接口，即open/next/close，每个算子并不关心其他算子是干什么或者怎么干的，只要实现这三个接口大家就可以配合工作，这真是一个非常巧妙的组合。这样做至少从以下几个优点：

很容易更新算法：比如已有的group by算子在资源占用上不够高效，那么只要按照这三个接口重新实现一个就可以方便的换掉已有的实现，而这个更换过程中对其他模块无感知（准确的说，是用新算子填充iterator，不是重新实现iterator）

很容易添加新的iterator：整个算子体系就是一堆实现了open/next/close迭代器的组合，那么想实现了一个新的算子放入这个体系也变得非常容易，并且对系统其它部分无感知

很容易异构化，并行化：本质上上游的iterator只关心下游iterator送来的数据，至于该下游iterator是如何得到这些数据的则完全不关心，所以这就使得我们很容易将iterator放到不同的CPU（分布式系统里面就是不同计算节点）运行，简化了并行化的复杂度，并可以将并行化做成标准流程，为所有算子共享

很容易重新组合算子：查询优化中可以基于一些重写规则或者统计信息来重新定义各个算子执行的顺序，从而达到优化查询的目的，而Volcano体系结构中，允许各个算子自由组合，那么这就使得查询优化变得更加容易实现

说道这里，我们还要插播一下iterator和operator的关系。作者在文章中说，In summary, demand-driven dataflow is implemented byencoding operators as iterators, i.e., with open, next, and close procedures,since ...，可以认为，iterator是一个更广泛的框架，规定了操作流程是open、next、close，然后可以提供了一些非常通用的实现，比如内存的控制，而从处理逻辑看，其基本可以认为是一个空壳，真正干活的是operator。

继续上面的主题，难道如此复杂的问题就这么简单的解决了？思路确实如此，但是还有很多细节。我们看到了图3中的arguments、input和state。input容易理解，就是来自下游iterator的输出，这个输出理论上是一片字节数据，如何解释这些数据靠的是支持函数（support function）。支持函数需要细致的了解一下，这个概念也是该文的核心信息。支持函数在作用上可以理解为虚拟文件系统的file_operations结构，里面以函数指针的形式规定了众多文件操作声明，比如要open一个文件，就要提供文件名，打开模式，权限信息。支持函数可以是预编译好的，也可以是动态生成的代码并在运行时进行解析。支持函数可能长下面这样，

int32_t comp(void* left, void* right) // 比较两条记录

int64_t hash-1(void* left) // hash

void pack(void* input, void* output); // 压缩

void unpack(void* input, void* output) // 解压

void add(void* input, const char* col) // 系统函数

void udf-1(void* input, void* output) // 用户定义函数

...

支持函数被当做arguments的一部分传入进来，每个state record记录其所属iterator需要的所有支持函数。需要注意的是，支持函数的参数也可以是一个函数指针，这又增加了系统的扩展能力。如果钻一点牛角尖的话，arguments里面不仅包含支持函数，也可以包含整个iterator体系需要的参数，比如用户传入的一些常量等，这一类参数文中称为bindings。解释了input和argument，还剩下state，这个也算比较容易理解，在iterator运行的过程中总有一些中间结果需要记录，比如count operator就需要记录中间结果，group by也需要记录中间结果，然后经过整理再吐给上游。

关于支持函数，operator，iterator的关系，按照文章的意思，应该是iterator在最外层，每个iterator都可以包装几个operators，然后支持函数被operator使用。而实际的系统中，我想他们的界线应该是模糊的，比如sum的operator是不是跟sum的支持函数可以并列？一个几乎是空壳的iterator是不是干脆换成operator好了？论文要求的是准确描述概念，概念越多越好，职责分明；工程要求代码精简，有些概念是可以权衡合并的。

说道这里，本文的核心逻辑就结束了，但是因为这篇文章的目标是实际的工程领域的可扩展性和并行性，因此还有一些细节是需要再次思考的。

首先，文中特别提到了scan和filter，并指出filter operator包括三个功能，分别是predicate，transform和apply。predicate可以过滤一些行，比如利用bit vector技术（如bloomfilter）减少上层operator处理的数据量；transform是按照上层operator要求进行必要的变换，比如去掉一些不必要的列，解压或者将读出来的数据变成指针继续向上传递；apply一般用来更新状态，比如读了多少行，打日志等。从理论角度看，filter这么多的功能应该拆开变成operator树上面的三层operator，但是实际上，这三个操作的组合关系是固定且有限的，因此拍平是更合理的选择。另外，文中还提到将索引读和数据读分开实现，并使用类似Join的技术在必要的时候连接起来，对于非主键索引，是一种合理的抽象；对于主键索引，我不太认同，因为数据库记录一般比较小，这种操作增加了系统复杂度甚至会增加查询的IO。

Fig 3. 二元输入，一对一记录匹配关系

其次，文中通过一个一对一操作符实现了众多的join类型，因为本质上这些join都是在笛卡尔积上面进行选择。不过我有点怀疑这样可能导致性能的损失，intersection和union应该有各自更高效的实现。

最后，文章提到了两个meta operator。一个是chose plan operator，这个概念就是在执行过程中允许动态的选择一些执行路径。动态执行今天是一个很流行的概念，但是却不是通过iterator加一层实现的，而是在查询优化阶段就确定了，而查询优化阶段跟执行阶段是并列的，并不从属。主要原因我觉得可能是优化太复杂，不是放在iterator里面通过支持函数选择一个策略这么简单。跳出来看，查询过程中动态优化当然很牛，不过更务实的做法也许是通过查询统计优化查询计划，然后在下一次查询时候体现出优化结果。第二个是exchange operator，这是用于自动并行化的标准算子，有了这个，其他算子就不用考虑并行化的问题。并行有两类，一类是将数据分成很多分区，每个分区执行一样的operator树，这些执行是并行的，最后结果合并起来；一类是数据只有一份，要执行的各个算子之间可以并行。这两种并行并不互斥，可以一起使用来优化系统。在Volcano的设计中，并行化operator交互使用的就是exchange operator，不管是单机或者多机。exchange 可以理解成一个异步信号，当这个信号发出后，接收方就开始干活，发送方不会停下来等待结果，而是继续前进，当接收方干完活返回结果的时候，发送方按照预定逻辑处理就可以了。在分布式系统里面，exchange operator大概可以理解为rpc operator（想想Map-Reduce），MPP SQL引擎Impala里面实现了此类算子。

至此，学习了这篇文章的核心理念，具备统一接口的算子，有向无环图的算子组合，通过添加交换节点而自动增加并行能力。似懂非懂，以后继续找这个领域的专家学习。

[1]. Volcano-An Extensible and Parallel Query Evaluation System

[2]. https://sigmod.org/sigmod-awards/people/goetz-graefe-2017-sigmod-edgar-f-codd-innovations-award/

[3]. https://researcher.watson.ibm.com/researcher/files/il-AVISHAY/01-block_io-v1.3.pdf