SIGMOD 1997, Online Aggregation

"Online Aggregation"

This paper proposes a new online aggregation interface that permits users to observe the progress of their aggregation and control execution on the fly. The system provide an answer for an aggregate query as long with confidence and a confidence interval. While the query is executed, the confidence increases.

Related work:
(a) Online Analytical Processing (OLAP)
(b) "fast-first" query processing that returns the first few tuples of the query
(c) APPROXIMATE: if the query is stopped before completion, a superset of the exact answer is returned in a combined extensional/intentional format.

When the records are retrieved in random order, a running aggregate can be viewed as a statistical estimator of the final query result.

Performance goals:
(a) minimum time to accuracy
(b) minimum time to completion
(c) pacing

Problems:

(1) statistically meaningful estimates of the precision of running aggregates are available only if records are retrieved in random order. This can be guaranteed by:
(a) hash scans: records are stored in an unspecified order. the method of CHOICE
(b) index scans: scanning an index returns tuples either in order based on some attributes (B+ --trees), or in groups based on some attributes (hash or multi-dimensional indices). Both of these techniques are inappropriate for online aggregation queries
(c) sampling from indices: NOT implemented in this project
(2) sort-based grouping algorithms are inappropriate for online aggregation: sorting is a blocking algorithm thus no output can be produced until the entire input has been processed and the aggregate for a group is computed to completion before the second group is considered.
(3) Sort-merge join are unacceptable for online aggregation
(4) hybrid hash join is useful only the inner relation is small, and in particularly if it fits into the buffer space
(5) pipeline hash join is a non-blocking hash join that treats its inner and outer relations symmetrically. Is slower than hybrid but it may fit better the online aggregations
(6) nested-loop join is the safest technique


TO DO: hybrid-hashing: what is this ? "Hashing methods and relational algebra operations." -K.Bratbergsengen, VLDB 1984

Solutions:

(a) Index Striding : the groups that have only few data are updated very infrequently. To avoid this, a new index search schema, that uses a weighted round-robin technique among all groups) is used. this technique discovers the groups first and then retrieves the tuples in a round-robin fashion.

REFERENCE:

"Online Aggregation" -Joseph M.Hellerstein, Peter J.Haas, Helen J.Wang

"Online Aggregation" -Joseph M.Hellerstein, Peter J.Haas, Helen J.Wang