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

目录

背景

优化规则SortProjectTransposeRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

上篇文章分享了基于成本优化器CBO可插拔式优化规则SortRemoveRule移除Sort的优化规则和SortJoinReduceRule把Sort下推到Join的优化规则，不熟悉的可翻阅往前文章。此篇文章讲解SortProjectTransposeRule优化规则，Sort排序和Project投影操作（相当于HSQ中的Select操作）的调换顺序的优化规则。

Hive几乎所有优化规则Rule继承了父类RelOptRule。这里先讲述一下RelOptRule相关概念。

RelOptRule Calcite框架中的优化规则Rule的抽象类，把一个关系表达式RelNode1转换为另一个关系表达式RelNode2，它有一系列RelOptRuleOperands，其决定了此Rule是否能被应用到一棵RelNodes操作符数的指定部分section，由optimizer优化器指出哪些Rule是可应用的，然后在这些Rules规则上调用onMatch（RelOptRuleCall）方法。

RelOptRuleCall是优化规则调用，其使用一系列RelNode关系表达式集合作为参数，对RelOptRule优化规则的调用。匹配上优化规则内一系列RelOptRuleOperands操作数，也代表了优化规则Rule配上了输入参数RelNode树的某些子RelNode，可进行优化。

优化规则SortProjectTransposeRule

Hive源码中实现的优化规则Rule，几乎都是继承了父类RelOptRule，也需实现两个方法matches和OnMatch两个方法。matches默认实现返回true。

1）matches方法逻辑详解

matches方法返回此规则Rule是否可能与给定的操作数operands匹配。优化器在匹配上规则Rule的所有操作数Operands之后和调用OnMatch（ReloptRuleCall）之前调用此方法。在优化器的实现中，它可能会在调用OnMatch（ReloptRuleCall）之前将匹配的ReloptRuleCall排队很长时间，matches方法提前判断这种方法是有好处的，因为优化器可以在处理的早期，把不满足匹配条件的规则放弃掉。

判断由RelOptCall调用的优化规则Rule是否与输入参数RelNode关系表达式匹配，即此优化规则Rule能否应用到一个RelNode关系表达式树上。SortJoinReduceRule的判断条件如下：

• Sort操作符没有LIMIT操作0，说明Sort操作获取全部记录数，这样没有优化空间，则放弃优化。其他则返回true。

@Override
public boolean matches(RelOptRuleCall call) {
  final HiveSortLimit sortLimit = call.rel(0);

  // If does not contain a limit operation, we bail out
  if (!HiveCalciteUtil.limitRelNode(sortLimit)) {  // 同样的是如果SortLimit 没有指定limit，将会退出优化。
    return false;
  }

  return true;
}

但是此方法的任何实现都可以给出误报，也就是说，规则与操作数匹配，但随后具有OnMatch（ReloptRuleCall）而不生成任何后续任务。

2）onMatch方法逻辑详解

同样，首先使用RelOptRuleCall对象rel(0)方法获取根RelNode关系表达式SortLimit，其次获取SortLimit的子RelNode关系表达式Project。

这里使用来确定Project投影的输入和输出字段之间的映射。如果Sort的字段不是Project投影内输入和输出字段映射内，即是由表达式产生的，非来自Project的相关字段，则不做任何优化的事情。就是所谓matches方法的误报。

RelOptUtil.permutation方法返回描述输出字段来源的排列。在返回的映射中，如果字段i投影输入字段n，则map.getTargetOpt（i）的值为n；如果是表达式，则为-1。如果为-1，这里不做任何优化的事情。

使用生成新的RelCollation排序信息，新成的SortLimit，再使用新的SortLimit生成新的Project，相当于SortLimit和Project颠倒顺序。变换如下：

                                Sort                 Project

                                   |          ->          |

                              Project               Sort

public void onMatch(RelOptRuleCall call) {
  final HiveSortLimit sort = call.rel(0);//根RelNOde
  final HiveProject project = call.rel(1);//子RelNode

  final Mappings.TargetMapping map =
      RelOptUtil.permutation(
          project.getProjects(), project.getInput().getRowType());
  for (RelFieldCollation fc : sort.getCollation().getFieldCollations()) { //遍历排序的排序字段集合
    if (map.getTargetOpt(fc.getFieldIndex()) < 0) { //如果Sort的字段不是Project投影内输入和输出字段映射内，即是由表达式产生的，非来自Project的相关字段，则不做任何优化的事情
      return;  //getTargetOpt为-1 说明是表达式
    }
  }
  // Create new collation
 //应用一个mapping 到 排序列表，并生成一个新的排序列表
  final RelCollation newCollation =
      RelCollationTraitDef.INSTANCE.canonize(
          RexUtil.apply(map, sort.getCollation()));
  // New operators
  final HiveSortLimit newSort = sort.copy(sort.getTraitSet().replace(newCollation),
          project.getInput(), newCollation, sort.offset, sort.fetch); //使用原Project的输入字段，等等信息，生成新的SortLimit
  final RelNode newProject = project.copy(sort.getTraitSet(),
          ImmutableList.<RelNode>of(newSort));//再用新的SortLimit作为子RelNode生成Project，相当于Sort与Project顺序颠倒一下。注册到优化器。
  call.transformTo(newProject);
}

        在onMatch方法的底部，是对一个RelNode做了等价变化后，注册到优化器的，这里是把新生成SortLimit放到新生成的Project之下作为Project的子RelNode。

总结

    Sort排序和Project投影操作（相当于HSQ中的Select操作）的调换顺序的优化规则。把原RelNode做了等价变化，新产生RelNode注册到优化器，使用动态规划算法构建出最优的执行计划。

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

往期文章分享

优化规则系列

成本模型系列