Improve multi-column sorting for primitive arrays by avoiding multi-column sort
- 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.**
When sorting multiple columns, like two u32 columns, we take the approach of creating a `LexicalComparator`, and sort by that.
However, this has higher overhead compared to sorting by a single primitive.
**Describe the solution you'd like**
We can try combining arrays (pack) into one or a smaller number of primitive arrays.
We can pack the items (based on sorting options) to the next biggest type:
(u16, u16) -> `u32`
(u16, f32) -> `u64`
(u8, u32) -> `u64`
(u32, u32) -> `u64`
(u64, u32) -> `u128`
(u64, u64) -> `u128`
...etc.
and sort on that. This is similar to the `RowFormat`, but should have much lower overhead of creating the arrays and sorting is faster on primitives compared to variable-sized data.
Even when the columns can't be packed into one column, sorting can still be faster as it will create fewer columns to sort on.
I believe we can also extend this idea a bit further for larger types and more columns by converting the inputs into a fixed number of `u64` tuples / fixed array sizes, so the compiler can optimize that. E.g. for a 4 column sort on i64 types we can convert it to `Vec<[u64; 4]>` and sort based on this.
**Describe alternatives you've considered**
**Additional context**
Contributor guide
Research direction
Start by locating the multi-column sorting path and its LexicalComparator usage in the Rust codebase. Compare the existing RowFormat approach with primitive-array sorting, then define and test when packed values or fixed-size tuples preserve the requested sorting options without the multi-column comparator overhead.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100