Dictionary Encoding and the Cardinality Cliff

A column holding 40-character product names repeats itself heavily. Storing each name once in a dictionary and each row as a small integer ordinal turns 40 bytes per row into one or two, and the ordinals then compress further because they follow the row order of the data. This is dictionary encoding, and on a low-cardinality column it is the single largest win available to a columnar writer.

On a high-cardinality column the same mechanism is a liability. The dictionary holds nearly every value, so the file stores the values twice, once in the dictionary and once as ordinals, and the ordinals are wide because the domain is large. The transition between the two regimes is sharp, and formats handle it with a budget rather than with a smarter encoding.

The mechanism and its accounting

The writer maintains a hash map from value to ordinal while filling a column chunk. The first occurrence of a value appends it to the dictionary and emits its index; later occurrences emit the index alone. Data pages then contain ordinals, encoded with whatever bit width or run-length scheme the writer chooses, and a single dictionary page at the head of the chunk holds the values themselves.

For a column of $n$ rows with $d$ distinct values of average width $w$ bytes, dictionary-encoded storage is approximately $d \cdot w$ bytes of dictionary plus $n \cdot \lceil \log_2 d \rceil / 8$ bytes of ordinals, against $n \cdot w$ bytes plain. The break-even point follows from setting the two equal. With $w = 40$ and 8-bit ordinals ($d \le 256$), the ordinal stream costs one byte per row and the dictionary costs at most 10 KB, so the encoding wins for any $n$ above a few hundred. With 16-bit ordinals the cost is two bytes per row, and the encoding still wins while $w$ is large.

The cliff appears when $d$ approaches $n$. Then the dictionary costs $n \cdot w$ and the ordinals cost $n \cdot \lceil \log_2 n \rceil / 8$, so the total exceeds the plain encoding by the ordinal stream. For a million distinct 40-byte strings, plain storage is about 40 MB and dictionary storage is about 40 MB of dictionary plus 2.5 MB of 20-bit ordinals, roughly a 6 percent loss. The loss is not catastrophic; the real damage is that the dictionary page must be read and parsed before any data page can be decoded, and the hash map must be built at write time, so the writer pays memory and CPU proportional to $d$ with no compression benefit.

Ordinal width compounds the effect. A dictionary of 300 values needs 9 bits per ordinal, which most implementations round to 16, so a column that just overflows an 8-bit ordinal pays twice the width for one extra value. Writers that pack at exact widths avoid the rounding but pay a decode cost; writers that round keep the decoder branchless. Either way, the step at each power of two is a place where a small change in cardinality produces a disproportionate change in size.

The budget and the fallback

Parquet’s specification does not require dictionary encoding, and implementations apply a heuristic: if the dictionary grows beyond a configured fraction of the column chunk or beyond a size limit, the writer abandons it for the remainder of the chunk. The already-written pages stay dictionary-encoded; later pages fall back to plain or to another encoding. The format permits this because each page header names its own encoding, so mixed encodings inside one chunk are legal and expected.

The consequence is that a chunk can contain both a dictionary page and plain pages, and the reader must handle both. It also means the transition is irreversible within a chunk: a writer that has spent its budget cannot return to dictionary encoding later even if the values become repetitive again, because the dictionary page has already been written and its ordinals are already fixed.

A common alternative to a hard fallback is a two-pass strategy: sample the column, estimate cardinality, and choose the encoding before writing any page. This produces a more uniform file at the cost of buffering or re-reading. Streaming writers cannot do it, which is why the budget approach dominates in practice.

When dictionary encoding beats the alternatives

The comparison that matters is against delta and run-length encoding, which also exploit structure, and against general-purpose compression applied to plain values.

On a sorted column, delta encoding usually wins over a dictionary, because the differences between adjacent values are small and the values themselves need not be stored twice. On a column of long strings with high cardinality but shared prefixes, prefix or front coding wins, as described in Varints, Zigzag, and Prefix Encoding of Integers. On a column with long runs of identical values, run-length encoding reduces a million-row run to a pair of integers and does not need a dictionary at all. Dictionary encoding wins in the middle: moderate cardinality, no ordering, and no long runs, which describes most categorical fields, identifiers repeated across a fact table, and the string keys of a dimension.

The comparison against general-purpose compression is subtler. A general-purpose compressor over plain values can find repeated substrings across the page and achieve much of the dictionary’s win without the writer maintaining a hash map. The difference is that a dictionary makes the repetition explicit and random-access-friendly: the ordinal stream can be filtered and compared without decompressing strings, whereas a general-purpose compressor must expand the page before any comparison. That is why dictionary encoding survives even when a general-purpose codec would compress the raw bytes comparably: the win is in the operator, not only in the file size.

Interaction with filtering and statistics

Ordinals are integers, so filtering a dictionary-encoded column compares integers instead of strings, which is a large constant-factor win in the inner loop. But the predicate arrives as a string, so the engine must first translate it into the set of matching ordinals by scanning the dictionary, then compare ordinals. The translation is $O(d)$ per predicate per chunk, negligible when $d$ is small and expensive when $d$ is large, which reinforces the same threshold from a different direction.

Statistics interact badly with dictionaries in one specific way. The min and max recorded for a column chunk should be the min and max of the values, not of the ordinals, and the two orders differ unless the dictionary was built in value order. A writer that records the ordinal range produces a statistic that a reader will use to skip row groups incorrectly. Implementations that sort the dictionary by value avoid the problem; those that do not must compute statistics from the values as they are inserted, which is the reason some writers disable dictionary encoding on columns where skipping matters more than size.

Sorting the dictionary also helps the ordinals compress, because value order and row order then correlate when the column is sorted, producing long runs in the ordinal stream that run-length encoding collapses. This is a case where the encoding choice and the sort order of the data interact, and where a writer that knows the data is clustered on a field can choose the dictionary order deliberately.

Cardinality is a property of the chunk

The difficulty is structural: cardinality belongs to the chunk, not to the column. A column of user identifiers is high-cardinality in a chunk covering a month of activity and low-cardinality in a chunk covering one hour of one shard. The same schema, written with different row group boundaries, produces files where the encoding succeeds and files where it fails. Since the row group boundary is a writer decision examined in Inside a Parquet File, the encoding outcome is downstream of a buffering policy that is usually set once, globally, for reasons unrelated to encoding.

A planner cannot tell from the footer alone how a chunk was encoded at the page level, so a cost estimate built from file metadata will be systematically wrong on one side or the other. The chunk metadata does list the set of encodings used in the chunk and, optionally, a per-page encoding histogram, which is a summary rather than a map: it says dictionary encoding appears somewhere in the chunk, not which pages use it or how large the dictionary is.