混合盘散列连接算法设计及其应用

摘要

随着新一代存储设备固态盘的发展，由固态盘和硬盘组成混合存储系统已成为热点研究课题。本文利用固态盘和硬盘的存储特性，对传统散列连接（GHJ、HHJ）进行优化，得到四个基于混合存储系统设计的散列连接算法（CGHJ、CHHJ、H-CGHJ和 H-CHHJ，合称混合盘散列连接），并给出算法的I/O代价和时间代价模型；同时，设计了查询计划选择器，选择适应当前可用资源、性能较优的连接算法，实现性能体面降级。在工程应用方面，设计了分布式流量计算系统处理交通数据，将混合盘散列连接算法作为流量计算系统的核心处理算法，统计区域间交通流量信息。本文主要贡献如下：
　　1.设计混合盘散列连接算法。将固态盘作为中间存储缓存，设计了一组新的连接散列算法（CGHJ，CHHJ，H-CGHJ和H-CHHJ），并给出两种缓存分配方案，优化算法性能。
　　2.连接算法I/O代价模型和时间代价模型。通过分析连接算法执行过程中各阶段操作行为，给出算法执行时的I/O代价和时间代价的估算模型，并给出算法各阶段对外存进行访问时的吞吐量估算方法。
　　3.查询计划选择器与性能降级机制。设计了查询计划选择器，在内存及固态盘等计算资源有限的情况下，选择性能最优的连接算法，实现系统性能体面降级。
　　4.将混合盘连接算法应用到交通数据处理中。混合盘散列连接算法作为系统核心处理算法，实现交通流量计算系统，统计不同区域之间的交通流量信息。
　　一系列实验结果表明本文设计的混合盘散列连接算法较传统散列连接（GHJ，HHJ）有明显的性能提升，从理论上估算连接算法实际执行耗时误差较小，查询计划选择器选择最优算法有很高的准确率。在工程应用方面，使用混合盘散列连接作为核心算法的流量计算系统在处理交通数据时拥有较好的计算性能。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 背景及意义

1.2 本文研究内容及贡献

1.3 论文组织

1.4 本章小结

第2章 相关工作

2.1 固态盘存储技术

2.2 传统连接算法

2.3 散列连接算法性能优化

2.4 固态盘在数据库系统中的应用

2.5 本章小结

第3章 混合盘散列连接算法设计及查询计划选择

3.1 混合盘散列连接算法设计及I/O代价分析

3.2 混合盘散列连接算法参数配置优化

3.3 连接算法时间代价估算方法

3.4 混合盘散列连接拓展算法

3.5 查询计划选择与性能降级机制

3.6 实验验证与结果分析

3.7 本章小结

第4章 混合盘散列连接算法在交通数据处理中的应用

4.1 系统需求背景

4.2 流量计算系统整体设计

4.3 系统核心模块设计

4.4 系统实现与性能测试分析

4.5 本章小结

第5章 总结和展望

5.1 总结

5.2 展望

参考文献

致谢

攻读学位期间参加的科研项目和成果