quickstep-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jianqiao <...@git.apache.org>
Subject [GitHub] incubator-quickstep pull request #185: Fuse Aggregate with HashLeftOuterJoin...
Date Thu, 09 Feb 2017 06:47:06 GMT
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 <jianqiao@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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---

Mime
View raw message