以前我们讨论过 数据库如何根据样本的 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\_selectivitymin(left\_selectivity, right\_selectivity)join_selectivitymin(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\_ndvmax(left\_ndv, right\_ndv)join_ndvmax(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_idd.department_idWHEREd.location_id1700ANDe.salary12008;在计算 e.department_id d.department_id 的 NDV 的时候就不能使用 employees 表和 departments 表的全表 NDV因为这里是经过本地谓词WHERE 条件中过滤后的部分数据那我们如何来估算它呢这个问题可以简单地抽象成一个概率问题N 个 D 种颜色的球不放回的抽取 n 个球里面有多少种d颜色也就是N 表示全量数据的个数D 表示全量数据的 NDVn 表示部分数据的个数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 ) dD\times(1-(1-\frac{n}{N})^{\frac{N}{D}})dD×(1−(1−Nn)DN)看个例子100 个 5 种颜色的球每种颜色 20 个不放回的抽取 10 个球里面有多少种颜色按照上述公式可得d 5 × ( 1 − ( 1 − 0.1 ) 20 ) ≈ 4.4 d5\times(1-(1-0.1)^{20})\approx 4.4d5×(1−(1−0.1)20)≈4.4拿 Excel 做个实验随机 20 次平均 4.65比较接近。如果用D × n N 0.5 D\times\frac{n}{N}0.5D×Nn0.5来估就会差很多。实际使用上开源的 Apache Impala 就使用了这种方式https://github.com/apache/impala/blob/master/fe/src/main/java/org/apache/impala/planner/AggregationNode.javadoubleperInstanceInputCardMath.ceil((double)inputCardinality/totalInstances);doubleglobalNdvInDouble(double)globalNdv;doubleprobValExist1.0-Math.pow((globalNdvInDouble-1.0)/globalNdvInDouble,perInstanceInputCard);doubleperInstanceNdvMath.ceil(probValExist*globalNdvInDouble);再来看之前的 SQLSELECTe.employee_id,e.first_name|| ||e.last_nameASfull_name,e.salary,d.department_name,d.location_idFROMemployees eJOINdepartments dONe.department_idd.department_idWHEREd.location_id1700ANDe.salary12008;||||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:2employees 表有 107 条记录department_id 的 NDV11应用本地谓词 e.salary 12008 剩 2 条departments 表有 27 条记录department_id 的 NDV26应用本地谓词 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\_ndv11\times(1-(1-\frac{2}{107})^{\frac{107}{11}})new_left_ndv11×(1−(1−1072)11107) 1.844485 1.8444851.844485n e w _ r i g h t _ n d v 26 × ( 1 − ( 1 − 21 27 ) 27 26 ) new\_right\_ndv26\times(1-(1-\frac{21}{27})^{\frac{27}{26}})new_right_ndv26×(1−(1−2721)2627) 20.546978 20.54697820.546978o 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\_rowsleft\_rows\times right\_rows\times \frac{1}{max(new\_left\_ndv, new\_right\_ndv)}out_rowsleft_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.044096222×21×20.54697812.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 的时候这个方法会更精确。 数据库如何根据全表 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\_selectivitymin(left\_selectivity, right\_selectivity)join_selectivitymin(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\_ndvmax(left\_ndv, right\_ndv)join_ndvmax(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_idd.department_idWHEREd.location_id1700ANDe.salary12008;在计算 e.department_id d.department_id 的 NDV 的时候就不能使用 employees 表和 departments 表的全表 NDV因为这里是经过本地谓词WHERE 条件中过滤后的部分数据那我们如何来估算它呢这个问题可以简单地抽象成一个概率问题N 个 D 种颜色的球不放回的抽取 n 个球里面有多少种d颜色也就是N 表示全量数据的个数D 表示全量数据的 NDVn 表示部分数据的个数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 ) dD\times(1-(1-\frac{n}{N})^{\frac{N}{D}})dD×(1−(1−Nn)DN)看个例子100 个 5 种颜色的球每种颜色 20 个不放回的抽取 10 个球里面有多少种颜色按照上述公式可得d 5 × ( 1 − ( 1 − 0.1 ) 20 ) ≈ 4.4 d5\times(1-(1-0.1)^{20})\approx 4.4d5×(1−(1−0.1)20)≈4.4拿 Excel 做个实验随机 20 次平均 4.65比较接近。如果用D × n N 0.5 D\times\frac{n}{N}0.5D×Nn0.5来估就会差很多。实际使用上开源的 Apache Impala 就使用了这种方式https://github.com/apache/impala/blob/master/fe/src/main/java/org/apache/impala/planner/AggregationNode.javadoubleperInstanceInputCardMath.ceil((double)inputCardinality/totalInstances);doubleglobalNdvInDouble(double)globalNdv;doubleprobValExist1.0-Math.pow((globalNdvInDouble-1.0)/globalNdvInDouble,perInstanceInputCard);doubleperInstanceNdvMath.ceil(probValExist*globalNdvInDouble);再来看之前的 SQLSELECTe.employee_id,e.first_name|| ||e.last_nameASfull_name,e.salary,d.department_name,d.location_idFROMemployees eJOINdepartments dONe.department_idd.department_idWHEREd.location_id1700ANDe.salary12008;||||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:2employees 表有 107 条记录department_id 的 NDV11应用本地谓词 e.salary 12008 剩 2 条departments 表有 27 条记录department_id 的 NDV26应用本地谓词 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\_ndv11\times(1-(1-\frac{2}{107})^{\frac{107}{11}})new_left_ndv11×(1−(1−1072)11107) 1.844485 1.8444851.844485n e w _ r i g h t _ n d v 26 × ( 1 − ( 1 − 21 27 ) 27 26 ) new\_right\_ndv26\times(1-(1-\frac{21}{27})^{\frac{27}{26}})new_right_ndv26×(1−(1−2721)2627) 20.546978 20.54697820.546978o 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\_rowsleft\_rows\times right\_rows\times \frac{1}{max(new\_left\_ndv, new\_right\_ndv)}out_rowsleft_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.044096222×21×20.54697812.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 的时候这个方法会更精确。