[C++] Add ordering information to exec batches

[asfimport]

I proposed this ages ago in https://lists.apache.org/thread/xpn9gyrs6kqc3g9t8k4ts8dmy7yyxskq and am finally getting around to implementing it.

I propose to add ordering information to exec nodes (mostly for node validation) and indices to exec batches. This is a fundamental step to allow nodes to consume this ordering information to achieve features such as ARROW-10883 and ARROW-16628. It also can replace the complicated batch enumeration in the current scanner to support in-order table reassembly.

Reporter: Weston Pace / @westonpace
Assignee: Weston Pace / @westonpace
Watchers: Rok Mihevc / @rok

Related issues:

• [C++][Dataset] Preserve order when writing dataset (is required by)

PRs and other links:

• GitHub Pull Request #14158

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

[westonpace]

I plan to start working on this task. However, it is quite large. I plan on breaking it up into the following tasks:

• [C++] Create a fetch node based on a batch index property #34059 Add batch index to ExecNode, Create a fetch node (this will serve as an example of how a batch index can work)
• [C++] Allow scanner to assert an ordering and/or support implicit ordering #34698 Add batch index to the scanner
• [C++] Add the concept of "ordering" to an exec node, reject non-sensible plans #34136 Add the concept of "ordering" to an exec node, reject non-sensible plans
• [C++] Add the concept of "ordering" to an exec node, reject non-sensible plans #34136 Update existing nodes to respect ordering and batch index (at this point "fetch" will be usable in larger plans)
• GH-32763: [C++] Add FromProto for fetch & sort #34651 Add bindings for fetch to substrait consumer
• GH-34248: [C++] Add an order_by node #34249 Add an order-by node which can modify an ordering
• Deprecate old DeclarationToXyz methods