Calcite 的优化器实现

手机用户2895 2023-10-27

1470

CASCADE-STYLE OPTIMIZER

原理

cascade-style 的优化器，其优化过程本质上是一种 Top-down 模式的动态规划算法：

给定初始的逻辑执行计划，放入一个称为“Memo”的数据结构中；这个计划是“逻辑计划”，基本上等同于对 SQL 的直接翻译；这个 Memo 的数据结构用于去重（i.e., 动态规划算法中的 memo table）
做一些简单 rewritting；比如 filter pushdown，common expression removal，几乎总是有益的，不用考虑代价；又比如一些必须做的改写，比如 subquery 的改写，AGGR(DISTINCT) 的改写；（IMCI 的现有优化器里面都是这一种类型的 rule）
自顶向下遍历 memo 中的每个节点（i.e., group expr），利用“转换规则”生成新的等价执行计划，并计算 cost；这里的转换规则分两种：
1. transform rule：等价的逻辑转换，比如把 R JOIN S 转换成 S JOIN R
2. implementation rule：物理转换，比如 JOIN 可以实现成 nested loop join、sort-merge join、hash join 等；group by 可以实现成 hash group by、streaming group by 等；

一般应用完 transform rule 后面会紧接着应用 implementation rule，因为只有物理算子才能算 cost；
一般成熟的优化器包含几十到上百条转换规则；

由于有 memo 的存在，在应用转换规则的时候，可以探测到 subtree 是否已经遍历过，避免重复遍历；比如 R JOIN S 转换成 S JOIN R 时，因为前面已经遍历过 R JOIN S，因此可以在 memo 中查到 R 和 S 已经遍历并且算出 cost，避免了重新遍历 R 和 S；同时由于有 cost 的存在，如果 cost 已经超过此前得知的最低 cost，那么就不需要接着遍历这颗树的其他未遍历节点了；
在遍历完全，或者遍历次数/时间超过阈值后，挑选出 cost 最低的执行计划，编译&执行；

数据结构

下图是一个 memo 的例子：

其中核心的数据结构是：

memo：类似于 topdown 动态规划算法里面的 memo table，用于保存已经优化过的内容，在后续优化过程中可以用于去重
Group: 一个 Group 中包含多个等价的 GroupExpr （i.e., group expressino)；上下两个 Group 之间的关系，类似于一个 relation 和他的 child relation 的关系；
GroupExpr：可以分为 logical group expr 和 physical group expr；比如 (t1 JOIN t2) 是 logical group expr，(t1 HASH JOIN t2) 是 physical group expr；

实现

业界的 cascade-style 优化器的实现，有 SQL Server、Calcite、Orca、Cockroach，以及 CMU db group 用于教学的 Peleton；在之前看过的 Orca、Calcite、Peleton 的代码来看，这些 cascade-style 的优化器的实现都来源于 columbia database 的 query optimizer；在《 EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER 》这篇 paper 里面，主要的优化过程被实现成了一个由 N 个 task 的栈（stack）组成的循环：

其中 task 的类型包括：

Optimize Group：对一个 Group 进行优化。其实就是对其中的每个 GroupExpr 进行优化
Optimize Expression: 优化一个 GroupExpr，即对每个 Expression 应用优化规则；
Explore Group: 对 logical relation 进行等价变化
Apply Rule: 应用优化规则，将 logical relation 转换成等价的 logical relation；或者是将 logical relation 转换成 physical relation
Optimize Input：对代价进行估算，自底向上地递归地计算子节点的统计信息和代价，再计算当前节点

在优化的过程中会进行 prunning，同时会从上往下传递 required properties。

Calcite 的 TopDown Volcano planner

Calcite 框架内部的的优化器主要有三种实现方式

top-down 的 volcano planner；这个 planner 属于 cascade-style 的优化器
iterative 的 volcano planner；优化时，遍历所有规则，对每一条规则，找出所有对应的节点，然后应用规则；
HepPlanner；利用启发式方法进行优化的 planner；

可以看出，“Volcano planner”有两种实现，一种是 top-down 的，一种是 iterative 的。前者是我们熟悉的 cascade-style 的实现，后者不是。不知道为何 calcite 要把这两者都放到 VolcanoPlanner 里面。

这里只描述 top-down 的 volcano planner。

Calcite 的实现基本上就是上面所述的 columnbia database optimizer 的优化过程；核心代码在 core/src/main/java/org/apache/calcite/plan/volcano/TopDownRuleDriver.java

By the way, GPORCA 的实现，大体也类似：
主要的入口是 CEngine::Optimize()，循环调度不同的 “job”，类似于 calcite 的 task：

Calcite 的 logical transformation rules

这里描述 Calcite 框架内部的 logical transformation rules。所谓 logical transformation，即这些规则只运用于 logical relation，将一个 logical relation 变成等价的另一个（多个） logical relation，后续根据这两个等价的 logical relation 来**实现（implement）或者枚举（enumerate）**出不同的物理实现，然后计算 cost（运行代价），这样就可以选出 cost 最小的计划。

注：

这里描述的 calcite 的 logical transformation rules 位于 core/src/main/java/org/apache/calcite/rel/rules/ 目录下，是最 common 的转换规则；
calcite 有一系列针对 materialized view 的转换规则，这里忽略。
| 规则名称 | 含义 | IMCI 相关 | IMCI 是否实现 |
| — | — | — | — |
| AbstractJoinExtractFilterRule | 把 inner join 转换成 cartesian join (i.e., cross product) + filter；其中 filter condition 就是 inner join 的 condition；

这个转换使得

join condition 可以跟 join 上方的其他表达式结合；
同时也可以为 FennelCartesianJoinRule 生成可作为输入的节点；

Note:

“join condition 可以跟 join 上方的其他表达式结合”，这个可以通过 condition pushdown 来实现；
FennelCartesianJoinRule 看起来是其他插件提供的规则，在 apache calcite 的代码里面找不到；
| IMCI 有个类似的 JoinToFilter 规则，不过是把 inner join 里面的非 equal 类型的 predicate 提取出来成为一个单独的 filter，filter 下方的 join 是一个只有 equal 类型 predicate 的 inner join，使得我们可以利用 hash join 这样的算法；

比如 t1 inner join t2 on t1.a = t2.a and t1.b > t2.b；可以变成一个 hash join + 一个 filter，这可能比一个单独的 nested loop join 更高效； | 不需要实现 |
| AggregateCaseToFilterRule | 把 aggr expr 里面带有 case when 的表达式，转换成 filter + aggr；比如，把这样的查询：```sql
SELECT
SUM(CASE WHEN gender = ‘F’ THEN salary END)
FROM Emp

转换成```sql
SELECT SUM(salary) FILTER (WHERE gender = 'F') FROM Emp

Note:

这个规则只能应用于 case when 只有一个 when clause 的情况，i.e., case when 充当过滤作用（因为如果 when 条件不符合，则默认输出 null，而 aggr 表达式都是忽略 null 的），因此有一定的限制性；
这个规则貌似想为 SUM() 提供一个“纯粹”的输入；虽然这种转换几乎不增加代价，但是也看不到可能产生收益的地方；可能跟某些执行器的执行相关；

Note:

看起来跟 ROLLUP / CUBE 相关；
mysql 没有这种语法
|
| 不需要实现 |
| AggregateExtractProjectRule | 把 aggr 函数里面的表达式抽出来，生成一个 project 推到下面去；

Note:

这里的 project 跟 imci 的 project 不是一个东西；一般意义上的 project 是关系代数里面的 “project” 操作，可以当作“列裁剪”；imci 的 project 是用来 send result；
|
IMCI 在优化完成后会遍历 relation tree 推导出哪个算子需要吐出哪些列（see SetupRelOutput()）；比如这样一棵树

PROJECT (t1.c)
	FILTER (t1.b >3)
		JOIN (t1.a = t2.a)

因为 join 的上面还需要 t1.b 和 t1.c，则 join 只需要输出 t1.b 和 t1.c 即可，t1.a 和 t2.a 不需要输出；
2. SQLServer 有一个相关的算子 ComputeScalar，用来输出一个表达式的值；比如 SELECT SUM(a + b), MIN(a+b)，可以在聚合算子下方挂一个 ComputeScalar，先把 a + b 算出来，这样就不需要在 SUM() 和 MIN() 里面重复计算了；
| ComputeScalar 未实现 |
| AggregateFilterTransposeRule | 把一个 filter + groupby 变成 groupby+ filter + groupby；比如```
groupby (group by t1.b, sum(t1.c))
filter (t1.a > 1)

变成```
groupby (group byt1.b, sum(sc))
   filter (t1.a > 1)
			groupby (group by t1.b, t1.a,  sum(t1.c) as sc)

Note:

一般情况下这种转换是没有收益的，因为一般 group by + aggregation 的代价比 filter 高；只有当 filter 的代价非常高的时候（比如进行了某些很复杂的计算），这种转换才有意义；
|
| 不需要实现 |
| AggregateJoinRemoveRule | 消除 distinct aggregation 下方的 left join；比如，下面的```sql
select
distinct s.product_id
from
sales as s
left join product as p
on s.product_id = p.product_id

可以转换成```sql
select distinct s.product_id from sales as s

Note:

必须是 distinct aggregation (i.e., SELECT DISTINCT)
aggregation 下方的 join 必须是 left outer join 或者 right outer join；如果是 left outer join，则 aggregation 中使用的列，只能是 join 的 left child 的 output columns；如果是 right outer join，则只能是 right child 的 output columns;
下方不能是 inner join，这是因为 inner join 本身会过滤掉没有 join 上的行，如果移除了这个 join，则结果可能多出一些本该被 inner join 过滤掉的行；而 left / right join 没有这个问题，因为 left join 一定会输出左边的所有行，right join 一定会输出右边的所有行；
需要注意的是，join predicate 不一定是 equal，可以是其他类型的 predicate
| | 未实现 |
| AggregateJoinJoinRemoveRule | 消除 distinct aggregation 下方的连续 left join；比如，下面的```sql
select distinct s.product_id, pc.product_id
from sales as s
left join product as p
on s.product_id = p.product_id
left join product_class pc
on s.product_id = pc.product_id

可以被等价转换成```sql
select distinct s.product_id, pc.product_id
   from sales as s
   left join product_class pc
     on s.product_id = pc.product_id

换言之，relation tree```sql
aggregation (distinct, t1.a, t3.a)
left join (t1.a = t3.a)
left join (t1.a = t2.a)
t1
t2
t3

可以被转换成```sql
aggregation (distinct, t1.a, t3.a)
	left join (t1.a = t3.a)
  	t1
    t3

Note:

必须是 distinct aggregation
两个 join 都必须是 left join (实际上两个连续的 right join 应该也是可以的，可能是考虑到 right join 可以被其他规则等价转换成 left join，所以 calcite 里面没有这样的匹配）
top join 的 join condition （i.e., t1.a = t3.a）不能引用 bottom join 的 right child （i.e., t2）的列；
top join 的 left join keys （i.e., t1.a）必须跟 bottom join 的 left join keys （i.e., t1.a）一样
需要注意的是，join predicate 不一定是 equal，可以是其他类型的 predicate
| | 未实现 |
| AggregateJoinTransposeRule | 将 aggregation 下推到 join 下方，利用 aggregation 的聚合作用，将 join 的输入减少；比如，从```sql
groupby (group by t1.a)
inner join (t1.a = t2.a)

变成```sql
groupby (group by t1.a)
	inner join (t1.a = t2.a)
  	groupby (group by t1.a)

| | 未实现 |
| AggregateMergeRule | 把两个连续的 aggregation 合并到一起；比如```sql
aggregation (group by t1.a, max(t1.c))
aggregation (group by t1.a, t1.b, max(t1.c))

可以合并成```sql
aggregation (group by t1.a, max(t1.c))

合并有一定的规则（不考虑 ROLLUP / CUDE）：

SUM of SUM becomes SUM; SUM of COUNT becomes COUNT; MAX of MAX becomes MAX; MIN of MIN becomes MIN. AVG of AVG would not match, nor would COUNT of COUNT, etc
top aggr 的 grouping keys 必须是 bottom aggr 的子集
top aggr expr 中的表达式（e.g, select sum(tmp.field) 中的 tmp.field 必须是 bottom aggr 中的某一个 aggr expr；
top aggr expr 不能是 AGGR(DISTINCT)；
aggr expr 中的表达式不能是 CASE WHEN 这种带过滤效果的；（实际上如果满足 3 则不可能满足 5）；
如果 top aggr 是 scalar-aggregation (i.e., 没有 group by），则不能应用 “SUM of COUNT becomes COUNT” 这个规则，因为当 bottom aggr 的是一个 empty input 的 group by，则这个转换会导致结果从 NULL -> 0，结果错误
| | 未实现 |
| AggregateProjectMergeRule | 用来处理 Aggr 下方是 Project 算子的情况，做表达式的合并； | IMCI 不需要实现；可以由 ComputeScalar 实现； | 不需要实现 |
| AggregateProjectPullUpConstantsRule | 用来消除 Aggr output constant 的情况，比如 select 100, sum(t1.a) xxx; calcite 会在上方加一个 project 100 来实现； | IMCI 不需要实现 | 不需要实现 |
| AggregateProjectStarTableRule | 用来处理 StarTable -> Project -> Aggregate 这种情况，然后利用 AggregateProjectMergeRule 把 aggregate / project 合并到一起；

StarTable 看起来像是一个 TableSpool； | IMCI 不需要实现 | 不需要实现 |
| AggregateReduceFunctionsRule | 对 aggr 表达式重写：```sql
AVG(x) → SUM(x) / COUNT(x)
STDDEV_POP(x) → SQRT( (SUM(x * x) - SUM(x) * SUM(x) / COUNT(x)) / COUNT(x))
STDDEV_SAMP(x) → SQRT( (SUM(x * x) - SUM(x) * SUM(x) / COUNT(x)) / CASE COUNT(x) WHEN 1 THEN NULL ELSE COUNT(x) - 1 END)
VAR_POP(x) → (SUM(x * x) - SUM(x) * SUM(x) / COUNT(x)) / COUNT(x)
VAR_SAMP(x) → (SUM(x * x) - SUM(x) * SUM(x) / COUNT(x)) / CASE COUNT(x) WHEN 1 THEN NULL ELSE COUNT(x) - 1 END
COVAR_POP(x, y) → (SUM(x * y) - SUM(x, y) * SUM(y, x) / REGR_COUNT(x, y)) / REGR_COUNT(x, y)
COVAR_SAMP(x, y) → (SUM(x * y) - SUM(x, y) * SUM(y, x) / REGR_COUNT(x, y)) / CASE REGR_COUNT(x, y) WHEN 1 THEN NULL ELSE REGR_COUNT(x, y) - 1 END
REGR_SXX(x, y) → REGR_COUNT(x, y) * VAR_POP(y)
REGR_SYY(x, y) → REGR_COUNT(x, y) * VAR_POP(x)

 |  | 未实现 |
| AggregateRemoveRule | 当一个 GROUP BY Aggregate 的输入已经是 DISTINCT（已经去过重了），且：
1. 这个 Aggregate 不包含 aggr 函数（i.e., SELECT DISTINCT），或
2. 这个 Aggregate 中的 aggr 函数都是 splittable 的（splittable 的意思是，可以先做“partial aggregate”，然后组合起来，比如 COUNT()，可以先在 subset 上做 COUNT()，然后 SUM() 起来）

则这个 GROUP BY Aggregate 能够直接被消除； |  | 未实现 |
| AggregateStarTableRule | 匹配 StarTable -> Aggregate 这个 pattern，并要求 StarTable 做出一定变化；略； | IMCI 不需要实现 | 不需要实现 |
| AggregateUnionAggregateRule | 把 UNION 底下的两个 Aggregate 抽到 UNION 上面，使得最终只需要做一次 Aggregate； |  | 未实现 |
| AggregateUnionTransposeRule | 把一个 Aggregate 推到一个 none-distinct UNION 下面 |  | 未实现 |
| AggregateValuesRule | 用来统一 scalar-aggregate 和 group by aggregate 的处理；在输入空集时，scalar-aggregate 始终返回一行，而 group by aggregate 返回空集； | IMCI 不需要实现；IMCI 的执行器在一个算子里面实现了两 scalar-aggregate 和 group by aggregate；SQL Server 的做法是只实现其中一种，然后加一个 CASE WHEN 表达式来实现另外一种； | 不需要实现 |
| CalcMergeRule | 将两个连续的 LogicalCalc 合并成一个 | IMCI 如果实现了 ComputeScalar，也需要将连续的 ComputeScalar 合并成一个 | 未实现 |
| CalcRelSplitter | 当一个 LogicalCal 负责计算两种输入源（Java v.s. Fennel）的表达式时，将这个LogicalCal切分成两个LogicalCal； | 跟 calcite 的 multiple input source 相关；IMCI 不需要实现； | 不需要实现 |
| CalcRemoveRule | 删除 trivial 的 LogicalCal | IMCI 应该不会产生 trivial 的 ComputeScalar，所以应该不需要实现； | 不需要实现 |
| CalcSplitRule | 将一个 LogicalCal 转换成 Project + Filter | 跟 calcite 的特定优化相关；IMCI 应该不需要实现； | 不需要实现 |
| CoerceInputsRule | 将输入数据 cast 到特定的类型后再输出 | IMCI 有 implicit cast，所以不需要实现 | 不需要实现 |
| CoreRules | 所有 transform rules 的集合 |  | 不需要实现 |
| DateRangeRules | 作用于某些“时间类型的表”，比如 druid 的一些表；比如，如下 SQL```sql
SELECT 
  ...
FROM 
  sales 
  JOIN time_by_day USING (time_id) 
WHERE 
  time_by_day.the_year = 1997 
  AND time_by_day.the_month IN (4, 5, 6)

转换成```sql
SELECT
…
FROM
sales
JOIN time_by_day USING (time_id)
WHERE
the_date BETWEEN DATE ‘2016-04-01’
AND DATE ‘2016-06-30’

 | IMCI 没有这种表/列类型；不过二级索引，以及 prunner 相关的优化，可以做成类似的； | 不需要实现 |
| ExchangeRemoveConstantKeysRule | 把 EXCHANGE 算子的 constant key 消除掉；比如```sql
SELECT key,value FROM (
  SELECT 1 AS key, value FROM src
) r DISTRIBUTE BY key

可以被转换成：```sql
SELECT 1 AS key, value FROM src

 |  | 未实现 |
| FilterAggregateTransposeRule | 在 Filter -> Aggregate 这样的 pattern 中，把 Filter 下推到 Aggregate 下方 |  | 未实现 |
| FilterCalcMergeRule | 把 LogicalCalc -> Filter 合并成一个 LogicalCalc（也就是说 LogicalCalc 需要有过滤功能） | IMCI 的 ComputeScalar 不具有过滤功能，因此这个规则应该没有应用意义； | 不需要实现 |
| FilterCorrelateRule | 把 Filter 推到 CorrelateJoin 下方；解关联相关； | IMCI 解关联子查询的方式与 calcite 不尽相同，因此未必会原模原样地实现这条规则。 | 未实现 |
| FilterFlattenCorrelatedConditionRule | 解关联相关； |  | 未实现 |
| FilterJoinRule | 把 Join 上方的 filter 或者 Join 的 join predicate 推到下方 | IMCI 的 FilterPushDown 以及 JoinPredPushDown 两条规则结合起来就能实现这个功能； | 已实现 |
| FilterMergeRule | 把两个连续的 Filter 合并到一起 |  | 未实现 |
| FilterMultiJoinMergeRule | 把一个 Filter 跟一个 MultiJoin 合并到一起，产生一个“语义更丰富”的 MultiJoin，使得 join reorder 过程的选择会更多；Join reorder 相关 | IMCI 的 join reorder 算法未必与 calcite 的方法相同，因此未必会原模原样地实现这条规则。 | 未实现 |
| FilterProjectTransposeRule | 把 Filter 推到 Project 下方 | 放到 IMCI 里面，则类似于把 Filter 推到 ComputeScalar 下方，i.e., 在 ComputeScalar 计算表达式之前，先过滤掉一些数据 | 未实现 |
| FilterRemoveIsNotDistinctFromRule | 把 NULL SAFE EQUAL 转换成等价的表示形式（calcite 里面的 IS NOT DISTINCT FROM 即是 mysql 里面的 null safe equal） |  | 未实现 |
| FilterSetOpTransposeRule | 把 Filter 下推到 Set 下方 | IMCI 里面没有 Set 这个 operator；实现了完全的解关联算法后或许会增加 Set 这个 operator； | 未实现 |
| FilterTableFunctionTransposeRule | 把 Filter 推到 LogicalTableFunctionScan 下方 | 应该类似于 IMCI 里面把 Filter 推到 table scan 上，在 table scan 过程中做 filter；这个功能在 FilterPushDown 这个规则中已经实现； | 不需要实现 |
| FilterTableScanRule | 类似于  FilterTableFunctionTransposeRule |  | 不需要实现 |
| FilterToCalcRule | 把一个 Filter 转换成 LogicalCalc；这个转换与 FilterCalcMergeRule 之类的规则结合起来使用，能够将两个 Filter 转换成 LogicalCal | IMCI 的 ComputeScalar 不具有过滤功能，因此这个规则应该没有应用意义； | 不需要实现 |
| IntersectToDistinctRule | 把 Interset 转换成 UNION 和 Aggregate 的组合（i.e., 用 UNION 和 Aggregate 来实现 Interset） | MYSQL/IMCI 没有 INTERSET 这个 operator，因此应该不需要实现。如果后面增加 Interset 算子，或许需要实现； | 不需要实现 |
| JoinAddRedundantSemiJoinRule | 把一个 join 变成 semi join + join：

LogicalJoin(X, Y) → LogicalJoin(SemiJoin(X, Y), Y)

产生一个“语义更丰富”的 产生一个“语义更丰富”的  join，对 join reorder 应该是有好处的； | 
 | 未实现 |
| JoinAssociateRule | ((a JOIN b) JOIN c) → (a JOIN (b JOIN c)) |  | 未实现 |
| JoinCommuteRule | (a JOIN b) → (b JOIN a) |  | 未实现 |
| JoinExtractFilterRule | 把一个 inner join 转成 cartesian inner join + filter；这个 filter 或许可以跟上方的其他 operator 结合； | IMCI 有个类似的 JoinToFilter，不过只是将 inner join predicate 中 "none-equal" 的部分抽出来转成 filter，使得这个 inner join 可以用 hash join 等实现； | 未实现 |
| JoinProjectTransposeRule | 把 join下方的 project 提取到 join 上方
Note:
1. 这个 project 不能是 left outer join 的 null-generating 的一边产生的；（关于这个 null-generating 的特殊之处，参考 IMCI 的 materialize 里面对 null-on-null expression 的处理）
 | IMCI 不需要实现； | 不需要实现 |
| JoinPushExpressionsRule | 把 join 中的表达式往下推；比如```sql
emp JOIN dept ON emp.deptno + 1 = dept.deptno

其中如果在 join 之前把 emp.deptno + 1 这个表达式先计算出来，则这个 join 就变成 t1.a = t2.a 这样的简单的 join 了； | 除非 emp.deptno + 1 这样的表达式在 join 的过程中被计算多次，否则推到下方意义不大；

如果要推到下方，则加一个 ComputeScalar 节点即可；

对 Aggregate 同样需要这样做，比如 TPCH Q1 中，、```sql
select
l_returnflag,
l_linestatus,
sum(l_quantity) as sum_qty,
sum(l_extendedprice) as sum_base_price,
sum(
l_extendedprice * (1 - l_discount)
) as sum_disc_price,
sum(
l_extendedprice * (1 - l_discount) * (1 + l_tax)
) as sum_charge,
avg(l_quantity) as avg_qty,
avg(l_extendedprice) as avg_price,
avg(l_discount) as avg_disc,
count(*) as count_order
from xxx;

有些表达式（比如 l_extendedprice * (1 - l_discount)） 是被重复计算的；像 SQL Server 会在 Aggregate 之前加一个 ComputeScalar 节点先把这些需要重复计算的表达式算出来，在 Aggregate 里面直接引用这个结果即可，不需要重复计算，提升了运算效率； | 未实现 |
| JoinPushThroughJoinRule | 把一个 ((A JOIN B) JOIN C) 中 xxx JOIN C 的 join predicate 推到里面那个 join 里；比如，```sql
(sales as s join product_class as pc on true)
   join product as p
   on s.product_id = p.product_id
   and p.product_class_id = pc.product_class_id

变成```sql
(sales as s join product as p on s.product_id = p.product_id)
join product_class as pc
on p.product_class_id = pc.product_class_id

在推之前，最里面的 join 只有一个 true predicate 作为 join condition，而后面的 join 有俩；推之后，每个 join 都有一个 equal predicate 作为 join condition 了； | MYSQL 的 equal propogation 应该会做这个事；

但是 mysql 的 equal propogation 可能会导致预期之外的关联项，因此我们可能选择不走 mysql 的 equal propogation，此时就需要这条规则了； | 未实现 |
| JoinPushTransitivePredicatesRule | 与 FilterJoinRule 里面把 join 中已有的 predicate 变成 filter 推到下方不同的是，这个规则会根据已有的 join predicate “推导”出等价的条件，下推到下方； | MYSQL 应该做了类似的事，但是不知道实现程度如何；

如果能从 join predicate 中推导出一些有用的等价条件，用于 prunning，应该是比较有用的； | 未实现 |
| JoinToCorrelateRule | 解关联相关 |  | 未实现 |
| JoinToMultiJoinRule | join reorder 相关；
把多个连续的 join 转成一个 multijoin，比如
A JOIN B → MJ(A, B)
A JOIN B JOIN C → MJ(A, B, C)
A LEFT JOIN B → MJ(A, B), left outer join on input#1
A RIGHT JOIN B → MJ(A, B), right outer join on input#0
A FULL JOIN B → MJ[full](A, B)
A LEFT JOIN (B JOIN C) → MJ(A, MJ(B, C))), left outer join on input#1 in the outermost MultiJoin
(A JOIN B) LEFT JOIN C → MJ(A, B, C), left outer join on input#2
(A LEFT JOIN B) JOIN C → MJ(MJ(A, B), C), left outer join on input#1 of the inner MultiJoin TODO
A LEFT JOIN (B FULL JOIN C) → MJ(A, MJ[full](B, C)), left outer join on input#1 in the outermost MultiJoin
(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) → MJ[full](MJ(A, B), MJ(C, D)), left outer join on input #1 in the first inner MultiJoin and right outer join on input#0 in the second inner MultiJoin |  | 未实现 |
| JoinUnionTransposeRule | 把 join 下推到 none-distinct union 下方：
把```sql
JOIN
	UNION_ALL
  	t1
    t2
  OtherRelation

转成```sql
UNION_ALL
JOIN
t1
OtherRelation
JOIN
t2
OtherRelation

需要注意的是，转换之前，UNION_ALL 不能出现在 LEFT JOIN 的右边，不能出现在 RIGHT JOIN 的左边，否则这条规则不适用； |  | 未实现 |
| LoptOptimizeJoinRule | 基于启发式算法的 join reordering 优化规则 |  | 未实现 |
| LoptSemiJoinOptimizer | semi join 优化，确定最佳的 semi join 位置 |  | 未实现 |
| MatchRule | 把一个 Match 转换成 LogicalMatch；MATCH 算子是带正则表达式过滤以及聚合语义的算子，参考 [https://docs.snowflake.com/en/sql-reference/constructs/match_recognize.html](https://docs.snowflake.com/en/sql-reference/constructs/match_recognize.html) |  | 不需要实现 |
| MaterializedViewFilterScanRule | 把 table scan + filter 变成 materializeview + filter |  | 不需要实现 |
| MultiJoinOptimizeBushyRule | 把 MultiJoin 转换成一棵 bushy tree；与 LoptOptimizeJoinRule 不同的是，LoptOptimizeJoinRule 只能生成左深树 ，而这个规则可以生成 bushy tree |  | 未实现 |
| MultiJoinProjectTransposeRule | 把 MultiJoin 上方，以及 LogicalJoin 下方的 Project 往上提 |  | 不需要实现 |
| ProjectAggregateMergeRule | 在 Aggregate -> Project 这种 pattern 中，通过 project 把 Aggregate 中不需要的 aggr expr 消除掉 | IMCI 没有 project 这个算子；但是可以左类似的表达式消除的事情； | 未实现 |
| ProjectCalcMergeRule | 把 Project 和 LogicalCal 合并成 LogicalCal | 类似于把两个 ComputeScalar 合并成一个（i.e., CalcMergeRule） | 不需要实现 |
| ProjectCorrelateTransposeRule | 把 project 推到 correlated join 下方；解关联相关； |  | 不需要实现 |
| ProjectFilterTransposeRule | 把 project 推到 filter 下方 | 类似于在 filter 前提前做列裁剪了 | 不需要实现 |
| ProjectJoinJoinRemoveRule | 类似于 AggregateJoinJoinRemoveRule；不过，要求 join keys 是 unique columns |  | 未实现 |
| ProjectJoinRemoveRule | 类似于 AggregateJoinRemoveRule; 不过，要求 join keys 是 unique columns |  | 未实现 |
| ProjectJoinTransposeRule | 把 project 推到 join 下面，下推后，project 一分为二，分别放在 join 的两个子节点的上方 |  | 未实现 |
| ProjectMergeRule | 将两个 project 合并 |  | 未实现 |
| ProjectMultiJoinMergeRule | 与 FilterMultiJoinMergeRule 类似，把一个 Project 跟一个 MultiJoin 合并到一起，产生一个“语义更丰富”的 MultiJoin，使得 join reorder 过程的选择会更多；Join reorder 相关 |  | 未实现 |
| ProjectRemoveRule | 把无用的 project 消除 |  | 未实现 |
| ProjectSetOpTransposeRule | 把 project 下推到 set 的下方 |  | 不需要实现 |
| ProjectTableScanRule | 把一个 tablescan + project 变成 Bindables.BindableTableScan. |  | 不需要实现 |
| ProjectToCalcRule | 把一个 project 转换成 LogicalCalc |  | 不需要实现 |
| ProjectToWindowRule | 把一个 project 切分成 window + logicalcalc  |  | 不需要实现 |
| ProjectWindowTransposeRule | 把 project 推到 window 下方 |  | 不需要实现 |
| PruneEmptyRules | 消除那些永远不产生结果的 relation（在 calcite 里面就是一个不产生结果的 Values 算子） |  | 不需要实现 |
| ReduceDecimalsRule | 把 decimal 操作归约到 primitive type（比如 int） | IMCI 可以通过 implicit cast 实现 | 未实现 |
| ReduceExpressionsRule | 表达式简化；这是很多 rule 的集合，分别有 filter expression reduction，project expression reduction, join expression reduction |  | 未实现 |
| SemiJoinFilterTransposeRule | 把 semi join 推到 filter 下方，如
SemiJoin(LogicalFilter(X), Y) → LogicalFilter(SemiJoin(X, Y))
下推后，其他规则可以适用于这个 pattern |  | 未实现 |
| SemiJoinJoinTransposeRule | 把 semi join 下推到另一个 join 下方，如
1. SemiJoin(LogicalJoin(X, Y), Z) → LogicalJoin(SemiJoin(X, Z), Y)
2. SemiJoin(LogicalJoin(X, Y), Z) → LogicalJoin(X, SemiJoin(Y, Z))

下推后，其他规则可以适用于这个 pattern。至于选择 1 还是 2，得看原始的 semi join 里面，到底是  X 还是 Y 与 Z 进行 semi join。 |  | 未实现 |
| SemiJoinProjectTransposeRule | 把一个 semi join 下推到 project 下方，如：
SemiJoin(LogicalProject(X), Y) → LogicalProject(SemiJoin(X, Y))
下推后，其他规则可以适用于这个 pattern。 |  | 未实现 |
| SemiJoinRemoveRule | 消除无用的 semi join  |  | 未实现 |
| SemiJoinRuleSemiJoinRule | 把 Aggregate -> Join 这样的组合转换成一个 semi join |  | 未实现 |
| SortJoinCopyRule | 把 join 上方的 sort 拷贝到下方（不带 offset 和 limit），原始的 sort 被保留 |  | 未实现 |
| SortJoinTransposeRule | 把 sort 推到 join 下方 |  | 未实现 |
| SortProjectTransposeRule | 把 Sort 推到 project 下方  |  | 未实现 |
| SortRemoveConstantKeysRule | 把 sort 里面的常量 sort key （比如常量数字，或者通过推导得出的常量 key）消除；如果所有 key 都消除了，则这个 Sort 被移除； |  | 未实现 |
| SortRemoveRule | 如果输入数据已经是有序的了，就把这个 Sort 消除； | mysql 应该做了一些相关的事；IMCI 有 RemoveOrderbyInSubquery，但是跟这个规则不是一个东西； | 未实现 |
| SortUnionTransposeRule | 把一个 Sort 推到 Union 下方 |  | 未实现 |
| SpatialRules | 处理 spatial expression 的一系列规则的集合；空间数据处理相关； |  | 不需要实现 |
| SubQueryRemoveRule | 把 subquery 用 join 表示 | IMCI 有下同的 SubqueryToJoin 规则 | 已实现 |
| SubstitutionRule | 这是一个 interface；所谓的 substitution rule，就是那种转换了一定比不转换的要好的那种规则，比如 filter pushdown；calcite 里面的 substitution rule 包括：
1. AggregateRemoveRule
2. AggregateValuesRule
3. CalcRemoveRule
4. ExchangeRemoveConstantKeyRule
5. FilterMergeRule
6. ProjectJoinJoinRemoveRule
7. ProjectJoinRemoveRule
8. ProjectRemoveRule
9. PruneEmptyRules
10. ReduceExpressionsRule
11. SortRemoveConstantKeysRule
12. UnionEliminatorRule
 | IMCI 不需要实现，但是这种“接口”可是实现成规则的某种属性； | 不需要实现 |
| TransformationRule | 所有 logical transformation rule 的 interface | IMCI 不需要实现，但是这种“接口”可是实现成规则的某种属性； | 不需要实现 |
| UnionEliminatorRule | 当 UNION 只有一个输入的时候，消除这个 union |  | 未实现 |
| UnionMergeRule | 用来将两个none-distinct 的 Set 操作合并成一个（因为最初始的时候是给 UNION 写的，所以取了这么个名字）；同时也适用于 Intersect 和 Minus 操作； | 
 | 未实现 |
| UnionPullUpConstantsRule | 把 Union 下方的 constant expression 往上提 |  | 未实现 |
| UnionToDistinctRule | 把一个 distinct union 实现成一个 Aggregate + none-distinct union | IMCI 目前就是这么实现 distinct union 的 | 不需要实现 |
| ValuesReduceRule | 把 Project 和 Filter 消除掉，直接利用下层的 Values 算子；

Values 算子是 calcite 里面的一种表现方式，用于实现在 select 语句中直接写一堆 constant 而组成一个“临时表”，比如：```sql
select a - b from (
  values (1, 2), (3, 5), (7, 11)
) as t (a, b)
where a + b > 4

通过这个规则，可以消除变成：```sql
select x from (values (-2), (-4))

Note:
- 如果 Values 是空的，则可以通过 PruneEmptyRules 进行消除，而不需要利用这条规则。
 | mysql 没有这种语法，所以应该不需要支持 Values 这种算子 | 不需要实现 |


## Calcite 的 physical implementation rules
实际上在 calcite 框架里面，对一个 logical relation 的 implementation 统一用 EnumerableRel 这个 interface，生成不同 EnumerableRel 的规则都是某种 ConverterRule；
（其实现位于 core/src/main/java/org/apache/calcite/adapter/enumerable/ 目录下）

因为一般的 logical relation 的实现就那么几种，比如 join 的实现，也就 hash join / sort merge join / nested loop join，index join 等几种，所以这里就不详细描述了。

## 利用 Calcite 优化 & 实现 MPP 计划
calcite 本身只是一个 query processing 的框架，可以看作一个可扩展的优化器框架，本身跟 MPP 没什么关系；不过由于 MPP 的执行计划只是一般执行计划的扩展，i.e., 加一个 Exchange 算子、带 distribution 属性、带 sort 属性，（可以参考《[IMCI 执行器的 MPP 扩展](https://yuque.antfin-inc.com/nituizi/oncxfu/twafbq)》），因此一个 query engine 可以利用 calcite 框架来生成一个 MPP 的执行计划。具体方法是：

1. 按照 Calcite 的接口增加 logical transformation rules （i.e., 上文的 logical transformation rules）
2. 增加不同的 logical relation 的 implementation，i.e., 上文说的 EnumerableRel ，以及生成这种 EnumerableRel 的 ConverterRule；
3. 提供不同 implemenation 的 cost

可以参考 POLAR-X 的实现，代码仓库 [https://github.com/ApsaraDB/galaxysql](https://github.com/ApsaraDB/galaxysql)；MPP 相关规则位于
polardbx-optimizer/src/main/java/com/alibaba/polardbx/optimizer/core/planner/rule/mpp/ 目录下；

## Calcite 的统计信息 & cost model
统计信息可以在优化器优化的过程中提供辅助，帮助优化器选择出代价（cost）最小的执行计划。具体的逻辑是，**给定一个执行计划，对于其中的每一个算子，优化器的 cost model 可以根据统计信息提供的 selectivity、range、number of distinct value 等信息，预估出这个算子的 cost，从而算出整个执行计划的 cost**；对比不同执行计划的 cost，就可以选出 cost 最小的执行计划了。

Calcite 的统计信息框架实现在  core/src/main/java/org/apache/calcite/rel/metadata/ 目录下；Calcite 内部把这些**统计信息称为 metadata**；同时为了支持不同的系统，calcite 的统计信息接口做成了可插拔式的：可以增加不同的 metadata；也可以自定义 metadata provider 以重载默认的 metadata 接口。**需要注意的是，获取一个算子的 cost 的接口，也在这套框架内**（e.g., 后文的 RelOptCost getNonCumulativeCost(RelNode rel) 接口），但是 cost model 的定义，是定义在每个算子内部的。

### 统计信息（i.e., METADATA)
这里主要描述默认的 metadata（i.e., builtin metadata）的接口及其实现。
#### 默认的 METADATA 定义
默认的 'BuiltInMetadata' 类主要提供如下几种类型的统计信息（metadata）：

| 名称 | 含义 | 默认实现类 |
| --- | --- | --- |
| Selectivity | Metadata about the selectivity of a predicate | RelMdSelectivity |
| UniqueKeys | Metadata about which combinations of columns are unique identifiers | RelMdUniqueKeys |
| ColumnUniqueness | Metadata about whether a set of columns uniquely identifies a row | RelMdColumnUniqueness |
| Collation | Metadata about which columns are sorted | RelMdCollation |
| Distribution | Metadata about how a relational expression is distributed | RelMdDistribution |
| NodeTypes | Metadata about the node types in a relational expression | RelMdNodeTypes |
| RowCount | Metadata about the number of rows returned by a relational expression | RelMdRowCount |
| MaxRowCount | Metadata about the maximum number of rows returned by a relational expression | RelMdMaxRowCount |
| MinRowCount | Metadata about the minimum number of rows returned by a relational expression | RelMdMinRowCount |
| DistinctRowCount | Metadata about the number of distinct rows returned by a set of columns in a relational expression | RelMdDistinctRowCount |
| PercentageOriginalRows | Metadata about the proportion of original rows that remain in a relational expression | RelMdPercentageOriginalRows
（这个类实现了三种 metadata） |
| PopulationSize | Metadata about the number of distinct values in the original source of a  column or set of columns | RelMdPopulationSize |
| Size | Metadata about the size of rows and columns | RelMdSize |
| ColumnOrigin | Metadata about the origins of columns | RelMdColumnOrigins |
| ExpressionLineage | Metadata about the origins of expressions | RelMdExpressionLineage |
| TableReferences | Metadata to obtain references to tables used by a given expression | RelMdTableReferences |
| CumulativeCost | Metadata about the cost of evaluating a relational expression, including all of its inputs | RelMdPercentageOriginalRows
（这个类实现了三种 metadata） |
| NonCumulativeCost | Metadata about the cost of evaluating a relational expression, not including its inputs | RelMdPercentageOriginalRows
（这个类实现了三种 metadata） |
| ExplainVisibility | Metadata about whether a relational expression should appear in a plan | RelMdExplainVisibility |
| Predicates | Metadata about the predicates that hold in the rows emitted from a relational expression | RelMdPredicates |
| AllPredicates | Metadata about the predicates that hold in the rows emitted from a relational expression. | RelMdAllPredicates |
| Parallelism | Metadata about the degree of parallelism of a relational expression, and how its operators are assigned to processes with independent resource pools | RelMdParallelism |
| LowerBoundCost | Metadata to get the lower bound cost of a RelNode | RelMdLowerBoundCost |
| Memory | Metadata about the memory use of an operator | RelMdMemory |

（Note: 上面的每一种 metadata 虽然都 extends Metadata 这个 common interface，但是都有自己的接口；用同一个接口是无法统一这么多种类的 metadata 的）

可以看出，这上面很多信息都**已经不属于“统计信息”的范畴**，比如 CumulativeCost（i.e., 执行某个算子的代价）、TableReferences（i.e., 某个 relation 涉及到的表），而更像是“information about a relation  or expression”；Calcite 用“metadata”把这些都封装到一个模块里，一方面可以使得其他模块的接口变得简洁，另一方面也是因为做成可插拔式的框架（i.e., 只有封装到一个模块里面，才可以方便提供 customized metadata provider），因此从这个角度而言，整体的逻辑稍微有点绕。

#### Example: Selectivity
下面展示 Selectivity 这种 metadata。
Selectivity 顾名思义就是给定一个 relatation，当应用某个 predicate 时，这个 "predicate" 的选择率是多少。在RelMdSelectivity 这个类里面，定义了针对不同算子的 getSelectivity() 接口：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639301120962-5a3b355a-dec4-4a58-ba02-fb0f4c96e7e5.png#clientId=u3106a387-5999-4&from=paste&height=287&id=u1eb1d1b1&originHeight=287&originWidth=586&originalType=binary&ratio=1&rotation=0&showTitle=false&size=28345&status=done&style=none&taskId=u3ef1f77b-1e75-4132-92a5-8dffb3b5365&title=&width=586)
显然，predicate 只有在 Filter / Join / table scan 这些算子才会有“过滤”的作用，因此才有“选择率”可言。因此大多数的 getSelectivity() 都是往下调用 child relation 的 getSelectivity()，最终默认走到“默认”的 getSelectivity() 接口：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639301451887-0135fa67-55aa-445b-9194-a066e669d7b0.png#clientId=u3106a387-5999-4&from=paste&height=152&id=u3bf83d29&originHeight=152&originWidth=606&originalType=binary&ratio=1&rotation=0&showTitle=false&size=19373&status=done&style=none&taskId=u9b7b457d-f5e1-4206-af45-b11374d0b6a&title=&width=606)
而 RelMdUtil::guessSelectivity(predicate) 的实现则非常地“heuristic”：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639301520146-d86871a4-d340-4d0e-94c0-45f86131043b.png#clientId=u3106a387-5999-4&from=paste&height=735&id=u3df91fbb&originHeight=735&originWidth=525&originalType=binary&ratio=1&rotation=0&showTitle=false&size=78436&status=done&style=none&taskId=u7246bf98-0eb2-4ce6-80c1-1598a55382c&title=&width=525)
不过基本上大多数的数据库实现都是这样的，在没有精准的统计信息时，只能依靠这种估算的方式（可以参考 《Access Path Selection In a Relation Database Management System》这篇文章）。Calcite 作为一个不带存储的 query processing 框架，在没有存储提供的统计信息前提下，只能以这种方式去估算。

#### Example: RowCount
下面展示 RowCount 这种 metadata
RowCount 顾名思义就是一个算子的“输出结果的大小”，i.e., estimated cardinality；在 relational database 里面，所有的算子的输出都可以看作一张表，因此所有的算子都有一个 estimated cardinality：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639302135572-a8e50849-7aea-49a0-a63c-9b5812704e4e.png#clientId=u3106a387-5999-4&from=paste&height=414&id=u68b10c0a&originHeight=414&originWidth=567&originalType=binary&ratio=1&rotation=0&showTitle=false&size=42481&status=done&style=none&taskId=u8327d0b6-a73c-4dbc-b8df-3472181e06f&title=&width=567)
默认的实现，则是调用**每个算子内部的 estimateRowCount() **接口：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639302182274-91eab98b-047c-4440-a39f-f4e62718174a.png#clientId=u3106a387-5999-4&from=paste&height=86&id=u1b3d3480&originHeight=86&originWidth=653&originalType=binary&ratio=1&rotation=0&showTitle=false&size=11131&status=done&style=none&taskId=u614f6feb-a484-4158-b6e9-56f6b992f9b&title=&width=653)
默认的 JOIN 算子的 getRowCount()，则同样是靠猜的启发式方法：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639302244674-4d58bcab-ffe4-4b69-9694-5aa04a979cc7.png#clientId=u3106a387-5999-4&from=paste&height=85&id=ub235d03f&originHeight=85&originWidth=679&originalType=binary&ratio=1&rotation=0&showTitle=false&size=13128&status=done&style=none&taskId=u03006e3c-28e0-46f2-ac82-229621c70ed&title=&width=679)
其核心逻辑同样实现在 RelMdUtil 这个类中：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639302343018-6a276244-af28-468f-bedd-05b9b31c408f.png#clientId=u3106a387-5999-4&from=paste&height=815&id=ud58e031e&originHeight=815&originWidth=789&originalType=binary&ratio=1&rotation=0&showTitle=false&size=116733&status=done&style=none&taskId=u932bb2db-462d-4634-bcd5-df00fe37150&title=&width=789)
比如 INNER JOIN，则是用 selectivity 乘以左右表的 row count。可以看出，这种默认的计算方法，也是一种启发式的计算方法，如果有存储提供的准确的统计信息，可能就是另外一种计算方法了。

### COST MODEL
在优化器里面，cost model 是一个泛称，而未必是一个独立的模块。cost model 的核心作用是：**在特定的统计信息辅助下，给定一个算子，输出他的运行代价（i.e., cost）**；为了实现这个目的，得解决两个问题：

1. 如何表示 cost
2. 如果定义每个算子的 cost

#### 如何表示 COST


在 Calcite 里面，所有的 cost 都继承自 RelOptCost 这个类，其中 Volcano planner 的 cost 使用 VolcanoCost 表示，默认只包含 CPU、IO、ROWCOUNT 三个要素：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639302896787-8ee9f86f-55df-4dc6-89f6-7574e7f7fd16.png#clientId=u3106a387-5999-4&from=paste&height=304&id=ub46aaf72&originHeight=304&originWidth=663&originalType=binary&ratio=1&rotation=0&showTitle=false&size=23557&status=done&style=none&taskId=u03ae5521-54e4-4452-803e-d33e9f56d91&title=&width=663)
换言之，一个算子的 CPU、IO、ROWCOUNT 越大，则他的“运行代价”越大。

#### 如何计算每个算子的 COST


Cacite 是通过 RelMdLowerBoundCost 、RelMdPercentageOriginalRows 这两个 metadata 类提供的接口来获取每个算子的 cost 值的，但是具体的 cost 计算放在每个算子中（i.e., 最终都绕回到每个具体的算子的实现里面）。

比如 Filter 这个算子的 cost：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639303365476-06e4dda9-700f-4e33-98b9-d301d1d859ad.png#clientId=u3106a387-5999-4&from=paste&height=159&id=u74555801&originHeight=159&originWidth=660&originalType=binary&ratio=1&rotation=0&showTitle=false&size=24581&status=done&style=none&taskId=u06977e76-7eb6-4f4d-af58-dd7f930cb66&title=&width=660)
根据 cost 的定义，他的不同方面的 cost：

1. CPU：输入数据的量；因为 filter 主要的工作是对输入数据进行过滤，因此其主要的 CPU 耗费就跟输入数据量成正比；
2. IO：没有 IO，因此 IO 方面的 cost 为 0；
3. ROWCOUNT: 即其输出的结果集大小

比如 Sort 这个算子的 cost，就稍微复杂一点，但是基本上就是上述三个方面的结合：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639303762429-20a2956a-500f-4c17-8062-a3c6825b0c04.png#clientId=u3106a387-5999-4&from=paste&height=741&id=u515d5915&originHeight=741&originWidth=706&originalType=binary&ratio=1&rotation=0&showTitle=false&size=115358&status=done&style=none&taskId=ua8cb7525-9801-4180-b776-28ceb12e8fd&title=&width=706)

比如 JOIN 这个算子的 cost：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639304366825-e4bb5605-7c7a-42a0-9cfa-730aedf90044.png#clientId=u3106a387-5999-4&from=paste&height=170&id=ueedba9ec&originHeight=170&originWidth=714&originalType=binary&ratio=1&rotation=0&showTitle=false&size=26310&status=done&style=none&taskId=uca545a62-e001-40dd-8180-44a1ddba569&title=&width=714)

需要注意的是，这些只是 logical relation 的 cost，作为一种默认的 cost 提供；**实际上，对于一个完整的 query engine 来说，应该使用 physical relation 的 cost 来得到最终的 cost**，i.e., 在 physical implementation 这个过程之后，得到了具体的 physical relation（e.g., 到底用 hash join 还是 nested loop join），再计算出 cost。

不同的 physical relation 的 cost 需要另外定义，比如 Calcite 内部的 InnodbSort （应该是使用 innodb 的 sort 作为 sort 的一种具体实现），它的 cost 的定义就是默认的 sort 定义上再乘以一个系数：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639304331215-da5b92a6-6f1c-40be-94a2-29d8390852ff.png#clientId=u3106a387-5999-4&from=paste&height=387&id=u3ab5f38e&originHeight=387&originWidth=686&originalType=binary&ratio=1&rotation=0&showTitle=false&size=48930&status=done&style=none&taskId=u57e4ad11-8d59-4be1-add8-1082688e84d&title=&width=686)
比如 calcite 内部的 EnumerableHashJoin （默认用来表示 hash join 的 physical relation），它的 cost 计算就比上面的 logical join 要精细很多：
![image.png](https://intranetproxy.alipay.com/skylark/lark/0/2021/png/136668/1639304580080-75cbe0a3-ab0c-458b-83c2-469c308946df.png#clientId=u376b6fe8-38bf-4&from=paste&height=852&id=udf1b418d&originHeight=852&originWidth=759&originalType=binary&ratio=1&rotation=0&showTitle=false&size=97064&status=done&style=none&taskId=ue3cd7a85-a130-4aec-a8d0-21e42fd5d75&title=&width=759)

## JOIN REORDER 算法
Calcite 的 volcano planner 的 join reorder 算法主要实现在 LoptOptimizeJoinRule、LoptSemiJoinOptimizer 和 MultiJoinOptimizeBushyRule 三个规则中。我们放到 [https://yuque.antfin-inc.com/nituizi/oncxfu/evck9r](https://yuque.antfin-inc.com/nituizi/oncxfu/evck9r) 统一描述。

polardb

「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」

关注作者

Calcite 的优化器实现

CASCADE-STYLE OPTIMIZER

原理

数据结构

实现

Calcite 的 TopDown Volcano planner

Calcite 的 logical transformation rules

评论