Compression Basics: Making Data Smaller

Concept. Columnar compression (run-length, dictionary, delta) exploits repetition inside one column, 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 contiguously. 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 compress a column by removing repeated structure. RLE stores each run as a value plus a count. Dictionary encoding maps each distinct value to a small integer code. Delta encoding stores differences between adjacent sorted numbers. Bit packing stores small integers in the minimum number of bits. The raw input is grey, the encoded result orange. Ratios run from about 4x (bit packing) to 100x (RLE on sorted data); choose based on the column's value distribution.

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. A 1M-row user_id column sorted by user_id with ~25,000 active users compresses by chaining encodings. RLE collapses the sorted runs (4 MB to 200 KB). Dictionary encoding then replaces ids with codes; 25,000 ids fit in a 2-byte code rather than a 4-byte int (to 100 KB). zstd entropy-codes the remaining byte patterns (to 50 KB), a 98.75% reduction. Unsorted data or high cardinality leaves little for these encoders to remove.