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

目录

背景

优化规则SortLimitPullUpConstantsRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

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

举例：从student表里取age=18的，并按照postCode邮编排序返回前1000学生信息

    SELECT  * 

    FROM ( 

        SELECT id,name,age,postCode FROM student WHERE age = 18  ORDER             BY postCode LIMIT 1000

    )  PSP;

        如这种写法，只是满足了有可能被上述规则Rule优化要求的形式条件。这里只是为了说明方便，使用了SQL进行讲述，其实优化器内部使用的RelNode关系表达式构造的操作符树组成来构建的。但是常量上拉是基于操作符树父与子的构建关系来确定上下关系的。

转换为操作符树，形式为：

等价变换后：                                     

变换后的SQL表示为：

SELECT id,name,18,postCode 

FROM ( 

    SELECT id,name,postCode FROM student WHERE age = 18  ORDER BY             postCode LIMIT 1000

 )  PSP;

说明：

        把子查询select中的age字段去掉了。把age=18等值常量谓词中a字段替换成常量18放在顶层Select中。

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

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

优化规则SortLimitPullUpConstantsRule

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

1）matches方法逻辑详解

此规则Rule只继承了父类的实现，默认返回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). RelNode关系表达式的Root根不能是Sort操作符，如图1SQL对Sort操作符              再嵌套一层的写法

   (b). 如果Project输入字段仅有一个，则不做任何优化，因为没有优化的空间。               没有优化空间，因为我们无法转换为空的Project运算符，如select a from t                只访问了一个字段a。

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

    (d). 如果谓词表达式中没有常量谓词，则不做任何优化。

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

final RelNode parent = call.rel(0);//根Root不是SortLimit
    final Sort sort = call.rel(1);
    final int count = sort.getInput().getRowType().getFieldCount(); //sort输入子RelNode Project投影的字段个数
    if (count == 1) {
      return;
    }
    final RexBuilder rexBuilder = sort.getCluster().getRexBuilder();
    final RelMetadataQuery mq = RelMetadataQuery.instance();
    final RelOptPredicateList predicates = mq.getPulledUpPredicates(sort.getInput());
    // 有关保留在从关系表达式RelNode发出的行中的谓词的元数据。
    if (predicates == null) {//如果没有谓词，即where条件，将不做任何优化
      return;
    }
    Map<RexNode, RexNode> conditionsExtracted = HiveReduceExpressionsRule.predicateConstants(
            //A map of each (e, constant) pair that occurs within pulledUpPredicates.
            RexNode.class, rexBuilder, predicates);//再从所有谓词集合中，把常量谓词提取
    Map<RexNode, RexNode> constants = new HashMap<>();
    for (int i = 0; i < count ; i++) { //遍历Project中指定的输入列引用
      RexNode expr = rexBuilder.makeInputRef(sort.getInput(), i);
      if (conditionsExtracted.containsKey(expr)) {
        constants.put(expr, conditionsExtracted.get(expr));//如果sort的输入子RelNode指定字段索引在常量谓词中，则加载constants映射中
      }
    }
    if (constants.isEmpty()) {
      return;
    }

接下来，遍历Sort的子Project中的字段引用，对这些字段引用进行分类topChildExprs和newChildExprs。topChildExprs收集这些字段引用RexNode，做顶层Project使用，也是常量上拉到Project的关键。

• 如果此字段在等值常量谓词引用过，则存放常量RexNode。

• 如果此字段在等值常量谓词没引用过，则存放该字段RexNode

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

List<RelDataTypeField> fields = sort.getInput().getRowType().getFieldList(); //获取Project中的字段列表
List<Pair<RexNode, String>> newChildExprs = new ArrayList<>(); //存放新的子表达式映射集合
List<RexNode> topChildExprs = new ArrayList<>();
List<String> topChildExprsFields = new ArrayList<>();

for (int i = 0; i < count ; i++) {
  RexNode expr = rexBuilder.makeInputRef(sort.getInput(), i); //创建Project中，指定的字段引用
  RelDataTypeField field = fields.get(i);
  if (constants.containsKey(expr)) {//如果此引用表达式在等值常量谓词映射中
    topChildExprs.add(constants.get(expr));//等值谓词常量表达式，这里存放的常量如a=1中1
    topChildExprsFields.add(field.getName());//等值常量谓词字段名称 a 字段名称  
  } else {
    newChildExprs.add(Pair.of(expr, field.getName())); //
    topChildExprs.add(expr);//如果该字段引用不在等值常量谓词表达式出现的字段，存在存放字段引用，如id
    topChildExprsFields.add(field.getName());
  }
}

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

// Update field collations 不在常量RexNode映射中的，
    final Mappings.TargetMapping mapping =
            RelOptUtil.permutation(Pair.left(newChildExprs), sort.getInput().getRowType()).inverse();//Project不在谓词常量集合的字段，与Project所有字段的mapping映射关系
//e字段表达式，与所有字段的排列组合,但是inverse 转换为了sort.getInput().getRowType()，Pair.left(newChildExprs)的映射关系
    List<RelFieldCollation> fieldCollations = new ArrayList<>();
    for (RelFieldCollation fc : sort.getCollation().getFieldCollations()) {//排序字段
      final int target = mapping.getTargetOpt(fc.getFieldIndex());//Returns the target that a source maps to, or -1 if it is not mapped.
      if (target < 0) {
        // It is a constant, we can ignore it
        continue;
      }
      fieldCollations.add(fc.copy(target));//找到在Sort中出现的，也必须select中出现的。
    }

        RexUtil.apply(mapping, topChildExprs)更新topChildExprs，把常量字段进行了上拉。列表集合准备topChildExprs列表由[ id,name,age,postCode] 替换成了topChildExprs [ id,name,18,postCode]，字段a替换成了常量18。

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

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

继续使用上述的例子：

原SQL:

SELECT * FROM ( SELECT id,name,age,postCode from student where age = 18  ORDER BY postCode LIMIT 1000)  PSP;

生成RelBuilder构建器来构建RelNode操作符树。

使用newChildExprs非等值常量谓词引用的RexNode列表构建Project。如上述 SELECT id,name,postCode from student where age = 18，注意去掉了age字段，因为age字段是等值常量谓词中引用了。

final RelBuilder relBuilder = call.builder();
relBuilder.push(sort.getInput());//压入的Sort的子RelNode，
relBuilder.project(Pair.left(newChildExprs), Pair.right(newChildExprs));//Creates a Project of the given list of expressions and field names.

下面是关键部分，是构建Sort并创建顶层Project将常量从上述去掉age字段的常量上拉到Project中

最终等价变换后的SQL：

SELECT id,name,18 as age ,postCode FROM ( SELECT id,name,postCode from student where age = 18  ORDER BY postCode LIMIT 1000)  PSP;

 

final ImmutableList<RexNode> sortFields =
          relBuilder.fields(RelCollations.of(fieldCollations));
  relBuilder.sortLimit(sort.offset == null ? -1 : RexLiteral.intValue(sort.offset),
          sort.fetch == null ? -1 : RexLiteral.intValue(sort.fetch), sortFields); // 使用上述整理的Sort排序字段，创建Sort
  // Create top Project fixing nullability of fields
  relBuilder.project(topChildExprs, topChildExprsFields);//创建上拉了常量谓词表达式Project
  relBuilder.convert(sort.getRowType(), false);//创建将当前关系表达式的输出转换为所需行类型的投影Project。
  List<RelNode> inputs = new ArrayList<>();
  for (RelNode child : parent.getInputs()) {  //最外层的RelNode
    if (!((HepRelVertex) child).getCurrentRel().equals(sort)) {//遍历父RelNode的子RelNode，不等于的都加入RelNode list，否则使用relBuilder.build()
      inputs.add(child);
    } else {
      inputs.add(relBuilder.build());//Returns the final relational expression. 如果等于sort对象，就返回最终的RelNode
    }
  }
  call.transformTo(parent.copy(parent.getTraitSet(), inputs));
}

上述代码的最后，遍历parent根Root关系表达式的其他输入RelNode，如不是上述等价变换后新Sort对象，则添加到parent根节点，同时注册到优化器。

总结

     优化规则SortLimitPullUpConstantsRule，需要满足上述几种优化条件后，将Sort子RelNode中Filter等值常量谓词表达式中的字段，替换为常量，上拉到Project中来达到优化的目的的优化Rule。

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

往期文章分享

优化规则系列

成本模型系列