Repository navigation
Sort performance - #9407
Closed
cetra3 wants to merge 1 commit into
Closed
Sort performance#9407cetra3 wants to merge 1 commit into
cetra3 wants to merge 1 commit into
Conversation
cetra3
commented
Feb 13, 2026
| let mut cur_idx = 0u32; | ||
|
|
||
| // 2) Write null indices by inverting | ||
| let inv_buf = !bitmap.inner(); |
Contributor
Author
There was a problem hiding this comment.
I think this is where most of the saving comes in. Recreating the bitmap with inverse is another pass over it, so we have to read it twice.
Contributor
There was a problem hiding this comment.
Interesting, I think this was changed in the other direction in 625e6ee#diff-2c3ee46148ccba8c1092294caab66ba73416314595ce2eef9b2bdd9cd898b27d
I wonder what changed now that makes the benchmarks go the other way.
cetra3
force-pushed
the
sort_performance
branch
from
February 13, 2026 07:50
32667d6 to
8657ae6
Compare
Contributor
|
run benchmark sort_kernel |
|
🤖 Hi @Dandandan, thanks for the request (#9407 (comment)).
Please choose one or more of these with You can also set environment variables on subsequent lines: Unsupported benchmarks: sort_kernels. |
|
🤖 |
|
🤖: Benchmark completed Details
|
Contributor
|
run benchmark sort_kernel |
Contributor
|
Seems like there are some benchmarks that show slowdowns: |
|
🤖 Arrow criterion benchmark running (GKE) | trigger |
|
🤖 Arrow criterion benchmark completed (GKE) | trigger Details
Resource Usagebase (merge-base)
branch
|
|
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days. |
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?
N/A
Rationale for this change
There are a few small wins we can get adjusting how sort works by avoiding some copies in memory & eliminates some unsafe code around the partition scan. I tried a few attempts at bringing down the numbers of the partition scan even more by chunking the bitmaps, but this "simpler" implementation looks like it compiles/branches pretty well
I also optimised the
sort_native_typeto avoid some double copies and bounds checks, which gets us a nice +17% speedup in some of the primitive benchmarks including null values (i.e,sort i32 nulls 2^12).Admittedly after changing this code it doesn't even look like DataFusion uses that path... it only uses
lexsort_to_indices.One other extension I thought of was for smaller arrays, whether it makes sense to delegate to the
sort_native_typeand then slice it, rather than do the indices rigmaroleWhat changes are included in this PR?
Adjustments to two inner functions:
sort_native_typepartition_validity_scanAre these changes tested?
Yes via:
& benched with
mainvia:Are there any user-facing changes?
Nope
Benchmark Results against
mainHere's a comparison against
mainon my PC.It would be interesting to run this via the standard benchmark and see if we have the same improvements there: