多存储层次能效散列连接算法

摘要

连接是数据库系统查询处理中的一个核心操作，高能效连接算法是能效DBMS中的一个重要研究议题。固态盘和硬盘比较具有随机读写性能快的优势，数据库系统中合理利用这一优势提升连接算法的能效成为可能。本文针对散列连接分区阶段随机写严重的情况，分别在二存储层次（内存+固态盘或硬盘）和多存储层次（内存+固态盘和硬盘）两种情形下，提出了不同的解决方案消除随机I/O对算法性能和能效的不利影响。主要完成了以下几方面工作:
　　1.在数据库存储设备为固态盘的环境中提出了单文件的GRACE散列连接算法(SFHJ)，SFHJ分区阶段同一张表的所有分区存储在一个临时文件。该算法能利用固态盘随机读延迟低和顺序写带宽高的优势，提升连接算法性能。
　　2.在数据库存储设备为硬盘的环境中，提出通过缓存优化来减少随机I/O的缓存优化混合散列连接算法(OHHJ)，即通过合理优化分区阶段桶缓存的大小来尽量减少分区过程中产生的随机I/O。
　　3.在由HDD和SSD混合的数据库多存储层次系统中，结合SFHJ提出了基于硬盘和固态盘混合存储系统下的组合盘GRACE散列连接算法(CGHJ)。CGHJ对GRACE散列连接算法分区阶段作如下改进:将固态盘作为内存和硬盘之间的缓存，分区阶段桶缓存满后先写回固态盘的临时文件；临时文件缓存满后，利用迁移缓存将固态盘中的数据转移到硬盘的分区文件。同时在多存储层次系统下对HHJ进行改进，提出了CHHJ。
　　实验结果表明OHHJ能效要一直好于HHJ，而SFHJ和CGHJ在特定的条件下能效也能得到较大的提升。

目录

声明

摘要

第1章 绪论

1．1 背景及意义

1．2 本文研究内容及贡献

1．2．1 研究内容

1．2．2 本文贡献

1．3 论文组织

第2章 相关工作

2．1 数据库系统能效优化

2．2 数据库散列连接算法

2．2．1 GRACE散列连接算法

2．2．2 混合散列连接算法

2．3 散列连接算法性能优化

2．3．1 连接算法性能基于CACHE和缓存的优化

2．3．2 多核环境下散列连接算法性能的优化

2．3．3 散列连接算法I／O性能的优化

2．4 固态盘在数据库系统中的应用

2．4．1 基于SSD和HDD混合存储系统

2．4．2 基于闪存数据库系统的连接算法

2．5 本章小结

第3章 散列连接算法随机I／O消除

3．1 单文件的GRACE散列连接算法

3．2 缓存优化的混合散列连接算法

3．3 算法实现及能效分析

3．3．1 实验设备及环境

3．3．2 实验数据

3．3．3 SFHJ能效比较

3．3．4 OHHJ能效比较

3．4 本章小结

第4章 组合盘散列连接算法

4．1 GRACE散列连接算法I／O分析

4．2 基于SSD和HDD的CGHJ散列连接算法

4．2．1 CGHJ算法设计

4．2．2 CGHJ散列连接算法I／O分析

4．3 CGHJ算法实现及能效分析

4．3．1 数据规模对算法性能的影响

4．3．2 缓存对两种散列连接算法性能影响

4．3．3 固态盘缓存大小对CGHJ性能的影响

4．3．4 迁移缓存对CGHJ散列连接算法性能的影响

4．3．5 CGHJ和GHJ能耗比较

4．4 基于组合盘的混合散列连接算法

4．5 本章小结

第5章 总结和展望

5．1 总结

5．2 展望

参考文献

致谢

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