hide
Free keywords:
-
Abstract:
Query optimizers rely on accurate estimations of the sizes of intermediate
results.
Wrong size estimations can lead to overly expensive execution plans.
We first define the \emph{q-error} to measure deviations of size estimates from
actual sizes.
The q-error enables the derivation of two important results:
(1) We provide bounds such that if the q-error is smaller than this bound,
the query optimizer constructs an optimal plan.
(2) If the q-error is bounded by a number $q$, we show that
the cost of the produced plan is at most a factor of $q^4$ worse than the
optimal
plan.
Motivated by these findings, we next show how to find the best approximation
under
the q-error.
These techniques can then be used to build synopsis for size estimates.
Finally, we give some experimental results where we apply
the developed techniques.
