（论文阅读-优化器）EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER

目录

ABSTRACT

Chapter 1. Introduction

Chapter 2. Terminology

2.1 查询优化器

2.2 逻辑算子和查询树

2.3 物理算子和执行计划

2.4 Groups

2.3 搜索空间

2.6 规则

Chapter 3. Related Work

3.1 System R和Starburst优化器

3.2 Exodus和Volcano优化生成器

3.3 Cascades优化器框架

Chapter 4. Structure of the Columbia Optimizer

4.1 Columbia优化器概览

4.1.1. 优化器输入

4.1.2 优化器输出

4.1.4 优化器的外部依赖

4.2 搜索引擎

4.2.1 搜索空间

4.2.1.1 搜索空间结构 - SSP类

4.2.1.2 搜索空间中的重复Multi-Expression检测

4.2.1.3 Group

4.2.1.4 Expressions

4.2.2 Rules

4.2.2.1 Rule Binding

4.2.2.2 Enforcer Rule

4.2.3 Tasks-Search Algorithm

4.2.3.1 O_GROUP - Task to Optimize a Group

4.2.3.2 E_GROUP - Task to Expand the Group

4.2.3.3 O_EXPR - Task to Optimize a Multi-Expression

4.2.3.4 APPLY_RULE - Task to Apply a Rule to a Multi-Expression

4.2.3.5 O_INPUTS - Task to optimize inputs and derive cost of an expression

4.3 Pruning Techniques

4.3.1 Lower Bound Pruning

4.3.2 Global Epsilon Pruning

4.4 Usability in the Columbia Optimizer

4.4.1 Windows Interface

4.4.2 Tracing of the optimizer

Chapter 5. Result and Performance

Chapter 2. Conclusions and Future works

---

ABSTRACT

查询性能优化是数据库系统中关键的领域之一。当代数据库应用普遍强调其优化器应具备良好的扩展能力和高性能处理能力。

查询性能优化是数据库系统中关键的领域之一。当代数据库应用普遍强调其优化器应具备良好的扩展能力和高性能处理能力。

采用Cascades优化框架构建的Columbia自顶而上的优化方案，在对搜索空间结构与搜索算法进行细致重构后，使得自顶向下的优化方案更加简洁明了。

Chapter 1. Introduction

可扩展优化器技术的第一阶段（我们称之为第一代)始于大约十年前,当时认识到需要开发新的数据模型,查询框架,编程语言以及计算架构来支持这种扩展性需求.这些项目的具体实施案例包括著名的_Earthus_与_StarBurst_等系统.其目标在于通过引入先进技术和架构,使优化器能够更加现代化以及更加容易实现规模化的部署与管理.在具体实现过程中,该团队主要采用了分层化组件设计以及基于规则的形式转换方法等创新技术.然而,尽管取得了一定成效,但这些早期工作仍存在一些局限性:一方面,系统的复杂性难以有效控制;另一方面,在性能调优效率方面还存在瓶颈;最后,系统设计仍然过分依赖基于记录的数据模型假设

第二代可扩展优化器通过引入更为复杂的搜索技术，并更加注重利用物理属性作为指引，在更为精细的策略调控下实现了显著的性能提升。尽管这类优化器具备了一定的适应性，在进一步拓展时仍面临较高的技术和实现难度。

该查询优化器框架采用了第三代技术

三代查询优化技术可被划分为两大类别的搜索策略：一种是基于Starburst风格的自下而上动态规划方法（Self-Bottom-Up Dynamic Programming Approach），另一种则是基于Cascades风格的成本评估与绑定规则驱动的分层处理方案（Cost-Based Hierarchical Binding Rule Driven Approach）。这类基于Bottom-Up的方法通常应用于传统的商业数据库系统中（Self-Bottom-Up Methods Are Commonly Employed In Conventional Commercial Databases）。然而，在扩展性方面，自下而上的方法相对逊色于自顶向下的方案（Despite Their Popularity, Bottom-Up Methods Lag Behind Top-Down Approaches In Terms Of Scalability）。因为它们要求将原始问题分解为若干子问题（This Is Primarily Due To Their Requirement Of Decomposing The Original Problem Into Smaller Subproblems）

鉴于此前基于自顶向下的优化实施所展现的情况

该框架采用自顶向下的优化策略，并特意设计了一支专业的工程队伍来实现效率提升的同时保证系统的可扩展性

为了最小化CPU和内存的使用需求,Columbia 采用了多种先进技术方案.其中包括: 高效冲突-free散列机制用于消除重复expression instance, 通过将逻辑与物理表达式区分开来以提高系统性能, 轻量型且结构紧凑的数据存储方案以节省资源, 同时构建了一种高效的group与input数据处理算法, 最后开发了一种高效的enforcer处理机制以确保系统稳定运行

另一个Columbia使用的核心技术是group剪枝技术，在大幅降低搜索空间的同时维持了规划质量。该系统会在预估high-level physical plans的成本后才开始生成lower-level plans。这些预估出的成本可作为后续优化工作的基础。通常情况下，我们可利用这些成本值来避免生成整个expression group，在搜索空间中有效地筛选出大量不具竞争力的查询方案。

除了Group剪枝方法外,Columbia大学开发了一种新的剪枝策略,即全局剪枝技术。该技术通过生成一系列可接受且接近最优解来有效地缩减了搜索空间。一旦找到一个解足够接近最优解时,优化目标便达到了预期效果,从而无需过多关注复杂的表达式。我们对这一剪枝策略进行了深入分析。研究结果表明该方法在优化效果和误差控制方面表现优异。

Chapter 2. Terminology

2.1 查询优化器

查询处理器的主要功能是接收以数据库系统数据操作语言（DML）形式提出的请求，并对其执行评估过程。

上图通过流程图的形式展示了查询处理过程中的关键步骤。DML语法中的原始查询被解析为由逻辑代数元素构建的逻辑表达式树结构，在后续计算阶段能够相对容易地被处理。该内部逻辑形式会被传递给专门负责优化查询的系统单元，并在那里将被实现的两种主要类型转换方案包括：第一种方案旨在提高查询执行效率；第二种则专注于减少资源占用。

构建一个与查询等价的可选逻辑形式的logical transformation ，例如通过swap树的left和right child节点

为了实现逻辑运算的高效执行，在硬件层面上可以选择合适的物理实现方案。其中一种常见的方法是针对join操作采用sort-merge join算法。

该过程一般会生成大量实现查询树的执行方案；基于成本模型而言, 其中包含了统计信息和其他catalog数据, 成为查询优化器的核心任务；当选择一个最佳或近最佳的物理执行方案时, 它会被传递给相应的处理单元；存储数据库作为输入资源会被用来实施这一方案, 并将处理后的结果返回给客户端.

从用户的立场来看, 查询处理过程是一个不可见的系统. 当用户希望将查询发送至数据库系统时, 他们通常会使用高阶语言, 如SQL, Quel或OQL 等等. 准确性是查询处理器必须满足的核心要求, 同时性能是立项过程中的一项关键考量. 优化器的主要任务之一就是识别出能够在规定时间内完成任务的最佳执行方案. 虽然理论上可以通过穷举法生成所有可能的执行计划并选择最优的一个, 但这种做法的成本实在过高. 即使面对简单的查询也会产生大量的替代方案. 因此, 优化器必须通过某种方式缩小其在选择候选方案时所考虑的空间范围.

查询优化涉及解决一个高度复杂的搜索问题。研究发现这一简化模型属于NP-hard类别。在动态规划方法中所必须计算的关系数目与输入关系的数量呈指数级增长。有效的搜索策略对于优化器的表现至关重要。

2.2 逻辑算子和查询树

逻辑操作符 是指定了数据转换逻辑但无需明确定义物理执行路径的一种高层操作符，在关系数据库系统中常用于接受 tables 作为输入并生成一个单独的 table 作为输出结果。每个逻辑操作符都会接收指定数量的对象（我们称之为 operator 的参数 arity），并且可以通过某些指标或类型的变化来区分不同的 operator 版本。

主要涉及的是逻辑运算符的是GET和EQJOIN这两个概念。每个GET操作符都没有输入，并且只有一个参数即是存储该relation所需的名称。该操作符会从磁盘上检索出该relation的所有记录，并将这些记录传递给后续的操作。每个EQJOIN操作符有两个输入，并且有一个额外的参数——这是一组用于定义连接条件的关系式集合。

查询树 query tree structure 是一种符号化表示整个查询过程的数据结构，并被提供给优化器作为输入使用的一种树形组织形式。通常情况下, 一个 query tree 通过 logical operators 的属性来定义其结构, 其中每个节点都代表一个逻辑运算符, 并且该运算符可以有零个或多个子节点来表示其所需操作数的数量. 每个节点的孩子数目即为该逻辑运算符所需的参数数量 arity. 查询树的作用在于确定这些逻辑运算符的操作执行顺序.

2.3 物理算子和执行计划

Physical Operator代表实现特定数据库操作的具体算法。单个或多个物理执行算法可在同一数据库上运行以实现特定查询逻辑操作。例如，在EQJOIN操作中可采用嵌套循环法、归并排序法或其他方法。这些特定算法可在不同的Physical Operator中被应用，并与Logical Operator类似地遵循固定的输入规范（即operator参数的数量arity）以及可能附加的参数设置。

在query tree中对其中的逻辑运算符进行替换后会生成一棵物理运算符树从而形成所谓的执行计划Execution Plan或访问策略access plan. 如图3所示则展示了与图2(b)对应的两种可能的执行方案.

该执行计划决定了对查询进行评估的方式。每个执行计划都对应着与成本模型及Catalog信息相关的执行成本。一般而言，在处理一个特定查询时，默认情况下系统会为其生成一个高效且合适的执行计划，并将其作为Query Execution Engine的输入使用。在运行过程中，Query Execution Engine将依据数据库系统的数据来实施相应的算法步骤，并最终生成所需的结果输出。

2.4 Groups

一个给定查询可以通过logically equivalent的一个或其他形式来表示。当两个查询树在所有情况下都能生成完全相同的最终结果时，则我们称它们为逻辑等价 logicall equivalent。每个查询树通常会有一个或多个执行方案能够生成严格一致的结果。同样地这些执行方案本身也可以被视为logically equivalent。下图展示了几个具有这种性质的例子

expression可以用来表示查询树和执行计划（或子树和子计划）。每个expression包含一个operator以及零个或一个input expression。基于operator的类型，我们将expression分为逻辑表达式或物理表达式。因此，在此语境下所述之查询树属于逻辑计划范畴（logical plan），而执行计划则是物理表达式（physical expression）。

给定一个逻辑表达式（logical expression），它将拥有一系列既是逻辑等价又是物理表达式的 logical 和 physical expressions。通过将这些表达式按组收集，并为每个组定义公共属性是很有用的做法

为了通过减少一个 group 中 expression 的数量而引入 Multi-expressions。一个 Multi-expression 由 logical 或 physical operator 组成并接受 group 作为输入。尽管 Multi-expression 和 expression 在本质上相同（其 input 是 group 而不是其他 expression），但它们在某些方面存在区别。其显著优势在于极大地节省空间（由于在一个 group 中等价的 multi-expressions 的数量较少）。如图所示，在此上下文中与 Figure 5 相比 multi-expressions 的数量有所减少。事实上，在这种情况下 Multi-expression 通过获取 group 作为输入能够代表多种不同的 expression

在典型的查询处理过程中，在生成最终元组之前会产生大量的中间元组组合（即元组的组合）。每个中间元组是通过计算某个group中的执行计划（或物理执行计划）而产生的。从这个角度来看，每个group都对应于一个中间元组（这些group统称为intermediate groups）。只有一个最终元组会被生成，并被归类为final group。

一个group中的Logical properties 被称作结果的逻辑属性，并不受该结果如何进行物理计算及组织方式的影响。这些属性包括cardinality（元组的数量）、schema和其他属性 ，它们共同作用于同一个group内的所有expression。

2.3 搜索空间

在数据库系统中，search space被定义为一个逻辑查询树（logical query structure）与物理计划（physical plans）之间的空间概念。为了优化资源利用效率，该空间采用分组（groups）体系进行组织管理：每个分组（group）负责接收其他分组（groups）作为输入，并在计算过程中进行数据整合处理。特别地，在整个计算流程中会被指定为最终group（final group），其作用就是反映初始查询（initial query）的最终评估结果。为了直观展示这一计算过程，在图中给出了初始搜索空间（initial search space）的具体分布情况

位于初始化搜索空间内的每个组仅包含一个逻辑表达式,这些逻辑表达式均源自初始查询树结构。在上图所示的情况下,组 ABC 被定义为最终查询组,它对应于三个关系联结后的最终结果。通过从初始化搜索空间内提取信息,我们可以构建起初始查询树结构,其中，在查询树中的每一个节点都对应于初始化搜索空间内的一个组中的一个多表达式。

在进行优化时，在每一个组中都会创建大量逻辑等价的 logical 和 physical 表达式以显著地扩大搜索范围。
每一个组都包含大量逻辑等价的 logical 表达式与 physical 表达式。
同时考虑物理层的构造并计算其执行成本，
并且知道这个 cost 仅与 physical 表达式相关；
然而为了构建所有 physical 表达式的结构就必须先构建所有对应的 logical 表达式的结构。

经过优化流程后, 每个group都生成了所有等价的物理表达式, 并且在所有可能执行计划被计算之后, 最优执行计划可以在搜索空间中被确定, 并作为优化器的结果输出。最终扩展后的搜索空间称为final search space, 通常地, 在一个final search空间中包含了给定查询的所有逻辑等价表达式（涉及逻辑和物理层面）。通过递归方法, 在final search空间中可以提取出所有可能的查询树

但潜在query tree的数量会随着执行计划节点的增长呈指数级增长。下表展示了具有n个relation的一个具有完全逻辑搜索空间且仅考虑logical expressions复杂度的情况。假设在search space中有N个loigcal expressions，并且该数据库系统中存在M个join algorithms，则最终搜索空间将包含M×N physical expressions.

2.6 规则

许多类型的优化器会根据预设的规则集合生成与初始查询等价的不同表达式。每个Rule定义了一套转换策略用于从现有的表达式推导出新的逻辑等价表达式。通过应用这些Rule到现有的表达式上，在实际应用中，这些规则被整合到优化算法中以实现对搜索空间的有效扩展，并最终生成完整的逻辑等价表达式集合。

每个规则都会说明一对特定模式（pattern）与替代项（substitute）。模式用来描述可以在这种规则下发挥作用的逻辑表达式的结构；替代项则指定了在这种规则下应用后会产生什么样的结果结构。当优化器在扩展搜索空间时（注意这些规则不仅仅单独应用于单一逻辑表达式），它会遍历每一个逻辑表达式，并判断该表达式是否符合任意一条规则中的模式部分；如果某个模式匹配成功，则该规则会被触发相应的处理流程，并根据替代项部分生成新的等效逻辑表达式。

Cascades通过expression来表示Pattern与Substitute两类元素。其中Pattern始终采用logical表达式的形式；而Substitute既可以是logical表达式也可以是physical表达式。主要包含Transformation规则与Implementation规则两种类型。当一个Rule的Substitute采用logical表达式时，则被称为Transformation规则；当一个Rule的Substitute采用physical表达式时，则被称为Implementation规则（如图所示）。

Chapter 3. Related Work

查询优化工作的开创性可追溯至二十年前。IBM的System R优化器[SAC+79]不仅获得了显著的成功，并且运行得非常出色。它已经成为当前许多商业优化器的基础。

数据库系统与应用不断进化发展，在面对数据库系统的进一步扩展需求时，则需要新一代的可扩展优化器予以支撑。关系数据模型拓展了更多特性，在包括新增数据类型与操作功能等方面均有显著提升。引入面向对象的数据模型旨在解决更为复杂的存储需求。由于早期设计仅针对相对简单的传统关系数据模型进行开发，在此背景下则演变为专门应对日益复杂的现实环境而产生的新一代可扩展性增强型优化器系列。这些新型优化器不仅专注于提升可扩展性这一核心能力，并且也致力于克服所有层次优化任务中的共同挑战——即追求更高的效率目标。本章将深入探讨对查询优化领域产生深远影响的关键技术

3.1 System R和Starburst优化器

System R优化器的一个重要贡献在于实现了统计式的成本估计（statistical-based cost estimation）。该优化器通过系统中预存的关系和索引信息（stored relations and indexes in the system catalog）推断出执行查询评估计划所需的成本（cost）。这一成本估算过程被划分为两个主要环节：一是计算操作符（operators）的成本（estimating operator costs）；二是评估查询块的结果规模（estimating query block size），以及是否对其进行排序处理（and whether sorting processing is required）。

为了估算 operator 的成本需要获取 input relation 的各种参数。例如 cardinality(relation size)、pages 的数量以及可用索引。这些统计信息存储在 DBMS system catalog 中。大小估计（大小估计） 在成本估算中起着至关重要的作用。因为一个操作符的操作结果可能作为另一个操作符的操作输入，并且操作符的成本与输入的数据量密切相关。System R 开发了一系列用于评估大小的数据公式。这些公式仍然被现代查询优化器采用。尽管近年来提出了基于更详细统计数据的新技术（例如系统值直方图）。

System R优化器的另一个重要贡献是自底向上的动态规划搜索策略。动态规划的核心思想是在查询树中找到底层的查询块（query block的概念对应于Cascade/Columnbia中的group），并为每个查询块保留最优计划（即每个query block只保存其最优解决方案）。这种自底向上的策略意味着它总是优先优化较低层次的表达式。为了计算上层表达式的成本（包括每个表达式的规模），我们必须计算所有下层输入的成本（包括每个表达式及其规模）。动态规划的关键技巧在于：在优化一个查询块后（例如找到了一个最优计划），我们舍弃该查询块的所有等价表达式，并仅保留这个查询块的最终计划以供后续使用。然而由于需要考虑O(3^N)个不同的表达式（plan的数量呈指数级增长），当N较大时系统R优化器需要考虑的表达式数量变得不可管理。因此系统R优化器同时采用了启发式方法来减少搜索空间：例如将涉及笛卡尔积的优化推迟到处理阶段最后或在处理大规模查询时仅考虑左深树结构（从而排除了大量的bushy tree结构）。然而这种做法可能会导致被迫选择次优解的情况出现因此无法保证全局最优性

IBM的Starburst[HCL90]优化器基于规则实现了良好的扩展性，并显著提升了System R优化器的功能。该系统由两个核心组件构成：一个是基于Query Graph Model（QGM）的知识型查询重写系统；另一个是专门负责执行查询计划生成的任务驱动型Plan生成模块（Plan Generator）。其中,QGM模块负责对查询进行内部语义表示,并采用启发式的策略将原始QGM转化为语法等价但更具优势的形式,从而简化并消除冗余信息,以便后续计划生成模块能够实现有效的成本效益规划。Plan模块则作为一个集成了多种连接评估标准的选择-投影-连接（Select-Project-Join）执行引擎,其组成部分包括一种高效的连接评估机制以及一种灵活的任务调度规划算法.该引擎利用C语言实现了连接评估逻辑,并通过可配置的方式支持多种不同的枚举策略替代方案.而Plan生成模块则通过参数化的生产式规则构建了执行连接操作所需的访问计划.这些参数化的生产式规则被统称为战略替代规则（Strategic Alternative Rules, STARs）。STARs不仅能够自动识别内层表与外层表的关系,还能够自动生成适合不同连接场景的最佳执行策略

在Starburst系统中，实施查询优化采用了双阶段策略进行处理。第一阶段中，以QGM形式表示的初始查询会被QGM优化器接收并转化为更为高效的QGM版本；随后将新生成的QGM传递至plan优化器进行后续处理。第二阶段中，在plan与QGM两个优化器之间建立通信渠道以确定访问路径，并通过类似于System R采用自底向上的方法生成最优执行计划

该QGM优化工具有执行复杂启发式的功能。因此它对Starburst优化工具的有效性产生帮助作用。然而在某些情况下启发式可能会导致错误决策这是因为它们仅基于逻辑信息而不受成本估算的影响即它们无法考虑具体成本因素。另一方面启发式方法难以扩展以适应更加复杂的涉及非关系运算符的数据库查询问题显然基于语法与规则的方法将有助于扩大数据库优化工的能力但如何利用这种方法来处理涉及非关系运算符以及复杂转换的问题仍待探索

3.2 Exodus和Volcano优化生成器

Exodus优化生成器是第一个使用top-down优化方法的可扩展优化器框架。Exodus的目标是为最小化数据模型的查询优化建立一个基础设施和工具。Exodus的输入是一个模型描述文件，它描述了一组operators、一组在构建和比较访问路径时需要考虑的方法、transformation rules（定义了query tree的transformation）和implementation rules（定义了operators和methods之间的对应关系）。为了给新的数据模型实现一个查询优化器，DBI（数据库实现者）编写了一个模型描述文件和一组C过程。生成器将模型文件转换一个编译并链接到一组C过程的C程序，以生成一个特定于数据模型的优化器。生成的优化器会一步一步地转换初始的query tree，在一个名称MESH 的数据结构中维护迄今为止探索的所有替代方案的信息。在优化过程中的任意时间都会有一组可能的下一步transformation，它们被存储在一个队列结构中，称为OPEN。但OPEN非空的时候，优化器会从OPEN中选择一个transformation，将它应用到MESH中的准确的节点上，为新节点执行cost估计并将新的可用transformation加入到OPEN中。

Exodus的主要贡献在于top-down优化生成器框架的提出，在这一创新中实现了搜索策略与数据模型的有效分离，并进一步实现了transformation rule与logical operators与implementation rule与physical operators之间的清晰区分。虽然构建高效优化器并非易事，在这一探索过程中所获得的经验仍然为下一代可扩展优化器奠定了重要基础。

Volcano优化生成器的核心目标在于显著提升Exodus的效率，并致力于通过动态规划与基于物理特性导向的目标搜索相结合的方式，在剪枝和启发式引导中实现高效的定向动态规划搜索算法（directed dynamic programming）的应用。该系统采用分层策略进行搜索：子表达式仅在必要时才会被优化，并且只会优化那些真正参与较大计划优化的关键表达式及计划。Volcano通过将计算成本、逻辑属性及物理属性等关键要素封装到抽象数据类型中实现了系统的扩展性，并通过允许穷举搜索的方式确保了其有效性，在优化决策者介入下进行路径精简以达到最佳效果。

Volcano搜索策略的能力使其能够生成真正的优化器，并被应用于面向对象的数据库系统中；特别适用于那些包含大量规则的原型科学数据库系统。

3.3 Cascades优化器框架

Cascades优化器框架是一个可扩展的查询优化器框架，在保留可扩展性、动态规划机制以及记忆化功能的前提下（同时保留了前两者的优点），相比前一版本，在功能、易用性和可靠性方面实现了显著提升

Cascades优化器有以下优点：

优化任务的抽象，作为数据结构

Rules对象化

防止属性enforcers，例如sort operation的操作抽象为rule

根据promise对行为排序

谓词operator可以同时是logical和physical的

明确了DBI-optimizer接口的抽象接口类，并支持DBI对子类间的层次结构进行定制

C++编写的鲁棒性更强的代码，以及充分利用C++抽象机制的clean interface

广泛的跟踪支持和更好的文档来帮助DBI

在Cascades系统中，优化算法被分解为多个独立的部分，并命名为' tasks '对象集合进行管理。每个' task '都被设计为一个可执行的对象，并且都包含一个名为' perform '的方法定义来完成特定功能操作。这些' task '对象都会整合到同一个任务栈中，并采用后进先出（Last-In-First-Out）的方式组织存储。调度一个'Task'的过程与调用函数非常相似：当调度一个'Task'时，在堆栈顶部弹出并执行其' perform '方法操作；完成该操作后会返回堆栈顶端位置以便后续的操作继续展开；在整个优化运行周期内都会有至少一个堆栈处于待执行状态以便及时响应新的任务请求；需要注意的是，在实际运行过程中如果某个'Task'的操作导致其他相关联的任务产生副作用或者依赖关系，则可能导致新的'Task'被临时压入堆栈等待处理以确保系统的稳定性与功能性得到充分保障

Cascades优化器首先会将原始查询复制到初始化的搜索空间中（在Cascades框架中，默认情况下搜索空间被称为"memo"这一术语源自于Volcano）。随后系统会针对初始搜索空间中的顶层分组执行特定优化任务（即触发整体优化流程），从而依次展开对搜索空间中小分组的逐步优化操作。确定一个分组的最佳计划（这一步骤被定义为一个"optimization goal"）意味着对该分组内的所有表达式应用相应的规则集合（即完成一次分组优化）。在这个过程中新任务会被依次推送到任务栈中同时新增的小分组及其相关表达式也会被加入到搜索空间中。当初始顶层分组完成优化后系统会自动要求该顶层分组的所有子分组各自独立完成各自的优化工作最终确定并输出顶层分组的最佳计划从而完成整个优化过程。

从top group开始执行优化过程的角度来看,Cascades被认为基于top-down搜索策略进行操作。在优化单个group的过程中,动态规划以及记忆化技术被应用到初始化所有group的expression阶段中去。为了提高效率,Cascades会先检查是否已经完成了与之相同的优化目标;如果是的话,它会直接引用在更早搜索过程中获得的结果计划。与Volcano搜索策略相比,Cascades的主要区别在于其探索机制更为精简,即它仅在必要时才探索单个group而不提前展开预优化工作;而Volcano则始终在真正意义上的优化阶段前的第一阶段生成所有等价的logical expressions以供后续操作使用这一显著特征正是导致两者性能差异的根本原因所在

相比Volcano优化器生成器界面过于复杂，在Cascades的设计中实现了更为简明扼要的数据结构抽象与接口设计。所有Cascades优化器与DBI之间的组成类都被定位为顶层类以简化层次结构。它们仅依赖于接口中定义的基本功能；而DBI则允许在定义子类时扩展这些功能。这一关键性接口涉及核心组件：操作符（operators）、成本模型（cost models）以及规则（rules）。这一设计使得整个系统更加稳定可靠，并显著提升了开发效率

Cascades仅仅是一个用于构建高性能计算平台的核心框架系统。通过引入一系列性能改进措施；然而，在现有应用中，并非所有的特性都被充分利用或仅限于基础实现阶段。基于上述研究发现的基础之上，在团队成员的努力下开发出了一个新的高效型优化器方案——Columbia。
在现有体系架构中，默认采用强分隔原则的前提下，默认支持虚方法的广泛应用；然而，在频繁对象分配及回收的过程中，则可能带来显著的性能挑战。
针对top-down策略进行针对性剪枝的技术研究能够有效提升搜索效率。
这些研究成果不仅深化了对当前技术局限性的认识；而且也激发了我们对于Cascades未来发展方向的关注与探索。

Chapter 4. Structure of the Columbia Optimizer

以Cascades框架为基础进行研究,Columbia团队则侧重于优化过程效率的提升。本章将深入阐述该优化器的设计理念及其实现机制,并着重探讨其实现细节与现有系统如Cascades之间的异同之处。

4.1 Columbia优化器概览

下图呈现了Columbia优化器的接口设计。该系统接收了一个初始化的查询文本文件作为输入，并生成了一个最佳运行方案作为输出结果。

4.1.1. 优化器输入

位于Columbia中的优化器输入作为一个文本文件形式存在，并包含按照Lisp风格表示的原始查询树。每个树都由顶层操作符及其可能存在的子树构成；其中子树即为输入内容。每个树或其子树之间使用括号进行分隔。

该表格以文本形式详细说明了query tree的BNF定义。当前Columbia实现了基于逻辑运算符的功能模块集合GET、EQJOIN、PROJECT和SELECT，并能够覆盖大部分Select-Project-Join查询的需求。这一设计还可以通过低成本扩展来增强功能。（具体语法说明略）

优化器中的Query Parser解析查询文本文件，并将其以expression tree的形式存储起来。这种expression tree采用递归式数据结构实现方式，在类EXPR对象中由一个Operator和零个或多个EXPR对象的input组成构成。因此可以从root（top）expression开始遍历该树结构。在search space被初始化后该expression tree会被优化器复制到search space中去作为中间格式存在。这种模块化设计使得系统的扩展性非常高（highly extensible）。Query Parser与优化过程之间具有松散的关联（它接收查询文本文件并输出一个query expression），因此在parser中添加更多的操作来支持更多功能变得非常容易（for example, schema checking, query rewriting等）。在Cascades系统中初始化的查询以C++代码编写的expression tree标识，并内嵌到优化器的核心代码中进行处理。如果想要优化另一个初始查询，则必须重新编译整个优化器代码以便对初始query expression进行修改（modify）。而Columbia系统则提供了一种更为简便的方式：只需重写查询文本文件即可表示新的初始查询而不必重新编译代码。

下图展示了一个查询文本文件和对应query expression tree的样例。

如图所示，在Columbia系统中，默认引入了三种操作符：传统的逻辑运算符与物理运算符以及源自Cascades框架设计的一项新特性——item操作符。与传统的逻辑与物理运算符相比，在功能上有显著差异的是项操作符：它仅处理单个特定数据单元的操作（即单个元组），而后者则可处理任意多的数据单元（即多个元组）。一般而言，则将项操作符视为基于单一元组或数值计算的功能模块。每个项操作符都由其对应的谓词所定义——该谓词采用一种层级化的表达式树形式表示，并最终返回布尔值结果；这种层级化的谓词结构不仅便于理解各项操作之间的关联性，在执行效率方面也提供了显著优势：能够通过高效的连接操作实现谓词传播功能

4.1.2 优化器输出

通过物理表达式的缩进树形式打印出来的最佳方案已经被优化器复制出来了。最佳方案与其所对应的表达式有关联性地存储起来。最终确定的成本值相对于特定的数据目录以及成本模型而言是最为理想的。使用不同数据目录以及成本模型会导致相同的查询产生出各自独特的最佳方案

4.1.4 优化器的外部依赖

如前所述，在优化器的设计架构中包含了两类关键信息：Catalog以及Cost Model。Columbia平台同样采用文本文件的形式来描述这两类关键信息以保证灵活性与便利性。Catalog Parser以及Cost Model Parser能够提取这些数据，并将其被存储进名为'Cat'与'Cm'的全局变量中。在处理优化过程时，Optimizer会依次调用相关功能模块进行处理。

Columbia现有采用简单版本的catalog以及cost model方案；然而文本文件格式的设计则为后续的功能扩展提供了良好的基础。

4.2 搜索引擎

该文展示了一个名为Columbia搜索引擎的关键组件及其工作流程。该系统通过复制原始查询表达式来启动搜索引擎功能。其核心模块旨在扩大搜索空间并在最终结果中找到最优执行计划。在Columbia系统中，默认情况下会根据预设规则对搜索空间进行分阶段优化。这些操作会针对搜索空间中的特定组别及表达式应用相应的规则集，并通过生成新的组别及表达式来不断扩展搜索空间范围直至完成优化任务为止。

4.2.1 搜索空间

在搜索空间中，组件为groups。每个group包含一个或多个逻辑上等价的expression。

4.2.1.1 搜索空间结构 - SSP类

Search space的概念源自人工智能领域，并被用作解决优化问题的一种工具。在查询优化过程中,系统会根据特定背景信息将给定查询映射到最佳执行策略。一个典型的 search space 由一系列问题及其子问题的所有可能解决方案构成。动态规划与记忆化搜索这两种方法都采用 search space 来实现最优化求解。这些方法主要通过逻辑等价性原则来区分不同的潜在解决方案。我们将每一个这样的区域称为 Group, 因此在整个 search space 中存在多个这样的 Groups 组成结构

在Columbia中使用了一个类似于Cascades中的MEMO数据结构来表示搜索空间，并将其命名为SSP实例。该实例包含一组组数组，并通过设置该组ID标识出搜索空间中的根组。其中每个组都包含一组逻辑上等价的multi-expression集合。如前所述每个multi expression由一个运算符及零个或多个组作为输入组成因而搜索空间内的每个组要么是根组要么是其他某个根组输入链的一部分所有非根组都可以通过访问其输入链到达根组这也是为什么必须明确标出根组件的原因之一通过复制初始查询表达式搜索空间可以利用几个基础群初始化每个基础群只包含单个逻辑上的multi-expression优化过程中进一步操作会通过增加新的multi-expression以及新的群添加到搜索空间中从而扩展其规模CopyIn方法将一个表达式转换为multi-expression并将其放置于与之逻辑上等效已有的某个群内若不存在这样的群则会创建一个新的群并将该multi-expression放置于该新群内这样做的后果是新生成的这个多维表达式将会与现有某个同名多维表达式产生冲突从而触发合并机制而CopyOut方法则会在优化结束后输出最优执行计划

4.2.1.2 搜索空间中的重复Multi-Expression检测

将一个 multi-expression 放入 search space 的潜在风险是可能出现重复现象；亦即，在 search space 中可能存在与当前 multi-expression 完全相同的另一个 multi-expression。此即意味着，在进行实际添加操作之前，“这个 multi-expression”的重复行必须首先在 search space 中进行检查。“若发现有重复，则不应进行添加。”

为了检查重复性，至少有3个算法可用：

某种基于树的搜索

可扩展的hash

静态hash

尽管算法1和算法2当前已有一些代码实现但它们具有较高的复杂度其有效性尚待验证备选方案3则非常简单且易于实现然而当multi-expression的数量呈现指数级增长时可能会导致方案出现性能瓶颈一种适用于处理小规模查询情况并使用固定数量桶的哈希表在处理大规模查询时可能会导致每个桶被大量元素填充因为在这种情况下会产生更多的expression

Both Cascade and Columbia have adopted 静态哈希表（备选方案3） to enable efficient detection of multivariate expressions. As a result, the inherent issue of inevitably encountering bucket overflow remains. The search space encompasses a static hash table, which serves as the foundation for identifying duplicate entries by hashing all three components of multi-expression: operator class names, parameters, and input group numbers. The primary distinction between Columbia and Cascade lies in Columbia's implementation of an 高效的哈希函数（efficient hashing function）.

与Cascades中采用传统哈希函数的方式不同,Columbia采用了高效的哈希函数"lookup2"这一由Bob Jenkins所著原始哈希函数LOOKUP2进行了优化版本. Jenkins认为,相比于许多传统哈希算法,LOOKUP2具有更为简单的结构以及更高的效率.该算法在处理密钥中的每一个bit时,都会通过基本运算和其他三个特定数值进行混合运算.值得注意的是,每一个bit的变化都会影响最终返回值中的相应bit. lookup2的优势之一在于其哈希表大小被设定为严格的幂次方,这使得模运算能够更加高效地执行.相比之下,传统的哈希算法通常需要对素数进行取模运算这一过程,而这对于非二进制幂次方来说计算效率要低得多.考虑到频繁使用的 hash 操作对其性能的重要性这一因素,Columbia选择了一种更具效率的设计方案

由于重复仅在优化阶段（其中物理表达式基于逻辑表达式的唯一生成）针对逻辑多表达式发生，并且所有生成的逻辑多表达式都需要计算其哈希以便在搜索空间中检测重复性

该SSP类中的FindDup()方法实现了重复检测功能。在Search space中设置了指向logical multi-expression的指针结构。该方法接受一个multi-expression作为输入，并返回在Search space中发现的相同multi-extension（当存在重复时）。其算法流程如下：首先计算每个multi-extension对应的哈希值；随后，在哈希表中进行查找以识别冲突。若有冲突，则按照复杂性简单的顺序进行比较：首先是operator数量少者优先；其次是包含较少input groups的情况；最后是operator arguments的数量。若未发现重复，则新的extension将紧跟在原始extension之后，并共享相同的哈希值。若哈希表未找到冲突，则新的extension将直接插入到哈希表中。

由于在全部范围内search space中的multi-expression数量众多,Columbia所提出的这种哈希机制能够有效地简化了其重复性。

4.2.1.3 Group

Group类在top-down优化中扮演着核心角色。每个group都包含一组具有逻辑等价性的logical和physical multi-expression集合，并且因为所有multi-expression都共享相同的logical properties，在Group类中只存储了一个由所有multi-expression共同拥有的logical property指针来表示这一特性。为了实现高效的动态规划与记忆化功能，在Group类中引入了一个记录最优策略（plan）的winner结构体来辅助决策过程的选择与维护。相较于现有的Cascades系统而言，在功能实现上进行了多项改进：增加了下界相关的LowerBoundMember组件；将物理表达式（physical）与逻辑表达式（logical）进行了更加明确地分离；同时优化了赢家结构体的设计以提高搜索效率并减少资源占用量

Group中的下界**：**该组的下界L定义为一个数值阈值，在该组的所有计划P中其总成本必须不低于L。该下界在top-down优化方法中扮演着关键角色，在某组的下界高于当前上界时就可能触发剪枝操作。通过剪枝策略可以有效避免枚举所有可能的输入组别，并且不会遗漏任何潜在的最佳计划选项。在4.4.1节我们将详细探讨Columbia系统中如何实施这一剪枝策略及其对优化器性能的重要意义。需要注意的是，在每组创建时系统都会自动计算并存储该组对应的下界信息以供后续优化过程使用

本章探讨如何在Columbia系统中获取群组的下界。显然地，在优化过程中越高的下界越理想。我们的目标是通过收集群组中的信息来确定能够达到的最大下界。一旦一个群组被创建，在初始化阶段就会捕获一系列逻辑属性。这些属性包括群组的基数和schema定义。这些属性组合决定了计算出的下界数值。由于下界仅基于群组的逻辑属性计算得出，在实际操作中无需遍历该群组中的任何表达式即可完成相关运算。

在描述lower bound的计算之前，我们先给出一些定义：

touchcopy()：该函数返回一个数字型值，在任意join操作中其值小于该join操作的整体cost除以该join输出元组的数量（cardinality）。该数值表示的是生成所需输出元组所需的访问两个必要的元组所需的时间成本（即计算生成所需输出元组所需的访问两个必要的元组所需的时间成本），以及复制结果所需要的时间成本。

Function Fetch(): 平摊到每个block中的单位开销是获取一个byte所需的开销，在这种情况下，默认假设所有数据都是以block为单位进行访问。

|G|：代表group G的cardinality

考虑一个群组 G，在其基础表 A 的某些属性 X 满足 A.X 存在于 G 的 schema 中时，则称该基础表位于 G 的 schema 之中。其中 cucard(A.X) 表示列 A.X 在 G 中的唯一 cardinality。而 cucard(A)，即表示该属性集的所有子属性中的最大 cardinality，在所有 G 的 schema 中取其最大值即可得到结果。假设以 A₁,…, Aₙ（n ≥ 1）作为该群组 schema 中的基础表，并按其 cardinality 递增排列

一个group中的lower bound计算方式如下图：

在上图中，在group中我们定义了三种类型的lower bounds。由于这三种lower bounds之间存在相互独立性，则当它们汇总在一起时，则会向该group提供一个下界。

该操作针对图G中的top join操作定义了touch-copy。该操作的基础在于G所具有的基数。由于G中任意一个计划生成的结果元组集合与group内部top join操作的结果一致。对于任何join操作（包括涉及复制出去成本的操作），其总成本至少等于touchcopy()值与最终join操作基数之积。

该方法涉及对图G中非顶级连接（non-top join）的触点复制边界（touch-copy bound）进行研究。该边界依据图G各列具有唯一性（uniqueness）的特点，并参考其属性结构（attributes structure）。我们证明了该触点复制边界构成了非顶级连接（non-top join）下界（lower bound）。此结论基于理论分析。

For leaf nodes within the base tables, there is an upper limit on fetching. This limit is also dependent on the attribute structure of the G schema. It corresponds to the cost associated with retrieving tuples from base tables. (Proof omitted.)

对逻辑型与物理型multi-expressions的分离。Cascades将其存储至一个独立的linked list中。Columbia则将其存放在各自的列表中，在多方面实现了时间上的节约

随后，在执行过程中, rule会将所有的logical multi-expressions作为input来检查它们的pattern是否匹配, 由于无需关注物理上的multi-expressions, 因此我们不需要遍历它们. 每个group通常包含大量逻辑上的multi-expressions, 这些表达式可能占用多个虚拟内存页. 因此对物理multi-expressions的一个独立引用可能导致内存页错误, 这可能显著影响程序运行速度. 通常情况下, 在一个group中物理上的multi-expressions数量是逻辑上的两到三倍. 通过分别关注逻辑表达式而非物理表达式,Columbia中的规则绑定机制预期上将超越Cascades.

此外，在已经实现了对某个group的有效优化的同时

更为优化的赢家结构。
动态规划与记忆化的核心理念在于将搜索过程中产生的赢家（winners）记录下来以备后续查询。
在解决每个问题或子问题时，默认会根据当前情境进行最优方案的选择。
每一个上下文都由两个要素构成：一是所需的物理属性（例如数据需按A.X排序），二是解题成本的一个上限（例如成本必须低于5）。这使得描述更加清晰。
赢者通常表现为一种物理多表达式集合体，在特定条件下能够覆盖多个相关的查询需求。
然而，在不同类型的搜索场景中（search contexts），同一个组可能会产生不同的赢家（winners）。因此，在组结构中需要维护多个赢家对象以适应各种情况的需求。

在Cascades架构中，Winner类由两个关键组件构成：一个是引导搜索进程的上下文（context），另一个是由多个表达式组成的pair集合（multi-expression pair）。每个Winner类都整合了这两个核心元素来实现搜索优化功能。

在Columbia中有关于Winner数据结构的简化处理。在Columbia系统中存储于Winner对象内的相关上下文信息以及指向其他Winner对象的引用被省略。每个Winner类由三个核心要素构成：参与搜索并获胜的那个multi-expression、其对应的成本值以及搜索所需的关键物理属性。每个group内的多个winner实例共同代表了该组可能产生的搜索结果。因此，在每个group内部都会维护一个赢家数组（winners array），无需为组内后续胜出者维护指针。显然地，在胜出者结构的设计上，Columbia方案较之于其竞争对手方案（如Cascades）具有更为简洁高效的特点。同样地，在整个系统运行过程中，在每个step阶段结束时都会将当前胜出者的信息记录下来，并将其保存到临时结果缓存表中。下面是Columbia中的Winner类结构：

4.2.1.4 Expressions

Expression对象分为两种类型：EXPR和M_EXPR。
每个(EXPR)对象对应于查询优化中的一个expression，
而每个这样的EXPR则代表了优化器内部的一个查询或子query。
每个EXPR包含了一个OP类实例作为操作符，
并通过指向input expressions的一个指针来引用这些表达式实例。
为了简化操作流程，
在此方案中
每个EXPR将保留其操作符所需的参数数量，
此外，在规则定义与绑定的过程中

该实现支持多表达式接口。
它采用一种高效的方式复用EXPR资源。
该操作符结合一个指向输入GROUP而非单个EXPR的指针结构。
每个该结构包含多个独立表达式节点。
在组内占据核心地位，并且所有搜索操作均围绕该核心结构展开。
为了管理这些相关状态，
表格列出了该实现的关键属性以及与之相关的EXPRESSIONS数据结构。

图中对比了Columbia与Cascades在处理multi-expression方面的两种实现方案。从观察中可以得出：相比而言,Columbia设计的M_EXPR结构包含的成员变量数量相对较少,而EXPR_LIST包含了额外的数据项,这些项并未必要地为M_EXPR提供其相关的物理属性及成本信息。由于operator接口可以方便地获取这些必要的信息,无需追踪创建M_EXPR的过程,也无需存储该结构体的物理属性及相关成本信息,因为一旦被计算完成并做出相关决策后就不会再被使用了。值得注意的是,简化数据结构对于减少内存占用具有重要意义,因为multi-expression占用了搜索空间中的主要内存区域。举例来说,单个M_EXPR实例占据24字节内存空间,而一个EXPR_LIST实例则需要40字节内存空间,两者之间的内存占用比例约为1.67:1的关系。如果初始查询涉及对十个表进行连接操作（即join操作）,那么根据估算的结果至少会产生57万个逻辑上的multi-expressions（即logical multi-expressions）。在Columbia系统下,这些multi-expressions将导致大约1368万字节的空间消耗;而在Cascades系统下则会消耗大约2280万字节的空间（即2280MB）。由此可见,Columbia通过采用更为简洁的数据组织方式显著降低了整体系统的内存负担

4.2.2 Rules

在优化搜索过程中被设定的该规则位于由一个规则集合定义的空间里，并且与搜索结构及算法保持完全分离。通过增删规则项的方式进行独立更改。附录C详细列出了一个简化的规则集合实例，该实例专门用于优化基本连接查询。

每一个Rule都属于RULE类这一实例。该类为每一个Rule命名，并提供了一个模式（pattern）和一个替代项（substitute）。Pattern和Subsitute均采用EXPR对象来表示，并且都包含叶操作符（leaf operator）。值得注意的是， leaf operator是一个特殊的只在规则中使用的操作符。当匹配Rule时，请注意Pattern中的叶节点能够匹配任何子树结构。例如，在Left To Right (LTOR) join连接规则中包含以下成员数据：其中L(i)代表Leaf operator i：

Pattern: ( L(1) join L(2) ) join L(3)

Substitute: L(1) join ( L(2) join L(3) )

Pattern和Substitute阐述了一种在search space中生成new multi-expression的方法。这些new multi-expression是由APPLY_RULE::perform()方法创建的，并分为两个步骤：首先，在这个过程中会有一个Bindery对象负责将Pattern与search space中的EXPR建立关联；随后，在同一个步骤中会通过RULE::next_substitute()方法创建一个新的expression，并将其整合到search space中。

在Rule类中提供了多种辅助方法以协助Rule的操作。top_match() 该方法会验证当前表达式的Top Operator与指定Rule Top Operator的一致性, 并通过在Rules进行绑定前完成这一验证过程, 我们能够显著地过滤掉那些明显不符合条件的表达式。

该工具始终决定了 rule 的应用顺序。
甚至根本不应用 rule。
它返回一个 Rule 对于优化上下文（如我们需要考虑的关键物理属性）的一个 Promise Value。
因此它是一个运行时的关键值。
炳辉通知了优化器该 Rule 有多重要。
如果 Promise Value 小于等于零，则不会调度此 Rule；如果 Promise Value 越高，则越早地被调度。
默认情况下, implementation rules 的 Promise Value 是 2；而其他规则则为 1。
Rule 的调度机制允许优化器来控制搜索顺序，并通过调度 Rule 来尽可能早、尽可能低成本地获得尽可能大的搜索边界。

采用并沿用了Cascades在rule机制方面的基础设置。然而，在此基础上进行了相应的优化工作。具体涉及了绑定策略以及酶处理过程。后续章节将深入探讨这些优化措施的具体细节。

4.2.2.1 Rule Binding

每个依赖于rule的优化器均需在其search space内将pattern与expression进行绑定。例如，在涉及LTOR join相关的规则中，该系统会包含两个成员数据。其中,L(i)被定义为下标为i的LEAF_OP:

Pattern: ( L(1) join L(2) ) join L(3)

Substitute: L(1) join ( L(2) join L(3) )

每一次优化器采用这个rule时，它都必须将这个pattern与search space中的一个expression进行关联。以下是一个简单的例子：

( G7 join G4 ) join G10

其中Gi是带有GROUP_NO i的group。

作为关键角色，在识别pattern时建立所有绑定关系的任务由BINDERY对象承担着。在生命周期管理中，BINDERY对象负责生成所有必要的绑定关系。要创建一个绑定关系，则每一个bindery都需对应其所属的input subgroup生成相应的bindery实例。例如，在LOTR规则下定义的bindery会针对left input subgroup单独创建对应的bindery实例；而right bindery则通常只与单个right input group相关联并产生唯一的一个绑定关系。相比之下，在左键操作中（left bindery），每个join操作都会独立地对应到各自的左键输入组别上并建立各自的绑定关系。

根据功能划分，在本系统中存在两类特殊的Bindery对象：expression Bindery与group Bindery。在expression Binditory结构中，则会将特定模式映射至单一的multi-expression实例。The corresponding rule is applied to the top-level group to associate individual expressions with this pattern.The Group Binditory构造则基于输入群组的需求.This allows each Group Binditory instance to associate all multi-expressions within its scope with the corresponding pattern.Since the system under consideration only applies rules to logical multi-expressions, which inherently possess a certain level of abstraction.For the corresponding Binditory instances, only logical operators are bound in this manner.

因为 search space 中存在大量 multi-expression, rule binding 这一过程对性能影响很大。实际上，在 Cascades 中, Advance() 函数作为最核心操作之一,其执行效率直接决定了优化器的整体性能表现。任何针对 rule binding 算法的改进都将直接带来显著的整体性能提升效果。Columbia 通过重构 Bindery 类及相关算法,有效降低了 rule binding 的计算开销,从而显著提升了系统的运行效率和处理能力。

由于一个bindery可能会与search space中的多个Expr进行绑定，并经历start阶段后循环几个有效binding最终完成整个过程，在Columbia系统中这些阶段由三个枚举类型BINDERY_STATE来标识每个状态。

Within the Cascades framework, the binding algorithm employs more states to track all binding stages, thereby incurring a higher degree of complexity and causing increased CPU usage. Within the Cascades framework, binding stages are represented by six binding states. Columbia defines these concepts as follows:

位于Columbia环境中的该算法，在BINDERY::advance()方法中实现了。该算法由APPLY_RULE::perform()函数调用来执行其核心操作。该算法负责遍历存在于搜索空间中的多种树结构，并以寻找潜在的bindings来优化整个系统。这些遍历操作利用有限状态机来完成。如图所示。

4.2.2.2 Enforcer Rule

Enforcer rule represents a unique category of rules designed to enforce or guarantee specific physical properties within a system. The physical operator introduced by an enforcer rule is referred to as an enforcing element. Typically, an enforcing element accepts a group as input and outputs a group with the same identifier but distinct physical properties. For instance, the QSORT physical operator serves as an example of such functionality. Additionally, SORT_RULE, functioning as an enforcing rule, integrates QSORT operators into substitution operations. This relationship can be formally expressed as follows:

Pattern: L(1)

Substitue: QSORT L(1)

L(1)代表下标为i的LEAF_OP

每当search context对有序的一个physical property施加要求时, 会触发相应的enforcer rule. 例如, 在优化merge-join操作时, 其输入所在的搜索上下文会引入一个required physical property来确保输入按照与该merge-join相关的属性进行排序. 例如以下涉及multi-expression的操作场景中.

MERGE_JOIN(A.X, B.X), G1, G2

In the process of optimizing this multi-expression by employing a top-down approach, the Input must be appropriately optimized within specific contextual boundaries. Specifically, for the left input group G1, the required physical properties within the search context must follow an A.X ordering; simultaneously, those within the right input group G2 must adhere to a B.X order. Whenever the search system requires enforcing an ordered attribute, the SORT_RULE will be activated and QSORT operators will be inserted to achieve this objective, thereby ensuring that each Input Group possesses its required properties.

另一个类似的enforcer规则也会适用。比如HASH_RULE会产生一个hashed physical property。触发enforcer规则的情况取决于rule对象中promise()方法的行为。Promise()方法仅在以下情况下返回正的Promise 值：当 search context包含required properties如sortes或hashed时。如果缺乏required physical properties，则 Promise 值将为零（即意味着该规则不会被激活）。

Cascades和Columbia处理enforcer rule时有2个主要的差异：

首先，excluded property 。Cascades使用promise()方法中的excluded properties（？？） 来决定一个enforcer的promise值。只有当required physical property set和exclude physical property set同时不为空时，promise()方法才会返回一个非0的promise值。使用excluded property的目的是为了避免对一个group重复使用相同的enforcer。但是这些excluded properties很难跟踪并且会使用更多内存（它要求search context包含一个指向excluded property的指针），并且会使search算法处理enforcer更复杂。而Columbia不会使用excluded properties。Columbia中的context只包含一个required property和upper bound。promise()方法只根据required physical property来决定一个rule的promise值。为了避免重复应用enforcer rule的潜在问题，会对enforcer rule使用unique rule set技术。即，每个M_EXPR都有一个RuleMask数据成员，包含每一个enforcer rule的bit。当一个enforcer rule被触发，这个rule对应的bit位会被设置为on，意味着这个enforcer rule已经对这个multi-expression使用了。在下一次触发enforcer之前，会检查rule mask，不会再重复触发rule。另一方面，这个简单的方法导致了一个潜在的问题：如果一个group已经被优化了，而我们需要针对另外一个不同的property来执行优化，此时multi-expression中的enforcer rule bit可能由于上一次的优化已经被设置为on了。那么在这个新的优化阶段中，这个enforcer rule则不会针对不同的property再被执行，即便它对于这个新的physical property有一个非常好的promise值。因此，优化器可能会在这个优化阶段给出错误的答案。这个问题的解决方案导致了Columbia基于Cascades的另外一个改进。见下面第二个差异点。

此外，在Cascades框架中，默认情况下enforcer由一个parameterized physical operator来表示。具体而言，在该实现中，默认情况下QSORT operator接收两个参数：一个是需要排序的attributes集合（如A.X, A.Y），另一个是排序顺序（asc或desc）。通过调用QSORT::input_reqd_prop()方法能够获取所需的物理属性信息，并未直接返回排序后的excluded property对象。相反，在优化multi-expression时会利用该context提供搜索上下文信息。需要注意的是，在enforcer rule绑定到expression后会触发RULE::next_substitute()方法生成新的expression实例，并将这些带enforcer的新expression与原有expression合并到同一个search space group中。值得注意的是，默认情况下拥有相同名称但不同参数配置的enforcers会被视为独立的对象实体。因此，在面对基于不同attributes排序需求的复杂搜索场景时，默认情况下会有多个具有相同名称但不同参数配置的enforcers存在于同一个search space group中。这种设计虽然简洁直观但在实际应用中可能会导致资源浪费的问题

相反，在Columbia中，在SORT_RULE执行之后不会生成多个QSORT operator以处理同一个group中的expression。因为一旦SORT_RULE应用后就会设置对应的rule bit，在后续的操作中该bit会被持续激活从而避免重复生成enforcer multi-expression. 这种机制确保了操作的安全性：因为对于每个input stream的所有sort操作都会被假设产生相同的cost值，并未考虑sort keys的变化. 换句话说，在Columbia优化器的设计中如果一个group已经针对某个特定property进行了优化，则该group中的所有enforcer multi-expression都会被直接映射到该property上. 这种映射关系使得后续针对不同property的优化能够避免重复计算带来的开销，并且能够更高效地利用已有的计算结果.

在优化器复制最优计划时，在计划中包含的物理属性已被明确指定后

4.2.3 Tasks-Search Algorithm

任务是搜索过程中的一项重要活动。原始的任务是对整个查询进行优化。这些任务之间可以相互创建并调度。当所有任务都已完成时, 优化过程也就结束了.每个 task 都与特定的上下文紧密相关, 并且有一个名为 perform() 的方法来真正执行每个 task. Task 类是一个抽象类, 具体实现的任务会继承这一抽象类, 并实现一个虚方法 perform(). PTasks 类包含一组未完成且需要调度及执行的任务. PTasks 使用栈结构来管理这些任务.包含一个名为 pop() 的方法用于将任务从栈中移除以便执行, 还有一个 push() 方法用于将新的任务推入栈中进行管理. PTAs实例是优化阶段创建的对象.在这一阶段, 原始 task 被推入 PTAs 中等待调度.当优化开始时, 这些原始 task 被 dequeued 并调度其 perform() 方法开始执行.其余需要参与优化的任务随后也会被创建并推入队列进行处理.下图展示了主过程伪代码框架.通过使用抽象类的方式, 我们能够实现代码结构上的简单清晰.

该搜索算法通过优化器中所有指定任务的执行来实现其功能。Columbia系统中的任务分为五类：组优化（O_GROUP）、组探索（E_GROUP）、表达式优化（O_EXPR）、输入优化（O_INPUTS）以及规则应用（APPLY_RULE）。 如下图所示，在系统架构中各任务之间存在特定的关系网络：箭头指示了哪些任务会触发其他任务的操作流程。本章后续部分将详细阐述Columbia系统中各个具体任务的具体实现方案，在每个方案描述过程中都会特别指出与现有系统的比较分析部分。

4.2.3.1 O_GROUP - Task to Optimize a Group

该任务将基于给定的一个context识别该组中代价最低的计划，并将其连同context一并存入该组所属的winner数据结构中。
若无法确定最优计划（如upper bound约束失效），该context将携带一个null值计划存入赢家结构。
为了实现这一目标，在完成当前操作后, O_GROUP类将创建两个子类类型——分别为生成与优化该组中的expressions——分别命名为O_EXPR 和O_INPUTS。

In dynamic programming and memoization, tasks are frequently utilized. Prior to optimizing all expressions within a group, it would first check if there has already been an optimization target with the same search context, if so, it would simply return the previously found plan. The reuse of derived plans represents a crucial aspect in both dynamic programming and memoization.

下图展示了O_GROUP task中的处理过程，它通过O_GROUP::perform()方法实现。

如上图，在group中将逻辑型和物理型多表达式的分离有助于完成该任务中搜索过程

执行O_GROUP task时有两种case：

第一种情况：首次对一个group进行优化操作（例如，在对每个context进行搜索时）：在此情况下该group仅包含单个logical mexpr（即初始表达式）。按照算法流程，在此情况下仅会生成单一任务序列（针对该初始mexpr），并将其推入任务堆栈中；随后该过程将通过应用规则来产生新的表达式。

第二种，在另一种不同的上下文场景中对同一个组进行优化时，请注意该组可能会生成多个赢家实体（winners）。因此，在这种情况下我们需要完成两项任务：第一，在新的上下文中对每一个逻辑上的multi-expression（mexpr）执行O_EXPR操作 ，因为某些在原有上下文中不适用的规则在新的情境下可能会生效应用。通过这种方式将确保每个mexpr仅会被应用一次规则集合（unique rule set technology），从而防止生成重复的multi-expressions（multi-expression）。第二，在新的上下文中对每一个物理上的mexpr执行O_INPUTS操作以评估其成本表现（cost evaluation） ，并在此基础上确定一个赢家实体（winner）。

在Cascades系统中，在优化单个group时，并不会处理物理型多表达式（...）。对于同一个group内的所有逻辑型多表达式（logical multi-expression），在优化过程中会分别创建相应的O_EXPR任务（操作类型）并将其推入堆栈（stack）中。随后将生成所有的物理型多表达式（physical multi-expression），并计算各自的开销（cost）。在对同一个组进行第二次优化时，则会基于新的上下文重新生成所有物理型多表达式并计算其开销。由于所有逻辑型和物理型多表达式都被存储在一个链表结构（linked list）中，在这种情况下该方法必须遍历该组内的所有物理型多表达式（multi-expressions）。基于这一比较标准，在Columbia系统中的分组优化算法在效率上更为出色。

4.2.3.2 E_GROUP - Task to Expand the Group

一些规则要求它们的输入必须包含特定的操作符,通常是逻辑运算符.例如,一个"join结合律"规则要求其中一个输入必须是一个"join".当multi-expression中包含的"join operator"与该规则中的"top join"进行匹配时,该multi-expression的"left input group"必须被扩展以查看group内部是否存在对应的"join",因为该规则要求该组输入必须是一个"join".此外,group内的所有"join操作都必须与该规则中的左'join'进行匹配".

为了扩展一个Group（Group），基于该Group定义了一个E_GROUP任务，并为每个目标logical operator生成相应的操作项；例如，在涉及Join Group时，触发机制能够生成适用于所有Join Group成员的规则；该任务仅在遵循特定模式的情况下主动发起探索行为时才会被激活；由另一个任务（O_EXPR）按照需求生成并负责调度相关操作项

下图展示了explore一个group的过程。它被E_GROUP::perform()方法实现。

动态规划也常用来消除重复计算。在开始探索一个group的所有expressions之前，请注意该系统会检查当前group是否已经被探索过。如果是，则该系统将在不生成新的任务的情况下立即终止；如果需要继续探索，则该系统会为每个逻辑上的multi-expression触发一个O_EXPR任务，并将multi-expression标记为正在探索的状态以便相关O_EXPR任务来执行表达式转换规则。

Within the Cascades framework, a single E_GROUP task would be responsible for creating other types of tasks, namely E_EXPR, aimed at exploring a multi-expression. Due to the identical behaviors between E_EXPR and O_EXPR, Columbia does not utilize E_EXPR tasks. Instead, Columbia employs OExpr tasks with a flag to indicate the purpose of the task.

4.2.3.3 O_EXPR - Task to Optimize a Multi-Expression

Columbia系统中的O_EXPR任务主要包含两个功能：其一是在一个多表达式集合中进行优化或改进；其二则是按照指定优先级顺序运行所有的转换规则，并根据需要生成新的逻辑上的multi-expressions；同时，在第二个功能下还伴随着implementation rules的应用来生成相应的物理层面的multi-expressions。此外，在这个过程中还有一个探索性的子任务：即通过触发特定范围内的transformation rules来生成并分析候选式的逻辑形式，并为后续的expression matching准备素材库所需的条件；只有在探索模式下才会被激活，并且只会生成新的逻辑形式表达式作为备选方案待用。为了明确区分这两种不同的操作模式,O_EXPR任务还提供了一个控制标志变量（flag）来进行设置选择，默认情况下该标志设置为"optimize"状态（即优先采用优化功能），但在特定情况下（特别是当由E_GROUP任务引发时）则会切换到"explore"模式以便进行式子匹配前的知识库准备工作）。

该段图示呈现了O_EXPR任务的具体算法架构，并包含有实现该功能的方法...。
在...中进行操作的是一个特定类型的优化器（此处特指），它负责决定如何将相应的规则推送到...堆栈中。
需要注意的是，在...的所有输入都被展开并与其模式进行匹配之前评估这些承诺。
其中，在...的所有输入都被展开并与其模式进行匹配之前评估这些承诺。
而承诺值则用于确定是否要展开这些输入。

在优化多表达式的过程中，在算法设计方面 Columbia 和 Cascades 之间并无明显差别。然而，在技术细节上存在差异：Columbia 采用了一种称为 O_EXPR 的方法来进行进一步探索；而 Cascades 则引入了研究 E_EXPR 的新任务作为其核心创新点。

4.2.3.4 APPLY_RULE - Task to Apply a Rule to a Multi-Expression

Columbia与Cascades中的apply rule算法具有相同特性。每个规则仅作用于single logical expressions上。该任务负责将单个规则应用于single logical multi-expression，并在搜索空间中生成新的logical或physical multi-expressions的任务。当给定一个rule及一个logical multi-expression时，在搜索空间中可使用的所有expressions都会被该任务确定为所有合理pattern bindings的基础上应用该rule，并在搜索空间中新增相应的substituted expressions。若新生成的multi-expressions为logical类型，则会在后续变换中被优化；若是物理型multi-expression，则会计算其计算成本。

下图呈现了该算法的核心内容，并且在其中实现了APPLY_RULE::perform()方法的功能。其内部的具体实现方式与Cascades完全一致。

一旦找到绑定（binding），随后会调用RULE::condition()方法来判断该rule能否应用于当前的expression。例如，在将select移动至join下方时所使用的规则必须满足与目标表结构兼容性的条件。这种条件仅在完成绑定操作后才能被验证，请注意这是因为input group所在的表结构仅在完成绑定操作后才会被确定下来。

当rule应用于multi-expression时，在其对应的bit位置将被设置为1。因此，在后续处理中该multi-expression不会再受到相同规则的影响,从而消除重复处理的问题。

4.2.3.5 O_INPUTS - Task to optimize inputs and derive cost of an expression

在应用一个implementation rule之后，在处理query树中的某个节点时应用相应的implementation算法时，在优化过程中会对每一个input进行相应的优化以推进整体优化效果。O_INPUTS任务的目标是通过计算该multi-expression的所有输入（input）的成本并将其累加到top操作符（operator）的成本上以确定整个physical multi-expression的成本值。为了实现这一目标，在O_INPUTS类中定义了一个成员变量input_no，默认初始化为0值以记录哪些输入已经完成了成本计算工作。该任务与其他任务的不同之处在于即使调度了其他tasks完成之后，并不会立即停止而是会将自己推入到一个队列中然后依次处理剩下的输入优化问题最终完成整个physical multi-expression的成本评估过程。

本节将详细讲解Columbia体系结构的核心内容，在原有基础上进行了优化和改进。

下图呈现了O_INPUTS::perform()方法的伪代码，并对该方法所实现的OINPUTS task中的算法进行了详细说明。

符号说明：

G ：被优化的group

IG ：G中expression的多种inputs

GLB ：一个input group的Group Lower Bound，作为group的数据成员存储

Full winner ：一个plan不为空的winner

InputCost[] ：包含G的最优inputs的真实（或是lower bound）cost

LocalCost ：正在被优化的top operator的cost

CostSoFar ：LocalCost + 所有InputCost[]条目的sum

算法中包含三个裁剪标志项：Pruning、CuCardPruning、GlobepsPruning。优化器用户可以根据Columbia中不同裁剪方法的实验结果来配置这些标志项

以下是对原文的同义改写

Starburst - [!Pruning && !CuCardPruning]: 通过避免执行剪枝操作，并为每个input group创建所有possible expressions, 进而实现completely expand the input groups.

Simple Pruning - [Pruning && !CuCardPruning]：旨在通过主动排查limits来防止input group的扩大。如果在优化过程中某个expression的CostSoFar超过了优化context中的上限值，则该任务将停止进一步优化工作。在这种情况下，InputCost数组中的条目仅会在输入存在针对优化context的最优解时才被记录下来。

Lower Bound Pruning - [CuCardPruning]

Global Epsilon Pruning - [GlobepsPruning]：当某个计划实例的成本值低于设定好的全局epsilon阈值（GLOBAL_EPS）时，则该计划实例被视为最终获胜者而不需再进行进一步优化。该标志与其他标志相互之间没有依赖关系，并能够与其他三种情况进行结合以实现整体上的优化效果。

4.3 Pruning Techniques

在本章中, 我们将探讨Columbia university提出的两套剪枝策略。这些策略不仅延伸了Cascades中的搜索机制, 还通过引入智能剪枝策略, 大大提升了计算效率。与之前一致, 这些剪枝技术主要应用于O INPUTS task模块中。

4.3.1 Lower Bound Pruning

动机： 该类Top-down优化器通过预估high-level物理计划（Physical plans）之前的low-level计划（Lower-level plans）的成本（Costs），从而为后续的任务提供参考数据。这些预估的成本将被用作后续子优化任务中的上限（Upper bounds），从而有助于减少不必要的计算。在实际应用中，这种上界机制通常有助于减少对所有可能表达式组合（Expressions group）的需求，并被称为剪枝（Pruning）。

基于Columbia搜索过程的特点——自顶向下且具有记忆性——我们可以应用bounds来进行全局剪枝操作。例如，在优化器处理输入(A x B) x C时, 该系统会首先评估由三个组件共同组成的复合组别中的单个计划, 其成本计算为5秒（即(A x LB) x LC）。随后, 系统会在扩展相关组件时跳过其他组合的可能性, 如(AC)与(B)等组合. 现在, 我们进一步探讨如何针对其他表达式进行优化处理, 比如说(AC)x(B). 假设(AC)表示笛卡尔积运算, 由于其规模庞大, 将其移动到(ABC)中会导致耗时超过5秒. 因此包含(AC)的所有计划都不可能是(ABC)的最佳方案. 在这种情况下, 该系统就不会生成所有(AC)相关的计划. 另一方面, Starburst和其他bottom-up优化器在开始处理(ABC)之前就已经对各个子组件进行了优化工作, 因此错过了多个计划同时被剪枝的机会.

若group G未被枚举，则称其已被剪枝。剪枝后的group最终仅包含单一的一个expression

算法： 在这一章节中我们将具体说明Columbia所采用的改进型优化方案以提高group剪枝的成功率。如图所示 这个算法属于O_INPUTS任务的部分 并且是Figure22 Note1的具体阐述

在图中所示，在第（1）至（4）行计算了一个Expr的成本下限...；当该下界超过当前上下文中的上限（即Limit）时，则当前路径可以直接返回；与Cascades算法相比，在本方案中省略了第（4）条指令的处理步骤

在Columbia系统中存在一个与每个组相关的下界值（Group Lower Bound），该下界值代表了从该组的所有表中提取所有元组所需付出的成本之和。这个Group Lower Bound通常会在进行表达式优化之前就已经计算完毕，并被存储于相应的数据结构中（因为其仅依赖于Group的基本逻辑属性）。特别地，在系统中的Line(4)段落特别关注那些无法通过现有策略获得最优解的目标状态（即required properties无最优计划的情况）所对应的Group下界值（Group Lower Bound），这一特殊关注使得Expr cost的整体下界得以显著提升，并进一步增强了Group剪枝策略的有效性。

该场景图中显示了当lower bound group发生剪枝时的情况。在此情况下，Cascades算法不会对group[BC]执行剪枝操作的原因在于：该被优化expression所对应的lower bound cost仅由当前expression的操作符成本以及输入中winner（若有）的成本之和构成。具体而言，在此情形下其值计算为1+2+0=3，并未超过context中的upper bound限制。因此，在此情况下group[BC]仍然会被扩展。

该方法的安全性有保障，在优化器设计中被采用以生成最优计划。具体而言，在4.1.2.3节中我们证明了所采用的界具有下界性质：只有当某个集合中各计划的下界成本高于其他计划的成本时（即该集合中的所有计划均无法超越其他集合中的相应计划），才会对该集合中的所有计划进行剪枝操作。

4.3.2 Global Epsilon Pruning

动机源自经济学理论基础。其核心理念是从理论上讲经济系统受到法律约束。实际中人们通常不会采取这种极端行动：他们只需达到几乎满足约束条件的最佳状态即可。这一现象被称为‘满意’。一种看待满意的方法是设想存在一个固定的小常数ε，在此范围内所有事物既被优化又被满意。

该方法将一个计划定义为一个group的final winner的前提是：当其cost（包含epsilon）与最优计划的cost足够接近时。一旦这样的winner被确定为某组的目标计划，则该组无需再进行进一步优化。因此，在搜索过程中可能会对搜索空间进行剪枝以提高效率。例如，在处理group[ABC]时，我们会计算并记录该组内第一个计划AxBxC的成本值为5秒。假设我们设定epsilon值为6秒，则当某个计划的成本小于6秒时即可被视为该组的目标winner（虽然可能不是全局最优解）。因此，在这种情况下AxBxC的成本5秒被视为group[ABC]的目标winner从而对该组的所有后续搜索工作都进行了终止处理无需继续探索其他可能性

这种剪枝技术命名为Global Epsilon Pruning。这是因为该epsilon在整个过程中被应用为全局策略，并非仅限于单个指定分组的局部应用。

算法：采用一个全局参数Globeps >0，并按照标准优化方法进行操作。除非某个group中明确指定了最终赢家，在这种情况下若发现一个计划其成本值低于当前设定的Globeps值，则立即选择该计划作为最优解。

加入该组中的胜出者，并将search context标记为已完成，以表示该组不再进行进一步的搜索。

该算法基于OINPUTS任务实现，并参考图中的注释。当对expressions进行优化并计算其成本时，在全局剪枝标志被启用的情况下，将与全局剪枝值进行比较。若成本低于epsilon，则搜索终止。

然而

设 'absolute-optimum' 对应于 常规 优化 的结果, 'GloBePs-optimum' 对应于 采用 Global Epsilon Pruning 优化 的结果. 若 绝对 最优 拥有 N 个 节点, 其 成本 均低于 GloBePs, 则 GloBePs-optimum 与 absolute-optIMUM 的 成本 差异 最大 值 为 N×GloBePs.

证明

cost(P) - cost(absolute-optimum) < N*Globeps

因为 search space 中的 P 被 Global Epsilon Pruning 算法所定义，在此前提下我们必须要满足某种特定条件

cost(Globeps-optimum) < cost(P)

不同设置下的epsilon值对剪枝操作会产生显著影响。当所设定的epsilon值非常小时，在实际应用中可能会出现无法产生剪枝的情况（因为group中所有计划的成本均高于该设定）。相反地，在设置过大的情况下将会导致大量计划被剪枝（尽管这可能不会产生与最优计划相差太远的结果）。值得注意的是，在剪枝技术的选择中存在高度依赖于所选epsilon值的情况；为此我们提出了一个基于定理推导得出的结果表明：在优化一个包含10个表的连接时，请考虑以下因素：首先估计该连接最优计划的成本范围大致在100秒左右；其次最优计划通常包含20个节点；此外假设与最优计划相比相差不超过10秒即可接受的话，则可以通过该定理推导得出的结果表明：基于该定理推导得出的结果表明：我们可以采用全局epsilon值为0.5作为推荐设置

怎么估计的最优计划cost 100s ？

我们可以通过在本章中提及的方法，在运行一段时间后收集优化器生成的最佳执行计划的cost，并据此指导epsilon pruning。

4.4 Usability in the Columbia Optimizer

除此之外，在前文部分也提到过基于Cascades提升了效率。而在Columbia系统中采用窗口界面作为主要的人机交互方式，并通过持续跟踪的信息来增强系统的稳定性和可靠性。本节将详细阐述如何提升基于Cascades系统的可用性。

4.4.1 Windows Interface

交互界面，略

4.4.2 Tracing of the optimizer

因为******具有高度复杂性

优化的跟踪可能包括：

该系统支持多种类型的查询请求，并能够根据不同的业务需求自定义查询模板和执行策略。
该系统支持多种类型的查询请求，并能够根据不同的业务需求自定义查询模板和执行策略。

任务栈中的内容：我们称这种结构为OPEN stack。其中包含了多个任务节点，并且每次都会从堆顶移除并执行任务。通过分析OPEN stack的工作机制, 我们能够清晰地了解优化器的工作原理及其任务分配方式。

每个task的执行细节：跟踪一个特定task的执行细节

每次任务执行后, search space可能会发生变化. 因为更多新的expressions或是winner会被包含进去. 这个信息用来跟踪每个任务的结果.

在完成优化后会显示搜索空间...。了解优化器的最终状态可以通过查看该搜索空间来实现。例如，在每个group中生成了多少个expressions？

该信息对于扩展性应用具有广泛的支持；通常情况下,用户对于跟踪结果中的特定部分更为关注；Columbia系统通过配置追踪选项实现了对优化器的有效监控；其追踪控制功能分为两个独立模块：

Trace To：用户可以选择跟踪信息输出目标，到文本文件、窗口等。

Trace Content：这个选项允许用户选择感兴趣的部分跟踪内容。略

Chapter 5. Result and Performance

略

Chapter 2. Conclusions and Future works

Columbia充分利用了Cascades的基础上应用了集中工程技术以提升其性能；这些技术在优化过程中降低了CPU和内存资源的使用量。

用户消除重复expressions的fast hash function

group中logical和physical expressions的分离

小而紧凑的数据结构

优化groups和inputs的高效算法

处理enforcer的高效方式

该方法实现了两种剪枝策略。
基于lower bound group pruning 的方法使得搜索空间得以大幅缩减。
每个组别下界可在其被优化前迅速确定。
当组别下界超出搜索范围时可安全舍弃。
该方法采用的整体截断策略通过生成足够接近最优解的方式实现搜索空间缩减。
一旦找到足够接近最优解的结果就能完成目标。
进一步分析表明，在合理设置截断阈值后能够实现既高效又可靠的优化过程。

Columbia 优化器尚有许多额外的优化工作待完善。当前优化器仍大量消耗内存用于处理大规模查询。当处理包含超过16个表的星型查询时，可能导致内存消耗过高。类似于周期性垃圾回收机制 和 内存共享机制 的技术可能有助于降低内存使用量

另一个关键问题是评估器方案的有效性。评估者无法断定结果是否最优,因为可能存在程序错误而导致次优结果,尤其是在处理大规模查询时。即便是在Columbia评估者中增加了监控工具,但结果验证与调试仍然是一项复杂而费时的工作.对于评估者而言,某些可视化方法或快速检验方法是非常有用的.