Mysql体系化解析之JOIN运算

本篇文章给大家带来了关于mysql的相关知识，主要介绍了体系化探讨令人头疼的JOIN运算,本文将对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的代码书写？

外键属性化

例子，设有如下两个表：

cf8d4bb0e624e981079e04acd0a64cac

• 这个写法其实也就预示了它还可以有更好的优化方案，下面来看看怎样实现。
• 如果所有数据都能够装入内存，我们可以实现外键地址化。
• 将事实表orders中的外键字段custkey，转换成维表customer中关联记录的地址，即orders表的custkey的取值已经是某个customer表中的记录，那么就可以直接引用记录的字段进行计算了。
• 用SQL无法描述这个运算的细节过程，我们使用SPL来描述、并用文件作为数据源来说明计算过程：

• A1读出客户表，A2为客户表设置主键并建立索引。
• A3读出订单表，A4的动作是将A3的外键字段custkey转换成对应的A1的记录，执行完后，订单表字段custkey将变成客户表的某条记录。A2建了索引能让switch更快，因为通常事实表远大于维表，这个索引能被复用很多次。
• A5就可以执行分组汇总了，遍历订单表时，由于custkey字段取值现在已经是一条记录，那么可以直接用.操作符引用其字段了，custkey.city就可以正常执行。
• 完成A4中的switch动作之后，内存中事实表A3的custkey字段存储内容已经是维表A1的某条记录的地址，这个动作即称为外键地址化。这时候引用维表字段时，可以直接取出，而不需要再用外键值在A1中查找，相当于在常数时间内就能取到维表的字段，避免了HASH值计算和比对。
• 不过，A2建主键索引一般也会用HASH办法，对key计算HASH值，A4转换地址时也是计算custkey的HASH值与A2的HASH索引表对比。如果只做一次关联运算，地址化的方案和传统HASH分段方案的计算量基本上一样，没有根本优势。
• 但不同的是，如果数据能在内存中放下，这个地址一旦转换之后可以复用，也就是说A1到A4只要做一次，下次再做关于这两个字段的关联运算时就不必再计算HASH值和比对了，性能就能大幅提高。
• 能够这样做，正是利用了前面说过的外键关联在维表这一方具有的唯一性，一个外键字段值只会唯一对应一条维表记录，可以把每个custkey转换成它唯一对应的那条A1的记录。而延用SQL中对JOIN的定义，就不能假定外键指向记录的唯一性，无法使用这种表示法。而且SQL也没有记录地址这种数据类型，结果会导致每次关联时都要计算HASH值并比对。
• 而且，如果事实表中有多个外键分别指向多个维表，传统的HASH分段JOIN方案每次只能解析掉一个，有多个JOIN要执行多遍动作，每次关联后都需要保持中间结果供下一轮使用，计算过程复杂得多，数据也会被遍历多次。而外键地址化方案在面对多个外键时，只要对事实表遍历一次，没有中间结果，计算过程要清晰很多。
• 还有一点，内存本来是很适合并行计算的，但HASH分段JOIN算法却不容易并行。即使把数据分段并行计算HASH值，但要把相同HASH值的记录归聚到一起供下一轮比对，还会发生共享资源抢占的事情，这将牺牲很多并行计算的优势。而外键式JOIN模型下，关联两表的地位不对等，明确区分出维表和事实表后，只要简单地将事实表分段就可以并行计算。
• 将HASH分段技术参照外键属性方案进行改造后，也能一定程度地改善多外键一次解析和并行能力，有些数据库能在工程层面上实施这种优化。不过，这种优化在只有两个表JOIN时问题不大，在有很多表及各种JOIN混在一起时，数据库并不容易识别出应当把哪个表当作事实表去并行遍历、而把其它表当作维表建立HASH索引，这时优化并不总是有效的。所以我们经常会发现当JOIN的表变多时性能会急剧下降的现象（常常到四五个表时就会发生，结果集并无显著增大）。而从JOIN模型上引入外键概念后，将这种JOIN专门处理时，就总能分清事实表和维表，更多的JOIN表只会导致性能的线性下降。
• 内存数据库是当前比较火热的技术，但上述分析表明，采用SQL模型的内存数据库在JOIN运算上是很难快起来的！

进一步的外键关联

• 我们继续讨论外键JOIN，并延用上一节的例子。
• 当数据量大到无法全部放进内存时，前述的地址化方法就不再有效了，因为在外存无法保存事先算好的地址。
• 一般来讲，外键指向的维表容量较小，而不断增长的事实表要大得多。如果内存还能把维表放下的话，我们可以采用临时指向的方法来处理外键。

	A
1	=file(“customer.btx”).import@b()
2	>A1.keys@i(key)
3	=file(“orders.btx”).import@b()
4	>A3.switch(custkey,A1)
5	=A3.groups(custkey.city;sum(amount))

	A
1	=file(“customer.btx”).import@b()
2	=file(“orders.btx”).cursor@b()
3	>A2.switch(custkey,A1:#)
4	=A2.groups(custkey.city;sum(amount))

• 前两步与全内存时相同，第4步的地址转换是边读入边进行的，而且转换结果无法保留复用，下次再做关联时还要再计算HASH和比对，性能要比全内存的方案差。计算量方面，比HASH JOIN算法少了一次维表的HASH值计算，这个维表如果经常被复用时会占些便宜，但因为维表相对较小，总体优势并不算大。不过，这个算法同样具有全内存算法可以一次解析全部外键以及易于并行的特点，在实际场景下比HASH JOIN算法仍有较大的性能优势。

外键序号化

在这个算法基础上，我们还可以做个变种：外键序号化。

如果我们能把维表的主键都转换成从1开始的自然数，那么我们就可以用序号直接定位维表记录，就不需要计算和比对HASH值，这样就可以获得类似全内存下地址化的性能了。

	A
1	=file(“customer.btx”).import@b()
2	=file(“orders.btx”).cursor@b()
3	>A2.switch(custkey,A1:#)
4	=A2.groups(custkey.city;sum(amount))

• 维表主键是序号时就不需要再做原来建HASH索引的第2步了。
• 外键序号化本质上相当于在外存实现地址化。这种方案需要把事实表中的外键字段转换成序号，这类似在全内存运算时地址化的过程，这个预计算也可以得到复用。需要注意的是，维表发生重大变化时，需要同步整理事实表的外键字段，否则可能对应错位。不过一般维表变化频度低，而且大多数动作是追加和修改而非删除，需要重整事实表的情况并不多。工程上的细节处理也可以再参考乾学院中的资料。
• SQL使用了无序集合的概念，即使我们事先把外键序号化了，数据库也无法利用这个特点，不能在无序集合上使用序号快速定位的机制，只能使用索引查找，而且数据库并不知道外键被序号化了，仍然会去计算HASH值和比对。
• 如果维表也大到内存装不下呢？
• 我们仔细分析上面的算法会发现，过程中对于事实表的访问是连续的，但对于维表的访问则是随机的。我们以前讨论硬盘的性能特征时谈到过，外存不适合随机访问，所以外存中的维表不能再使用上述算法了。
• 外存中的维表可以事先按主键排序存储，这样我们就可以继续利用维表关联键是主键的特征来优化性能。
• 如果事实表很小，可以在内存装放下，那么用外键去关联维表记录实际上会变成一个（批量）外存查找动作。只要维表上针对主键建有索引，也可以很快地查找，这样可以避免遍历大维表，获得更好的性能。这种算法也可以同时解析多个外键。SQL不区分维表和事实表，面对一大一小两个表时，优化过的HASH JOIN不会再做分堆缓存，通常会把小表读入内存而去遍历大表，这样仍然会有遍历大维表的动作，性能会比刚才说的外存查找算法差得多。
• 如果事实表也很大，则可以使用单边分堆的算法。因为维表已经按关联键（即主键）有序，可以方便地逻辑上分成若干段并取出每一段的边界值（每一段主键的最大最小值），然后将事实表按这些边界值做分堆，每一堆分别和维表的每一段再做关联就可以了。过程中只需要对事实表单边做物理分堆缓存，维表不需要再做物理分堆缓存，而且不使用HASH函数，直接用分段，不可能会出现HASH函数运气不好导致二次分堆，性能是可控的。而数据库的HASH分堆算法会将两个大表都做物理分堆缓存，也就是双边分堆，还可能出现HASH函数运气不好导致二次分堆的现象，性能要比单边分堆差得多，还不可控。

借助集群的力量解决大维表问题。

• 一台机器的内存装不下，可以多搞几台机器来装下，把维表按主键值分段存放在多台机器上形成集群维表，然后就可以继续使用上面针对内存维表的算法了，也能获得一次解析多个外键和易于并行的好处。同样地，集群维表也可以使用序号化的技术。这种算法下，事实表不需要被传输，产生的网络传输量并不大，也不需要节点本地缓存数据。而SQL体系下不能区分出维表，HASH拆分方法要将两个表都做Shuffle动作，网络传播量要大得多。
• 这些算法的细节仍有些复杂，这里限于篇幅无法详细解释，有兴趣的读者可以去乾学院的资料查阅。

有序归并

同维表&主子表的JOIN优化提速手段

• 我们前面讨论过，HASH JOIN算法的计算复杂度（即关联键的比较次数）是SUM(nimi)，比全遍历的复杂度nm要小很多，不过要看HASH函数的运气。
• 如果这两个表都对关联键有序，那么我们就可以使用归并算法来处理关联，这时的复杂度是n+m；在n和m都较大的时候（一般都会远大于HASH函数的取值范围），这个数也会远小于HASH JOIN算法的复杂度。归并算法的细节有很多材料介绍，这里就不再赘述了。
• 但是，外键JOIN时不能使用这个办法，因为事实表上可能有多个要参与关联的外键字段，不可能让同一个事实表同时针对多个字段都有序。
• 同维表和主子表却可以！因为同维表和主子表总是针对主键或主键的一部分关联，我们可以事先把这些关联表的数据按其主键排序。排序的成本虽然较高，但是一次性的。一旦完成了排序，以后就可以总是使用归并算法实现JOIN，性能可以提高很多。
• 这还是利用了关联键是主键（及其部分）的特征。
• 有序归并对于大数据特别有效。像订单及其明细这种主子表是不断增长的事实表，时间长了常常会积累得非常大，很容易超出内存容量。
• 外存大数据的HASH分堆算法需要产生很多缓存，数据在外存中被读两次写一次，IO开销很大。而归并算法时，两个表的数据都只要读一次就行了，没有写。不仅是CPU的计算量减少，外存的IO量也大幅下降。而且，执行归并算法需要的内存很少，只要在内存中为每个表保持数条缓存记录就可以了，几乎不会影响其它并发任务对内存的需求。而HASH分堆需要较大内存，每次读出更多数据，以减少分堆的次数。
• SQL采用笛卡尔积定义的JOIN运算不区分JOIN类型，不假定某些JOIN总是针对主键的，就没办法从算法层面上利用这一特点，只能在工程层面进行优化。有些数据库会检查数据表在物理存储上是否针对关联字段有序，如果有序则采用归并算法，但基于无序集合概念的关系数据库不会刻意保证数据的物理有序性，许多操作都会破坏归并算法的实施条件。使用索引可以实现数据的逻辑有序，但物理无序时的遍历效率还是会大打折扣。
• 有序归并的前提是将数据按主键排序，而这类数据常常会不断追加，原则上每次追加后就要再次排序，而我们知道大数据排序成本通常很高，这是否会导致追加数据难度很大呢？其实，追加数据再加入的过程也是个有序归并，把新增数据单独排序后和已有序的历史数据归并，复杂度是线性的，相当于把所有数据重写一次，而不像常规的大数据排序需要缓存式写出再读入。在工程上做些优化动作还可以做到不必每次都全部重写，进一步提高维护效率。这些在乾学院上都有介绍。

分段并行

• 有序归并的好处还在于易于分段并行。
• 现代计算机的都有多核CPU，SSD硬盘也有较强的并发能力，使用多线程并行计算就能够显著提高性能。但传统的HASH分堆技术实现并行比较困难，多线程做HASH分堆时需要同时向某个分堆写出数据，造成共享资源冲突；而第二步实现某组分堆关联时又会消费大量内存，无法让实施较大的并行数量。
• 使用有序归并实现并行计算时需要把数据分成多段，单个表分段比较简单，但两个关联表分段时必须同步对齐，否则归并时两个表数据错位了，就无法得出正确的计算结果，而数据有序就可以保证高性能的同步对齐分段。
• 先把主表（同维表则取较大的即可，其它讨论不影响）平均分成若干段，读出每段第一条记录的主键值，然后用这些键值到子表中用二分法寻找定位（因为也有序），从而获得子表的分段点。这样可以保证主子表的分段是同步对齐的。
• 因为键值有序，所以主表每段的记录键值都属于某个连续区间，键值在区间外的记录不会在这一段，键值在区间内的记录一定在这一段，子表对应分段的记录键值也有这个特性，所以不会发生错位情况；而同样因为键值有序，才可以在子表中执行高效的二分查找迅速定位出分段点。即数据有序保证了分段的合理性及高效性，这样就可以放心地执行并行算法了。
• 主子表这种主键关联的关系还有一个特征，就是子表只会和一个主表在主键上关联（其实同维表也有，但用主子表容易解释），它不会有多个相互无关的主表（可能有主表的主表）。这时候，还可以使用一体化存储的机制，把子表记录作为主表的字段值去存储。这样，一方面减少了存储量（关联键只要存储一次），又相当于预先做好了关联，不需要再做比对了。对于大数据，就能获得更好的性能。
• 我们已经将上述这些性能优化手段在集算器SPL中实现并在实际场景用得到了应用，也取得了非常好的效果。SPL目前已经开源，读者可以去数速公司或润乾公司官网及论坛下载并获得更多资料。

推荐学习：mysql视频教程

以上是Mysql体系化解析之JOIN运算的详细内容。更多信息请关注PHP中文网其他相关文章！