CBO全表扫描代价计算公式推导(4)
[English]
作者：
fuyuncat
来源：
www.HelloDBA.com
分享到
3.4.11. 过滤字段最大位置（混合数据类型过滤字段）
但是，当使用混合数据类型字段作为过滤字段做测试时，发现MAXFILPOS在公式中的作用并非一元线性的，不过其产生的变化还是有规律的：
date
NUMBER
MAXFILPOS
5
EFFCOLNUMS
5
FLTCOLNUM
resc_cpu
CPU_B
CPU_A
TYPFAC
1
387121440
7121440
380000000
380
2
402121440
7121440
395000000
395
3
402871440
7121440
395750000
395.75
4
402908940
7121440
395787500
395.7875
5
402910815
7121440
395789375
395.78938
date
NUMBER
MAXFILPOS
4
EFFCOLNUMS
5
FLTCOLNUM
resc_cpu
CPU_B
CPU_A
TYPFAC
1
368121440
7121440
361000000
361
19
2
382171440
7121440
375050000
375.05
19.95
3
382873940
7121440
375752500
375.7525
19.9975
4
382909060
7121440
375787620
375.78762
19.99988
date
NUMBER
MAXFILPOS
3
EFFCOLNUMS
5
FLTCOLNUM
resc_cpu
CPU_B
CPU_A
TYPFAC
1
349121440
7121440
342000000
342
19
2
362221440
7121440
355100000
355.1
19.95
3
362876440
7121440
355755000
355.755
19.9975
仔细观察上面的数据，不难找到规律：
F(MAXFILPOS)–F(MAXFILPOS-1) = 20–20^(1-FLTCOLNUM)
将这一等式代入公式12中，公式修正为：
公式13：TYPFAC = 130 + EFFCOLNUMS + 5*19 - (5-MAXFLTCOLPOS)*(20–20^(1-FLTCOLNUM)) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 225 + EFFCOLNUMS - (5-MAXFLTCOLPOS)*(20–20^(1-FLTCOLNUM)) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 225 + EFFCOLNUMS -100 + MAXFLTCOLPOS*20 + (5-MAXFLTCOLPOS)*20^(1-FLTCOLNUM) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 125 + EFFCOLNUMS + MAXFLTCOLPOS*20 + (5-MAXFLTCOLPOS)*20^(1-FLTCOLNUM) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
3.4.12. 有效字段数（混合数据类型过滤字段）
除了MAXFLTCOLPOS外，在测试数据中还发现一个因子违反之前公式的变化规律，那就是有效字段数EFFCOLNUM：
date
NUMBER
MAXFILPOS
3
EFFCOLNUMS
5
FLTCOLNUM
resc_cpu
CPU_B
CPU_A
TYPFAC
1
349121440
7121440
342000000
342
2
362221440
7121440
355100000
355.1
3
362876440
7121440
355755000
355.755
date
NUMBER
MAXFILPOS
3
EFFCOLNUMS
4
FLTCOLNUM
resc_cpu
CPU_B
CPU_A
TYPFAC
1
348121440
7121440
341000000
341
1
2
362171440
7121440
355050000
355.05
0.05
3
362873940
7121440
355752500
355.7525
0.0025
date
NUMBER
MAXFILPOS
3
EFFCOLNUMS
3
FLTCOLNUM
resc_cpu
CPU_B
CPU_A
TYPFAC
1
347121440
7121440
340000000
340
1
2
362121440
7121440
355000000
355
0.05
3
362871440
7121440
355750000
355.75
0.0025
还好，数字变化规律也不难找到：
F(EFFCOLNUMS)–F(EFFCOLNUMS-1) = 20^(1-FLTCOLNUM)
根据这一规律，修正公式13
公式14：TYPFAC = 130+(20*EFFCOLNUM-100)*(20^(-FILTCLNUM))+MAXFLTCOLPOS*20+(5-MAXFLTCOLPOS)*20^(1-FLTCOLNUM)+ COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 130 + EFFCOLNUM*20^(1-FILTCOLNUM) - 5*20^(1-FILTCOLNUM) + MAXFLTCOLPOS*20 + (5-MAXFLTCOLPOS)*20^(1-FLTCOLNUM) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 130 + EFFCOLNUM*20^(1-FILTCOLNUM) + MAXFLTCOLPOS*(20 - 20^(1-FLTCOLNUM))) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 130 + EFFCOLNUM*20^(1-FILTCOLNUM) + MAXFLTCOLPOS*(20 - 20^(1-FLTCOLNUM))) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 130 + EFFCOLNUM*20^(1-FILTCOLNUM) + MAXFLTCOLPOS*(20 - 20^(1-FLTCOLNUM))) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
由公式8-1，上面的公式可以演化为：
公式15：TYPFAC = 130 + (EFFQRYCOLNUM + MAXFLTCOLPOS)*20^(1-FILTCOLNUM) + MAXFLTCOLPOS*(20 - 20^(1-FLTCOLNUM))) + COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 130 + EFFQRYCOLNUM*(1/20)^(FILTCOLNUM-1) + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1)
= 130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1) + 20*EFFQRYCOLNUM*(1/20)^FILTCOLNUM
3.4.13. 过滤字段计算顺序（混合数据类型过滤字段）
我们之前提到，如果将两个数据类型的位置反过来的话，类似上面一组数据就很难看出规律。我推测优化器计算时会对过滤字段做一个排序，得出上面公式各个字段的幂的值（COLTYPEFAC2*(1/20)^n中的n）。
再仔细观察各种混合数据类型的数据，还是可以从诸多测试数据中看出其他规律来（这里以2个字段为例）：
COL1
COL2
MAXFLTPOS
COST_CPU
varchar2
date
3
262221440
number
char
4
274671440
date
varchar2
5
302121440
char
varchar2
1
269671440
varchar2
number
2
294621440
… …
… …
再将上述数据代入公式12中，发现一个这样的规律，当CHAR或VARCHAR2与NUMBER或DATE混合时，CHAR或VARCHAR2的字段就是最小的幂值；当NUMBER与DATE混合时，NUMBER字段就拥有最小幂值。这样一个规律再结合他们的COLTYPEFAC，我们可以得出一个这样的假设9：优化器会将AND过滤字段按照其COLTYPEFAC由小到大排序，从1开始递增幂值。
我们通过更加复杂的混合字段组合来证明这个假设：
COLA
COLB
COLC
COLD
COLE
MAXFLTPOS
COST_CPU
VARCAHR2
number
date
varchar2
date
5
290035815
Number
varchar2
date
date
varchar2
5
290035815
这2份数据中，尽管不同物理位置的数据类型不同，但是它们拥有相同的的数据类型集合：(VARCHAR2, NUMBER, DATE, VARCHAR2, DATE)。按照假设9，它们的排列顺序都为(DATE, DATE, NUMBER, VARCHAR2, VARCHAR2)，因此计算出的TYPEFAC都相同：
130+20*5+50*(1/20)^0+50*(1/20)^1+150*(1/20)^2+300*(1/20)^3+300*(1/20)^4 = 282.9144 = 282.914375
这个结果和公式5计算出的结果一致：
(290035815-(4500/8192+0.32)*1000*81929)/1000000=282.914375
再通过对其它的随机数据进行测试，发现假设9都是成立的。
注意：实际上，这个处理顺序规则也并非真正的规则，而是在满足当前条件下能够找出的规则，其真正规则我们将在引入更加复杂的情况时看到。
3.4.14. 过滤表达式匹配符（=）
在这之前，我们的过滤语句中表达式的匹配符都是用>或<。假如换成其他匹配符结果会如何呢？先尝试换成=。
3.4.14.1. 字段唯一值数
通过和之前对>符的推导相同的一个过程，得出公式（这里，我暂时没有将存在查询字段位置大于过滤字段最大位置的情况考虑进来，因为这种情况相对复杂，我稍后要做更详细的分析）：
130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/1600)^0 + COLTYPEFAC2*(1/1600)^1 + … + COLTYPEFACn*(1/1600)^(FLTCOLNUM-1)
和<符的公式相比，它的最大区别就在过滤字段子表达式中的底数，一个为1/20，一个为1/1600。通过参照基表的数据，这个结果很容易让我联想起我曾经做过的另外一项测试：字段选择性的测试（见文查询计划中Cardinality的计算）。测试中有一个初步的结论：在使用绑定变量时，>、<、<=、>=的选择性为1/20，=为1/NDV。这里的1600正是基表中所有字段的唯一值数（NDV）。
通过修改字段的NDV值，证明这个设想是正确的。因此的计算公式可以表述为：
公式16：130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/NDV)^0 + COLTYPEFAC2*(1/NDV)^1 + … + COLTYPEFACn*(1/NDV)^(FLTCOLNUM-1)
3.4.14.2. 混合唯一值数
由于我们的测试基表是将所有字段的NDV设为相等，得出公式16后，我们不难想到另外一个问题：当各个过滤字段的NDV不同时，是不是子表达式中的NDV也不同呢？还是看数据，将各个字段的NDV进行修改：
A:160
B:80
C:100
D:200
E:400
FILTER
CPU_B
CPU_A
TYPFAC
CACULATED
a = :v1 b = :v2
478996440
7121440
471.875
471.875
c = :v3 b = :v2
500121440
7121440
493
493
a = :v1 b = :v2 c = :v3
499015190
7121440
491.89375
491.89375
b = :v2 d = :v4 e = :v5
537875190
7121440
530.75375
530.75375
a = v1 b = :v2 c = :v4 e = :v5
537876174
7121440
530.75473
530.7547344
c = v3 b = :v2 d = :v4 e = :v5
537875228
7121440
530.75379
530.7537875
a = :v1 c = v3 b = :v2 d = :v4 e = :v5
537875214
7121440
530.75377
530.7537737
… …
从这些数据，可以找到规律：作用于每个过滤字段的NDV为之前字段中的NDV之积。例如，根据假设9，上述数据中的第五条数据：第一个字段的作用的NDV为1（前面没有字段）、第二个字段作用的NDV为400、第三个字段作用的NDV为400*200……，它的表达式为：
30 + 5*20+ 300*(1/1) + 300*(1/400) + 300*(1/400)*(1/200) + 300*(1/400)*(1/200)*(1/160) + 300*(1/400)*(1/200)*(1/160)*(1/100) = 530.7537875
根据这个规律，公式演变为：
公式16：130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/1) + COLTYPEFAC2*(1/MAXNDV1) + … + COLTYPEFACn*(1/MAXNDV1)*…*(1/MAXNDVn-1)
注意：以上推导出的公式也适用于<、>的情况，只不过当为<、>时，NDV为20。
3.4.14.3. 混合数据类型
在我们之前的推导中，确认当查询字段存在混合数据类型时，会按照类型系数由小到大排序计算过滤字段。但是，如果混合数据类型再混合唯一值数呢。将上面基表再修改数据类型，做2组测试数据：
A:VARCHAR2
B:DATE
C:NUMBER
D:NUMBER
E:VARCHAR2
FILTER
CPU_B
CPU_A
TYPFAC
CACULATED
a = :v1 b = :v2
228996440
7121440
221.875
221.875
c = :v3 b = :v2
350121440
7121440
343
343
a = :v1 b = :v2 c = :v3
248077690
7121440
240.95625
240.95625
b = :v2 d = :v4 e = :v5
287500190
7121440
280.37875
280.37875
a = v1 b = :v2 c = :v4 e = :v5
287248831
7121440
280.12739
280.1273906
c = v3 b = :v2 d = :v4 e = :v5
287498353
7121440
280.37691
280.3769125
a = :v1 c = v3 b = :v2 d = :v4 e = :v5
287248796
7121440
280.12736
280.1273557
A:VARCHAR2
B:NUMBER
C:DATE
D:DATE
E:NUMBER
FILTER
CPU_B
CPU_A
TYPFAC
CACULATED
a = :v1 b = :v2
228058940
7121440
220.9375
220.9375
c = :v3 b = :v2
350871440
7121440
343.75
343.75
a = :v1 b = :v2 c = :v3
248082378
7121440
240.96094
240.9609375
b = :v2 d = :v4 e = :v5
387505815
7121440
380.38438
380.384375
a = v1 b = :v2 c = :v4 e = :v5
288061342
7121440
280.9399
280.9399023
c = v3 b = :v2 d = :v4 e = :v5
387505862
7121440
380.38442
380.3844219
a = :v1 c = v3 b = :v2 d = :v4 e = :v5
288061343
7121440
280.9399
280.9399026
从这些数据中，可以得到另外一个规律：过滤字段先按照其COLTYPEFAC由小到大排序，再按照（1/NDV）由小到大排序，每个过滤字段的NDV为之前字段中最大的NDV之积。例如上面第二组中的第五条，表达式为：
130+5*20+150*1+150*(1/400)+300*(1/400)*(1/80)+300*(1/400)*(1/80)*(1/200) = 280.9399026
3.4.14.4. 有效查询字段
我们前面说过，位置大于过滤字段最大位置的查询字段属于有效查询字段。有效查询字段在过滤表达式出现=符时会发生更加复杂的情况（事实上，在<表达式中也会出现这样的情况，只不过是不容被发觉）。先回头看一下有效查询字段在<匹配符的表达式中影响：
TYPFAC = 130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/20)^0 + COLTYPEFAC2*(1/20)^1 + … + COLTYPEFACn*(1/20)^(FLTCOLNUM-1) + 20*EFFQRYCOLNUM*(1/20)^FILTCOLNUM
在比对之前推导出的=符的公式，我们不难设想在子表达式中20*EFFQRYCOLNUM*(1/20)^FILTCOLNUM，(1/20)也是由字段的NDV得到。看下面的数组，完全符合这种设想：
FLTCOLUMNS
2
MAXFLTCOLPOS
3
Density: 1/40
EFFQRYCOLNUM
COST_CPU
CPU_B
CPU_A
TYPFAC
CACULATED
1
504633940
7121440
497512500
497.5125
0.0125
2
504646440
7121440
497525000
497.525
0.025
3
504658940
7121440
497537500
497.5375
0.0375
4
504671440
7121440
497550000
497.55
0.05
但是，很快我就发现出现了违反这一公式的数据了：
MAXFLTPOS: 3
Density
1/200
FLTCOLUMNS
3
EFFQRYCOLNUM
COST_CPU
CPU_B
CPU_A
TYPFAC
CACULATED
1
498628960
7121440
491507520
491.50752
2E-05
2
498628980
7121440
491507540
491.50754
2E-05
3
498629000
7121440
491507560
491.50756
2E-05
4
498629020
7121440
491507580
491.50758
2E-05
MAXFLTPOS
3
Density
1/800
FLTCOLUMNS
2
EFFQRYCOLNUM
COST_CPU
CPU_B
CPU_A
TYPFAC
1
497496480
7121440
490375040
490.37504
4E-05
2
497496520
7121440
490375080
490.37508
4E-05
仔细研究这些数据，发现它们是随着DNV的增大，达到一定的临界值以后就不再变化了。那么这个临界值如何确定呢。先不急，我们先把这部分的研究放一放，看看另外一个影响因素先。
3.4.14.5. 表的记录数
在推导<、>匹配符的公式时，曾经得出一个结论：NDV、表的记录数都不影响COST_CPU。但是，在=匹配符公式中，NDV已经成为影响因素之一，那么，表的记录数的影响也需要重新考察了。
注意：在考察这一影响因素时，我引入了大量测试数据才最终得出结论，这里只给出一组数据做示例：
rows
1000
tabblks
100
Density
1/80
FLTCOLUMNS
1
EFFQRYCOLNUM
COST_CPU
CPU_B
CPU_A
TYPFAC
CACULATED
1
1202404
712144
490260
490.26
0.26
2
1202664
712144
490520
490.52
0.26
3
1202924
712144
490780
490.78
0.26
由这些数据，最终总结出有效查询字段部分的公式：
20*ROUND((1/NDV)^FLTCOLNUM*TABROWS,0)/TABROWS
在此基础上，继续观察上述大于某一临界值的数据，该部分公式可以调整为：
20*MAX(1,ROUND((1/NDV)^FLTCOLNUM*TABROWS,0))/TABROWS
公式16就演变为：
公式17：TYPFAC = 130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/1) + COLTYPEFAC2*(1/MAXNDV1) + … + COLTYPEFACn*(1/MAXNDV1)*…*(1/MAXNDVn-1) + 20*EFFQRYCOLNUM*MAX(1,ROUND((1/NDV)^FLTCOLNUM*TABROWS,0))/TABROWS
但是，这些数据的基表的所有字段的NDV是相同的，再次考察不同NDV的数据：
A:160
B:80
C:100
D:200
E:400
A:VARCHAR2
B:NUMBER
C:DATE
D:DATE
E:NUMBER
MAXFILPOS
4
EFFCOLNUMS
4
EFFQRYCOLNUM
COST_CPU
CPU_B
TYPFAC
CACULATED
1
275409060
7121440
268.28762
0.00012
2
275409180
7121440
268.28774
0.00012
MAXFILPOS
5
EFFCOLNUMS
5
1
295035835
7121440
287.914395
0.00002
2
295035855
7121440
287.914415
0.00002
也不难得出结论：有效查询字段的作用NDV是所有过滤字段的NDV之积。由这一结论，公式再次演变：
公式18：TYPFAC = 130 + MAXFLTCOLPOS*20+ COLTYPEFAC1*(1/1) + COLTYPEFAC2*(1/MAXNDV1) + … + COLTYPEFACn*(1/MAXNDV1)*…*(1/MAXNDVn-1) + 20*EFFQRYCOLNUM*MAX(1,ROUND((1/MAXNDV1)*…*(1/MAXNDVn)*TABROWS,0))/TABROWS
注意：这一公式也同样适用于<、>匹配符的情况。由于之前我所用的基表的记录数比较大（1000000），要达到临界值需要有5个以上的过滤字段ROUND((1/20)^5*1000000,0) = 0 < 1，因此这个临界值没有被留意到。通过再次取数据测试也证实临界值在<、>匹配符也同样起作用。