[转载]海量关系数据库的压缩存储与查询策略

海量关系数据库的压缩存储与查询策略

摘要:本文针对海量关系数据库的压缩存储和查询的问题，提出了基于同类型的同质属性划分  
的策略，使得关系数据库类型相同和相似的列放在一起进行存储，这种从垂直属性划分派生 u8-#0!!  
出来的方法使得数据可以获得比较大的压缩比，同时解决了垂直属性划分对查询效率的影 gKX>`j  
响。本文还提出了基于同质属性的划分的压缩存储下的关系代数的代价模型的修改，同时提 9 Oc6u \  
出了在这种存储上对原有查询操作实现的修改策略。  H~@Y* sRS  
关键字:压缩数据库 海量数据 同质属性划分 代价模型 查询策略  j:| SHyA  
!j9L kL#5  
1.引言  J_'U$s"  
最近几年，随着信息技术的发展，特别是 Internet 技术的发展，世界各国的信息量都 W>;2,O0  
12 c'xj$
g +g  
呈爆炸性增长趋势，高于 10 字节的海量数据库已成为常见的数据库。例如，美国 NASA 发 /N=7hf$  
15 sY0RN&\.  
射的人造卫星每年要向地面返回10 字节的观测数据。美国劳伦斯国家实验室的高能物理实 `gMar4  
14 k S7c+?  
验数据高达每年3×10 字节。现在Internet 上已经拥有的数据量达到万亿至兆亿字节量级， }-:^G'^  
并且处在不断扩充之中。  rEk!*V.  
海量数据对当前的数据库管理技术提出了挑战。对于海量数据库进行存储当前最主要的 p6VZ2Gz)0  
方法是使用 3 级存储器进行存储[1]和并行存储和查询技术[2]。但是这些方法对于数据的存储 C XcTzC @<  
最大的不足之处在于对于硬件的开销比较大,而且需要开发专门的数据库系统对其进行管理, RHX5y+N%2  
而且他们最本质的思路就是以扩充硬件设备来获取大的存储空间,加大存储容量的同时大大 |'V',~d  
增加的查询的处理时间。并行数据库技术虽然利用多个处理机获取的高速的处理速度，但代 & #Ov
JS  
价是增加硬件开销，而且处理的增长速度要低于硬件设备的处理速度。因此，当前对海量数 AT,hK`FsG  
据库更加经济的一种存储方法是对数据库里需要存储的数据进行压缩，这样一方面可以大大 pqK2#=S  
减小存储容量，另一方面如果对数据库中的数据进行压缩而可以不经过解压缩就可以进行处 U+0Gdt>  
理，可以大大减小磁盘的I/O 数量，而磁盘的I/O 是数据库查询处理的主要瓶颈之一。  IBB0//q  
数据库压缩[3]技术的根据是数据本身存在着冗余，方法是根据数据库的存储模式，对于 1$*YO]b  
特定模式的数据库进行特定形式的压缩。并且数据库压缩技术可以和并行数据库相结合，获 o~"lp;X  
取更高的处理效率。  ~>F 
[4] [5] F0 qR'^s  
对于压缩数据库的压缩和对于一般数据 和多媒体压缩 是有区别的，主要表现在几个 EV5j%m]&t  
需要考虑的问题上：  /WeAF:d3p  
压缩方法选择:压缩数据的查询效率是一个重要的问题，有些常用的压缩方法对 S7,bK*JVlg  
于数据库的直接使用对查询效率的影响非常大，因而需要设计适合于查询的压缩方 du{wyf^%#e  
法。  Gg0j r # 
压缩粒度的选择：根据查询处理方法，数据特点，压缩方法的不同，压缩可以 9D i@  
有不同的粒度，包括基于块[17]，基于表[8]，基于列[9]，基于元组[7]。  Yyw"H D 
查询优化:虽然压缩数据能够减少I/O 时间，但是相应的增加了CPU解压缩的处 \ l! +43  
理时间,如何在各种因素中取得合适的平衡点，从而使查询效率达到最优。  &8.~f}=
 
索引压缩:在很多情况下，对于数据库的操作并非直接作用在原始数据本身，而 R]4?qif  
需要通过索引进行，而索引的规模往往也比较大，有必要对其进行压缩[6].  J[3k*Q14  
通常地说，关系数据库中同一列的数据，往往具有相同得数据类型和取值范围，而这种 ^A 
类型的数据压缩起来往往比较容易。因此，对于关系数据库进行垂直属性划分，对于同质的 ^-_))7,  
数据进行压缩，容易得到更大的压缩比。而纯粹的垂直属性划分，容易增加小规模表查询的 0wz5. '  
I/O 的数量，因而通常使用在数据仓库中[10]，考虑的方法的扩展性，本文可以采取折衷的方 ~veRj4  
法，把性质和类型相同或者类似的列放到同一个文件中进行存储，将哪些列放到一起存储依 TTZ&wJ  
赖于存储代价和查询代价的平衡关系。 
RhHSjM<\2  
在这样的压缩数据上进行查询操作，查询优化中必须考虑解压缩的代价和解压缩后再进 <>pN6M./"  
行 I/O 所带来的代价的增加，因而在这种情况下需要定义新的代价模型。  $6'"1fOGb  
本文的主要贡献包括:  ^s:'QIE$$  
提出了基于同质属性划分的压缩存储方法以及上面的对这种存储方法进行优化 _E;; Nk2   
的模型。   L3_i  
定义了考虑压缩数据的代价模型。  aRt=b  
给出了考虑压缩数据的基本查询操作的实现策略  "nX26b&@  
本文在第2部分讨论了压缩数据的存储方法以及对存储优化的粗略，第3部分讨论了压 Bi>$e/#  
缩数据上的查询优化，第4 部分归纳了相关的工作，第5部分总结全文并且提出了未来的工 OYJs Ff  
作。   s%Pcs'f  
2.压缩存储策略  }U"x2{
[  
由于对于不同的数据采取不同的压缩方法可以得到最高的压缩效率，因此可以考虑把类型和 n~Un(7U/(  
属性相同的数据放到一起进行压缩，垂直属性划分可以确保每类数据具有相同类型和相似的 KlfVsy53d  
取值区间，但是垂直属性划分对于并非大规模的关系数据容易造成查询处理效率的降低，因 YEv~%h/Cm  
此，为了增加压缩方法的可扩展性，我们提出了同质划分的概念，将具有相同或者相近性质 G{A7WC]  
的列存储在一起，以期在不影响查询效率的情况下，获得较大的压缩效率。  OhF*&FACf  
2.1 基于同质划分的压缩  }G 
定义1：关系数据库中的一个关系定义为 R={r1, r2, …, rn},  其中每一个ri称为关系R 的一个 M/X=]$  
列，列 ri的属性用4元组(typei, rangei, keyi，sort_orderi)来描述，其中 typei表示 ri 的数据类型， KZ3.U\8  
rangei表示ri的取值范围，包括实际的取值范围和这个列上面的约束，key表示这个列的键属 kqLf ?W 
性，取值包括主键(prime key)，外键(foreign key), 非键属性(non-key)。Sort_orderi表示这个列 ;L)w)Bayb>  
在存储要求是的排序顺序。  I(B:[3X  
定义 2: 将一个关系 R 中的每一个ri分别进行存储的方法称为垂直属性划分。  )/Awl0I;  
基于垂直属性划分的数据存储可以使相同类型和取值范围的数据一起进行存储，便于压缩， r
[Vy5JgN  
对于一个列ri,具体的压缩方法如下:  4z>(b];io  
rangei为少量有限离散值（比如性别,年龄），不论 typei是什么，都采取字典压缩的方 *+^1X[7]  
法，将rangei进行编码,同时存储字典映射。  ,6Nf{[g  
typei 为纯量 rangei 为区间（比如整型，长整形，浮点数）,如果压缩数据的区间分布 W %Y7d\  
较小，则根据首值取差，将结果限定到一个以 0 为中心的小区间中，这样就起到了缩短 X$XP\ i/  
列存储需要的位数的作用。如果数据分布在一个非常大的区间，则以数据分布的磁盘块 3_"g*@
y  
为单位,这样同一个磁盘块数据分布的区间则变得比较小，可以采取和上面同样的方法进 ~IO|)!79  
行压缩。  }5afk2@#3.  
typei为纯量的复合属性(比如日期，时间)，采取将复合属性变换为矢量，进而对其编 ^yXMsMUN  
码的方法，比如以”dd/mm/yyyy”格式表示的日期可以用 5 位来表示日期，4 位表示月份 YXdB@< _5C  
11位表示年代。  e7} b^~{)G  
typei 为字符串，那么整个列的表示可以采用传统的文本压缩方法进行压缩，比如哈 >b>t'1  
夫曼编码，算术编码，LZW编码[4]等压缩方法，因为这些方法并不对压缩数据本身结构 7SixC,[sN  
产生影响，因而对查询效率的影响仅限于对于查询条件的压缩和结果的解压缩上。而对 } Q@t~:  
于存在排序顺序的字符串属性或者对字符串属性建立的索引则采用保序压缩[14]的方法。  f`7 <WT  
面向垂直属性划分进行的压缩能够获得较大的压缩比，但对查询效率也存在影响，因为 ^HiU- kGQ  
对于有n的列的关系 R来说在进行磁盘块的扫描的时候，在没有投影的情况下，每次至少要 W< *g]k  
装进内存n个磁盘块，这种情况下对于查询结果较小定位比较容易的情况，则会增加磁盘的 e6rWa+  
I/O。正因为此，当前的绝大多数关系数据库产品和工具都是基于水平属性划分的。为了提高 )T
3!]VF  
查询效率，在垂直属性划分的基础上，我们提出的同质属性划分。  8q 
定义3:一个关系R={r1, r2, …, rn}的列可以划分为性质相同的m个类，每一个类的列满足i)相 kLh}+  
同的数据类型，即 typei相同；ii)相同的取值范围，即 rangei相同，这样的类称为同质类。将 R@)a 
一个关系的列按照同质类进行存储的方法称为同质属性划分。  z~A:_zKe  
对于每一个同质属性划分中的数据，按照上面讨论的方法按照不同的数据类型进行压缩，同 EIaYC#
^  
一条记录中的元素临近存储。  1"wE,vS  
2.2 同质划分的优化策略  ;' 8l.h]  
同质属性划分可以取得比较好的压缩效果和查询效果的综合，最理想得情况仍然是关系中的 $quuZ3  
所有列具有相同或者相似的属性，可以使同质划分的同质类尽可能的变大，这样可以获得更 kA["qu=Gi  
好的查询效果。在一些特殊的情况下，可以采用一些策略实现一些异质列的同质化。  !~h-9
k  
策略1（纯量化策略）：一个关系中的列，如果不是纯量列，可以将其通过某种变换映射到纯 {8:\De w  
量的列，比如对于字符串可以使用基于字典的方法，对于复合属性可以采用 2.1 中描述的变 5IyB;C   
换为矢量然后对其进行编码的策略。  4uyBRTs9  
使用纯量化策略，可以使较多的列变成纯量，利于同质化和压缩，但是使用这种策略容易造 ` $LKxhL  
成额外的存储负担，比如字典压缩的字典的存储。而额外存储负担的代价是可以根据数据库 \V g[ l+ A  
的统计属性进行计算的，比如字符串属性的字典压缩可以根据这个属性的分布来估算字典的 lzT;u`4  
大小，因此可以通过计算确定是否应当对一个列进行纯量化。  d?eHld%fb  
策略 2(矢量量化策略):如果多个列之间存在某种关联(可能是偶然关联),使得每条记录中这些 1~z:U_rZ  
列的值构成的矢量可以被量化成一个纯量的值，对这样的列集合可以进行矢量量化。  xWWXrCv[P  
矢量量化策略可以有效的将多个异质的列合成一个纯量的列，但是代价是需要矢量对应表， #2#^Af  
同样可以根据数据库的统计性质计算对这些列进行矢量量化是否经济。  k8++I  
压缩对于查询的支持除了同质化之外，还可以根据查询的统计特征确定同质划分的方式，也 [Nz=nuEc  
就是说，经常放在一起查询的对象或者条件应当进行划分，使得查询效率得以提高。  aJd!le  
策略 3(共现查询策略):如果多个列之间存在某种关联，使得这些列在查询中经常性的共同出 T@!G{ J)  
现，则应当将这些列作为一个整体进行存储。  pE&
H]/  
使用共现查询策略进行划分存储可以优化查询效率，但是代价是容易造成非同质的数据被放 7: }`h g  
到一起存储，使得压缩效率降低。为了做是否使用这种策略的判定，需要为查询时间代价和 +bKzzB'  
存储代价各设定一个权值，计算在不同的策略下的存储代价和查询代价。其中存储代价用数 +  h)[Y1  
据的统计信息计算压缩数据的代价，限于篇幅，具体的估算策略从略；查询执行代价同样使 Uavngj aU  
用统计数据，计算在发生频率下各种操作的的平均 I/O 和CPU时间。由于通常一个关系中的 gKc^UL  
列数量并不是很多，能够在查询中经常共同出现的列更少，因而有效的查询空间不会很大， nQ9S 2)r  
从而判定根据共现查询进行数据分布的算法的搜索空间将会很小，从而方法可行。  OWK$>q1D ~  
3.压缩数据上的查询策略  6L^WE8Q/  
压缩数据的查询计划需要考虑压缩和解压缩的操作代价和执行时间，因为压缩的数据可以减 Vr\0DTWqu  
小 I/O,但对于值的比较，特别是非等值的比较，在使用一些压缩方法的情况下不能在压缩的 >7 zf&Ax  
数据上直接进行，需要进行解压缩。这样就引起了查询代价模型的变化，因此，在这一部分， M
.tE+  
首先讨论对代价模型的修改，继而讨论在修改的代价模型下进行查询优化以及查询执行的策 kZ*  
略。  .%lESGtV
 
3.1 修改代价模型  Z&<`h1Hf(  
[26] &olM!S  
因为传统的关系代数操作的代价模型包括代价的估算方法 已经相对成熟，因此代价模型及 &l[F4'C  
其代价估算方法继续沿用关系代数操作的框架，只在涉及到压缩的部分加以修改。  0Jy!5-TB3  
修改1 投影操作的代价：由于同质属性划分是基于垂直属性划分的，因此投影操作的代价将 z)= zXZT  
变小，投影操作的代价仅为对涉及查询的同质类进行投影操作的代价。  'N!y.   
修改2 I/O 的代价：因为将压缩数据读进内存的 I/O 数量比未经过压缩的数据要小得多，而进 ga^wk'0?\  
行同质划分之后的数据一次读进内存的磁盘块需要包含对应位置的所有列，同时由于同质划 /=I:P  
分的同质类中包含的列数量不同,因而对一个关系的处理需要保证每个同质类纳入内存的同 `mk<}(Wqb  
步。从而在压缩的情况下对于 I/O 的估算变得比较复杂，对于一次关系的扫描，我们定义这 Nu9O3j$} c  
样的 I/O 代价，假定存在 k 个同质类，其中 k’个进行了压缩，同质类 i 中经过投影可用的列 4 |q |`$a0  
数量为Ui,需要扫描的元组数为n,每个块的大小为B 则执行一次扫描I/O 的数量为  [`ff."M  
μU n U n 5F+\9'Xc9  
i i i |m1zJc  
+ ,其中μi是第 i个同质类的压缩比，这个值通常需要一个根据数据库中对相应 t#(U+;%!w  
∑ B ∑ B J p.5F}Ef  
' ' %}^{iW-  
k k-k H/h]=A  
列分布的统计计算得出。  _a]L;6  
修改3  增加压缩和解压缩操作的代价：解压缩操作可以放在不同的位置，包括将数据第一次 \3U~.^i  
读进内存的时候，对数据进行排序的时候，进行选择，join 或者聚集操作的时候以及数据最 P<>1X$y`F  
后输出的时候；压缩操作存在于需要将数据写入磁盘之前。解压缩操作的代价定义为解压缩 d7ar0  
方式的解压代价权β×T(Ci)×Col(Ci), T(Ci)是同质类Ci的元组数量，Col(Ci)是 Ci的列数量。 m0 <_8rl  
不同类型的数据由不同的β；同样的压缩操作的代价为α×T(Ci)×Col(Ci)，除了α表示对应 L$_E/&mK1  
数据类型的压缩代价，其他元素的含义和解压缩操作相同。  ,\p ! I>*  
修改4 对于压缩数据和非压缩数据操作代价的不同: 对于压缩得数据，执行代数操作代价的 '%3>xj  
差别不仅仅体现在 I/O 数量上，CPU时间也有所不同，通常某个操作对于一个类型的压缩数 R!|G|ahHa  
据的处理所增加的CPU 时间的倍数是一个固定的值，因此对于每个数据类型Type的数据上 g1{6|"_  
的操作γ，需要定义一个 CPU 时间系数γType,压缩数据上操作的 CPU 时间代价为γType× \qMY)WyoE  
CPU_Costγ.  \z@{5N)  
基本的查询优化算法适用于利用修改的代价模型进行查询优化，需要注意的是压缩和解压缩 :y!pn4a'H  
操作的插入位置对于查询效率的影响，压缩操作和解压缩操作对于任意操作符都满足交换 %N*O9~r>  
律。  >w!H9&'U  
3.2 压缩数据上查询操作实现  c&!'Cq{f  
对于压缩数据库的查询操作同时包含对于压缩数据的查询操作和非压缩数据的查询操作。这 1x\r'DSG  
里只讨论对于压缩数据的查询操作，对于不同类型的数据的操作方法有所不同，分情况进行  qbr[;3Z  
[26] z^RaK;.  
讨论，算法的基本框架和非压缩数据上算法 的类似，仅仅个别细节有所不同，这里仅仅给 V3ax`t7R  
出需要修改得地方。在这种存储结构下，投影操作变得非常简单在 3.1 中已有描述，这里不 C[][U  
加以讨论了。基于散列的算法基本没有变化，因此不加以详细讨论。  :)Hyi> W1H  
一次扫描算法  T1.;(j

 
这个类型的算法对于需要操作的元组进行一次扫描。  (E]Ac`Y  
通常的集合操作并交叉，对于任意一种类型的数据，都是基于查找的，由于对于所有数据类
v+C&>,?Y  
型的压缩操作都是一一对应的映射，所以对于压缩数据不需要经过修改。可以直接操作。在 D++?T">C  
选择操作中，需要修改选择的值，也就是说，对于压缩数据的选择需要变换到经过压缩变换 I[V)@J ,iX  
之后的值上去，在对纯量值进行压缩的时候，压缩变换会引起取值序的变化，但这种变化仅 wD%
+Uq_  
仅是反序的，只需要把比较符号取反。而对于字符串的变换，对于非等值的比较如果压缩不 |b WL=N  
[14] E1TzE[rGb-  
是保序 的，那么需要把查询对象解压缩进行比较，否则可以直接比较。  /- 6S  
基于排序的二次扫描算法  ;mSi@Y85  
对于需要排序的情况，上面考虑的序关系经过压缩变换之后的变化问题是需要考虑的，因而 M|dUai  
通常情况下，压缩并不增加排序算法的复杂度，相反的，压缩可以较少外排序的 I/O 数量， :'Pg@ K#y  
可以加快排序的速度。需要注意的是经过量化的复合属性，需要选择良好的能够保持原有符 S)x-O96  
合属性序关系的编码方法。  N DLN( OI  
聚集操作  WZ1,!$"/%  
5 种基本的聚集函数中，NUM 和原来的统计方法相同；对于 SUM 和 AVG 对于经过压缩的 y*]5q.  
纯量数据，需要累加聚集列压缩的时候减去的值；对于MAX和MIN,仅仅需要考虑经过压缩 +EWGVU]V  
序关系的变化情况。  }]ib/q/w  
根据上述讨论可以看出，在基于同质划分的压缩数据上进行查询，对查询操作实现的影响非 5,S[fpee  
常有限，可见，这种压缩算法适用于对关系数据库的压缩。  b`mC- w_[&  
4.相关工作  +/s\wEr  
[11][12][13]是对压缩数据库的早期研究工作，主要集中在科学统计数据库上，这些方法提供 jrYEk.)  
了压缩和被压缩数据之间的向前和向后两种映射函数，减少了每个压缩数据的解压缩时间， Ga}j?  
使之比较适应于数据库的随机存取模式。  6g yj6  
近年来，随着数据量的增大，压缩数据库的研究逐渐多了起来。一种方向是研究数据库中元 0oceq_j  
素的压缩方法.[14][15]提出了适用于压缩数据库的字符串保序压缩技术.[16]讨论了利用 i6h!1|l  
矢量量化的方法，对于具有特殊性质的数据块进行压缩，以及在这种压缩方法下的数据操作 f RYx<|_9U  
方法。  }Wv{; -b  
另一个研究方向从整体上对数据库进行压缩,整合现有的压缩方法或者通过数据库元素之间 (,$u^jkE9  
的关系对关系数据库进行压缩.[7]根据块内属性的取值范围限制进行压缩，同时利用类似方 S@5Z

C  
法对B树和R树进行了压缩.[9]面向超大的数据表格，根据列与列之间的关系进行压缩。[8] PRU> XCv  
给出了对于查询结果的表进行分块压缩的方法，但是没有考虑查询效率。[29]提出了利用数 ~} um!  
据挖掘中的相关规则挖掘获取列之间的关系来进行压缩。  WbI$R{N  
有对于压缩数据库进行查询优化的相关研究，但工作不是很多。[24]讨论了基于位图索引的 m{E"]2P0  
代价模型和查询优化算法。[28]研究了压缩数据上的查询优化方法，提出了解决压缩/解压 jot-L8t  
缩时机选择的问题。  9Z6Q)M,m3  
考虑到数据库索引的特殊地位,也有一部分研究是针对数据库索引进行压缩的.[7]中提出了 / \*$#  
将B树和R树用属性元组来表示进而通过类似矢量量化的方法对其进行压缩。[23]对位图索 V+DS*LSYvb  
引进行了研究，提出了对压缩位图索引的压缩算法.[25]讨论了对于多维索引的压缩以及在 gDvP`"Yi  
其上进行的操作方法。  C'p1=}d  
数据仓库有着特殊的存储形式同时常常有着海量的存储,也有一些工作集中在对多维数据库 Lvmk"haG  
进行压缩以及压缩的多维数据库上的查询处理.[21]研究了在无需解压缩的情况下对多维数 4-cU4z>:  
据进行聚集的算法.在[22]中讨论了在压缩的数据仓库上实现聚集操作的并行算法.[17]面 HI"bRbe0'  
向科学与统计数据库综合了现有的数据库压缩得方法,提出了基于块的压缩数据库及其上的 ?@RVL0i  
数据操作.  :W
fqGIc  
当前由于 web 逐渐成为研究的热点，也有一些压缩工作是面向 web 和 IR 的。[18]提出了面 g~:iejg  
向文本数据库的文本压缩方法。[19]提出了在压缩的文本上进行快速近似查询的算法。对与 9HO/UKvL  
信息检索中一种重要索引倒排表的压缩方法在[20]给出。[27]讨论了对于 web 网站数据的压 J X}dx:|51  
缩方法。  1rbst`*  
5.结论和进一步的工作  SFwu0#A  
本文提出了对于海量的压缩关系数据库基于同类型的同质属性划分的策略，使得关系数 s`Y98q5 P  
据库类型相同和相似的列放在一起进行存储，这种从垂直属性划分派生出来的方法使得数据 ?5W~2M"Y  
可以获得比较大的压缩比，同时解决了垂直属性划分对查询效率的影响。本文还提出了基于 E6f 0Y  
同质属性的划分的压缩存储下的关系代数的代价模型的修改，同时提出了在这种存储上对原 G2|  
有查询操作实现的修改策略。本文提出的压缩存储方法和上面的查询优化和查询执行策略适 , Vot1  
用于海量的压缩关系数据库，适用于各种压缩数据库的多种情况。  nRP%Qb  
本文提出的代价模型的修改和查询操作实现的修改是针对通常的同质属性划分进行的， FiYJLxCvW,  
并没有考虑优化的情况，下一步的工作是建立自适应的压缩存储算法，并且建立对于压缩数 )P}_h19  
据库的查询执行效率和压缩比之间的关系。  Yuv%[U)