SQL是如何理解JOIN运算

发布时间：2024-01-01 02:25:32 所属栏目：MySql教程来源：DaWei

导读： JOIN定义
JOIN的定义中并没有约定过滤条件的形式，理论上，只要结果集是两个源集合笛卡尔积的子集，都是合理的JOIN运算。
例子：假设集合A={1,2},B={1,2,3}，A JOIN B ON A<B的结果就是{(

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。

等值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时，硬遍历的复杂度会是nm，即要进行nm次过滤条件的计算。

显然这种算法会比较慢。不过，支持多数据源的报表工具中有时就是用这种慢办法实现关联的，因为在报表中数据集的关联关系（也就是JOIN中的过滤条件）会拆散定义在单元格的运算式中，已经看不出是多个数据集之间的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
分布式系统下做JOIN也是类似的，根据关联键的HASH值将记录分发到各个节点机上，称为Shuffle动作，然后再分别做单机的JOIN。

当节点比较多的时候，造成的网络传输量带来的延迟会抵消多机分摊任务得到的好处，所以分布式数据库系统通常有个节点数的极限，达到极限后，更多的节点并不能获得更好的性能。

（编辑：拼字网 - 核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!