Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

String interning and dictionary reuse

How much does a dictionary save, and why does its scope decide whether it becomes a leak?

The constraint

Variable-length data violates every assumption of the previous items. You cannot compute its size before allocating, cannot address it by fixed stride, cannot pool it cleanly by . And in real data, string columns are heavily repeated: the number of distinct values is low compared with the number of rows.

The arithmetic

For n rows, d distinct values and average length L:

  • naive storage: n·(L + header);
  • dictionary storage: d·L + n·⌈log₂ d⌉/8 bytes (the dictionary itself plus one code of ⌈log₂ d⌉ bits per row).

(If each naive string also pays a 16-byte header, the saving is about 29×. Rounding each code up to a whole 2 bytes per row gives 20 MB and 10×.)

The second-order win is larger than the first. Equality becomes integer comparison. Hashing becomes hashing an int. A group-by on a dictionary column can be a directly-addressed array (index by code) rather than a hash table, which removes a whole hash table from the memory reservation that Rationing must make.

The real question is scope, not encoding

Who owns the dictionary, how long does it live, is it shared?

  • Per-batch dictionary. Memory is bounded by construction. But codes are not comparable across batches, so every cross-batch operation decodes or re-maps. Shuffle boundaries force re-dictionarization.
  • Engine-wide intern table. Codes are comparable everywhere, which is a real win. But the table is unbounded live state that grows with every distinct value ever seen and never shrinks. It is also shared, so it is contended. This is the mechanism that converts a compression win into a leak. A high-cardinality column (a UUID, a URL with query parameters) meets a global intern table, and the table becomes your . String.intern() over unbounded input is the textbook case, and the same bug has shipped in every engine that tried it.
  • Bounded table with eviction. This brings back a replacement policy (see Residency) and admits that two identical strings may receive different codes, which breaks "compare by code" as an invariant.

The honest framing: is a bet on cardinality that is checked only at run time, and the failure mode is unbounded growth, not slowness. It does not show up in latency until it shows up as an . So every production implementation carries a cap and a fallback. Parquet writers abandon dictionary encoding for plain encoding when the dictionary page crosses its size threshold. The in-memory version of that decision is the same decision, made under the same pressure.

The general principle: a fixed-capacity structure meeting growing cardinality breaks the design. It is a fallback path, just like widening a transaction ID or giving an undo log an overflow rule.

One-line compression: interning converts repetition into integers and cardinality into a leak. Every production dictionary therefore ships with a cap and a fallback.