How can a columnar engine filter and group a dictionary-encoded column without decoding it?

## Why encoded data is still usable data A lightweight encoding preserves the *structure* of the column, which is exactly what a general byte codec destroys. That preservation is what lets the engine push work down onto the encoded representation rather than reconstructing the original values first. The gains are large because the encoded form is both smaller and cheaper to compare — integers instead of strings. ## Predicate evaluation against the dictionary The central idea: **a predicate on a column with N distinct values needs at most N evaluations, not one per row.** For each chunk the engine takes the chunk's dictionary and applies the predicate to every entry, producing a bitmap over codes: ``` dictionary : 0=US 1=DE 2=FR 3=GB predicate : country IN ('DE','FR') code set : {1, 2} row scan : compare each 2-bit code against {1,2} ``` Three consequences follow. 1. **Expensive predicates become cheap.** A pattern match, a case-insensitive comparison, even a function call is evaluated a few thousand times instead of a few hundred million. The per-row work collapses to an integer membership test. 2. **Whole chunks disappear.** If no dictionary entry satisfies the predicate — the literal simply is not present in this chunk — every row in the chunk is guaranteed not to match and the code stream is never read. This is a genuine skip, and it is why dictionary-encoded, well-clustered columns filter so well. 3. **Ranges depend on dictionary order.** If the dictionary is stored in sorted order, a range predicate maps to a contiguous run of codes and comparisons stay ordinal. If it is not sorted, the engine still evaluates entry by entry and gets a code set — correct, just not contiguous — so range filters remain cheap but lose the ordinal shortcut, and ordering the output by that column requires the real values. ## Grouping and aggregation on codes A `GROUP BY` on a dictionary-encoded column can hash the **codes**. Integer hashing beats string hashing, the keys are narrow, and the hash table stays small enough to sit in cache. When a chunk's dictionary is small the engine can skip hashing entirely and use the code as a direct array index — an array of accumulators sized to the dictionary. Only at the very end, when the result set is produced, does it decode the surviving group keys back to their values. Since the result usually has far fewer rows than the input, decoding is a rounding error in the total cost. Distinct counts benefit for the same reason: within a chunk, distinctness of values is distinctness of codes. ## Run-length encoding: aggregate a run at a time Where dictionary encoding shrinks the *width* of each comparison, run-length encoding shrinks the *number* of them. A run is a value and a count, so: - `COUNT(*)` per group adds the run length instead of incrementing per row. - `SUM(x)` over a run of a constant value is one multiplication. - A filter on the run's value either accepts or rejects the entire run in one test. A sorted, run-length-encoded column can therefore be aggregated in time proportional to the number of runs rather than the number of rows — which loops back to why sort order matters so much. ## Where the technique stops Be explicit about the boundaries; interviewers probe them. - **General byte codecs block everything.** A ZSTD- or LZ4-compressed block is opaque bytes. It must be decompressed before any of the above applies. Only the lightweight encodings survive into execution. - **Per-chunk dictionaries are not comparable.** Code 3 means one thing in this chunk and another in the next. Any operation spanning chunks — a global aggregation, a join, a merge sort — must decode or remap codes to a common space. Engines handle this, but it is real work and it is why the win is largest for filters and local aggregations. - **Joins are the hard case.** Joining on an encoded column generally requires the join key in a comparable form on both sides, which usually means decoding or building a shared mapping. A dictionary-encoded column is not automatically a cheap join key. - **Arbitrary expressions may force decode.** If an expression cannot be evaluated over the dictionary — because it combines two columns row by row, for example — the engine must materialise the values. - **Output eventually needs values.** Anything returned to the client is decoded. The design goal is to defer that to the smallest possible result, not to avoid it. ## The framing to give Say it as a cost transformation: *encoding moves work from per-row to per-distinct-value, and from per-row to per-run.* Then name the two limits — opaque byte codecs and per-chunk code spaces — and you have covered both the mechanism and its edges.