{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/44177613","id":44177613,"diff_hunk":"@@ -0,0 +1,108 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *    http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+package org.apache.spark.sql.catalyst.expressions\n+\n+import scala.collection.mutable\n+\n+/**\n+ * This class is used to compute equality of (sub)expression trees. Expressions can be added\n+ * to this class and they subsequently query for expression equality. Expression trees are\n+ * considered equal if for the same input(s), the same result is produced.\n+ */\n+class EquivalentExpressions {\n+  /**\n+   * Wrapper around an Expression that provides semantic equality.\n+   */\n+  case class Expr(e: Expression) {\n+    val hash = e.semanticHash()\n+    override def equals(o: Any): Boolean = o match {\n+      case other: Expr => e.semanticEquals(other.e)\n+      case _ => false\n+    }\n+    override def hashCode: Int = hash\n+  }\n+\n+  // For each expression, the set of equivalent expressions.\n+  private val equivalenceMap: mutable.HashMap[Expr, mutable.MutableList[Expression]] =\n+      new mutable.HashMap[Expr, mutable.MutableList[Expression]]\n+\n+  /**\n+   * Adds each expression to this data structure, grouping them with existing equivalent\n+   * expressions. Non-recursive.\n+   * Returns if there was already a matching expression.\n+   */\n+  def addExpr(expr: Expression): Boolean = {\n+    if (expr.deterministic) {\n+      val e: Expr = Expr(expr)\n+      val f = equivalenceMap.get(e)\n+      if (f.isDefined) {\n+        f.get.+= (expr)\n+        true\n+      } else {\n+        equivalenceMap.put(e, mutable.MutableList(expr))\n+        false\n+      }\n+    } else {\n+      false\n+    }\n+  }\n+\n+  /**\n+   * Adds the expression to this datastructure recursively. Stops if a matching expression\n+   * is found. That is, if `expr` has already been added, its children are not added.\n+   * If ignoreLeaf is true, leaf nodes are ignored.\n+   */\n+  def addExprTree(root: Expression, ignoreLeaf: Boolean): Unit = {","path":"sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala","position":70,"original_position":70,"commit_id":"2feafbcc2472503048d9d81c6985c1fcdd1dab80","original_commit_id":"2feafbcc2472503048d9d81c6985c1fcdd1dab80","user":{"login":"davies","id":40902,"avatar_url":"https://avatars.githubusercontent.com/u/40902?v=3","gravatar_id":"","url":"https://api.github.com/users/davies","html_url":"https://github.com/davies","followers_url":"https://api.github.com/users/davies/followers","following_url":"https://api.github.com/users/davies/following{/other_user}","gists_url":"https://api.github.com/users/davies/gists{/gist_id}","starred_url":"https://api.github.com/users/davies/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davies/subscriptions","organizations_url":"https://api.github.com/users/davies/orgs","repos_url":"https://api.github.com/users/davies/repos","events_url":"https://api.github.com/users/davies/events{/privacy}","received_events_url":"https://api.github.com/users/davies/received_events","type":"User","site_admin":false},"body":"Since ignoreLeaf is only useful for testing, we can have a default `true` here.","created_at":"2015-11-06T19:30:41Z","updated_at":"2015-11-06T19:30:41Z","html_url":"https://github.com/apache/spark/pull/9480#discussion_r44177613","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/9480","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/44177613"},"html":{"href":"https://github.com/apache/spark/pull/9480#discussion_r44177613"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/9480"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/9480","id":49770891,"html_url":"https://github.com/apache/spark/pull/9480","diff_url":"https://github.com/apache/spark/pull/9480.diff","patch_url":"https://github.com/apache/spark/pull/9480.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/9480","number":9480,"state":"open","locked":false,"title":"[SPARK-10371] [SQL] Implement subexpr elimination for UnsafeProjections","user":{"login":"nongli","id":242468,"avatar_url":"https://avatars.githubusercontent.com/u/242468?v=3","gravatar_id":"","url":"https://api.github.com/users/nongli","html_url":"https://github.com/nongli","followers_url":"https://api.github.com/users/nongli/followers","following_url":"https://api.github.com/users/nongli/following{/other_user}","gists_url":"https://api.github.com/users/nongli/gists{/gist_id}","starred_url":"https://api.github.com/users/nongli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nongli/subscriptions","organizations_url":"https://api.github.com/users/nongli/orgs","repos_url":"https://api.github.com/users/nongli/repos","events_url":"https://api.github.com/users/nongli/events{/privacy}","received_events_url":"https://api.github.com/users/nongli/received_events","type":"User","site_admin":false},"body":"This patch adds the building blocks for codegening subexpr elimination and implements\r\nit end to end for UnsafeProjection. The building blocks can be used to do the same thing\r\nfor other operators.\r\n\r\nIt introduces some utilities to compute common sub expressions. Expressions can be added to\r\nthis data structure. The expr and its children will be recursively matched against existing\r\nexpressions (ones previously added) and grouped into common groups. This is built using\r\nthe existing `semanticEquals`. It does not understand things like commutative or associative\r\nexpressions. This can be done as future work.\r\n\r\nAfter building this data structure, the codegen process takes advantage of it by:\r\n  1. Generating a helper function in the generated class that computes the common\r\n     subexpression. This is done for all common subexpressions that have at least\r\n     two occurrences and the expression tree is sufficiently complex.\r\n  2. When generating the apply() function, if the helper function exists, call that\r\n     instead of regenerating the expression tree. Repeated calls to the helper function\r\n     shortcircuit the evaluation logic.","created_at":"2015-11-05T01:22:29Z","updated_at":"2015-11-06T19:30:41Z","closed_at":null,"merged_at":null,"merge_commit_sha":"5e0a32fe9dc9252759ce3126479be8c82ce86924","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/9480/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/9480/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/9480/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/2feafbcc2472503048d9d81c6985c1fcdd1dab80","head":{"label":"nongli:spark-10371","ref":"spark-10371","sha":"2feafbcc2472503048d9d81c6985c1fcdd1dab80","user":{"login":"nongli","id":242468,"avatar_url":"https://avatars.githubusercontent.com/u/242468?v=3","gravatar_id":"","url":"https://api.github.com/users/nongli","html_url":"https://github.com/nongli","followers_url":"https://api.github.com/users/nongli/followers","following_url":"https://api.github.com/users/nongli/following{/other_user}","gists_url":"https://api.github.com/users/nongli/gists{/gist_id}","starred_url":"https://api.github.com/users/nongli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nongli/subscriptions","organizations_url":"https://api.github.com/users/nongli/orgs","repos_url":"https://api.github.com/users/nongli/repos","events_url":"https://api.github.com/users/nongli/events{/privacy}","received_events_url":"https://api.github.com/users/nongli/received_events","type":"User","site_admin":false},"repo":{"id":30051398,"name":"spark","full_name":"nongli/spark","owner":{"login":"nongli","id":242468,"avatar_url":"https://avatars.githubusercontent.com/u/242468?v=3","gravatar_id":"","url":"https://api.github.com/users/nongli","html_url":"https://github.com/nongli","followers_url":"https://api.github.com/users/nongli/followers","following_url":"https://api.github.com/users/nongli/following{/other_user}","gists_url":"https://api.github.com/users/nongli/gists{/gist_id}","starred_url":"https://api.github.com/users/nongli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nongli/subscriptions","organizations_url":"https://api.github.com/users/nongli/orgs","repos_url":"https://api.github.com/users/nongli/repos","events_url":"https://api.github.com/users/nongli/events{/privacy}","received_events_url":"https://api.github.com/users/nongli/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/nongli/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/nongli/spark","forks_url":"https://api.github.com/repos/nongli/spark/forks","keys_url":"https://api.github.com/repos/nongli/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nongli/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nongli/spark/teams","hooks_url":"https://api.github.com/repos/nongli/spark/hooks","issue_events_url":"https://api.github.com/repos/nongli/spark/issues/events{/number}","events_url":"https://api.github.com/repos/nongli/spark/events","assignees_url":"https://api.github.com/repos/nongli/spark/assignees{/user}","branches_url":"https://api.github.com/repos/nongli/spark/branches{/branch}","tags_url":"https://api.github.com/repos/nongli/spark/tags","blobs_url":"https://api.github.com/repos/nongli/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nongli/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nongli/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/nongli/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nongli/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/nongli/spark/languages","stargazers_url":"https://api.github.com/repos/nongli/spark/stargazers","contributors_url":"https://api.github.com/repos/nongli/spark/contributors","subscribers_url":"https://api.github.com/repos/nongli/spark/subscribers","subscription_url":"https://api.github.com/repos/nongli/spark/subscription","commits_url":"https://api.github.com/repos/nongli/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/nongli/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/nongli/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/nongli/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/nongli/spark/contents/{+path}","compare_url":"https://api.github.com/repos/nongli/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nongli/spark/merges","archive_url":"https://api.github.com/repos/nongli/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nongli/spark/downloads","issues_url":"https://api.github.com/repos/nongli/spark/issues{/number}","pulls_url":"https://api.github.com/repos/nongli/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/nongli/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/nongli/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nongli/spark/labels{/name}","releases_url":"https://api.github.com/repos/nongli/spark/releases{/id}","created_at":"2015-01-30T02:01:12Z","updated_at":"2015-01-30T02:01:28Z","pushed_at":"2015-11-05T21:33:08Z","git_url":"git://github.com/nongli/spark.git","ssh_url":"git@github.com:nongli/spark.git","clone_url":"https://github.com/nongli/spark.git","svn_url":"https://github.com/nongli/spark","homepage":null,"size":124063,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"d0b56339625727744e2c30fc2167bc6a457d37f7","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","created_at":"2014-02-25T08:00:08Z","updated_at":"2015-11-06T19:12:24Z","pushed_at":"2015-11-06T19:23:35Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":1649177,"stargazers_count":6053,"watchers_count":6053,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":5627,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":369,"forks":5627,"open_issues":369,"watchers":6053,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/9480"},"html":{"href":"https://github.com/apache/spark/pull/9480"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/9480"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/9480/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/9480/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/9480/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/2feafbcc2472503048d9d81c6985c1fcdd1dab80"}}}}