The SortPreservingMergeExec seems still rather "nonoptimal" as the batches themselves are already sorted (but the info is thrown away by RepartitionExec). Any plans for addressing this as well in the future?

Yes, if I'm not mistaken one of the WIP PRs in our pipeline will address this 🙂

RepartitionExec does not break the order of partitions in this case as it partitions 1 to 4. Because these partitions are already ordered, the presence of SortPreservingMerge is correct. For general cases, SortPreservingRepartitionExec implementation is on the way, which will have the capability to preserve order for all kinds of partitioning.

What I essentially mean is this:

The batches of the table multiple_ordered_table are ordered and order is preserved in RepartitionExec and ProjectionExec. If SortPreservingMergeExec would know the number of the batch (batch 0, batch 1, batch 2, etc.) as they were returned from the table it would only need to wait on batch 0, batch 1, batch 2, etc. to appear from the partition streams, but not the rows itself, which would be much faster (i.e. not having to merge).

Is that something you plan as well?

To maintain batch indices for preserving order, it’s actually a good idea. The current sort preserving algorithm, designed to preserve the hash repartition, tends to overfit to the row sorting. We could potentially collaborate on implementing this optimization in future work.

I don't fully understand how this is different than output_ordering (which can also be a Vec of PhysicalSortExpr`). Would it makes sense to always normalize the output ordering in terms of the input's equivalence classes?

I thought the notion of multiple equivalent orderings was expressed using https://docs.rs/datafusion-physical-expr/28.0.0/datafusion_physical_expr/equivalence/type.OrderingEquivalentClass.html

Or maybe the key difference is this can track the ordering of each expression independently?

You are correct in your last sentence. We calculate the order information for each expression that is projected. Since we use this information when determining ordering equivalences, I thought it would be wise to keep it in the executor's state. I would appreciate it if you have any ideas on how to handle this more effectively.