列式数据库压缩方法探讨

列式数据库——压缩算法探讨OUTLINE简介背景优势现状数据压缩简介列数据库压缩算法列数据库简介列存储数据库是相对于传统的以记录或数据行（Record，Row）为单位进行数据处理的数据库（例如SQLServer）来说的，它以数据表中的列（Column）为单位对数据进行存储和查询等处理。传统的关系型数据库,即数据按记录存储,每一条记录的所有属性都存储在一起,如果要查询一条记录的一个属性值,需要先读取整条记录的数据。而列数据库是按数据库记录的列来组织和存储数据的,数据库中每个表由一组据库记录的列来组织和存储数据的,数据库中每个表由一组页链的集合组成,每条页链对应表中的一个存储列,而该页链中每一页存储的是该列的一个或多个值。列数据库产生背景现今的关系数据库系统大多衍生于70年代的SystemR项目原型和Ingres项目原型，但是随着应用和硬件技术的发展，DBMS的需求不仅仅满足于SystemR和higres设计面向OLTP数据处理的初衷，而更多的是地球科学、医学等数据仓库以及决策支持系统等的OLAP的数据处理需求，而在这些应用中，大多数信息都是散乱的、稀疏的，并且需要对数据进行大量的查询处理，以便对其进行数据有效的分析处理;同时由于硬件技术的发展，传统的高性能硬件逐渐大众化，使得数据仓库等应用得更加普遍。因此为了满足该类应用场景的需求，数据库系统发展的方向由满足OLTP数据处理的需求转向满足OLAP数据处理的需求，OLAP是对列进行操作的，于是便衍生出面向分析处理(OLAP)的列存储数据库系统。列数据库优势能够迅速的执行复杂查询压缩技术为数据仓库、商务智能应用中巨大的数据量节约存储成本节省大量I/O带宽列数据库发展现状比较著名的列数据库系统有开源项目C-Store，是由麻省理工、耶鲁大学、布朗大学等合作研发的，并于2005年发布第一版本，2006年升级为第二版本。在C-Store的研究基础上，又衍生出来商业化的Vertica以及内存数据库系统MonetDB。Google的BigTable也是一种面向列存储的数据库系统，该系统是Google内部开发用来处理大数据量的系统，Googfe的很多项目包括网索引、GoogleEarth和谷歌财务都是建立在该系统基础上的。SQLSERVER2011也支持列存储索引FACEBOOK的数据仓库RCFile：一个结合了行存储和列存储的数据管理系统数据压缩简介定义：在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。流行算法：列数据库压缩随着数据库的规模越来越大，如何在数据库中使用数据压缩是很多研究者关注的热点。然而，传统的行存储数据库由于存储的数据的差异性较大，对其采用压缩也往往每次查询时不得不进行解压。不过压缩后数据量小的优点在某种程度上还是胜过解压的额外开销的。列存储的概念提出以后，由于列存储的特点，它非常适合轻量级压缩，从而可以不解压而直接访问压缩态的数据。公司组织数据仓库大小（TB）原始数据大小（TB）数据行数数据库操作系统数据库厂商存储厂商YAHOO100.38617.0143853ORACLEUNIXORALCEEMCNielsenMediaResearch17.68517.9695024SYSBASEIQUNIXSYSBASEEMC列数据库主要压缩算法在SIGMOD06会议上,DanielJ.Abadi通过在开源的列数据库C-Store上进行实验比较和理论分析指出,主要的压缩方法有以下三类:游程编码算法(Run-lengthEncoding)词典编码算法(DictionaryEncoding)位向量算法(Bit-VectorEncoding)。游程编码算法(RunlengthEncoding)游程编码算法是比较适合列数据库的压缩算法之一,即用一个三元组记录数据值、数据出现的起始位置和持续长度(即行程),以代替具有相同值的若干连续原始数据,使三元组的存储长度少于原始数据的长度。三元组描述为(X,Y,Z)其中X:数据的值,Y:起始位置,Z:长度。订单类型产品ID产品类型Q112Q115Q118Q114Q125Q232Q234订单类型产品ID产品类型Q1,1,51,1,42Q2,6,22,5,253,7,184524压缩后词典编码算法(DictionaryEncoding)词典编码就是生成一个原始值替代值的对照词典。为了起到压缩的作用,替代值的长度小于原始值的长度。存储的时候,只存储替代值而不是原始值,从而压缩了存储空间。字典表Q100Q201订单类型Q1Q1Q1Q1Q1Q2Q2订单类型00000000000101压缩后位向量编码算法(Bit-VectorEncoding)位向量编码是为每一个不同的取值生成一个位向量,根据位向量(串)中不同的位置取值0或1来对应并确定不同的原始值。订单类型Q1Q1Q1Q1Q1Q2Q2Q1位向量Q2位向量10101010100101压缩后优劣对比名称游程编码词典编码位向量算法共同特征适用于重复数据较多，不适用于重复数据较少适用数据列的不同特征重复数据的排序比较规则取值空间较小取值空间较小不适用的数据列不同特征排序不规则a)取间空间较大b)数据类型长度比词典符号长度更小取值空间较大优点对于适用的数据特征,有比较好的压缩效果a)对于数据类型要求较低b)对于数据排序要求较低a)对于数据类型要求较低b)对于数据排序要求较低c)在有些情况,查询效率要比词典编码高缺点对列值的重复性以及排序要求较高需要创建一张词典表,增加维护代价,如果数据重复性不高,词典表会过于巨大用位置代表数据,如取值空间较大,或重复性较低,占用空间会比较大LZ77压缩算法原理（1）LZ77算法在某种意义上又可以称为“滑动窗口压缩”，其基本原理是将已输入数据流的一部分作为字典，编码器为输入数据流开一个窗口，并且随着对字符串的编码不断地将窗中的数据从右一道左。滑动窗一般分为两部分，左边的部分称为搜索缓冲存储器，这一部分是当前的字典，始终存有刚刚输入的字符和已编码过的字符；右边的部分称为向前的缓冲存储器。其中存有即将被编码的输入字符集。在实际应用中，搜索缓冲存储器的窗口一般较长，可长达几千字节，而向前的缓冲存储器只有几十字节。LZ77编码举例sirsideastmaneasilyeasesseasickseals步骤位置匹配串输出11－－从右向左搜索22eas(7,3,e)34eas(15,3,e)第一个参数代表在在这个窗口的位置上中后退N个字符第二个参数代表匹配到的最长字符串的长度第三个参数代表未匹配到的第一个字符

sirsideastmaneasilyeasesseasicksealsLZ78算法介绍(1)LZ78是一个基于字典的压缩算法，需要维护一个字典，该算法输出的码字由两个元素组成:一个参照最长匹配字典输入索引以及一个非匹配的字符。其基本思想就是不断地从字符流中提取新的字符串，然后用码字表示这个词条，因此，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。LZ78算法介绍(2)例如，字符串ABBCBCABABCAABCAAB，其过程如图1234567ABBCBCABABCAABCAABoutputIndexString(0,A)1A(0,B)2B(2,C)3BC(3,A)4BCA(2,A)5BA(4,A)6BCAA(6,B)7BCAABLZW算法LZW编码是围绕称为词典的转换表来完成的。LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。

LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法LZW编码举例位置123456789字符ABBABABAC步骤位置码字词典输出1A2B3C114AB1225BB2336BA2447ABA4558ABAC76－－－3输入数据流：适应列数据库的LZ算法1LZ77和LZ78算法的结合背景：数据列中的数据项一般在上下文中更容易找到匹配串；数据列的存储类型固定，因此每项的存储空间固定，更易使用滑动窗口算法：采用两个滑动窗口，同时向后移动。一为比对窗口，2为待编码窗口初始字典置为空，先在最初的比对窗口中采用LZ78算法压缩，并将压缩的长度大于1的字符串存入字典。带编码窗口先和比对窗口进行匹配，并将匹配出来的字符串存入字典，再在字典表中查看是否有匹配的字符串。优点适合与数据库的数据特性压缩出来的数据可以方便进行数据库的增删改查，order，join等操作（即不解压数据，直接对压缩态数据进行操作）适应列数据库的LZ算法2RowId域名123……567/index滑动窗口编码窗口压缩后RowId域名123……50010116001cctv0107100/index字典表001100大致思路如下图：适应列数据库的LZ算法3原数据：Source.txt文件大小：21762字节LZ77算法压缩后大小：2869字节LZW算法压缩后大小：2172字节自定义算法压缩后字节：2791字节idNo.idNo.idNo.idNo.idNo.12000070482001070615200207082220020709292003071322000070492001070616200207082320020709302003071332000070410200207041720030713242