数据蒋堂 | 前半有序的大数据排序

作者：蒋步星

来源：数据蒋堂

本文共1800字，建议阅读8分钟。
我们不能解决通用的大排序问题，但在特定场合下却能设计出好算法提高性能。

最近碰到这么一个案例，情况可以简化总结成这样：数据库中有表T，其中有两个重要的字段a和b，a是一个时间戳，精确到秒；b是用户号；其它字段用来表示用户b在时刻a发生的事件属性。

现在任务是：把数据按a,b排序导出。简单来讲，就是把SELECT * FROM T ORDER BY a,b的结果集写出到文件。

但是，这个T表有几十亿条记录，这个SQL发出去之后，数据库就象死了一样，一个多小时都没有任何反应。

这也难怪，几十亿记录的大排序确实非常慢，上T的数据量内存装不下，而外存排序需要分段读入数据，在内存将每段排序后再缓存到硬盘，然后将这些缓存数据一起再归并。这样，必须把所有数据都遍历过一遍且分段排序后才能开始输出。

---

还有什么别的办法么？

通用的大排序可以说已经被全世界研究到极致了，再想出一个更优的办法几乎没有可能性了。但是，如果我们能找到这些数据的一些可得特征，说不定就能有办法了。

了解到一些业务信息后，我们发现这批数据有这样一些特征：

• 数据是按发生时刻（也就是a）为次序插入的，这样物理存储次序也就会接近于按a有序，而且数据库已经为字段a建好了索引；

• 从某个起始时刻到终止时刻，几乎每一秒都会有数据插入；

• 数据按时间分布比较平均，大概每秒数万条，没有某一秒的数据量特别多；

利用这些特征，我们可以设计这样的算法（用SPL写成），其中start,end分别是数据的起止时刻。

	A	B
1	for interval@s(start,end)+1	=elapse@s(start,A1-1)
2		=db.query(“SELECT * FROM T WHERE a=?”,B1)
3		=B2.sort(b)
4		>outputfile.export@a(B3)

基本逻辑是：循环所有的秒，从数据库取出某一秒的记录按b排序后再写出到文件。因为数据库为a建有索引，而数据也接近于按a有序存储，用索引取数就非常快。每一秒内的数据量并不大，可以在内存中排序，速度很快。容易证明这个算法返回的结果集就是按a,b有序的，这样就不需要缓存数据就可以完成这个大排序了。

这个算法执行后立即就有数据开始输出，数小时内就完成了按序导出数据的任务，之所以需要数小时，主要还是从数据库中取数以及写入文件的时间（几十亿行和上T的数据量），排序本身几乎没有占用时间。

---

针对这批数据，我们还有一个任务：想知道字段a,b是否可以用作T的主键，也就是说字段a,b的取值在T表是否是唯一的。

本来用SQL做这个判断也很简单，只要看看：

SELECT COUNT(*) FROM T

和

SELECT COUNT(*) FROM (SELECT a,b FROM T GROUP BY a,b)

是否相等就可以了（有些数据库不支持COUNT(DISTINCT a,b)写法，这里写成子查询形式）。

COUNT(*)容易算，但面对数十亿行的大数据做GROUP BY运算，其方法和外存排序是差不多的，成本也差不多，也是跑了一个多小时没动静。

但是，如果我们利用上述特征，就很容易计算出这个值：

	A	B
1	for interval@s(start,end)+1	=elapse@s(start,A1-1)
2		=db.query@1(“SELECT COUNT(DISTINCT b) FROM T WHERE a=?”,B1)
3		=@+B2

类似地，循环每一秒，针对每一条记录一个COUNT(DISTINCT B)，然后都加起来就是我们要的答案了（容易证明这个算法的正确性）。这段代码几分钟就完成了运算（和上例相比，这里不导出也就不需要取出明细数据了，也不必写文件，而且还能并行计算，不象上例中要有序写出就只能串行）。

---

细心的读者可能要问，这两个例子都是讲如何利用索引来快速计算，为什么本文标题要叫“前半有序”呢？

实际上我们就是利用了这批数据已经有的次序信息。这两个问题的关键点都是需要按a,b排序，而在索引的作用下，这批数据看起来已经对a有序了，也就是待排序字段中的前一部分字段已有序了。而如果前面字段相同时的记录数都没有大到内存放不下的地步，那么就可以不使用缓存实现大排序了。

如果数据已经存储在可以保持次序的文件中，则这个方法的适应面会更宽泛一些，不需要事先知道a的起止时刻并循环每一秒，代码也会更简单些。

假如数据文件T中按a的次序写入了T表的记录，则上面的两个问题的算法可以分别写出来是这样：

	A	B
1	for file(T).cursor();a	=A1.sort(b)
2		>outputfile.export@a(B1

	A	B
1	for file(T).cursor();a	=@+A1.id(b).len()

SPL中提供了针对游标的有序取出方法，上面两段代码中A1格的意思是针对文件T的数据游标循环，每次读到字段a的值发生变化时则进入循环体，然后再读下一批a相同的记录，...。

基于文件的运算比上述使用索引从数据库取数的效果又好了数倍。而且这几段代码对内存占用也非常少。本来大排序是个很耗用内存的动作，因为后一步归并的性能严重依赖于分段的数量，要减少分段，就要让每一段尽量大，所以内存越大的性能就越好。而利用前半有序的特征后，只要一点点内存（本例中只要能装入数万行记录）就可以高速完成运算了。

---

最后再温习一下我们的观点：性能优化要因地制宜，根据数据和运算的特征想办法。

我们不能解决通用的大排序问题，但在特定场合下却能设计出好算法提高性能。而数据库过于透明，看起来程序员不用操心了，但数据库并没有那么智能，经常不会利用数据特征来自动优化。而且，在SQL体系下，即使人为想出好算法，也几乎无法实现。

专栏作者简介

润乾软件创始人、首席科学家

清华大学计算机硕士，中国大数据产业生态联盟专家委员，著有《非线性报表模型原理》等，1989年，中国首个国际奥林匹克数学竞赛团体冠军成员，个人金牌；2000年，创立润乾公司；2004年，首次在润乾报表中提出非线性报表模型，完美解决了中国式复杂报表制表难题，目前该模型已经成为报表行业的标准；2014年，经过7年开发，润乾软件发布不依赖关系代数模型的计算引擎——集算器，有效地提高了复杂结构化大数据计算的开发和运算效率；2015年，润乾软件被福布斯中文网站评为“2015福布斯中国非上市潜力企业100强”；2016、2017年，荣获中国电子信息产业发展研究院评选的“中国软件和信息服务业十大领军人物”；2017年度中国数据大工匠、数据领域专业技术讲堂《数据蒋堂》创办者。

数据蒋堂

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

数据蒋堂第二年往期回顾：

数据蒋堂 | 存储和计算技术的选择

数据蒋堂 | 人工智能中的“人工”

数据蒋堂 | 中国报表漫谈

数据蒋堂 | 内存数据集产生的隐性成本

数据蒋堂 | 多维分析预汇总的功能盲区

数据蒋堂 | 多维分析预汇总的存储容量

数据蒋堂 | 多维分析预汇总的方案探讨

数据蒋堂 | 数据库的封闭性

数据蒋堂 | 内存数据集产生的隐性成本