Random Sampling for Histogram Construction: How much is enough?
Surajit Chaudhuri (Microsoft Research)
Rajeev Motwani (Stanford University)
Vivek Narasayya (Microsoft Research)
Random sampling is a standard technique for constructing (approximate)
histograms for query optimization. However, any real implementation in
commercial products requires solving the hard problem of determining
"How much sampling is enough?" We address this critical question
in the context of equi-height histograms used in many commercial products,
including Microsoft SQL Server. We introduce a conservative error
metric capturing the intuition that for an approximate histogram to have
low error, the error must be small in all regions of the histogram.
We then present a result establishing an optimal bound on the amount of
sampling required for pre-specified error bounds.
We also describe an adaptive page sampling algorithm
which achieves greater efficiency by using all values in a sampled page
but adjusts the amount of sampling depending
on clustering of values in pages. Next, we establish that the problem of
estimating the number of distinct values is provably difficult ,
but propose a new error metric which has a reliable estimator and can
still be exploited by query optimizers to influence the choice of
execution plans.
The algorithm for histogram construction was prototyped on Microsoft SQL
Server 7.0 and we present experimental results showing
that the adaptive algorithm accurately approximates the true histogram
over different data distributions.