开发者社区> 云雷> 正文

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

简介: 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。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14280 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19811 0
高性能计算--EHPC工业仿真最佳实践
本方案通用于采用高性能计算集群进行大批量计算场景。本例以LJ函数为算例,使用阿里云EHPC集群,LAMMPS模拟计算分子势能,并将结果自动上传到OSS,并图形化展示计算结果。
1067 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
29195 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
13578 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22540 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20710 0
+关注
云雷
日志计算驱动业务增长 让天下没有难分析的日志
104
文章
2
问答
来源圈子
更多
阿里云存储基于飞天盘古2.0分布式存储系统,产品包括对象存储OSS、块存储Block Storage、共享文件存储NAS、表格存储、日志存储与分析、归档存储及混合云存储等,充分满足用户数据存储和迁移上云需求,连续三年跻身全球云存储魔力象限四强。
+ 订阅
相关文档: 混合云容灾服务 混合云备份服务 日志服务
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载