Skip to content

Commit 27ad523

Browse files
fix(physical-expr): stop false infeasibility report from Eq+FALSE in cp_solver
propagate_comparison for Operator::Eq with parent == Interval::FALSE returned Ok(None), which ExprIntervalGraph::propagate_constraints interprets as infeasible. The correct semantics is that a = b being certainly false means a != b, which excludes at most a single point from each operand. Interval arithmetic cannot represent a hole, so the children cannot be refined further, but the expression is not infeasible. This caused analyze() to return None for the column interval when the predicate was NOT (a = 0.0) and the input domain contained 0.0 but was not equal to it (e.g. a in [-1, 1]). The None is documented in ExprBoundaries::interval to mean "evaluating the given column results in an empty set", but NOT (a = 0.0) is true for every a != 0, so the correct result is the full input domain. This is a contract violation of the public analyze() API, as reported in apache#19264 by an external user calling analyze() to infer bounds for pushdown into another library. The only case that should remain infeasible under Eq + FALSE is when both children are the same single-point interval: then a = b is certainly true, so NOT(a = b) is impossible. All other cases return the children unchanged (Ok(Some((left, right)))) so propagation completes with Success and the column interval is preserved. This guard was agreed on during review of apache#20138 by berkaysynnada and pepijnve. This revives the fix from apache#20138, which was closed as stale after review, and adds direct unit coverage for that guard. No analyze()-level test can reach it: when both children are the same single point the bounds evaluate to FALSE, so update_ranges short-circuits to Infeasible before propagate_constraints runs. Only a direct propagate_comparison call exercises the guard. Tests: - analysis.rs: E2E boundary pair via analyze(). Input [-1,1] is the reported case and does reach the fixed branch; input [0,0] is the nearest-invalid counterpart and must stay infeasible. - cp_solver.rs: direct propagate_comparison unit tests for Eq + FALSE covering identical singletons (infeasible), different singletons (feasible), overlapping intervals, and the [-1,1] vs [0,0] case from the issue. Negative control on baseline a1f64e9 with the production arm reverted to Ok(None): 3 of the 4 new tests fail, including the E2E test_analyze_not_eq_around_zero. test_analyze_not_eq_clamped_at_zero passes on baseline as well, so it is a boundary guard rather than evidence of the fix. Closes apache#19264. Co-authored-by: evangelisilva <[email protected]>
1 parent a1f64e9 commit 27ad523

2 files changed

Lines changed: 137 additions & 2 deletions

File tree

‎datafusion/physical-expr/src/analysis.rs‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -344,6 +344,7 @@ fn calculate_selectivity(
344344

345345
#[cfg(test)]
346346
mod tests {
347+
use std::ops::Not;
347348
use std::sync::Arc;
348349

349350
use arrow::datatypes::{DataType, Field, Schema};
@@ -589,4 +590,69 @@ mod tests {
589590

590591
let _ = selectivity; // silence unused warning
591592
}
593+
594+
// Regression test for #19264: `NOT (a = 0.0)` analysis is incorrect.
595+
//
596+
// The `analyze` function uses constraint propagation through `NotExpr::propagate_constraints`.
597+
// For `NOT (a = 0.0)` over input domain [-1, 1], the result should be the
598+
// full input domain (NOT can be true everywhere except at 0.0), but the
599+
// current implementation returns `None` (claiming infeasibility).
600+
fn analyze_not_eq_helper(
601+
lower: f32,
602+
upper: f32,
603+
) -> datafusion_common::Result<Option<Interval>> {
604+
let schema = Arc::new(Schema::new(vec![make_field("a", DataType::Float32)]));
605+
let df_schema = DFSchema::try_from(Arc::clone(&schema)).unwrap();
606+
607+
// Input column bounds: [lower, upper]
608+
let boundaries = vec![ExprBoundaries {
609+
column: Column::new("a", 0),
610+
interval: Some(Interval::try_new(
611+
ScalarValue::Float32(Some(lower)),
612+
ScalarValue::Float32(Some(upper)),
613+
)?),
614+
distinct_count: Precision::Inexact(100),
615+
}];
616+
let ctx = AnalysisContext::new(boundaries);
617+
618+
// Predicate: NOT (a = 0.0)
619+
let pred_not_eq = col("a").eq(lit(0.0f32)).not();
620+
let phys_not = create_physical_expr(
621+
&pred_not_eq,
622+
&df_schema,
623+
&ExecutionProps::new(),
624+
&PhysicalPlanningContext::default(),
625+
)?;
626+
let out = analyze(&phys_not, ctx, df_schema.as_ref())?;
627+
Ok(out.boundaries[0].interval.clone())
628+
}
629+
630+
#[test]
631+
fn test_analyze_not_eq_around_zero() -> datafusion_common::Result<()> {
632+
// Input domain [-1, 1] contains 0.0.
633+
// `NOT (a = 0.0)` can be true everywhere except at 0.0, so the output
634+
// interval should be the full input domain [-1, 1], NOT None.
635+
let out = analyze_not_eq_helper(-1.0, 1.0)?;
636+
let expected = Some(Interval::try_new(
637+
ScalarValue::Float32(Some(-1.0)),
638+
ScalarValue::Float32(Some(1.0)),
639+
)?);
640+
assert_eq!(
641+
out, expected,
642+
"NOT (a = 0.0) over [-1, 1] should yield [-1, 1], got {out:?}"
643+
);
644+
Ok(())
645+
}
646+
647+
#[test]
648+
fn test_analyze_not_eq_clamped_at_zero() -> datafusion_common::Result<()> {
649+
// Input domain [0, 0] is exactly the point where a = 0.0 is true.
650+
// `NOT (a = 0.0)` is always false here, so the output interval should be None.
651+
let out = analyze_not_eq_helper(0.0, 0.0)?;
652+
assert_eq!(
653+
out, None,
654+
"NOT (a = 0.0) over [0, 0] should yield None (infeasible), got {out:?}"
655+
);
656+
Ok(())
657+
}
592658
}

‎datafusion/physical-expr/src/intervals/cp_solver.rs‎

Lines changed: 71 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -363,8 +363,25 @@ pub fn propagate_comparison(
363363
} else if parent == &Interval::FALSE {
364364
match op {
365365
Operator::Eq => {
366-
// TODO: Propagation is not possible until we support interval sets.
367-
Ok(None)
366+
// `a = b` being certainly false means `a != b`, which excludes
367+
// at most a single point. Interval arithmetic cannot represent
368+
// a "hole", so we cannot refine the children. Return them
369+
// unchanged rather than `None`, which the caller interprets as
370+
// infeasible (see issue #19264).
371+
//
372+
// The one exception is when both children are the same
373+
// single-point interval: then `a = b` is certainly true, so
374+
// `NOT(a = b)` is infeasible. This preserves the only case
375+
// the previous `Ok(None)` correctly identified, as discussed
376+
// in PR #20138.
377+
if !left_child.is_unbounded()
378+
&& left_child == right_child
379+
&& left_child.lower() == left_child.upper()
380+
{
381+
Ok(None)
382+
} else {
383+
Ok(Some((left_child.clone(), right_child.clone())))
384+
}
368385
}
369386
Operator::Gt => satisfy_greater(right_child, left_child, false),
370387
Operator::GtEq => satisfy_greater(right_child, left_child, true),
@@ -1621,6 +1638,58 @@ mod tests {
16211638
Ok(())
16221639
}
16231640

1641+
#[test]
1642+
fn test_propagate_eq_false_identical_singletons() -> Result<()> {
1643+
// When both children are the same single-point interval, `a = b` is
1644+
// certainly true, so `NOT(a = b)` (parent = FALSE) is infeasible.
1645+
// This is the only case the `Eq + FALSE` arm should report as
1646+
// infeasible; all other cases over-approximate by leaving the
1647+
// children unchanged. See issue #19264 and PR #20138.
1648+
let left = Interval::make(Some(0_i64), Some(0_i64))?;
1649+
let right = Interval::make(Some(0_i64), Some(0_i64))?;
1650+
assert_eq!(
1651+
None,
1652+
propagate_comparison(&Operator::Eq, &Interval::FALSE, &left, &right)?
1653+
);
1654+
1655+
// Different single points: `a = b` is certainly false, so
1656+
// `NOT(a = b)` is feasible. The children cannot be refined, but must
1657+
// be preserved (not reported as infeasible).
1658+
let left = Interval::make(Some(0_i64), Some(0_i64))?;
1659+
let right = Interval::make(Some(1_i64), Some(1_i64))?;
1660+
assert_eq!(
1661+
Some((left.clone(), right.clone())),
1662+
propagate_comparison(&Operator::Eq, &Interval::FALSE, &left, &right)?
1663+
);
1664+
1665+
Ok(())
1666+
}
1667+
1668+
#[test]
1669+
fn test_propagate_eq_false_overlapping_intervals() -> Result<()> {
1670+
// The case from issue #19264: `a ∈ [-1, 1]`, `b = 0`. `a = b` is
1671+
// possibly true (at a = 0) and possibly false, so `NOT(a = b)` is
1672+
// feasible. Interval arithmetic cannot exclude the single point 0,
1673+
// so the children are returned unchanged rather than as infeasible.
1674+
let left = Interval::make(Some(-1_i64), Some(1_i64))?;
1675+
let right = Interval::make(Some(0_i64), Some(0_i64))?;
1676+
assert_eq!(
1677+
Some((left.clone(), right.clone())),
1678+
propagate_comparison(&Operator::Eq, &Interval::FALSE, &left, &right)?
1679+
);
1680+
1681+
// Overlapping non-singleton intervals: same reasoning, feasible but
1682+
// not refinable.
1683+
let left = Interval::make(Some(-1_i64), Some(1_i64))?;
1684+
let right = Interval::make(Some(0_i64), Some(2_i64))?;
1685+
assert_eq!(
1686+
Some((left.clone(), right.clone())),
1687+
propagate_comparison(&Operator::Eq, &Interval::FALSE, &left, &right)?
1688+
);
1689+
1690+
Ok(())
1691+
}
1692+
16241693
#[test]
16251694
fn test_propagate_or() -> Result<()> {
16261695
let expr = Arc::new(BinaryExpr::new(

0 commit comments

Comments
 (0)