apache / apache/arrow-rs

perf: gc dictionaries in interleave_fallback_dictionary

Open
#9,939 1 comment 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.