【数据蒋堂】第34期：JOIN提速 – 外键指针的衍生

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

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

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

1. P=file("products.txt").import()                读入商品信息表P
2. P.index(id)                                                  为P的主键id建立索引方便查找
3. S=file("sales.txt").cursor()                       建立商品销售记录的游标S，逐步读入数据
4. S.switch(productid,P:id)                           在流入数据时将S中的productid字段根据P的主键转换成P的记录
5. S.sum(quantity*productid.price)            计算销售额

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

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

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

1. P=file("products.txt").import()            读入商品信息表P，其主键id都是序号
2. S=file("sales.txt").cursor()                   建立商品销售记录的游标S，逐步读入数据
3. S.switch(productid,P:#)                        在流入数据时将S中的productid字段转换成P中相应序号的记录
4. S.sum(quantity*productid.price)        计算销售额

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

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

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

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

我们仔细分析上面的算法会发现，过程中对于事实表的访问是连续的，但对于维表的访问是随机的。我们以前讨论硬盘的性能特征时谈到过，外存不适合随机访问。如果把维表放在外存中再执行上面的算法，那性能会差到远不如HASH分段算法的地步，甚至赶不上把两个表排序后再做归并的性能。

这时候我们要借助集群的力量了。

一台机器的内存装不下，可以多搞几台机器来装下，把维表分段放在多台机器上形成集群维表，然后就可以继续使用上面的算法并获得一次解析多个外键和易于并行的好处。同样地，集群维表h 也可以使用序号化的技术。

需要注意的是，内存不仅适合随机访问，还适合小量频繁访问。而集群维表虽然是内存存储的，但中间多了网络传输，而网络却不适合小量频繁访问。这时，在遍历事实表时就不能象单机时那样每次只处理一条记录，而需要批量读取一批记录，把它们需要JOIN的键值聚集起来再发送到目标集群节点去获取维表的相关字段。

保证维表的内存化是提高性能的关键因素。对于现代计算机的内存容量而言，大部分维表在单台机器的内存都可以放下，少量巨大维表则采用集群维表来处理，这样可以确保对维表的高性能随机访问。如果真地出现连集群也装不下的维表，那可能还是只能回到低效的HASH分段算法了。