本文主要介紹如何使用JOIN和子查詢。JOIN是將多個表以某個或某些列為條件，進行連接操作而檢索出關聯數據的過程，多個表之間以共同列而關聯在一起。子查詢是指在父查詢的WHERE子句或HAVING子句中嵌套另一個SELECT語句的查詢。

基本概念

JOIN是SQL查詢中常見的操作，邏輯上說，它的語義等價于將兩張表做笛卡爾積，然后根據過濾條件保留滿足條件的數據。多數情況下是依賴等值條件做JOIN，即Equi-Join，用來根據某個特定列的值連接兩張表的數據。

子查詢是指嵌套在SQL內部的查詢塊，子查詢的結果作為輸入，填入到外層查詢中，從而用于計算外層查詢的結果。子查詢可以出現在SQL語句的很多地方，例如在SELECT子句中作為輸出的數據，在FROM子句中作為輸入的一個視圖，在WHERE子句中作為過濾條件等。

本文討論的均為不下推，在計算層執行的JOIN算子。如果JOIN被下推到LogicalView中，其執行方式由存儲層MySQL自行選擇。

JOIN類型

PolarDB-X 1.0支持Inner Join，Left Outer Join和Right Outer Join這3種常見的JOIN類型。

JOIN類型

下面是幾種不同類型JOIN的例子：

/* Inner Join */
SELECT * FROM A, B WHERE A.key = B.key;
/* Left Outer Join */
SELECT * FROM A LEFT JOIN B ON A.key = B.key;
/* Right Outer Join */
SELECT * FROM A RIGHT OUTER JOIN B ON A.key = B.key;

此外，PolarDB-X 1.0還支持Semi-Join和Anti-Join。Semi Join和Anti Join無法直接用SQL語句來表示，通常由包含關聯項的EXISTS或IN子查詢轉換得到。

下面是幾個Semi-Join和Anti-Join的例子：

/* Semi Join - 1 */
SELECT * FROM Emp WHERE Emp.DeptName IN (
   SELECT DeptName FROM Dept
)
 /* Semi Join - 2 */
SELECT * FROM Emp WHERE EXISTS (
  SELECT * FROM Dept WHERE Emp.DeptName = Dept.DeptName
)
/* Anti Join - 1 */
SELECT * FROM Emp WHERE Emp.DeptName NOT IN (
   SELECT DeptName FROM Dept
)
 /* Anti Join - 2 */
SELECT * FROM Emp WHERE NOT EXISTS (
  SELECT * FROM Dept WHERE Emp.DeptName = Dept.DeptName
)

JOIN算法

目前，PolarDB-X 1.0支持Nested-Loop Join、Hash Join、Sort-Merge Join和Lookup Join（BKAJoin）等JOIN算法。

Nested-Loop Join (NLJoin)

Nested-Loop Join通常用于非等值的JOIN。它的工作方式如下：

  1. 拉取內表（右表，通常是數據量較小的一邊）的全部數據，緩存到內存中。
  2. 遍歷外表數據，針對外表中的每一行數據，和內表做比較，構造結果行，檢查是否滿足JOIN條件，如果滿足條件則輸出。

如下是一個Nested-Loop Join的例子：

> EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey < s_suppkey;

NlJoin(condition="ps_suppkey < s_suppkey", type="inner")
  Gather(concurrent=true)
    LogicalView(tables="partsupp_[0-7]", shardCount=8, sql="SELECT * FROM `partsupp` AS `partsupp`")
  Gather(concurrent=true)
    LogicalView(tables="supplier_[0-7]", shardCount=8, sql="SELECT * FROM `supplier` AS `supplier`")

通常來說，Nested-Loop Join是效率最低的JOIN操作，一般只有在JOIN條件不含等值（例如上面的例子）或者內表數據量極小的情況下才會使用。

通過如下Hint可以強制PolarDB-X 1.0使用Nested-Loop Join以及確定JOIN順序： 

/*+TDDL:NL_JOIN(outer_table, inner_table)*/ SELECT ...

其中inner_table和outer_table也可以是多張表的JOIN結果，例如：

/*+TDDL:NL_JOIN((outer_table_a, outer_table_b), (inner_table_c, inner_table_d))*/ SELECT ...

下面其他的Hint也一樣。

Hash Join

Hash Join是等值JOIN最常用的算法之一。它的原理如下所示：

  • 拉取內表（右表，通常是數據量較小的一邊）的全部數據，寫進內存中的哈希表。
  • 遍歷外表數據，對于外表的每行：
    • 根據等值條件JOIN Key查詢哈希表，取出0-N匹配的行（JOIN Key相同）。
    • 構造結果行，并檢查是否滿足JOIN條件，如果滿足條件則輸出。

以下是一個Hash Join的例子：

EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey = s_suppkey;

HashJoin(condition="ps_suppkey = s_suppkey", type="inner")
  Gather(concurrent=true)
    LogicalView(tables="partsupp_[0-7]", shardCount=8, sql="SELECT * FROM `partsupp` AS `partsupp`")
  Gather(concurrent=true)
    LogicalView(tables="supplier_[0-7]", shardCount=8, sql="SELECT * FROM `supplier` AS `supplier`")

Hash Join常出現在JOIN數據量較大的復雜查詢、且無法通過索引Lookup來改善，這種情況下Hash Join是最優的選擇。例如上面的例子中，partsupp表和supplier表均為全表掃描，數據量較大，適合使用HashJoin。

由于Hash Join的內表需要用于構造內存中的哈希表，內表的數據量一般小于外表。通常優化器可以自動選擇出最優的JOIN順序。如果需要手動控制，通過如下Hint可以強制PolarDB-X 1.0使用Hash Join以及確定JOIN順序： 

/*+TDDL:HASH_JOIN(table_outer, table_inner)*/ SELECT ...
Lookup Join (BKAJoin)

Lookup Join是另一種常用的等值JOIN算法，常用于數據量較小的情況。它的原理如下：

  1. 遍歷外表（左表，通常是數據量較小的一邊）數據。
  2. 對于外表中的每批（例如1000行）數據，將這一批數據的JOIN Key拼成一個IN (....)條件，加到內表的查詢中。
  3. 執行內表查詢，得到JOIN匹配的行。
  4. 借助哈希表，為外表的每行找到匹配的內表行，組合并輸出。

以下是一個Lookup Join (BKAJoin）的例子：

EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey = s_suppkey AND ps_partkey = 123;

BKAJoin(condition="ps_suppkey = s_suppkey", type="inner")
  LogicalView(tables="partsupp_3", sql="SELECT * FROM `partsupp` AS `partsupp` WHERE (`ps_partkey` = ?)")
  Gather(concurrent=true)
    LogicalView(tables="supplier_[0-7]", shardCount=8, sql="SELECT * FROM `supplier` AS `supplier` WHERE (`s_suppkey` IN ('?'))")

Lookup Join通常用于外表數據量較小的情況，例如上面的例子中，左表partsupp由于存在ps_partkey = 123的過濾條件，僅有幾行數據。此外，右表的s_suppkey IN ( ... )查詢命中了主鍵索引，這也使得Lookup Join的查詢代價進一步降低。

通過如下Hint可以強制PolarDB-X 1.0使用LookupJoin以及確定JOIN順序： 

/*+TDDL:BKA_JOIN(table_outer, table_inner)*/ SELECT ...
說明 Lookup Join的內表只能是單張表，不可以是多張表JOIN的結果。
Sort-Merge Join

Sort-Merge Join是另一種等值JOIN算法，它依賴左右兩邊輸入的順序，必須按JOIN Key排序。它的原理如下：

  1. 開始Sort-Merge Join之前，輸入端必須排序（借助MergeSort或MemSort）。
  2. 比較當前左右表輸入的行，并按以下方式操作，不斷消費左右兩邊的輸入：
    • 如果左表的JOIN Key較小，則消費左表的下一條數據。
    • 如果右表的JOIN Key較小，則消費右表的下一條數據。
    • 如果左右表JOIN Key相等，說明獲得了1條或多條匹配，檢查是否滿足JOIN條件并輸出。

以下是一個Sort-Merge Join的例子：

EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey = s_suppkey ORDER BY s_suppkey;

SortMergeJoin(condition="ps_suppkey = s_suppkey", type="inner")
  MergeSort(sort="ps_suppkey ASC")
    LogicalView(tables="QIMU_0000_GROUP,QIMU_0001_GROUP.partsupp_[0-7]", shardCount=8, sql="SELECT * FROM `partsupp` AS `partsupp` ORDER BY `ps_suppkey`")
  MergeSort(sort="s_suppkey ASC")
    LogicalView(tables="QIMU_0000_GROUP,QIMU_0001_GROUP.supplier_[0-7]", shardCount=8, sql="SELECT * FROM `supplier` AS `supplier` ORDER BY `s_suppkey`")

注意上面執行計劃中的 MergeSort算子以及下推的ORDER BY，這保證了Sort-Merge Join兩邊的輸入按JOIN Key即s_suppkey (ps_suppkey)排序。

Sort-Merge Join由于需要額外的排序步驟，通常Sort-Merge Join并不是最優的。但是，某些情況下客戶端查詢恰好也需要按JOIN Key排序（上面的例子），這時候使用Sort-Merge Join是較優的選擇。

通過如下Hint可以強制PolarDB-X 1.0使用Sort-Merge Join： 

/*+TDDL:SORT_MERGE_JOIN(table_a, table_b)*/ SELECT ...

JOIN順序

在多表連接的場景中，優化器的一個很重要的任務是決定各個表之間的連接順序，因為不同的連接順序會影響中間結果集的大小，進而影響到計劃整體的執行代價。

例如，對于4張表JOIN（暫不考慮下推的情形），JOIN Tree可以有如下3種形式，同時表的排列又有4! = 24種，一共有72種可能的JOIN順序。

JOIN順序

給定N個表的JOIN，PolarDB-X 1.0采用自適應的策略生成最佳JOIN計劃：

  • 當（未下推的）N較小時，采取Bushy枚舉策略，會在所有JOIN順序中選出最優的計劃。
  • 當（未下推的）表的數量較多時，采取Zig-Zag（鋸齒狀）或Left-Deep（左深樹）的枚舉策略，選出最優的Zig-Zag或Left-Deep執行計劃，以減少枚舉的次數和代價。

PolarDB-X 1.0使用基于代價的優化器（Cost-based Optimizer，CBO）選擇出總代價最低的JOIN 順序。詳情參見查詢優化器介紹。

此外，各個JOIN算法對左右輸入也有不同的偏好，例如，Hash Join中右表作為內表用于構建哈希表，因此應當將較小的表置于右側。這些也同樣會在CBO中被考慮到。

子查詢

根據是否存在關聯項，子查詢可以分為非關聯子查詢和關聯子查詢。非關聯子查詢是指該子查詢的執行不依賴外部查詢的變量，這種子查詢一般只需要計算一次；而關聯子查詢中存在引用自外層查詢的變量，邏輯上，這種子查詢需要每次帶入相應的變量、計算多次。

/* 例子：非關聯子查詢 */
SELECT * FROM lineitem WHERE l_partkey IN (SELECT p_partkey FROM part);

/* 例子：關聯子查詢（l_suppkey 是關聯項） */
SELECT * FROM lineitem WHERE l_partkey IN (SELECT ps_partkey FROM partsupp WHERE ps_suppkey = l_suppkey);

PolarDB-X 1.0子查詢支持絕大多數的子查詢寫法，具體參見SQL使用限制。

對于多數常見的子查詢形式，PolarDB-X 1.0可以將其改寫為高效的SemiJoin或類似的基于JOIN的計算方式。這樣做的好處是顯而易見的。當數據量較大時，無需真正帶入不同參數循環迭代，大大降低了執行代價。這種查詢改寫技術稱為子查詢的去關聯化（Unnesting）。

下面是一個子查詢去關聯化的例子，可以看到執行計劃中使用JOIN代替了子查詢。

EXPLAIN SELECT p_partkey, (
      SELECT COUNT(ps_partkey) FROM partsupp WHERE ps_suppkey = p_partkey
      ) supplier_count FROM part;
Project(p_partkey="p_partkey", supplier_count="CASE(IS NULL($10), 0, $9)", cor=[$cor0])
  HashJoin(condition="p_partkey = ps_suppkey", type="left")
    Gather(concurrent=true)
      LogicalView(tables="part_[0-7]", shardCount=8, sql="SELECT * FROM `part` AS `part`")
    Project(count(ps_partkey)="count(ps_partkey)", ps_suppkey="ps_suppkey", count(ps_partkey)2="count(ps_partkey)")
      HashAgg(group="ps_suppkey", count(ps_partkey)="SUM(count(ps_partkey))")
        Gather(concurrent=true)
          LogicalView(tables="partsupp_[0-7]", shardCount=8, sql="SELECT `ps_suppkey`, COUNT(`ps_partkey`) AS `count(ps_partkey)` FROM `partsupp` AS `partsupp` GROUP BY `ps_suppkey`")

某些少見情形下，PolarDB-X 1.0無法將子查詢進行去關聯化，這時候會采用迭代執行的方式。如果外層查詢數據量很大，迭代執行可能會非常慢。

下面這個例子中，由于OR l_partkey < 50的存在，導致子查詢無法被去關聯化，因而采用了迭代執行： 

EXPLAIN SELECT * FROM lineitem WHERE l_partkey IN (SELECT ps_partkey FROM partsupp WHERE ps_suppkey = l_suppkey) OR l_partkey IS NOT

Filter(condition="IS(in,[$1])[29612489] OR l_partkey < ?0")
  Gather(concurrent=true)
    LogicalView(tables="QIMU_0000_GROUP,QIMU_0001_GROUP.lineitem_[0-7]", shardCount=8, sql="SELECT * FROM `lineitem` AS `lineitem`")

>> individual correlate subquery : 29612489
Gather(concurrent=true)
  LogicalView(tables="QIMU_0000_GROUP,QIMU_0001_GROUP.partsupp_[0-7]", shardCount=8, sql="SELECT * FROM (SELECT `ps_partkey` FROM `partsupp` AS `partsupp` WHERE (`ps_suppkey` = `l_suppkey`)) AS `t0` WHERE (((`l_partkey` = `ps_partkey`) OR (`l_partkey` IS NULL)) OR (`ps_partkey` IS NULL))")

這種情形下，建議改寫SQL去掉子查詢的OR條件。