perf: gc dictionaries in interleave_fallback_dictionary
- Dominant language
- Rust
- Stars
- 3.6k
- Forks
- 1.3k
- Avg merge
- 2d 16h
- Merged PRs (30d)
- 168
Description
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
`interleave_dictionaries` checks whether input dictionaries should be merged/GCed, but `should_merge_dictionary_values` has limited type support because of the byte keyed interner. For other value types, and in the general fallback case where the heuristic returns false, `interleave_fallback_dictionary` concatenates all the source `values` slices, leaving lots of bloat when the interleave selection is small relative to total values. This is common in DataFusion multi-partition sorts on dictionary columns: I observed a real world sort where the output `dict.values` was 99%+ unreferenced.
**Describe the solution you'd like**
In `interleave_fallback_dictionary`, gate on a cheap heuristic, `indices.len() < sum(all_values.len()). When it triggers, `take` only the referenced positions per Arc distinct group before concatenating. Output is logically equivalent; `values.len()` shrinks to the count of distinct referenced positions. No public API changes.
On the motivating workload this dropped runtime from ~20 minutes to ~7 minutes.
**Describe alternatives you've considered**
* Letting downstream `compact_dict`/`gc` strip the bloat after the fact. The problem is that the concat cost dominates, so this is still expensive.
* Always projecting: caused 80%+ regressions on existing `interleave_kernels.rs` dict microbenchmarks where every position is genuinely referenced.
**Additional context**
I will open a PR
Contributor guide
Research direction
Search for interleave_fallback_dictionary and read the surrounding dictionary interleave logic in interleave_kernels.rs, including the existing microbenchmarks. Run the relevant tests and dictionary benchmarks first; done means sparse references avoid concatenating unreferenced values while output remains logically equivalent and the existing dense-case benchmarks do not regress.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering, performance
- Issue type
- Refactor
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 68/100