You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 63af08d
Browse filesBrowse the repository at this point in the historyBrowse files
fix: keep file order for scans that advertise an output ordering (apache#26434)
## Which issue does this PR close?
- Closesapache#24272.
- Makes apache#24215 moot (the limit nodes no longer carry an ordering to
lose).
## Rationale for this change
`ORDER BY ... LIMIT` over a parquet table declared `WITH ORDER` can
return the wrong rows with default settings:
```sql
-- 8 sorted files plus one backfill file holding the smallest values
SET datafusion.execution.target_partitions = 8;
CREATE EXTERNAL TABLE t STORED AS PARQUET WITH ORDER (a ASC) LOCATION '...';
SELECT a FROM t ORDER BY a LIMIT 3; -- returns 0, 1, 2; min(a) is -100000
```
The plan is `SortPreservingMergeExec: fetch=3 -> DataSourceExec:
output_ordering=[a ASC], limit=3`.
`LimitPushdown` pushes the merge's fetch into the scan and, because its
own `preserve_order` flag defaults to `false`,
calls `with_preserve_order(false)`. That overwrites the `true` the scan
was built with, which:
- turns on work stealing: the partitions share one file queue, so a
partition can read a higher file before a lower one
and its stream is no longer sorted (the wrong rows above);
- turns on parquet limit pruning: the scan may skip a partially matching
row group for a later fully matching one (apache#24272).
Whether a scan must keep its file order is passed through six places
today: `EnforceSorting` sets `required_ordering`
on limit nodes, `LimitPushdown` copies it into a bool,
`ExecutionPlan::with_preserve_order` forwards it through
projection/filter/coalesce/merge, `DataSource::with_preserve_order` sets
`FileScanConfig::preserve_order`, and the file
stream and parquet opener read it. Any place that drops it means
"reorder freely" (apache#24173, apache#24215, apache#24272).
The scan already knows the answer: it advertises its output ordering,
and every parent that depends on order relies on
exactly that.
## What changes are included in this PR?
- `FileScanConfig::preserves_file_order()`: a scan with an output
ordering always reads its files in order. Work
stealing and parquet limit pruning use only this.
- `LimitPushdown` no longer tracks or pushes order sensitivity.
- Deprecated, no longer used: `ExecutionPlan::with_preserve_order`,
`DataSource::with_preserve_order` (the 5 forwarding
overrides are removed), and
`GlobalLimitExec`/`LocalLimitExec::required_ordering` /
`set_required_ordering`
(the field is removed; the protobuf field is ignored on read and no
longer written).
- Upgrade guide entry.
## What is the testing strategy for this PR?
- `limit_pruning.slt`: two new cases, both fail on `main` (`0..4`
instead of `-10..-6`; `4, 5, 6` instead of `2, 3, 4`).
- Unit test `output_ordering_keeps_files_in_order` in
`file_scan_config`.
- Updated tests that asserted the removed plumbing (core physical
optimizer, proto).
Benchmark: TPC-H SF10 `lineitem` declared `WITH ORDER (l_orderkey)`,
release-nonlto, same commit with and without
this change, median of 10 runs over two interleaved rounds (ms):
| Query | pushdown_filters | main | this PR |
|---|---|---|---|
| Q1 `ORDER BY l_orderkey LIMIT 10` | off / on | 19.5 / 19.0 | 19.0 /
19.0 |
| Q2 `WHERE l_quantity > 49 ORDER BY l_orderkey LIMIT 10` | off / on |
28.5 / 20.0 | 28.0 / 20.0 |
| Q3 `WHERE l_shipdate > '1998-11-25' ORDER BY l_orderkey LIMIT 10` |
off / on | 35.0 / 29.0 | 37.5 / 29.0 |
| Q4 `WHERE l_quantity > 49 LIMIT 10` | off / on | 18.0 / 17.5 | 17.0 /
17.5 |
| Q5 `WHERE l_shipdate > '1998-11-25' LIMIT 10` | off / on | 27.5 / 23.5
| 26.5 / 22.5 |
A rerun of Q3 (off) with 15 interleaved runs each gave 37-42 ms on main
and 36-41 ms with this PR. Scans with a declared ordering
already read files in order whenever no limit is pushed into them (the
builder sets `preserve_order`), so this PR only
removes the reordering on the path where a limit is pushed in; tables
without a declared ordering are unaffected.
## Are there any user-facing changes?
- Wrong results fixed for `ORDER BY ... LIMIT` over declared-ordering
file scans.
- A plain `LIMIT` (no `ORDER BY`) over a declared-ordering table now
keeps file order, so it no longer uses work stealing
or limit pruning. Tables without a declared ordering are unchanged. With
uneven file groups this costs time: 16 sorted
files (4 x 8M rows, 12 x 0.5M), 8 partitions, `WHERE b > 0.999999 LIMIT
10` takes 12 -> 14 ms with `pushdown_filters`
off and 4 -> 6 ms with it on (about 2x on @adriangb's machine). The same
uneven groups already slow every non-`LIMIT`
query over such tables on `main` (`sum(a + b) WHERE b > 0.5`: 233 ms vs
93 ms without a declared ordering). The cause
is count-based file grouping for ordered scans, not missing work
stealing; apache#26458 balances ordered file groups by size
(228 -> 78 ms on `main`, and the `LIMIT` case 11 -> 8 ms).
- API deprecations listed above (`api change` label).
0 commit comments