Calcite 规则匹配

Calcite 支持定义自定义规则，这些规则是如何在优化过程中高效匹配的呢？

为了支持规则的高效匹配，在定义规则时 Calcite 只支持我们明确的依据 RelNode 的 inputs 和 traits 来定义，不支持使用通配符来匹配中间节点。所以定义的匹配规则要想被匹配到，那么一定是优化过程中出现了与之匹配的结构。多说一点，Calcite 并没有限制说 RelNode 的 convention 必须要和 inputs 的 convention 相匹配，例如 ProjectTableScanRule 匹配完成后，就会出现 NONE 的节点依赖 BINDABLE 的节点的结构。如果你的规则对 inputs 的 convention 有要求，那么需要显示的调用 RelOptPlanner 的 changeTraits 方法来修改对应节点的 traits，实现上，Calcite 并不会实际去修改节点的 traits，只是去看节点所属的 RelSet 有没有符合目标 traits 的 RelSubset，如果有就直接返回对应的 RelSubset，没有就创建一个对应 traits 的 RelSubset，例如 EnumerableProjectRule 就会修改 inputs 的特征。总结，规则匹配转换过程中匹配是严格匹配，节点和 inputs 的 convention 允许不一样，inputs 可以是 RelSubset。

VolcanoPlanner 会记录所有注册的 Rule 和当前所有节点的类型，分别记录在 mapDescToRule 和 classes 属性里。每当有新的 Rule 注册（调用 VolcanoPlanner#addRule），删除（调用 VolcanoPlanner#removeRule）和新的类型的 RelNode 被添加进来（VolcanoPlanner#onNewClass），VolcanoPlanner 会维护更新 classOperands 属性，里面记录了节点类型和与之相关的 RelOptRuleOperand。RelOptRuleOperand 是什么呢？RelOptRuleOperand 是 Calcite 基于我们定义的规则的 RelRule.Config 生成的一个树形结构（对目标 RelNode 结构的一种描述），一个 RelRule.Config 会对应一组 RelOptRuleOperand，这些 RelOptRuleOperand 之间以树的形式关联起来。每个 RelOptRuleOperand 都有一个解析顺序的属性solveOrder（解析顺序是基于 RelOptRuleOperand 在树中的位置确定的，从自己开始先冒泡到根节点，然后再按照先根的深度优先顺序遍历），每当一个节点添加到 VolcanoPlanner 中，框架会找到节点类型对应的 RelOptRuleOperand，然后基于解析顺序，递归的检查节点的 parents 和 inputs 是否满足 RelOptRuleOperand 所属树结构的其他 RelOptRuleOperand 的定义，如果满足就会把对应规则添加到 RuleQueue 中，相关代码入口在 VolcanoPlanner#fireRules里。这里用到一个 DeferringRuleCall 的类，他存在的意义就是在规则匹配以后不立刻触发规则，而是把规则添加到 RuleQueue 里。