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

Reporter: Antoine Pitrou / @pitrou
Assignee: Antoine Pitrou / @pitrou

Related issues:

• [C++] Improve select_k_unstable performance (is related to)
• [C++] Investigate Table sort performance (is related to)

PRs and other links:

• GitHub Pull Request #11273

_{Note: This issue was originally created as ARROW-14165. Please see the migration documentation for further details.}