Optimization Of Database Join Algorithms On DRAM/NVM-Based Hybrid Memory

In modern computer systems,Non-Volatile Memory(NVM)is considered a new generation of memory that can replace DRAM.Compared with DRAM,NVM has the advantages of non-volatility,high density and byte addressbility.However,NVM also has some disadvantages,such as asymmetric reads and writes,high write latency,and limited write endurance.Therefore,building a hybrid memory architecture consisting of NVM and DRAM is a viable approach for future computer systems.However,this hybrid memory architecture also presents many new challenges to existing algorithms,because the new algorithm must take into account the characteristics of DRAM and NVM together,especially to adapt to the special nature of NVM.The rapid development of computer technology and the explosive growth of data scale put forward higher requirements on the data access speed of database system,and the hybrid memory architecture based on DRAM and NVM is expected to meet this demand.In the database system,the join algorithm is one of the most commonly used and important algorithms,which is also an important factor affecting the query processing performance of the database system.So in this thesis,based on a combination of DRAM and NVM memory architecture as the foundation,we focus on the optimization of join algorithms on hybrid memory architecture,hash join and sort join algorithms are the focuses of our research,finally,new NVM-aware join algorithms suitable for hybrid memory architecture is proposed,which lays a foundation for building a database system based on hybrid memory architecture.The main work and contributions of this thesis can be summarized as follows:(1)We propose a hash join algorithm based on hybrid memory called BF-Join.We redesign the partition data structure in hash join algorithm,introduce bloom filter to speed up query,and design new insert and query algorithms.In addition,in order to make the hash join algorithm have better CPU cache hit ratio,we further put forward the cache-optimized BF-Join,which effectively reduces the cache miss rate of the algorithm and further improves the time performance;(2)A new sort join algorithm C-Join based on key-value separation and key-value deduplication strategy is proposed for heterogeneous hybrid memory architecture.This algorithm effectively reduces the DRAM cost and improves the performance of the join process through the key-value separation strategy and the removal of repeated keys in the join process.In this thesis,three different implementation methods of C-Join algorithm are proposed,namely chained structure,linear structure and premalloc linear structure;(3)The BF-Join and C-Join algorithms are tested and evaluated.Experimental results show that the BF-Join and C-Join algorithms proposed in this thesis have better time performance than traditional join algorithms in hybrid memory architecture,and can effectively reduce the usage of DRAM.Our solution achieves the desired goals,not only reducing DRAM usage but also improving time performance.