全部产品
Search
文档中心

JOIN与子查询的优化和执行

更新时间: 2020-08-17

基本概念

JOIN是SQL查询中常见的操作,逻辑上说,它的语义等价于将两张表做笛卡尔积,然后根据用户提供的过滤条件过过滤,留下满足条件的数据行。JOIN多数情况下是依赖等值条件做的JOIN,即Equi-Join,用来根据某个特定列的值连接两张表的数据。

子查询是指嵌套在SQL内部的查询块,子查询的结果作为输入,填入到外层查询中,从而用于计算外层查询的结果。子查询可以出现在SQL语句的很多地方,比如在SELECT子句中作为输出的数据,在FROM子句中作为输入的一个视图,在WHERE子句中作为过滤条件等。

本章节讨论的均为不下推的JOIN算子。如果JOIN被下推到LogicalView中,其执行方式由MySQL自行选择。

JOIN类型

PolarDB-X支持Inner Join,Left Outer Join和Right Outer Join这3种常见的JOIN类型。
x

下面是几种不同类型JOIN的例子:

  1. /* Inner Join */
  2. SELECT * FROM A, B WHERE A.key = B.key;
  3. /* Left Outer Join */
  4. SELECT * FROM A LEFT JOIN B ON A.key = B.key;
  5. /* Right Outer Join */
  6. SELECT * FROM A RIGHT OUTER JOIN B ON A.key = B.key;

此外,PolarDB-X还支持Semi-Join和Anti-Join。Semi Join和Anti Join无法直接用SQL语句来表示,通常由包含关联项的EXISTS或IN子查询转换得到。

下面是几个Semi-Join和Anti-Join的例子:

  1. /* Semi Join - 1 */
  2. SELECT * FROM Emp WHERE Emp.DeptName IN (
  3. SELECT DeptName FROM Dept
  4. )
  5. /* Semi Join - 2 */
  6. SELECT * FROM Emp WHERE EXISTS (
  7. SELECT * FROM Dept WHERE Emp.DeptName = Dept.DeptName
  8. )
  9. /* Anti Join - 1 */
  10. SELECT * FROM Emp WHERE Emp.DeptName NOT IN (
  11. SELECT DeptName FROM Dept
  12. )
  13. /* Anti Join - 2 */
  14. SELECT * FROM Emp WHERE NOT EXISTS (
  15. SELECT * FROM Dept WHERE Emp.DeptName = Dept.DeptName
  16. )

JOIN算法

目前,PolarDB-X支持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的例子:

  1. > EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey < s_suppkey;
  2. NlJoin(condition="ps_suppkey < s_suppkey", type="inner")
  3. Gather(concurrent=true)
  4. LogicalView(tables="partsupp_[0-7]", shardCount=8, sql="SELECT * FROM `partsupp` AS `partsupp`")
  5. Gather(concurrent=true)
  6. 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顺序:

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

其中inner_table 和outer_table也可以是多张表的JOIN结果,例如:

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

下面其他的Hint也一样。

Hash Join

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

  1. 拉取内表(右表,通常是数据量较小的一边)的全部数据,写进内存中的哈希表。
  2. 遍历外表数据,对于外表的每行:
    • 根据等值条件JOIN Key查询哈希表,取出0-N匹配的行(JOIN Key相同)。
    • 构造结果行,并检查是否满足JOIN条件,如果满足条件则输出。

以下是一个Hash Join的例子:

  1. > EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey = s_suppkey;
  2. HashJoin(condition="ps_suppkey = s_suppkey", type="inner")
  3. Gather(concurrent=true)
  4. LogicalView(tables="partsupp_[0-7]", shardCount=8, sql="SELECT * FROM `partsupp` AS `partsupp`")
  5. Gather(concurrent=true)
  6. 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的两种表中较小的那一个。通常优化器可以自动选择出最优的JOIN顺序。如果需要手动控制,也可以通过下面的Hint。

通过如下Hint可以强制PolarDB-X使用Hash Join以及确定JOIN顺序:

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

Lookup Join (BKAJoin)

Lookup Join是另一种常用的等值JOIN算法,常用于数据量较小的情况。它的原理如下:

  1. 遍历外表(左表,通常是数据量较小的一边)数据,对于外表中的每批(例如1000行)数据。
    1. 将这一批数据的JOIN Key拼成一个IN (....)条件,加到内表的查询中。
    2. 执行内表查询,得到JOIN匹配的行。
    3. 借助哈希表,为外表的每行找到匹配的内表行,组合并输出。

以下是一个Lookup Join (BKAJoin)的例子:

  1. > EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey = s_suppkey AND ps_partkey = 123;
  2. BKAJoin(condition="ps_suppkey = s_suppkey", type="inner")
  3. LogicalView(tables="partsupp_3", sql="SELECT * FROM `partsupp` AS `partsupp` WHERE (`ps_partkey` = ?)")
  4. Gather(concurrent=true)
  5. 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使用LookupJoin以及确定JOIN顺序:

  1. /*+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的例子:

  1. > EXPLAIN SELECT * FROM partsupp, supplier WHERE ps_suppkey = s_suppkey ORDER BY s_suppkey;
  2. SortMergeJoin(condition="ps_suppkey = s_suppkey", type="inner")
  3. MergeSort(sort="ps_suppkey ASC")
  4. LogicalView(tables="QIMU_0000_GROUP,QIMU_0001_GROUP.partsupp_[0-7]", shardCount=8, sql="SELECT * FROM `partsupp` AS `partsupp` ORDER BY `ps_suppkey`")
  5. MergeSort(sort="s_suppkey ASC")
  6. 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使用Sort-Merge Join:

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

JOIN顺序

在多表连接的场景中,优化器的一个很重要的任务是决定各个表之间的连接顺序,因为不同的连接顺序会影响中间结果集的大小,进而影响到计划整体的执行代价。

例如,对于4张表JOIN(暂不考虑下推的情形),Join Tree可以有如下3种形式,同时表的排列又有4! = 24种,一共有72种可能的JOIN顺序。

x

给定N个表的JOIN,PolarDB-X采用自适应的策略生成最佳JOIN计划:

  • 当(未下推的)N较小时,采取Bushy枚举策略,会在所有JOIN顺序中选出最优的计划。
  • 当(未下推的)表的数量较多时,采取Zig-Zag(锯齿状) 或Left-Deep(左深树)的枚举策略,选出最优的Zig-Zag或Left-Deep执行计划,以减少枚举的次数和代价。

PolarDB-X使用基于代价的优化器(Cost-based Optimizer,CBO)选择出总代价最低的JOIN 顺序。详情请参见查询优化器介绍

此外,各个JOIN算法对左右输入也有不同的偏好,例如,Hash Join中右表作为内表用于构建哈希表,因此应当将较小的表置于右侧。这些也同样会在CBO中被考虑到。

子查询

根据是否存在关联项,子查询可以分为非关联子查询和关联子查询。非关联子查询是指该子查询的执行不依赖外部查询的变量,这种子查询一般只需要计算一次;而关联子查询中存在引用自外层查询的变量,逻辑上,这种子查询需要每次带入相应的变量、计算多次。

  1. /* 例子:非关联子查询 */
  2. SELECT * FROM lineitem WHERE l_partkey IN (SELECT p_partkey FROM part);
  3. /* 例子:关联子查询(l_suppkey 是关联项) */
  4. SELECT * FROM lineitem WHERE l_partkey IN (SELECT ps_partkey FROM partsupp WHERE ps_suppkey = l_suppkey);

PolarDB-X子查询支持绝大多数的子查询写法,具体参见SQL手册

对于多数常见的子查询形式,PolarDB-X可以将其改写为高效的SemiJoin或类似的基于JOIN的计算方式。这样做的好处是显而易见的。当数据量较大时,无需真正带入不同参数循环迭代,大大降低了执行代价。这种查询改写技术称为子查询的去关联化(Unnesting)。

下面是2个子查询去关联化的例子,可以看到执行计划中使用JOIN代替了子查询。

  1. > EXPLAIN SELECT * FROM lineitem WHERE l_partkey IN (SELECT ps_partkey FROM partsupp WHERE ps_suppkey = l_suppkey);
  2. SemiHashJoin(condition="l_partkey = ps_partkey AND l_suppkey = ps_suppkey", type="semi")
  3. Gather(concurrent=true)
  4. LogicalView(tables="lineitem_[0-7]", shardCount=8, sql="SELECT * FROM `lineitem` AS `lineitem`")
  5. Gather(concurrent=true)
  6. LogicalView(tables="partsupp_[0-7]", shardCount=8, sql="SELECT `ps_partkey`, `ps_suppkey` FROM `partsupp` AS `partsupp`")
  1. > EXPLAIN SELECT p_partkey, (
  2. SELECT COUNT(ps_partkey) FROM partsupp WHERE ps_suppkey = p_partkey
  3. ) supplier_count FROM part;
  4. Project(p_partkey="p_partkey", supplier_count="CASE(IS NULL($10), 0, $9)", cor=[$cor0])
  5. HashJoin(condition="p_partkey = ps_suppkey", type="left")
  6. Gather(concurrent=true)
  7. LogicalView(tables="part_[0-7]", shardCount=8, sql="SELECT * FROM `part` AS `part`")
  8. Project(count(ps_partkey)="count(ps_partkey)", ps_suppkey="ps_suppkey", count(ps_partkey)2="count(ps_partkey)")
  9. HashAgg(group="ps_suppkey", count(ps_partkey)="SUM(count(ps_partkey))")
  10. Gather(concurrent=true)
  11. 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无法将子查询进行去关联化,这时候会采用迭代执行的方式。如果外层查询数据量很大,迭代执行可能会非常慢。

下面这个例子中,由于OR l_partkey < 50的存在,导致子查询无法被去关联化,因而采用了迭代执行:

  1. > EXPLAIN SELECT * FROM lineitem WHERE l_partkey IN (SELECT ps_partkey FROM partsupp WHERE ps_suppkey = l_suppkey) OR l_partkey IS NOT
  2. Filter(condition="IS(in,[$1])[29612489] OR l_partkey < ?0")
  3. Gather(concurrent=true)
  4. LogicalView(tables="QIMU_0000_GROUP,QIMU_0001_GROUP.lineitem_[0-7]", shardCount=8, sql="SELECT * FROM `lineitem` AS `lineitem`")
  5. >> individual correlate subquery : 29612489
  6. Gather(concurrent=true)
  7. 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条件。