上一篇《SPL 中的关联计算 - 内存篇》（简称“内存篇”）介绍了 SPL 对关联计算的分类，以及内存关联计算的编程方法。

当一个或者多个关联表数据量很大需要外存时，就不能使用内存连接算法了，SPL 专门提供了外存连接的方法。

解决外存关联问题时，和内存关联有相同之处：

1、先明确区分连接的类型，找到参与关联的（逻辑）主键。

2、再根据外键连接和主键连接的不同情况，选择不同的 SPL 函数完成计算。

外键连接

内存篇中介绍过，外键连接是指 A 表的某个字段和 B 表的主键等值连接。A 表称为事实表，B 表称为维表。A 表中与 B 表主键关联的字段称为 A 指向 B 的外键，B 也称为 A 的外键表。

对于外存的外键连接，SPL 按照事实表、维表大小的三种不同情形，提供不同的计算方法。

情形 1：事实表很大，维表较小

这里所说的大小是相对内存而言的。维表较小，是指可以全部装入内存。事实表较大，意思是超过了内存容量。

在实际应用中，事实表很大、维表较小是比较常见的情况。这是因为事实表用于存储不断增长的事件，很容易变得很大。维表用于存储代码类信息，增长变化不大，规模相对稳定，不会太大。

我们知道，地址是个内存概念。因为只有维表在内存中，所以事实表的外键就不能实现地址化了，也就无法完成内存篇介绍的预关联，只能临时建立关联，称为临时地址化。

SPL 使用cs.switch（cs 代表游标）函数来实现临时地址化。

假设订单表 orders（事实表）通过产品号 pid 与产品表（维表）关联，现在要按照产品表中的提供商 vendor 分组，汇总订单总额。

临时地址化的代码大致是下面这样：

	A
1	=file("product.btx").import@b().keys@i(pid)
2	=file("orders.ctx").open().cursor(pid,amount)
3	=A2.switch(pid,A1)
4	=A3.groups(pid.vendor;sum(amount))

A1：维表全部装入内存，并建立带索引的主键。

A2：事实表建立游标，只读取需要的字段。

A3：在事实表游标上使用 cs.switch 函数实现外键地址化，它会返回一个延迟游标，在取数的时候才会进行实质性的关联计算。

A4 ：接下来的分组汇总计算要基于 A3 的返回结果才可以，不像全内存时可以基于原数据表运算，因为全内存时的 switch 会改变原数据表的外键字段，而现在的关联是在游标读取过程中做的。

和内存外键地址化类似，用 cs.switch 实现外键连接也会出现外键值丢失现象，且同样无法实现多字段外键的情况。这些问题可以用 cs.join 函数解决。

假设订单表和产品表是通过产品表的主键 ptype 和 pid 两个字段关联的，分组汇总计算代码大致如下：

	A
1	=file("product.btx").import@b().keys@i(ptype,pid)
2	=file("orders_new.ctx").open().cursor(ptype,pid,amount)
3	=A2.join(ptype:pid,A1,~:pid_fk)
4	=A3.groups(pid_fk.vendor;sum(amount))

A1：维表全部装入内存，并建立两个字段的主键。

A3 中 cs.join 按照主键关联产品表。除了原有字段之外，再增加一个 pid_fk，存储对应记录的引用地址。如果找不到对应记录，pid_fk 就为空。

A4 用 pid_fk 来引用产品表的字段 vendor，完成分组计算。

和内存计算类似，cs.switch 和 cs.join 也有 @i 和 @d 选项。当事实表的外键在维表没有找到对应记录的时候，@i 表示结果中删除这条事实表记录，@d 则表示只保留找不到外键对应记录的事实表记录。

cs.switch@i 是将事实表游标与维表关联，而且要过滤掉关联不上的游标记录。但它需要先从游标中取出记录再判断关联，即使关联不上，这条记录也已经生成了。

SPL 为组表游标提供了专门方法来提高过滤计算的性能，详细介绍参见游标前过滤。我们可以将这个方法应用在组表游标外键关联上，也就是 SPL 的组表游标关联过滤机制。

以订单和员工的关联为例，这种机制的代码大致是这样：

	A
1	=file("employee.btx").import@b().keys@i(eid)
2	=file("orders.ctx").open().cursor(o_eid,amount;o_eid:A1)
3	=A3.groups(o_eid.vendor;sum(amount))

为了更容易区分员工表中的员工号 eid，我们将订单表中的员工号写为 o_eid。

A2 中在组表游标过滤条件参数的位置写 o_eid:A1，SPL 就会在生成记录之前判断能否关联上。如果可以关联上，则同时将维表记录地址赋值给 o_eid，完成外键地址化。

假设只需要判断订单和员工是否有关联，而不做外键地址化，则可以用常规的条件语法：

	A
1	=file("employee.btx").import@b().keys@i(eid)
2	=file("orders.ctx").open().cursor(amount;A1.find(o_eid))
3	=A3.total(sum(amount))

A2 中的游标前过滤条件是 A1.find(o_eid) 不为空。

SPL 没有为 cs.join 函数提供相应的语法，多字段外键时只能先读出记录后再处理。

cs.switch和cs.join函数可以基于多路游标实现并行计算，本例中的 A4 可以用 cursor@m 选项写成多路游标，后面的代码不用改变。

对于多个小维表或多层小维表的情况，可以预先把维表读入内存，建好索引并在维表之间做好预关联，之后再遍历事实表计算。维表上的索引和维表之间的预关联可以多次复用。

除了临时地址化之外，SPL 还为大事实表、小维表的情形提供了一系列的高性能算法。比如外键序号化机制，是预先将事实表外键值转换为维表记录在维表中的序号，在计算关联时，就可以使用更快速的序号定位来实现了。

还以订单和员工的关联为例，可以预先将订单的外键字段 o_eid 转化为员工维表序号，为序号关联做准备。代码大致是这样：

	A
1	=file("employee.btx").import@b().keys@i(eid)
2	=file("orders.ctx").open().cursor(oid,o_eid,amount,…)
3	=A2.run(o_eid=A1.pfind(o_eid))
4	=file("orders_new.ctx").create(#oid,o_eid,amount,…)
5	=A4.append@i(A3)

A3 中用 pfind 将订单表中的 o_eid 转换为维表中的序号。

A4、A5 建立新的订单表，将 A3 的结果写入到新组表，实现外键序号化。

这时，新的订单表就能使用序号实现与员工表的关联。代码大致是这样写：

	A
1	=file("employee.btx").import@b()
2	=file("orders_new.ctx").open().cursor(o_eid,amount)
3	=A2.switch(o_eid,A1:#)
4	=A3.groups(o_eid.vendor;sum(amount))

A1：产品表用于序号定位，无需建立主键和索引，可以节省内存。

A3：switch 中使用 #，表示序号关联，直接用 o_eid 作为序号在维表对应位置上取得记录，比临时地址化性能更好。

A2 中的 switch 如果加上 @i，序号关联不上的订单记录会被删除。这种情况也可以用组表游标关联过滤来实现，代码大致是这样的：

	A
1	=file("employee.btx").import@b().keys@i(eid)
2	=file("orders.ctx").open().cursor(o_eid,amount;o_eid:A1:#)
3	=A3.groups(o_eid.vendor;sum(amount))

A2：组表游标前过滤参数写成 o_eid:A1:#，表示以 o_eid 为序号去取 A1 的记录，如果结果是 null，这条事实表记录将不会被生成。

序号化手段当然在内存关联时也能使用，只是内存时可以预关联成地址，使用地址和使用序号访问维表的性能差别不大。不过，如果维表已经序号化了，在内存中做预关联时使用序号化技术仍然会有优势。

有时候维表还会被过滤，SPL 也针对这种情况提供了高性能算法。这里不再详细解释，请参考：索引复用、对位序列。

情形 2：维表很大，事实表比较小

这种情况下，事实表可以全部装入内存，维表外存，用事实表关联维表，本质上是对外存的批量查找计算。

SPL 提供 T.joinx@q 函数来完成情形 2 的外键关联，这个函数要求大维表对主键有序。

假设订单表（事实表）很小，客户表（维表）比较大，我们要预先将客户表按照主键有序存放。这样预处理后，两表按照客户号关联的代码大致如下：

	A
1	=file("customer.ctx").open()
2	=file("orders.btx").import@b(cid,amount)
3	=A2.joinx@q(cid,A1:cid,area,discount)
4	=A3.groups(area;amount*discount)

需要注意 T.joinx@q 要求大维表不能以游标形式参与计算。对组表来说，要以 A1（实表）的方式参与计算，这是其计算原理决定的。详细的原理介绍和更多的场景参见：大维表查找。

外存表有序后，还要考虑数据量少量修改、定期追加和批量删除的问题。这里有详细的介绍：SPL 的有序存储。后续介绍中出现的有序外存数据，都可以参考这个文章来解决数据变化的问题。

情形 3：事实表和维表都很大

当维表和事实表都很大（通常事实表会更大）时，无论如何都很难高速计算出来。SPL 提供单边分堆机制，可以得到尽可能好的性能。

SPL 的 cs.joinx@u 函数封装了单边分堆机制，这个函数也要求维表按照主键有序。假如订单表和客户表都比较大，我们要预先将客户表按照主键有序存放。

完成预处理后，两个表按照客户号关联的代码大致是这样：

	A
1	=file("customer.btx")
2	=file("orders.btx").cursor@b(c_id,amount)
3	=A2.joinx@u(c_id,A1:cid,area,discount)
4	=A3.groups(area;amount*discount)

注意 T.joinx@u 也要求大维表不能以游标形式出现。对集文件来说，要以 A1（文件）方式参与计算。

详细的原理介绍和更多的场景参见：单边分堆。

主键连接

内存篇中介绍过，主键连接是指 A 表的主键和 B 表的主键或部分主键等值连接。主键连接再细分为同维连接和主子连接。

同维连接

表 A 的主键与表 B 的主键关联称为同维连接，A 和 B 互称为同维表。同维表是一对一的关系，逻辑上可以简单地看成一个表来对待。

互为同维表的多个表，往往会同时增长，所以不太会出现有大有小的情况。

SPL 采用有序归并算法（joinx 函数）实现外存同维表之间的连接，这个算法要求预先将同维表都按照主键有序存储。

假设客户 customer 和客户信息 customer_info 的主键都是客户号，分别存储客户的不同属性，现在要求客户表中的 acctbal 和客户信息表中的 fund 之和。

预先将两个表都按照客户号 cid 有序存储后，用 joinx 函数实现同维连接的代码大致是这样的：

	A
1	=file("customer.ctx").open().cursor(cid,acctbal)
2	=file("customer_info.ctx").open().cursor(cid,fund)
3	=joinx(A1:c,cid;A2:ci,cid)
4	=A3.new(c.acctbal+ci.fund:newValue)

A1、A2：定义客户和客户信息组表的游标。

A3：将两个游标按照主键有序归并连接。使用 joinx 时，参与关联的各游标数据必须按关联字段有序。

A4：取出 A3 中 c 的字段和 ci 的字段相加，构成一个新的游标。

joinx函数无选项、@1、@f 分别表示内连接、左连接和全连接。

joinx 函数支持多线程并行计算。在并行分段时，为了保证两个文件相同的主键分到对应的段中，必须指定以哪个游标为基准。

所以上述代码要改成这样，才能正确的并行计算：

	A
1	=file("customer.ctx").open().cursor(cid,acctbal;;4)
2	=file("customer_info.ctx").open().cursor(cid,fund;;A1)
3	=joinx(A4:c,cid;A5:ci,cid)
4	=A6.new(c.acctbal+ci.fund:newValue)

A1：用基本的办法定义多路游标，路数为 4。

A2：以 A1 为基准生成多路游标。因为组表在创建时可以定义主键（create 时带 #的字段名），这里就不用再写字段名而直接会将两个表的主键对应来查找（两表的主键字段名可以不同）。

有序归并连接原理的介绍参见这里：SPL 有序归并关联。

主子连接

表 A 的主键与表 B 的部分主键关联，A 称为主表，B 称为子表。主子表是一对多的关系。

和同维表类似，主子表一般都会同时增长，同时需要外存。

SPL 同样采用有序归并的机制计算主子连接，主子表也要预先按照主键有序存放。

假设订单表 orders（主键 oid）和订单明细表 order_detial（主键 oid，pid）通过订单表的主键 oid 和订单明细的部分主键 oid 关联。订单是主表，明细是子表。

现在要过滤出折扣大于 0.05 的订单，并按照 pid 分组，汇总 amount 求和、discount 求平均。

预先将两个表数据按照主键有序存储成组表后，两表关联的代码大致是这样：

	A
1	=file("orders.ctx").open().cursor(oid,amount)
2	=file("orders_detail.ctx").open().cursor(oid,pid;discount>0.05)
3	=joinx(A1:o,oid;A2:od,oid)
4	=A3.groups(od.pid;sum(amount),avg(discount))

A2：订单明细采用了游标前过滤算法，性能更优。

和同维连接类似，用多路游标计算主子连接时也要确定基准表。不同的是，主子连接只能以主表为基准，代码大致如下：

	A
1	=file("orders.ctx").open().cursor@m(oid,amount)
2	=file("orders_detail.ctx").open().cursor(oid,pid;discount>0.05;A1)
3	=joinx(A1:o,oid;A2:od,oid)
4	=A3.groups(od.pid;sum(amount),avg(discount))

A1：没有指定游标路数，用 SPL 默认的路数。

A2：子表多路游标，以主表 A1 为基准。

对于外存主键连接，SPL 还提供其他高性能算法，详情参见：关联定位、附表。