Skip to content

Commit 71beb85

Browse files
committed
Treat a fetch as a barrier in the PushdownSort and FilterPushdown rules
Replace the scan-level `limit` checks with one check per rule, as suggested in review: a node with a fetch keeps the first rows in its input's current order, so `PushdownSort` must not reorder the input below it and `FilterPushdown` must not move a filter from above into or below it (the node's own filters still push down). This also fixes #27194 at the default configuration. The two `filter_pushdown.rs` snapshots that merged an outer filter into a `FilterExec` with a fetch now keep the filters separate, which keeps the rows the inner fetch picks.
1 parent 8b3ef5b commit 71beb85

5 files changed

Lines changed: 82 additions & 55 deletions

File tree

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

Lines changed: 13 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -440,8 +440,10 @@ fn test_filter_collapse_outer_fetch_preserved() {
440440
}
441441

442442
#[test]
443-
fn test_filter_collapse_inner_fetch_preserved() {
444-
// When the inner filter has fetch and outer does not, the merged filter should preserve fetch
443+
fn test_filter_not_collapsed_into_inner_fetch() {
444+
// The inner filter keeps its first 5 matching rows before the outer filter
445+
// applies, so merging the outer predicate into it would change which rows
446+
// are kept. The filters stay separate.
445447
let scan = TestScanBuilder::new(schema()).with_support(false).build();
446448
let predicate1 = col_lit_predicate("a", "foo", &schema());
447449
let filter1 = Arc::new(
@@ -463,16 +465,17 @@ fn test_filter_collapse_inner_fetch_preserved() {
463465
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
464466
output:
465467
Ok:
466-
- FilterExec: b@1 = bar AND a@0 = foo, fetch=5
467-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
468+
- FilterExec: b@1 = bar
469+
- FilterExec: a@0 = foo, fetch=5
470+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
468471
"
469472
);
470473
}
471474

472475
#[test]
473-
fn test_filter_collapse_both_fetch_uses_minimum() {
474-
// When both filters have fetch, the merged filter should use the smaller (tighter) fetch.
475-
// Inner fetch=5 is tighter than outer fetch=10, so the result should be fetch=5.
476+
fn test_filter_with_fetch_not_collapsed_into_inner_fetch() {
477+
// Same as above with a fetch on the outer filter too: the inner filter's
478+
// fetch still picks its rows first, so the filters stay separate.
476479
let scan = TestScanBuilder::new(schema()).with_support(false).build();
477480
let predicate1 = col_lit_predicate("a", "foo", &schema());
478481
let filter1 = Arc::new(
@@ -499,8 +502,9 @@ fn test_filter_collapse_both_fetch_uses_minimum() {
499502
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
500503
output:
501504
Ok:
502-
- FilterExec: b@1 = bar AND a@0 = foo, fetch=5
503-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
505+
- FilterExec: b@1 = bar, fetch=10
506+
- FilterExec: a@0 = foo, fetch=5
507+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
504508
"
505509
);
506510
}

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

Lines changed: 1 addition & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ use datafusion_physical_plan::execution_plan::SchedulingType;
5151
use datafusion_physical_plan::{
5252
DisplayAs, DisplayFormatType,
5353
display::{ProjectSchemaDisplay, display_orderings},
54-
filter_pushdown::{FilterPushdownPropagation, PushedDown},
54+
filter_pushdown::FilterPushdownPropagation,
5555
metrics::ExecutionPlanMetricsSet,
5656
};
5757
use log::{debug, warn};
@@ -1077,15 +1077,6 @@ impl DataSource for FileScanConfig {
10771077
filters: Vec<Arc<dyn PhysicalExpr>>,
10781078
config: &ConfigOptions,
10791079
) -> Result<FilterPushdownPropagation<Arc<dyn DataSource>>> {
1080-
// The scan applies its limit after any filter it holds, so a filter
1081-
// from above the limit would let through rows the limit should have
1082-
// cut.
1083-
if self.limit.is_some() {
1084-
return Ok(FilterPushdownPropagation::with_parent_pushdown_result(
1085-
vec![PushedDown::No; filters.len()],
1086-
));
1087-
}
1088-
10891080
// Remap filter Column indices to match the table schema (file + partition columns).
10901081
// This is necessary because filters refer to the output schema of this `DataSource`
10911082
// (e.g., after projection pushdown has been applied) and need to be remapped to the table schema
@@ -1177,12 +1168,6 @@ impl DataSource for FileScanConfig {
11771168
&self,
11781169
order: &[PhysicalSortExpr],
11791170
) -> Result<SortOrderPushdownResult<Arc<dyn DataSource>>> {
1180-
// Reordering the files or rows of a scan changes which rows its limit
1181-
// keeps.
1182-
if self.limit.is_some() {
1183-
return Ok(SortOrderPushdownResult::Unsupported);
1184-
}
1185-
11861171
let pushdown_result = self
11871172
.file_source
11881173
.try_pushdown_sort(order, &self.eq_properties())?;
@@ -3861,36 +3846,6 @@ mod tests {
38613846
Ok(())
38623847
}
38633848

3864-
/// A scan that holds a limit is not reordered: reading it in another order
3865-
/// would change which rows the limit keeps.
3866-
#[test]
3867-
fn sort_pushdown_with_limit_unsupported() -> Result<()> {
3868-
let file_schema =
3869-
Arc::new(Schema::new(vec![Field::new("a", DataType::Float64, false)]));
3870-
let table_schema = TableSchema::from(&file_schema);
3871-
let file_source = Arc::new(ExactSortPushdownSource::new(table_schema));
3872-
let sort_expr = PhysicalSortExpr::new_default(Arc::new(Column::new("a", 0)));
3873-
let config =
3874-
FileScanConfigBuilder::new(ObjectStoreUrl::local_filesystem(), file_source)
3875-
.with_file_groups(vec![FileGroup::new(vec![
3876-
make_file_with_stats("file1", 0.0, 9.0),
3877-
make_file_with_stats("file2", 10.0, 19.0),
3878-
])])
3879-
.with_output_ordering(vec![
3880-
LexOrdering::new(vec![sort_expr.clone()]).unwrap(),
3881-
])
3882-
.with_limit(Some(5))
3883-
.build();
3884-
3885-
let result = config.try_pushdown_sort(&[sort_expr.reverse()])?;
3886-
3887-
assert!(
3888-
matches!(result, SortOrderPushdownResult::Unsupported),
3889-
"Expected Unsupported result, got {result:?}"
3890-
);
3891-
Ok(())
3892-
}
3893-
38943849
#[test]
38953850
fn sort_pushdown_exact_source_overlapping_downgraded_to_inexact() -> Result<()> {
38963851
let file_schema =

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -430,6 +430,16 @@ fn push_down_filters(
430430
config: &ConfigOptions,
431431
phase: FilterPushdownPhase,
432432
) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>> {
433+
// A node with a fetch picks its rows before a filter from above applies, so
434+
// that filter can't move below or into it. The node's own filters still can.
435+
if node.fetch().is_some() && !parent_predicates.is_empty() {
436+
let result = push_down_filters(node, vec![], config, phase)?;
437+
return Ok(FilterPushdownPropagation {
438+
filters: vec![PushedDown::No; parent_predicates.len()],
439+
updated_node: result.updated_node,
440+
});
441+
}
442+
433443
let mut parent_filter_pushdown_supports: Vec<Vec<PushedDown>> =
434444
vec![vec![]; parent_predicates.len()];
435445

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -91,6 +91,9 @@ impl PhysicalOptimizerRule for PushdownSort {
9191
&& sort_child.preserve_partitioning()
9292
{
9393
let sort_input = Arc::clone(sort_child.input());
94+
if input_has_fetch(&sort_input)? {
95+
return Ok(Transformed::no(plan));
96+
}
9497
let required_ordering = sort_child.expr();
9598
match sort_input.try_pushdown_sort(required_ordering)? {
9699
SortOrderPushdownResult::Exact { inner } => {
@@ -144,6 +147,9 @@ impl PhysicalOptimizerRule for PushdownSort {
144147
};
145148

146149
let sort_input = Arc::clone(sort_exec.input());
150+
if input_has_fetch(&sort_input)? {
151+
return Ok(Transformed::no(plan));
152+
}
147153
let required_ordering = sort_exec.expr();
148154

149155
// Try to push the sort requirement down through the plan tree
@@ -216,3 +222,9 @@ impl PhysicalOptimizerRule for PushdownSort {
216222
true
217223
}
218224
}
225+
226+
/// Whether a node below this sort has a fetch. A fetch keeps the first rows in the
227+
/// input's current order, so changing that order would change which rows it keeps.
228+
fn input_has_fetch(input: &Arc<dyn ExecutionPlan>) -> Result<bool> {
229+
input.exists(|node| Ok(node.fetch().is_some()))
230+
}

‎datafusion/sqllogictest/test_files/sort_pushdown_exact_reverse.slt‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -482,6 +482,52 @@ SELECT ts FROM days ORDER BY date_trunc('day', ts) DESC LIMIT 4;
482482
1970-01-03T12:00:00
483483
1970-01-03T18:00:00
484484

485+
# Test 16: #27194, with the option off (the default). A subquery's
486+
# `ORDER BY ... LIMIT` over a sorted file leaves the scan holding the limit;
487+
# neither a reversing sort pushdown nor a pushed-down filter may change which
488+
# rows that limit keeps.
489+
statement ok
490+
SET datafusion.execution.parquet.enable_exact_reverse_scan = false;
491+
492+
query I
493+
COPY (SELECT value AS s, value * 10 AS x FROM generate_series(1, 12) ORDER BY s)
494+
TO 'test_files/scratch/sort_pushdown_exact_reverse/issue_27194/t.parquet'
495+
STORED AS PARQUET OPTIONS ('format.max_row_group_size' '3');
496+
----
497+
12
498+
499+
query I
500+
COPY (SELECT value AS k FROM generate_series(7, 8))
501+
TO 'test_files/scratch/sort_pushdown_exact_reverse/issue_27194/b.parquet'
502+
STORED AS PARQUET;
503+
----
504+
2
505+
506+
statement ok
507+
CREATE EXTERNAL TABLE issue_27194_t STORED AS PARQUET
508+
LOCATION 'test_files/scratch/sort_pushdown_exact_reverse/issue_27194/t.parquet';
509+
510+
statement ok
511+
CREATE EXTERNAL TABLE issue_27194_b STORED AS PARQUET
512+
LOCATION 'test_files/scratch/sort_pushdown_exact_reverse/issue_27194/b.parquet';
513+
514+
query I
515+
SELECT s FROM (SELECT * FROM issue_27194_t ORDER BY s LIMIT 3) ORDER BY s DESC;
516+
----
517+
3
518+
2
519+
1
520+
521+
query I
522+
SELECT s FROM (SELECT * FROM issue_27194_t ORDER BY s LIMIT 3) ORDER BY x DESC LIMIT 1;
523+
----
524+
3
525+
526+
query I
527+
SELECT i.s FROM issue_27194_b JOIN (SELECT s FROM issue_27194_t ORDER BY s LIMIT 3) i
528+
ON issue_27194_b.k = i.s;
529+
----
530+
485531
# Cleanup
486532
statement ok
487533
RESET datafusion.execution.parquet.enable_exact_reverse_scan;

0 commit comments

Comments
 (0)