Abstract
There has been significant amount of excitement and recent work on GPU-based database systems. Previous work has claimed that these systems can perform orders of magnitude better than CPU-based database systems on analytical workloads such as those found in decision support and business intelligence applications. A hardware expert would view these claims with suspicion. Given the general notion that database operators are memory-bandwidth bound, one would expect the maximum gain to be roughly equal to the ratio of the memory bandwidth of GPU to that of CPU. In this paper, we adopt a model-based approach to understand when and why the performance gains of running queries on GPUs vs on CPUs vary from the bandwidth ratio (which is roughly 16x on modern hardware). We propose Crystal, a library of parallel routines that can be combined together to run full SQL queries on a GPU with minimal materialization overhead. We implement individual query operators to show that while the speedups for selection, projection, and sorts are near the bandwidth ratio, joins achieve less speedup due to differences in hardware capabilities. Interestingly, we show on a popular analytical workload that full query performance gain from running on GPU exceeds the bandwidth ratio despite individual operators having speedup less than bandwidth ratio, as a result of limitations of vectorizing chained operators on CPUs, resulting in a 25x speedup for GPUs over CPUs on the benchmark.
Introduction
For years, the database community has been divided on the utility of GPUs. Some researchers claimed 100x speedups, while hardware experts remained skeptical. If database operators are primarily memory-bandwidth bound, and the bandwidth ratio between a high-end GPU and a CPU is only about 16x, where do those 100x claims come from? This paper seeks to establish the fundamental performance limits when the working set is stored directly in GPU memory, moving beyond the bottlenecked "GPU as a coprocessor" model.
The Performance Bottleneck
The authors identify two major flaws in previous literature that led to misleading performance claims. First, many studies compared GPUs against slow, unoptimized CPU databases rather than state-of-the-art, SIMD-optimized systems. Second, the traditional "coprocessor" model ships data from CPU RAM to the GPU over PCIe during query execution. Since PCIe is significantly slower than both CPU and GPU memory bandwidth, the transfer time becomes the bottleneck, often making the GPU slower than a pure CPU approach like Hyper.
Methods: Tile-Based Execution and Crystal
To overcome these limitations, the authors propose a Tile-based execution model implemented via a new library called Crystal.
- Tile-based Execution: While CPUs often process data in vectors, Crystal processes data in "tiles" (blocks of ~1000 elements). Instead of treating thousands of GPU threads as independent workers, they are grouped into "thread blocks" that cooperatively process a tile.
- Crystal Library: This is a collection of CUDA "block-wide" primitives (e.g.,
BlockLoad,BlockScan,BlockShuffle). These primitives allow developers to compose full SQL queries that utilize fast GPU shared memory and registers, minimizing expensive "materialization"—the process of writing intermediate results back to slow global memory.
Key Insights and Results
Using the Star Schema Benchmark (SSB) at Scale Factor 20, the researchers found that the GPU speedup (25x) actually exceeds the raw hardware bandwidth ratio (16x). This is primarily due to Latency Hiding: GPUs are designed to instantly swap execution contexts (warps) when one stalls waiting for memory, whereas CPUs suffer more from stalls during irregular memory accesses.
Key findings include:
- Full Query Speedup: Crystal was 25x faster than a highly optimized, SIMD-parallel Standalone CPU implementation.
- Comparison to Commercial Systems: Crystal outperformed Omnisci (a leading commercial GPU database) by roughly 16x because Omnisci treats threads independently rather than using cooperative tile-based processing.
- Cost-Effectiveness: Despite higher hardware costs, the 25x performance gain makes the GPU roughly 4x more cost-effective than the CPU for these workloads.
Conclusion and Future Work
The study proves that the "right" way to build a GPU database is to treat the GPU as the primary storage and execution engine for the active working set. While memory capacity remains a hurdle (32GB on a V100 vs. terabytes on a CPU), the efficiency of the tile-based model provides a clear path forward for high-performance analytical engines. Future work will focus on distributed hybrid systems and implementing efficient compression schemes to mitigate the "memory wall."
Summary updated