CBO全表扫描代价计算公式推导(6)

[English]

作者： fuyuncat

来源： www.HelloDBA.com

日期： 2009-08-01 15:03:32

分享到 

3.4.20.           OR   当引入OR以后，情况变得更加复杂。它最少产生以下2方面的影响：1、选择性的变化；2、OR与AND的优先级不同，因此要影响到过滤顺序。 3.4.20.1.                    同一字段上多个OR 这一点相对比较简单。从逻辑上看，我们知道，在同一优先级内，同一字段的多个OR实际上就等于对这个字段进行了一次多变量的IN匹配。通过测试数据也能证明这一点： EFFQRYCOLNUM 1       FILTER COST_CPU CPU_A TYPFAC CACULATED a in (:a1, :a2) 257421440 7121440 250300000 250.3 a = :a1 or a = :a2 257421440 7121440 250300000 250.3 3.4.20.2.                    不同字段上的OR 当对不同字段进行OR操作时，情况变得更加复杂。最重要的是，当与AND混合存在时，过滤字句中会形成多个优先级。不过，只要数据充分，还是能发现其中的奥秘的。我们先从纯OR表达式中找规律： a varchar2(50), b number, c varchar2(50), d date, e date, f number,g nunber   EFFQRYCOLNUM 0 a:100;b:200;c:300;d:80;e:160;f:250;g:400 TABROWS 1000000   FILTER COST_CPU CPU_A CPU_B TYPFAC b=:v2 or c=:v3 or d=:v4 366372690 7121440 359251250 359.25125 a=:v1 or b=:v2 or d=:v3 or d=:v4 415626434 7121440 408504994 408.504994 a=:v1 and b=:v2 or c=:v3 or d=:v4 366620196 7121440 359498756 359.498756 b>:v2 or c<:v3 or d>:v4 359746440 7121440 352625000 352.625 b<>:v2 or c<>:v3 or d<>:v4 267372690 7121440 260251250 260.25125 b like :v2 or c like :v3 or d like :v4 502371440 7121440 495250000 495.25 规律很快就可以找到：OR操作的选择性是（1-原选择性）。例如对a IN (:a1, :a2)进行OR操作，其选择性变为(1-2*1/100)。 3.4.20.3.                    OR与AND混合 然后我们再看在OR与AND的混合表达式中的计算。我之前说过，OR与AND的优先级不同，AND的优先级高于OR，即在没有()限制的情况下，表达式会选处理AND再处理OR。这一点很快就让我们遇到一个困扰：在存在不同优先级的情况下，处理的最小单位不是单个字段，而是一个子句。例如，这个过滤式存在2个优先级：(a=:v1 or b<:v2) and (c=:v3 or d in (:d1,:d2))。在对第一优先级（小括号中的2个or子句）处理时，处理单位是字段，可以按照我们之前的方法计算，但是，对于第二优先级，最小单位就是这个2个子句了。于是，我们首先要解决的问题是如何计算一个子句的COLTYPFAC和COLSEL。   a varchar2(50), b number, c varchar2(50), d date, e date, f number,g nunber   EFFQRYCOLNUM 0 a:100;b:200;c:300;d:80;e:160;f:250;g:400 TABROWS 1000000   FILTER COST_CPU CPU_A CPU_B TYPFAC b > :v2 and c = :v3 247621440 7121440 240500000 240.5 b > :v2 or c = :v3 394621440 7121440 387500000 387.5 a like :v1 and b > :v2 284621440 7121440 277500000 277.5 a like :v1 or b > :v2 419621440 7121440 412500000 412.5 a <> :v1 and b = :v2 and c in (:c1, :c2) 297956440 7121440 290835000 290.835 a <> :v1 or b = :v2 or c in (:c1, :c2) 249609773 7121440 242488333 242.488333 a like :v1 and c = :v3 and d in (:d1, :d2) 267554148 7121440 260432708 260.432708 a like :v1 and (b > :v2 or c = :v3) 306996440 7121440 299875000 299.875   还是以测试数据为依据，最终得出对子句的计算： AND子句： EXPTYPEFAC = MIN((COLTYPFAC1+ COLTYPFAC2*COLSEL1), (COLTYPFAC2+ COLTYPFAC1*COLSEL2) EXPSEL = COLSEL1*COLSEL2 OR子句： EXPTYPEFAC = MIN((COLTYPFAC1+ COLTYPFAC2*(1-COLSEL1)), (COLTYPFAC2+ COLTYPFAC1*(1-COLSEL2)) EXPSEL = COLSEL1 + COLSEL2 - COLSEL1*COLSEL2 当单位为子句时，可对上述公式做扩展： 公式21： AND子句： EXPTYPEFAC = MIN((SUBEXPTYPFAC1+ SUBEXPTYPFAC2*SUBEXPSEL1), (SUBEXPTYPFAC2+ SUBEXPTYPFAC1*SUBEXPSEL2) EXPSEL = SUBEXPSEL1*SUBEXPSEL2 OR子句： EXPTYPEFAC = MIN((SUBEXPTYPFAC1+ SUBEXPTYPFAC2*(1-SUBEXPSEL1)), (SUBEXPTYPFAC2+ SUBEXPTYPFAC1*(1-SUBEXPSEL2)) EXPSEL = SUBEXPSEL1 + SUBEXPSEL2 - SUBEXPSEL1*SUBEXPSEL2 其中SUBEXPTYPFAC和SUBEXPSEL可以为子句或者字段的TYPFAC和SELECTIVITY。 3.4.21.           NOT 从OR的经验，我们很容易推导NOT的情况：它使子句的选择性变为（1-EXPSEL）。测试数据也能证明： EFFQRYCOLNUM:0 not (a=:v1 and b=:v2 and c=:v3) 247293107 7121440 240171667 240.171667 EFFQRYCOLNUM:1 b=:v1 327221440 7121440 320100000 320.1 EFFQRYCOLNUM:1 not (b=:v1) 347021440 7121440 339900000 339.9 EFFQRYCOLNUM:1 not (a like :v1) and not (b = :v2) 285616440 7121440 278495000 278.495 EFFQRYCOLNUM:1 (a like :v1) and (b = :v2) 284626440 7121440 277505000 277.505 EFFQRYCOLNUM:1 (a like :v1 or b = :v2) 420716440 7121440 413595000 413.595 EFFQRYCOLNUM:1 not (a like :v1 or b = :v2) 285616440 7121440 278495000 278.495 EFFQRYCOLNUM:0 (a like :v1 or b = :v2) 419621440 7121440 412500000 412.5 EFFQRYCOLNUM:0 not (a like :v1 or b = :v2) 284621440 7121440 277500000 277.5   因此过滤式中引入了NOT时，选择性取反，且符合公式22。要注意的是NOT的默认优先级是高于AND和OR的。 4.   总结 由此，COST_CPU的公式可以演化为： 公式22：COST_CPU = TYPFAC*TABROWS + 0.32*TABBLKS*TABSIZ + 4500*TABBLKS 其中 TYPFAC = ROUND((130 + MAXFLTCOLPOS*20 + EXPTYPEFAC1+ EXPTYPEFAC2* EXPSEL1 + 20*EFFQRYCOLNUM*MAX(1,ROUND(EXPTYPEFAC *TABROWS,0))/TABROWS)*TABROWS,0)/TABROWS 其中，子句的计算是由它的上优先级的子句计算得出，计算式如下： AND子句： EXPTYPEFAC = MIN((SUBEXPTYPFAC1+ SUBEXPTYPFAC2*SUBEXPSEL1), (SUBEXPTYPFAC2+ SUBEXPTYPFAC1*SUBEXPSEL2) EXPSEL = SUBEXPSEL1*SUBEXPSEL2 OR子句： EXPTYPEFAC = MIN((SUBEXPTYPFAC1+ SUBEXPTYPFAC2*(1-SUBEXPSEL1)), (SUBEXPTYPFAC2+ SUBEXPTYPFAC1*(1-SUBEXPSEL2)) EXPSEL = SUBEXPSEL1 + SUBEXPSEL2 - SUBEXPSEL1*SUBEXPSEL2 其中SUBEXPTYPFAC和SUBEXPSEL可以为子句或者字段的TYPFAC和SELECTIVITY。 不同数据类型字段的TYPFAC： 数据类型 COLTYPEFAC CHAR、VARCHAR2 50 NUMBER 150 DATE 300 当匹配符为LIKE时，COLTYPEFAC_NEW = COLTYPEFAC + 50 当匹配符为IN、NOT IN时COLTYPFAC_NEW = COLTYPEFAC*(1-1/NDV)^0+COLTYPEFAC*(1-1/NDV)^1+…+COLTYPEFAC*(1-1/NDV)^(INNUM-1) 各种匹配符的选择性计算如下： 匹配符 COLSEL >、<、<=、>= 1/20 LIKE 1/20 = 1/NDV <>  1-1/NDV IN NOTINNUM*1/NDV NOT IN (1-1/NDV)^NOTINNUM 当作用NOT时，选择性变为 (1-原选择性).   我们这个推导出来的公式基本上已经可以计算绝大多数情况下的全表扫描COST了，但是，在公式中还存在一些常量，我没有发现这些常量能受到哪些已知的参数影响，或许是我没有找到、也或许它们确实是一些常量。 为了简化推导，我这里采用的都是绑定变量。但是，从最终公式可以看出，在使用非绑定变量时，它影响到的仅仅是过滤字段的选择性。而非绑定变量的选择性的计算在Metalink上是有响应文档（如A > val，选择性不再是1/20，而是(A_MAXVAL-val)/(A_MAXVAL-A_MINVAL)），有兴趣的朋友可以对非绑定变量的情况对公式进行验证。此外，还会有更多情况影响到代价的计算，例如，并行、分区等等。 无论如何，如果有足够时间的话，我们仍然可以按照这种推演思路推导出其他情况下的代价公式。也希望有兴趣的朋友继续这个推导。有了这些公式，相信DBA们在对CBO环境中语句调优会有更大确定性。 5.   举例 为了让读者更好的理解公式，我从生产库上对一张表做了一个比较复杂的全表扫描的Trace，利用推导出的公式计算出它的代价： **************** QUERY BLOCK TEXT **************** select /*+ full(a) */ SI_STAT_DT_GMT, REMARKS, TO_ORDER from cs2_bkg_cfm a where BKG_NUM LIKE :V1 and (MSG_ID > :v2 or BKG_STAT IN (:B1, :b2)) and not (SI_CTOFF_DT_GMT = :v3) or CNTR_AGGREGATE_STAT NOT IN (:C1, :C2, :C3) ********************* QUERY BLOCK SIGNATURE ********************* qb name was generated signature (optimizer): qb_name=SEL$1 nbfros=1 flg=0   fro(0): flg=0 objn=64859 hint_alias="A"@"SEL$1" ***************************** SYSTEM STATISTICS INFORMATION *****************************   Using NOWORKLOAD Stats   CPUSPEED: 714 millions instruction/sec   IOTFRSPEED: 4096 bytes per millisecond (default is 4096)   IOSEEKTIM: 10 milliseconds (default is 10) *************************************** BASE STATISTICAL INFORMATION *********************** Table Stats::   Table: CS2_BKG_CFM  Alias:  A     #Rows: 7561040  #Blks:  490172  AvgRowLen:  235.00 Index Stats::   Index: CS2_BKG_CFM_IDX3  Col#: 2     LVLS: 2  #LB: 30940  #DK: 7558140  LB/K: 1.00  DB/K: 1.00  CLUF: 7805400.00 … … *************************************** SINGLE TABLE ACCESS PATH   Column (#2): BKG_NUM(VARCHAR2)     AvgLen: 11.00 NDV: 7558140 Nulls: 0 Density: 1.3236e-07     Histogram: HtBal  #Bkts: 254  UncompBkts: 254  EndPtVals: 255   Column (#6): MSG_ID(NUMBER)     AvgLen: 11.00 NDV: 7561040 Nulls: 0 Density: 1.3226e-07 Min: 10948 Max: 9200001000004500480     Histogram: HtBal  #Bkts: 254  UncompBkts: 254  EndPtVals: 255   Column (#7): BKG_STAT(VARCHAR2)     AvgLen: 10.00 NDV: 5 Nulls: 0 Density: 6.6128e-08     Histogram: Freq  #Bkts: 5  UncompBkts: 378052  EndPtVals: 5   Column (#18): SI_CTOFF_DT_GMT(DATE)     AvgLen: 3.00 NDV: 8834 Nulls: 6252260 Density: 1.1320e-04 Min: 2415021 Max: 2455186   Column (#34): CNTR_AGGREGATE_STAT(VARCHAR2)     AvgLen: 15.00 NDV: 9 Nulls: 163020 Density: 0.11111   Table: CS2_BKG_CFM  Alias: A     Card: Original: 7561040  Rounded: 5358744  Computed: 5358744.20  Non Adjusted: 5358744.20   Access Path: TableScan     Cost:  134465.61  Resp: 134465.61  Degree: 0       Cost_io: 132757.00  Cost_cpu: 14638940663       Resp_io: 132757.00  Resp_cpu: 14638940663   Best:: AccessPath: TableScan          Cost: 134465.61  Degree: 1  Resp: 134465.61  Card: 5358744.20  Bytes: 0 按照过滤子句的优先级形成下面的树状计算表： 优先级 过滤子句       EXPTYPFAC EXPSEL 5         496.1136034   4 or       168.3162426 0.708733677 3   CNTR_AGGREGATE_STAT NOT IN (:C1, :C2, :C3) 133.9507716 0.702334595 3   and     115.45 0.021497566 2     not (SI_CTOFF_DT_GMT = :v3) 300 0.9998868 2     BKG_NUM LIKE :V1 100 0.05 2     OR   180 0.43 1       MSG_ID > :v2 150 0.05 1       BKG_STAT IN (:B1, :b2) 90 0.4   最终计算出的 TYPFAC = ROUND((130+34*20+168.3162426+496.1136034)*C1176,0)/C1176 = 1474.429846 COST_CPU = 1474.429846*7561040+(4500/8192+0.32)* 490172*8192 = 14638953530.47984 这个结果与实际结果相差仅为(14638953530.47984 - 14638940663)/14638940663*100 = 0.000088%   而由此计算出的最终COST = 134464.5613，和实际结果（134465.61）基本吻合。         --The end--