Faster multi column sort.

[ghuls]

Problem description

Faster multi column sorting by sorting encoded forms of each column.
https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-2/

https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-1/

apache/arrow-rs#2929

[ritchie46]

Yeah, I read the duckdb post a while ago already. I think we first need to do some comparisons. How are we doing against duckdb and arrow on this?

[ghuls]

Not sure how fast we are compared with duckdb and arrow-rs, but it seems that compared with their old implementation, they get a big speedup.

Using this format for lexicographic sorting is more than 3x faster than the comparator based approach, with the benefits especially pronounced for strings, dictionaries and sorts with large numbers of columns.

We have also already used it to more than double the performance of sort preserving merge in the DataFusion project, and expect similar or greater performance uplift as we apply it to sort, grouping, join, and window function operators as well.

[ritchie46]

I think we still first need to check before we can conclude that ours would speed up from this. We have a different sort implementation.

[ritchie46]

We have proper row encoding now.