Skip to content

Commit 63af08d

Browse files
authored
fix: keep file order for scans that advertise an output ordering (apache#26434)
## Which issue does this PR close? - Closes apache#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).
1 parent b86f1f2 commit 63af08d

20 files changed

Lines changed: 332 additions & 361 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_sorting.rs‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2360,14 +2360,12 @@ fn test_spm_fetch_preserves_ordering_through_child_rewrite() -> Result<()> {
23602360
.downcast_ref::<LocalLimitExec>()
23612361
.expect("SPM fetch should become a local limit");
23622362
assert_eq!(limit.fetch(), 100);
2363-
assert_eq!(limit.required_ordering().as_ref(), Some(&ordering));
23642363

23652364
let config = ConfigOptions::new();
23662365
let optimized = ProjectionPushdown::new().optimize(optimized, &config)?;
23672366
let limit = optimized
23682367
.downcast_ref::<LocalLimitExec>()
23692368
.expect("projection rewrite should retain the local limit");
2370-
assert_eq!(limit.required_ordering().as_ref(), Some(&ordering));
23712369
assert!(limit.input().is::<DataSourceExec>());
23722370

23732371
let optimized = LimitPushdown::new().optimize(optimized, &config)?;
@@ -2379,7 +2377,7 @@ fn test_spm_fetch_preserves_ordering_through_child_rewrite() -> Result<()> {
23792377
.downcast_ref::<FileScanConfig>()
23802378
.expect("parquet scan should use FileScanConfig");
23812379
assert_eq!(config.limit, Some(100));
2382-
assert!(config.preserve_order);
2380+
assert!(config.preserves_file_order());
23832381

23842382
Ok(())
23852383
}

‎datafusion/core/tests/physical_optimizer/ensure_requirements.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -877,10 +877,10 @@ fn test_fetch_fallback_is_stable() {
877877

878878
let output_children = pushed_down.children();
879879
let merge_children = output_children[0].children();
880-
let limit = merge_children[0]
881-
.downcast_ref::<LocalLimitExec>()
882-
.expect("the fetch should be carried by a local limit");
883-
assert_eq!(limit.required_ordering(), &Some(ordering));
880+
assert!(
881+
merge_children[0].is::<LocalLimitExec>(),
882+
"the fetch should be carried by a local limit"
883+
);
884884

885885
let pushed_down = plan_string(&pushed_down);
886886
let next_pass = plan_string(&next_pass);

‎datafusion/datasource-parquet/src/source.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -636,7 +636,7 @@ impl FileSource for ParquetSource {
636636
.batch_size
637637
.expect("Batch size must set before creating ParquetMorselizer"),
638638
limit: base_config.limit,
639-
preserve_order: base_config.preserve_order,
639+
preserve_order: base_config.preserves_file_order(),
640640
predicate: self.predicate.clone(),
641641
table_schema: self.table_schema.clone(),
642642
metadata_size_hint: self.metadata_size_hint,

‎datafusion/datasource/src/file_scan_config/mod.rs‎

Lines changed: 54 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -184,10 +184,12 @@ pub struct FileScanConfig {
184184
/// The maximum number of records to read from this plan. If `None`,
185185
/// all records after filtering are returned.
186186
pub limit: Option<usize>,
187-
/// Whether the scan's limit is order sensitive
188-
/// When `true`, files must be read in the exact order specified to produce
189-
/// correct results (e.g., for `ORDER BY ... LIMIT` queries). When `false`,
190-
/// DataFusion may reorder file processing for optimization without affecting correctness.
187+
/// Read files in the order of [`Self::file_groups`].
188+
///
189+
/// [`FileScanConfigBuilder::build`] sets this when the scan has an output
190+
/// ordering. Readers use [`Self::preserves_file_order`], which also checks
191+
/// the current [`Self::output_ordering`], so clearing this flag never
192+
/// reorders a scan that advertises an ordering.
191193
pub preserve_order: bool,
192194
/// All equivalent lexicographical output orderings of this file scan, in terms of
193195
/// [`FileSource::table_schema`]. See [`FileScanConfigBuilder::with_output_ordering`] for more
@@ -333,14 +335,10 @@ impl FileScanConfigBuilder {
333335
self
334336
}
335337

336-
/// Set whether the limit should be order-sensitive.
337-
///
338-
/// When `true`, files must be read in the exact order specified to produce
339-
/// correct results (e.g., for `ORDER BY ... LIMIT` queries). When `false`,
340-
/// DataFusion may reorder file processing for optimization without
341-
/// affecting correctness.
342-
pub fn with_preserve_order(mut self, order_sensitive: bool) -> Self {
343-
self.preserve_order = order_sensitive;
338+
/// Set whether files must be read in the order of the file groups even
339+
/// when the scan has no output ordering. See [`FileScanConfig::preserve_order`].
340+
pub fn with_preserve_order(mut self, preserve_order: bool) -> Self {
341+
self.preserve_order = preserve_order;
344342
self
345343
}
346344

@@ -1188,18 +1186,6 @@ impl DataSource for FileScanConfig {
11881186
}
11891187
}
11901188

1191-
fn with_preserve_order(&self, preserve_order: bool) -> Option<Arc<dyn DataSource>> {
1192-
if self.preserve_order == preserve_order {
1193-
return Some(Arc::new(self.clone()));
1194-
}
1195-
1196-
let new_config = FileScanConfig {
1197-
preserve_order,
1198-
..self.clone()
1199-
};
1200-
Some(Arc::new(new_config))
1201-
}
1202-
12031189
fn apply_expressions(
12041190
&self,
12051191
f: &mut dyn FnMut(&Arc<dyn PhysicalExpr>) -> Result<TreeNodeRecursion>,
@@ -1220,7 +1206,7 @@ impl DataSource for FileScanConfig {
12201206
&self,
12211207
config: &ConfigOptions,
12221208
) -> Option<Arc<dyn Any + Send + Sync>> {
1223-
if self.preserve_order
1209+
if self.preserves_file_order()
12241210
|| self.output_partitioning.is_some()
12251211
|| !config.execution.enable_file_stream_work_stealing
12261212
{
@@ -1269,6 +1255,16 @@ fn append_known_empty_files(
12691255
}
12701256

12711257
impl FileScanConfig {
1258+
/// Returns true if files must be read in the order of the file groups.
1259+
///
1260+
/// Parents such as `SortPreservingMergeExec` rely on the output ordering
1261+
/// this scan advertises, so a scan with an output ordering never shares
1262+
/// files between partitions (work stealing) and never skips rows based on
1263+
/// its limit (limit pruning).
1264+
pub fn preserves_file_order(&self) -> bool {
1265+
self.preserve_order || !self.output_ordering.is_empty()
1266+
}
1267+
12721268
/// Returns only the output orderings that are validated against actual
12731269
/// file group statistics.
12741270
///
@@ -3036,6 +3032,39 @@ mod tests {
30363032
}
30373033
}
30383034

3035+
/// A scan that advertises an output ordering never shares files between
3036+
/// partitions, even if `preserve_order` is cleared after it is built.
3037+
#[test]
3038+
fn output_ordering_keeps_files_in_order() {
3039+
let schema =
3040+
Arc::new(Schema::new(vec![Field::new("a", DataType::Float64, false)]));
3041+
let sort_expr = PhysicalSortExpr::new_default(Arc::new(Column::new("a", 0)));
3042+
let mut config = FileScanConfigBuilder::new(
3043+
ObjectStoreUrl::local_filesystem(),
3044+
Arc::new(MockSource::new(schema)),
3045+
)
3046+
.with_file_groups(vec![
3047+
FileGroup::new(vec![make_file_with_stats("file1", 0.0, 9.0)]),
3048+
FileGroup::new(vec![make_file_with_stats("file2", 10.0, 19.0)]),
3049+
])
3050+
.with_output_ordering(vec![LexOrdering::new(vec![sort_expr]).unwrap()])
3051+
.build();
3052+
let options = ConfigOptions::default();
3053+
3054+
config.preserve_order = false;
3055+
assert!(config.preserves_file_order());
3056+
assert!(config.create_sibling_state(&options).is_none());
3057+
3058+
config.output_ordering = vec![];
3059+
assert!(!config.preserves_file_order());
3060+
assert!(config.create_sibling_state(&options).is_some());
3061+
3062+
// An explicit `preserve_order` keeps file order without an output ordering
3063+
config.preserve_order = true;
3064+
assert!(config.preserves_file_order());
3065+
assert!(config.create_sibling_state(&options).is_none());
3066+
}
3067+
30393068
#[test]
30403069
fn test_output_partitioning_not_partitioned_by_file_group() {
30413070
let file_schema = aggr_test_schema();

‎datafusion/datasource/src/source.rs‎

Lines changed: 4 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -223,6 +223,10 @@ pub trait DataSource: Any + Send + Sync + Debug {
223223
}
224224

225225
/// Returns a variant of this `DataSource` that is aware of order-sensitivity.
226+
#[deprecated(
227+
since = "56.0.0",
228+
note = "no longer called: a scan that advertises an output ordering always preserves it"
229+
)]
226230
fn with_preserve_order(&self, _preserve_order: bool) -> Option<Arc<dyn DataSource>> {
227231
None
228232
}
@@ -585,18 +589,6 @@ impl ExecutionPlan for DataSourceExec {
585589
})
586590
}
587591

588-
fn with_preserve_order(
589-
&self,
590-
preserve_order: bool,
591-
) -> Option<Arc<dyn ExecutionPlan>> {
592-
self.data_source
593-
.with_preserve_order(preserve_order)
594-
.map(|new_data_source| {
595-
Arc::new(self.clone().with_data_source(new_data_source))
596-
as Arc<dyn ExecutionPlan>
597-
})
598-
}
599-
600592
fn with_new_state(
601593
&self,
602594
state: Arc<dyn Any + Send + Sync>,

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs‎

Lines changed: 3 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -467,8 +467,7 @@ pub fn ensure_sorting(
467467
// single partition.
468468
let child_node = requirements.children.swap_remove(0);
469469
if let Some(fetch) = requirements.plan.fetch() {
470-
let mut limit = LocalLimitExec::new(Arc::clone(&child_node.plan), fetch);
471-
limit.set_required_ordering(requirements.plan.output_ordering().cloned());
470+
let limit = LocalLimitExec::new(Arc::clone(&child_node.plan), fetch);
472471
return Ok(Transformed::yes(PlanContext::new(
473472
Arc::new(limit),
474473
false,
@@ -516,17 +515,11 @@ fn analyze_immediate_sort_removal(
516515
// Remove the sort:
517516
node.children = node.children.swap_remove(0).children;
518517
if let Some(fetch) = sort_exec.fetch() {
519-
let required_ordering = sort_exec.properties().output_ordering().cloned();
520518
// If the sort has a fetch, we need to add a limit:
521519
if properties.output_partitioning().partition_count() == 1 {
522-
let mut global_limit =
523-
GlobalLimitExec::new(Arc::clone(sort_input), 0, Some(fetch));
524-
global_limit.set_required_ordering(required_ordering);
525-
Arc::new(global_limit)
520+
Arc::new(GlobalLimitExec::new(Arc::clone(sort_input), 0, Some(fetch)))
526521
} else {
527-
let mut local_limit = LocalLimitExec::new(Arc::clone(sort_input), fetch);
528-
local_limit.set_required_ordering(required_ordering);
529-
Arc::new(local_limit)
522+
Arc::new(LocalLimitExec::new(Arc::clone(sort_input), fetch))
530523
}
531524
} else {
532525
Arc::clone(sort_input)

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs‎

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -189,13 +189,9 @@ fn preserve_fetch_above_ordered_plan(
189189
let input = Arc::clone(&node.plan);
190190

191191
let limit: Arc<dyn ExecutionPlan> = if input_has_multiple_partitions {
192-
let mut limit = LocalLimitExec::new(input, fetch);
193-
limit.set_required_ordering(Some(ordering.clone()));
194-
Arc::new(limit)
192+
Arc::new(LocalLimitExec::new(input, fetch))
195193
} else {
196-
let mut limit = GlobalLimitExec::new(input, 0, Some(fetch));
197-
limit.set_required_ordering(Some(ordering.clone()));
198-
Arc::new(limit)
194+
Arc::new(GlobalLimitExec::new(input, 0, Some(fetch)))
199195
};
200196
let limit_node = PlanContext::new(limit, ParentRequirements::default(), vec![node]);
201197

‎datafusion/physical-optimizer/src/limit_pushdown.rs‎

Lines changed: 3 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -100,7 +100,6 @@ pub struct GlobalRequirements {
100100
fetch: Option<usize>,
101101
skip: usize,
102102
satisfied: bool,
103-
preserve_order: bool,
104103
}
105104

106105
impl LimitPushdown {
@@ -128,7 +127,6 @@ impl PhysicalOptimizerRule for LimitPushdown {
128127
fetch: None,
129128
skip: 0,
130129
satisfied: false,
131-
preserve_order: false,
132130
};
133131
with_statistics_context(context, |stats_ctx| {
134132
pushdown_limits(plan, global_state, stats_ctx)
@@ -148,7 +146,6 @@ struct LimitInfo {
148146
input: Arc<dyn ExecutionPlan>,
149147
fetch: Option<usize>,
150148
skip: usize,
151-
preserve_order: bool,
152149
}
153150

154151
/// This function is the main helper function of the `LimitPushDown` rule.
@@ -198,7 +195,6 @@ pub fn pushdown_limit_helper_with_stats(
198195
);
199196
global_state.skip = skip;
200197
global_state.fetch = fetch;
201-
global_state.preserve_order = limit_info.preserve_order;
202198
global_state.satisfied = false;
203199

204200
if let Some(fetch) = fetch
@@ -315,28 +311,17 @@ pub fn pushdown_limit_helper_with_stats(
315311
let maybe_fetchable = pushdown_plan.with_fetch(skip_and_fetch);
316312
if global_state.satisfied {
317313
if let Some(plan_with_fetch) = maybe_fetchable {
318-
let plan_with_preserve_order = plan_with_fetch
319-
.with_preserve_order(global_state.preserve_order)
320-
.unwrap_or(plan_with_fetch);
321-
Ok((Transformed::yes(plan_with_preserve_order), global_state))
314+
Ok((Transformed::yes(plan_with_fetch), global_state))
322315
} else {
323316
Ok((Transformed::no(pushdown_plan), global_state))
324317
}
325318
} else {
326319
global_state.satisfied = true;
327320
pushdown_plan = if let Some(plan_with_fetch) = maybe_fetchable {
328-
let plan_with_preserve_order = plan_with_fetch
329-
.with_preserve_order(global_state.preserve_order)
330-
.unwrap_or(plan_with_fetch);
331-
332321
if global_skip > 0 {
333-
add_global_limit(
334-
plan_with_preserve_order,
335-
global_skip,
336-
Some(global_fetch),
337-
)
322+
add_global_limit(plan_with_fetch, global_skip, Some(global_fetch))
338323
} else {
339-
plan_with_preserve_order
324+
plan_with_fetch
340325
}
341326
} else {
342327
add_limit(pushdown_plan, global_skip, global_fetch)
@@ -460,15 +445,13 @@ fn extract_limit(plan: &Arc<dyn ExecutionPlan>) -> Option<LimitInfo> {
460445
input: Arc::clone(global_limit.input()),
461446
fetch: global_limit.fetch(),
462447
skip: global_limit.skip(),
463-
preserve_order: global_limit.required_ordering().is_some(),
464448
})
465449
} else {
466450
plan.downcast_ref::<LocalLimitExec>()
467451
.map(|local_limit| LimitInfo {
468452
input: Arc::clone(local_limit.input()),
469453
fetch: Some(local_limit.fetch()),
470454
skip: 0,
471-
preserve_order: local_limit.required_ordering().is_some(),
472455
})
473456
}
474457
}

‎datafusion/physical-plan/src/coalesce_partitions.rs‎

Lines changed: 1 addition & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -28,9 +28,7 @@ use super::{
2828
DisplayAs, ExecutionPlanProperties, PlanProperties, SendableRecordBatchStream,
2929
Statistics,
3030
};
31-
use crate::execution_plan::{
32-
CardinalityEffect, EvaluationType, SchedulingType, replace_children_if_necessary,
33-
};
31+
use crate::execution_plan::{CardinalityEffect, EvaluationType, SchedulingType};
3432
use crate::filter_pushdown::{FilterDescription, FilterPushdownPhase};
3533
use crate::projection::{ProjectionExec, make_with_child};
3634
use crate::sort_pushdown::SortOrderPushdownResult;
@@ -347,18 +345,6 @@ impl ExecutionPlan for CoalescePartitionsExec {
347345
}))
348346
}
349347

350-
fn with_preserve_order(
351-
&self,
352-
preserve_order: bool,
353-
) -> Option<Arc<dyn ExecutionPlan>> {
354-
self.input
355-
.with_preserve_order(preserve_order)
356-
.and_then(|new_input| {
357-
replace_children_if_necessary(Arc::new(self.clone()), vec![new_input])
358-
.ok()
359-
})
360-
}
361-
362348
fn gather_filters_for_pushdown(
363349
&self,
364350
_phase: FilterPushdownPhase,

‎datafusion/physical-plan/src/execution_plan.rs‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -996,10 +996,12 @@ pub trait ExecutionPlan: Any + Debug + DisplayAs + Send + Sync {
996996

997997
/// Returns a variant of this `ExecutionPlan` that is aware of order-sensitivity.
998998
///
999-
/// This is used to signal to data sources that the output ordering must be
1000-
/// preserved, even if it might be more efficient to ignore it (e.g. by
1001-
/// skipping some row groups in Parquet).
1002-
///
999+
/// No longer called by DataFusion: a data source that advertises an output
1000+
/// ordering always preserves it, so no optimizer rule needs to request it.
1001+
#[deprecated(
1002+
since = "56.0.0",
1003+
note = "no longer called: a scan that advertises an output ordering always preserves it"
1004+
)]
10031005
fn with_preserve_order(
10041006
&self,
10051007
_preserve_order: bool,

0 commit comments

Comments
 (0)