浓缩数据立方高效实化和快速查询方法研究

摘要

联机分析处理(OLAP)服务器中以数据立方作为基本的数据模型。为了提高OLAP查询效率，数据立方的构建成为许多研究的焦点。除了可以利用浓缩数据立方来减少数据立方的尺寸，从而大幅减少数据立方的计算时间与存储开销外,在应用实践中，往往还可以通过预先将数据立方进行实化的方法提高OLAP的查询响应速度。因此,进一步研究复杂数据立方的快速计算方法、浓缩数据立方在不同存储介质中的高效实化方法、以及如何利用实化数据快速响应查询等具有重要意义。
　　为了解决层次结构引入到数据立方的构建中带来的问题，提出了层次前缀立方的结构。层次结构带来了两个主要问题：一是立方格上的节点急剧增加，它的模型更加复杂，为了有效对其计算，需要开发新的立方格遍历方法；二是数据立方中需要实化的元组数急剧增加，为有效利用空间，需要研究新的存储模式，以消除各种形式的冗余。结合基本单元组浓缩与小方内前缀共享这两种方法，就得到了一种新的数据立方结构：前缀立方，但是，前缀立方不能直接支持维层次。为此，对前缀立方组织结构进行扩展，使之能够计算层次数据立方，并提出了一种新的结构：层次前缀立方（HierPrefixCube），将层次数据立方组织成一组共享前缀簇树，从而在数据立方尺寸压缩、数据立方元组恢复以及数据立方查询这几个方面求得了平衡。试验结果表明，层次前缀立方在实现了基于维层次查询的同时，其计算时间代价较低，对数据立方尺寸压缩的效果也很明显。
　　预先计算并实化数据立方，可大大缩短OLAP查询响应时间。但在外存存储实化数据，仍会带来大量的I/O操作。随着内存价格逐渐地降低，将数据立方的一个子集在内存实化，将特别适用于有时间约束的联机分析处理环境。为此，在现有技术的基础上，以元组为实化单元构建适用于浓缩数据立方的内存实化数据选择模型。以内存空间至少能容纳最细粒度数据小方为前提，在内存中构造两级元组存储结构，达到避免数据立方重新计算，快速准确响应查询的目的。并进一步对查询进行优化，构造性能更好的选择模型。由于最细粒度小方元组和其它一些粗粒度元组都在内存中，避免了费时的外存存取，数据立方更新和维护代价也得以降低。试验证明，在内存实化数据立方可有效降低查询响应时间，浓缩数据立方优先小尺寸是内存实化元组几种不同的选择模型中时间最优的。
　　通过在内存实化数据立方可以缩短查询响应时间，但易受内存空间的限制，很难满足尺寸较大数据立方的实化要求。随着闪存技术的快速发展，基于NAND闪存的固态硬盘具有了读取速度快、功耗低等优点，且其成本要比内存低得多，访问速度比传统硬盘要快得多。为此，结合浓缩数据立方的元组存储特征，提出了在内存实化粗粒度的小方，在闪存实化细粒度的元组，在硬盘存放事实表的三级存储结构。由于闪存具有读、写、擦除的时间延迟不均衡、非本地更新和擦除次数受限等特性，对于闪存中存放的实化数据立方元组采用了多级动态完美哈希索引，并把实化过程中的写操作转变为串行化的操作序列，以逐一追加的方式解决了由数据插入引发的闪存“频繁写”问题。实验结果表明，基于该索引结构的数据立方存储方法，既能提供高于磁盘存储的查询响应速度，又能避免内存空间不足的问题。
　　使用实化视图加速查询是一种常用的查询优化方法，在多维聚集应用中，其本质也是利用实化的数据立方来快速响应查询。含有SPREADSHEET子句的SQL语句增强了多维计算能力。研究了含有SPREADSHEET子句的实化视图匹配，利用实化数据加快SPREADSHEET查询的响应速度。提出了含有SPREADSHEET子句的视图匹配算法。实验结果表明，含有SPREADSHEET子句的视图匹配方法，具有良好的查询响应能力和良好的可扩展性。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 课题背景

1.2 国内外研究概况

1.3 本文的研究内容

1.4 课题来源

2 层次前缀立方的有效计算

2.1 引言

2.2 前缀立方分析

2.3 层次前缀立方的结构及计算

2.4 实验研究

2.5 本章小结

3 浓缩数据立方的内存实化

3.1 引言

3.2 内存实化方案

3.3 内存数据立方的查询

3.4 实验结果分析

3.5 本章小结

4 浓缩数据立方的闪存实化

4.1 引言

4.2 相关工作

4.3 闪存存储方案

4.4 基于NAND闪存的数据立方哈希索引

4.5 哈希索引的归并算法

4.6 实验结果分析

4.7 本章小结

5 含有SPREADSHEET子句查询的实化视图匹配

5.1 引言

5.2 相关研究

5.3 实化视图匹配算法

5.4 实验结果

5.5 本章小结

6 总结与展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

未标题