查看原文
其他

遍历复用

蒋步星 数据蒋堂 2023-02-25

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

遍历是大数据计算中必不可少的环节。有时候,我们会发现在一个计算任务中,会有两次(或更多)涉及针对同一批数据的遍历动作。如果我们能有办法让两次遍历合并成一次,那么总的计算量(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遍历数据,浪费时间。如果有管道机制,我们就可以在排序的同时把计数也做完了。

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)

//找出中间一个或两个数


《数据蒋堂》官方技术交流群

欢迎各路技术大咖入群,与作者交流

(该二维码七天后失效)


数据蒋堂 第二年原创文章

- 一些数据压缩手段

用HBase做高性能键值查询?

BI系统中容易被忽视的数据源功能

这个产品能支持多大数据量?

最简单的大数据性能估算方法

大清单报表应当怎么做?

大清单报表的打印?

大数据技术的4个E

做基础软件很悲壮?

做基础软件要投入很多钱?

- 国产操作系统还能怎么做?

- 国产数据库通通都没戏!

人工智能中的“人工”

- 存储和计算技术的选择

- 区块链技术的一些疑问

- 数据蒋堂新一年




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

中国大数据产业生态联盟 专家委员

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

清华大学计算机硕士

发明了非线性报表模型,并著《非线性报表模型原理》

创建离散数据集模型,颠覆四十年关系代数理论体系!

2016、2017年中国软件和信息服务业 • 十大领军人物

2017年度中国数据大工匠

数据领域专业技术讲堂《数据蒋堂》创办者


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存