PolarDB：JOIN最佳化和執行

PolarDB-X支援Inner Join，Left Outer Join和Right Outer Join這3種常見的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;

還支援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
)

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使用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 ...

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`")

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

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

Lookup Join是另一種常用的等值JOIN演算法，常用於資料量較小的情況。它的原理如下：

1. 遍曆外表（左表，通常是資料量較小的一邊）資料，對於外表中的每批（例如1000行）資料。

2. 將這一批資料的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 ('?'))")

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

/*+TDDL:BKA_JOIN(table_outer, table_inner)*/ SELECT ...

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`")

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

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

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

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

• 當（未下推的）N較小時，採取Bushy枚舉策略，會在所有JOIN順序中選出最優的計劃。

• 當（未下推的）表的數量較多時，採取Zig-Zag（鋸齒狀）或Left-Deep（左深樹）的枚舉策略，選出最優的Zig-Zag或Left-Deep執行計畫，以減少枚舉的次數和代價。

PolarDB-X支援了上述比較豐富的Join演算法，最佳化器會根據統計資訊選擇相對於合理的Join演算法。這裡羅列下各個Join演算法比較適合的情境。