skip to content

What happens when a columnar engine dictionary-encodes a column with millions of distinct values per block?

level: seniorimportance: should knowfreq 45%

answer

  1. The dictionary itself must be stored too
  2. Code width tracks log2 of distinct count
  3. What matters is distinct values per block
  4. Engines give up and store the column plain

basics

~20 s

The dictionary grows toward the size of the column itself and each code widens to roughly log2 of the cardinality, so the saving collapses. Most engines detect this and fall back to plain storage, leaving only the general codec to compress the column.

solid answer

~50 s

Dictionary encoding pays off when a block has few distinct values relative to its row count. Push cardinality up and two things degrade at once: the **dictionary** must store every distinct value, approaching the raw column size when nearly every row is unique, and the **code width** grows with log2 of the distinct count, so codes stop being narrow. At the limit you store the data twice plus an index. Engines therefore sample each block and fall back to plain storage — which is the right call, but it means the column's ratio quietly depends on data you don't control, and a rise in distinct values can inflate storage and bytes scanned without any schema change. There are also runtime costs: building and holding large per-block dictionaries consumes memory during write and scan, and lookups become random memory access that misses cache. The fixes are structural — reduce distinct values *per block* by sorting or partitioning, or split the column so a low-cardinality component can be encoded separately.

code

text · 5 lines
text
block = 1,000,000 rows

low cardinality  (5 distinct)   : dict ~ tiny         + 3 bits/row  -> huge win
medium           (100k distinct): dict ~ 100k values  + 17 bits/row -> still a win
high             (1M distinct)  : dict ~ whole column + 20 bits/row -> bigger than plain

go deeper

for a junior

Recall that dictionary encoding pays off only when values repeat; with nearly unique values you end up storing the data plus an index of it.

for a middle

Explain both cost terms — dictionary size and code width — and why the cardinality that matters is measured within a block rather than across the table.

for a senior

Demonstrate the diagnosis and the fixes: per-column byte inspection, distinct values per block, sorting or splitting the column, and knowing when to stop and accept plain storage.

for a principal

Own the fact that encoding choice is data-dependent and can shift without a deploy; decide how storage regressions get detected and who owns column design for high-cardinality identifiers.

## What dictionary encoding actually costs A dictionary-encoded column chunk is two artefacts: the **dictionary**, holding each distinct value once, and the **code stream**, holding one integer per row. Total size is roughly ``` distinct_values x average_value_size + rows x ceil(log2(distinct_values)) bits ``` Both terms grow with cardinality, which is why the encoding degrades from both ends simultaneously. - With 5 distinct values over a million rows: a trivial dictionary plus 3 bits per row. Enormous win. - With 100,000 distinct values: the dictionary is real but amortised, and codes are 17 bits — still a win over wide strings. - With a million distinct values over a million rows: the dictionary stores every value once (the raw column), plus 20 bits per row of codes on top. You have made the column **bigger**, and you also pay to build the structure. ## Cardinality is per block, not per table The number that matters is distinct values **within one block or chunk**, because dictionaries are normally scoped there. A URL column with a hundred million distinct values table-wide might have only a few thousand distinct values inside a block if the data is sorted or partitioned in a way that clusters them. Conversely a genuinely random high-cardinality column has near-block-size cardinality in every block. This distinction is the entire lever you have: you cannot reduce the column's global cardinality, but you can often reduce its **local** cardinality. ## What engines do about it Most columnar writers sample or fully scan each block, estimate distinct count, and abandon dictionary encoding above a threshold — falling back to plain storage with the general byte codec on top, or to a different encoding if one fits. That is correct behaviour, and it has a consequence worth stating in an interview: **encoding choice is data-dependent and can change under you**. A column that dictionary-encoded beautifully at 10,000 distinct values can silently fall back after a change upstream pushes it to millions, and the symptom is a jump in stored bytes and in bytes scanned per query, with no schema or query change to blame. ## Runtime, not just storage Beyond size, large dictionaries hurt at both ends of the lifecycle: - **Write:** the encoder builds a hash table of distinct values per block. A huge dictionary means memory pressure and slower ingest, and it can push the writer into smaller blocks, which costs ratio again. - **Read:** decoding a value means indexing into a large dictionary — random memory access with poor cache behaviour. Small dictionaries live in cache and are nearly free; large ones are not. - **Cross-block operations:** dictionaries are per block, so code 7 in one block and code 7 in another mean different values. Any operation that spans blocks — a global GROUP BY, a join, a sort — must decode or remap. With small dictionaries that is cheap; with large ones the remap itself becomes real work. ## Diagnosing it Symptom: one column dominates the table's storage, or a scan reads far more bytes than the row count and column type suggest. Confirm it by looking at **per-column compressed bytes** rather than table totals, and by measuring distinct values inside a realistic block boundary — count distinct within one partition or one day of data, not across the whole table, because the table-wide number will overstate what the encoder sees. ## Fixes, in the order worth trying 1. **Reduce local cardinality.** Sort or cluster the load so similar values land in the same block. A column that is random table-wide but grouped by tenant or host inside a block gets its dictionary back. 2. **Split the column.** High-cardinality strings are frequently composites: a URL is a host (thousands of distinct values) plus a path; an identifier is a prefix plus a serial. Store the low-cardinality part as its own column — it dictionary-encodes well, and it is usually the part queries filter on. The remaining tail may still be incompressible, but you have removed the repeated portion. 3. **Normalise to a surrogate.** If the values come from a bounded set that merely looks unbounded, map them to integers upstream and store the mapping once, table-wide, instead of re-deriving a dictionary per block. 4. **Accept plain plus a stronger codec.** For genuinely random values — UUIDs, hashes, tokens — no encoding will help. The honest answer is to stop trying, choose a higher-ratio general codec if storage matters, and if possible avoid storing the column in the hot table at all. ## The framing to give Dictionary encoding is a bet that repetition exists locally. Above a cardinality threshold the bet loses, the engine folds, and your ratio silently becomes whatever the byte codec can manage. The engineering work is not tuning the dictionary — it is changing the data layout so repetition exists where the encoder can see it.

  • How would you reduce a column's cardinality as seen by the encoder without changing its values?
    Change what lands in a block. Sorting or clustering the load so rows sharing a value are adjacent cuts distinct values per block sharply, even when the table-wide count is unchanged. Partitioning by a correlated attribute does the same. The encoder only ever sees one block, so local clustering is the whole lever.
  • Why not keep one dictionary for the whole column instead of one per block?
    A table-wide dictionary must be built, held and updated for every write, and it must be loaded to read any block — turning a per-block decision into a global dependency. Per-block dictionaries bound memory and let each block choose its own encoding, at the cost that codes are not comparable across blocks.
  • A URL column is destroying your storage budget. What would you change?
    Split it. The host component usually has a few thousand distinct values and dictionary-encodes well, and it is typically what queries filter on; the path tail stays high entropy. Storing host and path separately recovers most of the ratio, improves filtering, and leaves only the genuinely random remainder to the general codec.

saying these in an interview costs you the question

  • Says dictionary encoding always shrinks string columns
  • Uses table-wide distinct count instead of per-block
  • Thinks code width is fixed regardless of cardinality
  • Forgets the dictionary itself occupies storage
  • Believes codes are comparable across different blocks

context

resolving links…