jayzhan211 opened a new pull request, #26434:
URL: https://github.com/apache/datafusion/pull/26434
## Which issue does this PR close?
- Closes #24272.
- Makes #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 (#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" (#24173, #24215, #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.
- API deprecations listed above (`api change` label).
--
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]
