SQL 提速：大数据 DISTINCT 和 COUNT(DISTINCT)
【摘要】
从原理上分析 SQL 语句慢的原因，用代码示例给出提速办法。点击了解SQL 提速：大数据 DISTINCT 和 COUNT(DISTINCT)
问题描述
去重本质上是分组运算，需要遍历原数据。计算时要一直保持一个去重后的结果集，每一条原数据都要到结果集中查找是否有相同的，以决定丢弃还是添加。
如果结果集较小，全内存查找的速度还能接受。但是，如果结果集太大无法装入内存，一般就需要使用 HASH 分堆算法，把原数据拆成几部分缓存到外存中，再分别做内存结果集的去重。这样会多出外存读写动作，性能就很差。
只要计数的 COUNT(DISTINCT)，也要保持去重的结果集才能正确计算出来，面临同样的问题。
提速方案
一、原数据排序后另存为有序数据，实现快速去重。
如果原数据对于去重字段有序，那么问题就会简单很多。只要在遍历过程中把与上一条不相同的字段逐步保存下来，即使内存放不下也不必做分堆处理。COUNT(DISTINCT) 则只要在发生不同时加 1 即可，甚至不需要保持结果集。
通常要做去重（计数）的大都是类似用户帐号等少量确定的字段，而很少会随意指定任何字段做去重（计数），事先对这些数据先排序，之后再做各种去重（计数）就可以比较快了。
其实，对字段建立索引，一定程度相当于排序，这时候也能迅速地计算出去重（计数）的结果。但是去重前后一般都有其他计算，比如常见的先过滤后去重等，有可能用到原数据中的任意字段。过滤字段如果不再索引中，就无法使用索引来去重了。对去重字段建立索引也不能完全解决实际的去重问题。
二、新增数据追加。
新增数据通常并不会按要去重的字段继续有序，所以不能直接追加到有序数据的末尾。例如数据是按照用户帐号排序的，新增数据中则可能包含任意一个用户账号，如果直接追加到有序数据的最后，就不能保持整体上对帐号有序了。而直接将有序数据和新增数据一起重新做常规大排序，会非常耗时。
可以将新增数据排序后，和原有序数据一起，用低成本的有序归并算法生成新的有序数据，这样整体复杂度相当于把所有数据读写一遍，可以避免常规大排序中产生很多临时外存缓存的现象，从而获得更好的性能。
更进一步，可以另外保持一个小规模的有序数据 (以下称为补数据)。新增数据排序后和补数据归并，原有序数据不变。经过适当的时间后，补数据积累到合适大小时，再和原有序数据归并。做去重计算时，要从有序数据和补数据中分别读取，归并后遍历，会比只有一份有序数据时性能下降一些，但仍能利用有序快速去重。
这个适当时间的确定，与新增数据的周期有关。比如每天都有新增数据，则每个月做一次原有序数据和补数据的归并。补数据不会超过一个月的数据量，原有序数据存储一个月之前的所有数据。也就是说补数据可能会比原有序数据小很多，所以每天归并的数据量相对较小，很快就能完成数据追加。每个月才需要完成一次全量有序归并，耗时长一些也可以接受了。
代码示例
去重 SQL 举例如下：
SQL1：select distinct F1,…,Fn from T where …
SQL2：select count(distinct F1,…,Fn) from T where …
第一步，数据预处理，有序存储。
A |
|
1 |
=file("T-original.ctx") |
2 |
=A1.open().cursor().sortx('F1',…,'Fn').new('F1',…,'Fn',…) |
3 |
=file("T.ctx").create('#F1',…,'#Fn',…) |
4 |
=A3.append@i(A2) |
A1：转换前的原始组表 T-original.ctx。
A2：打开组表 T-original.ctx 建立游标，按照去重字段排序，结果游标将去重字段放在前面。因为 F1…Fn 与单元格名称重复，所以要加单引号。不重复的字段名不需要单引号。
A3：新建组表 T.ctx，字段名前面加了 #，即表明该组表对这些字段有序（按字段的次序有序，且必须是组表的前几个字段）。
A4：将排好序的数据输出到组表 T.ctx 中。
第二步，实现 SQL1 去重查询。
A |
|
1 |
=file("T.ctx").open().cursor('F1',…,'Fn';…) |
2 |
=A1.group@1('F1','F2','F3') |
3 |
… |
A1：打开组表 T.ctx，定义游标取去重字段。过滤条件要写在 cursor 参数中的分号之后，例如字段 Fx、Fy、Fz 的过滤条件写作：cursor('F1',…,'Fn';Fx==1 && Fy<10 && Fz>200)，相当于 SQL 的 where Fx=1 and Fy<10 and Fz>200。
A2：对游标定义有序分组，且取每一个分组的第一条记录返回成游标（注意是数字 1，不是字母 l）。
A3：结果集可能很大而不能全部取出，得到游标后可以再做进一步的计算或将结果集保存起来。
第三步，实现 SQL2 去重计数。
A |
|
1 |
=file("T.ctx").open().cursor('F1',…,'Fn';…) |
2 |
=A1.group@1('F1','F2','F3') |
3 |
=A2.skip() |
A3：对游标计数。
第四步，数据追加。
假设每天的新增数据存储在 T_new.btx 中，且字段名称、顺序与 T.ctx 相同。
A |
B |
|
1 |
=file("T.ctx").open() |
|
2 |
=file("T-new.btx").cursor@b().sortx('F1',…,'Fn') |
|
3 |
if (day(now())==1) |
>A1.reset() |
4 |
>A1.append@a(A2) |
|
A1：打开组表 T.ctx。
A2：定义 T-new.btx 的游标并排序，通常每天新增数据量不大，这里虽然用 sortx，但实际上经常会是内存排序，速度很快。
A3：判断日期是否为 1 号，如果不是则执行 A4，用 append@a 只在补数据上归并。如果是 1 号，那么就执行 B3，用 reset 把主数据和补数据合并。
