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.
, describe techniques for doing @cite_18 . They describe a way to apply pre-aggregation to input relations when another aggregation is conducted on their join result. A simple hash table is used to aggregate tuples in the same relation, thus reducing the number of tuples joining with the next relation. As groups are pre-aggregated sequentially, if the number of pre-aggregated groups surpasses the memory capacity, partially pre-aggregated tuples are output to make room for new groups; therefore the pre-aggregation can be incomplete. Those same-group tuples will be aggregated later on at the final aggregation step. They also describe techniques to combine this pre-aggregation process with a join by pre-aggregating while reading the relation and joining the output partially pre-aggregated tuples with the tuples from the inner relation. These techniques however apply to a single binary join at a time, and as we show in Figure , Join-Agg provides substantial memory benefits than partial pre-aggregation especially when the two are combined and we use pre-aggregation before loading in the data graph.
@cite_18
2124645273
Partial preaggregation is a simple data reduction operator that can be applied to aggregation queries. Whenever we group and aggregate on a column set G, we can preaggregate on any column set that functionally determines G. Preaggregation can be used, for example, to reduce the input size to a join. Regular aggregation reduces the input to one record per group. Partial preaggregation exploits the fact that preaggregation need not be complete-if multiple records happen to be output for a group, they will be combined into the same group by the final aggregation. This paper describes a straightforward hash-based algorithm for partial preaggregation, discusses where it can be applied, and derives a mathematical model for estimating the output size. The effectiveness of the technique and the accuracy of the model are shown on both artificial and real data. It is also shown how to reduce memory requirements by combining partial preaggregation with the input phase of a subsequent join or sort operator. Partial preaggregation has been implemented, in part, in Microsoft SQL Server.