src/backend/statistics/README

   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.