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: [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]
