Fixed-precision estimation of join selectivity

Abstract

We compare the performance of sampling-based procedures for estimation of the selectivity of an equijoin. A main result of this paper is a partial ordering that compares the variability of the estimators for the different procedures after an arbitrary fixed number of sampling steps. Our second main result is a general method for such an extension and a proof that the method is valid for all the estimation procedures under consideration. Finally, we show that, under reasonable assumptions on sampling costs, the partial ordering on the variability of the fixed-step estimation procedures implies a partial ordering on the cost of the corresponding fixed-precision estimation procedures. These results lead to a new algorithm for fixed-precision estimation of the selectivity of an equijoin. Our results can be extended to general select-join queries.