這種 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 ApplyA×A×：這是最基本的形式，行為剛剛我們已經描述過了；
• Left Outer ApplyALOJALOJ：即使 E(r)E(r) 為空，也生成一個 r°{NULLs}r°{NULLs}。
• Semi ApplyA?A?：如果 E(r)E(r) 不為空則返回 rr，否則丟棄；
• Anti-Semi ApplyA?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）。

規則 (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] 中為例，思路大致是：

1. 對于任意的查詢關系樹，首先將關聯子查詢從表達式中提取出來，用 Apply 算子表示；
2. 一步步去掉其中非基本關系算子，首先，通過等價變換去掉 Union 和 Subtract；
3. 進一步縮小算子集合，去掉 OuterJoin、ALOJALOJ、A?A?、A?A?；
4. 最后，去掉所有的 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 是很常見的事情。

References

1. Parameterized Queries and Nesting Equivalencies - C Galindo-Legaria
2. Orthogonal Optimization of Subqueries and Aggregation - C Galindo-Legaria, M Joshi
3. Unnesting Arbitrary Queries - T Neumann, A Kemper
4. The Complete Story of Joins (inHyPer) - T Neumann, V Leis, A Kemper