Dictionary Encoding

Strings repeat. "USA" might appear in millions of rows of a country column.

Dictionary encoding:

1. Build a dictionary: {0: "USA", 1: "Canada", 2: "Mexico", ...}.
2. Replace each value with its dictionary index: [0, 1, 0, 2, 0, ...].

Storage: 1MB strings → 1MB of small ints (4-byte indices) + tiny dict.

Cardinality matters:

• Low cardinality (< 1000 distinct values): huge savings.
• High cardinality (close to distinct per row): little savings (dict + indices ~= original).

Impl:

Bit-packed indices: if dict has 100 entries, indices need only 7 bits each.

• 8 indices = 7 bytes (packed) vs 8 bytes (per-byte).
• Decompression is bit-shifting, very fast.

Operations on dictionary-encoded data:

• Equality filter: lookup target in dict (1 dict lookup), then scan indices for matches. Skip the strings entirely.
• Range filter: lookup range in dict (or scan), get matching indices, scan column.
• Group by: indices ARE the group keys. Cheap!

Modern systems detect cardinality at write time and pick encoding:

• < 1024 distinct: dict-encode.
• Close to row count: leave raw.
• Numeric in tight range: bit-pack.

Parquet uses dictionary encoding by default for low-cardinality columns; falls back to raw if dict overflows.

Across stripes: each stripe may have its own dictionary. Allows independent processing.