前言

笔者近日在做一个基于 Calcite 的自定义 SQL 解析框架，须要理解 Calcite，但因为当初网上 Calcite 材料极少，有价值的更是寥寥无几，因而只能本人 debug 源码。Calcite 是一个比较复杂的框架，因而本篇内容集中在当中的一个小但重要的阶段：SQL 优化。
限于篇幅，本篇只谈 HepPlanner 的优化流程，有任何问题欢送评论交换。

HepPlanner

HepPlanner 是一个启发式的优化器，基于非常简单的思维：即遍历匹配 RelOptRule 和 RelNode，匹配胜利则进行优化。HepPlanner 的优化流程大体能够分为两步：

1. 初始化 HepPlanner；

2. 调用 HepPlanner 的 findBestExp() 执行真正的优化流程，而优化流程也是一个非常复杂的逻辑，能够细分为以下三步：

   1. 遍历：启动一个双层的 for 循环去遍历 RelOptRule 和 RelNode；
   2. 匹配：在遍历过程中对 RelOptRule 和 RelNode 尝试进行匹配；
   3. 优化：当匹配胜利后执行 RelOptRule 的 onMatch 进行优化。

初始化

初始化 HepPlanner 有两步十分重要：注入优化规定（RelOptRule）以及注入需优化的 RelNode root。

注入优化规定（RelOptRule）：HepPlanner 会将注入的 RelOptRule 包装成 HepInstruction，具体的类型为 HepInstruction.RuleInstance，在 HepPlanner 中，HepInstruction 才是执行单位。

注入需优化的 RelNode root：RelNode 是关系代数表达式的一种形象构造，因而与关系表达式类似是一种相似树的构造（组合模式的利用），HepPlanner 会依据这个特点将其转换成一个有向无环图 DirectedGraph，图上的每个节点都是一个 RelNode，但这个 RelNode 不是原来的 RelNode，而是 RelNode 的另一个实现类 HepRelVertex，HepRelVertex 有一个成员变量 currentRel 指向它包装的 RelNode。

遍历

HepPlanner 通过 findBestExp 进入到优化流程，其关键步骤有以下几步。

首先，HepPlanner 会进入第一层 for 循环，遍历所有 instructions（后面提到 RelOptRule 也被包装成 HepInstruction 存在 instructions 中），对每个 RelOptRule 尝试匹配所有的 RelNode（即 HepRelVertex）。

在 HepPlanner 中，RelNode 曾经被转成一个有向无环图 DirectedGraph，因而 HepPlanner 会先依据 DirectedGraph 生成一个 RelNode 汇合的迭代器，

private Iterator<HepRelVertex> getGraphIterator(HepRelVertex start) {collectGarbage();
    switch (currentProgram.matchOrder) {
    case ARBITRARY:
    case DEPTH_FIRST:
          return DepthFirstIterator.of(graph, start).iterator();
    case TOP_DOWN:
          assert start == root;
          return TopologicalOrderIterator.of(graph).iterator();
    case BOTTOM_UP:
    default:
          assert start == root;
          final List<HepRelVertex> list = new ArrayList<>();
          for (HepRelVertex vertex : TopologicalOrderIterator.of(graph)) {list.add(vertex);
          }
          Collections.reverse(list);
          return list.iterator();}
}

能够看到，迭代器的生成形式由一个类型为 HepMatchOrder 的参数 matchOrder 指定，该参数指定了四种生成规定：

• ARBITRARY
• DEPTH_FIRST
• TOP_DOWN
• BOTTOM_UP（default）

ARBITRARY 和 DEPTH_FIRST 应用的都是深度优先算法生成规定汇合，而 TOP_DOWN 和 BOTTOM_UP 则是基于拓扑排序，后者因为是自底向上，所以会有一个 reverse list 的过程。

失去 RelNode 汇合后，HepPlanner 开始进入第二层 for 循环，尝试匹配 RelOptRule 和 RelNode，

注：在优化过程每次批改了原先的 graph，须要从新调用 getGraphIterator 办法生成迭代器。如果 matchOrder 是 ARBITRARY || DEPTH_FIRST，则间接从优化新生成的 RelNode 开始遍历建设迭代器，否则则持续从 root 开始从新生成。

匹配

HepPlanner 在 applyRule 中实现了对于规定匹配和优化的逻辑。

private HepRelVertex applyRule(
    RelOptRule rule,
    HepRelVertex vertex,
    boolean forceConversions) {
        // 一些非凡状况解决，如 ConverterRule 的解决逻辑

        // 1. 进行 operand 匹配
        boolean match =
        matchOperands(rule.getOperand(),
            vertex.getCurrentRel(),
            bindings,
            nodeChildren);

    if (!match) {return null;}
        
        HepRuleCall call =
        new HepRuleCall(
            this,
            rule.getOperand(),
            bindings.toArray(new RelNode[0]),
            nodeChildren,
            parents);

    // 2. 进行 rule 匹配
    if (!rule.matches(call)) {return null;}

        // 3. 优化
        fireRule(call);

        // 4. 应用优化后新的 RelNode 替换原先老的 RelNode
        if (!call.getResults().isEmpty()) {
          return applyTransformationResults(
              vertex,
              call,
              parentTrait);
    }

    return null;
}

具体对于规定和关系表达式的匹配有两步：

1. 对 RelOptRule 里的 RelOptRuleOperand 尝试进行匹配；
2. 执行 RelOptRule 的 matches 办法。

RelOptRuleOperand

RelOptRuleOperand 则是用于判断某个 RelOptRule 是否与某个特定的关系表达式（RelNode）匹配胜利。RelOptOperand 的构造如下：

public class RelOptRuleOperand {
      //~ Instance fields --------------------------------------------------------

      private RelOptRuleOperand parent;
      private final ImmutableList<RelOptRuleOperand> children;
        public final RelOptRuleOperandChildPolicy childPolicy;

        private RelOptRule rule;
      private final Predicate<RelNode> predicate;
        private final Class<? extends RelNode> clazz;
        private final RelTrait trait;
      
        // TODO trait
        // ...
}

很显著这是 RelOptRuleOperand 也是一个树结构，依据不同的 Rule 它可能有子 operand 和 父 operand，须要递归进行匹配，childPolicy 决定了对子 operand 的匹配逻辑，在下面 HepPlanner 的 matchOprands 办法中就会针对 childPolicy 不同的值采取不同的匹配校验形式。

operand 执行匹配的具体方法是 matches，默认一共有三步校验：

public boolean matches(RelNode rel) {if (!clazz.isInstance(rel)) {return false;}
      if ((trait != null) && !rel.getTraitSet().contains(trait)) {return false;}
      return predicate.test(rel);
}

首先是 clazz，RelNode 必须是 clazz 或其子类生成的对象。

其次是 trait，该 RelNode 的特色中必须蕴含该 RelOptRuleOperand 的特色。

最初是 predicate，每个 RelOptRuleOperand 都有一个断言，RelNode 需通过该断言的校验。

RelOptRule

RelOptRule 是优化规定，通过其 onMatch 办法咱们能将一个关系表达式（RelNode）优化成另一个关系表达式。

RelOptRule 中有一个 RelOptRuleOperand 类型的成员 operand，保留了整个 RelOptRuleOperand 树的 root，在 matchOperands 办法中能够看出，RelOptRule 是否与某个特定的 RelNode 匹配胜利一部分由 RelOptRuleOperand 决定。当通过 RelOptRuleOperand 校验后，HepPlanner 会调用 RelOptRule 的 matches 办法进行第二次校验，matches 办法的默认实现是返回 true，但用户能够在实现自定义优化规定时增加自定义判断条件。

优化

优化流程也能够再细分为三步：

1. 利用 RelOptRule 的 onMatch 办法；
2. 调用 applyTransformationResults 将优化后的 RelNode 增加到图中，替换原先的 RelNode；
3. 应用 Mark-Sweep 算法革除过期的 RelNode 及相干数据。

onMatch

以 FilterIntoJoinRule 优化 SQL select * from product p join order o on p.id=o.id where p.id > 1 为例，FilterIntoJoinRule 的作用是通过谓词下推技术优化 filter 和 join 语句的程序。

FilterIntoJoinRule 的 onMatch 非常简单，取出了 Filter 和 Join，调用了 perform 办法尝试做谓词下推。

public void onMatch(RelOptRuleCall call) {Filter filter = call.rel(0);
      Join join = call.rel(1);
      perform(call, filter, join);
}

perform 的逻辑较为简单，这里只讲述要害流程：

1. 计算出 Filters，分为 4 局部：

   • aboveFilters：join 之上的 filters；
   • joinFilters：join 的 on filters；
   • leftFilters：join 左表的 filters；
   • rightFilters：join 右表的 filters；
2. 调用 RelOptUtil.classifyFilters 尝试将 aboveFilters 下推到 leftFilters 或 rightFilters 中（也可能两者兼有），在这一步会通过创立两个 bitmap，以计算偏移量的形式来断定应该将 aboveFilters 下推到哪里；
3. 利用跟 2 类似的逻辑尝试将 aboveFilters 下推到 joinFilters；
4. 构建新的 RelNode，从 leftFilters 和 rightFilters 向上构建，再新建一个 Join RelNode；
5. 将新建的 RelNode 放入 HepRuleCall，留待后续解决。

以下面的例子为例，尝试用 FilterIntoJoinRule 对该关系表达式进行优化，在遍历到 LogicFilter 时，满足匹配条件并触发了优化，失去了右图优化后的 RelNode 树，黄色局部示意优化过程中复用的 RelNode，而红色则是在优化过程中新生成的 RelNode。

applyTransformationResults

持续上述的例子，新生成的 RelNode root 为 LogicJoin，applyTransformationResults 所做的事即是将 LogicJoin 写进原先的 RelNode 树中（即替换掉 LogicFilter），并增加到 HepPlanner 的 graph 中（不便后续对 RelNode 进一步优化）。

这部分较清晰简略，是典型的对于树 / 图数据结构的解决。

1. 首先建设 LogicProject → LogicJoin 的连贯，这须要 批改 LogicProject 的 input 指向 LogicJoin，并增加 LogicProject → LogicJoin 的边。
2. 删除 LogicProject → LogicFilter 的边。

collectGarbage

在 applyTransformationResults 中，咱们曾经建设了新的 RelNode 树，但优化前的一些 RelNode 尽管和 RelNode 树断开了连贯，但仍存在于 HepPlanner 的 graph 中，这一步所做的就是清理这些无用的 RelNode。

private void collectGarbage() {
      // ...

        // mark
      final Set<HepRelVertex> rootSet = new HashSet<>();
      if (graph.vertexSet().contains(root)) {BreadthFirstIterator.reachable(rootSet, graph, root);
      }
    
        // ...
      final Set<HepRelVertex> sweepSet = new HashSet<>();
      for (HepRelVertex vertex : graph.vertexSet()) {if (!rootSet.contains(vertex)) {sweepSet.add(vertex);
                  RelNode rel = vertex.getCurrentRel();
                  notifyDiscard(rel);
            }
      }

      assert !sweepSet.isEmpty();
        // sweep
      graph.removeAllVertices(sweepSet);
    
      // ...
}

这里的革除是一个简略的 Mark-Sweep 算法的实现，通过宽度优先获取所有可达的节点，并革除残余不可达的节点。

目前从 Calcite 源码来看，在做 mark-sweep 时没有 clean edges。