1
2
3

select 10 + 30, users.name, users.age
from users join jobs on users.id= user.id
where users.age > 30 and jobs.id>10

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// org.apache.calcite.plan.hep.HepRelVertex
/**
 * note：HepRelVertex 将一个 RelNode 封装为一个 DAG 中的 vertex（DAG 代表整个 query expression）
 */
public class HepRelVertex extends AbstractRelNode {
  //~ Instance fields --------------------------------------------------------

  /**
   * Wrapped rel currently chosen for implementation of expression.
   */
  private RelNode currentRel;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

//org.apache.calcite.plan.hep.HepInstruction
/** Instruction that executes a given rule. */
//note: 执行指定 rule 的 Instruction
static class RuleInstance extends HepInstruction {
  /**
   * Description to look for, or null if rule specified explicitly.
   */
  String ruleDescription;

  /**
   * Explicitly specified rule, or rule looked up by planner from
   * description.
   * note：设置其 Rule
   */
  RelOptRule rule;

  void initialize(boolean clearCache) {
    if (!clearCache) {
      return;
    }

    if (ruleDescription != null) {
      // Look up anew each run.
      rule = null;
    }
  }

  void execute(HepPlanner planner) {
    planner.executeInstruction(this);
  }
}

1
2
3
4
5

HepProgramBuilder builder = new HepProgramBuilder();
builder.addRuleInstance(FilterJoinRule.FilterIntoJoinRule.FILTER_ON_JOIN); //note: 添加 rule
HepPlanner hepPlanner = new HepPlanner(builder.build());
hepPlanner.setRoot(relNode);
relNode = hepPlanner.findBestExp();

1
2
3
4
5
6
7

// org.apache.calcite.plan.hep.HepPlanner
public void setRoot(RelNode rel) {
  //note: 将 RelNode 转换为 DAG 表示
  root = addRelToGraph(rel);
  //note: 仅仅是在 trace 日志中输出 Graph 信息
  dumpGraph();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//org.apache.calcite.plan.hep.HepPlanner
//note: 根据 RelNode 构建一个 Graph
private HepRelVertex addRelToGraph(
    RelNode rel) {
  // Check if a transformation already produced a reference
  // to an existing vertex.
  //note: 检查这个 rel 是否在 graph 中转换了
  if (graph.vertexSet().contains(rel)) {
    return (HepRelVertex) rel;
  }

  // Recursively add children, replacing this rel's inputs
  // with corresponding child vertices.
  //note: 递归地增加子节点，使用子节点相关的 vertices 代替 rel 的 input
  final List<RelNode> inputs = rel.getInputs();
  final List<RelNode> newInputs = new ArrayList<>();
  for (RelNode input1 : inputs) {
    HepRelVertex childVertex = addRelToGraph(input1); //note: 递归进行转换
    newInputs.add(childVertex); //note: 每个 HepRelVertex 只记录其 Input
  }

  if (!Util.equalShallow(inputs, newInputs)) { //note: 不相等的情况下
    RelNode oldRel = rel;
    rel = rel.copy(rel.getTraitSet(), newInputs);
    onCopy(oldRel, rel);
  }
  // Compute digest first time we add to DAG,
  // otherwise can't get equivVertex for common sub-expression
  //note: 计算 relNode 的 digest
  //note: Digest 的意思是：
  //note: A short description of this relational expression's type, inputs, and
  //note: other properties. The string uniquely identifies the node; another node
  //note: is equivalent if and only if it has the same value.
  rel.recomputeDigest();

  // try to find equivalent rel only if DAG is allowed
  //note: 如果允许 DAG 的话，检查是否有一个等价的 HepRelVertex，有的话直接返回
  if (!noDag) {
    // Now, check if an equivalent vertex already exists in graph.
    String digest = rel.getDigest();
    HepRelVertex equivVertex = mapDigestToVertex.get(digest);
    if (equivVertex != null) { //note: 已经存在
      // Use existing vertex.
      return equivVertex;
    }
  }

  // No equivalence:  create a new vertex to represent this rel.
  //note: 创建一个 vertex 代替 rel
  HepRelVertex newVertex = new HepRelVertex(rel);
  graph.addVertex(newVertex); //note: 记录 Vertex
  updateVertex(newVertex, rel);//note: 更新相关的缓存，比如 mapDigestToVertex map

  for (RelNode input : rel.getInputs()) { //note: 设置 Edge
    graph.addEdge(newVertex, (HepRelVertex) input);//note: 记录与整个 Vertex 先关的 input
  }

  nTransformations++;
  return newVertex;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//org.apache.calcite.plan.hep.HepPlanner
// implement RelOptPlanner
//note: 优化器的核心，匹配规则进行优化
public RelNode findBestExp() {
  assert root != null;

  //note: 运行 HepProgram 算法(按 HepProgram 中的 instructions 进行相应的优化)
  executeProgram(mainProgram);

  // Get rid of everything except what's in the final plan.
  //note: 垃圾收集
  collectGarbage();

  return buildFinalPlan(root); //note: 返回最后的结果，还是以 RelNode 表示
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//org.apache.calcite.plan.hep.HepPlanner
private void executeProgram(HepProgram program) {
  HepProgram savedProgram = currentProgram; //note: 保留当前的 Program
  currentProgram = program;
  currentProgram.initialize(program == mainProgram);//note: 如果是在同一个 Program 的话，保留上次 cache
  for (HepInstruction instruction : currentProgram.instructions) {
    instruction.execute(this); //note: 按 Rule 进行优化(会调用 executeInstruction 方法)
    int delta = nTransformations - nTransformationsLastGC;
    if (delta > graphSizeLastGC) {
      // The number of transformations performed since the last
      // garbage collection is greater than the number of vertices in
      // the graph at that time.  That means there should be a
      // reasonable amount of garbage to collect now.  We do it this
      // way to amortize garbage collection cost over multiple
      // instructions, while keeping the highwater memory usage
      // proportional to the graph size.
      //note: 进行转换的次数已经大于 DAG Graph 中的顶点数，这就意味着已经产生大量垃圾需要进行清理
      collectGarbage();
    }
  }
  currentProgram = savedProgram;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//org.apache.calcite.plan.hep.HepPlanner
//note: 执行相应的 RuleInstance
void executeInstruction(
    HepInstruction.RuleInstance instruction) {
  if (skippingGroup()) {
    return;
  }
  if (instruction.rule == null) {//note: 如果 rule 为 null，那么就按照 description 查找具体的 rule
    assert instruction.ruleDescription != null;
    instruction.rule =
        getRuleByDescription(instruction.ruleDescription);
    LOGGER.trace("Looking up rule with description {}, found {}",
        instruction.ruleDescription, instruction.rule);
  }
  //note: 执行相应的 rule
  if (instruction.rule != null) {
    applyRules(
        Collections.singleton(instruction.rule),
        true);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

//org.apache.calcite.plan.hep.HepPlanner
//note: 执行 rule（forceConversions 默认 true）
private void applyRules(
    Collection<RelOptRule> rules,
    boolean forceConversions) {
  if (currentProgram.group != null) {
    assert currentProgram.group.collecting;
    currentProgram.group.ruleSet.addAll(rules);
    return;
  }

  LOGGER.trace("Applying rule set {}", rules);

  //note: 当遍历规则是 ARBITRARY 或 DEPTH_FIRST 时，设置为 false，此时不会从 root 节点开始，否则每次 restart 都从 root 节点开始
  boolean fullRestartAfterTransformation =
      currentProgram.matchOrder != HepMatchOrder.ARBITRARY
      && currentProgram.matchOrder != HepMatchOrder.DEPTH_FIRST;

  int nMatches = 0;

  boolean fixedPoint;
  //note: 两种情况会跳出循环，一种是达到 matchLimit 限制，一种是遍历一遍不会再有新的 transform 产生
  do {
    //note: 按照遍历规则获取迭代器
    Iterator<HepRelVertex> iter = getGraphIterator(root);
    fixedPoint = true;
    while (iter.hasNext()) {
      HepRelVertex vertex = iter.next();//note: 遍历每个 HepRelVertex
      for (RelOptRule rule : rules) {//note: 遍历每个 rules
        //note: 进行规制匹配，也是真正进行相关操作的地方
        HepRelVertex newVertex =
            applyRule(rule, vertex, forceConversions);
        if (newVertex == null || newVertex == vertex) {
          continue;
        }
        ++nMatches;
        //note: 超过 MatchLimit 的限制
        if (nMatches >= currentProgram.matchLimit) {
          return;
        }
        if (fullRestartAfterTransformation) {
          //note: 发生 transformation 后，从 root 节点再次开始
          iter = getGraphIterator(root);
        } else {
          // To the extent possible, pick up where we left
          // off; have to create a new iterator because old
          // one was invalidated by transformation.
          //note: 尽可能从上次进行后的节点开始
          iter = getGraphIterator(newVertex);
          if (currentProgram.matchOrder == HepMatchOrder.DEPTH_FIRST) {
            //note: 这样做的原因就是为了防止有些 HepRelVertex 遗漏了 rule 的匹配（每次从 root 开始是最简单的算法），因为可能出现下推
            nMatches =
                depthFirstApply(iter, rules, forceConversions, nMatches);
            if (nMatches >= currentProgram.matchLimit) {
              return;
            }
          }
          // Remember to go around again since we're
          // skipping some stuff.
          //note: 再来一遍，因为前面有跳过一些节点
          fixedPoint = false;
        }
        break;
      }
    }
  } while (!fixedPoint);
}