共计 4778 个字符，预计需要花费 12 分钟才能阅读完成。
JOIN 始终是数据库性能优化的老大难问题，原本挺快的查问，一旦波及了几个 JOIN，性能就会陡降。而且，参加 JOIN 地表越大越多，性能就越难提上来。
其实，让 JOIN 跑得快的要害是要对 JOIN 分类，分类之后，就能利用各种类型 JOIN 的特色来做性能优化了。
JOIN 分类
有 SQL 开发教训的同学都晓得，绝大多数 JOIN 都是等值 JOIN，也就是关联条件为等式的 JOIN。非等值 JOIN 要少见得多，而且少数状况也能够转换成等值 JOIN 来解决，所以咱们能够只探讨等值 JOIN。
等值 JOIN 次要又能够分为两大类：外键关联和主键关联。
外键关联是指用一个表的非主键字段，去关联另一个表的主键，前者称为事实表，后者为维表。比方下图中，订单表是事实表，客户表、产品表、雇员表是维持表。
外键表是多对一关系，而且是不对称的，事实表和维持表的地位不能调换。须要阐明的是，这里说的主键是指逻辑上的主键，也就是在表中取值惟一、能够用于惟一确定某条记录的字段（或字段组），不肯定在数据库表上建设过主键。
主键关联是指用一个表的主键关联另一个表的主键或局部主键。比方下图中的客户和 VIP 客户、订单表和订单明细表的关联。
客户和 VIP 客户依照主键关联，这两个表互为同维表。订单则是用主键去关联明细的局部主键，咱们称订单表是主表，明细表是子表。
同维表是一对一关系。且同维表之间是对称的，两个表的位置雷同。奴才表则是一对多关系，而且是不对称的，有明确的方向。
仔细观察会发现，这两类人 JOIN 都波及到主键了。而不波及主键的 JOIN 会导致多对多关系，大多数状况都没有业务意义。换句话说，上述这两大类 JOIN 涵盖了简直全副有业务意义的 JOIN。如果咱们能利用 JOIN 总会波及主键这个特色做性能优化，能解决掉这两大类 JOIN，其实也就意味着解决了大部分 JOIN 性能问题。
然而，SQL 对 JOIN 的定义并不波及主键，只是两个表做笛卡尔积分后再按某种条件过滤。这个定义很简略也很宽泛，简直能够形容所有。然而，如果严格按这个定义去实现 JOIN，也就没方法在性能优化时利用主键的特色了。
SPL 扭转了 JOIN 的定义，专门针对这两大类 JOIN 别离解决，利用了主键的特色缩小运算量，从而实现性能优化的指标。
上面咱们来看看 SPL 具体是怎么做的。
外键关联
如果事实表和维表都不太大，能够全副装入内存，SPL 提供了外键地址化办法：先把事实表中的外键字段值转换为对应维表记录的地址，之后援用维表字段时，就能够用地址间接取出了。
以后面的订单表、雇员表为例，假设这两个表曾经被读入内存。外键地址化的工作机制是这样的：对于订单表某记录 r 的 eid 字段，到雇员表中找到这个 eid 字段值对应的记录，失去其内存地址 a，再将 r 的 eid 字段值替换成 a。对订单表的所有记录都做好这样的转换，就实现了外键地址化。这时候，订单表记录 r 要援用雇员表字段时，间接用 eid 字段存储的地址 a 取出雇员表记录和字段就能够了，相当于常数工夫内就能获得雇员表的字段，不须要再到雇员表做查找。
能够在系统启动时把事实表和维表读入内存，并一次性做好外键地址化，即预关联。这样，在后续关联计算时就能间接用事实表外键字段中的地址去取代表记录，实现高性能的 JOIN 计算。
外键地址化和预关联的具体原理请参考：【性能优化】6.1 [内政关联] 外键地址化
SQL 通常应用 HASH 算法来做内存连贯，须要计算机 HASH 值和比对，性能会比间接用地址读取差很多。
SPL 之所以能实现外键地址化，是利用了维表的关联字段是主键这一特色。下面例子中，关联字段 eid 是雇员表的主键，具备唯一性。订单表中的每个 eid 只会惟一对应一条雇员记录，所以能力把每个 eid 转换成它惟一对应的那条雇员记录的地址。
而 SQL 对 JOIN 的定义中没有主键的约定，就不能认定与事实表中关联的维表记录有唯一性，有可能产生与多条记录关联的状况。对于订单表的记录来讲，eid 值没有方法惟一对应一条雇员记录，就无奈做到外键地址化了。而且 SQL 也没有记录地址这种数据类型，后果会导致每次关联时还是要计算 HASH 值并比对。
只是两个表 JOIN 时，外键地址化和 HASH 关联的差异还不是非常明显。这是因为 JOIN 并不是最终目标，JOIN 之后还会有其它很多运算，JOIN 自身运算耗费的工夫的占比绝对不大。但事实表经常会有多个维表，甚至维表还会有很多层。比方订单关联产品，产品关联供应商，供应商关联城市，城市关联国家等等。在关联表很多时，外键地址化的性能劣势会更显著。
上面的测试，在关联表个数不同的状况下比照 SPL 与 Oracle 的性能差别，能够看出在表很多时，外键地址化的劣势相当显著：
测试的详细情况请参考：性能优化技巧：预关联。
对于只有维表能装入内存，而事实表很大须要外存的状况，SPL 提供了外键序号化办法：事后将事实表中的外键字段值转换为维表对应记录的序号。关联计算时，分批读入新事实表记录，再用序号取出对应维表记录。
以上述订单表、产品表为例，假设产品表曾经装入内存，订单表存储在外存中。外键序号化的过程是这样：先读入一批订单数据，设其中某记录 r 中的 pid 对应的是内存中产品表的第 i 条记录。咱们要将 r 中的 pid 字段值转换为 i。对这批订单记录都实现这样的转换后，再做关联计算时，从外存中分批读入订单数据。对于其中的记录 r，就能够间接依据 pid 值，去内存中的产品表里用地位取出相应的记录，也防止了查找动作。
外键序号化原理更具体的介绍参考：【性能优化】6.3 [外键关联] 外键序号化。
数据库通常会把小表读入内存，再分批读入大表数据，用哈希算法做内存连贯，须要计算哈希值和比对。而 SPL 应用序号定位是间接读取，不须要进行任何比对，性能劣势比拟显著。尽管事后把事实表的外键字段转换成序号须要肯定老本，但这个预计算只须要做一次，而且能够在屡次外键关联中失去复用。
SPL 外键序号化同样利用了维表关联字段是主键的特色。如前所述，SQL 对 JOIN 的定义没有主键的约定，无奈利用这一特色做到外键序号化。另外，SQL 应用无序汇合的概念，即便咱们当时把外键序号化了，数据库也无奈利用这个特点，不能在无序汇合上应用序号疾速定位的机制，最快也就是用索引查找。而且，数据库并不知道外键被序号化了，依然会去计算 HASH 值和比对。
上面这个测试，在不同并行数状况下，比照 SPL 和 Oracle 实现大事实表、小维表关联计算的速度，SPL 跑的比 Oracle 快 3 到 8 倍。测试后果见下图：
这个测试更具体的信息请参考：性能优化技巧：外键序号化。
如果维表很大也须要外存，而事实表较小能装入内存，SPL 则提供了大维表查找机制。如果维表和事实表都很大，SPL 则应用单边分堆算法。对于维表过滤后再关联的状况，SPL 提供了索引复用办法及对位序列等办法。
数据量大到须要分布式计算时，如果维表较小，SPL 采纳复写维表机制，将维表在集群节点上复制多份；如果维表很大，则采纳集群维表办法以保障随机拜访。这两种办法都能够无效的防止 Shuffle 动作。相比而言，SQL 体系下不能辨别出维表，HASH 拆分办法要将两个表都做 Shuffle 动作，网络传输量要大得多。
主键关联
主键关联波及的表个别都比拟大，须要存储在外存中。SPL 为此提供了有序归并办法：事后将外存表依照主键有序存储，关联时程序取出数据做归并计算。
以客户和 VIP 客户两个表做内连贯为例，假如曾经事后将两个表依照主键 cid 有序存储在外存中。关联时，从两个表的游标中读取记录，逐条比拟 cid 值。如果 cid 相等，则将两表的记录合并成后果游标的一条记录返回。如果不相等，则 cid 小的那个游标再读取记录，持续判断。反复这些动作直到任何一个表的数据被取完，返回的游标就是 JOIN 的后果。
对于两个大表关联，数据库通常应用哈希分堆算法，复杂度是乘法级的。而有序归并算法复杂度是加法级，性能会好很多。而且，数据库做大数据的外存运算时，哈希分堆会产生缓存文件的读写动作。有序归并算法则只须要对两个表顺次遍历，不用借助外存缓存，能够大幅升高 IO 量，有微小的性能劣势。
事后依照主键排序的老本虽高，然而一次性做好即可，当前就总能应用归并算法实现 JOIN，性能能够进步很多。同时，SPL 也提供了在有追加数据时依然保持数据整体有序的计划。
这类 JOIN 的特色在于关联字段是主键或局部主键，有序归并算法正是依据这个特色来设计的。因为不论是同维表还是奴才表，关联字段都不会是主键之外的其余字段，所以咱们将关联表依照主键有序这一种形式排序存储就能够了，不会呈现冗余。而外键关联就不具备这个特色，不能应用有序归并。具体来说，是因为事实表的关联字段不是主键，会存在多个要参加关联的外键字段，咱们不可能让同一个事实表同时按多个字段都有序。
SQL 对 JOIN 的定义不辨别 JOIN 类型，不假设某些 JOIN 总是针对主键的，就没方法从算法层面上利用主键关联的特色。而且，后面说过 SQL 基于无序汇合概念，数据库不会刻意保证数据的物理有序性，很难施行有序归并算法。
有序归并算法的劣势还在于易于分段并行。以订单和订单明细按 oid 关联为例，如果将两表都依照记录数大抵均匀分为 4 段，订单第 2 段的 oid 有可能会呈现在明细第 3 段，相似的错位会导致谬误的计算结果。SPL 再次利用主键 oid 的有序性，提供同步分段机制，解决了这个问题：先将有序的订单表分为 4 段，再找到每一段起止记录的 oid 值造成 4 个区间，将明细表也分成同步的 4 段。这样，在并行计算时两表对应分段就不会呈现错位了。因为明细表也对 oid 有序，能够迅速地依照起止 oid 定位，不会升高有序归并的性能。
有序归并和同步分段并行的原理，详见：SPL 有序归并关联。
传统的 HASH 分堆技术实现并行就比拟艰难了，多线程做 HASH 分堆时须要同时向某个分堆写出数据，造成共享资源抵触；而下一步实现某组分堆关联时又会生产大量内存，无奈施行较大的并行数量。
理论测试证实，在雷同状况下，咱们对两个大表做主键关联测试（详情参见性能优化技巧：有序归并），后果是 SPL 比 Oracle 快了近 3 倍：
除了有序归并，SPL 还提供了很多高性能算法，全面提高主键关联 JOIN 的计算速度。包含：附表机制，能够将多表一体化存储，缩小存储数据量的同时，还相当于事后实现了关联，不须要再比对了；关联定位算法，实现先过滤再关联，能够防止全表遍历，取得更好的性能等等。
当数据量持续减少，须要多台服务器集群时，SPL 提供复组表机制，将须要关联的大表依照主键散布到集群节点上。雷同主键的数据在同一节点，防止分机之间的数据传输，也不会呈现 Shuffle 动作。
回顾与总结
回顾下面两大类、各场景 JOIN，采纳 SPL 分状况提供的高性能算法，能够利用不同类型 JOIN 的特色提速，让 JOIN 跑得更快。SQL 对上述这么多种 JOIN 场景抽象的解决，就没方法针对不同 JOIN 的特色来施行这些高性能算法。比方：事实表和维表都装入内存时，SQL 只能依照键值计算 HASH 和比对，无奈利用地址间接对应；SQL 数据表无序，在大表依照主键关联时无奈做到有序归并，只能应用 HASH 分堆，有可能会呈现屡次缓存的景象，性能有肯定的不可控性。
并行计算方面，SQL 单表计算时还容易做到分段并行，多表关联运算时个别就只能当时做好固定分段，很难做到同步动静分段，这就难以依据机器的负载长期决定并行数量。
对于集群运算也是这样，SQL 在实践上不辨别维表和事实表，要实现大表 JOIN 就会不可避免地产生占用大量网络资源的 HASH Shuffle 动作，在集群节点数太多时，网络传输造成的提早会超过节点多带来的益处。
SPL 设计并利用了新的运算和存储模型，能够在原理和实现上解决 SQL 的这些问题。对于 JOIN 的不同分类和场景，程序员有针对性的采取上述高性能算法，就能取得更快的计算速度，让 JOIN 跑得更快。
