Why can a columnar engine group by a dictionary-encoded string column faster by hashing the integer codes?

## Setup: what dictionary encoding gives execution Dictionary encoding stores a column as two things: a dictionary of the distinct values, and, for each row, a small integer code identifying which dictionary entry it holds. A `country` column with 200 distinct values becomes a vector of one- or two-byte codes plus a 200-entry string dictionary. It is chosen for compression, but its effect on *execution* is at least as important, and this is where the interview question lives. ## The cost of grouping on raw strings A hash aggregation over `GROUP BY country` does, per row: load a pointer and a length, run a hash function over the bytes, probe a hash table, and on any collision or match compare the bytes to confirm equality. Three of those steps are variable-cost and pointer-chasing; the string bytes live somewhere other than the column buffer, so each probe risks a cache miss the prefetcher cannot anticipate. None of it vectorizes well, because lane width is undefined for variable-length data. ## The cost of grouping on codes Now do the same on the codes. Per row: load a fixed-width integer from a contiguous buffer, mix it into a hash with a couple of arithmetic instructions, probe, compare with one integer compare. Everything is fixed width, everything is in the vector already being streamed, equality is exact with no byte comparison, and the loop is branch-free enough to keep the pipeline full. The hash table's keys are also 4 or 8 bytes rather than pointers to strings, so far more of it fits in cache — which matters enormously, because a hash aggregation's probe is the classic random-access cache-miss generator. ## The special case worth naming: no hash at all If the engine knows the code range is small — say fewer than a few thousand distinct values — it can skip hashing entirely and use the code as an **array index** into a dense array of accumulators. That is a perfect, collision-free hash: one load, one add, done. Multi-column grouping can use the same trick by packing several narrow codes into one integer key ("grouping keys as a bit-concatenation"), and only falling back to a real hash table if the packed key space is too large. This is why low-cardinality `GROUP BY` in a columnar engine can run at close to scan speed. ## Decoding late The accumulators are keyed by code, so the output labels are missing. The engine resolves them once at the end: for each *group*, look up the dictionary entry. Over a billion input rows producing 200 groups, the dictionary is consulted 200 times rather than a billion. The same idea applies to filters: `WHERE country = 'DE'` can be answered by resolving `'DE'` to its code once and then comparing integers for the whole chunk — and if the value is absent from a chunk's dictionary, the entire chunk is skipped without reading its codes. ## The complication: dictionaries are local The reason this is a real interview question rather than a trivia fact is the failure mode. Dictionaries in analytical formats are typically built **per file, per row group or per chunk**, not globally, because a global dictionary would need coordination across every writer. Consequently code `7` in one file and code `7` in another may be different strings. An engine therefore cannot blindly aggregate codes across files. The usual strategies: - **Per-chunk aggregation, then merge on decoded values.** Aggregate on codes within a chunk, decode the (few) group keys, and merge partials globally on the real values. - **Remapping.** Build a translation table from each chunk's local codes into a query-scoped global code space as chunks are opened, then aggregate globally on the remapped codes. - **Give up per chunk.** If a chunk's dictionary is huge or the column falls back to plain encoding — which writers do when cardinality grows too high — the engine aggregates on values for that chunk. That last point is the practical caveat: dictionary encoding is chosen by the writer based on observed cardinality, so a column you *believe* is dictionary-encoded may not be in every file. High-cardinality columns (UUIDs, free text, timestamps at microsecond precision) usually are not, and the code-level speedup silently disappears. If a `GROUP BY` on what you thought was a low-cardinality column is slow, checking whether the column is actually dictionary-encoded, and whether the encoding survived the last load, is a legitimate first move. ## What to demonstrate Name the three wins in order — fixed-width keys, cache-resident hash table, direct-indexed accumulators for small ranges — then the decode-once-per-group point, then the per-chunk-dictionary caveat. The last one is what separates a memorized answer from an operational one.