BF-Join: An Efficient Hash Join Algorithm for DRAM-NVM-Based Hybrid Memory Systems

摘要

Non-volatile memory (NVM) has been regarded as the next-generation memory that can replace DRAM in modern computer systems. However, NVM also has some limitations, e.g., read/write asymmetry and limited write endurance. Thus, a practical way is to construct hybrid memory composed of both NVM and DRAM. Such hybrid memory architecture introduces many new challenges for existing algorithms. In this paper, we focus on improving hash join algorithms for DRAM-NVM-based hybrid memory. In particular, we propose a memory-efficient and NVM-friendly join scheme called BF-Join. BF-Join has several new designs. First, BF-Join proposes to maintain the build table and the probe table on NVM to ensure the persistency of data as well as the avoidance of NVM writes. Second, BF-Join devises a Bloom filter based compact structure on DRAM to organize the partitions generated in the hash-join process, through which we can reduce the memory cost during the join process. Moreover, we propose an improved cache-optimized BF-Join that employs cache-friendly Bloom filters to reduce cache misses in the join process. We present theoretical analysis on the time and space complexity of BF-Join, and conduct experiments on a server equipped with DRAM and NVDIMM. The comparative results between BF-Join and four baseline hash join algorithms suggest the space efficiency and high time performance of our proposal.