Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Unify Sorting Implementations #5879

Closed
tustvold opened this issue Apr 5, 2023 · 0 comments · Fixed by #6163
Closed

Unify Sorting Implementations #5879

tustvold opened this issue Apr 5, 2023 · 0 comments · Fixed by #6163
Assignees
@tustvold
Labels
enhancement New feature or request

Comments

@tustvold
Copy link
Contributor

tustvold commented Apr 5, 2023

Is your feature request related to a problem or challenge?

Currently there is separate logic to handle in-memory sorts, spilling sorts, and merging sorts, spread across ExternalSorter, SortPreservingMergeStream. This logic is incredibly hard to follow, and maintain, and there is a high likelihood of inconsistency between the implementations.

Additionally, the in-memory sort implementation currently relies on concatenating batches, which for dictionaries is extremely memory inefficient, as it will concatenate the underlying dictionary values.

Describe the solution you'd like

I would like in-memory sort to proceed by first sorting the batches, and then performing a sort preserving merge

Describe alternatives you've considered

No response

Additional context

This would help with #5230
@tustvold tustvold added the enhancement New feature or request label Apr 5, 2023
@tustvold tustvold self-assigned this Apr 5, 2023
This was referenced Apr 5, 2023
Closed
Merged
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 5, 2023
@tustvold
Generify SortPreservingMerge (apache#5882) (apache#5879)
f0b971c
@tustvold tustvold mentioned this issue Apr 5, 2023
Closed
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 5, 2023
@tustvold
Generify SortPreservingMerge (apache#5882) (apache#5879)
99ca36f
This was referenced Apr 5, 2023
Merged
Merged
tustvold added a commit that referenced this issue Apr 7, 2023
@tustvold
Generify SortPreservingMerge (#5882) (#5879) (#5886)
e41711b 
* Generify SortPreservingMerge (#5882) (#5879)

* Review feedback
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
20f638f
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
f3eb335
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
85f57e9
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
aec4337
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
7943f28
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
7de43e5
@tustvold tustvold mentioned this issue Apr 29, 2023
Merged
tustvold added a commit to tustvold/arrow-datafusion that referenced this issue Apr 29, 2023
@tustvold
Adaptive in-memory sort (apache#5879)
3567b5c
tustvold added a commit that referenced this issue May 2, 2023
@tustvold
Adaptive in-memory sort (~2x faster) (#5879) (#6163)
9a0ab5f 
* Adaptive in-memory sort (#5879)

* Clippy

* Fix test

* Clippy

* Update test_source_sorted_builtin
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@tustvold tustvold

Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
1 participant
@tustvold