Calcite CBO ① - 核心流程

一、问题 & 目标

数据库/大数据引擎主要由三部分组成，分别是解析器、优化器和执行引擎，如下图所示：

其中，优化器在很大程度上决定了性能，其作用好比找到两点之间的最短路径。优化器主要分为两类：

RBO: Rule Based Optimizer

• 根据优化规则对关系表达式进行转换，同时原有的表达式会被裁剪掉，经过一系列转换后生成最终执行计划
• 包含一套有着严格顺序的优化规则，同样一条 SQL，无论读取的表中的数据怎么样，最终生成的执行计划都是一样的。即数据不敏感

CBO: Cost Based Optimizer

• 根据优化规则对关系表达式进行转换，这里的转换是说一个关系表达式经过优化规则后会生成另一个关系表达式，同时原有表达式也会保留，经过一系列转换后会生成多个执行计划
• 然后根据数据统计信息和代价模型计算每个执行计划的 cost
• 从众多执行计划中挑选出 cost 最小的执行计划

从上面的描述可知，CBO 是优于 RBO 的，原因是 RBO 是一种只认规则，对数据不敏感的呆板的优化器，而在实际过程中，数据往往是有变化的，通过 RBO 生成的执行计划很有可能不是最优的。

举个例子：如下图，A、B、C 三个表的 join 顺序可以有多种，如下图分别是 (A join B) join C 和(B join C) join A。

例如 A 有 1000 条数据，B 有 1000 条，C 有 10 条数据，三个表之间存在一定的 join 谓词使得：

• A JOIN B 返回 10000 条数据，B JOIN C 返回 200 条数据；那么前一个执行计划需要处理 1000 * 1000 + 1000 * 10 = 101w 次循环，而后一个执行计划则需要处理 1000 * 10 + 200 * 1000 = 21w 次循环，因此后者会更优

• A JOIN B 返回 10 条数据，B JOIN C 返回 9000 条数据；那么前一个执行计划需要处理 1000 * 1000 + 10 * 10 = 100.01w 次循环，而后一个执行计划则需要处理 1000 * 10 + 9000 * 1000 = 901w 次循环，因此前者会更优

• 更进一步，join 的策略还有 MapJoin、HashJoin、SortMergeJoin 等多种策略可选

那么此时就会面临选择，需要从多个执行计划中选择出最优的。这个选择的过程可以分解为三部分：

• Statistics：收集/维护统计信息
• Cost model：基于统计信息，对具体的执行计划进行代价评估
• Plan enumeration：对可能得执行计划进行搜索，对其代价进行比较，选择最优执行计划

二、业界思路

一个成熟的优化器，可能有几百条规则，每条规则都会作用于执行计划，并产生另一个逻辑等价的执行计划，因此我们可以把优化的问题理解为一个搜索的问题。业界主要使用动态规划的思想，即可以把原问题分解成子问题来解决复杂问题。

如上图：

• 对于 Join 来说可以有多种实现，例如 NestLoop 和 HashJoinJoin，即 Join 可以分解为两个子问题
• 而对于 NestLoop 来说，需要求解其子节点 Scan A 和 Scan B，Scan 也有多种实现，例如 SeqScan 和 IndexScan
• 同时，这里遇到了重叠子问题，在求解 HashJoin 的时候也需要计算 Scan A

就这样，将原问题分解为子问题求解，并配合统计信息及代价模型，就能找到那个最优的执行计划了。

目前，也就对于搜索的实现主要有两种：

• 自下而上：有哪些引擎用的这个？

• 自上而下：一般称为 Volcano/Cascades

2.1、自下而上

Calcite 的 CBO 使用了 Volcano/Cascades 思路，这部分我们配合 Calcite 的实现来讲。

三、Calcite 实现 - VolcanoPlanner

VolcanoPlanner 在搜索过程中涉及几个主要概念：

• RelNode：Calcite 的关系表达式，一个执行计划是 RelNode，执行计划上的节点也是 RelNode
• RelTrait：定义关系表达式的物理属性，共有三类：
  • Convention：Calcite 特有的概念，为了支持多（异构）数据源。每种 Convention 表示一种物理实现，比如：
    • Convention.NONE：不可实现的，必须转换成其他东西才能实现，cost 为正无穷大
    • EnumerableConvention：能返回 Enumerable 的 Convention 实现，一般默认用这个。通过 codegen 的方式来生成 linq4j 代码来访问并在本地内存操作数据
      • 注：LINQ4J 是 LINQ 的 java 实现。LINQ 提供一种统一的方式，支持在 C# 编程语言内直接创建被称为“查询表达式”的实体，在广义的数据上获取和操作数据。支持各种数据源：数据库、XML文档、内存集合等。
    • SparkRel.CONVENTION：通过 Enumerable 去访问/操作 Spark RDD 数据的实现
    • ......
  • RelCollation：描述 ordering 信息，包含 ordering 列（可以多个）和 ordering 顺序
  • RelDistribution：用来定义数据在物理存储上的分布方式（比如：single、hash、range、random 等）
• RelSet：
  • 一组逻辑上相等的 RelNode 的集合（这些 RelNode 都是经过一个个规则转换而来的）。所有的等价的 RelNode 都会记录在 List<RelNode> rels 中
  • rels 语义等价，但可以有不同的 Trait，比如

• RelSubset：

  • 在一个 RelSet 中相同的 RelTraitSet 的 RelNode 会在同一个 RelSubset 内

  • 添加一个 Rel 到 RelSubset 会天际到 rel 到对应的 RelSet 中

  • 一个 RelSet 可能有多个 trait（一组 RelNode 逻辑上等价，物理上可以不等价），比如在 [X] 和 [Y, Z] 进行排序，那么对于这个 RelSet 有两个 RelSubset

• VolcanoRuleMatch：优化规则与一组特定的目标表达式的匹配（一组是因为可以匹配单个或连续的表达式，比如 Project/Flilter/Join）

3.1、VolcanoPlanner 初始化

当通过 addRule 将这些 rules 都添加进来的时候，会在 Multimap<Class<? extends RelNode>, RelOptRuleOperand> classOperands 中缓存每个 Rule 可 apply 的 RelNode 类型，以加速后续的匹配

将物化视图添加到 Planner

在 HepPlanner 和 VocanoPlanner 中都有一个 List<RelOptMaterialization> materializations 成员，来持有可以用来识别的物化视图。

RelOptMaterialization 三个最核心的成员：

• List<String> qualifiedTableName：mv 全名

• RelNode tableRel：这个 mv 对应的 LogicalTableScan，后续要改写替换的时候用到

• RelNode queryRel：mv 对应的 DDL 的 RelNode 表达

3.2、VolcanoPlanner#setRoot(...): 基于 originalRoot 构建 RelSubset Graph

接下来我们以如下 RelNode 为例，来介绍 VolcanoPlanner 是如何进行 CBO 的，VolcanoPlanner.originalRoot: RelNode 如下

LogicalAggregate(group=[{0}], C=[COUNT()])
  LogicalProject(DEPTNO=[$2])
    LogicalValues(tuples=[[{ 100, 'Fred', 10, null, null, 40, 25, true, false, 1996-08-03 }, { 110, 'Eric', 20, 'M', 'San Francisco', 3, 80, null, false, 2001-01-01 }, { 110, 'John', 40, 'M', 'Vancouver', 2, null, false, true, 2002-05-03 }, { 120, 'Wilma', 20, 'F', null, 1, 5, null, true, 2005-09-07 }, { 130, 'Alice', 40, 'F', 'Vancouver', 2, null, false, true, 2007-01-01 }]])

接下来执行 VolcanoPlanner#setRoot(RelNode rel) 来为 rel 的每个节点创建对应的 RelSet 和 RelSubset，伪代码如下：

planner#registerImpl(RelNode rel, RelSet set)
        rel#onRegister(VolcanoPlanner planner)
            // input 为 rel.getInputs 的每个元素（循环）
            // setRoot 的时候，因为各层 rel 对应的 subset 都不存在
            // 结合下面的递归逻辑，会一直递归到叶子节点
                planner#ensureRegistered(input)        
                          if (如果 rel 对应的 subset 不存在): 
                                  planner#register(input, null)
                                          planner#registerImpl(input, set)
                          else:
                                  // setRoot 的流程中不会走到这

        if (rel 的等价 set 为 null):
                // 创建 rel 的等价 RelSet
                set = new RelSet(...)

        // 构建 rel, set, subset 的关联关系
        RelSubset subset = addRelToSet(rel, set)

        // 对于 rel 的每个 input，构建 input 的 set 与 rel 的 set 的父子关系
        ((RelSubset) input).set.parents.add(rel)

        // 找出所有该 rel 能 match 的 rules 
        // 构建 VolcanoRuleMatch 添加到 RuleQueue 中
        // 注意：这里可以看到是越底层的节点的 VolcanoRuleMatch 在 RuleQueue 的越前面
        fireRules(rel)

总结来说，做了这么几个事：

1. 自上而下递归的为每个 relation expression（后文简称 rel） 创建对应的 RelSet 及 RelTraitSet 为 None.[]（NONE 表示 Convention 为空，即不做任何物理实现；[] 表示不额外做排序）的 RelSubset（触发是自上而下，实际上是越底层的 rel 越早创建相应的 set 和 subset）
2. 构建 rel、set、subset 之间的关联关系；构建 input 的 set（RelSet）和 parent 的 set 的父子关系（只有 Convention 相同能作为父子，以及非 None 的 Convention 可作为 None 的 parent）

3. 自下而上的为每个 rel 筛选出 match 的 rules，封装成 VolcanoRuleMatch 添加到 RuleQueue 中（注意，这里只是将 Rules 添加到 Queue 中，并没有执行），在 Queue 中越底层的 rel 的 match 的 VolcanoRuleMatch 在越前面，如：

   
   
4. setRoot 得到的 RelSubset 的树存放在 RelSubset VolcanoPlanner.root 成员中

3.3、VolcanoPlanner#findBestExp() Part1: 应用优化规则构建搜索空间

代码主要在 VolcanoPlanner#findBestExp 的 ruleDriver.drive()

其中 ruleDriver 有两种实现：

• IterativeRuleDriver：对应IterativeRuleQueue ，该算法不断的从 RuleQueue 中取出优化规则并执行。退出条件有两种：

  • Queue 中没有规则需要执行了
  • 在规则执行时抛出 VolcanoTimeoutException 异常，当 VolcanoPlanner 的 cancelFlag 设置为 true 时会抛出这个异常，所以在使用如果觉得优化时间太长，超过一定时间可设置cancleFlag 为 true 强制优化结束

• TopDownRuleDriver：对应 TopDownRuleQueue，是 Cascades 论文的实现，也参考了 Columbia 优化器，其内部并非是一个简单的递归函数，而是用栈 tasks 模拟了整个 top-down 的过程：不断从栈顶取出 Task 执行，Task 执行中又会产生新的 Task，重复这一过程直到栈为空。实现了递归的效果，但是可以不用每次“递归到底”，来实现剪枝的效果

分别详见：

[VolcanoPlanner 之 IterativeRuleDriver]
[VolcanoPlanner 之 TopDownRuleDriver]

3.4、VolcanoPlanner#findBestExp() Part2: 找出 cost 最小的执行计划

代码主要在 VolcanoPlanner#findBestExp 的 RelNode cheapest = root.buildCheapestPlan(this)

不管使用 IterativeRuleDrvier 还是 TopDownRuleDriver，buildCheapestPlan 的逻辑都是一样的

核心逻辑主要封装在 CheapestPlanReplacer 中，该类用于：以递归的方式，遍历上一步生成的 RelSet Tree，用 cheapest 的 expression 替换每一个 RelSet。

findBestExp 中通过调用 RelNode cheapest = replacer.visit(root, -1, null)来获取最终的 best plan，其逻辑如下：