一种利用固态盘特性的散列连接改进算法

An Improved Hash Join Algorithm by Exploiting SSD I/O Characteristics

随着新一代存储设备固态盘的发展,如何发挥新存储设施的性能成为近年来的一个研究热点.将固态盘作为"黑盒",通过观察固态盘I/O外部特性,即考察访问粒度与访问队列深度与固态盘性能之间的关系,得出算法设计应遵循的原则,并应用到数据库散列连接算法的设计中.提出了并行化Grace散列连接设计方法,以及根据访问粒度、队列深度计算各阶段缓冲区大小的优化分配方法.一系列实验结果表明本文提出的并行散列连接方法能够充分发挥固态盘性能,优化的缓存分配方案可保证固态盘性能充分发挥而不浪费内存资源.

With the development of SSD,howto fully profit from the newstorage has become the hot research topic for recent years.Taking SSD as a black box,this paper derived some algorithm design principles by only knowing the I / O characteristics of SSD,to be specific,by looking into the relationship between access granularity and queue depth,and applied them to hash join in DBMS. We proposed a method to parallelize Grace hash join and invented a buffer allocation scheme based on access granularity and queue depth. Experiments result demonstrated that our proposed method could fully take advantage of the SSD performance gain,and the buffer allocation scheme worked well without wasting the memory resource unnecessarily.