
Query Optimization 31
19
20
5
13
10
17
0123456789
(d) Max-diff histogram.
10 11 12 13 14 15 16 17 18 19
19
18
17
11
9
10
0123456789
(e) End-biased histogram.
10 11 12 13 14 15 16 17 18 19
FIGURE 2.5 (Continued).
In absence of multidimensional statistics, we also assume that predicates in
different columns are independent. Using these assumptions, there are simple
procedures to estimate the number of output tuples for each operator. For
instance, to estimate the cardinality of single-table range predicates we use
interpolation over the histogram buckets. Join estimation requires that we
combine information of two histograms, and involves aligning buckets and
relying on ...