摘要：当今,许多企事业单位的高管人员,迫切需要高性能的浅析型数据库管理系统,用于浅析大数据,辅助决策。列存储技术在处理大数据方面,显著优于行存储技术,所以吸引了许多学者的探讨。列存储技术的探讨取得了一些成果,但是关于列存储系统的存储优化、查询优化和查询执行等关键技术还有待进一步探讨。在列存储系统中,按列存储数据,使得在查询处理时能够只读取查询所需要的列,避开读入无关的列。按列存储的数据具有很好的可压缩性,在查询处理历程中可以直接对压缩数据进行处理。这两点使得列存储系统在查询处理历程中的数据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。本论文探讨的内容是我们所研制的原型系统中的关键技术。探讨的结果对提升系统的总体性能起到了决定性的作用。关键词：列存储论文DWMS论文物化多列论文RB+树索引论文区级压缩论文富扩展划分位图论文APWAH压缩策略论文缓冲区管理论文基于带值路径的物化论文
摘要5-8
Abstract8-17
第1章 绪论17-32
1.1 探讨背景与作用17-18
1.2 列存储技术的形成与进展近况18-23
1.2.1 列存储技术的形成19-20
1.2.2 列存储系统的进展近况20-23
1.3 列存储系统的关键技术23-25
1.4 本论文的探讨内容25-29
1.5 本论文的组织结构29-32
第2章 基于列存储的组合多列存储模型32-49
2.1 引言32-33
2.2 相关工作33-36
2.3 概念和定义36-38
2.4 自适应的组合多列38-43
2.4.1 找强相关的属性集38-41
2.4.2 自适应的多列组合41-43
2.5 组合多列的存储实现43-45
2.5.1 存储组合多列的现有策略43-44
2.5.2 一种组合多列的列存储策略44-45
2.6 块中行组的行数计算45-46
2.7 在查询中对多列的利用和管理46-48
2.7.1 组合多列表的命名46
2.7.2 组合多列表的利用46-48
2.8 本章小结48-49
第3章 列存储系统中的B+树索引技术探讨49-67
3.1 引言49-51
3.2 相关工作51-53
3.3 一种精简的B-树索引—RB+树53-55
3.3.1 RB+树的定义53-55
3.3.2 RB+树和传统B+树的比较55
3.4 行号索引55-61
3.4.1 行号索引的概念55-56
3.4.2 行号索引的创建56-57
3.4.3 行号索引的性能浅析57-58
3.4.4 行号间隙不足58
3.4.5 行号索引的维护58-61
3.5 列值索引61-64
3.5.1 列值索引的概念与基本实现62
3.5.2 列值索引的浅析62-63
3.5.3 列值索引的压缩63
3.5.4 列值索引的维护63-64
3.6 实验评估64-66
3.7 本章小节66-67
第4章 列存储数据的压缩技术探讨67-110
4.1 引言67-69
4.2 相关工作69-74
4.3 富扩展划分位图索引74-78
4.3.1 富扩展划分位图索引的创建75-76
4.3.2 富扩展划分位图的利用76-78
4.4 一种自适应划分字对齐的位向量压缩策略78-92
4.4.1 字节对齐和字对齐的位向量压缩技术回顾79-81
4.4.2 自适应划分字对齐的位向量压缩81-86
4.4.3 基于APWAH的查询处理86-92
4.5 压缩策略选择92-99
4.5.1 定义和符号94-95
4.5.2 压缩策略选择对策95-98
4.5.3 压缩策略选择对策浅析98-99
4.6 区级压缩99-103
4.6.1 数据仓库的存储层次介绍100-101
4.6.2 区级压缩的概念及其实现101-103
4.7 关于压缩编码的两个注记103-105
4.8 实验评估105-109
4.8.1 对选择对策的评估105-106
4.8.2 评估APWAH的有效性106-109
4.9 本章小结109-110
第5章 列存储系统的缓冲区管理技术探讨110-129
5.1 引言110-111
5.2 相关工作111-118
5.4 列存储系统中的缓冲区管理案例118-128
5.4.1 列存储系统的工作负载和存储特点118-119
5.4.2 列存储系统中的缓冲区管理案例设计119-128
5.5 本章小结128-129
第6章 列存储系统中的物化技术探讨129-149
6.1 引言129-130
6.2 相关探讨工作130-131
6.3 基于带值路径的物化131-145
6.3.1 物理操作符132-134
6.3.2 物理执行计划与物化对策134-136
6.3.3 传递块136-138
6.3.4 带值路径与含带值路径的物理执行计划138-140
6.3.5 寻带值路径140-142
6.3.6 基于带值路径的物化技术—VPM142-145
6.4 实验浅析145-148
6.4.1 三种物化技术针对高选择率的查询性能比较145-147
6.4.2 三种物化技术针对低选择率的查询性能比较147-148
6.5 本章小节148-149
第7章 总结与展望149-153
7.1 本论文探讨工作总结149-151
7.2 未来工作展望151-153
本站原创