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 182451592 2132808937 2120113238
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. Computer systems have enjoyed an exponential growth in processor speed for the past 20 years, while main memory speed has improved only moderately. Today a cache miss to main memory takes hundreds of processor cycles. Recent studies have demonstrated that on commercial databases, about 50 or more of execution time in memory is often wasted due to cache misses. In light of this problem, a number of recent studies focused on reducing the number of cache misses of database algorithms. In this thesis, we investigate a different approach: reducing the impact of cache misses through a technique called cache prefetching. Since prefetching for sequential array accesses has been well studied, we are interested in studying non-contiguous access patterns found in two classes of database algorithms: the B+-Tree index algorithm and the hash join algorithm. We re-examine their designs with cache prefetching in mind, and combine prefetching and data locality optimizations to achieve good cache performance. For B+-Trees, we first propose and evaluate a novel main memory index structure, Prefetching B+Trees, which uses prefetching to accelerate two major access patterns of B+-Tree indices: searches and range scans. We then apply our findings in the development of a novel index structure, Fractal Prefetching B+-Trees, that optimizes index operations both for CPU cache performance and for disk performance in commercial database systems by intelligently embedding cache-optimized trees into disk pages. For hash joins, we first exploit cache prefetching separately for the I O partition phase and the join phase of the algorithm. We propose and evaluate two techniques, Group Prefetching and Software-Pipelined Prefetching, that exploit inter-tuple parallelism to overlap cache misses across the processing of multiple tuples. Then we present a novel algorithm, Inspector Joins, that exploits the free information obtained from one pass of the hash join algorithm to improve the performance of a later pass. This new algorithm addresses the memory bandwidth sharing problem in shared-bus multiprocessor systems. We compare our techniques against state-of-the-art cache-friendly algorithms for B+-Trees and hash joins through both simulation studies and real machine experiments. Our experimental results demonstrate dramatic performance benefits of our cache prefetching enabled techniques. Recently, Haas and Hellerstein proposed the hash ripple join algorithm in the context of online aggregation. Although the algorithm rapidly gives a good estimate for many join-aggregate problem instances, the convergence can be slow if the number of tuples that satisfy the join predicate is small or if there are many groups in the output. Furthermore, if memory overflows (for example, because the user allows the algorithm to run to completion for an exact answer), the algorithm degenerates to block ripple join and performance suffers. In this paper, we build on the work of Haas and Hellerstein and propose a new algorithm that (a) combines parallelism with sampling to speed convergence, and (b) maintains good performance in the presence of memory overflow. Results from a prototype implementation in a parallel DBMS show that its rate of convergence scales with the number of processors, and that when allowed to run to completion, even in the presence of memory overflow, it is competitive with the traditional parallel hybrid hash join algorithm. Online aggregation is a promising solution to achieving fast early responses for interactive ad-hoc queries that compute aggregates on a large amount of data. Essential to the success of online aggregation is a good non-blocking join algorithm that enables both (i) high early result rates with statistical guarantees and (ii) fast end-to-end query times. We analyze existing non-blocking join algorithms and find that they all provide sub-optimal early result rates, and those with fast end-to-end times achieve them only by further sacrificing their early result rates. We propose a new non-blocking join algorithm, Partitioned expanding Ripple Join (PR-Join), which achieves considerably higher early result rates than previous non-blocking joins, while also delivering fast end-to-end query times. PR-Join performs separate, ripple-like join operations on individual hash partitions, where the width of a ripple expands multiplicatively over time. This contrasts with the non-partitioned, fixed-width ripples of Block Ripple Join. Assuming, as in previous non-blocking join studies, that the input relations are in random order, PR-Join ensures representative early results that are amenable to statistical guarantees. We show both analytically and with real-machine experiments that PR-Join achieves over an order of magnitude higher early result rates than previous non-blocking joins. We also discuss the benefits of using a flash-based SSD for temporary storage, showing that PR-Join can then achieve close to optimal end-to-end performance. Finally, we consider the joining of finite data streams that arrive over time, and find that PR-Join achieves similar or higher result rates than RPJ, the state-of-the-art algorithm specialized for that domain.