150      阿裏雲  技術社區[雲棲]

SQL優化器原理 - Join重排

這是ODPS有關SQL優化器原理的係列文章之一。我們會陸續推出SQL優化器有關優化規則和框架的其他文章。添加釘釘群“關係代數優化技術”（群號11719083）可以獲取最新文章發布動態。

本文的目標是解釋Join重排這個特性的基礎概念和算法，如果想快速了解並在ODPS上使用這個特性，請直接跳到“總結”。

簡介

Join重排是經典的SQL優化問題。考慮3個表的自然連接 A ⋈ B ⋈ C ，在不影響最終結果集的前提下，可以改變連接的順序為下列：

1. A ⋈ C ⋈ B
2. B ⋈ A ⋈ C
3. B ⋈ C ⋈ A
4. C ⋈ A ⋈ B
5. C ⋈ B ⋈ A

熟悉SQL開發的讀者會明白，這個順序可能極大影響SQL執行的效率。打個比方，A，B，C的數據量各自是100條記錄，如果A ⋈ C的數據量是1條記錄，A ⋈ B是100條記錄，顯然A ⋈ B ⋈ C的效率低於A ⋈ C ⋈ B，因為前者的中間結果是100條記錄，而後者是1條，並且最終結果的數據量是相同的。因此我們得到結論1。

結論1：Join的順序影響中間結果的數據量，決定了Join的執行效率

另外一種影響Join效率的原因是Join算法。考慮Hash Join算法（對MaxCompute熟悉的讀者可以理解為MapJoin），它提前把右邊表的數據建立一張哈希表，循環獲取左邊表的記錄查表做Join。假設建立哈希表的代價很大，且隨數據量線性遞增，那麼我們總希望更小的數據集在右邊。假設A表是100條記錄，B表是10條記錄，那麼A ⋈ B優於B ⋈ A。因此我們得到結論2。

結論2：Join的順序影響具體Join算法的效率，決定了Join的執行效率

綜上所述，Join的順序很大程度決定了Join的執行效率。這麼看來，在開發SQL程序的時候，我們一定要仔細安排Join的順序，讓它達到最優的執行效率？不盡然。事實上，Join重排的難度如此之大，以至於手工調整是不現實的。主要的難度體現在兩部分：

1. 窮舉和驗證最優方案的算法複雜度是指數級的（NP hard問題）
2. 獲取某個Join的中間結果數據量的代價很大。我們不得不實際執行一遍Join才能獲知中間結果數據量，每個Join都可能花費數小時甚至數天。

因此必須借助機器自動優化。在最新的MaxCompute SQL 2.0中，基於代價的優化器（Cost Based Optimizer，CBO）已經包含了Join重排的優化規則。在本文中，我們嚐試從算法、代價計算、數據量估計等方方麵麵解釋Join重排，也會包含一部分CBO的基本概念。

問題分類

Join樹

在SQL優化器程序中表達的Join大部分時候是一棵二叉樹。把Join節點作為二叉樹的節點，可以構建一棵Join樹。

例如，上述的A ⋈ B ⋈ C生成的邏輯執行計劃（Algebrized Tree）如下：

生成的Join樹如下：

至此一切都很完美，每個查詢都是樹，直到有一種奇怪的查詢闖進了這個森林。考慮以下Join：

SELECT * FROM A JOIN B ON A.id = B.id JOIN C ON B.id = C.id

顯然，通過A.id = B.id and B.id = C.id可以推出另一個Join，即C.id = A.id，這時的Join"樹"是這樣的：

這種形態稱為 有環 的Join樹。有環在Join重排算法裏會非常複雜，大部分的算法不支持環。當然我們可以考慮隨機刪除某個Join操作，保證整個Join樹 無環 ，但是這麼做會損失一些優化的可能性。

Join樹形態

上文提到的Join樹在SQL的邏輯表達中通常是一個 偏樹 。考慮A ⋈ B ⋈ C ⋈ D，這棵偏樹的形態如下：

我們稱這種Join樹為 左深（Left-deep）樹 ，對應的也有 右深樹 。在單機／單任務數據庫上，我們隻考慮這種形態的Join樹就可以做Join重排，但是在分布式環境，我們還要考慮 稠密（Bushy）樹 ，如下圖所示：

顯然，如果有更多計算節點，AB和CD可以並行執行，從而降低整體響應時間。大部分的Join重排算法隻能支持左深樹，我們會在後續提到稠密樹的增強算法。MaxCompute SQL 2.0支持了稠密樹的重排算法。

笛卡爾積

區別於自然連接，笛卡爾積將兩邊的輸入做兩層循環的完全展開。部分Join重排算法不支持笛卡爾積。

綜上，我們有“有／無環”，“左深／稠密樹”，“支持／不支持笛卡爾積”這三類8種問題分類。

動態規劃算法

終於到了Join重排算法了！希望之前的概念解釋沒有嚇跑你。首先看 動態規劃算法 ，這是一個非常自然的Join重排算法，它最早是由P. Griffiths Selinger etl在1979年提出 [Selinger79]，並使用在數據庫鼻祖級的係統System R上。

動態規劃保留所有可能的Join順序，加入到CBO的執行計劃選項（被稱為Memo的一個數據結構）中，最後由代價模型選擇最優的Join順序。為了避免代價被反複計算，使用動態規劃的算法記錄局部最優的代價。

這是一種窮舉（exhaustive）算法，但是我們通常提到的Join重排都不是窮舉算法，因為它的複雜度實在是太高了！考慮n個輸入自由組建一棵左深樹或稠密樹的所有可能性，它的複雜度是卡特蘭數序列，下表是一個直觀的例子：

在MaxCompute中，我們最初利用了這個算法，因為它在理論上總能找到最優解（區別於後續我們提到的算法，理論上隻能找到次優解），並且支持稠密樹和笛卡爾積。為了降低它的複雜度，我們用了一些限製：

1. 不區分A ⋈ B和B ⋈ A（交換）
2. 僅處理n<=5的情況，當n>5時，分裂為多個n<=5的組分別做Join重排

截止本文，MaxCompute線上仍然使用以上限製的動態規劃算法。你可以通過set odps.optimizer.cbo.rule.filter.white=pojr打開Join重排。但是，正如我們看到的，這個算法複雜度非常大，限製也非常多。我們在最新未發布的版本使用了啟發式算法替換它。

啟發式算法

為了降低動態規劃算法的複雜度，我們必須在Join重排算法上就開始做剪枝，而不是把所有可能性都留下來。需要解釋的是，啟發式算法同樣是建立在動態規劃算法上的一種優化，而不是獨立的自成一套。

既然要“啟發”，就需要一個定義什麼是 好 的Join。我們需要引入一個評估體係，被稱為cost function（如果讀者對CBO熟悉，這裏的cost不是指CBO框架的代價，而僅僅是用於評估Join順序好壞的一個公式，因為此時Join並沒有build，我們無法獲取準確的cost）。為了簡化問題，接下來我們使用的cost function都等於Join的輸出數據量（cardinality。有關cardinality的估計算法是另一個大話題，留到下一篇文章解釋，此處請讀者先假定我們有能力獲取一個精確的cardinality）。選擇執行計劃的準則就是選擇cost最小的那個。

最重要的啟發式算法有貪婪算法和GOO算法兩種。MaxCompute采用了增強的GOO算法。

貪婪算法

貪婪算法考慮邏輯執行計劃，以輸入為節點，每次選取cost最小的節點直到所有節點都被選取，從而組建一個左深樹作為最後的Join重排順序。貪婪算法隻支持左深樹。

最基礎的貪婪算法的偽代碼如下：

ø = {所有輸入}
orders = {}
while ø != {}
  n = ni of min(cost(orders ⋈ ni)) for ni in ø
  orders = orders + n
  ø = ø - n  
return orders

實踐中，這個算法很容易受到第一個輸入選擇的影響，因為首次選擇節點，cost({} ⋈ ni)，還沒有任何Join，這個cost被定義為ni的cardinality，小表會優先選擇，這並不一定是最好的。因此一個改進的算法是在首次選擇時，所有表都有機會，偽代碼如下：

ø = {所有輸入}
options = {}
for n in ø
  orders = {n}
  rest = ø - n
  while rest != {}
    n = ni of min(cost(orders ⋈ ni)) for ni in ø
    orders = orders + n
    ø = ø - n  
  options = options + orders  
return i of min(cost(i)) for i in options

貪婪算法的好處是，它每次選擇的一個Join都是可以實際執行的（區別於下文的GOO算法，選擇的可能是一個中間Join），因此我們很容易計算cost。和所有的啟發式算法一樣，它隻能獲得次優解。考慮到它不支持稠密樹，我們沒有選擇這個算法。

GOO算法

區別於貪婪算法以輸入為節點，GOO（Greedy Operator Ordering）考慮Join樹，以Join為節點。它循環選擇一個節點，和已選擇的所有節點嚐試Join並選擇代價最小的那個，生成一個新的節點，直到所有的節點都被選擇了。

考慮A ⋈ B ⋈ C ⋈ D的例子，如果cost的估計結果是 A ⋈ B < C ⋈ D < B ⋈ C，GOO算法的執行過程如下圖所示：

這個算法的複雜度比貪婪算法高，cost估計從實體的輸入改為抽象的Join，難度更大，但是它的優勢在於支持稠密樹。MaxCompute最新的版本使用了這種算法。

KBZ算法

KBZ或IIKBZ是在cost function滿足ASI（adjacent sequence interchange）條件下理論最優的啟發式算法。因為MaxCompute無法滿足ASI，且KBZ僅支持左深樹，我們沒有考慮KBZ算法。感興趣的讀者可以參考 [Ibaraki84]。

隨機算法簡介

我們之前討論了動態規劃算法，也討論了啟發式算法。這兩種算法是兩個極端，前者保留所有的Join形態，後者隻保留唯一的Join形態，這是算法複雜度和最優解之間的tradeoff。實際操作中，這兩個極端通常不是好的策略，我們希望有更折中的辦法，這就是 隨機算法 。

Random Walk算法 是最基礎的隨機算法。在次優解的基礎上隨機改變一些排序，嚐試查找更優的方案。__Iterative Random Walk算法__ 做了改進，避免Random Walk生成的環。

折中的考量最後回到了基本的最優化問題上。數學上的一些算法也被應用於Join重排，討論比較多的包括 模擬退火算法 和 基因算法 [Steinbrunn]。

擴展問題

稠密樹偏好

像MaxCompute這樣的分布式係統下，我們更偏好生成稠密樹，因為分布式係統可以並行執行那些在樹中同深度的Join。怎樣表達這樣的偏好是一個難題。

在我們的實現中，我們對cost function施加一個深度的懲罰（例如，每一級深度施加30%的cost懲罰），我們通過“深度厭惡”這個想法來表達“稠密樹偏好”。

Join 分組

在現實中，某些Join可以被合並在一個分組裏實現。如果讀者熟悉MaxCompute，容易理解有兩類分組：

1. 對於Sorted Merge Join，當參與Join的每一路輸入，Join key都是相同的，可以在一個task完成。
2. 對於Map Join，當大表是相同的，可以在一個map裏完成。

顯然，Join分組很大程度影響了代價，從而影響了最優順序。我們在Join重排的實現會保留兩種optional plan：合並的方案和不合並的方案，留給CBO框架去選擇最優方案。

總結

這篇文檔中，我們解釋了Join重排這一優化的意義、概念和經典的幾種算法。

1. 動態規劃的算法總能找到最優方案，但是複雜度是最高的。
2. 啟發式算法的複雜度最低，隻能找到次優解。
3. 隨機算法的效果是上麵兩種算法的折中。

MaxCompute最新的算法使用了啟發式的GOO算法。在線上運行的MaxCompute還在使用受限的動態規劃算法。從經典的數據倉庫測試集TPC-H的測試發現，使用受限的動態規劃算法可以幫助我們獲得額外的8%以上的性能提升。

Join重排是一個較激進的優化規則，考慮到CBO無法完美估計數據量（這在我們的後續文章中解釋），打開這個規則可能會產生worst plan。這個worst plan的比例經過我們線上實測是非常低的，但是我們仍然不得不默認關閉Join重排規則，你可以嚐試設置odps.optimizer.cbo.rule.filter.white=pojr來打開某個query或project的Join重排特性。

索引

[Selinger79] Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, I. A., Price, T. G., Lorie, R. a., … Price, T. G. (1979). Access path selection in a relational database management system. ACM SIGMOD International Conference on Management of Data., 23–34. https://doi.org/10.1145/582095.582099

[Ibaraki84] Ibaraki, T., & Kameda, T. (1984). On the optimal nesting order for computing N-relational joins. ACM Transactions on Database Systems, 9(3), 482–502. https://doi.org/10.1145/1270.1498

[Steinbrunn] Steinbrunn, M., Moerkotte, G., & Kemper, A. (n.d.). Optimizing Join Orders, 1–55.

最後更新：2017-08-25 10:32:32

  上一篇：  一個由正則表達式引發的血案

  下一篇：  怡海軟件：如何成為Salesforce 專家?