{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/9480","labels_url":"https://api.github.com/repos/apache/spark/issues/9480/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/9480/comments","events_url":"https://api.github.com/repos/apache/spark/issues/9480/events","html_url":"https://github.com/apache/spark/pull/9480","id":115188660,"number":9480,"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},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-11-05T01:22:29Z","updated_at":"2015-11-06T20:04:54Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/9480","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"},"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."},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/154518082","html_url":"https://github.com/apache/spark/pull/9480#issuecomment-154518082","issue_url":"https://api.github.com/repos/apache/spark/issues/9480","id":154518082,"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},"created_at":"2015-11-06T20:04:54Z","updated_at":"2015-11-06T20:04:54Z","body":"> In general, I think we'd better add more IR (Intermediate Representation, should be the Expression or Logical Plan node here) for common sub expression cases, and we then we can identify the common sub expressions and transform to the new IRs, which should be more clean for code gen part of work.\r\n\r\n>As the codegen code is a runtime behavior, which is difficult to debug and maintain, more IR will be helpful for this case, and that's also how a modern compiler works.\r\n\r\n>And I don't think the approach I described can be done right now, it's will be a big change, actually, we have lots of similar optimization like \"Common Table Expression\" (CTE), or self join can be optimized in the same way, it will be cool if we can figure a approach for the general common xxx elimination.\r\n\r\nI'm still not sure how you are suggesting we execute the version you are proposing. I'd guess you do that by adding an additional project that creates a new intermediate row and substitute the common subexpression to read from that new intermediate row. I think this is bad for performance. One of the big benefits of codegen is to remove those \"unnecessary\" intermediate rows. \r\n\r\nI agree that we should expand this logic in planning and analysis but I think the utility class to compute equivalence is reusable in other parts."}}