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


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

join类型

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

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


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

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))。

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

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。

上一篇:小米游戏本加装固态(三盘同用)


下一篇:解决MFC使用OpenCV动态库会误报内存泄露的问题(太多人遇到这个问题了)