ITPub博客

首页 > Linux操作系统 > Linux操作系统 > CBO学习笔记系列5(转载)

CBO学习笔记系列5(转载)

原创 Linux操作系统 作者:alsrt 时间:2012-06-09 14:10:06 0 删除 编辑
selectivity

selectivity是Oracle的CBO中比较重要的一个概念。和selectivity经常一起提到的一个概念是cardinality,其实这两个概念的本质上是一样的。selectivity是指一个SQL操作的得出结果集占原来结果集的百分比,而cardinality就是指一个SQL操作的得出结果集的行数,CBO是通过selectivity来计算cardinality的,也就是说cardinality=selectivity*原结果集行数。

特别提醒一下,我们本节做的讨论都是不考虑Histograms的情况的。

我们知道当Oracle要访问一个表的时候,可以做全表扫描,也可以通过B-tree索引进行访问。CBO一般会在需要访问的数据占整个表的总数据量比较少的时候倾向使用索引,那么Oracle是通过什么来判断需要访问的数据占总数据量的多少呢,就是通过selectivity。
selectivity的另外一个主要的用途就是当SQL里面需要做多个join的时候,CBO通过比较不同的join的selectivity来决定先做哪个join,后做哪个join。

下面我们就来看一看CBO是如何来计算selectivity的。
加入我们有1200个听众,从统计的角度,这些听众里面会有多少人是12月份出生的呢?
按照我们正常的想法:
1. 一共有12个不同的月份。
2. 人们的出生日期很可能是在一年12个月份当中平均分配的。
3. 因此任何一个月份出生的人占所有听众的比率是1/12。
4. 我们一共有1200个听众。
5. 因此12月份出生的人应该是 1200/12=100人


CBO做的事情其实是和我们上面的推断非常类似的:

实验1.
我们先建立这样一个audience 表并收集统计信息:
create table audience as
select
trunc(dbms_random.value(1,13)) month_no
from
all_objects
where
rownum <= 1200
;

Table created.


begin
dbms_stats.gather_table_stats(
user,
'audience',
cascade => true,
estimate_percent => null,
method_opt => 'for all columns size 1'
);
end;
/

PL/SQL procedure successfully completed.

通过查询user_tab_col_statistics和user_tab_histograms这两张字典视图,可以看到Oracle对这张表的统计情况:


select
column_name,
num_distinct,
num_nulls,
density,
value_to_number(low_value) low,
value_to_number(high_value) high
from
user_tab_columns
where table_name = 'AUDIENCE'
and column_name = 'MONTH_NO'
;

COLUMN_NAM NUM_DISTINCT NUM_NULLS DENSITY LOW HIGH
---------- ------------ ---------- ---------- ---------- ----------
MONTH_NO 12 0 .083333333 1 12

我们看到month_no这个列上的不同的值为12个,没有null值, 密度为0.83(即1/12),最大值为12,最小值为1。

select
column_name, endpoint_number, endpoint_value
from
user_tab_histograms
where
table_name = 'AUDIENCE'
order by
column_name, endpoint_number
;

COLUMN_NAM ENDPOINT_NUMBER ENDPOINT_VALUE
---------- --------------- --------------
MONTH_NO 0 1
MONTH_NO 1 12

从USER_TAB_HISTOGRAMS我们只能看到一个最大值和一个最小值,说明Oracle认为1~12之间的数据是均匀分配的。所以如果我们查询month_no为12的行数,Oracle会认为month_no=12的行占整个表的1/12,所以这个查询的cardinality将会等于(1/12) * 1200 = 100行, 从下面的查询我们也可以看到这一点:

set autotrace traceonly explain

select count(*)
from audience
where month_no = 12
;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=1 Bytes=3)
1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (FULL) OF 'AUDIENCE' (Cost=2 Card=100 Bytes=300)

实验2. 如果我们修改一下我们的SQL,把等于的条件改成in:
select count(*)
from audience
where month_no in (6,7,8)
;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=1 Bytes=3)
1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (FULL) OF 'AUDIENCE' (Cost=2 Card=300 Bytes=900)

这一次CBO对cardinality的计算结果是300,这应该也是正确的。但是如果我们进一步修改我们的SQL的条件,把in (6,7,8) 改成in (6, 16):
select count(*)
from audience
where month_no in (6,16)
;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=1 Bytes=3)
1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (FULL) OF 'AUDIENCE' (Cost=2 Card=200 Bytes=600)

问题出现了,因为我们知道我们的月份里面是没有16的,其实Oracle本身通过数据字典也是知道这一点的,但在计算selectivity和cardinality的时候并没有把这一点考虑进去。这其实是Oracle9i的CBO的一个问题。如果我们进一步做一些类似的实验,我们发现这个问题相当的普遍:

条件 cardinality
where month_no = 25 100 Incorrect
where month_no in (4, 4) 100 Correct
where month_no in (3, 25) 200 Incorrect
where month_no in (3, 25, 26) 300 Incorrect
where month_no in (3, 25, 25, 26) 300 Incorrect
where month_no in (3, 25, null) 300 Incorrect
where month_no in (:b1, :b2, :b3) 300 Incorrect


条件 cardinality
where month_no = 25 100 Incorrect
where month_no in (4, 4) 100 Correct
where month_no in (3, 25) 200 Incorrect
where month_no in (3, 25, 26) 300 Incorrect
where month_no in (3, 25, 25, 26) 300 Incorrect
where month_no in (3, 25, null) 300 Incorrect
where month_no in (:b1, :b2, :b3) 300 Incorrect

上面的几个测试唯一结果正确的就是在in里面出现重复值的时候,但是当出现不可能的值或null值的时候CBO对selectivity就有问题了。这是9i的CBO的bug,在10g里已经改善了,在10g里的测试结果是这样的:

条件 Cardinality(10.1.0.2) Cardinality(10.1.0.4)
month_no=13 100 91
month_no=15 100 73
month_no in (13,15) 200 164
month_no in (16,18) 200 109


条件 Cardinality(10.1.0.2) Cardinality(10.1.0.4)
month_no=13 100 91
month_no=15 100 73
month_no in (13,15) 200 164
month_no in (16,18) 200 109

从10.1.0.4开始,当条件里面的值不在表的取值范围的时候(即条件里给出的值超出过小于统计数据的max_value和min_value的时候),CBO计算的Cardinality会随着给出的值离表的取值范围越远而逐渐减少。这无疑是一个进步,但是有时候也会有一些问题:如果一张表的一个列就是日期,如果我们长期忘记收集表的统计数据,随着新的日期
的增加,当我们对新日期进行查询的时候,我们会在10.1.0.4及以后的版本里得到比较小的Cardinality,而在9i或10.1.0.4以前,我们反倒是可以误打误撞的得到一个正确的“Cardinality”。

10.1.0.4里的这个改进可以用下图来描述:

实验3
如果我们把我们的条件改成范围查询呢?

select count(*)
from audience
where month_no >8
;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=1 Bytes=3)
1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (FULL) OF 'AUDIENCE' (Cost=2 Card=436 Bytes=1308)

我们知道大于8的值是9,10,11,12,所以正常的话我们的Cardinality应该是400,但实际上CBO却认为是436,通过多做几次不同的范围查询,我们发现这个问题相当严重:

case 条件 Cardinality
1 month_no > 8 436
2 month_no >= 8 536
3 month_no < 8 764
4 month_no <= 8 864
5 month_no between 6 and 9 527
6 month_no >=6 and month_no <= 9 527
7 month_no >= 6 and month_no < 9 427
8 month_no>6 and month_no <= 9 427
9 month_no > 6 and month_no <9 327
10 month_no > :b1 60
11 month_no >= :b1 60
12 month_no < :b1 60
13 month_no <= :b1 60
14 month_no between :b1 and :b2 3
15 month_no >= :b1 and month_no <= :b2 3
16 month_no >= :b1 and month_no < :b2 3
17 month_no > :b1 and month_no < :b2 3
18 month_no > :b1 and month_no <= :b2 3
19 month_no > 12 100
20 month_no between 25 and 30 100


case 条件 Cardinality
1 month_no > 8 436
2 month_no >= 8 536
3 month_no < 8 764
4 month_no <= 8 864
5 month_no between 6 and 9 527
6 month_no >=6 and month_no <= 9 527
7 month_no >= 6 and month_no < 9 427
8 month_no>6 and month_no <= 9 427
9 month_no > 6 and month_no <9 327
10 month_no > :b1 60
11 month_no >= :b1 60
12 month_no < :b1 60
13 month_no <= :b1 60
14 month_no between :b1 and :b2 3
15 month_no >= :b1 and month_no <= :b2 3
16 month_no >= :b1 and month_no < :b2 3
17 month_no > :b1 and month_no < :b2 3
18 month_no > :b1 and month_no <= :b2 3
19 month_no > 12 100
20 month_no between 25 and 30 100

我们发现几乎所有的范围查询的Cardinality都是不准的,而且between查询和同时包括大于小于的查询的偏差,比只有一个大于或只有一个小于条件的查询偏差要大(比较case1~9),我们发现>=总是比>操作多100的Cardinality(比较case1和case2),我们发现绑定变量的Cardinality看上去相当的小(case10~case18),我们发现当查询的条件里面涉及的数据如果超出表的实际取值范围的时候,CBO给Cardinality指定了一个固定的Cardinality=100(case19和case20)

让我们来逐一分析。
首先,当我们进行范围查询的时候,我们的selectivity=(我们需要的范围)/ (总范围),对于case 1的month_no > 8,selectivity=(12-8)/(12-1)=1/11,所以
Cardinality=1200*4/11=436。

对于case 2的month_no >= 8,selectivity=selectivity of (month_no > 8) + selectivity of (month_no = 8) = (12-8)/(12-1)+1/12 = 4/11 + 1/12,所以
Cardinality=1200*4/11 + 1200*1/12=436+199=536。

对于case 5和case 6,他们的算法是一样的:
selectivity of (month_no between 6 and 9)= selectivity of (month_no >=6 and month_no <= 9)
= (9-6)/(12-1) + 1/12 + 1/12 = 3/11 + 1/6
Cardinality = 1200 * (3/11 + 1/6) = 527

Oracle的公式似乎总是算出有误差的结果,是公式的问题么?其实公式没有什么问题,这个公式只是不太适合于我们这种distinct值太少的情况。如果我们的数据分布是类似于:1,2,3...100,101,102...1200,当我们计算where x>800的时候,我们的Cardinality=(1200-800)/(1200-1)*1200=400.3,这时候其实是一个比较精确的结果。由此我们知道其实Oracle的CBO并不是向我们想象的那么聪明,他只是一个还有待改进程序而已。其实上面这些实验所反映出的问题还不是最严重,想一下如果一个程序里面一个列是日期,这个列的值的分布是2006年1月1日到2006年12月31日,本来这个列的值是有一些Null值的,但后来我们认为Null值是不被允许的,我们决定把所有的Null改成9999年12月31日,想想这样会对我们的范围查询产生什么影响,这时候当我们查询day<2006年1月10日 的时候,我们原本的selectivity=9/364(实际上要小于这个值一点,因为要考虑原来有多少的null值),但现在我们可以想象,修改后的selectivity=9/2917444。这将带动整个explain plan的改动,我们前面说过selectivity对于索引的取舍,join的顺序是有很大影响的。


对于绑定变量的范围查询,Oracle不再做具体的计算,总是使用内部设定的一个selectivity,也就是5%,当我们查询month_no < :b1,Cardinality = 1200 * 5%=60,而当查询month_no > :b1 and month_no < :b2,Cardinality = 1200 * 5% * 5%=3。(其实这个5%很明显是一个比较适合于OLTP系统的估计值,而不适合于DW系统)

尽管很多资料建议应用里应该尽量使用绑定变量,但我们应该知道绑定变量不是什么时候都好用的。在OLTP里面绑定变量是个宝,因为在事务频繁却很类似的系统里,时候绑定变量可以让Oracle尽量重用相似的SQL,避免大量的hard parse,而且在Oracle9i里面还引入了一个对于绑定变量是很好的特性,就是bind variable peeking,这个特性是当一个SQL在第一次使用的时候,CBO会根据绑定变量的值来确定最好的执行计划。但是当以后我们使用相同的SQL(但是不同的绑定变量)的时候,CBO就直接使用以前生成的执行计划,不再对照绑定变量的值(否则绑定变量也就没有什么意义了),这其实有一些问题,但对于OLTP来说,这种问题一般影响并不大,因为OLTP里面同样的SQL,尽管绑定的值不一样,但一般selectivity是差不多的。但是到了DW系统里面,这就可能引起很大的问题,所以一般DW系统都是不太使用绑定变量的。


实验4

我们继续我们的最后一个实验,这一次我们不在使用and, in,我们看看or的情况:

SQL> select count(*)
2 from audience
3 where month_no > 8
4 or month_no <= 8
5 ;

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT ptimizer=ALL_ROWS (Cost=2 Card=1 Bytes=3)
1 0 SORT (AGGREGATE)
2 1 TABLE ACCESS (FULL) OF 'AUDIENCE' (Cost=2 Card=986 Bytes=2958)

这里的explain plan给出了很可笑的结果,因为我们认为month_no>8 or month_no<=8的Cardinality应该是1200,但CBO给出的结果是968,实际上这次又是CBO使用了基本上正确的公式,但在特殊的情况下算出了错误的结果。当条件里面出现多个条件的时候,CBO计算selectivity的通用的公式是:

The selectivity of (predicate1 AND predicate2) = selectivity of (predicate1) * selectivity of (predicate2).

The selectivity of (predicate1 OR predicate2) = selectivity of (predicate1) + selectivity of (predicate2) - selectivity of (predicate1 AND predicate2) (否则中间的部分你会算两次,基本上是个初中水平的问题:))
The selectivity of (NOT predicate1) = 1 – selectivity of (predicate1) ... (绑定变量是个例外)

注:前面的month_no between 6 and 9和month_no >=6 and month_no <= 9,是作为一个特例,当看作一个单一的range的查询了。

用这个公式来计算month_no > 8or month_no <= 8的selectivity就是:
(selectivity of month_no > 8) + (selectivity of month_no <=8) - (selectivity of month_no > 8)*(selectivity of month_no <=8)
因为
(selectivity of month_no > 8)=(12 – 8) / (12 – 1) = 4 / 11 = 0.363636,
(selectivity of month_no <=8)=(8 – 1) / (12 – 1) + 1/12 = 7/11 +1/12 = 0.719696
最后我们知道month_no > 8or month_no <= 8的selectivity=0.8216
于是算得Cardinality=986。

其实CBO使用的这个公式在很多情况下确实是可以正常工作的,但通过我们上面的实验,我们发现在某些情况下会得到意料之外的结果比如,我们看到的month_no > 8or month_no <= 8这个特例,是一个很特殊的情况,更常见的问题通常出现在当我们的条件是where col1= x and(or) col2 =y,但x和y有一定的关系的时候,我们来举个例子看一看:

还是我们的1200个听众的例子,如果现在我要知道出生在12月份的人有多少个,CBO会认为是100个。因为按照正常人的出生是按照1年12个月份平均的。
如果我问星座是白羊做的人有多少个,因为一共也是有12个星座,而且按照正常人的星座的分布也是平均的,所以CBO也会认为是100,这个也是个正常的结果。
现在如果我们12月份出生而且是白羊座的人有多少个人,这时候CBO一定会按照The selectivity of (predicate1 AND predicate2) = selectivity of (predicate1) * selectivity of (predicate2)这个公式计算,也就是1200*(1/12)*(1/12)=9。然而事实是白羊座的人是在3月和4月之间出生的人,所以真正的结果应该是0个人,这就是CBO的这个计算selectivity公式的问题,他不知道列与列之间的关系是怎样的。

在这里我们介绍了CBO计算selectivity基本方法,我们其实知道这些方法和公式是在很多情况下帮助我们得出正确的结果,但我们故意在实验中让CBO暴露出他的问题和局限,这些局限的是因为CBO本身只不过是一个软件,一些代码,不管Oracle怎么夸耀,软件总是有缺陷的。以前Oracle使用RBO的时代,我们需要了解不同的rule,现在RBO逐渐被替代为CBO,而我们也听到和看到CBO确实是比RBO更聪明,更强大了,但不要忘了CBO还是代码,总要有所依据,这些依据就是CBO所使用的公式和规则,这些东西不过是一种新的Rule而已,所以要想了解SQL在CBO下如何工作,了解CBO中的Rule是必要的。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/8410760/viewspace-732354/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2011-05-02

  • 博文量
    34
  • 访问量
    33582