Notesstorage🌱 seedling

Columnar Compression

Also: Column Compression · Dictionary Encoding · Run-Length Encoding · RLE · Bit-Packing · Delta Encoding · Bitmap Encoding

Lightweight encodings that exploit a column holding one type with few distinct values and long repeats: dictionary codes, bit-packing, run-length and delta encoding, often with LZ4 or Zstandard on top. Fewer bytes means faster scans, and engines can filter on the encoded form directly.

Why it exists

Scans are limited by how fast bytes arrive from disk, network or memory. Shrinking a column ten times can make reading it up to ten times faster, not just cheaper to store.

How it works

  • Dictionary: store each distinct value once; replace values with small integer codes.
  • Bit-packing: store each code in exactly the bits it needs (2 bits for 3 values).
  • Run-length (RLE): store (value, count) for each run; best on sorted columns.
  • Delta: store differences between neighbours, so timestamps and IDs become small numbers.
  • Each multiplies the last: a 3-value string column of a billion rows goes from ~7 GB raw to ~250 MB bit-packed, and to far less once sorted and run-length encoded.
  • Operate on compressed data: a predicate becomes a code comparison, checked once per run; SUM over a run is value × count.

Trade-offs

Choice Gains Costs
lightweight encodings decode at memory speed, queryable in place ratio depends on data and sort order
heavy codecs (Zstandard, gzip) higher ratio more CPU per byte decoded
sorting for compression long runs, tiny columns only one sort order per copy

In practice

  • Apache Parquet uses dictionary encoding by default and falls back to plain encoding when a chunk's dictionary grows too big.
  • ClickHouse exposes dictionaries as the LowCardinality type and per-column codecs such as Delta, DoubleDelta and Gorilla.
  • Dremel's team reordered rows to lengthen runs and saved 17% of storage on average across 40 datasets.

Pitfalls

  • Dictionary-encoding a high-cardinality column (IDs, URLs) adds a lookup and saves little.
  • Delta codecs on non-monotonic data can make compression worse.

Recall

These cards are also in your review deck, scheduled with spaced repetition.