lakshaydevoo-arch opened a new pull request, #27590:
URL: https://github.com/apache/datafusion/pull/27590
## Which issue does this PR close?
- Closes #26862.
## Rationale for this change
`df.sort(a DESC).select(a, a + 1)` can return rows out of order when
`target_partitions > 1`. The same happens when the projection drops the sort
key (`select(a + 1 AS c)`), with a `.limit()` after the select, and for
hand-built plans with a `FilterExec` over a sort.
The physical plan for the first case is:
```
ProjectionExec: expr=[a@0 as a, a@0 + 1 as a_plus_one]
RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1,
maintains_sort_order=true
SortExec: expr=[a@0 DESC NULLS LAST], preserve_partitioning=[false]
```
`OutputRequirements` attaches the global ordering requirement to the
`SortExec` itself, below the projection. `EnsureRequirements` then adds an
optional round-robin under the projection to parallelize it. Nothing above the
repartition requires the order, so no merge is added and the output has 4
partitions.
## What changes are included in this PR?
The fix has two parts, both in `datafusion-physical-optimizer`.
1. **`OutputRequirements` (add mode)**: when the requirement is placed below
the root, it is now moved to the root if the sort keys can be expressed in the
root's schema. Projections are mapped with `update_ordering_requirement`. Other
operators are crossed only if their columns keep the same names and types. The
requirement at the sort stays, but without the `SinglePartition` distribution.
`EnsureRequirements` can then still parallelize the projection or filter and
adds a `SortPreservingMergeExec` at the root:
```
SortPreservingMergeExec: [a@0 DESC NULLS LAST]
ProjectionExec: expr=[a@0 as a, a@0 + 1 as a_plus_one]
RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1,
maintains_sort_order=true
SortExec: expr=[a@0 DESC NULLS LAST], preserve_partitioning=[false]
```
The requirement is not moved if a sort expression is volatile, because
the merge would evaluate it again.
2. **`EnsureRequirements`**: if the requirement could not be moved, either
because a projection drops a sort key or because the key is volatile, the
optional round-robin is no longer added between the requirement and the
operators above it. In that case the operators above the sort run in its single
partition. Required repartitioning is unchanged.
An earlier version of this fix only did part 2 for all cases. It changed the
expected plan of `parallelization_limit_with_filter` and ran every computed
projection over a sort on one thread. With part 1, that test is unchanged and
projections that keep the sort key stay parallel.
## What is the testing strategy for this PR?
New tests in `core/tests/physical_optimizer/output_requirements.rs` run the
full default physical optimizer, execute the plan, and check both the rows and
the plan structure. They cover:
- a projection that keeps the sort key, which must still run on several
partitions;
- a projection that drops the sort key;
- LIMIT/OFFSET above and below the projection;
- a filter, and a limit over a filter;
- a multi-key sort, keeping both keys and dropping the second;
- a volatile sort key under a projection and under a filter;
- an unordered projection, which must still get a round-robin.
Every test also checks the following:
- the schema is unchanged;
- `check_plan_tree_sanity` passes;
- re-optimizing the plan keeps the output's partition count and ordering
until the plan stops changing.
Without the production change, 9 of the 14 tests in the file fail. Eight
check row order or parallelism; the ninth is the `OutputRequirements` add-mode
snapshot, updated to show the requirement at the root. The unordered-projection
test passes both with and without the change.
## Are there any user-facing changes?
There are no public API changes. Plans change only where an ordered result
previously lost its order.
Two changes need a reviewer's opinion:
1. **SQL plans in `order.slt`.** `SELECT a + b AS sum1 FROM (SELECT a, b
FROM ordered_table ORDER BY a LIMIT 1)` no longer has a round-robin above
`TopK(fetch=1)`, because the projection drops the sort key. Both blocks now
expect the same plan, so they no longer cover
`use_row_number_estimates_to_optimize_partitioning`. If that coverage matters,
it may be better to change the query, for example to keep `a`, than to change
the expected plan.
2. **The intended contract.** This PR assumes the order requested by
`DataFrame::sort` should hold through a later `select`, and the same for a
sorted SQL subquery with `LIMIT`. SQL does not require this, and the
`DataFrame::sort` docs make no promise either. If the project decides this is
not guaranteed, this PR should be closed.
## Open questions for review
- **The key-dropped case is single-threaded.** In a local micro-benchmark
with an expensive projection, it was about 60% slower than the current,
unordered result. Keeping it parallel would need the optimizer to compute the
projection with the sort key carried internally, merge on it, and then drop it.
That is a larger rewrite, so I left it out. I would like to know whether it is
worth doing here or as a follow-up.
- **Re-optimizing a key-kept plan simplifies it once more.** It becomes a
merge over a parallel sort above the projection, and then stops changing.
Limit-over-sort plans already behave this way on `main`, but please say if this
is a concern for adaptive re-planning.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]