A Better Tool for Query Optimization

Abstract

When evaluating the performance of a query strategy, one must often estimate the number of distinct values of an attribute in a randomly selected subset of a relation. Most query optimizers compute this estimate based on the assumption that prior to the selection, the attribute values are uniformly distributed in the relation. In this paper we depart from this assumption and instead consider Zipf distributions that are known to accurately model text and name distributions. Given a relation of cardinality $n$ where a non-key attribute $A$ has a Zipf distribution, we derive both an exact formula and an approximate non-iterative formula for the expected number of distinct $A$-values contained in a sample of $k$ randomly selected tuples. The approximation is accurate, and it is very easy to compute. Thus it provides a practical tool to deal with non-uniform distributions in query optimization.