Paper Reading: The Cascades Framework for Query Optimization

这篇paper是 The Cascades Framework for Query Optimization, in IEEE Data Engineering Bulletin, 1995。

对应15-721的Query Optimizer Implementation II，主要涉及数据库的查询优化器的具体实现。

这篇 paper 是 volcano 作者 Graefe 基于 volcano 的优化改进版，但理解起来仍然比较抽象和模糊，因此，学习的大部分内容来源其它资料：

• 15-721视频
• Efficiency in the Columbia Database Query Optimizer (pages 1-35), in Portland State University, 1998

Introduction

首先看下，cascades 要解决 volcano 的什么问题：

volcano 明确区分了 逻辑优化 和 物理优化 阶段。在逻辑优化时，需要 generate all possible logical operators，再交给物理优化去 search，这带来大量不必要的预计算 和 search cost。

因此，cascades 不在严格区分 logical operator 和 physical operator，并且它是 按需 explore，下面会具体说明。

Key Terms

先看下 cascades 里的核心概念

• operator：SQL 最终会被翻译成 关系代数表达式 组成的 plan tree，而 operator 就是树中的节点，也就是 关系代数运算符。比如 join、scan、projection等。

• expression：我们以往理解的表达式是 plan 的基础构建块，比如 column ref、literal value、math function 等。但 cascades 中表达式代表一个 high level operator，它带着 input expression。比如 join with expr1 + expr2。

  举例来说：select * from A join B on A.id=B.id join C on C.id=A.id;

  Logical Expression：$ (A \bowtie B) \bowtie C $

  Physical Expression：$ (A_{seq} \bowtie_{HJ} B_{seq}) \bowtie_{NLJ} C_{Idx} $

• group：一组逻辑等价的 logical expression 和 physical expression，这些 expression 的 output 都是相同的。如下图

  

• multi-expression：它是上面 group 的优化情况，即取代明确地列出 所有可能的 expression，通过 implicitly 将多余的 expressions 组成一个组概念的 placeholder，作为 multi-expression，它的 cost 从更下层的 group 来获得。目的：通过 placeholder 减少复杂度，即 减少 transformation 次数，减少 storage overhead，减少 重复的成本估算。如下图

  

• rule：logically equivalent expression 的 transformation。Transformation Rule：Logical to Logical。Implementation Rule：Logical to Physical。

  每个 rule 都包含了 如下 attributes：

  • pattern：定义能够 match 这个 rule 的 logical expression structure
  • substitute：定义应用 rule 之后的 structure

  比如，定义的 pattern：( L(1) join L(2) ) join L(3)，它的 substitute：L(1) join ( L(2) join L(3) )

• Memo Table：保持上面各种结构的容器，在 search 过程中不断保存生成的 operator/expression/group，同时也负责消除 duplicate 的数据。如下图

  

• Search Termination：设想一个问题，如果一条 SQL 包含许多 join，那么它可以一直 deep into query plan，直到找到 best plan。但这所消耗的时间和资源是不可接受的，因此需要决定何时 stop。如下

  • wall-clock time：通过具体时间长度去 stop optimizer
  • cost threshold：只要当前 plan 的 cost 低于给定的 threshold，就 stop 返回当前 plan
  • transformation exhaustion：当前 plan 的所有 transformation 都 visit 过了，即所有可能性都走完了

尽管 cascades paper 比较晦涩，但下面会从 cascades 具体的实现者来帮助理解。

Columbia Optimizer

来源于 Efficiency in the Columbia Database Query Optimizer，它的开源实现。

1.回顾下数据库的 query processing 流程：

• 输入的 DML 会被解析成 logical expression tree，再传递给 optimizer
• optimizer 将 logical plan 转换为 best physical plan，再传递给 query execution engine
• query execution engine 根据 plan 从 database store 读取数据 并 evaluate outputs

2.本质来说，query optimization 是一个 复杂的搜索问题。需要在一个 search space 中找到 best plan。

search space 代表着 plan trees，从上面 introduction 我们知道，cascades 中 search space 本质是 一系列 groups，最顶层的 top group 作为 final group 去计算最终的 outputs。如下图

3.search space 的复杂度在于，expand 过程中，存在不同等价 logical expression，不同的 physical expression 实现算法，不同的 join 算法。如下图是一种 join query 的简单情况，其中 N(logical expression 个数)、M(join 算法个数>=1)，则存在 M*N 个 physical expression 在 search space 中。如下图

4.继续讨论造成 search space 的复杂度的因素之一：rules。

optimizer 通过 rules 去产生 逻辑相等的 expressions for initial query。每个 rule 包含着 pattern + substitute。

pattern 用于在 expand search space 中，去匹配每个 logical expression（只用于 logical expression），如果 match，则根据 substitute 产生新的 逻辑相等的 expression。

pattern 总是 logical expressions，substitute 则存在 logical 和 physical 情况。

rule 的类型由 substitute 类型决定，比如 substitute 是 logical expression，则 rule 是 transformation rule，反之，为 implementation rule。

到这里，应该更加深入地理解了，introduction 中说的，不在严格区分 logical operator 和 physical operator 的原因，而是统一通过 rules 来去转换，最后通过 physical expressions 去计算 cost。

如下图中的两种 rules，都对应了一个 pattern：

5.现有优化器的实现

查询优化器技术，最早可以追溯到 1970年，其中 IBM System R Optimizer 取得了成功，并提成为许多商业优化器的基础。

但随着数据库系统的发展，关系模型上扩展了更多功能，新的数据类型、新的数据操作，新一代优化器 focus on extensibility 和 efficiency 。

下面会依次 high-level 概括现有优化器的特点：

• System R：
  • 主要贡献1：提出了 cost-based optimization。通过 catalog 获取到统计信息再去 估算 operator执行cost(依赖于input relation的 cardinality (size of the relation), number of pages and available indexes) 和 operator output size 估算(作为给下一个operator的input)
  • 主要贡献2：bottom-up dynamic programming 搜索策略，同时仍然采用 Heuristic rules + 仅考虑 left deep tree，去尽量减少 search space。
• Exodus Optimizer：
  • 主要贡献：第一个 extensible optimizer，并且采用 top-down 优化方式。开创性地将 search strategy 分为 logical operator 和 physical operator，通过 transformation rules 和 implementation rules 两阶段优化。为后来的 volcano 建立基础。
• Volcano：
  • 主要贡献：结合 dynamic programming + 基于 physical properties 的定向搜索 + branch-and-bound 的剪枝 + Heuristic guidance。从而形成了一种新的 搜索算法。
• Cascades：
  • 主要贡献：解决 Exodus 和 Volcano 的痛点。参考文章开头部分。

Search Engine

1.Class SSP

columbia 保持和 cascades 一样，通过 task 来组织优化流程，task 去优化 groups 和 expressions，task 的核心是 apply rules 并生成新的 expressions 和 groups，最终达到 expand search space。

由上面介绍得知，search space 本质是一系列 groups，columbia 中组织 search space 的结构是 SSP(类似 Cascades’ MEMO)。

• SSP 包含 group ID 组成的数组
• 一个 group 包含 一组 multi-expressions
• 一个 multi-expression 由 operator + 其它 groups 组成。（因此，一个 group 可能是 root group 或 其它 group 的 input group）

在初始化时候，通过 CopyIn 方法，将输入的 expression 分割为一系列的 basic groups。

2.Groups

group 是 top-down optimization 的核心，它是包含 一组逻辑等价的 logical 和 physical multi-expressions。

Columbia 的改进点如下：

• 引入 lower bound cost，做更积极的 group pruning：我们从 Volcano 那篇中知道利用 upper bound 做到剪枝过滤掉不必要的搜索。这里的 lower bound 是在更靠前的阶段，它基于 group 的 logical property (cardinality 和 group schema)，在 group 构造时就已经计算出了。
• 将 logical multi-exprs 和 physical multi-exprs 分开存储到两个链表中。一个 group 中包含大量 logical multi-expres，而 physical multi-expres 一般又是 logical 的2~3倍，因此在频繁的 rule binding 操作中需要 check logical rule pattern 时候，如果从 virtual memory 中读取到大量 physical exprs，必然会引起大量 memory page fault。

3.Winner

由于每个 group 会根据不同的 search context(required physical properties，比如 sorted + upper bound) 反复优化，因此每个 context 都存在一个 best multi-expres，保存在 group 的 winners 数组中，提供后续使用。

Cascades 中 winner 结构是，Pair<Search Context, best multi-exprs(physical)>，Columbia 简化后的 winner 结构是，当前group中最优的 m-expr + 这个 expr 的 cost + required physical property。对应代码

4.Expressions

前面已经提到了，两种 expression object：EXPR 和 M_EXPR。对应代码。

5.Rules

rule 是事先定义好的，优化 expression 的规则。对应代码。

其中两个方法辅助 apply 过程：

• bool top_match (OP *op_arg)：作为快速的预检查，比较 rule 的 top op 和 当前 m-expr 的 top op，不匹配则 skip
• int promise ( OP * op_arg, int ContextID)：对 rule 进行打分，分数越高 apply 的优先级越高，比如 PHYS_PROMISE 就比 LOG_PROMISE 大，有助于尽快生成 physical exprs，也更利于后续基于 cost 的剪枝。

6.Rule Binding

当优化器需要 apply 一个 rule 时候，必须要将 rule pattern 与 search space 中的 expression 做 binding。

解释：参考上面 Key Terms 里的 rule 定义，对于 pattern：( L(1) join L(2) ) join L(3)，它的 substitute：L(1) join ( L(2) join L(3) )，它对于的 binding：(G7 join G4 ) join G10。其中 Gn 是 group_no 的含义。

因此，binding 将一个 expression 与 group 对应上。

7.Enforcer Rule

在 Volcano 那篇中提到了 enforcer，它会强制一种物理属性，也可以理解是一种 implementation rule。例如 sort_rule 就是一种 enforcer rule，它会 insert QSORT 作为 top operator。如下示例：

1
2

Pattern：L1(1)
Substitute：QSORT L(1)

8.Task

task 是基础单元来组织优化流程，task 以 stack 的方式来调度。包含如下几种类型：

• O_GROUP：group optimization。在给定 context 下，找出 cheapest plan 并保存到 winner 中。对于 logical m-expr 创建 O_EXPR task，对于 physical m-expr 会创建 O_INPUTS task.

  

• E_GROUP：group exploration。即扩展一个group，创建 O_EXPR task。

• O_EXPR：expression optimization。优化一个 logical expr，即创建 APPLY_RULE task，去做具体的优化。

• APPLY_RULE：rule application。apply 一个 rule 到 logical expr 上，并更加 rule 的类型，会创建 O_EXPR task 扩展 space，或 创建 O_INPUTS task 来计算 cost。

• O_INPUTS：input optimization。计算出 physical multi-exprs 的 cost，并加入到 top operator 中，因为整个流程是 stack 方式调度，因此算完 cost 后，需要进行剪枝策略。

总结

• Columbia Optimizer 更像是 cascades 的详细解释版本，建议看完 15721 视频后刷一遍，主要是其中的一些 terms 解释，以便在后面看 Calcite 代码时候能够理解
• Columbia paper 中虽然有 pseudo-code，但最好还是配合代码。参考Calcite 中新增的 Top-down 优化器 与 对应PR
• Columbia paper 各种算法细节，还需要在后续代码实现中，再进行精读，这次先做 high level 概念学习

Reference

• henry liang：更高效的Cascades优化器 - Columbia Query Optimizer
• 揭秘 TiDB 新优化器：Cascades Planner 原理解析
• hellocode：Cascades Optimizer
• FindBestPlan动画展示