The Cascades Framework for Query Optimization(翻译)

摘要

这篇论文描述了一个新的可扩展查询优化框架，解决了 EXODUS 和 Volcano优化器/生成器的许多不足之处。除了可扩展性、基于EXODUS和Volcano原型的动态规划和记忆化，这个新的优化器提供了以下功能：

1. 使用规则或函数来操作算子参数，
2. 对谓词等既有逻辑又有物理算子，
3. 针对物化视图的特定于模式的规则，
4. 插入"enforcers"或"glue算子"的规则，
5. 规则特定的引导，允许对规则进行分组，
6. 基本设施将在以后允许并行搜索、部分有序的成本度量和动态计划
7. 广泛的跟踪支持，
8. 和 清晰的接口和实现，充分利用了C++的抽象机制。

我们对每个问题的设计选择进行了描述和证明。这里描述的优化器系统已经投入使用，并将成为Tandem的NonStop SQL产品和Microsoft的SQL Server产品中新的查询优化器的基础。

前言

在我们使用EXODUS优化器/生成器[GrD87]的经验基础上，我们在Volcano项目[GrM93]中构建了一个新的优化器生成器。EXODUS工作的主要贡献是基于从声明性规则、逻辑和物理代数生成代码的优化器生成器架构，将查询优化器划分为模块化组件，并定义了由数据库实现者（DBI）提供支持函数的接口定义。而Volcano工作则将改进的可扩展性与基于动态规划和记忆化的高效搜索引擎相结合。通过在两个应用中使用Volcano优化器生成器，即面向对象数据库系统[BMG93]和科学数据库系统原型[WoG93]，我们发现了其设计中的一些缺陷。克服这些缺陷是Cascades项目的目标，这是一个全新的可扩展优化器项目，应用了从Volcano项目中学到的许多经验教训，包括可扩展查询优化、并行查询执行和物理数据库设计。与Volcano的设计和实现相比，新的Cascades优化器具有以下优势。作为整体，它们在功能性、易用性和稳健性方面相对于我们自己以及其他相关工作都有了显著的改进。

• 定义DBI-优化器接口的抽象接口类，并允许DBI定义子类层次结构
• 将规则表示为对象
• 支持模式和甚至查询特定的规则
• 简单规则，需要最少的DBI支持
• 替代规则由复杂表达式组成
• 将输入模式映射到DBI提供的函数的规则
• 放置属性强制执行器（例如排序操作）的规则
• 可以是逻辑和物理的算子，例如谓词
• 匹配整个子树的模式，例如谓词
• 将优化任务表示为数据结构
• 递增枚举等价逻辑表达式
• 引导或穷举搜索
• 根据承诺对移动进行排序
• 规则特定的指导
• 递增改进估计的逻辑属性

本文将讨论上述列表中的各个点及其影响。虽然该系统已经投入使用，但我们尚未进行任何性能研究，该系统也尚未完全调优。对Cascades优化器效率的详细分析和重点改进留待进一步工作。

优化算法和任务

优化算法被分成了几个部分，我们称之为“任务”。虽然每个任务可以很容易地实现为一个过程，但我们选择将任务实现为对象，这些对象除了其他方法外，还有一个为它们定义的“执行”方法。任务对象比过程调用提供了显著更大的灵活性，特别是在搜索算法和搜索控制方面。对于每个尚未完成的任务，都存在一个任务对象；所有这些任务对象都被收集在一个任务结构中。目前，任务结构被实现为一个后进先出的堆栈；然而，其他结构也可以很容易地想象出来。特别地，任务对象可以在任何时候非常容易地重新排序，从而为启发式指导提供非常灵活的机制。此外，我们计划通过一个图来表示任务结构，该图捕捉任务之间的依赖关系或拓扑排序，并允许使用共享内存进行高效的并行搜索。然而，为了快速获得一个可工作的系统，当前的实现被限制为一个后进先出的堆栈，并且调度一个任务非常类似于调用一个函数，唯一的区别是在子任务完成后需要安排任何后续工作作为单独的任务。

图1

图1显示了构成优化器搜索算法的任务。箭头表示哪种类型的任务调度（调用）哪种其他类型的任务；虚线箭头表示调用涉及输入的位置，即子查询或子计划。任务的简要伪代码也在附录中给出。"optimize()"过程首先将原始查询复制到内部的"memo"结构中，然后使用一个任务来触发整个优化过程，该任务用于优化与原始查询树根节点对应的类，这又会触发越来越小的子树的优化。

优化一个组或表达式的任务代表了Volcano优化器生成器中所称的"优化目标"：它将一个组或表达式与成本限制以及所需和排除的物理属性相结合。执行这样的任务会导致计划或失败。优化一个组意味着为组中的任何表达式找到最佳计划，因此应用规则到所有表达式，而优化一个表达式则从单个表达式开始。前者通过为每个表达式调用后者来实现。后者会产生传递性规则应用，因此，如果规则集是完整的，则在起始表达式的组中找到最佳计划。这两种任务类型之间的区别纯粹是出于实用原因。一方面，必须有一个任务来找到组中任何表达式的最佳计划，以便在应用实现规则后启动整个查询树或子树的优化；另一方面，必须有一个任务来优化一个单独的（新的）表达式，在应用转换规则后。

优化一个组的任务还实现了动态规划和记忆化。在启动所有组表达式的优化之前，它会检查是否已经追求了相同的优化目标；如果是，则简单地返回在早期搜索中找到的计划。重用早期推导出的计划是动态规划和记忆化的关键方面。探索一个组或表达式是Volcano优化器生成器中没有相应概念的全新概念。在Volcano搜索策略中，第一阶段应用所有转换规则来创建查询及其所有子树的所有可能逻辑表达式。第二阶段，即执行实际优化的阶段，在等价类和表达式的网络中导航，应用实现规则以获取计划，并确定最佳计划。

在Cascades优化器中，这种分为两个阶段的方式被废除了，因为推导所有逻辑上等价的表达式形式（例如谓词的所有形式）并没有什么用处。一个组只在需要时使用转换规则进行探索，并且只探索以创建与给定模式匹配的组的所有成员。因此，探索一个组或表达式（这两者之间的区别反映了优化一个组或表达式之间的区别）意味着推导出与给定模式匹配的所有逻辑表达式。模式是任务定义的一部分，它是规则的前提或"before"模式的子树。

与优化任务一样，探索任务也避免了重复工作。在探索一个组的表达式之前，探索组的任务会检查是否已经为给定组探索了相同的模式。如果是这样，任务会立即终止而不生成其他任务。因此，通过动态规划来保留和重用先前搜索工作的结果，也减少了扩展逻辑表达式的整体工作量。判断一个模式是否已经被探索过是通过由DBI初始化和管理的"模版记忆"来进行的决策。

为了使这个讨论更具体化，考虑一个连接结合律规则。在Volcano中，在实际优化阶段开始之前，所有等价类都被完全扩展以包含所有等价的逻辑表达式。因此，在优化阶段中，当一个连接算子与规则中的顶部连接算子匹配时，规则的下层连接的所有连接表达式都是可用的，因此规则可以立即应用于所有可能的绑定。在Cascades中，这些表达式不是立即可用的，必须在应用规则之前推导出来。探索任务提供了这个功能；它们不像Volcano中的预优化阶段那样被调用，而是按需为特定的组和特定的模式调用。

人们可能会问，Volcano技术和Cascades技术中哪种更高效、更有效。Volcano技术在第一阶段中详尽地生成了所有等价的逻辑表达式。即使实际的优化阶段使用了贪婪搜索算法，Volcano中的第一阶段仍然必须是详尽的。在Cascades技术中，这代表了最坏的情况。如果没有指示哪个规则可能导致与给定模式匹配的表达式，就无法避免对所有等价的逻辑表达式进行详尽枚举。另一方面，如果有一些指导，就可以避免一部分工作，Cascades搜索策略似乎更优越。然而，同一个组可能需要为不同的模式进行多次探索；如果是这样，可能会发生冗余的规则应用和推导。为了避免这种情况，"memo"结构中的每个表达式都包括一个位图，指示已经应用了哪些转换规则，因此不应重新应用。因此，我们认为Cascades搜索策略更高效，因为它只为真正有用的模式探索组。在最坏的情况下，即没有任何指导的情况下，Cascades搜索的效率将与Volcano搜索策略相等。

然而，如果这种指导是错误的，可能会导致搜索空间的错误剪枝，从而使Cascades优化器的效果受到影响。因此，确保这种指导是正确的非常重要。我们计划使用两种尚未实现的技术来进行指导。首先，通过检查整个规则集，特别是每个规则前提（"before"模式）和结果（"after"模式，替代）的顶级算子，我们可以确定哪些算子可以在单个规则应用中映射到其他算子。通过对这种可达性关系的传递闭包进行计算，我们可以排除一些规则的考虑。请注意，这个传递闭包可以在从规则集生成优化器时计算，即只需计算一次。其次，我们计划通过DBI实现指导机制。

应用规则会创建一个新的表达式；请注意，新的表达式可以是复杂的（由多个算子组成，如连接结合律规则），可以是转换规则（创建一个新的逻辑表达式）或实现规则（创建一个新的物理表达式或计划）。实际上，由于一个算子可以既是逻辑的又是物理的，一个规则可能既是转换规则又是实现规则。对于这样的规则，正确的规则应用是有保证的，尽管我们预计这样的算子和规则是例外而不是常规。

执行"应用规则"任务相当复杂。它可以大致分为四个组成部分。首先，为规则的模式派生并逐个迭代所有绑定。其次，对于每个绑定，使用规则创建一个新的表达式。请注意，对于函数规则，每个绑定可能有多个新的表达式。第三，将新的表达式集成到"memo"结构中。在这个过程中，识别并从进一步考虑中删除已经存在于"memo"中的表达式的精确副本。第四，对于不是之前表达式的重复的每个表达式，使用触发当前规则应用的相同目标和上下文进行优化或探索。让我们依次讨论这四个组成部分。

由于每个规则的前提（"before"模式）可能很复杂，Cascades优化器采用了一种复杂的过程来识别规则的所有可能绑定。这个过程是递归的，每个节点在模式中都有一个递归调用。它的大部分复杂性用于获取规则模式的所有可能绑定。实际上，该过程被实现为一个迭代器，每次调用都会产生下一个可行的绑定。这个迭代的状态被捕获在"BINDING"类中，每个模式中的节点都有一个该类的实例。一旦找到一个绑定，它就被转换成由"EXPR"节点组成的树（请注意，这个类是DBI接口的一部分，而优化器的内部数据结构不是）。这个复制步骤代表了一些努力，但它将优化器与可能为这个树调用的DBI方法隔离开来。对于每个绑定，调用规则的条件函数，然后将符合条件的绑定转换为规则的结果（"after"模式，替代）。对于某些规则，这非常容易，完全由优化器处理。对于其他规则，DBI指定了一个函数来创建substitute，这个函数被重复调用以创建尽可能多的substitute。换句话说，这个函数可能是一个迭代器，在连续的调用中产生多个substitute。因此，如果可能的话，从"memo"中提取绑定的努力将为多个转换发挥作用。

然后，每个 substitute 表达式都被集成到"memo"结构中。这个过程包括搜索和检测重复的表达式，即在优化中之前派生的表达式。这个过程与EXODUS和Volcano优化器生成器中的重复表达式检测非常相似。它是一个递归过程，从 substitute 的叶子开始，这些叶子可以是查询或计划树的叶子（即扫描），也可以是表示重写操作范围的叶子算子（作为DBI接口的一部分描述），并向上工作到substitute的根；这个方向是正确的重复检测所必需的。搜索重复的过程非常快，因为它使用一个哈希表，使用算子和其输入组作为键。

最后，如果 substitute 的根是一个新的表达式，可能会启动后续任务。如果substitute是作为探索的一部分创建的，则创建一个任务来探索相同模式的 substitute。如果 substitute 是作为优化的一部分创建的，则后续任务取决于规则是转换规则还是实现规则，即substitute的根算子是逻辑算子还是物理算子。请注意，一个算子既可以是逻辑的又可以是物理的；因此，一个规则既可以是转换规则也可以是实现规则。在这种情况下，将创建两种类型的后续任务。对于逻辑根算子，创建一个优化任务来优化substitute，保持相同的优化目标。对于物理根算子，安排一个新任务来优化算子的输入并计算处理成本。"优化输入"任务与所有其他任务都不同。虽然所有其他任务都安排了后续任务，然后消失了，但这第六种任务类型会多次活动。换句话说，它安排一个后续任务，等待其完成，恢复并安排下一个后续任务，依此类推。后续任务都是相同类型的，即为适当的优化目标优化输入组。因此，像Volcano搜索策略一样，Cascades搜索引擎保证只有那些确实可以参与查询评估计划的子树和有趣的属性被优化。每次在输入被优化后，"优化输入"任务获取派生的最佳执行成本，并为优化下一个输入派生一个新的成本限制。因此，剪枝尽可能紧密。

数据抽象和用户界面

开发Cascades优化器系统需要迅速交替进行三种不同的活动。首先，设计数据库实现者和优化器之间的接口必须专注于最小化、功能性和清晰的抽象。其次，实现一个原型优化器作为我们自己的DBI是一种利用接口尽可能有效的练习。第三，设计和实现高效的搜索策略是基于EXODUS和Volcano项目中学到的经验教训，结合学术和工业查询优化研究人员的研讨会和该软件的第一个用户组提出的要求。这三个活动各有不同的目标，需要不同的思维方式；在我们的内部讨论中，我们不断地在这些角度之间交替，以设计和开发一个真正可扩展和有用的工具。在本节中，我们描述了为数据库实现者和优化器之间的接口所做的数据结构决策。

EXODUS和Volcano优化器生成器的用户明确表示这些系统的接口可以改进。来自Volcano优化器生成器用户的反馈与我们自己的分析相匹配[BMG93]；因此，我们专注于：

1. 支持函数的清晰抽象，以便优化器生成器可以从规范中创建它们，
2. 规则机制，允许DBI选择规则或函数来操作算子参数（如谓词），
3. 更简洁和完整的接口规范，无论是在代码中还是在书面文档中。

遵循这些指导方针，我们设计了以下接口。

在Cascades优化器和DBI之间的接口中，每个类都被设计为成为子类层次结构的根。因此，创建这些类中的任何一个的新对象都与另一个类相关联。例如，创建一个新的"guidance"结构与一个"rule"对象相关联。规则对象可以是接口类"RULE"的某个DBI定义的子类，新创建的指导结构可以是接口类"GUIDANCE"的任何DBI定义的子类。优化器仅依赖于在此接口中定义的方法；DBI可以在定义子类时添加其他方法。

算子及其参数

任何数据库查询优化器的核心都是查询语言和查询评估引擎中支持的算子集合。请注意，这两个集合是不同的；我们称它们为逻辑算子和物理算子[Gra93]。虽然以前的可扩展算子要求这两个集合是不相交的，但我们已经放弃了这个要求。Cascades优化器接口中的"OP-ARG类"包括逻辑算子和物理算子。对于每个算子，一个名为"is-logical"的方法指示算子是否是逻辑算子，而一个名为"is-physical"的第二个方法指示算子是否是物理算子。实际上，可能存在一个既不是逻辑算子也不是物理算子的算子；如果优化是组织成包括"非终端符"的扩展语法，如Starburst优化器[Loh88]，这样的算子可能是有用的。另一方面，希望这样做的DBI可以轻松地保持逻辑和物理算子的严格分离，例如，通过定义具有适当的"is-logical"和"is-physical"方法定义的子类，并将所有算子定义为这两个类的子类。

算子的定义包括它们的参数。因此，不需要或提供类似于EXODUS和Volcano中的"参数传递"的单独机制。然而，请注意，有两个关键的功能允许和鼓励将谓词等建模为逻辑和物理代数中的主要算子，这在我们在EXODUS和Volcano框架中构建的所有原型中都将其建模为算子参数。首先，一个算子可以既是逻辑的又是物理的，这对于单记录谓词是自然的，在System R中被称为"sargable" [SAC79]。其次，特定的谓词转换，例如，从复杂谓词中分离出可以通过连接推送的组件，最容易和高效地在DBI函数中实现，而不是作为由优化器的搜索引擎解释的规则，可以轻松地在调用DBI提供的规则中实现，将表达式映射到替代表达式（一个或多个）。因此，在EXODUS和Volcano的工作反复受到批评，认为谓词操作非常繁琐之后，Cascades优化器提供了大大改进的功能。

优化器的设计不包括对要优化的逻辑和物理代数的假设；因此，没有查询或计划算子内置于优化器中。然而，为了在规则中使用，有两个特殊的算子，称为"LEAF-OP"和"TREE-OP"。叶子算子可以作为任何规则中的叶子使用；在匹配过程中，它可以匹配任何子树。在应用规则之前，从搜索内存中提取与规则模式匹配的表达式；当规则模式具有叶子时，提取的表达式也具有叶子算子，这些叶子算子通过数组索引引用搜索内存中的等价类。树算子类似于叶子算子，只是提取的表达式包含整个表达式，与其大小或复杂性无关，直到逻辑代数中的叶子算子。这个算子在与函数规则结合使用时特别有用，下面将对其进行描述。

除了"is-logical"和"is-physical"方法之外，所有算子都必须提供一个"opt-cutoff"方法。给定一个优化任务期间的一组移动，该方法确定将追求其中多少个，显然是最有前途的。默认情况下，将追求所有可能的移动，因为穷举搜索保证会找到最优的计划。还有一小组方法，只需要为已声明为逻辑的算子提供。对于模式匹配和查找重复表达式，需要匹配和哈希方法。用于查找和改进逻辑属性的方法用于确定原始属性集（例如，模式），然后在找到替代表达式时改进它（例如，更多关于选择性或输出大小的边界）。最后，对于探索任务，可能会调用算子来初始化模版记忆，并决定在探索任务期间追求多少步。

同样地，物理算子也有一些方法。显然，有一种方法可以确定算子（物理）输出属性，即表示的属性。此外，还有三种方法计算和检查成本。第一种方法计算算法的本地成本，不考虑其输入的成本。第二种方法将算法的成本和物理属性结合起来，计算整个子计划的成本。这三种方法中的第三种方法在优化算法的两个输入之间验证成本限制是否已超过，并计算在优化下一个输入时要使用的新成本限制。最后，正如最后一种方法将表达式的成本限制映射到其输入之一的成本限制一样，还有一种方法将表达式的优化目标映射到其输入之一的优化目标，即成本限制和所需和排除的物理属性，称为"input-reqd-prop"。接下来让我们讨论属性及其方法。

逻辑和物理的属性、成本

用于预期执行成本的接口"类COST"非常简单，因为成本实例是由与其他类（例如算子）相关联的方法创建和返回的。除了销毁和打印之外，成本的唯一方法是比较方法。同样，用于封装逻辑属性的"类SYNTH-LOG-PROP"的唯一方法是哈希函数，它允许更快地检索重复表达式。由于即使这个函数也不适用于物理表达式，因此封装物理属性的"类SYNTH-PHYS-PROP"根本没有方法。用于所需物理属性的类"REQD-PHYS-PROP"只有一个与之相关联的方法，该方法确定合成的物理属性实例是否涵盖所需的物理属性。如果一个属性集比另一个属性集更具体，例如，一个属性集指示按属性"A、B、C"排序的结果，而另一个属性集仅要求按"A、B"排序，则比较方法返回值"MORE"。此方法的默认实现返回值"UNDEFINED"。

表达式树

为了在DBI和优化器之间传递表达式（例如查询、计划或规则），接口中还有另一个抽象数据类型，称为"类EXPR"。该类的每个实例都是树中的一个节点，由一个算子和两个指向输入节点的指针组成。显然，任何表达式节点中的子节点数量必须等于节点算子的arity函数。除了构造函数、析构函数和打印函数之外，表达式节点上的方法还包括提取算子或其中一个输入的方法，以及匹配方法，该方法递归遍历两个表达式树，并为每个节点的算子调用匹配方法。

启发式搜索

除了模式、成本限制和所需和排除的物理属性之外，规则应用还可以通过"类GUIDANCE"的实例来控制启发式。它的目的是将优化启发式从一个规则应用传递到下一个规则应用。请注意，成本和属性涉及到正在操作的表达式以及这些表达式在执行查询计划时将产生的中间结果；Guidance类捕获有关搜索过程和启发式的知识，以用于未来的搜索活动。例如，一些规则（如可交换性规则）只能应用一次；对于这些规则，作为DBI接口的一部分，提供了一个简单的Guidance结构和一个规则类，称为"ONCE-GUIDANCE"和"ONCE-RULE"。一些研究人员主张将查询优化器的规则集划分为可以逐个调用的"模块"，例如Mitchell等人[MDZ93]。guidance结构可以轻松地促进这种设计：guidance结构指示应选择哪个模块，每个规则在其promise（或condition）函数中检查此指示，然后在为其新创建的表达式及其输入创建guidance结构时创建适当的指示。

模版记忆

除了搜索引导，探索工作还可以通过使用模版记忆来限制。模版记忆的目的是防止同一组被不必要地探索，例如，对于相同的模式进行两次探索。每个组都有一个与之关联的模版记忆实例。在为模式探索组之前，允许模版记忆将模式添加到自身，并询问是否应进行探索。在最简单的搜索中，通过对变换规则进行穷举应用来执行任何模式的探索，模版记忆只需要包含一个布尔值，即一个记忆，用于记录该组是否先前已被探索过。更复杂的模版记忆将存储每个模式。

显然，模版记忆与探索承诺函数相互作用。对于始终允许穷尽搜索的最简单的承诺函数，上述简单模版记忆是合适的。DBI需要设计最适合要优化的代数的模版记忆和承诺函数。

除了检查给定模式是否已存在于内存中，并保存以检测具有相同模式的第二次探索之外，模版记忆的最复杂方法是将两个模版记忆合并为一个。当检测到两个等价表达式组实际上是一个时，即当转换后的表达式已经出现在搜索内存中的另一个组中时，就需要使用此方法。

规则

除了算子之外，Cascades优化器中另一个重要的对象类别是规则。请注意，规则是对象；因此，可以在运行时创建新规则，可以打印规则等。虽然其他基于规则的优化器，特别是EXODUS和Volcano优化器生成器，将逻辑和物理算子以及（逻辑）转换和（物理）实现规则划分为不相交的集合，但Cascades优化器不区分这些规则，除了在新创建的表达式上调用"is-logical"和"is-physical"方法之外。所有规则都是"类RULE"的实例，该类提供规则名称、前提（"before"模式）和结果（substitute）。模式和substitute表示为表达式树，这些树在上面已经讨论过。

在它们最简单的情况下，规则不包含更多内容；每当找到模式或可以通过探索任务创建模式时，替代表达式就包含在搜索内存中。规则的模式和substitute都可以任意复杂。在EXODUS和Volcano优化器生成器中，实现规则的substitute不能超过一个实现算子；在Cascades设计中，这个限制已经被取消了。剩下的限制是除了substitute的顶级算子之外，所有算子都必须是逻辑算子。例如，可以将（逻辑）连接算子转换为（物理）嵌套循环算子，并在其内部输入上使用（逻辑）选择，从而将选择谓词从连接算法中分离出来并将其推入内部输入树中。

对于更复杂的规则，支持两种类型的条件函数。它们都考虑了规则以及当前的优化目标，即成本限制和所需和排除的物理属性。首先，在探索开始之前，“promise”函数通知优化器规则可能有多有用。优化任务和探索任务各有一个promise函数。对于未经引导的穷尽搜索，所有promise函数都应返回值1.0。值为0或更低将阻止优化器继续为当前规则和表达式工作。默认的promise函数如果需要特定的物理属性，则返回0，如果substitute是实现算法，则返回2，否则返回1。如果与算子相关联的截止方法选择穷尽搜索（见上文），则promise函数的返回值不会改变最终查询评估计划的质量，尽管它可能会影响发现计划的顺序、剪枝效果和因此优化所需的时间。

由于promise函数在探索子组之前被调用，即在完整的表达式树对应于规则的模式已被探索并从搜索内存中提取之前，"condition"函数在探索完成并且与规则中的模式相对应的完整算子集合可用后检查规则是否真正适用。虽然promise函数返回表示承诺等级的实数值，但condition函数返回一个布尔值，以指示规则是否适用。

除了promise和condition函数之外，一小组方法与规则相关联。当然，有构造函数、析构函数和打印方法，以及提取模式、substitute、规则名称和其元数（模式的叶算子数量）的方法。"rule-type"方法指示规则是简单规则（如上所述）还是函数规则（稍后将进行描述）。"top-match"方法确定搜索内存中的算子是否与规则模式中的顶级算子匹配；这个方法是在调用promise函数之前唯一内置的检查。"opt-cases"方法指示如何使用不同的物理属性优化物理表达式的次数。除了少数情况外，这将是1；其中少数例外是具有两个等式子句（例如"R.A == S.A and R.B == S.B"）的合并连接算法，应该对两个排序顺序（按"A，B"排序和按"B，A"排序）进行优化。默认情况下，此方法返回1。其余的方法都创建新的指导结构，用于优化新创建的表达式及其输入。对于优化和探索，每个都有两种方法，对于新表达式和其输入，分别称为"opt-guidance"、"expl-guidance"、"input-opt-guidance"和"input-expl-guidance"。默认情况下，它们都返回"NULL"，即没有特定的指导。

如果一个规则的substitute只包含一个叶算子，那么这个规则就是一个约简规则。如果一个约简规则是适用的，那么搜索内存中的两个组将被合并。另一方面，如果一个规则的模式只包含一个叶算子，那么这个规则就是一个扩展规则，它总是适用的。Cascades优化器必须依赖于DBI来设计适当的promise和condition函数，以避免无用的转换。尽管如此，有一类重要的情况，扩展规则是有用的，即插入强制或保证所需物理属性的物理算子。这样的规则也可以称为强制规则。考虑合并连接的输入，它们必须排序。一个强制规则可以插入一个排序操作，规则的promise和condition函数必须只允许这个规则，如果需要排序顺序，排序算子的"input-reqd-prop"方法必须设置排除属性，以避免考虑产生所需排序顺序的计划作为排序运算子的输入。

在某些情况下，编写一个直接转换表达式的函数比为相同的转换设计和控制规则集更容易。例如，将复杂的连接谓词分成适用于左、右和两个输入的子句是一个最好由单个函数实现的确定性过程。对于这些情况，Cascades优化器支持第二类规则，称为"FUNCTION-RULE类"。一旦提取出与规则模式相对应的表达式，就会重复调用迭代器方法来创建表达式的所有substitute。请注意，如果在规则的模式中使用了树算子（见上文），则提取的表达式可以任意深和复杂。因此，树算子和函数规则允许DBI编写几乎任何转换。在极端情况下，一组函数规则可以执行所有查询转换，尽管这将破坏Cascades框架的某些目的。

未来工作

当然，有很多工作需要做，以使Cascades优化器更加有用和完善。首先，优化器尚未经过彻底的评估和调优阶段。其次，基于这个框架构建额外的优化器无疑会显示出许多尚未明显的弱点。第三，一个或多个生成器，可以根据更高级的数据模型和代数描述生成Cascades规范，将非常有用。第四，我们已经知道一些对搜索策略及其实现的改进是可取的。

Cascades优化器的设计目标是具有合理的速度，尽管可扩展性是更重要的设计目标。将优化器框架和DBI的算子、成本函数等规范分离的结果是广泛使用虚拟方法、结构之间非常多的引用以及非常频繁的对象分配和释放。虽然这是不可避免的，但可能还有改进的空间，特别是如果愿意放弃强制分离，以允许修改DBI代码而无需重新编译Cascades代码。然而，在进行这个"去模块化"步骤之前，应该基于测量研究做出强有力的论据，证明这确实会提高优化器的性能。

总结

除了比EXODUS和Volcano优化器/生成器更好、更健壮的实现之外，Cascades优化器还提供了许多优点，而不放弃在这些早期原型中探索的模块化、可扩展性、动态规划和记忆化。首先，谓词和其他项操作可以方便地建模为查询和计划代数的一部分。算子既是逻辑的又是物理的；因此，很容易指定可能出现在优化器输入（查询）和输出（计划）中的算子。函数规则和树算子允许使用DBI提供的函数直接操作甚至复杂的项操作树。其次，排序等强制器在所有方面都是普通的算子；特别是，它们是基于显式规则插入计划的算子。在Volcano中，它们是不出现在任何规则中的特殊算子。第三，探索（枚举等效逻辑表达式）和优化（将逻辑表达式映射到物理表达式）都可以由DBI进行指导和控制。加上更健壮的实现，以满足工业部署的要求，我们相信Cascades优化器代表了比早期可扩展数据库查询优化器更为重大的改进。

（具体类似的实现可以参考Calcite TopDownRuleDriver代码）

本文主要基于 Chatgbt 3.5 。

致谢

Tandem的查询处理组在迫使我解决EXODUS和Volcano优化器生成器中未解决的难题以及寻找有效和可用的解决方案方面非常有帮助。David Maier在Cascades优化器的设计和开发过程中一直是一个很好的想法交流平台。

参考文献

[BMG93] J. A. Blakeley, W. J. McKenna, and G. Graefe, Experiences Building the Open OODB Query Opti- mizer, Proc. ACM SIGMOD Conf., Washington, DC, May 1993, 287.

[GrD87] G. Graefe and D. J. DeWitt, The EXODUS Optimizer Generator, Proc. ACM SIGMOD Conf., San Francisco, CA, May 1987, 160.

[Gra93] G. Graefe, Query Evaluation Techniques for Large Databases, ACM Computing Surveys 25, 2 (June 1993), 73-170.

[GrM93] G. Graefe and W. J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proc. IEEE Int’l. Conf. on Data Eng., Vienna, Austria, April 1993, 209.

[Loh88] G. M. Lohman, Grammar-Like Functional Rules for Representing Query Optimization Alternatives, Proc. ACM SIGMOD Conf., Chicago, IL, June 1988, 18.

[MDZ93] G. Mitchell, U. Dayal, and S. B. Zdonik, Control of an Extensible Query Optimizer: A Planning- Based Approach, Proc. Int’l. Conf. on Very Large Data Bases, Dublin, Ireland, August 1993, 517.

[SAC79] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price, Access Path Selec- tion in a Relational Database Management System, Proc. ACM SIGMOD Conf., Boston, MA, May-June 1979, 23.

[WoG93] R. H. Wolniewicz and G. Graefe, Algebraic Optimization of Computations over Scientific Databases, Proc. Int’l Conf. on Very Large Data Bases, Dublin, Ireland, August 1993, 13.