Inf1mum opened a new pull request, #27587:
URL: https://github.com/apache/datafusion/pull/27587

   ## Problem
   
   `ORDER BY seq LIMIT 3 OFFSET 2` followed by a projection that computes 
something (a `CAST` or `concat`) can return its rows out of order when 
`target_partitions > 1` (#27550). The physical plan ends with a round-robin 
repartition above the ordered limit:
   
   ```
   ProjectionExec: expr=[seq@0 as seq, CAST(label@1 AS Utf8) as label]
     RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, 
maintains_sort_order=true
       GlobalLimitExec: skip=2, fetch=3
         DataSourceExec: ..., limit=5, output_ordering=[seq@0 ASC]
   ```
   
   `maintains_sort_order` holds only within each output partition: the round 
robin splits the single ordered partition into several, each of which is 
sorted, and nothing above merges them back. The plan root then has several 
partitions whose concatenation is not globally ordered, and `execute_stream` 
(used by `DataFrame::collect`) concatenates partitions without re-establishing 
any ordering, so the query result was not in `ORDER BY` order. With a plain 
column projection the repartition is not inserted (`ProjectionExec` reports it 
does not benefit from input partitioning), which is why only computed 
projections were affected.
   
   ## Root cause
   
   `EnsureRequirements` adds the round-robin repartition for parallelism (the 
`UnspecifiedDistribution` child branch of `ensure_distribution`) because a 
computed projection benefits from input partitioning. That is legal for 
per-partition ordering semantics - `required_input_ordering` asks for ordering 
*within each partition*, and operators above the ordering anchor are allowed to 
keep several ordered partitions (for example under `prefer_existing_sort`, see 
`repartition_does_not_destroy_sort`). What was missing is enforcement of the 
*global* ordering at the plan root: the query's ordering requirement is tracked 
by `OutputRequirementExec` at the operator that establishes it, and nothing 
checked that the plan root actually delivers it in one piece.
   
   ## Fix
   
   At the end of `EnsureRequirements`, I detect the broken state and restore 
the global ordering:
   
   - find the query's global ordering requirement (an `OutputRequirementExec` 
carrying a non-empty ordering, added by the `OutputRequirements` add-mode rule),
   - if the optimized plan root claims an output ordering but has more than one 
output partition, merge the ordered partitions with a `SortPreservingMergeExec`.
   
   Plans whose global ordering requirement also demands a partitioned output 
(`KeyPartitioned`) - stage fragments of distributed engines, see 
`test_keep_sort_above_repartitioned_partial_aggregate` - are left untouched, as 
are queries without a global ordering requirement and plans whose root already 
has a single partition. The round-robin repartition is kept, so the projection 
still runs in parallel.
   
   After the fix the plan from above becomes:
   
   ```
   SortPreservingMergeExec: [seq@0 ASC]
     ProjectionExec: expr=[seq@0 as seq, CAST(label@1 AS Utf8) as label]
       RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, 
maintains_sort_order=true
         GlobalLimitExec: skip=2, fetch=3
           DataSourceExec: ..., limit=5, output_ordering=[seq@0 ASC]
   ```
   
   ## Testing
   
   - `ordered_limit_with_computed_projection_keeps_global_order`: runs the full 
default physical optimizer on `ProjectionExec(computed) <- GlobalLimitExec <- 
SortExec <- ordered scan with unknown statistics` (the parquet listing-table 
shape, where unknown statistics let the repartition pass its benefit gate) and 
asserts the root has one partition, a merge is present, and the collected rows 
are in `seq` order. It fails on main (root has 4 partitions, rows out of order).
   - `ordered_limit_with_plain_projection_keeps_global_order`: the 
plain-column-projection shape keeps working.
   - `ordered_aggregate_key_types.slt`: the documented plan gains the root 
merge - the fixture reads from a view with `ORDER BY ... LIMIT 1000`, so the 
plan now actually delivers the ordering it claims; the per-partition ordering 
assertions of the fixture (`maintains_sort_order` on the hash repartition) are 
unchanged.
   - The issue's standalone reproducer (parquet listing table, 
`pushdown_filters`, 40 runs): 16/40 runs out of order on main, 0/40 after the 
fix (`cast`, `concat`, `plain`, `target_partitions` 1/4/8).
   
   Crate and integration tests: `cargo test -p datafusion-physical-optimizer`, 
`cargo test -p datafusion --test core_integration` (1524 passed, includes the 
`physical_optimizer` suite), and the full `cargo test --test sqllogictests`.
   
   Refs #27550.
   
   Signed-off-by: Inf1mum <[email protected]>


-- 
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