CBO的相關(guān)原理

CBO在oracle7中被引入，基于數(shù)據(jù)對(duì)象的統(tǒng)計(jì)信息（包括數(shù)據(jù)集的行數(shù)，唯一值的個(gè)數(shù)等等）來計(jì)算執(zhí)行計(jì)劃的執(zhí)行成本。隨著版本的演化，CBO逐漸完善起來，在9i開始使用系統(tǒng)統(tǒng)計(jì)信息(system statistics，系統(tǒng)統(tǒng)計(jì)信息的出現(xiàn)是為了估算SQL在CPU方面的消耗)。但是CBO仍然存在一些缺陷，通過了解CBO的一些相關(guān)原理，其缺陷大家也就很容易理解了，從而也會(huì)明白，很多時(shí)候CBO所依賴的統(tǒng)計(jì)信息都收集的百分之百準(zhǔn)確了，還是會(huì)選錯(cuò)執(zhí)行計(jì)劃的原因。

創(chuàng)新互聯(lián)公司長(zhǎng)期為上千客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為北塔企業(yè)提供專業(yè)的成都做網(wǎng)站、成都網(wǎng)站建設(shè)，北塔網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

執(zhí)行計(jì)劃的選擇

CBO在生成一條執(zhí)行計(jì)劃后，會(huì)計(jì)算其成本；然后和已經(jīng)生成的執(zhí)行計(jì)劃中成本最低的進(jìn)行比較。這種比較在以下條件滿足其一就停止：

1.    所有執(zhí)行計(jì)劃都已經(jīng)被計(jì)算過

查詢塊的join排列數(shù)超過了OPTIMIZER_MAX_PERMUTATIONS（10g及以后為_OPTIMIZER_MAX_PERMUTATIONS）參數(shù)指定的值。默認(rèn)是2000.
我們可以做個(gè)簡(jiǎn)單的計(jì)算，比如下面這個(gè)SQL：

一個(gè)查詢塊中有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
......
所有可能的排列數(shù)就是7!=5040，遠(yuǎn)遠(yuǎn)超過了OPTIMIZER_MAX_PERMUTATIONS的默認(rèn)值。那么這種情況下，CBO不會(huì)把所有可能的join順序計(jì)算一遍。這就有可能錯(cuò)過了成本最低的執(zhí)行計(jì)劃。之所以這么設(shè)計(jì)是防止過多的對(duì)執(zhí)行計(jì)劃成本的比較導(dǎo)致花費(fèi)在SQL解析的時(shí)間過長(zhǎng)。

成本計(jì)算的基本概念

1 cardinality（基數(shù)）

cardinality指的是一個(gè)行源的結(jié)果集的行數(shù)。比如在下面這個(gè)查詢中，返回的為emp表的所有行，基數(shù)就是表的行數(shù)14.

再比如：

其cardinality是emp表經(jīng)過謂詞過濾（job='CLERK'）返回的行數(shù)4.

2 selectivity（選擇率）

選擇率，也叫選擇性，和cardinality密切相關(guān)。選擇率的計(jì)算公式如下：

比如emp表共有14行，empno是主鍵，那么每一個(gè)值出現(xiàn)的頻率就是1/14.那么下面這條sql的過濾條件選擇率就是1/14.

我們知道CBO在執(zhí)行計(jì)劃的某一步選擇訪問全表還是索引時(shí)會(huì)考慮到選擇率，從上面的公式可以看出，要得出選擇率需要知道兩個(gè)數(shù)據(jù)。下面仍然以1.cardinality部分的例子，解釋CBO如何根據(jù)統(tǒng)計(jì)信息來計(jì)算選擇率。

可以看到這條sql實(shí)際返回4條，但是rows部分的值為3.3是怎么被算出來的呢？

首先，CBO從統(tǒng)計(jì)信息中獲得emp表的總行數(shù)為14；然后根據(jù)job這一列上的唯一鍵值（num_distinct）得出該列上等值條件的選擇率為1/5（即1/num_distinct，在沒有直方圖的情況下，CBO認(rèn)為列值沒有數(shù)據(jù)傾斜，數(shù)據(jù)分布都是均勻的，那么列中的每一個(gè)值出現(xiàn)的頻率都是同樣的1/num_distinct）。這樣計(jì)算應(yīng)該得到的結(jié)果集為141/5=2.8，CBO的算法中對(duì)該結(jié)果還要向上取整（ceil），即結(jié)果是ceil(141/5)=3.
打個(gè)比方，在一個(gè)黑色布袋里放有若干白球和黑球，在沒有打開袋子去數(shù)的情況下，要猜測(cè)每個(gè)顏色的球各有多少個(gè)，只能先做一個(gè)假設(shè)它們的數(shù)量是差不多的。
可以預(yù)想，在一個(gè)有數(shù)據(jù)傾斜（即不同的唯一值對(duì)應(yīng)的行數(shù)差異很大）的列上，繼續(xù)使用這種算法，可能會(huì)產(chǎn)生錯(cuò)誤的執(zhí)行計(jì)劃。
下面創(chuàng)建一個(gè)有數(shù)據(jù)傾斜的表

現(xiàn)在如果我們查詢gender='M'的行的數(shù)據(jù)，顯然如果在gender列如果有索引，訪問索引獲得rowid后再回表是最高效的，但是根據(jù)前面的解釋，在收集了統(tǒng)計(jì)信息而沒有收集直方圖的情況下，CBO會(huì)認(rèn)為gender='M'返回的數(shù)據(jù)量為全部數(shù)據(jù)量的50%，從而選擇全表掃描。

可以看到rows對(duì)應(yīng)的值65537，確實(shí)是表的總行數(shù)*50%（向上取整）。
在實(shí)際的應(yīng)用場(chǎng)景里，表的過濾條件可能有多個(gè)，過濾條件之間有and或者or連接。這兩種情況下的選擇率的計(jì)算，和高中知識(shí)中計(jì)算概率的與或運(yùn)算很相似。
首先對(duì)于條件之間使用and的情況：
比如：select ... from a where a.col1=value1 and a.col2=value2。這種情況下，CBO是如何計(jì)算選擇率呢？我們?cè)谥暗睦由霞右粋€(gè)過濾條件：

可以看到rows部分預(yù)估的是1，實(shí)際有2條數(shù)據(jù)。我們把兩個(gè)過濾條件分別記為i和j，出現(xiàn)的頻率記為P(i)和P(j)，在沒有多列統(tǒng)計(jì)信息的情況下，CBO認(rèn)為i和j同時(shí)成立的頻率就是P(i)P(j).根據(jù)前面的解釋，我們知道P(i)=1/5，P(j)=1/3，那么P(i)P(j)=1/15.emp表的總行數(shù)為14，那么由這兩個(gè)過濾條件產(chǎn)生的結(jié)果集為ceil(14*(1/15))=1.
對(duì)于2個(gè)以上過濾條件的情況，也有類似的算法。比如有過濾條件i1,i2,i3...，in，那么最終的選擇率的算法為：

對(duì)于過濾條件之間是or的情況，算法為(涉及高中概率的知識(shí))：

可見如果當(dāng)過濾條件過多時(shí)，選擇率計(jì)算的結(jié)果很可能大大失真。
比如對(duì)于sql：

根據(jù)上面的公式算出來的選擇率很可能非常接近于0，據(jù)此計(jì)算出來的cardinality接近于1.而實(shí)際上返回結(jié)果很可能會(huì)有多條。

3 Transitivity(傳遞性)

transitivity是指CBO對(duì)過濾或者連接條件做一些等價(jià)轉(zhuǎn)換，使得原來僅僅作用在表A的過濾或者連接條件，可以作用在與A做JOIN的B表上。比如：

可以轉(zhuǎn)換成：

對(duì)于這種轉(zhuǎn)換，如果b表的col1列上有選擇性較好的索引，CBO就可以選擇訪問索引。RBO模式下是不會(huì)做此轉(zhuǎn)換的。
除了上面這種情況，還有join的傳遞：

轉(zhuǎn)換為

CBO的缺陷

通過前面這些介紹，我們可以得出CBO存在的缺陷：

1.    對(duì)于復(fù)雜SQL，有可能會(huì)無法覆蓋全部可能的執(zhí)行計(jì)劃，因此而忽略最佳的執(zhí)行計(jì)劃；

2.    在沒有收集直方圖的情況下，CBO認(rèn)為列的值是均勻分布的，對(duì)于有數(shù)據(jù)傾斜的表，這種假設(shè)將大大失真；

3.    在沒有多列統(tǒng)計(jì)信息和拓展統(tǒng)計(jì)信息的情況下，CBO認(rèn)為列和列之間是孤立的，在SQL包含多個(gè)列的過濾條件或者表之間做join的情況下，計(jì)算的選擇率很可能會(huì)失真。

我們常常聽到說，用explain,autotrace等從plan table里獲得執(zhí)行計(jì)劃是假的，或者rows等不準(zhǔn)等說法，原因就在這里。但是oracle的厲害之處在于可以不斷改進(jìn)CBO，像上面也提到了，oracle推出了直方圖，多列統(tǒng)計(jì)信息，拓展統(tǒng)計(jì)信息等技術(shù)來彌補(bǔ)原本算法的不足。這些技術(shù)的使用也將另起一文。
對(duì)于本文中有表述錯(cuò)誤或者片面的地方，還請(qǐng)大家多多指出；還有解釋不清的地方，也可以告訴我，在下一篇中做下解釋。