Abstract: In column database, the join operation is still the most important and the most timcconsuming operation.UPUs' powerful computing capabilities can provide new optimizing solutions. This paper proposed a new Hash Join algorithm and a new Sort merge Join which are both based on Fermi architecture. These two new implementation approaches take full advantage of the new parallel cache hierarchy of Fermi, and successfully reduce the cache miss rate of the join operation. Combined with CUDA stream technology, the new join algorithms can effectively hide the data transfer delay between the main memory and global memory, when the join operation generates a large number of results. The experimental results show that Hash Join based on Fermi performs better when it deals with data skew, while Sort merge Join based on Fermi is more stable. Comparing with the implementations based on multi-core CPUs, these two algorithms are faster, speed up 2.4 times at most, and the new Hash Join even achieves 217M tuples per second when foreign key's dataset is high skew.

Key words: Join algorithm, Fermi architecture, Cache, CUDA stream