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

目录

背景

优化规则SortMergeRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

上篇文章分享了基于成本优化器CBO可插拔式优化规则SortUnionReduceRule优化规则，Sort操作符下推到Union操作符的优化规则，想详细了解的可翻阅往期文章（在文章结尾有相关链接）。此篇文章讲解SortMergeRule优化规则，把重复的Sort操作去除的优化规则。把外层仅有的Limit操作合并到内部SortLimit操作，最终Limit限制记录数大小，要通过内外部Limit的offset和rows返回总记录大小来判定，为了说明方便，这里使用SQL进行讲述，举例说明：

原SQL

   SELECT id FROM (

      SELECT id FROM tab1 SORT BY a.id  LIMIT offset,rows;

   ) a  LIMIT M;

等价变化后SQL：

   SELECT id FROM t1 SORT BY id LIMIT offset,rows

        其实优化器内部使用的RelNode关系表达式构造的操作符树组成。将顶层（或外部的）SortLimit操作符（仅有Limit没有排序的SortLimit）合并到每个子RelNode的SortLimit。等价变换后的RelNode会注册到优化器的。优化器在RelSet等价集合内看到这等价变换后的RelNode不保证一定会使用，优化器会根据RelSet中RelNode关系表达式成本进行计算，动态规划算法综合考虑需要构建的执行计划，会从中选择一个最优的执行计划。

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

优化规则SortMergeRule

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

1）matches方法逻辑详解

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

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

• 顶部的Sort操作符是纯LIMIT操作，没有排序操作，且不是由其他优化规则Rule创建的，否则放弃优化。

• 底部的Sort操作符存在LIMIT操作，fetch不为null，否则放弃优化。

• 底部的Sort操作符必须是由优化规则Rule创建的，否则放弃优化。

public boolean matches(RelOptRuleCall call) {
   final HiveSortLimit topSortLimit = call.rel(0); //顶SortLimit
   final HiveSortLimit bottomSortLimit = call.rel(1);//底部SortLimit

   // If top operator is not a pure limit, we bail out
   if (!HiveCalciteUtil.pureLimitRelNode(topSortLimit)) {//判断是否纯limit的RelNode
     return false;
  }
   // If the bottom operator is not synthetic and it does not contain a limit,
   // we will bail out; we do not want to end up with limits all over the tree
   //如果底部操作符不是合成的，并且不包含限制，那么我们将退出；
   if (topSortLimit.isRuleCreated() && !bottomSortLimit.isRuleCreated() &&
           !HiveCalciteUtil.limitRelNode(bottomSortLimit)) {//必须不仅仅包含limit，顶部SortLimit规则创建的，不是底部SortLimit创建的，则优化退出
     return false;
  }
   return true;
}

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

2）onMatch方法逻辑详解

此方法最关键的步骤，是把顶层SortLimit操作fetch和offset通过与底部的SortLimit操作的fetch和offset的比较来确定最终合并的SortLimit的fetch和offset的大小，再使用底部SortLimit的特征集合、排序信息等，等价变换后一个新RelNode注册到优化器。

同样，首先使用RelOptRuleCall对象rel(0)方法获取根RelNode关系表达式SortLimit，其次获取SortLimit的子RelNode关系表达式SortLimit。并获取顶层SortLimmit和底部SortLimit的fetch和offset（为null，默认赋值为0），通过两者各自参数的比较来生成合并后的新SortLimit的fetch和offset。

(1) 在底部是SortLimit并fetch不为null的条件下，又分三种情况：

    a. 顶层offset + 顶层fetch <= 底部Limit

             合并offset = 底部offset + 顶层offset

              合并fetch = 顶层fetch

    b. 顶层offset  <= 底部Limit

    合并offset = 底部offset + 顶层offset

    合并fetch = 底部Limit - 顶层fetch

    c. 其他

             合并offset = null

             合并fetch = 0

(2) 如果底部不是SortLimit的，则使用顶层SortLimit的fetch和offset参数，即

              合并offset = 顶层offset

              合并fetch = 顶层fetch

    之后再使用顶部SortLimit相关的参数和上述新计算的合并offse和合并fetch生成，生成合并后的新SortLimit，注册到优化器

public void onMatch(RelOptRuleCall call) {
   final HiveSortLimit topSortLimit = call.rel(0);
   final HiveSortLimit bottomSortLimit = call.rel(1);

   final RexNode newOffset;
   final RexNode newLimit;
   if (HiveCalciteUtil.limitRelNode(bottomSortLimit)) {//底部SortLimit
     final RexBuilder rexBuilder = topSortLimit.getCluster().getRexBuilder();
     //分别去顶部和底部SortLimit中 offset fetch
     int topOffset = topSortLimit.offset == null ? 0 : RexLiteral.intValue(topSortLimit.offset);
     int topLimit = RexLiteral.intValue(topSortLimit.fetch);
     int bottomOffset = bottomSortLimit.offset == null ? 0 : RexLiteral.intValue(bottomSortLimit.offset);
     int bottomLimit = RexLiteral.intValue(bottomSortLimit.fetch);
     // Three different cases
     if (topOffset + topLimit <= bottomLimit) {  //如果顶部的offset + fetch 小于 底部的fetch，则新offset = 底部offset + 顶部offset。新fetch = 顶部fetch。取得最小的limit和最大offset
     // 1. Fully contained
     // topOffset + topLimit <= bottomLimit
       newOffset = bottomOffset + topOffset == 0 ? null :
         rexBuilder.makeExactLiteral(BigDecimal.valueOf(bottomOffset + topOffset));
       newLimit = topSortLimit.fetch;
    } else if (topOffset < bottomLimit) {  // 如果 顶部offset 小于 底部fetch，则新offset = 底部offset + 顶部offset，新fetch = 底部fetch - 顶部offset
       // 2. Partially contained
       // topOffset + topLimit > bottomLimit && topOffset < bottomLimit
       newOffset = bottomOffset + topOffset == 0 ? null :
         rexBuilder.makeExactLiteral(BigDecimal.valueOf(bottomOffset + topOffset));
       newLimit = rexBuilder.makeExactLiteral(BigDecimal.valueOf(bottomLimit - topOffset));
    } else { // 其他 新offset = null；新fetch = 0；
       // 3. Outside
       // we need to create a new limit 0
       newOffset = null;
       newLimit = rexBuilder.makeExactLiteral(BigDecimal.valueOf(0));
    }
  } else {
     // Bottom operator does not contain offset/fetch
     newOffset = topSortLimit.offset; //优先底部Sort中的Limit，如果底部不是纯limit，则使用顶部的Sort offset fetch
     newLimit = topSortLimit.fetch;
  }
   final HiveSortLimit newSort = bottomSortLimit.copy(bottomSortLimit.getTraitSet(),
           bottomSortLimit.getInput(), bottomSortLimit.collation, newOffset, newLimit); //使用底部SortLimit，再加上由底部SortLimit和顶部SortLimit的新生成offset 和 fetch合并，新生成的SortLimit注册到优化器去优化器
   call.transformTo(newSort);
}

        代码最后的newSort的生成，用底部SortLimit的TraitSet特征集合（是否是分布式，是否排序等物理特性的集合），bottomSortLimit.getInput()底部SortLimit的输入RelNode和排序信息bottomSortLimit.collation，以及上述讲到的新生成的newOffset, newLimit变量复制的SortLimit对象newSort，用call.transformTo(newSort)注册到优化器。

总结

        SortMergeRule优化规则把SQL中最外层Sort操作符（包括Sort by Limit或 Order by Limit从句在底层实现都是一个Sort操作符来完成）仅有Limit N没有排序信息，合并到内部的SortLimit的SQL子句中。这些RelNode关系表达式变换的前提，都是基于关系代数等价变换的，把变换后新生成的RelNode注册到优化器，优化器从等价的关系表达式集合RelSet取RelNode，通过CosModel成本模型和统计信息，计算一个RelNode成本，再使用动态规划算法，综合地构建最优的执行计划。

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

往期文章分享

优化规则系列

成本模型系列