（计算机应用技术专业论文）基于支持列存储的数据压缩算法研究.pdf

硕j 二论文 支持列存储的数据压缩算法研究 摘要 由于日益庞大的业务处理，许多决策系统和o l a p 系统的数据正在朝着t b 数量级发展。面对各种存储了海量数据的巨型表，如何充分利用存储空间，节省 系统维护成本，在查询海量数据时取得更好的性能，引起了数据库研究者们越来 越多的关注。而将数据压缩技术引进数据库系统，成为了解决大数据量环境下数 据库性能问题的有效手段之一。 在传统的关系型数据库中，数据均是按行存储的( 行存数据库) ，即关系表 中同一条记录的不同属性值被依次顺序存放在物理磁盘上。遗憾的是，由于记录 中不同的属性值通常取值于不同的值域，彼此间的相关性很小，导致按行存储的 数据存储方式并不利于数据压缩的实现。 列存数据库消除了行存数据库在数据压缩领域的不利条件。在列存数据库 中，连续存储的数据均来源于同一个值域，而对同一个值域内的数据进行压缩正 是各种经典数据压缩算法实现的前提和关键。为此，本文对如何将各种经典的数 据压缩算法融入列存数据库进行了研究。 首先，本文阐述了列存环境下数据压缩的重要意义，并对数据压缩技术的发 展历程和国外主流列存商业数据库的现状进行了分析；其次，综述了数据压缩的 相关概念以及列存数据库在数据压缩领域的巨大优势，并详细讨论了各种经典的 数据压缩算法，具体包括了赫夫曼编码、算术编码、l z 7 7 算法、l z w 算法、r l e 算法和空值压缩算法等。 随后，本文深入研究了列存压缩运算库的结构设计。列存压缩运算库由压缩 数据物理存储机制、压缩模块和数据源模块三个部分构成。其中，物理存储机制 描述了不同压缩数据在列存数据库中同时存储的合理方案，是列存环境下各种压 缩算法实现的必要保证；压缩模块则封装了具体压缩算法的细节，并负责对外提 供统一的解压接口；而数据源模块扮演着通信媒介的角色，为压缩模块与数据库 存储层之间的消息和数据传递提供服务。此外，通过归纳各种压缩数据的属性， 本文对传统的数据库执行器算子进行了相应的改进，从而实现了压缩数据在压缩 态下的直接查询。 最后，本文以国产数据库神舟o s c a r 为平台，具体实现了上述各项关键技 术。通过对相关的性能测试结果进行对比分析，验证了本文所述内容的正确性和 有效性，在减少列存数据库存储规模的同时，进一步自动优化了数据库系统的性 能。 关键字：数据压缩；列存数据库；列存压缩运算库；压缩态下的数据查询 a b s t r a c t 硕 论文 a b s t r a c t b e c a u s eo ft h eg r o w i n gb u s i n e s so p e r a t i o nn o w a d a y s ，t h ed a t as t o r a g eo fm a n y d e c i s i o ns u p p o r ts y s t e m sa n do l a ps y s t e m sb e c o m e sm o r ea n dm o r eu n a c c e p t a b l ea s i ti sg r a d u a l l yc l o s et ot bl e v e l i nt h ef a c eo ft h et a b l e sw h i c hh o l dt h eh u g ev o l u m e o fd a t a , h o wt ou s et h es t o r a g em o r ee f f i c i e n t l ya n dc u td o w nt h ec o s to fm a i n t e n a n c e f o rab e t t e rp e r f o r m a n c ew h e nq u e r yo nt h eh u g et a b l et u r n si n t ot h ef o c u si nt h e d o m a i no fd a t a b a s er e s e a r c h c e r t a i n l y , o n eo ft h ee f f i c i e n tm e t h o d st or e s o l v et h e a b o v ep r o b l e m si st oi n t r o d u c et h ed a t ac o m p r e s s i o nt e c h n o l o g yi n t ot h ed a t a b a s e s y s t e m i nt h en o r m a lr e l a t i o n a ld a t a b a s es y s t e m ，d a t ai so nt h eb a s i so ft h er o wt ob e s t o r e d ( r o w - s t o r e ) ，w h i c hm e a n st h a tt h ev a l u e so fd i f f e r e n ta t t r i b u t ef r o mt h es a m e t u p l ea r es t o r e dc o n s e c u t i v e l y h o w e v e r , b e c a u s eo ft h el o w e rc o r r e l a t i o nb e t w e e nt h e d i f f e r e n ta t t r i b u t ev a l u e st h a tc o m ef r o mt h ed i f f e r e n tr a n g e s ，t h ed a t ac o m p r e s s i o n t e c h n o l o g yi sn o te a s yt oi m p l e m e n ti nt h er o w - s t o r ed a t a b a s es y s t e m t h ed i s a d v a n t a g e sh a v eb e e ne l i m i n a t e di nt h ec o l u m n s t o r ed a t a b a s e a c o l u m n - s t o r ed a t a b a s es y s t e mi so n ei nw h i c he a c ha t t r i b u t ei ss t o r e di nas e p a r a t e c o l u m n ，s u c ht h a ts u c c e s s i v ev a l u e so ft h a ta t t r i b u t ea r es t o r e dc o n s e c u t i v e l yo nd i s k t h ec h a r a c t e r i s t i co ft h es i m i l a r i t yo fa d j a c e n tv a l u e si nc o l u m n - s t o r ed a t a b a s es y s t e m i su s e f u lf o ra l lk i n d so fc l a s s i c a ld a t ac o m p r e s s i o na l g o r i t h m s c o n s e q u e n t l y , w e d i s c u s sh o wt h e s ec l a s s i c a la l g o r i t h m sc a nb ei n t e g r a t e di n t oac o l u m n - s t o r ed a t a b a s e i nt h i sp a p e r f i r s t l y , t h ei m p o r t a n c eo fd a t ac o m p r e s s i o nu n d e rt h ec o l u m n s t o r ec o n d i t i o n , w i t l lt h ed e v e l o p m e n th i s t o r yo fd a t ac o m p r e s s i o na n dt h ep r e s e n ts i t u a t i o no ft h e f a m o u sc o m m e r c i a lc o l u m n - s t o r ed a t a b a s e sa b r o a d ，h a v eb e e ne l a b o r a t e d s p e c i f i c a l l y , a f t e rt h es u m m a r i z a t i o na b o u tt h er e l e v a n tc o n c e p t so fd a t ac o m p r e s s i o n a n dt h ea d v a n t a g e so fc o l u m n s t o r ed a t a b a s e ，w ed i s c u s sv a r i o u sd a t ac o m p r e s s i o n a l g o r i t h m s ，i n c l u d i n gh u f f m a ne n c o d i n g ，a r i t h m e t i ce n c o d i n g ，l z 7 7a l g o r i t h m ， l z w a l g o r i t h m ，r u n l e n g t he n c o d i n g ( r l e ) ，n u l ls u p p r e s s i o na n ds oo n s e c o n d l y ，w em a k e as t u d yo ft h es t r u c t u r a l d e s i g n f o rc o l u m n - s t o r e c o m p r e s s i o nl i b r a r y , w h i c hi sc o m p o s e do ft h es t o r a g em e c h a n i s m ，t h ec o m p r e s s i o n m o d u l e ，a n dt h ed a t a s o u r c em o d u l e t h es t o r a g em e c h a n i s mp r o v i d e sg u a r a n t e ef o r t h er e a l i z a t i o no ft h o s ec o m p r e s s i o na l g o r i t h m sb e c a u s et h a ti td e s c r i b e sar e a s o n a b l e 硕1 ：论文基于支持列存储的数据乐缩算法研究 s o l u t i o nt ot h es t o r a g eo fd i f f e r e n tc o m p r e s s e dd a t ai nc o l u m n s t o r ed a t a b a s e t h e c o m p r e s s i o nm o d u l ee n c a p s u l a t e sc o m p r e s s i o nd e t a i l sb yp r o v i d i n gs t a n d a r di n t e r f a c e f o re x t e r n a lm o d u l e s a n dt h ed a t a - s o u r c em o d u l ep l a y st h er o l eo fc o m m u n i c a t i o n b e t w e e nt h ec o m p r e s s i o nm o d u l ea n dd a t a b a s es t o r a g el a y e r b e s i d e s ，b ye v a l u a t i n g t h ea t t r i b u t e so fd i f f e r e n tc o m p r e s s e dd a t aa n di m p r o v i n gt h et r a d i t i o n a ld a t a b a s e e x e c u t o ro p e r a t o r , w ea l s od e s c r i b eh o wt h eq u e r ye x e c u t i o ne n g i n ec a nr e t r i e v ed a t a d i r e c t l yf r o mc o m p r e s s e dd a t aw i t h o u td e c o m p r e s s i o n ( c o m p r e s s i o ns t a t eq u e r y ) f i n a l l y , w i t hs h e n z h o uo s c a rd a t a b a s ea st h ep l a t f o r m ，w ei m p l e m e n tt h e a b o v ek e yt e c h n o l o g i e s o nt h eb a s i so ft h ea n a l y s i sa n dc o m p a r i s o no nr e l e v a n t p e r f o r m a n c et e s t i n gr e s u l t s ，b o t hv a l i d i t ya n de f f e c t i v e n e s so fo u rr e s e a r c hh a v eb e e n t e s t i f i e d ，w h i c hc a nn o to n l yr e d u c et h ea o r a g es i z eo fc o l u m n - s t o r ed a t a b a s e ，b u t a l s oo p t i m i z et h ed a t a b a s es y s t e mp e r f o r m a n c ea u t o m a t i c a l l y k e y w o r d s ：d a t a c o m p r e s s i o n ；c o l u m n - s t o r ed a t a b a s e ；c o l u m n - - s t o r e c o m p r e s s i o nl i b r a r y ；c o m p r e s s i o ns t a t eq u e r y i l i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均己在论文中作了明 确的说明。 研究生签名：v ( 。年月z 咽 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：沙c 。年月乙咽 硕l 二论文 基于支持列存储的数据压缩算法研究 l 绪论 1 1 课题来源 本课题来源于国家“核心电子器件、高端通用芯片及基础软件产品 ( 核高 基) 科技重大专项大型通用对象关系数据库管理系统( o s c a r ) 的研制及 其应用。 1 2 课题研究意义 列存数据库采用了列式存储体系结构，主要适用于批量数据处理、实时查询、 以及为决策层提供支持的数据仓库发掘【l j 。从1 9 9 4 年前后列式存储体系结构的 概念被提出以来，伴随着人工智能、数据仓库发掘、云计算等新兴技术的发展， 国外先后出现了s y b a s ei q 、s e n s a g e 、c s t o r e 、v a l e n t i n ad a t a b a s e 等著名的商业 列存数据库管理系统 2 1 。而随着各种开源列存数据库代码的迅速推广，比如： r c 2 1 、x p l a i n 、c a l p o n t si n f i n i d b 等，也进一步促进了列存数据库技术的成熟和 完善。通过列存数据库可集成产品计划、维护管理、专家系统、实验室信息系统、 模拟与优化等应用程序，在实际应用中的各种业务管理和决策支持之间搭建起快 速沟通的桥梁【3 】。目前，列存数据库已广泛应用于工业控制、企业m e s 、公用工 程、环境、地理、智能交通、智能楼字、通信等领域1 4 j 。 近年来，国内很多高校和研究部门也掀起了对列存数据库研究的热潮，但对 列存数据库理论的研究主要集中在事务的优先级分派、调度和并发控制的协议与 算法；系统资源调度、恢复、通信的协议与算法等掣5 1 ，而对制约列存数据库发 展的瓶颈：比如文件的索引和数据的组织结构、以及由于压缩态数据查询引起的 磁盘i o 等问题没有深入的研究。在实际应用中，特别是在积累了大量历史数据 的环境下( 比如数据仓库) ，数据具有数据量大、存储格式简单固定、保存时间 间隔差距大、查询性能要求高的特点。因此，对列存数据库的开发始终围绕着三 大方面1 6 l ：首先，要求能够高效地存储海量的压缩数据，系统存储数据的速度必 须超过数据上传的速度，而且不能因为在短时间内输入大量的数据而失去对其他 事件的响应。其次，在列存数据存储、查询的流程和结构上需要做特别的优化， 以满足高速数据存储和查询的要求。最后，为满足列存数据文件最小化的要求， 数据存储前必须进行有效的压缩，但同时必须确保高效的压缩数据查询效率。 l 绪论硕上论文 因此，设计一个好的文件存储结构，并将数据压缩技术引入列存数据库中， 对列存数据库整体性能的提高有很重要的作用。 1 3 国内外研究动态 1 9 4 8 年信息论之父c e s h a n n o n 发表的论文“通信的数学理论( a m a t h e t n a t i c a lt h c o r yo fc o m m i n i c a t i o n ) 7 】 中指出，任何信息都存在冗余，冗余 大小与信息中每个符号( 数字、字母或单词) 的出现概率不确定性有关。s h a n n o n 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵【8 1 ， 并给出了计算信息熵的数学表达式。这里借用“熵”来表示一条信息中真正需要 编码的信息量。 考虑用0 和1 组成的二进制数码为含有n 个符号的某条信息编码，假设符号 f n 在整条信息中重复出现的概率为p n ，则该符号的熵也即表示该符号所需的位 数为：e n = 1 0 9 2 ( p n ) ，整条信息的熵( 即表示整条信息所需的位数) 为：e = e e n 。 这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压 缩算法的理论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而 信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵 公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编 码长度不可能小于信息熵公式给出的结果。 第一个实用的编码方法是由d a h u f f m a n 在1 9 5 2 年的论文“最小冗余度代 码的构造方法【9 1 ”中提出的。直到今天，许多“数据结构”教材在讨论二叉树时 仍要提及这种被后人称为赫夫曼编码的方法。赫夫曼编码看似简单，但却影响深 远，其编码效率高，运算速度快，实现方式灵活，从2 0 世纪6 0 年代至今，在数 据压缩领域得到了广泛的应用。 1 9 6 8 年前后，p e l 协发展了s h a n n o n 和f a n o 的编码方法，构造出从数学角 度看来更为完美的s h a n n o n f a n o e l i a s 编码。沿着这一编码方法的思路，1 9 7 6 年， j r i s s a n e n 提出了一种可以成功地逼近信息熵极限的编码方法算术编码【1 0 1 。 1 9 8 2 年，r i s s a n e n 和g g l a n g d o n 一起改进了算术编码。之后，人们又将算术编 码与j g c l e a r y 和i h w i t t e n 于1 9 8 4 年提出的部分匹配预测模型( p p m ) 相结合， 开发出了压缩效果近乎完美的算法。今天，那些名为p p m c 、p p m d 或p p m z 并 号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。 2 硕十论文基于支持列存铭的数据压缩算法研究 犹太入j z i v 和a l e m p e l 脱离h u f f m a n 及算术编码的设计思路，创造出了一 系列比赫夫曼编码更有效，比算术编码更快捷的压缩算法。这些算法统称为l z 系列算法，如：l z 7 7 算法【1 1 1 、比l z 7 8 算法【1 2 1 、以及l z w 算法【1 3 1 。该系列算 法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们 只是用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。这种基于字典 模型的思路在表面上虽然和s h a n n o n 、h u f f m a n 等人开创的统计学方法大相径庭， 但在效果上一样可以逼近信息熵的极限。而且l z 系列算法在本质上符合信息熵 的基本规律。l z 系列算法的优越性使得使用该算法的压缩软件数量呈爆炸式增 长。今天，我们熟悉的p k z i p 、w i n z l p 、w i n r a r 、g z i p 等压缩工具以及及z i p 、 g i f 、p n g 等文件格式都是l z 系列算法的受益者。 1 9 9 4 年，m b u r r o w s 和d j w h e e l e r 共同提出了一种全新的通用数据压缩算 法。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换，类 似的变换算法被称为b u r r o w s w h e e l e r 变换，简称b w t 。与z i v 和l e m p e l 另辟 蹊径的做法如出一辙，b u r r o w s 和w h e e l e r 设计的b w t 算法与以往所有通用压 缩算法的设计思路都迥然不同。如今，b w t 算法在开放源码的压缩工具b z i p 中 获得了巨大的成功，b z i p 对于文本文件的压缩效果要远好于使用l z 系列算法的 工具软件。这至少可以表明，即便在日趋成熟的通用数据压缩领域，只要能在思 路和技术上不断创新，我们仍然可以找到新的突破口。 数据压缩技术在发展的过程中逐步出现了通用压缩技术结合某些专用领域 的专用压缩技术。列存数据库的实现离不开数据压缩技术，列存数据压缩是数据 压缩技术在列存数据库这一特定领域中的一种特定应用，正如图像压缩【1 4 1 、音 频压缩1 5 1 、视频压缩【阍、医学数据压缩切、空间信息压缩1 羽等是数据压缩技术 在其它领域的特定应用一样。虽然列存数据库的许多压缩算法都脱胎于传统的压 缩技术，可以直接使用这些己在很多领域中得到证明的行之有效的压缩算法，但 是，因为列存数据库的数据有着其特定的特性和规律，所以研究适应于列存数据 库数据要求的压缩算法不仅是可行的，更是必要的。 下面我们将介绍国外两种应用较为广泛的列存数据库，以及它们所采用的压 缩方法。 1 s y b a s ei q 1 9 1 s y b a s ei q 是与m i c r o s o f ts q ls e r v e r ，o r a c l e 和i b md b 2 一样的关系型数据 l 绪论硕i ：论文 库管理系统，它最初是e x p r e s s w a y 公司作为查询加速器推出的，后来s y b a s e 收 购了该产品，发现将其技术作为独立的数据仓库产品远比集成到s y b a s ea s e 更 有市场。对于许多高性能要求的查询，特别是对于大量的实时查询( 非预定义的 查询) ，s y b a s ei q 的技术特性比传统的关系型数据引擎更有优势。这些优势得益 于一点：s y b a s ei q 完全是为决策支持数据库设计的，并不只是简单地为o l t p 数据库添加决策支持功能。特别是s y b a s ei q 按列存储和超强压缩的技术特性， 极大地提高了查询引擎的性能。 在s y b a s ei q 中，传统数据库中基本表的元组是不存在的。s y b a s ei q 通过对 元组进行垂直分割，把基本表的元数据信息存储在了目录存储空f 司( c a t a l o gs t o r e ) 中，并将其中的每个字段建立成缺省的f p 索引。因为s y b a s ei q 只存储索引， 并不按行存储表的基础数据，所以s y b a s ei q 即可以像传统的索引一样利用这些 索引查询，也可以把这些索引当作基础表的字段一样作为数据源访问的基础数 据。因此，s y b a s ei q 中的每个查询只需要读查询语句中涉及的字段的信息，不 必像传统数据库那样访问表中的所有字段。而通过为用户提供标准的s q l 界面， s y b a s ei q 将其特殊的物理结构和复杂索引封装了起来，从而使其从外表上看和 其他的关系型数据没有区别。 在传统的数据库中，为提高查询性能所建的索引占用的磁盘空间往往比数据 本身需要的磁盘空间多出3 1 0 倍。而在s y b a s ei q 中，数据库在完全索引的情况 下只占a s c i i 裸数据大小的5 0 到1 2 0 。智能压缩技术与精巧的索引结构和列 存储结合，决定了s y b a s ei q 能够比其他数据库引擎得到更优的压缩效果，使得 s y b a s ei q 对按列存储的数据的压缩率通常能大于5 0 。由于多种压缩技术的混 合使用，一方面使得s y b a s ei q 在一个页面上可以比传统数据库存储更多的数据， 另一方面也进一步减少了磁盘i o ，节省了磁盘带宽。此外，s y b a s ei q 的这一压 缩能力不但可以节约空间，还可以带来查询性能上的优势，因为对于任何给定的 数据库块，系统仅需很少的磁盘i o 读取或写入数据即可。总之，大的压缩比例， 加上大页面的f o ，在减少s y b a s ei q 对存储空间的需求的同时，也确保了s y b a s e i q 优良的查询性能。 2 s e n s a g e s e n s a g e 是一种企业级的列存数据库，一个典型的s e n s a g e 系统含有以下几 个组成部分：具有各种采集接口的s e n s a g e 数据采集器、s e n s a g e 服务器、s e n s a g e 4 硕i j 论文基于支持列存储的数据胝缩算法研究 w e b 管理器、s e n s a g en a n w e b 管理器、s e n s a g eo l d d bp r o v i d e r 、安装在任何 客户节点上的一个或多个e x c e l 加载宏、用s d k 编写的程序。所有的客户端通 过s e n s a g ea p i 访问服务器。 s e n s a g e 数据采集器是数据源和数据归档之间的接口，它们通过各类专用接 口，如i f i xe d a 、o p c i 0 或2 0 来采集数据，需要时提供自动负载平衡，并执 行第一级数据压缩；当服务器连接中断时，缓冲数据。s e n s a g e 的第二级数据压 缩采用l z 系列压缩算法，由s e n s a g e 服务器执行。 s e n s a g e 具有强力的数据压缩和毫秒级的时间标记分辨率。利用第一级数据 压缩和变化率压缩等技术，s e n s a g e 列存数据库可以在不影响性能的情况下，单 台服务器自动平衡负载采集1 4 4 0 0 0 个数据点，且具备利用最小的数据记录文件 提供每秒2 0 0 0 0 个事件的回取能力。数据采集压缩率和数据存储的变化率可以由 管理人员自由配置。所有在s e n s a g e 列存数据库里的时间标记都可达到毫秒级分 辨率，且任何数据的储存都可在此等级，多个采集器的时间标记都可以与服务器 的时钟同步。 1 4 课题研究方法和论文组织 目前，关于各种通用数据压缩算法在列存数据库中的具体实现和应用，国内 尚处于起步阶段，可参考的文献技术资料稀少。在国外，一方面，各种开源的列 存数据库由于受到资金、人力资源和实践检验的约束，导致其自身的设计与实现 均存在着各种各样的缺陷，因此这些开源数据库的数据压缩实现方案仅仅只能作 为一种参考和借鉴；另一方面，尽管国外各大商业列存数据库系统均已各自实现 了功能强大的数据压缩运算库，但与之相关的文献论述都只是涉及到数据库的功 能介绍和使用而已，具体到实现结构、设计思想等关键技术，都是各大数据库厂 商的商业机密，不可能为外界所知。 基于上述现实情况，本课题的研究将首先通过查阅相关技术资料，综合比较 国外各大商业列存数据压缩运算库在功能和性能上的差异。然后详细分析o s c a r 列存数据库的实现机制，评估国外列存数据库的各种数据压缩方案在o s c a r 列存 数据库上实现的可行性及其难度。之后对国外各种开源列存数据库的相关技术路 线进行研究，参考并借鉴先进技术和算法。最后结合o s c a r 列存数据库自身的特 点，提出各项关键技术的解决方案，并通过工程实践的方式在o s c a r 系统上进行 5 i 绪论 硕1 ：论文 验证。 综上，本文的论文组织结构如下： 第一章绪论，对列存数据库及数据压缩的基本概念进行阐述，分析了列存数 据库中数据压缩技术的研究现状。 第二章首先综述说明了在数据库系统中引入数据压缩技术的利弊，同时阐述 了行存数据库和列存数据库在数据压缩方面的优势和劣势，接着研究了现有的各 种通用无损数据压缩算法，并对它们各自的压缩解压性能进行了分析和比较。 第三章设计了一个适用于各种压缩数据的存储结构，并基于此结构实现了对 各种压缩数据长度信息的编码和解码。同时通过对数据库执行器体系结构进行扩 展，增加了两个和数据压缩相关的功能模块，以确保在将第二章介绍的各种通用 无损数据压缩算法融入列存数据库的同时，不仅可以避免系统产生如“性能瓶颈 转移 、“代码复杂度增加等影响系统效率和稳定性的不利因素，而且还能充分 利用压缩数据的特性，实现压缩态下的数据查询。 第四章为神舟o s c a r 列存压缩数据库管理系统的实现和实验验证部分。首 先，我们对神舟o s c a r 列存压缩数据库管理系统的体系结构进行了完整的介绍。 由于压缩和解压数据的过程位于整个o s c a e r 体系结构的数据库内核底层，所 以接下来我们详细说明了o s c a r 列存压缩数据库的存储模式设计和执行器模块 设计。最后，在不同类型的数据查询环境下，我们测试、比较、分析和论证了本 文介绍的各种通用数据压缩算法在o s c a r 列存数据库实际应用中的效果。 第五章为总结与展望，在总结本文研究成果的基础上，对列存数据库及其压 缩技术提出一些前瞻性的展望。 6 硕上论文基于支持列存储的数据压缩算法研究 2 列存数据库中数据压缩算法的研究 2 1 数据压缩综述 所谓数据压缩，就是用最少的代码来表示原始数据，即将数据的一种表示方 式转换为另一种表示方式，新的表示方式包含相同的信息量，但是长度却比原来 的方式尽可能短【2 0 1 。作为一种常见且重要的计算机技术，数据压缩广泛应用于 声音、图像和视频数据处理、网络通信的数据传输、各种海量数据的备份恢复等 和人们只常生活息息相关的领域1 2 1 1 。而u n i x 系统下的g z i p 文件格式以及d o s 系统下的z i p 文件格式则是被人们普遍了解和接受的两种著名的数据压缩格式。 对于数据库系统而言，数据压缩可以进一步发掘系统自身的潜力。首先，采 用数据压缩技术可以减小数据自身的规模，降低各种数据在存储介质( 如内存、 硬盘、磁带) 上的存储代价，提高数据查询中特定数据的命中率1 2 2 】；其次，数 据压缩可以大幅节省系统内存与外部设备之间的i o 带宽，降低数据的传输时间， 对于i o 需求较大的应用可以有效缓解系统的i o 瓶颈，提高系统的运行效率【2 3 1 。 尽管数据压缩技术的引入为数据库系统带来了种种好处，但数据压缩技术仍 然有着自身的局限性。由于系统需要付出额外的c p u 代价来对数据进行首次压 缩，并且在将来每次查询数据的时候都必须对压缩数据进行解压，因此数据压缩 会进一步造成系统c p u 开销的加剧【2 4 1 。例如，在不引入数据压缩的情况下，系 统的一个数据查询请求需要耗费6 0 s 的i o 代价和3 0 s 的c p u 代价，从而该请求 得到最终响应的等待时间为6 0 s ( 假设i o 和c p u 计算可以同时进行) ；而在引 入了一个重量级的数据压缩算法后，同样一个数据查询请求的i o 代价得以减半 为3 0 s ，但压缩和解压过程耗费的c p u 代价却有可能超过6 0 s 。由此可见，数据 压缩算法的选择和使用不当不仅会造成系统性能瓶颈的转移，把一个i o 级别的 查询转变为一个c p u 级别的查询，而且还有可能导致系统整体性能的下降，使 最终结果适得其反【2 引。 综上，在本章以下章节中，我们将首先分析列存数据库下数据压缩技术的实 现优势，然后引入了几种适用于列存数据库的轻量级( 耗费c p u 代价较少) 数 据压缩算法，并主要研究和讨论了各种算法的基本原理和实现思想。最后，通过 对各种压缩算法的性能分析，确定了这些算法各自的适用范畴，从而为o s c a r 7 2 列存数据库中数据压缩算法的研究 硕i ：论文 列存压缩数据库的实现奠定了理论基础。 2 z 支持列存储的数据压缩算法 2 2 1 列存环境下的数据压缩优势 在各种传统的关系型数据库系统中( 比如o r a c l e 、d b 2 、m i c r o s o f ts q l s e r v e r ) ，数据是按照关系表的“行 进行存储的。也就是说，来自于关系表中 同一条记录( 元组) 的不同属性值是依次连序存储在磁盘上的。这些传统的数据 库被统称为“行存数据库 。 传统的行存数据库压缩引擎不能以一种通用的方式进行数据压缩，主要是由 于存在以下三个方面的问题【2 6 】： 1 按行存储的数据存储方式不利于压缩。因为数据( 大多为二进制数据) 在 以这种方式存储时重复并不多。研究发现，按行存储的数据，最多能有5 1 0 的压缩比例。 2 对于许多2 k 和4 k 的二进制数据页来说，行存数据库环境下为压缩和解 压增加的开销太大。 3 在o l t p 环境中，大量读取和更新混杂在一起。每一次更新需要进行压 缩操作，而读取只需进行解压操作，大多数的数据压缩算法在压缩时比解压 时慢4 倍。这一开销将明显降低o l t p 数据库引擎的事务处理效率，同时使 得数据压缩的代价昂贵到几乎不能忍受。 一方面，在数据仓库实际应用中，数据压缩可以用较小的代价换取更大好处， 其中包括减少对于存储量的要求、增大数据吞吐量、减少查询响应时间等2 刀。 而另一方面，由于自身的限制，行存数据库在数据仓库应用中却不利于数据压缩 的实现。而列存压缩数据库的出现则很好地解决了上述矛盾。与行存数据库不同， 在列存数据库中，关系表的每个属性列被单独存储在各自独立的磁盘空间上，同 一条记录的不同属性值不再是连续存储的，取而代之的是同一个属性列的所有属 性值依照其在关系表中出现的位置依次连续存储1 2 懿。由于自身存储方式的特殊 性，使得列存数据库在数据压缩方面具备了行存数据库不可比拟的优势。因为在 列存数据库中，连续存储的数据均来源于同一个属性列，即来源于同一个值域， 而对同一个值域内的数据进行压缩正是各种经典数据压缩算法实现的前提和关 键【2 9 】。但是在行存数据库中，数据压缩算法必须要对不同类型、来源于不同值 8 硕_ f ：论文基于支持列存储的数据乐缩算法研究 域的数据进行压缩合并，这无疑是一项具有挑战性的工作。正是因为上述原因， 导致了数据压缩技术在行存数据库中的实际应有极为有限，而随着近几年列存数 据库的广泛使用和推广，数据压缩技术在列存环境下巨大优势也逐渐引起了该领 域研究者们的广泛关注。 在传统的行存数据库中，最常使用的数据压缩算法是赫夫曼算法和基于字典 的压缩算法【3 们，而这些压缩算法在列存数据库中同样可以很好的实现。此外， 列存数据库还非常适合于那些可以一次性压缩关系表中多个元组属性值的算法， 比如r l e 算法和空值压缩算法等。在压缩效率方面，列存数据库也比行存数据 库表现出了更为明显的优势，因为同一个属性列中连续的属性值彼此之间的相似 度往往较高，而关系表一条元组中相邻的属性值之间却没有这个特点。至于对 c p u 的计算开销而言【3 ，对物理页面中同一个属性列的各种属性值进行迭代计 算，其开销也远小于对物理页面中一张关系表的各种元组进行迭代计算的开销， 特别是当属性列的取值是定长数据类型时，情况更是如此。更重要的是，列存数 据库可以按照不同的排序顺序存储不同的属性列值，从而进一步促进了数据的可 压缩性，因为对于压缩技术而言，有序的数据往往更易于被压缩和解压【3 2 1 。 综上所述，列存数据库在数据压缩方面的巨大潜力，为各种数据压缩技术的 实现提供了必要的前提和保障。 2 2 2 列存环境下基于统计的数据压缩算法 基于统计的数据压缩算法是根据字符出现的概率来进行编码的。其中，赫夫 曼编码和算术编码是此类算法中的经典之作。下面将对这两种算法进行详细的介 绍。 1 赫夫曼编码 赫夫曼编码是一种高效的变长前缀编码，通过对各种出现频率不同的字符赋 予不同长度的码值，赫夫曼编码达到了完善的概率匹配，确保了编码数据的总长 度最短，从而最终实现了平均信息量意义下的最佳编码【3 3 】。 赫夫曼编码实现的关键在于构造相应的赫夫曼二叉树。在二叉树中，从树的 一个结点到另一个结点之间的分支构成了这两个结点之间的路径，而路径上的分 支数目就是“路径长度。如果树中有n 个叶子结点，每个叶子结点的权值为w i ， 那么整棵二叉树的“带权路径长度( w p l ) 计算公式为： 9 2 列存数据库中数据k 缩算法的研究硕土 论文 w p l 2 w ，( 其中厶表示第f 个叶子结点到根结点的路径长度) f = l 对于任意给定的1 1 个叶子结点以及相应权值，赫夫曼二叉树的w p l 取值必 然为所有可能的二叉树中取值最小的，因此赫夫曼二叉树又被称为“最优二叉 树 。关于赫夫曼二叉树的具体构造，可遵循如下四个基本步骤： 1 ) 根据给定的n 个权值 w l ，w 2 ，w n l 构成n 棵二叉树的集合f = t l ， 1 2 ，t n ) ，其中每棵二叉树t i 中只有一个权值为w i 的根结点，其左右子树均为 空： 2 ) 在f 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉 树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和； 3 1 在f 中删除这两棵树，同时将新得到的二叉树加入f 中； 4 ) 重复步骤2 ) 和步骤3 ) ，直到f 中只含有一棵树为止。这棵树就是最终生 成的赫夫曼二叉树。 对于一个由1 1 种字符组成的数据流，只需要分别以这n 种字符在数据流中出 现的频率作为权值，构造出相应的赫夫曼二叉树，即可实现对1 1 种字符的赫夫曼 编码。现举例说明其编码步骤，如下所示： 1 ) 数据统计。对于预备压缩的数据流，计算其中各个字符的出现次数( 实 际应用中通常是对各个字符在数据流中的出现概率进行估计并用作替代) ，如表 2 2 2 1 所示。 表2 2 2 1 赫夫曼举例 字符abcde f 出现次数 2 031 3871 5 2 ) 按照表2 2 2 1 所列数据，构造一个具体的赫夫曼二叉树，如图2 2 - 2 1 所示，数据流中出现的各个字符均悬挂在二叉树的叶子结点上。 3 ) 对图2 2 2 1 所示的二叉树进行编码。约定树中左分支标志为数值“o ”， 右分支标志为数值“1 ”，则可以从根结点到叶子结点的路径上分支数值组成的数 值串作为该叶子结点字符的编码。具体编码值如表2 2 2 2 所示。 1 0 硕上论文基于支持列存储的数据压缩算法研究 af 图2 2 2 1 赫夫曼二叉树 表2 2 2 2 赫夫曼编码值 字符 编码字符编码 a0 0b0 1 1 0 c1 0d0 1 0 e0 1 1 1f1 1 由于赫夫曼二叉树实现了w p l 的最优化，从而在理论上保证了以赫夫曼编 码压缩得到的数据其编码总长度必为所有可能编码方案中最短的。但是，赫夫曼 编码没有错误保护的功能。在解码时，如果码串中出现错误，哪怕仅仅是1 位的 编码错误，那么不但包含错误编码的数据本身无法正确解码，而且在此错误编码 后面的所有编码都有可能会被错误解码甚至是无法解码，这种现象被称为“错误 传播”。因此，赫夫曼编码的实现要求数据库本身有严格的数据验证机制，以便 保证数据编码和解码的正确性。 2 算术编码 由于赫夫曼编码使用整数个二进制位对符号进行编码，导致这种方法在许多 情况下无法得到最优的压缩效果。比如，假设某个字符的出现