基于三级存储器的数据库查询处理技术研究

摘要

日益加剧的竞争迫使企业必须构建能够迅速、准确地分析和挖掘行业信息的数据仓库系统，目前的磁盘存储器却无法满足企业日益增长的海量信息管理需要，由主存、磁盘和联机使用的第三级存储器构成的三级存储器系统为海量数据的管理提供了一种廉价可行的解决方案。然而三级存储器与磁盘系统的物理特性差异很大，为磁盘存储器设计的存储结构和操作算法无法直接移植到三级存储器中，需要针对三级存储器的特点设计优化的存储结构与高效的关系操作算法。本文结合三级存储器的物理特征与联机分析处理应用的特点，设计出了适合管理三级存储器上海量数据的读优化的存储结构、关系操作算法和查询优化方法。主要研究成果如下：
　　在三级存储器上的数据组织方面，提出了三级存储器各存储层次间的数据分布方法、第三级存储器上针对读操作优化的数据组织结构和将数据迁移到第三级存储器时的数据预处理方法。由于三级存储器各个存储层次的物理特性存在差异，并且不同数据的访问频率不同，合理地在三级存储器上分布数据会显著提高三级存储器的访问性能。第三级存储器中的数据主要面向分析型应用，针对分析型应用的特点提出了数据紧缩、聚簇、按列方式的数据存储、引入多个关系副本等一系列方法，每种方法针对不同类型的查询。通过选择合适的数据组织方法，可以显著提高从第三级存储器访问数据的效率。数据从磁盘迁移到第三级存储器之前，通过预排序、代理信息抽取、聚集的预计算等一系列方法，显著地提高查询执行效率。通过在磁盘中保存必要的代理信息，使一部分查询可以在磁盘上直接得到回答。
　　在基于三级存储器的关系操作算法方面，重点研究了三级存储器上的非阻塞连接算法和基于属性分离的连接算法。设计与实现了两种尽早产生连接结果的非阻塞式连接算法CDT-PH和CDT-Merge。传统的连接操作是阻塞式操作，需要对磁盘中的数据进行预处理，然后才能产生第一个连接结果。阻塞式连接不适用于数据可视化等应用。非阻塞式连接算法不仅在连接开始的时候就能产生结果，而且整体性能与目前最高效 CDT-GH性能很相近， CDT-Merge算法的性能甚至高于CDT-GH算法。设计与实现了基于属性分离的磁带-磁带连接算法ASJ。针对通常磁带上连接操作具有的数据多遍扫描问题和冗余 I/O问题，ASJ算法利用属性分离技术、连接索引技术有效地避免了以上问题。ASJ算法比目前最好的磁带-磁带连接算法CTT-GH性能提高很多。该算法最大的优点是能够将磁带-磁带连接算法转变为磁盘上的连接算法与磁带数据的一遍扫描操作。
　　在基于三级存储器的查询优化方面，提出了适用于三级存储器的代价模型和能够处理多关系副本的查询优化算法。传统的关系代价模型都是针对磁盘上的关系操作，不能够直接用于估算第三级存储器上的操作代价。提出的代价模型不仅能够估算第三级存储器上关系操作的代价，而且能够比较磁盘上关系操作与第三级存储器上相同关系操作的代价。提出的查询优化方法不仅能够为查询中的关系操作选择优化的执行算法，而且能够为参与查询的关系选择最优数据组织方式的关系副本，从而显著地提高查询效率。
　　最后基于上述研究成果，设计与实现了一个数据库原型系统 TERMS。TERMS具有如下特点：(1)能够自动地在指定时机将磁盘数据迁移到第三级存储器，同时能够进行指定的数据预处理。(2)采用读优化的存储结构组织第三级存储器上的数据。(3)采用针对第三级存储器中数据特点的关系操作算法和基于代价的查询优化方法。(4)通过设备层隔离第三级存储器的物理特性差异。

目录

基于三级存储器的数据库查询处理技术研究

DATABASE QUERY PROCESSING TECHNIQUES BASED ON TERTIARY STORAGE

摘 要

Abstract

目 录

Contents

第1章 绪 论

1.1 研究的目的和意义

1.2 国内外研究现状

1.3 本文研究内容及组织

第2章 预备知识

2.1 引言

2.2 三级存储器

2.3 实验环境介绍

2.4 本章小结

第3章 数据组织方法与预处理技术

3.1 三级存储器各存储层次间的数据分布方法

3.2 三级存储器中读优化的数据组织方法

3.3 数据预处理

3.4 本章小结

第4章 基于三级存储器的关系操作算法

4.1 基于属性分离的连接算法

4.2 非阻塞式的连接算法

4.3 其他关系操作算法

4.4 本章小结

第5章 基于三级存储器的查询优化方法

5.1 引言

5.2 查询计划的表示

5.3 代价模型

5.4 查询优化方法

5.5 本章小节

第6章 基于三级存储器的数据库原型系统

6.1 引言

6.2 TERMS的体系结构

6.3 TERMS的几个实现技术

6.4 本章小结

结论

参考文献

攻读博士学位期间发表的学术论文

科研经历

攻读博士学位期间获得的奖励

哈尔滨工业大学博士学位论文原创性声明

哈尔滨工业大学博士学位论文使用授权书

哈尔滨工业大学博士学位涉密论文管理

致 谢

个人简历