Abstract
The Golden Estimator: Efficient Range Query Estimation
by: Y. Wu, D. Agrawal, and A. El Abbadi
Abstract:
Query size estimation is crucial for many database system components.In particular, query optimizers need efficient and accurate query size estimation when deciding among alternative query plans. In this paper we propose the Golden Estimator, which is based on the socalled golden rule of sampling proposedby von Neumann, for estimating the size of single dimensional range queries.The {\\it Golden Estimator} randomly samples the frequency domain using thecumulative frequency distribution.We argue why this approach will yield good estimates irrespective of theactual underlying distribution of values.We then experimentally show that the Golden Estimator gives better approximationthan state of the art histogram based and wavelet based approaches under thesame space requirement.
Keywords:
random sampling, cumulative frequency distribution, query estimation, range query
Date:
August 2000
Document: 2000-15
