Source-linked AI summary
Tile-Based Decompression in Compiled GPU Engines
Antonio Boffa, Ananya Gupta, Hamish Nicholson, Anastasia Ailamaki
TL;DR
GPU memory budgets are under pressure, and existing compressed-execution approaches either bind decompression to a particular execution model or materialize decoded columns in HBM. The paper introduces CB2T, a compiler-integrated operator that fuses cooperative tile decompression with tuple-at-a-time execution. Against HeavyDB and Sirius, fused on-chip decompression achieves competitive query times with lower resident memory footprint and bandwidth consumption.
Problem
GPU memory pressure is growing, while existing compressed-execution approaches bind decompression to particular execution models or materialize decoded columns in HBM.
Source: §1 · p. 1Method
Results
Up to 4× lower resident GPU memory footprint and 6× lower GPU memory-bandwidth consumption accompany competitive query times against HeavyDB and Sirius.
Source: §1 · p. 3Takeaways & Limitations
Executing directly over compressed data reduces memory traffic and footprint, letting queries fit within smaller GPU-memory budgets and more workloads share a device.
Source: §7 · p. 12The experiments apply the same compression algorithm to every column and block; selecting algorithms per column or block is left for future work.
Source: §5.2 · p. 9
Abstract
from arXiv · showhide
Modern GPUs reach record analytical performance only when a query's working set fits within its GPU memory budget, and that budget is under growing pressure: GPUs are partitioned and shared, working sets are outgrowing high-bandwidth memory (HBM), and HBM is a fixed on-device resource whose per-dollar capacity has stagnated across generations. Lightweight compression can relieve this pressure by shrinking both footprint and bandwidth demand, but existing GPU compressed-execution techniques either bind decompression to a specific execution model or materialize decompressed columns in HBM before query execution. We present a compression subsystem for compiled GPU query engines that treats decompression as a first-class physical operator. Compression-specific logic is isolated behind a narrow backend interface, so new GPU-oriented encodings can be added without rewriting downstream operators. We implement the design in Proteus and study where decompressed values should be materialized in the GPU memory hierarchy. Our compiler-integrated shared-memory strategy fuses cooperative tile decompression with tuple-at-a-time query execution inside a single generated GPU kernel, avoiding decompressed-column materialization in HBM. Compared with HeavyDB and Sirius on GPU-resident data, fused on-chip decompression achieves competitive query times while reducing the resident memory footprint by up to 4x and memory-bandwidth consumption by up to 6x.
1 INTRODUCTION
GPU memory pressure makes compressed execution attractive, but existing designs do not provide a reusable path for compiled tuple-at-a-time engines to consume compressed data. The paper introduces CB2T and fuses tile decompression with query execution, reporting competitive query times alongside lower memory use.
1 INTRODUCTION
- GPU memory budgets face pressure from shared devices and growing working sets, while capacity gains have not kept pace with per-dollar memory affordability.Lossless compression can reduce stored and transferred data while preserving information.Source: §1 · pp. 1–2
- Compressed execution either materializes decoded columns in HBM or is tied to execution models that do not expose decompression as a reusable compiler-level component.The paper identifies compiled tuple-at-a-time execution over compressed data without eager intermediate materialization as an unexplored design space.Source: §1 · p. 2
- CB2T is a physical decompression operator that isolates format-specific metadata resolution and tile loading behind a backend while exposing ordinary tuple bindings to downstream operators.The operator boundary preserves the relational interface and supports compiler-mediated fusion with tuple-at-a-time pipelines.Source: §1 · p. 3
- Up to 4× lower resident GPU memory footprint and 6× lower GPU memory-bandwidth consumption accompany competitive query times against HeavyDB and Sirius.The comparison covers SSB, TPC-H, and Stack queries on GPU-resident data.Source: §1 · p. 3
2 PRELIMINARIES AND RELATED WORKS
The section reviews GPU execution and memory fundamentals, existing query-engine models and compression approaches, then frames the structural and placement challenges of bringing tile-oriented compressed data into compiled tuple-at-a-time pipelines.
2.1 GPU architecture essentials for database kernels
- GPU threads cooperate in blocks, with registers and shared memory providing limited on-chip storage; higher per-block shared-memory use or register pressure can reduce occupancy or cause spills.Spilled values use thread-local memory backed by the device memory hierarchy.Source: §2.1 · p. 3
2.2 Compilation-based query execution and the GPU memory hierarchy
- Compilation fuses relational operators into generated dataflow, while BlockToTuples exposes block positions as tuple bindings that LLVM can promote to registers and lower to GPU address spaces.NVPTX lowering preserves pointer address spaces to select corresponding PTX memory instructions.Source: §2.2 · pp. 3–4
2.3 GPU database execution models
- GPU query engines span tuple-at-a-time, vectorized, and tensor-at-a-time execution; HeavyDB uses fixed-width column storage, whereas Sirius uses vectorized libcudf processing and materializes uncompressed blocks between operators.The section also situates Proteus among compiled fused-pipeline systems and describes differing approaches to GPU execution.Source: §2.3 · p. 4
2.4 Lightweight GPU integer compression
- GPU compression includes bit-packing, Frame-of-Reference, and run-length encoding; GPU-RFOR cascades encodings for compression ratio, while FastLanes BitPack targets decode throughput with a lower compression ratio.Other compressed-execution designs embed encoding-specific decoding in relational operators, trading generality for avoiding decompressed-column materialization.Source: §2.4 · p. 5
2.5 Challenges of compiled execution over compressed columns
- Lightweight encodings align with cooperative tile decoding, but tuple-at-a-time pipelines consume values individually, requiring decoded tiles to be staged in registers, shared memory, or global memory.Placement must be handled through GPU address-space and register-allocation mechanisms while remaining hidden from the operator interface; direct decoding also risks divergence, register pressure, and scattered memory traffic.Source: §2.5 · p. 5
3 THE MODULAR DECOMPRESSION OPERATOR: A CONTRACT FOR COMPOSABLE COMPRESSED SCANS
CB2T keeps compressed input in a columnar layout while feeding tuple-at-a-time operators without materializing decoded intermediates in HBM. Its composability contract preserves the ordinary tuple interface while isolating compression-specific work in reusable backends.
3 THE MODULAR DECOMPRESSION OPERATOR: A CONTRACT FOR COMPOSABLE COMPRESSED SCANS
- CB2T is the only described approach that combines tuple-at-a-time, JIT-compiled execution with reusable backends that confine compression-format knowledge.Downstream operators consume ordinary tuple bindings regardless of encoding.Source: §3 · p. 5
3.1 Interface substitutability
- Interface substitutability means compressed columns use the standard scan/tuple interface, so relational operators consume ordinary values without format-specific APIs.Their generated code is identical whether values come from compressed or uncompressed sources.Source: §3 · p. 6, §3.1 · p. 6
3.2 Decompression encapsulation
- Decompression encapsulation confines metadata interpretation and tile decoding to a reusable backend, leaving downstream operators unaware of the encoding.The backend resolves tile metadata and produces decoded values through the common interface.Source: §3 · p. 6
3.1 Interface substitutability
- CB2T receives GPU-resident compressed blocks partitioned into fixed-size tiles, with placement and launch configuration exposed as execution knobs.Compression-specific logic stays behind the two backend hooks while downstream code remains fixed across formats.Source: §3.1 · p. 6
3.2 Decompression encapsulation
- Each backend implements resolve_metadata() and decompress_tile(), separating per-tile layout interpretation from cooperative tile decoding.The metadata hook runs on one block-leader thread; tile decompression runs cooperatively across the block.Source: §3.2 · p. 6
- The contract supports lightweight, tile-decodable encodings whose decoding uses per-tile metadata resolution followed by cooperative tile materialization.New formats can register the two backend hooks without changing other engine components.Source: §3.2 · p. 6
4 REALIZING THE CONTRACT: A JIT-COMPILED, FUSED GPU KERNEL
The implementation fuses cooperative tile decompression and tuple-at-a-time query execution in one compiled GPU kernel. Shared memory bridges their access patterns, while configurable decode placement and launch settings preserve the tuple interface and let the system tune resource tradeoffs.
4 REALIZING THE CONTRACT: A JIT-COMPILED, FUSED GPU KERNEL
- The compiled GPU kernel cooperatively decompresses each tile-sized row group into on-chip storage, then immediately runs downstream tuple-at-a-time code over that tile.Both phases share one LLVM IR module and kernel, enabling inlining, value propagation, and elimination of redundant materialization at the operator boundary.Source: §4 · p. 7
4.1 Shared-memory as the bridge
- Shared memory bridges block-cooperative column decoding and row-wise tuple execution, with barriers protecting decoded data from premature reads or overwrite.Decoded values pass through the shared scratchpad rather than being materialized in HBM.Source: §4.1 · p. 7
4.2 Preserving the tuple binding across the JIT boundary
- The shared-memory binding incurs no indirection: downstream loads lower directly to shared-memory accesses, and only compressed input remains globally loaded.Emitted PTX uses ld.shared/st.shared without address-space conversions.Source: §4.2 · p. 7
4.3 Execution knobs: decode placement and launch configuration
- Decode placement can be global memory, shared memory, or registers while preserving the same external tuple binding.The register variant reduces shared-memory pressure by staging one decoded column tile at a time and lifting assigned values into registers.Source: §4.3 · p. 7
- For K columns and tile cardinality T, decoded-value staging alone scales as K×T and can reduce concurrent block occupancy.The tile size T is fixed at compression time; larger shared-memory budgets can accommodate larger tiles, while smaller budgets or wider projections favor smaller ones.Source: §4.3 · p. 8
- The tpb/ipt mapping trades synchronization and setup overhead against per-thread register pressure, and the best choice depends on query and codec.Because decoding and relational operators share a kernel, joins and aggregations add resource demands; configurations can be retuned per query.Source: §4.3 · p. 8
5 SYSTEM INTEGRATION AND EVALUATION
The evaluation integrates CB2T into Proteus and compares decompression placements, codecs, and GPU database baselines across GPU-resident workloads. It finds that shared-memory decompression reduces footprint and traffic, while runtime depends on the query, codec, and launch configuration.
5.2 Compression algorithms
- RFOR compresses best overall at 2.24×, while FLBP has the fastest decompression throughput across all eight families, at 559–729 GB/s.RFOR’s run-length encoding benefits from long runs in some SSB columns; FLBP uses a warp-level, synchronization-free decoder.Source: §5.2 · p. 9, Table 2 · p. 9
5.3 Decompression strategies
- Pre-decom materializes decoded data in global memory, Global-stage reuses a bounded global pool, and Shared feeds decoded tiles to the tuple loop from shared memory.Register placement reduces shared-memory use but adds register pressure; it benefits simple queries on A40, but not A100.Source: §5.3 · pp. 9–10, Figure 4 · p. 9
5.4 GPU DRAM traffic decomposition
- Shared reduces physical HBM traffic relative to Pre-decom by 6.3× for RFOR and 5.6× for FLBP.For Q1.1, Shared traffic consists only of compressed input reads.Source: §5.4 · p. 10, Figure 5 · p. 10
5.5 Comparing encoders and decompression placements against uncompressed Proteus
- Shared matches Uncom on SSB Q1.1 and Stack Q11, stays near it on TPC-H Q12, but runs slower on Q5 and Stack Q14.On Q1.1, FLBP-Shared takes 19.7 ms versus 19.7 ms for Uncom; on Q14 it takes 30.0 ms versus 22.9 ms.Source: §5.5 · p. 10
- RFOR’s best launch setting is query-independent in this suite, but FLBP’s optimum varies; higher thread count alone does not ensure better throughput.The Table 3 sweep varies threads per block and items per thread for RFOR and FLBP on SSB Q1.1 and Q4.1.Source: §5.5 · p. 11, Table 3 · p. 11
- Across eight queries, FLBP-Shared reduces footprint by 54% with 8% runtime overhead, while RFOR-Shared reduces it by 60% with 45% overhead.Shared is the fastest compressed placement in all 16 query–codec cases; the recommended launch configuration differs by codec.Source: §5.5 · p. 11
5.6 Production GPU database baseline
- FLBP-Shared uses 46% less memory than HeavyDB and 50% less than Sirius, with only 8% runtime overhead over Proteus-Uncom on average.Across eight queries, HeavyDB remains runtime-competitive, while Sirius is slower than Proteus-Uncom on every query.Source: Figure 6 · p. 11, §5.6 · p. 12
5.7 Specialized compressed-execution baselines
- Against specialized Crystal kernels, CB2T’s advantage is composability and more stable FLBP performance, not lower absolute kernel time.Crystal is available only for SSB; its compressed kernels are 2.7–4.7× faster than their Proteus counterparts.Source: §5.7 · p. 12
6 FUTURE WORK
The paper outlines three directions: workload-aware decompression placement, compiler-visible compression semantics, and compressed data exchange across pipeline boundaries.
6 FUTURE WORK
- Compiler models could select threads per block, items per thread, and decode location based on their interaction with the fused query pipeline.The compiler already observes projected columns, operator shape, backend, and target SM resources.Source: §6 · p. 12
- Encoding metadata in generated LLVM IR could let optimization passes skip tiles or avoid decoding values that cannot affect the result.The proposed metadata includes tile minimum values, bit widths, and run boundaries.Source: §6 · p. 12
- A TupleToCompressedBlocks operator could compress pipeline outputs before materialization or transfer across devices, reducing HBM footprint and PCIe/NVLink traffic.The proposed operator would consume standard tuples and emit compressed blocks at pipeline breakers or device crossings.Source: §6 · p. 12
7 CONCLUSION
The paper makes decompression a first-class operator in a JIT-compiled GPU engine, with encoding-specific logic behind reusable backend hooks. It concludes that execution over compressed data reduces memory traffic and footprint.
7 CONCLUSION
- A first-class decompression operator fills the compiled, tuple-at-a-time-over-compressed design space in a JIT-compiled GPU engine.CB2T confines encoding-specific logic behind reusable backend hooks, allowing a new compression format to be added as a backend rather than through a pipeline rewrite.Source: §7 · p. 12
- Executing directly over compressed data reduces memory traffic and footprint, letting queries fit within smaller GPU-memory budgets and more workloads share a device.Source: §7 · p. 12
- The compiler can reach decompression and open automatic optimizations that hand-written kernels cannot express.Source: §7 · p. 12