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.
@cite_31 , presented a series of optimizations applicable to certain types of iceberg queries. The main focus of this work is to use formal methods towards whether a general SQL query would benefit from certain specialized optimizations for evaluating certain types of iceberg queries, as well as towards automatically using such optimizations during evaluation. The optimizations they consider involve pruning techniques based on memoization and complex non-equality join conditions. Given a general SQL query, their methods systematically identify if any optimization technique is applicable, and use it during execution of the query. Similarly to us, the authors implement and wrap the above optimizations into a custom database . The work in this paper is largely orthogonal to ours since it mainly deals with complex join conditions, it does not focus on minimizing extra memory consumption during execution, and is more aimed at providing formal methods for automatically identifying queries that would benefit from these specialized optimizations.
@cite_31
2612705754
Iceberg queries, commonly used for decision support, find groups whose aggregate values are above or below a threshold. In practice, iceberg queries are often posed over complex joins that are expensive to evaluate. This paper proposes a framework for combining a number of techniques---a-priori, memoization, and pruning---to optimize iceberg queries with complex joins. A-priori pushes partial GROUP BY and HAVING condition before a join to reduce its input size. Memoization caches and reuses join computation results. Pruning uses cached results to infer that certain tuples cannot contribute to the final query result, and short-circuits join computation. We formally derive conditions for correctly applying these techniques. Our practical rewrite algorithm produces highly efficient SQL that can exploit combinations of optimization opportunities in ways previously not possible. We evaluate our PostgreSQL-based implementation experimentally and show that it outperforms both baseline PostgreSQL and a commercial database system.