Calcite系列(九)：执行流程-优化器优化

背景

优化器优化是SQL处理的第四步，也是最核心的一步，优化器优化本质是基于优化规则实现关系代数等价转换。

关系代数等价转换：是数据库查询优化中的一个重要概念，指的是将一个关系代数表达式转换为另一个关系代数表达式，尽管这两个表达式的形式有所不同，但它们具有相同的语义且计算结果相同，而新转换的关系表达式的计算性能往往更优于原有的表达式。在Calcite中，关系代数等价转换即为RelNode计划树的等价转换。

RelNode计划树等价转换

目前，Calcite内置两类优化器：

• HepPlanner：RBO（Rule-based Optimizer）基于规则的优化器，将计划树构建为DAG有向无环图，按顺序依次遍历并执行优化规则
• VolcanoPlanner：CBO（Cost-based Optimizer）基于代价的优化器，基于Volcano/Cascades Optimizer 经典的优化器框架实现，通过Memo维护等价集，使用贪心算法寻找最优解。 除此之外，CBO的优化效果取决于两个关键因素：代价模型（Cost Model）和 统计信息（Statistics）

优化器类型

优化规则

Calcite内置的优化规则超过200条，可分为两个类别：

• TransformationRule：用于逻辑计划的关系代数等价转换，例如常量折叠、谓词下推、列剪裁等。逻辑计划等价转换并不能保证转换后的计划树更优，其子类SubstitutionRule维护了转换后一定效果更优的规则集
• ConverterRule：用于Calling Convention，实现不同Convention之间的转换，可等价理解为：实现逻辑计划到物理计划的转换

如图展示基于优化规则实现的计划树等价转换：

1. 常量折叠：在优化时直接计算出常量表达式的值，如图2020+6=2026，将计算后的常量值代替常量表达式，减少查询执行时的常量计算
2. 谓词下推：将过滤条件（谓词）尽可能提前进行计算和应用，即在计划树中，尽可能将Filter算子下推到树的底层，通过过滤下推降低上层操作的数据输入量
3. 列剪裁：只获取查询中实际所需的列，通过Project算子移除未使用的列，从而减少使用列和数据处理量

优化效果

Calcite通过执行优化规则，实现RelNode等价转换，由三个步骤组成：

1. 规则匹配模式：基于 RelOptRule#matches 判断规则应用的条件和模式，确保特定树节点，只能应用满足匹配模式的规则，即 实现规则筛选过程
2. 规则应用：基于RelOptRule#onMatch→RelOptRuleCall#transformTo 触发规则执行，实现计划树的等价转换
3. 等价节点构建：转换后的等价计划树维护在RelOptRuleCall中，优化器可根据实现要求，构造出对应的等价RelNode

在Calcite中，各类优化器都基于相同的规则应用机制实现计划树等价转换，不同优化器的主要差异在于规则匹配策略和等价节点构建的方式不同。

RBO优化器

下图展示RBO优化器HepPlanner的执行流程，分为三个步骤：

1. 初始化：将RelNode转换为DAG有向无环图，其中各个顶点使用 HepRelVertex 表示并维护关联的子节点
2. 搜索最优计划树：遍历DAG按照顺序依次触发规则应用（fireRule），其中遍历顺序可基于HepMatchOrder参数化配置
3. 构建最优计划树：基于Visitor模式自顶向下遍历DAG顶点，获取对应的RelNode节点，基于转换后RelNode构建出最优计划树

CBO优化器

备注：该CBO流程说明基于Calcite版本V1.21.0展示，与最新Calcite版本存在差异

执行流程

下图展示CBO优化器VolcanoPlanner的执行流程，分为三个步骤：

1. 初始化：构建等价集，遍历RelNode生成对应的Relset/RelSubset。注册RelSubset时，计算节点代价并添加规则到RuleQueue。
2. 搜索最优计划树：根据RuleQueue规则队列中弹出匹配条件的优化规则，应用规则后，若新计划树成本更低，则重新注册该等价计划树并将其维护在搜索空间中。退出计划树搜索需满足以下任一条件：（1）. RuleQueue中可应用的优化规则为空；（2）. 最优计划树COST代价稳定，没有显著下降；（3）. 搜索优化超时
3. 构建最优计划树：退出搜索后，遍历RelSubset维护的最优代价节点，构建出最优计划树

其中，CBO优化器基于RuleQueue (规则队列)维护优化规则集，与RBO顺序匹配规则不同，CBO规则匹配是随机的。主要基于RelSubset中计算的Importance倒序排列，COST代价越高的节点Importance越大，会优先进行规则匹配。

初始化

如图展示VolcanoPlanner初始化的实现流程，初始化执行入口有两个：

• changeTraits 变更RelNode物理属性，遍历RelNode计划树注册各个节点，基于VolcanoPlanner#addRelToSet 方法生成相对应的RelSet和RelSubset，若已存在等价计划树，则追加到对应的等价集里
• setRoot 保证AbstractConverter节点在RelSubset计划中已被注册，该节点可用于后续Convention的转换触发

初始化过程中，核心处理主要包括：

• 代价计算：如下图紫色框所示，注册RelSubset 时，将会调用propagateCostImprovements 方法计算该等价集中的所有计划树COST代价，并独立维护代价非infinite且代价最小的最优计划树，该过程除了计算COST代价也会触发RelNode Importance计算，对应Importance维护在RuleQueue中，用于排序规则的执行顺序
• 注册规则：如下图红色框所示，注册完RelSubset后，基于fireRules从初始化规则集中匹配出满足该节点的规则子集，并根据Importance将规则子集添加到RelQueue规则队列中

其中，RelSet 代表一组关系代数等价计划树，即等价的逻辑计划树集合；RelSubset属于RelSet子集，代表一组物理属性相同的关系代数等价计划树，即等价的物理计划树集合。

搜索最优树

如图展示VolcanoPlanner搜索最优计划树的实现流程：

1. 基于RuleQueue弹出对应节点匹配的优化规则，通过VolcanoRuleCall触发规则应用以生成新的等价计划树
2. 基于ensureRegistered方法注册新的等价计划树，如果新计划树的代价低于对应RelSubset等价集中的最优计划树，则重新递归计算父节点代价，并将该计划树维护在Memo搜索空间中

计划树变换

下面将以计划树变换图直观的展示CBO执行流程，示例SQL：select name, num from student where name = 'add'

1. 初始化：changeTraits将RelNode变为RelSubset，代表一组物理属性相同的逻辑计划；setRoot保证AbstractConverter节点注册，由于Convention=NONE，此时COST代价是infinite无穷大
2. 搜索执行：基于最优计划树搜索，最终得到COST代价最优的计划树，此时COST代价是有限的

CBO最优计划树搜索基于贪心算法和自顶向下动态规划实现，遵循动态规划的最优子结构原理，局部最优可最终得到全局最优。因此，在Memo搜索空间中，可以自顶向下从物理属性相同的RelSubset中选择最优代价的子节点，组合得到最优计划树。

构建最优计划树流程如下图所示：从根节点(Root节点)出发

1. rel#41 等价集中 EnumerableProject 代价最低，对应子节点为 rel#58
2. rel#58 等价集中 EnumerableFilter 代价最低，对应子节点为 rel#63
3. rel#63 等价集中 JdbcToEnumerableConverter 代价最低，对应子节点为 rel#26
4. rel#26 等价集中 JdbcTableScan 代价最低，且该节点为TableScan叶子节点

Calling Convention

Calling Convention：实现不同Convention转换，在CBO优化阶段完成的。下图展示基于ConvertRule转换规则将计划树从Convention=NONE（代价无穷大infinite）的LogicalPlan转换为Convention=ENUMERABLE（代价有限）的可执行计划。

跳转

我正在参与2024腾讯技术创作特训营最新征文，快来和我瓜分大奖！