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 A2f02b88b6995ef5293e99827ac11a920A1.keys@i(key) 3 =file(“orders.btx”).import@b() 4 >A3.switch(custkey,A1) 5 =A3.groups(custkey.city;sum(amount))
  • 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	=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中文网其他相关文章！