SQL 提速：两个大数据表在主键上做连接
【摘要】
从原理上分析 SQL 语句慢的原因，用代码示例给出提速办法。点击了解SQL 提速：两个大数据表在主键上做连接
问题描述
主键连接是非常常见的情况，如订单和订单明细。但数据库并不区分关联的字段是什么，一般都会采用 HASH JOIN 算法计算，常常出现大表连接非常慢的现象。这是因为 HASH JOIN 本质上是内存运算，数据量巨大的时候需要做分堆缓存才能把大数据 JOIN 转换成若干小数据 JOIN，IO 开销很大，而且 HASH 运气不好时还可能多次缓存。
提速方案
一、有序归并计算连接
若两表都对主键有序，就可以使用归并算法实现连接，有序归并算法只需要对两个表依次遍历，不必借助缓存，可以大幅降低 IO 量。而且有序归并复杂度很低，是加法级的，而 HASH JOIN 是乘法级的。
如果两表无序，我们要预先按主键排序。排序成本很高，每次都排序会导致总体性能还不如传统算法。幸运的是，仅是主键（或部分主键）之间关联的场景就非常多，能解决这个场景应用面就足够广了。事实上，其他有意义的关联也都和主键相关，我们会另行讨论。
预先按照主键排序虽然慢，但是一次性的，而且只需要保持主键有序这一种存储即可，没有冗余。
二、新增数据追加
新增数据并不总是按主键继续有序，所以不能简单的追加到有序数据的末尾。而直接将有序数据和新增数据一起重新做常规大排序，会非常耗时。
我们可以将新增数据排序后，和原有序数据一起，也用低成本的有序归并算法生成新的有序数据。这样整体复杂度相当于把所有数据读写一遍，可以避免常规大排序中产生很多临时外存缓存的现象，从而获得更好的性能。
更进一步，可以另外保持一个小规模的有序数据 (以下称为补数据)。新增数据排序后和补数据归并，原有序数据不变。经过适当的时间后，补数据积累到合适大小时，再和原有序数据归并。做连接计算时，从有序数据和补数据中分别读取，归并后再和其他表做连接，性能会比只有一份有序数据时下降一些，但仍能利用有序实现快速连接计算。
这个适当时间的确定，与新增数据的周期有关。比如每天都有新增数据，则每个月做一次原有序数据和补数据的归并。补数据不会超过一个月的数据量，原有序数据存储一个月之前的所有数据。也就是说补数据可能会比原有序数据小很多，所以每天归并的数据量相对较小，很快就能完成数据追加。每个月才需要完成一次全量有序归并，耗时长一些也可以接受了。
代码示例
第一步，数据预处理，有序存储。
以表 A 为例，表 B 的代码类似。
A |
|
1 |
=file("A-original.ctx") |
2 |
=A1.open().cursor().sortx(a).new(a,…) |
3 |
=file("A.ctx").create(#a,…) |
4 |
=A3.append@i(A2) |
A1：转换前的原始组表 A-original.ctx。
A2：打开组表 A-original.ctx 建立游标，按照字段 a 排序，结果游标将字段 a 放在前面。
A3：新建组表 A.ctx，字段名前面加了 #，即表明该组表对 a 字段有序。
A4：将排好序的数据输出到组表 A.ctx 中。
第二步，有序归并实现连接。
A |
|
1 |
=file("A.ctx").open().cursor(a,…) |
2 |
=file("B.ctx").open().cursor(b,…) |
3 |
=joinx(A1:A,a;A2:B,b) |
4 |
… |
A1、A2：打开组表 A.ctx 和 B.ctx，定义游标。
A3：采用有序归并算法，两个游标按照字段 a 和 b 做内连接，返回游标。类似的，joinx@f 表示全连接，joinx@1 表示左连接。
A4：继续对有序归并的结果游标做其他计算。
第三步，新增数据追加。
假设 A 表每天的新增数据存储在 A_new.btx 中，且字段名称、顺序与 A.ctx 相同。
A |
B |
|
1 |
=file("A.ctx").open() |
|
2 |
=file("A_new.btx").cursor@b().sortx(a) |
|
3 |
if (day(now())==1) |
>A1.reset() |
4 |
>A1.append@a(A2) |
|
A1：打开组表 A.ctx。
A2：定义 A_new.btx 的游标并排序，通常每天新增数据量不大，这里虽然用 sortx，但实际上经常会是内存排序，速度很快。
A3：判断日期是否为 1 号，如果不是则执行 A4，用 append@a 只在补数据上归并。如果是 1 号，那么就执行 B3，用 reset 把原有序数据和补数据有序归并成新的有序数据。
