目录
背景
非重复值数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没使用。
代码语言：javascript复制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。
代码语言：javascript复制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并返回。
代码语言：javascript复制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...
代码语言：javascript复制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在不改变其内容的情况下对输入施加特定的分布的关系表达式。
代码语言：javascript复制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连接,同时遇到重复谓词将会移除一个。
代码语言：javascript复制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作为输入的）
代码语言：javascript复制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的返回值。
代码语言：javascript复制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返回所提供的非重复值的数目。
代码语言：javascript复制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个不同的值，因为您将多次选择一些相同的值。
代码语言：javascript复制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估算的方法等讲解。
