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

目录

背景

优化规则ProjectSortTransposeRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

        此篇文章讲解ProjectSortTransposeRule优化规则，Project投影操作（相当于HSQL中的Select操作）和Sort排序的调换顺序的优化规则。

变换如下：

        Hive基于成本优化器实现时，内置的规则中也不是每条优化规则Rule都能保证对此RelNoe关系表达树式进行等价变换后都能减少成本Cost。每次等价交换后注册到RelNode等价关系表达RelNode集合中，由CBO通过计算成本模型CostModel和统计信息来计算成本，从选择最优的执行计划。

        之前文章讲过SortProjectTransposeRule规则，是把Sort排序操作和Project投影操作进行顺序颠倒。和本篇讲解内容刚好是一个相反的操作，也即优化器不能保证Project和Sort颠倒顺序两者一定能优化，可以对满足matches条件的RelNode进行尝试Project和Sort的两者的顺序进行调换。多一种等价的执行计划供CBO成本优化器选择，感兴趣的童鞋，可翻看前期文章（文末有连接）。

        这里会对ProjectSortTransposeRule进行更详细讲解，如Mappings.TargetMapping输入字段和输出字段映射关系的生成过程，前期几篇文章都有提到这个知识点，但是都没展开。这里会结合Calcite相关知识点进行说明。

        为了保证每篇文章的对立性，尽量避免读者再去翻阅往前文章查找相关知识点，有些知识点是在优化规则Rule重复提到的。高手可跳跃阅读，下面言归正传。

        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，可进行优化。

优化规则ProjectSortTransposeRule

        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关系表达式树上。

        此优化规则Rule中，matches方法是从父类继承的默认实现，即一直返回true。但是此方法的任何实现都可以给出误报，也就是说，规则与操作数匹配，但随后具有OnMatch（ReloptRuleCall）而不生成任何后续任务。

2）onMatch方法逻辑详解

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

final HiveProject project = call.rel(0);
final HiveSortLimit sort = call.rel(1);

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

// Determine mapping between project input and output fields. If sort
// relies on non-trivial expressions, we can't push.
final Mappings.TargetMapping map =
    RelOptUtil.permutation(
        project.getProjects(), project.getInput().getRowType()).inverse();
    for (RelFieldCollation fc : sort.getCollation().getFieldCollations()) {
      if (map.getTarget(fc.getFieldIndex()) < 0) {//说明映射关系中，输入含有表达式和输出字段的映射。
        return;
      }
    }

        RelOptUtil.permutation方法返回描述输出字段来源的排列，即输入字段和输出字段的映射。在返回的映射中，如果Sort字段输入i投影输出字段n，则map.getTargetOpt（i）的值为n；如果是表达式expression，则为-1。如果返回值为-1，说明输入字段和输出字段之间的映射的不是完全的字段与字段的对应映射，而是含有表达式expression与字段的映射。这里不做任何优化的事情。

        顶层Project 和 子Sort这种RelNode表达式树，子Sort作为顶层Project的输入Input，则Project作为Output。两者顺序颠倒，就是Project操作作为子输入Input，而Sort就是作为顶层输出Output。如果子Sort中含有表达式expression，这种过程是不可逆的。例如Sort input输入字段 A + B 对应Project Output输出字段D，这样就导致无法简单的Project和Sort进行顺序颠倒。所以onMatch对这种情况是不做任何优化的。

下面对permutation方法对说明：

        首先创建PARTIAL_FUNCTION类型，即每个源最多有一个目标输入和输出之间的映射关系mapping对象。使用Ord.zip方法把project.getProjects()的List<RexNode>生成java.util.List<Ord<E>>对象包含（在行中序号和RexNOde的对应关系），并遍历之把输入字段序号和输出字段序号的对应关系形成映射关系写入到mapping对象。其中如果是简单的Cast函数的类型转换就第一个操作数，如Cast（id as string）取id字段，如果是RexInputRef输入字段引用，则映射关系同样写入mapping对象。最终生成一个输入字段和输出字段的序号映射关系对象。

Mapping接口：

        Mapping接口是源域到目标域之间的关系。即源字段序号和目标字段序号的之间映射关系。

        此接口表示最一般的可能映射。根据特定映射的映射类型，某些操作可能不适用。如果调用该方法，将收到运行时错误。例如：

• 如果目标有多个源，那么方法mappings.sourcemapping.getsource（int）将抛出mappings.toomanyelementexception。

• 如果源没有目标，那么方法mappings.functionmapping.getTarget（int）将抛出mappings.noelementexception。

MappingType类型：

public enum MappingType
extends java.lang.Enum<MappingType>

       描述映射的类型，从最一般的MULTI_FUNCTION函数（源域和目标域中的每个元素都可以参与许多映射）到最严格的双映射（源域和目标域中的每个元素都必须与另一个域中的一个元素精确配对）。

一些常见类型：

•     ONTO类型：每个目标至少有一个源，则满射是一个映射

•     PARTIAL_FUNCTION类型：每个源最多有一个目标

•     FUNCTION类型：每个源正好有一个目标

•     INJECTION类型：注入是一种映射，其中目标最多有一个源；因此有点混乱地称为一对一映射。

•     BIJECTION：双映射是一种既注入又回注的映射。每个源都有一个目标，反之亦然。

        一旦知道所需的映射类型，就调用mappings.create（mapping type，int，int）来创建该映射的有效实现。

/**
 * Returns a permutation describing where output fields come from. In
 * the returned map, value of {@code map.getTargetOpt(i)} is {@code n} if
 * field {@code i} projects input field {@code n}, -1 if it is an
 * expression.
 */
public static Mappings.TargetMapping permutation(
    List<RexNode> nodes,
    RelDataType inputRowType) {
  final Mappings.TargetMapping mapping =
      Mappings.create(
          MappingType.PARTIAL_FUNCTION,//如果每个源最多有一个目标，则映射是一个PARTIAL_FUNCTION类型。
          nodes.size(),//行表达式RexMode列表的大小。
          inputRowType.getFieldCount()//输入行类型的字段的个数
  );
  for (Ord<RexNode> node : Ord.zip(nodes)) {//引用字段序号和字段表达式之间的映射关系遍历
    if (node.e instanceof RexInputRef) {
      mapping.set(
          node.i,
          ((RexInputRef) node.e).getIndex());
    } else if (node.e.isA(SqlKind.CAST)) {//如是cast类型转换函数，则取第一个操作数
      RexNode operand = ((RexCall) node.e).getOperands().get(0);
      if (operand instanceof RexInputRef) {
        mapping.set(
            node.i,
            ((RexInputRef) operand).getIndex());
      }
    }
  }
  return mapping;
}

Ord类型：

        继承子Map实体的类，用于存放RexNode行表达式和在行中所在的序号。

public class Ord<E>
extends java.lang.Object
implements java.util.Map.Entry<java.lang.Integer,E>
Pair of an element and an ordinal.

zip函数生成一个Ord列表对象。

static <E> java.util.List<Ord<E>>   zip(E[] elements)
Returns a numbered list based on an array.
  //创建Ord对象
static <E> Ord<E>  of(int n, E e)
Creates an Ord.

        使用mapping对象和sort的RelCollation生成新的RelCollation排序信息。生成新Project，再使用新的Project生成新的Sort，相当于Project和Sort颠倒顺序。

// Create new collation
    final RelCollation newCollation =
        RelCollationTraitDef.INSTANCE.canonize(
            RexUtil.apply(map, sort.getCollation()));//Applies a mapping to a collation
    // New operators
    final RelNode newProject = project.copy(sort.getInput().getTraitSet(),
            ImmutableList.<RelNode>of(sort.getInput()));
    final HiveSortLimit newSort = sort.copy(newProject.getTraitSet(),
            newProject, newCollation, sort.offset, sort.fetch);//使Project做为子RelNode生成Sort，做两者顺序颠倒的变换
    call.transformTo(newSort);//注册
  }

        call.transformTo(newSort)做等价变换后注册到优化器。

总结

        内置的规则中也不是每条优化规则Rule都能保证对此RelNoe关系表达树式进行等价变换后都能减少成本Cost。每次等价交换后注册到RelNode等价关系表达RelNode集合中，由CBO通过计算成本模型CostModel和统计信息来计算成本，从选择最优的执行计划。

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

往期文章分享

优化规则系列

成本模型系列