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

本文涉及的产品
云原生数据库 PolarDB 分布式版,标准版 2核8GB
简介: 本文主要介绍如何使用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开源数据库
本实验环境已内置PostgreSQL数据库以及PolarDB开源数据库:PolarDB PostgreSQL版和PolarDB分布式版,支持一键拉起使用,方便各位开发者学习使用。
相关文章
|
JavaScript 前端开发
2022年了!你有几种获取URL参数的方法?
前言 作为一个前端开发,我们很多时候都需要对URL进行操作和处理,最常见的一种就是获取URL链接中携带的参数值了。使用框架开发的小伙伴可能会觉得这很简单,因为框架提供了很多方法让我们方便的获取URL链接携带的参数。但是有些时候我们不能依赖框架,需要我们使用原生JS去获取参数,这也是面试中经常遇到的一道题。今天我们就手撕代码,利用原生JS去获取URL链接参数值。
1230 1
2022年了!你有几种获取URL参数的方法?
|
消息中间件 Java 中间件
秒懂消息队列MQ,万字总结带你全面了解消息队列MQ
消息队列是大型分布式系统不可缺少的中间件,也是高并发系统的基石中间件,所以掌握好消息队列MQ就变得极其重要。接下来我就将从零开始介绍什么是消息队列?消息队列的应用场景?如何进行选型?如何在Spring Boot项目中整合集成消息队列。
13844 7
秒懂消息队列MQ,万字总结带你全面了解消息队列MQ
|
SQL 存储 缓存
SQL调优指南—SQL调优进阶—JOIN优化和执行
本文主要介绍如何使用JOIN。JOIN将多个表以某个或某些列为条件进行连接操作而检索出关联数据的过程,多个表之间以共同列而关联在一起。
141 0
SQL调优指南—SQL调优进阶—JOIN优化和执行
|
SQL 存储 算法
SQL调优指南—SQL调优进阶—排序优化和执行
本文介绍如何排序(Order-by)算子,以达到减少数据传输量和提高执行效率的效果。
128 0
|
12月前
|
SQL 存储 关系型数据库
【面试题精讲】MySQL-执行器
【面试题精讲】MySQL-执行器
|
关系型数据库 MySQL 索引
MySQL InnoDB中的锁-插入意向锁(Insert Intention Lock)
MySQL InnoDB 插入意向锁 Insert Intention Lock
3493 0
MySQL InnoDB中的锁-插入意向锁(Insert Intention Lock)
|
存储 SQL JSON
5、DataX(DataX简介、DataX架构原理、DataX部署、使用、同步MySQL数据到HDFS、同步HDFS数据到MySQL)(一)
5、DataX(DataX简介、DataX架构原理、DataX部署、使用、同步MySQL数据到HDFS、同步HDFS数据到MySQL)(一)
|
存储 SQL JSON
【MySQL从入门到精通】【高级篇】(二十五)EXPLAIN中ref、rows、filtered、Extra字段的剖析
上一篇文章我们介绍了 【MySQL从入门到精通】【高级篇】(二十四)EXPLAIN中select_type,partition,type,key,key_len字段的剖析,重点介绍了EXPLAIN命令的select_type,partition,type,key,key_len 字段含义。这篇文章我将接着介绍剩余字段的含义。本文会介绍ref、rows、filtered、Extra这几个字段。比较重要的两个字段是rows、Extra
1393 0
【MySQL从入门到精通】【高级篇】(二十五)EXPLAIN中ref、rows、filtered、Extra字段的剖析
|
Oracle Java 关系型数据库
Java中JDK8、JDK11、JDK17,该怎么选择?
Java这个语言,1995 年发展至今,生态方面就不多说了,没有强大的生态,在科技快速发展的今天,是不可能被互联网企业与开发者认同的。
16827 0
|
SQL 存储 算法
如何写出高性能的SQL Join: join实现和最佳实践
Join是数据库和数仓中最常用的一个感念了。在关系型数据库的数据模型中,为了避免数据冗余存储,不同的数据往往放在不同的表中,分为事实表和维度表,这样做可以极大的节省数据存储空间。但是在分析数据时,则需要通过join把多表关联起来分析。可以说,做数据分析,绕不开的一个话题就是join。而join有多种类型,在使用上有不同的使用方式,而在实现上也有不同的实现方式。不同的使用方式和实现方式,则会造成性能上的天差地别。本文尝试由表及里梳理join的使用和内部实现方式,通过了解内部实现,了解如何写出一个高性能的join SQL。
2588 2
如何写出高性能的SQL Join: join实现和最佳实践