Title: Increasing the Efficiency of GPU Bitmap Index Query Processing
Authors: Brandon Tran, Brennan Schaffner, Jason Sawin, Joseph M. Myre and David Chiu
Abstract: Once exotic, computational accelerators are now commonly available in many computing systems. Graphics processing units (GPUs) are perhaps the most frequently encountered computational accelerators. Recent work has shown that GPUs are beneficial when analyzing massive data sets. Specifically related to this study, it has been demonstrated that GPUs can significantly reduce the query processing time of database bitmap index queries. Bitmap indices are typically used for large, readonly data sets and are often compressed using some form of hybrid runlength compression. In this paper, we present three GPU algorithm enhancement strategies for executing queries of bitmap indices compressed using Word Aligned Hybrid compression: 1) data structure reuse 2) metadata creation with various type alignment and 3) a preallocated memory pool. The data structure reuse greatly reduces the number of costly memory system calls. The use of metadata exploits the immutable nature of bitmaps to pre-calculate and store necessary intermediate processing results. This metadata reduces the number of required query-time processing steps. Preallocating a memory pool can reduce or entirely remove the overhead of memory operations during query processing. Our empirical study showed that performing a combination of these strategies can achieve 33x to 113x speedup over the unenhanced implementation.
