连接运算 6- 外键预关联

七、进一步的外键关联

我们继续讨论外键 JOIN，并延用上一篇的例子。

当数据量大到无法全部放进内存时，前述的地址化方法就不再有效了，因为在外存无法保存事先算好的地址。

一般来讲，外键指向的维表容量较小，而不断增长的事实表要大得多。如果内存还能把维表放下的话，我们可以采用临时指向的方法来处理外键。

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

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

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

维表主键是序号时就不需要再做原来建 HASH 索引的第 2 步了。

外键序号化本质上相当于在外存实现地址化。这种方案需要把事实表中的外键字段转换成序号，这类似在全内存运算时地址化的过程，这个预计算也可以得到复用。需要注意的是，维表发生重大变化时，需要同步整理事实表的外键字段，否则可能对应错位。不过一般维表变化频度低，而且大多数动作是追加和修改而非删除，需要重整事实表的情况并不多。工程上的细节处理也可以再参考乾学院中的资料。

SQL 使用了无序集合的概念，即使我们事先把外键序号化了，数据库也无法利用这个特点，不能在无序集合上使用序号快速定位的机制，只能使用索引查找，而且数据库并不知道外键被序号化了，仍然会去计算 HASH 值和比对。

如果维表也大到内存装不下呢？

我们仔细分析上面的算法会发现，过程中对于事实表的访问是连续的，但对于维表的访问则是随机的。我们以前讨论硬盘的性能特征时谈到过，外存不适合随机访问，所以外存中的维表不能再使用上述算法了。

外存中的维表可以事先按主键排序存储，这样我们就可以继续利用维表关联键是主键的特征来优化性能。

如果事实表很小，可以在内存装放下，那么用外键去关联维表记录实际上会变成一个（批量）外存查找动作。只要维表上针对主键建有索引，也可以很快地查找，这样可以避免遍历大维表，获得更好的性能。这种算法也可以同时解析多个外键。SQL 不区分维表和事实表，面对一大一小两个表时，优化过的 HASH JOIN 不会再做分堆缓存，通常会把小表读入内存而去遍历大表，这样仍然会有遍历大维表的动作，性能会比刚才说的外存查找算法差得多。

如果事实表也很大，则可以使用单边分堆的算法。因为维表已经按关联键（即主键）有序，可以方便地逻辑上分成若干段并取出每一段的边界值（每一段主键的最大最小值），然后将事实表按这些边界值做分堆，每一堆分别和维表的每一段再做关联就可以了。过程中只需要对事实表单边做物理分堆缓存，维表不需要再做物理分堆缓存，而且不使用 HASH 函数，直接用分段，不可能会出现 HASH 函数运气不好导致二次分堆，性能是可控的。而数据库的 HASH 分堆算法会将两个大表都做物理分堆缓存，也就是双边分堆，还可能出现 HASH 函数运气不好导致二次分堆的现象，性能要比单边分堆差得多，还不可控。

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

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

这些算法的细节仍有些复杂，这里限于篇幅无法详细解释，有兴趣的读者可以去乾学院的资料查阅。

连接运算 8- 有序归并