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

作者 | 貓來

來源 | 阿里技術公眾號

 

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

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

 

一 背景介紹

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

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

假如我們希望查詢出“所有從來沒有下過單的客戶的資訊”，那麼我們可以將關聯子查詢作為過濾條件。使用關聯子查詢寫出的sql如下。可以看到這裡的not exists子查詢使用列外部的列c_custkey。

-- 所有從來沒有下過單的客戶的資訊
select c_custkey
from
  customer
where
  not exists (
    select
      *
    from
      orders
    where
      o_custkey = c_custkey
  )

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

-- 所有從來沒有下過單的客戶的資訊
select c_custkey
from
  customer
  left join (
    select
      distinct o_custkey
    from
      orders
  ) on o_custkey = c_custkey
where
  o_custkey is null

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

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

 

-- tpch q17
SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly 
FROM   lineitem l1, 
       part p
WHERE  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 p
WHERE  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 l2
WHERE  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                    - Scalar
10                        -> 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 l2
WHERE  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了。

1. 下推規則

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

 

由於篇幅限制，下面我們只介紹下推到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等都不滿足這個特性。空集的平均值為0, 而對包含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.c2
FROM
  t1
WHERE 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就可以了。

更具體的例子就是前文提到的tpch q17。這裡的scalar子查詢作用在過濾條件中的情況也可以進行進一步改寫。

 

下圖為按照之前說的理論下推correlated join並改寫為left join之後的邏輯計劃。

而由於這個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。可以進行下面的改寫：

這裡之所能改寫成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.c2
From
  t1
Where
  t1.c3 < (
    Select min(t2.c3)
    From t2
    Where t1.c1 = t2.c1
    group by t1.c1
  )
  
-- 在子查詢中使用t2.c1 代替 t1.ct進行簡化

Select t1.c2
From
  t1
Where
  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 t1
order by
  1

6. 需要注意的地方

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

計數錯誤

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

Select t1.c2
From
  t1
Where
  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 1
SELECT t1.c1
  FROM t1
 WHERE t1.c2 > ( 
   SELECT min(t2.c2) 
     FROM t2 
    WHERE t2.c1 = t1.c1
   );

-- sql 2
SELECT 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]中的結果複用仍然可以產生優化。

http://developer.aliyun.com/article/783334?utm_content=g_1000260320

本文為阿里雲原創內容，未經允許不得轉載。