[C++] Introducing Row format for faster sort?

[power1628]

Describe the enhancement requested

In arrow-rs, there is a row representation of a table. And converting to row format will bring 3x performance benefits on sorting. Is there any plan to apply this optimization to arrow-cpp?

[1] https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-1/
[2] apache/arrow-rs#2929

Component(s)

C++

[mapleFU]

Personally I'm +1 with this, DuckDB also introduce Join using Row: https://duckdb.org/2021/08/27/external-sorting.html

@westonpace Would you mind take a look?

[power1628]

Seems arrow already has a row representation [1] , close this issue for now.

[1]https://github.com/apache/arrow/blob/1951a1ae69590ad58d97f6be929fa14485f81f42/cpp/src/arrow/compute/row/row_internal.h

[westonpace]

Yes, row_internal.h contains a row representation that can be used if needed. It is what is in use in the hash join. However, it is not used by any sort algorithm. It's not clear the cost would be worth it for an in-memory sort and we do not have an external/spilling sort.