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.
Data Reduction Operators Work on lazy vs eager aggregation @cite_27 @cite_5 @cite_29 aims at re-arranging group-by operators in the logical query plan tree, moving them after or before joins accordingly. These techniques don't deal with avoiding materialization of intermediate results in situations when group by operators cannot be pushed down. Aggregation can only be pushed down if it can be partially applied to a single relation, thus reducing that relation's cardinality. In the general case however when the query contains a series of group by attributes, each one coming from a different relation, there's no way to apply any complex aggregation to a single relation because the aggregation applies to the result.
@cite_5 @cite_27 @cite_29
1761301028 2122265344
Efficient processing of aggregation queries is essential for decision support applications. This paper describes a class of query transformations, called eager aggregation and laty aggregation, that allows a query optimizer to move group-by operations up and down the query tree. Eager aggregation partially pushes a groupby past a join. After a group-by is partially pushed down, we still need to perform the original groupby in the upper query block. Eager aggregation reduces the number of input rows to the join and thus may result in a better overall plan. The reverse transformation, lazy aggregation, pulls a group-by above a join and combines two group-by operations into one. This transformation is typically of interest when an aggregation query references a grouped view (a view containing a groupby). Experimental results show that the technique is very beneficial for queries in the TPC-D benchmark. Assume that we have an SqL query containing joins and a group-by. The standard way of evaluating this type of query is to first perform all the joins and then the group-by operation. However, it may be possible to perform the group-by early, that is, to push the groupby operation past one or more joins. Early grouping may reduce the query processing cost by reducing the amount of data participating in joins. We formally define the problem, adhering strictly to the semantics of NULL and duplicate elimination in SqLQ and prove necessary and suficient conditions for deciding when this transfownation is valid. In practice, it may be ezpensive OT even impossible to test whether the conditions are satisfied. Therefore, we also present a more practical algorithm that tests a simpler, suficient condition. This algorithm is fast and detects a large subclass of transformable queries.