您现在的位置是：网站首页> 编程资料编程资料
Mysql体系化探讨令人头疼的JOIN运算_Mysql_
2023-05-26
453人已围观
简介 Mysql体系化探讨令人头疼的JOIN运算_Mysql_
前言
- 之前经历过从零到一初创项目，也有海量数据项目；总体来说当项目在逐渐发展过程中如何构建一个安全可靠，稳定的数据存储一直是项目中最核心、最重要、最关键部分，没有之一
- 接下来我会体系化输出存储系列文章；本篇文章我们先谈一下数据中一个最令人头疼的连接运算—JOIN
- JOIN 一直是SQL中的老大难问题。在关联表稍多一点的时候，代码书写就变得很容易出错了且因为JOIN语句的复杂，导致关联查询也一向是BI软件的软肋，几乎没有BI软件能让业务用户顺畅地完成多表关联查询。对于性能优化也是，关联表较多或者数据量大时，JOIN的性能也很难得到提升
- 基于以上，本文将对JOIN运算进行体系化深入的探讨，根据自己工作经验及参考业界经典案例，针对性地提出语法简化和性能优化的方法论，希望对大家有所帮助
一图总览
SQL中的JOIN
SQL是如何理解JOIN运算
SQL对JOIN的定义
两个集合（表）做笛卡尔积后再按某种条件过滤，写出来的语法就是A JOIN B ON …。
- 理论上讲，笛卡尔积的结果集应该是以两个集合成员构成的二元组作为成员，不过由于SQL中的集合也就是表，其成员总是有字段的记录，而且也不支持泛型数据类型来描述成员为记录的二元组，所以就简单地把结果集处理成两表记录的字段合并后构成的新记录的集合。
- 这也是JOIN一词在英语中的原意（即把两个记录的字段连接起来），并没有乘法（笛卡尔积）的意思。不过，把笛卡尔积成员理解成二元组还是合并字段的记录，并不影响我们后续的讨论。
JOIN定义
- JOIN的定义中并没有约定过滤条件的形式，理论上，只要结果集是两个源集合笛卡尔积的子集，都是合理的JOIN运算。
- 例子：假设集合A={1,2},B={1,2,3}，A JOIN B ON A
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。
- 当节点比较多的时候，造成的网络传输量带来的延迟会抵消多机分摊任务得到的好处，所以分布式数据库系统通常有个节点数的极限，达到极限后，更多的节点并不能获得更好的性能。
等值JOIN的剖析
三种等值JOIN：
外键关联
- 表A的某个字段和表B的主键字段关联（所谓字段关联，就是前一节说过的在等值JOIN的过滤条件中要对应相等的字段）。A表称为事实表，B表称为维表。A表中与B表主键关联的字段称为A指向B的外键，B也称为A的外键表。
- 这里说的主键是指逻辑上的主键，也就是在表中取值唯一、可以用于唯一某条记录的字段（组），不一定在数据库表上建立过主键。
- 外键表是多对一的关系，且只有JOIN和LEFT JOIN，而FULL JOIN非常罕见。
- 典型案例：商品交易表和商品信息表。
- 显然，外键关联是不对称的。事实表和维表的位置不能互换。
同维表
- 表A的主键与表B的主键关联，A和B互称为同维表。同维表是一对一的关系，JOIN、LEFT JOIN和FULL JOIN的情况都会有，不过在大多数数据结构设计方案中，FULL JOIN也相对少见。
- 典型案例：员工表和经理表。
- 同维表之间是对称的，两个表的地位相同。同维表还构成是等价关系，A和B是同维表，B和C是同维表，则A和C也是同维表。
主子表
- 表A的主键与表B的部分主键关联，A称为主表，B称为子表。主子表是一对多的关系，只有JOIN和LEFT JOIN，不会有FULL JOIN。
- 典型案例：订单和订单明细。
- 主子表也是不对称的，有明确的方向。
- 在SQL的概念体系中并不区分外键表和主子表，多对一和一对多从SQL的观点看来只是关联方向不同，本质上是一回事。确实，订单也可以理解成订单明细的外键表。但是，我们在这里要把它们区分开，将来在简化语法和性能优化时将使用不同的手段。
- 我们说，这三种JOIN已经涵盖了绝大多数等值JOIN的情况，甚至可以说几乎全部有业务意义的等值JOIN都属于这三类，把等值JOIN限定在这三种情况之中，几乎不会减少其适应范围。
- 仔细考察这三种JOIN，我们发现所有关联都涉及主键，没有多对多的情况，是不是可以不考虑这种情况？
- 是的！多对多的等值JOIN几乎没有业务意义。
- 如果两个表JOIN时的关联字段没有涉及到任何主键，那就会发生多对多的情况，而这种情况几乎一定还会有一个规模更大的表把这两个表作为维表关联起来。比如学生表和科目表在JOIN时，会有个成绩表把学生表和科目表作为维表，单纯只有学生表和科目表的JOIN没有业务意义。
- 当写SQL语句时发现多对多的情况，那大概率是这个语句写错了！或者数据有问题！这条法则用于排除JOIN错误很有效。
- 不过，我们一直在说“几乎”，并没有用完全肯定的说法，也就是说，多对多在非常罕见的情况下也会业务意义。可举一例，用SQL实现矩阵乘法时会发生多对多的等值JOIN，具体写法读者可以自行补充。
- 笛卡尔积再过滤这种JOIN定义，确实非常简单，而简单的内涵将得到更大的外延，可以把多对多等值JOIN甚至非等值JOIN等都包括进来。但是，过于简单的内涵无法充分体现出最常见等值JOIN的运算特征。这会导致编写代码和实现运算时就不能利用这些特征，在运算较为复杂时（涉及关联表较多以及有嵌套的情况），无论是书写还是优化都非常困难。而充分利用这些特征后，我们就能创造出更简单的书写形式并获得更高效的运算性能，后面的内容中将会逐步加以说明。
- 与其为了把罕见情况也被包括进来而把运算定义为更通用的形式，还不如把这些情况定义成另一种运算更为合理。
JOIN的语法简化
如何利用关联都涉及主键这个特征来简化JOIN的代码书写？
外键属性化
例子，设有如下两个表：
employee 员工表 id 员工编号 name 姓名 nationality 国籍 department 所属部门 department 部门表 id 部门编号 name 部门名称 manager 部门经理
- employee表和department表的主键都是其中的id字段，employee表的department字段是指向department表的外键，department表的manager字段又是指向employee表的外键（因为经理也是个员工）。这是很常规的表结构设计。
- 现在我们想问一下：哪些美国籍员工有一个中国籍经理？用SQL写出来是个三表JOIN的语句：
SELECT A.* FROM employee A JOIN department B ON A.department=B.id JOIN employee C ON B.manager=C.id WHERE A.nationality='USA' AND C.nationality='CHN'
- 首先要FROM employee用于获取员工信息，然后这个employee表要和department做JOIN获取员工的部门信息，接着这个department表还要再和employee表JOIN要获取经理的信息，这样employee表需要两次参与JOIN，在SQL语句中要为它起个别名加以区分，整个句子就显得比较复杂难懂。
- 如果我们把外键字段直接理解成它关联的维表记录，就可以换一种写法：
SELECT * FROM employee WHERE nationality='USA' AND department.manager.nationality='CHN'
当然，这不是标准的SQL语句了。
- 第二个句子中粗体部分表示当前员工的“所属部门的经理的国籍”。我们把外键字段理解成维表的记录后，维表的字段被理解为外键的属性，department.manager即是“所属部门的经理”，而这个字段在department中仍然是个外键，那么它对应的维表记录字段可以继续理解为它的属性，也就会有department.manager.nationality，即“所属部门的经理的国籍”。
- 外键属性化:这种对象式的理解方式即为外键属性化，显然比笛卡尔积过滤的理解方式要自然直观得多。外键表JOIN时并不会涉及到两个表的乘法，外键字段只是用于找到维键表中对应的那条记录，完全不会涉及到笛卡尔积这种有乘法特性的运算。
- 我们前面约定，外键关联时时维表中关联键必须是主键，这样，事实表中每一条记录的外键字段关联的维表记录就是唯一的，也就是说employee表中每一条记录的department字段唯一关联一条department表中的记录，而department表中每一条记录的manager字段也唯一关联一条employee表中的记录。这就保证了对于employee表中的每一条记录，department.manager.nationality都有唯一的取值，可以被明确定义。
- 但是，SQL对JOIN的定义中并没有主键的约定，如果基于SQL的规则，就不能认定与事实表中外键关联的维表记录有唯一性，有可能发生与多条记录关联，对于employee表的记录来讲，department.manager.nationality没有明确定义，就不能使用了。
- 事实上，这种对象式写法在高级语言（如C，Java）中很常见，在这类语言中，数据就是按对象方式存储的。employee表中的department字段取值根本就是一个对象，而不是编号。其实许多表的主键取值本身并没有业务意义，仅仅是为了区分记录，而外键字段也仅仅是为了找到维表中的相应记录，如果外键字段直接是对象，就不需要再通过编号来标识了。不过，SQL不能支持这种存储机制，还要借助编号。
- 我们说过外键关联是不对称的，即事实表和维表是不对等的，只能基于事实表去找维表字段，而不会有倒过来的情况。
同维表等同化
同维表的情况相对简单，还是从例子开始，设有两
