apache / apache/datafusion

LimitPushdown and sort pushdown re-create limit nodes without `required_ordering`, losing order-sensitivity for later passes

Open
#24,215 1 comment 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.