{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/22364","repository_url":"https://api.github.com/repos/apache/spark","labels_url":"https://api.github.com/repos/apache/spark/issues/22364/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/22364/comments","events_url":"https://api.github.com/repos/apache/spark/issues/22364/events","html_url":"https://github.com/apache/spark/pull/22364","id":358279966,"node_id":"MDExOlB1bGxSZXF1ZXN0MjE0MDg2ODIz","number":22364,"title":"[SPARK-25379][SQL] Improve AttributeSet and ColumnPruning performance","user":{"login":"mgaido91","id":8821783,"node_id":"MDQ6VXNlcjg4MjE3ODM=","avatar_url":"https://avatars1.githubusercontent.com/u/8821783?v=4","gravatar_id":"","url":"https://api.github.com/users/mgaido91","html_url":"https://github.com/mgaido91","followers_url":"https://api.github.com/users/mgaido91/followers","following_url":"https://api.github.com/users/mgaido91/following{/other_user}","gists_url":"https://api.github.com/users/mgaido91/gists{/gist_id}","starred_url":"https://api.github.com/users/mgaido91/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mgaido91/subscriptions","organizations_url":"https://api.github.com/users/mgaido91/orgs","repos_url":"https://api.github.com/users/mgaido91/repos","events_url":"https://api.github.com/users/mgaido91/events{/privacy}","received_events_url":"https://api.github.com/users/mgaido91/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":10,"created_at":"2018-09-08T09:31:43Z","updated_at":"2018-09-14T10:57:58Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/22364","html_url":"https://github.com/apache/spark/pull/22364","diff_url":"https://github.com/apache/spark/pull/22364.diff","patch_url":"https://github.com/apache/spark/pull/22364.patch"},"body":"## What changes were proposed in this pull request?\r\n\r\nThis PR contains 3 optimizations:\r\n 1)  it improves significantly the operation `--` on `AttributeSet`. As a benchmark for the `--` operation, the following code has been run\r\n```\r\ntest(\"AttributeSet -- benchmark\") {\r\n    val attrSetA = AttributeSet((1 to 100).map { i => AttributeReference(s\"c$i\", IntegerType)() })\r\n    val attrSetB = AttributeSet(attrSetA.take(80).toSeq)\r\n    val attrSetC = AttributeSet((1 to 100).map { i => AttributeReference(s\"c2_$i\", IntegerType)() })\r\n    val attrSetD = AttributeSet((attrSetA.take(50) ++ attrSetC.take(50)).toSeq)\r\n    val attrSetE = AttributeSet((attrSetC.take(50) ++ attrSetA.take(50)).toSeq)\r\n    val n_iter = 1000000\r\n    val t0 = System.nanoTime()\r\n    (1 to n_iter) foreach { _ =>\r\n      val r1 = attrSetA -- attrSetB\r\n      val r2 = attrSetA -- attrSetC\r\n      val r3 = attrSetA -- attrSetD\r\n      val r4 = attrSetA -- attrSetE\r\n    }\r\n    val t1 = System.nanoTime()\r\n    val totalTime = t1 - t0\r\n    println(s\"Average time: ${totalTime / n_iter} us\")\r\n  }\r\n```\r\nThe results are:\r\n```\r\nBefore PR - Average time: 67674 us (100  %)\r\nAfter PR -  Average time: 28827 us (42.6 %)\r\n```\r\n2) In `ColumnPruning`, it replaces the occurrences of `(attributeSet1 -- attributeSet2).nonEmpty` with `attributeSet1.subsetOf(attributeSet2)` which is order of magnitudes more efficient (especially where there are many attributes). Running the previous benchmark replacing `--` with `subsetOf` returns:\r\n```\r\nAverage time: 67 us (0.1 %)\r\n```\r\n\r\n3) Provides a more efficient way of building `AttributeSet`s, which can greatly improve the performance of the methods `references` and `outputSet` of `Expression` and `QueryPlan`. This basically avoids unneeded operations (eg. creating many `AttributeEqual` wrapper classes which could be avoided)\r\n\r\nThe overall effect of those optimizations has been tested on `ColumnPruning` with the following benchmark:\r\n\r\n```\r\ntest(\"ColumnPruning benchmark\") {\r\n    val attrSetA = (1 to 100).map { i => AttributeReference(s\"c$i\", IntegerType)() }\r\n    val attrSetB = attrSetA.take(80)\r\n    val attrSetC = attrSetA.take(20).map(a => Alias(Add(a, Literal(1)), s\"${a.name}_1\")())\r\n\r\n    val input = LocalRelation(attrSetA)\r\n    val query1 = Project(attrSetB, Project(attrSetA, input)).analyze\r\n    val query2 = Project(attrSetC, Project(attrSetA, input)).analyze\r\n    val query3 = Project(attrSetA, Project(attrSetA, input)).analyze\r\n    val nIter = 100000\r\n    val t0 = System.nanoTime()\r\n    (1 to nIter).foreach { _ =>\r\n      ColumnPruning(query1)\r\n      ColumnPruning(query2)\r\n      ColumnPruning(query3)\r\n    }\r\n    val t1 = System.nanoTime()\r\n    val totalTime = t1 - t0\r\n    println(s\"Average time: ${totalTime / nIter} us\")\r\n}\r\n```\r\n\r\nThe output of the test is:\r\n\r\n```\r\nBefore PR - Average time: 733471 us (100  %)\r\nAfter PR  - Average time: 362455 us (49.4 %)\r\n```\r\n\r\nThe performance improvement has been evaluated also on the `SQLQueryTestSuite`'s queries:\r\n\r\n```\r\n(before) org.apache.spark.sql.catalyst.optimizer.ColumnPruning                                              518413198 / 1377707172                          2756 / 15717                                   \r\n(after)  org.apache.spark.sql.catalyst.optimizer.ColumnPruning                                              415432579 / 1121147950                          2756 / 15717                                   \r\n% Running time                                                                                                  80.1% / 81.3%\r\n```\r\n\r\nAlso other rules benefit especially from (3), despite the impact is lower, eg:\r\n```\r\n(before) org.apache.spark.sql.catalyst.analysis.Analyzer$ResolveReferences                                  307341442 / 623436806                           2154 / 16480                                   \r\n(after)  org.apache.spark.sql.catalyst.analysis.Analyzer$ResolveReferences                                  290511312 / 560962495                           2154 / 16480                                   \r\n% Running time                                                                                                  94.5% / 90.0%\r\n```\r\n\r\nThe reason why the impact on the `SQLQueryTestSuite`'s queries is lower compared to the other benchmark is that the optimizations are more significant when the number of attributes involved is higher. Since in the tests we often have very few attributes, the effect there is lower.\r\n\r\n## How was this patch tested?\r\n\r\nrun benchmarks + existing UTs\r\n"},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/421321628","html_url":"https://github.com/apache/spark/pull/22364#issuecomment-421321628","issue_url":"https://api.github.com/repos/apache/spark/issues/22364","id":421321628,"node_id":"MDEyOklzc3VlQ29tbWVudDQyMTMyMTYyOA==","user":{"login":"mgaido91","id":8821783,"node_id":"MDQ6VXNlcjg4MjE3ODM=","avatar_url":"https://avatars1.githubusercontent.com/u/8821783?v=4","gravatar_id":"","url":"https://api.github.com/users/mgaido91","html_url":"https://github.com/mgaido91","followers_url":"https://api.github.com/users/mgaido91/followers","following_url":"https://api.github.com/users/mgaido91/following{/other_user}","gists_url":"https://api.github.com/users/mgaido91/gists{/gist_id}","starred_url":"https://api.github.com/users/mgaido91/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mgaido91/subscriptions","organizations_url":"https://api.github.com/users/mgaido91/orgs","repos_url":"https://api.github.com/users/mgaido91/repos","events_url":"https://api.github.com/users/mgaido91/events{/privacy}","received_events_url":"https://api.github.com/users/mgaido91/received_events","type":"User","site_admin":false},"created_at":"2018-09-14T10:57:58Z","updated_at":"2018-09-14T10:57:58Z","author_association":"CONTRIBUTOR","body":"@maropu anyway I checked and that is the only other places where this pattern happens. So I am ok including it here. The point is that there the situation is a bit different, ie. it is not an `(AttributeSet -- AttributeSet).nonEmpty` case, but it is a `(AttributeSet -- Seq[Attribute]).nonEmpty`. So I am not sure the performance gain/difference will be significant in this case.\r\n\r\nI'll try and do some benchmarks and I'll do the change if I see a significant difference. Thanks."}}
{"actor":{"display_login":"mgaido91"}}