Dictionary and run-length encoding

What do dictionary and run-length encodings bet on, and what do they give up?

Dictionary encoding

Idea. Replace each value by an index into the list of distinct values. The list of distinct values is the dictionary.

values:      ["DELIVERED", "LOADED", "DELIVERED", "DELIVERED", "LOADED"]
dictionary:  0 = "DELIVERED", 1 = "LOADED"
codes:       [0, 1, 0, 0, 1]      (each code needs only 1 bit here)

Cost. N × ⌈log₂ k⌉ bits for the codes, plus the dictionary itself (k × average value size). (⌈x⌉ means "round up".) Let us run the numbers on a string column with N = 1,000,000 values and an average length of 20 bytes, so 20 MB raw.

• k = 1,000 distinct values. Codes need ⌈log₂ 1000⌉ = 10 bits each: 1,000,000 × 10 bits = 1.25 MB. Dictionary: 1,000 × 20 B = 20 KB. Total about 1.27 MB against 20 MB, a ratio of about 15×.
• k = 500,000 distinct values. Codes need ⌈log₂ 500,000⌉ = 19 bits: 1,000,000 × 19 bits ≈ 2.4 MB. Dictionary: 500,000 × 20 B = 10 MB. Total about 12.4 MB against 20 MB, a ratio of only 1.6×. The dictionary is now the main cost.

The second case shows a cliff, and the cliff has a reason beyond the ratio: the dictionary must be resident in memory to decode anything. A 10 MB dictionary pushes everything else out of the CPU cache and turns each decode into a random memory access that probably misses the cache. So implementations stop using a dictionary instead of degrading slowly. Parquet abandons dictionary encoding for a column chunk when the dictionary page exceeds its threshold (1 MB by default) and falls back to plain encoding. The threshold looks like a size limit, but it is really a cache-residency decision.

Look at the structure of that fallback. A dictionary is an indirection layer (a lookup between a code and a value) over an immutable set of values, and the fallback to plain storage plays the role of its "cleaner". This is the same shape as an SSD's translation table and a table format's manifest: immutable storage, a lookup layer, and a cleanup path.

Where does the dictionary live? (scope)

The dictionary's scope is another granularity choice:

• One dictionary per page repeats common values in every page.
• One dictionary per file compresses better, but the whole dictionary must be read before any page can be decoded.
• One dictionary shared across files makes codes comparable across files, so you can merge, join and group without re-encoding. But it creates a coordination point, a versioning problem and an obligation to keep the dictionary forever.

This is the schema registry from Serialization, one level down, applied to values instead of fields. The description lives elsewhere, with the same cost structure.

The real win is operability

Dictionary encoding earns its place through what you can do without decoding, and this win is larger than the I/O saving.

• Filtering. WHERE country = 'India' becomes: one dictionary lookup to find the code (say 47), then a scan that compares 2-byte integers. You replaced 20-byte string comparisons by integer comparisons that use SIMD (SIMD = Single Instruction, Multiple Data: one CPU instruction compares many values at once). This is typically 10–50× faster on the predicate itself, in addition to reading fewer bytes.
• Grouping. Dictionary codes form a dense integer key space (0, 1, 2, ...). An aggregation such as COUNT(*) GROUP BY country becomes array indexing (counts[code]++) instead of hashing. That removes the hash table, and with it the contention that many threads cause when they update one shared table.

The boundary. A range predicate pushes down to the codes only if the dictionary is order-preserving (code order equals value order). Building an order-preserving dictionary requires seeing all values before assigning codes: two passes, or buffering everything. A streaming writer cannot do this. So WHERE country = 'India' pushes down on every dictionary, but WHERE name BETWEEN 'A' AND 'M' pushes down only on a sorted dictionary, and sorting the dictionary costs you single-pass writing.

Run-length encoding (RLE)

Idea. Store (value, count) pairs.

AAAAAAABBBBCC   →   (A,7) (B,4) (C,2)

Cost. Size = number of runs × (w + c) bits, where w is the bits for a value and c the bits for a count. RLE pays off when the average run length is above about (w + c) / w, which is roughly 1.2 to 2. This is a very low bar.

The worst case (every run has length 1) is an expansion of 1.5–2×. This is small but real, and it forces every serious implementation into a hybrid. Parquet's RLE/bit-packing hybrid chooses, for each group of eight values, between a bit-packed literal run and an RLE run, and stores the mode in the run header. The switching group of eight is itself a case of "a fixed cost sets a natural batch size", here at the scale of a single byte.

RLE computes without decoding

This is RLE's special feature. It is the strongest "compute without decoding" story in this stage. An aggregation runs in O(runs), not O(values): SUM is Σ (value × count), and COUNT, MIN and MAX are all computed run by run. A column compressed 1,000× also aggregates 1,000× faster. That is a different kind of proposition from general-purpose compression, which always costs CPU to save bytes. Here the ratio turns directly into CPU speed-up. This is why query engines work hard to keep RLE runs intact through the whole execution pipeline instead of expanding them early.

Where does RLE's value sit in a real Parquet file? Often in the definition and repetition levels from Serialization. Most columns are completely non-null, so the definition-level sequence is a single run that covers the whole page and costs a handful of bytes. The Dremel encoding looked expensive when we derived it; RLE is the reason it is cheap.