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推出了直方圖，多列統計信息，拓展統計信息等技術來彌補原本算法的不足。這些技術的使用也將另起一文。
對于本文中有表述錯誤或者片面的地方，還請大家多多指出；還有解釋不清的地方，也可以告訴我，在下一篇中做下解釋。