云原生数据库 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算法比较适合的场景。