原文：The Volcano Optimizer Generator: Extensibility and Efficient Search
The Volcano Optimizer Generator: Extensibility and Efficient Search 论文翻译。
2023.01.25 —— by zz
【中括号内为译者注】
对原文部分关键术语，或重点句有加粗。便于定位。
为了避免英文和中文对应时的歧义问题，部分中文用小括号标注了英文对应词。
这篇论文给出了一个独立任何数据模型的查询优化器生成器（volcano）的设计架构描述。其提出的概念架构大多经历了时间的考验，现在仍然在使用。volcano是查询优化器设计演进中的一个里程碑。
概述
数据库应用领域的新需求不仅包含新功能，还包含高性能。为了满足这两个要求，Volcano 项目提供了高效（efficient）、可扩展（extensible）的查询和请求处理工具，尤其是面向对象和科学数据库系统。其中一个工具是一个新的优化器生成器。数据模型、逻辑代数、物理代数和优化规则由优化器生成器翻译成优化器源代码。与我们早期的 EXODUS 优化器生成器原型相比，搜索引擎（search engine）的扩展性和功能性更强；它为非平凡的 代价模型（cost model）和物理属性（physical properties）提供了有效的支持，比如排序顺序（sort order）。同时，它结合了动态规划（该方法至今仅用于关系的 选择-投影-连接（select-project-join，SPJ） 优化）、目标导向搜索（goal-directed search）和 分支定界修剪（branch-and-bound pruning），因此效率更高。与其他基于规则的优化系统相比，它提供了完全的数据模型独立性和更自然的可扩展性。
简介
虽然可扩展性是许多当前数据库研究项目和系统原型的重要目标和要求，但不能因为两个原因而牺牲性能。首先，存储在数据库系统中的数据量持续增长，在许多应用领域中远远超出了大多数现有数据库系统的能力。其次，为了克服科学计算等新兴数据库应用领域的可接受性问题，数据库系统必须与当前使用的文件系统有至少达到相同的性能。附加的数据库管理软件层必须与这些通常不使用数据库的应用领域中，使用数据库的所产生性能的性能提升相平衡。优化和并行化是提供这些性能优势的主要选项，用于优化和并行化的工具和技术对于更广泛地使用可扩展数据库技术至关重要。
从许多研究项目，即 Volcano 可扩展并行查询处理器 [4]、REVEVLATION OODBMS 项目 [11] 和科学数据库中的优化和并行化 [20] 以及协助其他研究人员的研究工作，我们已经建立了一种新的可扩展查询优化系统。我们使用 EXODUS 优化器生成器的早期经验并没有形成定论。虽然它已经证明了优化器生成器范式(optimizer generator paradigm)的可行性和有效性，但很难构建高效的、达到生产质量的优化器。因此，我们设计了一个新的优化器生成器，需要对 EXODUS 原型进行几项重要改进。
首先，这个新的优化器生成器必须既可以在 Volcano 项目中使用现有的查询执行软件，也可以作为独立工具在其他项目中使用。其次，新系统必须更高效，无论是优化时间还是搜索的内存消耗。第三，它必须为排序顺序和压缩状态等物理属性提供有效（effective）、高效和可扩展的支持。第四，它必须允许使用启发式和数据模型语义（heuristics and data model semantics）来指导搜索并修剪搜索空间的无用部分。最后，它必须支持灵活的代价模型，允许为不完全指定（specified）的查询生成动态计划。在本文中，我们描述了 Volcano Optimizer Generator，它将很快满足上述所有要求。第 2 节介绍了 Volcano 优化器生成器的主要概念，并列举了用于定制新优化器的设施（facilities）。第 3 节详细讨论了优化器搜索策略。第 4 节比较了 EXODUS 和 Volcano 优化器生成器的功能、可扩展性和搜索效率。在第 5 节中，我们描述和比较了可扩展查询优化的其他研究。我们在第 6 节中提供了我们从这项研究中得出的结论。
【注意高效指的是时间空间上的效率高，通过优化算法可以达到。有效指的是达到最终目标的程度。从优化器整体也就是最终plan结果好坏，是和搜索空间范围相关。从优化单步搜索过程角度看是指不会搜索一些注定不需要的结果。可扩展这里指软件模块增加功能的能力，也就是优化器面向新需求开发和维护的难易程度】
2. 从外部看 Volcano 优化器生成器
在本节中，我们将描述实现数据库系统及其查询优化器的人所看到的 Volcano 优化器生成器。 重点是为优化器实现者提供的广泛设施，如 Volcano 优化器生成器设计的模块化和可扩展性。 在考虑了 Volcano 优化器生成器的设计原则之后，我们讨论了生成器的输入和操作。 第 3 节讨论了由 Volcano 优化器生成器生成的优化器使用的搜索策略。
图 1 显示了优化器生成器范例。 在构建 DBMS 软件时，一个模型规约（model specification）【specification 指确定行为的说明材料，有规范，规格，规约三种用词选择，这里选择'规约'】被翻译成优化器源代码，然后编译并链接与其他 DBMS 软件，如查询执行引擎等。 其中一些软件是由优化器实现者编写的，例如代价函数（cost function）。 在将数据模型描述翻译成优化器的源代码后，生成的代码将被编译并与作为 Volcano 优化软件一部分的搜索引擎链接。 当 DBMS 运行并输入查询时，查询被传递给优化器，优化器为其生成优化计划。 我们称指定数据模型并实现 DBMS 软件的人为“优化器实现者（optimizer implementor）”。 提出要由数据库系统优化和执行的查询的人称为 DBMS 用户。
2.1. 设计原则
系统中包含五个基本设计决策，它们有助于使用 Volcano 优化器生成器设计和实现的优化器的可扩展性和搜索效率。我们依次解释和证明这些决定。
【在本文中，'算法'指物理运行时实现上使用的程序（大致对应于 calcite 中的 physical operator），'运算符' 指SQL对应的关系代数运算符（大致对应于 calcite 中的 logical operator）】
首先，虽然关系系统中的查询处理一直基于关系代数，但越来越清楚的是，在可扩展和面向对象系统中的查询处理也将基于代数技术，即通过定义代数运算符(algebra operators)、代数等价律(algebraic equivalence)，以及合适的实现算法(implementation algorithms)。最近提出了几个面向对象的代数，例如[16-18] 等等。他们的共同点是代数运算符使用一个或多个批量类型(bulk type)（例如，集合、包、数组、时间序列或列表）并生成另一个适合作为下一个运算符的输入的类型。这些系统的执行引擎也基于代数运算符，即 消费(consume)和生产(produce) 批量类型 的算法。但是，运算符集和算法集是不同的，选择最有效的算法是查询优化的中心任务之一。因此，Volcano 优化器生成器使用两个代数，称为逻辑代数和物理代数，并生成将逻辑代数（查询）表达式映射到物理代数表达式（由算法组成的查询求值计划(query evaluation plan)）的优化器。为此，它使用逻辑代数中的变换（transformations）和逻辑运算符到算法基于代价的映射。【transformations或译作转换。转换更多指类型发生变化的整体变化，变换更多指类型不变的局部变化。逻辑代数内部的变化称为变换更合适，到物理代数的映射过程称为转换/实现可能更合适】
其次，规则（rule）被确定是一种简洁和模块化的方式指定有关 模式(patten) 的知识的通用概念（general concept），并且查询优化中的等价变换（equivalence transformation）所需的 代数定律知识 可以很容易地使用 模式 和 规则 来表达。因此，大多数可扩展查询优化系统都使用规则，包括 Volcano 优化器生成器。此外，对独立规则的关注确保了模块化。在我们的设计中，规则翻译相互独立，并且仅在优化查询时由搜索引擎组合使用。考虑到查询优化是任何数据库系统概念上最复杂的组件之一【为什么说是最复杂？】，模块化本身对于优化器的初始构建和维护都是一个优势。
第三，查询优化器可以将 查询 映射到 最佳等效查询求值计划，在 Volcano 优化器生成器的输入中表示为 代数等价。其他系统在将查询变换为计划时使用多个中间级别【或者叫做中间层级，总之是多个阶段的含义】。例如，Starburst 可扩展关系数据库系统的基于代价的优化器组件使用具有多级“非终结符（non-terminals）”的“扩展语法（expansion grammar）”，例如交换二元连接、非交换二元连接等 [10]。我们认为，多个中间层以及需要重新设计新的或扩展的代数使得多个等价性上的议题(issue)被混淆，比如定义对优化器 开放的可选集(choices) 与 搜索方法，又比如优化器对查询求值计划可能顺序的考虑。正如导航性（navigational）查询语言的用户友好性不如非导航性查询语言那样【更高范式的语言，更好的数据独立性】，需要来自数据库实现者的控制信息的可扩展查询优化系统不如不需要的系统那样方便。因此，优化器可选集在 Volcano 优化器生成器的输入文件中表示为代数等价，并且优化器生成器的搜索引擎以合适的方式应用它们。然而，对于希望对搜索进行控制的数据库实现者，例如希望指定搜索和修剪启发式函数的数据库实现者，也会有可选的工具来执行此操作。
第四个基本设计决策涉及规则 解释 vs 编译。 一般来说，解释更加灵活（特别是可以在运行时扩充规则集），编译规则集通常执行得更快。 由于查询优化是 CPU 密集型的，我们决定使用类似于 EXODUS 优化器生成器的规则编译。 此外，我们相信扩展查询处理系统及其优化器是如此复杂和耗时，以至于永远无法快速完成，这使得解释器的最强论据毫无意义。 为了通过编译的规则集获得额外的灵活性，对规则及其条件进行参数化可能很有用，例如，控制搜索的彻底性，以及观察和利用规则应用的重复序列。 一般来说，搜索引擎的灵活性问题与解释与编译之间的选择问题是正交的。【类似calcite的框架并不存在一个用模型语言实现的规则集模型，而是用java 语言面向对象的实现了一些 rule。本文的解释与编译是相对于模型规约来说的，如果把java也看做一种描述 rule 的模型语言，则可以认为calcite是既是解释又是编译，因为模型语言与通用编程语言的统一】
最后，使用 Volcano 优化器生成器生成的优化器使用的搜索引擎是基于动态规划的。 我们将在第 3 节讨论动态规划的使用。
2.2. 优化器生成器的输入和优化操作
由于 Volcano 优化器生成器的一个主要设计目标是最小化对要实现的数据模型的假设，因此 优化器生成器 仅提供一个框架，优化器实现者 可以将数据模型特定的操作和功能集成到该框架中。 在本节中，我们将讨论优化器实现者在实现新的数据库查询优化器时定义的组件。 实际的用户查询和执行计划是生成的优化器的输入和输出，如图1所示。本节讨论的所有其他组件在优化器生成之前由优化器实现者以等价规则（equivalence rule）和支持函数（support function）的形式指定，在优化器生成期间编译和链接，然后在查询优化时由生成的优化器使用。 我们在这里讨论生成的优化器的部分操作，但将搜索部分留着，后续再将所有部分组合在一起。
用户待优化查询被指定为逻辑运算符（logical operator）的代数表达式（树）。 从用户接口到逻辑代数表达式的翻译必须由 parser 执行，这里不讨论。 逻辑运算符集在模型规约中声明，并在生成期间编译到优化器中。 运算符可以有零个或多个输入， 输入的数量不受限制。 优化器的输出是一个计划（plan），它是算法上代数（algebra of algorithm）的一个表达式。 算法集合（the set of algorithm），其能力(capability)和代价（cost）代表了数据库系统用于永久和临时数据的数据格式和物理存储结构【？】。
优化包括将逻辑代数表达式映射到最佳等效物理代数表达式。 换句话说，生成的优化器会重新排序运算符并选择实现算法。 表达式等价的代数规则，例如，交换律（commutaitvity）【a·b = b·a】或 结合律（associativity）【(a·b)·c = a·(b·c)】，是使用 变换规则 指定的。 运算符到算法的可能映射是使用 实现规则（implementation rule）指定的。 规则语言允许复杂的映射是很重要的。 例如，一个连接后跟一个投影（没有重复删除）应该在一个过程中实现； 因此，可以将多个逻辑运算符映射到单个物理运算符。 除了运算符和算法的简单模式匹配之外，还可以对两种规则指定附加条件。 这是通过将条件代码附加到规则来完成的，该规则将在模式匹配成功后调用。
表达式的结果使用属性（properties）来描述，类似于 EXODUS 优化器生成器和 Starburst 优化器中的属性概念。 逻辑属性（logical properties）可以从逻辑代数表达式中导出，包括模式(schema)、预期大小(expected size)等，而物理属性（physical properties）取决于算法，例如排序顺序、分区（partition）等。在优化多排序（many-sorted）代数时，逻辑属性还包括 中间结果的类型（或排序），可以通过规则的条件代码进行检查，以确保规则仅应用于正确类型的表达式。 逻辑属性附属于等价类 - 一组等效的逻辑表达式和计划。物理属性附属于特定的计划和算法选择。
每个中间结果的物理属性集会汇总在一个物理属性向量（physical property vector）中，该向量由优化器实现者定义，并被 Volcano 优化器生成器及其搜索引擎视为抽象数据类型。 换句话说，物理属性的类型和语义可以由优化器实现者设计。
物理代数中有一些运算符与逻辑代数中的任何运算符都不对应，例如排序和解压缩。 这些运算符的目的不是执行任何逻辑数据操作，而是在其输出中 enforce(强制) 后续查询处理算法所需的物理属性。 我们称这些运算符为enforcers(强制器)； 它们可与 Starburst 中的“胶水”运算符相媲美。 enforcers 可以同时确保两个属性，或者enforce一个但破坏另一个。
每个优化目标（goal）（和子目标(subgoal)）都是一对 逻辑表达式 和 物理属性向量。为了决定是否可以使用 算法 或 enforcer【注意 enforcer 是物理代数中与逻辑代数无关的物理算子，其实也是一种‘算法’，本文术语上'算法'指和与逻辑代数有关的物理算子】 来执行逻辑表达式的根节点，生成的优化器会先匹配实现规则，执行与规则关联的条件代码，然后调用一个 适用性函数（applicability function）来确定是否 算法 或 enforcer 可以 交付(deliver) 满足 物理属性向量中物理属性 的 逻辑表达式。适用性函数还决定了算法输入必须满足的物理属性向量。例如，当优化结果为应按连接属性排序的连接表达式时，混合散列连接(hybrid hash join)不符合条件，而 合并连接(merge join) 符合其输入被排序的要求。排序 enforcer 也通过了测试，其输入要求不包括排序顺序。当对排序的输入进行优化时，混合散列连接符合条件。还有一项规定是确保算法不会冗余限定，例如，在本示例中，不得将合并连接视为排序的输入。
【比如一个SQL(select c1 from t order by c1;)优化目标是一个关系代数表达式(project_t1(t)) 和 物理属性向量('按照c1列asc排序')，则适用性函数会保证该逻辑表达式匹配实现规则时检查:1.物理算子匹配输入(表 t)的物理属性。2.物理算子满足输出物理属性（按照c1列asc排序）。最终实现规则会产生一个project c1 列的算法和sort c1 列的 enforcer。】
在优化器决定使用算法或 enfocer 进行探索后，它会调用算法的 代价函数 来估计其代价。 代价是优化器生成器的抽象数据类型（abstract data type，ADT）； 因此，优化器实现者可以选择代价是一个数字（例如，估计经过的时间）、一条记录（例如，估计的 CPU 时间和 I/O 计数）或任何其他类型。 代价算术和比较是通过调用与抽象数据类型“代价”相关的函数来执行的。
对于每个逻辑和物理代数表达式，逻辑属性和物理属性是使用属性函数（properties function）导出 的。 每个逻辑运算符、算法和 enforcer 都必须有一个属性函数。 在执行任何优化之前，逻辑属性（logical properties）由与 逻辑运算符 相关联的 属性函数 基于 逻辑表达式 确定。 例如，schema 可以独立于任意等价代数表达式导出。 逻辑属性函数还封装了选择度估计（selectivity estimation）【因为可以基于logical operator中的表达式中谓词估计输出，物理算法实现不影响逻辑算子输出的选择度】。 另一方面，诸如排序顺序之类的物理属性只能在选择了执行计划后才能确定。 作为许多一致性检查之一，生成的优化器会验证所选计划的物理属性确实满足作为优化目标的一部分给出的物理属性向量。
总结本节，优化器实现者提供
(1) 一组逻辑运算符，
(2) 代数变换规则，可能带有条件代码，
(3) 一组算法和enforcer，
(4) 实现规则，可能带有条件代码,
(5) 具有基本算术函数和比较函数的 ADT “代价”，
(6) ADT “逻辑属性”，
(7) ADT “物理属性向量”，包括比较函数（相等和覆盖），
(8) 每个算法和enforcer的适用性函数，
(9) 每个算法和enforcer的代价函数，
(10) 每个算子(operator)【指逻辑算子】、算法(algorithm)和 enforcer 的属性函数。
这似乎是很多代码；但是，无论是否使用优化器生成器，都需要所有这些功能来构建数据库查询优化器。【这一点上得到了时间的检验。如果把优化器分为业务规则和搜索框架两部分，这10条就是业务规则(在不考虑搜索引擎要求下)至少需要明确指定的规格说明。】考虑到查询优化器通常是数据库管理系统中最复杂的模块之一，并且优化器生成器为这些必要的优化器组件规定了一个干净的模块化方式，相比从头开始设计和实现一个新的优化器，使用 Volcano 优化器生成器构建新的数据库查询优化器的工作应该会大大减少。尤其是，因为使用 Volcano 优化器生成器的优化器实现者不需要设计和实现新的搜索算法。
3. 搜索引擎
由于数据库查询优化的一般范例是创建替代（等效）查询评估计划，然后在许多可能的计划中进行选择，因此搜索引擎及其算法是任何查询优化器的核心组件。 Volcano 优化器生成器没有强制每个数据库和优化器实现者实现一个全新的搜索引擎和算法，而是提供了一个搜索引擎，可在所有创建的优化器中使用。该搜索引擎自动链接数据模型描述生成的模式匹配和规则的应用程序代码。
由我们使用 EXODUS 优化器生成器的经验表明，在可扩展的查询优化中很容易浪费大量搜索工作，因此我们将 Volcano 优化器生成器的搜索算法设计为使用动态规划并且非常面向目标（goal-oriented），即根据需要驱动而不是根据可能性驱动。
动态规划以前曾在数据库查询优化中使用过，特别是在 System R 优化器 [15] 和 Starburst 的基于代价的优化器 [8, 10] 中，但仅用于SPJ查询。使用 Volcano 优化器生成器设计的搜索策略将动态规划从关系连接优化扩展到一般代数查询和请求优化，并将其与自顶向下（top-down）、面向目标 的控制策略相结合(其中代数可能的计划数量超过预计算的可行限制)。我们的动态规划方法仅为那些被视为较大子查询（和整个查询）的一部分的部分查询导出等效表达式和计划，而不是所有可行或按照排序顺序看起来有利(interesting)的等效表达式和计划 [15]。因此，对子查询及其替代方案的探索和优化是直接且面向目标的。在某种程度上，虽然 EXODUS 优化器生成器以及 System R 和 Starburst 关系系统的搜索引擎使用前向链接(forward chaining)（在人工智能中使用该术语的意义上），但Volcano搜索算法使用后向链接，因为它只探索那些真正参与更大表达式的子查询和计划。我们称我们的搜索算法为定向动态规划（directed dynamic programming）。【这里的意思应该是说volcano使用的记忆化启发式搜索是从终点(也就是 最大的查询树+最终结果要求的物理属性) 开始自顶向下搜索，所以一开始目标是确定的，不会像一些自底向上方法一样探索很多注定被剪枝的子状态】
动态规划用于使用 Volcano 优化器生成器创建的优化器，方法是保留大量部分优化结果并在以后的优化决策中使用这些早期结果。目前，这组部分优化结果会针对每个正在优化的查询重新初始化。换句话说，在优化单个查询的过程中，使用了较早的部分优化结果。我们正在考虑在未来研究更长期存在的部分优化结果。
代数变换系统（algebraic transformation systems【系统的常见含义有两个，一个是异构部分组成的有序整体，内部可以互相转换。另一个是可以将一个输入加工成一个输出的东西，这里应该更符合第二种含义】）总是包含以几种不同方式导出相同表达式的可能性。为了通过在优化期间检测相同逻辑表达式和计划的冗余（如多个等价）推导来防止冗余优化工作，表达式和计划被捕获在表达式和等价类的哈希表中。一个等价类（equivalence class）表示两个集合，一个是等价的逻辑表达式集合，一个是物理表达式（计划）集合。逻辑代数表达式集合 用于有效和完整地探索搜索空间，计划集合 用于快速选择满足物理属性要求的合适输入计划。对于已经优化了等价类的物理属性的每个组合，例如，未排序、在 A 上排序和在 B 上排序，保留找到的最佳计划。
图 2 显示了 Volcano 优化器生成器使用的搜索算法的概要。 FindBestPlan 过程起始要求传递给优化器的参数有：要优化查询的逻辑表达式、用户请求的物理属性（例如，SQL 的 ORDER BY 子句中的排序顺序）和代价限制。对于用户查询，这个代价限制通常是无限的，但是用户接口可以允许用户设置他们自己的限制以“捕获”不合理的查询，例如，由于缺少连接谓词而使用笛卡尔积的查询。
FindBestPlan 过程分为两部分。首先，如果满足物理属性向量的表达式的计划可以在哈希表中找到，则根据找到的计划是否满足给定的代价限制，返回 计划及其代价 或 失败指示。如果在哈希表中找不到表达式，或者如果表达式之前已经优化但没有针对当前所需的物理属性，则开始实际优化。
优化器可以随时探索三组可能的“移动(move)”。首先，表达式可以使用变换规则进行变换。其次，可能有一些算法可以提供具有所需物理属性的逻辑表达式，例如，针对不排序输出的混合哈希链接(hybrid hash join)和针对属性上排序的合并连接(merge join)。第三，enforcer 可能有助于允许额外的算法选择，例如，即使最终输出要排序，排序运算符也允许使用混合哈希连接。
在生成并访问了所有可能的移动之后，最有希望（promising）的移动是已探索过的（pursued)。目前，只实现了穷尽式搜索，所有的移动都会探索。将来，移动的子集将由优化器实现者提供的另一个函数进行选择、确定和排序。探索所有移动或只探索少数几个移动是优化器实现者手中的主要启发式【启发式指使用受限信息的情况下做出决策，用于确定搜索方向】方法。在极端情况下，优化器实现者可以选择转换逻辑表达式而无需任何算法选择和代价分析，这涵盖了 Starburst 中分离到查询重写级别上的的优化。 Starburst 的两级方法和 Volcano 方法之间的区别在于，这种分离在 Starburst 中是强制性的，而 Volcano 将把它留给优化器实现者进行选择【后文会详述与Starburst的区别】。
代价限制用于改进使用分支定界裁剪（branch-and-bound pruning）的搜索算法。一旦一个完整的计划已知为一个逻辑表达式（用户查询或它的一部分）和一个物理属性向量，没有其他具有更高代价的计划或部分计划可以成为最佳查询评估计划的一部分【已经定了上界】。因此，即使优化器使用穷举搜索，快速找到相对好的计划也很 重要（针对优化速度，而不是正确性）。此外，代价限制在子表达式的优化中被传递，严格的上界也加速了它们的优化。
如果要进行的移动是变换（transformation），则使用 FindBestPlan 形成和优化新表达式。为了检测两个（或多个）规则彼此相反的情况，将当前表达式和物理属性向量标记为“进行中(in progress)”。 如果一个新形成的表达式已经存在于哈希表中并且被标记为“进行中”，它被忽略，因为它的最优计划将在它完成时被考虑。
通常在转换过程中会创建一个新的 等价类。考虑图 3 中的结合律规则（Associativity Rule）。以 A 和 B 为根的表达式是等价的，因此属于同一类。但是，表达式 C 不等价于左表达式中的任何表达式，并且需要一个新的等价类。在这种情况下，将创建一个新的等价类并根据需要对表达式 B 进行代价分析和优化。
如果要进行的移动是探索常规查询处理算法如合并连接等，则其代价由算法的代价函数算出。算法的适用性函数确定算法输入的正确物理向量，并通过为输入调用 FindBestPlan 找到它们的代价和最优计划。
对于一些二元算子来说，输入的实际物理属性不如输入之间物理属性的一致性重要。例如，对于基于排序的交集实现，即与合并连接非常相似的算法，只要两个输入以相同的方式排序，两个输入的任何排序顺序就足够了。类似地，对于并行连接，如果两个输入都使用兼容的分区规则进行分区，则跨多个处理节点的连接输入的任何分区都是可接受的。对于这些情况，搜索引擎允许优化器实现者指定要尝试的多个物理属性向量。例如，对于具有属性 A、B 和 C 的两个输入 R 和 S 的交集，其中 R 在 (A,B,C) 上排序，S 在 (B,A,C) 上排序，这两种排序顺序都可以由优化器实现者指定并将由生成的优化器优化，而其他可能的排序顺序，例如 (C,B,A)，将被忽略。
如果要采取的移动是使用诸如排序之类的 enforcer，则其代价由优化器实现者提供的代价函数估算，并且原始逻辑表达式使用 FindBestPlan 和经过适当修改（如放松）的物理属性向量进行优化。在许多方面，enforcer的处理方式与算法完全相同，考虑到两者都是物理代数的运算符，这并不奇怪。在使用修改后的物理属性向量进行优化期间，不应该再次探索在 放松物理属性 之前已经应用的算法。【也就是说增加enforcer场景对于放松的物理属性应显式排除，不应该任意加各类无意义enforcer】例如，如果需要在连接列上对连接结果进行排序，则将应用合并连接（一种算法）和排序（一种enforcer）。当优化没有排序要求的连接表达式的排序输入时 ，应该应用混合哈希连接，但不应该再使用合并连接。为了确保这一点，FindBestPlan 使用了一个额外的参数（图 2 中未显示），称为排除物理属性向量（the excluding physical property vector），仅在优化 enforcer 的输入时使用。 在示例中，排除物理属性向量将包含排序条件，并且由于合并连接能够满足排除属性，因此它不会被认为是排序输入的合适算法。
在优化过程 FindBestPlan 结束时（或实际上已经在其过程中），新导出的有利结果（interesting fact）被捕获在哈希表中。 “有利”是针对可能的未来用途定义的，包括三类，
1.对给定物理属性优化的计划，
2.优化失败（failures）结果，用于减少未来逻辑表达式优化搜索代价，
3.相同或更低代价限制的逻辑表达式和物理属性向量。
【导出(derives)在本文有两个含义，一个是通过表达式变换衍生出新的表达式（逻辑或物理的），另一个是指通过表达式和函数导出属性】
总之，使用 Volcano 优化器生成器创建的优化器使用的搜索算法通过存储所有优化子计划以及优化失败来使用动态规划，直到查询完全优化。 在没有关于代数本身的任何先验假设的情况下，它旨在将逻辑代数上的表达式映射到物理代数上的最优等价表达式。它非常面向目标，通过使用物理属性，并且仅导出那些真正参与了 有希望的更大计划的 表达式和计划。因此该算法比以前在数据库查询优化中使用动态规划的方法更有效。
4. 和 EXODUS 优化器生成器的对比
由于 EXODUS 优化器生成器是我们设计和实现可扩展查询优化系统或工具的第一次尝试，本节将详细比较 EXODUS 和 Volcano 优化器生成器。 EXODUS 优化器生成器是成功的，它定义了 基于查询代数、生成器范式（数据模型规约作为输入数据）、逻辑和物理代数分离、逻辑和物理属性分离、广泛使用代数规则（转换规则和实现规则），并且重点关注软件模块化 [2, 3]。考虑到典型查询优化软件的复杂性和定义明确的模块对克服软件设计和维护复杂性的重要性，后两点很可能是 EXODUS 优化器生成器研究的最重要贡献。
生成器的概念非常成功，因为输入数据（数据模型规约）可以转化为机器码；特别是，所有字符串都被转换为整数，这确保了非常快的模式匹配。然而，EXODUS 优化器生成器的搜索引擎远非最佳。首先，不可预见的代数所需的修改及其奇异性(peculiarities)使其成为糟糕的代码补丁拼凑。其次，“MESH”数据结构（包含迄今为止探索的所有逻辑和物理代数表达式）的组织在时间和空间复杂性方面都非常繁重（cumbersome）。第三，MESH 中表达式的几乎随机转换导致“重新分析”现有计划的大量开销。事实上，对于较大的查询，大部分时间都花在重新分析现有计划上。
Volcano 优化器生成器解决了这三个问题，并包含了 EXODUS 优化器生成器中没有的新功能。我们首先总结了它们在功能上的差异，然后对关系查询进行了性能比较。
4.1. 功能性和可扩展性
EXODUS 和 Volcano 优化器生成器在功能性和可扩展性上有几个重要的区别。首先，Volcano 区分了逻辑表达式和物理表达式。在EXODUS中，哈希表（称为MESH）中只存在一种节点，它既包含逻辑运算符如join，也包含物理算法如hybrid hash join。为了使merge-join和hybrid hash join保留等价的计划，逻辑表达式（或至少一个节点）必须保留两次，导致MESH中有大量节点。【这里猜测原文意思是 EXODUS 逻辑和物理计划存了一个pair 在hash表，可能hash key是逻辑表达式的signature，value 是物理表达式列表。volcano 的 hash 表提供一个逻辑计划以及其等价类对应多个物理计划的保存机制，其hash key应该是逻辑表达式等价类 ID，值为逻辑表达式等价类数组以及物理表达式等价类map两部分，物理表达式等价类map内部键为物理属性向量，值为物理表达式】
其次，在 EXODUS 中，物理属性的处理相当随意。如果代价最低的算法碰巧提供了具有有用物理属性的结果，则将其记录在 MESH 中并用于后续优化决策。否则，enforcer的代价（使用 Volcano 术语）必须包含在其他算法的代价函数中，例如合并连接。换句话说，EXODUS 中完全不具备指定所需物理属性并让这些属性与逻辑表达式一起驱动优化过程的能力【比如没有避免无效enforcer的能力】，并且对 Volcano 优化器生成器搜索引擎的效率做出了重大贡献。
物理属性的概念非常强大和可扩展。数据库查询处理中最明显和最知名的物理属性候选者是中间结果的排序顺序。其他属性可以由优化器实现者随意定义。根据数据模型的语义，唯一性(uniqueness)可能是一种物理属性，具有两个enforcer，即基于排序和基于散列的。并行和分布式系统中的定位（locationing）和分区（partitioning）可以通过网络和并行算子（例如 Volcano 的交换（exchange）算子 [4]）来enforce。对于面向对象系统中的查询优化，我们计划将内存中复杂对象的“组装性（assembledness）”定义为物理属性，并使用 [5] 中描述的组装（assembly）运算符作为该属性的enforcer。
第三，Volcano算法自顶向下驱动；子表达式仅在必要（warranted）时才被优化。在极端情况下，如果只追求变换，则逻辑表达式在逻辑代数级别上进行变换，而不优化其子表达式，也不对子表达式进行算法选择和代价分析。在 EXODUS 中，算法选择和代价分析总是紧随其后。此外，转换无论是否是当前从整体查询逻辑表达式和物理计划的一部分角度上看最有希望的，总是会被探索。并且，对于优化器性能而言，【EXODUS的】最糟糕的是决定首先执行具有最高预期代价改进的转换。由于预期代价改进计算方法为 转换规则相关的因子 乘以 转换前的当前代价，因此表达式顶部的节点（总代价高）优于较低的表达式。当下层表达式最终被转换时，上面的所有消费者节点（此时有很多）都必须重新分析，从而创建大量的 MESH 节点。
第四，与 EXODUS 优化器生成器相比，Volcano 中的代价定义更为通用（general）。在 Volcano 中，代价是一种抽象数据类型，所有计算和比较都是通过调用优化器实现者提供的函数来执行的。它可以是一个简单的数字，例如估计经过的秒数，也可以是一个结构，例如由 CPU 时间和 I/O 计数组成的记录，对于类似于 System R [15] 中的代价模型，甚至可以是一个函数，例如, 可用主存的数量。
最后，我们认为 Volcano 优化器生成器比 EXODUS 原型更具可扩展性，特别是在搜索策略方面。 包含逻辑表达式和物理计划以及对该哈希表的操作的哈希表非常通用，并且将支持各种搜索策略，而不仅仅是上一节中概述的过程。 我们仍在修改（扩展和完善）搜索策略，并计划在随后几年进一步修改它并使用 Volcano 优化器生成器进行进一步研究。
4.2. 搜索效率和有效性(Search Efficiency and Effectiveness)
在本节中，我们通过实验比较了 EXODUS 和 Volcano 搜索引擎中内置机制的效率和有效性。用于此比较的示例是一个相当小的“数据模型”，仅包含关系选择和连接运算符；然而，正如我们将看到的，即使是这种小型数据模型和查询语言也足以证明 Volcano 优化器生成器的搜索策略优于为早期 EXODUS 原型设计的搜索策略。对于更丰富和更复杂的数据模型、（逻辑）查询代数和（物理）执行代数，这里暴露的效果会更强。
对于实验，我们为 EXODUS 和 Volcano 优化器生成器指定了尽可能相似的数据模型描述。特别是，我们指定了相同的运算符（get、select、join）和算法（file scan、filter for selection、sort、merge-join、hybrid hash join），相同的转换和实现规则，以及相同的属性和代价函数。排序在 Volcano 中被建模为enforcer，而在 EXODUS 中它隐含在合并连接的代价函数中。转换规则允许生成所有计划，包括稠密(bushy)的计划（组合内部输入(composite inner inputs)）。测试关系包含 1,200 到 7,200 条 100 字节的记录。代价函数包括 I/O 和 CPU 代价。散列连接被假定在没有分区文件的情况下继续进行，而排序代价是基于单级合并计算的。
作为两个搜索引擎之间的第一次比较，我们对关系选择连接查询进行了穷尽式的优化。图 4 显示了平均优化工作量，并且为了显示优化器输出的质量，为具有 1 到 7 个二元连接（即 2 到 8 个输入关系以及与输入关系一样多的选择）的查询生成的计划的估计执行时间。实线表示 Sun SparcStation-1 上提供大约 12MIPS 的优化时间。虚线表示估计的计划执行时间。请注意，y 轴是对数的。 EXODUS 优化器生成器的测量值用 [] 标记，Volcano测量值用 O 标记。
对于每个复杂度级别，我们生成并优化了 50 个查询。对于一些更复杂的查询，EXODUS 优化器生成器由于内存不足而中止，或者由于运行时间比 Volcano 优化器生成器长得多而中止。此外，我们在重复实验中观察到 EXODUS 优化器生成器的测量结果非常不稳定。在 [3] 中报告的 EXODUS 实验中观察到了类似的问题。 Volcano 生成的优化器对所有工作空间不足 1 MB 的查询执行了穷举式的搜索。图 4 中的数据点仅代表 EXODUS 优化器生成器完成了优化。
搜索时间反映了 Volcano 更有效的搜索策略，在两条实线之间的较大距离中可见。对于 EXODUS 生成的优化器，搜索工作量从 3 个输入关系到 4 个输入关系过程中急剧增加，因为此时重新分析成为 EXODUS 中查询优化工作的重要部分。 Volcano 优化代价的增加是指数级的，几乎呈直线显示，这正好反映了等价逻辑代数表达式数量的增加 [13]。对于更复杂的查询，EXODUS 和 Volcano 的优化时间相差大约一个数量级。
对于中等复杂的查询（最多 4 个输入关系），计划质量（由估计的执行代价显示；图 4 中的虚线）是相同的。然而，对于更复杂的查询，EXODUS 优化计划的代价要高得多，因为 EXODUS 生成的优化器及其搜索引擎没有系统地探索和利用物理属性和有利的排序。
综上所述，Volcano 优化器生成器不仅可扩展性更强，而且比早期的 EXODUS 原型更加高效和有效。在下一节中，我们将我们的工作与其他相关工作进行比较。
5. 其他相关工作
Starburst 可扩展关系数据库管理系统的查询优化器由两个具有嵌套范围(nested scope)的基于规则的子系统组成。这两个子系统通过一个共同的数据结构连接起来，该结构代表一个完整的查询，称为查询图模型（QGM）。第一个子系统称为查询重写（query rewrite），它合并嵌套子查询并捆绑选择和连接谓词，以便在第二个基于代价的优化器中进行优化。查询重写阶段的优化，即嵌套 SQL 查询、联合、外连接、分组和聚合，完全基于启发式，对代价不敏感。 SPJ 查询组件由第二个优化器(实际上基于代价的优化器覆盖了所有算子。然而其只支持受限在查询的 SPJ 块上的优化)覆盖，也称为基于代价的优化器，它基于规则将SPJ查询从关系演算扩展到访问计划(access plan)，并通过估计的执行代价比较结果计划 [8, 10]。基于代价的优化器在某些结构化的边界内执行穷举搜索。例如，可以将搜索空间限制为左深树（没有组合内部(composite inner)），去包括所有稠密的树木，或者设置一个参数来探索一些但不是所有的稠密树木。对于中等复杂的连接查询，Starburst 的基于代价的优化器的穷举搜索非常快，因为它使用了动态规划。此外，基于代价的优化器会考虑诸如排序顺序之类的物理属性，并创建有效的访问计划，其中包括“胶水”运算符以 enforce 物理属性。
正如我们所见，Starburst 的可扩展查询优化方法存在两个基本问题。首先，基于代价的优化器的设计侧重于基于类语法规则的对连接表达式的逐步扩展。 “语法”依赖于中间级别的层次结构（类似于解析语法中的非终结符），例如交换连接和非交换连接，并且规则集和中间级别专门针对关系连接优化。问题是现有规则集如何与其他运算符和扩展规则交互并不明显。例如，层次结构的哪个层是多路连接算法的正确位置？必须为扩展文法定义哪些新的中间层（非终结符）？为了将新的运算符集成到 Starburst 的基于代价的优化器中，数据库实现者必须设计许多新的中间层及其新的语法规则。这些规则可能与现有规则交互，使 Starburst 基于代价的优化器的任何扩展成为一项复杂而乏味的任务。 Volcano 的代数方法看起来更自然，更容易理解。面向对象查询优化和一些数据库编程语言方面的最新工作都集中在代数和代数变换上，例如[9, 16-18] 等等。
【在查询树变换上，术语'启发式'指的是纯规则无代价计算的优化过程，单个规则直接变换查询树为新的查询树，不会保留之前的历史查询树。】
其次，为了避免与向基于代价的优化器中添加新运算符相关的问题，在查询重写级别集成了新运算符。但是，查询重写级别的查询优化是启发式的；换言之，它不包括代价估算。虽然启发式对于某些转换来说已经足够了，例如，将嵌套 SQL 查询重写为连接表达式，但对于已经处于 Starburst 查询重写级别的关系运算符来说，它们是不够的。当然对于查询优化系统未知代数运算符及其属性的未来扩展也不够。以现有 Starburst 算子优化能力不足为例，考虑优化 N 个集合的并集或交集与优化 N 个关系的连接非常相似；然而，虽然连接优化使用了对树形和连接顺序的穷尽搜索，考虑了选择度(selectivity)和代价估计，但联合和交集仅使用查询重写启发式和交换性进行优化。我们相信，所有代数等价和转换都用一种语言指定并由单个优化器组件执行的单级方法更有利于数据库查询代数及其优化的未来研究和探索。需要说明的是，火山优化器生成器将允许通过适当的排名和“移动”选择进行启发式转换；然而，它让数据库实现者选择何时以及如何使用启发式优化与代价敏感优化，而不是像 Starburst 设计中那样先验地做出选择。
Sciore 和 Sieg 批评了早期基于规则的查询优化器（rule-based query optimizer，RBO），并得出结论认为模块化是可扩展查询优化系统的主要要求，例如，在规则集（rule set）和在规则应用的控制结构（control structures for rule application） 中 [14]【也就是rule set和search engine的模块分离】。 查询优化的不同任务，例如规则应用和选择度估计，应该封装在独立和合作的“专家”中。 Mitchell等人最近提出了一种非常相似的方法来优化面向对象的数据库系统中的查询 [12]。 虽然作为一种概念性方法很有希望，但我们认为这种分离可以在查询优化的某些方面保持（并且已经尝试在 Volcano 优化器生成器中的代价等抽象数据类型中这样做），但我们已经发现它在实际实现中很难保持在所有封装上 理想的关注点独立性（desirably separate concerns）。【以译者的理解，优化器其实对应软件架构风格中的黑板系统，查询的逻辑和物理代数表示是黑板的上的显示数据结构，各个'专家'以规则(volcano 推荐的做法)的形式模块化，可以分别修改黑板上的数据结构，由搜索过程作为统一的控制。这里是在讨论，已知用规则来模块化'专家'是一个不错的方法，是否还应进一步做更多的先验模块划分。而volcano提出的模式是反对多优化阶段的设计，希望统一到前文提到的三类 moves 上。】
Kemper 和 Moerkotte 为通用对象模型 [6] 设计了一个基于规则的查询优化器。 这些规则几乎完全在路径表达式(path expressions)（例如employee.department.floor）上运行，通过扩展和切割(extending and cutting)它们以允许有效使用访问支持关系(access support relations)[7]。 虽然规则的使用使优化器具有可扩展性，但尚不清楚这些技术可以在多大程度上用于不同的数据模型和不同的执行引擎。
6. 总结与结论
新兴的数据库应用领域不仅需要高功能性，还需要高性能。为了满足这两个要求，Volcano 项目提供了高效、可扩展的查询和请求处理工具，尤其是面向对象和科学数据库系统。我们不建议将关系查询处理重新引入下一代数据库系统；相反，我们致力于一种独立于任何数据模型的新型查询处理引擎。基本假设是高级查询和请求语言现在并将继续基于集合、其他批量类型、谓词和运算符（sets, other bulk types, predicates, and operators）。因此，消费和产生集合或序列的算子是下一代查询和请求处理系统的基本构建块。换句话说，我们假设集合的一些代数是查询处理的基础，我们的研究试图支持任何集合的代数，包括异构集合和多排序代数。幸运的是，代数和代数等价规则是非常适合数据库查询优化的基础。此外，集合（允许定义和利用子集）和在它们之间传递（或流水线化）数据的运算符也是数据库查询处理并行算法的基础。因此，我们对可扩展数据库系统中查询处理的基本假设与高性能并行处理兼容。
Volcano 研究提供的工具之一是一种新的优化器生成器，其设计和实现是为了进一步探索搜索引擎中的可扩展性、搜索算法、有效性（即生成的计划的质量）、启发式方法以及时间和空间效率。通过从数据模型规约生成优化器源代码并将代价以及逻辑和物理属性封装到抽象数据类型中来实现可扩展性。通过允许穷尽式搜索来实现有效性（effectiveness），只有在优化器实现者的判断下才会对其进行修剪。通过将动态规划与基于物理属性的定向搜索、分支定界修剪和启发式引导相结合，形成一种新的搜索算法，我们称之为定向动态规划（directed dynamic programming），从而实现了高效。与 EXODUS 优化器生成器的初步性能比较表明，使用 Volcano 优化器生成器构建的优化器比使用 EXODUS 原型构建的优化器效率更高。我们希望新的 Volcano 优化器生成器将允许我们自己的研究小组以及其他人更快地为新的数据模型、查询代数和数据库管理系统开发新的数据库查询优化器。 Volcano 优化器生成器已用于开发优化器，用于科学数据库 [20] 和德州仪器的 Open OODB 项目 [1, 19]，该项目引入了一个新的“物化(materialize)”或范围(scope)运算符，用于在一个逻辑代数表达式中捕获路径表达式的语义。这两个优化器最近都已投入使用。此外，Volcano 优化器生成器目前正在由三大洲的几位学术和工业研究人员进行评估。
除了将 结合 基于动态规划的穷举搜索的有效实现（也可以在 Starburst 的关系优化器的基于代价的组件中找到）与 EXODUS 优化器生成器的通用性和更自然的单层级代数变换方法， Volcano 优化器生成器具有许多新功能，这些功能增强了其作为软件开发和研究工具的价值，超越了所有早期的可扩展查询优化工作。
首先，对于何时以及如何使用启发式转换与代价敏感优化的选择没有规定或“固定(wried in)”。 在 EXODUS 中，代价分析总是在转换之后进行； 在 Starburst 中，一个级别只能执行启发式优化，而另一个级别执行代价敏感的穷举搜索。 因此，Volcano 优化器生成器消除了早期可扩展查询优化器设计对搜索策略的限制。
其次，使用 Volcano 优化器生成器生成的优化器非常有效地使用物理属性来指导搜索。 Volcano 优化器生成器的搜索算法不是首先优化表达式，然后将“胶水”运算符及其代价添加到计划中（Starburst 方法），而是立即考虑哪些物理属性将被enforce，并且可以由哪些enforcer算法enforce，并且 从用于分支定界修剪的界限中减去enforcer算法的代价。 因此，Volcano 优化器生成器承诺在搜索和修剪方面比关系型 Starburst 优化器更有效。
第三，对于可以从物理属性的多种替代组合中受益的二元（三元等）运算，可以多次优化子表达式。 例如，只要两个输入以相同的方式排序，基于合并连接的交集算法就可以利用任何排序顺序。 尽管相同的考虑适用于并行和分布式关系查询处理中的位置和分区，但早期的查询优化器没有提供此功能。
第四，等价类的内部结构足够模块化和可扩展，以支持替代搜索策略。远远超出（Starburst 和 EXODUS 中可以找到大致相似的）规则条件代码参数化（parameterizeation of rule condition code）。 我们正在探索关于搜索策略的几个方向，即 预优化子计划；学习转换序列；一种替代的；甚至更多参数化的搜索算法，可以“切换”到不同的现有算法；以及并行搜索（在共享内存机器上） .
最后，逻辑代数和物理代数的一致分离使得规约以及任一级别的修改对于数据库和优化器实现者来说特别容易，并使搜索引擎非常高效。例如，在 Volcano 中引入一种新的、重要的算法，例如多路连接（而不是二元连接）需要一到两个实现规则，而 Starburst 的基于代价的优化器的设计需要重新考虑几乎整个规则集。虽然 EXODUS 规则语言中已经存在逻辑代数和物理代数的分离，但 Volcano 设计还在搜索引擎中利用了这种分离，这使得优化器实现者提供的代码得以扩展（有时必须检查内部数据结构，例如, 在规则条件代码中) 更容易编写、理解和修改。总之，Volcano 优化器生成器是比 Starburst 优化器和 EXODUS 优化器生成器更具可扩展性和有用的研究工具。
Acknowledgements
见原文
References
见原文
【概念小结】
logical operator：逻辑算子，对应关系表达式树中的一个 关系代数运算符
physical operator：物理算子，对应查询执行树中一个具体的数据处理算法，类似一个数据流图的加工节点
logical expression：逻辑表达式，关系代数表达式。
physical propertie：物理属性，在关系代数范围之外，对于执行过程中数据的描述。
cost：代价，一个抽象数据类型， 可以比较大小，用于在搜索过程剪枝和保留最优解。
look-up table: 查找表，保存一个 logical expression + physical propertie 作为键的 plan
moves ：移动，表示搜索可能的路径，可能是下面三中类型
transformation：转换，表示在关系代数表达式上的变换
algorithm：算法，表示一个带有关系代数含义的物理算子
enforcer：强制器，表示一个无关系代数含义的纯物理算子
promise：希望，表示一个具体移动在执行前的有希望的程度。
