Bridging the Indexing Gap in Fused GPU Query Engines

GPU query backends achieve high throughput on analytical workloads 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 index 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 executes arbitrary boolean predicates with low overhead. We fuse index access with subsequent column lookups, joins, and aggregation, keeping intermediate results in registers and eliminating global-memory round-trips. To handle misaligned query boundaries, 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 candidates, 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 database 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.