Rich-T-kid opened a new issue, #12056:
URL: https://github.com/apache/arrow-rs/issues/12056
### Is your feature request related to a problem or challenge?
`interleave` recognizes when its dictionary inputs share the same values
mapping, but currently routes that case through
`interleave_fallback_dictionary`. The fallback concatenates every values array
and offsets the selected keys, duplicating a mapping that could be reused.
For example, given two slices of the same dictionary:
```text
Dictionary A Dictionary B
keys: [0, 2] keys: [1, 0]
\ /
+---- shared values Arc V ----+
indices: [(A, 1), (B, 0)]
today:
values = concat(V, V)
keys = [2, len(V) + 1]
desired:
values = Arc::clone(V)
keys = [2, 1]
```
Both outputs are logically equivalent, but the current path copies the
values once per source and creates a larger dictionary. This is particularly
expensive for wide or sparsely referenced Utf8/Binary dictionaries.
The existing [`take` dictionary
path](https://github.com/apache/arrow-rs/blob/b231cf15efa5dbbbe4ae8503849aa6ab3cfc4e0c/arrow-select/src/take.rs#L1446-L1452)
already gathers the primitive keys and clones the existing values `Arc`.
This shape can reach Arrow from DataFusion. For example:
```sql
SELECT user_id, array_agg(event_type)
FROM events
GROUP BY user_id;
```
If multiple input batches are slices, filters, or takes of the same
dictionary-encoded `event_type` array, DataFusion's array accumulator stores
those arrays and later gathers rows with `interleave`:
```text
Batch 0: Dictionary(keys_0, Arc V) --+
Batch 1: Dictionary(keys_1, Arc V) --+--> array_agg group ordering -->
interleave
Batch 2: Dictionary(keys_2, Arc V) --+
```
Sort-preserving merge, partial sort, TopK, sort-merge join, and ASOF join
also use `interleave` to materialize rows from multiple batches.
### Describe the solution you'd like
Add a dictionary fast path that:
1. Considers only referenced sources with selected non-null keys.
2. Verifies that those sources share the same values mapping.
3. Gathers their primitive keys directly, preserving nulls.
4. Reuses the first values `Arc` in the output dictionary.
Inputs with distinct mappings should continue through the existing merge or
concatenation paths. Ignoring unreferenced and all-null sources is important
for callers that retain extra batches or prepend a null sentinel.
### Describe alternatives you've considered
The existing dictionary merge path could deduplicate the mappings, but it
does substantially more work than necessary when the mappings are already
identical. Implementing this in each downstream caller would also duplicate
logic that belongs in the Arrow kernel.
### Additional context
The existing [`interleave_kernels`
benchmarks](https://github.com/apache/arrow-rs/blob/b231cf15efa5dbbbe4ae8503849aa6ab3cfc4e0c/arrow/benches/interleave_kernels.rs#L34-L65)
already create shared-mapping inputs by slicing one base dictionary. The
`dict_distinct` cases provide a control for independently backed dictionaries.
--
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]
