【性能优化】2.4 [外存数据集] 组表与列存

 

【性能优化】2.3 [外存数据集] 数据类型

2.4 组表与列存

文本文件和集文件都是依次存入每条记录,这种方式称为行式存储(简称行存)。

大多数运算都不会使用到数据表的所有字段,由于硬盘必须成块的读取,这导致在行存方式时,无论读取多少字段,几乎都要把整条记录读取出来,所能做的优化最多是读出后不处理(比如产生相应的数据对象),但硬盘的读取时间是少不掉的。

如果采用列式存储(简称列存)就可以避免多余的读取了。

所谓列存,就是把数据表的各个记录的同一字段的值连续存储在一起。这样,如果运算只用到少数字段,那只要读取这些字段对应的数据即可,这样能减少读取量,有效提高性能。

但是,要考虑数据还会追加时,列存就会比行存麻烦得多。数据通常是按记录追加的,行存时只要把追加的记录写在后面即可,而列存时则不能这么简单的处理,要把字段值追加到各自的区域后面,这要求字段存储区域留有空位,否则很难保证同一字段数据的连续性。然而,事先并不知道总共有多少条记录,更不知道每个字段占用的空间大小,无法留出合适的空间。

通行的处理方法采用分块,整个数据区由一些有一定大小的数据块构成。同一个字段的值将写入同一个数据块,当这个数据块占满时再产生一个新数据块继续写入。这样,一个字段会占用若干数据块,数据块之间是不连续的,但数据块内部的字段值是连续存储的。只要数据块足够大时(现代硬盘超过 1M 基本就够了),数据块之间的不连续性导致的硬盘多余读取量已经可以忽略不计了。

既然分块了,可以顺便在数据块上做minmax 索引,即把这个块中的字段值的最大最小值记到块头,这占不了多少空间。在执行过滤时,如果发现要对比的字段值不在当前块的最大最小值范围内,则可以直接跳过整块而不再读取和解析,可以进一步减少读取量和运算量。

列存还有个麻烦之处在于分段的同步性。

各个数据块存储的字段数量不一样,除了各字段的第一个数据块之外,对于两个不同字段的其它任何数据块,都无法保证它们存储的是同一批记录的字段,简单使用数据块实现的列存无法实现分段。

业内常用的办法是再把数据按记录分批,比如每 1M 条记录作为一批,使用列存用上述的分块方式存储,而分段就只能以整批为单位,每一批内部不能再分段了。

这个办法在数据量特别大的时候还比较有效。因为一批必须足够大,让列存的数据块能连续地存储足够多的数据。而批数又要足够多,否则分段又会受到限制,因为分段只能以批为单位。记录数要达到亿级甚至更大的规模才合适使用这种方法。

采用倍增分段方法就可以解决这个问题了。

数据不再分批,只是为每个字段的数据区(由多个数据块构成)建立前述的索引区,在索引区记录每个分段起始的数据块及块内位置。追加记录时,所有索引区会同步填充和倍增,始终保证一致。所有索引区的索引块对应的记录数(其实是字段数)都相同,这样分段时也能保证不同字段数据区的同一序号分段一定会对应同样记录的字段。数据量不需要很大也可以获得良好的分段效果。

SPL 的列存文件称为组表,其中就实现了上述数据存储、minmax 索引以及倍增分段的机制。


A

B

C

1

=file("data.ctx")

=file("date.btx")


2

=A1.create(…)

=A2.append(B1.cursor@b())


3

=A1.open()



4

=A3.cursor(…;;4:10)

=A3.cursor(…;;5:10)

=A3.cursor(…;23:100)

5

=A4.fetch(1)

=B4.fetch(100)

=C4.fetch()

和集文件不同,组表需要事先创建后才能追加数据(A2 创建,B2 追加数据)创建时要先指明数据结构(A2 中的…部分),这有点类似数据库中的表需要先 CREATE TABLE。A4、B4、C4 类似前面产生了不同分段的游标,注意要多写一个分号。组表创建时会缺省使用列存,读取时在参数中(A4、B4、C4 中的…)写上用到的字段名,就能利用列存优势减少读取量了。

结构化数据的编码方式一般都不会非常紧凑(即使使用了前节说过的优化方式),这样常常都还有一定的可压缩余地。数据被压缩后可以减少硬盘的空间占用,从而减少读取时间,但解压缩又会增加 CPU 的运算量,消耗更多计算时间。压缩的效果也和采用的算法有关,压缩率高的算法通常会在解压时占用更多 CPU 时间。所以,压缩与否并不是一个确定的选择,需要根据实际情况甚至进行一定的测试后才能决定。

列存比行存更有利于数据压缩。结构化数据中同一个字段的数据类型一般都是相同的,甚至有些情况取值都很接近,这样一批数据构成的数据块通常会有较好的压缩率。

组表创建时会缺省使用列存和压缩方式。SPL 提供了选项可由用户选择行存或不压缩。

采用列存方式时,如果数据表中某个字段有序,就意味着,相邻记录的该字段值会有较大相同的可能性。这样,可以只存入重复的数量和一个值,而不必把同样的值存储多遍,少占用的空间是相当可观的。

为了利用这个方案,我们可以事先将数据排序再存入文件。不过,一个数据表只能有一种排序方式,对 A 字段有序时就无法再对 B 字段有序,那么应该优先哪个字段排序呢?

如果不需要考虑其它因素时,一般可以选择重复情况更多的字段排到前面。精确地说,如果 T.id(A).len()小于 T.id(B).len(),则先按 A 排序再按 B 排序,占用空间通常会更小。

把有序数据追加进列存组表时,SPL 会自动执行上述方案,只记录一次值和重复计数,不需要使用者干预。

【性能优化】2.5 [外存数据集] 有序及补文件

【性能优化】 前言及目录