ITPub博客

首页 > 数据库 > Oracle > CBO的相关原理 系列一

CBO的相关原理 系列一

原创 Oracle 作者:沃趣科技 时间:2016-03-08 14:53:49 0 删除 编辑

CBO的相关原理

CBO在oracle7中被引入,基于数据对象的统计信息(包括数据集的行数,唯一值的个数等等)来计算执行计划的执行成本。随着版本的演化,CBO逐渐完善起来,在9i开始使用系统统计信息(system statistics,系统统计信息的出现是为了估算SQL在CPU方面的消耗)。但是CBO仍然存在一些缺陷,通过了解CBO的一些相关原理,其缺陷大家也就很容易理解了,从而也会明白,很多时候CBO所依赖的统计信息都收集的百分之百准确了,还是会选错执行计划的原因。

执行计划的选择

CBO在生成一条执行计划后,会计算其成本;然后和已经生成的执行计划中成本最低的进行比较。这种比较在以下条件满足其一就停止:

1.    所有执行计划都已经被计算过

查询块的join排列数超过了OPTIMIZER_MAX_PERMUTATIONS(10g及以后为_OPTIMIZER_MAX_PERMUTATIONS)参数指定的值。默认是2000.
我们可以做个简单的计算,比如下面这个SQL:

一个查询块中有7张表,这7张表做join可能的顺序有:

1.    a1 -> a2 -> a3 -> a4 -> a5 -> a6 -> a7

2.    a1 -> a2 -> a3 -> a4 -> a5 -> a7 -> a6

3.    a1 -> a2 -> a3 -> a4 -> a6 -> a5 -> a7
......
所有可能的排列数就是7!=5040,远远超过了OPTIMIZER_MAX_PERMUTATIONS的默认值。那么这种情况下,CBO不会把所有可能的join顺序计算一遍。这就有可能错过了成本最低的执行计划。之所以这么设计是防止过多的对执行计划成本的比较导致花费在SQL解析的时间过长。

成本计算的基本概念

1 cardinality(基数)

cardinality指的是一个行源的结果集的行数。比如在下面这个查询中,返回的为emp表的所有行,基数就是表的行数14.

再比如:


其cardinality是emp表经过谓词过滤(job='CLERK')返回的行数4.

2 selectivity(选择率)

选择率,也叫选择性,和cardinality密切相关。选择率的计算公式如下:

比如emp表共有14行,empno是主键,那么每一个值出现的频率就是1/14.那么下面这条sql的过滤条件选择率就是1/14.

我们知道CBO在执行计划的某一步选择访问全表还是索引时会考虑到选择率,从上面的公式可以看出,要得出选择率需要知道两个数据。下面仍然以1.cardinality部分的例子,解释CBO如何根据统计信息来计算选择率。


可以看到这条sql实际返回4条,但是rows部分的值为3.3是怎么被算出来的呢?

首先,CBO从统计信息中获得emp表的总行数为14;然后根据job这一列上的唯一键值(num_distinct)得出该列上等值条件的选择率为1/5(即1/num_distinct,在没有直方图的情况下,CBO认为列值没有数据倾斜,数据分布都是均匀的,那么列中的每一个值出现的频率都是同样的1/num_distinct)。这样计算应该得到的结果集为141/5=2.8,CBO的算法中对该结果还要向上取整(ceil),即结果是ceil(141/5)=3.
打个比方,在一个黑色布袋里放有若干白球和黑球,在没有打开袋子去数的情况下,要猜测每个颜色的球各有多少个,只能先做一个假设它们的数量是差不多的。
可以预想,在一个有数据倾斜(即不同的唯一值对应的行数差异很大)的列上,继续使用这种算法,可能会产生错误的执行计划。
下面创建一个有数据倾斜的表


现在如果我们查询gender='M'的行的数据,显然如果在gender列如果有索引,访问索引获得rowid后再回表是最高效的,但是根据前面的解释,在收集了统计信息而没有收集直方图的情况下,CBO会认为gender='M'返回的数据量为全部数据量的50%,从而选择全表扫描。

可以看到rows对应的值65537,确实是表的总行数*50%(向上取整)。
在实际的应用场景里,表的过滤条件可能有多个,过滤条件之间有and或者or连接。这两种情况下的选择率的计算,和高中知识中计算概率的与或运算很相似。
首先对于条件之间使用and的情况:
比如:select ... from a where a.col1=value1 and a.col2=value2。这种情况下,CBO是如何计算选择率呢?我们在之前的例子上加一个过滤条件:


可以看到rows部分预估的是1,实际有2条数据。我们把两个过滤条件分别记为i和j,出现的频率记为P(i)和P(j),在没有多列统计信息的情况下,CBO认为i和j同时成立的频率就是P(i)P(j).根据前面的解释,我们知道P(i)=1/5,P(j)=1/3,那么P(i)P(j)=1/15.emp表的总行数为14,那么由这两个过滤条件产生的结果集为ceil(14*(1/15))=1.
对于2个以上过滤条件的情况,也有类似的算法。比如有过滤条件i1,i2,i3...,in,那么最终的选择率的算法为:

对于过滤条件之间是or的情况,算法为(涉及高中概率的知识):

可见如果当过滤条件过多时,选择率计算的结果很可能大大失真。
比如对于sql:

根据上面的公式算出来的选择率很可能非常接近于0,据此计算出来的cardinality接近于1.而实际上返回结果很可能会有多条。

3 Transitivity(传递性)

transitivity是指CBO对过滤或者连接条件做一些等价转换,使得原来仅仅作用在表A的过滤或者连接条件,可以作用在与A做JOIN的B表上。比如:

可以转换成:

对于这种转换,如果b表的col1列上有选择性较好的索引,CBO就可以选择访问索引。RBO模式下是不会做此转换的。
除了上面这种情况,还有join的传递:


转换为

CBO的缺陷

通过前面这些介绍,我们可以得出CBO存在的缺陷:

1.    对于复杂SQL,有可能会无法覆盖全部可能的执行计划,因此而忽略最佳的执行计划;

2.    在没有收集直方图的情况下,CBO认为列的值是均匀分布的,对于有数据倾斜的表,这种假设将大大失真;

3.    在没有多列统计信息和拓展统计信息的情况下,CBO认为列和列之间是孤立的,在SQL包含多个列的过滤条件或者表之间做join的情况下,计算的选择率很可能会失真。

我们常常听到说,用explain,autotrace等从plan table里获得执行计划是假的,或者rows等不准等说法,原因就在这里。但是oracle的厉害之处在于可以不断改进CBO,像上面也提到了,oracle推出了直方图,多列统计信息,拓展统计信息等技术来弥补原本算法的不足。这些技术的使用也将另起一文。
对于本文中有表述错误或者片面的地方,还请大家多多指出;还有解释不清的地方,也可以告诉我,在下一篇中做下解释。

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

请登录后发表评论 登录
全部评论
杭州沃趣科技股份有限公司创建于2012年(股票代码:839849),是一家专注为企业用户提供基于高性能、高可用、可扩展的开放数据库云平台解决方案的国产厂商。公司创始团队为原阿里巴巴数据库技术团队核心骨干,凭借丰富的研发及运维经验,为行业客户提供数据库云产品及软硬件一体化解决方案。

注册时间:2016-07-18

  • 博文量
    219
  • 访问量
    661435