【性能优化】7.2 [归并与连接] 分段归并

【性能优化】7.1 [归并与连接] 有序归并

7.2 分段归并

面向大数据的有序归并算法有个不太方便的地方,数据要一条条从两个(或更多)游标中读出后比对,这种逻辑下无法直接实现分段并行。因为无法保证两个表的关联键值是在对应分段中能同步分布,A 表在第二段的键值可能会对应到 B 表的第三段。

我们还可以再次利用主键的有序性来解决这个问题。

A 表和 B 表用主键关联时,以 A 为基准,将其分段。然后可以快速取出每一段主键的起止值,然后再用每一段的主键区间作为条件到 B 表中去做查找,因为 B 表也是主键有序的,主键值落在这区间的记录是连续存储的,也可以迅速地被定位并生成游标,这样就可以同步分段并实现并行计算了:


A

B

1

=file("A.ctx").open()

=file("B.ctx").open()

2

=[-inf()]   | 9.(A1.cursor(;;~+1:10).fetch(1).id)| [inf()]

3

=10.("id>="/A2(#)/"  &&"id<"A2(#+1))

4

fork   to(10)

=A1.cursor(;;A4:10)

5


=B1.cursor(;${A3(A4)})

6


=joinx(B4,id;B5,id)

7


=…

8

=A4.conj().…


A2 中先读出 A 表中在每个分段的第一条记录的 id 值,A3 用这些分段点拼出区间条件。然后在每个线程中,A 表仍然正常分段,B 表则用相应的条件来分段,这样就能保证两边的键值是同步对应的,得到分段游标的关联游标再继续计算。

SPL 提供了相应的函数用这种方法生成可关联的多路游标:


A

B

1

=file("A.ctx").open()

=file("B.ctx").open()

2

=A1.cursor@m(;;4)

=B1.cursor(;;A3)

3

=joinx(A2,id;B2,id)

A2 中正常生成 A 表的多路游标,B2 中可以基于 A2 生成 B 表的多路游标,因为组表在创建时可以定义主键(create 时带 #的字段名),这里就不用再写字段名而直接会将两个表的主键对应来查找(两表的主键字段名可以不同)。A3 的 joinx 也会返回多路游标。

SPL 也支持在有序的集文件和文本文件上使用这种对位同步分段机制,但需要写上关联的字段了,工作原理是一样的,这里就不举例了。

还有一个问题。

主键是不重复的,分段时不可能把两个相同主键的记录分到两个段中。但主子关联时,子表的关联键并不是全部的主键,可能有重复值,也就可能在两个自然分段中出现关键键相同的记录。所以,在主子关联情况要做并行分段时,要以主表作为基准,子表跟随主表分段,而不能随意倒过来。

同时,还要在子表创建时设置分段字段(参见有序分组那一节讲述的并行分段,组表创建时 create 函数后部增加的参数),保证分段时不会把相同的字段值分到两个段中,这样可以在跟随分段时更快速的定位。

【性能优化】7.3 [归并与连接] 关联定位
【性能优化】 前言及目录