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

目录

背景

优化规则HiveJoinCommuteRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

        此篇文章讲解HiveJoinCommuteRule优化规则，此优化规则Rule主要功能是通过改变Join左右两侧的输入RelNode的顺序来试图探索可优化的执行计划。但前提是对Join关联操作之上Project投影操作的RelNode树，形如：

亦可用SQL表示,有表TA和TB两张表，分别含有字段如下：

• TA:a0,a1

• TB:b0,b1,b2

如：

        SELECT a0,a1,b0,b1

        FROM TA JOIN TB ON TA.a0 = TB.b0

转化为

        SELECT a0,a1,b0,b1

        (

            SELECT b0,b1,a0,a1

            FROM TB JOIN TA ON TA.a0 = TB.b0

        )

        上述SQL是对执行计划等价变换的描述。就可通过改变TA JOIN TB 为TB JOIN TA来优化逻辑执行计划，在物理实现的过程中，如果Join物理层算法实现是Nest Loop算法，改变了左右两表的顺序，是可以减少IO次数的，IO次数也是影响执行效率的因素之一，同时IO也是CBO基于成本优化器成本模型CostModel元素之一。如果Join物理层算法实现是Hash Join或Sort Merge Join算法改变顺序，将“小的”输入进行hash或进行分桶来减少计算成本。

        此Hive优化规则是对Apache Calcite框架优化相关模块中的优化规则RelOptRule父类的实现，继承了matches方法，实现了onMatch方法，但是Calcite中是有JoinCommuteRule优化规则的，但是本规则没有完全继承它，只是使用了swap方法，改变了Join左右两侧的输入的顺序。

优化规则HiveJoinCommuteRule

        优化器的优化规则Rule实现，都需实现两个方法matches和OnMatch两个方法。

1）matches方法逻辑详解

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

        判断由RelOptCall调用的优化规则Rule是否与输入参数RelNode关系表达式匹配，即此优化规则Rule能否应用到一个RelNode关系表达式树上。但此matches方法是继承自父类方法，默认返回true。

public boolean matches(RelOptRuleCall call) {
  return true;
}

2）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>)注册表达式。而RelOptRuleCall用一系列RelNode关系表达式集合作为参数，对RelOptRule优化规则的调用。

       讲解此方法实现逻辑之前，补一点《离散数学》置换和恒等置换的知识：

定义. 

设M是一个非空的有限集合，M的一个一对一变换称为一个置换。设M={a1,a2,…,an},则M的置换σ可简记为

   σ：

bi=σ(ai)，i=1,2,…,n

结论：M的置换共有n！个。M上的置换称为n元置换。特别地， 若σ(ai)=ai, i=1,2,…,n,则σ为n元恒等置换。Sn: n！个置换作成的集合。

恒等置换：

置换在这里仅仅用来表示输入和输出字段索引序号的映射关系。接下来开始onMatcch方法实现逻辑讲解。

        首先，用call.rel(0)获取顶层Project投影操作，其次，call.rel(1)获取子输入Join操作。

        开始判断Project投影字段的置换topPermutation不为null，则说明它仅仅是输入字段的置换；值为null，则不做任何优化。同样，该字段索引的置换如果为恒等置换，也不做任何优化。

Project topProject = call.rel(0);
Join join = call.rel(1);
final Permutation topPermutation = topProject.getPermutation();
/**
 * 如果投影Project仅仅是它输入字段的置换。则返回该置换，如果不是，则返回null
 */
if (topPermutation == null) { //这里说明是单射、满射或双射，而不是一对多非置换了
  return;
}
if (topPermutation.isIdentity()) {//恒等置换，自身到自身的置换
  return;
}

        HiveJoinCommuteRule优化规则没直接使用Calcite的优化规则JoinCommuteRule的逻辑，仅仅只是使用了swap方法把Join左右两侧输入进行调换实现。

public static RelNode swap(Join join, boolean swapOuterJoins)

Returns a relational expression with the inputs switched round. Does not modify join. Returns null if the join cannot be swapped (for example, because it is an outer join).

• Parameters:

  join - join to be swapped

  swapOuterJoins - whether outer joins should be swapped

• Returns:

  swapped join if swapping possible; else null

        如果参数join的输入顺序没有改变则返回null。其次需要一个Project投影保证其字段的顺序，如果没project，将不做任何优化。

        获取到改变Join的输入顺序后，对swapped的Project进行，同上的判断，如果返回Project不是输入字段索引的置换，或该字段索引的置换为恒等置换，则不做任何优化。

//To preserve the order of columns in the output row, the rule adds a Project.
final RelNode swapped = JoinCommuteRule.swap(join,true);
if (swapped == null) {//如join输入顺序没改变，则为null
  return;
}
if (swapped instanceof Join) {//如果没Project，而是Join的话，直接退出优化
  return;
}
//转后join输入的顺序后的添加的Project投影操作
final Project bottomProject = (Project) swapped;
final Permutation bottomPermutation = bottomProject.getPermutation();
if (bottomPermutation == null) {
  return;
}
if (bottomPermutation.isIdentity()) {
  return;
}

注意：JoinCommuteRule.swap(join,true)，第二参数为true，说明这里支持外连接输入顺序的交换。

最后，顶层Project投影置换topPermutation与join变换输入顺序在顶层添加的Project投影的置换bottomPermutation的乘积的结果为恒等置换则说明可以做等价变换的优化。bottomProject.getInput(0)移除底部Project投影操作，产生新Join注册到优化器。

// 5. If the product of the topPermutation and bottomPermutation yields
//    the identity, then we can swap the join and remove the project on
//    top.
final Permutation product = topPermutation.product(bottomPermutation);
if (!product.isIdentity()) {//如果不是恒等置换，则不做任何优化。
  return;
}
// 6. Return the new join as a replacement
final Join swappedJoin = (Join) bottomProject.getInput(0);
call.transformTo(swappedJoin);

总结

        HiveJoinCommuteRule优化规则通过Join的输入顺序来达到优化目标，这是蛮成熟的一条优化规则，Oracle，SQL Server，Mysql都此相应的JoinCommuteRule优化规则。

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

往期文章分享

优化规则系列

成本模型系列