目录
背景
优化规则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，则说明没有满足优化条件，没有优化空间，退出优化。
代码语言：javascript复制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下推重写，如果全都不满足则跳出优化。
