Estimating Bucket Accesses: A Practical Approach

摘要

The data base query optimization problem of estimating the number of bucket accesses, when drawing randomly and without replacement k balls from m buckets containing together n balls is discussed. The expected number of buckets from which at least one ball has been drawn depends strongly on the distribution of the balls over the buckets. A set of ball distributions covering many practical situations is defined. For a member of this set the expected number of upper and lower bound for this number can be given. A very fast method to approximate this expected number for an arbitrary member of the set is given.