Query Size Estimation using Systematic Sampling
Banchong Harangsri,
John Shepherd,
Anne H.H. Ngu
International Symposium on Cooperative Database Systems for Advanced Applications,
Heian Shrine, Kyoto, December 1996.
(Compressed Postscript ... 80KB)
In this paper, we propose a new approach to the estimation of
query size for select and join operations. The technique, which we
have called "systematic sampling", is a novel variant of the
sampling approach, which sorts the relation before sampling, and
which maintains a summary relation to improve run-time performance.
We compare the method to a number of existing methods to tackle the
problem of query size estimation, and demonstrate, with extensive
experimental results, that it performs better than existing
approaches over a wide range of data sets.
Keys:
Databases,
Query optimisation,
Selectivity estimation,
Sampling
Recent Publications ...
John Shepherd ...
CSE ...
UNSW