[[398825]]

本文主要介紹什么是關(guān)聯(lián)子查詢以及如何將關(guān)聯(lián)子查詢改寫為普通語(yǔ)義的sql查詢。

在背景介紹中我們將講講常見的關(guān)聯(lián)子查詢的語(yǔ)義，關(guān)聯(lián)子查詢語(yǔ)法的好處以及其執(zhí)行時(shí)對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的挑戰(zhàn)。第二章中我們將主要介紹如何將關(guān)聯(lián)子查詢改寫為普通的查詢的形式，也就是解關(guān)聯(lián)。第三章中我們會(huì)介紹解關(guān)聯(lián)中的優(yōu)化方法。

一 背景介紹

關(guān)聯(lián)子查詢是指和外部查詢有關(guān)聯(lián)的子查詢，具體來說就是在這個(gè)子查詢里使用了外部查詢包含的列。

因?yàn)檫@種可以使用關(guān)聯(lián)列的靈活性，將sql查詢寫成子查詢的形式往往可以極大的簡(jiǎn)化sql以及使得sql查詢的語(yǔ)義更加方便理解。下面我們通過使用tpch schema來舉幾個(gè)例子以說明這一點(diǎn)。tpch schema是一個(gè)典型的訂單系統(tǒng)的database，包含customer表，orders表，lineitem表等，如下圖：

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

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

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

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

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

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

從這個(gè)簡(jiǎn)單的例子中就可以看到使用關(guān)聯(lián)子查詢降低了sql編寫的難度，同時(shí)提高了可讀性。

除了在exists/in子查詢中使用關(guān)聯(lián)列，關(guān)聯(lián)子查詢還可以出現(xiàn)在where中作為過濾條件需要的值。比如tpch q17中使用子查詢求出一個(gè)聚合值作為過濾條件。

-- 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); 

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

-- 客戶以及對(duì)應(yīng)的消費(fèi)總額

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

更復(fù)雜一些的比如，我們希望查詢每一個(gè)customer及其對(duì)應(yīng)的在某個(gè)日期前已經(jīng)簽收的訂單總額。利用關(guān)聯(lián)子查詢只需要做一些小的改變?nèi)缦拢?/p>

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 

看了這些例子，相信大家都已經(jīng)感受到使用關(guān)聯(lián)子查詢帶來的便捷。但是同時(shí)關(guān)聯(lián)子查詢也帶來了執(zhí)行上的挑戰(zhàn)。為了計(jì)算關(guān)聯(lián)結(jié)果的值（子查詢的輸出），需要iterative的執(zhí)行方式。

以之前討論過的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 

是外部查詢的列優(yōu)化器將這個(gè)查詢表示為如下圖的邏輯樹：

如果數(shù)據(jù)庫(kù)系統(tǒng)不支持查看邏輯樹，可以通過explain命令查看物理計(jì)劃，一般輸出如下圖：

+---------------+| 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] 

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

例子中對(duì)應(yīng)的邏輯計(jì)劃和相關(guān)定義如下圖所示，explain返回結(jié)果中第6-8行為外部查詢，9-13行為子查詢，關(guān)聯(lián)部位在子查詢中第12行的filter。

這個(gè)算子的輸出等價(jià)于一種iterative的執(zhí)行的結(jié)果。也就將左子樹的每一行關(guān)聯(lián)列的值帶入到右子樹中進(jìn)行計(jì)算并返回一行結(jié)果。有些類似將子查詢看成一個(gè)user defined function（udf），外部查詢的關(guān)聯(lián)列的值作為這個(gè)udf的輸入?yún)?shù)。需要注意的是，我們需要子查詢是確定的，也就是對(duì)同樣值的關(guān)聯(lián)列，每次運(yùn)行子查詢返回的結(jié)果應(yīng)該是確定的。

在上圖的栗子中，如果外部查詢有一行的p.partkey的值為25，那么這一行對(duì)應(yīng)的correlatedjoin的輸出就是下面這個(gè)查詢的結(jié)果：

-- p.partkey = 25 時(shí)對(duì)應(yīng)的子查詢?yōu)?/p>

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

需要注意的是，如果計(jì)算結(jié)果為空集，則返回一行null。而如果運(yùn)行中子查詢返回了超過一行的結(jié)果，應(yīng)該報(bào)運(yùn)行時(shí)錯(cuò)誤。在邏輯計(jì)劃里，用enforcesinglerow這個(gè)node來約束。

從上面的介紹中可以發(fā)現(xiàn)，CorrelatedJoin這個(gè)算子打破了以往對(duì)邏輯樹自上而下的執(zhí)行模式。普通的邏輯樹都是從葉子節(jié)點(diǎn)往根結(jié)點(diǎn)執(zhí)行的，但是CorreltedJoin的右子樹會(huì)被帶入左子樹的行的值反復(fù)的執(zhí)行。

correlatedjoinnode的輸出就是在外部查詢的結(jié)果上增加了一列，但是可以看到這種iterative的執(zhí)行方式的復(fù)雜度和將外部查詢和子查詢關(guān)聯(lián)產(chǎn)生之前的那部分樹進(jìn)行cross join的復(fù)雜度相同。

同時(shí)，這樣iterative的執(zhí)行方式對(duì)分布式數(shù)據(jù)庫(kù)系統(tǒng)來說是很大的挑戰(zhàn)。因?yàn)樾枰薷膱?zhí)行時(shí)調(diào)度的邏輯。而且我們可以看到，這樣的執(zhí)行方式如果不進(jìn)行結(jié)果的緩存，會(huì)進(jìn)行很多重復(fù)結(jié)果的計(jì)算。

傳統(tǒng)的優(yōu)化器的優(yōu)化規(guī)則沒有特別的針對(duì)Correlatedjoin node進(jìn)行處理，為了支持關(guān)聯(lián)子查詢的這種iterative的形式，在優(yōu)化器初始階段就會(huì)把Correlatedjoin進(jìn)行等價(jià)轉(zhuǎn)換，轉(zhuǎn)換過后的邏輯樹用join，aggregation等普通算子來進(jìn)行關(guān)聯(lián)子查詢結(jié)果的計(jì)算。這個(gè)過程被稱為解關(guān)聯(lián)（decorrelation/unnesting）。下面一章我們主要介紹常見的解關(guān)聯(lián)的方式。

二 常見的解關(guān)聯(lián)方式

為了方便起見，我們?cè)谶@一章只討論scalar關(guān)聯(lián)子查詢，就是會(huì)輸出一列值的關(guān)聯(lián)子查詢。

在討論如何解關(guān)聯(lián)之前，我們總結(jié)一下關(guān)聯(lián)子查詢的輸出有以下特點(diǎn)：

• correlated join算子的計(jì)算結(jié)果為在外部查詢上增加一列。
• 增加的那一列的結(jié)果為將外部查詢關(guān)聯(lián)列的值帶入子查詢計(jì)算得出的。當(dāng)計(jì)算結(jié)果超過一行則報(bào)錯(cuò)，計(jì)算結(jié)果為空則補(bǔ)充null。
• 不同于join算子，correlated join不改變外部查詢的其他列（不少行也不膨脹）。

解開關(guān)聯(lián)的關(guān)鍵在于使得子查詢獲得對(duì)應(yīng)的外部查詢的行的值。

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

correlated join推過的那些算子都是需要進(jìn)行改寫，以保持等價(jià)性（上圖的栗子中subquery變?yōu)榱藄ubquery’）。

1 下推規(guī)則

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

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

為了簡(jiǎn)單起見，我們?cè)谶壿嫎渲腥サ袅薳nforcesinglerow。

轉(zhuǎn)換1 無關(guān)聯(lián)時(shí)轉(zhuǎn)換為join

回顧前文所說，correlated join算子的左子樹為input，右子樹為subquery。當(dāng)correlated join的左右子樹沒有關(guān)聯(lián)的時(shí)候，這個(gè)時(shí)候?qū)ν獠坎樵兊拿恳恍?，子查詢的結(jié)果都是相同的。

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

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

轉(zhuǎn)換2 簡(jiǎn)單關(guān)聯(lián)條件時(shí)轉(zhuǎn)換為join

當(dāng)correlated join右子樹中最上面的節(jié)點(diǎn)為一個(gè)關(guān)聯(lián)filter而他的下面無關(guān)聯(lián)時(shí)，可以直接將這個(gè)filter放到left join的條件中，也可以理解為filter上提。如下圖：

轉(zhuǎn)換3 下推穿過filter

論文中correlatedjoin*可以直接推過filter。如果需要下推的為correlatedjoin，則需要對(duì)filter進(jìn)行改寫，改寫成帶有case when的project。當(dāng)subquery的行不滿足filter的條件時(shí)應(yīng)輸出null。

轉(zhuǎn)換4 下推穿過project

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

轉(zhuǎn)換5 下推穿過aggregation

correlated join下推到帶有g(shù)roup by的aggregation時(shí)，需要對(duì)aggregation進(jìn)行改寫。

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

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

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

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

論文Orthogonal Optimization of Subqueries and Aggregation[2]反復(fù)運(yùn)用上面這些規(guī)則進(jìn)行correlatedjoin的下推，直到correlatedjoin可以轉(zhuǎn)換為普通的join。

帶入之前的tpch q17的栗子中，我們先使用將correlated join推到子查詢中的project下面，查詢變?yōu)椋?/p>

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

這里我們忽略 avg()!=avg(null) 。如果考慮這個(gè)情況，則需要mark子查詢?nèi)康男?，在correlated join之后根據(jù)子查詢的結(jié)果結(jié)合mark的值對(duì)空集進(jìn)行特別處理（將mark了的行的值從null變?yōu)?）。感興趣的讀者可以參考下一張中q17的最終計(jì)劃。

接著直接調(diào)用之前的規(guī)則2，上提這個(gè)filter。這樣這個(gè)查詢就變?yōu)槠胀ǖ臎]有關(guān)聯(lián)的查詢了。

2 結(jié)果復(fù)用

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

15年Newmann的論文Unnesting Arbitrary Queries[3]介紹了一種方法就是先對(duì)外部查詢里關(guān)聯(lián)列取distinct，再將correlated join返回的值和原本的外部查詢根據(jù)關(guān)聯(lián)列進(jìn)行l(wèi)eft join，如下圖所示：

這里的not distinct join的條件對(duì)應(yīng)mysql里面的<=>，null<=>null的結(jié)果為true，是可以join到一起的。

帶入到之前的例子中如下圖所示，對(duì)外部查詢的關(guān)聯(lián)列partkey先進(jìn)行distinct，然后帶入子查詢計(jì)算結(jié)果，最后再通過join將對(duì)應(yīng)的結(jié)果接到原本的外部查詢上。

如果進(jìn)行了上述轉(zhuǎn)換，那么我們可以認(rèn)為新的input的關(guān)聯(lián)列永遠(yuǎn)是distinct的。而現(xiàn)在的correlatedjoin*算子可以允許input的列被過濾。這樣做的好處除了對(duì)于相同的列不進(jìn)行重復(fù)的子查詢的計(jì)算之外，主要還有下面兩個(gè)：

• 新的外部查詢是永遠(yuǎn)有key的，因?yàn)閐istinct過了。
• correlatedjoin*算子由于過濾外部查詢的列，所以它的下推更為簡(jiǎn)單（不需要assignuniqueid，不需要保留全部行）。

進(jìn)行上述的轉(zhuǎn)換后，緊接著再套用之前的等價(jià)下推規(guī)則，我們又可以將correlatedjoin*下推到一個(gè)左右子樹沒有關(guān)聯(lián)的地方，從而改寫為inner join。

如果按照Unnesting Arbitrary Queries[3]的方法進(jìn)行解關(guān)聯(lián)，需要將input的一部分結(jié)果進(jìn)行復(fù)用，這個(gè)復(fù)用需要執(zhí)行引擎的支持。需要注意的是，當(dāng)系統(tǒng)不支持復(fù)用的時(shí)候，我們需要執(zhí)行兩次input的子樹（如下圖），這個(gè)時(shí)候就需要input這顆子樹的結(jié)果是deterministic的，否則無法用這個(gè)方法進(jìn)行解關(guān)聯(lián)。

三 關(guān)聯(lián)子查詢的優(yōu)化

在ADB的優(yōu)化器中，邏輯計(jì)劃會(huì)根據(jù)每一條轉(zhuǎn)換規(guī)則進(jìn)行匹配和轉(zhuǎn)換，也就意味著在關(guān)聯(lián)解開之后不需要關(guān)心解關(guān)聯(lián)產(chǎn)生的計(jì)劃的效率而將它直接交給后續(xù)的優(yōu)化規(guī)則。但是現(xiàn)實(shí)并不是那么的美好，因?yàn)楹罄m(xù)規(guī)則不夠完備，以及解關(guān)聯(lián)之后丟失了外部查詢和子查詢之間的關(guān)系，我們希望在解關(guān)聯(lián)的時(shí)候就將計(jì)劃盡可能優(yōu)化。

1 exists/in/filter關(guān)聯(lián)子查詢

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

但是可以看到，如果子查詢的返回結(jié)果被用來過濾外部查詢的行，實(shí)際上會(huì)簡(jiǎn)化整個(gè)解關(guān)聯(lián)的過程。所以我們對(duì)exists/in這樣的子查詢進(jìn)行特殊處理，在語(yǔ)法解析時(shí)就進(jìn)行區(qū)分。在解關(guān)聯(lián)的過程中，如果可以使用semijoin/antijoin算子進(jìn)行解關(guān)聯(lián)則直接解開關(guān)聯(lián)，否則后續(xù)會(huì)轉(zhuǎn)化成scalar子查詢也就是correlatedjoin的形式。

2 關(guān)聯(lián)條件的上提

看到這里會(huì)發(fā)現(xiàn)，隨著correlatedjoin的下推，這個(gè)邏輯樹會(huì)變得更加復(fù)雜，所以我們?cè)谙峦浦皶?huì)在子查詢內(nèi)部進(jìn)行關(guān)聯(lián)算子的上提。當(dāng)這個(gè)邏輯就是產(chǎn)生關(guān)聯(lián)的算子越高，correlatedjoin就可以早點(diǎn)推到關(guān)聯(lián)部位的下面。比如下面這個(gè)查詢：

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 上面(因?yàn)閷?duì)于子查詢這是一個(gè)在group by列上的條件)，我們就可以進(jìn)行下面的轉(zhuǎn)換。先把關(guān)聯(lián)的filter上提（有時(shí)需要改寫），這樣就只要把correlatedjoin推過filter，調(diào)用轉(zhuǎn)換2就可以了。

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

3 代價(jià)相關(guān)的子查詢優(yōu)化

利用window算子解關(guān)聯(lián)

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

window解關(guān)聯(lián)的改寫就是在外部查詢包含子查詢中全部的表和條件時(shí)，可以直接使用window將子查詢的結(jié)果拼接到外部查詢上。他好處是節(jié)約了很多tablescan。比如說tpch q2。可以進(jìn)行下面的改寫：

這里之所能改寫成window是因?yàn)橥獠坎樵儼藘?nèi)部查詢?nèi)康谋砗蜅l件。而且agg函數(shù)min也滿足特性agg()=agg(null) （如果不滿足，需要對(duì)行進(jìn)行mark以及用case when 改寫輸出）。

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

這些好處很多文章里都說了。我們?cè)谶@里討論一下這樣改寫的不好的地方：

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

綜上所述，什么時(shí)候使用window進(jìn)行改寫關(guān)聯(lián)子查詢需要進(jìn)行收益和代價(jià)的估計(jì)。

CorrelatedJoin在外部查詢中的下推

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

這樣做是因?yàn)閏orrelatedJoin永遠(yuǎn)不會(huì)造成數(shù)據(jù)的膨脹，所以理論上應(yīng)該早點(diǎn)做。但實(shí)際上correlatejoin下推后也可能切割joingraph，從而造成和window改寫差不多的問題。

4 等價(jià)列的利用

如果在子查詢中存在和外部等價(jià)的列，那么可以先用這個(gè)列改寫子查詢中的關(guān)聯(lián)列減少關(guān)聯(lián)的地方從而簡(jiǎn)化查詢。下面舉一個(gè)簡(jiǎn)單的例子。

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進(jìn)行簡(jiǎn)化Select t1.c2From t1Where t1.c3 < ( Select min(t2.c3) From t2 Where t1.c1 = t2.c1 group by t2.c1 )

5 子查詢相關(guān)的優(yōu)化規(guī)則

一個(gè)方面correaltedjoin這個(gè)算子的特性給了我們一些進(jìn)行優(yōu)化的信息。下面舉一些例子：

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

另一個(gè)方面，在子查詢的改寫中，可以通過屬性推導(dǎo)進(jìn)行子查詢的化簡(jiǎn)。比如：

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

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

16 需要注意的地方

子查詢解關(guān)聯(lián)中最需要注意的地方就是兩個(gè)地方，一個(gè)是確保僅對(duì)外部查詢進(jìn)行加一列的操作，一個(gè)是對(duì)null值的處理。

計(jì)數(shù)錯(cuò)誤

文獻(xiàn)中常提到的是一個(gè)經(jīng)典的解關(guān)聯(lián)容易出錯(cuò)的地方。比如下面的查詢，我們有一個(gè)前提條件就是t1.c3全都是小于0的。在這個(gè)情況下子查詢參與的關(guān)聯(lián)條件應(yīng)該是沒有任何過濾度的。而改寫成inner join則會(huì)過濾掉一些行。語(yǔ)義上是不等價(jià)的。

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

分布式下的leftmarkjoin

另一個(gè)容易出錯(cuò)的地方是論文Unnesting Arbitrary Queries[3]中的LeftMarkJoin，其輸出的結(jié)果與in的語(yǔ)義相同。簡(jiǎn)單來說就是下面這個(gè)查詢的結(jié)果。

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

這個(gè)查詢對(duì)應(yīng)的邏輯計(jì)劃如下：

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

在分布式環(huán)境下，對(duì)這個(gè)算子進(jìn)行repartition和落盤很容易造成和null值相關(guān)的計(jì)算出錯(cuò)。

舉一個(gè)簡(jiǎn)單的例子，當(dāng)leftmarkjoin為repartition的執(zhí)行方式時(shí)，會(huì)對(duì)左表和右表的數(shù)據(jù)根據(jù)c1的hash值進(jìn)行重分布reshuffle。那么t1.c1中為null的行會(huì)被shuffle到同一臺(tái)executor上。這個(gè)時(shí)候假如右表沒有數(shù)據(jù)被shuffle到這臺(tái)機(jī)器上，那么這一臺(tái)executor并不知道對(duì)于null的這些行該輸出null還是false。因?yàn)閚ull in空集的結(jié)果為false，而null in 任何非空集合的結(jié)果為null。此時(shí)這臺(tái)executor并不知道右表是否為空。

解開關(guān)聯(lián)后的效率

在最開始的時(shí)候我們提到了iterative的執(zhí)行方式，這里我們需要說明對(duì)有些關(guān)聯(lián)子查詢來說即使關(guān)聯(lián)被解開為join/agg等算子，計(jì)算查詢結(jié)果也需要一個(gè)cross join的代價(jià)。

比如下面這個(gè)兩個(gè)查詢， 第一個(gè)是我們常見的關(guān)聯(lián)子查詢的樣子，可以轉(zhuǎn)換成inner join + early agg的形式。而第二個(gè)解開關(guān)聯(lián)后則會(huì)變成一個(gè)left join on非等值條件（代價(jià)同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解開關(guān)聯(lián)后的計(jì)劃如下：

sql2解開關(guān)聯(lián)后的計(jì)劃如下：

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

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

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