FlinkSql之CalciteVolcano优化器（源码解析）

Calcite作为⼤数据领域最常⽤的SQL解析引擎，⽀持Flink , hive, kylin , druid等⼤型项⽬的sql解析同时想要深⼊研究Flink sql源码的话calcite也是必备技能之⼀，⾮常值得学习

我们内部也通过它在做⾃研的sql引擎，通过⼀套sql⽀持关联查询任意多个异构数据源（eg : mysql表join上 hbase表在做⼀个聚合计算）

因为calcite功能⽐较多，本⽂主要还是从calcite重要的主流程源码⼊⼿，主要侧重在VolcanoPlanner的优化器上梳理⼀下Calcite SQL执⾏的⼏个阶段

总结下来就是

1. 通过Parser解析器将传⼊的sql解析成⼀颗词法树，SqlNode作为树的节点2. 做词法的校验Validate，类型校验，元数据校验等等

3. 将校验好的SqlNode树转换成对应的关系代数表达式，也是⼀颗树，RelNode作为节点

4. 将RelNode关系代数表达式树，通过内置的两种优化器Volcano , Hep 优化关系代数表达式得到最优逻辑代数的⼀颗树，也是RelNode

5. 最优的逻辑代数表达式（RelNode）,会被转换成对应的可执⾏的物理执⾏计划（转换逻辑根据框架有所不同），像Flink就转成他的Operator去运⾏

来详细的看下每个阶段

1. Sql语句解析成语法树阶段（SQL - > SqlNode）

这⼀个阶段其实不是calcite实现的，⽽是calcite⾃⼰定义了⼀套sql语法分析规则模板，通过javaCC这个框架去实现的拉代码来看下

源码中那个Parser.jj就是calcite核⼼的语法模板了，⽐如说我们要为flink sql添加什么语法⽐如count window就要修改这⾥

其中定义了是什么sql token 如何返回sqlNode的具体逻辑

看个例⼦

\"select ID,NAME from MYHBASE.MYHBASE where ID = '1' \"就会被解析成这样⼀颗sqlNode树

这⾥就不赘述了，javacc 可以参考官⽹（https://javacc.github.io/javacc/）

2 . 语法校验validator阶段

这⾥通过校验器去校验，这⾥不展开了，不是重点

3. 将sqlNode转成relNode的逻辑表达式树（sqlNode - > relNode）

这⾥calcite有默认的sql2rel转换器org.apache.calcite.sql2rel.SqlToRelConverter这⾥也先不展开了

4. 逻辑关系代数树优化（relNode - > relNode）

这⾥是中重点中的重点！！！为什么有那么多框架选择Calcite就是因为它的sql优化

通过3阶段我们得到了⼀个relNode树，但这⾥这颗树并不是最优解，⽽calcite通过⾃⾝的两种优化器planner得到⼀个优化后的best树

这⾥才是整个calcite的核⼼，calcite提供的两种优化器

HepPlanner规则优化器（简单理解为定义许多规则Rule，只要能符合优化规则的树节点的就按规则转换，得到⼀颗规则优化后的树，这个⽐较简单）

VolcanPanner代价优化器（基于代价cost，树会根据rule⼀直迭代,不停计算更新root relnode节点的代价值，来找到最优的树）先来看下

select ID,NAME from a where ID = '1' 这样sql转换⽽来的⼀颗RelNode树长什么样⼦

可以看到很多节点都是以Logical命名的，因为这是3阶段通过calcite默认的转化器（SqlToRelConverter）转换⽽来的逻辑节点，逻辑节点是没有物理属性的也⽆法运⾏的

接下来进⼊calcite的代价cost优化器VolcanoPlanner进⾏优化

返回的就是代价最优的解进去calcite的optimize⽅法

⾸先calcite会将我们上⼀阶段得到的relNode设置到我们代价Volcano优化器的root⾥去在其中 org.apache.calcite.plan.volcano.VolcanoPlanner.registerImpl() ⽅法中

断点的地⽅在register的过程中会先将relnode的input先注册在ensureRestered⽅法中

可以看到有绕回了registerImpl()⽅法也就是树的⼦节点深度遍历先注册接下来看⼀下注册过程

既然是深度遍历回到刚才看的VolcanoPlanner.registerImpl()⽅法中看下onRegister()⽅法之后做了什么

可以看到要触发规则了，这⾥就要穿插⼀个概念，calcite中的Rule

从类描述中我们可以知道，规则可以将⼀个表达式转换成另⼀个，什么意思呢，来看下有哪些抽象⽅法

什么意思呢？归纳起来就是两个核⼼⽅法

matches（）返回当前的relnode是否能匹配上此规则rule

onMatch () 当匹配上此规则时，这个⽅法会被调⽤，在其中可以调⽤transformTo()⽅法，这个⽅法的作⽤就是将⼀个relNode转换成另⼀个relNode

规则就是整个calcite的核⼼了，其实所有的sql优化都是由对应的rule组成的，将sql的优化逻辑实现为对应的rule让对应的relNode树节点做对应的转换来得到最优的best执⾏计划

ok回到我们的主流程上，继续上⾯的volcanoPlanner.fireRule()⽅法看看如何触发规则的

这⾥逻辑是⽐较简单的，就是当relnode满⾜rule就调⽤volcanoRuleCall的match()⽅法

但是有个地⽅需要注意，这⾥的classOperands这⾥包含了relNode以及所有可能匹配上这个relnode的规则的映射关系，并且可以向上也可以向下具体是什么意思呢？

假设我有⼀个LogicFilter的RelNode，然后定义了两个规则RuleA

operand(Logicalfilter.class, operand(TableScan.class))RuleB

operand(Logicalproject.class, operand(Logicalfilter.class))

那这两个rule都会进⼊这个可能匹配上的映射关系classOperands⾥⾯去当匹配上rule以后，接着来继续看代码

然后⾛到了volcanoPlanner.DeferringRuleCall的onMatch中

这⾥就是把这个rule的加⼊到了IterativeRuleDriver中的ruleQueue，这个队列就是专门⽤来存放已经匹配上的rule的，不难发现这些匹配上的rule只是存在队列⾥⾯，但还没有执⾏这些规则

那多久会执⾏呢？

回到主流程当我们setRoot⾥的所有relnode⼦节点都register以后

会⾛具体planner的findBestExp()⽅法，从名字可以看出来找到最优的表达式

这⾥要提前说⼀下，claicte的优化原理是，它假定如果⼀个表达式最优，那它的局部也是最优的，那当前relNode的best我们也就只⽤关⼼，从1.⼦节点的所有best加起来

2. ⾃⼰能匹配上的所有规则，以及剩下部位的best加起来从中⽐较得到的就是当前relnode的最优解了引⽤个图

如果A只能匹配这两种规则，那我们枚举求最优解的时候就只⽤考虑这⼏张情况

关于原理不太了解的可以看看这篇 https://io-meter.com/2018/11/01/sql-query-optimization-volcano/ 接着看findBestexp()

这⾥就是整个优化寻找最优解bestExp的主loop了

不停的从queue中拿rule, 运⾏rule,直到所有rule都执⾏完才退出

没错这⾥的这个queue就是前⾯说到的，当默认的relnode注册进来的时候会把能匹配上的rule放这queue⾥⾯去这⾥⾃然就有个疑问， 前⾯说到rule运⾏的时候会改变relNode节点，也就是添加relndoe的等价节点，

那这⾥树的结构变化会导致，之前不能匹配上的rule改变树的结构后就能匹配上，那这⾥能匹配上的rule不就漏了，那就接着看rule的onMatch()中⽤于转换等价节点的⽅法transformTo（）

其中转换的新节点，在transformTo⽅法中⼜会执⾏register

也就是说新来的节点也会⾛⼀遍，默认relNode注册的流程，当新节点注册成等价节点会有新的规则匹配上的时候，⼜会将此rule加⼊rulequeu

中等待下⼀次执⾏rule了

另外当这个relnode节点会被规则rule转换时,⽣成的新relnode会被设置加⼊到这个relnode的等价节点中去

加⼊等价节点，并且在propagateCostImprovement⽅法中

计算当前等价节点会不会使，当前relnode的cost代价下降，如果下降了，那就更新当前relnode的bestcost并且向上冒泡修改⽗relnode的最优

bestCost

while true ⼀直触发拉取ruleQueue中的rule,直到rule为空然后rule会添加新的等价节点

新的等价节点如果更优cost,更新整棵树的best Relnode

新的等价节点relnode会匹配上新的规则，新的rule加⼊到rulequeue中

进⼊下⼀次循环，直到没有rule可以匹配上，这样bestexp就可以返回优化后的最优的relnode了

之后就是根据这个最优的relnode,不同的框架翻译成⾃⼰的apicalciet终于说完，，之后就可以开始解析flink sql的源码了