hive优化器（1）

大数据启示录 2022-08-21

388

背景

目前，数据库优化器分两种，一种是基于规则优化器；另一种是基于成本优化器，这两种优化器各有千秋。但现在大部分成熟的数据库优化器都是两种优化器结合起来使用，这样做为了优化器在执行计划Plan的构建速度和准确性之间找到一个好的平衡点。

下面介绍一下两种优化器特性：

基于规则的优化器(RBO，Rule-Based Optimizer)
根据预先准备好的优化规则rule，不考虑数据动态变化，在关系表达式等价转换的前提下，对符合匹配规则条件的关系表达式，替换掉原来的关系表达式，达到优化的目的。
基于成本的优化器(CBO，Cost-Based Optimizer)
根据预先准备好的优化规则rule，在关系表达式等价转换的前提下，对符合匹配规则条件的关系表达式，保留原来的关系表达式并把匹配上新关系表达式加入等价关系表达式集合，根据成本模型和统计信息和算法（Calcite使用的是动态规划算法），从等价关系表达式集合，构建出成本最优执行计划
这里再简单讲述CBO优化器如何对一个SQL使用优化规则Rule，进行优化的。根据预先准备好的优化规则Rule加载规则队列RuleQueue，在关系表达式等价转换的前提下，对符合匹配规则Rule内Operands匹配条件的关系表达式RelNode（一个SQL操作符树表示），保留原来的关系表达式并把匹配上新关系表达式注册到RelSet等价关系表达式集合，CBO根据成本模型CostModel和统计信息，并使用算法（Calcite使用的是动态规划算法），从RelSet等价关系表达式集合，构建出成本最优执行计划。优化规则Rule是优化器能对一个RelNode关系表达式，判断是否满足变换匹配条件并做出等价变换Transfer动作的关键。足见优化规则Rule的重要性。

SortRemoveRule

SortRemoveRule:是移除由SortLimit由HiveSortJoinReduceRule创建的操作符的优化规则。

核心方法和属性：

1）SortRemoveRule两个属性：

reductionProportion预设的SortLimit限制的减少比例
reductionTuples预设的SortLimit减少记录数

这两个参数是构造SortRemoveRule对象需要初始化的，也是作为是否满足优化条件判断条件之一。

2）matches方法返回此规则Rule是否可能与给定的操作数operands匹配的判断，此方法是一个将附加条件应用于规则的机会。

3）OnMatch方法

接收有关一条规则Rule匹配的通知后，同时此方法被调用，call.rels保存了与规则Rule的操作数Operands匹配上的关系表达式RelNode集合；

public void onMatch(RelOptRuleCall call) {
 final HiveSortLimit sortLimit = call.rel(0);//根关系表达式
  We remove the limit operator
 call.transformTo(sortLimit.getInput());//转换并注册，传递的是HiveSortLimit输入跳过了根，移除HiveSortLimit
}

总结：

SortRemoveRule优化规则是移除由SortLimit由HiveSortJoinReduceRule创建的操作符的优化规则。

优化规则Rule就是在等价变换的前提下把一个关系表达式RelNode1转换为另一个关系表达式RelNode2。它有一系列RelOptRuleOperands，其决定了此Rule是否能被应用到一棵RelNodes操作符数的指定部分Section，由optimizer优化器指出哪些Rule是可应用的，然后在这些Rules规则上调用onMatch（RuleCall）方法。这些等价变换的等价集合即使注册到优化器，优化器也因某些原因全部会进行优化，比如其他规则Rule达到了优化成本的预期，则会停止优化；再如优化的空间不大，优先级较低，排队时间太长等等因素。这些优化规则匹配上的等价交换的RelNode注册到优化器构建最优的执行计划选择。

SortJoinReduceRule

SortJoinReduceRule:主要优化方法对Sort Join 写法，把Sort操作符下推到Join以下，来达到优化的目的

核心方法和属性：

1）matches方法逻辑详解

matches方法返回此规则Rule是否可能与给定的操作数operands匹配。此方法是一个将附加条件是否能应用于规则Rule的机会的判断。优化器在匹配上规则Rule的所有操作数Operands之后和调用OnMatch（ReloptRuleCall）之前调用此方法。

即此优化规则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操作。

2）onMatch方法逻辑详解 onMatch方法会把Sort下推到Join下。

首先获取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下。

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成本模型和统计信息，使用动态规划算法构建出最优执行计划。

SortProjectTransposeRule

SortProjectTransposeRule:Sort排序和Project投影操作（相当于HSQ中的Select操作）的调换顺序的优化规则。

核心方法和属性：

1）matches方法
matches方法返回此规则Rule是否可能与给定的操作数operands匹配。优化器在匹配上规则Rule的所有操作数Operands之后和调用OnMatch（ReloptRuleCall）之前调用此方法。

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

Sort操作符没有LIMIT操作0，说明Sort操作获取全部记录数，这样没有优化空间，则放弃优化。其他则返回true。

2）onMatch方法

首先使用RelOptRuleCall对象rel(0)方法获取根RelNode关系表达式SortLimit，其次获取SortLimit的子RelNode关系表达式Project。确定Project投影的输入和输出字段之间的映射。RelOptUtil.permutation方法返回描述输出字段来源的排列。在返回的映射中，如果字段i投影输入字段n，则map.getTargetOpt（i）的值为n；如果是表达式，则为-1。如果为-1，这里不做任何优化的事情。使用生成新的RelCollation排序信息，新成的SortLimit，再使用新的SortLimit生成新的Project，相当于SortLimit和Project颠倒顺序。onMatch方法的底部，是对一个RelNode做了等价变化后，注册到优化器的，这里是把新生成SortLimit放到新生成的Project之下作为Project的子RelNode。

总结：

Sort排序和Project投影操作（相当于HSQ中的Select操作）的调换顺序的优化规则。把原RelNode做了等价变化，新产生RelNode注册到优化器，使用动态规划算法构建出最优的执行计划。

SortUnionReduceRule

SortUnionReduceRule:将Sort操作符下推到Union操作符下，由全局的Sort转换为Union各个子RelNode的Sort操作，其中也不是Sort下推到所有子RelNode，还要经过优化条件的判断，条件满足了再相关等价变换。

原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;

核心方法和属性：
1）matches方法

matches方法返回此规则Rule是否可能与给定的操作数operands匹配。...

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

Sort操作符LIMIT操作fetch大于0，否则放弃优化。
Union操作符的判断。在SQL中，如果只使用了Union，默认是Union Distinct的去重复的合并操作。必须是Union ALL，不去重复的Union合并操作，否则放弃优matches方法匹配是有可能执行优化等价变换的前提。

2）onMatch方法

使用RelOptRuleCall对象rel(0)方法获取根RelNode关系表达式SortLimit，其次获取SortLimit的子RelNode关系表达式Union。会判断每个子输入记录数是否大于Sort的limit + offset（返回前丢弃的记录数，同样要花费成本来取值，只是在返回时丢弃了，所以要加上offset偏移量），如果大于说明还有优化的空间，否则直接跳过此子输入RelNode的原封不动存在Union子RelNode列表

如果满足优化条件，在重写时会设置标示位finishPushSortPastUnion=false说明对子输入RelNode进行了优化重写，重写的逻辑是把Sort的fetch+offset作为新Sort的fetch。并下推到子RelNode，即如，SELECT id FROM table1 SORT BY id LIMIT 1000。

遍历完Union所有子RelNode后，并判断是否有子RelNode完成重写并下推。如果finishPushSortPastUnion=true，则说明没有满足优化条件，没有优化空间，退出优化。

最后步骤是Union操作符将重写的下推了Sort的新子RelNode，生成新Union。新生成Union做Sort的子RelNode生成新Sort，保持了原RelNode是等价变换。注册到优化器。

总结：

SortUnionReduceRule优化规则遍历Union下各个输入的子RelNode，判断Sort Limit限制的记录数是否大于子RelNode记录数，大于则说明取子RelNode总记录数的全部，已经没必要进行下推了，跳过此子RelNode的重写优化。对满足条件的子RelNode关系表达式进行Sort下推重写，如果全都不满足则跳出优化。

SortMergeRule

SortMergeRule:把重复的Sort操作去除的优化规则。把外层仅有的Limit操作合并到内部SortLimit操作，最终Limit限制记录数大小，要通过内外部Limit的offset和rows返回总记录大小来判定。

核心方法和属性：
1）matches方法逻辑详解

matches方法返回此规则Rule是否可能与给定的操作数operands匹配。...

SortMergeRule的判断条件如下：

顶部的Sort操作符是纯LIMIT操作，没有排序操作，且不是由其他优化规则Rule创建的，否则放弃优化。
底部的Sort操作符存在LIMIT操作，fetch不为null，否则放弃优化。
底部的Sort操作符必须是由优化规则Rule创建的，否则放弃优化。

2）onMatch方法逻辑详解

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

(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，注册到优化器

总结：

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

ProjectFilterPullUpConstantsRule

ProjectFilterPullUpConstantsRule:从Project投影（Select 从句）和Filter谓词（Where条件）这种SQL语句写法中上拉常量。

核心方法和属性：

1）matches方法逻辑
matches方法返回此规则Rule是否可能与给定的操作数operands匹配。...

ProjectFilterPullUpConstantsRule的判断条件如下：

call.rel(1)取得Filter谓词，并判断此谓词条件是否为确定性的。如果此谓词是非确定性的，则不满足匹配条件，放弃优化。

所谓谓词条件的确定性，是如果对该运算符的调用保证在给定相同操作数operand时始终返回相同的结果，即为确定性。

2）onMatch方法顶层是Project投影，子RelNode是Filter谓词。rewriteProjects方法是进行常量上拉最为关键的部分，其对Project进行了重写和替换来上拉常量。那么如果newProjects == null，则不做任何优化。否则继续向下执行相关优化操作。

使用rewriteProjects重写Project生成新的Project，使用Builder对象压入Filter对象，再重新构建已上拉了常量的新Project对象，注册到优化器。3）rewriteProjects方法是常量上拉最为关键的部分，其对Project进行了重写优化并返回一个新Project对象。

例如：

 SELECT id,name,age FROM student WHERE age = 18 and name <> '张三'

等值常量谓词上拉后为

SELECT id,name,18 as age 
        FROM student WHERE age = 18 and name <> '张三'

总结：

ProjectFilterPullUpConstantsRule优化规则就是where出现常量等值谓词表达式形如a=1，同时select 含有a字段，那么就确定select中的a字段的为1。就在select中a字段的值，把a=1常量值1上拉到select中，select 1 达到优化目的。

hive

文章转载自大数据启示录，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

hive优化器（1）

评论