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

目录

背景

优化规则HivePointLookupOptimizerRule

• matches方法逻辑详解

• onMatch方法逻辑详解

总结

背景

        这篇文章来讲优化规则HivePointLookupOptimizerRule点查找优化规则，主要功能此优化将要应用到Filter过滤表达式上，如果他的表达式包含一个OR操作，且它的子表达式是常量表达式，优化器将会产生一个IN表达式来替代（这样效率更高），如果此OR操作又包含AND子操作可能使用struct结构来产生一个In子句。

        此外，规则内设置minNumORClauses最小Or连接个数限制，如果Or个数太少优化空间不大。做转换优化的操作符树如下：

优化规则HivePointLookupOptimizerRule

1）matches方法逻辑详解

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

        判断由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优化规则的调用。

        onMatch做RelNode关系表达式树相对复杂，涉及到对这个RelNode操树的遍历、转换、合并等操作。使用两次RexShuttle继承实现的RexTransformIntoInClause转换为IN clause语句类和RexMergeInClause合并IN clause语句类并有返回结果的访问器模式的遍历器，即对一颗操作符树遍历操作。

但实现逻辑较明确大致分为四个步骤：

• 对Filter过滤器操作进行遍历，找到可转换的点，即OR连接的谓词表达式中的常量收集。如a = 1 or a = 3 or...

• 合并IN clause 语句，即把上述a = 1 or a = 3 or ...谓词表达式，转为a in (1,3...)

• 比较Filter的谓词条件部分变换前和变换后是否相同，即真正满足优化规则并做Filter谓词表达式的优化，否则推出优化。

• 使用变换后的谓词表达式创建新Filter操作，并进行优化转换

public void onMatch(RelOptRuleCall call) {
  final Filter filter = call.rel(0);
  final RexBuilder rexBuilder = filter.getCluster().getRexBuilder();
  final RexNode condition = RexUtil.pullFactors(rexBuilder, filter.getCondition());
  // 1. 对Filter过滤器操作进行遍历，找到可转换的点
  RexTransformIntoInClause transformIntoInClause = new RexTransformIntoInClause(rexBuilder, filter,minNumORClauses);
  RexNode newCondition = transformIntoInClause.apply(condition);
  // 2. 合并IN clause 语句
  RexMergeInClause mergeInClause = new RexMergeInClause(rexBuilder);
  newCondition = mergeInClause.apply(newCondition);
  // 3. 比较Filter的谓词条件部分变换前和变换后是否相同
  if (newCondition.toString().equals(condition.toString())) {
    return;
  }
  // 4. 使用变换后的谓词表达式创建新Filter操作，并进行优化转换
  RelNode newFilter = filter.copy(filter.getTraitSet(), filter.getInput(), newCondition);
  call.transformTo(newFilter);
}

对关键步骤的大致实现讲解：

        对Filter过滤器操作进行遍历，找到可转换的点，合并IN clause 语句，即把上述a = 1 or a = 3 or ...谓词表达式，转为a in (1,3...)。

        RexCall是Calcite中的通过调用运算符而形成的表达式，其中零个或多个表达式作为操作数。如 A = 1 AND B = 2运算符可以是二进制的、一元的、函数的、特殊的语法结构，如CASE ... WHEN ... END，甚至内部生成的构造，如隐式类型转换。运算符的语法实际上是不相关的，因为行表达式（与SQL表达式不同）不直接表示一段源代码。

• RexCall的连接操作符为AND：

        RexUtil.flattenAnd方法把RexCall对象的表达式，以AND节点为把表达式分解为RexNode列表operands，NUll则忽略。

        遍历operands如果每个子表达式再含有Or连接，transformIntoInClauseCondition遍历此表达式是否含有形如，a = 1 或 2= a 的Or连接的表达式，则转换MultiMap<a,<1,2>>的对象，便于转换a in （1，2）的IN 语句。

• RexCall的连接操作符为OR：

可直接使用transformIntoInClauseCondition遍历此表达式，递归遍历地查找并转换。

public RexNode visitCall(RexCall call) {
  RexNode node;
  switch (call.getKind()) {//调用 带有操作符的 表达式
    case AND:
      ImmutableList<RexNode> operands = RexUtil.flattenAnd(((RexCall) call).getOperands());//转换为AND连接 RexNode行表达式列表
      List<RexNode> newOperands = new ArrayList<RexNode>();
      for (RexNode operand: operands) {//遍历上述的 行表达式，如果一个行表达式，再含有Or操作符
        RexNode newOperand;
        if (operand.getKind() == SqlKind.OR) {
          try {
            newOperand = transformIntoInClauseCondition(rexBuilder,
                    filterOp.getRowType(), operand, minNumORClauses);//经过变换后，转换IN
            if (newOperand == null) {
              newOperand = operand;
            }
          } catch (SemanticException e) {
            LOG.error("Exception in HivePointLookupOptimizerRule", e);
            return call;
          }
        } else {//不含Or直接，作为新newOperand
          newOperand = operand;
        }
        newOperands.add(newOperand);//新操作数列表
      }
      node = RexUtil.composeConjunction(rexBuilder, newOperands, false);//合并And连接
      break;
    case OR:
      try {//如果Or连接，直接返回call
        node = transformIntoInClauseCondition(rexBuilder,
                filterOp.getRowType(), call, minNumORClauses);
        if (node == null) {
          return call;
        }
      } catch (SemanticException e) {
        LOG.error("Exception in HivePointLookupOptimizerRule", e);
        return call;
      }
      break;
    default:
      return super.visitCall(call);
  }
  return node;
}

transformIntoInClauseCondition把Or连接谓词表达式转换为IN clause语句的实现：

        RexUtil.flattenOr方法，以OR节点为把表达式分解为RexNode列表。并把形如字段 a=1 or a=3 or a= 8语句转换为 a in (1,3,8)语句。

同时此方法转换需要满足一定的条件限制：

• 1、Or连接的个数小于 目标最小Or数，退出优化

• 2、谓词表达式必须等值连接，“=” 如 a = 1 ，否则退出优化，如a > 1

• 3、相同字段名称的 Or 常量，不等于 加入常量的个数，则退出优化。

private static RexNode transformIntoInClauseCondition(RexBuilder rexBuilder, RelDataType inputSchema,
        RexNode condition, int minNumORClauses) throws SemanticException {
  assert condition.getKind() == SqlKind.OR;

  // 1. We extract the information necessary to create the predicate for the new
  //    filter
  ListMultimap<RexInputRef,RexLiteral> columnConstantsMap = ArrayListMultimap.create();
  ImmutableList<RexNode> operands = RexUtil.flattenOr(((RexCall) condition).getOperands());//分解为Or连接的RexNode集合
  if (operands.size() < minNumORClauses) {//Or连接的个数小于 目标最小Or数，退出优化。
    // We bail out
    return null;
  }
  for (int i = 0; i < operands.size(); i++) {//遍历RexNode
    final List<RexNode> conjunctions = RelOptUtil.conjunctions(operands.get(i));//每个RexNode元素，再转换为AND连接的列表
    for (RexNode conjunction: conjunctions) {
      // 1.1. If it is not a RexCall, we bail out
      //如果不是表达式调用，则推出优化
      if (!(conjunction instanceof RexCall)) {
        return null;
      }
      // 1.2. We extract the information that we need
      RexCall conjCall = (RexCall) conjunction;
      if(conjCall.getOperator().getKind() == SqlKind.EQUALS) { //如果调用为"=" 表达式 ，如果 a=1
        if (conjCall.operands.get(0) instanceof RexInputRef &&
                conjCall.operands.get(1) instanceof RexLiteral) {
          RexInputRef ref = (RexInputRef) conjCall.operands.get(0);
          RexLiteral literal = (RexLiteral) conjCall.operands.get(1);
          columnConstantsMap.put(ref, literal);//加入 字段，常量值映射
          if (columnConstantsMap.get(ref).size() != i+1) {
            // If we have not added to this column before, we bail out
            return null;
          }
          //如果调用为"=" 表达式 ，如果 1 = a情况
        } else if (conjCall.operands.get(1) instanceof RexInputRef &&
                conjCall.operands.get(0) instanceof RexLiteral) {
          RexInputRef ref = (RexInputRef) conjCall.operands.get(1);
          RexLiteral literal = (RexLiteral) conjCall.operands.get(0);
          columnConstantsMap.put(ref, literal);//加入 字段，常量值映射
          if (columnConstantsMap.get(ref).size() != i+1) {//相同字段名称的 Or 常量，不等于 加入的个数，则推出优化，a=1 or a=3 or a= 8
            // If we have not added to this column before, we bail out
            return null;
          }
        } else {
          // Bail out
          return null;
        }
      } else {
        return null;
      }
    }
  }

之后，还会对各个谓词表达式解析出IN clause进行一次合并操作。

总结

        优化规则HivePointLookupOptimizerRule点查询优化，从SQL语句上OR连接的等值谓词，转换为IN语句，这条优化规则相对容易理解。但是底层实现还蛮复杂的，此文章没大量的贴代码而是对关键代码进行讲解，需更多详解了解的，请自行翻阅源码。

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

往期文章分享

优化规则系列

成本模型系列