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

【性能优化】6.7 [外键关联] 大维表查找

6.8 单边分堆

我们最后来处理维表和事实表都很大的情况,通常事实表会更大。这种情况无论如何都很难高速计算出来,但仍然要想办法尽量做得快。

是否可以把事实表用游标读出来,分批执行上一节的维表查找算法呢?

不可以。因为事实表很大,过多批次的查找,总会把所有维表记录都查找到,甚至不止一遍,这会导致严重的频繁小量读取,就如同之前讲过索引排序的总耗时不见得比大排序算法更好,这种算法的性能大概率赶不上把事实表和维表都排序再做归并连接的算法。

对于两个大表的情况,数据库一般采用哈希分堆的方法。即分别计算两个表中关联键的哈希值,将哈希值在一定范围的数据分到一堆,形成外存的缓存数据,保证每一堆都足够小可以装入内存,然后再逐个针对每一对堆(两个表)执行内存连接算法。这种方法会将两个大表都拆分缓存,也可以称为双边分堆方法。在哈希函数运气不好时,还可能发生某一堆过大而要再做第二轮哈希的情况。

如果维表按主键有序存储并采用了合适的存储方案后可以分段读取,我们就可以认为维表已经在逻辑上做过了分堆(简单将每一段作为堆,知道数据表的总大小也容易计算出合适的分段数),现在只要将事实表按其外键落在维表主键的哪一段来做拆分并缓存,即只要将事实表分堆即可。再逐步针对(事实表的)每一堆和维表的相应段做关联,因为分堆已经保证了这一堆的事实表记录只会和对应段的维表记录关系。

算法的逻辑过程如下:


A

B

C

D

1

=file("customer.btx")

2

=10.(A1.cursor@b(id;~:10).fetch(1).cid)

3

=file("orders.btx").cursor@b(c_id,amount)

4

=10.(file("temp"/~))

5

=A3.groupn(pseg(A2,c_id);A4)

6

func  

for   10

=A1.curor@b(cid,area,discount;B6:10)

7



=A4(B6).cursor@b().join(c_id,C7:cid,area,discount)

8



for   C7,1000

return   C8

9

=cursor@c(A6).groups(area;amount*discount)

整体过程和双边分堆算法差不多,但维表不需要再被分维,只要将事实表分堆,所以可以称为单边分堆。而且,这种办法可以将维表平均分段,不会出现运气不好要二次哈希分堆的情况。可能某一个事实表的分堆太大,但这时候可以执行大事实表小维表的算法,也不需要二次分堆。单边分堆算法的缓存数据量要比双边分堆少得多,性能也会更优越。

过程还是比较复杂,SPL 也将算法做好了封装:


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)

不再使用 @q 选项的 joinx 函数,SPL 即认为事实表也很大,需要做分堆处理。和上一节的算法类似,维表需要被分段访问,要以数据文件的方式出现,而不能是游标。

joinx@u 返回的游标取出数据的次序看起来是乱的,从上面算法上可知,它会按维表的分段逐个取出做连接后返回,总体次序应该和维表主键相同。但对于每一段又会以事实表分堆的次序,这一段内并不一定按维表主键有序,总体看起来很像是无序的。

如果希望按事实表的原序返回,把 @u 选项也去掉就可以了。

这时候,SPL 会生成一个原事实表中记录的序号,在分堆缓存时按这个序号排序后再写入,做完每一段连接后还要再次写成缓存,然后将后一轮的所有缓存按原序号做归并排序。这样相当于比 joinx@u 多做一次大排序,性能会更差。但有时事实表本来是有序的,还需要利用这个次序做下一轮计算,就要必须继续保持这个序。

【性能优化】7.1 [归并与连接] 有序归并
【性能优化】 前言及目录