Compression Basics: Making Data Smaller

Concept. Columnar compression (run-length, dictionary, delta) exploits the fact that values in a single column repeat heavily, typically shrinking on-disk size 10× and cutting IO by the same factor.

Intuition. Mickey appears in 3 of 9 Listens rows. At a billion rows, his user_id might appear 100 million times in a stretch. Run-length encoding stores "Mickey × 100M" instead of repeating the string, Listens shrinks 10× and reads 10× fewer pages.

When to Use What?

Four panels, one per technique: RLE (runs to value plus count, 10–100×, very fast, sorted repeated values), Dictionary (strings to integer codes, 5–20×, fast, low-cardinality strings), Delta (differences between sorted numbers, 5–10×, fast, timestamps), Bit packing (minimum bits for small ints, 4–8×, very fast, flags). Raw input grey, encoded result orange.

Figure 1. Four columnar techniques, same idea: a column repeats, so stop repeating it. RLE collapses runs into a value plus a count, dictionary swaps strings for small integer codes, delta stores differences between sorted numbers, bit packing uses the minimum bits. The raw input is grey, the encoded result orange. Ratios run from about 4x (bit packing) to 100x (RLE on sorted data); pick by what the column looks like.

Run-Length Encoding (RLE)

The cleanest case. A sorted column with long runs of the same value. Instead of storing Mickey, Mickey, Mickey, Mickey ... a hundred million times, store Mickey × 100M. One value plus a count. Compression ratios of 10× to 100× are normal on user_id when the table is physically sorted by user_id, on country in a sorted log, on any column where the same value lingers. The runs come from the data's sort order on disk, not from a query.

Dictionary Encoding

When a column has a small set of distinct values, replace each value with a small integer index into a dictionary. Genre has maybe 50 distinct values; storing each as a 1-byte code instead of a 16-byte string is a 16× win. Country, currency, status flags, all good targets.

Delta Encoding

For sorted numeric columns, store the difference between consecutive values rather than the values themselves. Timestamps arriving microseconds apart turn into tiny deltas that pack into 1-byte ints instead of 8-byte longs. Auto-increment IDs and sensor readings benefit the same way.

Combining Techniques

You run the techniques in sequence, each one on what the previous step produced, so the savings compound. This works only under the condition that makes each step work: the column is physically sorted (or clustered) by user_id and has limited cardinality. Take a 1M-row Listens user_id column sorted by user_id, with about 25,000 active users:

A descending staircase of orange boxes: raw user_id 4 MB, then after RLE 200 KB, after dictionary 100 KB, after zstd 50 KB, ending in an ink result box reading 4 MB to 50 KB, 98.75% smaller. Grey labels name the step at each arrow.

Figure 2. Run in sequence, each step on the previous one's output, the techniques compound, given a 1M-row user_id column sorted by user_id with ~25,000 active users. RLE collapses the sorted runs (4 MB to 200 KB). Dictionary then shrinks each value: 25,000 ids need only a 2-byte code, not a 4-byte int (to 100 KB). zstd is different in kind, a general-purpose codec that entropy-codes whatever byte patterns the structural steps left (to 50 KB), a 98.75% reduction. Unsorted or high-cardinality, almost none of this happens.