Volcano - An Extensible and Parallel Query Evaluation System

[mrdrivingduck]

graefe-ieee1994.pdf

Goetz Graefe 发表于 1994 年的文章，介绍了 DBMS 的 迭代器执行模型 (iterator model) 和一种可扩展的 并行执行模型。

[mrdrivingduck]

这是一篇深刻影响现代 DBMS 设计的论文。Volcano 严格来说不算一个 DBMS，而是一个查询执行系统，因为其中并没有用户友好的 UI、查询语言、类型系统、优化器、catalog 等。Volcano 完成了以下设计特性：

1. 模块化、可扩展设计
2. 不对数据模型作出任何假设，查询处理基于参数化的算子实现
3. 在基于单进程实现的算子上实现基于 shared memory 的并行化，并行处理与数据操纵无关
4. 使用 mechanism 来支持 policy
5. 实现了两个不对数据发生 manipulation 的 meta 算子

[mrdrivingduck]

Volcano System Design

Volcano 包含两层：

1. 文件系统层：包含记录、文件、索引扫描操作，缓冲区管理
2. 查询处理层：查询处理模块，可以被组织为复杂的查询处理树

The File System

缓冲区管理器只提供 mechanism，比如保持页面、读写 disk page 等；而更高层的软件根据数据的敏感性、重要性、访问模式来决定如何使用这些 mechanism 的 policy。Volcano 中大量使用了这种 mechanism 和 policy 分离的设计策略，从而实现高度的模块化。

文件系统的扫描实现了两套接口。其中一套是标准的文件扫描接口：open、next、close、rewind，为了快速创建文件，还实现了 append。另外，扫描还支持可选的 predicate 函数——由返回下一条记录的 next 调用，并传入参数和记录地址。Predicate 的 support function 以函数指针的方式传递给算子，算子本身并不关心其中具体的逻辑，从而实现了更好的扩展性。

传递给 support function 的参数可以以两种方式被使用：

1. 编译查询执行：support function 已经被编译为机器代码，那么参数可以直接传递常量或指针
2. 解释查询执行：参数可以被用于指向解释器的特定代码，而 support function 函数指针指向的是解释器的入口地址

编译执行和解释执行被实现在了单一的 mechanism 中，由上层 policy 决定使用编译执行还是解释执行。这里又体现了 mechanism 和 policy 分离的设计思想。

Query Processing

在 Volcano 中，所有的代数物理算子（与逻辑算子相区分）都被实现为 迭代器模式：它们遵循包含 open-next-close 三个操作协议。分别对应了：首先进行初始化，然后进行循环和递增直到到达循环结束条件，最终进行收尾的三个过程。与每个迭代器相对应的是一个 state 记录，包含了 open 操作中需要用到的参数和状态。

所有对数据对象进行操作和解释的功能都以函数指针的形式提供给物理算子，具体逻辑实现在 support function 中。每个 support function 使用一个参数来标识是进行解释执行还是编译执行。

迭代器（算子）之间可以嵌套，从而以类似子函数的方式被使用。对应地，state 记录也需要通过孩子指针链起来。

使用这种标准的迭代器接口，Volcano 的算子不需要知道它的下层算子是什么类型的，下层算子的记录是如何产生的，只需要调用下层算子的 next 函数即可。这种概念被称为 anonymous inputs 或 streams。Streams 是一个简单但强大的抽象，可以使任意数量和种类的算子节点组合起来，从而执行一个复杂的查询。这是本文提供的核心执行模型。

从最顶层的算子开始调用 open，将会初始化对应的 state，然后对它的下层算子调用 open。这样，查询中的所有迭代器都被递归地初始化了。为了执行查询，在最顶层算子调用 next 直到它返回 end-of-stream 为止。当需要更多数据时，最顶层的算子将会调用下层算子的 next。最终，close 将会递归关闭所有迭代器。

一些和查询与环境相关的参数可能会影响 open 阶段的行为，比如用于过滤数据的常量，或是一些系统负载信息。这些参数被称为 bindings，可以以无类型指针的形式传递给所有迭代器，用于 policy 决策。Policy 决策也是以 support function 的形式实现的，比如可用于动态决定 hash join 时的 hash 表大小。

综上，通过将算子实现为迭代器，实现了对树形的查询计划的需求驱动（demand-driven）查询。

[mrdrivingduck]

Dynamic Query Evaluation Plans

查询优化器需要对系统中可用资源进行估算，最终查询计划的优劣性直接受估算准确性的影响。Volcano 提供了一个可以避免优化器不准的方法：动态查询计划选择。

在 Volcano 中，引入了一个也被实现为迭代器模式的 choose-plan 算子，它不会对数据有任何操作，所以是一个 meta 算子。该算子的 open 操作决定下属的哪一个子计划树应当被执行，并调用被选中子计划树的 open。该算子的 open 操作调用 support function 来决定使用哪个子计划，并传入 bindings 作为参数。next 和 close 就是简单地调用被选中子计划的 next 和 close。

对上面这张图来说，索引扫描和文件（顺序）扫描在查询不同变量时速度不一样。当索引非聚簇，且选择率较高（一大堆行将会被返回）时，顺序扫描速度更快，否则索引扫描更快。优化器可以为这两种情况准备不同的执行计划，在查询执行时动态选择不同的查询计划可以在两种场景下都收获不错的性能。

Choose-plan 算子虽然能够实现计划的动态选择，但它并不关心具体选择哪个计划，而是直接调用实现了计划选择 policy 的 support function，因此算子本身只提供了 mechanism。这也是 mechanism 和 policy 分离设计的一个体现。

[mrdrivingduck]

Multiprocessor Query Evaluation

关系型查询处理系统中能够相对容易使用并行的主要原因：

1. 查询处理以表达式树流水线的形式表示，可以实现 算子间并行（inter-operator parallelism）
2. 每个算子内消费或产生的数据可以被分片为不相交的集合，从而实现 算子内并行（intra-operator parallelism）

Volcano 的目标是不修改所有已有的单进程查询处理代码，所有的并行化问题都在一个提供标准迭代器接口的算子内解决，该算子在 Volcano 中被称为 exchange 算子。由于实现了标准的迭代器接口，因此这个算子可以被插入在计划树的任何位置上：

Vertical Parallelism

所谓垂直并行即进程间的流水化。Exchange 算子的第一个功能就是提供垂直并行能力。算子的 open 操作在共享内存中创建了一个叫做 port 的数据结构用于同步和数据交换，然后将创建一个新进程。子进程是父进程的完整拷贝，但是在 exchange 算子中将进入两个不同的路径：父进程将成为 consumer，子进程将成为 producer。

消费者进程中的 exchange 算子也是一个迭代器，唯一的不同是它获取数据的来源是不是递归调用下层迭代器，而是来自进程间通信。当消费者的 open 成功创建子进程后，next 将等待数据到达 port 中并返回，close 将通知生产者可以关闭，并等待回复确认。

生产者进程中，exchange 算子负责驱动在其之下的计划树算子的 open、next、close。next 输出的结果将会被汇集到数据包中，当数据包被填满时，将会被插入到共享内存 port 中的链表里，然后通过信号量通知消费者。当输入枯竭时，生产者 exchange 算子将会在数据包中放入一个 EOF 表示没有更多数据了。

通过一个额外的信号量，生产者和消费者之间可以做到流量控制 / 背压。当生产者明显快于消费者时，为了防止共享内存 buffer pool 中过多的记录被锁定，在生产者产生一个数据包后，必须等到消费者将数据包消费完后释放信号量，生产者才可以继续产生下一个数据包。信号量的数值决定了生产者可以领先消费者多少个数据包。

Horizontal Parallelism

所谓水平并行分为两类：

• Bushy parallelism：不同 CPU 执行不同的计划子树，也是一种进程间并行
• Intra-operator parallelism：多个 CPU 在同一个算子上对不同的子集并行操作

Bushy parallelism 能够通过在计划树中插入 exchange 算子轻易实现。

算子内并行需要实现数据分区，是通过使用多个文件实现的。中间结果的分区是通过在 port 中分配多个队列实现的，如果有多个消费者进程，那么它们使用 port 中各自的队列。对于生产者来说，它们使用 support function 来决定把记录输出到哪一个队列中。Support function 的引入意味着可以实现轮转分区、key 值范围分区或 hash 分区。

水平并行需要的条件：在 exchange 算子的 state 中需要有 degree of parallelism，并且还需要提供 support function 来决定把扫描结果发送到哪个进程。如果一个进程组执行同一个算子，那么当计划树被 open 时，唯一正在运行的进程将会成为 master。当 master 以生产者-消费者模式 fork 出一个子进程后，子进程将会成为它所在进程组中的 master。这个 master 生产者进程的第一个动作是调用 support function 决定需要 fork 出多少个 slave 进程——如果需要并行执行，那么 master 生产者将会 fork 出其它 slave 生产者进程。其它生产者进程被创建后，除了访问共享数据结构以外，将不需要更多的同步。

当 close 递归传播至 exchange 算子时，消费者进程使用信号量通知所有的生产者关闭。

Variant of the Exchange Operator

在一些场景中，生产者需要将输出广播给所有消费者。

Exchange 中的输入记录可以根据它们的生产者而分开存放，从而实现 merge。