The Optimization Of Hash Join Algorithm Based On KNL

With the rapid development of information age and the rapid growth of user data,the performance of database becomes more and more important.As a fast and widely-used implementation of database join algorithms,main-memory hash join algorithm is paid much attention by researchers at home and abroad.According to whether hash join algorithms are optimized by hardware architecture features,they can be divided into two types: hardware oblivious hash join and hardware conscious hash join.Knights Landing processor(KNL),a new generation of many-core processor,has different architectures from that of multi-core processors,which brings new opportunities and challenges to the optimization of hash join algorithm.This paper optimizes both hardware oblivious and hardware conscious hash join algorithms according to the architectural characteristics of KNL and compares their performance on KNL.The core idea of hardware oblivious hash join is to rely on multi-thread technology and avoid complex hardware optimization.Benefitting from excellent design of modern processor architecture,its simple and effective implementation has achieved good performance.In order to further improve the performance,this paper optimizes hardware oblivious hash join by AVX-512 instruction set,cache alignment and data prefetching.Besides,this paper optimizes the memory allocation mode of shared hash table under SNC-4 clustering mode.In order to improve the memory access performance,hardware conscious hash join limits the size of hash table to fit in local cache by partitioning.This paper combines multi-pass partitioning and software-managed buffers to improve performance.In addition,AVX-512 instruction set is used to optimize the join process.Last but not least,this paper designs different memory allocation strategies for these two types of hash join algorithms to make full use of high-bandwidth MultiChannel DRAM(MCDRAM).In the experiment of this paper,the performance of hardware oblivious and hardware conscious hash join is improved by 3.7 and 2.1 times respectively after optimization.On KNL,hardware oblivious hash join without any optimization is far less powerful than hardware conscious hash join,while hardware oblivious hash join optimized according to KNL architecture is more competitive than hardware conscious hash join.In conclusion,in order to improve the performance of hash join algorithms,hardware architecture characteristics are still non-negligible factors.