Hive优化器原理与源码解析系列--优化规则SortJoinReduceRule(二)
目录
背景
优化规则SortJoinReduceRule
matches方法逻辑详解
onMatch方法逻辑详解
总结
背景
基于成本优化器CBO，常用的优化规则如子查询移除、相关性拆解、笛卡尔积加等值判断转换为内关联，谓词下推等等常用优化规则Rule。如谓词下推优化规则是将判断条件下推到数据源头，来加少中间结果，在成本优化器中，每个RelNode的中间结果大小即RowCount记录数大小决定一个RelNode的成本大小，（RowCount记录数是构成CostModel成本模型元素之一），此文讲述是HiveSort下推到HiveJoin下。也具有减少中间结果，降低一个RelNode关系表达式成本功能。在Hive中Sort操作符就代表在HQL中 SORT BY field LIMIT n 语句写法，上篇文章SortRemoveRule优化规则将由SortJoinReduceRule产生的SortLimit移除，详细可参考上篇文章Hive优化器原理与源码解析系列--优化规则SortRemoveRule(一)。
这期一系列文章都是在讲优化规则Rule，它们都统一继承了父类RelOptRule。
RelOptRule Calcite框架中的优化规则Rule的抽象类，功能就是把一个关系表达式RelNode1转换为另一个关系表达式RelNode2，它有一系列RelOptRuleOperands，其决定了此Rule是否能被应用到一棵RelNodes操作符的指定部分section，由optimizer优化器指出哪些Rule是可应用的，然后在这些Rules规则上调用onMatch（RelOptRuleCall）方法。RelNode关系表达式暂时不熟悉的没关系，可理解为查询SQL的另一种等价的表示。
RelOptRuleCall是对优化规则Rule的调用，其使用一系列RelNode关系表达式集合作为参数，对RelOptRule优化规则的调用。匹配上优化规则内一系列RelOptRuleOperands操作数，也代表了优化规则Rule配上了输入参数RelNode树的某些子RelNode，可进行优化。
优化规则SortJoinReduceRule
Hive源码中实现的优化规则Rule，几乎都是继承了父类RelOptRule，也需实现两个方法matches和OnMatch两个方法。matches默认实现返回true。
matches方法返回此规则Rule是否可能与给定的操作数operands匹配。此方法是一个将附加条件是否能应用于规则Rule的机会的判断。优化器在匹配上规则Rule的所有操作数Operands之后和调用OnMatch（ReloptRuleCall）之前调用此方法。
在优化器的实现中，它可能会在调用OnMatch（ReloptRuleCall）之前将匹配的ReloptRuleCall排队很长时间，matches方法提前判断这种方法是有好处的，因为优化器可以在处理的早期，把不满足匹配条件的规则放弃掉。
此方法的任何实现都可以给出误报，也就是说，规则与操作数匹配，但随后具有OnMatch（ReloptRuleCall）而不生成任何后续任务。
1）matches方法逻辑详解
判断由RelOptCall调用的优化规则Rule是否与输入参数RelNode关系表达式匹配，即此优化规则Rule能否应用到一个RelNode关系表达式树上。SortJoinReduceRule的判断条件如下：
1）Sort操作符没有LIMIT操作或LIMIT=0，说明Sort操作获取全部记录数或一条记录都不获取，这样没有优化空间，则放弃优化。
2）一个RelNode操作符树中必须是Left Join 或 Right Join关联方式，这两种关联方式，下推Sort不会影响最终的结果。
3）LIMIT必须满足达到减少记录数目标，否则也没达到减少中间结果的优化意义，则放弃优化
4）如果任何排序列必须是推送Sort操作符的输入的一部分，也即如果LeftJoin则需对左输入数据字段的Sort by Limit操作，如果是Right Left则需对左输入数据字段的Sort by Limit操作。
public boolean matches(RelOptRuleCall call) {
final HiveSortLimit sortLimit = call.rel(0);
final HiveJoin join = call.rel(1);
//如果sort 不包含 limit 操作或limit 0，此规则失败。没有limit 或 limit =0 都不取或都是取全部，不然没有下推的意义。
//limit 减少的 不多没有优化的意义，就相当于limit all或没有limit。
if (!HiveCalciteUtil.limitRelNode(sortLimit) ||
RexLiteral.intValue(sortLimit.fetch) == 0) {
return false;
}
//此规则必须适用left或right外连接，才可适用，
//如果任何sort column列不是我们下推的输入排序列的一部分，将会失败。sort by指定的列，下推也是输入排序的列
RelNode reducedInput;
if (join.getJoinType() == JoinRelType.LEFT) {//Join为左关联的
reducedInput = join.getLeft();
if (sortLimit.getCollation() != RelCollations.EMPTY) { //必须指定排序的
for (RelFieldCollation relFieldCollation
: sortLimit.getCollation().getFieldCollations()) {//遍历每个列的排序关系
if (relFieldCollation.getFieldIndex()
>= join.getLeft().getRowType().getFieldCount()) {//如果排序列的索引（序号，从0开始的表示），大于join 左侧RelNode的字段总数，说明这里里面还有右侧RelNode的排序字段，优化退出，即不能左右两侧RelNode，只能是一个Input输入的一部分。
return false;
}
}
}
} else if (join.getJoinType() == JoinRelType.RIGHT) {//右连接，
reducedInput = join.getRight();
if (sortLimit.getCollation() != RelCollations.EMPTY) {
for (RelFieldCollation relFieldCollation
: sortLimit.getCollation().getFieldCollations()) {
if (relFieldCollation.getFieldIndex()
< join.getLeft().getRowType().getFieldCount()) {//排序列的索引必须大于 左侧 RelNode的总数的位置上，否退出。另外如果不是左右关联都会失败
return false;
}
}
}
} else {
return false;
}
//最后，如果不是我们没有减少input的大小，，退出优化
final int offset = sortLimit.offset == null ? 0 : RexLiteral.intValue(sortLimit.offset);
if (offset + RexLiteral.intValue(sortLimit.fetch)
>= RelMetadataQuery.instance().getRowCount(reducedInput)) {
return false;
}
return true;
}
这是SortJoinReduceRule优化规则应用满足包括并不限于的四个条件。其中，RelOptRuleCall对象是RelNode调用，如：
final HiveSortLimit sortLimit = call.rel(0);final HiveJoin join = call.rel(1);
顶部rel(0)代表HiveSortLimit操作符，顶部rel(1)代表HiveJoin操作符。onMatch方法会把Sort下推到Join下。
2）onMatch方法逻辑详解
首先获取Join操作符左右两侧的RelNode inputLeft和inputRight，根据判断是Left Join还是Right Join，使用原sortLimit的特征集合TraitSet、Left或者Right输入侧RelNode、排序信息、offset、fetch等信息，重新生成新SortLimit，并达标为此RelNode是Rule创建的。强调的是，在操作符树上，SortLimit是Join的根，在其顶部。
然后，使用新生成的SortLimit作为子RelNode和原Join的信息拷贝生成新Join。此时新Join操作符相当于对SortLimit进行了下推。同时，再使用新Join作为子RelNode构造一个SortLimit。根RelNode SortLimit不变，把SortLimit复制一份下推到Join下。如：
原Sort
Sort |
| --> 原Join
Join |
新Sort
上述表示一个等价变换的RelNode关系表达式操作符Operator树，把原Sort下推到原Join下，但是原Sort还继续保留，上篇文章SortRemoveRule优化规则就是对根部原Sort的删除优化。
public void onMatch(RelOptRuleCall call) {final HiveSortLimit sortLimit = call.rel(0);
final HiveJoin join = call.rel(1);
RelNode inputLeft = join.getLeft(); //join 左侧RelNode
RelNode inputRight = join.getRight();//join 右侧RelNode
if (join.getJoinType() == JoinRelType.LEFT) {
inputLeft = sortLimit.copy(sortLimit.getTraitSet(), inputLeft,
sortLimit.getCollation(), sortLimit.offset, sortLimit.fetch);
//使用原sortLimit的 特征集合、Left的RelNode、排序、offset、fetch生成新的sortLimit对象
((HiveSortLimit) inputLeft).setRuleCreated(true); // 标志此SortLimit是由优化规则Rule产生的
} else {//如果是右连接
final RelCollation rightCollation =
RelCollationTraitDef.INSTANCE.canonize(
RelCollations.shift(sortLimit.getCollation(),
-join.getLeft().getRowType().getFieldCount()));
//shift，字段索引向右偏移offset数，这里-负号，代表左偏移，在左侧RelNode列数的基础，移到从0开始
inputRight = sortLimit.copy(sortLimit.getTraitSet().replace(rightCollation), inputRight,
rightCollation, sortLimit.offset, sortLimit.fetch);
//使用调整后排序，生成新的sortLimit并标识为规则生成的RelNode
((HiveSortLimit) inputRight).setRuleCreated(true);
}
// We copy the join and the top sort operator
RelNode result = join.copy(join.getTraitSet(), join.getCondition(), inputLeft,
inputRight, join.getJoinType(), join.isSemiJoinDone());
//inputLeft 和 inputRight两者其中之一是新生成的带有SortLimit的左侧或右侧的RelNode，这样复制一个带子RelNode带有SortLimit的Join
result = sortLimit.copy(sortLimit.getTraitSet(), result, sortLimit.getCollation(),
sortLimit.offset, sortLimit.fetch);
// 这里把新的Join从新生成了SortLimit注册到优化器，结合上篇文章SortRemoveRule，就会把根SortLimit移除掉，只保留了Join下的SortLimit
call.transformTo(result);
}
onMatch方法接收有关一条规则匹配上的通知。同时此方法被调用，call.rels保存了与规则Rule的操作数Operands匹配上的关系表达式RelNode集合；call.rels[0]是根表达式。
通常一条规则Rule会检查这些节点是否有效匹配，创建一个新表达式RelNode，然后调用RelOptRuleCall.transformTo(org.apache.calcite.rel.RelNode,java.util.Map<org.apache.calcite.rel.RelNode,org.apache.calcite.rel.RelNode>)注册表达式。
总结
在优化规则Rule中，是通过matches方法来实现优化规则Rule是否与RelNode树的特定部分匹配上的判断条件。
matches满足了匹配条件后，onMatch再去相应的等价变换动作，产生新的RelNode，再使用RelOptRuleCall.transformTo方法把新RelNode注册到优化器。优化器再根据CostModel成本模型和统计信息，使用动态规划算法构建出最优执行计划。
由于笔者知识及水平有限,因此文中错漏之处在所难免,恳请各位老师、专家不吝赐教。
往期文章分享
Hive优化器原理与源码解析系列—统计信息带谓词选择率Selectivity
Hive优化器原理与源码解析系列--统计信息中间结果大小计算
Hive优化器原理与源码解析系列—CBO成本模型CostModel(一)
Hive优化器原理与源码解析系列—CBO成本模型CostModel(二)
Hive优化器原理与源码解析系列—统计信息UniqueKeys列集合
Hive优化器原理与源码解析—统计信息Parallelism并行度计算
Hive优化器原理与源码解析系列--优化规则SortRemoveRule(一)