CBO的相关原理 系列一

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推出了直方图，多列统计信息，拓展统计信息等技术来弥补原本算法的不足。这些技术的使用也将另起一文。
对于本文中有表述错误或者片面的地方，还请大家多多指出；还有解释不清的地方，也可以告诉我，在下一篇中做下解释。