We develop a novel method, based on the statistical concept of VC-dimension,
for selecting a small representative sample from a large database. The
execution of a query on the sample provides an accurate estimate for the
selectivity (or cardinality of the output) of each operation in the execution
of the query on the original large database. The size of the sample does not
depend on the size (number of tuples) of the database, but is a function of the
complexity of the queries we plan to run, measured by their VC-dimension. The
major theoretical contribution of this work is an explicit bound on the
VC-dimension of a range space defined by all possible outcomes of a collection
of queries. We prove that the VC-dimension is a function of the maximum number
of Boolean operations in the selection predicate, and of the maximum number of
select and join operations in any individual query in the collection, but it is
not a function of the number of queries in the collection. The sample
representation computed by our method is typically sufficiently small to be
stored in main memory. Once a sample representation is precomputed, it can be
used to evaluate the selectivity of multiple queries belonging to the
collection. The sample needs to be refreshed only following major changes in
the database. We present experimental results validating our theoretical
analysis and demonstrating the efficiency and accuracy of our technique. We
compared the selectivity estimates obtained from the sample with
histogram-based estimates obtained from the PostgreSQL query plan optimizer.
The results show that the former estimates are more accurate and respect the
theoretical guarantees, even with small sample sizes and for complex queries.