Bridging the Indexing Gap in Fused GPU Query Engines
Abstract
GPU query backends achieve high throughput on analytical work- loads through massive parallelism, but lack indexing support that accelerates selective queries in CPU databases. Existing GPU index implementations face three limitations: (1) supporting conjunctive predicates only, (2) materializing intermediate results between in- dex access and query execution, and (3) assuming query boundaries align with pre-built index bins. We present a fused bitmap indexing approach that addresses these limitations. We introduce virtual query program that exe- cutes arbitrary boolean predicates with low overhead. We fuse index access with subsequent column lookups, joins, and aggre- gation, keeping intermediate results in registers and eliminating global-memory round-trips. To handle misaligned query bound- aries, we propose GPU friendly candidate checking that tracks three-valued row states (certain-in, certain-out, uncertain) through in-register boolean operations and verifies only the necessary can- didates, without accessing global memory. On Star Schema Benchmark SF=140 with RTX 5090 D, our fused bitmap index achieves up to 6.9× geometric-mean speed over our optimized non-indexed baseline built upon the Crystal GPU data- base query backend (Dense layout), and 4.3× with practical Sparse layout using less memory. Compared to current best compressed GPU bitmap implementation under perfect bin alignment (best case), our Sparse layout achieves 1.4× speed end-to-end. We show that generic elementwise-style GPU fusion achieves only 1.34× speed, while our pipeline reaches 3.19× with 0.8% overhead versus dedicated compile-time kernels. Results on an NVIDIA H800 server GPU show the approach remains stable across GPU architectures, with smaller but still consistent fusion benefits on server GPUs.
Assigned reviewers
No reviewers assigned yet.
Candidates from the panel ranked by taxonomy affinity
| # | Reviewer | Match | Load | Why |
|---|