Hive优化器原理与源码解析系列--优化规则UnionPullUpConstantsRule(八)

目录

背景

优化规则UnionPullUpConstantsRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

上篇文章讲解了SortLimitPullUpConstantsRule等值常量谓词上拉，这样可以把即出现在谓词中等于某个常量constant的又出现在Project投影中的变量或列引用，是此列引用不在参与中间结果的一系列的计算，直接在投影Project使用常量作为此列引用的返回值。在等价变换即输入结果和输出结果不变的前提下，达到优化的目的，这也是优化器的价值所在。

优化规则Rule关于常量上拉的优化思路大致如此。

这篇文章分享基于成本优化器CBO可插拔式优化规则UnionPullUpConstantsRule，从SQL角度讲，带有UNION ALL、 Where等值谓词常量条件的这种SQL语句写法中将谓词中上拉常量到Project投影（Select操作）中。

举例说明：

如这种写法，只是满足了有可能被规则Rule优化要求的形式条件

SELECT key, value, ds FROM (
     SELECT key, value, ds FROM src_union_1
     UNION ALL
     SELECT key, value, ds FROM src_union_2
     UNION ALL
     SELECT key, value, ds FROM src_union_3
) subq where key = 86;

        这里只是为了说明方便，使用了SQL进行讲述，其实优化器内部使用的RelNode关系表达式构造的操作符树组成来构建的。但是常量上拉是基于操作符树父与子的构建关系来确定上下关系的，转换为操作符树。

变换后的SQL表示为：

SELECT 86 as key, value, ds FROM (
        SELECT value, ds FROM src_union_1
        UNION ALL
        SELECT value, ds FROM src_union_2
        UNION ALL
        SELECT value, ds FROM src_union_3
) subq where key = 86;

        转换后的操作符树把子查询select中的key字段去掉了。把key=86等值常量谓词中key字段替换成常量86放在顶层Select中。

在优化器内部，虽然在操作符树的形式上能满足优化要求，在具体实现逻辑上，还有其他逻辑限制，比如，Project投影的字段个数较少，就没有太多优化空间，Filter中必须是等值的谓词常量如key = 86，比如name<>'张山'是常量谓词，但是'<>'运算符不是等值的，就会放弃继续优化等等。

Hive几乎所有优化规则Rule继承了父类RelOptRule。关于RelOptRule和RelOptRuleCall相关概念。这里不再赘述，详细翻阅前期文章。也需实现两个方法matches和OnMatch两个方法。matches默认实现返回true。

优化规则UnionPullUpConstantsRule

因为matches和OnMatch两个方法是每条优化规则的关键，这里还是做一些两个方法的简要说明

1）matches方法逻辑详解

此规则UnionPullUpConstantsRule和上篇SortLimitPullUpConstantsRule规则matches方法一样，都只是继承了父类的实现，默认返回true。意味着各种ReNode关系表达式都有匹配应用的可能。

matches方法返回此规则Rule是否可能与给定的操作数operands匹配，但是此方法的任何实现都可以给出误报，也就是说虽然规则与操作数匹配，但随后具OnMatch（ReloptRuleCall）而不生成任何后续任务。

2）onMatch方法逻辑详解

接收有关一条规则匹配的通知。同时此方法被调用，call.rels保存了与规则Rule的操作数Operands匹配上的关系表达式RelNode集合；call.rels[0]是根表达式。通常一条规则Rule会检查这些节点是否有效匹配，创建一个新表达式RelNode（等价的）然后调用RelOptRuleCall.transformTo(org.apache.calcite.rel.RelNode, java.util.Map<org.apache.calcite.rel.RelNode, org.apache.calcite.rel.RelNode>)注册表达式。而RelOptRuleCall用一系列RelNode关系表达式集合作为参数，对RelOptRule优化规则的调用。

此onMatch方法设计逻辑较多，这里分成几块进行从上到下的单独讲解。

首先，因为此Rule规则matches默认实现，是返回true，增加每个RelNode匹配的可能性，但是onMatch再做优化转换也是需要做相关判断。

onMatch的判断条件如下：

    a、如果Project输入字段仅有一个，则不做任何优化，因为没有优化的空间。因为我们无法转换为空的Project运算符，如select a from t where a = 1 无法在对等值常量a进行上拉。

    b、有关保留在从关系表达式RelNode发出的行中的谓词的元数据。如果谓词为null，则不做任何优化

     c、如果谓词表达式中没有常量谓词，则不做任何优化。

关于HiveReduceExpressionsRule此优化规则以后会文章讲解。

这里重点讲一下HiveReduceExpressionsRule.predicateConstants方法，该方法功能是从上述谓词元数据predicates提取等值的常量谓词，如a=1就是等值常量谓词，name<>'李四'是非等值常量谓词。还如a=1 and a=4 存在不一致问题也不是。把等值常量谓词的结果存放到constants映射（字段表达式，常量表达式）中。

final Union union = call.rel(0);
    final int count = union.getRowType().getFieldCount();
    if (count == 1) {//投影中只有一个字段无法再进行上拉，会导致select中字段为空列表
      return;
    }
    final RexBuilder rexBuilder = union.getCluster().getRexBuilder();
    final RelMetadataQuery mq = RelMetadataQuery.instance();
    final RelOptPredicateList predicates = mq.getPulledUpPredicates(union);
    if (predicates == null) {//从union操作符中拉取谓词
      return;
    }
    Map<RexNode, RexNode> conditionsExtracted = HiveReduceExpressionsRule.predicateConstants(//提取常量谓词
            RexNode.class, rexBuilder, predicates);
    Map<RexNode, RexNode> constants = new HashMap<>();
    for (int i = 0; i < count ; i++) {
      RexNode expr = rexBuilder.makeInputRef(union, i);
      if (conditionsExtracted.containsKey(expr)) {
        constants.put(expr, conditionsExtracted.get(expr));
      }
    }
    // None of the expressions are constant. Nothing to do.
    if (constants.isEmpty()) {//常量谓词为null，则不做任何优化
      return;
    }

接下来，遍历Union的子Project中的字段引用，对这些字段引用进行分类topChildExprs和newChildExprs。

topChildExprs收集这些字段引用RexNode，做顶层Project使用，也是常量上拉到Project的关键。如果此字段在等值常量谓词引用过，则存放常量RexNode。否则此字段在等值常量谓词没引用过，则存放该字段RexNode

如select a,b from t1 where a=1,topChildExprs收集的 [1,b],其中1常量，b为字段。refs则收集没在等值常量谓词中引用过的字段，如上述pair(b,b字段名称).

        Mappings.TargetMapping mapping为将源列映射到目标列的映射关系，目标列与源列是1：N的关系，每个目标列至少对应一个源列，一个源列只能对应一个目标列。inverse()方法是把从源列到目标列的映射关系，翻转为从目标列到源列的映射关系。这样就变成了Project中的所有字段到不在常量谓词中的字段的映射mapping。

// Create expressions for Project operators before and after the Union
    List<RelDataTypeField> fields = union.getRowType().getFieldList();
    List<RexNode> topChildExprs = new ArrayList<>(); //存放顶层Unoin的子所有的字段RexNode（常量 + 非常量）
    List<String> topChildExprsFields = new ArrayList<>();
    List<RexNode> refs = new ArrayList<>();
    ImmutableBitSet.Builder refsIndexBuilder = ImmutableBitSet.builder();

    for (int i = 0; i < count ; i++) {
      RexNode expr = rexBuilder.makeInputRef(union, i);
      RelDataTypeField field = fields.get(i);
      if (constants.containsKey(expr)) {
        topChildExprs.add(constants.get(expr));//如果是常量，则存放的字段对应的常量rexnode值
        topChildExprsFields.add(field.getName());
      } else {
        topChildExprs.add(expr);//不是常量谓词，则存放的是该字段RexNode
        topChildExprsFields.add(field.getName());
        refs.add(expr);//，仅存放的该字段RexNode不是常量谓词的字段
        refsIndexBuilder.set(i);
      }
    }
    ImmutableBitSet refsIndex = refsIndexBuilder.build();

    // Update top Project positions
    final Mappings.TargetMapping mapping =
            RelOptUtil.permutation(refs, union.getInput(0).getRowType()).inverse();
    topChildExprs = ImmutableList.copyOf(RexUtil.apply(mapping, topChildExprs));

        RexUtil.apply(mapping, topChildExprs)更新topChildExprs，把常量字段进行了上拉。列表集合准备topChildExprs列表由[key, value, ds] 替换成了topChildExprs [ 86,value, ds]，字段key替换成了常量86。

// Update top Project positions         select中字段已经更新为常量
topChildExprs = ImmutableList.copyOf(RexUtil.apply(mapping, topChildExprs));//并生成一个新的排序列表

        下面是生成新的Project-Union-Project序列表达式。

        遍历Union的各个子RelNode中构建出不在等值常量谓词列表的中字段引用存放到newChildExprs.

// Create new Project-Union-Project sequences
final RelBuilder relBuilder = call.builder();
    for (int i = 0; i < union.getInputs().size() ; i++) {
      RelNode input = union.getInput(i);
      List<Pair<RexNode, String>> newChildExprs = new ArrayList<>();
      for (int j = 0; j < refsIndex.cardinality(); j++ ) {
        int pos = refsIndex.nth(j);
        newChildExprs.add(
                Pair.<RexNode, String>of(rexBuilder.makeInputRef(input, pos),
                        input.getRowType().getFieldList().get(pos).getName()));
      }
      if (newChildExprs.isEmpty()) {
        // At least a single item in project is required.
        newChildExprs.add(Pair.<RexNode,String>of(
                topChildExprs.get(0), topChildExprsFields.get(0)));
      }
      
      // Add the input with project on top
      relBuilder.push(input);
      relBuilder.project(Pair.left(newChildExprs), Pair.right(newChildExprs));//子relNode创建新的字段引用，此时已经去掉了已经被上拉的常量字段
    }
    relBuilder.union(union.all, union.getInputs().size());
    // Create top Project fixing nullability of fields
    relBuilder.project(topChildExprs, topChildExprsFields);
    relBuilder.convert(union.getRowType(), false);
    call.transformTo(relBuilder.build());

        生成RelBuilder构建器来构建RelNode操作符树。使用newChildExprs非等值常量谓词引用的RexNode列表构建Project。子RelNode创建新的字段引用，此时已经去掉了已经被上拉的常量字段。关键部分，是构建Union并创建顶层Project将常量从上述去掉age字段的常量上拉到Project中。最后做了等价变换注册到优化器。

最终等价变换后的SQL：

SELECT 86 as key, value, ds FROM (
SELECT value, ds FROM src_union_1
UNION ALL
SELECT value, ds FROM src_union_2
UNION ALL
SELECT value, ds FROM src_union_3
) subq where key = 86;

        注：在Calcite中火山优化器，所有的等价变换，都是基于关系代数，和等价变换的前提，这是只是为了方便说明使用SQL说明，操作符树的变换省略了，以后会单独的文章对Calcite单独介绍。

总结

        常量上拉的大致思路是对出现在谓词中等于某个常量constant的又出现在Project投影中的变量或列引用，是此列引用不在参与中间结果的一系列的计算，直接在投影Project使用常量作为此列引用的返回值。详细可参考以往文章关于常量上拉优化规则Rule（文末尾有连接）。

        由于笔者知识及水平有限,因此文中错漏之处在所难免,恳请各位老师、专家不吝赐教。

往期文章分享

优化规则系列

成本模型系列