Load Balancing Parallel Hash Join Algorithm Based on Shared Cache Chip Multi-Processor

摘要

Chip Multi-Processor (CMP) presents new opportunities for improving database performance on large queries. Because various resources are shared by many threads, such as L2-Cache, multiprocessors system and simultaneous multithreading are inherently different from CMP system. Based on Chip Multi-Processor (CMP), this paper explores multithreaded hash join execution optimization framework. A major problem of hash join algorithm is that if the hash table can not fit into the cache, each access to the hash table is likely to cause one cache thrashing due to its random nature. To resolve this problem, we designed a reusable triangular buffering structure such that the partitioning granularity is smaller than the cache capacity. Furthermore, in order to reduce cache access conflict in the multithreaded join phase, we optimized the partitioning granularity in accordance with the number of threads. Besides, to address the issue of imbalance of thread's workload, we proposed a novel method to optimize the workload assignment among threads. Our theoretical analysis and empirical evaluation show that the proposed algorithm could impressively improve in the performance of hash join operation.