Categories
程式開發

數據庫內核雜談(八):數據庫優化器(下)


在上一篇文章中,我們介紹了優化器的大概並且講解了一系列通過語句重寫來對查詢進行優化的方法。文末也留了一個坑:當語句中涉及到多個表的join時,優化器該如何決定join的順序(join ordering)來找到最優解呢?這期,我們接著這個話題往下說。

答案就是,優化器也只能盡力而為。上一篇文章中我們提到過n個表的join搜索空間高達4^n,理論上只有窮盡搜索空間,才能保證找到最優解。但即便有時間和能力窮盡搜索空間,也未必能找到最優解(此為後話,暫且不表)。因此優化器的主要職責是,在資源限制內,這裡資源可以是計算資源或者優化時間,找到盡可能足夠好的執行計劃。

啟發式算法(Heuristic approach)

4^n的搜索空間實在太大了,首先要做的就是,減小搜索空間。數據庫的先賢們,想到了應用啟發式算法(heuristic approach)來降低搜素空間。比如,最早的Volcano Optimizer裡,就提出了對於Join-order,只考慮left-deep-tree,即所有的右子樹必須是一個實體表。可能解釋起來不太直觀,對應下面三張不同的join-order的樹形結構,就一目了然了。

數據庫內核雜談(八):數據庫優化器(下) 1

left-deep-tree

數據庫內核雜談(八):數據庫優化器(下) 2

bushy-tree 1

數據庫內核雜談(八):數據庫優化器(下) 3

bushy-tree 2

其中圖1就是left-deep-tree,圖2和圖3稱為bushy-tree。那為什麼只選擇left-deep-tree?要知道,即使是left-deep-tree,搜素空間也有n! 。我自己的理解是結構比較簡單,執行計劃也很直觀:左邊的表不斷和右邊的表join生成新的intermediate表(中間表),然後不斷遞歸。在講join實現的那章時,我們提到過,大部分情況下都會使用HashJoin。如果能夠使得左邊的result set一直很小,從而建立的Hash表能一直存放在內存中的話,對於全部右子樹的表,只要進行一次全表掃描,即可得到最終結果。因此,右子樹的table order就不是特別影響運行時間了(因為總是得至少進行一次全表掃描的)。這種情況下,已經算是很優的執行計劃了。

說完了優點,再來看看left-deep-tree有什麼不好的地方?那就是不能同時執行多個join。如果按圖3中的bushy-tree 2,那A和B, C和D可以同時進行join。對於現在服務器配備多個CPU和大內存作為計算資源,考慮bushy tree,肯定是會有更多的優化可能的。反之,也可能因為早期的服務器並沒有那麼多計算資源,本來也並不考慮對一個SQL查詢進行並行執行,因此採用left-deep-tree的heuristic,也就說得通了。

因此,left-deep-tree的join ordering優化關鍵在於能夠讓左邊的結果集, 從一開始的葉節點以及後續的所有intermediate result越來越小,最好能一直fit in memory,這樣就能保證所有的右子樹表只需要進行一次全表掃描。要如何選擇哪個表放在哪個位置呢?我們需要一些概率統計的知識。

Cardinality Estimation

Cardinality estimation,就是用來預測單個表的selection cardinality和2個表的join cardinality的技術。首先,簡單介紹一些術語。

Selection cardinality: SC(P, R)

表示當predicate是P的時候,對於表R,最後大約會有多少條row輸出。

舉個例子,對於表student, 假設P為 major = ‘CS’, 相當於我們要計算下面這個SQL有多少row輸出。

SELECT * FROM student WHERE major = 'CS';

要對輸出進行預測,我們先要對錶收集一些基本的元信息。有哪些信息呢? 1)對於表student,首先需要知道總共有多少row;2)對於student表中的每個column,總共有多少個distinct value。你可能會想, 數據庫是什麼收集這些數據的呢?有些數據庫會不定期地自動更新每個表以及每個column的統計信息,一般都還提供相關的語句來讓數據庫對某個表做元數據的統計:analyze TABLE語句。有了這兩個信息,那我們怎麼計算selection cardinality,再來看下面這個公式。

SC(P, R) = N_R * SEL(P, R) 

這邊SEL§ 就是統計意義上每個row滿足P的概率。那怎麼計算SEL§呢。假設P很簡單,只是單個column的equality,比如上述示例 major = ‘CS’。基於distinct value的信息,我們假設V(major, student)總共有10個專業,在此基礎上,我們進一步假設數據均勻分佈,那major = 'CS'的概率就是10%, 即SEL(major = ' CS', student) = 10% 。如果N_R = 100。那我們就可以推算出SC(major = ‘CS’, student)約等於10條輸出。是不是挺簡單的,下面來看一些複雜的predicate的預測。

如果P並不是簡單的equality join,比如 age != 30。假設 SEL(age = 30, student) = 90%, 可以通過negation推算出 SEL(age != 30, student) = 10%

如果P是age > 30呢?這時候就需要用到大於30的age還有多少個distinct value,我們假設age總共有10個distinct value,且大於30的還有4個值,再次基於數據均勻分佈假設,就可以推算出SEL( age > 30, student) = 40%。

再來看更複雜一些的predicate,如牽涉多個column的。如果是P是age = 30 and major = ‘CS’。這裡,我們需要一個新的假設,樸素貝葉斯定理假設條件互相獨立。則SEL(age = 30 ^ major = ‘CS’, student) = SEL(age = 30, student) * SEL(major = ‘CS’, student)。

如果predicate的condition是disjunction,如SEL(age = 30 V major = 'CS', student) = SEL(age = 30, student) + SEL(major = 'CS', student) – SEL(age = 30, student ) * SEL(major = 'CS', student)。可以根據下圖來推出這個公式:

數據庫內核雜談(八):數據庫優化器(下) 4

disjunction
講完了單個表的selection cardinality。那join cardinality呢?比如下面這句語句:

SEL * FROM R1, R2 WHERE R1.a = R2.a;

由於本人數學實在不好,就直接給出公式了:

JC(R1, R2, R1.a = R2.a) = N_R * N_S / max(V(a, R), V(a, S))

其中V(a, R)就是指對於表R中column a,一共有多少個distinct value。

剛剛我們通過示例講解了許多計算selection cardinality和join cardinality的方法。但剛才所有的計算假設都是數據是均勻分佈(uniformly distributed)。現實情況肯定不會這麼容易,比如我們計算major = 'CS’的student,CS專業的學生肯定比其他專業學生要多一些。那有什麼辦法可以改進嗎?另一種常見的對column的值分佈進行統計的方法就是使用Histogram。 Histogram呢,除了統計有哪些distinct value,還記錄了這些value分別出現了幾次,下圖給出了一個Histogram統計的示例。

數據庫內核雜談(八):數據庫優化器(下) 5

Histogram example
由於牽涉過多數學,我們就不展開了,有興趣的同學可以參考這裡

Histogram通過存儲更多的信息來統計更精確的數值分佈。但很多情況下,統計並不需要那麼精確。工程方面要在使用資源和準確性裡找平衡。後來,又有大牛提出了HyperLogLog,是一種佔用資源少,但能給出較為準確的近似結果的cardinality estimator。

總結一下,有了cardinality estimation,我們終於能預測哪兩個表join後的cardinality比較小,可以用來決定join ordering了。但同時也發現,cardinality estimation給出的只是預測結果,這也是為什麼文章開頭的時候談到,即使能夠窮盡搜索空間,依然不一定能找到最優解的原因。因為預測的結果是有出入的,並且隨著join變得更複雜, 層級越多,越往上的誤差就越大。

Cardinality estimation僅僅是幫助決定了join ordering,相當於logical operator tree上,不同的表分別應該放在哪個位置。但對於每個logical operator,最後還需要變換成physical operator (物理算子)才算完成最終的優化。如,對與TableScan這個邏輯算子,它對應的physical operator有SequentialScan和IndexScan,應該用哪個?對於JoinOperator,到底是用NestedLoopJoin, SortMergeJoin,還是HashJoin呢?下面,我們介紹第二個關鍵技術。

Cost Model

Cost Model的主要思想是,對於每一個Physical operator,根據輸入輸出的cardinality,會被賦值一個cost(代價)。這個cost,通常情況下可以認為是執行這個operator需要的時間,當然也可以是計算資源。那如何計算這個cost呢?對於每個operator,都有一個cost formula(公式),這個公式根據輸入輸出的信息,最後能計算出這個operator的cost值。

還是配合示例來講解:對於SequentialScan(全表掃描),它的cost formula我們定義成如下:

Cost = NumRowsInTable * RowWidth * SEQ_SCAN_UNIT_COST

解釋一下這個公式,因為對於全表掃描,需要讀取所有的row,因此讀取時間大致正比於表的total row * 表的width。而最後的coeffficient SEQ_SCAN_UNIT_COST,可以想像成是一個虛擬的時間單位。

對於IndexScan呢?它的cost formula又長成什麼樣呢?區別於Sequential Scan,它不需要全表掃描,但對於從Index中讀取滿足條件的Row,需要回到原表中讀取,相當於執行了random IO。因此,我們可以根據操作的實現,定義它cost formula如下:

Cost = SelectionCardinality * RowWidth * INDEX_SCAN_UNIT_COST

而這邊,INDEX_SCAN_UNIT_COST可以認為是random IO的cost,所以它的值應該要比SEQ_SCAN_UNIT_COST要大很多。比如,我們假定SEQ_SCAN_UNIT_COST值為1,那INDEX_SCAN_UNIT_COST就可以設為100。先不管這樣設是否準確。但有了cost formula的定義,我們就能計算每個physical operator在當前環境下的cost了。再來參考下面這個示例:

SELECT * FROM student WHERE major = 'CS';

現在假設,student表對major建有index,然後st​​udent表總共有10000個row,然後假定cardinality estimation給出的selection cardinality是500,即有500個CS學生。我們再假設width是10。分別把這些信息帶入SequentialScan和IndexScan的公式可得:

SequentialScan Cost = 10000 * 10 * 1 = 100000

IndexScan Cost = 500 * 10 * 100 = 500000

在這種情況下,Optimizer就會選擇SequentialScan。但如果查詢語句變了,變為major = ‘archaeology’ (考古學),作為一個冷門專業,cardinality estimation預測只有10。再分別計算cost:

SequentialScan Cost = 10000 * 10 * 1 = 100000

IndexScan Cost = 10 * 10 * 100 = 10000

在上述情況下,optimizer就應該選擇IndexScan。

那如何定義cost formula和coefficient的值呢?這確實是一個很難的問題。筆者曾經做過相關的research,cost formula是需要根據operator的實現來定義的。甚至一個operator,根據不同的執行環境,都會有不同的cost formula。 cost formula意在去simulate真實執行下所花掉的時間。而對於coefficient,筆者當時提出的方法就是通過執行mini-benchmark來calibrate coefficient的值,因為不同的部署環境,網絡條件和硬件資源,都會影響coefficient。當時對一些operator進行了測試,calibrate後,效果立竿見影,只可惜後來離開公司了,沒能把這個research做完。

講完了單個operator,我們再來看全局。對於一個logical operator tree,Optimizer要做的就是,當它變換成Physical operator tree後,所有的operator的cost相加(也可以是有權重的相加,假定多個operator可以並行執行,這邊我們暫且不考慮這種複雜情況)後,使得total cost最小,這便是optimizer給出的最優physical execution plan。

你可能會覺得,似乎對於每一個logical operator, 選擇哪一個physical operator是一個local optimization的問題。至少Scan operator看上去是這樣的。其實並沒那麼簡單。還記得我們說過index Scan帶來的一個好處是什麼嗎?就是讀取後的數據是有序的。有序是一個很好的屬性,如果上層的operator對有序有需求,比如SortMergeJoin,或者SortGroupByAggregate,那原本需要排序的cost就被省去了。因此對於同一個operator,它的cost不僅僅和自己的cost formula相關,還和它的子節點的operator也相關。比如對於SortMergeJoin operator來說,它的兩個子節點都是IndexScan, 或者是Sequential Scan會對它本身的cost產生影響,如果是sequential scan的話,排序的cost是需要計算在它的cost formula裡的,但如果是index scan,那排序的cost就為0了。因此,計算每個operator的cost是一個global optimization的問題。假定,對每個operator,我們定義一個aggregated cost等於它本身的cost加上所有子節點的cost。那Optimizer要求解的就是使得root operator的aggregated cost最小的physical operator tree。是否有聯想到什麼算法了嗎? global optimization? Bingo!就是dynamic programming。我覺得這可能是我工作中遇到的第一個真正使用DP解決的問題了吧:多階段決策最優解模型;求解過程中需要多個決策階段,每個決策階段都會取決於最優子結構;並且,最優子結構屬於重複子問題,因為會被多次使用到。上層無論是HashJoin或者是SortMergeJoin都會需要知道下層表的SequentialScan的cost是多少。因此我們需要memorize這個SequentialScan的cost。整個計算過程自頂向下遞歸,對於子問題memorize結果,最終我們就能計算出最小的root operator的aggregated cost, 以及它所對應的physical operator tree。這就是最後optimizer輸出的physical execution plan。

總結

今天我們先從join ordering問題講起,介紹了cardinality estimation技術,它通過預測selection cardinality和join cardinality來幫助決定join ordering。然後介紹了cost model來對每個對應的physical operator計算cost。最後通過dynamic programming來求解最小cost的physical operator tree,以此得到最終的physical execution plan。

終於,理論部分講完了。這兩期比較枯燥和深奧,但為了完整性,我覺得還是有必要的。最後,推薦大家一篇paper,介紹一個開源的數據庫優化器ORCA的設計和實現(本人也是作者之一)。這是我當時第一份工作時參與的項目。

說了那麼多枯燥的理論,咱們以一個小趣事結尾吧。當時我問組裡的人為什麼叫ORCA(虎鯨),是不是因為虎鯨很聰明?然後組裡的頭說”let me show you something”。然後打開Youtube,放的是一段幾頭虎鯨圍獵一群海豚的視頻,場面略帶血腥。頭邊放邊說,“look at these babies, they are so smart!” 當時我也是虎軀一震。後來我仔細去查了一下,虎鯨生性殘暴,喜歡虐殺。還有相關research說,從已經解析的虎鯨叫聲中發現,大約70%的叫聲都是抱怨和咒罵。 。可見脾氣之暴躁。但誰讓它長得萌,和大熊貓一樣黑白配。所以說,這是一個看臉的世界。相對的,大白鯊,一副凶神惡煞的樣子,被拉了不少仇恨。但你不知道,大白鯊,特別怕虎鯨,特別怕。

相關閱讀:

數據庫內核雜談(一):一小時實現一個基本功能的數據庫

數據庫內核雜談(二):存儲“演化論”

數據庫內核雜談(三):索引優化

數據庫內核雜談(四):執行模式

數據庫內核雜談(五):如何實現排序和聚合

數據庫內核雜談(六):表的 JOIN(連接)

數據庫內核雜談(七):數據庫優化器(上)