The Decompression Bottleneck in High-Throughput Computing

311 concepts236 papers2 proposals

For decades, data management systems operated under a simple hardware assumption: storage I/O is slow, and CPUs are fast. To maximize system performance, it made sense to spend CPU cycles aggressively compressing data on disk to minimize the time spent reading bytes across a slow I/O bus.

However, modern hardware has inverted this trade-off. With the advent of high-speed NVMe SSDs, high-bandwidth interconnects, and massively parallel accelerators like GPUs, storage and network transfer speeds have skyrocketed. Meanwhile, single-threaded CPU decompression speeds have largely stagnated. As a result, the time required for a processor to decompress data can now easily exceed the time saved by reading a smaller, compressed file from disk. The computational cost of decompression has become the new performance bottleneck.

The Inverted Hardware Landscape

To understand why traditional compression fails in modern environments, consider the total time ($T$) required to process a dataset:

$$T = T_{\text{I/O}} + T_{\text{decompression}} + T_{\text{compute}}$$

Historically, $T_{\text{I/O}}$ dominated the equation. Reducing the data size by a factor of three cut $T_{\text{I/O}}$ by nearly two-thirds, easily offsetting a small increase in $T_{\text{decompression}}$.

As noted by Ching‐Hsien Hsu et al., big data systems now face a persistent tension between maximizing compression ratios and preserving high data processing throughput. When storage media becomes fast enough, aggressive compression actually degrades end-to-end performance.

Evaluating this shift across modern storage formats, Xinyu Zeng et al. demonstrate that on high-bandwidth NVMe SSDs, traditional block-level compression formats (like those used in Apache Parquet or ORC) become severe bottlenecks. Because the CPU cannot decompress blocks fast enough to keep pace with the drive's read speeds, using uncompressed or lightly compressed formats yields significantly higher throughput by shifting the bottleneck away from the processor.

This performance gap forces a re-evaluation of data reduction strategies. As Shingo Takamatsu et al. argue, the effectiveness of any I/O-focused compression strategy is strictly contingent on the performance gap between storage hardware and processing units. When that gap closes, complex entropy-based compression algorithms become a liability.

The Random Access and Queryability Penalty

The decompression bottleneck is exacerbated by the way traditional compression algorithms handle data organization. Standard tools treat data as a continuous stream of bits, meaning that individual data points cannot be read in isolation.

This lack of queryability introduces severe latency penalties in database and analytics workflows:

  1. The Sequential Decoding Requirement: Standard entropy coding schemes require sequential decoding from the beginning of a compressed block. As Christine Guillemot demonstrates, performing range queries or alphabetical searches on compressed data typically necessitates a full decompression step because the mapping between symbols and bitstrings fails to preserve the original data's sequence properties.
  2. Point vs. Aggregate Trade-offs: Systems optimized for rapid analytical processing often struggle with granular lookups. For example, Søren Kejser Jensen et al. show that while model-based time-series compression can dramatically accelerate aggregate queries, retrieving a single, specific timestamped data point requires evaluating or decompressing the underlying mathematical model, creating a localized performance bottleneck.
  3. The Random Access Absence: In specialized domains like genomics, high-ratio compression techniques often lack the ability to perform random access. Bobbie Chern et al. observe that this limitation forces applications to decompress and process entire datasets even when only a small, localized segment of sequence data is required for analysis.

Computing Directly on Compressed Data

To bypass the decompression bottleneck entirely, a major research direction focuses on co-designing compression formats so that computational or mathematical operations can run directly on the compressed representation. By eliminating the decompression step from the execution path, systems can achieve both high storage efficiency and maximum processing speed.

Traditional Pipeline:
[ Compressed Data ] ──> ( Decompression Overhead ) ──> [ Raw Data ] ──> ( Compute )

Direct Computation Pipeline:
[ Compressed Data ] ──> ( Compute Directly on Compressed Format )

A prime example of this paradigm is found in large-scale machine learning training. Fengan Li et al. introduced Tuple-Oriented Compression (TOC) to accelerate mini-batch Stochastic Gradient Descent (SGD). Instead of decompressing data chunks before feeding them to a model, TOC structures the compressed format such that standard matrix operations can execute directly on the compressed representations. This eliminates the CPU-bound decompression phase entirely, accelerating end-to-end training pipelines while maintaining a minimal memory footprint.

A similar approach is utilized in out-of-core learning frameworks. The authors of Large Linear Classification When Data Cannot Fit in Memory demonstrate that by partitioning massive datasets into disk-based blocks and performing intensive local updates, systems can balance the CPU cycles spent on lightweight transformations against slow disk access, preventing the system from falling into a performance death-spiral caused by memory swapping.

Massively Parallel Decompression

When data must be fully reconstructed before use, the solution shifts from avoiding decompression to accelerating it via hardware parallelization. Traditional compression algorithms (like Gzip or Huffman coding) are inherently sequential; each step depends on the internal state calculated from the preceding bytes, making them notoriously difficult to parallelize on modern multi-core processors or accelerators.

To resolve this, researchers are redesigning compression formats from scratch to be natively parallel. In deep learning pipelines where data ingestion is a major bottleneck, Jonghyun Bae et al. developed the L3 image format. L3 intentionally sacrifices a fraction of the compression ratio in exchange for a format that can be decoded in parallel directly on the GPU. This shifts the decompression burden away from the CPU, allowing the data-loading pipeline to keep pace with high-throughput training loops.

This strategy is equally vital for handling massive scientific datasets. High-fidelity simulations generate petabytes of data, making storage space a critical constraint. To maintain throughput, frameworks must compress data in situ (as it is generated).

Jiannan Tian et al. optimized error-bounded lossy compression for GPUs by introducing parallelized run-length encoding and reconstruction techniques. Further advancing this direction, Jinyang Liu et al. developed multi-level interpolation predictors that achieve high compression ratios on the GPU while preserving the massive throughput required for real-time scientific instruments and exascale simulations.

Ultimately, overcoming the decompression bottleneck requires moving away from general-purpose, storage-centric compression. Whether by computing directly on compressed bytes or by designing formats for massive hardware parallelization, modern systems must treat compression and computation as a unified, co-designed pipeline.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compression_computation_trade_off_2ccc4df0,
  title = {compression-computation trade-off},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compression-computation-trade-off/rdr_2ccc4df0fb2542dda9ec39a522794b42},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_compression_computation_trade_off_2ccc4df0_v1,
  title = {compression-computation trade-off},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compression-computation-trade-off/rdr_2ccc4df0fb2542dda9ec39a522794b42/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake