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 DictionaryArray is not a compressed column — it is a pre-built hash cache that the file format already paid for. DataFusion exploits that: it hashes the D distinct dictionary values once, scatters the D hashes out to the N row positions, and memoizes a value index → group slot map, so a row whose key repeats a dictionary index costs one array lookup instead of a string comparison. GROUP BY on a dictionary column does O(D) hashing work per batch, not O(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:

text
DictionaryArray<Int32, Utf8>

   keys:    [ 0, 1, 0, 1, 2, 0, ... ]     <- one Int32 per row
   values:  [ "US", "DE", "FR" ]          <- the distinct values, once

The 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.

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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:

  1. 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_inner fill-only, so it can never go stale.
  2. 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.
  3. 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:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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 = false

The promotion happens at schema-inference time, by inspecting the Parquet footer for dictionary pages:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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:

rust
// 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_dedup is exactly the mechanism that prevents this bug, and it is the part you must not remove.

  • Key type overflow. Int8 keys address 127 values. Exceed that and you get an error, not a wrong answer — but it is an error, and check_key_overflow runs 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 at D size.

  • 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_dictionary is off by default. That is a deliberate trade: promoting the column changes the user-visible schema (the column’s type becomes Dictionary<Int32, Utf8>), which can break downstream code expecting Utf8. 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_schemas makes 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_inner turns “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.

DatafusionArrowPerformanceInternals