GitHub user jianqiao opened a pull request:
https://github.com/apache/incubator-quickstep/pull/185
Fuse Aggregate with HashLeftOuterJoin to accelerate evaluation
This PR fuses `Aggregate` with `HashJoin` (left outer) into the
`CrossReferenceCoalesceAggregate` node to enable fast-path evaluation for a
class of queries.
Here we briefly describe the semantics of
`CrossReferenceCoalesceAggregate`: Let `L` be a table with PRIMARY KEY `u`. Let
`R` be a table with FOREIGN KEY `x` referring to `L(u)`. Then
`CrossReferenceCoalesceAggregate` represents a common class of analytical
queries that
> For each u in L, COUNT/SUM the records in R that correspond to u (i.e.
those records satisfying R.x = L.u). In the case that there is no record for u
in R, use 0 as the result value.
That is, `CrossReferenceCoalesceAggregate` represents queries in the
following forms:
```
-- Form 1 --
SELECT u, COALESCE(count, 0), COALESCE(sum, 0)
FROM L LEFT OUTER JOIN (
SELECT x, COUNT(*) AS count, SUM(y) AS sum
FROM R
GROUP BY x) Rt ON L.u = Rt.x;
```
or (COUNT only)
```
-- Form 2 --
SELECT u, COUNT(x) AS count
FROM L LEFT OUTER JOIN R ON L.u = R.x
GROUP BY u;
```
where `L`, `R`, `u`, `v` and `SUM(...)/COUNT(...)` are arguments to
`CrossReferenceCoalesceAggregate`.
The fast-path evaluation is that, we first use `L.u` to build the
`existence_map` for a `CollisionFreeVectorTable` which is then used to perform
aggregation on `R` grouped by `R.x`. At the time of aggregation finalization,
any `existence_map` entry that is set by `L.u` but not updated with `R`'s
records will have aggregation result as `0` by default -- this implicitly
achieves the left outer join + coalesce 0 semantics.
This optimization improves TPC-H Q13's performance from ~15.5s to ~3s on a
cloudlab machine with scale factor 100.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/apache/incubator-quickstep
aggregate-on-left-outer-join
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-quickstep/pull/185.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 #185
----
commit a28b1e4d77ee12466b0801a5a7c5185f7a83e7f8
Author: Jianqiao Zhu <jianq...@cs.wisc.edu>
Date: 2017-01-30T20:46:39Z
Fuse Aggregate with LeftOuterJoin to accelerate evaluation.
----
---
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.
---
