Rich-T-kid opened a new issue, #26780:
URL: https://github.com/apache/datafusion/issues/26780
### Is your feature request related to a problem or challenge?
Part of #24111. Related to #26696 and #26703.
`hash_dictionary` avoids hashing the same value once per row: it hashes
every dictionary value into a temporary `Vec<u64>`, then scatters those hashes
through the keys. However, that temporary result is local to one
`create_hashes` call. The same dictionary values are therefore hashed again as
a batch moves through the plan.
A grouped query can currently do this:
```text
DictionaryArray(keys, values)
|
v
PartialAggregationExec
|-- GroupValues hashes the group columns
| `-- hashes `values`
`-- DictionaryGroupValuesColumn builds its value lookup
`-- hashes the same `values` again
|
v
RepartitionExec
`-- hashes `values` again for each input batch/slice
|
v
output coalescer
`-- when dictionaries need merging, scans/remaps values per piece
|
v
FinalAggregationExec
`-- repeats both aggregation hash paths
```
Joins have the same shape:
```text
Dictionary input
|
+-- RepartitionExec: partition hashes
|
`-- HashJoinExec: build/probe hashes
```
`take`, filtering, and repartitioning commonly rewrite the keys while
retaining the same dictionary values array. `DictionaryGroupValuesColumn`
already caches hashes by values-array identity within one group-values
instance, but that cache is not shared with the outer group-column hashing,
another aggregation stage, repartitioning, or joins.
This matters for #24111: choosing dictionary encoding based on cardinality
will not deliver its full benefit if each operator repeatedly pays O(dictionary
cardinality) work and allocation for the same values. The O(rows) scatter is
necessary; recomputing the O(dictionary values) hashes is not.
### Describe the solution you'd like
Separate dictionary hashing into two reusable operations:
```text
values + hash state -- once --> Arc<[value_hash]>
|
keys -----------------------------+--> row hashes
```
Add a bounded, memory-accounted cache for the value hashes, keyed by:
- dictionary values identity (without keeping otherwise-dead arrays alive)
- hash algorithm/state/seed
- any datatype or null semantics needed for correctness
Then let `RepartitionExec`, aggregation group values,
`DictionaryGroupValuesColumn`, and hash joins request the same cached value
hashes. Composite group keys can reuse the per-value hash and still combine it
with the other columns per row.
Hash state is an important constraint: repartitioning, aggregation, and
joins do not necessarily use the same seed today. We should either use a
compatible plan-scoped hash state for these paths or keep separate cache
entries per state. Hashes from different states must never be mixed.
When a dictionary is merged or remapped, preserve/remap compatible hashes
alongside its values where practical, or compute hashes only for newly
introduced values. This part may require an Arrow API; a first DataFusion
implementation can still cover operators that share the same values array.
The cache must be bounded and visible to memory accounting. Hashes remain
only an accelerator: hash-table equality checks must continue to resolve
collisions.
### How will we know this is complete?
- A shared dictionary values array is hashed once per compatible hash state,
rather than once per operator or aggregation hash path.
- Benchmarks cover `PartialAggregate -> Repartition -> FinalAggregate` and
partitioned hash joins, with low- and higher-cardinality dictionaries.
- Metrics or test instrumentation count dictionary values hashed, so the
optimization is verified directly rather than inferred only from wall time.
- Tests cover null keys/values, slices, multiple dictionary key types,
multiple group columns, hash collisions, and dictionary merge/remap boundaries.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
