You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by we...@apache.org on 2022/02/22 05:52:48 UTC

[spark] branch branch-3.2 updated: [SPARK-37290][SQL] - Exponential planning time in case of non-deterministic function

This is an automated email from the ASF dual-hosted git repository.

wenchen pushed a commit to branch branch-3.2
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/branch-3.2 by this push:
     new fb5d83b  [SPARK-37290][SQL] - Exponential planning time in case of non-deterministic function
fb5d83b is described below

commit fb5d83b0206f800e079af40c174381971232da88
Author: Franck Thang <st...@outlook.com>
AuthorDate: Tue Feb 22 13:49:32 2022 +0800

    [SPARK-37290][SQL] - Exponential planning time in case of non-deterministic function
    
    ### What changes were proposed in this pull request?
    
    When using non-deterministic function, the method getAllValidConstraints can throw an OOM
    
    ```
      protected def getAllValidConstraints(projectList: Seq[NamedExpression]): ExpressionSet = {
        var allConstraints = child.constraints
        projectList.foreach {
          case a  Alias(l: Literal, _) =>
            allConstraints += EqualNullSafe(a.toAttribute, l)
          case a  Alias(e, _) =>
            // For every alias in `projectList`, replace the reference in constraints by its attribute.
            allConstraints ++= allConstraints.map(_ transform {
              case expr: Expression if expr.semanticEquals(e) =>
                a.toAttribute
            })
            allConstraints += EqualNullSafe(e, a.toAttribute)
          case _ => // Don't change.
        }
    
        allConstraints
      }
    ```
    In particular, this line `allConstraints ++= allConstraints.map(...)` can generate an exponential number of expressions
    This is because non deterministic functions are considered unique in a ExpressionSet
    Therefore, the number of non-deterministic expressions double every time we go through this line
    
    We can filter and keep only deterministic expression because
    1 - the `semanticEquals` automatically discard non deterministic expressions
    2 - this method is only used in one code path, and we keep only determinic expressions
    ```
    lazy val constraints: ExpressionSet = {
        if (conf.constraintPropagationEnabled) {
          validConstraints
            .union(inferAdditionalConstraints(validConstraints))
            .union(constructIsNotNullConstraints(validConstraints, output))
            .filter { c =>
              c.references.nonEmpty && c.references.subsetOf(outputSet) && c.deterministic
            }
        } else {
          ExpressionSet()
        }
      }
    ```
    
    ### Why are the changes needed?
    It can lead to an exponential number of expressions and / or OOM
    
    ### Does this PR introduce _any_ user-facing change?
    No
    
    ### How was this patch tested?
    
    Local test
    
    Closes #35233 from Stelyus/SPARK-37290.
    
    Authored-by: Franck Thang <st...@outlook.com>
    Signed-off-by: Wenchen Fan <we...@databricks.com>
    (cherry picked from commit 881f562f7b6a2bed76b01f956bc02c4b87ad6b80)
    Signed-off-by: Wenchen Fan <we...@databricks.com>
---
 .../scala/org/apache/spark/sql/catalyst/plans/logical/LogicalPlan.scala | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/LogicalPlan.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/LogicalPlan.scala
index 7c31a00..a34a9c6 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/LogicalPlan.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/LogicalPlan.scala
@@ -182,7 +182,7 @@ trait UnaryNode extends LogicalPlan with UnaryLike[LogicalPlan] {
     projectList.foreach {
       case a @ Alias(l: Literal, _) =>
         allConstraints += EqualNullSafe(a.toAttribute, l)
-      case a @ Alias(e, _) =>
+      case a @ Alias(e, _) if e.deterministic =>
         // For every alias in `projectList`, replace the reference in constraints by its attribute.
         allConstraints ++= allConstraints.map(_ transform {
           case expr: Expression if expr.semanticEquals(e) =>

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