Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation

systems ability to estimate the sizes of intermediate
results accurately. For this purpose, accurate approximations
of the data distributions need to be stored and maintained.
In histograms, parametric techniques, and sampling, a number
of data reduction techniques exist; however, they are limited in their
ability to estimate arbitrary distributions or their
adaptivity towards the current query workload, respectively.

Our work aims to improve the accuracy of query result-size
estimations in query optimizers by leveraging the dynamic
feedback obtained from observations on the executed query
workload. To this end, an approximate ``synopsis'' of
data-value distributions is devised that combines histograms
with parametric curve fitting, leading to a specific class
of linear splines. The approach reconciles the benefits
of histograms, simplicity and versatility, with those of
parametric techniques, especially the adaptivity to
statistically biased and dynamically evolving query
workloads.