Nested Loop Join Optimization Based on Radix-Join in Chip Multi-Processor

Aiming at current chip multi-processor(CMP), presented in this paper is a non-indexed nested loop join (NINLJ) optimization based on shared cache CMP. The authors firstly present multithreaded NINLJ execution framework based on radix-NL-join algorithm, and then, through reducing cache conflict and improving cache hit ratio, optimize cache performance of cluster partition thread and cluster join thread in the framework. The main contributions are as follows: 1.Aiming at the shared cache confliction when multiple threads access shared cache simultaneously, the start time of cluster partition thread is optimized to reduce shared cache confliction in cluster partition phase; 2. In cluster join phase, cluster join threads have poor cache behaviors. To solve this performance bottleneck, the advantage of sequent cluster access is utilized when cluster join threads executing, and preload thread is adopted to preload cluster from main memory to L2-cache before cluster join threads need it; 3.In the experiments, the framework is realized in EaseDB, and the performance of multithreaded NINLJ is tested. The experiment results show that the multithreaded NINLJ execution framework could fully utilize computing resource of CMP and effectively solve shared cache conflict in multithreaded environment, and the performance of NINLJ is improved. The algorithm proposed outperforms traditional multithreaded Radix-NL-Join by 26% on average.