数据库如何根据全表 NDV 估算子集的 NDV

以前我们讨论过 数据库如何根据样本的 NDV 来估计总体的 NDV，也就是以一个小集合的 NDV 去估算一个更大集合的 NDV，但有的时候会反过来，会要求用全表的 NDV 要去估算表中某个子集的 NDV，什么情况下会用到呢？比如在多表关联的时候，JOIN 条件的选择率为（假设是等值连接）：
j o i n _ s e l e c t i v i t y = m i n ( l e f t _ s e l e c t i v i t y , r i g h t _ s e l e c t i v i t y ) join\_selectivity=min(left\_selectivity, right\_selectivity)join_selectivity=min(left_selectivity,right_selectivity)
换而言之，也就是：
j o i n _ n d v = m a x ( l e f t _ n d v , r i g h t _ n d v ) join\_ndv=max(left\_ndv, right\_ndv)join_ndv=max(left_ndv,right_ndv)
但不管是 JOIN 的左支还是右支，是可能有本地谓词（local predicate）的，连接时用的 NDV 就不再是全表的 NDV，而是经过本地谓词过滤后的子集的 NDV。
举个例子：

SELECTe.employee_id,e.first_name||' '||e.last_nameASfull_name,e.salary,d.department_name,d.location_idFROMemployees eJOINdepartments dONe.department_id=d.department_idWHEREd.location_id=1700ANDe.salary=12008;

在计算 e.department_id = d.department_id 的 NDV 的时候，就不能使用 employees 表和 departments 表的全表 NDV，因为这里是经过本地谓词（WHERE 条件中）过滤后的部分数据，那我们如何来估算它呢？

这个问题可以简单地抽象成一个概率问题：N 个 D 种颜色的球，不放回的抽取 n 个球，里面有多少种（d）颜色？

也就是：N 表示全量数据的个数，D 表示全量数据的 NDV，n 表示部分数据的个数，d 表示部分数据的 NDV，我们要用 N、D、n 来估算 d。

在假设数据分布比较均衡的前提下，可以按如下方法推导：
对于某一种颜色的球来说，有两种可能，一种是落在抽到的子集中，一种是落在抽到的子集外，落在子集外的概率是：1 − n N 1-\frac{n}{N}1−Nn​
平均而言，每一种颜色的球有N D \frac{N}{D}DN​个，
所以该种颜色的球全部落在抽到的子集外的概率是：
( 1 − n N ) N D (1-\frac{n}{N})^{\frac{N}{D}}(1−Nn​)DN​
于是，该种颜色的球至少有一个落在抽到的子集中的概率就是：
1 − ( 1 − n N ) N D 1-(1-\frac{n}{N})^{\frac{N}{D}}1−(1−Nn​)DN​
一共有 D 种颜色的球，落在抽到子集中的颜色种数的数学期望就是：
d = D × ( 1 − ( 1 − n N ) N D ) d=D\times(1-(1-\frac{n}{N})^{\frac{N}{D}})d=D×(1−(1−Nn​)DN​)

看个例子：
100 个 5 种颜色的球，每种颜色 20 个，不放回的抽取 10 个球，里面有多少种颜色？按照上述公式可得：d = 5 × ( 1 − ( 1 − 0.1 ) 20 ) ≈ 4.4 d=5\times(1-(1-0.1)^{20})\approx 4.4d=5×(1−(1−0.1)20)≈4.4
拿 Excel 做个实验，随机 20 次，平均 4.65，比较接近。如果用D × n N = 0.5 D\times\frac{n}{N}=0.5D×Nn​=0.5来估，就会差很多。

实际使用上，开源的 Apache Impala 就使用了这种方式：
https://github.com/apache/impala/blob/master/fe/src/main/java/org/apache/impala/planner/AggregationNode.java

doubleperInstanceInputCard=Math.ceil((double)inputCardinality/totalInstances);doubleglobalNdvInDouble=(double)globalNdv;doubleprobValExist=1.0-Math.pow((globalNdvInDouble-1.0)/globalNdvInDouble,perInstanceInputCard);doubleperInstanceNdv=Math.ceil(probValExist*globalNdvInDouble);

再来看之前的 SQL：

SELECTe.employee_id,e.first_name||' '||e.last_nameASfull_name,e.salary,d.department_name,d.location_idFROMemployees eJOINdepartments dONe.department_id=d.department_idWHEREd.location_id=1700ANDe.salary=12008;|=================================================================|||ID|OPERATOR|NAME|EST.ROWS|EST.TIME(us)|||----------------------------------------------------------------- |||0|HASHJOIN||3|73||||1|├─TABLERANGE SCAN|D(DEPT_LOCATION_IX)|21|59||||2|└─TABLEFULLSCAN|E|2|9|||=================================================================|D:||table_rows:27||physical_range_rows:21||logical_range_rows:21||index_back_rows:21||output_rows:21|E:||table_rows:107||physical_range_rows:107||logical_range_rows:107||output_rows:2

employees 表有 107 条记录，department_id 的 NDV=11，应用本地谓词 e.salary = 12008 剩 2 条，departments 表有 27 条记录，department_id 的 NDV=26，应用本地谓词 d.location_id = 1700 后剩 21 条，问优化器如何估算 e.department_id = d.department_id 连接后的 NDV、selectivity 和行数？

套用上述公式，也就是：
n e w _ l e f t _ n d v = 11 × ( 1 − ( 1 − 2 107 ) 107 11 ) new\_left\_ndv=11\times(1-(1-\frac{2}{107})^{\frac{107}{11}})new_left_ndv=11×(1−(1−1072​)11107​)
= 1.844485 =1.844485=1.844485
n e w _ r i g h t _ n d v = 26 × ( 1 − ( 1 − 21 27 ) 27 26 ) new\_right\_ndv=26\times(1-(1-\frac{21}{27})^{\frac{27}{26}})new_right_ndv=26×(1−(1−2721​)2627​)
= 20.546978 =20.546978=20.546978
o u t _ r o w s = l e f t _ r o w s × r i g h t _ r o w s × 1 m a x ( n e w _ l e f t _ n d v , n e w _ r i g h t _ n d v ) out\_rows=left\_rows\times right\_rows\times \frac{1}{max(new\_left\_ndv, new\_right\_ndv)}out_rows=left_rows×right_rows×max(new_left_ndv,new_right_ndv)1​
= 2 × 21 × 1 20.546978 = 2.04409622 =2\times 21\times\frac{1}{20.546978}=2.04409622=2×21×20.5469781​=2.04409622

从 optimizer trace 中也能看到：

E :rows:2.000000baserows:107.000000statistype: OPTIMIZER version:0used partitions:[502555]normal stat partitions:[]histogram stat partitions:[]DEPARTMENT_ID : NDV:1.844485BASE NDV:11.000000D :rows:21.000000baserows:27.000000statistype: OPTIMIZER version:0used partitions:[502534]normal stat partitions:[]histogram stat partitions:[]DEPARTMENT_ID : NDV:20.546978BASE NDV:26.000000

分毫不差。

可以推算，当 NDV << rows 的时候，这个方法会更精确。