如何写出高性能的SQL Join: join实现和最佳实践

本文涉及的产品
对象存储 OSS,20GB 3个月
对象存储 OSS,恶意文件检测 1000次 1年
对象存储 OSS,内容安全 1000次 1年
简介: Join是数据库和数仓中最常用的一个感念了。在关系型数据库的数据模型中,为了避免数据冗余存储,不同的数据往往放在不同的表中,分为事实表和维度表,这样做可以极大的节省数据存储空间。但是在分析数据时,则需要通过join把多表关联起来分析。可以说,做数据分析,绕不开的一个话题就是join。而join有多种类型,在使用上有不同的使用方式,而在实现上也有不同的实现方式。不同的使用方式和实现方式,则会造成性能上的天差地别。本文尝试由表及里梳理join的使用和内部实现方式,通过了解内部实现,了解如何写出一个高性能的join SQL。


Join是数据库和数仓中最常用的一个感念了。在关系型数据库的数据模型中,为了避免数据冗余存储,不同的数据往往放在不同的表中,分为事实表和维度表,这样做可以极大的节省数据存储空间。但是在分析数据时,则需要通过join把多表关联起来分析。可以说,做数据分析,绕不开的一个话题就是join。而join有多种类型,在使用上有不同的使用方式,而在实现上也有不同的实现方式。不同的使用方式和实现方式,则会造成性能上的天差地别。本文尝试由表及里梳理join的使用和内部实现方式,通过了解内部实现,了解如何写出一个高性能的join SQL。

join类型

image.png

SQL Join从大的分类上,分为Inner Join,Outer Join,Self Join和Cross Join。


image.png

Inner join

内连接Inner Join是最常用的一种连接方式。左右表通过谓词连接。只有既在左表出现的行、又在右表出现的行才满足条件,也就是左右表的交集。语法是 select  A.x, B.y from A join B on A.x = B.y 内连接不区分左右表的顺序,A inner join B 等同于 B join A。

Inner Join又分为 Equal join和Non Equal Join(Theta Join)。 区别在于,Equal join是在连接条件中,左表的某个字段等与右表的某个字段。而Theta Join的连接条件,不是一个相等条件,有可能是大于或者小于条件。

Outer join

Outer Join包括Left Join,Right Join, Full Join。各个join的不同点参考上图。

Left Join返回左表的全部行,不论这些行是否和右表匹配。这些数据中,又分为两类,分别是匹配右表的数据和不匹配右表的数据。对于左右表交集的部分,即匹配右表的数据,分别输出左右表的列。对于不在交集中的部分,即不匹配右表的数据,输出左表的列值,右表的列值为null。left join不可以左右互换。

right join和left join对称,返回右表的全部行,不论这些数据行是否和左表匹配。这些数据中,又分为两类,分别是匹配左表的数据和不匹配左表的数据。对于左右表有交集的部分,即匹配左表的数据,输出左右表的列。对于不在交集中的行,正常输出右表的列,而左表的列卫null。right join也是不可以左右互换的。但left join和right join是左右对称的。即一个left join可以转写成right join。 A left join B 等同于A right join B

full join是left join和right join的综合,返回的是左右表的并集。在结果中包含三部分数据,分别是左右表的交集(同时匹配左表和右表的数据)、只匹配左表的数据、只匹配右表的数据。对于左右表的交集数据,输出左右表的列值。对于只匹配左表的数据,输出左表的列,右表的列为null。对于只匹配右表的数据,输出右表的列,左表的列为null。

Inner Join和Outer join的区别

Inner Join和Outer Join的区别在于,Inner Join的结果是左右表中同时存在的行,即两个表的交集,也就是结果都在左右表内部。而Outer Join的结果中,可能包含不属于本表的行,如下图中的left join、right join和full join,有些结果是属于本表外部的,所以称为outer join

Cross Join

Cross join是两个表的的笛卡尔积,即左表和右表的N*M种组合。这种一般很少用到,毕竟不是所有的组合都是有意义的。一般在组合后,再加上筛选条件,选择出部分有意义的结果。使用方式如:A cross join

Self Join

Self Join顾名思义,就是自己join 自己,左右表都是自己,可能是inner join,也可能是outer join。

Semi join

Semi Join是半连接,从一个表中返回的行与另一个表中数据行进行不完全联接查询(查找到匹配的数据行就返回,不再继续查找)。典型的查询如in和exists查询。

Anti Semi join

Anti-semi-join 从一个表中返回的行与另一个表中数据行进行不完全联接查询,然后返回不匹配的数据。典型的查询时not exists和not in。

例如 select * from A where not exists (select B.y from B)

join实现方式

了解系统实现,有助于我们写出性能最佳的SQL。 如果不做任何优化,一个朴素的Hash算法是怎么做的?用两层循环,依次遍历左表和右表的每一行,然后判定连接条件,如果满足连接条件,则输出该行。这种做法称为Product Join(点积join)。

for rowX in left_table:

   for rowY in right_table:

    if rowX match rowY

        output rowX and rowY

这种做法虽然能达到目的,但显然这种做法的时间复杂度是O(N*M),速度是非常慢的。于是有了下边几种更加快速实现方式。

Sort Merge

首先对左右表排序,然后把两个排好序的表按照多路归并算法,合并两个排序表。排序的时间复杂度是O(nlog(n)),归并时间复杂的是O(n)。整体时间复杂度是O(nlog(n))。

image.png

Hash Join

Hash Join的算法是对右表构建Hash表,然后遍历左表,根据join key的hash值到hash表中寻找。因此右表称为build side, 左表称为probe side。

构建Hash表的时间复杂度是O(n)。probe的时间复杂度也是O(n)。更重要的时,Hash Join可以用来做分布式join,当数据量太大时,可以把数据Hash到不同的机器上,相同的数据Hash到同一个机器上匹配。可以利用分布式机器解决大数据的join问题。

BroadCast Hash Join

HashJoin要求把左右表都计算Hash,然后按照Hash key分发到其他机器上执行join。如果数据很大的话,shuffle的代价就很大。这个时候就可以区分下情况,如果另一张表也很大,那只能乖乖的Hash做分布式处理了;但如果另外一张表很小,则可以直接把这个小表广播拷贝到大表所在的机器上,这样大表就避免了shuffle。

Shuffle Sort Merge Join

对于大表和大表的join。除了Shuffle hash Join,还可以用shuffle sort merge join,区别在于,Hash Join按照特定的hash key shuffle到固定机器上。而shuffle sort merge join可以按照一个更加宽泛的partition key shuffle到固定机器上。同一个partition的数据,shuffle到同一台机器上,再按照单机的sort merge算法join。


关系型数据库和数仓的不同做法

我们在上文讨论join的实现方式时,有一个隐含的前提是,数据是存在数仓中的。数据量比较大,是多partitoin存储的,左右表更是在不同机器上存储的。而单机的关系性数据库,左右表的全部数据存储在同一个机器上,因此两者的算法存在很大不同。对于数仓而言,天然的需要shuffle数据,把左右表移动到同一个机器上。不过,根据表的大小,有不同的优化方案。如果一个表很小,那么只需要广播这张小表就够了;如果两个表都很大,那么只能乖乖的shuffle两张表了。

Equal join和None Equal join

如果join连接条件中,全都是相等条件,那么在join时,就可以直接按照连接条件进行shuffle,同时按照hash key构建hash表,这样probe的时候,就能够利用hash表在O(1)级别查找数据。

但如果连接条件中包含了非相等条件,或者包含or,那么在连接时,只能逐行验证条件了。

最佳实践

上文介绍了SQL的使用方式和内部实现,通过了解内部实现,我们可以大致了解到如何写出一个高性能的join 语句了

1: 尽量大表join小表,不要大表join大表。

2: 在连接条件中使用相等条件和and条件,不要有or条件。

3: 尽量使用inner join或者outer join,不要使用cross join。

相关实践学习
数据库实验室挑战任务-初级任务
本场景介绍如何开通属于你的免费云数据库,在RDS-MySQL中完成对学生成绩的详情查询,执行指定类型SQL。
阿里云云原生数据仓库AnalyticDB MySQL版 使用教程
云原生数据仓库AnalyticDB MySQL版是一种支持高并发低延时查询的新一代云原生数据仓库,高度兼容MySQL协议以及SQL:92、SQL:99、SQL:2003标准,可以对海量数据进行即时的多维分析透视和业务探索,快速构建企业云上数据仓库。 了解产品 https://www.aliyun.com/product/ApsaraDB/ads
目录
相关文章
|
8天前
|
SQL 关系型数据库 MySQL
7种SQL Join语句
7种SQL Join语句
12 1
|
3月前
|
SQL
sql 各种join 对比
sql 各种join 对比
27 0
|
5月前
|
SQL 数据库
04SQL - SQL连接 left join
04SQL - SQL连接 left join
24 0
|
5月前
|
SQL 关系型数据库 数据挖掘
软件测试|教你学会SQL LEFT JOIN的使用
软件测试|教你学会SQL LEFT JOIN的使用
32 0
|
5月前
|
SQL 存储 关系型数据库
软件测试|SQL JOIN的用法,你会了吗?
软件测试|SQL JOIN的用法,你会了吗?
43 0
|
6月前
|
SQL
SQL语句多个表查询,inner join的用法
SQL语句多个表查询,inner join的用法
86 0
|
2月前
|
SQL Java 数据库连接
这个问题是由于Flink在执行SQL语句时,无法找到合适的表工厂来处理JOIN操作。
【1月更文挑战第17天】【1月更文挑战第85篇】这个问题是由于Flink在执行SQL语句时,无法找到合适的表工厂来处理JOIN操作。
21 8
|
3月前
|
SQL 数据库
SQL FULL OUTER JOIN 关键字:左右表中所有记录的全连接解析
SQL RIGHT JOIN关键字返回右表(table2)中的所有记录以及左表(table1)中的匹配记录。如果没有匹配,则左侧的结果为0条记录。
56 0
|
3月前
|
SQL 数据库
SQL JOIN 子句:合并多个表中相关行的完整指南
SQL LEFT JOIN关键字返回左表(table1)中的所有记录以及右表(table2)中的匹配记录。如果没有匹配,则右侧的结果为0条记录。
50 0
|
5月前
|
SQL 测试技术
软件测试|深入理解SQL CROSS JOIN:交叉连接
软件测试|深入理解SQL CROSS JOIN:交叉连接
37 0

相关产品

  • 对象存储
  • 文件存储NAS
  • 日志服务