Repository navigation
perf: optimizing take_n for DictionaryGroupValuesColumn - #24476
Draft
saadtajwar wants to merge 5 commits into
Draft
saadtajwar wants to merge 5 commits into
saadtajwar wants to merge 5 commits into
Conversation
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #24476 +/- ##
=======================================
Coverage 81.45% 81.45%
=======================================
Files 1119 1119
Lines 400421 400491 +70
Branches 400421 400491 +70
=======================================
+ Hits 326159 326218 +59
- Misses 55184 55192 +8
- Partials 19078 19081 +3 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
saadtajwar
marked this pull request as ready for review
August 20, 2026 15:40
Contributor
Author
|
@Rich-T-kid & @kumarUjjawal - ready for review! Thanks in advance for your feedback! |
saadtajwar
changed the title
Contributor
|
run benchmark dictionary_group_values |
|
🤖 Benchmark running (GKE) | trigger CPU Details (lscpu)Comparing saadtajwar/DictionaryGroupValuesColumn-take-n-optimization (901e301) to dbdc627 (merge-base) diff Run configurationrun benchmark dictionary_group_valuesResults will be posted here when complete File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Instance: Comparing saadtajwar/DictionaryGroupValuesColumn-take-n-optimization (901e301) to dbdc627 (merge-base) diff Run configurationrun benchmark dictionary_group_valuesCPU Details (lscpu)Details
Resource Usagedictionary_group_values — base (merge-base)
dictionary_group_values — branch
File an issue against this benchmark runner |
Contributor
|
Contributor
Author
Oof, if I'm reading this correctly this doesn't look like a huge win for us here...any thoughts on how we want move forward here? I feel like we could either:
My preference would be the last option, but I'm obviously biased in wanting to see these changes move the needle 😆 open to any feedback! |
Contributor
|
the current |
kumarUjjawal
left a comment
kumarUjjawal
left a comment
Contributor
There was a problem hiding this comment.
Thank you @saadtajwar for working on this. I have left few comments for you.
Also could you add some tests for these code changes.
Contributor
Author
Thanks @kumarUjjawal ! Will take a look through these and make changes to address over the next week! |
Keep both slot_hash (take_n) and cached_values (append_val hash reuse).
Contributor
Author
|
run benchmark dictionary_group_values |
|
Hi @saadtajwar, thanks for the request (#24476 (comment)). Only whitelisted users can trigger benchmarks. Allowed users: 2010YOUY01, Dandandan, Fokko, Jefffrey, Omega359, Rachelint, Rich-T-kid, adriangb, alamb, asubiotto, avantgardnerio, brunal, buraksenn, cetra3, codephage2020, coderfender, comphead, erenavsarogullari, etseidl, friendlymatthew, gabotechs, geoffreyclaude, grtlr, haohuaijin, jonathanc-n, kevinjqliu, klion26, kosiew, kumarUjjawal, kunalsinghdadhwal, liamzwbao, mbutrovich, mkleen, mzabaluev, neilconway, rluvaton, sdf-jkl, timsaucer, xudong963, zhuqi-lucas. File an issue against this benchmark runner |
Contributor
Author
|
@kumarUjjawal thanks for the review as always! Pushed a commit to address your changes - please let me know your thoughts - curious to see if this made any improvements wrt the benchmark 👀 |
Contributor
|
run benchmark dictionary_group_values |
|
🤖 Benchmark running (GKE) | trigger CPU Details (lscpu)Comparing saadtajwar/DictionaryGroupValuesColumn-take-n-optimization (57131f2) to d1fe988 (merge-base) diff Run configurationrun benchmark dictionary_group_valuesResults will be posted here when complete File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Instance: Comparing saadtajwar/DictionaryGroupValuesColumn-take-n-optimization (57131f2) to d1fe988 (merge-base) diff Run configurationrun benchmark dictionary_group_valuesCPU Details (lscpu)Details
Resource Usagedictionary_group_values — base (merge-base)
dictionary_group_values — branch
File an issue against this benchmark runner |
| } | ||
|
|
||
| #[test] | ||
| fn take_n_utf8_view_emits_and_interns_leftover_values() { |
Contributor
There was a problem hiding this comment.
This test passes when you delete the gc_array call. It asserts on values and on equality, and gc() changes only the buffer layout, not the data. The three strings also hold about 60 bytes of
non-inline data. should_gc_view_array needs more than 10 KB, so the compaction never runs here. Could the test build enough non-inline data to pass that limit, then assert on
get_buffer_memory_size() of the emitted array?
| let compact_emit_values = | ||
| take(&*all_inner_values, &emit_indices, None).expect("take emit values"); | ||
| // take() keeps original view buffers while spill's gc_array copies only when worth it | ||
| let gced_compact_emit_values = gc_array(&compact_emit_values) |
Contributor
There was a problem hiding this comment.
Would it work to add a case with Utf8View values longer than twelve bytes, and enough of them to pass the 10 KB limit?
| let leftover_non_null_len = new_to_old.len() - null_old_slot.is_some() as usize; | ||
| let old_hashes = std::mem::take(&mut self.slot_hash); | ||
| // Remapping entries from current slot | ||
| self.value_dedup.retain(|(_, slot)| { |
Contributor
There was a problem hiding this comment.
would a shrink_to_fit help here, with the accounting corrected to match?
Contributor
|
@saadtajwar are you still working on this? no rush just checking |
Contributor
Author
Hey @Rich-T-kid , apologies for the super delayed response - unfortunately I've had to take a step back from contributing recently. If anyone else is wanting to work on this/take it to the finish line please feel free to! Hopefully I can get back to DF contributing in the future :) |
|
Marked as draft after 14 days without activity: merge conflicts. Please address these items and mark Ready for review when ready. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
Rationale for this change (copied from issue)
DictionaryGroupValuesColumn::take_n emits the first n groups and rebuilds the remainder in-place. Every call hashes all surviving distinct values from scratch to reconstruct value_dedup, making repeated partial emissions O(G² / batch_size) over the lifetime of a query, where G is the total number of distinct values seen. Additionally, arrow::compute::take does not compact the backing storage for Utf8View, BinaryView, or nested dictionary value arrays; the rebuilt column retains a reference to the full original allocation rather than releasing memory proportional to the dropped groups. Under a high-cardinality dictionary key with frequent spill-driven partial emissions (e.g. streaming aggregation with a large fan-out), this combination causes both CPU and peak RSS to grow super-linearly with group count.
What changes are included in this PR?
value_dedupto only remove/move relevant slots instead of complete rebuildinnerfor the remainder loopAre these changes tested?
Yes
Are there any user-facing changes?
No