這是odps有關sql優化器原理的系列文章之一。我們會陸續推出sql優化器有關優化規則和架構的其他文章。添加釘釘群“關系代數優化技術”（群号11719083）可以擷取最新文章釋出動态。
本文的目标是解釋join重排這個特性的基礎概念和算法，如果想快速了解并在maxcompute上使用這個特性，請直接跳到“總結”。
join重排是經典的sql優化問題。考慮3個表的自然連接配接 <code>a ⋈ b ⋈ c</code> ，在不影響最終結果集的前提下，可以改變連接配接的順序為下列：
<code>a ⋈ c ⋈ b</code>
<code>b ⋈ a ⋈ c</code>
<code>b ⋈ c ⋈ a</code>
<code>c ⋈ a ⋈ b</code>
<code>c ⋈ b ⋈ a</code>
熟悉sql開發的讀者會明白，這個順序可能極大影響sql執行的效率。打個比方，a，b，c的資料量各自是100條記錄，如果<code>a ⋈ c</code>的資料量是1條記錄，<code>a ⋈ b</code>是100條記錄，顯然<code>a ⋈ b ⋈ c</code>的效率低于<code>a ⋈ c ⋈ b</code>，因為前者的中間結果是100條記錄，而後者是1條，并且最終結果的資料量是相同的。是以我們得到結論1。
另外一種影響join效率的原因是join算法。考慮hash join算法（對maxcompute熟悉的讀者可以了解為mapjoin），它提前把右邊表的資料建立一張哈希表，循環擷取左邊表的記錄查表做join。假設建立哈希表的代價很大，且随資料量線性遞增，那麼我們總希望更小的資料集在右邊。假設a表是100條記錄，b表是10條記錄，那麼<code>a ⋈ b</code>優于<code>b ⋈ a</code>。是以我們得到結論2。
綜上所述，join的順序很大程度決定了join的執行效率。這麼看來，在開發sql程式的時候，我們一定要仔細安排join的順序，讓它達到最優的執行效率？不盡然。事實上，join重排的難度如此之大，以至于手工調整是不現實的。主要的難度展現在兩部分：
擷取某個join的中間結果資料量的代價很大。我們不得不實際執行一遍join才能獲知中間結果資料量，每個join都可能花費數小時甚至數天。
是以必須借助機器自動優化。在最新的maxcompute sql 2.0中，基于代價的優化器（cost based optimizer，cbo）已經包含了join重排的優化規則。在本文中，我們嘗試從算法、代價計算、資料量估計等方方面面解釋join重排，也會包含一部分cbo的基本概念。
join樹
在sql優化器程式中表達的join大部分時候是一棵二叉樹。把join節點作為二叉樹的節點，可以建構一棵join樹。
例如，上述的<code>a ⋈ b ⋈ c</code>生成的邏輯執行計劃（algebrized tree）如下：
生成的join樹如下：
至此一切都很完美，每個查詢都是樹，直到有一種奇怪的查詢闖進了這個森林。考慮以下join：
顯然，通過<code>a.id = b.id and b.id = c.id</code>可以推出另一個join，即<code>c.id = a.id</code>，這時的join"樹"是這樣的：
這種形态稱為 有環 的join樹。有環在join重排算法裡會非常複雜，大部分的算法不支援環。當然我們可以考慮随機删除某個join操作，保證整個join樹 無環 ，但是這麼做會損失一些優化的可能性。
join樹形态
上文提到的join樹在sql的邏輯表達中通常是一個 偏樹 。考慮<code>a ⋈ b ⋈ c ⋈ d</code>，這棵偏樹的形态如下：
我們稱這種join樹為 左深（left-deep）樹 ，對應的也有 右深樹 。在單機／單任務資料庫上，我們隻考慮這種形态的join樹就可以做join重排，但是在分布式環境，我們還要考慮 稠密（bushy）樹 ，如下圖所示：
顯然，如果有更多計算節點，ab和cd可以并行執行，進而降低整體響應時間。大部分的join重排算法隻能支援左深樹，我們會在後續提到稠密樹的增強算法。maxcompute sql 2.0支援了稠密樹的重排算法。
笛卡爾積
差別于自然連接配接，笛卡爾積将兩邊的輸入做兩層循環的完全展開。部分join重排算法不支援笛卡爾積。
綜上，我們有“有／無環”，“左深／稠密樹”，“支援／不支援笛卡爾積”這三類8種問題分類。
動态規劃保留所有可能的join順序，加入到cbo的執行計劃選項（被稱為memo的一個資料結構）中，最後由代價模型選擇最優的join順序。為了避免代價被反複計算，使用動态規劃的算法記錄局部最優的代價。
輸入數 <code>n</code>
左深樹 <code>2^(n−1)</code>
稠密樹 <code>2^(n−1) * c(n − 1)</code>
1
2
3
4
8
40
5
16
224
6
32
1344
7
64
8448
128
54912
9
256
366080
10
512
2489344
在maxcompute中，我們最初利用了這個算法，因為它在理論上總能找到最優解（差別于後續我們提到的算法，理論上隻能找到次優解），并且支援稠密樹和笛卡爾積。為了降低它的複雜度，我們用了一些限制：
不區分<code>a ⋈ b</code>和<code>b ⋈ a</code>（交換）
僅處理n<=5的情況，當n>5時，分裂為多個n<=5的組分别做join重排
截止本文，maxcompute線上仍然使用以上限制的動态規劃算法。你可以通過<code>set odps.optimizer.cbo.rule.filter.white=pojr</code>打開join重排。但是，正如我們看到的，這個算法複雜度非常大，限制也非常多。我們在最新未釋出的版本使用了啟發式算法替換它。
為了降低動态規劃算法的複雜度，我們必須在join重排算法上就開始做剪枝，而不是把所有可能性都留下來。需要解釋的是，啟發式算法同樣是建立在動态規劃算法上的一種優化，而不是獨立的自成一套。
既然要“啟發”，就需要一個定義什麼是 好 的join。我們需要引入一個評估體系，被稱為cost function（如果讀者對cbo熟悉，這裡的cost不是指cbo架構的代價，而僅僅是用于評估join順序好壞的一個公式，因為此時join并沒有build，我們無法擷取準确的cost）。為了簡化問題，接下來我們使用的cost function都等于join的輸出資料量（cardinality。有關cardinality的估計算法是另一個大話題，留到下一篇文章解釋，此處請讀者先假定我們有能力擷取一個精确的cardinality）。選擇執行計劃的準則就是選擇cost最小的那個。
最重要的啟發式算法有貪婪算法和goo算法兩種。maxcompute采用了增強的goo算法。
貪婪算法
貪婪算法考慮邏輯執行計劃，以輸入為節點，每次選取cost最小的節點直到所有節點都被選取，進而組建一個左深樹作為最後的join重排順序。貪婪算法隻支援左深樹。
最基礎的貪婪算法的僞代碼如下：
實踐中，這個算法很容易受到第一個輸入選擇的影響，因為首次選擇節點，<code>cost({} ⋈ ni)</code>，還沒有任何join，這個cost被定義為ni的cardinality，小表會優先選擇，這并不一定是最好的。是以一個改進的算法是在首次選擇時，所有表都有機會，僞代碼如下：
貪婪算法的好處是，它每次選擇的一個join都是可以實際執行的（差別于下文的goo算法，選擇的可能是一個中間join），是以我們很容易計算cost。和所有的啟發式算法一樣，它隻能獲得次優解。考慮到它不支援稠密樹，我們沒有選擇這個算法。
goo算法
差別于貪婪算法以輸入為節點，goo（greedy operator ordering）考慮join樹，以join為節點。它循環選擇一個節點，和已選擇的所有節點嘗試join并選擇代價最小的那個，生成一個新的節點，直到所有的節點都被選擇了。
考慮<code>a ⋈ b ⋈ c ⋈ d</code>的例子，如果cost的估計結果是 <code>a ⋈ b</code> < <code>c ⋈ d</code> < <code>b ⋈ c</code>，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，容易了解有兩類分組：
對于sorted merge join，當參與join的每一路輸入，join key都是相同的，可以在一個task完成。
對于map join，當大表是相同的，可以在一個map裡完成。
顯然，join分組很大程度影響了代價，進而影響了最優順序。我們在join重排的實作會保留兩種optional plan：合并的方案和不合并的方案，留給cbo架構去選擇最優方案。
這篇文檔中，我們解釋了join重排這一優化的意義、概念和經典的幾種算法。
動态規劃的算法總能找到最優方案，但是複雜度是最高的。
啟發式算法的複雜度最低，隻能找到次優解。
随機算法的效果是上面兩種算法的折中。
join重排是一個較激進的優化規則，考慮到cbo無法完美估計資料量（這在我們的後續文章中解釋），打開這個規則可能會産生worst plan。這個worst plan的比例經過我們線上實測是非常低的，但是我們仍然不得不預設關閉join重排規則，你可以嘗試設定<code>odps.optimizer.cbo.rule.filter.white=pojr</code>來打開某個query或project的join重排特性。
[steinbrunn] steinbrunn, m., moerkotte, g., & kemper, a. (n.d.). optimizing join orders, 1–55.