前半有序的排序及有序游标

碰到过这么一个案例，情况可以简化总结成这样：数据库中有表 T，其中有两个重要的字段 a 和 b，a 是一个时间戳，精确到秒；b 是用户号；其它字段用来表示用户 b 在时刻 a 发生的事件属性。
现在任务是：把数据按 a,b 排序导出。简单来讲，就是把 SELECT * FROM T ORDER BY a,b 的结果集写出到文件。
但是，这个 T 表有几百亿条记录，这个 SQL 发出去之后，数据库就象死了一样，一个多小时都没有任何反应。
这也难怪，这个任务需要先把数据做完排序才能输出，而几百亿记录的大排序非常慢，内存装不下时会涉及复杂的内外存倒换，数据要遍历三次（读两次写一次），一个小时时间不可能完成排序，

还有什么别的办法么？
通用的大排序可以说已经被全世界研究到极致了，再想出一个更优的办法几乎没有可能性了。但是，如果我们能找到这些数据的一些特征，说不定就能有办法了。
了解到一些业务信息后，我们发现这批数据有这样一些特征：
1. 数据是按发生时刻（也就是 a）为次序插入的，这样物理存储次序也就会接近于按 a 有序，而且数据库已经为字段 a 建好了索引；
2. 从起始时刻到终止时刻，几乎每一秒都会有数据插入；
3. 数据按时间分布比较平均，大概每秒数万条，没有某一秒的数据量特别多；
利用这些特征，我们可以设计这样的算法（用 SPL 写成），其中 start,end 分别是数据的起止时刻。

基本逻辑是：循环所有的秒，从数据库取出某一秒的记录按 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 运算，其方法和外存排序是差不多的，成本也差不多，也是跑了一个多小时没动静。
如果我们利用上述特征，就很容易计算出这个值：

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

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

如果数据已经存储在可以保持次序的文件中，则这个方法的适应面会更宽泛一些，不需要事先知道 a 的起止时刻并循环每一秒，代码也会更简单些。
假如数据文件 T 中按 a 的次序写入了 T 表的记录，则上面的两个问题的算法可以分别写出来是这样：

SPL 中提供了针对游标的有序取出方法，这两段代码中 A1 格的意思是针对文件 T 的数据游标循环，每次读到字段 a 的值发生变化时则进入循环体，然后再读下一批 a 相同的记录，…。
基于文件的运算比上述使用索引从数据库取数的效果又好了数倍。而且这几段代码对内存占用也非常少。本来大排序是个很耗用内存的动作，因为要让归并分段数尽量少，就要让每一段尽量大，所以内存越大的性能就越好。而利用前半有序的特征后，只要一点点内存（本例中只要能装入数万行记录）就可以高速完成运算了。

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

开源SPL源码地址

免费下载试用