You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by "wangyum (via GitHub)" <gi...@apache.org> on 2026/10/06 14:11:15 UTC

[PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

wangyum opened a new pull request, #59258:
URL: https://github.com/apache/spark/pull/59258

   ### What changes were proposed in this pull request? This PR extends Catalyst constraint propagation to support transitive inequality chaining:
   1. Infers transitive inequality constraints (e.g., a < 5 from a < b and b < 5, a > 5 from a > b and b > 5).
   2. Supports strict and non-strict inequalities (<, <=, >, >=) as well as literal bindings (=).
   3. Propagates range constraints across equi-joins and left-outer joins, enabling partition pruning and data skipping on fact tables (as shown in TPC-H Q12).
   
   ### Why are the changes needed?
   When range conditions connect attributes (e.g., **windowed joins** or **event-attribution queries** such as b.time >= a.time with a.time >= '2020-03-01'), Catalyst previously did not infer the corresponding bound on b.time, leading to full-table scans. This optimization allows pushing down the inferred range filters into data sources.
   
   ### Does this PR introduce any user-facing change? No.
   
   ### How was this patch tested?
   - Added unit tests to InferFiltersFromConstraintsSuite and ConstraintPropagationSuite.
   - Regenerated TPC-H Q12 plan stability golden files.
   - This feature has been running stably in our production environment for more than 6 years. 
   
   ### Was this patch authored or co-authored using generative AI tooling? 
   Generated-by: Cursor (Grok 4.7).
   


-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4268724222


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal

Review Comment:
   Addressed in QueryPlanConstraints.scala:132-139. Corrected the Scaladoc to describe the actual ordering requirement: inferInequalityConstraints must see equalityInferred to chain through equality-derived edges/bounds, and since it produces only inequalities, equality passes gain nothing from re-running on its output. 



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4268732018


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal
+   * binding (an `attr = literal` equality), only new inequalities or substitutions into existing
+   * predicates, so a single downstream call to [[inferInequalityConstraints]] sees every literal
+   * bound they can ever contribute; it does not need to be interleaved with them.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)

Review Comment:
   Addressed. Added SPARK-30768: equality-to-inequality composition in ConstraintPropagationSuite.scala:621-634



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "HyukjinKwon (via GitHub)" <gi...@apache.org>.
HyukjinKwon commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4237130134


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may

Review Comment:
   **Nit (P3):** The cited reason doesn't apply here. Lines 98-100 justify the literal-binding guard by noting that non-binary-stable collations "may equate strings that are binary-distinct, so substituting the literal would change results". That is about substituting through an equality, not about ordering. Chaining never substitutes a value: the inferred bound reuses the candidate's operand and the bound's literal under the same collation-aware comparison. So the comment makes the guard look required when it is really conservative. Keeping the guard is fine.
   
   The comment also says only attribute-to-attribute equality is excluded. The filter at line 164 actually drops every `EqualTo` without a foldable side, including `a + 1 = b`. `inferAdditionalConstraints` handles only Attribute and Cast(Attribute) operands, so no path handles that case, and `a + 1 = b AND b < 5` infers no `a + 1 < 5`.
   
   Could the comment describe the binary-stable restriction on its own terms (e.g. as a conservative choice) and state the full equality exclusion?
   
   **Verification:**
   - **Inspection:** The comment above validComparisons describes the binary-stable restriction with a rationale consistent with the referenced literal-binding comment and describes the full equality exclusion that the filter implements.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may
+    // order values differently than their binary representation would suggest. Attribute-to-
+    // attribute equality is excluded here too: its transitivity is already handled by
+    // inferAdditionalConstraints via substitution, so chaining it here would only re-derive the
+    // same fact as a redundant <= / >= pair instead of the clean substituted equality that path
+    // already produces.
+    val validComparisons = constraints.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&
+          (!b.isInstanceOf[EqualTo] || b.left.foldable || b.right.foldable) &&
+          isBinaryStable(b.left.dataType) && isBinaryStable(b.right.dataType)
+      case _ => false
+    }
+
+    def hasFoldableOperand(e: Expression): Boolean = e match {
+      case BinaryComparison(l, r) => l.foldable || r.foldable
+      case _ => false
+    }
+
+    if (!validComparisons.exists(hasFoldableOperand)) {
+      return ExpressionSet()
+    }
+
+    // Canonicalize comparisons into LessThan / LessThanOrEqual direction. EqualTo is expanded
+    // into both directions, unlike GreaterThan/GreaterThanOrEqual, because an equality acts as
+    // both an upper and a lower bound and the matching below is direction-sensitive on which
+    // side carries the literal.
+    val canonical = validComparisons.flatMap {

Review Comment:
   **Nit (P3):** `validComparisons` is an `ExpressionSet`, so this `flatMap` adds each result through `ExpressionSet.add`, which skips any expression whose canonical form is already present. `EqualTo` canonicalizes by ordering its operands by hash code. That gives `EqualTo(r, l)` the same canonical form as `EqualTo(l, r)`, so it is dropped, and only the orientation the user wrote reaches `bounds`. This contradicts the comment above, which says equality is expanded into both directions. The bound match below is direction-sensitive. As a result, `WHERE a + 1 = 5 AND a + 1 < b` no longer infers `b > 5`, while `WHERE 5 = a + 1 AND a + 1 < b` still does. The join form `x.a + 1 = 5` with `x.a + 1 < y.b` likewise pushes nothing to `y`. The previous revision's `toSet[Expression]` kept both orientations. Results stay correct; the pushdown is silently missed.
   
   The new tests can't catch this. Every equality bound in them is a bare `Attribute = Literal`, for example `$"a" > $"b" && $"b" === 3` in InferFiltersFromConstraintsSuite. For those, `inferConstraintsFromLiteralBindings` derives the same filters by substitution, so the expectations hold even with the reverse orientation gone.
   
   Iterating a `Seq` here (e.g. `validComparisons.toSeq.flatMap`), so that `partition` and the for-comprehension below also run over `Seq`s, keeps both orientations. It also removes the hash ordering still open in the earlier thread on this method.
   
   **Verification:**
   - **Regression:** An optimizer test bounds a non-attribute expression with an equality written in each operand order and asserts that the same transitive bound is inferred for both orders.
   - **Regression:** A Filter whose chaining infers at least five bounds in one pass yields the same inferred-conjunct order when its attributes are re-created with different exprIds, compared without order normalization.
   - **Compatibility:** Existing inequality-inference, constraint-propagation, and q12 plan-stability expectations remain unchanged.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "vboo123 (via GitHub)" <gi...@apache.org>.
vboo123 commented on PR #59258:
URL: https://github.com/apache/spark/pull/59258#issuecomment-6029065318

   I worked through the soundness of the transitive chaining and I think it holds — under Spark's total-order comparison (SQLOrderingUtil.compareDoubles, where NaN == NaN and NaN sorts highest) a NaN can't satisfy the small side of a <, and a NULL makes the original predicate UNKNOWN so the row is already dropped before the inferred bound matters. The one gap I notice: the new tests all assert plan shape (comparePlans / constraints.contains), so none would actually catch an unsound bound that drops a row. Would it be worth a row-level test — a float/double column including NaN, plus a widening-cast case like int < long < lit — to pin the correctness down? Or is that covered somewhere I missed?
   
   


-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4236615625


##########
sql/core/src/test/scala/org/apache/spark/sql/SQLQuerySuite.scala:
##########
@@ -5369,6 +5369,55 @@ class SQLQuerySuite extends SharedSparkSession with AdaptiveSparkPlanHelper
         Seq(Row(0), Row(1), Row(2)))
     }
   }
+
+  test("SPARK-30768: inferred inequality chaining does not drop rows with NaN operands") {

Review Comment:
   add the tests.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "HyukjinKwon (via GitHub)" <gi...@apache.org>.
HyukjinKwon commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4225050761


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may
+    // order values differently than their binary representation would suggest. Attribute-to-
+    // attribute equality is excluded here too: its transitivity is already handled by
+    // inferAdditionalConstraints via substitution, so chaining it here would only re-derive the
+    // same fact as a redundant <= / >= pair instead of the clean substituted equality that path
+    // already produces.
+    val validComparisons = constraints.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.isInstanceOf[EqualNullSafe] &&
+          (!b.isInstanceOf[EqualTo] || b.left.foldable || b.right.foldable) &&
+          isBinaryStable(b.left.dataType) && isBinaryStable(b.right.dataType)
+      case _ => false
+    }
+
+    def hasFoldableOperand(e: Expression): Boolean = e match {
+      case BinaryComparison(l, r) => l.foldable || r.foldable
+      case _ => false
+    }
+
+    if (!validComparisons.exists(hasFoldableOperand)) {
+      return ExpressionSet()
+    }
+
+    // Canonicalize comparisons into LessThan / LessThanOrEqual direction. EqualTo is expanded
+    // into both directions, unlike GreaterThan/GreaterThanOrEqual, because an equality acts as
+    // both an upper and a lower bound and the matching below is direction-sensitive on which
+    // side carries the literal.
+    val canonical = validComparisons.toSet[Expression].flatMap {

Review Comment:
   **Nit (P3):** `toSet[Expression]`, and the `partition` and for-comprehension that follow, switch from the insertion-ordered `ExpressionSet` to Scala `Set`s. Those become hash-ordered `HashSet`s once there are 5 or more elements. Since `AttributeReference.hashCode` includes the exprId, the order of the inferred conjuncts can change between runs of the same query whenever one pass infers two or more bounds. That order carries into EXPLAIN, `PushedFilters`, and generated code. An example is `a < c AND b < c AND c < 10 AND a > 0 AND b > 0`. Plan-stability goldens normalize exprIds but not conjunct order, so such a query would make them flaky. Keeping these as `Seq`s (e.g. `validComparisons.toSeq.flatMap`) would preserve the input order, as the other inference helpers do.
   
   **Verification:**
   - **Regression:** A Filter with at least five chainable comparisons that infers two or more bounds in one pass yields the same inferred-conjunct order when its attributes are re-created with different exprIds, checked without order-normalizing the plan.
   - **Inspection:** inferInequalityConstraints iterates only insertion-ordered collections between validComparisons and the returned ExpressionSet.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may
+    // order values differently than their binary representation would suggest. Attribute-to-
+    // attribute equality is excluded here too: its transitivity is already handled by
+    // inferAdditionalConstraints via substitution, so chaining it here would only re-derive the
+    // same fact as a redundant <= / >= pair instead of the clean substituted equality that path
+    // already produces.
+    val validComparisons = constraints.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.isInstanceOf[EqualNullSafe] &&

Review Comment:
   **Nit (P3):** `validComparisons` checks `deterministic` but not `throwable`, so a comparison whose operand can throw is still chained. `InferFiltersFromConstraints` then materializes the derived bound where the original predicate was never evaluated. For example, in `SELECT * FROM x JOIN y ON x.k = y.k AND CASE WHEN y.v < 0 THEN raise_error('neg') ELSE y.v END < x.b WHERE x.b < 10`, the inferred `CASE ... END < 10` is pushed as a Filter on `y`, so an unmatched `y` row with `v < 0` now fails the query. `PushPredicateThroughJoin` and `CombineFilters` keep throwable predicates in place for this reason. Adding `!b.throwable` here, with a small test, would keep the new chaining consistent with them. The literal-binding path already has the same gap, so guarding where `inferNewFilter` materializes inferred constraints would cover both.
   
   **Verification:**
   - **Regression:** An inner equi-join whose residual compares a raise_error-containing CASE expression with a join attribute that has a literal bound on its own side optimizes with no inferred Filter on the throwable side.
   - **Compatibility:** The existing inequality-inference optimizer, constraint-propagation, and q12 plan-stability expectations remain unchanged.



##########
sql/core/src/test/scala/org/apache/spark/sql/SQLQuerySuite.scala:
##########
@@ -5369,6 +5369,55 @@ class SQLQuerySuite extends SharedSparkSession with AdaptiveSparkPlanHelper
         Seq(Row(0), Row(1), Row(2)))
     }
   }
+
+  test("SPARK-30768: inferred inequality chaining does not drop rows with NaN operands") {

Review Comment:
   **Nit (P3):** This test cannot fail for the case its name describes. Under Spark's NaN-is-largest ordering, every NaN-bearing row already fails `a < b AND b < 3.0`, so the expected `Row(1.0, 2.0)` does not depend on how the inferred `a < 3.0` handles NaN. To pin NaN behavior, add a case where the original predicate keeps a NaN row: for example `a > b AND b > 3.0` over `(Double.NaN, 5.0)`. Then assert that the row survives and that `a > 3.0` is inferred.
   
   **Verification:**
   - **Behavior:** With constraint propagation on and off, `a > b AND b > 3.0` over data containing (NaN, 5.0) returns that row, and the inferred `a > 3.0` is present only when propagation is enabled.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "HyukjinKwon (via GitHub)" <gi...@apache.org>.
HyukjinKwon commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4263387021


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal
+   * binding (an `attr = literal` equality), only new inequalities or substitutions into existing
+   * predicates, so a single downstream call to [[inferInequalityConstraints]] sees every literal
+   * bound they can ever contribute; it does not need to be interleaved with them.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)

Review Comment:
   **Nit (P3):** This line lets chains start from edges or bindings that only the equality passes create, but no added test depends on that. In one `constraints` evaluation, `a = c AND c < b AND b < 5` gives `a < 5` only because `inferAdditionalConstraints` rewrites `c < b` into `a < b`. Likewise `a = 5 AND a = b AND c < b` gives `c < 5` only through the derived `b = 5`. If this line became `inferInequalityConstraints(constraints)`, both bounds would disappear and every added test would still pass. InferFiltersFromConstraintsSuite can't catch it, because its FixedPoint(100) batch re-derives the bound on a later iteration, while production runs 'Infer Filters' Once. A ConstraintPropagationSuite case asserting those two bounds on `plan.constraints` would pin it.
   
   See **Shared repair plan 1** in the review body.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal
+   * binding (an `attr = literal` equality), only new inequalities or substitutions into existing
+   * predicates, so a single downstream call to [[inferInequalityConstraints]] sees every literal
+   * bound they can ever contribute; it does not need to be interleaved with them.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * Infers the full set of constraints derivable by transitively chaining inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`; a longer chain such as `a < b && b < c && c < 5`
+   * derives both `b < 5` and `a < 5` in this same call.
+   *
+   * This is computed as a worklist over a directed bound graph rather than a repeated fixed point
+   * over the full candidate set: each candidate comparison becomes a directed edge once, and each
+   * newly discovered bound is propagated only along its adjacent edges, instead of rescanning the
+   * full candidates x bounds product after every newly inferred bound (which costs O(n^3) on a
+   * sparse n-element chain such as `x1 < x2 < ... < xn < lit`). A site only ever keeps its single
+   * tightest bound per direction, so reaching it via multiple literals (e.g. `b < 5` and `b < 10`
+   * both reaching `a` through `a < b`) converges to one inferred predicate instead of one per
+   * literal; a relaxation only re-enters the worklist when it strictly tightens that site's bound,
+   * which bounds the number of relaxations per site by the number of distinct literals that can
+   * reach it and guarantees termination.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Admits only comparisons between binary-stable types. This is a conservative guard, not a
+    // strict requirement: chaining never substitutes a value the way
+    // inferConstraintsFromLiteralBindings does, it only reuses an operand under the same
+    // collation-aware comparison, so a non-binary-stable collation could in principle still order
+    // consistently with its binary form here. EqualTo is admitted only when at least one side is
+    // foldable (a literal bound); every other EqualTo -- attribute-to-attribute (handled by
+    // inferAdditionalConstraints's transitivity), as well as any other shape without a foldable
+    // side such as `a + 1 = b` -- is excluded, since no inference path below handles a
+    // non-foldable equality operand.
+    val validComparisons = constraints.toSeq.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&
+          (!b.isInstanceOf[EqualTo] || b.left.foldable || b.right.foldable) &&
+          isBinaryStable(b.left.dataType) && isBinaryStable(b.right.dataType)
+      case _ => false
+    }
+
+    def hasFoldableOperand(e: Expression): Boolean = e match {
+      case b: BinaryComparison => b.left.foldable || b.right.foldable
+      case _ => false
+    }
+
+    if (!validComparisons.exists(hasFoldableOperand)) {
+      return ExpressionSet()
+    }
+
+    // Canonicalize comparisons into LessThan / LessThanOrEqual direction. EqualTo is expanded
+    // into both directions, unlike GreaterThan/GreaterThanOrEqual, because an equality acts as
+    // both an upper and a lower bound and the matching below is direction-sensitive on which
+    // side carries the literal. Kept as a Seq, not an ExpressionSet: ExpressionSet canonicalizes
+    // EqualTo(l, r) and EqualTo(r, l) to the same entry and would silently keep only one of the
+    // two directions just expanded.
+    val canonical = validComparisons.flatMap {
+      case GreaterThan(l, r) => LessThan(r, l) :: Nil
+      case GreaterThanOrEqual(l, r) => LessThanOrEqual(r, l) :: Nil
+      case EqualTo(l, r) => EqualTo(l, r) :: EqualTo(r, l) :: Nil
+      case other => other :: Nil
+    }
+
+    val (initialBounds, candidates) = canonical.partition(hasFoldableOperand)
+    if (initialBounds.isEmpty || candidates.isEmpty) return ExpressionSet()
+
+    // A candidate operand is only safe to copy into a newly inferred, single-side filter when
+    // doing so cannot raise an error on rows that never evaluated it before: an attribute
+    // reference, or a lossless (non-truncating, non-failing) widening cast of one. Arbitrary
+    // expressions -- a parsing/narrowing cast, arithmetic that can overflow under ANSI, etc. --
+    // are excluded, since the comparison they came from may have been a cross-side join
+    // condition that only ever ran on matched rows.
+    def isSafeToRelocate(e: Expression): Boolean = e match {
+      case _: Attribute => true
+      case Cast(a: Attribute, toType, _, _) => UpCastRule.canUpCast(a.dataType, toType)
+      case _ => false
+    }
+
+    // Bound represents a known literal bound on `site`: `site {<,<=} lit` when `upper`, or
+    // `lit {<,<=} site` otherwise.
+    case class Bound(upper: Boolean, site: Expression, lit: Expression, strict: Boolean)
+
+    def toBound(e: Expression): Option[Bound] = e match {
+      case b: BinaryComparison =>
+        val strict = b.isInstanceOf[LessThan]
+        if (b.right.foldable) Some(Bound(upper = true, b.left, b.right, strict))

Review Comment:
   **Nit (P3):** `toBound` accepts any foldable operand as the bound's `lit`. The worklist then copies that `lit` into the inferred predicate on the relocated site, and `isTighter` calls `eval()` on it during optimization. `isSafeToRelocate` checks only the edge endpoint, and `!b.throwable` does not flag ANSI casts or arithmetic. `inferConstraintsFromLiteralBindings` runs in the same call and can produce exactly such an operand. With ANSI on:
   
   ```sql
   SELECT * FROM (SELECT * FROM x WHERE s = 'abc') x
   LEFT JOIN y ON x.k = y.k AND y.c < x.b AND x.b < CAST(x.s AS INT)
   ```
   
   Substitution turns the preserved-side ON conjunct into `x.b < CAST('abc' AS INT)`. The `y.c < x.b` edge then relocates it to `y.c < CAST('abc' AS INT)` on the right side, and ConstantFolding raises CAST_INVALID_INPUT during optimization, even when no key-matched pair exists. Before this PR, that left-only conjunct was never pushed for a LeftOuter join. If x's subquery also has `b < 5`, `isTighter` throws inside InferFiltersFromConstraints itself. This is the error-on-unevaluated-rows behavior the relocation guard was added to rule out, reached through the bound operand instead of the edge endpoint. With ANSI off the cast yields NULL and the query is unaffected.
   
   Evaluating the foldable operand once in `toBound`, inside a `NonFatal` guard, would close this: drop the bound if evaluation fails, and keep the evaluated value on `Bound` so `isTighter` compares stored values. The emitted predicate can keep its current operand expression, so existing plan expectations stay the same.
   
   **Verification:**
   - **Regression:** Under ANSI, a left-outer join whose preserved-side ON conjunct substitutes into a failing cast plans and returns the same rows with constraint propagation on and off.
   - **Regression:** A site bounded by both a valid literal and a failing foldable is optimized without an exception and still infers the chained bound from the valid literal.
   - **Compatibility:** Existing inequality-inference, constraint-propagation, and q12 plan-stability expectations remain unchanged.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal

Review Comment:
   **Nit (P3):** This says the equality-based passes never produce a new literal binding. `inferAdditionalConstraints` documents exactly that a few lines above: (`a = 5`, `a = b`) gives `b = 5`. `inferConstraintsFromLiteralBindings` can also produce `b = 5 + 1` from `a = 5` and `b = a + 1`. The code is correct only because line 143 passes `constraints ++ equalityInferred` to the inequality pass. A maintainer who trusts this comment could call `inferInequalityConstraints(constraints)` directly and silently lose chains such as (`a = 5`, `a = b`, `c < b`) => `c < 5`.
   
   Could the comment give the actual reason? The inequality pass has to see the equality passes' output, and because it emits only inequalities, the equality passes gain nothing from re-running on its result.
   
   See **Shared repair plan 1** in the review body.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal
+   * binding (an `attr = literal` equality), only new inequalities or substitutions into existing
+   * predicates, so a single downstream call to [[inferInequalityConstraints]] sees every literal
+   * bound they can ever contribute; it does not need to be interleaved with them.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * Infers the full set of constraints derivable by transitively chaining inequality constraints.

Review Comment:
   **Nit (P3):** This method doesn't infer the full transitive set. It emits only `site op literal` bounds, keeps the single tightest one per direction and site, and bounds only relocatable sites, so `a < c` from `a < b AND b < c` is never produced. Separately, the `isSafeToRelocate` comment at line 208 calls the admitted cast lossless, but `UpCastRule.canUpCast` also admits Long to Float/Double and Timestamp to Long, which lose precision. Relocation is sound because those casts can't fail and the same Cast expression is reused, not because they are lossless. Could both comments state what the code actually guarantees?
   
   **Verification:**
   - **Inspection:** The headline matches the literal-bound, tightest-per-site, relocatable-site behavior, and the relocation comment matches what UpCastRule.canUpCast admits.



##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/InferFiltersFromConstraintsSuite.scala:
##########
@@ -465,4 +465,350 @@ class InferFiltersFromConstraintsSuite extends PlanTest {
     comparePlans(optimized, correctAnswer)
   }
 
+  test("infer inequality constraints: chained inequalities within a single relation") {
+    Seq(($"a" < $"b" && $"b" < 3, $"a" < $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" <= 3, $"a" < $"b" && $"b" <= 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" === 3, $"a" < $"b" && $"b" === 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" < 3, $"a" <= $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" <= 3, $"a" <= $"b" && $"b" <= 3 && $"a" <= 3),
+      ($"a" <= $"b" && $"b" === 3, $"a" <= $"b" && $"b" === 3 && $"a" <= 3),
+      ($"a" > $"b" && $"b" > 3, $"a" > $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" >= 3, $"a" > $"b" && $"b" >= 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" === 3, $"a" > $"b" && $"b" === 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" > 3, $"a" >= $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" >= 3, $"a" >= $"b" && $"b" >= 3 && $"a" >= 3),
+      ($"a" >= $"b" && $"b" === 3, $"a" >= $"b" && $"b" === 3 && $"a" >= 3)
+    ).foreach {
+      case (filter, inferred) =>
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: chained inequality across an equi-join") {
+    Seq(("left.b".attr < "right.b".attr, $"b" < 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" === 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" <= 1, $"b" < 1),
+      ("left.b".attr <= "right.b".attr, $"b" <= 1, $"b" <= 1),
+      ("left.b".attr <= "right.b".attr, $"b" === 1, $"b" <= 1),
+      ("left.b".attr > "right.b".attr, $"b" > 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" === 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" >= 1, $"b" > 1),
+      ("left.b".attr >= "right.b".attr, $"b" >= 1, $"b" >= 1),
+      ("left.b".attr >= "right.b".attr, $"b" === 1, $"b" >= 1)
+    ).foreach {
+      case (cond, filter, inferred) =>
+        val originalLeft = testRelation.subquery("left")
+        val originalRight = testRelation.where(filter).subquery("right")
+
+        val left =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred).subquery("left")
+        val right =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && filter).subquery("right")
+        val condition = Some("left.a".attr === "right.a".attr && cond)
+        testConstraintsAfterJoin(originalLeft, originalRight, left, right, Inner, condition)
+    }
+  }
+
+  test("infer inequality constraints: chained inequalities through an implicit cast") {
+    Seq(($"a" < $"b" && $"b" < 3L, $"a".cast(LongType) < $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" <= 3L, $"a".cast(LongType) < $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" === 3L, $"a".cast(LongType) < $"b" && $"b" === 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" < 3L, $"a".cast(LongType) <= $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" <= 3L, $"a".cast(LongType) <= $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" <= $"b" && $"b" === 3L, $"a".cast(LongType) <= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" < $"b" && $"b" < 3, $"a".cast(LongType) < $"b" && $"b" < Literal(3).cast(LongType)
+        && $"a".cast(LongType) < Literal(3).cast(LongType)),
+      ($"a" > $"b" && $"b" > 3L, $"a".cast(LongType) > $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" >= 3L, $"a".cast(LongType) > $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" === 3L, $"a".cast(LongType) > $"b" && $"b" === 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" > 3L, $"a".cast(LongType) >= $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" >= 3L, $"a".cast(LongType) >= $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" >= $"b" && $"b" === 3L, $"a".cast(LongType) >= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" > $"b" && $"b" > 3, $"a".cast(LongType) > $"b" && $"b" > Literal(3).cast(LongType)
+        && $"a".cast(LongType) > Literal(3).cast(LongType))
+    ).foreach {
+      case (filter, inferred) =>
+        val testRelation = LocalRelation($"a".int, $"b".long)
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: an attr=literal binding on one join side bounds " +
+    "an inequality join key on the other side") {
+    val condition = Some("x.a".attr > "y.a".attr)
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && $"a" === 1).as("x")
+    val optimizedRight = testRelation.where($"a" < 1 && IsNotNull($"a")).as("y")
+    val correct = optimizedLeft.join(optimizedRight, Inner, condition)
+
+    Seq(Literal(1) === $"a", $"a" === Literal(1)).foreach { filter =>
+      val original =
+        testRelation.where(filter).as("x").join(testRelation.as("y"), Inner, condition)
+      comparePlans(Optimize.execute(original.analyze), correct.analyze)
+    }
+  }
+
+  test("infer inequality constraints: a three-attribute chain bounded by a literal") {
+    val original = testRelation.where($"a" < $"b" && $"b" < $"c" && $"c" < 5)
+    val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"a" < $"b" && $"b" < $"c" && $"a" < 5 && $"b" < 5 && $"c" < 5)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: a range join condition combined with a range filter") {
+    val left = testRelation.where($"b" >= 3 && $"b" <= 13).as("x")
+    val right = testRelation.as("y")
+
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b" >= 3 && $"b" <= 13).as("x")
+    val optimizedRight = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"c" > 3 && $"b" <= 13).as("y")
+    val condition = Some("x.a".attr === "y.a".attr
+      && "x.b".attr >= "y.b".attr && "x.b".attr < "y.c".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: chain across a join through an implicit cast") {
+    val testRelation1 = LocalRelation($"a".long, $"b".long, $"c".long).as("x")
+    val testRelation2 = LocalRelation($"a".int, $"b".int, $"c".int).as("y")
+
+    // y.b < 13 inferred from y.b < x.b && x.b <= 13
+    val left = testRelation1.where($"b" <= 13L).as("x")
+    val right = testRelation2.as("y")
+
+    val optimizedLeft =
+      testRelation1.where(IsNotNull($"a") && IsNotNull($"b") && $"b" <= 13L).as("x")
+    val optimizedRight = testRelation2.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b".cast(LongType) < 13L).as("y")
+
+    val condition = Some("x.a".attr === "y.a".attr && "y.b".attr < "x.b".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: range predicate in left-outer join ON clause " +
+    "is pushed to right side when left attr is bounded by inequality") {
+    // Left side: a.k >= 5
+    // Join condition: b.v >= a.k
+    // Transitive inference should deduce b.v >= 5 and push it down to the right side of
+    // LeftOuter join.
+    val left = LocalRelation($"k".int, $"key".int).subquery("a")
+    val right = LocalRelation($"v".int, $"key".int).subquery("b")
+
+    val joinCond = ("a.key".attr === "b.key".attr) && ("b.v".attr >= "a.k".attr)
+    val originalQuery = left
+      .where("a.k".attr >= 5)
+      .join(right, LeftOuter, Some(joinCond))
+      .analyze
+
+    val optimized = Optimize.execute(originalQuery)
+    var pushedToRight = false
+    optimized.foreach {
+      case Join(_, Filter(cond, _), LeftOuter, _, _) =>
+        pushedToRight = splitConjunctivePredicates(cond).exists {
+          case GreaterThanOrEqual(attr: Attribute, Literal(v: Int, IntegerType)) =>
+            attr.name == "v" && v == 5
+          case _ => false
+        }
+      case _ =>
+    }
+    assert(pushedToRight, s"Expected b.v >= 5 pushed to right side; plan was:\n$optimized")
+  }
+
+  test("SPARK-30768: do not infer filters from throwable expressions") {
+    val x = testRelation.where($"b" < 10).subquery("x")
+    val y = testRelation.subquery("y")
+    val raiseErr = new RaiseError(Literal("neg")).cast(IntegerType)
+    val caseExpr = CaseWhen(Seq(("y.b".attr < 0, raiseErr)), elseValue = Some("y.b".attr))
+    val cond = Some("x.a".attr === "y.a".attr && caseExpr < "x.b".attr)
+    val query = x.join(y, Inner, cond).analyze
+    val optimized = Optimize.execute(query)
+    var inferredThrowable = false
+    optimized.foreach {
+      case Join(_, Filter(cond, _), _, _, _) =>
+        inferredThrowable = cond.throwable
+      case _ =>
+    }
+    assert(!inferredThrowable, s"Unexpected throwable filter condition inferred: $optimized")
+  }
+
+  test("SPARK-30768: equality orientation does not affect inequality chaining") {
+    Seq($"a" + 1 === 5, Literal(5) === ($"a" + 1)).foreach { eq =>
+      val original = testRelation.where(eq && ($"a" + 1) < $"b")
+      val optimized = testRelation.where(
+        IsNotNull($"a") && IsNotNull($"b") && eq && ($"a" + 1) < $"b" && $"b" > 5)
+      comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("SPARK-30768: equality orientation does not affect join-side inequality pushdown") {
+    def hasPushedFilter(plan: LogicalPlan)(pred: Expression => Boolean): Boolean = {
+      plan.collectFirst {
+        case Join(_, Filter(cond, _), _, _, _) => splitConjunctivePredicates(cond).exists(pred)
+      }.getOrElse(false)
+    }
+
+    Seq($"a" + 1 === 5, Literal(5) === ($"a" + 1)).foreach { eq =>
+      val x = testRelation.where(eq).subquery("x")
+      val y = testRelation.subquery("y")
+
+      // Upper bound on a + 1 propagates to y.b > 5

Review Comment:
   **Nit (P3):** These two labels are reversed. For `(x.a + 1) < y.b`, `x.a + 1` is not relocatable, so the only edge is the lower edge keyed by `a + 1`, and `y.b > 5` comes from the lower bound `5 <= a + 1`. For `y.b < (x.a + 1)` at line 680, `y.b < 5` comes from the upper bound `a + 1 <= 5`. The assertions are right. Swapping the two comments, and the `optUpper`/`optLower` names, would make the test describe the direction it checks.
   
   **Verification:**
   - **Inspection:** The labels attribute `y.b > 5` to the lower bound and `y.b < 5` to the upper bound on `a + 1`, and the assertions are unchanged.



##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/InferFiltersFromConstraintsSuite.scala:
##########
@@ -465,4 +465,350 @@ class InferFiltersFromConstraintsSuite extends PlanTest {
     comparePlans(optimized, correctAnswer)
   }
 
+  test("infer inequality constraints: chained inequalities within a single relation") {
+    Seq(($"a" < $"b" && $"b" < 3, $"a" < $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" <= 3, $"a" < $"b" && $"b" <= 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" === 3, $"a" < $"b" && $"b" === 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" < 3, $"a" <= $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" <= 3, $"a" <= $"b" && $"b" <= 3 && $"a" <= 3),
+      ($"a" <= $"b" && $"b" === 3, $"a" <= $"b" && $"b" === 3 && $"a" <= 3),
+      ($"a" > $"b" && $"b" > 3, $"a" > $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" >= 3, $"a" > $"b" && $"b" >= 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" === 3, $"a" > $"b" && $"b" === 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" > 3, $"a" >= $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" >= 3, $"a" >= $"b" && $"b" >= 3 && $"a" >= 3),
+      ($"a" >= $"b" && $"b" === 3, $"a" >= $"b" && $"b" === 3 && $"a" >= 3)
+    ).foreach {
+      case (filter, inferred) =>
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: chained inequality across an equi-join") {
+    Seq(("left.b".attr < "right.b".attr, $"b" < 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" === 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" <= 1, $"b" < 1),
+      ("left.b".attr <= "right.b".attr, $"b" <= 1, $"b" <= 1),
+      ("left.b".attr <= "right.b".attr, $"b" === 1, $"b" <= 1),
+      ("left.b".attr > "right.b".attr, $"b" > 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" === 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" >= 1, $"b" > 1),
+      ("left.b".attr >= "right.b".attr, $"b" >= 1, $"b" >= 1),
+      ("left.b".attr >= "right.b".attr, $"b" === 1, $"b" >= 1)
+    ).foreach {
+      case (cond, filter, inferred) =>
+        val originalLeft = testRelation.subquery("left")
+        val originalRight = testRelation.where(filter).subquery("right")
+
+        val left =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred).subquery("left")
+        val right =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && filter).subquery("right")
+        val condition = Some("left.a".attr === "right.a".attr && cond)
+        testConstraintsAfterJoin(originalLeft, originalRight, left, right, Inner, condition)
+    }
+  }
+
+  test("infer inequality constraints: chained inequalities through an implicit cast") {
+    Seq(($"a" < $"b" && $"b" < 3L, $"a".cast(LongType) < $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" <= 3L, $"a".cast(LongType) < $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" === 3L, $"a".cast(LongType) < $"b" && $"b" === 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" < 3L, $"a".cast(LongType) <= $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" <= 3L, $"a".cast(LongType) <= $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" <= $"b" && $"b" === 3L, $"a".cast(LongType) <= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" < $"b" && $"b" < 3, $"a".cast(LongType) < $"b" && $"b" < Literal(3).cast(LongType)
+        && $"a".cast(LongType) < Literal(3).cast(LongType)),
+      ($"a" > $"b" && $"b" > 3L, $"a".cast(LongType) > $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" >= 3L, $"a".cast(LongType) > $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" === 3L, $"a".cast(LongType) > $"b" && $"b" === 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" > 3L, $"a".cast(LongType) >= $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" >= 3L, $"a".cast(LongType) >= $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" >= $"b" && $"b" === 3L, $"a".cast(LongType) >= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" > $"b" && $"b" > 3, $"a".cast(LongType) > $"b" && $"b" > Literal(3).cast(LongType)
+        && $"a".cast(LongType) > Literal(3).cast(LongType))
+    ).foreach {
+      case (filter, inferred) =>
+        val testRelation = LocalRelation($"a".int, $"b".long)
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: an attr=literal binding on one join side bounds " +
+    "an inequality join key on the other side") {
+    val condition = Some("x.a".attr > "y.a".attr)
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && $"a" === 1).as("x")
+    val optimizedRight = testRelation.where($"a" < 1 && IsNotNull($"a")).as("y")
+    val correct = optimizedLeft.join(optimizedRight, Inner, condition)
+
+    Seq(Literal(1) === $"a", $"a" === Literal(1)).foreach { filter =>
+      val original =
+        testRelation.where(filter).as("x").join(testRelation.as("y"), Inner, condition)
+      comparePlans(Optimize.execute(original.analyze), correct.analyze)
+    }
+  }
+
+  test("infer inequality constraints: a three-attribute chain bounded by a literal") {
+    val original = testRelation.where($"a" < $"b" && $"b" < $"c" && $"c" < 5)
+    val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"a" < $"b" && $"b" < $"c" && $"a" < 5 && $"b" < 5 && $"c" < 5)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: a range join condition combined with a range filter") {
+    val left = testRelation.where($"b" >= 3 && $"b" <= 13).as("x")
+    val right = testRelation.as("y")
+
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b" >= 3 && $"b" <= 13).as("x")
+    val optimizedRight = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"c" > 3 && $"b" <= 13).as("y")
+    val condition = Some("x.a".attr === "y.a".attr
+      && "x.b".attr >= "y.b".attr && "x.b".attr < "y.c".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: chain across a join through an implicit cast") {
+    val testRelation1 = LocalRelation($"a".long, $"b".long, $"c".long).as("x")
+    val testRelation2 = LocalRelation($"a".int, $"b".int, $"c".int).as("y")
+
+    // y.b < 13 inferred from y.b < x.b && x.b <= 13
+    val left = testRelation1.where($"b" <= 13L).as("x")
+    val right = testRelation2.as("y")
+
+    val optimizedLeft =
+      testRelation1.where(IsNotNull($"a") && IsNotNull($"b") && $"b" <= 13L).as("x")
+    val optimizedRight = testRelation2.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b".cast(LongType) < 13L).as("y")
+
+    val condition = Some("x.a".attr === "y.a".attr && "y.b".attr < "x.b".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: range predicate in left-outer join ON clause " +
+    "is pushed to right side when left attr is bounded by inequality") {
+    // Left side: a.k >= 5
+    // Join condition: b.v >= a.k
+    // Transitive inference should deduce b.v >= 5 and push it down to the right side of
+    // LeftOuter join.
+    val left = LocalRelation($"k".int, $"key".int).subquery("a")
+    val right = LocalRelation($"v".int, $"key".int).subquery("b")
+
+    val joinCond = ("a.key".attr === "b.key".attr) && ("b.v".attr >= "a.k".attr)
+    val originalQuery = left
+      .where("a.k".attr >= 5)
+      .join(right, LeftOuter, Some(joinCond))
+      .analyze
+
+    val optimized = Optimize.execute(originalQuery)
+    var pushedToRight = false
+    optimized.foreach {
+      case Join(_, Filter(cond, _), LeftOuter, _, _) =>
+        pushedToRight = splitConjunctivePredicates(cond).exists {
+          case GreaterThanOrEqual(attr: Attribute, Literal(v: Int, IntegerType)) =>
+            attr.name == "v" && v == 5
+          case _ => false
+        }
+      case _ =>
+    }
+    assert(pushedToRight, s"Expected b.v >= 5 pushed to right side; plan was:\n$optimized")
+  }
+
+  test("SPARK-30768: do not infer filters from throwable expressions") {

Review Comment:
   **Nit (P3):** Since `isSafeToRelocate` was added, this test no longer exercises `!b.throwable`. Without the guard, `caseExpr < x.b` becomes a candidate edge, but `caseExpr` fails `isSafeToRelocate`, so no upper edge on `x.b` is recorded. There is also no bound on `caseExpr` to propagate, so nothing is inferred and the assertion passes either way.
   
   The guard still matters within one relation. In `Filter(x < caseExpr AND caseExpr < 5)`, `caseExpr` is the bounded site and `x` is relocatable, so without the guard `x < 5` is inferred and prepended. That short-circuits the `raise_error` the original predicate evaluates for rows with `x >= 5`. Using that shape and asserting that no `x < 5` is inferred would give the guard a real regression signal.
   
   **Verification:**
   - **Regression:** A single-relation filter whose throwable expression is bounded by a literal and chained to a relocatable attribute infers no new bound on that attribute.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4268727586


##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/InferFiltersFromConstraintsSuite.scala:
##########
@@ -465,4 +465,350 @@ class InferFiltersFromConstraintsSuite extends PlanTest {
     comparePlans(optimized, correctAnswer)
   }
 
+  test("infer inequality constraints: chained inequalities within a single relation") {
+    Seq(($"a" < $"b" && $"b" < 3, $"a" < $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" <= 3, $"a" < $"b" && $"b" <= 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" === 3, $"a" < $"b" && $"b" === 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" < 3, $"a" <= $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" <= 3, $"a" <= $"b" && $"b" <= 3 && $"a" <= 3),
+      ($"a" <= $"b" && $"b" === 3, $"a" <= $"b" && $"b" === 3 && $"a" <= 3),
+      ($"a" > $"b" && $"b" > 3, $"a" > $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" >= 3, $"a" > $"b" && $"b" >= 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" === 3, $"a" > $"b" && $"b" === 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" > 3, $"a" >= $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" >= 3, $"a" >= $"b" && $"b" >= 3 && $"a" >= 3),
+      ($"a" >= $"b" && $"b" === 3, $"a" >= $"b" && $"b" === 3 && $"a" >= 3)
+    ).foreach {
+      case (filter, inferred) =>
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: chained inequality across an equi-join") {
+    Seq(("left.b".attr < "right.b".attr, $"b" < 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" === 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" <= 1, $"b" < 1),
+      ("left.b".attr <= "right.b".attr, $"b" <= 1, $"b" <= 1),
+      ("left.b".attr <= "right.b".attr, $"b" === 1, $"b" <= 1),
+      ("left.b".attr > "right.b".attr, $"b" > 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" === 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" >= 1, $"b" > 1),
+      ("left.b".attr >= "right.b".attr, $"b" >= 1, $"b" >= 1),
+      ("left.b".attr >= "right.b".attr, $"b" === 1, $"b" >= 1)
+    ).foreach {
+      case (cond, filter, inferred) =>
+        val originalLeft = testRelation.subquery("left")
+        val originalRight = testRelation.where(filter).subquery("right")
+
+        val left =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred).subquery("left")
+        val right =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && filter).subquery("right")
+        val condition = Some("left.a".attr === "right.a".attr && cond)
+        testConstraintsAfterJoin(originalLeft, originalRight, left, right, Inner, condition)
+    }
+  }
+
+  test("infer inequality constraints: chained inequalities through an implicit cast") {
+    Seq(($"a" < $"b" && $"b" < 3L, $"a".cast(LongType) < $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" <= 3L, $"a".cast(LongType) < $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" === 3L, $"a".cast(LongType) < $"b" && $"b" === 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" < 3L, $"a".cast(LongType) <= $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" <= 3L, $"a".cast(LongType) <= $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" <= $"b" && $"b" === 3L, $"a".cast(LongType) <= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" < $"b" && $"b" < 3, $"a".cast(LongType) < $"b" && $"b" < Literal(3).cast(LongType)
+        && $"a".cast(LongType) < Literal(3).cast(LongType)),
+      ($"a" > $"b" && $"b" > 3L, $"a".cast(LongType) > $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" >= 3L, $"a".cast(LongType) > $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" === 3L, $"a".cast(LongType) > $"b" && $"b" === 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" > 3L, $"a".cast(LongType) >= $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" >= 3L, $"a".cast(LongType) >= $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" >= $"b" && $"b" === 3L, $"a".cast(LongType) >= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" > $"b" && $"b" > 3, $"a".cast(LongType) > $"b" && $"b" > Literal(3).cast(LongType)
+        && $"a".cast(LongType) > Literal(3).cast(LongType))
+    ).foreach {
+      case (filter, inferred) =>
+        val testRelation = LocalRelation($"a".int, $"b".long)
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: an attr=literal binding on one join side bounds " +
+    "an inequality join key on the other side") {
+    val condition = Some("x.a".attr > "y.a".attr)
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && $"a" === 1).as("x")
+    val optimizedRight = testRelation.where($"a" < 1 && IsNotNull($"a")).as("y")
+    val correct = optimizedLeft.join(optimizedRight, Inner, condition)
+
+    Seq(Literal(1) === $"a", $"a" === Literal(1)).foreach { filter =>
+      val original =
+        testRelation.where(filter).as("x").join(testRelation.as("y"), Inner, condition)
+      comparePlans(Optimize.execute(original.analyze), correct.analyze)
+    }
+  }
+
+  test("infer inequality constraints: a three-attribute chain bounded by a literal") {
+    val original = testRelation.where($"a" < $"b" && $"b" < $"c" && $"c" < 5)
+    val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"a" < $"b" && $"b" < $"c" && $"a" < 5 && $"b" < 5 && $"c" < 5)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: a range join condition combined with a range filter") {
+    val left = testRelation.where($"b" >= 3 && $"b" <= 13).as("x")
+    val right = testRelation.as("y")
+
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b" >= 3 && $"b" <= 13).as("x")
+    val optimizedRight = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"c" > 3 && $"b" <= 13).as("y")
+    val condition = Some("x.a".attr === "y.a".attr
+      && "x.b".attr >= "y.b".attr && "x.b".attr < "y.c".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: chain across a join through an implicit cast") {
+    val testRelation1 = LocalRelation($"a".long, $"b".long, $"c".long).as("x")
+    val testRelation2 = LocalRelation($"a".int, $"b".int, $"c".int).as("y")
+
+    // y.b < 13 inferred from y.b < x.b && x.b <= 13
+    val left = testRelation1.where($"b" <= 13L).as("x")
+    val right = testRelation2.as("y")
+
+    val optimizedLeft =
+      testRelation1.where(IsNotNull($"a") && IsNotNull($"b") && $"b" <= 13L).as("x")
+    val optimizedRight = testRelation2.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b".cast(LongType) < 13L).as("y")
+
+    val condition = Some("x.a".attr === "y.a".attr && "y.b".attr < "x.b".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: range predicate in left-outer join ON clause " +
+    "is pushed to right side when left attr is bounded by inequality") {
+    // Left side: a.k >= 5
+    // Join condition: b.v >= a.k
+    // Transitive inference should deduce b.v >= 5 and push it down to the right side of
+    // LeftOuter join.
+    val left = LocalRelation($"k".int, $"key".int).subquery("a")
+    val right = LocalRelation($"v".int, $"key".int).subquery("b")
+
+    val joinCond = ("a.key".attr === "b.key".attr) && ("b.v".attr >= "a.k".attr)
+    val originalQuery = left
+      .where("a.k".attr >= 5)
+      .join(right, LeftOuter, Some(joinCond))
+      .analyze
+
+    val optimized = Optimize.execute(originalQuery)
+    var pushedToRight = false
+    optimized.foreach {
+      case Join(_, Filter(cond, _), LeftOuter, _, _) =>
+        pushedToRight = splitConjunctivePredicates(cond).exists {
+          case GreaterThanOrEqual(attr: Attribute, Literal(v: Int, IntegerType)) =>
+            attr.name == "v" && v == 5
+          case _ => false
+        }
+      case _ =>
+    }
+    assert(pushedToRight, s"Expected b.v >= 5 pushed to right side; plan was:\n$optimized")
+  }
+
+  test("SPARK-30768: do not infer filters from throwable expressions") {
+    val x = testRelation.where($"b" < 10).subquery("x")
+    val y = testRelation.subquery("y")
+    val raiseErr = new RaiseError(Literal("neg")).cast(IntegerType)
+    val caseExpr = CaseWhen(Seq(("y.b".attr < 0, raiseErr)), elseValue = Some("y.b".attr))
+    val cond = Some("x.a".attr === "y.a".attr && caseExpr < "x.b".attr)
+    val query = x.join(y, Inner, cond).analyze
+    val optimized = Optimize.execute(query)
+    var inferredThrowable = false
+    optimized.foreach {
+      case Join(_, Filter(cond, _), _, _, _) =>
+        inferredThrowable = cond.throwable
+      case _ =>
+    }
+    assert(!inferredThrowable, s"Unexpected throwable filter condition inferred: $optimized")
+  }
+
+  test("SPARK-30768: equality orientation does not affect inequality chaining") {
+    Seq($"a" + 1 === 5, Literal(5) === ($"a" + 1)).foreach { eq =>
+      val original = testRelation.where(eq && ($"a" + 1) < $"b")
+      val optimized = testRelation.where(
+        IsNotNull($"a") && IsNotNull($"b") && eq && ($"a" + 1) < $"b" && $"b" > 5)
+      comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("SPARK-30768: equality orientation does not affect join-side inequality pushdown") {
+    def hasPushedFilter(plan: LogicalPlan)(pred: Expression => Boolean): Boolean = {
+      plan.collectFirst {
+        case Join(_, Filter(cond, _), _, _, _) => splitConjunctivePredicates(cond).exists(pred)
+      }.getOrElse(false)
+    }
+
+    Seq($"a" + 1 === 5, Literal(5) === ($"a" + 1)).foreach { eq =>
+      val x = testRelation.where(eq).subquery("x")
+      val y = testRelation.subquery("y")
+
+      // Upper bound on a + 1 propagates to y.b > 5

Review Comment:
   Addressed



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4236598475


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may
+    // order values differently than their binary representation would suggest. Attribute-to-
+    // attribute equality is excluded here too: its transitivity is already handled by
+    // inferAdditionalConstraints via substitution, so chaining it here would only re-derive the
+    // same fact as a redundant <= / >= pair instead of the clean substituted equality that path
+    // already produces.
+    val validComparisons = constraints.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.isInstanceOf[EqualNullSafe] &&
+          (!b.isInstanceOf[EqualTo] || b.left.foldable || b.right.foldable) &&
+          isBinaryStable(b.left.dataType) && isBinaryStable(b.right.dataType)
+      case _ => false
+    }
+
+    def hasFoldableOperand(e: Expression): Boolean = e match {
+      case BinaryComparison(l, r) => l.foldable || r.foldable
+      case _ => false
+    }
+
+    if (!validComparisons.exists(hasFoldableOperand)) {
+      return ExpressionSet()
+    }
+
+    // Canonicalize comparisons into LessThan / LessThanOrEqual direction. EqualTo is expanded
+    // into both directions, unlike GreaterThan/GreaterThanOrEqual, because an equality acts as
+    // both an upper and a lower bound and the matching below is direction-sensitive on which
+    // side carries the literal.
+    val canonical = validComparisons.toSet[Expression].flatMap {

Review Comment:
   ok



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on PR #59258:
URL: https://github.com/apache/spark/pull/59258#issuecomment-6040988895

   Added row-level tests in `SQLQuerySuite` to cover both cases:
   1. Floating-point comparisons with `NaN` operands (`a < b AND b < 3.0` over `NaN`, finite values, and boundaries).
   2. Transitive inequality chaining across widening casts (`int < long <= lit`) in a join condition.
   
   Both tests verify that the inferred inequality predicate is generated when `spark.sql.constraintPropagation.enabled` is `true` (and absent when `false`), and assert that query results are identical and preserve all expected rows.


-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4268736592


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal
+   * binding (an `attr = literal` equality), only new inequalities or substitutions into existing
+   * predicates, so a single downstream call to [[inferInequalityConstraints]] sees every literal
+   * bound they can ever contribute; it does not need to be interleaved with them.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * Infers the full set of constraints derivable by transitively chaining inequality constraints.

Review Comment:
   Addressed. Accurately stated that only tightest literal bounds on relocatable sites are inferred, and clarified that relocation is sound because admitted upcasts cannot throw runtime failures and reuse the existing expression.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "HyukjinKwon (via GitHub)" <gi...@apache.org>.
HyukjinKwon commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4270130044


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,229 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality pass must see the equality passes' output
+   * to chain through equality-derived edges and bounds. Because the inequality pass emits only
+   * inequalities, the equality-based passes gain nothing from re-running on its result, so a

Review Comment:
   **Nit (P3):** This says the equality passes gain nothing from re-running on the inequality output, but that doesn't hold for multi-hop equality chains. `inferAdditionalConstraints` does one substitution round, and the inequality pass drops every `EqualTo` without a safe literal side. Take `a = c AND c = d AND d < b AND b < 5`. One round adds only `a = d` and `c < b`, so the inequality pass emits `d < 5` and `c < 5` but never `a < 5`. Re-running the equality pass on `c < 5` with `a = c` would derive it. Production runs Infer Filters once, so `a < 5` is never added as a filter. Results stay correct; only that pushdown is missed.
   
   The `validComparisons` comment at lines 240-241 has the same issue from the other side. It says a non-literal `EqualTo` is excluded "since no inference path below handles a non-literal equality operand". But the canonical step already expands `EqualTo` into both orientations, and the edge loop matches any `BinaryComparison`. An admitted `a + 1 = b` would therefore become non-strict edges that soundly carry a bound across. So the exclusion is a choice, not a limit of the code below.
   
   The "gain nothing" wording came from my suggestion in the previous round, and it was wrong. Could both comments describe the actual boundary instead? One round of the equality passes is followed by one inequality pass, and non-literal equalities are deliberately not used as chaining edges, so multi-hop equality chains can leave a bound uninferred.
   
   **Verification:**
   - **Inspection:** Both comments match the code. One equality substitution round precedes one inequality pass, a two-hop chain such as a = c, c = d, d < b, b < 5 does not infer a < 5, and excluding non-literal EqualTo is described as a design choice consistent with the literal-bounds-only scope.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,229 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality pass must see the equality passes' output
+   * to chain through equality-derived edges and bounds. Because the inequality pass emits only
+   * inequalities, the equality-based passes gain nothing from re-running on its result, so a
+   * single downstream call to [[inferInequalityConstraints]] suffices without interleaving.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * True when `e` cannot raise an error during evaluation: a non-null literal, or an upcast of
+   * one admitted by [[UpCastRule.canUpCast]]. Used by [[inferInequalityConstraints]] to decide
+   * which literals are safe to treat as chain anchors without risking an ANSI eval failure.
+   * Arbitrary expressions (such as a parsing cast `CAST('abc' AS INT)` or arithmetic that can
+   * fail under ANSI) are excluded.
+   */
+  @tailrec
+  private def isSafeBoundLiteral(e: Expression): Boolean = e match {
+    case l: Literal => l.value != null
+    case Cast(child, toType, _, _) =>
+      UpCastRule.canUpCast(child.dataType, toType) && isSafeBoundLiteral(child)
+    case _ => false
+  }
+
+  private def hasBoundOperand(e: Expression): Boolean = e match {
+    case b: BinaryComparison => isSafeBoundLiteral(b.left) || isSafeBoundLiteral(b.right)
+    case _ => false
+  }
+
+  /**
+   * True when `e` is safe to copy into a newly inferred, single-side filter produced by
+   * [[inferInequalityConstraints]] without risking an error on rows that never evaluated it
+   * before: an attribute reference, or an upcast of one admitted by [[UpCastRule.canUpCast]].
+   * While some upcasts may lose precision (e.g. Long to Float/Double), relocation is sound
+   * because they cannot fail and reuse the existing Cast expression. Arbitrary expressions -- a
+   * parsing/narrowing cast, arithmetic that can overflow under ANSI, etc. -- are excluded, since
+   * the comparison they came from may have been a cross-side join condition that only ever ran
+   * on matched rows.
+   */
+  private def isSafeToRelocate(e: Expression): Boolean = e match {
+    case _: Attribute => true
+    case Cast(a: Attribute, toType, _, _) => UpCastRule.canUpCast(a.dataType, toType)
+    case _ => false
+  }
+
+  /**
+   * A known literal bound discovered while chaining inequality constraints in
+   * [[inferInequalityConstraints]]: `site {<,<=} lit` when `upper`, or `lit {<,<=} site`
+   * otherwise. `value` stores the evaluated literal value to avoid repeatedly evaluating `lit`
+   * during optimization.
+   */
+  private case class InequalityBound(
+      upper: Boolean,
+      site: Expression,
+      lit: Expression,
+      strict: Boolean,
+      value: Any)
+
+  /**
+   * Converts a canonicalized comparison into an [[InequalityBound]] when exactly one side is a
+   * safe literal bound ([[isSafeBoundLiteral]]); `None` for attribute-to-attribute comparisons.
+   */
+  private def toBound(e: Expression): Option[InequalityBound] = e match {
+    case b: BinaryComparison =>
+      val strict = b.isInstanceOf[LessThan]
+      if (isSafeBoundLiteral(b.right) && !isSafeBoundLiteral(b.left)) {
+        Some(InequalityBound(upper = true, b.left, b.right, strict, b.right.eval()))
+      } else if (isSafeBoundLiteral(b.left) && !isSafeBoundLiteral(b.right)) {
+        Some(InequalityBound(upper = false, b.right, b.left, strict, b.left.eval()))
+      } else {
+        None
+      }
+    case _ => None
+  }
+
+  /**
+   * Infers tightest literal inequality bounds on relocatable sites by transitively chaining
+   * inequality constraints with literal bounds. For e.g., if an operator has constraints of the
+   * form (`a > b`, `b > 5`), this returns an additional constraint of the form `a > 5`; a longer
+   * chain such as `a < b && b < c && c < 5` derives both `b < 5` and `a < 5` in this same call.
+   * Note that attribute-to-attribute inequalities without literal bounds (e.g., `a < c` from
+   * `a < b && b < c`) are not inferred.
+   *
+   * This is computed as a worklist over a directed bound graph rather than a repeated fixed point
+   * over the full candidate set: each candidate comparison becomes a directed edge once, and each
+   * newly discovered bound is propagated only along its adjacent edges, instead of rescanning the
+   * full candidates x bounds product after every newly inferred bound (which costs O(n^3) on a
+   * sparse n-element chain such as `x1 < x2 < ... < xn < lit`). A site only ever keeps its single
+   * tightest bound per direction, so reaching it via multiple literals (e.g. `b < 5` and `b < 10`
+   * both reaching `a` through `a < b`) converges to one inferred predicate instead of one per
+   * literal; a relaxation only re-enters the worklist when it strictly tightens that site's bound,
+   * which bounds the number of relaxations per site by the number of distinct literals that can
+   * reach it and guarantees termination.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Admits only comparisons between binary-stable types. This is a conservative guard, not a
+    // strict requirement: chaining never substitutes a value the way
+    // inferConstraintsFromLiteralBindings does, it only reuses an operand under the same
+    // collation-aware comparison, so a non-binary-stable collation could in principle still order
+    // consistently with its binary form here. EqualTo is admitted only when at least one side is
+    // a safe literal bound; every other EqualTo -- attribute-to-attribute (handled by
+    // inferAdditionalConstraints's transitivity), as well as any other shape without a safe
+    // literal bound such as `a + 1 = b` -- is excluded, since no inference path below handles a
+    // non-literal equality operand.
+    val validComparisons = constraints.toSeq.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&

Review Comment:
   **Nit (P3):** `b.deterministic` is the only thing that keeps the pass from chaining through a non-deterministic operand. `Filter.validConstraints` keeps non-deterministic conjuncts, and the later `c.deterministic` filters only drop non-deterministic outputs. But no test covers this check. Without it, `WHERE a < rand(0) AND rand(0) < 0.5` on an int column would infer the deterministic `cast(a as double) < 0.5`. Both `rand(0)` instances canonicalize to the same edge key, so the bound on one is chained through the other, even though they are evaluated separately and the original filter doesn't imply it. Every added and existing test still passes with the check removed, because the existing rand tests use `a = rand(0)` or arithmetic sites that the new pass never chains. A small test next to the rewritten throwable one, asserting that this filter infers no bound on `a`, would pin it.
   
   **Verification:**
   - **Regression:** A literal-bounded chain through a non-deterministic operand infers no deterministic bound on the relocatable attribute, and removing the deterministic admission check makes the assertion fail.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal

Review Comment:
   Thanks for updating this. The wording I suggested doesn't fully hold, though. With `a = c AND c = d AND d < b AND b < 5`, one equality round only adds `a = d` and `c < b`, so the inequality pass emits `d < 5` and `c < 5` but never `a < 5`, which re-running the equality pass on its output would derive. I left a separate comment with a suggested rewording.
   
   <!-- SPARK_DEV_REVIEW_REPLY {"feedback_id":"inline:4263387004","thread_id":"inline:4263387004","verdict_sha256":"504ace95b97cc57b766e13a0b73e622f081c281a8659d4632255b64ca45c5d35"} -->



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4237673518


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may
+    // order values differently than their binary representation would suggest. Attribute-to-
+    // attribute equality is excluded here too: its transitivity is already handled by
+    // inferAdditionalConstraints via substitution, so chaining it here would only re-derive the
+    // same fact as a redundant <= / >= pair instead of the clean substituted equality that path
+    // already produces.
+    val validComparisons = constraints.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&

Review Comment:
   **Non-blocking (P2):** `!b.throwable` is not positive evidence that the operand is safe to evaluate on additional rows: ordinary ANSI casts and arithmetic can fail while inheriting `throwable = false`. A cross-side residual such as `CAST(x.s AS INT) < y.b`, combined with `y.b < 5`, now derives a child filter `CAST(x.s AS INT) < 5`; an unmatched `x` row that never evaluated the residual before can therefore raise `CAST_INVALID_INPUT`. This changes query behavior for inner, left-outer, and left-anti paths rather than merely adding a pushdown.
   
   **Verification:**
   - **Regression:** Execute an ANSI parsing-cast range predicate with unmatched keys through inner, outer, and anti join relocation paths and verify that enabling constraint propagation neither evaluates the cast on previously unevaluated rows nor changes the result.
   - **Compatibility:** Verify that a lossless numeric widening comparison still derives and pushes its range bound, while parsing, narrowing, arithmetic, and unknown-expression operands do not.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)

Review Comment:
   **Blocking (P1):** This fixed point rescans the full candidates-by-bounds product after every newly discovered bound. For `x1 < x2 < ... < xn < L`, only one bound advances per round, but all `n - 1` candidates are compared with every settled bound each time, yielding Theta(n^3) semantic comparisons (about 500 million at `n = 1000`) before execution. Because constraint propagation is enabled by default and the input width is unbounded, wide generated predicates can make planning impractical even when the inferred filters provide no I/O benefit.
   
   **Recommended change:** Replace the recursive full-set fixed point with an endpoint-indexed directed work list. Normalize each inequality into a directed edge with strictness metadata, expand a foldable equality into both directed bounds outside ExpressionSet canonical membership, seed the queue with equality- and literal-derived bounds, and propagate only newly discovered semantic bounds along adjacent edges. Convert results back to ExpressionSet only at the output boundary. Add mixed-chain spelling regressions and a wide sparse-chain workload that detects settled-pair rescanning.
   
   **Why this works:** A directed record preserves the endpoint orientation that commutative EqualTo canonicalization loses. An adjacency index finds only edges whose endpoint matches a newly queued upper or lower bound; the derived edge is strict when either input edge is strict, and a semantic-key set prevents cycles and duplicate work. Each discovered bound is processed once instead of rebuilding and crossing the complete closure on every depth step.
   
   **Scope:** Make inequality closure explicitly directed and incremental while preserving the public ExpressionSet result and both existing production call routes.
   
   **Compatibility:** Constraint propagation continues to infer the complete supported transitive range closure when enabled, including safe literal-equality and widening-cast chains, and produces no added bounds when disabled.
   
   **Risks:** An incorrect semantic key can merge distinct typed or collated bounds or fail to terminate on cycles. Strictness can be weakened if a path containing one strict comparison is combined incorrectly. Multiple incomparable literal bounds can still require output-proportional work even after avoidable rescans are removed.
   
   **Constraints:** Preserve all currently supported strict, non-strict, upper, lower, equality-bound, cast-coercion, and collation admission semantics except where a separate safety repair narrows unsafe expressions. Keep spark.sql.constraintPropagation.enabled as the existing switch and preserve legacy no-inference behavior when it is disabled. Return canonical ExpressionSet predicates to callers so downstream constraint and filter consumers keep their existing contract.
   
   **Success:** Mixed equality/inequality chains derive the same bound for both SQL equality operand orders. Every newly discovered directed bound is expanded once; advancing chain depth does not trigger a Cartesian rescan of all settled candidates and bounds. Strictness and direction of every emitted upper or lower bound match the composed path. Plan-local constraints and join-side pushed filters observe the same complete canonical closure.
   
   **Verification:**
   - **Regression:** Exercise equality-derived literal bounds followed by inequality edges in both equality operand orders and verify identical inferred upper and lower bounds through both plan-local and join-side propagation.
   - **Behavior:** Cover combinations of strict and non-strict edges, cycles, multiple paths, and multiple foldable bounds and verify the exact directed closure without duplicate predicates.
   - **Regression:** Build a wide sparse chain with one terminal literal bound and verify planning completes within a bounded workload that would expose full settled-set rescanning rather than relying on a small three-edge example.
   - **Inspection:** Confirm the traversal indexes edges by endpoint, queues only newly discovered semantic bounds, and has no loop that recomputes the full candidates-by-bounds product at each fixed-point depth.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4236597845


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +125,92 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality step is iterated to a fixed point because a
+   * single pass only chains pairs present in the input set: e.g. `a < b && b < c && c < 5`
+   * requires one pass to derive `b < 5` and a second to derive `a < 5` from it.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    @tailrec
+    def chainInequalities(inferred: ExpressionSet): ExpressionSet = {
+      val newlyInferred = inferInequalityConstraints(constraints ++ inferred)
+      if (newlyInferred.isEmpty) inferred else chainInequalities(inferred ++ newlyInferred)
+    }
+
+    chainInequalities(
+      inferAdditionalConstraints(constraints) ++
+        inferConstraintsFromLiteralBindings(constraints))
+  }
+
+  /**
+   * Infers an additional set of constraints from a given set of inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Substituting through a comparison is only safe under binary-stable collations, for the
+    // same reason as in inferConstraintsFromLiteralBindings: non-binary-stable collations may
+    // order values differently than their binary representation would suggest. Attribute-to-
+    // attribute equality is excluded here too: its transitivity is already handled by
+    // inferAdditionalConstraints via substitution, so chaining it here would only re-derive the
+    // same fact as a redundant <= / >= pair instead of the clean substituted equality that path
+    // already produces.
+    val validComparisons = constraints.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.isInstanceOf[EqualNullSafe] &&

Review Comment:
   good catch



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4236615625


##########
sql/core/src/test/scala/org/apache/spark/sql/SQLQuerySuite.scala:
##########
@@ -5369,6 +5369,55 @@ class SQLQuerySuite extends SharedSparkSession with AdaptiveSparkPlanHelper
         Seq(Row(0), Row(1), Row(2)))
     }
   }
+
+  test("SPARK-30768: inferred inequality chaining does not drop rows with NaN operands") {

Review Comment:
   added the test.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4272953577


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,229 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality pass must see the equality passes' output
+   * to chain through equality-derived edges and bounds. Because the inequality pass emits only
+   * inequalities, the equality-based passes gain nothing from re-running on its result, so a

Review Comment:
   Updated the doc



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,229 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The inequality pass must see the equality passes' output
+   * to chain through equality-derived edges and bounds. Because the inequality pass emits only
+   * inequalities, the equality-based passes gain nothing from re-running on its result, so a
+   * single downstream call to [[inferInequalityConstraints]] suffices without interleaving.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * True when `e` cannot raise an error during evaluation: a non-null literal, or an upcast of
+   * one admitted by [[UpCastRule.canUpCast]]. Used by [[inferInequalityConstraints]] to decide
+   * which literals are safe to treat as chain anchors without risking an ANSI eval failure.
+   * Arbitrary expressions (such as a parsing cast `CAST('abc' AS INT)` or arithmetic that can
+   * fail under ANSI) are excluded.
+   */
+  @tailrec
+  private def isSafeBoundLiteral(e: Expression): Boolean = e match {
+    case l: Literal => l.value != null
+    case Cast(child, toType, _, _) =>
+      UpCastRule.canUpCast(child.dataType, toType) && isSafeBoundLiteral(child)
+    case _ => false
+  }
+
+  private def hasBoundOperand(e: Expression): Boolean = e match {
+    case b: BinaryComparison => isSafeBoundLiteral(b.left) || isSafeBoundLiteral(b.right)
+    case _ => false
+  }
+
+  /**
+   * True when `e` is safe to copy into a newly inferred, single-side filter produced by
+   * [[inferInequalityConstraints]] without risking an error on rows that never evaluated it
+   * before: an attribute reference, or an upcast of one admitted by [[UpCastRule.canUpCast]].
+   * While some upcasts may lose precision (e.g. Long to Float/Double), relocation is sound
+   * because they cannot fail and reuse the existing Cast expression. Arbitrary expressions -- a
+   * parsing/narrowing cast, arithmetic that can overflow under ANSI, etc. -- are excluded, since
+   * the comparison they came from may have been a cross-side join condition that only ever ran
+   * on matched rows.
+   */
+  private def isSafeToRelocate(e: Expression): Boolean = e match {
+    case _: Attribute => true
+    case Cast(a: Attribute, toType, _, _) => UpCastRule.canUpCast(a.dataType, toType)
+    case _ => false
+  }
+
+  /**
+   * A known literal bound discovered while chaining inequality constraints in
+   * [[inferInequalityConstraints]]: `site {<,<=} lit` when `upper`, or `lit {<,<=} site`
+   * otherwise. `value` stores the evaluated literal value to avoid repeatedly evaluating `lit`
+   * during optimization.
+   */
+  private case class InequalityBound(
+      upper: Boolean,
+      site: Expression,
+      lit: Expression,
+      strict: Boolean,
+      value: Any)
+
+  /**
+   * Converts a canonicalized comparison into an [[InequalityBound]] when exactly one side is a
+   * safe literal bound ([[isSafeBoundLiteral]]); `None` for attribute-to-attribute comparisons.
+   */
+  private def toBound(e: Expression): Option[InequalityBound] = e match {
+    case b: BinaryComparison =>
+      val strict = b.isInstanceOf[LessThan]
+      if (isSafeBoundLiteral(b.right) && !isSafeBoundLiteral(b.left)) {
+        Some(InequalityBound(upper = true, b.left, b.right, strict, b.right.eval()))
+      } else if (isSafeBoundLiteral(b.left) && !isSafeBoundLiteral(b.right)) {
+        Some(InequalityBound(upper = false, b.right, b.left, strict, b.left.eval()))
+      } else {
+        None
+      }
+    case _ => None
+  }
+
+  /**
+   * Infers tightest literal inequality bounds on relocatable sites by transitively chaining
+   * inequality constraints with literal bounds. For e.g., if an operator has constraints of the
+   * form (`a > b`, `b > 5`), this returns an additional constraint of the form `a > 5`; a longer
+   * chain such as `a < b && b < c && c < 5` derives both `b < 5` and `a < 5` in this same call.
+   * Note that attribute-to-attribute inequalities without literal bounds (e.g., `a < c` from
+   * `a < b && b < c`) are not inferred.
+   *
+   * This is computed as a worklist over a directed bound graph rather than a repeated fixed point
+   * over the full candidate set: each candidate comparison becomes a directed edge once, and each
+   * newly discovered bound is propagated only along its adjacent edges, instead of rescanning the
+   * full candidates x bounds product after every newly inferred bound (which costs O(n^3) on a
+   * sparse n-element chain such as `x1 < x2 < ... < xn < lit`). A site only ever keeps its single
+   * tightest bound per direction, so reaching it via multiple literals (e.g. `b < 5` and `b < 10`
+   * both reaching `a` through `a < b`) converges to one inferred predicate instead of one per
+   * literal; a relaxation only re-enters the worklist when it strictly tightens that site's bound,
+   * which bounds the number of relaxations per site by the number of distinct literals that can
+   * reach it and guarantees termination.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Admits only comparisons between binary-stable types. This is a conservative guard, not a
+    // strict requirement: chaining never substitutes a value the way
+    // inferConstraintsFromLiteralBindings does, it only reuses an operand under the same
+    // collation-aware comparison, so a non-binary-stable collation could in principle still order
+    // consistently with its binary form here. EqualTo is admitted only when at least one side is
+    // a safe literal bound; every other EqualTo -- attribute-to-attribute (handled by
+    // inferAdditionalConstraints's transitivity), as well as any other shape without a safe
+    // literal bound such as `a + 1 = b` -- is excluded, since no inference path below handles a
+    // non-literal equality operand.
+    val validComparisons = constraints.toSeq.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&

Review Comment:
   add the test



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4268719887


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,189 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers the full additional constraint set for a given set of constraints by combining the
+   * equality-based inferences above ([[inferAdditionalConstraints]],
+   * [[inferConstraintsFromLiteralBindings]]) with transitive inequality chaining
+   * ([[inferInequalityConstraints]]). The two equality-based passes never produce a new literal
+   * binding (an `attr = literal` equality), only new inequalities or substitutions into existing
+   * predicates, so a single downstream call to [[inferInequalityConstraints]] sees every literal
+   * bound they can ever contribute; it does not need to be interleaved with them.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * Infers the full set of constraints derivable by transitively chaining inequality constraints.
+   * For e.g., if an operator has constraints of the form (`a > b`, `b > 5`), this returns an
+   * additional constraint of the form `a > 5`; a longer chain such as `a < b && b < c && c < 5`
+   * derives both `b < 5` and `a < 5` in this same call.
+   *
+   * This is computed as a worklist over a directed bound graph rather than a repeated fixed point
+   * over the full candidate set: each candidate comparison becomes a directed edge once, and each
+   * newly discovered bound is propagated only along its adjacent edges, instead of rescanning the
+   * full candidates x bounds product after every newly inferred bound (which costs O(n^3) on a
+   * sparse n-element chain such as `x1 < x2 < ... < xn < lit`). A site only ever keeps its single
+   * tightest bound per direction, so reaching it via multiple literals (e.g. `b < 5` and `b < 10`
+   * both reaching `a` through `a < b`) converges to one inferred predicate instead of one per
+   * literal; a relaxation only re-enters the worklist when it strictly tightens that site's bound,
+   * which bounds the number of relaxations per site by the number of distinct literals that can
+   * reach it and guarantees termination.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Admits only comparisons between binary-stable types. This is a conservative guard, not a
+    // strict requirement: chaining never substitutes a value the way
+    // inferConstraintsFromLiteralBindings does, it only reuses an operand under the same
+    // collation-aware comparison, so a non-binary-stable collation could in principle still order
+    // consistently with its binary form here. EqualTo is admitted only when at least one side is
+    // foldable (a literal bound); every other EqualTo -- attribute-to-attribute (handled by
+    // inferAdditionalConstraints's transitivity), as well as any other shape without a foldable
+    // side such as `a + 1 = b` -- is excluded, since no inference path below handles a
+    // non-foldable equality operand.
+    val validComparisons = constraints.toSeq.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&
+          (!b.isInstanceOf[EqualTo] || b.left.foldable || b.right.foldable) &&
+          isBinaryStable(b.left.dataType) && isBinaryStable(b.right.dataType)
+      case _ => false
+    }
+
+    def hasFoldableOperand(e: Expression): Boolean = e match {
+      case b: BinaryComparison => b.left.foldable || b.right.foldable
+      case _ => false
+    }
+
+    if (!validComparisons.exists(hasFoldableOperand)) {
+      return ExpressionSet()
+    }
+
+    // Canonicalize comparisons into LessThan / LessThanOrEqual direction. EqualTo is expanded
+    // into both directions, unlike GreaterThan/GreaterThanOrEqual, because an equality acts as
+    // both an upper and a lower bound and the matching below is direction-sensitive on which
+    // side carries the literal. Kept as a Seq, not an ExpressionSet: ExpressionSet canonicalizes
+    // EqualTo(l, r) and EqualTo(r, l) to the same entry and would silently keep only one of the
+    // two directions just expanded.
+    val canonical = validComparisons.flatMap {
+      case GreaterThan(l, r) => LessThan(r, l) :: Nil
+      case GreaterThanOrEqual(l, r) => LessThanOrEqual(r, l) :: Nil
+      case EqualTo(l, r) => EqualTo(l, r) :: EqualTo(r, l) :: Nil
+      case other => other :: Nil
+    }
+
+    val (initialBounds, candidates) = canonical.partition(hasFoldableOperand)
+    if (initialBounds.isEmpty || candidates.isEmpty) return ExpressionSet()
+
+    // A candidate operand is only safe to copy into a newly inferred, single-side filter when
+    // doing so cannot raise an error on rows that never evaluated it before: an attribute
+    // reference, or a lossless (non-truncating, non-failing) widening cast of one. Arbitrary
+    // expressions -- a parsing/narrowing cast, arithmetic that can overflow under ANSI, etc. --
+    // are excluded, since the comparison they came from may have been a cross-side join
+    // condition that only ever ran on matched rows.
+    def isSafeToRelocate(e: Expression): Boolean = e match {
+      case _: Attribute => true
+      case Cast(a: Attribute, toType, _, _) => UpCastRule.canUpCast(a.dataType, toType)
+      case _ => false
+    }
+
+    // Bound represents a known literal bound on `site`: `site {<,<=} lit` when `upper`, or
+    // `lit {<,<=} site` otherwise.
+    case class Bound(upper: Boolean, site: Expression, lit: Expression, strict: Boolean)
+
+    def toBound(e: Expression): Option[Bound] = e match {
+      case b: BinaryComparison =>
+        val strict = b.isInstanceOf[LessThan]
+        if (b.right.foldable) Some(Bound(upper = true, b.left, b.right, strict))

Review Comment:
   Addressed. Instead of swallowing runtime exceptions with try-catch NonFatal, we statically enforce bound safety via isSafeBoundLiteral, allowing only non-null Literals or valid recursive UpCasts. Evaluated literal values are stored on InequalityBound.value (line 188-210), and isTighter (line 302-312) compares them directly.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "wangyum (via GitHub)" <gi...@apache.org>.
wangyum commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4268741546


##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/InferFiltersFromConstraintsSuite.scala:
##########
@@ -465,4 +465,350 @@ class InferFiltersFromConstraintsSuite extends PlanTest {
     comparePlans(optimized, correctAnswer)
   }
 
+  test("infer inequality constraints: chained inequalities within a single relation") {
+    Seq(($"a" < $"b" && $"b" < 3, $"a" < $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" <= 3, $"a" < $"b" && $"b" <= 3 && $"a" < 3),
+      ($"a" < $"b" && $"b" === 3, $"a" < $"b" && $"b" === 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" < 3, $"a" <= $"b" && $"b" < 3 && $"a" < 3),
+      ($"a" <= $"b" && $"b" <= 3, $"a" <= $"b" && $"b" <= 3 && $"a" <= 3),
+      ($"a" <= $"b" && $"b" === 3, $"a" <= $"b" && $"b" === 3 && $"a" <= 3),
+      ($"a" > $"b" && $"b" > 3, $"a" > $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" >= 3, $"a" > $"b" && $"b" >= 3 && $"a" > 3),
+      ($"a" > $"b" && $"b" === 3, $"a" > $"b" && $"b" === 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" > 3, $"a" >= $"b" && $"b" > 3 && $"a" > 3),
+      ($"a" >= $"b" && $"b" >= 3, $"a" >= $"b" && $"b" >= 3 && $"a" >= 3),
+      ($"a" >= $"b" && $"b" === 3, $"a" >= $"b" && $"b" === 3 && $"a" >= 3)
+    ).foreach {
+      case (filter, inferred) =>
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: chained inequality across an equi-join") {
+    Seq(("left.b".attr < "right.b".attr, $"b" < 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" === 1, $"b" < 1),
+      ("left.b".attr < "right.b".attr, $"b" <= 1, $"b" < 1),
+      ("left.b".attr <= "right.b".attr, $"b" <= 1, $"b" <= 1),
+      ("left.b".attr <= "right.b".attr, $"b" === 1, $"b" <= 1),
+      ("left.b".attr > "right.b".attr, $"b" > 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" === 1, $"b" > 1),
+      ("left.b".attr > "right.b".attr, $"b" >= 1, $"b" > 1),
+      ("left.b".attr >= "right.b".attr, $"b" >= 1, $"b" >= 1),
+      ("left.b".attr >= "right.b".attr, $"b" === 1, $"b" >= 1)
+    ).foreach {
+      case (cond, filter, inferred) =>
+        val originalLeft = testRelation.subquery("left")
+        val originalRight = testRelation.where(filter).subquery("right")
+
+        val left =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred).subquery("left")
+        val right =
+          testRelation.where(IsNotNull($"a") && IsNotNull($"b") && filter).subquery("right")
+        val condition = Some("left.a".attr === "right.a".attr && cond)
+        testConstraintsAfterJoin(originalLeft, originalRight, left, right, Inner, condition)
+    }
+  }
+
+  test("infer inequality constraints: chained inequalities through an implicit cast") {
+    Seq(($"a" < $"b" && $"b" < 3L, $"a".cast(LongType) < $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" <= 3L, $"a".cast(LongType) < $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" < $"b" && $"b" === 3L, $"a".cast(LongType) < $"b" && $"b" === 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" < 3L, $"a".cast(LongType) <= $"b" && $"b" < 3L &&
+        $"a".cast(LongType) < 3L),
+      ($"a" <= $"b" && $"b" <= 3L, $"a".cast(LongType) <= $"b" && $"b" <= 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" <= $"b" && $"b" === 3L, $"a".cast(LongType) <= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) <= 3L),
+      ($"a" < $"b" && $"b" < 3, $"a".cast(LongType) < $"b" && $"b" < Literal(3).cast(LongType)
+        && $"a".cast(LongType) < Literal(3).cast(LongType)),
+      ($"a" > $"b" && $"b" > 3L, $"a".cast(LongType) > $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" >= 3L, $"a".cast(LongType) > $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" > $"b" && $"b" === 3L, $"a".cast(LongType) > $"b" && $"b" === 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" > 3L, $"a".cast(LongType) >= $"b" && $"b" > 3L &&
+        $"a".cast(LongType) > 3L),
+      ($"a" >= $"b" && $"b" >= 3L, $"a".cast(LongType) >= $"b" && $"b" >= 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" >= $"b" && $"b" === 3L, $"a".cast(LongType) >= $"b" && $"b" === 3L &&
+        $"a".cast(LongType) >= 3L),
+      ($"a" > $"b" && $"b" > 3, $"a".cast(LongType) > $"b" && $"b" > Literal(3).cast(LongType)
+        && $"a".cast(LongType) > Literal(3).cast(LongType))
+    ).foreach {
+      case (filter, inferred) =>
+        val testRelation = LocalRelation($"a".int, $"b".long)
+        val original = testRelation.where(filter)
+        val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && inferred)
+        comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+    }
+  }
+
+  test("infer inequality constraints: an attr=literal binding on one join side bounds " +
+    "an inequality join key on the other side") {
+    val condition = Some("x.a".attr > "y.a".attr)
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && $"a" === 1).as("x")
+    val optimizedRight = testRelation.where($"a" < 1 && IsNotNull($"a")).as("y")
+    val correct = optimizedLeft.join(optimizedRight, Inner, condition)
+
+    Seq(Literal(1) === $"a", $"a" === Literal(1)).foreach { filter =>
+      val original =
+        testRelation.where(filter).as("x").join(testRelation.as("y"), Inner, condition)
+      comparePlans(Optimize.execute(original.analyze), correct.analyze)
+    }
+  }
+
+  test("infer inequality constraints: a three-attribute chain bounded by a literal") {
+    val original = testRelation.where($"a" < $"b" && $"b" < $"c" && $"c" < 5)
+    val optimized = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"a" < $"b" && $"b" < $"c" && $"a" < 5 && $"b" < 5 && $"c" < 5)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: a range join condition combined with a range filter") {
+    val left = testRelation.where($"b" >= 3 && $"b" <= 13).as("x")
+    val right = testRelation.as("y")
+
+    val optimizedLeft = testRelation.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b" >= 3 && $"b" <= 13).as("x")
+    val optimizedRight = testRelation.where(IsNotNull($"a") && IsNotNull($"b") && IsNotNull($"c")
+      && $"c" > 3 && $"b" <= 13).as("y")
+    val condition = Some("x.a".attr === "y.a".attr
+      && "x.b".attr >= "y.b".attr && "x.b".attr < "y.c".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: chain across a join through an implicit cast") {
+    val testRelation1 = LocalRelation($"a".long, $"b".long, $"c".long).as("x")
+    val testRelation2 = LocalRelation($"a".int, $"b".int, $"c".int).as("y")
+
+    // y.b < 13 inferred from y.b < x.b && x.b <= 13
+    val left = testRelation1.where($"b" <= 13L).as("x")
+    val right = testRelation2.as("y")
+
+    val optimizedLeft =
+      testRelation1.where(IsNotNull($"a") && IsNotNull($"b") && $"b" <= 13L).as("x")
+    val optimizedRight = testRelation2.where(IsNotNull($"a") && IsNotNull($"b")
+      && $"b".cast(LongType) < 13L).as("y")
+
+    val condition = Some("x.a".attr === "y.a".attr && "y.b".attr < "x.b".attr)
+    val original = left.join(right, Inner, condition)
+    val optimized = optimizedLeft.join(optimizedRight, Inner, condition)
+    comparePlans(Optimize.execute(original.analyze), optimized.analyze)
+  }
+
+  test("infer inequality constraints: range predicate in left-outer join ON clause " +
+    "is pushed to right side when left attr is bounded by inequality") {
+    // Left side: a.k >= 5
+    // Join condition: b.v >= a.k
+    // Transitive inference should deduce b.v >= 5 and push it down to the right side of
+    // LeftOuter join.
+    val left = LocalRelation($"k".int, $"key".int).subquery("a")
+    val right = LocalRelation($"v".int, $"key".int).subquery("b")
+
+    val joinCond = ("a.key".attr === "b.key".attr) && ("b.v".attr >= "a.k".attr)
+    val originalQuery = left
+      .where("a.k".attr >= 5)
+      .join(right, LeftOuter, Some(joinCond))
+      .analyze
+
+    val optimized = Optimize.execute(originalQuery)
+    var pushedToRight = false
+    optimized.foreach {
+      case Join(_, Filter(cond, _), LeftOuter, _, _) =>
+        pushedToRight = splitConjunctivePredicates(cond).exists {
+          case GreaterThanOrEqual(attr: Attribute, Literal(v: Int, IntegerType)) =>
+            attr.name == "v" && v == 5
+          case _ => false
+        }
+      case _ =>
+    }
+    assert(pushedToRight, s"Expected b.v >= 5 pushed to right side; plan was:\n$optimized")
+  }
+
+  test("SPARK-30768: do not infer filters from throwable expressions") {

Review Comment:
   Addressed. Rewrote the test to a single-relation filter where the throwable expression is bounded by a literal and chained to relocatable attribute $"a", directly exercising !b.throwable.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org


Re: [PR] [SPARK-30768][SQL] Constraints inferred from inequality attributes [spark]

Posted by "spark-test (via GitHub) via reviews" <re...@spark.apache.org>.
spark-test commented on code in PR #59258:
URL: https://github.com/apache/spark/pull/59258#discussion_r4507090894


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,232 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers additional constraints for a given set of constraints by combining the equality-based
+   * inferences above ([[inferAdditionalConstraints]], [[inferConstraintsFromLiteralBindings]])
+   * with transitive inequality chaining ([[inferInequalityConstraints]]).
+   *
+   * One round of the equality passes is followed by one inequality pass so the latter can chain
+   * through equality-derived edges and bounds. Non-literal equalities are deliberately not used
+   * as chaining edges in [[inferInequalityConstraints]] and the equality passes are not re-run on
+   * the inferred inequalities, so multi-hop equality chains (e.g.
+   * `a = c AND c = d AND d < b AND b < 5`) may leave a bound on `a` uninferred without further
+   * optimization rounds.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * True when `e` cannot raise an error during evaluation: a non-null literal, or an upcast of
+   * one admitted by [[UpCastRule.canUpCast]]. Used by [[inferInequalityConstraints]] to decide
+   * which literals are safe to treat as chain anchors without risking an ANSI eval failure.
+   * Arbitrary expressions (such as a parsing cast `CAST('abc' AS INT)` or arithmetic that can
+   * fail under ANSI) are excluded.
+   */
+  @tailrec
+  private def isSafeBoundLiteral(e: Expression): Boolean = e match {
+    case l: Literal => l.value != null

Review Comment:
   **Nit (P3):** This check is the only thing that keeps NULL literals out of the bound graph. CAST(NULL AS t) reaches it too, through the Cast arm, because canUpCast(NullType, _) is true. None of the tests this PR adds uses a NULL comparison operand, so removing or weakening the check would leave every test green. NULL comparisons can still be unfolded when constraints are computed, for example when EliminateOuterJoin reads a Filter's constraints before NullPropagation runs in the same batch. Without the check, a chain such as `b < a AND a < 'm' AND a < CAST(NULL AS STRING)` makes isTighter compare a null value with the string ordering and fail during optimization, and on primitive sites the null is compared as zero. A ConstraintPropagationSuite case that puts a NULL bound next to a valid one would pin the check.
   
   **Verification:**
   - **Regression:** With the NULL-literal exclusion removed, a chain such as `b < a AND a < 'm' AND a < CAST(NULL AS STRING)` fails the test, either by raising during constraint inference or by inferring a bound against NULL.
   - **Behavior:** With the exclusion in place, the same constraints infer `b < 'm'`, and no inferred constraint compares against a NULL literal.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,232 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers additional constraints for a given set of constraints by combining the equality-based
+   * inferences above ([[inferAdditionalConstraints]], [[inferConstraintsFromLiteralBindings]])
+   * with transitive inequality chaining ([[inferInequalityConstraints]]).
+   *
+   * One round of the equality passes is followed by one inequality pass so the latter can chain
+   * through equality-derived edges and bounds. Non-literal equalities are deliberately not used
+   * as chaining edges in [[inferInequalityConstraints]] and the equality passes are not re-run on
+   * the inferred inequalities, so multi-hop equality chains (e.g.
+   * `a = c AND c = d AND d < b AND b < 5`) may leave a bound on `a` uninferred without further
+   * optimization rounds.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * True when `e` cannot raise an error during evaluation: a non-null literal, or an upcast of
+   * one admitted by [[UpCastRule.canUpCast]]. Used by [[inferInequalityConstraints]] to decide
+   * which literals are safe to treat as chain anchors without risking an ANSI eval failure.
+   * Arbitrary expressions (such as a parsing cast `CAST('abc' AS INT)` or arithmetic that can
+   * fail under ANSI) are excluded.
+   */
+  @tailrec
+  private def isSafeBoundLiteral(e: Expression): Boolean = e match {
+    case l: Literal => l.value != null
+    case Cast(child, toType, _, _) =>
+      UpCastRule.canUpCast(child.dataType, toType) && isSafeBoundLiteral(child)
+    case _ => false
+  }
+
+  private def hasBoundOperand(e: Expression): Boolean = e match {
+    case b: BinaryComparison => isSafeBoundLiteral(b.left) || isSafeBoundLiteral(b.right)
+    case _ => false
+  }
+
+  /**
+   * True when `e` is safe to copy into a newly inferred, single-side filter produced by
+   * [[inferInequalityConstraints]] without risking an error on rows that never evaluated it
+   * before: an attribute reference, or an upcast of one admitted by [[UpCastRule.canUpCast]].
+   * While some upcasts may lose precision (e.g. Long to Float/Double), relocation is sound
+   * because they cannot fail and reuse the existing Cast expression. Arbitrary expressions -- a

Review Comment:
   **Nit (P3):** This comment says admitted up-casts cannot fail, and isSafeBoundLiteral's Scaladoc says an admitted literal cannot raise an error during evaluation, but both guards accept whatever UpCastRule.canUpCast accepts. canUpCast admits DECIMAL(19,0) to BIGINT, because DecimalType.isTighterThan only checks that 19 is below the 20-digit decimal precision of BIGINT, yet under ANSI the cast raises CAST_OVERFLOW for 19-digit values above Long.MaxValue. It also admits DATE to timestamp, which overflows for dates outside the documented 0001-01-01 to 9999-12-31 range. A relocated `CAST(d AS BIGINT) < lit` never runs in default configurations, because UnwrapCastInBinaryComparison later rewrites it onto the uncast decimal, but that protection lives outside these guards. toBound has no such protection. Under ANSI, `(SELECT * FROM x WHERE d = 9999999999999999999) x RIGHT JOIN y ON x.k = y.k AND CAST(x.d AS BIGINT) < y.b` now fails during planning: literal binding turns the condition int
 o `CAST(9999999999999999999 AS BIGINT) < y.b`, and toBound evaluates that cast. The base branch plans this query and fails only if a key-matched pair evaluates the cast; the inner-join form already fails there. Excluding decimal-to-integral casts from both guards and stating the DATE-range assumption in both comments would make the documented contract hold.
   
   This extends existing discussions [1](https://github.com/apache/spark/pull/59258#discussion_r4237673518), [2](https://github.com/apache/spark/pull/59258#discussion_r4263386983), [3](https://github.com/apache/spark/pull/59258#discussion_r4263387034).
   
   **Verification:**
   - **Behavior:** Under ANSI, a chain such as `CAST(x.d AS BIGINT) < y.b AND y.b < 5` with x.d of type DECIMAL(19,0) infers no bound on x. A right outer join whose left side filters x.d to 9999999999999999999 and whose condition includes `CAST(x.d AS BIGINT) < y.b` plans without error, as on the base branch.
   - **Compatibility:** Widening casts such as INT to BIGINT and DATE to TIMESTAMP are still relocated and still infer their existing expected bounds.
   - **Inspection:** The comments on both guards state the admitted cast set and the documented-range assumption for datetime casts, without an unconditional no-failure claim.



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/QueryPlanConstraints.scala:
##########
@@ -126,6 +128,232 @@ trait ConstraintHelper {
     inferred -- constraints
   }
 
+  /**
+   * Infers additional constraints for a given set of constraints by combining the equality-based
+   * inferences above ([[inferAdditionalConstraints]], [[inferConstraintsFromLiteralBindings]])
+   * with transitive inequality chaining ([[inferInequalityConstraints]]).
+   *
+   * One round of the equality passes is followed by one inequality pass so the latter can chain
+   * through equality-derived edges and bounds. Non-literal equalities are deliberately not used
+   * as chaining edges in [[inferInequalityConstraints]] and the equality passes are not re-run on
+   * the inferred inequalities, so multi-hop equality chains (e.g.
+   * `a = c AND c = d AND d < b AND b < 5`) may leave a bound on `a` uninferred without further
+   * optimization rounds.
+   */
+  def inferAllAdditionalConstraints(constraints: ExpressionSet): ExpressionSet = {
+    val equalityInferred =
+      inferAdditionalConstraints(constraints) ++ inferConstraintsFromLiteralBindings(constraints)
+    equalityInferred ++ inferInequalityConstraints(constraints ++ equalityInferred)
+  }
+
+  /**
+   * True when `e` cannot raise an error during evaluation: a non-null literal, or an upcast of
+   * one admitted by [[UpCastRule.canUpCast]]. Used by [[inferInequalityConstraints]] to decide
+   * which literals are safe to treat as chain anchors without risking an ANSI eval failure.
+   * Arbitrary expressions (such as a parsing cast `CAST('abc' AS INT)` or arithmetic that can
+   * fail under ANSI) are excluded.
+   */
+  @tailrec
+  private def isSafeBoundLiteral(e: Expression): Boolean = e match {
+    case l: Literal => l.value != null
+    case Cast(child, toType, _, _) =>
+      UpCastRule.canUpCast(child.dataType, toType) && isSafeBoundLiteral(child)
+    case _ => false
+  }
+
+  private def hasBoundOperand(e: Expression): Boolean = e match {
+    case b: BinaryComparison => isSafeBoundLiteral(b.left) || isSafeBoundLiteral(b.right)
+    case _ => false
+  }
+
+  /**
+   * True when `e` is safe to copy into a newly inferred, single-side filter produced by
+   * [[inferInequalityConstraints]] without risking an error on rows that never evaluated it
+   * before: an attribute reference, or an upcast of one admitted by [[UpCastRule.canUpCast]].
+   * While some upcasts may lose precision (e.g. Long to Float/Double), relocation is sound
+   * because they cannot fail and reuse the existing Cast expression. Arbitrary expressions -- a
+   * parsing/narrowing cast, arithmetic that can overflow under ANSI, etc. -- are excluded, since
+   * the comparison they came from may have been a cross-side join condition that only ever ran
+   * on matched rows.
+   */
+  private def isSafeToRelocate(e: Expression): Boolean = e match {
+    case _: Attribute => true
+    case Cast(a: Attribute, toType, _, _) => UpCastRule.canUpCast(a.dataType, toType)
+    case _ => false
+  }
+
+  /**
+   * A known literal bound discovered while chaining inequality constraints in
+   * [[inferInequalityConstraints]]: `site {<,<=} lit` when `upper`, or `lit {<,<=} site`
+   * otherwise. `value` stores the evaluated literal value to avoid repeatedly evaluating `lit`
+   * during optimization.
+   */
+  private case class InequalityBound(
+      upper: Boolean,
+      site: Expression,
+      lit: Expression,
+      strict: Boolean,
+      value: Any)
+
+  /**
+   * Converts a canonicalized comparison into an [[InequalityBound]] when exactly one side is a
+   * safe literal bound ([[isSafeBoundLiteral]]); `None` for attribute-to-attribute comparisons.
+   */
+  private def toBound(e: Expression): Option[InequalityBound] = e match {
+    case b: BinaryComparison =>
+      val strict = b.isInstanceOf[LessThan]
+      if (isSafeBoundLiteral(b.right) && !isSafeBoundLiteral(b.left)) {
+        Some(InequalityBound(upper = true, b.left, b.right, strict, b.right.eval()))
+      } else if (isSafeBoundLiteral(b.left) && !isSafeBoundLiteral(b.right)) {
+        Some(InequalityBound(upper = false, b.right, b.left, strict, b.left.eval()))
+      } else {
+        None
+      }
+    case _ => None
+  }
+
+  /**
+   * Infers tightest literal inequality bounds on relocatable sites by transitively chaining
+   * inequality constraints with literal bounds. For e.g., if an operator has constraints of the
+   * form (`a > b`, `b > 5`), this returns an additional constraint of the form `a > 5`; a longer
+   * chain such as `a < b && b < c && c < 5` derives both `b < 5` and `a < 5` in this same call.
+   * Note that attribute-to-attribute inequalities without literal bounds (e.g., `a < c` from
+   * `a < b && b < c`) are not inferred.
+   *
+   * This is computed as a worklist over a directed bound graph rather than a repeated fixed point
+   * over the full candidate set: each candidate comparison becomes a directed edge once, and each
+   * newly discovered bound is propagated only along its adjacent edges, instead of rescanning the
+   * full candidates x bounds product after every newly inferred bound (which costs O(n^3) on a
+   * sparse n-element chain such as `x1 < x2 < ... < xn < lit`). A site only ever keeps its single
+   * tightest bound per direction, so reaching it via multiple literals (e.g. `b < 5` and `b < 10`
+   * both reaching `a` through `a < b`) converges to one inferred predicate instead of one per
+   * literal; a relaxation only re-enters the worklist when it strictly tightens that site's bound,
+   * which bounds the number of relaxations per site by the number of distinct literals that can
+   * reach it and guarantees termination.
+   */
+  private def inferInequalityConstraints(constraints: ExpressionSet): ExpressionSet = {
+    // Admits only comparisons between binary-stable types. This is a conservative guard, not a
+    // strict requirement: chaining never substitutes a value the way
+    // inferConstraintsFromLiteralBindings does, it only reuses an operand under the same
+    // collation-aware comparison, so a non-binary-stable collation could in principle still order
+    // consistently with its binary form here. EqualTo is admitted only when at least one side is
+    // a safe literal bound (acting as a directional upper and lower bound). Non-literal equalities
+    // -- attribute-to-attribute (handled by inferAdditionalConstraints's transitivity), as well as
+    // any other shape without a safe literal bound such as `a + 1 = b` -- are deliberately
+    // excluded from serving as chaining edges to keep the graph focused on literal bounds.
+    val validComparisons = constraints.toSeq.filter {
+      case b: BinaryComparison =>
+        b.deterministic && !b.throwable && !b.isInstanceOf[EqualNullSafe] &&
+          (!b.isInstanceOf[EqualTo] || hasBoundOperand(b)) &&
+          isBinaryStable(b.left.dataType) && isBinaryStable(b.right.dataType)
+      case _ => false
+    }
+
+    if (!validComparisons.exists(hasBoundOperand)) {
+      return ExpressionSet()
+    }
+
+    // Canonicalize comparisons into LessThan / LessThanOrEqual direction. EqualTo is expanded
+    // into both directions, unlike GreaterThan/GreaterThanOrEqual, because an equality acts as
+    // both an upper and a lower bound and the matching below is direction-sensitive on which
+    // side carries the literal. Kept as a Seq, not an ExpressionSet: ExpressionSet canonicalizes
+    // EqualTo(l, r) and EqualTo(r, l) to the same entry and would silently keep only one of the
+    // two directions just expanded.
+    val canonical = validComparisons.flatMap {
+      case GreaterThan(l, r) => LessThan(r, l) :: Nil
+      case GreaterThanOrEqual(l, r) => LessThanOrEqual(r, l) :: Nil
+      case EqualTo(l, r) => EqualTo(l, r) :: EqualTo(r, l) :: Nil
+      case other => other :: Nil
+    }
+
+    val (initialBounds, candidates) = canonical.partition(hasBoundOperand)
+    if (initialBounds.isEmpty || candidates.isEmpty) return ExpressionSet()
+
+    // Index candidate edges by the semantic key of the endpoint a bound would match, so a newly
+    // discovered bound only revisits the edges that touch it instead of the full candidate list.
+    // An edge `l < r` (or `l <= r`) propagates an upper bound on `r` to `l`, and a lower bound on
+    // `l` to `r`.
+    val upperEdges = new mutable.HashMap[Expression, mutable.Buffer[(Expression, Boolean)]]
+    val lowerEdges = new mutable.HashMap[Expression, mutable.Buffer[(Expression, Boolean)]]
+    candidates.foreach {
+      case c @ BinaryComparison(l, r) =>
+        val strict = c.isInstanceOf[LessThan]
+        if (isSafeToRelocate(l)) {
+          upperEdges.getOrElseUpdate(r.canonicalized, mutable.Buffer.empty) += (l -> strict)
+        }
+        if (isSafeToRelocate(r)) {
+          lowerEdges.getOrElseUpdate(l.canonicalized, mutable.Buffer.empty) += (r -> strict)
+        }
+      case _ =>
+    }
+
+    if (upperEdges.isEmpty && lowerEdges.isEmpty) return ExpressionSet()
+
+    // Key: (upper, site.canonicalized) -> tightest bound discovered for that site so far, keyed
+    // without the literal so that bounding the same site via different literals (e.g. `b < 5` and
+    // `b < 10` both reaching `a` through `a < b`) converges to the single tightest predicate
+    // instead of emitting one inferred conjunct per literal it was ever bounded by.
+    type BoundKey = (Boolean, Expression)
+    val bestBound = new mutable.HashMap[BoundKey, InequalityBound]
+    val inferredBounds = new mutable.LinkedHashMap[BoundKey, InequalityBound]
+    val worklist = new mutable.Queue[InequalityBound]
+
+    // True when `candidate` improves on `current` for the same key: a smaller upper-bound literal
+    // (or larger lower-bound one), or an equal literal newly made strict. Compares with the same
+    // per-type ordering BinaryComparison.eval itself uses, so tightness agrees with the actual
+    // `<`/`<=` runtime semantics (decimal scale, etc.) instead of a parallel notion of "smaller".
+    def isTighter(upper: Boolean, candidate: InequalityBound, current: InequalityBound): Boolean = {
+      val cmp = TypeUtils.getInterpretedOrdering(candidate.site.dataType)
+        .compare(candidate.value, current.value)
+      if (cmp == 0) {
+        candidate.strict && !current.strict

Review Comment:
   **Blocking (P1):** Consider two join inputs that are otherwise identical, such as a self-join with matching filters or a deterministic CTE inlined twice, where both carry the same non-strict range bound on the columns of a strict cross-instance inequality. This check lets an equal-valued strict copy win over the site's own bound. For `WITH r AS (SELECT user, ts FROM events WHERE ts >= DATE'2020-03-01') SELECT count(*) FROM r a JOIN r b ON a.user = b.user AND a.ts < b.ts`, inference carries `a.ts >= DATE'2020-03-01'` across `a.ts < b.ts` as `b.ts > DATE'2020-03-01'`, and inferNewFilter adds it to b only, because b's constraints hold just the non-strict form. With a shared BETWEEN bound, a also gains `ts < hi`. When both inputs are shuffled, they no longer canonicalize equally, so the stage cache under AQE, or ReuseExchangeAndSubquery without it, stops reusing the first exchange. The shared input is then scanned and shuffled twice, where the base branch does it once. The extra conju
 nct removes only rows exactly equal to the literal, and results are unchanged. Event-attribution self-joins under a shared date filter have exactly this shape, and no test plans exchanges for it.
   
   **Recommended change:** Keep using strictness to propagate bounds along chains in the inequality inference, but stop emitting a derived bound on a site that the input constraints already bound in the same direction with an equal literal value. Emit only bounds that are new for the site or tighter in value. Add exchange-reuse planning coverage for a self-join and a twice-referenced CTE, alongside the existing inequality-inference optimizer tests.
   
   **Why this works:** Record the bound that the input comparisons give each direction and site, then compare each derived bound with it at emission, using the site type's interpreted ordering. Drop the derived bound when the two values are equal. Identical non-strict bounds on both instances then stay identical after inference, so their exchanges canonicalize equally again, while strict tightening among derived bounds still applies.
   
   **Scope:** Adjust the emission rule of the inequality inference and add exchange-reuse coverage for self-join and CTE shapes.
   
   **Compatibility:** Strictness still propagates along chains, and strict tightening among derived bounds on the same site is still emitted when the input constraints held no equal-valued bound for that site.
   
   **Risks:** A join side that already carries `x >= lit` no longer gains the strict `x > lit` derived through a strict edge, so pruning of rows or partitions exactly equal to that literal on that side is given up. The join condition still removes those rows, so results are unchanged and the loss is limited to the boundary value. The change is contained in the inference and can be reverted on its own.
   
   **Constraints:** Inferred bounds must remain implied by the input constraints, keep their deterministic emission order, and keep one tightest bound per direction and site.
   
   **Exclusions:**
   - Plan-identity effects of other inferred constraints, such as equality and literal-binding inference, are unchanged and out of scope.
   
   **Success:** A self-join or twice-referenced deterministic CTE whose instances share a non-strict literal bound, joined by an equi-key plus a strict cross-instance inequality, plans one reused exchange or query stage, as on the base branch. Sites without an equal-valued existing bound still receive strict derived bounds, and the TPC-H Q12 plan keeps its two inferred lineitem bounds.
   
   **Verification:**
   - **Regression:** For a twice-referenced CTE that filters `ts >= lo` and is joined to itself on an equi-key with `a.ts < b.ts`, and for the variant with a shared BETWEEN bound, the optimized plan adds no strict copy of the shared bound to either instance, and the physical plan reuses one exchange or query stage.
   - **Behavior:** A strict bound is still inferred where the target site has no bound or only a weaker one, for example `left.b < right.b` with `right.b <= 1` still infers `left.b < 1`.
   - **Compatibility:** Existing inequality-inference expectations for tightest-bound convergence, strictness composition, cycles and the TPC-H Q12 plan stay unchanged.



-- 
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: reviews-unsubscribe@spark.apache.org

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


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org