子查詢（Subquery）的優(yōu)化一直以來(lái)都是 SQL 查詢優(yōu)化中的難點(diǎn)之一。關(guān)聯(lián)子查詢的基本執(zhí)行方式類似于 Nested-Loop，但是這種執(zhí)行方式的效率常常低到難以忍受。當(dāng)數(shù)據(jù)量稍大時(shí)，必須在優(yōu)化器中對(duì)其進(jìn)行去關(guān)聯(lián)化（Decoorelation 或 Unnesting），將其改寫(xiě)為類似于 Semi-Join 這樣的更高效的算子。

前人已經(jīng)總結(jié)出一套完整的方法論，理論上能對(duì)任意一個(gè)查詢進(jìn)行去關(guān)聯(lián)化。本文結(jié)合 SQL Server 以及 HyPer 的幾篇經(jīng)典論文，由淺入深地講解一下這套去關(guān)聯(lián)化的理論體系。它們二者所用的方法大同小異，基本思想是想通的。

本文的例子都基于 TPC-H 的表結(jié)構(gòu)，這里 有一份供你參考。

子查詢簡(jiǎn)介

子查詢是定義在 SQL 標(biāo)準(zhǔn)中一種語(yǔ)法，它可以出現(xiàn)在 SQL 的幾乎任何地方，包括 SELECT, FROM, WHERE 等子句中。

總的來(lái)說(shuō)，子查詢可以分為關(guān)聯(lián)子查詢（Correlated Subquery）和非關(guān)聯(lián)子查詢（Non-correlated Subquery）。后者非關(guān)聯(lián)子查詢是個(gè)很簡(jiǎn)單的問(wèn)題，最簡(jiǎn)單地，只要先執(zhí)行它、得到結(jié)果集并物化，再執(zhí)行外層查詢即可。下面是一個(gè)例子：

SELECTc_count,count(*)AScustdist
FROM(
SELECTc_custkey,count(o_orderkey)ASc_count
FROMCUSTOMER
LEFTOUTERJOINORDERSONc_custkey=o_custkey
ANDo_commentNOTLIKE'%pending%deposits%'
GROUPBYc_custkey
)c_orders
GROUPBYc_count
ORDERBYcustdistDESC,c_countDESC;

▲ TPCH-13 是一個(gè)非關(guān)聯(lián)子查詢

非關(guān)聯(lián)子查詢不在本文討論范圍之列，除非特別聲明，以下我們說(shuō)的子查詢都是指關(guān)聯(lián)子查詢。

關(guān)聯(lián)子查詢的特別之處在于，其本身是不完整的：它的閉包中包含一些外層查詢提供的參數(shù)。顯然，只有知道這些參數(shù)才能運(yùn)行該查詢，所以我們不能像對(duì)待非關(guān)聯(lián)子查詢那樣。

根據(jù)產(chǎn)生的數(shù)據(jù)來(lái)分類，子查詢可以分成以下幾種：

標(biāo)量（Scalar-valued）子查詢：輸出一個(gè)只有一行一列的結(jié)果表，這個(gè)標(biāo)量值就是它的結(jié)果。如果結(jié)果為空（0 行），則輸出一個(gè) NULL。但是注意，超過(guò) 1 行結(jié)果是不被允許的，會(huì)產(chǎn)生一個(gè)運(yùn)行時(shí)異常。

標(biāo)量子查詢可以出現(xiàn)在任意包含標(biāo)量的地方，例如 SELECT、WHERE 等子句里。下面是一個(gè)例子：

SELECTc_custkey
FROMCUSTOMER
WHERE1000000

	

	▲ Query 1: 一個(gè)出現(xiàn)在 WHERE 子句中的標(biāo)量子查詢，關(guān)聯(lián)參數(shù)用紅色字體標(biāo)明了

	
SELECTo_orderkey,(
SELECTc_name
FROMCUSTOMER
WHEREc_custkey=o_custkey
)ASc_nameFROMORDERS


	

	▲ Query 2: 一個(gè)出現(xiàn)在 SELECT 子句中的標(biāo)量子查詢

	存在性檢測(cè)（Existential Test）子查詢：特指 EXISTS 的子查詢，返回一個(gè)布爾值。如果出現(xiàn)在 WHERE 中，這就是我們熟悉的 Semi-Join。當(dāng)然，它可能出現(xiàn)在任何可以放布爾值的地方。

	
SELECTc_custkey
FROMCUSTOMER
WHEREc_nationkey=86ANDEXISTS(
SELECT*FROMORDERS
WHEREo_custkey=c_custkey
)


	

	▲ Query 3: 一個(gè) Semi-Join 的例子

	集合比較（Quantified Comparision）子查詢：特指 IN、SOME、ANY 的查詢，返回一個(gè)布爾值，常用的形式有：x = SOME(Q)（等價(jià)于x IN Q）或X <> ALL(Q)（等價(jià)于x NOT IN Q）。同上，它可能出現(xiàn)在任何可以放布爾值的地方。

	
SELECTc_name
FROMCUSTOMER
WHEREc_nationkey<>ALL(SELECTs_nationkeyFROMSUPPLIER)


	

	▲ Query 4: 一個(gè)集合比較的非關(guān)聯(lián)子查詢

	原始執(zhí)行計(jì)劃

	我們以 Query 1 為例，直觀地感受一下，為什么說(shuō)關(guān)聯(lián)子查詢的去關(guān)聯(lián)化是十分必要的。

	下面是 Query 1 的未經(jīng)去關(guān)聯(lián)化的原始查詢計(jì)劃（Relation Tree）。與其他查詢計(jì)劃不一樣的是，我們特地畫(huà)出了表達(dá)式樹(shù)（Expression Tree），可以清晰地看到：子查詢是實(shí)際上是掛在 Filter 的條件表達(dá)式下面的。

	

	img實(shí)際執(zhí)行時(shí)，查詢計(jì)劃執(zhí)行器（Executor）在執(zhí)行到 Filter 時(shí)，調(diào)用表達(dá)式執(zhí)行器（Evaluator）；由于這個(gè)條件表達(dá)式中包含一個(gè)標(biāo)量子查詢，所以 Evaluator 又會(huì)調(diào)用 Executor 計(jì)算標(biāo)量子查詢的結(jié)果。

	這種 Executor - Evaluator - Executor 的交替調(diào)用十分低效！考慮到 Filter 上可能會(huì)有上百萬(wàn)行數(shù)據(jù)經(jīng)過(guò)，如果為每行數(shù)據(jù)都執(zhí)行一次子查詢，那查詢執(zhí)行的總時(shí)長(zhǎng)顯然是不可接受的。

	Apply 算子

	上文說(shuō)到的 Relation - Expression - Relation 這種交替引用不僅執(zhí)行性能堪憂，而且，對(duì)于優(yōu)化器也是個(gè)麻煩的存在——我們的優(yōu)化規(guī)則都是在匹配并且對(duì) Relation 進(jìn)行變換，而這里的子查詢卻藏在 Expression 里，令人無(wú)從下手。

	為此，在開(kāi)始去關(guān)聯(lián)化之前，我們引入 Apply 算子：

	Apply 算子（也稱作 Correlated Join）接收兩個(gè)關(guān)系樹(shù)的輸入，與一般 Join 不同的是，Apply 的 Inner 輸入（圖中是右子樹(shù)）是一個(gè)帶有參數(shù)的關(guān)系樹(shù)。

	Apply 的含義用下圖右半部分的集合表達(dá)式定義：對(duì)于 Outer Relation RR 中的每一條數(shù)據(jù) rr，計(jì)算 Inner Relation E(r)E(r)，輸出它們連接（Join）起來(lái)的結(jié)果 r?E(r)r?E(r)。Apply 的結(jié)果是所有這些結(jié)果的并集（本文中說(shuō)的并集指的是 Bag 語(yǔ)義下的并集，也就是 UNION ALL）。

	

	“

	Apply 是 SQL Server 的命名，它在 HyPer 的文章中叫做 Correlated Join。它們是完全等價(jià)的。考慮到 SQL Server 的文章發(fā)表更早、影響更廣，本文中都沿用它的命名。

	根據(jù)連接方式（??）的不同，Apply 又有 4 種形式：

	Cross ApplyA×A×：這是最基本的形式，行為剛剛我們已經(jīng)描述過(guò)了；

	Left Outer ApplyALOJALOJ：即使 E(r)E(r) 為空，也生成一個(gè) r°{NULLs}r°{NULLs}。

	Semi ApplyA?A?：如果 E(r)E(r) 不為空則返回 rr，否則丟棄；

	Anti-Semi ApplyA?A?：如果 E(r)E(r) 為空則返回 rr，否則丟棄；

	我們用剛剛定義的 Apply 算子來(lái)改寫(xiě)之前的例子：把子查詢從 Expression 內(nèi)部提取出來(lái)。結(jié)果如下：

	

	上面的例子中，我們可以肯定 Scalar Agg 子查詢有且只有一行結(jié)果，所以可以直接轉(zhuǎn)成 Apply。但某些情況下，可能無(wú)法肯定子查詢一定能返回 0 或 1 行結(jié)果（例如，想象一下 Query 2 如果 c_custkey 不是唯一的），為了確保 SQL 語(yǔ)義，還要在 Apply 右邊加一個(gè) Max1RowMax1Row 算子：

	Max1Row(E)=?????Null,E,error,if |E|=0if |E|=1otherwiseMax1Row(E)={Null,if |E|=0E,if |E|=1error,otherwise

	理論上，我們可以將所有的子查詢轉(zhuǎn)換成 Apply 算子，一個(gè)通用的方法如下：

	如果某個(gè)算子的表達(dá)式中出現(xiàn)了子查詢，我們就把這個(gè)子查詢提取到該算子下面（留下一個(gè)子查詢的結(jié)果變量），構(gòu)成一個(gè) ALOJALOJ 算子。如果不止一個(gè)子查詢，則會(huì)產(chǎn)生多個(gè) ALOJALOJ。必要的時(shí)候加上 Max1RowMax1Row 算子。

	然后應(yīng)用其他一些規(guī)則，將 ALOJALOJ 轉(zhuǎn)換成 A×A×、A?A?、A?A?。例如上面例子中的子查詢結(jié)果 XX 被用作 Filter 的過(guò)濾條件，NULL 值會(huì)被過(guò)濾掉，因此可以安全地轉(zhuǎn)換成 A×A×。

	下面這個(gè)例子中，F(xiàn)ilter 條件表達(dá)式中包含 Q1Q1、Q2Q2 兩個(gè)子查詢。轉(zhuǎn)換之后分別生成了對(duì)應(yīng)的 Apply 算子。其中 Q2Q2 無(wú)法確定只會(huì)生成恰好一條記錄，所以還加上了 Max1RowMax1Row 算子。

	

	基本消除規(guī)則

	第一組規(guī)則是最基本的規(guī)則，等式中的 ?? 說(shuō)明它不限制連接類型，可以是 {×,LOJ,?,?}{×,LOJ,?,?} 中的任意一個(gè)。

	

	這兩條規(guī)則是非常顯而易見(jiàn)的，翻譯成大白話就是：如果 Apply 的右邊不包含來(lái)自左邊的參數(shù)，那它就和直接 Join 是等價(jià)的。

	下面是對(duì) Query 3 應(yīng)用規(guī)則 (2) 的例子：

	

	Project 和 Filter 的去關(guān)聯(lián)化

	第二組規(guī)則描述了如何處理子查詢中的 Project 和 Filter，其思想可以用一句話來(lái)描述：盡可能把 Apply 往下推、把 Apply 下面的算子向上提。

	

	

	注意這些規(guī)則僅處理 Cross Apply 這一種情況。其他 3 種 Apply 的變體，理論上都可以轉(zhuǎn)換成 Cross Apply，暫時(shí)我們只要知道這個(gè)事實(shí)就可以了。

	你可能會(huì)問(wèn)：通常我們都是盡可能把 Filter、Project 往下推，為什么這里會(huì)反其道而行呢？關(guān)鍵在于：Filter、Project 里面原本包含了帶有關(guān)聯(lián)變量的表達(dá)式，但是把它提到 Apply 上方之后，關(guān)聯(lián)變量就變成普通變量了！這正是我們想要的。

	我們稍后就會(huì)看到這樣做的巨大收益：當(dāng) Apply 被推最下面時(shí)，就可以應(yīng)用第一組規(guī)則，直接把 Apply 變成 Join，也就完成了子查詢?nèi)リP(guān)聯(lián)化的優(yōu)化過(guò)程。

	下面是對(duì) Query 2 應(yīng)用規(guī)則 (3) 的例子。之后再應(yīng)用規(guī)則 (1)，就完成了去關(guān)聯(lián)化過(guò)程。

	

	Aggregate 的去關(guān)聯(lián)化

	第三組規(guī)則描述如何處理子查詢中的 Aggregate（即 Group By）。和上一組一樣，我們的指導(dǎo)思想仍然是：盡可能把 Apply 往下推、把 Apply 下面的算子向上提。

	下面等式中，GA,FGA,F 表示帶有 Group By 分組的聚合（Group Agg），其中 AA 表示分組的列，F(xiàn)F 表示聚合函數(shù)的列；G1FGF1 表示不帶有分組的聚合（Scalar Agg）。

	

	img這一組規(guī)則不像之前那么簡(jiǎn)單直白，我們先看一個(gè)例子找找感覺(jué)。下面是對(duì) Query 1 運(yùn)用規(guī)則 (9) 的結(jié)果：

	

	規(guī)則 (9) 在下推 Apply 的同時(shí)，還將 ScalarAgg 變成了 GroupAgg，其中，分組列就是 R 的 key，在這里也就是 CUSTOMER 的主鍵 c_custkey。

	“

	如果 R 沒(méi)有主鍵或唯一鍵，理論上，我們可以在 Scan 時(shí)生成一個(gè)。

	為什么變換前后是等價(jià)的呢？變換前，我們是給每個(gè) R 的行做了一次 ScalarAgg 聚合計(jì)算，然后再把聚合的結(jié)果合并起來(lái)；變換后，我們先是將所有要聚合的數(shù)據(jù)準(zhǔn)備好（這被稱為 augment），然后使用 GroupAgg 一次性地做完所有聚合。

	這也解釋了為什么我們要用 ALOJALOJ 而不是原本的 A×A× ：原來(lái)的 ScalarAgg 上，即使輸入是空集，也會(huì)輸出一個(gè) NULL。如果我們這里用 ALOJALOJ，恰好也會(huì)得到一樣的行為（＊）；反之，如果用 A×A× 就有問(wèn)題了——沒(méi)有對(duì)應(yīng) ORDERS 的客戶在結(jié)果中消失了！

	規(guī)則 (8) 處理的是 GroupAgg，道理也是一樣的，只不過(guò)原來(lái)的分組列也要留著。

	ScalarAgg 轉(zhuǎn)換中的細(xì)節(jié)＊

	細(xì)心的讀者可能注意到，規(guī)則 (9) 右邊產(chǎn)生的聚合函數(shù)是 F′F′，多了一個(gè)單引號(hào)，這暗示它和原來(lái)的聚合函數(shù) FF 可能是有些不同的。那什么情況下會(huì)不同呢？這個(gè)話題比較深入了，不感興趣的同學(xué)可以跳過(guò)。

	首先我們思考下，GroupAgg 以及 ALOJALOJ 的行為真的和變換前一模一樣嗎？其實(shí)不然。舉個(gè)反例：

	
SELECT c_custkey, (
    SELECT COUNT(*)
    FROM ORDERS
    WHERE o_custkey = c_custkey
) AS count_orders
FROM CUSTOMER


	

	設(shè)想一下：客戶 Eric 沒(méi)有任何訂單，那么這個(gè)查詢應(yīng)當(dāng)返回一個(gè)['Eric', 0]的行。但是，當(dāng)我們應(yīng)用了規(guī)則 (9) 做變換之后，卻得到了一個(gè)['Eric', 1]的值，結(jié)果出錯(cuò)了！

	為何會(huì)這樣呢？變換之后，我們是先用 LeftOuterJoin 準(zhǔn)備好中間數(shù)據(jù)（augment），然后用 GroupAgg 做聚合。LeftOuterJoin 為客戶 Eric 生成了一個(gè)['Eric', NULL, NULL, ...]的行；之后的 GroupAgg 中，聚合函數(shù)COUNT(*)認(rèn)為 Eric 這個(gè)分組有 1 行數(shù)據(jù)，所以輸出了['Eric', 1]。

	下面是個(gè)更復(fù)雜的例子，也有類似的問(wèn)題：

	
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
)


	

	作為總結(jié)，問(wèn)題的根源在于：F(?)≠F({NULL})F(?)≠F({NULL})，這樣的聚合函數(shù) FF 都有這個(gè)問(wèn)題。

	變換后的 GroupAgg 無(wú)法區(qū)分它看到的 NULL 數(shù)據(jù)到底是 OuterJoin 產(chǎn)生的，還是原本就存在的，有時(shí)候，這兩種情形在變換前的 ScalarAgg 中會(huì)產(chǎn)生不同的結(jié)果。

	幸運(yùn)的是，SQL 標(biāo)準(zhǔn)中定義的聚合函數(shù) F(col)F(col) 都是 OK 的——它們都滿足 F(?)=F({NULL})F(?)=F({NULL})，我們只要對(duì) FF 稍加變換就能解決這個(gè)問(wèn)題。

	對(duì)于例子一，將COUNT(*)替換成一個(gè)對(duì)非空列（例如主鍵）的 Count 即可，例如：COUNT(o_orderkey)；

	對(duì)于例子二，需要把MIN(IF_NULL(o_totalprice, 42))分成兩步來(lái)做：定義中間變量X，先用 Project 計(jì)算X = IF_NULL(o_totalprice, 42)，再對(duì)聚合函數(shù)MIN(X)進(jìn)行去關(guān)聯(lián)化即可。

	集合運(yùn)算的去關(guān)聯(lián)化

	最后一組優(yōu)化規(guī)則用來(lái)處理帶有 Union（對(duì)應(yīng)UNION ALL）、Subtract（對(duì)應(yīng)EXCEPT ALL） 和 Inner Join 算子的子查詢。再?gòu)?qiáng)調(diào)一遍，我們的指導(dǎo)思想是：盡可能把 Apply 往下推、把 Apply 下面的算子向上提。

	下面的等式中，×× 表示 Cross Join，?R.key?R.key 表示按照 RR 的 Key 做自然連接：r°e1°e2r°e1°e2 。和之前一樣，我們假設(shè) RR 存在主鍵或唯一鍵，如果沒(méi)有也可以在 Scan 的時(shí)候加上一個(gè)。

	

	

	注意到，這些規(guī)則與之前我們見(jiàn)過(guò)的規(guī)則有個(gè)顯著的不同：等式右邊 RR 出現(xiàn)了兩次。這樣一來(lái)，要么我們把這顆子樹(shù)拷貝一份，要么做成一個(gè) DAG 的執(zhí)行計(jì)劃，總之會(huì)麻煩許多。

	事實(shí)上，這一組規(guī)則很少能派上用場(chǎng)。在 [2] 中提到，在 TPC-H 的 Schema 下甚至很難寫(xiě)出一個(gè)帶有 Union All 的、有意義的子查詢。

	其他

	有幾個(gè)我認(rèn)為比較重要的點(diǎn)，用 FAQ 的形式列在下面。

	? 是否任意的關(guān)聯(lián)子查詢都可以被去關(guān)聯(lián)化？

	可以說(shuō)是這樣的，在加上少量限定之后，理論上可以證明：任意的關(guān)聯(lián)子查詢都可以被去關(guān)聯(lián)化。

	證明方法在 [1]、[3] 中都有提及。以 [1] 中為例，思路大致是：

	對(duì)于任意的查詢關(guān)系樹(shù)，首先將關(guān)聯(lián)子查詢從表達(dá)式中提取出來(lái)，用 Apply 算子表示；

	一步步去掉其中非基本關(guān)系算子，首先，通過(guò)等價(jià)變換去掉 Union 和 Subtract；

	進(jìn)一步縮小算子集合，去掉 OuterJoin、ALOJALOJ、A?A?、A?A?；

	最后，去掉所有的 A×A×，剩下的關(guān)系樹(shù)僅包含基本的一些關(guān)系算子，即完成了去關(guān)聯(lián)化。

	另一方面，現(xiàn)實(shí)世界中用戶使用的子查詢大多是比較簡(jiǎn)單的，本文中描述的這些規(guī)則可能已經(jīng)覆蓋到 99% 的場(chǎng)景。雖然理論上任意子查詢都可以處理，但是實(shí)際上，沒(méi)有任何一個(gè)已知的 DBMS 實(shí)現(xiàn)了所有這些變換規(guī)則。

	? HyPer 和 SQL Server 的做法有什么異同？

	HyPer 的理論覆蓋了更多的去關(guān)聯(lián)化場(chǎng)景。例如各種 Join 等算子，[3] 中都給出了相應(yīng)的等價(jià)變換規(guī)則（作為例子，下圖是對(duì) Outer Join 的變換）。而在 [1] 中僅僅是證明了這些情況都可以被規(guī)約到可處理的情形（實(shí)際上嘛，可想而知，一定是沒(méi)有處理的）。

	

	另一個(gè)細(xì)節(jié)是，HyPer 中還存在這樣一條規(guī)則：

	

	其中，D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1)，表示對(duì) T1T1 的 Distinct Project 結(jié)果（所謂的Magic Set）。直接看等式比較晦澀，看下面的例子就容易理解了：

	

	圖中，在做 Apply 之前，先拿到需要 Apply 的列的 Distinct 值集合，拿這些值做 Apply，之后再用普通的 Join 把 Apply 的結(jié)果連接上去。

	這樣做的好處是：如果被 Apply 的數(shù)據(jù)存在大量重復(fù)，則 Distinct Project 之后需要 Apply 的行數(shù)大大減少。這樣一來(lái)，即使之后 Apply 沒(méi)有被優(yōu)化掉，迭代執(zhí)行的代價(jià)也會(huì)減小不少。

	? 本文說(shuō)的這些變換規(guī)則，應(yīng)該用在 RBO 還是 CBO 中呢？換句話說(shuō)，去關(guān)聯(lián)化后之后的執(zhí)行計(jì)劃一定比去關(guān)聯(lián)化之前更好嗎？

	答案是，不一定。

	直觀的看，如果 Apply 的左邊數(shù)據(jù)量比較少（例如，僅有 1 條數(shù)據(jù)），那直接帶入 Apply 的右邊計(jì)算反而是更好的方式。另一種情況是，右邊有合適的索引，這種情況下，多次 Apply 的代價(jià)也并非不可接受。

	所以把這些規(guī)則放進(jìn)一個(gè) CBO 的優(yōu)化器是更合適的，優(yōu)化器根據(jù)代價(jià)估計(jì)選出最優(yōu)的計(jì)劃來(lái)。甚至，在某些情況下，我們還會(huì)自右向左地運(yùn)用這些等式，做“加關(guān)聯(lián)化”。

	這和用 HashJoin 還是 NestedLoopJoin 是同樣的道理。事實(shí)上，NestedLoopJoin 就是 Apply 的一個(gè)特例。如果存在合適的索引，NestedLoopJoin 效率高于 HashJoin 是很常見(jiàn)的事情。

	





	審核編輯：劉清