[ARROW-14165] [C++] Improve table sort performance #2

• Type: Task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 6.0.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/29752
• Assignee: Antoine Pitrou
• Reporter: Antoine Pitrou
• Created: 29/Sep/21 07:40
• Updated: 11/Jan/23 08:38
• Resolved: 30/Sep/21 12:17

Description

After ARROW-10898 is solved, it seems some performance may still be left on the table when merging sorted record batches. Two possible directions:

• save on chunked indexing by relying on record batches and directly accessing subsequent columns in MultipleKeyComparator
• use left-to-right "radix" merging

Issue Links

• is related to: ARROW-14183 [C++] Improve select_k_unstable performance
• is related to: ARROW-10898 [C++] Investigate Table sort performance
• links to: GitHub Pull Request #11273