遍历复用

发布时间：2018-07-17 分类：数据蒋堂 Tag：遍历

sjjt-217

减少外存（硬盘）访问量一直是提高大数据计算性能的永恒话题，我们也讨论过列存、压缩等直接减少访问量甚至存储量的手段。除了这些存储层面的方法外，在算法和计算实现环节，也可以想办法减少外存的访问量。

遍历是大数据计算中必不可少的环节。有时候，我们会发现在一个计算任务中，会有两次（或更多）涉及针对同一批数据的遍历动作。如果我们能有办法让两次遍历合并成一次，那么总的计算量（CPUT的动作）并没有差别，但硬盘的访问量会减少了一半，这样计算性能还是能得到提升，对于数据密集型计算的提升效果还相当明显。

设有简化的帐目表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

SQL没有直接提供遍历复用的语法，不同的WHERE还可以用CASE WHEN去绕，但不同的GROUP BY就无法再合并起来了，只能遍历两次表T。

理论上，使用数据库游标可以做到这一点，定义一个基于SELECT D,P,M FROM T的游标，一行行取数，然后分别针对D和P去做GROUP BY运算。这个运算用SQL写起来实在太麻烦了，而且游标遍历的性能很差，结果不仅繁琐而且更慢了。

SQL的体系下解决不了这个问题了，我们需要设计新的概念和语法来实现遍历复用。

在游标机制中引入管道的概念。游标遍历数据实施某个运算的同时，将数据压入到一个管道中，而管道上可以再定义另一个运算，这样，数据在一次遍历时可以同时获得游标本身以及附加的管道上的两个运算结果。上面的的运算写出来的大体代码结构如下：

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遍历数据，浪费时间。如果有管道机制，我们就可以在排序的同时把计数也做完了。