SQL 中的 JOIN（JOIN 简化与提速系列 1）

毗连运算（JOIN）不绝是 SQL 中的老浩劫标题。在关联表稍多一点的时间，代码誊写就变得很容易堕落了。而且由于 JOIN 语句的复杂，导致关联查询也不绝是 BI 软件的软肋，险些没有 BI 软件能让业务用户顺畅地完成多表关联查询。对于性能优化也是，关联表较多大概数据量大时，JOIN 的性能也很难过到提拔。
这个系列文章将对 JOIN 运算举行深入讨论，针对性地提出语法简化和性能优化的方法。
一. SQL 中的 JOIN
我们先来看 SQL 是怎样明确 JOIN 运算的。
SQL 对 JOIN 的界说非常简单，就是两个聚集（表）做笛卡尔积后再按某种条件过滤，写出来的语法就是 A JOIN B ON …。理论上讲，笛卡尔积的效果集应该是以两个聚集成员构成的二元组作为成员，不外由于 SQL 中的聚集也就是表，其成员总是有字段的纪录，而且也不支持泛型数据范例来形貌成员为纪录的二元组，以是就简单地把效果集处置惩罚成两表纪录的字段归并后构成的新纪录的聚集。这也是 JOIN 一词在英语中的原意（即把两个纪录的字段毗连起来），并没有乘法（笛卡尔积）的意思。不外，把笛卡尔积成员明确成二元组照旧归并字段的纪录，并不影响我们后续的讨论。
JOIN 的界说中并没有约定过滤条件的情势，理论上，只要效果集是两个源聚集笛卡尔积的子集，都是公道的 JOIN 运算。比如假设聚集 A={1,2},B={1,2,3}，A JOIN B ON A=B 的效果是 {(1,1),(2,2)}; A JOIN B ON A<B 的效果就是 {(1,2),(1,3),(2,3)}。我们把过滤条件为等式的称为等值 JOIN，而不是等值 JOIN 的情况则称为非等值 JOIN。这两个例子中，前者是等值 JOIN，后者优劣等值 JOIN。
对于数据表之间的等值 JOIN，条件大概由多个有 AND 关系的等式构成，语法情势 A JOIN B ON A.ai=B.bi AND …，此中 ai 和 bi 分别是 A 和 B 的字段。有履历的步调员都知道，实际中绝大多数 JOIN 都是等值 JOIN，非等值 JOIN 要少见得多，而且大多数情况都可以转换成等值 JOIN 来处置惩罚，以是我们在这里重点讨论等值 JOIN，而且后续讨论中也重要使用表和纪录而不是聚集和成员来举例。
根据对空值的处置惩罚规则，严格的等值 JOIN 又称为INNER JOIN，还可以再衍生出LEFT JOIN和FULL JOIN，共有三种情况（RIGHT JOIN 可以明确为 LEFT JOIN 的反向关联，不再单独作为一种范例）。评论 JOIN 时一样寻常还会根据两个表中关联纪录（也就是满意过滤条件的二元组）的数目分为一对一、一对多、多对一以及多对多这几种情况，这些通例术语在 SQL 和数据库资料中都有先容，这里就不再多说了。
我们再来看 JOIN 的实现。
最容易想到的简单办法就是按照界说做硬遍历，不区分等值 JOIN 和非等值 JOIN。设表 A 有 n 条纪录，B 有 m 条纪录，要盘算 A JOIN B ON A.a=B.b 时，硬遍历的复杂度会是 n*m，即要举行 n*m 次过滤条件的盘算。
显然这种算法会比力慢。不外，支持多数据源的报表工具中偶尔就是用这种慢办法实现关联的，由于在报表中数据集的关联关系（也就是 JOIN 中的过滤条件）会拆散界说在单位格的运算式中，已经看不出是多个数据集之间的 JOIN 运算，也就只能用遍历方法去盘算这些关联表达式了。
成熟的数据库固然不会这么笨了，对于等值 JOIN，数据库一样寻常会接纳 HASH JOIN 算法。即将关联表的纪录按其关联键（过滤条件中对应相称的字段，即 A.a 和 B.b)的 HASH 值分成多少组，将雷同 HASH 值的纪录分到一组。如 HASH 值范围是 1…k，则将 A 和 B 表都分成 k 个子集 A1,…,Ak 和 B1,…,Bk。Ai 中纪录的关联键的 HASH 值为 i，Bi 中纪录的关联键的 HASH 值也为 i，然后，只要分别在 Ai 和 Bi 之间做遍历毗连就可以了。由于 HASH 差异时字段值也一定差异，假如 i!=j 时，Ai 中纪录不大概和 Bj 中纪录发生关联。假如 Ai 的纪录数是 ni，Bi 的纪录数是 mi，则过滤条件的盘算次数为 sum(ni*mi)，最匀称的情况时，ni=n/k，mi=m/k，则总的复杂度只有原始硬遍历本事的 1/k，能有用地进步运算性能！
以是，多数据源关联报表要提速的话，也必要在数据预备阶段做好关联，否则数据量稍大时性能就会急剧降落。
不外，HASH 函数并不总能包管匀称分拆，在运气不好的时间大概会发生某一组特殊大的情况，那样性能提拔效果就会差很多。而且还不能使用太复杂的 HASH 函数，否则盘算 HASH 的时间又变多了。
当数据量大到凌驾内存时，数据库会使用 HASH 分堆的方法，算是 HASH JOIN 算法的推广。遍历 A 表和 B 表，将纪录按关联键的 HASH 值拆分成多少小子集缓存到外存中，称为分堆。然后再在对应的堆之间做内存 JOIN 运算。同样的原理，HASH 值差异时键值也一定差异，关联肯定发生在对应的堆之间。如许就把大数据的 JOIN 转换成多少小数据的 JOIN 了。
但是雷同地，HASH 函数存在运气标题，有大概会发生某个分堆还特殊大而无法装入内存，这时间就大概要举行二次 HASH 分堆，即换一个 HASH 函数对这组太大的分堆再做一次 HASH 分堆算法。以是，外存 JOIN 运算有大概出现多次缓存的征象，其运算性能有肯定的不可控性。
分布式体系下做 JOIN 也是雷同的，根据关联键的 HASH 值将纪录分发到各个节点机上，称为Shuffle 动作，然后再分别做单机的 JOIN。当节点比力多的时间，造成的网络传输量带来的耽误会抵消多机分摊任务得到的长处，以是分布式数据库做 JOIN 时会有个节点数的极限，到达极限后，更多的节点并不能得到更好的性能。