{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/25552386","id":25552386,"diff_hunk":"@@ -422,6 +424,108 @@ class Analyzer(catalog: Catalog,\n         Generate(g, join = false, outer = false, None, child)\n     }\n   }\n+\n+  /**\n+   * Transforms the query which has subquery expressions in where clause to left semi join.\n+   * select T1.x from T1 where T1.x in (select T2.y from T2) transformed to\n+   * select T1.x from T1 left semi join T2 on T1.x = T2.y.\n+   */\n+  object SubQueryExpressions extends Rule[LogicalPlan] {\n+\n+    def apply(plan: LogicalPlan): LogicalPlan = plan transform {\n+      case p: LogicalPlan if !p.childrenResolved => p\n+      case filter @ Filter(conditions, child) =>\n+        val subqueryExprs = conditions.collect {\n+          case In(exp, Seq(SubqueryExpression(subquery))) => (exp, subquery)\n+        }\n+        // Replace subqueries with a dummy true literal since they are evaluated separately now.\n+        val transformedConds = conditions.transform {\n+          case In(_, Seq(SubqueryExpression(_))) => Literal(true)\n+        }\n+        subqueryExprs match {\n+          case Seq() => filter // No subqueries.\n+          case Seq((exp, subquery)) =>\n+            createLeftSemiJoin(\n+              child,\n+              exp,\n+              subquery,\n+              transformedConds)\n+          case _ =>\n+            throw new TreeNodeException(filter, \"Only one SubQuery expression is supported.\")\n+        }\n+    }\n+\n+    /**\n+     * Create LeftSemi join with parent query to the subquery which is mentioned in 'IN' predicate\n+     * And combine the subquery conditions and parent query conditions.\n+     */ \n+    def createLeftSemiJoin(left: LogicalPlan,\n+        value: Expression,\n+        subquery: LogicalPlan,\n+        parentConds: Expression) : LogicalPlan = {\n+      val (transformedPlan, subqueryConds) = transformAndGetConditions(value, subquery)\n+      // Add both parent query conditions and subquery conditions as join conditions\n+      val allPredicates = And(parentConds, subqueryConds)\n+      Join(left, transformedPlan, LeftSemi, Some(allPredicates))\n+    }\n+\n+    /**\n+     * Transform the subquery LogicalPlan and add the expressions which are used as filters to the\n+     * projection. And also return filter conditions used in subquery\n+     */\n+    def transformAndGetConditions(value: Expression,\n+          subquery: LogicalPlan): (LogicalPlan, Expression) = {\n+      val expr = new scala.collection.mutable.ArrayBuffer[Expression]()\n+      // TODO : we only decorelate subqueries in very specific cases like the cases mentioned above\n+      // in documentation. The more complex queries like using of subqueries inside subqueries can \n+      // be supported in future.\n+      val transformedPlan = subquery transform {\n+        case project @ Project(projectList, f @ Filter(condition, child)) =>\n+          // Don't support more than one item in select list of subquery\n+          if(projectList.size > 1) {\n+            throw new TreeNodeException(\n+                project,\n+                \"SubQuery can contain only one item in Select List\")\n+          }\n+          val resolvedChild = ResolveRelations(child)\n+          // Add the expressions to the projections which are used as filters in subquery\n+          val toBeAddedExprs = f.references.filter{a =>\n+            resolvedChild.resolve(a.name, resolver) != None && !project.outputSet.contains(a)}\n+          val nameToExprMap = collection.mutable.Map[String, Alias]()\n+          // Create aliases for all projection expressions.\n+          val witAliases = (projectList ++ toBeAddedExprs).zipWithIndex.map {\n+            case (exp, index) => \n+              nameToExprMap.put(exp.name, Alias(exp, s\"sqc$index\")())\n+              Alias(exp, s\"sqc$index\")()\n+          }\n+          // Replace the condition column names with alias names.\n+          val transformedConds = condition.transform {\n+            case a: Attribute if resolvedChild.resolve(a.name, resolver) != None =>\n+              nameToExprMap.get(a.name).get.toAttribute\n+          }\n+          // Join the first projection column of subquery to the main query and add as condition\n+          // TODO : We can avoid if the parent condition already has this condition.\n+          expr += EqualTo(value, witAliases(0).toAttribute)\n+          expr += transformedConds","path":"sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/analysis/Analyzer.scala","position":102,"original_position":102,"commit_id":"7653eee3d8ded847ceeb3a03e11a507b827c5066","original_commit_id":"7653eee3d8ded847ceeb3a03e11a507b827c5066","user":{"login":"chenghao-intel","id":2367031,"avatar_url":"https://avatars.githubusercontent.com/u/2367031?v=3","gravatar_id":"","url":"https://api.github.com/users/chenghao-intel","html_url":"https://github.com/chenghao-intel","followers_url":"https://api.github.com/users/chenghao-intel/followers","following_url":"https://api.github.com/users/chenghao-intel/following{/other_user}","gists_url":"https://api.github.com/users/chenghao-intel/gists{/gist_id}","starred_url":"https://api.github.com/users/chenghao-intel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chenghao-intel/subscriptions","organizations_url":"https://api.github.com/users/chenghao-intel/orgs","repos_url":"https://api.github.com/users/chenghao-intel/repos","events_url":"https://api.github.com/users/chenghao-intel/events{/privacy}","received_events_url":"https://api.github.com/users/chenghao-intel/received_events","type":"User","site_admin":false},"body":"https://github.com/apache/spark/blob/master/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala#L544","created_at":"2015-02-28T01:50:35Z","updated_at":"2015-02-28T01:50:35Z","html_url":"https://github.com/apache/spark/pull/3249#discussion_r25552386","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/3249","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/25552386"},"html":{"href":"https://github.com/apache/spark/pull/3249#discussion_r25552386"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/3249"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/3249","id":24389045,"html_url":"https://github.com/apache/spark/pull/3249","diff_url":"https://github.com/apache/spark/pull/3249.diff","patch_url":"https://github.com/apache/spark/pull/3249.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/3249","number":3249,"state":"open","locked":false,"title":"[SPARK-4226][SQL] SparkSQL - Add support for subqueries in predicates('in' clause)","user":{"login":"ravipesala","id":8134086,"avatar_url":"https://avatars.githubusercontent.com/u/8134086?v=3","gravatar_id":"","url":"https://api.github.com/users/ravipesala","html_url":"https://github.com/ravipesala","followers_url":"https://api.github.com/users/ravipesala/followers","following_url":"https://api.github.com/users/ravipesala/following{/other_user}","gists_url":"https://api.github.com/users/ravipesala/gists{/gist_id}","starred_url":"https://api.github.com/users/ravipesala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ravipesala/subscriptions","organizations_url":"https://api.github.com/users/ravipesala/orgs","repos_url":"https://api.github.com/users/ravipesala/repos","events_url":"https://api.github.com/users/ravipesala/events{/privacy}","received_events_url":"https://api.github.com/users/ravipesala/received_events","type":"User","site_admin":false},"body":"This PR supports subqueries in preicates 'in' clause. The queries will be transformed to the LeftSemi join as mentioned below.\r\n\r\nCase 1 Uncorelated queries\r\n\r\n-- original query\r\nselect C\r\nfrom R1\r\nwhere R1.A in (Select B from R2)\r\n-- rewritten query\r\nSelect C\r\nfrom R1 left semijoin R2 on R1.A = R2.B\r\n\r\nCase 2 Corelated queries\r\n\r\n-- original query\r\nselect C\r\nfrom R1\r\nwhere R1.A in (Select B from R2 where R1.X = R2.Y)\r\n-- rewritten query\r\nselect C\r\nfrom R1 left semi join\r\n(select B, R2.Y as sq1_col0 from R2) sq1\r\non R1.X = sq1.sq1_col0 and R1.A = sq1.B\r\n\r\nRestriction : Alias need to be used as we convert it into join queries.\r\nComplete specification is available in https://issues.apache.org/jira/secure/attachment/12614003/SubQuerySpec.pdf","created_at":"2014-11-13T18:24:05Z","updated_at":"2015-02-28T01:50:35Z","closed_at":null,"merged_at":null,"merge_commit_sha":"55a4a1bda93927822fb02fce9ba890d5e6f01e59","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/3249/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/3249/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/3249/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/7653eee3d8ded847ceeb3a03e11a507b827c5066","head":{"label":"ravipesala:SPARK-4226","ref":"SPARK-4226","sha":"7653eee3d8ded847ceeb3a03e11a507b827c5066","user":{"login":"ravipesala","id":8134086,"avatar_url":"https://avatars.githubusercontent.com/u/8134086?v=3","gravatar_id":"","url":"https://api.github.com/users/ravipesala","html_url":"https://github.com/ravipesala","followers_url":"https://api.github.com/users/ravipesala/followers","following_url":"https://api.github.com/users/ravipesala/following{/other_user}","gists_url":"https://api.github.com/users/ravipesala/gists{/gist_id}","starred_url":"https://api.github.com/users/ravipesala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ravipesala/subscriptions","organizations_url":"https://api.github.com/users/ravipesala/orgs","repos_url":"https://api.github.com/users/ravipesala/repos","events_url":"https://api.github.com/users/ravipesala/events{/privacy}","received_events_url":"https://api.github.com/users/ravipesala/received_events","type":"User","site_admin":false},"repo":{"id":21731737,"name":"spark","full_name":"ravipesala/spark","owner":{"login":"ravipesala","id":8134086,"avatar_url":"https://avatars.githubusercontent.com/u/8134086?v=3","gravatar_id":"","url":"https://api.github.com/users/ravipesala","html_url":"https://github.com/ravipesala","followers_url":"https://api.github.com/users/ravipesala/followers","following_url":"https://api.github.com/users/ravipesala/following{/other_user}","gists_url":"https://api.github.com/users/ravipesala/gists{/gist_id}","starred_url":"https://api.github.com/users/ravipesala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ravipesala/subscriptions","organizations_url":"https://api.github.com/users/ravipesala/orgs","repos_url":"https://api.github.com/users/ravipesala/repos","events_url":"https://api.github.com/users/ravipesala/events{/privacy}","received_events_url":"https://api.github.com/users/ravipesala/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/ravipesala/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/ravipesala/spark","forks_url":"https://api.github.com/repos/ravipesala/spark/forks","keys_url":"https://api.github.com/repos/ravipesala/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ravipesala/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ravipesala/spark/teams","hooks_url":"https://api.github.com/repos/ravipesala/spark/hooks","issue_events_url":"https://api.github.com/repos/ravipesala/spark/issues/events{/number}","events_url":"https://api.github.com/repos/ravipesala/spark/events","assignees_url":"https://api.github.com/repos/ravipesala/spark/assignees{/user}","branches_url":"https://api.github.com/repos/ravipesala/spark/branches{/branch}","tags_url":"https://api.github.com/repos/ravipesala/spark/tags","blobs_url":"https://api.github.com/repos/ravipesala/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ravipesala/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ravipesala/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/ravipesala/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ravipesala/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/ravipesala/spark/languages","stargazers_url":"https://api.github.com/repos/ravipesala/spark/stargazers","contributors_url":"https://api.github.com/repos/ravipesala/spark/contributors","subscribers_url":"https://api.github.com/repos/ravipesala/spark/subscribers","subscription_url":"https://api.github.com/repos/ravipesala/spark/subscription","commits_url":"https://api.github.com/repos/ravipesala/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/ravipesala/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/ravipesala/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/ravipesala/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/ravipesala/spark/contents/{+path}","compare_url":"https://api.github.com/repos/ravipesala/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ravipesala/spark/merges","archive_url":"https://api.github.com/repos/ravipesala/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ravipesala/spark/downloads","issues_url":"https://api.github.com/repos/ravipesala/spark/issues{/number}","pulls_url":"https://api.github.com/repos/ravipesala/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/ravipesala/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/ravipesala/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ravipesala/spark/labels{/name}","releases_url":"https://api.github.com/repos/ravipesala/spark/releases{/id}","created_at":"2014-07-11T10:05:59Z","updated_at":"2015-02-05T18:32:03Z","pushed_at":"2015-02-27T19:20:21Z","git_url":"git://github.com/ravipesala/spark.git","ssh_url":"git@github.com:ravipesala/spark.git","clone_url":"https://github.com/ravipesala/spark.git","svn_url":"https://github.com/ravipesala/spark","homepage":null,"size":90004,"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":"57566d0af3008982a1e24a763ed2f6a700b40f8f","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-02-28T01:46:22Z","pushed_at":"2015-02-28T00:42:50Z","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":1344470,"stargazers_count":3025,"watchers_count":3025,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":2616,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":265,"forks":2616,"open_issues":265,"watchers":3025,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/3249"},"html":{"href":"https://github.com/apache/spark/pull/3249"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/3249"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/3249/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/3249/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/3249/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/7653eee3d8ded847ceeb3a03e11a507b827c5066"}}}}