[[398825]]

本文主要介紹什么是關聯子查詢以及如何將關聯子查詢改寫為普通語義的sql查詢。

在背景介紹中我們將講講常見的關聯子查詢的語義，關聯子查詢語法的好處以及其執行時對數據庫系統的挑戰。第二章中我們將主要介紹如何將關聯子查詢改寫為普通的查詢的形式，也就是解關聯。第三章中我們會介紹解關聯中的優化方法。

一 背景介紹

關聯子查詢是指和外部查詢有關聯的子查詢，具體來說就是在這個子查詢里使用了外部查詢包含的列。

因為這種可以使用關聯列的靈活性，將sql查詢寫成子查詢的形式往往可以極大的簡化sql以及使得sql查詢的語義更加方便理解。下面我們通過使用tpch schema來舉幾個例子以說明這一點。tpch schema是一個典型的訂單系統的database，包含customer表，orders表，lineitem表等，如下圖：

假如我們希望查詢出“所有從來沒有下過單的客戶的信息”，那么我們可以將關聯子查詢作為過濾條件。使用關聯子查詢寫出的sql如下?？梢钥吹竭@里的not exists子查詢使用列外部的列c_custkey。

-- 所有從來沒有下過單的客戶的信息

select c_custkeyfrom customerwhere not exists ( select * from orders where o_custkey = c_custkey ) 

如果不寫成上面的形式，我們則需要考慮將customer和orders兩個表先進行left join，然后再過濾掉沒有join上的行，同時我們還需要markorder的每一行，使得本來就是null的那些。查詢sql如下：

-- 所有從來沒有下過單的客戶的信息

select c_custkeyfrom customer left join ( select distinct o_custkey from orders ) on o_custkey = c_custkeywhere o_custkey is null 

從這個簡單的例子中就可以看到使用關聯子查詢降低了sql編寫的難度，同時提高了可讀性。

除了在exists/in子查詢中使用關聯列，關聯子查詢還可以出現在where中作為過濾條件需要的值。比如tpch q17中使用子查詢求出一個聚合值作為過濾條件。

-- tpch q17SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly FROM lineitem l1, part pWHERE p.partkey = l1.partkey AND p.brand = 'Brand#44' AND p.container = 'WRAP PKG' AND l1.quantity < (SELECT 0.2 * Avg(l2.quantity) FROM lineitem l2 WHERE l2.partkey = p.partkey); 

除了出現在where里面，關聯子查詢可以出現在任何允許出現單行(scalar)的地方，比如select列表里。如果我們需要做報表匯總一些customer的信息，希望對每一個customer查詢他們的訂單總額，我們可以使用下面包含關聯子查詢的sql。

-- 客戶以及對應的消費總額

select c_custkey, ( select sum(o_totalprice) from orders where o_custkey = c_custkey ）from customer 

更復雜一些的比如，我們希望查詢每一個customer及其對應的在某個日期前已經簽收的訂單總額。利用關聯子查詢只需要做一些小的改變如下：

select c_custkey, ( select sum(o_totalprice) from orders where o_custkey = c_custkey and '2020-05-27' > ( select max(l_receiptdate) from lineitem where l_orderkey = o_orderkey ) ）from customer 

看了這些例子，相信大家都已經感受到使用關聯子查詢帶來的便捷。但是同時關聯子查詢也帶來了執行上的挑戰。為了計算關聯結果的值（子查詢的輸出），需要iterative的執行方式。

以之前討論過的tpch 17為例子：

SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly FROM lineitem l1, part pWHERE p.partkey = l1.partkey AND p.brand = 'Brand#44' AND p.container = 'WRAP PKG' AND l1.quantity < (SELECT 0.2 * Avg(l2.quantity) FROM lineitem l2 WHERE l2.partkey = p.partkey); 

這里的子查詢部分使用了外部查詢的列 p.partkey。

SELECT 0.2 * Avg(l2.quantity) FROM lineitem l2WHERE l2.partkey = p.partkey -- p.partkey 

是外部查詢的列優化器將這個查詢表示為如下圖的邏輯樹：

如果數據庫系統不支持查看邏輯樹，可以通過explain命令查看物理計劃，一般輸出如下圖：

+---------------+| Plan Details |+---------------+ 1- Output[avg_yearly] avg_yearly := expr 2 -> Project[] expr := (`sum` / DOUBLE '7.0') 3 - Aggregate sum := `sum`(`extendedprice`) 4 -> Filter[p.`partkey` = l1.`partkey` AND `brand` = 'Brand#51' AND `container` = 'WRAP PACK' AND `quantity` < `result`] 5 - CorrelatedJoin[[p.`partkey`]] 6 - CrossJoin 7 - TableScan[tpch:lineitem l1] 8 - TableScan[tpch:part p] 9 - Scalar10 -> Project[] result := (DOUBLE '0.2' * `avg`)11 - Aggregate avg := `avg`(`quantity`)12 -> Filter[(p.`partkey` = l2`partkey`)] 13 - TableScan[tpch:lineitem l2] 

我們將這個連接外部查詢和子查詢的算子叫做CorrelatedJoin(也被稱之為lateral join, dependent join等等。它的左子樹我們稱之為外部查詢(input)，右子樹稱之為子查詢(subquery)。子查詢中出現的外部的列叫做關聯列。在栗子中關聯列為p.partkey。

例子中對應的邏輯計劃和相關定義如下圖所示，explain返回結果中第6-8行為外部查詢，9-13行為子查詢，關聯部位在子查詢中第12行的filter。

這個算子的輸出等價于一種iterative的執行的結果。也就將左子樹的每一行關聯列的值帶入到右子樹中進行計算并返回一行結果。有些類似將子查詢看成一個user defined function（udf），外部查詢的關聯列的值作為這個udf的輸入參數。需要注意的是，我們需要子查詢是確定的，也就是對同樣值的關聯列，每次運行子查詢返回的結果應該是確定的。

在上圖的栗子中，如果外部查詢有一行的p.partkey的值為25，那么這一行對應的correlatedjoin的輸出就是下面這個查詢的結果：

-- p.partkey = 25 時對應的子查詢為

SELECT 0.2 * Avg(l2.quantity) FROM lineitem l2WHERE l2.partkey = 25 

需要注意的是，如果計算結果為空集，則返回一行null。而如果運行中子查詢返回了超過一行的結果，應該報運行時錯誤。在邏輯計劃里，用enforcesinglerow這個node來約束。

從上面的介紹中可以發現，CorrelatedJoin這個算子打破了以往對邏輯樹自上而下的執行模式。普通的邏輯樹都是從葉子節點往根結點執行的，但是CorreltedJoin的右子樹會被帶入左子樹的行的值反復的執行。

correlatedjoinnode的輸出就是在外部查詢的結果上增加了一列，但是可以看到這種iterative的執行方式的復雜度和將外部查詢和子查詢關聯產生之前的那部分樹進行cross join的復雜度相同。

同時，這樣iterative的執行方式對分布式數據庫系統來說是很大的挑戰。因為需要修改執行時調度的邏輯。而且我們可以看到，這樣的執行方式如果不進行結果的緩存，會進行很多重復結果的計算。

傳統的優化器的優化規則沒有特別的針對Correlatedjoin node進行處理，為了支持關聯子查詢的這種iterative的形式，在優化器初始階段就會把Correlatedjoin進行等價轉換，轉換過后的邏輯樹用join，aggregation等普通算子來進行關聯子查詢結果的計算。這個過程被稱為解關聯（decorrelation/unnesting）。下面一章我們主要介紹常見的解關聯的方式。

二 常見的解關聯方式

為了方便起見，我們在這一章只討論scalar關聯子查詢，就是會輸出一列值的關聯子查詢。

在討論如何解關聯之前，我們總結一下關聯子查詢的輸出有以下特點：

• correlated join算子的計算結果為在外部查詢上增加一列。
• 增加的那一列的結果為將外部查詢關聯列的值帶入子查詢計算得出的。當計算結果超過一行則報錯，計算結果為空則補充null。
• 不同于join算子，correlated join不改變外部查詢的其他列（不少行也不膨脹）。

解開關聯的關鍵在于使得子查詢獲得對應的外部查詢的行的值。

表現在計劃上，就是將correleted join算子向右下推到產生關聯的部位的下面。當correlated join算子的左右子樹沒有關聯列的時候，correlated join算子就可以轉換成join算子。這樣子查詢就通過和外部查詢join的方式獲得了關聯列的值，從而可以自上而下計算，回到原本的計算方式。如下圖，下圖中rest subquery為在關聯產生部位之前的子查詢部分。當correlated join 推到產生關聯的部位之下，就可以轉換為普通的join了。

correlated join推過的那些算子都是需要進行改寫，以保持等價性（上圖的栗子中subquery變為了subquery’）。

1 下推規則

論文Orthogonal Optimization of Subqueries and Aggregation[2]給出了將correlatedjoin算子下推到其他算子（filter，project，aggregation，union 等）下面的的等價轉換規則。但是文中的correlatedjoin算子是會過濾外部查詢的行數的，類似于inner join（論文中稱為 ）。我們這里討論更加general的類似于left join的 correlatedjoin (論文中稱為 )，并討論如果要保證外部查詢行數不被過濾需要做哪些改寫。

由于篇幅限制，下面我們只介紹下推到filter，project，aggregation算子下面的等價規則。

為了簡單起見，我們在邏輯樹中去掉了enforcesinglerow。

轉換1 無關聯時轉換為join

回顧前文所說，correlated join算子的左子樹為input，右子樹為subquery。當correlated join的左右子樹沒有關聯的時候，這個時候對外部查詢的每一行，子查詢的結果都是相同的。

我們就可以把correlated join轉換成普通的沒有join criteria的leftjoin算子。

注：需要在subquery上添加enforcesinglerow來保證join語義和correlatedjoin相同（不會造成input的膨脹）。

轉換2 簡單關聯條件時轉換為join

當correlated join右子樹中最上面的節點為一個關聯filter而他的下面無關聯時，可以直接將這個filter放到left join的條件中，也可以理解為filter上提。如下圖：

轉換3 下推穿過filter

論文中correlatedjoin*可以直接推過filter。如果需要下推的為correlatedjoin，則需要對filter進行改寫，改寫成帶有case when的project。當subquery的行不滿足filter的條件時應輸出null。

轉換4 下推穿過project

correlated join下推過project，需要在project中添加input的輸出列。

轉換5 下推穿過aggregation

correlated join下推到帶有group by的aggregation時，需要對aggregation進行改寫。

改寫為在aggregation的group by的列中增加外部查詢的全部列。這里要求外部查詢一定有key，如果沒有則需要生成臨時的key。生成可以的算子在圖中為assignuniqueid算子。

如果aggregation為全局的，那么還需要進行額外的處理。如下圖：

correlated join下推到全局aggregation的時候，需要對aggregation增加input的列(以及key)作為group by的列。這個下推規則還需要一個前提，那就是aggregation函數需要滿足滿足特性 agg()=agg(null) 。這個的意思就是aggragtion函數需要對空集和對null的計算結果是相同的。

注：在mysql和AnalyticDB for MySQL（阿里云自研的云原生數據倉庫[1]，兼容mysql語法，下文簡稱ADB）的語法里，sum, avg等都不滿足這個特性?？占钠骄禐?, 而對包含null值的任意集合取平均值結果為null不為0。所以需要mark子查詢里的每一行，對空集進行特別的處理，在這里就不展開解釋了。

論文Orthogonal Optimization of Subqueries and Aggregation[2]反復運用上面這些規則進行correlatedjoin的下推，直到correlatedjoin可以轉換為普通的join。

帶入之前的tpch q17的栗子中，我們先使用將correlated join推到子查詢中的project下面，查詢變為：

然后下推穿過這個agg，并改寫這個agg，如下圖：

這里我們忽略 avg()!=avg(null) 。如果考慮這個情況，則需要mark子查詢全部的行，在correlated join之后根據子查詢的結果結合mark的值對空集進行特別處理（將mark了的行的值從null變為0）。感興趣的讀者可以參考下一張中q17的最終計劃。

接著直接調用之前的規則2，上提這個filter。這樣這個查詢就變為普通的沒有關聯的查詢了。

2 結果復用

回顧上一節所說，子查詢的查詢結果是帶入每一行關聯列的值之后計算得出的，那么顯而易見相同值的關聯列帶入子查詢中計算出的結果是完全相同的。在上面的栗子中，對同樣的p.partkey，correlatedjoin輸出的子查詢的結果是相等的。如下圖中外部查詢partkey為25的話產生的關聯子查詢時是完全相同的，那么結果也自然相同。

15年Newmann的論文Unnesting Arbitrary Queries[3]介紹了一種方法就是先對外部查詢里關聯列取distinct，再將correlated join返回的值和原本的外部查詢根據關聯列進行left join，如下圖所示：

這里的not distinct join的條件對應mysql里面的<=>，null<=>null的結果為true，是可以join到一起的。

帶入到之前的例子中如下圖所示，對外部查詢的關聯列partkey先進行distinct，然后帶入子查詢計算結果，最后再通過join將對應的結果接到原本的外部查詢上。

如果進行了上述轉換，那么我們可以認為新的input的關聯列永遠是distinct的。而現在的correlatedjoin*算子可以允許input的列被過濾。這樣做的好處除了對于相同的列不進行重復的子查詢的計算之外，主要還有下面兩個：

• 新的外部查詢是永遠有key的，因為distinct過了。
• correlatedjoin*算子由于過濾外部查詢的列，所以它的下推更為簡單（不需要assignuniqueid，不需要保留全部行）。

進行上述的轉換后，緊接著再套用之前的等價下推規則，我們又可以將correlatedjoin*下推到一個左右子樹沒有關聯的地方，從而改寫為inner join。

如果按照Unnesting Arbitrary Queries[3]的方法進行解關聯，需要將input的一部分結果進行復用，這個復用需要執行引擎的支持。需要注意的是，當系統不支持復用的時候，我們需要執行兩次input的子樹（如下圖），這個時候就需要input這顆子樹的結果是deterministic的，否則無法用這個方法進行解關聯。

三 關聯子查詢的優化

在ADB的優化器中，邏輯計劃會根據每一條轉換規則進行匹配和轉換，也就意味著在關聯解開之后不需要關心解關聯產生的計劃的效率而將它直接交給后續的優化規則。但是現實并不是那么的美好，因為后續規則不夠完備，以及解關聯之后丟失了外部查詢和子查詢之間的關系，我們希望在解關聯的時候就將計劃盡可能優化。

1 exists/in/filter關聯子查詢

在之前的章節中為了簡化，我們只討論了scalar子查詢。因為exists/in這些子查詢都可以改寫成scalar子查詢。比如將exists改寫為count(*) > 0

但是可以看到，如果子查詢的返回結果被用來過濾外部查詢的行，實際上會簡化整個解關聯的過程。所以我們對exists/in這樣的子查詢進行特殊處理，在語法解析時就進行區分。在解關聯的過程中，如果可以使用semijoin/antijoin算子進行解關聯則直接解開關聯，否則后續會轉化成scalar子查詢也就是correlatedjoin的形式。

2 關聯條件的上提

看到這里會發現，隨著correlatedjoin的下推，這個邏輯樹會變得更加復雜，所以我們在下推之前會在子查詢內部進行關聯算子的上提。當這個邏輯就是產生關聯的算子越高，correlatedjoin就可以早點推到關聯部位的下面。比如下面這個查詢：

SELECT t1.c2FROM t1WHERE t1.c2 < ( SELECT 0.2 * max(t2.x) FROM t2 WHERE t2.c1 = t2.c1 GROUP BY t2.c1 ); 

這里由于t2.c1 = t2.c1可以推到agg 上面(因為對于子查詢這是一個在group by列上的條件)，我們就可以進行下面的轉換。先把關聯的filter上提（有時需要改寫），這樣就只要把correlatedjoin推過filter，調用轉換2就可以了。

而由于這個scalar子查詢是作為filter條件的，這種情況下子查詢沒有結果返回為null對應的外部查詢是一定會被過濾掉的。所以correlatedjoin可以直接轉為 correlatedjoin*，再加上將filter進行上提，我們可以得到下面的計劃。這樣改寫的好處是可以在join前先進行agg(early agg)。壞處就是如果不小心處理，很容易造成語義不等價造成count bug。

3 代價相關的子查詢優化

利用window算子解關聯

回顧到目前為止我們講的這些，是不是印象最深刻的在于correlatedjoin算子是在外部查詢上增加一列。而他的這個行為和window算子類似。window算子的語義就是不改變輸入的行數，只是在每一行上增加一個在window的frame里計算出的值。所以我們可以利用window算子進行解關聯，如果感興趣可以參考這兩篇論文Enhanced Subquery Optimizations in Oracle[4]和 WinMagic : Subquery Elimination Using Window Aggregation[5]。

window解關聯的改寫就是在外部查詢包含子查詢中全部的表和條件時，可以直接使用window將子查詢的結果拼接到外部查詢上。他好處是節約了很多tablescan。比如說tpch q2?？梢赃M行下面的改寫：

這里之所能改寫成window是因為外部查詢包含了內部查詢全部的表和條件。而且agg函數min也滿足特性agg()=agg(null) （如果不滿足，需要對行進行mark以及用case when 改寫輸出）。

可以看到改寫后tablescan的數量大大減少。更進一步，優化器后面的優化規則會進行根據primarykey的信息以及agg函數的特性進行join 和 window的順序交換從而進一步減少window算子輸入的數據量（filter-join pushdown）。

這些好處很多文章里都說了。我們在這里討論一下這樣改寫的不好的地方：

• 比如在pk未能顯示提供/agg的函數對duplicates敏感的情況下，window算子會阻擋filter-join的下推，從而打斷了joingraph造成join的中間結果變大。
• 如果改寫為兩棵子樹的join，filter-join可以下推到其中一顆子樹上。而進行window改寫后，filter-join無法下推。
• 在pipeline的執行模型下/&使用cte的情況下，掃表獲得的收益有限。
• 傳統優化器對join&agg的優化處理/優化規則比對window好/豐富很多。

綜上所述，什么時候使用window進行改寫關聯子查詢需要進行收益和代價的估計。

CorrelatedJoin在外部查詢中的下推

在將correlatedJoin往子查詢方向下推之前，我們會將correlatedjoin先在外部查詢中進行下推(比如推過cross join等)。

這樣做是因為correlatedJoin永遠不會造成數據的膨脹，所以理論上應該早點做。但實際上correlatejoin下推后也可能切割joingraph，從而造成和window改寫差不多的問題。

4 等價列的利用

如果在子查詢中存在和外部等價的列，那么可以先用這個列改寫子查詢中的關聯列減少關聯的地方從而簡化查詢。下面舉一個簡單的例子。

Select t1.c2From t1Where t1.c3 < ( Select min(t2.c3) From t2 Where t1.c1 = t2.c1 group by t1.c1 ) -- 在子查詢中使用t2.c1 代替 t1.ct進行簡化Select t1.c2From t1Where t1.c3 < ( Select min(t2.c3) From t2 Where t1.c1 = t2.c1 group by t2.c1 )

5 子查詢相關的優化規則

一個方面correaltedjoin這個算子的特性給了我們一些進行優化的信息。下面舉一些例子：

1. 經過correaltedjoin算子之后的行數與左子樹的行數相同。
2. enforcesinglerow的輸出為1行。
3. 外部查詢的關聯列決定(function dependency)correaltedjoin的新增的輸出列。
4. assignuniqueid產生的key具備unique的屬性等，可用于之后化簡aggregation和group by等。
5. 子查詢里的sort可以被裁剪。

另一個方面，在子查詢的改寫中，可以通過屬性推導進行子查詢的化簡。比如：

1. 如果原本外部查詢就是unique的則沒有別要增加uniqueid列。
2. enforcesinglerow的子節點的輸出如果永遠為1行則可以進行裁剪。
3. 關聯列在project上的子查詢，如下圖，在一些情況下改寫為exists子查詢。

select t1.orderkey, ( select min(t1.orderkey) from orders t2 where t2.orderkey > t1.orderkey )from orders t1order by 1

16 需要注意的地方

子查詢解關聯中最需要注意的地方就是兩個地方，一個是確保僅對外部查詢進行加一列的操作，一個是對null值的處理。

計數錯誤

文獻中常提到的是一個經典的解關聯容易出錯的地方。比如下面的查詢，我們有一個前提條件就是t1.c3全都是小于0的。在這個情況下子查詢參與的關聯條件應該是沒有任何過濾度的。而改寫成inner join則會過濾掉一些行。語義上是不等價的。

Select t1.c2From t1Where t1.c3 < ( Select COUNT (*) From t2 Where t1.c1 = t2.c1 ) 

分布式下的leftmarkjoin

另一個容易出錯的地方是論文Unnesting Arbitrary Queries[3]中的LeftMarkJoin，其輸出的結果與in的語義相同。簡單來說就是下面這個查詢的結果。

select t1.c1 in ( select t2.c1 from t2)from t1 

這個查詢對應的邏輯計劃如下：

其輸出結果為在左子樹結果上加一列in的結果，in的結果有三種可能true,false和null。

在分布式環境下，對這個算子進行repartition和落盤很容易造成和null值相關的計算出錯。

舉一個簡單的例子，當leftmarkjoin為repartition的執行方式時，會對左表和右表的數據根據c1的hash值進行重分布reshuffle。那么t1.c1中為null的行會被shuffle到同一臺executor上。這個時候假如右表沒有數據被shuffle到這臺機器上，那么這一臺executor并不知道對于null的這些行該輸出null還是false。因為null in空集的結果為false，而null in 任何非空集合的結果為null。此時這臺executor并不知道右表是否為空。

解開關聯后的效率

在最開始的時候我們提到了iterative的執行方式，這里我們需要說明對有些關聯子查詢來說即使關聯被解開為join/agg等算子，計算查詢結果也需要一個cross join的代價。

比如下面這個兩個查詢， 第一個是我們常見的關聯子查詢的樣子，可以轉換成inner join + early agg的形式。而第二個解開關聯后則會變成一個left join on非等值條件（代價同cross join）。

-- sql 1SELECT t1.c1 FROM t1 WHERE t1.c2 > ( SELECT min(t2.c2) FROM t2 WHERE t2.c1 = t1.c1 );-- sql 2SELECT t1.c1 FROM t1 WHERE t1.c2 > ( SELECT min(t2.c2) FROM t2 WHERE t2.c1 > t1.c1 ); 

sq1解開關聯后的計劃如下：

sql2解開關聯后的計劃如下：

對于sql1來說，從語義上理解，外部查詢的每一行帶入子查詢里掃過的行都是沒有重疊的，所以代價和innerjoin on等值條件是一樣的。再加上同樣的外部行對應的子查詢中min的結果相同可以應用early agg從而可以進一步優化。

對于sql2來說，從語義上理解，外部查詢的每一行都必須要帶入子查詢中掃過所有的行才能判斷在滿足t2.c1 > t1.c1這個條件下的子查詢的輸出應該是什么。為了計算出結果這個代價是無法通過優化節約的。但是對同樣的t1.c1輸出始終是相同的，Unnesting Arbitrary Queries[3]中的結果復用仍然可以產生優化。

參考文獻[1] https://www.aliyun.com/product/ApsaraDB/ads[2] Galindo-Legaria，César和Milind Joshi。“子查詢和聚合的正交優化。” ACM SIGMOD記錄30.2（2001）：571-581。[3] Neumann，Thomas和Alfons Kemper。“取消嵌套任意查詢。” 商業，技術和網絡數據庫系統（BTW 2015）（2015年）。[4]貝拉姆康達（Bellamkonda），斯里坎特（Srikanth）等。“增強了Oracle中的子查詢優化。” VLDB基金會論文集2.2（2009）：1366-1377[5] Zuzarte，Calisto等人。“ Winmagic：使用窗口聚合消除子查詢。” 2003 ACM SIGMOD國際數據管理國際會議論文集。2003。[6] Neumann，Thomas，Viktor Leis和Alfons Kemper。“聯接的完整故事（inHyPer）。” 商業，技術和網絡數據庫系統（BTW 2017）（2017）。[7]加利福尼亞州加林多-萊加里亞（Galindo-Legaria），參數化查詢和嵌套等效項。技術報告，Microsoft，2001年。MSR-TR-2000-31，2000年。