GitHub user jianqiao opened a pull request: https://github.com/apache/incubator-quickstep/pull/237

## Advertising

QUICKSTEP-89 Add support for common subexpression. This PR adds support for common subexpression elimination in Quickstep. In summary we apply two kinds of optimizations: **(1)** Query rewriting for _aggregate expressions_, e.g. ``` SELECT SUM(x), SUM(x)*2, AVG(x), COUNT(x) FROM s; ``` will be rewritten as ``` SELECT sum_x, sum_x * 2, sum_x / count_x, count_x FROM ( SELECT SUM(x) AS sum_x, COUNT(x) AS count_x ) t; ``` **(2)** Common subexpression labeling with **per-storage-block memoization table** to cache result column vectors to avoid redundant computation. For example, the evaluation of expressions in ``` SELECT (x + 1) * (y + 2) * 3, (x + 1) * (y + 2), x + 1 FROM s; ``` will essentially look like: ``` t1 = x + 1 t2 = t1 * (y + 2) Out1 = t2 * 3 Out2 = Reference(t2) Out3 = Reference(t3) ``` Here `t1`, `t2`, `Out1`, `Out2`, `Out3` are per-storage-block `ColumnVector`'s. This PR together with a (later) new aggregation hash table implementation will improve the performance of TPC-H Q01 from ~11.5s to ~5.3s, with scale factor 100 on a cloud lab machine. ___ **Note**: For optimization (1), note that it is not free-of-cost to "re-project" the columns, so it may not worth doing the transformation in situations where a group-by aggregation has large number of groups. E.g., it may actually slow down the query to rewrite ``` SELECT SUM(a), SUM(b), SUM(c), SUM(d), SUM(a) FROM s GROUP BY x; ``` as ``` SELECT sum_a, sum_b, sum_c, sum_d, sum_a FROM ( SELECT SUM(a) AS sum_a, SUM(b) AS sum_b, SUM(c) AS sum_c, SUM(d) AS sum_d FROM s GROUP BY x; ) t; ``` if the number of distinct values of attribute x is large -- in that case, we avoid one duplicate computation of `SUM(a)`, but introduce 5 extra expensive column copying due to the intermediate relation `t`. Thus currently we employ a simple heuristic that if either _(1) The estimated number of groups for the Aggregate node is smaller than the specified `FLAGS_reuse_aggregate_group_size_threshold`._ or _(2) The ratio of (# of eliminable columns) to (# of original columns) is greater than the specified `FLAGS_reuse_aggregate_ratio_threshold`._ then we perform the transformation. You can merge this pull request into a Git repository by running: $ git pull https://github.com/apache/incubator-quickstep common-subexpression Alternatively you can review and apply these changes as the patch at: https://github.com/apache/incubator-quickstep/pull/237.patch To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message: This closes #237 ---- commit b31f0360a93727ed1250e8e3cf28c242c3d727a1 Author: Jianqiao Zhu <jianq...@cs.wisc.edu> Date: 2017-04-20T20:28:12Z Add common-subexpression support. ---- --- If your project is set up for it, you can reply to this email and have your reply appear on GitHub as well. If your project does not have this feature enabled and wishes so, or if the feature is enabled but not working, please contact infrastructure at infrastruct...@apache.org or file a JIRA ticket with INFRA. ---