遍历复用

减少外存(硬盘)访问量一直是提高大数据计算性能的永恒话题,我们也讨论过列存、压缩等直接减少访问量甚至存储量的手段。除了这些存储层面的方法外,在算法和计算实现环节,也可以想办法减少外存的访问量。
遍历是大数据计算中必不可少的环节。有时候,我们会发现在一个计算任务中,会有两次(或更多)涉及针对同一批数据的遍历动作。如果我们能有办法让两次遍历合并成一次,那么总的计算量(CPU 的动作)并没有差别,但硬盘的访问量会减少了一半,这样计算性能还是能得到提升,对于数据密集型计算的提升效果还相当明显。

设有简化的帐目表 T 的数据结构中如下字段:账号 A、日期 D、发生地 P,金额 M
现在我们想统计账号 a1 和 a2 的余额,用 SQL 写出来是这样:

SELECT SUM(M) FROM T WHERE A=a1
SELECT SUM(M) FROM T WHERE A=a2

这样两句计算就会导致遍历两次表 T,如果表 T 非常大,计算效率就很低了。
如果我们把这句 SQL 写成这样:

SELECT SUM(CASE WHEN A=a1 THEN M ELSE 0 END),
       SUM(CASE WHEN A=a2 THEN M ELSE 0 END)
FROM T

一个语句把这两个统计值都计算出来,句子复杂了不少,数据库的总计算量也反而略有变大(判断次数相同,累计次数变多,要多加很多次 0),但是表 T 却只要遍历一次就可以了,最后获得的运算效率却要高很多。
作为数据库程序员,要学会这种技巧。

不过,并不是所有运算都可以用 CASE WHEN 来对付。
我们想分别统计每天的金额合计和每个发生地的金额合计,写出 SQL 是:

SELECT D,SUM(M) FROM T GROUP BY D
SELECT P,SUM(M) FROM T GROUP BY P

不同的 WHERE 还可以用 CASE WHEN 去绕,但不同的 GROUP BY 就无法再合并起来了,只能遍历两次表 T。
理论上,SQL 也可以遍历一次,写成

SELECT D,P,SUM(M) FROM T GROUP BY D,P

然后再自己编程针对这个中间结果计算 GROUP BY D 和 GROUP BY P 的运算。但实现起来实在是太麻烦了,而且这只是两个字段分组,如果多几个,中间结果集可能会大到内存装不下,反而会慢很多

SQL 的体系下解决不了这个问题了,我们需要设计新的概念和语法来实现可以复用的遍历运算。
SPL 的游标中引入管道的概念。游标遍历数据实施某个运算的同时,将数据压入到一个管道中,而管道上可以再定义另一个运算,这样,数据在一次遍历时可以同时获得游标本身以及附加的管道上的两个运算结果。上面的的运算写出来的大体代码结构如下:

cs = T.cursor(...)
ch = channel(cs).groups( P; sum(M) )
dg = cs.groups( D; sum(M) )
pg = ch.result()

channel(cs) 在游标 cs 上绑定一个管道 ch,并且定义一个针对 P 的分组运算,然后游标 cs 照常遍历并实施针对 D 的分组运算,遍历完毕后,从管道 ch 中取了相关结果就可以了。

前面那个不同条件汇总的问题当然也可以用游标和管道机制写出来

cs = T.cursor()
ch = channel(cs).select( A==a2 ).sum(M))
m1 = cs.select( A==a1 ).sum(M)
m2 = ch.result()

代码结构都是一样的。

当然,一个游标上还可以附加多个管道,比如刚才这两件事(条件汇总和不同分组)也可以一次遍历做完:

cs = T.cursor()
ch1 = channel(cs).select( A==a2 ).sum(M))
ch2 = channel(cs).groups( P; sum(M) )
ch3 = channel(cs).groups( D; sum(M) )
m1 = cs.select( A==a1 ).sum(M)
m2 = ch1.result()
dg = ch2.result
pg = ch3.result()

再举一个计算中位数的例子。
计算中位数时需要排序,但一般情况下排序运算只管排序本身,并不管计数,排序完成了甚至还不知道总共有多少数据, 这时候要找中位数,就还得再做一次 COUNT 遍历数据,浪费时间。如果有管道机制,我们就可以在排序的同时把计数也做完了。

cs = T.cursor()
ch = channel(cs).count()
s = cs.sortx(M)					//遍历排序过程中把管道上的计数也完成
k = ch.result()
m = s.skip( (k-1)\2 ).fetch@x(2-k%2).avg(M)	//找出中间一个或两个数