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]