（论文阅读-优化器）Volcano-An Extensible and Parallel Query Evaluation System

摘要

一、简介

三、火山模型系统设计

3.1 文件系统

3.2 查询处理

四、扩展性

五、动态查询评估计划

六、多处理器查询评估

6.1 垂直并行化

6.2 水平并行化Horizontal

6.3 exchange operator的变体

6.4 文件系统修改

七、总结

摘要

火山模型Volcano在数据库查询系统的设计中，为查询优化、并行执行和资源收集提供了丰富的环境。

火山模型在代数运算符之间使用了一个标准接口，允许简单地添加新运算符和实现运算符。火山模型极具扩展性，它对于新的算子、算法、数据类型和限定类型的方法都提供了极大的扩展性。

火山模型包含两个新颖的元操作符：

choose-plan元操作符支持动态的查询评估计划，可以通过延迟执行进行优化。
exchange-plan元操作符支持分布式数据集内部的操作符并行，以及横向和纵向的操作符并行。在需求驱动的数据流和数据驱动的数据流的进程之间进行转换。

除了exchange operator外，所有的operator，都是以单进程环境作为前提设计的，通过exchange operator来进行并行化。通过operator的组合，使得数据操作和并行化能够得到很好的结合。火山模型是第一个有效地结合了扩展性和并行性来实现的查询引擎。

一、简介

火山模型的设计目的是为查询执行技术和查询优化启发提供实验工具，而不是提供一个直接可以支持上层应用的数据库系统。相对于一个完整的数据库系统，它缺少了用户友好的查询语言、数据类型定义、查询优化器和catalog。

处于火山模型的研究目的，它具有以下几个特点：

首先，它是模块化的和可扩展的，以支持未来的研究。
设计足够简单，以允许学生使用和研究
不预设数据模型，唯一的假设是查询流程是基于一组参数化的opeartor之间的转换实现的。
从复杂的并行性中解放算法设计、实现、调试、调优和初始试验，而允许进行并行查询处理的试验。
火山模型在查询执行范式上进行了实现，以确保学生学习如何在商业数据库产品中真正进行查询处理。

火山模型可以用于一个独立的进程，或是一个并行系统中。单进程查询评估计划已经可以很容易地在共享内存机器上并行化，很快也可以在分布式内存机器上并行化。

遵循了在操作系统研究中已经确立但在大多数数据库系统设计中没有被利用的设计原则，Volcano提供了支持策略的机制。策略可以由实验人员设置，也可以由查询优化器设置。机制和策略的分离促进了现代操作系统的可扩展性和模块化，并可能对可扩展的数据库系统作出同样的贡献。我们将在本文中反复地回到这种分离。

出于火山模型对未来扩展性和研究的目标，它在不断地扩展和修改。这其中最重要的扩展性在于两个元操作符的扩展。它们不仅是新的操作符，而且包含并封装了用于查询处理的新概念。它们是元操作符，因为它们对数据操作、选择、派生等没有贡献，而是提供了对查询处理的额外控制，而传统操作符(如文件扫描、排序和合并连接)无法提供这些控制。

choose-plan选择计划操作符实现了动态查询评估计划，这是为必须使用不完整信息进行优化的查询而开发的概念。例如，如果查询谓词中的某个常量实际上是程序变量，因此在编译和优化期间未知，则不可能可靠地优化嵌入式查询。动态计划允许准备多个等效的计划，每个计划对一定范围的实际参数值最优。choose-plan在运行时在这些计划中进行选择，而Volcano操作符集中的所有其他操作符(现在或将来)完全忽略了选择计划操作符的存在和功能。

第二个元操作符，exchange operator，在火山模型中实现并控制了并行查询评估。exchange operator能够跨越进程和处理器的边界来进行数据交换，所以其他的operator都无需考虑并行性，类似分区和流控制等并行特性都可以交给exchange operator来执行。

注意，火山模型所提供的两个元操作符：choose和exchange，它们的主要目的是对查询流程进行控制。

三、火山模型系统设计

当前火山模型是一个有20多个模块的C库，这些模块包含了文件系统、缓存管理、排序、B+ tree、自然join的两种实现算法（sort/ hash）,各种其他join、聚合、重复消除、各种关系代数等等。此外，还有两个模块实现了动态查询评估计划并且能够实现以上所有算法的并行执行。

火山模型中的通用且不断出现的主题是，它的设计中提供了查询评估机制，以允许策略的选择和试验。机制和策略的分离在操作系统的设计和实现中是一种广为人知和非常稳固的准则，但它还没有被持续扩展地应用在数据库系统中。它对现代操作系统的可扩展性和模块化做出了重大贡献，并可能对可扩展的数据库系统做出同样的贡献。

操作系统设计的重要原理是策略（policy）和机制（mechanism）的区别

机制与策略

当前，火山模型由两层组成，文件系统层和查询处理层。前者提供了记录、文件和索引操作，包括携带可选谓词的scan操作，以及缓存机制；后者是一组查询处理模型，它们可以嵌套来构建一个复杂的查询评估树。

火山模型不包括系统catalog或是数据字典，这是由于扩展性和数据模型独立的目标所致。

3.1 文件系统

在我们对Volcano文件系统的讨论中，我们同样从下往上进行，从缓冲区管理到数据文件和索引。

缓冲区管理Buffer manager是文件系统中最有趣味的一部分，因为缓冲区管理在任一个数据库系统中都是性能关键点。火山模型的缓冲区管理设计目标是包含一些机制，这些机制可以在多种环境中使用得最有效，并具有广泛的策略。这样设计目标的结果是，火山模型的缓冲区管理包含了多个缓冲池，在火山模型中称之为cluster的变长缓冲单元，以及上层应用的替换特性。

缓冲区管理的特性是火山模型中一个非常优秀的通过实现机制mechanism来支持多策略policies的案例。缓冲区管理只提供机制，例如，pinning，page replacement，读写磁盘页，与此同时上层的软件根据数据语义、优先级和访问模式来定义策略policies。令人惊讶的是，数据库缓冲区管理器从观察到的引用行为中得出替换决策，尽管这种行为是由更高级别的数据库软件生成的，因此在同一系统中，尽管是不同的子组件，但在事先是已知和可预见的。

文件Files由记录、集群和区段组成。由于文件操作在任何数据库系统中都被非常频繁地调用，因此文件模块中的所有设计决策都是为了提供具有最高可达到的性能的基本功能。cluster由一个或多个page组成，是I/O和缓冲的单位，如上所述。cluster大小是为每个文件分别设置的。因此，同一设备上的不同文件可以具有不同的集群大小。文件的磁盘空间是在物理上连续的区段中分配的，因为区段允许非常快的扫描而不需要寻找和大块的预读和后写。

记录Record都具有一个唯一id，为了快速访问大量记录，Volcano不仅支持单个文件和记录操作，还支持扫描，支持迭代读和追加append操作。文件扫描有两种实现接口，一种是文件系统级别的扫描，另一种则是查询处理级别的操作。前者具有文件扫描的标准程序，即open，next，close以及rewind。next操作会返回下一个记录的主存地址。

为了支持快速的file创建，scan操作支持append。

同样，scan操作也支持可选的谓词predicate，predicate function是在next操作中调用的，输入参数是一个记录的地址。选择性扫描selective scan是引言中简要提到的支持函数support functions的第一个例子。sacn机制依赖于从更高级别导入的谓词函数predicate function，而不是它的限定本身。

support function会作为一个函数入口以及一个作为谓词参数的无类型指针传递给一个操作。以两种不同的查询执行过程：编译型查询过程compiled query execution和解释性查询过程interpreted query execution为例，在编译型查询过程中，参数会用来传递常量指针给机器码，而在解释型执行过程中，则是将对应的代码传递给解释器。

Volcano对support function及其参数的使用是另一种机制mechanism的例子，这种机制让决策(在这种情况下是使用编译扫描还是解释扫描)留给更高级别的软件来决定。

索引Indices当前只实现了B+tree，通过类似于file的一个接口。

总之，Volcano的大部分文件系统在其目标上是传统的，但以一种灵活、高效和紧凑的方式实现。文件系统支持基础的抽象和操作，即device、file、record、B+ tree 以及scan，提供了访问这些对象的机制，将策略留给上层软件。在这些机制的设计和实现中，高性能是一个非常重要的目标，因为只有在底层机制有效时，性能研究和并行才有意义。

3.2 查询处理

上述的文件系统设计在查询处理过程中充分利用，以实现复杂的查询。查询被表示为查询计划或代数表达式; 这些代表着查询处理算法的代数表达式我们称之为可执行代数，也称为关系代数，和逻辑代数相反。然而，我们必须指出，这些操作可以被看作是对一组对象的操作，并且火山并不依赖于对这些对象的内部结构的假设。实际上，我们试图使用火山模型在对象数据库系统之上进行查询处理。使用火山模型的关键点在于将对数据对象的处理和解释隔离开来。

在火山模型中，所有的代数运算符都是以迭代器的方式实现的，它们支持了一个简单的open-next-close协议。

所有对数据对象的操作和解释，例如比较和hash，都会通过指向对应的support function入口指针来传递给迭代器。这些support function会使用参数来进行解释或是编译的查询评估，例如前面提到的file scan predicates。如果没有support function，火山模型的迭代器将会是一些不会执行任何有效工作的空的算法外壳。实际上，分成算法外壳和支持函数support function将对于记录或对象的解释，和对于集合的控制和迭代进行了分离。这种分离是Volcano数据模型独立性和可扩展性的基石之一。

迭代器可以进行嵌套，像协程一样执行。使用火山模型的标准迭代器，一个运算符无需关注什么类型的运算符生产的它的输入，或是它的输入是从一个复杂的查询树还是一个简单的file scan中产生的。我们称这个概念为匿名输入anonymous input或是流streams。流Streams是一个简单但是非常强大的抽象，它可以结合任意数量任意类型的操作符来执行一个复杂的查询，是火山模型扩展性的第二块基石。与迭代器控制范例一起，流代表了单进程查询计算的时间(同步操作符的开销)和空间(必须同时驻留在内存中的记录数量)方面最有效的执行模型。

在火山模型中，一个查询中的所有迭代器是递归初始化open的。同时为了执行查询，根节点的运算符会一直调用next方法，直到流Stream消费完成。最终，close方法的调用也会查询的迭代器中递归调用。

对于一些在查询评估计划中，可能影响策略policy决定的查询和环境变量参数，例如，查询谓词常量和系统负载信息，在火山模型中会使用一个叫bindings的参数来再所有的open程序中进行传递。这些策略policy的决定同样是使用support function来实现的。bindings参数在动态查询评估计划中是非常有用的。

迭代器的next record结构中，operator之间需要传输完整的数据记录。为了节约资源使用，operator可以尽可能地进行数据复用，例如，join operator可以直接在检索到的record上构建它的输出record，而不是重新构建一条完全新的record。但是，尽管这样的操作能够减少内存拷贝，但它在火山模型中没有被显式地实现，因为火山模型已经提供了必要的机制mechanism，即filter （Biter？）operator，它可以用RID指针对替换流中的每条记录（下一章节中详细介绍），反之亦然。

总的来说，需求驱动的数据流是通过将operator编码为iterator的方式实现的，例如，通过open，next和close程序，因为这种方案保证了通用性、可扩展性、效率和低开销。

下面是一些火山模型当前已有的迭代器，火山模型在极少数模块中，所描述的操作符通过通用性和机制和策略的分离提供了其他查询评估系统的大部分功能。

Scans, Functional Join, Filter：
One-to-One Match：在单个算子中实现了连接、半连接、外连接、反连接、交、并、差、反差、聚集和消除重复。一对一匹配操作符是类似sort的物理操作符，即可执行代数的一部分，而不是像关系代数的操作符那样的逻辑操作符。它是一种操作符，根据两个项目之间的比较结果，实现输出中包含一个项目的所有操作。
One-to-Many Match：在one-to-one match算子中，输出的元素取决于两个元素的对比结果，而one-to-many match算子将每个元素与其他元素对比以决定是否需要产生一个新的元素。一个典型的例子就是关系切分relational division。火山模型中关系切换有两种形式，一种被称为native division，基于排序，另一种被称为hash division

四、扩展性

许多数据库的研究工作都致力于提高扩展性，接下来我们讨论几个在数据库领域中频繁被提出的扩展性问题，以及说明它们是如何在火山模型中实现的。

对象类型的扩展：火山模型并没有提供对象的类型体系，因此新增一个抽象的数据类型对于火山模型来说是不受影响的。所有对独立对象的操作和计算都是通过support function来完成的。在某种程度上，火山模型是不完全的（它并不是一个数据库系统），但通过分离集合运算和实例的解释性操作，以及通过提供一个它们之间良好定义的接口，火山模型在实例类型和语义层面上具有内在的可扩展性。
函数的扩展（独立对象函数或聚合函数）：火山模型通过support function来使得查询处理路径不受support function的语法影响。火山模型只提供通过stream处理对象及合的抽象和实现。
访问模式的扩展（access mode）：为了实现新的访问模式，就需要扩展多维索引以及对应的迭代器。迭代器中不仅可以检索数据还可以维护存储结构。例如，如果一组通过谓词（或是选择）操作定义的元素集合需要被更新，那么查询树中实现这个选择性的迭代器可以将它的数据输入到维护存储结构的迭代器中。来充分利用存储格式带来的访问模式的扩展。
查询处理算法扩展：在火山模型的迭代器模型中，新的算法实现必须提供迭代器的处理程序open、next、close，并且必须使用这些处理程序来处理它的输入流。在算法已经按照这种方式实现后，它和火山模型的融合成本就微不足道了。火山模型通过这种迭代器模式能够支持越来越复杂的查询处理。
前端交互扩展性：前端交互扩展性是为了降低使用成本。当前火山模型使用了两套交互方式，一个是基于火山模型可执行代数的、未经过优化的命令解释器，另一个是使用了新的优化生成器实现优化的，基于逻辑代数或是微积分语言的交互方式。火山模型使用便利的方式来执行优化转化。我们也会使用优化交互来进行动态查询评估计划的实验。

总的来说，由于火山模型的模块化设计，以及它天然的扩展性，我们可以说它不存在扩展性方面的问题。但是需要注意的是，火山模型仅仅是数据库系统中的一部分，也就是查询执行inquiry，因此它只解决了可扩展性问题的一个子集，而忽略了另一个子集。火山模型假设它的查询评估计划和support function是正确的。

火山模型作为一个可扩展的查询评估系统来说的关键之处在于它提供了一种简单但非常有效的机制来实现高效的查询处理，并且它可以作为一个弹性的研究工具。

五、动态查询评估计划

在大多数数据库系统中，使用传统编程语言编写的程序内嵌查询通常是在程序编译时进行优化的。查询优化器必须对查询中作为常量出现的程序变量和数据库中的数据进行假设。同时优化器必须考虑查询执行过程中的资源信息，例如处理器的数量、缓冲区的大小等等。如果一个查询评估计划在一段时间中被频繁使用到，那么决定何时对它进行重新优化是非常重要的。

火山模型中包含的元操作符choose-plan operator同时支持了多样化的访问路径和动态执行计划。在某种意义上，它不是操作符，因为它不执行任何数据操作。因为它提供了对查询执行的控制，所以它是一个元操作符。这个元操作符同样遵循了open-next-close协议，因此可以插入到查询执行计划的任何位置。Open调用了这个策略决定对应的支持函数support function，将前面提到的binding参数传递给这个support function。next和close操作则只是为打开期间选择的输入调用适当的操作。

注意，choose-plan operator不做决定哪些执行计划需要执行的策略决策policy desicion，它只是提供了动态查询评估的机制mechanism。策略是通过support function来实现的。

choose-plan operator在查询优化和评估中提供了非常重要的自由度，只需要极少的代码。由于它与查询处理的范式是兼容的，因此它的存在根本不会影响其他操作符。并且可以以一种非常灵活的方式使用。

operator是另外一个例子，它为火山模型的设计原则提供了能支持多种策略的机制。我们在设计和实现并行查询评估时使用了同样的原理。

六、多处理器查询评估

大量的研究表明，在过去十年汇总，基于关系数据库系统的查询处理过程从并行算法中显著获益。

并行化在关系查询处理系统中相对容易被利用的主要原因为以下节点：

查询处理过程使用了一个树形结构的operator来执行，可以通过pipeline（操作符间并行）的方式在多个分离的进程和处理器间进行连接
每一个operator消费并输出一个集合，这个集合可以被分区（partition）或是切分（fragment）划分为多个不相交的子集以进行并行处理（操作符内并行）

注意，关系型数据库中并行化容易实现的原因和关系型数据模型无关，只要求查询处理过程通过一个opeartor树执行对数据集合的处理。而这正是设计火山模型时所做的假设，因此在Volcano中并行化可扩展查询处理是合乎逻辑的。

当火山模型被移植到一个多处理器机器中时，使用当前已有的单进程查处理代码来并行执行，而不做任何改动时是非常有必要的。这样我们得到的结果是非常清晰的、自调度的并行处理。我们将这种新的方法为并行化查询评估引擎的operator模型( the operator model of paralleliziing a query evaluation engine )。

在这个模型中，所有的并行性问题都局限在一个operator中，这一个operator为查询树中的前置和后置operator都提供了标准的迭代器接口。

负责并行执行和同步的模块在Volcano中称为交换迭代器exchange iterator。它同样遵守了iterator的open, next, close协议，因此，它和choose-plan operator一样，也可以在一个复杂查询树的任意一个地方或是多个地方插入，如下图所示。

exchange operator显著增强了火山模型的能力。实际上，它代表了并行查询执行中的一个新概念，在并行化现有的商业数据库产品和可扩展的单进程系统方面很可能是有用的。

6.1 垂直并行化

exchange提供的第一个方法是进程间的pipeline，或者称为垂直并行化。exchange的open方法在共享内存中创建了一个为同步和数据交换服务的数据结构后，创建了一个新的进程。子进程是父进程的完全副本。exchange 操作符在父子进程中采取不同的路径。

在火山模型中，父进程是消费者，子进程是生产者。消费者中的exchange operator以一个正常的迭代器执行，和其他迭代器的唯一区别是它通过进程间通信来接收它的输入，而不是通过迭代器调用。在创建子进程之后，消费者中的open_exchange过程就完成了。Next_change会等到从网络通信接口接收到的数据，并每次返回一行记录。Close_exchange通知生产者它可以关闭了，等待ack并返回。在生产者进程中，exchange operator会通过在它的input基础上使用open、next和close方法，成为它下面查询树的驱动器driver。next方法的输出，及一组Next-Record结构体，会封装为包packet，packet的大小是exchange iterator状态记录的参数，可以设置为1~32000之间。当packet被填满后，，它会被插入到来自该端口的链表中，并使用一个信号量来通知消费者新数据包的信息。包中的记录固定在共享缓冲区中，必须由消费操作符解除固定。（网络通信过程s）。当input被消费完成后，生产者端的exchange operator会使用一个end-of-stream tag标记最后一个packet，传递给消费者，并等待消费者关闭所有open的文件。火山模型中的延迟关闭是必须的，因为记录会被锁定在缓冲区。这是由于火山模型的缓冲区设计决定的，和并行计算模型上的exchange iterator无关。

如下图所示，exchange operator创建了进程，同时在两个进程的边界执行，通过operator的工作过程隐藏了进程的存在边界。

同样，在火山模型中，exchange operator只是提供了并行查询评估的机制mechanism，更多的实现选择，即策略policy可以被扩展实现。

在exchange的实现过程中，根据其他模块的驱动方式可以分为数据驱动（被动接收数据）和需求驱动（主动请求拉数据），数据驱动相对于需求驱动来说可以减少控制通信的开销。由于非常高的并行度和非常高性能的查询评估需要一个紧密联系的网络，例如共享内存机器的超立方体，火山模型决定使用一个已被证明在“无共享”数据库机器中表现良好的数据交换范例，即数据驱动模式。在数据驱动的运行时交换过程中，需要完善的流控和背压机制，及需要额外的控制信号传输。

6.2 水平并行化Horizontal

水平并行化有两种形式，我们称之为bushy并行化和intra-operator并行化（算子间并行）。在bushy并行化体系中，不同的CPU执行复杂查询树的不同子树。bushy并行和垂直并行是算子间并行的两种形式。算子间并行意味着不同CPU执行同一operator在不同数据集和中间计算结果上的计算。

bushy并行化可以通过在查询树中增加一或两个exchange operator来很简单地实现。

算子间的并行化要求对数据进行分区。

6.3 exchange operator的变体

在许多情况下，我们上文中描述的exchange oeprator都需要进行一些修改或是扩展。这里对于exchange operator的典型扩展operator如下：

broadcast
并行排序（merge sort）

6.4 文件系统修改

保缓冲区管理器不会成为共享内存机器中的瓶颈是一个独立于数据库查询处理的有趣子项目[181]。缓冲区管理器中的并发控制旨在为将来使用有效和高效的机制进行研究提供一个试验台，而不是破坏策略和机制的分离。

七、总结

火山模型的设计和实现遵循了一下几个简单却有效的原则：

机制和策略的隔离：火山模型重点实现了能支持应用层自定义或是查询优化策略policy的机制mechanism
迭代器计算模型：operator以迭代器iterator的模式实现，允许单进程中的有效数据传输和控制
标准operator接口：支持新的查询operator和算法的扩展性和继承
计算模型独立：stream元素的解释和操作允许了数据模型和数据类型的扩展
并行性封装：封装并行实现允许将单进程环境的算法并行执行

火山模型引入了两个新颖的meta-operator，来控制查询流程。同时引入了动态查询评估计划。

火山模型在进程内和进程间都很好地使用了的dataflow技术：

在进程内，通过stream和iterator实现了demand-driven dataflow，在单进程的查询评估中获得了最有效的时间和空间执行模型。
在进程间，通过data-driven dataflow实现了生产者和消费者之间的高效数据传输。同时可以按需使用流控和背压

将并行性控制的所有问题封装在一个exchange操作符中，从而使数据操作和并行性正交化，这提供了重要的可扩展性和可移植性优势。要并行化一个新的operator，只需要将它与查询执行计划中的exchange operator结合起来。

许多特性使Volcano成为进一步性能研究的有趣对象：

LRU/MRU缓冲区替换机制
在单个设备上使用不同大小的集群，并通过动态分配缓冲区空间而不是静态分配来避免缓冲区变换，这需要精确的计算和控制
基于sort和基于hash的查询处理算法及实现的时间和负载开销对比，值得进一步探索
Volcano允许测量并行算法的性能，并识别共享内存体系结构上的瓶颈
评估分布式内存查询处理(如在GAMMA中使用)中单独调度器进程的优点和缺点
在data-driven的dataflow被证明在无共享机制的数据库机器上表现良好后，应该在共享内存计算机上的网络上探索demand-driven和data-driven的dataflow的组合