You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "xudong963 (via GitHub)" <gi...@apache.org> on 2026/10/08 05:30:03 UTC

[PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

xudong963 opened a new pull request, #26132:
URL: https://github.com/apache/datafusion/pull/26132

   ## Which issue does this PR close?
   
   - Closes #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 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.
   
   Targeted validation:
   
   ```text
   cargo test --profile ci -p datafusion-optimizer simplify_predicates --lib
   cargo test --profile ci -p datafusion-optimizer push_down_filter --lib
   cargo test --profile ci --test sqllogictests -- simplify_predicate_disjunctions.slt simplify_predicates.slt
   cargo test --profile ci -p datafusion --test core_integration contradictory_disjunction_eliminates_provider_scan
   cargo fmt --all -- --check
   cargo clippy --all-targets --all-features -- -D warnings
   uv run ./dev/rust_lint.sh
   ```
   
   All checks above passed. 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; no tooling or manifest changes are included in the patch. Only the targeted tests above 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.
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26132:
URL: https://github.com/apache/datafusion/pull/26132#discussion_r4247750477


##########
datafusion/optimizer/src/push_down_filter.rs:
##########
@@ -1410,9 +1465,17 @@ impl OptimizerRule for PushDownFilter {
             }
             child => {
                 filter.input = Arc::new(child);
-                Ok(Transformed::no(LogicalPlan::Filter(filter)))
+                Ok(Transformed::new(
+                    LogicalPlan::Filter(filter),
+                    predicates_changed || reorder_changed,
+                    TreeNodeRecursion::Continue,
+                ))

Review Comment:
   ```suggestion
   Ok(Transformed::no(LogicalPlan::Filter(filter)))
   ```



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #26132:
URL: https://github.com/apache/datafusion/pull/26132#issuecomment-6075412767

   cc @wudidapaopao 


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26132:
URL: https://github.com/apache/datafusion/pull/26132#discussion_r4235738104


##########
datafusion/optimizer/src/simplify_expressions/simplify_predicates.rs:
##########
@@ -29,25 +29,143 @@
 
 use super::utils::{is_false, is_null};
 use datafusion_common::utils::normalize_float_zero_scalar;
-use datafusion_common::{Column, Result, ScalarValue, internal_err};
+use datafusion_common::{Column, DataFusionError, Result, ScalarValue, internal_err};
+use datafusion_expr::utils::{conjunction, split_conjunction_owned};
 use datafusion_expr::{BinaryExpr, Expr, Operator, lit};
+use indexmap::IndexSet;
 use std::cmp::Ordering;
 use std::collections::BTreeMap;
 
+const MAX_DISJUNCTION_WORK: usize = 4096;
+const MAX_DISJUNCTION_DEPTH: usize = 32;
+
 /// Simplifies a list of predicates by removing redundancies.
 ///
 /// This function takes a vector of predicate expressions and groups them by the column they reference.
 /// Predicates that reference a single column and are comparison operations (e.g., >, >=, <, <=, =, !=)
 /// are analyzed to remove redundant conditions. For instance, `x > 5 AND x > 6` is simplified to
 /// `x > 6`. Predicates that contradict each other, such as `x > 6 AND x < 5`, reduce the whole
 /// conjunction to `false`. Other predicates that do not fit this pattern are retained as-is.
+/// Comparisons in an enclosing conjunction also constrain each branch of an `OR`:
+/// `x >= 10 AND (x < 3 OR x < 7)` cannot be true. This simplification preserves
+/// which rows pass a filter, rather than Boolean values in projection expressions.
 ///
 /// # Arguments
 /// * `predicates` - A vector of `Expr` representing the predicates to simplify.
 ///
 /// # Returns
 /// A `Result` containing a vector of simplified `Expr` predicates.
 pub fn simplify_predicates(predicates: Vec<Expr>) -> Result<Vec<Expr>> {
+    let mut remaining = MAX_DISJUNCTION_WORK;
+    simplify_with_context(predicates, &[], 0, &mut remaining)
+}
+
+/// Only descend through positive AND/OR expressions. In particular, replacing a
+/// nullable, unsatisfiable predicate with false below NOT would change its truth set.
+/// Keep assumptions outside the expressions they simplify, and never distribute
+/// conjunctions over disjunctions. The budget bounds repeated comparison work.
+fn simplify_with_context(
+    predicates: Vec<Expr>,
+    assumptions: &[Expr],
+    depth: usize,
+    remaining: &mut usize,
+) -> Result<Vec<Expr>> {
+    let predicates = simplify_conjunction(predicates)?;
+    if predicates.iter().any(is_false) {
+        return Ok(always_false());
+    }
+    let has_disjunction = predicates.iter().any(|expr| {
+        matches!(
+            expr,
+            Expr::BinaryExpr(BinaryExpr {
+                op: Operator::Or,
+                ..
+            })
+        )
+    });
+    if assumptions.is_empty() && !has_disjunction {
+        return Ok(predicates);
+    }
+    let cost = assumptions.len().saturating_add(predicates.len());
+    if depth >= MAX_DISJUNCTION_DEPTH || cost > *remaining {
+        return Ok(predicates);
+    }
+    *remaining -= cost;
+
+    let context = assumptions
+        .iter()
+        .chain(predicates.iter().filter(|expr| is_column_comparison(expr)))
+        .cloned()
+        .collect();
+    let context = simplify_conjunction(context)?;
+    if context.iter().any(is_false) {
+        return Ok(always_false());
+    }
+
+    let mut result = Vec::with_capacity(predicates.len());
+    for predicate in predicates {
+        let predicate = simplify_disjunction(predicate, &context, depth, remaining)?;
+        if is_false(&predicate) {
+            return Ok(always_false());
+        }
+        result.push(predicate);
+    }
+    Ok(result)
+}
+
+fn simplify_disjunction(

Review Comment:
   `simplify_disjunction` splits one binary `OR` and recurses with `depth + 1`, so a left-deep `a OR b OR c ...` spends one depth level per disjunct. Disjuncts past `MAX_DISJUNCTION_DEPTH` are never checked: `x >= 5000 AND (<120 disjoint ranges below 5000>)` still keeps 27 impossible disjuncts (and the scan) after the default 3 passes, and the result depends on `max_passes`. Flattening the chain makes depth count AND/OR nesting only. With the change below that query plans to `EmptyRelation`, and `predicates.slt` / `simplify_predicate*.slt` still pass.
   
   ```diff
   -    let Expr::BinaryExpr(BinaryExpr {
   -        left,
   -        op: Operator::Or,
   -        right,
   -    }) = predicate
   -    else {
   -        return Ok(predicate);
   -    };
   +    if !matches!(
   +        predicate,
   +        Expr::BinaryExpr(BinaryExpr {
   +            op: Operator::Or,
   +            ..
   +        })
   +    ) {
   +        return Ok(predicate);
   +    }
        ...
   -    let left = simplify_branch(*left)?;
   -    let right = simplify_branch(*right)?;
   -    Ok(if is_false(&left) {
   -        right
   -    } else if is_false(&right) {
   -        left
   -    } else {
   -        left.or(right)
   -    })
   +    // Flatten `a OR b OR c` so the depth limit counts AND/OR nesting, not disjuncts.
   +    let mut branches = Vec::new();
   +    for branch in split_binary_owned(predicate, Operator::Or) {
   +        let branch = simplify_branch(branch)?;
   +        if !is_false(&branch) {
   +            branches.push(branch);
   +        }
   +    }
   +    Ok(disjunction(branches).unwrap_or_else(|| lit(false)))
   ```



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 merged PR #26132:
URL: https://github.com/apache/datafusion/pull/26132


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #26132:
URL: https://github.com/apache/datafusion/pull/26132#issuecomment-6054733809

   ## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/26132?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
   :x: Patch coverage is `91.13924%` with `14 lines` in your changes missing coverage. Please review.
   :white_check_mark: Project coverage is 82.74%. Comparing base ([`102a162`](https://app.codecov.io/gh/apache/datafusion/commit/102a1628592121d96bfe3d09d80e63180eef288a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`df8872d`](https://app.codecov.io/gh/apache/datafusion/commit/df8872dca9bc16e551e52c62b1198e0465b99d0a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
   
   | [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/26132?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
   |---|---|---|
   | [...er/src/simplify\_expressions/simplify\_predicates.rs](https://app.codecov.io/gh/apache/datafusion/pull/26132?src=pr&el=tree&filepath=datafusion%2Foptimizer%2Fsrc%2Fsimplify_expressions%2Fsimplify_predicates.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9vcHRpbWl6ZXIvc3JjL3NpbXBsaWZ5X2V4cHJlc3Npb25zL3NpbXBsaWZ5X3ByZWRpY2F0ZXMucnM=) | 90.29% | [1 Missing and 9 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26132?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
   | [datafusion/optimizer/src/push\_down\_filter.rs](https://app.codecov.io/gh/apache/datafusion/pull/26132?src=pr&el=tree&filepath=datafusion%2Foptimizer%2Fsrc%2Fpush_down_filter.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9vcHRpbWl6ZXIvc3JjL3B1c2hfZG93bl9maWx0ZXIucnM=) | 92.72% | [4 Missing :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26132?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
   
   <details><summary>Additional details and impacted files</summary>
   
   
   
   ```diff
   @@           Coverage Diff            @@
   ##             main   #26132    +/-   ##
   ========================================
     Coverage   82.74%   82.74%            
   ========================================
     Files        1147     1147            
     Lines      449767   449909   +142     
     Branches   449767   449909   +142     
   ========================================
   + Hits       372157   372279   +122     
   - Misses      54942    54952    +10     
   - Partials    22668    22678    +10     
   ```
   </details>
   
   [:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/26132?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).   
   :loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
   <details><summary> :rocket: New features to boost your workflow: </summary>
   
   - :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
   - :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
   </details>


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #26132:
URL: https://github.com/apache/datafusion/pull/26132#issuecomment-6145056494

   🚀 


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat: simplify contradictory ranges across AND/OR predicates [datafusion]

Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on code in PR #26132:
URL: https://github.com/apache/datafusion/pull/26132#discussion_r4236254608


##########
datafusion/optimizer/src/simplify_expressions/simplify_predicates.rs:
##########
@@ -29,25 +29,143 @@
 
 use super::utils::{is_false, is_null};
 use datafusion_common::utils::normalize_float_zero_scalar;
-use datafusion_common::{Column, Result, ScalarValue, internal_err};
+use datafusion_common::{Column, DataFusionError, Result, ScalarValue, internal_err};
+use datafusion_expr::utils::{conjunction, split_conjunction_owned};
 use datafusion_expr::{BinaryExpr, Expr, Operator, lit};
+use indexmap::IndexSet;
 use std::cmp::Ordering;
 use std::collections::BTreeMap;
 
+const MAX_DISJUNCTION_WORK: usize = 4096;
+const MAX_DISJUNCTION_DEPTH: usize = 32;
+
 /// Simplifies a list of predicates by removing redundancies.
 ///
 /// This function takes a vector of predicate expressions and groups them by the column they reference.
 /// Predicates that reference a single column and are comparison operations (e.g., >, >=, <, <=, =, !=)
 /// are analyzed to remove redundant conditions. For instance, `x > 5 AND x > 6` is simplified to
 /// `x > 6`. Predicates that contradict each other, such as `x > 6 AND x < 5`, reduce the whole
 /// conjunction to `false`. Other predicates that do not fit this pattern are retained as-is.
+/// Comparisons in an enclosing conjunction also constrain each branch of an `OR`:
+/// `x >= 10 AND (x < 3 OR x < 7)` cannot be true. This simplification preserves
+/// which rows pass a filter, rather than Boolean values in projection expressions.
 ///
 /// # Arguments
 /// * `predicates` - A vector of `Expr` representing the predicates to simplify.
 ///
 /// # Returns
 /// A `Result` containing a vector of simplified `Expr` predicates.
 pub fn simplify_predicates(predicates: Vec<Expr>) -> Result<Vec<Expr>> {
+    let mut remaining = MAX_DISJUNCTION_WORK;
+    simplify_with_context(predicates, &[], 0, &mut remaining)
+}
+
+/// Only descend through positive AND/OR expressions. In particular, replacing a
+/// nullable, unsatisfiable predicate with false below NOT would change its truth set.
+/// Keep assumptions outside the expressions they simplify, and never distribute
+/// conjunctions over disjunctions. The budget bounds repeated comparison work.
+fn simplify_with_context(
+    predicates: Vec<Expr>,
+    assumptions: &[Expr],
+    depth: usize,
+    remaining: &mut usize,
+) -> Result<Vec<Expr>> {
+    let predicates = simplify_conjunction(predicates)?;
+    if predicates.iter().any(is_false) {
+        return Ok(always_false());
+    }
+    let has_disjunction = predicates.iter().any(|expr| {
+        matches!(
+            expr,
+            Expr::BinaryExpr(BinaryExpr {
+                op: Operator::Or,
+                ..
+            })
+        )
+    });
+    if assumptions.is_empty() && !has_disjunction {
+        return Ok(predicates);
+    }
+    let cost = assumptions.len().saturating_add(predicates.len());
+    if depth >= MAX_DISJUNCTION_DEPTH || cost > *remaining {
+        return Ok(predicates);
+    }
+    *remaining -= cost;
+
+    let context = assumptions
+        .iter()
+        .chain(predicates.iter().filter(|expr| is_column_comparison(expr)))
+        .cloned()
+        .collect();
+    let context = simplify_conjunction(context)?;
+    if context.iter().any(is_false) {
+        return Ok(always_false());
+    }
+
+    let mut result = Vec::with_capacity(predicates.len());
+    for predicate in predicates {
+        let predicate = simplify_disjunction(predicate, &context, depth, remaining)?;
+        if is_false(&predicate) {
+            return Ok(always_false());
+        }
+        result.push(predicate);
+    }
+    Ok(result)
+}
+
+fn simplify_disjunction(

Review Comment:
   done https://github.com/apache/datafusion/pull/26132/changes/f2972d2d1a2fbb0f7853b8aa1ccc07e5892a43ec



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org