列存储系统的若干关键技术研究.pdf

幕季天学学校代码:10255 学号:104962 博士学位论文列存储系统的若干关键技术研究 Research on Some Key Technologies 专业名称: 控制理论与控制工程作者姓名: 指导教师: 丁祥武乐嘉锦完成日期: 2012年12月 Y2278994 东华大学学位论文原创性声明本人郑重声明:我恪守学术道德,崇尚严谨学风。所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写,我对所写的内容负责,并完全意识到本声明的法律结果由本人承担。学位论文作者签名:了砰或日期: ≯/多年2月2牛日东华大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定, 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版, 允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口,在——年解密后适用本版权书。本学位论文属于不保密《. 日期:矽侈年2月2户日期:加I弓年≯月“日东华大学博士学位论文摘要摘要当今,许多企事业单位的高管人员,迫切需要高性能的分析型数据库管理系统,用于分析大数据,辅助决策。列存储技术在处理大数据方面,显著优于行存储技术,所以吸引了许多学者的研究。列存储技术的研究取得了一些成果,但是关于列存储系统的存储优化、查询优化和查询执行等关键技术还有待进一步研究。在列存储系统中,按列存储数据,使得在查询处理时能够只读取查询所需要的列,避免读入无关的列。按列存储的数据具有很好的可压缩性,在查询处理过程中可以直接对压缩数据进行处理。这两点使得列存储系统在查询处理过程中的数据I/O效率比行存储高得多,有利于提高查询处理的速度。另一方面,对按列存储的数据进行查询处理时,需要将分散存储在不同位置的多列数据进行元组重构。元组重构形成了列存储系统中的一个重要性能瓶颈。本文以国家工信部核高基重大专项课题“数据仓库专用DBMS原型系统研制”()和国家自然科学基金项目“数据仓库中行列混合存储引擎的优化模型”(61070031)为依托,以提高列存储系统的查询性能为目标,对影响列存储系统性能的一些关键技术进行了深入研究。本文主要做了以下几个方面的工作: (1)研究列存储系统中数据存储布局对元组重构性能的影响后,提出了一个以列存储为基础,结合组合多列的存储模型。该模型对历史查询使用数据的方式进行分析,分析一个逻辑表中的哪些列经常一起被查询输出,将这些列进行物化,供后续查询使用。对需要物化的多列,首先形成逻辑上的一个投影并进行水平划分,然后对划分的每一块,在块内按列组织并压缩后存储。这样能充分利用列存储的优势,同时也能减少元组重构的开销,为后续查询提供了最优存储。(2)传统B+树索引是稀疏的,对其搜索的路径较长,对其进行插入和搜索的效率较低,不适合分析型应用。对此,本文提出了一种精简的、适合于东华大学博士学位论文摘要列存储的B+树结构一RB+树。RB+树几乎是一棵满的平衡二叉树,一页能容纳更多的索引项,因而能用较矮的RB+树存储大量的索引项。按这种结构树组织数据,搜索数据的路径短,搜索效率高。关于RB+树索引的创建和维护, 分别对行号索引和列值索引提出了自底向上的高效创建方法和维护方法。(3)研究了数据库中的数据压缩技术,包括轻量级的压缩方法、压缩粒度的选择和压缩方法的选择策略。特别对位图压缩技术进行了深入的研究,提出了一种富扩展划分位图索引和一种自适应的划分字对齐压缩方法(APWAH)。富扩展划分位图包含了一些统计信息,为直接使用划分位图进行聚集操作提供了方便。,,提高了压缩效率和查询处理效率。同时研究了区级压缩,区级压缩同时具有压缩率高和压缩管理方便的优点。本文提出根据数据的分布情况,自适应地选择区的大小。一个区由若干块构成,每区的块数不一定相同。这样可以根据相邻数据块之间的相似性,灵活地进行区划分,不受区大小的限制,保证区内数据分布特征相似性强,区之间数据分布特征相似性弱,以便对每个区选择更合适的压缩方法。关于压缩方法的选择,建立了一个数据分布特征模型,并根据提出的模型建立了选择压缩方法的决策方案。(4)研究缓冲区管理技术,提出了一种适应于列存储系统的三级缓冲区管理方案。在全局级,使用两条链分别管理系统的自由缓冲区和所有查询使用的缓冲区,对使用的缓冲区按综合自适应置换策略进行置换。一个缓冲