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

【性能优化】6.8 [外键关联] 单边分堆

7.1 有序归并

我们已经多次提到过有序归并,比如第二章中讲有序组表的追加时就用到这个算法,它可以用于实现大集合的交并差运算。以并集为例写出来的算法逻辑大体如下:


A

B

C

D

1

func


=file("A.btx").cursor@b()

=file("B.btx").cursor@b()

2



=C1.fetch(1))

=D1.fetch(1)

3


for

if   C2==null && D2==null

break

4



else   if C2==null

>r=D2,D2=D1.fetch(1)

5



else   if D2==null

>r=C2,C2=C1.fetch(1)

6



else   if C2.id<D2.id

>r=C2,C2=C1.fetch(1)

7



else   if C2.id>D2.id

>r=D2,D2=D1.fetch(1)

8



else

>r=C2,C2=C1.fetch(1),D2=D1.fetch(1)

9



return   r


10

return   cursor@c(A1)

数据表 A 和 B 都按 id 字段有序,从游标 C1 和 D1 中分别取出一条记录,比较出哪条记录的 id 更小,保存这条记录准备返回,并继续读取该记录所属游标,反复这个动作直到把两个游标的数据都取完。返回的游标就是两个数据集针对 id 字段计算出的并集。

计算交集,可以改成仅在相等时才返回数据,并且有一个游标结束时循环就结束了。差集也可以类似地实现。这个算法也可以推广到 n 个表的情况,代码会更复杂。

有序归并还可以用于实现连接运算,以内连接为例的算法逻辑:


A

B

C

D

1

func


=file("A.btx").cursor@b()

=file("B.btx").cursor@b()

2



=C1.fetch(1))

=D1.fetch(1)

3


for

if   C2==null || D2==null

break

4



else   if C2.id<D2.id

>C2=C1.fetch(1)

5



else   if C2.id>D2.id

>D2=D1.fetch(1)

6



else

=new(C2,D2)

7




>r,C2=C1.fetch(1),D2=D1.fetch(1)

8




return   D6

9

return   cursor@c(A1)

算法逻辑和交集运算很像,全连接和左连接了可以类似实现,调整中间判断代码即可。同样也可以推广到 n 个表的情况。

有序归并算法只要把两个表都遍历一次就可以完成,即使是大数据表,也不必借助缓存文件。如果两个表的规模分别是 N 和 M,则复杂度为 O(N+M)。无序时实现集合或连接运算,不做优化时要两两比较,复杂度将会是 O(N*M),远远大于 O(N+M)。数据库通常使用的是上一章讲过的哈希分堆算法,复杂度可以下降 K 倍(K 是哈希值的平均重复数量),但一般仍然会远大于有序归并算法。而且对于大数据的外存运算,哈希分堆会还产生缓存文件的读写动作,以及我们多次提过的可能运气不好的情况。利用有序后的归并算法有巨大的性能优化。

SPL 把集合运算和连接运算的有序归并算法都实现了:


A

1

=file("A.btx").cursor@b()

2

=file("B.btx").cursor@b()

3

=[A1,A2].mergex@u(id)

3

=[A1,A2].mergex@i(id)

3

=[A1,A2].mergex@d(id)

mergex 函数的选项 @u、@i、@d 分别表示并集、交集和差集。


A

1

=file("A.btx").cursor@b()

2

=file("B.btx").cursor@b()

3

=joinx(A1,id;A2,id)

3

=joinx@1(A1,id;A2,id)

3

=joinx@f(A1,id;A2,id)

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

mergex 和 joinx 都会假定作为参数的游标已经有序,针对无序游标执行这两个函数会得到错误的计算结果。

这两个函数都是延迟游标,需要再定义进一步的计算。

除了外键关联外,常见的连接运算还有同维关联和主子关联两类。同维关联是一对一的,两个表用主键关联。主子关联则是主表的主键和子表的前一部分主键关联,是一对多的。这两种关联的双方都和主键相关,如果数据按主键有序,就可以采用低复杂度的有序归并算法。上一章讲过的外键关联,在大维表对主键有序时也能获得高性能。

数据表对主键有序是实现高性能连接运算的关键,而且仅对主键有序就足够了,满足这个前提的成本并不是很高。在 SPL 中,我们会假定缺省情况下外存数据表都对主键有序,只有个别用于特殊查找目标的数据表才会另行排序。

关系代数对连接运算的定义过于简单(笛卡尔积再过滤),并没有涉及主键,严格实现这个定义时,理论上不能假定关联键的有序性,也就不能采用这些优化算法。而且关系代数的理论无序性也很难保证数据表对任何字段有序,数据库即使想在工程优化中实现也比较困难。

【性能优化】7.2 [归并与连接] 分段归并
【性能优化】 前言及目录