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

发布时间：2018-10-21 20:12

【摘要】：当今,许多企事业单位的高管人员,迫切需要高性能的分析型数据库管理系统,用于分析大数据,辅助决策。列存储技术在处理大数据方面,显著优于行存储技术,所以吸引了许多学者的研究。列存储技术的研究取得了一些成果,但是关于列存储系统的存储优化、查询优化和查询执行等关键技术还有待进一步研究。在列存储系统中,按列存储数据,使得在查询处理时能够只读取查询所需要的列,避免读入无关的列。按列存储的数据具有很好的可压缩性,在查询处理过程中可以直接对压缩数据进行处理。这两点使得列存储系统在查询处理过程中的数据I/O效率比行存储高得多,有利于提高查询处理的速度。另一方面,对按列存储的数据进行查询处理时,需要将分散存储在不同位置的多列数据进行元组重构。元组重构形成了列存储系统中的一个重要性能瓶颈。本文以国家工信部核高基重大专项课题“数据仓库专用DBMS原型系统研制”(2010ZX01042-001-003-04)和国家自然科学基金项目“数据仓库中行列混合存储引擎的优化模型”(61070031)为依托,以提高列存储系统的查询性能为目标,对影响列存储系统性能的一些关键技术进行了深入研究。本文主要做了以下几个方面的工作： (1)研究列存储系统中数据存储布局对元组重构性能的影响后,提出了一个以列存储为基础,结合组合多列的存储模型。该模型对历史查询使用数据的方式进行分析,分析一个逻辑表中的哪些列经常一起被查询输出,将这些列进行物化,供后续查询使用。对需要物化的多列,首先形成逻辑上的一个投影并进行水平划分,然后对划分的每一块,在块内按列组织并压缩后存储。这样能充分利用列存储的优势,同时也能减少元组重构的开销,为后续查询提供了最优存储。 (2)传统B+树索引是稀疏的,对其搜索的路径较长,对其进行插入和搜索的效率较低,不适合分析型应用。对此,本文提出了一种精简的、适合于列存储的B+树结构——RB+树。RB+树几乎是一棵满的平衡二叉树,一页能容纳更多的索引项,因而能用较矮的RB+树存储大量的索引项。按这种结构树组织数据,搜索数据的路径短,搜索效率高。关于RB+树索引的创建和维护,分别对行号索引和列值索引提出了自底向上的高效创建方法和维护方法。 (3)研究了数据库中的数据压缩技术,包括轻量级的压缩方法、压缩粒度的选择和压缩方法的选择策略。特别对位图压缩技术进行了深入的研究,提出了一种富扩展划分位图索引和一种自适应的划分字对齐压缩方法(APWAH)。富扩展划分位图包含了一些统计信息,为直接使用划分位图进行聚集操作提供了方便。(?)PWAH能根据位向量中0-1分布情况,自适应地选择最合适的0-填充段长和1-填充段长,提高了压缩效率和查询处理效率。同时研究了区级压缩,区级压缩同时具有压缩率高和压缩管理方便的优点。本文提出根据数据的分布情况,自适应地选择区的大小。一个区由若干块构成,每区的块数不一定相同。这样可以根据相邻数据块之间的相似性,灵活地进行区划分,不受区大小的限制,保证区内数据分布特征相似性强,区之间数据分布特征相似性弱,以便对每个区选择更合适的压缩方法。关于压缩方法的选择,建立了一个数据分布特征模型,并根据提出的模型建立了选择压缩方法的决策方案。 (4)研究缓冲区管理技术,提出了一种适应于列存储系统的三级缓冲区管理方案。在全局级,使用两条链分别管理系统的自由缓冲区和所有查询使用的缓冲区,对使用的缓冲区按综合自适应置换策略进行置换。一个缓冲区是否可被置换,不仅考虑正在执行的查询,同时还考虑了一定量的后续查询。在查询级,每个执行的查询都用一条主链管理它使用的缓冲区,一个查询处理中每出现一个并发操作阶段,都从主链中产生一条相应的分支链来管理并发操作阶段使用的缓冲区。在操作阶段级,对每个操作阶段设计了一种灵活且自适应的缓冲区分配策略(MG-x-y-z)和与它的访问模式相适应的置换策略。提出的三级缓冲区管理方案充分考虑了分析型工作负载的特点、数据访问模式特点和可用的缓冲区情况,也考虑了数据预取。 (5)研究列存储系统中的物化技术后,针对现有物化技术的不足,提出了基于带值路径的物化技术(PVM)。PVM在物理执行树中增加了带值路径,并使用传递块来保存执行的中间结果。通过这种方法,避免了查询执行过程中对原始数据的重读。对带值路径中包含的位向量,使用本文提出的APWAH压缩方法进行压缩,减少或避免了因中间结果太大而造成的额外I/O。本文研究的内容是我们所研制的原型系统中的关键技术。研究的结果对提高系统的总体性能起到了决定性的作用。
[Abstract]:......
【学位授予单位】：东华大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP333

【相似文献】