SQL 提速：组内取时间最早的记录
【摘要】
从原理上分析 SQL 语句慢的原因，用代码示例给出提速办法。点击了解SQL 提速：组内取时间最早的记录
问题描述
组内取时间最早的记录属于分组时序计算。比如用户行为分析要取出每个用户 ID、会话编号下操作时间最早的记录。股票分析取出每个股票的第一个交易日记录。分组时序计算的总数据量通常都很大，需要外存；每组数据量都不太大，可以装入内存。
设 T 表中分组字段是 gid，时间字段是 time1。计算需求是：对 T 表中满足某种条件（这个条件会随着具体的场景发生变化，也可能包含传入的参数变量）的记录，按 gid 分组，找出每组时间最早的记录。
SQL1：不支持窗口函数的数据库写法
Select T1.gid,T1.time1,…,
not exist (select 1 from T T2
where T1.gid=T2.gid and T2.time1<T1.time1 and …) isFirst
where isFirst =true and …
数据库通常会把 EXISTS 转换成 JOIN，并不会全遍历，性能也不差。但 SQL1 这种条件是非等值比较的 EXISTS 则不能转换成 JOIN 了，数据库在遍历 T 表过滤出来的数据时，每一条记录都找一轮 gid 相同且时间更早的数据，性能较差。
SQL2：支持窗口函数的数据库写法
select * from
(select gid,time1,…
row_number()over (partition by gid order by time1 asc) rn
from T
where ...)
where rn=1
一般来说，T 表过滤出来的数据按 gid 分组结果集会很大，而大分组需要外存缓存，计算的性能会比较差。
提速方案
一、预先排序，有序计算
将原数据预先按照分组字段有序存放。计算时，遍历符合条件的有序数据，依次把每组数据读入内存，并取出时间字段最早的记录。这样做，不用每条记录都找一轮，也不用大分组，性能提升会很明显。
我们还可以预先按照分组字段和时间字段都有序存放，计算时不必每组再排序，对性能提升的作用相对较小，但可以简化代码。
事实上，很多组内时序计算的分组字段都是确定的（比如用户号、帐号），不会是随意选择的字段。只要按照这些确定的字段做一种排序，就能适用于很多组内时序计算了。其他组内时序计算只是组内的具体算法不一样，我们将另外介绍。
预先排序虽然慢，但是一次性的，而且只需要保持一种存储即可，没有冗余。
SQL 基于无序集合，不能严格保证每组数据连续存放，也无法保证每组记录按照时间顺序直接读出，所以不能直接应用有序算法，需要用额外的计算来保证取出的数据按照时间有序。
二、新增数据
新增数据并不总是按分组字段继续有序，所以不能简单的追加到有序数据的末尾。而直接将有序数据和新增数据一起重新做常规大排序，会非常耗时。
我们可以将新增数据排序后，和原有序数据一起，用低成本的有序归并算法生成新的有序数据。这样整体复杂度相当于把所有数据读写一遍，可以避免常规大排序中产生很多临时外存缓存的现象，从而获得更好的性能。
更进一步，可以另外保持一个小规模的有序数据 (以下称为补数据)。新增数据排序后和补数据归并，原有序数据不变。经过适当的时间后，补数据积累到合适大小时，再和原有序数据归并。做组内时序计算时，从有序数据和补数据中分别读取，归并后再计算，性能会比只有一份有序数据时下降一些，但仍能利用有序实现快速时序计算。
这个适当时间的确定，与新增数据的周期有关。比如每天都有新增数据，则每个月做一次原有序数据和补数据的归并。补数据不会超过一个月的数据量，原有序数据存储一个月之前的所有数据。也就是说补数据可能会比原有序数据小很多，所以每天归并的数据量相对较小，很快就能完成数据追加。每个月才需要完成一次全量有序归并，耗时长一些也可以接受了。
代码示例
一，数据按照分组字段有序，时间字段无序时，取出组内时间最早的记录。
A |
|
1 |
=file("T.ctx").open().cursor(gid,time1,…;…) |
2 |
=A1.group(gid).(~.minp(time1)) |
3 |
… |
A1：打开组表 T.ctx，定义游标。分号后写 where 条件。
A2：先按照 gid 分组。每组再取 time1 最小的记录，返回游标。
A3：继续对游标做其他计算。
这里采用聚合函数 minp，每组数据量不大时，性能比 sort 略好，代码也更简单。
二，数据按照分组、时间字段都有序时，取出组内时间最早的记录。
A |
|
1 |
=file("T.ctx").open().cursor(gid,time1,…;…) |
2 |
=A1.group@1(gid) |
3 |
… |
A2：按照 gid 分组，每组只取第一条记录，返回游标。
A3：继续对结果游标做其他计算。
和前面的代码比较，我们可以发现，如果预先按照分组、时间字段都有序，代码会简单不少。
三，数据预处理，有序存储。
A |
|
1 |
=file("T-original.ctx") |
2 |
=A1.open().cursor().sortx(gid,time1).new(gid,time1,…) |
3 |
=file("T.ctx").create(#gid,#time1,…) |
4 |
=A3.append@i(A2) |
A1：转换前的原始组表 T-original.ctx。
A2：打开组表 T-original.ctx 建立游标，按照字段 gid，time1 排序，结果游标将字段 gid，time1 放在前面。如果仅按 gid 排序，sortx 写作 sortx(gid) 即可。
A3：新建组表 T.ctx，字段名前面加了 #，即表明该组表对 gid，time1 字段有序。如果仅按照 gid 排序，create 写作 create(#gid,time1,…) 即可。
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,time1) |
|
3 |
if (day(now())==1) |
>A1.reset() |
4 |
>A1.append@a(A2) |
|
A1：打开组表 T.ctx。
A2：定义 T_new.btx 的游标并排序，通常每天新增数据量不大，这里虽然用 sortx，但实际上经常会是内存排序，速度很快。如果仅对 gid 有序，去掉 sortx 中的 time1 就可以了。
A3：判断日期是否为 1 号，如果不是则执行 A4，用 append@a 只在补数据上归并。如果是 1 号，那么就执行 B3，用 reset 把原有序数据和补数据有序归并成新的有序数据。
英文版