子查詢 （Subquery）的優化一直以來都是 SQL 查詢優化中的難點之一，關聯子查詢的基本執行方式類似于 Nested-Loop，但是這種執行方式的效率常常低到難以忍受，當資料量稍大時，必須在優化器中對其進行去關聯化 （Decoorelation 或 Unnesting），將其改寫為類似于 Semi-Join 這樣的更高效的算子，
前人已經總結出一套完整的方法論，理論上能對任意一個查詢進行去關聯化，本文結合 SQL Server 以及 HyPer 的幾篇經典論文，由淺入深地講解一下這套去關聯化的理論體系，它們二者所用的方法大同小異，基本思想是想通的，
子查詢簡介
子查詢是定義在 SQL 標準中一種語法，它可以出現在 SQL 的幾乎任何地方，包括 SELECT, FROM, WHERE 等子句中，
總的來說，子查詢可以分為關聯子查詢（Correlated Subquery） 和非關聯子查詢（Non-correlated Subquery） ，后者非關聯子查詢是個很簡單的問題，最簡單地，只要先執行它、得到結果集并物化，再執行外層查詢即可，下面是一個例子：
SELECT c_count, count(*) AS custdist
FROM (
SELECT c_custkey, count(o_orderkey) AS c_count
FROM CUSTOMER
LEFT OUTER JOIN ORDERS ON c_custkey = o_custkey
AND o_comment NOT LIKE '%pending%deposits%'
GROUP BY c_custkey
) c_orders
GROUP BY c_count
ORDER BY custdist DESC, c_count DESC;
非關聯子查詢不在本文討論范圍之列 ，除非特別宣告，以下我們說的子查詢都是指關聯子查詢，
關聯子查詢的特別之處在于，其本身是不完整的：它的閉包中包含一些外層查詢提供的引數，顯然，只有知道這些引數才能運行該查詢，所以我們不能像對待非關聯子查詢那樣，
根據產生的資料來分類，子查詢可以分成以下幾種：
標量（Scalar-valued） 子查詢：輸出一個只有一行一列的結果表，這個標量值就是它的結果，如果結果為空（0 行），則輸出一個 NULL，但是注意，超過 1 行結果是不被允許的，會產生一個運行時例外，
標量子查詢可以出現在任意包含標量的地方，例如 SELECT、WHERE 等子句里，下面是一個例子：
SELECT c_custkey
FROM CUSTOMER
WHERE 1000000 < (
SELECT SUM(o_totalprice)
FROM ORDERS
WHERE o_custkey = c_custkey
)
Query 1: 一個出現在 WHERE 子句中的標量子查詢，關聯引數用紅色字體標明了
SELECT o_orderkey, (
SELECT c_name
FROM CUSTOMER
WHERE c_custkey = o_custkey
) AS c_name FROM ORDERS
Query 2: 一個出現在 SELECT 子句中的標量子查詢
存在性檢測（Existential Test） 子查詢：特指 EXISTS 的子查詢，回傳一個布林值，如果出現在 WHERE 中，這就是我們熟悉的 Semi-Join，當然，它可能出現在任何可以放布林值的地方，
SELECT c_custkey
FROM CUSTOMER
WHERE c_nationkey = 86 AND EXISTS(
SELECT * FROM ORDERS
WHERE o_custkey = c_custkey
)
Query 3: 一個 Semi-Join 的例子
集合比較（Quantified Comparision） 子查詢：特指 IN、SOME、ANY 的查詢，回傳一個布林值，常用的形式有：x = SOME(Q) （等價于 x IN Q）或 X <> ALL(Q)（等價于 x NOT IN Q），同上，它可能出現在任何可以放布林值的地方，
SELECT c_name
FROM CUSTOMER
WHERE c_nationkey <> ALL (SELECT s_nationkey FROM SUPPLIER)
Query 4: 一個集合比較的非關聯子查詢
原始執行計劃
我們以 Query 1 為例，直觀地感受一下，為什么說關聯子查詢的去關聯化是十分必要的，
下面是 Query 1 的未經去關聯化的原始查詢計劃（Relation Tree），與其他查詢計劃不一樣的是，我們特地畫出了運算式樹（Expression Tree），可以清晰地看到：子查詢是實際上是掛在 Filter 的條件運算式下面的，
實際執行時，查詢計劃執行器（Executor）在執行到 Filter 時，呼叫運算式執行器（Evaluator）；由于這個條件運算式中包含一個標量子查詢，所以 Evaluator 又會呼叫 Executor 計算標量子查詢的結果，
這種 Executor - Evaluator - Executor 的交替呼叫十分低效 ！考慮到 Filter 上可能會有上百萬行資料經過，如果為每行資料都執行一次子查詢，那查詢執行的總時長顯然是不可接受的，
Apply 算子
上文說到的 Relation - Expression - Relation 這種交替參考不僅執行性能堪憂，而且，對于優化器也是個麻煩的存在——我們的優化規則都是在匹配并且對 Relation 進行變換，而這里的子查詢卻藏在 Expression 里，令人無從下手，
為此，在開始去關聯化之前，我們引入 Apply 算子：
Apply 算子 （也稱作 Correlated Join）接收兩個關系樹的輸入，與一般 Join 不同的是，Apply 的 Inner 輸入（圖中是右子樹）是一個帶有引數的關系樹，
Apply 的含義用下圖右半部分的集合運算式定義：對于 Outer Relation RR 中的每一條資料 rr，計算 Inner Relation E(r)E(r)，輸出它們連接（Join）起來的結果 r?E(r)r?E(r)，Apply 的結果是所有這些結果的并集（本文中說的并集指的是 Bag 語意下的并集，也就是 UNION ALL），
Apply 是 SQL Server 的命名，它在 HyPer 的文章中叫做 Correlated Join，它們是完全等價的，考慮到 SQL Server 的文章發表更早、影響更廣，本文中都沿用它的命名，
根據連接方式（??）的不同，Apply 又有 4 種形式：
- Cross Apply A×A×：這是最基本的形式，行為剛剛我們已經描述過了；
- Left Outer Apply ALOJALOJ：即使 E(r)E(r) 為空，也生成一個 r°{NULLs}r°{NULLs}，
- Semi Apply A?A?：如果 E(r)E(r) 不為空則回傳 rr，否則丟棄；
- Anti-Semi Apply A?A?：如果 E(r)E(r) 為空則回傳 rr，否則丟棄；
我們用剛剛定義的 Apply 算子來改寫之前的例子：把子查詢從 Expression 內部提取出來，結果如下：
上面的例子中，我們可以肯定 Scalar Agg 子查詢有且只有 一行結果，所以可以直接轉成 Apply，但某些情況下，可能無法肯定子查詢一定能回傳 0 或 1 行結果（例如，想象一下 Query 2 如果 c_custkey 不是唯一的），為了確保 SQL 語意，還要在 Apply 右邊加一個 Max1RowMax1Row 算子：
Max1Row(E)=?????Null,E,error,if |E|=0if |E|=1otherwiseMax1Row(E)={Null,if |E|=0E,if |E|=1error,otherwise
理論上，我們可以將所有的子查詢轉換成 Apply 算子 ，一個通用的方法如下：
1.如果某個算子的運算式中出現了子查詢，我們就把這個子查詢提取到該算子下面（留下一個子查詢的結果變數），構成一個 ALOJALOJ 算子，如果不止一個子查詢，則會產生多個 ALOJALOJ，必要的時候加上 Max1RowMax1Row 算子，
2.然后應用其他一些規則，將 ALOJALOJ 轉換成 A×A×、A?A?、A?A?，例如上面例子中的子查詢結果 XX 被用作 Filter 的過濾條件，NULL 值會被過濾掉，因此可以安全地轉換成 A×A×，
下面這個例子中，Filter 條件運算式中包含 Q1Q1、Q2Q2 兩個子查詢，轉換之后分別生成了對應的 Apply 算子，其中 Q2Q2 無法確定只會生成恰好一條記錄，所以還加上了 Max1RowMax1Row 算子，
基本消除規則
第一組規則是最基本的規則，等式中的 ?? 說明它不限制連接型別，可以是 {×,LOJ,?,?}{×,LOJ,?,?} 中的任意一個，
這兩條規則是非常顯而易見的，翻譯成大白話就是：如果 Apply 的右邊不包含來自左邊的引數，那它就和直接 Join 是等價的，
下面是對 Query 3 應用規則 (2) 的例子：
Project 和 Filter 的去關聯化
第二組規則描述了如何處理子查詢中的 Project 和 Filter，其思想可以用一句話來描述：盡可能把 Apply 往下推、把 Apply 下面的算子向上提 ，
注意這些規則僅處理 Cross Apply 這一種情況，其他 3 種 Apply 的變體，理論上都可以轉換成 Cross Apply，暫時我們只要知道這個事實就可以了，
你可能會問：通常我們都是盡可能把 Filter、Project 往下推，為什么這里會反其道而行呢？關鍵在于：Filter、Project 里面原本包含了帶有關聯變數的運算式，但是把它提到 Apply 上方之后，關聯變數就變成普通變數了！ 這正是我們想要的，
我們稍后就會看到這樣做的巨大收益：當 Apply 被推最下面時，就可以應用第一組規則，直接把 Apply 變成 Join ，也就完成了子查詢去關聯化的優化程序，
下面是對 Query 2 應用規則 (3) 的例子，之后再應用規則 (1)，就完成了去關聯化程序，
Aggregate 的去關聯化
第三組規則描述如何處理子查詢中的 Aggregate（即 Group By），和上一組一樣，我們的指導思想仍然是：盡可能把 Apply 往下推、把 Apply 下面的算子向上提 ，
下面等式中，GA,FGA,F 表示帶有 Group By 分組的聚合（Group Agg），其中 AA 表示分組的列，FF 表示聚合函式的列；G1FGF1 表示不帶有分組的聚合（Scalar Agg），
這一組規則不像之前那么簡單直白，我們先看一個例子找找感覺，下面是對 Query 1 運用規則 (9) 的結果：
規則 (9) 在下推 Apply 的同時，還將 ScalarAgg 變成了 GroupAgg，其中，分組列就是 R 的 key，在這里也就是 CUSTOMER 的主鍵 c_custkey，
如果 R 沒有主鍵或唯一鍵，理論上，我們可以在 Scan 時生成一個，
為什么變換前后是等價的呢？變換前，我們是給每個 R 的行做了一次 ScalarAgg 聚合計算，然后再把聚合的結果合并起來；變換后，我們先是將所有要聚合的資料準備好（這被稱為 augment），然后使用 GroupAgg 一次性地做完所有聚合，
這也解釋了為什么我們要用 ALOJALOJ 而不是原本的 A×A× ：原來的 ScalarAgg 上，即使輸入是空集，也會輸出一個 NULL，如果我們這里用 ALOJALOJ，恰好也會得到一樣的行為（＊）；反之，如果用 A×A× 就有問題了——沒有對應 ORDERS 的客戶在結果中消失了！
規則 (8) 處理的是 GroupAgg，道理也是一樣的，只不過原來的分組列也要留著，
ScalarAgg 轉換中的細節＊
細心的讀者可能注意到，規則 (9) 右邊產生的聚合函式是 F′F′，多了一個單引號，這暗示它和原來的聚合函式 FF 可能是有些不同的，那什么情況下會不同呢？這個話題比較深入了，不感興趣的同學可以跳過，
首先我們思考下，GroupAgg 以及 ALOJALOJ 的行為真的和變換前一模一樣嗎？其實不然，舉個反例：
SELECT c_custkey, (
SELECT COUNT(*)
FROM ORDERS
WHERE o_custkey = c_custkey
) AS count_orders
FROM CUSTOMER
設想一下：客戶 Eric 沒有任何訂單，那么這個查詢應當回傳一個 ['Eric', 0] 的行，但是，當我們應用了規則 (9) 做變換之后，卻得到了一個 ['Eric', 1] 的值，結果出錯了！
為何會這樣呢？變換之后，我們是先用 LeftOuterJoin 準備好中間資料（augment），然后用 GroupAgg 做聚合，LeftOuterJoin 為客戶 Eric 生成了一個 ['Eric', NULL, NULL, ...] 的行；之后的 GroupAgg 中，聚合函式 COUNT(*) 認為 Eric 這個分組有 1 行資料，所以輸出了 ['Eric', 1]，
下面是個更復雜的例子，也有類似的問題：
SELECT c_custkey
FROM CUSTOMER
WHERE 200000 < (
SELECT MAX(IF_NULL(o_totalprice, 42)) -- o_totalprice may be NULL
FROM ORDERS
WHERE o_custkey = c_custkey
)
作為總結，問題的根源在于：F(?)≠F({NULL})F(?)≠F({NULL})，這樣的聚合函式 FF 都有這個問題，
變換后的 GroupAgg 無法區分它看到的 NULL 資料到底是 OuterJoin 產生的，還是原本就存在的 ，有時候，這兩種情形在變換前的 ScalarAgg 中會產生不同的結果，
幸運的是，SQL 標準中定義的聚合函式 F(col)F(col) 都是 OK 的——它們都滿足 F(?)=F({NULL})F(?)=F({NULL})，我們只要對 FF 稍加變換就能解決這個問題，
- 對于例子一，將
COUNT(*)替換成一個對非空列（例如主鍵）的 Count 即可，例如：COUNT(o_orderkey)； - 對于例子二，需要把
MIN(IF_NULL(o_totalprice, 42))分成兩步來做：定義中間變數X，先用 Project 計算X = IF_NULL(o_totalprice, 42)，再對聚合函式MIN(X)進行去關聯化即可，
集合運算的去關聯化
最后一組優化規則用來處理帶有 Union（對應 UNION ALL）、Subtract（對應 EXCEPT ALL） 和 Inner Join 算子的子查詢，再強調一遍，我們的指導思想是：盡可能把 Apply 往下推、把 Apply 下面的算子向上提 ，
下面的等式中，×× 表示 Cross Join，?R.key?R.key 表示按照 RR 的 Key 做自然連接：r°e1°e2r°e1°e2 ，和之前一樣，我們假設 RR 存在主鍵或唯一鍵，如果沒有也可以在 Scan 的時候加上一個，
注意到，這些規則與之前我們見過的規則有個顯著的不同：等式右邊 RR 出現了兩次，這樣一來，要么我們把這顆子樹拷貝一份，要么做成一個 DAG 的執行計劃，總之會麻煩許多，
事實上，這一組規則很少能派上用場，在 [2] 中提到，在 TPC-H 的 Schema 下甚至很難寫出一個帶有 Union All 的、有意義的子查詢，
其他
有幾個我認為比較重要的點，用 FAQ 的形式列在下面，
? 是否任意的關聯子查詢都可以被去關聯化？
可以說是這樣的，在加上少量限定之后，理論上可以證明：任意的關聯子查詢都可以被去關聯化，
證明方法在 [1]、[3] 中都有提及，以 [1] 中為例，思路大致是：
- 對于任意的查詢關系樹，首先將關聯子查詢從運算式中提取出來，用 Apply 算子表示；
- 一步步去掉其中非基本關系算子，首先，通過等價變換去掉 Union 和 Subtract；
- 進一步縮小算子集合，去掉 OuterJoin、ALOJALOJ、A?A?、A?A?；
- 最后，去掉所有的 A×A×，剩下的關系樹僅包含基本的一些關系算子，即完成了去關聯化，
另一方面，現實世界中用戶使用的子查詢大多是比較簡單的，本文中描述的這些規則可能已經覆寫到 99% 的場景，雖然理論上任意子查詢都可以處理，但是實際上，沒有任何一個已知的 DBMS 實作了所有這些變換規則，
? HyPer 和 SQL Server 的做法有什么異同？
HyPer 的理論覆寫了更多的去關聯化場景，例如各種 Join 等算子，[3] 中都給出了相應的等價變換規則（作為例子，下圖是對 Outer Join 的變換），而在 [1] 中僅僅是證明了這些情況都可以被規約到可處理的情形（實際上嘛，可想而知，一定是沒有處理的），
另一個細節是，HyPer 中還存在這樣一條規則：
其中，D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1)，表示對 T1T1 的 Distinct Project 結果（所謂的 Magic Set），直接看等式比較晦澀，看下面的例子就容易理解了：
圖中，在做 Apply 之前，先拿到需要 Apply 的列的 Distinct 值集合，拿這些值做 Apply，之后再用普通的 Join 把 Apply 的結果連接上去，
這樣做的好處是：如果被 Apply 的資料存在大量重復，則 Distinct Project 之后需要 Apply 的行數大大減少，這樣一來，即使之后 Apply 沒有被優化掉，迭代執行的代價也會減小不少，
? 本文說的這些變換規則，應該用在 RBO 還是 CBO 中呢？換句話說，去關聯化后之后的執行計劃一定比去關聯化之前更好嗎？
答案是，不一定，
直觀的看，如果 Apply 的左邊資料量比較少（例如，僅有 1 條資料），那直接帶入 Apply 的右邊計算反而是更好的方式，另一種情況是，右邊有合適的索引，這種情況下，多次 Apply 的代價也并非不可接受，
所以把這些規則放進一個 CBO 的優化器是更合適的，優化器根據代價估計選出最優的計劃來，甚至，在某些情況下，我們還會自右向左地運用這些等式，做“加關聯化”，
這和用 HashJoin 還是 NestedLoopJoin 是同樣的道理，事實上，NestedLoopJoin 就是 Apply 的一個特例，如果存在合適的索引，NestedLoopJoin 效率高于 HashJoin 是很常見的事情，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/283099.html
標籤：Java