【摘要】

问题描述

组内最早的 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 个事件类型计数。

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

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

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

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

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

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

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 相同。

A1：打开组表 T.ctx。

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

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