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

天津师范大学硕士学位论文 摘要 随着数据仓库、决策支持等o l a p 技术的广泛应用，数据库系统对执行引擎 查询效率的要求越来越高，因此人们提出了一种的新的数据库系统设计理念，即 以列为基本存储单位的列存储数据库系统。 本文首先将列存储数据库系统与行存储数据库系统之间在存储结构、查询效 率上进行对比，得出列存储数据库系统在查询执行效率上优于行存储数据库系统 的结论。研究了列存储数据库系统中的所适宜采用的字典编码、行程编码以及位 向量编码等压缩技术。通过分析查询过程中不同属性列连接的时机的特点，研究 后物化技术对于列存储数据库系统查询效率的影响，并进一步研究采取直接访问 压缩态数据的策略对数据库系统性能的影响。 结合列存储数据库系统与稀疏数据自身的特点，本文提出了一种列存储数据 库系统适宜存储稀疏数据的观点，并给出稀疏数据库的设计方式。通过研究稀疏 数据的应用场景，分析稀疏数据的存储结构特点，给出稀疏数据库常见的数据模 型。 最后本文着重研究了字典编码压缩算法中的l e n l p e l z i v ，分析并比较其两种 分支算法l z 7 7 和l z 7 8 各自的优缺点，提出了一种基于l z 7 7 和l z 7 8 算法的改 进算法，以便利用两者各自的优点提高算法的性能。进而通过实验，将改进后的 算法在压缩率和压缩时间上与l z 7 7 和l z 7 8 算法相比较，得出改进后算法在整 体上的性能优于l z 7 7 和l z 7 8 。 关键词：列存储数据库系统；稀疏数据库；压缩技术；l 锄p e l 一z i v ；查询效率 天津师范大学硕士学位论文 a b s t r a c t w i mm ew i d eu s eo fo l a pt e c h n 0 1 0 蹦s u c h 硒d a t aw a p e h o u s ea i l dd e c i s i o n s u p p o r t ，t l l e r eh a sb e c o m ea i li n c r c a l s i n gd 锄锄d i n gf o re 缳c i e n tw a y t oi m p m v et h e p 晌m a i l c eo f d a t a b a s eq u e 巧吼百n e p e o p l eh a v ep r e s e n t e dan e wc o n c 印tt od e s i 盟 d a t a b a s es y s t e m ，c o l u m - o r i e i l t e dd a t a b a s ew h i c hs t o 】治si t sc o n t e n tb yc o l u n m 础l e r t l l a l l b y r o w i i l l i sp a p w ef i r s tc o m p a r ec 0 1 硼 1 1 1 - o r i e n t e dd a t a b a s ea i l dr o w o r i e i l t e d d a t a b a s ei nm es t o r a g el a y e ra n dq u e 叫e n 百n e ，a n do b s e r y em a tt l l eq u e r ye n 百n eo f c 0 1 u l 】 m o r i e n t e dd a t a b a s ei sm u c hm o r ee 蚯c i e n tb e c a u s eo fi t ss t o r a g es t m c t u r e w e a l s oa i l a l y z et h ec o m p r e s s i o nt e c l l i l 0 1 0 百e ss u c ha sn u l ls u p p r e s s i o n ，d i c t i o n a 叮 e n c o d i n g ，r u n l e n g t he n c o d i n ga n de 髓c t so fo p e r a t i n gd i r e c t l yo n 吐l ec o m p r e s s e d d a t a w ea l s od os o m ew o r kt od i s c u s st h ee f 3 f e c to fl a t em a t 耐a l i z a t i o no nq u e 叮 c 1 1 目n e t h r o u 曲a n a l ) ，z i n gt 1 1 ec h a r a c t 嘶s t i c so fs p a r s ed a t a ，w ec o n c l u d et h a ti t s s u i t a b l ef o rc o l w n n - o r i e n t e dd a t a b a s et os t o r es p a r s ed a t aa i l d 百v et h em e t l l o do fh o w t od e s i g ns p a r s ed a t a b a s e t h e nw ei i e s t i g a t es p a r s ed a t as c e l l a r i o ss u c he x c 印t o l a p a n a l y z et h es t o r a g es t m c t u r ec h a r a c t e r i s t i c so fs p a r s ed a t aa n d 西v em r e e c o m m o nd a t am o d e l si nt h es p a r s ed a t a b a s e f i n a l l y w ed oo u rr e s e c ho n o n ea 1 9 0 r i t h mo fd i c t i o n a r y e n c o d i n g ， l 锄p e l z i va n dc o m p a r ei t s 铆ob r a l l c h i n ga l g o r i t h m s ，l z 7 7 锄dl z 7 8 ，a n dw e 百v e a i li i n p r o v e da l g o r i t h i nb a s e do nl z 7 7a i l dl z 7 8t ou s em e i ra d v a l l t a g e s t h e i l 缸o u 曲e x p e f i m e n t so fc o m p a r i n gt h ei m p r o v e da j g o r i t mw i t hl z 7 7 锄dl z 7 8i n c o m p r e s s i o nr a t i oa n dc o m p r e s s i o nt i m e ，w ec o n c l u d em a tt l l ei m p r o v e da l g o r i t l l m p e r f o 咖sm u c hb e t t e ro v e r a l l k e yw o r d s ：c o l u l m - 嘶e n t e dd a t a b a s e ，s p a r s ed a t c o m p r e s s i o nt e d m o l o 鼢 l e i 】1 p e l z i v ，q u e 巧e m c i e i l c y 天津师范大学硕士学位论文 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得苤壅竖垫盘堂或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：李些日期：z 幽 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：盔哓豳 导师签名： 期： 天津师范大学硕士学位论文 第一章引言 1 1 列存储数据库系统产生的背景 从逻辑层上看，关系数据库系统是以一张二维表的形式存储数据的，每行代 表着现实世界中的一个实体，每列都是这些实体的一个属性，例如，在一个顾客 信息表中，每行代表一个不同的顾客，每列代表某个顾客的一个属性，如姓名、 住址、电话等等。但是这种二维表只是存在于数据存储的逻辑层次上，在实际存 储数据的物理层次上，由于计算机的物理存储设备在读写数据时都是按线性的结 构进行的，于是便为数据库的存储结构提供了两种可能，按行存储和按列存储。 现今的关系数据库系统大多衍生于7 0 年代的s y s t 锄r 项目原型和i n 黟e s 项 目原型，但是随着应用和硬件技术的发展，d b m s 的需求不仅仅满足于s y s t 锄r 和h 1 黟e s 设计面向o l t p 数据处理的初衷，而更多的是地球科学【1 ，1 2 1 、医学等数 据仓库以及决策支持系统等的o l a p 的数据处理需求，而在这些应用中，大多数 信息都是散乱的、稀疏的，并且需要对数据进行大量的查询处理，以便对其进行 数据有效的分析处理；同时由于硬件技术的发展，传统的高性能硬件逐渐大众化， 使得数据仓库等应用得更加普遍。因此为了满足该类应用场景的需求，数据库系 统发展的方向由满足0 m 数据处理的需求转向满足o l a p 数据处理的需求， o l a p 是对列进行操作的，于是便衍生出面向分析处理( o l a p ) 的列存储数据 库系统。 1 2o l a p 软件的特点 在数据仓库中，将操作型系统( 数据库系统) 中的数据关系转变成数据仓库 模型，需要对操作型数据模型做一定的修改。数据仓库过程中的数据查询与事务 过程中的数据查询有很大的不同，主要表现在： ( 1 ) 可预测性小。在o l t p 数据处理过程中，因为数据库用于自动化业务 任务，查询是由一系列预定义的具体动作来初始化的，因此，应用于此查询的基 本结构是被提前编码的，而数据仓库中的查询伸缩性比较大，他们可以人为的初 始化。 ( 2 ) 持续时问长。事务查询语句比较短、简单，例如，添加客户信息，查 询账户余额等，而数据仓库中的查询语句因为其本身用于分析处理和决策，需要 天津师范大学硕士学位论文 读取比较多的数据产生复杂的信息，如：一个分析客户属性和贷款风险之间关系 的查询语句需要查询客户与贷款记录的很多条记录。 ( 3 ) 读操作比写操作多。在数据仓库中，写数据都是批量进行的，大部分 都是查询操作。 ( 4 ) 更关注属性而不是实体。在数据仓库中，通常不查询单个实体信息， 而是查询多个实体，并对它们进行聚集，如查询客户的平均账户余额等。同时， 在一次查询中只关注少数属性列。 1 3 列存储数据库系统的发展现状 列存储数据库的研究可以追溯到二十世纪七十年代，从开始研究置换文件开 始，紧接着，可以研究对表中属性聚集技术进行垂直分割。直到八十年代中期， 2 7 中说明已分解的存储模型d s m ( d e c o m p o s e ds t o r a g em o d e l ，列存储数据库 系统的前身) 相对于n s m ( 传统的行存储数据库) 的优点，随后开始研究相对 于n s m 模型，d s m 模型在连接和列族索引方面的优势。由于市场的需求，以及 没有新技术的出现，使得行数据库系统成为主流。但从2 0 0 0 年开始，列数据库 的研究及其在商业中的应用开始成为一种趋势。 在此过程中，比较著名的列数据库系统有开源项目c s t o r e 【4 1 ，是由麻省理工、 耶鲁大学、布朗大学等合作研发的，并于2 0 0 5 年发布第一版本，2 0 0 6 年升级为 第二版本。在c s t o r e 的研究基础上，又衍生出来商业化的v 缸i c a 以及内存数 据库系统m o n e t d b 。应用于g o o 哲e 的b i g t a b l e 也是一种面向列存储的数据库系 统，该系统是g o o 舀e 内部开发用来处理大数据量的系统，g o o 罾e 的很多项目包 括网索引、g o o 哲ee 砷和谷歌财务都是建立在该系统基础上的，但与传统的关 系数据库不同之处在于其不支持任意标准的s q l 查询，所以b i g t a b l e 还不能是 完全意义上列存储数据库系统，但是b i g t a b l e 的广泛应用显示了列存储数据库 发展的广阔前景。数据库大师m i c h a e ls t o n e b r a k e r 曾在一篇博客上写到，“在不 久的将来，列存储数据库系统将会占领数据仓库市场，完全取代行存储数据库系 统，因为现今的数据库系统不支持即席查询，除非升级设备，不然不能提高系统 的执行效率【3 1 ，因此可以看出列存储数据库存储系统成为数据库发展的趋势。 1 4 稀疏数据的应用场景 稀疏数据广泛存在于各种应用场景中，如：在分布式管理系统c o n d o r 中， 2 天津师范大学硕士学位论文 用户可以自己定义新的属性，因此，在一个数据集中很多属性几乎都是空值；同 时，稀疏数据还大量存在于电子商务的应用中，每位商家都可以定义自己商品或 者订单特有的属性，从而使得数据有成千上万的属性值，如【l 】中有5 0 0 0 个属性， 但是对于每个元组，这些属性值几乎都是空值；在医掣5 1 、地球科学2 1 等领域， 存在着大量的稀疏数据。 为了满足现今的o l a p 需求，由于存储稀疏数据的表都具有至少几千个属 性，即宽表，而每次执行查询时并不需要读取表中的所有属性，显然，采用传统 的行数据库存储稀疏数据性能比较低下，因此，列数据库成为人们存储稀疏数据 的一种选择趋势，如现今流行的b i 9 1 a b l e 就是采用列式存储。 1 5 本文的主要贡献 本文中指出后物化技术对于列存储数据库查询效率的重要作用，并通过实验 对其进行分析，本文的实验是在m o n e t d b 的基础上实现的。在第二章将简述列 存储数据库系统研究的相关技术，本部分实验数据采用s s b m 数据模型；第三 章将研究直接对压缩态数据进行访问的技术；第四章主要介绍稀疏数据库系统的 设计及其数据存储特点；第五章主要研究列数据库中采用的l e i i l p e l z i v 压缩算 法及其改进；第六章提出本文中一些技术难点的研究方向。 天津师范人学硕士学位论文 第二章列存储数据库系统研究的相关技术 2 1 列存储数据库系统与行存储数据库系统比较 在传统的关系数据库中，用户可以方便的进行插入、删除及修改等更新操作， 因其存储结构是按行进行存储的，c p u 只要进行一次寻址操作，便可完成此操 作，所以行存储数据库系统非常适用于频繁进行更新操作的数据库系统中。但是 随着数据仓库、数据挖掘、决策支持1 1 和地理信息系统【2 】等查询密集型系统的发 展，关系数据库已不能满足企业的需求，因此，人们提出了一种基于列进行存储 的数据库系统，即列存储数据库系统。 2 1 1 列存储数据库的优势 列存储数据库与行存储数据的本质区别在于其存储结构的不同，在行存储数 据库中，数据是以记录或行为单位进行存储的，而在列存储数据库中，数据是以 关系数据库中属性或列为单位进行存储的，数据表记录中同一属性的值都存储在 一起，而同条记录中不同的属性值则分别存放于不同的文件中，以职工表为例， 其存储结构如图2 1 所示。 i d 姓名生日工资部门 1 王娟 1 9 8 5 0 1 叭2 0 0 0 信息 2李红1 9 8 4 1 0 儿2 1 0 0技术 3杨阳1 9 8 5 0 5 1 01 9 0 0信息 4 王倩 1 9 8 7 0 2 0 12 3 0 0 研发 5 王旭 1 9 8 6 儿1 7 2 0 0 0技术 6 李情 1 9 8 3 1 0 0 83 0 0 0 研发 7任娜1 9 8 5 0 4 1 72 8 0 0信息 娜 i d 1 2 姓名 王娟 李红 生日 1 9 8 5 0 1 0 1 1 9 8 4 1 0 1 1 行存储数据库数据存储结构列数据库敦据存储结构 图2 1 行存储数据库与列存储数据库存储结构比较 因为与行存储数据库的存储结构不同，列存储数据库系统中的列具有数据独 立性和操作独立性，可以支持独立的数据存储、数据压缩和数据操作，列存储数 4 天津师范大学硕士学位论文 据库有许多优势： ( 1 ) 一个s q l 语句可以分解为若干个可独立执行的、基于列的原子操作， 即s q l c o m m a i l d = c o l o p e r l ，c o l o p e r 2 ，) ，列数据库只需要从磁盘读取相 关的属性，以节省i o 带宽。列数据库执行引擎访问数据的基本单位是单个属性 值，与行数据库对记录进行按顺序的逐条访问不同，列数据库对属性值的访问有 3 种方式：顺序访问、跳跃访问和随机访问。 例如：假设有表e m p ( n 锄e ，a g e ，d 印a r t m e m ，s a l a r y ) 和查询语句s e l e c t n a m e ，a g e ，s a l a 哆f r o me m pw h e r ea g e 2 5a n ds a l a r y 2 0 0 0o r d e r b y a g e 。经过查询分析器的优化，执行引擎首先会访问属性a g e ，对于a g e 5 的行， 再访问属性s a l a r y ，经筛选得到满足谓词条件的行号集合，然后根据a g e 的值将 这些行号排序，最后按这些有序的行号集合访问n 锄e ，而避免对属性d 印a n m e n t 的访问。在上例中，执行引擎对属性a g e 进行了顺序访问，对属性s a l a r y 进行 了跳跃访问，对属性n a m e 进行了随机访问，而对属性d 印a r t m 饥t 则未访问。实 际上，列数据库的执行引擎在执行过程中，只对其中的一列进行顺序访问，而对 于其他列的数据都是按跳跃或随机的方式访问 ( 2 ) 同一个文件中的数据具有相同的数据类型，相邻数据之间的相似性比 较大，增加了数据压缩比率【3 1 。 ( 3 ) 由于数据都以列的形式存储，在s q l 语句执行过程中，节省了行数据 库中映射( p r o j e c t i o n ) 运算的开销。 ( 4 ) 列存储数据库中可以进行轻量级的压缩，从而可以在不解压的情况下 直接对压缩态的数据进行操作。 通过执行s o l 查询语句，我们可以看出列存储数据库的查询执行效率要高 于行存储数据库，其性能对比如图2 2 。 5 天津师范大学硕士学位论文 熏鬟 4 0 o 3 0 o 2 0 o l o o 0 o 够均皴 图2 2 行数据库与列数据库性能对比图 但是，列存储数据库系统也存在以下的缺点： ( 1 ) 增加的磁盘寻址的时间。当并行读取多列时，需要从磁盘读取多个数 据块的数据，但是，增加预取数据的磁盘空间，可以降低这种代价。 ( 2 ) 增加了插入数据时的花费。在列数据库中插入需要寻找每个属性列的 位置，执行效率非常低，但是可以通过批量插入数据来消除此花费。 ( 3 ) 增加了元组重构的代价。为了给列数据库提供一个标准的通用关系数 据库接口，如o d b c 、j d b c 等，必须在查询计划中将不同的属性列重组成元组， 虽然可以在内存中进行该操作，但是c p u 执行该操作的代价非常高。通常情况 下，采用后物化技术可以将该操作的代价达到最低。 2 1 2 研究列数据库的技术 随着数据库技术在商业分析、决策以及智能方面的应用，目前对列存储数据 库的研究越来越多，人们一般采用三种方法对其进行研究【刀。 ( 1 ) 在行存储数据库中，对表进行纵向划分，一张表被划分成多张只包含 ( k e y ，a t t r i b u t e ( i ) ) 两个属性列的小表【6 1 ，源表中除了主键之外的所有的属性 列都对应一张小表，其分割结构图如2 3 。 6 天津师范大学硕士学位论文 i d i 姓名i 生日l 工资l 翻 i d姓名 l 王娟 1 9 8 50 1 0 l2 0 0 0信息 映 l王娟 2 孪红 】9 8 4 1 0 1 l2 1 0 0按术 射 2挛红 3杨阳1 9 8 5 0 51 01 9 0 0信息3杨阳 4 王倩 1 9 8 7 0 2 叭2 3 0 0研发4王倩 d _ 。一 1 _ 一 2 _ _ - 3 - _ 一 4 生日 1 9 8 5 0 l0 1 1 9 8 41 01 1 1 9 8 5 0 51 0 1 9 8 7 0 2 0 1 d工资 l2 0 0 0 22 1 0 0 31 9 0 0 42 3 0 0 图2 3 行存储数据库中表的划分图 执行s q l 查询语句时，只访问相关属性列所在的小表，并通过主键将其连 接，对相关属性进行投影，来执行查询操作。该方法对于含有属性越少的查询语 句执行效率越高。 ( 2 ) 第二种方法强调修改传统的行数据库的存储层结构，不改变其逻辑层 结构1 。在物理层，记录表是以列为单位进行存储，而不是以行为单位进行存 储的。该方法与第一种方法的区别在于：不是将主键与每个属性值存储在一起， 每列中的第i 个属性值与其他列中的第i 个属性值相关联。与第一种方法类似， 在执行s q l 查询语句时，只读取与查询相关的属性列，然后将其连接成一张记 录表，然后由传统的执行引擎来处理该查询语句。【7 中已经证明单纯的改变行 数据库的存储层结构并不能完全提高s q l 查询执行效率。 ( 3 ) 第三种方法是在存储层和执行引擎层次上改变行存储数据库【8 】，在物 理层上，数据以列为单位进行存储，同时执行引擎也是将数据以列为单位进行处 理。该方法能够在很大程度上提高数据库的查询效率，其执行过程如图2 4 。 图2 4 列数据库中查询执行过程及其优点 8 对列存储数据库中存储层和逻辑层的设计有详细的说明， 9 】中对以上三 种方法做了对比实验，得出完第三种方法，即列存储数据库，在查询执行效率上 7 天津师范大学硕士学位论文 要明显优于其他两种方法。 2 2 压缩技术 目前，压缩技术广泛应用图像存储中，因为其相邻像素之间以及色彩组成部 分的相关性，数据的相似度很大，使得采用数据压缩技术并不会影响图像的视觉 效果。随着对数据库技术的不断研究，人们也将数据压缩技术广泛的应用于数据 库技术中。压缩技术分为有损压缩和无损压缩，主要采用无损压缩技术压缩文本 和数据，被压缩的数据能够恢复，因此，在数据库中，采用的主要的是无损压缩 技术。 在传统的行数据库中，压缩技术对于提高数据的查询效率有很大贡献【1 1 】：压 缩技术减少了数据大小，降低了磁盘寻址时间以及数据传输时间，增加了缓冲区 的命中率，从而提高了i o 的效率。在传统的行数据库中，通常采用字典编码压 缩技术将编码比较长的数据转换成编码比较短的数据，如：“红色”一“0 ，“黄 色”一“l ”，“绿色 一“2 ”等。在行数据库中，还经常采用哈夫曼编码等技 术。 除了上述特点外，列存储数据库还非常适宜于同时压缩多列的压缩模式，所 以列存储数据库可采用的压缩算法种类更多，如行程编码( r l e ) 等，也可采用 对传统压缩算法改进后的算法。由于数据在列存储数据库中是以列为单位进行存 储的，相邻数据间的相似性比行数据库中的大，所以数据的压缩率比较高【1 7 1 。其 次，内存中列属性值的迭代次数要比记录行的迭代少，从而可以通过矢量编码来 增加解压缩的速率。同时，列数据库中的每列都可以按不同的方式排序，而有序 数据有利于数据压缩。 列存储数据库还允许执行引擎直接对压缩数据操作，尤其是在行程编码等压 缩技术中，如：对某个属性列进行求和运算，已知值“3 0 ”在该列中连续出现 1 0 0 0 次，在求和运算过程中，不必对该列解压缩，可以直接用3 0 1 0 0 0 求出该 列的数值和。 显然，压缩技术能够提高磁盘的利用率，对i o 操作有很大益处。首先，访 问压缩数据时，降低了寻址空间和寻址时间；每个磁盘页中存储的数据增多，使 得更多相关对象的聚类存储在临近的位置；空闲磁盘可以用于磁盘映射，提高数 据的可靠性、易访问性以及i o 效率；压缩数据传输的更快，即能够增加磁盘的 8 天津师范大学硕士学位论文 带宽，能够缓解数据库系统的i o 瓶颈；在分布式系统中，压缩数据传输的效率 更高；同时缓存中可以存储较多压缩态的数据，因此能够增加缓存的命中率，减 少数据i o 的次数。同时列数据库有利于对压缩态数据进行操作，从而避免了解 压缩对系统性能的消耗，使得数据压缩技术的优势在列数据库中得到充分的发 挥。因此，本文在该章节中研究列数据库中主要采用的几种压缩算法。 2 2 1 消零或空格符法 该算法有很多变体，但是其基本的思想为：去掉连续出现的空值或者零，用 出现的次数和出现的位置来描述该列中所有的空值，如j ! l 5 表示5 个连续的零， 6 表示6 个连续的空值，是行程编码的一种特例。 2 2 2 字典编码 字典编码属于无损压缩算法，其基本思想就是标识经常出现的符号模式，保 存于字典中，对这些经常出现的模式采用更有效的编码方式，即用其在字典中的 索引为码字，而其他部分采用缺省的编码方式。 字典编码包括静态字典编码、半适应字典编码以及自适应字典编码三种形 式。字典编码中最简单的形式是静态字典编码，该类字典中通常包含任意长度的 字段，以一种已经存在的编码形式为基础，如a s c i i 码，可以非常容易的建立该 字典，但是该类算法的压缩率不高，也有可能会导致压缩后数据的长度增加。而 半适应字典编码可克服该缺点，但是需要同时存储字典与数据信息，并需要在数 据上建立两条路径，一条是建立字典，一条是用来压缩数据。但是自适应字典编 码完全克服了上述两种编码方式的缺点。 实用的字典编码，即自适应字典编码，核心是如何动态形成字典以及如何有 效的选择输出格式，以减小冗余。其编码思路为：利用数据本身包含许多重复的 字符串特性，例如：吃葡萄不吐葡萄皮，不吃葡萄到吐葡萄皮。如果用一些简 单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的 相关性，其中字符串与代号之间的对应表就是字典。l z 7 7 和l z 7 8 是两种常用 的字典编码算法，其存在很多变种，是很多主流压缩算法的基础，我们将在第四 章中着重介绍该类算法。 在列数据库中，字典编码算法会先计算某个属性列所需要的字符数目，然后 根据具体的个数确定需要的字符位数，如表2 1 。 9 天津师范大学硕士学位论文 表2 1 职- t 表格信息 姓名年龄 工资部门 王娟 2 01 8 0 0 信息 李红 2 01 9 0 0 信息 杨阳 2 01 8 0 0 研发 王倩 2 01 9 0 0 技术 w e n d y 2 l1 8 0 0 研发 t 0 m2 01 8 0 0 信息 其中“部门”的属性值的种类是有限的，假如该公司中含有信息、研发、技 术、人事以及财务五个部门，则我们可以采用3 个比特位进行编码，其编码如 表2 2 。 表2 2 字典编码表 信息研发技术人事财务 0 00 0 1o l o0 l l1 0 0 表2 2 就构成了一个字典，这样在数据被编码时，遇到已经在字典中出现的 属性值时，编码器就输出该属性值所对应的位串，而不是属性值本身。假如该公 司增加了销售部，则可以将销售部添加到字典中，用1 0 1 来代替销售部。 2 2 3 行程编码 行程编码( r l e ，r u n - 1 e n g t l le i l c o d i n g ) 是一种最简单、最古老的数据压缩 技术，它视数据信息为无语义的字符序列( 字节流) ，基于简单的编码数据原则， 即重复的数据值序列( 或称为“流 ) 用一个重复次数和单个数据值来代替。这 里，重复的值称为一个“连续( m ) 。实际应用时，采用多种形式的r l e 编码。 如： 未压缩数据：a b x x x x x x x x d e f f g g g 其r l e 编码为：a b 8 x c d e f f 3 g 对比该数据编码前后的代码数可以发现，在编码前要用1 7 个代码表示的数 据，而编码后只要用1 0 个代码，压缩比为1 7 ：l 。这说明r l e 确实是种有效 的压缩技术，而且这种编码技术相当直观，也非常经济。r l e 所能获得的压缩 比有多大，这主要取决于数据本身的特点。 1 0 天津师范大学硕士学位论文 在数据库中，其常用的格式是由一个起位，止位和属性值构成的，如表2 3 。 表2 3r i 虎编码格式图 该算法广泛用于图像的存储，也非常适用于列数据库，因为在列数据库中， 同一属性列中可能会连续出现某个值，同时可以对每列采用不同的排序方式，所 以非常适宜采用此算法。 例如，在列数据库中，由于不同列中的属性值可以按不同的顺序排序，若表 2 1 中“年龄”和“工资列分别按升序排序，其中年龄属性列经过压缩后可以 变为( 1 ，5 ，2 0 ) ，2 l ；工资列可以压缩为( 1 ，4 ，1 8 0 0 ) ，1 9 0 0 ，1 9 0 0 。当压缩 的数据少于3 个时，就没有必要再对数据进行压缩。 2 2 4 位向量编码 当列中的属性值的种类一定时，非常适合采用位向量编码。在该编码中，用 一个位向量表示该属性列，若含有某个值，将位向量中相应的位置“1 ”，否则置 “o ”，如下： 1 ，l ，3 ，2 ，2 ，3 ，l 则1 的位向量为：1 1 0 0 0 0 1 ，2 的位向量为：o 0 0 1 1 0 0 ，3 的位向量为：0 0 l 0 0 1 0 。 2 2 5 l e m p e i - z i v 压缩算法 l 锄p e i z i v 编码是一种广泛应用的无损压缩算法，l 锄p e l - z i v ，简称l z ， 拥有l z 7 7 ，l z 7 8 ，l z w 几种不同的演变算法。l z 是一种典型的字典型压缩算法， 巧妙的利用字典，减少信息量。例子： 原始编码为：1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 现在有空字典一个，首先由第一的b i t 开始，索引1 对应1 ，因为字典中没 有o 这个元素，所以索引2 对应0 ，第三个b i t ，o 已经出现在字典中，我们推后一 位0 1 ，没有出现在字典中，因此索引为3 加入字典。以此类推! 索引最终用二进制方式表示，我们得到1 ，o ，l o ，1 1 ，0 1 ，1 0 1 ，0 1 0 ，1 0 l l 这8 个字典项，用3 位码可以表示，l z 扩展了一位已表示各个元素间关系。 2 3 物化技术 在列数据库中，数据以列为单位进行存储的，所以在数据输出时要对各列进 天津师范大学硕士学位论文 行重构成元组。每个列数据库体系都采用将元组的i d 或者位置与属性值存储在 一起的策略，在重构的过程中，数据库根据i d 来对各列进行连接操作。 在查询执行过程中，元组重构可以在任何不同的时间点进行，我们把在查询 执行计划开始时，进行元组重构的策略称为先物化技术( e 耐ym a t 耐a l i z a t i o n ， 简称e m ) ，而在查询执行计划后期，甚至是元组输出之前进行元组重构的策略 称为后物化技术( l a t em a t e r i a l i z a t i o n ，简称l m ) 【2 9 】。 2 3 1 查询处理和优化 首先我们来看一下在数据库中查询处理的步骤，如图2 5 【1 们。 语法分析器与翻 l 查询l 译器 l 关系代数表达式 i 有关数据的统 计信息 图2 5 查询处理步骤 对于给出的查询，一般都会有多种计算结果的方法，例如，已知在s q l 中， 一个查询能够用几种不同的方式表示，每个s q l 查询可以用其中的一种方式翻 译成关系代数表达式，以职工表为例，如 s e l e c t 姓名 f r o m 职工表 w h e r e 工资 2 5 0 0 其关系代数表达式可以表达如下： 1 2 天津师范大学硕士学位论文 ( 1 ) 吒瓷。2 5 0 0 ( n 姓名( 职工表) ) ( 2 ) 兀姓名( 仃工资。2 5 0 0 ( 职工表) ) 对于上述两个关系代数表达式，在执行查询的过程中，可以采取不同的执行 策略，对于每种查询的代价，我们可以通过该查询对各种资源的使用情况进行度 量，这些资源包括磁盘存取、执行一个查询所用c p u 时间、还有在并行分布式 数据库系统中的通信开销等。 在列数据库中，数据是以列为单位进行存储的，这样在进行查询操作时，需 要对每列数据进行连接。在数据库中，数据连接可以发生在不同的时刻，通常会 采用e m ( e a r l ym a t 嘶a l i z a t i o n ) 和l m ( l a t em a t 击a l i z a t i o n ) 两种物化方式。 2 3 2e m 与l m 物化技术比较 ( 1 ) e m 物化技术的特点：在查询执行的任何时刻，当所访问的属性列被 后续的执行引擎访问或者被包含在输出序列中时，就将其属性值添加到元组中， 这样能够减少查询执行引擎对磁盘的访问次数。 但是，在列数据库中，e m 物化技术并不完全适用于任何场合。如：一个查 询计划中需要对三个属性列尺。，心，r ，分别做选择操作仃。，盯：，仃：，在e m 物化策略中，其执行顺序如图2 6 。 图2 6 执行引擎采用e m 物化技术的执行过程 在此过程中，连接操作先于选择操作，因为对r ，垦，r 所有数据做连接 操作，c p u 的代价较高。 ( 2 ) 后物化技术的特点：执行引擎能够直接对压缩数据、面向列的数据进 行操作，避免了解压缩，提高了查询执行效率，同时推迟了查询计划中的元组重 构，从而减少了数据连接的次数。以( 1 ) 中的例子为例，其执行过程如图2 7 。 1 3 曰曰回 天津师范大学硕士学位论文 读 图2 7 执行引擎采用l m 物化技术的执行过程 因此，两种物化技术并没有优劣，而是适用于不同的场景，但是在 1 l 】已经 证明l m 物化技术在列数据库中具有更大的优势，这是由列数据库的存储特点所 决定的。在列数据库中，数据是以列为单位进行存储的，在查询执行过程中，若 先做选择操作，可以减少记录连接的条数，提高查询执行的效率。 2 4 分布式特点 在列数据库中，引入了“列族的概念，列族是建立在一个特定的逻辑表t 上的，包含该表中一个或者多个属性值。此外，列族也可以包含其他表中的任意 属性，只要其与基表t 之间存在1 ：，z 的关即可。例如：有关系 e m p ( n 锄e ，a g e ，d e p t ，s a l a r y ) ，d e p t ( d n 锄e ，f 1 0 0 r ) 我们可以将其 分解为以下几个列族： e ? l 绵( n 锄e ，a g e ) j 邑： 垄咒( d 印t ，a g e ，d e p t f l o o r ) e 假( n 锄e ，s a l a r y ) d e p 正( d n 锄e ，f 1 0 0 r ) 列族中的元组是按列进行存储的，因此，如果一个列族中含有k 个属性， 将会存在k 种数据结构，每种数据结构存储一列数据，所有的列都是按同一个 排序键进行排序。如上述列族可以按下列键进行排序： 上互 织( n 锄e ，a g e ia g e ) 上 ：2 1 4 咒( d e p t ，a g e ，d e p t f l o o r ld e p t f l o o r ) 1 4 天津师范大学硕士学位论文 e ? l 织( n 锄e ，s a l a 拶is a l a 巧) d e 尸正( d n 锄e ，f l o o r if 1 0 0 r ) 列族是访问控制的基本单位，每一列可以存储在不同的列族中，这与集中式 数据库系统尽量降低冗余的特点不同，在列数据库中，数据冗余是所必需的，列 存储数据库系统通常都是分布式系统，可以将这种数据库系统看作是一系列集中 式数据库系统的集合，它们在逻辑上属于同一个系统，但在物理结构上是分布式 的。分布式数据库系统具有以下优点： ( 1 ) 更适合分布式的管理与控制。分布式数据库系统的结构更适合具有地 理分布特性的组织或机构使用，允许分布在不同区域、不同级别的各个部门对其 自身的数据实行局部控制。 ( 2 ) 具有灵活的体系结构。集中式数据库系统强调的是集中控制，物理数 据库是存放在一个场地上的，由一个d b m s 集中管理。多用户只可以通过近程 或远程终端在多用户操作系统支持下运行该d b m s 来共享集中式数据库中的数 据。 ( 3 ) 在一定的条件下响应速度加快。如果存取的数据在本地数据库中，那 么就可以由用户所在的计算机来执行，速度就快。 ( 4 ) 可扩展性好，易于集成现有系统，也易于扩充。 同一列族可以分布在不同的结点，即同一列族会在不同的结点有多个副本， 如果一个结点发生故障时，可以在其它结点上到该结点存储的信息，尽管一个结 点发生故障，系统仍可以继续处理该列族的查询。如果绝大部分对关系r 的范 文都只会导致对关系的查询，可以对关系中的各个列族做并行处理。但是分布式 数据库系统也存在缺点，当数据进行更新时，需要更新所有副本的数据，使得所 有数据保持一致，因此增加了系统的开销。 分布式数据库系统已经成为信息处理学科的重要领域，正在迅速发展，随着 云计算技术的广泛应用，分布式数据库系统将会得到更广泛的应用，b i g t a b l e 就 是一个已经广泛使用于网络的分布式列数据库系统，分布式数据库系统执行查询 操作的过程如图2 8 。 1 5 天津师范大学硕士学位论文 图2 8 分布式查询执行过程 1 6 o l 系统l d 天津师范大学硕士学位论文 第三章压缩态数据访问 在列存储数据库系统中，采用压缩技术能够减少数据的存储空间，也降低了 数据从磁盘读入到内存时的空间消耗，但是在读入数据后，对数据进行解压缩消 耗的时间可能就会抵消，并不能达到压缩数据的目的。 1 2 】中的研究已经证明直 接访问态数据，可以大大的提高数据库的执行效率，因此，在数据库体系的构造 过程中，我们尽量采用直接对压缩数据进行操作的策略，使得查询执行引擎直接 访问压缩态数据。 但是，对于不同的压缩算法，执行引擎直接操作压缩态数据的能力是不一样 的，对于2 2 节中的压缩算法，执行引擎直接访问字典编码中的数据的效率比较 高，有两种方法可对其进行访问，一种是直接从一个3 2 位的字典压缩记录中提 取单个编码，通过在这些属性上执行g r o u pb y 操作来计算总数，然后将每个编码 还原成原来的值，可将还原后的值求和。例如，0 0 0 表示数值2 ，0 0 1 表示数值4 ， 0 0 2 表示数值8 ，假设聚合器接收下列字符串： 0 0 1 ，0 0 1 ，o o o ，0 0 1 ，0 0 2 ，0 0 2 接着聚合器就会计算每个字典输入流中数值的个数：0 0 1 ：3 ；0 0 0 ：1 ；0 0 2 ： 2 ，然后再对数据进行解码并计算数据的和，输出1 2 ，2 ，1 6 。 另一种方法与第一种方法相似，除了在解码之前，对所有的输入流进行分组， 并计算出包含特定值v a l u e 的每个输入流的个数c o m t ，并在解码时做 c d “咒f 觑p 操作。 除了可以直接对字典编码数据进行直接访问之外，还可以直接访问行程编码 ( r l e ) 以及位向量编码数据，我们可以发现直接对压缩态数据操作可以使执行 引擎的查询效率比较高。在接下来的章节中，我们分别研究在存储层以及逻辑层 数据压缩及其访问的过程，其中以压缩整数访问以及数据仓库中采取的压缩态访 问为例进行研究。 3 1 压缩态整数访问 本节中我们主要来分析整数的压缩结构和压缩态数据访问，以此来了解压缩 数据的访问过程及其原理，压缩整数的本质其实就是对二进制流的压缩过程。 1 7 天津师范人学硕士学位论文 3 1 1 整数压缩流程 整数压缩采用空格或者零消除算法，针对0 x o 0 0 0 0 0 0 0 o x l f f f f f f f 间的3 2 位无符号整数，而大于o x l f f f f f f f 的整数不能压缩，为了将整数压缩用于数据 库，首先对其可压缩范围进行扩充，使其能够对任意的3 2 位无符号整数进行压 缩。 压缩后的数据依照压缩前的顺序连续存放在一起，并且压缩后整数各字节的 顺序与内存中整数的存放顺序相反，即高地址为最低位，低地址为最高位。定位 压缩态数据是指一个在包含n 个整数的压缩态数据块中，假设其大小是s 字节， 对于给定的任意整数o ， ，找出第1 个整数在压缩态数据中的首地址。例如： 第0 个整数在压缩态数据中的首地址是o ，如果它占2 个字节，则第1 个整数在压缩 态数据中的首地址即为2 ，依次类推。因此，只要找到了某个整数在压缩态数据 中的首地址，就可以不用解压整块数据而直接取出其值，扩展后的定位算法如下 【1 8 】： p a c k l o c a t e ( n ：整数个数；p o s ：待定位的位置号；b u f 压缩态数据首地址) b e g i n i n d e x = 0 f o ri - 0t op o s - 1d o b e g i n 仃n p = b u f 【i n d e x 】 i f ( n i l p & o x 8 0 ) ! = o 臼n p 最高位是l t h e ni n d e x = i n d e x + 1 第i 个整数占1 个字节 e l s ei f ( t n l p & o x 4 0 ) ! = o 胁p 次高位是1