Dictionary Columns Are a Hash Cache: How DataFusion Groups by Dictionary Index and What That Buys
DataFusion exploits Arrow dictionary columns to hash and compare group keys once per distinct value instead of once per row
TL;DR: A
DictionaryArrayis not a compressed column — it is a pre-built hash cache that the file format already paid for. DataFusion exploits that: it hashes theDdistinct dictionary values once, scatters theDhashes out to theNrow positions, and memoizes avalue index → group slotmap, so a row whose key repeats a dictionary index costs one array lookup instead of a string comparison.GROUP BYon a dictionary column doesO(D)hashing work per batch, notO(N). And DataFusion will introduce dictionary encoding for you when reading Parquet, because Parquet files already contain the dictionary.
The naive way to group a string column
GROUP BY country over 10 million rows means 10 million string
comparisons and 10 million string hashings. The strings are long, the
values repeat (maybe 200 distinct countries), and the CPU spends all its
time re-deriving facts the data already told it.
The obvious fix is to intern the strings into integers first: build a table
value → id, replace each string with its id, group the ids. That is
exactly what a dictionary-encoded Arrow column already is:
DictionaryArray<Int32, Utf8>
keys: [ 0, 1, 0, 1, 2, 0, ... ] <- one Int32 per row
values: [ "US", "DE", "FR" ] <- the distinct values, onceThe keys array says “row 0 has value 0”; the values array is the
interned table. DataFusion’s job is to use that table rather than throw
it away.
The hashing trick: hash the values, scatter to the keys
The first place the dictionary pays off is hashing. A hash aggregation
must compute a u64 hash per row. For a plain string array that means
hashing 10 million strings. For a dictionary array, the same 200 distinct
strings only need hashing once — the hashes are then scattered to the row
positions by looking up each row’s key.
// datafusion/common/src/hash_utils.rs:626-642
/// Hash the values in a dictionary array.
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_dictionary<K: ArrowDictionaryKeyType>(
array: &DictionaryArray<K>,
random_state: &impl HashState,
hashes_buffer: &mut [u64],
multi_col: bool,
) -> Result<()> {
// Hash each dictionary value once, and then use that computed
// hash for each key value to avoid a potentially expensive
// redundant hashing for large dictionary elements (e.g. strings)
let dict_values = array.values();
let mut dict_hashes = vec![0; dict_values.len()];
create_hashes([dict_values], random_state, &mut dict_hashes)?;
dispatch_dictionary_scatter(array, &dict_hashes, hashes_buffer, multi_col);
Ok(())
}The shape is O(D) hashing plus O(N) cheap array reads. The scatter
itself uses const generics to eliminate runtime branching:
// datafusion/common/src/hash_utils.rs:522-539
/// Scatter precomputed dictionary value hashes to key positions.
///
/// Uses const generics to eliminate runtime branching in the hot loop:
/// - `HAS_NULL_KEYS`: Whether to check for null dictionary keys
/// - `HAS_NULL_VALUES`: Whether to check for null dictionary values
/// - `MULTI_COL`: Whether to combine with existing hash (true) or initialize (false)
#[cfg(not(feature = "force_hash_collisions"))]
#[inline(never)]
fn hash_dictionary_scatter<
K: ArrowDictionaryKeyType,
const HAS_NULL_KEYS: bool,
const HAS_NULL_VALUES: bool,
const MULTI_COL: bool,
>(
array: &DictionaryArray<K>,
dict_hashes: &[u64],
hashes_buffer: &mut [u64],
) {A dispatcher picks one of eight monomorphizations once per batch, so the
hot loop contains zero null checks and zero branches on the multi-column
flag. Note the null subtlety the const generics encode: a valid
dictionary key can point at a null dictionary value. That row is
logically null but physically valid, and HAS_NULL_VALUES handles it.
The grouping trick: memoize value-index → group-slot
Hashing is only half of it. After the hash, the aggregation must decide “is this row’s key the same group as the one in bucket H?”. The natural answer is to compare the values. But the dictionary gives a better answer: within one dictionary, the same index means the same value.
DataFusion’s DictionaryGroupValuesColumn is built around that idea. Its
state is three things: the dedup store of values, a hashbrown table that
bridges batches, and a per-batch memo:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:37-71
/// [`GroupColumn`] for dictionary-encoded columns with key type `K`.
///
/// `inner` holds one slot per distinct value seen across all batches.
/// `group_to_inner[group_idx]` maps each group to its slot in `inner`,
/// so groups with the same value share a slot rather than duplicating data.
pub struct DictionaryGroupValuesColumn<K: ArrowDictionaryKeyType + Send + Sync> {
/// Deduplicated store of distinct values.
inner: Box<dyn GroupColumn>,
/// Unary null array (length 1) reused for every null appended to `inner`.
null_array: ArrayRef,
/// Maps each group index to its slot in `inner`.
group_to_inner: Vec<usize>,
/// Lookup table mapping `(value_hash, inner_slot)` for each non-null distinct value.
value_dedup: HashTable<(u64, usize)>,
...
/// Maps `val_idx → inner_slot` for the values array in `cached_values`.
///
/// Valid only while `cached_values` is `Some` and matches the incoming
/// values array; `usize::MAX` means "not yet resolved". Entries are only
/// ever filled in, never invalidated, because `inner` slots are stable
/// under append. `take_n` remaps `inner` and therefore drops the cache.
val_to_inner: Vec<usize>,
/// Hashes of the values array in `cached_values`, one per `val_idx`.
val_hashes: Vec<u64>,
/// Weak reference to the values array that `val_hashes` and `val_to_inner`
/// were built for. A matching live array reuses both caches without
/// retaining an input dictionary after its batch is released.
cached_values: Option<Weak<dyn Array>>,
_phantom: PhantomData<K>,
}val_to_inner is the memo table. val_hashes is the precomputed hash
array. value_dedup is the cross-batch bridge: a hashbrown table mapping
(value_hash, inner_slot) so a value seen in a previous batch — with a
different dictionary, hence a different index — still resolves to the
same inner slot.
The append path is where the memo pays off:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:441-476
fn vectorized_append(&mut self, array: &ArrayRef, rows: &[usize]) -> Result<()> {
let dict = array.as_dictionary::<K>();
let dict_keys = dict.keys();
let dict_values = dict.values();
// Reuses `val_hashes`/`val_to_inner` when this batch carries the same
// values array as the last one, which is the common case downstream of
// a repartition or filter. Previously this unconditionally re-hashed
// and re-initialised both buffers, costing O(D) per batch.
self.sync_value_cache(dict_values);
...
let raw_keys = dict_keys.values();
if dict_keys.null_count() == 0 {
for &row in rows {
let val_idx = raw_keys[row].as_usize();
if self.val_to_inner[val_idx] == usize::MAX {
// A non-null key can still point to a null value in the values array.
self.val_to_inner[val_idx] = if dict_values.is_null(val_idx) {
self.find_or_insert_null()?
} else {
self.find_or_insert_value(
dict_values,
val_idx,
self.val_hashes[val_idx],
)?
};
}
self.group_to_inner.push(self.val_to_inner[val_idx]);
}
} else {Read the fast path: self.val_to_inner[val_idx]. One array read. If it
is not usize::MAX, the group slot is already known — no hashing, no
value comparison. For a batch with 10 million rows and 200 distinct
countries, 9,999,800 rows take that path.
The slow path — an index never seen before in this batch — does a hash lookup by value hash and, on a miss, appends the value to the inner store:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:208-235
fn find_or_insert_value(
&mut self,
dict_values: &ArrayRef,
val_idx: usize,
hash: u64,
) -> Result<usize> {
let inner = &*self.inner;
let existing = self
.value_dedup
.find(hash, |&(entry_hash, slot)| {
entry_hash == hash && inner.equal_to(slot, dict_values, val_idx)
})
.map(|&(_, slot)| slot);
match existing {
Some(slot) => Ok(slot),
None => {
let slot = self.inner.len();
self.inner.append_val(dict_values, val_idx)?;
self.value_dedup.insert_accounted(
(hash, slot),
|&(entry_hash, _)| entry_hash,
&mut self.value_dedup_size,
);
Ok(slot)
}
}
}This is the part that makes the whole thing correct rather than merely
fast. The grouping key is the value, not the index — because the same
value can arrive with different indices in different batches, and two
batches may use entirely different dictionaries. value_dedup bridges
that: keyed on the hash of the value, with an equality check to resolve
collisions.
So the precise statement of the optimization is:
The dictionary index is a memo key within a batch (a cache of “index → group”); the value hash is the grouping key across batches. The dictionary never changes the grouping semantics — only the cost.
The equality path: memoize, but only positive results
The comparison side has the same structure, with a subtle twist. When the
aggregation checks “does this incoming row’s key equal the group in this
bucket?”, it can consult val_to_inner — but only if the existing
group’s slot is known for that index. DataFusion exploits a fact about its
own data structure:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:237-271
/// Compares the value at `val_idx` against `inner[lhs_slot]` directly,
/// memorizing `lhs_slot` in `val_to_inner` when they are equal.
///
/// Each distinct value occupies exactly one slot in `inner`, so an equal
/// comparison proves `lhs_slot` is the slot for `val_idx` without probing
/// `value_dedup` or hashing. An unequal result is deliberately not
/// memoized: it says which slot the value is *not* in, not which one it
/// is. That is what keeps `val_to_inner` fill-only and never stale.
///
/// Only called on a `val_to_inner` miss. It takes the fields it needs
/// rather than `&mut self`, so the caller's hot loop can keep its slices
/// of `val_to_inner` and `group_to_inner` in registers across the call.
#[cold]
#[inline(never)]
fn equal_to_uncached(
val_to_inner: &mut [usize],
inner: &dyn GroupColumn,
null_array: &ArrayRef,
dict_values: &ArrayRef,
val_idx: usize,
lhs_slot: usize,
) -> bool {
let equal = if dict_values.is_null(val_idx) {
inner.equal_to(lhs_slot, null_array, 0)
} else {
inner.equal_to(lhs_slot, dict_values, val_idx)
};
if equal {
val_to_inner[val_idx] = lhs_slot;
}
equal
}Three decisions in one function:
- Only positive results are memoized. A negative result (“this index
is not that slot”) does not say which slot it is, so caching it
would be wrong. This keeps
val_to_innerfill-only, so it can never go stale. - The function is
#[cold]and#[inline(never)]. It is the rare path; keeping it out of the hot loop lets LLVM pipeline the hot loop’s array reads. - It takes
&mut [usize]rather than&mut self. The caller’s hot loop can hold its slices in registers across the call.
The vectorized path puts it together, and adds an adaptive heuristic:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:364-380
let cached = self.is_cached(dict_values);
if !cached && rhs_rows.len() < dict_values.len() {
self.equal_to_per_row(
lhs_rows,
dict_values,
dict,
rhs_rows,
equal_to_results,
);
return;
}
self.sync_value_cache(dict_values);
let raw_keys = dict_keys.values();
let group_to_inner = self.group_to_inner.as_slice();
let val_to_inner = self.val_to_inner.as_mut_slice();Building the memo costs O(D). If the batch only has a handful of rows to
check, O(D) setup to save O(rows) work is a loss — so DataFusion falls
back to a per-row comparison path. A genuinely good adaptive heuristic, and
easy to get wrong.
The “no null keys” arm of the same loop skips the get_bit(idx) guard,
with the comment explaining why: the loop only ever writes false into
equal_to_results, so overwriting an already-false bit is harmless. That
removes a branch from the hot loop.
The cross-batch cache: sync_value_cache
val_hashes and val_to_inner are only valid for a specific dictionary.
If the next batch has a different one, they must be rebuilt. DataFusion
detects this by pointer identity:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:184-206
fn is_cached(&self, values: &ArrayRef) -> bool {
self.cached_values
.as_ref()
.is_some_and(|cached| std::ptr::addr_eq(cached.as_ptr(), Arc::as_ptr(values)))
}
/// Makes `val_hashes` and `val_to_inner` correspond to `dict_values`,
/// reusing them when they were already built for this same values array.
///
/// `take`, `filter` and repartitioning clone the values `Arc` and rewrite
/// only the keys, so batches in a partition usually share one values
/// array; without this the per-batch cost is O(dictionary cardinality)
/// rather than O(rows). `take_n` remaps `inner` and clears
/// `cached_values`, forcing a rebuild.
fn sync_value_cache(&mut self, dict_values: &ArrayRef) {
if self.is_cached(dict_values) {
return;
}
self.hash_values(dict_values);
self.val_to_inner.clear();
self.val_to_inner.resize(dict_values.len(), usize::MAX);
self.cached_values = Some(Arc::downgrade(dict_values));
}The Weak reference is a nice touch: it detects “same dictionary” without
keeping the dictionary alive. If the input batch is dropped, the Weak
fails to upgrade and the cache is rebuilt for the next dictionary. Using
Weak rather than a strong Arc avoids accidentally pinning an input
batch’s dictionary buffer in memory.
The output: a dictionary again, but compacted
On the way out, group values must be emitted as a dictionary again. Group indices are group ids, and the dictionary keys must index into the values array. And the null group must not consume a key index:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:91-140
/// Build a `DictionaryArray` from `values` (all inner slots) and the
/// per-group slot mapping. The null inner slot, if any, is excluded from
/// the values array and its groups emit a null key — so it never consumes
/// a key index regardless of where it sits in `inner`.
fn into_dict(
values: ArrayRef,
group_to_inner: &[usize],
null_inner_slot: Option<usize>,
) -> ArrayRef {
let Some(null_slot) = null_inner_slot else {
// Fast path: no null group — raw slot indices are valid keys.
let keys: PrimitiveArray<K> = group_to_inner
.iter()
.map(|&slot| Some(K::Native::usize_as(slot)))
.collect();
return Arc::new(DictionaryArray::<K>::new(keys, values));
};
// Build a compact remap: each non-null slot gets a contiguous key
// starting from 0; the null slot is skipped entirely.
...
// Compact values array: drop the null slot so key indices stay tight.
let compact_indices: Int64Array = (0..n)
.filter(|&i| i != null_slot)
.map(|i| i as i64)
.collect();
let compact =
take(&*values, &compact_indices, None).expect("compact values in into_dict");
Arc::new(DictionaryArray::<K>::new(keys, compact))
}Without the remap, the null group’s slot would leave a hole in the key space, wasting a key index and making the key type overflow sooner. There is an explicit guard:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs:142-155
// https://github.com/apache/datafusion/issues/23127
// Null groups emit a null key (None), not a slot index, so the null inner
// slot never consumes a key index regardless of its position in inner.
fn check_key_overflow(&self) -> Result<()> {
let non_null_count = self.inner.len() - self.null_inner_slot.is_some() as usize;
if !Self::key_type_fits(non_null_count) {
return exec_err!(
"Dictionary key type {:?} cannot represent {} distinct values",
K::DATA_TYPE,
non_null_count
);
}
Ok(())
}An Int8 dictionary key can only address 127 distinct values. Group by a
column with 200 distinct values and the Int8 key type overflows. This
is a real failure mode of dictionary-based grouping, caught with a clean
error rather than a silent wraparound.
Where dictionary encoding comes from
Now the good part: DataFusion introduces dictionary encoding automatically, because Parquet files already contain the dictionary.
Parquet’s dictionary encoding stores, per column chunk, a dictionary page (the distinct values) plus RLE-encoded indices into it. The information is right there in the file. By default the Parquet reader expands it back to plain values, throwing away the dictionary and paying to re-derive it.
DataFusion has a config option to keep it:
// datafusion/common/src/config.rs:1429-1438
/// (reading) If true, top-level string and binary Parquet columns with
/// dictionary pages are inferred and scanned as
/// `Dictionary<Int32, Utf8>` / `Dictionary<Int32, Binary>` instead of
/// their plain value type.
///
/// This applies only when DataFusion infers the table schema. Tables with
/// a user-supplied schema are not promoted because the Parquet footer is
/// not read at DDL time, so dictionary pages cannot be detected per column.
/// See <https://github.com/apache/datafusion/issues/24112>
pub enable_rle_to_dictionary: bool, default = falseThe promotion happens at schema-inference time, by inspecting the Parquet footer for dictionary pages:
// datafusion/datasource-parquet/src/metadata.rs:463-505
let schema = if self.enable_rle_to_dictionary {
let schema_descr = file_metadata.schema_descr();
// Top-level columns that have a dictionary page in at least one row group.
let dict_cols: HashSet<String> = metadata
.row_groups()
.iter()
.flat_map(|rg| {
rg.columns()
.iter()
.enumerate()
.filter_map(|(col_idx, col)| {
col.dictionary_page_offset()?;
let col_desc = schema_descr.column(col_idx);
let parts = col_desc.path().parts();
// Skip nested columns: their leaf name doesn't match the
// Arrow top-level field name.
(parts.len() == 1).then(|| parts[0].clone())
})
})
.collect();Note “in at least one row group” and the parts.len() == 1 check — only
top-level columns are promoted, because for a nested column the Parquet
leaf name does not match the Arrow field name.
Since different files may disagree, the schemas are normalized before merging:
// datafusion/datasource-parquet/src/file_format.rs:494-499
// Normalize dict-promoted schemas before merging so mixed dict/plain files merge cleanly.
let mut schemas: Vec<Schema> =
schemas.into_iter().map(|(_, schema)| schema).collect();
if self.options.global.enable_rle_to_dictionary {
schemas = crate::schema_coercion::uniform_dict_schemas(schemas);
}So the user-visible schema has a Dictionary column, and the whole
pipeline — including the GROUP BY — sees a dictionary. The
dictionary-aware group column is selected automatically, because the type
dispatch in make_group_column handles DataType::Dictionary:
// datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs:1025-1051
DataType::Dictionary(key_dt, value_dt) => {
let new_field = Field::new("", *value_dt.clone(), true);
let inner = make_group_column(&new_field)?;
macro_rules! dict_col {
($T:ty) => {
Box::new(dictionary::DictionaryGroupValuesColumn::<$T>::new(
inner, &new_field,
))
};
}
let col: Box<dyn GroupColumn> = match key_dt.as_ref() {
DataType::Int8 => dict_col!(Int8Type),
DataType::Int16 => dict_col!(Int16Type),
DataType::Int32 => dict_col!(Int32Type),
DataType::Int64 => dict_col!(Int64Type),
DataType::UInt8 => dict_col!(UInt8Type),
DataType::UInt16 => dict_col!(UInt16Type),
DataType::UInt32 => dict_col!(UInt32Type),
DataType::UInt64 => dict_col!(UInt64Type),
_ => {
return not_impl_err!(
"Dictionary key type {key_dt} not supported in GroupValuesColumn"
);
}
};
Some(col)
}The inner is a normal GroupColumn for the value type — the dictionary
column delegates storage of the actual values to the ordinary builder and
only adds index bookkeeping on top. Clean layering: the dictionary is an
index optimization, not a different storage model.
The catch: the row format throws dictionaries away
Arrow’s RowConverter hydrates dictionaries to their plain value type.
So the row-format GROUP BY fallback (GroupValuesRows) cannot use the
dictionary at all, and must re-encode the output to put it back:
// datafusion/physical-plan/src/aggregates/group_values/row.rs:319-334
/// Re-apply dictionary / run-end encoding to `array` so it matches `expected`.
///
/// Arrow's [`RowConverter`] flattens dictionary and run-end-encoded values to
/// their plain value type during row encoding (at [`RowConverter::append`]),
/// so any group-value array produced from the row format is in that plain
/// type and must be re-encoded to match the schema's expected type before
/// being returned. Shared with the generic row-backed `GroupColumn`.
pub(crate) fn encode_array_if_necessary(
array: &ArrayRef,
expected: &DataType,
) -> Result<ArrayRef> {
match (expected, array.data_type()) {
...
(DataType::Dictionary(_, _), _) => Ok(cast(array.as_ref(), expected)?),The single-line cast re-creates the dictionary from scratch, a full pass
over the group values. Not free — but paid once per group on the output
path, not per row.
Dictionary awareness is spreading
The same “operate on the values, then scatter to the keys” pattern shows
up across the expression layer. IN lists with dictionary needles
evaluate the filter once on the dictionary values and then take the
result by the keys:
// datafusion/physical-expr/src/expressions/in_list/dictionary_filter.rs:41-48
fn contains(&self, needles: &dyn Array, negated: bool) -> Result<BooleanArray> {
let Some(dictionary) = needles.as_any_dictionary_opt() else {
return self.inner.contains(needles, negated);
};
let values_contains = self.contains(dictionary.values().as_ref(), negated)?;
let result = take(&values_contains, dictionary.keys(), None)?;
Ok(result.as_boolean().clone())
}Case conversion transforms only the values and reuses the keys
(datafusion/functions/src/string/common.rs:539-547). And the hash join
must cope with the logical null problem — a valid dictionary key
pointing at a null value is logically null:
// datafusion/physical-plan/src/joins/hash_join/exec.rs:3620-3622
let build_has_null = null_aware == Some(NullAwareMode::RightAnti)
&& !left_values.is_empty()
&& left_values[0].logical_null_count() > 0;Failure modes and trade-offs
The dictionary is per-batch. Two batches can have completely different dictionaries, so the index is not a stable group identity. Any code that treats “same index” as “same value” across batches is wrong.
value_dedupis exactly the mechanism that prevents this bug, and it is the part you must not remove.Key type overflow.
Int8keys address 127 values. Exceed that and you get an error, not a wrong answer — but it is an error, andcheck_key_overflowruns after every append.The dictionary can be bigger than the data. A column with 10 million rows and 9 million distinct values has a nearly-as-large dictionary, and the memo tables cost 8 and 8 bytes per dictionary entry. The
rhs_rows.len() < dict_values.len()heuristic guards the comparison path, but the memo arrays are still allocated atDsize.Dictionary + row format is a losing combination. The row format hydrates the dictionary, so you pay for the dictionary and the row bytes, then re-encode on output.
enable_rle_to_dictionaryis off by default. That is a deliberate trade: promoting the column changes the user-visible schema (the column’s type becomesDictionary<Int32, Utf8>), which can break downstream code expectingUtf8. It also only works when DataFusion infers the schema.Promotion is per-file-set, not per-file. A column is promoted if any row group in any file has a dictionary page, and then
uniform_dict_schemasmakes all files agree. Files without a dictionary get their values expanded and re-interned — wasted work, but it keeps the schema consistent.
The takeaway
A dictionary column is a hash table the file format built for you. DataFusion’s job is not to throw it away, and the way it does that is by splitting the problem in two:
- Within a batch, the dictionary index is a memo key:
val_to_innerturns “which group does this row belong to?” into a single array read for every row whose index was seen before. Only positive results are memoized, so the cache can never go stale. - Across batches, the value is the grouping key, bridged by
value_dedup, a hashbrown table keyed on the value’s hash with an equality check for collisions.
The hashing side gets the same treatment: hash_dictionary hashes the D
distinct values once and scatters the results to the N row positions,
with eight const-generic monomorphizations keeping the hot loop
branch-free. Grouping a dictionary column costs O(D) string work per
batch rather than O(N), and the only thing DataFusion adds is the
bookkeeping to make the index and the value agree. It is a clean example
of the general principle: when the input format has already done
expensive work, build your data structures so that work is not repeated.