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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
