Skip to content

Commit 44e5403

Browse files
feat: simplify contradictory ranges across AND/OR predicates (apache#26132)
## Which issue does this PR close? - Closes apache#26131. ## Rationale for this change An outer range can make every branch of an OR impossible, but the logical optimizer currently considers the direct comparisons and the disjunction independently. For example, `x >= 10 AND ((x >= 1 AND x < 3) OR (x >= 5 AND x < 7))` retains a scan despite never matching a row. This matters for a `UNION ALL` containing historical backfill branches: a request outside their time windows should eliminate those branches before physical planning calls their table providers, including when the query has an outer `ORDER BY ... LIMIT`. ## What changes are included in this PR? - Carry direct column/literal comparisons from enclosing conjunctions into positive AND/OR descendants. Reuse the existing per-column comparison simplifier to prove contradictions and remove impossible disjuncts. - Retain the original assumption predicates. Do not infer through NOT, casts, arbitrary functions, or across sibling OR branches. Bound contextual analysis by depth and work limits without expanding expressions into DNF. - Preserve predicate rewrites even when the number of conjuncts is unchanged, and report their transformation status when pushdown itself is unavailable. Preserve existing predicate order, including within OR branches, when comparison grouping only permutes the conjuncts. - Convert an impossible filter directly into an `EmptyRelation` before provider pushdown; an `Exact` provider must not absorb FALSE into its scan and still receive a `scan()` call. ## What is the testing strategy for this PR? - `simplify_predicate_disjunctions.slt`: empty intersections, gaps, partial overlap, retained outer assumptions, equality/inequality predicates, NULL, NOT, casts, arithmetic, timestamp precision/time zones, and union branch removal with an outer sort/limit. - `simplify_predicates.slt`: existing regression coverage and an updated plan expectation for independently simplified OR arms. - A public API test with a provider whose `scan()` returns an error verifies that the eliminated union branch is never scanned under Exact, Inexact, or Unsupported pushdown. - Unit tests cover conservative fallback when contextual analysis reaches its work/depth limits. - Existing `predicates.slt` and TPC-H Q19 plan/answer tests verify that unchanged OR branches retain their predicate order. The two CI failures were due to predicate-order differences; their existing plan expectations now pass without snapshot updates. All checks above passed (`predicates.slt` also matches `simplify_predicates.slt`). TPC-H Q19 was additionally run with CI's SF0.1 data and a temporary SQL logic test wrapper including only its table setup, plan, answer, and cleanup files. The full lint script used an isolated current `cargo-audit` and a temporary workspace boundary for `dev/depcheck` because this checkout is nested inside another Cargo workspace. On the final lint run, `cargo-audit --no-fetch` used the advisory database and registry index downloaded earlier the same day because local DNS could not resolve `index.crates.io`. No tooling or manifest changes are included in the patch. Only targeted tests were run, not the full workspace test suite. ## Are there any user-facing changes? Queries with contradictory ranges across AND/OR can avoid planning and scanning impossible inputs. Partial simplification retains all matching rows. No public API or configuration changes. This reasoning is specific to filter truth sets; it does not change nullable Boolean projection results or derive cross-column date/timestamp equivalences. --------- Co-authored-by: Jay Zhan <[email protected]>
1 parent 2c568b4 commit 44e5403

5 files changed

Lines changed: 644 additions & 24 deletions

File tree

‎datafusion/core/tests/custom_sources_cases/provider_filter_pushdown.rs‎

Lines changed: 76 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ use datafusion::scalar::ScalarValue;
3535
use datafusion_catalog::Session;
3636
use datafusion_common::cast::as_primitive_array;
3737
use datafusion_common::tree_node::TreeNodeRecursion;
38-
use datafusion_common::{DataFusionError, internal_err, not_impl_err};
38+
use datafusion_common::{DataFusionError, assert_batches_eq, internal_err, not_impl_err};
3939
use datafusion_expr::expr::{BinaryExpr, Cast};
4040
use datafusion_functions_aggregate::expr_fn::count;
4141
use datafusion_physical_expr::EquivalenceProperties;
@@ -290,3 +290,78 @@ async fn test_filter_pushdown_results() -> Result<()> {
290290
assert_provider_row_count(2, 0).await?;
291291
Ok(())
292292
}
293+
294+
/// Fail at physical planning time if an impossible branch reaches its provider.
295+
#[derive(Debug)]
296+
struct RejectScanProvider {
297+
pushdown: TableProviderFilterPushDown,
298+
}
299+
300+
#[async_trait]
301+
impl TableProvider for RejectScanProvider {
302+
fn schema(&self) -> SchemaRef {
303+
Arc::new(Schema::new(vec![Field::new("x", DataType::Int64, true)]))
304+
}
305+
306+
fn table_type(&self) -> TableType {
307+
TableType::Base
308+
}
309+
310+
async fn scan(
311+
&self,
312+
_state: &dyn Session,
313+
_projection: Option<&[usize]>,
314+
_filters: &[Expr],
315+
_limit: Option<usize>,
316+
) -> Result<Arc<dyn ExecutionPlan>> {
317+
internal_err!("An unsatisfiable branch must not call scan()")
318+
}
319+
320+
fn supports_filters_pushdown(
321+
&self,
322+
filters: &[&Expr],
323+
) -> Result<Vec<TableProviderFilterPushDown>> {
324+
Ok(vec![self.pushdown.clone(); filters.len()])
325+
}
326+
}
327+
328+
#[tokio::test]
329+
async fn contradictory_disjunction_eliminates_provider_scan() -> Result<()> {
330+
for pushdown in [
331+
TableProviderFilterPushDown::Exact,
332+
TableProviderFilterPushDown::Inexact,
333+
TableProviderFilterPushDown::Unsupported,
334+
] {
335+
let ctx = SessionContext::new();
336+
ctx.register_table("backfill", Arc::new(RejectScanProvider { pushdown }))?;
337+
let df = ctx
338+
.sql(
339+
"SELECT value FROM (
340+
SELECT CAST(20 AS BIGINT) AS value
341+
UNION ALL
342+
SELECT x AS value FROM backfill
343+
WHERE (x >= 1 AND x < 3) OR (x >= 5 AND x < 7)
344+
) u WHERE value >= 10 ORDER BY value LIMIT 1",
345+
)
346+
.await?;
347+
let plan = df
348+
.clone()
349+
.into_optimized_plan()?
350+
.display_indent()
351+
.to_string();
352+
assert!(!plan.contains("TableScan: backfill"), "{plan}");
353+
assert!(!plan.contains("Union"), "{plan}");
354+
let batches = df.collect().await?;
355+
assert_batches_eq!(
356+
[
357+
"+-------+",
358+
"| value |",
359+
"+-------+",
360+
"| 20 |",
361+
"+-------+"
362+
],
363+
&batches
364+
);
365+
}
366+
Ok(())
367+
}

‎datafusion/optimizer/src/push_down_filter.rs‎

Lines changed: 74 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -52,8 +52,8 @@ use datafusion_common::tree_node::{
5252
Transformed, TransformedResult, TreeNode, TreeNodeRecursion,
5353
};
5454
use datafusion_common::{
55-
Column, DFSchema, Result, assert_eq_or_internal_err, internal_err, plan_err,
56-
qualified_name,
55+
Column, DFSchema, Result, ScalarValue, assert_eq_or_internal_err, internal_err,
56+
plan_err, qualified_name,
5757
};
5858
use datafusion_expr::expr::WindowFunction;
5959
use datafusion_expr::expr_rewriter::replace_col;
@@ -62,7 +62,7 @@ use datafusion_expr::utils::{
6262
conjunction, expr_to_columns, split_conjunction, split_conjunction_owned,
6363
};
6464
use datafusion_expr::{
65-
BinaryExpr, Distinct, Expr, Filter, Operator, Projection,
65+
BinaryExpr, Distinct, EmptyRelation, Expr, Filter, Operator, Projection,
6666
TableProviderFilterPushDown, and, or,
6767
};
6868

@@ -889,8 +889,25 @@ impl OptimizerRule for PushDownFilter {
889889
// predicates on rows that have already been filtered out.
890890
let (new_predicates, reorder_changed) = reorder_predicates(new_predicates);
891891

892-
let count_changed = old_predicate_len != new_predicates.len();
893-
if count_changed || reorder_changed {
892+
// An OR branch can change without changing the number of conjuncts.
893+
// Ignore permutations from grouping comparisons by column: the cost
894+
// reordering above decides when to change predicate evaluation order.
895+
let predicates_changed = if old_predicate_len != new_predicates.len() {
896+
true
897+
} else {
898+
let old_predicates = split_conjunction(&filter.predicate);
899+
new_predicates
900+
.iter()
901+
.zip(&old_predicates)
902+
.any(|(new, old)| new != *old)
903+
&& {
904+
let new_predicates: IndexSet<_> = new_predicates.iter().collect();
905+
old_predicates
906+
.iter()
907+
.any(|old| !new_predicates.contains(old))
908+
}
909+
};
910+
if predicates_changed || reorder_changed {
894911
let Some(new_predicate) = conjunction(new_predicates) else {
895912
// new_predicates is empty - remove the filter entirely
896913
// Return the child plan without the filter
@@ -899,14 +916,32 @@ impl OptimizerRule for PushDownFilter {
899916
filter.predicate = new_predicate;
900917
}
901918

919+
// A provider accepting Exact pushdown would absorb FALSE into its scan,
920+
// hiding the contradiction from EliminateFilter and still invoking scan().
921+
if matches!(
922+
filter.predicate,
923+
Expr::Literal(ScalarValue::Boolean(Some(false)), _)
924+
) {
925+
return Ok(Transformed::yes(LogicalPlan::EmptyRelation(
926+
EmptyRelation {
927+
produce_one_row: false,
928+
schema: Arc::clone(filter.input.schema()),
929+
},
930+
)));
931+
}
932+
902933
// If the child has a fetch (limit) or skip (offset), pushing a filter
903934
// below it would change semantics: the limit/offset should apply before
904935
// the filter, not after.
905936
if filter.input.fetch()?.is_some() || filter.input.skip()?.is_some() {
906-
return Ok(Transformed::no(LogicalPlan::Filter(filter)));
937+
return Ok(Transformed::new(
938+
LogicalPlan::Filter(filter),
939+
predicates_changed || reorder_changed,
940+
TreeNodeRecursion::Continue,
941+
));
907942
}
908943

909-
match Arc::unwrap_or_clone(filter.input) {
944+
let result = match Arc::unwrap_or_clone(filter.input) {
910945
LogicalPlan::Filter(mut child_filter) => {
911946
// Child filters first to preserve execution order.
912947
// Use IndexSet to remove duplicates while preserving predicate order.
@@ -1025,7 +1060,11 @@ impl OptimizerRule for PushDownFilter {
10251060
// If no non-unnest predicates exist, early return
10261061
if non_unnest_predicates.is_empty() {
10271062
filter.input = Arc::new(LogicalPlan::Unnest(unnest));
1028-
return Ok(Transformed::no(LogicalPlan::Filter(filter)));
1063+
return Ok(Transformed::new(
1064+
LogicalPlan::Filter(filter),
1065+
predicates_changed || reorder_changed,
1066+
TreeNodeRecursion::Continue,
1067+
));
10291068
}
10301069

10311070
// Push down non-unnest filter predicate
@@ -1305,7 +1344,11 @@ impl OptimizerRule for PushDownFilter {
13051344
.all(|res| res == &TableProviderFilterPushDown::Unsupported)
13061345
{
13071346
filter.input = Arc::new(LogicalPlan::TableScan(scan));
1308-
return Ok(Transformed::no(LogicalPlan::Filter(filter)));
1347+
return Ok(Transformed::new(
1348+
LogicalPlan::Filter(filter),
1349+
predicates_changed || reorder_changed,
1350+
TreeNodeRecursion::Continue,
1351+
));
13091352
}
13101353

13111354
// Compose scan filters from non-volatile filters of `Exact` or `Inexact` pushdown type
@@ -1331,7 +1374,11 @@ impl OptimizerRule for PushDownFilter {
13311374
&& scan.filters == new_scan_filters
13321375
{
13331376
filter.input = Arc::new(LogicalPlan::TableScan(scan));
1334-
return Ok(Transformed::no(LogicalPlan::Filter(filter)));
1377+
return Ok(Transformed::new(
1378+
LogicalPlan::Filter(filter),
1379+
predicates_changed || reorder_changed,
1380+
TreeNodeRecursion::Continue,
1381+
));
13351382
} else {
13361383
scan.filters = new_scan_filters;
13371384
}
@@ -1356,7 +1403,11 @@ impl OptimizerRule for PushDownFilter {
13561403
// so we return the original Filter unchanged.
13571404
if extension_plan.node.inputs().is_empty() {
13581405
filter.input = Arc::new(LogicalPlan::Extension(extension_plan));
1359-
return Ok(Transformed::no(LogicalPlan::Filter(filter)));
1406+
return Ok(Transformed::new(
1407+
LogicalPlan::Filter(filter),
1408+
predicates_changed || reorder_changed,
1409+
TreeNodeRecursion::Continue,
1410+
));
13601411
}
13611412
let prevent_cols =
13621413
extension_plan.node.prevent_predicate_push_down_columns();
@@ -1373,7 +1424,11 @@ impl OptimizerRule for PushDownFilter {
13731424
// all predicates are kept, no changes needed
13741425
if predicate_push_or_keep.iter().all(|&x| !x) {
13751426
filter.input = Arc::new(LogicalPlan::Extension(extension_plan));
1376-
return Ok(Transformed::no(LogicalPlan::Filter(filter)));
1427+
return Ok(Transformed::new(
1428+
LogicalPlan::Filter(filter),
1429+
predicates_changed || reorder_changed,
1430+
TreeNodeRecursion::Continue,
1431+
));
13771432
}
13781433

13791434
// going to push some predicates down, so split the predicates
@@ -1414,7 +1469,11 @@ impl OptimizerRule for PushDownFilter {
14141469
filter.input = Arc::new(child);
14151470
Ok(Transformed::no(LogicalPlan::Filter(filter)))
14161471
}
1417-
}
1472+
};
1473+
result.map(|mut result| {
1474+
result.transformed |= predicates_changed || reorder_changed;
1475+
result
1476+
})
14181477
}
14191478
}
14201479

@@ -4653,14 +4712,8 @@ mod tests {
46534712
TestUserNode
46544713
",
46554714
);
4656-
// Check that the filter is pushed down to the user-defined node
4657-
assert_optimized_plan_equal!(
4658-
plan,
4659-
@r"
4660-
Filter: Boolean(false)
4661-
TestUserNode
4662-
"
4663-
)
4715+
// An impossible filter eliminates even a leaf extension before pushdown.
4716+
assert_optimized_plan_equal!(plan, @"EmptyRelation: rows=0")
46644717
}
46654718

46664719
/// Test that filters are NOT pushed through MoveTowardsLeafNodes projections.

0 commit comments

Comments
 (0)