Dictionary performance improvement tickets

[Rich-T-kid]

This is a collection of related dictionary optimizations

The goal of these optimizations is for dictionary-encoded paths to do work
that takes advantage of the dictionary structure itself, rather than
falling back to plain-array behavior. There are two related axes worth
optimizing for:

1. Operate in terms of O(values_array) (the K distinct values) instead
   of O(N) (the row count), and wherever possible use the integer keys
   as a proxy for comparison/equality/grouping work (the way
   FilterExec-style kernels already do), only touching the values array
   when a real value-level operation is unavoidable.
2. GroupValuesRows-style aggregation execs can cache the dictionary
   values Arc pointer across batches, since dictionary value arrays
   typically span multiple batches in practice (e.g. Parquet reads
   generally produce one values array per row group, reused across all
   batches sliced from it), so a cached ptr check can skip re-doing
   values-array work entirely on subsequent batches, not just avoid
   per-row value fetches within a batch.

optimizations

heres a list of operators that I (with the help of Claude) to have opportunity to be optimized for the dictionary path

SortExec

File : Line: sorts/sort.rs:965 970
What's currently wrong: Raw DictionaryArray to Arrow lexsort_to_indices. Sort kernel does a key to value lookup on every pairwise compare: N rows at cardinality K to ~2N value fetches
Optimized approach: Pre-sort K values, assign integer rank per key, sort an Int32Array of ranks. Zero value fetches during the sort pass; K log K one-time setup

• Done?

SortPreservingMerge

File : Line: sorts/streaming_merge.rs:263 278 (no Dict arm, RowCursorStream falls through at :278); sorts/stream.rs:155 (RowConverter::new); sorts/stream.rs:182 (converter.append)
What's currently wrong: No Dict cursor. RowConverter encodes all N rows with a key to value lookup plus full value byte copy each. N rows with K distinct values does N full encodes despite only K distinct encodings being possible
Optimized approach: Pre-encode the K element values array once; per batch scatter K pre-built encodings by key index. K encodes plus N integer ops instead of N encodes

• Done?

TopK

File : Line: topk/mod.rs:365 367 (TODO comment plus RowConverter::new); topk/partitioned_topk.rs (same)
What's currently wrong: Identical RowConverter N-encode issue as SortPreservingMerge. The TODO at line 365 literally says "potential to add special cases for single column sort fields"
Optimized approach: Same fix: pre-encode K values once, scatter via key index per batch

• Done?

SortMergeJoin

File : Line: joins/utils.rs:2489 (make_comparator on raw dict); joins/utils.rs:2631 (not_impl_err! crash)
What's currently wrong: Primary path: Arrow make_comparator on dict does a key to value lookup per compare. Fallback compare_join_arrays (lines 2552 2641) has no Dict arm, causing a runtime crash on any dict join key
Optimized approach: For equality: if values Arc ptr_eq, integer key compare, zero fetches. For less than/greater than: rank remap values; compare rank ints. Add Dict arm to compare_join_arrays to fix crash

• Done?

Hash Join equality

File : Line: joins/utils.rs:2321 (call site); joins/utils.rs:2369 (fn def); joins/utils.rs:2434 (_ => None fallthrough)
What's currently wrong: equal_rows_single_col covers bool/int/decimal/string/date but no Dict arm (comment at :2315 names "dictionaries" as excluded). Returns None, leading to a boxed DynComparator with a key to value lookup per pair
Optimized approach: Add Dict arm: ptr_eq on values Arc, integer key compare. Otherwise values[key_l] == values[key_r], at most one value lookup per pair

• Done?

NestedLoopJoin

File : Line: joins/nested_loop_join.rs:3434 (take left); :3437 (take right); :3445 3448 (filter.expression().evaluate)
What's currently wrong: Arrow take materializes N_left times N_right intermediate rows; filter evaluates via BinaryExpr, then an Arrow comparison kernel, then a key to value lookup for every candidate pair
Optimized approach: Pre-build bool[K_left][K_right] match table (K_left plus K_right hash ops). Inside loop: match_table[key_l][key_r] is one integer index, zero value fetches across all N_left times N_right pairs

• Done?

BinaryExpr = / !=

File : Line: physical-expr/binary.rs:662 674 (routes to apply_cmp); physical-expr-common/datum.rs:60 94 (not nested, Arrow eq/neq at :94)
What's currently wrong: Dict is not is_nested(), so the non-nested branch at datum.rs:65 calls the Arrow eq/neq kernel directly. Arrow does a key to value lookup per row, N byte compares even when K is much less than N
Optimized approach: If Arc::ptr_eq(lhs.values(), rhs.values()): equality is an integer key compare, N integer ops, zero value fetches. Otherwise cross-dict presence set (K_l plus K_r hash ops) plus N integer lookups

• Done?

BinaryExpr < / > / <= / >=

File : Line: physical-expr/binary.rs:662 674 to physical-expr-common/datum.rs:60 94 to Arrow lt/gt/lt_eq/gt_eq
What's currently wrong: Same path as = / !=. Arrow order kernels do a key to value lookup per row, N value byte compares per filter/sort pass
Optimized approach: Sort K values, rank[key] = sort_position, build an Int32Array of ranks (one per row), compare rank integers. K log K setup plus N integer compares, zero value fetches

• Done?

BinaryExpr arithmetic + scalar

File : Line: physical-expr/binary.rs:688 (call site); :1083 (fn def); :1099 (cast(&array, result_type)?)
What's currently wrong: to_result_type_array unpacks the entire dict to a plain array via cast() before arithmetic, N value copies even when K is much less than N
Optimized approach: Compute on the K element values array only; scatter result through key indices via Arrow take. K arithmetic ops plus N take ops vs N copies plus N arithmetic ops

• Done?

Agg SUM / AVG

File : Line: aggregates/grouped_hash_stream.rs:913 (evaluate_expressions_to_arrays); :966 (acc.update_batch with raw dict)
What's currently wrong: Raw DictionaryArray passed as is to update_batch. Accumulator iterates all N rows paying a key to value lookup each, N value fetches even when K_distinct is much less than N
Optimized approach: Count key occurrences (N integer bucket increments, zero value fetches); one value lookup per distinct key that appeared, K_distinct fetches total, not N

• Done?

Agg MIN / MAX

File : Line: aggregates/grouped_hash_stream.rs:913 plus :966
What's currently wrong: Same raw dict pass-through. Accumulator compares N values per batch even though the result only depends on the K_present values that actually appear (K_present <= K)
Optimized approach: Boolean presence mask (N integer ops); scan only values[k] where seen[k] is true, K_present value compares, not N

• Done?

Window PARTITION BY

File : Line: windows/bounded_window_agg_exec.rs:935 (get_row_at_idx, collision check); :937 (Vec equality); :945 (get_row_at_idx, new key insert)
What's currently wrong: get_row_at_idx allocates a Vec per row, cloning full value bytes for every hash collision check and every new partition key, an O(avg_value_bytes) clone plus compare per row
Optimized approach: For dict-encoded partition cols, compare integer keys directly for same-batch checks, an O(1) integer compare per row, zero byte clones

• Done?

Related issues

• Epic: Cost-Based Dictionary Encoding #24111
• Reuse the cached dictionary value→slot map in vectorized_equal_to instead of rebuilding it per batch #25219
• Dictionary-encoded group keys pay 27-37% aggregation tax vs Utf8View in TPC-H (Q2/Q19/Q20), DF 54 & 55 both #24822

Related discussions

• Add physical plan optimization to decide dictionary encoding #24117 (comment)

cc @lxc512157407 @yinli-systems

[Rich-T-kid]

with #24227 we should be able benchmark these improvements without needing to add several micro-benchmarks