[ARROW-18344] [C++] Use input pre-sortedness to create concatenated sorted table

• Type: New Feature
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: C++
• Labels: kernel
• External issue URL: https://github.com/apache/arrow/issues/33512

Language

C++

• Assignee: Unassigned
• Reporter: Rok Mihevc
• Created: 16/Nov/22 15:01
• Updated: 11/Jan/23 11:59

Description

In case of concatenating large sorted tables (e.g. sorted timeseries data) the resulting table is no longer sorted. However the input sortedness can be used to significantly speed up post concatenation sorting. A potential API could be to add ConcatenateTablesOptions.inputs_sorted and implement the logic in ConcatenateTables.