JavaScript is disabled for your browser. Some features of this site may not work without it.
A Better Tool for Query Optimization

Author
Bitton, Dina; Vander Zanden, Bradley T.
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.
Date Issued
1985-04Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-671
Type
technical report