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語句來表示，通常由包含關(guān)聯(lián)項(xiàng)的EXISTS或IN子查詢轉(zhuǎn)換得到。如下為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. 拉取內(nèi)表（右表，通常是數(shù)據(jù)量較小的一邊）的全部數(shù)據(jù)，緩存到內(nèi)存中。

2. 遍歷外表數(shù)據(jù)，對(duì)于外表的每行：

   • 對(duì)于每一條緩存在內(nèi)存中的內(nèi)表數(shù)據(jù)。

   • 構(gòu)造結(jié)果行，并檢查是否滿足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條件不含等值（例如上面的例子）或者內(nèi)表數(shù)據(jù)量極小的情況下才會(huì)使用。通過如下Hint可以強(qiáng)制PolarDB-X使用Nested-Loop Join以及確定JOIN順序：

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

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

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

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

• 拉取內(nèi)表（右表，通常是數(shù)據(jù)量較小的一邊）的全部數(shù)據(jù)，寫進(jìn)內(nèi)存中的哈希表。

• 遍歷外表數(shù)據(jù)，對(duì)于外表的每行：

  • 根據(jù)等值條件JOIN Key查詢哈希表，取出0-N匹配的行（JOIN Key相同）。

  • 構(gòu)造結(jié)果行，并檢查是否滿足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可以強(qiáng)制PolarDB-X使用Hash Join以及確定JOIN順序：

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

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

1. 遍歷外表（左表，通常是數(shù)據(jù)量較小的一邊）數(shù)據(jù)，對(duì)于外表中的每批（例如1000行）數(shù)據(jù)。

2. 將這一批數(shù)據(jù)的JOIN Key拼成一個(gè)IN (....)條件，加到內(nèi)表的查詢中。

3. 執(zhí)行內(nèi)表查詢，得到JOIN匹配的行。

4. 借助哈希表，為外表的每行找到匹配的內(nèi)表行，組合并輸出。

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可以強(qiáng)制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. 比較當(dāng)前左右表輸入的行，并按以下方式操作，不斷消費(fèi)左右兩邊的輸入：

   • 如果左表的JOIN Key較小，則消費(fèi)左表的下一條數(shù)據(jù)。

   • 如果右表的JOIN Key較小，則消費(fèi)右表的下一條數(shù)據(jù)。

   • 如果左右表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可以強(qiáng)制PolarDB-X使用Sort-Merge Join

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

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

給定N個(gè)表的JOIN，PolarDB-X采用自適應(yīng)的策略生成最佳JOIN計(jì)劃：

• 當(dāng)（未下推的）N較小時(shí)，采取Bushy枚舉策略，會(huì)在所有JOIN順序中選出最優(yōu)的計(jì)劃。

• 當(dāng)（未下推的）表的數(shù)量較多時(shí)，采取Zig-Zag（鋸齒狀）或Left-Deep（左深樹）的枚舉策略，選出最優(yōu)的Zig-Zag或Left-Deep執(zhí)行計(jì)劃，以減少枚舉的次數(shù)和代價(jià)。

PolarDB-X支持了上述比較豐富的Join算法，優(yōu)化器會(huì)根據(jù)統(tǒng)計(jì)信息選擇相對(duì)于合理的Join算法。這里羅列下各個(gè)Join算法比較適合的場(chǎng)景。