Apache Calcite查询优化器之HepPlanner

Database>SQL Engine 17 minutes read (About 2500 words) VISITED TIMES

本文已收录在合集Apche Calcite原理与实践中.

本文是Apache Calcite原理与实践系列的第六篇. 上一篇文章介绍了与查询优化器相关的基本理论, 本文开始介绍Calcite中的查询优化器HepPlanner的实现, HepPlanner是基于规则的优化器, 相对于VolcanoPlanner来说实现比较简单. 本文首先介绍HepPlanner中引入的相关概念和数据结构, 之后介绍HepPlanner的整个优化流程.

HepPlanner概念和数据结构

HepRelVertex

在HepPlanner内部, 会将待优化的RelNode算子树转化为一个有向无环图(DAG), 而HepRelVertex就是这个DAG的顶点. 其实现关系如下图所示.

HepRelVertex就是对一个RelNode的包装, 其currentRel成员变量指向一个原始的RelNode. 待优化的RelNode树中的每个RelNode节点都会转化为一个HepRelVertex.

1
2
3
4
public class HepRelVertex extends AbstractRelNode {

    private RelNode currentRel;
}

将RelNode树转化为DAG的过程在HepPlanner的addRelToGraph()函数中, 其本质就是对RelNode树进行深度优先遍历, 笔者已经在其中加了详细的注释.

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
private HepRelVertex addRelToGraph(RelNode rel) {
    // Check if a transformation already produced a reference to an existing vertex.
    // 检查DAG顶点中是否已经包含了当前RelNode, 若包含证明该RelNode已经转换过, 直接返回即可
    if (graph.vertexSet().contains(rel)) {
        return (HepRelVertex) rel;
    }

    // Recursively add children, replacing this rel's inputs
    // with corresponding child vertices.
	// 递归将当前RelNode的子节点加入到DAG中
    final List<RelNode> inputs = rel.getInputs();	// 原来的子节点
    final List<RelNode> newInputs = new ArrayList<>();	// 转化为HepRelVertex之后的子节点
    for (RelNode input1 : inputs) {
        // 递归将子节点加入到DAG中(深度优先遍历)
        HepRelVertex childVertex = addRelToGraph(input1);
        newInputs.add(childVertex);
    }

    if (!Util.equalShallow(inputs, newInputs)) {
        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
	// 计算RelNode的digest(唯一标识当前节点), 用于后续获取等价节点
    rel.recomputeDigest();

    // try to find equivalent rel only if DAG is allowed
	// 如果允许DAG, 尝试从已转化的顶点中获取等价HepRelVertex
	// 注意这里的noDag变量仅用于指示是否重用等价的表达式, 
	// 与文中所说的由HepRelVertex组成的DAG无关
    if (!noDag) {
        // Now, check if an equivalent vertex already exists in graph.
        HepRelVertex equivVertex = mapDigestToVertex.get(rel.getRelDigest());
        if (equivVertex != null) {
            // Use existing vertex.
            // 如果已存在等价节点则直接返回
            return equivVertex;
        }
    }

    // No equivalence:  create a new vertex to represent this rel.
	// 创建新的顶点并添加到DAG中
    HepRelVertex newVertex = new HepRelVertex(rel);
    graph.addVertex(newVertex);
    updateVertex(newVertex, rel);

	// 在当前节点和其子节点之间创建边
    for (RelNode input : rel.getInputs()) {
        graph.addEdge(newVertex, (HepRelVertex) input);
    }
    
    nTransformations++;
    return newVertex;
}

HepProgram

HepProgram是一个工具类, 包含了初始化HepPlanner所需的一些信息, 几个重要的成员变量如下:

  • instructions包含了所有需要执行的优化规则;
  • matchLimit指定最大匹配次数, 防止规则匹配的过程陷入无限循环. 默认值是MATCH_UNTIL_FIXPOINT = Integer.MAX_VALUE;
  • matchOrder定义了规则匹配的顺序(即DAG的遍历顺序), HepPlanner支持4中匹配顺序:
    • ARBITRARY: 按任意顺序匹配, 这是默认值, 实际在执行的时候用的是DEPTH_FIRST.
    • BOTTOM_UP: 以拓扑排序的顺序进行遍历.
    • TOP_DOWN：以拓扑排序的逆序进行遍历.
    • DEPTH_FIRST: 深度优先匹配.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      public class HepProgram {
          // 需要执行的优化规则
          final ImmutableList<HepInstruction> instructions;
      	// 最大匹配次数
          int matchLimit;
      	// 遍历顺序
          HepMatchOrder matchOrder;

          HepInstruction.EndGroup group;
      }

HepInstruction

HepInstruction是对HepPlanner所执行指令的统一封装, 包含多种类型的操作, 其实现类如下图所示.

具体的HepInstruction可分为以下几类:

  • RuleClass和RelInstance用于执行一个优化规则, 不同的是RuleClass需要当前优化器中已经存在对应的优化规则, 即通过RelOptPlanner.addRule()添加过该规则, 而RelInstance不需要. RuleCollection用于执行一组优化规则, 它也不需要调用RelOptPlanner.addRule()添加规则.
  • BeginGroup用于开始一个规则组, EndGroup用于结束一个规则组, 在BeginGroup和EndGroup之间的所有优化规则会整组一起执行.
  • SubProgram包装了一个子HepProgram.
  • MatchLimit用于指示最大匹配次数, 执行该指令会修改当前HepProgram的matchLimit值; MatchOrder用于指示匹配匹配顺序, 执行该指令会修改当前HepProgram的matchOrder.

HepPlanner优化过程

以下是一个使用HepPlanner的简单示例, 完整的代码在HepPlannerExample中.

1
2
3
4
5
6
7
8
9
10
11
12
HepProgramBuilder hepProgramBuilder = new HepProgramBuilder();
// 添加优化规则
hepProgramBuilder.addRuleInstance(CoreRules.FILTER_TO_CALC);
hepProgramBuilder.addRuleInstance(EnumerableRules.ENUMERABLE_TABLE_SCAN_RULE);
hepProgramBuilder.addRuleInstance(EnumerableRules.ENUMERABLE_CALC_RULE);

// 1. 构建HepPlanner
HepPlanner planner = new HepPlanner(hepProgramBuilder.build());
// 2. 构建DAG
planner.setRoot(root);
// 3. 执行优化
RelNode optimizedRoot = planner.findBestExp();

从上述代码中可以看到, 使用HepPlanner进行查询优化分为三步:

  1. 创建HepPlanner;
  2. 调用HepPlanner.setRoot()构建DAG;
  3. 调用HepPlanner.findBestExp()执行查询优化.

步骤一: 创建HepPlanner

创建HepPlanner需要一个HepProgram, Calcite提供了HepProgramBuilder来创建HepProgram, 其方法都是用来创建HepInstruction, 每种HepInstruction实例都有一个对应的方法, 比如:

  • addRuleClass()用于创建RuleClass;
  • addRuleCollection()用于创建RuleCollection;
  • addMatchOrder()用于创建MatchOrder.

步骤二: 构建DAG

构建DAG的过程是通过调用HepPlanner.setRoot()触发的, 通过源代码也可以看到最终是调用了addRelToGraph(), 其具体流程已经在上文分析过, 不再赘述.

1
2
3
4
public void setRoot(RelNode rel) {
    root = addRelToGraph(rel);
	dumpGraph();
}

步骤三: 执行查询优化

执行查询优化的过程是在HepPlanner.findBestExp()中触发的.

1
2
3
4
5
6
7
8
9
10
public RelNode findBestExp() {
    assert root != null;

    executeProgram(mainProgram);

    // Get rid of everything except what's in the final plan.
    collectGarbage();
    dumpRuleAttemptsInfo();
    return buildFinalPlan(root);
}

可以看到在findBestExp()中, 主要是调用了executeProgram()来执行优化, 其主要流程就是遍历当前HepProgram中的HepInstruction, 并逐个执行.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void executeProgram(HepProgram program) {
    HepProgram savedProgram = currentProgram;
	currentProgram = program;
	currentProgram.initialize(program == mainProgram);
	// 遍历当前HepProgram中的HepInstruction, 逐个执行
    for (HepInstruction instruction : currentProgram.instructions) {
        instruction.execute(this);
        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.
            collectGarbage();
        }
    }
    currentProgram = savedProgram;
}

真正的优化规则是保存在HepInstruction中的, 这里我们以RuleInstance为例来说明HepPlanner是如何执行优化规则的. RuleInstance.execute()会调用HepPlanner.executeInstruction()方法.

1
2
3
4
5
6
7
8
9
10
11
12
void executeInstruction(HepInstruction.RuleInstance instruction) {
    if (skippingGroup()) {
        return;
    }
    if (instruction.rule == null) {
        assert instruction.ruleDescription != null;
        instruction.rule = getRuleByDescription(instruction.ruleDescription);
    }
    if (instruction.rule != null) {
        applyRules(Collections.singleton(instruction.rule), true);
    }
}

对于需要执行优化规则的HepInstruction, 最终都会调用applyRules().

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
private void applyRules(Collection<RelOptRule> rules, boolean forceConversions) {
    if (currentProgram.group != null) {
        assert currentProgram.group.collecting;
        currentProgram.group.ruleSet.addAll(rules);
        return;
    }

    // 当遍历顺序是ARBITRARY或DEPTH_FIRST时为false
    // 此时不会每次匹配成功之后都从root顶点开始
    boolean fullRestartAfterTransformation =
        currentProgram.matchOrder != HepMatchOrder.ARBITRARY
        && currentProgram.matchOrder != HepMatchOrder.DEPTH_FIRST;

    int nMatches = 0;

    boolean fixedPoint;
    do {
        // 根据遍历顺序获取对应的迭代器
        Iterator<HepRelVertex> iter = getGraphIterator(root);
        fixedPoint = true;
        while (iter.hasNext()) {	// 遍历每个顶点
            HepRelVertex vertex = iter.next();
            for (RelOptRule rule : rules) {		// 遍历每个RelOptRule
                // 对每个规则尝试进行匹配和转换
                HepRelVertex newVertex = applyRule(rule, vertex, forceConversions);
                if (newVertex == null || newVertex == vertex) {
                    continue;
                }
                ++nMatches;
                // 匹配次数超过最大次数, 则直接退出
                if (nMatches >= currentProgram.matchLimit) {
                    return;
                }
                if (fullRestartAfterTransformation) {
                    // 当不是DEPTH_FIRST时, 匹配成功后从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.
                    // 如果是DEPTH_FIRST, 那么直接递归匹配新节点的子节点.
                    // 因为转换后的子节点可能被重新匹配到现有规则.
                    iter = getGraphIterator(newVertex);
                    if (currentProgram.matchOrder == HepMatchOrder.DEPTH_FIRST) {
                        nMatches = depthFirstApply(iter, rules, forceConversions, nMatches);
                        if (nMatches >= currentProgram.matchLimit) {
                            return;
                        }
                    }
                    // Remember to go around again since we're skipping some stuff.
                    fixedPoint = false;
                }
                break;
            }
        }
    } while (!fixedPoint);
}

在applyRules()会遍历DAG中的所有顶点, 并调用applyRule()依次匹配当前规则组中的所有规则. 在applyRule()中会具体判断当前节点子树的Pattern与规则所指定的Pattern是否一致, 如果一直则触发规则, 进行转换.

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
private HepRelVertex applyRule(RelOptRule rule, HepRelVertex vertex, boolean forceConversions) {
    if (!graph.vertexSet().contains(vertex)) {
        return null;
    }
    RelTrait parentTrait = null;
    List<RelNode> parents = null;
    if (rule instanceof ConverterRule) {
        // Guaranteed converter rules require special casing to make sure
        // they only fire where actually needed, otherwise they tend to
        // fire to infinity and beyond.
        ConverterRule converterRule = (ConverterRule) rule;
        if (converterRule.isGuaranteed() || !forceConversions) {
            if (!doesConverterApply(converterRule, vertex)) {
                return null;
            }
            parentTrait = converterRule.getOutTrait();
        }
    } else if (rule instanceof CommonRelSubExprRule) {
        // Only fire CommonRelSubExprRules if the vertex is a common
        // subexpression.
        List<HepRelVertex> parentVertices = getVertexParents(vertex);
        if (parentVertices.size() < 2) {
            return null;
        }
        parents = new ArrayList<>();
        for (HepRelVertex pVertex : parentVertices) {
            parents.add(pVertex.getCurrentRel());
        }
    }

    final List<RelNode> bindings = new ArrayList<>();
    final Map<RelNode, List<RelNode>> nodeChildren = new HashMap<>();
    // 判断当前节点子树的Pattern与规则指定的Pattern是否一致
    boolean match = matchOperands(rule.getOperand(), vertex.getCurrentRel(), bindings, nodeChildren);

    if (!match) {
        return null;
    }

    // 创建RelOptRuleCall, 最终会传递给RelRule.onMatch()方法进行转换
    HepRuleCall call =
        new HepRuleCall(
            this,
            rule.getOperand(),
            bindings.toArray(new RelNode[0]),
            nodeChildren,
            parents);

    // Allow the rule to apply its own side-conditions.
    // 调用RelRule.matches(), 允许规则添加自己的判断条件
    if (!rule.matches(call)) {
        return null;
    }

    // 触发规则, 进行转换
    fireRule(call);

    if (!call.getResults().isEmpty()) {
        return applyTransformationResults(vertex, call, parentTrait);
    }

    return null;
}

整体执行流程

HepPlanner的整个查询优化流程如下图所示.

总结

可以看到HepPlanner的优化流程还是比较简单的, 无非是暴力地遍历整个RelNode树和所有规则, 一旦发现某个节点的子树Pattern符合规则所指定的Pattern就进行转换. 需要注意的是, 尽管HepPlanner也可以用来生成物理执行计划(如HepPlannerExample中那样), 但是在生产实践中千万不要这么做, 而仅是用HepPlanner进行一些肯定有正收益的规则优化, 如投影下推, 谓词下推等. 因为HepPlanner无法保证输出计划的物理属性, 并且无法对比不同计划之间的成本, 如果要生成物理计划, 需要使用下一篇文章中介绍的VolcanoPlanner.

参考

[1] Rule-based Query Optimization

#Apache Calcite
Apache Calcite查询优化器之VolcanoPlanner Apche Calcite查询优化概述

本博客所有文章除特别声明外, 均采用CC BY-NC-SA 3.0 CN许可协议. 转载请注明出处!



关注笔者微信公众号获得最新文章推送

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×