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

Original 后羿BigDataplus BigDataplus 2021-10-15

背景

优化规则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成本，再使用动态规划算法，综合地构建最优的执行计划。

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

往期文章分享

优化规则系列

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

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

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

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

成本模型系列

Hive优化器原理与源码解析系列—统计信息带谓词选择率Selectivity

Hive优化器原理与源码解析系列—统计信息之选择性

Hive优化器原理与源码解析系列—统计模块内存成本估算

Hive优化器原理与源码解析系列--统计信息中间结果大小计算