【摘要】
从原理上分析 SQL 语句慢的原因，用代码示例给出提速办法。点击了解SQL 提速：两个大数据表在主键上做连接

问题描述

主键连接是非常常见的情况，如订单和订单明细。但数据库并不区分关联的字段是什么，一般都会采用 HASH JOIN 算法计算，常常出现大表连接非常慢的现象。这是因为 HASH JOIN 本质上是内存运算，数据量巨大的时候需要做分堆缓存才能把大数据 JOIN 转换成若干小数据 JOIN，IO 开销很大，而且 HASH 运气不好时还可能多次缓存。

提速方案

一、有序归并计算连接

若两表都对主键有序，就可以使用归并算法实现连接，有序归并算法只需要对两个表依次遍历，不必借助缓存，可以大幅降低 IO 量。而且有序归并复杂度很低，是加法级的，而 HASH JOIN 是乘法级的。

如果两表无序，我们要预先按主键排序。排序成本很高，每次都排序会导致总体性能还不如传统算法。幸运的是，仅是主键（或部分主键）之间关联的场景就非常多，能解决这个场景应用面就足够广了。事实上，其他有意义的关联也都和主键相关，我们会另行讨论。

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

二、新增数据追加

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

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

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

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

代码示例

第一步，数据预处理，有序存储。

以表 A 为例，表 B 的代码类似。

A1：转换前的原始组表 A-original.ctx。

A2：打开组表 A-original.ctx 建立游标，按照字段 a 排序，结果游标将字段 a 放在前面。

A3：新建组表 A.ctx，字段名前面加了 #，即表明该组表对 a 字段有序。

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

第二步，有序归并实现连接。

A1、A2：打开组表 A.ctx 和 B.ctx，定义游标。

A3：采用有序归并算法，两个游标按照字段 a 和 b 做内连接，返回游标。类似的，joinx@f 表示全连接，joinx@1 表示左连接。

A4：继续对有序归并的结果游标做其他计算。

第三步，新增数据追加。

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

A1：打开组表 A.ctx。

A2：定义 A_new.btx 的游标并排序，通常每天新增数据量不大，这里虽然用 sortx，但实际上经常会是内存排序，速度很快。

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