连接运算 1-SQL 中的 JOIN
连接运算（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,2),(1,3),(2,3)}；A JOIN B ON A=B 的结果是 {(1,1),(2,2)}。我们把过滤条件为等式的称为等值 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 中记录的关联键 a 的 HASH 值为 i，Bi 中记录的关联键 b 的 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。当节点比较多的时候，造成的网络传输量带来的延迟会抵消多机分摊任务得到的好处，所以分布式数据库系统通常有个节点数的极限，达到极限后，更多的节点并不能获得更好的性能。
