Github user sameeragarwal commented on a diff in the pull request:
https://github.com/apache/spark/pull/15319#discussion_r84648636
--- Diff:
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/QueryPlan.scala
---
@@ -74,20 +74,98 @@ abstract class QueryPlan[PlanType <:
QueryPlan[PlanType]] extends TreeNode[PlanT
* additional constraint of the form `b = 5`
*/
private def inferAdditionalConstraints(constraints: Set[Expression]):
Set[Expression] = {
+ // Collect alias from expressions to avoid producing non-converging
set of constraints
+ // for recursive functions.
+ //
+ // Don't apply transform on constraints if the replacement will cause
an recursive deduction,
+ // when that happens a non-converging set of constraints will be
created and finally throw
+ // OOM Exception.
+ // For more details, refer to
https://issues.apache.org/jira/browse/SPARK-17733
+ val aliasMap = AttributeMap((expressions ++
children.flatMap(_.expressions)).collect {
+ case a: Alias => (a.toAttribute, a.child)
+ })
+
+ val equalExprSets = generateEqualExpressionSets(constraints, aliasMap)
+
var inferredConstraints = Set.empty[Expression]
constraints.foreach {
case eq @ EqualTo(l: Attribute, r: Attribute) =>
- inferredConstraints ++= (constraints - eq).map(_ transform {
- case a: Attribute if a.semanticEquals(l) => r
+ val candidateConstraints = constraints - eq
+ inferredConstraints ++= candidateConstraints.map(_ transform {
+ case a: Attribute if a.semanticEquals(l) &&
+ !isRecursiveDeduction(r, aliasMap, equalExprSets) => r
})
- inferredConstraints ++= (constraints - eq).map(_ transform {
- case a: Attribute if a.semanticEquals(r) => l
+ inferredConstraints ++= candidateConstraints.map(_ transform {
+ case a: Attribute if a.semanticEquals(r) &&
+ !isRecursiveDeduction(l, aliasMap, equalExprSets) => l
})
case _ => // No inference
}
inferredConstraints -- constraints
}
+ /*
+ * Generate a sequence of expression sets from constraints, where each
set stores an equivalence
+ * class of expressions. For example, Set(`a = b`, `b = c`, `e = f`)
will generate the following
+ * expression sets: (Set(a, b, c), Set(e, f)). This will be used to
search all expressions equal
+ * to an selected attribute.
+ */
+ private def generateEqualExpressionSets(
+ constraints: Set[Expression],
+ aliasMap: AttributeMap[Expression]): Seq[Set[Expression]] = {
+ var equalExprSets = Seq.empty[Set[Expression]]
+ constraints.foreach {
+ case eq @ EqualTo(l: Attribute, r: Attribute) =>
+ // Transform [[Alias]] to its child.
+ val left = aliasMap.getOrElse(l, l)
+ val right = aliasMap.getOrElse(r, r)
+ // Get the expression set for equivalence class of expressions.
+ val leftEqualSet = getEqualExprSet(left,
equalExprSets).getOrElse(Set.empty[Expression])
+ val rightEqualSet = getEqualExprSet(right,
equalExprSets).getOrElse(Set.empty[Expression])
+ if (!leftEqualSet.isEmpty && !rightEqualSet.isEmpty) {
+ // Combine the two sets.
+ equalExprSets = equalExprSets.diff(leftEqualSet :: rightEqualSet
:: Nil) :+
+ (leftEqualSet ++ rightEqualSet)
+ } else if (!leftEqualSet.isEmpty) { // && rightEqualSet.isEmpty
+ // Update equivalence class of `left` expression.
+ equalExprSets = equalExprSets.diff(leftEqualSet :: Nil) :+
(leftEqualSet + right)
+ } else if (!rightEqualSet.isEmpty) { // && leftEqualSet.isEmpty
+ // Update equivalence class of `right` expression.
+ equalExprSets = equalExprSets.diff(rightEqualSet :: Nil) :+
(rightEqualSet + left)
+ } else { // leftEqualSet.isEmpty && rightEqualSet.isEmpty
+ // Create new equivalence class since both expression don't
present in any classes.
+ equalExprSets = equalExprSets :+ Set(left, right)
+ }
+ case _ => // Skip
+ }
+
+ equalExprSets
+ }
+
+ /*
+ * Get all expressions equivalent to the selected expression.
+ */
+ private def getEqualExprSet(
+ expr: Expression,
+ equalExprSets: Seq[Set[Expression]]): Option[Set[Expression]] =
+ equalExprSets.filter(_.contains(expr)).headOption
+
+ /*
+ * Check whether replace by an [[Attribute]] will cause an recursive
deduction. Generally it
+ * has an form like: `a -> f(a, b)`, where `a` and `b` are expressions
and `f` is an function.
+ * Here we first get all expressions equal to `attr` and then check
whether at least one of them
+ * is child of the referenced expression.
--- End diff --
nit: `is a child`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org
