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

2022-04-25 15:42:39 浏览数 (1)

目录

背景

优化规则FilterReduceExpressionsRule

  • matches方法逻辑详解
  • onMatch方法逻辑详解

总结

背景

这篇文章来讲优化规则FilterReduceExpressionsRule，主要功能减少不必要谓词表达式判断，如冗余cast转换移除，cast转换为字段本身的相同的数据类型；Filter内含有条件是常量，恒为True等等。和Filter减少不必要的Expression相似的优化规则，还有Calcite框架自带的ProjectReduceExpressionsRule、JoinReduceExpressionsRule是与Project投影和Join关联相关的减少不必要表达式的优化规则。

操作符表达式树，等价变换如下：

FilterReduceExpressionsRule是HiveReduceExpressionsRule优化规则中，实现一部分。其他都引用Calcite自带的ReduceExpressionsRule优化规则。

优化规则FilterReduceExpressionsRule

1）matches方法逻辑详解

matches方法返回此规则Rule是否可能与给定的操作数operands匹配，但是此方法的任何实现都可以给出误报，也就是说虽然规则与操作数匹配，但随后具OnMatch（ReloptRuleCall）而不生成任何后续任务。

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

代码语言：javascript复制
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优化规则的调用。

通过使用RelMetadataQuery HiveMeta元数据收集信息的访问对象getPulledUpPredicates方法提取Filter对象子输入RelNode上的谓词表达式列表RelOptPredicateList对象predicates。

RelOptPredicateList：

已知保存在特定关系表达式输出中的谓词。

谓词分两种：

  • 上拉谓词：（字段pulldupredicates是应用于关系表达式输出的每一行的谓词。它们是从输入关系表达式和关系运算符推断出来的。

例如，如果将Filter（x>1）应用于谓词y<10的关系表达式，则过滤器的上拉谓词为[y<10，x>1]。

  • 推断谓词：仅适用于联接。如果联接的左输入上有谓词，并且该谓词位于联接条件中使用的列上，则可以在联接的右输入上推断谓词。（反之亦然。）

先找到RelNode表达式的谓词表达式，为FilterReduceExpress移除不必要的表达式做准备。

代码语言：javascript复制
final Filter filter = call.rel(0);
final List<RexNode> expList =
    Lists.newArrayList(filter.getCondition());//Filter的谓词列表
RexNode newConditionExp;
boolean reduced;//判断谓词是否可移除的标识
final RelMetadataQuery mq = RelMetadataQuery.instance();//创建访问Hive元数据对象
final RelOptPredicateList predicates =
    mq.getPulledUpPredicates(filter.getInput());//通过元数据信息，拉取该Filter子输入的谓词列表

上述boolean reduced是用来标识判断谓词是否可移除的。

reduceExpressions是从父类ReduceExpressionsRule继承的方法，主要功能返回是否已经成功地减少了一些表达式。

reduceExpressions方法说明：

代码语言：javascript复制
protected static boolean reduceExpressions(
RelNode rel, 
java.util.List<RexNode> expList, 
RelOptPredicateList predicates,
 boolean unknownAsFalse, 
 boolean matchNullability)

减少一系列表达式

  • Parameters: rel - Relational expression，关系表达式 expList - List of expressions, modified in place 就地修改的表达式列表 predicates - Constraints known to hold on input expressions 已知保留输入表达式的约束 unknownAsFalse - Whether UNKNOWN will be treated as FALSE 是否把未知UNKNOWN当成False
  • Returns: whether reduction found something to change, and succeeded 返回是否已经成功地减少表达式

如果成功地减少谓词表达式，取expList.get(0)由方法已经修改的表达式（对filter.getCondition()返回RexNode的修改后的）。则是否可减少标识reduced=true。

如果没有减少，取filter.getCondition()过滤条件作为newConditionExp，仍然测试原始谓词，看看它是否已经是一个常量，在这种情况下，我们不需要任何关于筛选的运行时决策。则是否可减少标识reduced=false

代码语言：javascript复制
if (reduceExpressions(filter, expList, predicates, true)) {
  assert expList.size() == 1;
  newConditionExp = expList.get(0);//Filter第一个谓词赋予给新newConditionExp
  reduced = true;
} else {//没有减少的情况下
  newConditionExp = filter.getCondition(); //否则Filter的过滤其条件赋值给newConditionExp
  reduced = false;
}

对newConditionExp已经减少了表达式新谓词表达式或原始谓词的判断：

  • 如果newConditionExp恒为true，则移除此Filter谓词。
  • 如果reduced=true，即已缩减谓词表达式，返回表达式是否仅为可为空的而强制转换Cast转换，则只取方法的第一个操作数，即移除cast不必要的转换。冗余Cast转换还有如cast( 10 as int)，这种就取第一个操作数10取掉cast转换。
  • 如果Ruduce可能以创建一个NULL类型表达式而结束。例如，条件（null=null）被简化为具有null类型的条件（null）因为这是一个始终为布尔类型的条件，所以我们将其强制转换为布尔类型。

其他无缩减谓词表达式的情况下，判断是否为方法（RexCall方法调用对象）或表达式的调用。如果其RexCall是以NOT 开头，还有以去掉NOT 进行判断是否为RexCall方法调用或表达式调用。

去掉NOT后操作数若不是RexCall，则推出优化。否则取第一个操作数，即去掉NOT的操作数。

代码语言：javascript复制
if (newConditionExp.isAlwaysTrue()) {//如果此Filter的谓词条件表达式恒为true
  call.transformTo(
      filter.getInput());//直接使用Filter的子输入注册到RelSet，相当于跳过或移除Filter操作
} else if (reduced) {//如果可减少为真
  if (RexUtil.isNullabilityCast(filter.getCluster().getTypeFactory(),
      newConditionExp)) {//返回表达式是否仅为可为空的目的而强制转换，而不更改类型的任何其他方面。
    newConditionExp = ((RexCall) newConditionExp).getOperands().get(0);//取此方法第一个操作数，因为没必要
  }
  if(newConditionExp.getType().getSqlTypeName() == SqlTypeName.NULL) {//为null情况
    newConditionExp = call.builder().cast(newConditionExp, SqlTypeName.BOOLEAN);
  }
  call.transformTo(call.builder().
      push(filter.getInput()).filter(newConditionExp).build());
} else {//没有减少的情况下
  if (newConditionExp instanceof RexCall) {//判断是否为方法或表达式调用
    RexCall rexCall = (RexCall) newConditionExp;
    boolean reverse = rexCall.getKind() == SqlKind.NOT;//如果运算符是NOT，说明可取反的
    if (reverse) {
      if (!(rexCall.getOperands().get(0) instanceof RexCall)) {//如果子操作数 不是为RexCall，则退出优化
        return;
      }
      rexCall = (RexCall) rexCall.getOperands().get(0);//否则取第一个操作数
    }
    reduceNotNullableFilter(call, filter, rexCall, reverse);//相见下面函数
  }
  return;
}

最后，优化器判定，新生成的执行计划绝对的好与旧执行计划。即缩减expression后的执行计划，一定没缩减的更优化。

代码语言：javascript复制
call.getPlanner().setImportance(filter, 0.0);//唯一可确定的，新执行计划好与旧执行计划。

对于一个静态模式Schema系统，Schema信息是从输入RelNode获取的，一个总是为False或NUll的Filter总是被一个不产生任何记录值操作符替代。对于动态模式Schema系统，Filter可能有unknown未知输入类型。在这些情况下，它们必须定义Values operator的系统特定替代项，例如插入LIMIT 0来替代在原始输入上Filter。

此方法的实现是调用RelBuilder的empty，是静态模式Schema可以被优化为一个空的Values操作。

代码语言：javascript复制
protected RelNode createEmptyRelOrEquivalent(RelOptRuleCall call, Filter input) {
  return call.builder().push(input).empty().build();//empty优化为空Values操作
}

对于不可为空的表达式为is[NOT]NULL，则可以移除筛选器或将其替换为空Empty。如对一个非空列上限制为IS NULL，谓词表达式肯定为False。

对于不可为空的列，结果恒为真True谓词表达式，Filter可移除；结果为未知的，可用空来替代。

代码语言：javascript复制
private void reduceNotNullableFilter(
        RelOptRuleCall call,
        Filter filter,
        RexCall rexCall,
        boolean reverse) {
      boolean alwaysTrue;
      switch (rexCall.getKind()) {
      case IS_NULL:
      case IS_UNKNOWN:
        alwaysTrue = false;//对于非空列，这是恒为假的
        break;
      case IS_NOT_NULL:
        alwaysTrue = true;//对于非空列，恒为真
        break;
      default:
        return;
      }
      if (reverse) {// 可取反的
        alwaysTrue = !alwaysTrue; //恒为真或恒为假，取反
      }
      RexNode operand = rexCall.getOperands().get(0);//取第一个操作数
      if (operand instanceof RexInputRef) {//如果为字段
        RexInputRef inputRef = (RexInputRef) operand;
        if (!inputRef.getType().isNullable()) {//判断其数据类型及元数据是为非空字段
          if (alwaysTrue) {//恒为真
            call.transformTo(filter.getInput());//移除Filter
          } else {
            call.transformTo(createEmptyRelOrEquivalent(call, filter));
          }
        }
      }
    }

总结

优化规则FilterReduceExpressionsRule主要是通过元数据信息或统计信息获知字段或表达式上的Filter限制条件，已经是冗余的或恒为True，恒为False，或未知等情况，在构建执行计划时，来减少这些不必要的Filter谓词表达式达优化的目的。

express mapreduce

0 人点赞