作者：王旭東
Databend 研發(fā)工程師

https://github.com/xudong963

基本介紹

在SQL查詢中，子查詢是一種常用的技術，它允許我們在一個查詢內(nèi)部嵌套另一個查詢，以實現(xiàn)更復雜的數(shù)據(jù)檢索和分析。如何在數(shù)據(jù)庫內(nèi)核中高效的處理子查詢是非常有挑戰(zhàn)的。本文將介紹如何在 Databend 中構建 state-of-art 的子查詢 optimizer。

從寬泛的角度，子查詢分為關聯(lián)和非關聯(lián)子查詢, 細分的種類包含：SCALAR/ANY/ALL/SOME/(NOT)IN/(NOT)EXISTS. 對于每一種子查詢的含義，讀者可以參考：https://www.postgresql.org/docs/current/functions-subquery.html?。盡管子查詢有這么多種，但是在 Databend 中，我們只需要處理 SCALAR/EXISTS/ANY 三種子查詢，因為在 binder 階段，可以做如下 SQL 語義等價轉(zhuǎn)換:

• "in"?=>??"=any(...)"

• "i > all()"?=> "not(i <= any(...))"

• "some"?=> "any"

子查詢幾乎可以出現(xiàn)在 SQL 的任何位置，如 "from/where/select/group by/having/order by", 外加關聯(lián)子查詢的存在，所以處理子查詢變得具有挑戰(zhàn)性，在深入子查詢之前，先介紹一下 Databend 為了高效處理子查詢而引入的非標準 join 類型：single join?和?mark join。

• single join:?single join 的存在是為了處理 scalar 子查詢，left single join 與 left outer join 類似，但是如果超過一個 join partner 被發(fā)現(xiàn)就會報錯，這點對應 scalar 子查詢只產(chǎn)生一列且最多一行結(jié)果。

• mark join:?mark join 引入了一個新的屬性：mark, 用來標記 tuple 是否有 join partner. 其值可以是 "TRUE, FALSE, NULL", 可以用來處理 ANY/EXISTS 子查詢

有了這兩種非標準 join， 我們可以保證所有的子查詢在經(jīng)過子查詢 optimizer 后已經(jīng)全部轉(zhuǎn)化為 join, 這為 join reorder 提供了更多的可能，可以大幅降低執(zhí)行代價。

非關聯(lián)子查詢

非關聯(lián)子查詢的處理相對簡單，只需要做簡單的變換即可。下面通過幾個簡單的例子來看一下如何展開非關聯(lián)子查詢:

1. 非關聯(lián) scalar 子查詢 "select number, (select number from numbers(10) as t2 where number > 3 limit 1) from numbers(10) as t1"， 直接用 single join即可?

2. 非關聯(lián) exists 子查詢 "select number, exists(select * from numbers(10) as t2 where number > 3) from numbers(10) as t1";, 給子查詢加上 "limit 1,?count(*)"?和 "count(*) = 1?operator", 其中 "limit 1"?可以使查詢更加高效，因為只需要判斷是否存在即可?

3. 非關聯(lián) any 子查詢 "select number from numbers(10) as t1 where number > any(select number from numbers(20) as t2) or number > 1;"， 在這條 SQL 中，因為包含 disjunction predicate，所以不能用 semi join 來對轉(zhuǎn)化子查詢，mark join 的 mark 列將替換子查詢 => "marker or number > 1"?

關聯(lián)子查詢

在介紹關聯(lián)子查詢前，需要引入?dependent join, dependent join 會為 LHS 中的每一行執(zhí)行一次 RHS 。

核心思想在于如何消除 dependent join 中的 correlated columns？下面通過一條 ANY 關聯(lián)子查詢來看一下是如何去關聯(lián)的 "select a from t1 where a > any(select b from t2 where t1.a < 1) or a > 1;mysql>?desc?t1;"


子查詢中包含 correlated column "t1.a", 核心的一步就是對子查詢中的表進行擴展(cross join)，t2 x t1(a)?, 擴展后的子查詢自然就完成了去關聯(lián)。?

擴展后的表假設叫 t3 包含兩列(b, a'), t3 會與 t1 進行 mark join, 返回 (t1.a, mark) 兩列，mark 列用于 filter: "mark or a > 1"?中，對 mark join 后的結(jié)果進行進一步過濾。

這里需要注意的是 mark join 的 equi condition 和 non-equi condition.至此，子查詢處理的核心思想已經(jīng)介紹完了。還有很多工程上的優(yōu)化和特殊情況就不展開講述了，比如

1. 如何正確的處理 NULL, 特別是在 mark join 的實現(xiàn)中，NULL 的正確處理對子查詢結(jié)果的正確性非常重要

2. 在對子查詢中的表進行拓展時，直接 cross join 有一定的開銷，能否避免 cross join?

3. mark join 在什么情況下可以轉(zhuǎn)化為 semi join?

4. ......

縱觀全文，所有的子查詢最終的形態(tài)都是 join, 所以 join 的性能很大程度上決定了子查詢的性能，下一篇我們講一講 Databend join 從 0 到 1 的一個迭代過程。