Oracle 11g中基于哈希算法对唯一值数（NDV）的估算

[English]

作者： fuyuncat

来源： www.HelloDBA.com

日期： 2011-09-15 04:39:58

分享到 

字段的统计数据是CBO优化器估算执行计划代价的重要依据。而字段的统计数据可以分为两类：概要统计数据（如NDV、字段平均长度ACL、最大、最小值等）和柱状图数据。对于第一类数据，实际上可以通过一次扫描表获取所有字段的统计数据。但是，但是，对于大型表的分析，为减少资源消耗，需要通过采样分析。由于采样具有随机性，对于一些数据分布不均匀的字段，通过采样数据获取统计数据可能会导致获取到的数据与实际数据产生较大差异。尤其对于一些海量数据表，通常采样比较低，因而每次分析对象获取到的数据的精度会存在较大的不确定性。这种不确定性可能会对系统的整体性能造成重大影响。例如，对于以下一组数据，     [0,1,1,1...(100*1)...1,2,3,4,5,6,7,8,9]     其实际的NDV是10，通过采样（假设采样比为10%）获取NDV时，由于采样的随机性，可能就会出现以下情况：     [1...(10*1)...,2,6]     得到的NDV是3，和实际值值存在很大的出入（如果除以采样比的话，NDV为3/10×100=30）。而如果优化器采样了这样数据进行执行计划代价估算的话，就很有可能获取不到最优的执行计划。     而降低这种不确定性的手段就是提高采样比例。但是，对于大型表来说，提高采样比又会带来更多的资源消耗，尤其是获取NDV数值时。由于获取NDV数值需要消除重复值（通过count(distinct col)方式获取），oracle是通过排序的方法将已经读取的唯一值保持在PGA当中，以便消除后续的重复值。因此，当取样比增加时，PGA的消耗也会线性增加。对于大型表，PGA可能不足以容纳全部数据，从而会导致临时磁盘空间的读写，导致重大的性能问题。     在11g中，采用了一种新的算法消除NDV计算时，数据量与PGA消耗之间的线性关系，从而使得通过完全扫描表获得精确统计数据成为可能。因此，在11g，自动采样模式下不再进行快速取样，而是直接进行全表扫描获取统计数据。这一新算法称为唯一值数估计（Approximate NDV）。默认情况下，在进行自动采样（AUTO_SAMPLE_SIZE）时，就采样该算法。也可以通过隐含参数"APPROXIMATE_NDV"关闭该特性。 SQL代码 HELLODBA.COM>exec dbms_stats.set_param('APPROXIMATE_NDV','FALSE');      PL/SQL procedure successfully completed.       注意：11g中，对分区表全局统计数据的增量（INCREMENTAL）计算方式，也是利用了该算法。     该算法充分利用了哈希算法的分布均衡特性。其基本算法过程如下：     它将每个扫描到的数值通过哈希算法转换为一个二进制数值，并放入一个数据结构中，我们称该数据结构为一个纲要（synopsis）；     扫描下一个数值，获取到其哈希二进制数值，将其与纲要中已有哈希值比较，如果已经存在相同值，则丢弃该值，否则就插入纲要中；     纲要是有大小限制的，当新插入哈希值时，纲要已经达到大小限制，则按照一定规则分裂改纲要、并丢弃其中一份数据（例如，将首位为0的数值丢弃掉），此时，纲要级别也相应增加（起始为0，分裂一次加1）；     获取到新的哈希数值时，如果其符合被丢弃数据的规则，则不再插入纲要中；     再次分裂时，按照递进的规则（如将前2为都为0的数值分裂）丢弃数据，并以此类推，直到扫描完所有数据；     我们称纲要中最终剩下数值数成为集数（S），纲要分裂次数称为级数（I），NDV的估算公式           NDV = S*2^I     在这种算法下，由于每个字段在PGA中仅保存一个纲要数据结构，因此，它不会随着读取的数据量的增加而导致PGA消耗的增加。    以下Perl代码演示了该算法。脚本可以在此下载。 SQL代码 D:\Documents\Hellodba.com>perl appr_ndv.pl 16 32 100   0 Scaning 8 (Hash: 0010000000000000) inserted.   1 Scaning 78 (Hash: 0011100000000010) inserted.   2 Scaning 80 (Hash: 0100000000000010) inserted.   ...   36 Scaning 97 (Hash: 1000010000000011)  splitting (current level: 0) ( 0010000000000000 0011100000000010 010000000000001   0 1101010000000001 0001110000000000 1010000000000001 0000110000000010 0100010000000000 0000000000000000 0110000000000000    1100110000000001 0000110000000000 0010000000000010 1000100000000011 0110000000000010 0110110000000000 0101100000000010   1110000000000001 1000000000000011 0100110000000000 0101000000000010 0111000000000000 0111100000000000 0001110000000010 1   100100000000001 0101010000000000 0111010000000010 1011100000000001 1111110000000001 0101010000000010 1001000000000001 00   00000000000010 )   discarded.   ...   99 Scaning 22 (Hash: 0101100000000000) discarded.   Approximated NDV:72( element num: 18, level: 2); Actual NDV:65      上例中，通过新算法计算得到的NDV为72，与实际NDV（65）相当接近。    --- Fuyuncat ---