apache / apache/datafusion

`LimitPushdown` can return incorrect rows for fetched `SortPreservingMergeExec` over ordered Parquet scans

Open
#24,272 0 comments 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

Queries using `ORDER BY ... LIMIT` can return incorrect rows when the physical plan contains a fetched `SortPreservingMergeExec` over an ordered Parquet scan.

For a plan shaped like:

```text
SortPreservingMergeExec: [key@0 ASC], fetch=5
DataSourceExec: output_ordering=[key@0 ASC]
```

`LimitPushdown` pushes the fetch into the scan but does not recognize that the fetch on `SortPreservingMergeExec` is order-sensitive. It consequently updates the scan with:

```text
limit=Some(5)
preserve_order=false
```

This overrides the scan's existing order-preservation requirement.

For Parquet scans, `preserve_order=false` enables limit-based row-group pruning. That optimization may discard an earlier partially matched row group in favor of a later fully matched row group, changing which rows are returned by the ordered limit.

### To Reproduce

Consider a Parquet file sorted by `key`, scanned into multiple ordered partitions and combined by the fetched `SortPreservingMergeExec` above:

| Row group | Values | Predicate classification |
|---|---|---|
| RG0 | `0..99` | Partially matches `key >= 1` |
| RG1 | `100..199` | Fully matches `key >= 1` |

Run:

```sql
SELECT key
FROM t
WHERE key >= 1
ORDER BY key ASC
LIMIT 5;
```

Expected result:

```text
1
2
3
4
5
```

The faulty plan can discard RG0 during limit-based pruning and return:

```text
100
101
102
103
104
```

A minimal optimizer-level reproduction is:

1. Construct an ordered Parquet `DataSourceExec`.
2. Wrap it in a `SortPreservingMergeExec` with `fetch=5`.
3. Run `LimitPushdown`.
4. Inspect the resulting `FileScanConfig`.

On `main` at `66677feea`, the resulting scan has `limit=Some(5)` but `preserve_order=false`.

### Expected behavior

A fetch on `SortPreservingMergeExec` selects the leading rows according to its ordering. When that fetch is pushed into the underlying scan, `LimitPushdown` should propagate `preserve_order=true`.

The resulting `FileScanConfig` should contain:

```text
limit=Some(5)
preserve_order=true
```

This prevents order-insensitive Parquet limit pruning from changing which rows are eligible for the ordered limit.

### Additional context

The issue occurs because `pushdown_limit_helper` updates its global requirements when it encounters an operator with a fetch, but does not infer order sensitivity from a fetched `SortPreservingMergeExec`.

This is related to #24215, but is a distinct path. #24215 concerns order requirements lost when limit nodes are reconstructed or optimized again. This issue occurs in the standard single-pass optimizer flow after a fetched `SortPreservingMergeExec` has already been created.

Contributor guide

Open the contributing guide

Research direction

Start at pushdown_limit_helper in LimitPushdown and inspect how a fetched SortPreservingMergeExec updates requirements for the underlying FileScanConfig. Reproduce the optimizer-level case described in the issue, then verify that the scan retains limit=Some(5) with preserve_order=true and that the ordered query returns 1 through 5.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend, databases
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.