共计 3353 个字符，预计需要花费 9 分钟才能阅读完成。
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。
原文链接
本文为阿里云原创内容，未经容许不得转载。
