Why do per-column encodings such as run-length, dictionary and delta pay off in a columnar file but not a row-major one?
answer
- think about what neighbouring values share
- same type, same domain, adjacent
- runs, repeats, small differences
- codes replace repeated values
- interleaving records breaks the patterns
basics
~20 sValues inside one column share a type and a value domain, so runs repeat, distinct values are few and neighbouring numbers sit close together — exactly the redundancy run-length, dictionary and delta encoding exploit. Row-major order interleaves unrelated fields and destroys it.
solid answer
~50 sEvery one of these encodings is a bet about what the next value looks like. Run-length bets the next value equals this one; dictionary bets the column draws from a small set of distinct values; delta bets the next value is numerically close. Those bets only pay when neighbouring bytes come from the same column, which is precisely what a column-oriented layout guarantees and what interleaving fields of different types destroys. A status column of a billion records with a few hundred distinct values becomes one-byte codes into a small table — roughly a tenfold shrink before any general-purpose codec runs. Encoding and block compression are then two separate stages: encoding uses knowledge of the column's domain, the codec only sees bytes, and the codec finds far more redundancy in an encoded homogeneous run than in interleaved records.
go deeper
Recall what each encoding replaces: repeats become a value plus a count, repeated values become small codes into a table, and near-neighbours become differences. All three need similar values to sit next to each other.
Explain why adjacency is the precondition and separate domain-aware encoding from the domain-blind codec that runs after it. A worked number helps: 200 distinct values need an eight-bit code against roughly ten bytes of text.
Bring the trade-offs: high-cardinality columns where a dictionary backfires, decode processor cost on a scan that is already compute-bound, and sort order as the biggest ratio lever a write path actually controls.
Own the write-path policy. Decide which sort order a dataset is clustered by, who pays the write-time cost, and how you know the chosen encodings still suit the data months later as its cardinality and distribution drift.
## Homogeneity is the precondition, not a bonus Compression of any kind exploits **redundancy that is local**: a coder looks at a window of recent bytes and predicts what comes next. Record-at-a-time order puts a timestamp next to a country name next to a price next to a device identifier; nothing in that window predicts anything else in it. Column order puts a timestamp next to the next timestamp. Same data, same total size before encoding, wildly different predictability. That is why the encodings discussed here are described as **per-column**: each is a statement about a column's *domain*, and each is only checkable when the column's values are adjacent. ## What each encoding bets on | Encoding | The bet it makes | A column it suits | Where it fails | |---|---|---|---| | Run-length | The next value equals this one | A low-cardinality field, especially after sorting | Values alternate constantly | | Dictionary | The column draws from few distinct values | Country, status, device class, event name | Near-unique values such as identifiers | | Delta | The next value is numerically close | Timestamps, counters, monotonically rising keys | Values scattered over the full range | Worked numbers for the dictionary case: a country column over one billion records with roughly 200 distinct values. A code must distinguish 200 values, so it needs `ceil(log2(200)) = 8` bits — one byte — against an average of about ten bytes for the text itself, plus one small table of the 200 distinct strings held once per chunk. That is about a tenfold reduction, achieved with no general-purpose codec involved at all. For the delta case: timestamps in milliseconds stored as eight-byte integers, written roughly in time order, with consecutive differences that fit comfortably in two bytes. Storing differences rather than absolute values turns 8 GB into roughly 2 GB, again before any codec runs. ## Encoding and compression are two stages, not one Interviews often blur these, and separating them is a good signal: 1. **Encoding** is domain-aware. It knows this run of bytes is one typed column and applies a transform that only makes sense there — replace repeats with a count, values with codes, absolutes with differences. 2. **Block compression** is domain-blind. A general-purpose codec sees a byte stream and finds repeated substrings and skewed byte frequencies. 3. **They compose.** Encoding both shrinks the input and makes what remains more regular, so the codec then finds more. Running a codec straight over interleaved records skips step one entirely and hands step two its worst-case input. A further consequence worth volunteering: some filters can be evaluated **on the encoded form**. If a column is dictionary encoded, a reader can translate the predicate's literal into a code once and then compare small integers, never materialising the strings. That is a property of the encoding, not of the codec — a block-compressed stream has to be decompressed before anything can be tested. ## When it does not pay - **High cardinality.** A near-unique identifier column gives a dictionary almost as large as the column, plus an extra indirection on every read. Some writers detect this and fall back to storing values directly. - **Unordered numeric data.** Deltas of randomly distributed values are as wide as the values, so nothing is saved and a decode step is added. - **Decode CPU.** Higher ratios are not free: every layer added has to be undone on the read path, and a scan that is already limited by processor time can get slower even as it reads fewer bytes. - **Small chunks.** A chunk of a few hundred records offers no runs worth collapsing and a dictionary whose table rivals its data. ## Why sort order is the hidden lever The single biggest ratio change available to a writer is usually not the codec but the **order records are written in**. Sorting a chunk by a low-cardinality column turns scattered repeats into long runs, which run-length encoding collapses to a handful of pairs; it also clusters the secondary columns that correlate with the sort key, and it makes a near-sorted numeric column delta-friendly. Sorting costs write-time memory and time, and it can only be done by one order at a time, so it is a genuine trade-off rather than a free win — but it is where the leverage is. The conclusion an interviewer wants is the causal chain, not a list of encoding names: layout creates homogeneity, homogeneity is what these encodings bet on, and record-at-a-time layout destroys the homogeneity before any encoder gets a chance.
- Why can sorting records before writing them change the compression ratio so much?Sorting turns scattered repeats into long unbroken runs, which run-length encoding collapses into a few value-count pairs, and it makes a numeric column near-monotonic so deltas stay small. It also clusters any column correlated with the sort key. The costs are write-time memory and time, and only one sort order can be exploited at a time.
- When does dictionary encoding actively hurt?When cardinality approaches the record count. A near-unique identifier column produces a dictionary nearly as large as the data, so total size grows, and every read pays an extra indirection through the table. Writers that detect high cardinality fall back to storing the values directly, which is the right call.
A warehouse that shelves all screws of one size together labels the shelf once and counts by the box. Put one screw, one bolt and one washer in every box and each box needs its own full description.
saying these in an interview costs you the question
- Says compression is just the codec and layout makes no difference
- Claims dictionary encoding always shrinks a column, whatever its cardinality
- Thinks delta encoding helps on values scattered across the whole range
- Assumes a filter can never be evaluated against encoded values
- Treats a higher ratio as free, ignoring decode processor cost