| 1 |
Extended statistics |
| 2 |
=================== |
| 3 |
|
| 4 |
When estimating various quantities (e.g. condition selectivities) the default |
| 5 |
approach relies on the assumption of independence. In practice that's often |
| 6 |
not true, resulting in estimation errors. |
| 7 |
|
| 8 |
Extended statistics track different types of dependencies between the columns, |
| 9 |
hopefully improving the estimates and producing better plans. |
| 10 |
|
| 11 |
|
| 12 |
Types of statistics |
| 13 |
------------------- |
| 14 |
|
| 15 |
There are currently several kinds of extended statistics: |
| 16 |
|
| 17 |
(a) ndistinct coefficients |
| 18 |
|
| 19 |
(b) soft functional dependencies (README.dependencies) |
| 20 |
|
| 21 |
(c) MCV lists (README.mcv) |
| 22 |
|
| 23 |
|
| 24 |
Compatible clause types |
| 25 |
----------------------- |
| 26 |
|
| 27 |
Each type of statistics may be used to estimate some subset of clause types. |
| 28 |
|
| 29 |
(a) functional dependencies - equality clauses (AND), possibly IS NULL |
| 30 |
|
| 31 |
(b) MCV lists - equality and inequality clauses (AND, OR, NOT), IS [NOT] NULL |
| 32 |
|
| 33 |
Currently, only OpExprs in the form Var op Const, or Const op Var are |
| 34 |
supported, however it's feasible to expand the code later to also estimate the |
| 35 |
selectivities on clauses such as Var op Var. |
| 36 |
|
| 37 |
|
| 38 |
Complex clauses |
| 39 |
--------------- |
| 40 |
|
| 41 |
We also support estimating more complex clauses - essentially AND/OR clauses |
| 42 |
with (Var op Const) as leaves, as long as all the referenced attributes are |
| 43 |
covered by a single statistics object. |
| 44 |
|
| 45 |
For example this condition |
| 46 |
|
| 47 |
(a=1) AND ((b=2) OR ((c=3) AND (d=4))) |
| 48 |
|
| 49 |
may be estimated using statistics on (a,b,c,d). If we only have statistics on |
| 50 |
(b,c,d) we may estimate the second part, and estimate (a=1) using simple stats. |
| 51 |
|
| 52 |
If we only have statistics on (a,b,c) we can't apply it at all at this point, |
| 53 |
but it's worth pointing out clauselist_selectivity() works recursively and when |
| 54 |
handling the second part (the OR-clause), we'll be able to apply the statistics. |
| 55 |
|
| 56 |
Note: The multi-statistics estimation patch also makes it possible to pass some |
| 57 |
clauses as 'conditions' into the deeper parts of the expression tree. |
| 58 |
|
| 59 |
|
| 60 |
Selectivity estimation |
| 61 |
---------------------- |
| 62 |
|
| 63 |
Throughout the planner clauselist_selectivity() still remains in charge of |
| 64 |
most selectivity estimate requests. clauselist_selectivity() can be instructed |
| 65 |
to try to make use of any extended statistics on the given RelOptInfo, which |
| 66 |
it will do if: |
| 67 |
|
| 68 |
(a) An actual valid RelOptInfo was given. Join relations are passed in as |
| 69 |
NULL, therefore are invalid. |
| 70 |
|
| 71 |
(b) The relation given actually has any extended statistics defined which |
| 72 |
are actually built. |
| 73 |
|
| 74 |
When the above conditions are met, clauselist_selectivity() first attempts to |
| 75 |
pass the clause list off to the extended statistics selectivity estimation |
| 76 |
function. This function may not find any clauses which it can perform any |
| 77 |
estimations on. In such cases, these clauses are simply ignored. When actual |
| 78 |
estimation work is performed in these functions they're expected to mark which |
| 79 |
clauses they've performed estimations for so that any other function |
| 80 |
performing estimations knows which clauses are to be skipped. |
| 81 |
|
| 82 |
Size of sample in ANALYZE |
| 83 |
------------------------- |
| 84 |
|
| 85 |
When performing ANALYZE, the number of rows to sample is determined as |
| 86 |
|
| 87 |
(300 * statistics_target) |
| 88 |
|
| 89 |
That works reasonably well for statistics on individual columns, but perhaps |
| 90 |
it's not enough for extended statistics. Papers analyzing estimation errors |
| 91 |
all use samples proportional to the table (usually finding that 1-3% of the |
| 92 |
table is enough to build accurate stats). |
| 93 |
|
| 94 |
The requested accuracy (number of MCV items or histogram bins) should also |
| 95 |
be considered when determining the sample size, and in extended statistics |
| 96 |
those are not necessarily limited by statistics_target. |
| 97 |
|
| 98 |
This however merits further discussion, because collecting the sample is quite |
| 99 |
expensive and increasing it further would make ANALYZE even more painful. |
| 100 |
Judging by the experiments with the current implementation, the fixed size |
| 101 |
seems to work reasonably well for now, so we leave this as future work. |