Hive优化器原理与源码解析—统计信息NDV唯一值数估算

目录

背景

非重复值数NDV估算

• TableScan的NDV估算

• Join的NDV估算

• Filter的NDV估算

• Aggregate的NDV估算

• Project的NDV估算

总结

背景

NDV全称为Number Of Distinct Values，即非重复值的个数。

之前文章有讲过统计信息模块选择率Selectivity估算和带有谓词Predicate的选择率Selectivity的估算，这两篇文章的相关选择率Selectivity的估算里都用到过NDV计算方法和引用，其中如非等值谓词Predicate选择率和函数Function选择率是使用NDV来估算的，还有计算最大NDV方法、平滑选择率Selectivity计算方法、指数后退选择计算方法、getMaxNDVForJoinSelectivity和getMaxNDVFromProjections等等方法。

上述相关选择率Selectivity估算方法，可点击文末相关连接，这里不再赘述。这里只讲述基于Operator操作符如Union、Filter、TableScan、Join、SemiJoin、Sort等等的NDV（Number Of Distinct Values）计算方法。

在HiveMeta元数据信息表TAB_COL_STATS或PART_COL_STATS收集了每列的为NUM_DISTINCTS的记录数，TAB_COL_STATS是非分区表的统计信息，而PART_COL_STATS是表分区级别的统计信息，两者收集的统计信息维度相同，但统计模块只收集了最基本每列NDV非重复值个数。这里PART_COL_STATS的表结构如下：

里面还有NUM_DISTINCTS非重复值数、NUM_TRUE、NUM_FALSE、平均记录大小、字段名称、字段数据类型等等信息。

PART_COL_STATS表里统计信息NUM_DISTINCTS的NDV信息都是基于某列的统计，但是实际应用是基于Operators的，所以这里要讲解的是基于Operator操作符NDV估算的方法。

非重复值数NDV估算

计算NDV的方法需要使用RelNode、RelMetadataQuery元数据访问对象、GroupBy列位图信息，RexNode行表达式谓词Predicate（相当于Where条件）四类信息，再针对不同Operator操作符特性来计算NDV方法。接下来详解一下各Operator操作符的NDV估算方法。

1）操作符TableScan的非重复值数NDV估算

首先从GroupBy指定访问列的位图表示信息，转换为Project投影（类似Select 选择字段的信息）每列的列索引序数词（从0开始，依次类推）列表。然后获取这些列统计信息列表。即PART_COL_STATS基于列的记录，记录里含有NUM_DISTINCTS非重复值数，再对所有列的NDV累乘，即非重复排列组合，构成非重复记录数的基数Cardinality，最后与TableScan总记录数两者中取最小值作为返回值。强调一下，TableScan操作符是对表的全扫描，谓词Predicate没使用。

private Double getDistinctRowCount(HiveTableScan htRel, RelMetadataQuery mq, ImmutableBitSet groupKey,RexNode predicate) {
  List<Integer> projIndxLst = HiveCalciteUtil
      .translateBitSetToProjIndx(groupKey); //投影位图存储转换为索引，投影字段序数集合
  List<ColStatistics> colStats = htRel.getColStat(projIndxLst); //由project投影指定的列索引，来返回列统计信息
  Double noDistinctRows = 1.0;
  for (ColStatistics cStat : colStats) {  //遍历累乘每列的CountDistint
    noDistinctRows *= cStat.getCountDistint();
  }
  return Math.min(noDistinctRows, htRel.getRows());//tablescan行数和累计乘的结果取最小
}

2）操作符Join的非重复值数NDV估算

如果是Join并且是SemiJoin，则使用RelMetadataQuery对象传入该rel的左侧输入RelNode作为参数，获取NDV，否则RelMdUtil.getJoinDistinctRowCount获取Join的最大NDV。如果不是Join则使用元数据的getDistinctRowCount方法获取NDV。

public Double getDistinctRowCount(Join rel, RelMetadataQuery mq, ImmutableBitSet groupKey,
    RexNode predicate) {
  if (rel instanceof HiveJoin) {
    HiveJoin hjRel = (HiveJoin) rel; //如果是HiveJoin，待优化
    //TODO: Improve this
    if (rel instanceof SemiJoin) {
      return mq.getDistinctRowCount(hjRel.getLeft(), groupKey,  //元数据统计中返回
          rel.getCluster().getRexBuilder().makeLiteral(true));
    } else {
      return RelMdUtil.getJoinDistinctRowCount(mq, rel, rel.getJoinType(),//从join中返回
          groupKey, predicate, true);
    }
  }
  return mq.getDistinctRowCount(rel, groupKey, predicate);
}

3）通用RelNode的非重复值数NDV估算

这里谓词Predicate默认为True常量谓词，指定的列索引转换为位图BitSet信息，使用RelMetadataQuery元数据对象获取NDV并返回。

public static Double getDistinctRowCount(RelNode r, RelMetadataQuery mq, int indx) {
  ImmutableBitSet bitSetOfRqdProj = ImmutableBitSet.of(indx);
  return mq.getDistinctRowCount(r, bitSetOfRqdProj, r
      .getCluster().getRexBuilder().makeLiteral(true));
}

Hive继承了Calcite的RelMdDistinctRowCount，其自带常用Operators的NDV估算的讲解

1）操作符Union的非重复值数NDV估算

        先获取Union关系表达式的列数，创建调整因子数组，默认为null

遍历Union的输入，如 

select a from t1 where b=10  

union select a from t2 where b=9  

union select a from t3 where b=8 

三个输入的RelNode

把谓词predicate 转化为对每个子RelNode的引用，使用RelOptUtil.RexInputConverter遍历此子RelNode树，根据调整因子数组，来获取子谓词Predicate，然后使用新的谓词，每个子RelNode，利用RelMetadataQuery对象的访问元数据获取NDV，再把每个子RelNode的NDV进行累加。

计算公式：

Unoin的NDV = 子RelNode1的NDV + 子RelNode2的NDV + 子RelNode3的NDV...

public Double getDistinctRowCount(Union rel, RelMetadataQuery mq,
    ImmutableBitSet groupKey, RexNode predicate) {
  Double rowCount = 0.0;
  int[] adjustments = new int[rel.getRowType().getFieldCount()];
  RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
  for (RelNode input : rel.getInputs()) {
    // convert the predicate to reference the types of the union child
    RexNode modifiedPred;
    if (predicate == null) {
      modifiedPred = null;
    } else {
      modifiedPred =
          predicate.accept(//Accepts a visitor, dispatching to the right overloaded visitXxx method.
        // Walks an expression tree, converting the index of RexInputRefs based on some adjustment factor.
              new RelOptUtil.RexInputConverter(
                  rexBuilder,
                  null,
                  input.getRowType().getFieldList(),
                  adjustments));
    }
    Double partialRowCount =
        mq.getDistinctRowCount(input, groupKey, modifiedPred);
    if (partialRowCount == null) {
      return null;
    }
    rowCount += partialRowCount;
  }
  return rowCount;
}

2）操作符Sort和Exchange的非重复值数NDV估算

Sort 和ExChange都是元数据对象的getDistinctRowCount方法来获取NDV的。

其中，ExChange在不改变其内容的情况下对输入施加特定的分布的关系表达式。

public Double getDistinctRowCount(Sort rel, RelMetadataQuery mq,
                                  ImmutableBitSet groupKey, RexNode predicate) {
    return mq.getDistinctRowCount(rel.getInput(), groupKey, predicate);
}

public Double getDistinctRowCount(Exchange rel, RelMetadataQuery mq,
                                  ImmutableBitSet groupKey, RexNode predicate) {
    return mq.getDistinctRowCount(rel.getInput(), groupKey, predicate);
}

3）操作符Filter的非重复值数NDV估算

如果谓词为null或谓词一直true并，没有指定访问列，则NDV为1，否则使用RelMdUtil.unionPreds方法把参数predicate谓词和filter中谓词两个谓词使用AND连接,同时遇到重复谓词将会移除一个。

public Double getDistinctRowCount(Filter rel, RelMetadataQuery mq,
                                  ImmutableBitSet groupKey, RexNode predicate) {
    if (predicate == null || predicate.isAlwaysTrue()) {
        if (groupKey.isEmpty()) {//无访问字段
            return 1D;
        }
    }
    RexNode unionPreds =
            RelMdUtil.unionPreds( //AND's two predicates together, either of which may be null, removing redundant filters.
                    rel.getCluster().getRexBuilder(),
                    predicate,
                    rel.getCondition());

    return mq.getDistinctRowCount(rel.getInput(), groupKey, unionPreds);
}

4）操作符SemiJoin的非重复值数NDV估算

如果谓词为null或谓词一直true并，没有指定访问列，则NDV为1。

这里使用了SemiJoin的filter的代表选择率的RexNode作为predicate谓词，传递个mq.getDistinctRowCount来计算SemiJoin的NDV（注：SemiJoin使用的左RelNode作为输入的）

public Double getDistinctRowCount(SemiJoin rel, RelMetadataQuery mq,
                                  ImmutableBitSet groupKey, RexNode predicate) {
    if (predicate == null || predicate.isAlwaysTrue()) {
        if (groupKey.isEmpty()) {
            return 1D;
        }
    }
    // create a RexNode representing the selectivity of the
    // semijoin filter and pass it to getDistinctRowCount
    RexNode newPred = RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
    if (predicate != null) {
        RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
        newPred =
                rexBuilder.makeCall(
                        SqlStdOperatorTable.AND,
                        newPred,
                        predicate);
    }
    return mq.getDistinctRowCount(rel.getLeft(), groupKey, newPred);
}

5）操作符Aggregate的非重复值数NDV估算

        如果谓词为null或谓词一直true并，没有指定访问列，则NDV为1。

        使用RelOptUtil.splitFilters方法将参数predicate根据getGroupSet引用字段位图信息，拆分为可下推子RelNode和不能下推都子RelNode的两个谓词Filter列表，分别存放pushable列表和notPushable列表。

对子RelNode的谓词列表pushable来说，使用RexUtil.composeConjunction方法，把列表用AND连结Predicate谓词，RelMdUtil.setAggChildKeys方法提取聚合aggregate中按group by列引用的位图，childKey位图信息表示输入列引用集合。然后用元数据获取对象mq.getDistinctRowCount来获取distinctRowCount，如此distinctRowCount为null，则返回null，如果notPushable不可下推的谓词列表也为空则返回distinctRowCount，否则distinctRowCount *notPushable的谓词选择率作为作为NDV的返回值。

public Double getDistinctRowCount(Aggregate rel, RelMetadataQuery mq,
                                      ImmutableBitSet groupKey, RexNode predicate) {
        if (predicate == null || predicate.isAlwaysTrue()) {
            if (groupKey.isEmpty()) {
                return 1D;
            }
        }
        // determine which predicates can be applied on the child of the
        // aggregate
        final List<RexNode> notPushable = new ArrayList<>();
        final List<RexNode> pushable = new ArrayList<>();
        //根据filter是否只引用其子输入，将filter拆分为两个列表
        RelOptUtil.splitFilters(
                rel.getGroupSet(),//字段的位图信息
                predicate, //将要被拆分的谓词filter
                pushable, //能下推到子RelNode的filter列表
                notPushable);//不能下推到子RelNode的filter列表
        final RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
        //Converts a collection of expressions into an AND. If there are zero expressions, returns TRUE.
        // If there is one expression, returns just that expression. If any of the expressions are FALSE, returns FALSE.
        // Removes expressions that always evaluate to TRUE. Returns null only if nullOnEmpty and expression is TRUE.
        RexNode childPreds =
                RexUtil.composeConjunction(rexBuilder, pushable, true);
        // set the bits as they correspond to the child input
        ImmutableBitSet.Builder childKey = ImmutableBitSet.builder();
        RelMdUtil.setAggChildKeys(groupKey, rel, childKey);

        Double distinctRowCount =
                mq.getDistinctRowCount(rel.getInput(), childKey.build(), childPreds);
        if (distinctRowCount == null) {
            return null;
        } else if (notPushable.isEmpty()) {
            return distinctRowCount;
        } else {
            RexNode preds =
                    RexUtil.composeConjunction(rexBuilder, notPushable, true);
            return distinctRowCount * RelMdUtil.guessSelectivity(preds);//如谓词是不可下推到子RelNode的谓词，则使用此谓词的选择率 乘以 非重复值个数，来作为NDV
        }
    }

6）操作符Project的非重复值数NDV估算

如果谓词为null或谓词一直true，没有指定访问列，则NDV为1。

把投影Project的表达式集合projExprs用RelMdUtil.splitCols方法拆分为子RelNode的引用列的位图信息baseCols和非子RelNode引用列位图信息projCols。 使用RelOptUtil.splitFilters方法将参数predicate根据getGroupSet引用字段位图信息，拆分为可下推子RelNode和不能下推都子RelNode的两个谓词Filter列表，分别存放pushable列表和notPushable列表。对子RelNode谓词信息AND拼接，并将基于Project投影输出字段的谓词表达式转换为Project输入字段上的等价谓词表达式形成新的谓词信息modifiedPred。再使用子RelNode的列和新的modifiedPred从元数据获取对象获取distinctRowCount （NDV）。

如果notPushable非空，则将其谓词Predicate表达式集合以AND拼接形成新的谓词，使用RelMdUtil.guessSelectivity估算谓词选择率乘以子RelNode的distinctRowCount 并赋值给distinctRowCount。

如果投影列的基数Cardinality为0，则返回distinctRowCount，否则遍历每个投影列的NDV（从统计信息表中获取）并与distinctRowCount累乘。再使用RelMdUtil.numDistinctVals返回所提供的非重复值的数目。

public Double getDistinctRowCount(Project rel, RelMetadataQuery mq,
                                  ImmutableBitSet groupKey, RexNode predicate) {
    if (predicate == null || predicate.isAlwaysTrue()) {
        if (groupKey.isEmpty()) {
            return 1D;
        }
    }
    ImmutableBitSet.Builder baseCols = ImmutableBitSet.builder();
    ImmutableBitSet.Builder projCols = ImmutableBitSet.builder();
    List<RexNode> projExprs = rel.getProjects();
    RelMdUtil.splitCols(projExprs, groupKey, baseCols, projCols);

    final List<RexNode> notPushable = new ArrayList<>();
    final List<RexNode> pushable = new ArrayList<>();
    RelOptUtil.splitFilters(
            ImmutableBitSet.range(rel.getRowType().getFieldCount()),
            predicate,
            pushable,
            notPushable);
    final RexBuilder rexBuilder = rel.getCluster().getRexBuilder();

    // get the distinct row count of the child input, passing in the
    // columns and filters that only reference the child; convert the
    // filter to reference the children projection expressions
    RexNode childPred =
            RexUtil.composeConjunction(rexBuilder, pushable, true);//可下推的谓词集合用And拼接
    RexNode modifiedPred;
    if (childPred == null) {
        modifiedPred = null;
    } else {
        modifiedPred = RelOptUtil.pushPastProject(childPred, rel);//将基于Project投影输出字段的表达式转换为Project输入字段上的等价表达式。
    }
    Double distinctRowCount =
            mq.getDistinctRowCount(rel.getInput(), baseCols.build(),//子RelNode的列
                    modifiedPred);//子RelNode新生成的谓词
    if (distinctRowCount == null) {
        return null;
    } else if (!notPushable.isEmpty()) {
        RexNode preds =
                RexUtil.composeConjunction(rexBuilder, notPushable, true);
        distinctRowCount *= RelMdUtil.guessSelectivity(preds);
    }
    // No further computation required if the projection expressions
    // are all column references
    if (projCols.cardinality() == 0) {
        return distinctRowCount;
    }
    // multiply by the cardinality of the non-child projection expressions
    for (int bit : projCols.build()) {
        Double subRowCount =
                RelMdUtil.cardOfProjExpr(mq, rel, projExprs.get(bit));
        if (subRowCount == null) {
            return null;
        }
        distinctRowCount *= subRowCount;
    }

    return RelMdUtil.numDistinctVals(distinctRowCount, mq.getRowCount(rel));
}

7）操作符Values的非重复值数NDV估算

Values为它的值为零个或多个字面行值序列的关系表达式RelNode。

同样地，如果谓词为null或谓词一直true并，没有指定访问列，则NDV为1。

使用RelMdUtil.guessSelectivity猜测参数predicate谓词的选择率，rel.estimateRowCount估算其总记录数，假设一半为为重复，所以除以2.

RelMdUtil.numDistinctVals返回所提供的非重复值的数目。如果存在nRows非重复值，则选择nRows * selectivity。请注意，如果nRows==nRows * selectivity，则返回值不应为nRows。    例如，如果您选择100个介于1和100之间的随机值，那么最终很可能会得到少于100个不同的值，因为您将多次选择一些相同的值。

public Double getDistinctRowCount(Values rel, RelMetadataQuery mq,
                                  ImmutableBitSet groupKey, RexNode predicate) {
    if (predicate == null || predicate.isAlwaysTrue()) {
        if (groupKey.isEmpty()) {
            return 1D;
        }
    }
    Double selectivity = RelMdUtil.guessSelectivity(predicate);
    // assume half the rows are duplicates
    Double nRows = rel.estimateRowCount(mq) / 2;
    return RelMdUtil.numDistinctVals(nRows, nRows * selectivity);
}

总结

    NDV非重复值数目的估算，在选择率估算中会用到，NDV的准确性直接影响到选择率Selectivity的准确性，进而影响中间结果大小的准确性，成本估算是否合理，执行计划是否是最优的。TAB/PART_COL_STATS表里统计信息NUM_DISTINCTS的NDV信息都是基于某列的统计，但是实际应用是基于Operators的，上述是基于Operator操作符NDV估算的方法等讲解。

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

往期文章分享