Data-Parallel Query Processing on Non-Uniform Data
Henning Funke and Jens Teubner
Proceedings of the VLDB Endowment, volume 13, number 6, February 2020
Graphics processing units (GPUs) promise spectacular performance advantages when used as database coprocessors. Their massive compute capacity, however, is often hampered by control flow divergence caused by non-uniform data distributions. When data-parallel work items demand for different amounts or types of processing, instructions execute with lowered efficiency. Query compilation techniques—a recent advance in GPU-accelerated database processing—suffer from the problem even more, because divergence effects are amplified during the execution of fused pipeline operators.
In this work, we identify two types of control flow divergence—filter divergence and expansion divergence—that frequently occur in real world workloads. We quantify the problem for two poster cases and propose techniques to balance these divergence effects. By balancing divergence effects, our approach is able to restore processing efficiency even when pipelines contain heavily skewed operations. Our query compiler DogQC has a wider range of functionality than other query coprocessors and achieves performance improvements. We observe shorter execution times for TPC-H benchmark queries by factors up to 4.51x compared with existing GPU query compilers and by factors up to 4.54x compared with CPU-based systems.
Energy Awareness in Database Algorithms and Systems (SFB 876, A2)
MxKernel: A Bare-Metal Runtime System for Database Operations on Heterogeneous Many-Core Hardware
The source code of the DogQC query compiler is available for download here.
It is also available on Github.
Revised Submission to VLDB 2020 (result: Accept)
Submission to VLDB 2020 (result: Revision)