SQL 提速:组内最早的 N 个事件统计

【摘要】

从原理上分析 SQL 语句慢的原因,用代码示例给出提速办法。点击了解SQL 提速:组内最早的 N 个事件统计

问题描述

组内最早的 N 个事件统计属于分组时序计算,要统计的数据中一般都有分组字段、事件的时间字段及其它信息。例如:用户行为分析的分组字段是用户 ID,事件有类型属性(如页面浏览、加购物车等),要统计最早 N 个事件中各个类型的数量,再找出所有用户发生次数最多的那些事件类型。这种问题中要计算的数据总量通常都很大,需要外存;每组(用户)数据量不大,可以装入内存。

假设 T 表中包含分组字段 gid、事件类型字段 event 和时间字段 etime,每个 gid 对应多个事件。计算的需求是:对 T 表中满足某种条件(这个条件会随着具体的场景发生变化,也可能包含传入的参数变量)的记录,按 gid 分组,找出发生事件不少于 N 的组。然后,将这些事件类型按发生次序分组统计数量。N 一般不大,结果集也不会太大。

 

以 N=5 为例,SQL 写法样例如下:

with t1 as (select gid,

             MAX(CASE WHEN event_number = 1 THEN event ELSE NULL END) AS e1,

             MAX(CASE WHEN event_number = 2 THEN event ELSE NULL END) AS e2,

             MAX(CASE WHEN event_number = 3 THEN event ELSE NULL END) AS e3,

             MAX(CASE WHEN event_number = 4 THEN event ELSE NULL END) AS e4,

             MAX(CASE WHEN event_number = 5 THEN event ELSE NULL END) AS e5

                      from (select gid,event,

                           ROW_NUMBER()over (PARTITION BY gid ORDER BY etime ASC) AS event_number

                           from T

                           where …)

                      where event_number <=5

                      group by gid

                      )

select t1.e1,t1.e2,t1.e3,t1.e4,t1.e5,count(*) as c

from t1

where t1.e2 IS NOT NULL AND t1.e3 IS NOT NULL AND t1.e4 IS NOT NULL AND t1.e5 IS NOT NULL

group by 1,2,3,4,5

 

数据库要先执行最内层的子查询,先用一定的条件过滤出 T 表的部分数据,再用窗口函数按 gid 分组,组内对时间排序计算序号。在中间层子查询 t1 中,按照 gid 分组聚合,将序号为 1 到 5 的事件类型转换为 5 个字段。在最外层查询中,过滤出后 4 个字段都不为空的记录,再按 5 个字段分组计数。一般来说,T 表过滤出来的数据按 gid 分组结果集会很大,而大分组需要外存缓存,计算的性能会比较差。

提速方案

一、预先排序,有序计算

在数据准备阶段,我们要预先将原数据按照分组字段有序存放。计算时,遍历符合条件的有序数据,依次把每组数据读入内存。如果当前组长度小于 N 则舍弃,读入下一组。如果不小于 N,则组内数据按照时间排序后,用前 N 条记录的事件类型做分组汇总。这样做,对数据遍历一次即可,不用大分组,性能提升会很明显。

我们还可以预先按照分组字段和时间字段都有序存放,计算时不必每组再排序,对性能提升的作用相对较小,但可以简化代码。

事实上,很多组内时序计算的分组字段都是确定的(比如用户号、帐号),不会是随意选择的字段。只要按照这些确定的字段做一种排序,就能适用于很多组内时序计算了。其他组内时序计算只是组内的具体算法不一样,我们将另外介绍。

预先排序虽然慢,但是一次性的,而且只需要保持一种存储即可,没有冗余。

SQL 基于无序集合,不能严格保证每组数据连续存放,所以不能直接应用有序算法。而且,因为 SQL 的代码书写顺序和执行顺序并不一致,所以编写和阅读都不是很容易。如果能做到书写顺序就是执行顺序,代码将会大大的简化,也有利于发现性能瓶颈,提升计算速度。

二、新增数据

新增数据并不总是按分组字段继续有序,所以不能简单的追加到有序数据的末尾。而直接将有序数据和新增数据一起重新做常规大排序,会非常耗时。

我们可以将新增数据排序后,和原有序数据一起,用低成本的有序归并算法生成新的有序数据。这样整体复杂度相当于把所有数据读写一遍,可以避免常规大排序中产生很多临时外存缓存的现象,从而获得更好的性能。

更进一步,可以另外保持一个小规模的有序数据 (以下称为补数据)。新增数据排序后和补数据归并,原有序数据不变。经过适当的时间后,补数据积累到合适大小时,再和原有序数据归并。做组内时间有序计算时,从有序数据和补数据中分别读取,归并后再计算,性能会比只有一份有序数据时下降一些,但仍能利用有序实现快速时序计算。

这个适当时间的确定,与新增数据的周期有关。比如每天都有新增数据,则每个月做一次原有序数据和补数据的归并。补数据不会超过一个月的数据量,原有序数据存储一个月之前的所有数据。也就是说补数据可能会比原有序数据小很多,所以每天归并的数据量相对较小,很快就能完成数据追加。每个月才需要完成一次全量有序归并,耗时长一些也可以接受了。

 

代码示例

一,数据按照分组字段有序,时间字段无序时,组内最早的 5 个事件类型计数。


A

1

=file("T.ctx").open().cursor(gid,etime,event;…)

2

=A1.group(gid).select(~.len()>=5).(~.sort(etime))

3

=A2.groups(~(1).event:e1,~(2).event:e2,~(3).event:e3,~(4).event:e4,~(5).event:e5;count(1):c)

A1:打开组表 T.ctx,定义游标。分号后可以写 where 条件。

A2:先对游标定义 gid 有序分组计算。再定义过滤、排序计算,去掉长度小于 5 的分组,每组内按照 etime 排序。这里只是定义了游标上的计算,并没有真正开始遍历。

A3:遍历游标,依次对每个 gid 分组执行 A2 中定义的计算,再按照每组前 5 条记录的 event 分组聚合(计数)。因为结果集不会太大,所以采用 groups 小结果集分组。

 

二,数据按照分组、时间字段都有序时,组内最早的 5 个事件类型计数。


A

1

=file("T.ctx").open().cursor(gid,etime,event;…)

2

=A1.group(gid).select(~.len()>=5)

3

=A2.groups(~(1).event:e1,~(2).event:e2,~(3).event:e3,~(4).event:e4,~(5).event:e5;count(1):c)

和前面的代码比较,我们可以发现,如果预先按照分组、时间字段都有序,A2 可以省去 (~.sort(etime)),代码更简单。

 

三,数据预处理,有序存储。


A

1

=file("T-original.ctx")

2

=A1.open().cursor().sortx(gid,etime).new(gid,etime,…)

3

=file("T.ctx").create(#gid,#etime,…)

4

=A3.append@i(A2)

A1:转换前的原始组表 T-original.ctx。

A2:打开组表 T-original.ctx 建立游标,按照字段 gid,etime 排序,结果游标将字段 gid,etime 放在前面。如果仅按 gid 排序,sortx 写作 sortx(gid) 即可。

A3:新建组表 T.ctx,字段名前面加了 #,即表明该组表对 gid,etime 字段有序。如果仅按照 gid 排序,create 写作 create(#gid,etime,…) 即可。

A4:将排好序的数据输出到组表 T.ctx 中。

 

四,新增数据追加。

假设 T 表每天的新增数据存储在 T_new.btx 中,且字段名称、顺序与 T.ctx 相同。


A

B

1

=file("T.ctx").open()


2

=file("T_new.btx").cursor@b().sortx(gid,etime)

3

if   (day(now())==1)

>A1.reset()

4

>A1.append@a(A2)


A1:打开组表 T.ctx。

A2:定义 T_new.btx 的游标并排序,通常每天新增数据量不大,这里虽然用 sortx,但实际上经常会是内存排序,速度很快。如果仅对 gid 有序,去掉 sortx 中的 etime 就可以了。

A3:判断日期是否为 1 号,如果不是则执行 A4,用 append@a 只在补数据上归并。如果是 1 号,那么就执行 B3,用 reset 把原有序数据和补数据有序归并成新的有序数据。

 

 


以下是广告时间

对润乾产品感兴趣的小伙伴,一定要知道软件还能这样卖哟性价比还不过瘾? 欢迎加入好多乾计划。
这里可以低价购买软件产品,让已经亲民的价格更加便宜!
这里可以销售产品获取佣金,赚满钱包成为土豪不再是梦!
这里还可以推荐分享抢红包,每次都是好几块钱的巨款哟!
来吧,现在就加入,拿起手机扫码,开始乾包之旅



嗯,还不太了解好多乾?
猛戳这里
玩转好多乾