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

目录

背景

优化规则SortRemoveRule

• HiveSortLimit关系表达式

• SortRemoveRule优化规则

总结

背景

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

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

• 基于规则的优化器(RBO，Rule-Based Optimizer)

  根据预先准备好的优化规则rule，不考虑数据动态变化，在关系表达式等价转换的前提下，对符合匹配规则条件的关系表达式，替换掉原来的关系表达式，达到优化的目的。

• 基于成本的优化器(CBO，Cost-Based Optimizer)

  根据预先准备好的优化规则rule，在关系表达式等价转换的前提下，对符合匹配规则条件的关系表达式，保留原来的关系表达式并把匹配上新关系表达式加入等价关系表达式集合，根据成本模型和统计信息和算法（Calcite使用的是动态规划算法），从等价关系表达式集合，构建出成本最优执行计划。

通过上述两种优化器特性比较，可明显看出两者优化器的优缺点，但无论基于规则或成本优化器，都需要预先准备好的优化器规则Rule。那么优化器可插拔式的优化规则Rule就是这期系列文章的主题。

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

Hive实现了三十九条优化规则Rule，如谓词下推、Union常量上拉、子查询移除、Project投影合并、列裁剪、谓词和汇总顺序调换、Aggregate常量上拉等等共计三十九条优化规则Rule，接下来会一一介绍。

优化规则SortRemoveRule

    这篇文章讲解一下HiveSortRemoveRule规则，即SortLimit移除优化规则。

• HiveSortLimit关系表达式

        HiveSortLimit是对Calcite的Sort的RelNode的实现，继承关系如下：

        从上图可看出Sort 是Calcite的RelNode。其是排序关系表达式RelNode，在不改变其内容的情况下对输入采用特定顺序排序。

Sort RelNode的关键属性：

• RelCollation collation对象，是对一个RelNode关系表达式物理顺序的描述，排序信息有排序字段的序数词（从0开始，依次类推）和排序方向（升序或降序）的构成的。

• RexNode offset返回记录数前，指定需要丢弃记录数的行表达式。

• RexNode fetch 指定获取记录数行表达式。

例如，员工信息表employe总记录数1000条。按照员工id和员工名称排序取100条。

SELECT id, emp_name 

FROM employe 

SORT BY id,emp_name DESC 

LIMIT 100;

说明如下：

RelCollation collation对象为字段序数次从0开始为0，1和降序DESC。

offset = 1000 - 100 = 900

fetch = 100

public abstract class Sort extends SingleRel {
  //~ Instance fields --------------------------------------------------------
  public final RelCollation collation;//
  protected final ImmutableList<RexNode> fieldExps;
  public final RexNode offset;//返回结果前，需要丢弃的记录数
  public final RexNode fetch;//需要返回的记录数
  /**
   * Creates a Sort.
   * @param cluster   Cluster this relational expression belongs to
   * @param traits    Traits
   * @param child     input relational expression
   * @param collation array of sort specifications
   * @param offset    Expression for number of rows to discard before returning
   *                  first row
   * @param fetch     Expression for number of rows to fetch
   */
  public Sort(
      RelOptCluster cluster,RelTraitSet traits,RelNode child,RelCollation collation,RexNode offset,RexNode fetch) {
    super(cluster, traits, child);
    this.collation = collation;
    this.offset = offset;
    this.fetch = fetch;
    ImmutableList.Builder<RexNode> builder = ImmutableList.builder();
    for (RelFieldCollation field : collation.getFieldCollations()) {
      int index = field.getFieldIndex();
      builder.add(cluster.getRexBuilder().makeInputRef(child, index));
    }
    fieldExps = builder.build();
  }
}

那么HiveSortLimit是对Sort的继承。根据Sort属性可知道，其不是单单具有排序的功能的，还有Limit操作符限制返回记录数的功能。

SortRemoveRule优化规则

        有的数据库，从SQL查询中对输出结果进行排序。但是又不需要返回输出全部结果， 就可以在SQL语句中使用SORT LIMIT从句。数据库基于添加了Sort Limit优化器规则，在内存中维护一个特殊数据结构来保存这些Limit限制大小的数据，显着减少内存使用并优化性能。

        但是此SortRemoveRule优化规则是针对HiveSortLimit的Operator操作符的优化规则Rule，是Sort Remove排序操作移除的优化规则Rule。如果它不是HiveSortJoinReduceRule（把sortLimit下推到hivejoin下）创建的，我们不能删除，是HiveSortJoinReduceRule创建的，我们就能下推，下推后原来的给删除掉。还有对于Sort Limit限制返回记录数已经非常接近总记录数时，就没必要加入优化队列。

例如：

员工信息表employe有总记录数100001，即10万零1条记录。

SELECT 

  id, emp_name 

FROM employe 

SORT BY id,emp_name DESC 

LIMIT 100000;

然而limit 限制返回10万条记录，10万已经非常接近总记录数10万零1条没必要再做Limit操作的优化，所以优化器会limit操作移除掉，减少构建执行计划需要的成本。

        SortRemoveRule继承自父类RelOptRule。

        RelOptRule Calcite框架中的优化规则Rule的抽象类，把一个关系表达式RelNode1转换为另一个关系表达式RelNode2。强调的是，优化器所有关系表达式转换都是基于等价变换的前提下进行的，它有一系列RelOptRuleOperands，其决定了此Rule是否能被应用到一棵RelNodes操作符数的指定部分Section，由optimizer优化器指出哪些Rule是可应用的，然后在这些Rules规则上调用onMatch（RuleCall）方法。

        RelOptRule 里面包含的属性和功能，主要包含Rule的operands集合，对operands槽位顺序的分配，各种operand对象的生成和子operand的策略，按照特征trait对RelNode的转换。而RelOptRuleOperand对象决定一个RelOptRule能否应用到特定到关系表达式。

        所有的优化规则Rule都要实现重写matches和OnMatch方法，matches方法是判断规则Rule是否与给定operands匹配，如果不匹配不会继续后续任务了。如果匹配了才会执行OnMatch方法，把Rule生成的等价的RelNode注册到优化器的RelSet关系表达式等价集合，供优化器使用动态规划算法构建成最优执行计划。

1）SortRemoveRule两个属性：

• reductionProportion预设的SortLimit限制的减少比例

• reductionTuples预设的SortLimit减少记录数

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

protected final float reductionProportion;  //减少比例
protected final float reductionTuples;  //减少元组 这两个参数都是判断是需要match的判断条件

2）matches方法返回此规则Rule是否可能与给定的操作数operands匹配的判断

        此方法是一个将附加条件应用于规则的机会。ReloptPlanner在匹配规则的所有操作数之后和调用OnMatch（ReloptRuleCall）之前调用此方法。在ReloptPlanner的实现中，它可能会在调用OnMatch（ReloptRuleCall）之前将匹配的ReloptRuleCall排队很长时间，这种方法是有益的，因为它允许Planer在处理的早期放弃规则。此方法的默认实现返回true。此方法的任何实现都可以给出误报，也就是说，规则与操作数匹配，但随后具有OnMatch（reloptrulecall）而不生成任何后续任务。

        SortRemoveRule优化规则实现的matches方法，获取call.rel(0)根表达式HiveSortLimit关系表达式。如果次SortLimit不是由HiveSortJoinReduceRule规则（后续会讲文章讲解此规则）创建的，则不匹配返回false。

     同时，另一个重要的匹配判断是 sortLimit.fetch相当于Limit返回限制的记录条数，如果Limit限制条数没达到预期的减少比例和减少返回的记录数变量，则不匹配返回false，无法继续优化，这些条件外，则返回true

public boolean matches(RelOptRuleCall call) {
 final HiveSortLimit sortLimit = call.rel(0);

 // If it is not created by HiveSortJoinReduceRule, we cannot remove it
 //如果它不是HiveSortJoinReduceRule（把sortLimit下推到hivejoin下）创建的，我们不能删除
 //是HiveSortJoinReduceRule创建的，我们就能下推，我们就能把下推后，原来的给删除掉。
 if (!sortLimit.isRuleCreated()) {
   return false;
}
 /**
  * 如果limit减少不多，我们将会，将有可能把limit限制移除（优化），停止继续优化
  */
 // Finally, if we do not reduce the size input enough, we bail out
 int limit = RexLiteral.intValue(sortLimit.fetch);
 Double rowCount = RelMetadataQuery.instance().getRowCount(sortLimit.getInput());
 if (rowCount != null && limit <= reductionProportion * rowCount &&
         rowCount - limit >= reductionTuples) {
   return false;
}
 return true;
}

3）OnMatch方法

接收有关一条规则Rule匹配的通知后，同时此方法被调用，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优化规则的调用。

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

call.transformTo方法是移除HiveSortLimit掉，并把一个由优化规则Rule产生的等价的RelNode关系表达式注册到优化器。也就是加入到RelSubset或等价集合RelSet，然后供优化器从中算出最优的执行计划。

总结

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

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

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

往期文章分享