Online aggregation provides estimates to the final result of a computation during the actual processing. The user can stop the computation as soon as the estimate is accurate enough, typically early in the execution. This allows for the interactive data exploration of the largest datasets. In this paper we introduce the first framework for parallel online aggregation in which the estimation virtually does not incur any overhead on top of the actual execution. We define a generic interface to express any estimation model that abstracts completely the execution details. We design a novel estimator specifically targeted at parallel online aggregation. When executed by the framework over a massive @math TPC-H instance, the estimator provides accurate confidence bounds early in the execution even when the cardinality of the final result is seven orders of magnitude smaller than the dataset size and without incurring overhead.
It is the work in @cite_13 where HOP is elevated to a real online aggregation system by providing an estimation mechanism. The proposed solution is a Bayesian framework to handle the correlation between the time to process a data partition and the result it generates. This is required because chunks are treated as black boxes that only produce an aggregate. There is no information on what operation was performed to generate the aggregate or on the content of the chunk. Based on the aggregates produced by the processed chunks and the time it took to schedule and process the chunk, a prediction is made for the aggregates in the chunks not scheduled yet---the processed chunks are an independent and identically distributed (iid) sample from the entire chunk population. The Bayesian model is continuously updated as more chunks are processed. This results in more accurate estimates as more data are processed. Although this estimation model is not based on sampling, it can still be expressed as a GLA using the extended UDA interface. We plan to do this in future work to further validate the expressiveness of the PF-OLA framework.
@cite_13
2164507334
In online aggregation, a database system processes a user’s aggregation query in an online fashion. At all times during processing, the system gives the user an estimate of the final query result, with the confidence bounds that become tighter over time. In this paper, we consider how online aggregation can be built into a MapReduce system for large-scale data processing. Given the MapReduce paradigm’s close relationship with cloud computing (in that one might expect a large fraction of MapReduce jobs to be run in the cloud), online aggregation is a very attractive technology. Since large-scale cloud computations are typically pay-as-you-go, a user can monitor the accuracy obtained in an online fashion, and then save money by killing the computation early once sufficient accuracy has been obtained.