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]

Reply via email to