Join是数据库和数仓中最罕用的一个感怀了。在关系型数据库的数据模型中，为了防止数据冗余存储，不同的数据往往放在不同的表中，分为事实表和维度表，这样做能够极大的节俭数据存储空间。然而在剖析数据时，则须要通过join把多表关联起来剖析。能够说，做数据分析，绕不开的一个话题就是join。而join有多种类型，在应用上有不同的应用形式，而在实现上也有不同的实现形式。不同的应用形式和实现形式，则会造成性能上的天差地别。本文尝试由表及里梳理join的应用和外部实现形式，通过理解外部实现，理解如何写出一个高性能的join SQL。
join类型
SQL Join从大的分类上，分为Inner Join，Outer Join，Self Join和Cross 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 joinSelf 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))。
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。
原文链接
本文为阿里云原创内容，未经容许不得转载。