SPL 中的关联计算 - 外存篇

上一篇《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 还提供其他高性能算法,详情参见:关联定位附表