Energy-Efficient Join Algorithms In Multi-Memory Hierarchies

Join is the core operation and energy-efficient join algorithm has been highly concerned in power-aware DBMS. Solid state driver(SSD) has a faster random I/O speed compared with hard disk, this advantage can be used to improve energy-efficiency of join algorithm. To reduce serious random-writes in partition phase of hash join, which affects the performance and energy efficiency, this thesis proposes solutions by considering the different memory hierarchies(RAM+SSD or hard disk, and RAM+SSD and HDD). The contributions are as follows:1. The SFHJ join algorithm is presented, which stores all the partitions of a relation in one temporary file during the partition stage and takes full advantage of the superiority of SSD in low latency of random read and high bandwidth of sequencial write.2. An optimized bucket buffer allocation scheme for hybrid hash join is contrived and its corresponding optimized hybrid hash join algorithm (OHHJ) to reduce random I/Os during the partition phase as much as possible.3. By using SSD as the memory extension and combined with SFHJ, a combo GRACE hash join algorithm(CGHJ) has been put forward, which enchances the GRACE hash algorithm by caching bucket segments in SSD and migrating them to HDD after assembling them into large I/O unit.The experiment results show that the energy efficiency of OHHJ is much higher than HHJ, while the energy efficiency of SFHJ and CGHJ is promising as well.