  Aggregate computation in relational databases has long been done using the
standard unary aggregation and binary join operators. These implement the
classical model of computing joins between relations two at a time,
materializing the intermediate results, and then proceeding to do either
sort-based or hash-based aggregate computation to derive the final result. This
approach, however, can be dramatically sub-optimal in the case of
low-selectivity joins, and often ends up generating large intermediate results
even if the relations involved as well as the final result sets themselves are
quite small. Moreover, many of the computed intermediate results may never be
part of the final result. In this paper we propose a novel aggregate query
processing technique that leverages graph data structures towards efficiently
answering aggregate queries over joins, without materializing intermediate join
results. We wrap this technique inside a multi-way composite database operator
called JOIN-AGG that combines Join and Aggregation. We provide a general
framework for executing aggregation queries over arbitrary acyclic joins,
involving any number of group-by attributes from any relation. We also present
a thorough experimental evaluation on both real world and synthetic datasets.
Our experiments show that our operators can achieve orders of magnitude lower
query times and memory requirements compared to the traditional approach, even
when implemented outside of the database system.
