The Golden Estimator: Efficient Range Query Estimation

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.