LimitPushdown and sort pushdown re-create limit nodes without `required_ordering`, losing order-sensitivity for later passes
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Describe the bug
`GlobalLimitExec`/`LocalLimitExec` carry a `required_ordering` field recording that the limit is order-sensitive (typically an `ORDER BY ... LIMIT` whose `SortExec` was optimized away). `LimitPushdown` consumes it when extracting a limit:
https://github.com/apache/datafusion/blob/fc846dd3681e3b6b7c8f9979aa54ee06c1d64f2c/datafusion/physical-optimizer/src/limit_pushdown.rs#L414-L431
and applies it via `with_preserve_order(...)` when an operator absorbs the fetch. However, `GlobalRequirements` only tracks `preserve_order: bool`, so when the rule **re-inserts** a limit node instead of absorbing it — `add_limit` / `add_global_limit`:
https://github.com/apache/datafusion/blob/fc846dd3681e3b6b7c8f9979aa54ee06c1d64f2c/datafusion/physical-optimizer/src/limit_pushdown.rs#L438-L459
the new node is built with plain `new(...)` and `required_ordering` is dropped (and could not be reconstructed from the bool anyway).
Within a single `LimitPushdown` run this is harmless because the flag travels in the rule's state. But the output plan has lost the only durable record that the limit is order-sensitive. Any *later* `LimitPushdown` run — a repeated optimizer pass, or a serialize/deserialize + re-optimize cycle as in distributed execution (the exact scenario from #24173, whose serde half is fixed by #24183) — extracts `preserve_order = false` and may push the limit into a scan that is then free to read files out of order, returning wrong rows for `ORDER BY ... LIMIT`.
The same pattern exists in `pushdown_sort.rs`: when a `SortExec` with a fetch is eliminated because the source guarantees `Exact` ordering, the fallback limits are created without `required_ordering` even though they are order-sensitive (the fetch must apply to the first N rows in the pushed-down order, e.g. per-partition first-N feeding a `SortPreservingMergeExec`):
https://github.com/apache/datafusion/blob/fc846dd3681e3b6b7c8f9979aa54ee06c1d64f2c/datafusion/physical-optimizer/src/pushdown_sort.rs#L111-L116
https://github.com/apache/datafusion/blob/fc846dd3681e3b6b7c8f9979aa54ee06c1d64f2c/datafusion/physical-optimizer/src/pushdown_sort.rs#L170-L177
### To Reproduce
Sketch (no end-to-end repro yet):
1. Build a plan where an order-sensitive limit (with `required_ordering` set) sits above an operator that `supports_limit_pushdown()` but where the fetch cannot be absorbed, so `LimitPushdown` removes the limit and re-adds one via `add_limit`.
2. Observe the re-added `GlobalLimitExec`/`LocalLimitExec` has `required_ordering() == None`.
3. Roundtrip the plan through proto (or just run `LimitPushdown` again after further rewrites) and let the limit reach a `DataSourceExec`: `FileScanConfig.preserve_order` is now `false`, so a multi-file scan may reorder files under the limit.
### Expected behavior
- `GlobalRequirements` should carry the actual `Option` rather than just `preserve_order: bool`, and `add_limit`/`add_global_limit` should re-attach it to the re-inserted node.
- The `pushdown_sort.rs` fallback limits should set `required_ordering` from the eliminated sort's expressions.
### Additional context
Noticed while reviewing #24183; it is orthogonal to that PR (those code paths are untouched there and the loss predates it).
Contributor guide
Research direction
Start in datafusion/physical-optimizer/src/limit_pushdown.rs, reading GlobalRequirements and the add_limit/add_global_limit paths, then inspect the fallback limit creation in pushdown_sort.rs. Trace how required_ordering is consumed and reattached, and verify that reinserted limits retain the eliminated ordering information across a repeated optimization or proto roundtrip. Done means both optimizer paths preserve order-sensitive limits instead of allowing an unordered file scan.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend, databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100