Perhaps the most basic synopsis of a data stream is a sample of elements from the stream. A
key benefit of such a sample is its flexibility: the sample can serve as input to a wide variety …

Abstract Methods for Approximate Query Processing (AQP) are essential for dealing with
massive data. They are often the only means of providing interactive response times when …

Cardinality estimation is a fundamental problem in database systems. To capture the rich
joint data distributions of a relational table, most of the existing work either uses data as …

We present a new family of join algorithms, called ripple joins, for online processing of multi-
table aggregation queries in a relational database management system (DBMS). Such …

A major bottleneck in implementing sampling as a primitive relational operation is the
inefficiency of sampling the output of a query. It is not even known whether it is possible to …

In large data warehousing environments, it is often advantageous to provide fast,
approximate answers to complex aggregate queries based on statistical summaries of the …

Estimating the selectivity of a query is a key step in almost any cost-based query optimizer.
Most of today's databases rely on histograms or samples that are periodically refreshed by …

Accurately predicting the cardinality of intermediate plan operations is an essential part of
any modern relational query optimizer. The accuracy of said estimates has a strong and …

The rapidly increasing volume of information contained in relational databases places a
strain on databases, performance, and maintainability: DBAs are under greater pressure …

This paper introduces bifocal sampling, a new technique for estimating the size of an equi-
join of two relations. Bifocal sampling classifies tuples in each relation into two groups …