{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/55272651","id":55272651,"diff_hunk":"@@ -195,9 +202,28 @@ case class Aggregate(\n     child: LogicalPlan)\n   extends UnaryNode {\n \n+  override lazy val resolved: Boolean = {\n+    val hasWindowExpressions = aggregateExpressions.exists ( _.collect {\n+        case window: WindowExpression => window\n+      }.nonEmpty\n+    )\n+\n+    !expressions.exists(!_.resolved) && childrenResolved && !hasWindowExpressions\n+  }\n+\n   override def output: Seq[Attribute] = aggregateExpressions.map(_.toAttribute)\n }\n \n+case class Window(\n+    projectList: Seq[Attribute],","path":"sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/plans/logical/basicOperators.scala","position":47,"original_position":47,"commit_id":"76fe1c89d5bb95a9928fe77401985889c3876864","original_commit_id":"76fe1c89d5bb95a9928fe77401985889c3876864","user":{"login":"gatorsmile","id":11567269,"avatar_url":"https://avatars.githubusercontent.com/u/11567269?v=3","gravatar_id":"","url":"https://api.github.com/users/gatorsmile","html_url":"https://github.com/gatorsmile","followers_url":"https://api.github.com/users/gatorsmile/followers","following_url":"https://api.github.com/users/gatorsmile/following{/other_user}","gists_url":"https://api.github.com/users/gatorsmile/gists{/gist_id}","starred_url":"https://api.github.com/users/gatorsmile/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gatorsmile/subscriptions","organizations_url":"https://api.github.com/users/gatorsmile/orgs","repos_url":"https://api.github.com/users/gatorsmile/repos","events_url":"https://api.github.com/users/gatorsmile/events{/privacy}","received_events_url":"https://api.github.com/users/gatorsmile/received_events","type":"User","site_admin":false},"body":"Sure, will do it today. @yhuai  Thanks!","created_at":"2016-03-07T21:11:06Z","updated_at":"2016-03-07T21:11:06Z","html_url":"https://github.com/apache/spark/pull/5604#discussion_r55272651","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/5604","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/55272651"},"html":{"href":"https://github.com/apache/spark/pull/5604#discussion_r55272651"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/5604"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/5604","id":33731513,"html_url":"https://github.com/apache/spark/pull/5604","diff_url":"https://github.com/apache/spark/pull/5604.diff","patch_url":"https://github.com/apache/spark/pull/5604.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/5604","number":5604,"state":"closed","locked":false,"title":"[SPARK-1442][SQL] Window Function Support for Spark SQL","user":{"login":"guowei2","id":6811813,"avatar_url":"https://avatars.githubusercontent.com/u/6811813?v=3","gravatar_id":"","url":"https://api.github.com/users/guowei2","html_url":"https://github.com/guowei2","followers_url":"https://api.github.com/users/guowei2/followers","following_url":"https://api.github.com/users/guowei2/following{/other_user}","gists_url":"https://api.github.com/users/guowei2/gists{/gist_id}","starred_url":"https://api.github.com/users/guowei2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/guowei2/subscriptions","organizations_url":"https://api.github.com/users/guowei2/orgs","repos_url":"https://api.github.com/users/guowei2/repos","events_url":"https://api.github.com/users/guowei2/events{/privacy}","received_events_url":"https://api.github.com/users/guowei2/received_events","type":"User","site_admin":false},"body":"Adding more information about the implementation...\r\n\r\nThis PR is adding the support of window functions to Spark SQL (specifically OVER and WINDOW clause). For every expression having a OVER clause, we use a WindowExpression as the container of a WindowFunction and the corresponding WindowSpecDefinition (the definition of a window frame, i.e. partition specification, order specification, and frame specification appearing in a OVER clause). \r\n# Implementation #\r\nThe high level work flow of the implementation is described as follows.\r\n\r\n*\tQuery parsing: In the query parse process, all WindowExpressions are originally placed in the projectList of a Project operator or the aggregateExpressions of an Aggregate operator. It makes our changes to simple and keep all of parsing rules for window functions at a single place (nodesToWindowSpecification). For the WINDOWclause in a query, we use a WithWindowDefinition as the container as the mapping from the name of a window specification to a WindowSpecDefinition. This changes is similar with our common table expression support.\r\n\r\n*\tAnalysis: The query analysis process has three steps for window functions.\r\n\r\n *\tResolve all WindowSpecReferences by replacing them with WindowSpecReferences according to the mapping table stored in the node of WithWindowDefinition. \r\n *\tResolve WindowFunctions in the projectList of a Project operator or the aggregateExpressions of an Aggregate operator. For this PR, we use Hive's functions for window functions because we will have a major refactoring of our internal UDAFs and it is better to switch our UDAFs after that refactoring work. \r\n *\tOnce we have resolved all WindowFunctions, we will use ResolveWindowFunction to extract WindowExpressions from projectList and aggregateExpressions and then create a Window operator for every distinct WindowSpecDefinition. With this choice, at the execution time, we can rely on the Exchange operator to do all of work on reorganizing the table and we do not need to worry about it in the physical Window operator. An example analyzed plan is shown as follows\r\n\r\n```\r\nsql(\"\"\"\r\nSELECT\r\n  year, country, product, sales,\r\n  avg(sales) over(partition by product) avg_product,\r\n  sum(sales) over(partition by country) sum_country\r\nFROM sales\r\nORDER BY year, country, product\r\n\"\"\").explain(true)\r\n\r\n== Analyzed Logical Plan ==\r\nSort [year#34 ASC,country#35 ASC,product#36 ASC], true\r\n Project [year#34,country#35,product#36,sales#37,avg_product#27,sum_country#28]\r\n  Window [year#34,country#35,product#36,sales#37,avg_product#27], [HiveWindowFunction#org.apache.hadoop.hive.ql.udf.generic.GenericUDAFSum(sales#37) WindowSpecDefinition [country#35], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING AS sum_country#28], WindowSpecDefinition [country#35], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING\r\n   Window [year#34,country#35,product#36,sales#37], [HiveWindowFunction#org.apache.hadoop.hive.ql.udf.generic.GenericUDAFAverage(sales#37) WindowSpecDefinition [product#36], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING AS avg_product#27], WindowSpecDefinition [product#36], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING\r\n    Project [year#34,country#35,product#36,sales#37]\r\n     MetastoreRelation default, sales, None\r\n```\r\n\r\n*\tQuery planning: In the process of query planning, we simple generate the physical Window operator based on the logical Window operator. Then, to prepare the executedPlan, the EnsureRequirements rule will add Exchange and Sort operators if necessary. The EnsureRequirements rule will analyze the data properties and try to not add unnecessary shuffle and sort. The physical plan for the above example query is shown below.\r\n\r\n```\r\n== Physical Plan ==\r\nSort [year#34 ASC,country#35 ASC,product#36 ASC], true\r\n Exchange (RangePartitioning [year#34 ASC,country#35 ASC,product#36 ASC], 200), []\r\n  Window [year#34,country#35,product#36,sales#37,avg_product#27], [HiveWindowFunction#org.apache.hadoop.hive.ql.udf.generic.GenericUDAFSum(sales#37) WindowSpecDefinition [country#35], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING AS sum_country#28], WindowSpecDefinition [country#35], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING\r\n   Exchange (HashPartitioning [country#35], 200), [country#35 ASC]\r\n    Window [year#34,country#35,product#36,sales#37], [HiveWindowFunction#org.apache.hadoop.hive.ql.udf.generic.GenericUDAFAverage(sales#37) WindowSpecDefinition [product#36], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING AS avg_product#27], WindowSpecDefinition [product#36], [], ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING\r\n     Exchange (HashPartitioning [product#36], 200), [product#36 ASC]\r\n      HiveTableScan [year#34,country#35,product#36,sales#37], (MetastoreRelation default, sales, None), None\r\n```\r\n\r\n*\tExecution time: At execution time, a physical Window operator buffers all rows in a partition specified in the partition spec of a OVER clause. If necessary, it also maintains a sliding window frame. The current implementation tries to buffer the input parameters of a window function according to the window frame to avoid evaluating a row multiple times. \r\n\r\n# Future work #\r\n\r\nHere are three improvements that are not hard to add:\r\n*\tTaking advantage of the window frame specification to reduce the number of rows buffered in the physical Window operator. For some cases, we only need to buffer the rows appearing in the sliding window. But for other cases, we will not be able to reduce the number of rows buffered (e.g. ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING). \r\n\r\n*\tWhen aRAGEN frame is used, for <value> PRECEDING and <value> FOLLOWING, it will be great if the <value> part is an expression (we can start with Literal). So, when the data type of ORDER BY expression is a FractionalType, we can support FractionalType as the type <value> (<value> still needs to be evaluated as a positive value).\r\n\r\n*\tWhen aRAGEN frame is used, we need to support DateType and TimestampType as the data type of the expression appearing in the order specification. Then, the <value> part of <value> PRECEDING and <value> FOLLOWING can support interval types (once we support them).\r\n\r\nThis is a joint work with @guowei2 and @yhuai \r\nThanks @hbutani @hvanhovell for his comments\r\nThanks @scwf for his comments and unit tests","created_at":"2015-04-21T06:07:23Z","updated_at":"2016-03-07T21:11:06Z","closed_at":"2015-05-06T17:54:19Z","merged_at":null,"merge_commit_sha":"710e374fc8e2bb03040cb5f1bfefc1e599e6a91e","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/5604/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/5604/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/5604/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/76fe1c89d5bb95a9928fe77401985889c3876864","head":{"label":"guowei2:windowImplement","ref":"windowImplement","sha":"76fe1c89d5bb95a9928fe77401985889c3876864","user":{"login":"guowei2","id":6811813,"avatar_url":"https://avatars.githubusercontent.com/u/6811813?v=3","gravatar_id":"","url":"https://api.github.com/users/guowei2","html_url":"https://github.com/guowei2","followers_url":"https://api.github.com/users/guowei2/followers","following_url":"https://api.github.com/users/guowei2/following{/other_user}","gists_url":"https://api.github.com/users/guowei2/gists{/gist_id}","starred_url":"https://api.github.com/users/guowei2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/guowei2/subscriptions","organizations_url":"https://api.github.com/users/guowei2/orgs","repos_url":"https://api.github.com/users/guowei2/repos","events_url":"https://api.github.com/users/guowei2/events{/privacy}","received_events_url":"https://api.github.com/users/guowei2/received_events","type":"User","site_admin":false},"repo":{"id":23093621,"name":"spark","full_name":"guowei2/spark","owner":{"login":"guowei2","id":6811813,"avatar_url":"https://avatars.githubusercontent.com/u/6811813?v=3","gravatar_id":"","url":"https://api.github.com/users/guowei2","html_url":"https://github.com/guowei2","followers_url":"https://api.github.com/users/guowei2/followers","following_url":"https://api.github.com/users/guowei2/following{/other_user}","gists_url":"https://api.github.com/users/guowei2/gists{/gist_id}","starred_url":"https://api.github.com/users/guowei2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/guowei2/subscriptions","organizations_url":"https://api.github.com/users/guowei2/orgs","repos_url":"https://api.github.com/users/guowei2/repos","events_url":"https://api.github.com/users/guowei2/events{/privacy}","received_events_url":"https://api.github.com/users/guowei2/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/guowei2/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/guowei2/spark","forks_url":"https://api.github.com/repos/guowei2/spark/forks","keys_url":"https://api.github.com/repos/guowei2/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/guowei2/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/guowei2/spark/teams","hooks_url":"https://api.github.com/repos/guowei2/spark/hooks","issue_events_url":"https://api.github.com/repos/guowei2/spark/issues/events{/number}","events_url":"https://api.github.com/repos/guowei2/spark/events","assignees_url":"https://api.github.com/repos/guowei2/spark/assignees{/user}","branches_url":"https://api.github.com/repos/guowei2/spark/branches{/branch}","tags_url":"https://api.github.com/repos/guowei2/spark/tags","blobs_url":"https://api.github.com/repos/guowei2/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/guowei2/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/guowei2/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/guowei2/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/guowei2/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/guowei2/spark/languages","stargazers_url":"https://api.github.com/repos/guowei2/spark/stargazers","contributors_url":"https://api.github.com/repos/guowei2/spark/contributors","subscribers_url":"https://api.github.com/repos/guowei2/spark/subscribers","subscription_url":"https://api.github.com/repos/guowei2/spark/subscription","commits_url":"https://api.github.com/repos/guowei2/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/guowei2/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/guowei2/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/guowei2/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/guowei2/spark/contents/{+path}","compare_url":"https://api.github.com/repos/guowei2/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/guowei2/spark/merges","archive_url":"https://api.github.com/repos/guowei2/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/guowei2/spark/downloads","issues_url":"https://api.github.com/repos/guowei2/spark/issues{/number}","pulls_url":"https://api.github.com/repos/guowei2/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/guowei2/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/guowei2/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/guowei2/spark/labels{/name}","releases_url":"https://api.github.com/repos/guowei2/spark/releases{/id}","deployments_url":"https://api.github.com/repos/guowei2/spark/deployments","created_at":"2014-08-19T02:12:50Z","updated_at":"2015-05-05T05:28:15Z","pushed_at":"2015-10-13T02:22:56Z","git_url":"git://github.com/guowei2/spark.git","ssh_url":"git@github.com:guowei2/spark.git","clone_url":"https://github.com/guowei2/spark.git","svn_url":"https://github.com/guowei2/spark","homepage":null,"size":111507,"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":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"c688e3c5e46b26cb9fdba7987139c9ea63e2458b","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}","deployments_url":"https://api.github.com/repos/apache/spark/deployments","created_at":"2014-02-25T08:00:08Z","updated_at":"2016-03-07T20:51:33Z","pushed_at":"2016-03-07T21:04:56Z","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":442607,"stargazers_count":7708,"watchers_count":7708,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":7016,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":405,"forks":7016,"open_issues":405,"watchers":7708,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/5604"},"html":{"href":"https://github.com/apache/spark/pull/5604"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/5604"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/5604/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/5604/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/5604/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/76fe1c89d5bb95a9928fe77401985889c3876864"}}}}