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

目录

背景

优化规则SortUnionReduceRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

上篇文章分享了基于成本优化器CBO可插拔式优化规则SortJoinReduceRule把Sort下推到Join的优化规则，不熟悉的可翻阅往前文章（文章底部有往期文章链接）。

        此篇文章讲解SortUnionReduceRule优化规则，优化思路是将Sort操作符下推到Union操作符下，由全局的Sort转换为Union各个子RelNode的Sort操作，其中也不是Sort下推到所有子RelNode，还要经过优化条件的判断，条件满足了再相关等价变换。为了说明方便，这里使用SQL进行讲述，其实优化器内部使用的RelNode关系表达式构造的操作符树组成。将Sort操作符下推到每个子RelNode。但保留了顶层的Sort操作符。

举例说明：

• 原SQL

        SELECT id FROM (

          SELECT id FROM table1

          UNION ALL

          SELECT id FROM table2

           UNION ALL

           SELECT id FROM tablet3

        ) a SORT BY a.id LIMIT 1000;

• 等价变换后SQL：

     SELECT id FROM (

           SELECT id FROM table1 SORT BY id LIMIT 1000

           UNION ALL

           SELECT id FROM table2

           UNION ALL

           SELECT id FROM table3 SORT BY id LIMIT 1000

      ) a SORT BY a.id LIMIT 1000;

        其中子RelNode关系表达式SELECT id FROM table2，再没满足相关条件则在没有Sort下推。等价变换后的RelNode会注册到优化器的。优化器在RelSet等价集合内看到这等价变换后的RelNode不保证一定会使用，优化器会根据RelSet中RelNode关系表达式成本进行计算，用动态规划算法综合考虑需要构建的执行计划，会从中选择一个最优的执行计划。

Hive几乎所有优化规则Rule继承了父类RelOptRule。关于RelOptRule和RelOptRuleCall相关概念前期文章都有详细阐述，这里不再赘述，自行翻阅前期文章（文章底部有前期文章相关链接）。所有优化规则Rule都需实现两个方法matches和OnMatch两个方法。matches默认实现返回true。每个优化规则Rule都会有自己的判断逻辑和等价变换逻辑，关于两个方法实现实现逻辑下文会进行详细说明。

优化规则SortUnionReduceRule

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

1）matches方法逻辑详解

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

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

• Sort操作符LIMIT操作fetch大于0，否则放弃优化。

• Union操作符的判断。在SQL中，如果只使用了Union，默认是Union Distinct的去重复的合并操作。必须是Union ALL，不去重复的Union合并操作，否则放弃优化。

public boolean matches(RelOptRuleCall call) {
    final HiveSortLimit sort = call.rel(0);
    final HiveUnion union = call.rel(1);
    // We only apply this rule if Union.all is true.
    // And Sort.fetch is not null and it is more than 0.
    return union.all && sort.fetch != null
        // Calite bug CALCITE-987
        && RexLiteral.intValue(sort.fetch) > 0;
  }

        这里matches方法判断逻辑相对简单，即Union去重复合并和Limit限制条数N大于0即可满足匹配条件。matches方法匹配是有可能执行优化等价变换的前提。

2）onMatch方法逻辑详解

在讲解onMatch方法之前，这里先讲一下HSQL在Hive2.0以后版本的Limit offset,N写法。

SELECT [ALL | DISTINCT] select_expr, select_expr, ...

  FROM table_reference

  [WHERE where_condition]

  [GROUP BY col_list]

  [ORDER BY col_list]

  [CLUSTER BY col_list

    | [DISTRIBUTE BY col_list] [SORT BY col_list]

  ]

 [LIMIT [offset,] rows]

• offset为返回第一条记录前，丢弃的记录数，偏移量

• rows为返回限制的记录数
  

举例说明：消费者信息表customers

• 根据消费者创建时间create_date排序，取前5名消费者信息
  

    SELECT * FROM customers ORDER BY create_date LIMIT 5

• 根据消费者创建时间create_date排序，取第3名开始5名消费者信息，即第3名到第7名，5名消费者信息。

SELECT * FROM customers ORDER BY create_date LIMIT 2,5

这里offset为2，返回前丢弃前2条记录，从第3条记录开始。

        那么onMatch优化逻辑，同样首先使用RelOptRuleCall对象rel(0)方法获取根RelNode关系表达式SortLimit，其次获取SortLimit的子RelNode关系表达式Union。

        这里使用了对操作树逻辑重写的优化，遍历Union的子输入RelNode，如上文提到SELECT id FROM table1为Union的子输入RelNode。首先会判断每个子输入记录数是否大于Sort的limit + offset（返回前丢弃的记录数，同样要花费成本来取值，只是在返回时丢弃了，所以要加上offset偏移量），如果大于说明还有优化的空间，否则直接跳过此子输入RelNode的原封不动存在Union子RelNode列表。如

SELECT id FROM (

           SELECT id FROM table1 SORT BY id LIMIT 1000

           UNION ALL

           SELECT id FROM table2

           UNION ALL

           SELECT id FROM table3 SORT BY id LIMIT 1000

      ) a SORT BY a.id LIMIT 1000;

SELECT id FROM table2为没有满足优化条件，limit 1000 大于 table2的总记录数RowCount则，没Sort下推意义了。

        如果满足优化条件，在重写时会设置标示位finishPushSortPastUnion=false说明对子输入RelNode进行了优化重写，重写的逻辑是把Sort的fetch+offset作为新Sort的fetch。并下推到子RelNode，即如，SELECT id FROM table1 SORT BY id LIMIT 1000。

        遍历完Union所有子RelNode后，并判断是否有子RelNode完成重写并下推。如果finishPushSortPastUnion=true，则说明没有满足优化条件，没有优化空间，退出优化。

public void onMatch(RelOptRuleCall call) {
    final HiveSortLimit sort = call.rel(0);
    final HiveUnion union = call.rel(1);
    List<RelNode> inputs = new ArrayList<>();
    // Thus we use 'finishPushSortPastUnion' as a flag to identify if we have finished pushing the
    // sort past a union.
    boolean finishPushSortPastUnion = true;
    final int offset = sort.offset == null ? 0 : RexLiteral.intValue(sort.offset);//如果返回前丢弃的offset为null，默认为0，否则为本身
    for (RelNode input : union.getInputs()) { //这里遍历Union的每个子RelNode
      // If we do not reduce the input size, we bail out
      //因为每个子RelNode的输入记录数
      if (RexLiteral.intValue(sort.fetch) + offset < RelMetadataQuery.instance().getRowCount(input)) { //如果两者之和 小于总记录数
        finishPushSortPastUnion = false;
        // Here we do some query rewrite. We first get the new fetchRN, which is
        // a sum of offset and fetch.
        // We then push it through by creating a new branchSort with the new
        // fetchRN but no offset.
        RexNode fetchRN = sort.getCluster().getRexBuilder()
            .makeExactLiteral(BigDecimal.valueOf(RexLiteral.intValue(sort.fetch) + offset));
        HiveSortLimit branchSort = sort.copy(sort.getTraitSet(), input, sort.getCollation(), null,
            fetchRN);//创建一个新的SortLimit，这里offset为null
        branchSort.setRuleCreated(true);//并设置为是由Rule创建的RelNode标识
        inputs.add(branchSort);//把每个子RelNode加入到Union的集合
      } else {
        inputs.add(input);
      }
    }
    // there is nothing to change
    if (finishPushSortPastUnion) {//如果优化失败，则什么都不做，不会去任何优化操作
      return;
    }
    // create new union and sort
    HiveUnion unionCopy = (HiveUnion) union.copy(union.getTraitSet(), inputs, union.all);//all
    HiveSortLimit result = sort.copy(sort.getTraitSet(), unionCopy, sort.getCollation(), sort.offset,
        sort.fetch);//把新产生Union添加的SortLimit下，注册到优化器。//这里最顶层的SortLimit其实没有去掉，不会影响最终的结果，不会出现1000 变 3000的情况。
    call.transformTo(result);
  }

        最后步骤是Union操作符将重写的下推了Sort的新子RelNode，生成新Union。新生成Union做Sort的子RelNode生成新Sort，保持了原RelNode是等价变换。注册到优化器。

总结

        SortUnionReduceRule优化规则遍历Union下各个输入的子RelNode，判断Sort Limit限制的记录数是否大于子RelNode记录数，大于则说明取子RelNode总记录数的全部，已经没必要进行下推了，跳过此子RelNode的重写优化。对满足条件的子RelNode关系表达式进行Sort下推重写，如果全都不满足则跳出优化。

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

往期文章分享

优化规则系列

成本模型系列