You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by GitBox <gi...@apache.org> on 2020/11/04 06:25:05 UTC

[GitHub] [spark] viirya opened a new pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

viirya opened a new pull request #30245:
URL: https://github.com/apache/spark/pull/30245


   <!--
   Thanks for sending a pull request!  Here are some tips for you:
     1. If this is your first time, please read our contributor guidelines: https://spark.apache.org/contributing.html
     2. Ensure you have added or run the appropriate tests for your PR: https://spark.apache.org/developer-tools.html
     3. If the PR is unfinished, add '[WIP]' in your PR title, e.g., '[WIP][SPARK-XXXX] Your PR title ...'.
     4. Be sure to keep the PR description updated to reflect all changes.
     5. Please write your PR title to summarize what this PR proposes.
     6. If possible, provide a concise example to reproduce the issue for a faster review.
     7. If you want to add a new configuration, please read the guideline first for naming configurations in
        'core/src/main/scala/org/apache/spark/internal/config/ConfigEntry.scala'.
   -->
   
   ### What changes were proposed in this pull request?
   <!--
   Please clarify what changes you are proposing. The purpose of this section is to outline the changes and how this PR fixes the issue. 
   If possible, please consider writing useful notes for better and faster reviews in your PR. See the examples below.
     1. If you refactor some codes with changing classes, showing the class hierarchy will help reviewers.
     2. If you fix some SQL features, you can provide some references of other DBMSes.
     3. If there is design documentation, please add the link.
     4. If there is a discussion in the mailing list, please add the link.
   -->
   
   
   Currently we skip subexpression elimination in branches of conditional expressions including `If`, `CaseWhen`, and `Coalesce`. Actually we can do subexpression elimination for such branches if the subexpression is common across all branches. This patch proposes to support subexpression elimination in branches of conditional expressions.
   
   ### Why are the changes needed?
   <!--
   Please clarify why the changes are needed. For instance,
     1. If you propose a new API, clarify the use case for a new API.
     2. If you fix a bug, you can clarify why it is a bug.
   -->
   
   We may miss subexpression elimination chances in branches of conditional expressions. This kind of subexpression is frequently seen. It may be written manually by users or come from query optimizer. For example, project collapsing could embed expressions between two `Project`s and produces conditional expression like:
   
   ```
   CASE WHEN jsonToStruct(json).a = '1' THEN 1.0 WHEN jsonToStruct(json).a = '2' THEN 2.0 ... ELSE 1.2 END
   ```
   
   If `jsonToStruct(json)` is time-expensive expression, we don't eliminate the duplication and waste time on running it repeatedly.
   
   ### Does this PR introduce _any_ user-facing change?
   <!--
   Note that it means *any* user-facing change including all aspects such as the documentation fix.
   If yes, please clarify the previous behavior and the change this PR proposes - provide the console output, description and/or an example to show the behavior difference if possible.
   If possible, please also clarify if this is a user-facing change compared to the released Spark versions or within the unreleased branches such as master.
   If no, write 'No'.
   -->
   
   No
   
   ### How was this patch tested?
   <!--
   If tests were added, say they were added here. Please make sure to add some test cases that check the changes thoroughly including negative and positive cases if possible.
   If it was tested in a way different from regular unit tests, please clarify how you tested step by step, ideally copy and paste-able, so that other reviewers can test and check, and descendants can verify in the future.
   If tests were not added, please describe why they were not added and/or why it was difficult to add.
   -->
   
   Unit 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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721557561


   **[Test build #130593 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130593/testReport)** for PR 30245 at commit [`db0cfcc`](https://github.com/apache/spark/commit/db0cfcc26a9ca2312afd34eda1e616670001218b).


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya closed pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya closed pull request #30245:
URL: https://github.com/apache/spark/pull/30245


   


----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-723993934


   This update looks useful and I left some comments.


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721553230


   **[Test build #130592 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130592/testReport)** for PR 30245 at commit [`a8e0c22`](https://github.com/apache/spark/commit/a8e0c2251d3bf01fcaa29344f2357c8768792d49).
    * This patch **fails Spark unit tests**.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] dongjoon-hyun commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
dongjoon-hyun commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r523281950



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -146,20 +146,111 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     equivalence.addExprTree(add)
     // the `two` inside `fallback` should not be added
     assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
+    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3) // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {
     val add = Add(Literal(1), Literal(2))
-    val ifExpr = If(condition, add, add)
+    val condition = GreaterThan(add, Literal(3))
 
-    val equivalence = new EquivalentExpressions
-    equivalence.addExprTree(ifExpr)
-    // the `add` inside `If` should not be added
-    assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    // only ifExpr and its predicate expression
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 2)
+    val ifExpr1 = If(condition, add, add)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(ifExpr1)
+
+    // `add` is in both two branches of `If` and predicate.
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 2) == 1)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    // one-time expressions: only ifExpr and its predicate expression
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))

Review comment:
       Thank you, @leoluan2009 and @viirya . The follow-up is merged to reduce the flakiness.




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-725046176


   Thanks! Merging to master.


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722983372






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722173682






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722110081






----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724549854


   retest this please


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724405621


   Merged build finished. Test FAILed.


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724398205


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35422/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722074288


   cc @cloud-fan @maropu @dongjoon-hyun 


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722942091


   **[Test build #130705 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130705/testReport)** for PR 30245 at commit [`9182e3d`](https://github.com/apache/spark/commit/9182e3d2d576a12829ce1263c1b0c080ad30f6ef).


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722942091


   **[Test build #130705 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130705/testReport)** for PR 30245 at commit [`9182e3d`](https://github.com/apache/spark/commit/9182e3d2d576a12829ce1263c1b0c080ad30f6ef).


----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520188198



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()

Review comment:
       How about the overhead? It seems the current code clones a whole expr set per update though.




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-723070562






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721553348


   Merged build finished. Test FAILed.


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724363089


   **[Test build #130813 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130813/testReport)** for PR 30245 at commit [`33f3bd3`](https://github.com/apache/spark/commit/33f3bd3d7e56beb285276d70f3ea36c15425a849).


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724372681


   **[Test build #130803 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130803/testReport)** for PR 30245 at commit [`cc0648a`](https://github.com/apache/spark/commit/cc0648af351cdf19700691344a227bf209fc9338).
    * This patch passes all tests.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660900968



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       only some trivial conflicts, #32980 should be merged first as it has been reviewed and approved.




-- 
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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724373481






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724534407


   **[Test build #130835 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130835/testReport)** for PR 30245 at commit [`b415728`](https://github.com/apache/spark/commit/b41572884401d5e02d6cda69068433376c6ab328).
    * This patch **fails due to an unknown error code, -9**.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721561406






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-723069464


   **[Test build #130705 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130705/testReport)** for PR 30245 at commit [`9182e3d`](https://github.com/apache/spark/commit/9182e3d2d576a12829ce1263c1b0c080ad30f6ef).
    * This patch passes all tests.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721576154






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724253482


   **[Test build #130803 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130803/testReport)** for PR 30245 at commit [`cc0648a`](https://github.com/apache/spark/commit/cc0648af351cdf19700691344a227bf209fc9338).


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721537711


   **[Test build #130592 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130592/testReport)** for PR 30245 at commit [`a8e0c22`](https://github.com/apache/spark/commit/a8e0c2251d3bf01fcaa29344f2357c8768792d49).


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724713108






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724471038


   **[Test build #130835 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130835/testReport)** for PR 30245 at commit [`b415728`](https://github.com/apache/spark/commit/b41572884401d5e02d6cda69068433376c6ab328).


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721537711


   **[Test build #130592 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130592/testReport)** for PR 30245 at commit [`a8e0c22`](https://github.com/apache/spark/commit/a8e0c2251d3bf01fcaa29344f2357c8768792d49).


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724535089


   Test FAILed.
   Refer to this link for build results (access rights to CI server needed): 
   https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/130835/
   Test FAILed.


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660870034



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       There is a flaw here: we exclude the first condition, so a common subexpressions in the rest of the conditions doesn't mean it's always evaluated.
   
   e.g. `CaseWhen(cond1, ... cond2, ..., cond2, ...)`, `cond2` is shared between the rest conditions but it's not always evaluated.




-- 
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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660879756



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       WDYT? Should we only consider all conditions?




-- 
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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520284775



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,74 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {

Review comment:
       This can be private as well.




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721587992






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722972813


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35315/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520084936



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }
+
+    exprSetForAll.foreach(addFunc)
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      val conditions = c.branches.tail.map(_._1)
+      val values = c.branches.map(_._2) ++ c.elseValue
+      Seq(conditions, values)

Review comment:
       A subexpression in conditions is definitely run because it is shared among `conditions`. It doesn't need to be shared in `values`. Similarly, a subexpression among `values` doesn't need to be in `conditions` because no matter which condition is true, it will be evaluated.




----------------------------------------------------------------
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.

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


[GitHub] [spark] dongjoon-hyun commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
dongjoon-hyun commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r518408688



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,46 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {

Review comment:
       To reduce the SET expression, is it better to exclude non-deterministic expression like `addExpr` function?




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722074922


   **[Test build #130627 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130627/testReport)** for PR 30245 at commit [`cd3776c`](https://github.com/apache/spark/commit/cd3776c1dc997e30f1c44d873b8e1ab35e567726).


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r521767608



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -146,20 +146,111 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     equivalence.addExprTree(add)
     // the `two` inside `fallback` should not be added
     assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
+    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3) // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {
     val add = Add(Literal(1), Literal(2))
-    val ifExpr = If(condition, add, add)
+    val condition = GreaterThan(add, Literal(3))
 
-    val equivalence = new EquivalentExpressions
-    equivalence.addExprTree(ifExpr)
-    // the `add` inside `If` should not be added
-    assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    // only ifExpr and its predicate expression
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 2)
+    val ifExpr1 = If(condition, add, add)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(ifExpr1)
+
+    // `add` is in both two branches of `If` and predicate.
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 2) == 1)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    // one-time expressions: only ifExpr and its predicate expression
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))

Review comment:
       Ok, I will create a follow-up for making sure it will not possibly flaky. Thanks.




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724287926






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724485726


   **[Test build #130812 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130812/testReport)** for PR 30245 at commit [`16314a9`](https://github.com/apache/spark/commit/16314a91ed673a0a04a9da248b343a3c0ba07ce6).
    * This patch passes all tests.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660875150



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       yes, this is related to #32977. This looks more a aggressive optimization. Consider if we respect short-circuit evaluation practice for CaseWhen, this might be an issue if users reply short-circuit evaluation to guard later conditions.
   
   Safest approach is to only consider all conditions.




-- 
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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721576082


   **[Test build #130593 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130593/testReport)** for PR 30245 at commit [`db0cfcc`](https://github.com/apache/spark/commit/db0cfcc26a9ca2312afd34eda1e616670001218b).
    * This patch **fails due to an unknown error code, -9**.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724287926






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724620591






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724470900






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724363089


   **[Test build #130813 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130813/testReport)** for PR 30245 at commit [`33f3bd3`](https://github.com/apache/spark/commit/33f3bd3d7e56beb285276d70f3ea36c15425a849).


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724373481






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721587992






----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r517120205



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -149,17 +149,43 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {

Review comment:
       I will add the tests for `CaseWhen` and `Coalesce`.




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724287900


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35413/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721587973


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35194/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721553355


   Test FAILed.
   Refer to this link for build results (access rights to CI server needed): 
   https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/130592/
   Test FAILed.


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724273316


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35413/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660890475



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       Ok, thanks!




-- 
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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660890773



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       BTW, does #32980 conflict with your refactor?




-- 
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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722110063


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35233/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520285317



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,74 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        val e = Expr(expr)
+        if (exprSetForAll.contains(e)) {
+          true
+        } else {
+          exprSetForAll.add(e)
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+
+      addExprTree(expr, (innerExpr: Expression) => {
+        if (innerExpr.deterministic) {

Review comment:
       Similar code appears twice. Can we create a method for it?




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724604433


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35461/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r518419317



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +131,21 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    // For some special expressions we cannot just recurse into all of its children, but we can
+    // recursively add the common expressions shared between all of its children.
+    def commonChildrenToRecurse: Seq[Seq[Expression]] = expr match {

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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520086265



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       I prefer to separate them. The merged method looks quite hard to read, IMO.




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724620568


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35461/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724620591






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724551834


   **[Test build #130853 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130853/testReport)** for PR 30245 at commit [`b415728`](https://github.com/apache/spark/commit/b41572884401d5e02d6cda69068433376c6ab328).


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r518584261



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,46 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (exprSetForAll.contains(expr)) {
+        true
+      } else {
+        exprSetForAll += expr
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (exprSet.contains(expr)) {
+          true
+        } else {
+          exprSet += expr
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }

Review comment:
       For expression `head`, we add underlying expressions into `exprSetForAll` set. But for expressions in `tail`, we keep intersect between `exprSetForAll` and `exprSet`.
   
   We can merge two blocks, but in the block we need to check if current expression is head expression and do different logic based on the check.
   
   I prefer current one since it looks simpler.




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721577870


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35194/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722089879


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35233/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519766271



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       Seems like we can merge them like this?
   ```
       // There are some special expressions that we should not recurse into all of its children.
       //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
       //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
       //          false expressions in `If` may not get accessed, according to the predicate
       //          expression. We should only recurse into the predicate expression.
       //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
       //                condition. We should only recurse into the first condition expression as it
       //                will always get accessed.
       //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
       //                children, because others may not get accessed.
       lazy val (childrenToRecurse, commonChildrenToRecurse) = expr match {
         case _: CodegenFallback => (Nil, Nil)
         case i: If => (i.predicate :: Nil, Seq(Seq(i.trueValue, i.falseValue)))
         case c: CaseWhen =>
           val (Seq(headCondition), otherConditions) = c.branches.map(_._1).splitAt(1)
           val values = c.branches.map(_._2) ++ c.elseValue
           (headCondition :: Nil, Seq(otherConditions, values))
         case c: Coalesce => (c.children.head :: Nil, Seq(c.children.tail))
         case other => (other.children, Nil)
       }
   ```
   Then, I think its better to update the comment above for describing how to handle these "special expressions (If, CaseWhen, and Coalesce)".




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724535080






----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519782905



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()

Review comment:
       Just a question; Any reason to use `ExpressionSet` instead of `mutable.Set[Expr]`? I thought we can write it like this;
   ```
     def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
       val exprSetForAll = mutable.Set[Expr]()
   
       addExprTree(exprs.head, (expr: Expression) => {
         if (expr.deterministic) {
           val e = Expr(expr)
           if (exprSetForAll.contains(e)) {
             true
           } else {
             exprSetForAll += e
             false
           }
         } else {
           false
         }
       })
   
       val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
         val otherExprSet = mutable.Set[Expr]()
         addExprTree(expr, (expr: Expression) => {
           if (expr.deterministic) {
             val e = Expr(expr)
             if (otherExprSet.contains(e)) {
               true
             } else {
               otherExprSet += e
               false
             }
           } else {
             false
           }
         })
         exprSet.intersect(otherExprSet)
       }
   
       commonExprSet.foreach(expr => addFunc(expr.e))
     }
   ```




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r518571332



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,46 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {

Review comment:
       Sounds good.




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520089446



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       > childrenToRecurse is an inner method, shall we make commonChildrenToRecurse an inner method as well and put it next to childrenToRecurse?
   
   @cloud-fan That is what I did initially, but put it outside for review comment https://github.com/apache/spark/pull/30245#discussion_r518409583. Both work for me. 




----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519768518



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }
+
+    exprSetForAll.foreach(addFunc)
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      val conditions = c.branches.tail.map(_._1)
+      val values = c.branches.map(_._2) ++ c.elseValue
+      Seq(conditions, values)

Review comment:
       Why do we need to handle `conditions` and `values` separately?




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722687545


   > Also, could you add a negative test case having the expression cannot be eliminated from conditional expressions?
   
   I mixed positive and negative test cases. I think I can add some comment to explain it.


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519686328



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)

Review comment:
       does the order of `exprs` affect the result?




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520085711



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)

Review comment:
       Here we take the intersection of all expressions. So the order doesn't matter.




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722149727


   Thank you @dongjoon-hyun 


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722173682






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722074922


   **[Test build #130627 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130627/testReport)** for PR 30245 at commit [`cd3776c`](https://github.com/apache/spark/commit/cd3776c1dc997e30f1c44d873b8e1ab35e567726).


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r523207679



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -146,20 +146,111 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     equivalence.addExprTree(add)
     // the `two` inside `fallback` should not be added
     assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
+    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3) // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {
     val add = Add(Literal(1), Literal(2))
-    val ifExpr = If(condition, add, add)
+    val condition = GreaterThan(add, Literal(3))
 
-    val equivalence = new EquivalentExpressions
-    equivalence.addExprTree(ifExpr)
-    // the `add` inside `If` should not be added
-    assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    // only ifExpr and its predicate expression
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 2)
+    val ifExpr1 = If(condition, add, add)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(ifExpr1)
+
+    // `add` is in both two branches of `If` and predicate.
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 2) == 1)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    // one-time expressions: only ifExpr and its predicate expression
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))

Review comment:
       Created #30371.




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724360152


   **[Test build #130812 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130812/testReport)** for PR 30245 at commit [`16314a9`](https://github.com/apache/spark/commit/16314a91ed673a0a04a9da248b343a3c0ba07ce6).


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721557561


   **[Test build #130593 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130593/testReport)** for PR 30245 at commit [`db0cfcc`](https://github.com/apache/spark/commit/db0cfcc26a9ca2312afd34eda1e616670001218b).


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520287026



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -146,20 +146,111 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     equivalence.addExprTree(add)
     // the `two` inside `fallback` should not be added
     assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
+    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3) // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {
     val add = Add(Literal(1), Literal(2))
-    val ifExpr = If(condition, add, add)
+    val condition = GreaterThan(add, Literal(3))
 
-    val equivalence = new EquivalentExpressions
-    equivalence.addExprTree(ifExpr)
-    // the `add` inside `If` should not be added
-    assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    // only ifExpr and its predicate expression
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 2)
+    val ifExpr1 = If(condition, add, add)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(ifExpr1)
+
+    // `add` is in both two branches of `If` and predicate.
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 2) == 1)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    // one-time expressions: only ifExpr and its predicate expression
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).last == Seq(condition))
+
+    // Repeated `add` is only in one branch, so we don't count it.
+    val ifExpr2 = If(condition, Add(Literal(1), Literal(3)), Add(add, add))
+    val equivalence2 = new EquivalentExpressions
+    equivalence2.addExprTree(ifExpr2)
+
+    assert(equivalence2.getAllEquivalentExprs.count(_.size > 1) == 0)
+    assert(equivalence2.getAllEquivalentExprs.count(_.size == 1) == 3)
+
+    val ifExpr3 = If(condition, ifExpr1, ifExpr1)
+    val equivalence3 = new EquivalentExpressions
+    equivalence3.addExprTree(ifExpr3)
+
+    // `add`: 2, `condition`: 2
+    assert(equivalence3.getAllEquivalentExprs.count(_.size == 2) == 2)
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 2).last == Seq(condition, condition))
+
+    // `ifExpr1`, `ifExpr3`
+    assert(equivalence3.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 1).last == Seq(ifExpr3))
+  }
+
+  test("Children of conditional expressions: CaseWhen") {
+    val add1 = Add(Literal(1), Literal(2))
+    val add2 = Add(Literal(2), Literal(3))
+    val conditions1 = (GreaterThan(add2, Literal(3)), add1) ::
+      (GreaterThan(add2, Literal(4)), add1) ::
+      (GreaterThan(add2, Literal(5)), add1) :: Nil
+
+    val caseWhenExpr1 = CaseWhen(conditions1, None)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(caseWhenExpr1)
+
+    // `add2` is repeatedly in all conditions.

Review comment:
       `add1` is also repeated. Why it's not included?




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724405596


   Kubernetes integration test status failure
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35422/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] dongjoon-hyun commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
dongjoon-hyun commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r518409583



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +131,21 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    // For some special expressions we cannot just recurse into all of its children, but we can
+    // recursively add the common expressions shared between all of its children.
+    def commonChildrenToRecurse: Seq[Seq[Expression]] = expr match {

Review comment:
       nit. Although this is used only here, can we declare this outside of this function as a private method? Currently, `addExprTree` seems to grow unnecessarily. 




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722983372






----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722987368


   Do you still remember why "subexpression elimination" must be eagerly executed? Because implementing "lazy" is expensive?


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724469763


   **[Test build #130813 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130813/testReport)** for PR 30245 at commit [`33f3bd3`](https://github.com/apache/spark/commit/33f3bd3d7e56beb285276d70f3ea36c15425a849).
    * This patch passes all tests.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722983345


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35315/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-723199081


   > Do you still remember why "subexpression elimination" must be eagerly executed? Because implementing "lazy" is expensive?
   
   I don't remember if we have tried to implement "lazy" behavior in codegen. Looks like at least it will bring complex as we need extra variable to check if a subexpression is evaulated in first time. Every time we use a subexpression, we might need to first check the extra variable and decide to evaluate the subexpression or just use evaluated value.
   
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520185710



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }
+
+    exprSetForAll.foreach(addFunc)
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      val conditions = c.branches.tail.map(_._1)
+      val values = c.branches.map(_._2) ++ c.elseValue
+      Seq(conditions, values)

Review comment:
       ah, 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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724487723






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724501292






----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520289276



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -146,20 +146,111 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     equivalence.addExprTree(add)
     // the `two` inside `fallback` should not be added
     assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
+    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3) // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {
     val add = Add(Literal(1), Literal(2))
-    val ifExpr = If(condition, add, add)
+    val condition = GreaterThan(add, Literal(3))
 
-    val equivalence = new EquivalentExpressions
-    equivalence.addExprTree(ifExpr)
-    // the `add` inside `If` should not be added
-    assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    // only ifExpr and its predicate expression
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 2)
+    val ifExpr1 = If(condition, add, add)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(ifExpr1)
+
+    // `add` is in both two branches of `If` and predicate.
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 2) == 1)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    // one-time expressions: only ifExpr and its predicate expression
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).last == Seq(condition))
+
+    // Repeated `add` is only in one branch, so we don't count it.
+    val ifExpr2 = If(condition, Add(Literal(1), Literal(3)), Add(add, add))
+    val equivalence2 = new EquivalentExpressions
+    equivalence2.addExprTree(ifExpr2)
+
+    assert(equivalence2.getAllEquivalentExprs.count(_.size > 1) == 0)
+    assert(equivalence2.getAllEquivalentExprs.count(_.size == 1) == 3)
+
+    val ifExpr3 = If(condition, ifExpr1, ifExpr1)
+    val equivalence3 = new EquivalentExpressions
+    equivalence3.addExprTree(ifExpr3)
+
+    // `add`: 2, `condition`: 2
+    assert(equivalence3.getAllEquivalentExprs.count(_.size == 2) == 2)
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 2).last == Seq(condition, condition))
+
+    // `ifExpr1`, `ifExpr3`
+    assert(equivalence3.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))
+    assert(equivalence3.getAllEquivalentExprs.filter(_.size == 1).last == Seq(ifExpr3))
+  }
+
+  test("Children of conditional expressions: CaseWhen") {
+    val add1 = Add(Literal(1), Literal(2))
+    val add2 = Add(Literal(2), Literal(3))
+    val conditions1 = (GreaterThan(add2, Literal(3)), add1) ::
+      (GreaterThan(add2, Literal(4)), add1) ::
+      (GreaterThan(add2, Literal(5)), add1) :: Nil
+
+    val caseWhenExpr1 = CaseWhen(conditions1, None)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(caseWhenExpr1)
+
+    // `add2` is repeatedly in all conditions.

Review comment:
       We treat the first condition specially because it is definitely run. So it counts one for `add2`.  Other conditions all contain `add2` so it counts for one. That is where the count 2 comes from for `add2`.
   
   For `add1`, although all values contain it, it is definitely run, so we count it one. If no other expression contains `add1`, we don't extract subexpression for `add1` as it will run just once (we only run one value of `CaseWhen`).




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724471038


   **[Test build #130835 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130835/testReport)** for PR 30245 at commit [`b415728`](https://github.com/apache/spark/commit/b41572884401d5e02d6cda69068433376c6ab328).


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721553348






----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r517120205



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -149,17 +149,43 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {

Review comment:
       I will add the tests for `CaseWhen` and `Coalesce`, but the idea is the same.




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724470900






----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660886137



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       I think we should. I hit an issue caused by it in my refactor and I'll open a PR for the refactor with multiple bugs fixed.




-- 
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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520290960



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       okay.




----------------------------------------------------------------
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.

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


[GitHub] [spark] leoluan2009 commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
leoluan2009 commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r521757764



##########
File path: sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
##########
@@ -146,20 +146,111 @@ class SubexpressionEliminationSuite extends SparkFunSuite {
     equivalence.addExprTree(add)
     // the `two` inside `fallback` should not be added
     assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3)  // add, two, explode
+    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 3) // add, two, explode
   }
 
-  test("Children of conditional expressions") {
-    val condition = And(Literal(true), Literal(false))
+  test("Children of conditional expressions: If") {
     val add = Add(Literal(1), Literal(2))
-    val ifExpr = If(condition, add, add)
+    val condition = GreaterThan(add, Literal(3))
 
-    val equivalence = new EquivalentExpressions
-    equivalence.addExprTree(ifExpr)
-    // the `add` inside `If` should not be added
-    assert(equivalence.getAllEquivalentExprs.count(_.size > 1) == 0)
-    // only ifExpr and its predicate expression
-    assert(equivalence.getAllEquivalentExprs.count(_.size == 1) == 2)
+    val ifExpr1 = If(condition, add, add)
+    val equivalence1 = new EquivalentExpressions
+    equivalence1.addExprTree(ifExpr1)
+
+    // `add` is in both two branches of `If` and predicate.
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 2) == 1)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 2).head == Seq(add, add))
+    // one-time expressions: only ifExpr and its predicate expression
+    assert(equivalence1.getAllEquivalentExprs.count(_.size == 1) == 2)
+    assert(equivalence1.getAllEquivalentExprs.filter(_.size == 1).head == Seq(ifExpr1))

Review comment:
       Should we use contains method? HashMap can not guarantee the order




----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520185710



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }
+
+    exprSetForAll.foreach(addFunc)
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      val conditions = c.branches.tail.map(_._1)
+      val values = c.branches.map(_._2) ++ c.elseValue
+      Seq(conditions, values)

Review comment:
       Ah, ok. Thanks. Could you leave comments about it in the code side?




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724551834


   **[Test build #130853 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130853/testReport)** for PR 30245 at commit [`b415728`](https://github.com/apache/spark/commit/b41572884401d5e02d6cda69068433376c6ab328).


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520087660



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()

Review comment:
       They actually the same effect. `Expr` compares expressions by `semanticeEquals` which compares `canonicalized` expressions. `ExpressionSet` compares `canonicalized` internally too.




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722110081






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721576154






----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724840905


   Thanks! Passed Jenkins and GitHub Actions. Will merge this today.


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724420399


   Thank you @maropu 


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721561387


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35193/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r660875150



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       yes, this is related to #32977. This looks more a aggressive optimization. Consider if we respect short-circuit evaluation practice for CaseWhen, this might be an issue.
   
   Safest approach is to only consider all conditions.




-- 
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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520285536



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       Then shall we move `childrenToRecurse` out too?




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724405621






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724713108






----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721561406






----------------------------------------------------------------
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.

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


[GitHub] [spark] maropu commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
maropu commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724409931


   No more my comment and LGTM.


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724405626


   Test FAILed.
   Refer to this link for build results (access rights to CI server needed): 
   https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder-K8s/35422/
   Test FAILed.


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519685416



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()

Review comment:
       I'm a bit lost. Shall we create an `ExpressionSet` for each input expr and get the intersaction at the end?




----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519683944



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       `childrenToRecurse` is an inner method, shall we make `commonChildrenToRecurse` an inner method as well and put it next to `childrenToRecurse`?




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724487723






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724484721


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35444/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724535080


   Merged build finished. Test FAILed.


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [WIP][SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-721553472


   Kubernetes integration test starting
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35193/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] Kimahriman commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
Kimahriman commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r661470618



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,82 @@ class EquivalentExpressions {
     }
   }
 
+  private def addExprToSet(expr: Expression, set: mutable.Set[Expr]): Boolean = {
+    if (expr.deterministic) {
+      val e = Expr(expr)
+      if (set.contains(e)) {
+        true
+      } else {
+        set.add(e)
+        false
+      }
+    } else {
+      false
+    }
+  }
+
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  private def addCommonExprs(
+      exprs: Seq[Expression],
+      addFunc: Expression => Boolean = addExpr): Unit = {
+    val exprSetForAll = mutable.Set[Expr]()
+    addExprTree(exprs.head, addExprToSet(_, exprSetForAll))
+
+    val commonExprSet = exprs.tail.foldLeft(exprSetForAll) { (exprSet, expr) =>
+      val otherExprSet = mutable.Set[Expr]()
+      addExprTree(expr, addExprToSet(_, otherExprSet))
+      exprSet.intersect(otherExprSet)
+    }
+
+    commonExprSet.foreach(expr => addFunc(expr.e))
+  }
+
+  // There are some special expressions that we should not recurse into all of its children.
+  //   1. CodegenFallback: it's children will not be used to generate code (call eval() instead)
+  //   2. If: common subexpressions will always be evaluated at the beginning, but the true and
+  //          false expressions in `If` may not get accessed, according to the predicate
+  //          expression. We should only recurse into the predicate expression.
+  //   3. CaseWhen: like `If`, the children of `CaseWhen` only get accessed in a certain
+  //                condition. We should only recurse into the first condition expression as it
+  //                will always get accessed.
+  //   4. Coalesce: it's also a conditional expression, we should only recurse into the first
+  //                children, because others may not get accessed.
+  private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
+    case _: CodegenFallback => Nil
+    case i: If => i.predicate :: Nil
+    case c: CaseWhen => c.children.head :: Nil
+    case c: Coalesce => c.children.head :: Nil
+    case other => other.children
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  private def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {
+    case i: If => Seq(Seq(i.trueValue, i.falseValue))
+    case c: CaseWhen =>
+      // We look at subexpressions in conditions and values of `CaseWhen` separately. It is
+      // because a subexpression in conditions will be run no matter which condition is matched
+      // if it is shared among conditions, but it doesn't need to be shared in values. Similarly,
+      // a subexpression among values doesn't need to be in conditions because no matter which
+      // condition is true, it will be evaluated.
+      val conditions = c.branches.tail.map(_._1)

Review comment:
       FWIW, I also addressed this issue in https://github.com/apache/spark/pull/32987 which assumed CaseWhen's (and Coalesce) should short circuit and guard later conditions. The main benefit/difference is if you have
   
   `CaseWhen(cond1, ..., cond1, ..., cond2, ...)`, `cond1` gets pulled out as a subexpression when it wouldn't otherwise even with https://github.com/apache/spark/pull/33142 I think




-- 
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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520089446



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -96,8 +151,9 @@ class EquivalentExpressions {
       case other => other.children
     }
 
-    if (!skip && !addExpr(expr)) {
-      childrenToRecurse.foreach(addExprTree)
+    if (!skip && !addFunc(expr)) {
+      childrenToRecurse.foreach(addExprTree(_, addFunc))
+      commonChildrenToRecurse(expr).filter(_.nonEmpty).foreach(addCommonExprs(_, addFunc))

Review comment:
       > childrenToRecurse is an inner method, shall we make commonChildrenToRecurse an inner method as well and put it next to childrenToRecurse?
   
   @cloud-fan That is what I did initially, but put it outside later for review comment https://github.com/apache/spark/pull/30245#discussion_r518409583. Both work for me. 




----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-723070562






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724501267


   Kubernetes integration test status success
   URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/35444/
   


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA removed a comment on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724360152


   **[Test build #130812 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130812/testReport)** for PR 30245 at commit [`16314a9`](https://github.com/apache/spark/commit/16314a91ed673a0a04a9da248b343a3c0ba07ce6).


----------------------------------------------------------------
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.

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


[GitHub] [spark] AmplabJenkins commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724501292






----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724253482


   **[Test build #130803 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130803/testReport)** for PR 30245 at commit [`cc0648a`](https://github.com/apache/spark/commit/cc0648af351cdf19700691344a227bf209fc9338).


----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-724711253


   **[Test build #130853 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130853/testReport)** for PR 30245 at commit [`b415728`](https://github.com/apache/spark/commit/b41572884401d5e02d6cda69068433376c6ab328).
    * This patch passes all tests.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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


[GitHub] [spark] cloud-fan commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
cloud-fan commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r519681590



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (expr.deterministic) {
+        if (exprSetForAll.contains(expr)) {
+          true
+        } else {
+          exprSetForAll += expr
+          false
+        }
+      } else {
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (expr.deterministic) {
+          if (exprSet.contains(expr)) {
+            true
+          } else {
+            exprSet += expr
+            false
+          }
+        } else {
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }
+
+    exprSetForAll.foreach(addFunc)
+  }
+
+  // For some special expressions we cannot just recurse into all of its children, but we can
+  // recursively add the common expressions shared between all of its children.
+  def commonChildrenToRecurse(expr: Expression): Seq[Seq[Expression]] = expr match {

Review comment:
       nit: private




----------------------------------------------------------------
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.

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


[GitHub] [spark] viirya commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
viirya commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r520198830



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,66 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()

Review comment:
       Sounds good point. `ExpressionSet` has an overhead of maintaining `originals`.




----------------------------------------------------------------
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.

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


[GitHub] [spark] dongjoon-hyun commented on a change in pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
dongjoon-hyun commented on a change in pull request #30245:
URL: https://github.com/apache/spark/pull/30245#discussion_r518408118



##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
##########
@@ -65,11 +65,46 @@ class EquivalentExpressions {
     }
   }
 
+  /**
+   * Adds only expressions which are common in each of given expressions, in a recursive way.
+   * For example, given two expressions `(a + (b + (c + 1)))` and `(d + (e + (c + 1)))`,
+   * the common expression `(c + 1)` will be added into `equivalenceMap`.
+   */
+  def addCommonExprs(exprs: Seq[Expression], addFunc: Expression => Boolean = addExpr): Unit = {
+    var exprSetForAll = ExpressionSet()
+
+    addExprTree(exprs.head, (expr: Expression) => {
+      if (exprSetForAll.contains(expr)) {
+        true
+      } else {
+        exprSetForAll += expr
+        false
+      }
+    })
+
+    exprs.tail.foreach { expr =>
+      var exprSet = ExpressionSet()
+      addExprTree(expr, (expr: Expression) => {
+        if (exprSet.contains(expr)) {
+          true
+        } else {
+          exprSet += expr
+          false
+        }
+      })
+      exprSetForAll = exprSetForAll.intersect(exprSet)
+    }

Review comment:
       Do we need to handle `head` and `tail` seperately?




----------------------------------------------------------------
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.

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


[GitHub] [spark] SparkQA commented on pull request #30245: [SPARK-33337][SQL] Support subexpression elimination in branches of conditional expressions

Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #30245:
URL: https://github.com/apache/spark/pull/30245#issuecomment-722172383


   **[Test build #130627 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/130627/testReport)** for PR 30245 at commit [`cd3776c`](https://github.com/apache/spark/commit/cd3776c1dc997e30f1c44d873b8e1ab35e567726).
    * This patch passes all tests.
    * This patch merges cleanly.
    * This patch adds no public classes.


----------------------------------------------------------------
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.

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