We present a novel design and implementation of relational join algorithms for new-generation graphics processing units (GPUs). The most recent GPU features include support for writing to random memory locations, efficient inter-processor communication, and a programming model for general-purpose computing. Taking advantage of these new features, we design a set of data-parallel primitives such as split and sort, and use these primitives to implement indexed or non-indexed nested-loop, sort-merge and hash joins. Our algorithms utilize the high parallelism as well as the high memory bandwidth of the GPU, and use parallel computation and memory optimizations to effectively reduce memory stalls. We have implemented our algorithms on a PC with an NVIDIA G80 GPU and an Intel quad-core CPU. Our GPU-based join algorithms are able to achieve a performance improvement of 2-7X over their optimized CPU-based counterparts.

This is joint work with Bingsheng He, Ke Yang, Rui Fang, Mian Lu, Naga K. Govindaraju, and Pedro V. Sander. 

Qiong Luo is an assistant professor at the Department of Computer Science and Engineering, the Hong Kong University of Science and Technology (HKUST). Her research interests are in database systems, in particular, architecture-friendly databases, query processing in sensor networks, and web data management. Qiong received her PhD degree from the University of Wisconsin, and her B.S. and M.S. degrees from Peking University.