AI 助理
备案控制台
开发者社区 数据库 文章 正文

SQL调优指南—SQL调优进阶—JOIN优化和执行

2022-06-15 253
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文主要介绍如何使用JOIN。JOIN将多个表以某个或某些列为条件进行连接操作而检索出关联数据的过程，多个表之间以共同列而关联在一起。

基本概念

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类型。2.5.png下面是几种不同类型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
 )

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条件，如果满足条件则输出。
  1. 如下为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

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。

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


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

Lookup Join (BKAJoin)

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 ('?'))")

Lookup Join通常用于外表数据量较小的情况，例如上面的例子中，左表partsupp由于存在ps_partkey = 123的过滤条件，仅有几行数据。此外，右表的s_suppkey IN ( ... )查询命中了主键索引，这也使得Lookup Join的查询代价进一步降低。

通过如下Hint可以强制PolarDB-X使用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条件并输出。

Lookup Join (BKAJoin）示例：


> 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使用Sort-Merge Join


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

JOIN顺序

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

例如，对于4张表JOIN（暂不考虑下推的情形），JOIN Tree可以有如下3种形式，同时表的排列又有4! = 24种，一共有72种可能的JOIN顺序。3.2.png

下面是几种不同类型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
)

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条件，如果满足条件则输出。
  1. 如下为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

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。

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


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

Lookup Join (BKAJoin)

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 ('?'))")

Lookup Join通常用于外表数据量较小的情况，例如上面的例子中，左表partsupp由于存在ps_partkey = 123的过滤条件，仅有几行数据。此外，右表的s_suppkey IN ( ... )查询命中了主键索引，这也使得Lookup Join的查询代价进一步降低。

通过如下Hint可以强制PolarDB-X使用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条件并输出。

Lookup Join (BKAJoin）示例：


> 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使用Sort-Merge Join


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

JOIN顺序

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

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

文章标签：
云原生分布式数据库 PolarDB-X
SQL
关系型数据库
索引
MySQL
算法
缓存
存储
xaubllxwtvaqiu
目录
相关文章
赵广陆
|
Oracle Java Linux
Maven搭建Nexus私服
Maven搭建Nexus私服
赵广陆
506 0
有勇气的牛排
|
索引 Python
python操作Elasticsearch7.17.0
python操作Elasticsearch7.17.0 作者主页：https://www.couragesteak.com/
有勇气的牛排
472 0
hackett
|
编解码 Linux 开发工具
ffmpeg的基本用法（下）
ffmpeg的基本用法的下篇来喽！
hackett
1278 0
嘟嘟嘟嘟嘟嘟
|
关系型数据库 MySQL Java
flink cdc 同步问题之多表数据如何同步
Flink CDC（Change Data Capture）是一个基于Apache Flink的实时数据变更捕获库，用于实现数据库的实时同步和变更流的处理；在本汇总中，我们组织了关于Flink CDC产品在实践中用户经常提出的问题及其解答，目的是辅助用户更好地理解和应用这一技术，优化实时数据处理流程。
嘟嘟嘟嘟嘟嘟
1140 0
嘟嘟嘟嘟嘟嘟
|
SQL 缓存 Java
flink cdc 同步问题之如何同步多张库表
Flink CDC（Change Data Capture）是一个基于Apache Flink的实时数据变更捕获库，用于实现数据库的实时同步和变更流的处理；在本汇总中，我们组织了关于Flink CDC产品在实践中用户经常提出的问题及其解答，目的是辅助用户更好地理解和应用这一技术，优化实时数据处理流程。
嘟嘟嘟嘟嘟嘟
2818 0
Davidham3
|
8月前
|
并行计算 Python 容器
uv找不到Python头文件的解决方案
最近在微调LLM的时候，我发现使用uv构建的环境，有时候会找不到Python.h，导致一些库报错，如`fatal error: Python.h: No such file or directory`。通过设置`python-preference`可以解决。
Davidham3
580 35
游客szolpe7lr4a3g
|
5月前
|
弹性计算 供应链 固态存储
2025 首选的 ERPNext 安装指南
ERPNext 是一款基于 Python 和 Node 的开源 ERP 系统，适用于财务、供应链、生产、CRM 等企业数字化管理场景。支持自定义流程与模块适配，可大幅降低信息化成本。部署方式灵活，可通过云平台（如阿里云）快速搭建，或使用 Websoft9 控制台一键安装。适合各类企业实现业务流程数字化、提升运营效率。
游客szolpe7lr4a3g
1742 4
蚝油菜花
|
9月前
|
存储 人工智能 API
OWL：告别繁琐任务！开源多智能体系统实现自动化协作，效率提升10倍
OWL 是基于 CAMEL-AI 框架开发的多智能体协作系统，通过智能体之间的动态交互实现高效的任务自动化，支持角色分配、任务分解和记忆功能，适用于代码生成、文档撰写、数据分析等多种场景。
蚝油菜花
1843 13
OWL：告别繁琐任务！开源多智能体系统实现自动化协作，效率提升10倍
北京宏哥
|
Java 测试技术 Python
《手把手教你》系列技巧篇（五十九）-java+ selenium自动化测试 - 截图三剑客 -上篇（详细教程）
【5月更文挑战第23天】本文介绍了使用Java和Selenium进行自动化测试时如何实现截图操作。原本计划讲解远程测试内容，但因服务器网络问题无法进行，因此转而分享Selenium的截图方法。文章分为三部分，首先简述背景，然后重点介绍了TakeScreenshout类，这是一个用于获取浏览器窗口内容的截图工具，不包含浏览器菜单和任务栏。接着，列举了一个测试场景：访问百度首页并截图保存。最后，提供了代码示例，展示了如何设计自动化测试代码以及截图保存到指定目录，并附有代码运行效果展示。
北京宏哥
258 2
游客j4mujezz7vm7y
|
Linux Android开发 iOS开发
使用Kivy创建“Hello World”应用并打包成APK
使用Kivy创建“Hello World”应用并打包成APK
游客j4mujezz7vm7y
1677 8