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

蒋步星《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)

计算销售额

42 34978 42 14988 0 0 3671 0 0:00:09 0:00:04 0:00:05 3671tion>

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

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

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

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

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

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

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

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

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

  正文结束  

 课程视频（可点击底部阅读原文观看）

https://edu.hellobi.com/course/197/lessons  （主题二）

 近期文章

    关于数据蒋堂    

《数据蒋堂》的作者蒋步星，从事信息系统建设和数据处理长达20多年的时间。他丰富的工程经验与深厚的理论功底相互融合、创新思想与传统观念的相互碰撞，虚拟与现实的相互交织，产生出了一篇篇的沥血之作。此连载的内容涉及从数据呈现、采集到加工计算再到存储以及挖掘等各个方面。大可观数据世界之远景、小可看技术疑难之细节。针对数据领域一些技术难点，站在研发人员的角度从浅入深，进行全方位、360度无死角深度剖析；对于一些业内观点，站在技术人员角度阐述自己的思考和理解。蒋步星还会对大数据的发展，站在业内专家角度给予预测和推断。静下心来认真研读你会发现，《数据蒋堂》的文章，有的会让用户避免重复前人走过的弯路，有的会让攻城狮面对扎心的难题茅塞顿开，有的会为初入行业的读者提供一把开启数据世界的钥匙，有的甚至会让业内专家大跌眼镜，产生思想交锋。

蒋步星，清华大学计算机硕士，著有《非线性报表模型原理》等

1989年中国国际奥林匹克数学竞赛团体冠军成员，个人金牌。

2000年创立润乾公司，首次在润乾报表中提出非线性报表模型，完美解决了中国式复杂报表制表难题，目前该模型已经成为报表行业的标准。

2008年开始研发不依赖关系型数据的计算引擎，历经多个版本后，于2014年集算器正式发布。有效地提高了复杂结构化大数据计算的开发速度和运算效率。

2016年荣获中国电子信息产业发展研究院评选的“2016年中国软件和信息服务业 • 十大领军人物”。

2017年创办数据领域技术讲堂《数据蒋堂》，专注数据、每周一期。

2017年获得中国大数据产业生态大会评选的“2017年度中国数据大工匠”