Calcite CBO ① - 核心流程

2024-02-17  本文已影响0人  牛肉圆粉不加葱

一、问题 & 目标

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

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

RBO: Rule Based Optimizer

CBO: Cost Based Optimizer

从上面的描述可知，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 谓词使得：

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

二、业界思路

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

如上图：

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

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

2.1、自下而上

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

三、Calcite 实现 - VolcanoPlanner

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

3.1、VolcanoPlanner 初始化

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

将物化视图添加到 Planner

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

RelOptMaterialization 三个最核心的成员：

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 有两种实现：

分别详见：

[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，其逻辑如下：

上一篇 下一篇

猜你喜欢

热点阅读