← Back to branch summary

~ubuntu-branches/debian/experimental/postgresql-11/experimental

« back to all changes in this revision

Viewing changes to src/backend/statistics/README.dependencies

  • Committer: Package Import Robot
  • Author(s): Christoph Berg
  • Date: 2018-05-22 14:19:08 UTC
  • Revision ID: package-import@ubuntu.com-20180522141908-0oy9ujs1b5vrda74
Tags: upstream-11~beta1
Import upstream version 11~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/statistics/README.dependencies
 
1
Soft functional dependencies
 
2
============================
 
3
 
 
4
Functional dependencies are a concept well described in relational theory,
 
5
particularly in the definition of normalization and "normal forms". Wikipedia
 
6
has a nice definition of a functional dependency [1]:
 
7
 
 
8
    In a given table, an attribute Y is said to have a functional dependency
 
9
    on a set of attributes X (written X -> Y) if and only if each X value is
 
10
    associated with precisely one Y value. For example, in an "Employee"
 
11
    table that includes the attributes "Employee ID" and "Employee Date of
 
12
    Birth", the functional dependency
 
13
 
 
14
        {Employee ID} -> {Employee Date of Birth}
 
15
 
 
16
    would hold. It follows from the previous two sentences that each
 
17
    {Employee ID} is associated with precisely one {Employee Date of Birth}.
 
18
 
 
19
    [1] https://en.wikipedia.org/wiki/Functional_dependency
 
20
 
 
21
In practical terms, functional dependencies mean that a value in one column
 
22
determines values in some other column. Consider for example this trivial
 
23
table with two integer columns:
 
24
 
 
25
    CREATE TABLE t (a INT, b INT)
 
26
        AS SELECT i, i/10 FROM generate_series(1,100000) s(i);
 
27
 
 
28
Clearly, knowledge of the value in column 'a' is sufficient to determine the
 
29
value in column 'b', as it's simply (a/10). A more practical example may be
 
30
addresses, where the knowledge of a ZIP code (usually) determines city. Larger
 
31
cities may have multiple ZIP codes, so the dependency can't be reversed.
 
32
 
 
33
Many datasets might be normalized not to contain such dependencies, but often
 
34
it's not practical for various reasons. In some cases, it's actually a conscious
 
35
design choice to model the dataset in a denormalized way, either because of
 
36
performance or to make querying easier.
 
37
 
 
38
 
 
39
Soft dependencies
 
40
-----------------
 
41
 
 
42
Real-world data sets often contain data errors, either because of data entry
 
43
mistakes (user mistyping the ZIP code) or perhaps issues in generating the
 
44
data (e.g. a ZIP code mistakenly assigned to two cities in different states).
 
45
 
 
46
A strict implementation would either ignore dependencies in such cases,
 
47
rendering the approach mostly useless even for slightly noisy data sets, or
 
48
result in sudden changes in behavior depending on minor differences between
 
49
samples provided to ANALYZE.
 
50
 
 
51
For this reason, extended statistics implement "soft" functional dependencies,
 
52
associating each functional dependency with a degree of validity (a number
 
53
between 0 and 1). This degree is then used to combine selectivities in a
 
54
smooth manner.
 
55
 
 
56
 
 
57
Mining dependencies (ANALYZE)
 
58
-----------------------------
 
59
 
 
60
The current algorithm is fairly simple - generate all possible functional
 
61
dependencies, and for each one count the number of rows consistent with it.
 
62
Then use the fraction of rows (supporting/total) as the degree.
 
63
 
 
64
To count the rows consistent with the dependency (a => b):
 
65
 
 
66
 (a) Sort the data lexicographically, i.e. first by 'a' then 'b'.
 
67
 
 
68
 (b) For each group of rows with the same 'a' value, count the number of
 
69
     distinct values in 'b'.
 
70
 
 
71
 (c) If there's a single distinct value in 'b', the rows are consistent with
 
72
     the functional dependency, otherwise they contradict it.
 
73
 
 
74
 
 
75
Clause reduction (planner/optimizer)
 
76
------------------------------------
 
77
 
 
78
Applying the functional dependencies is fairly simple: given a list of
 
79
equality clauses, we compute selectivities of each clause and then use the
 
80
degree to combine them using this formula
 
81
 
 
82
    P(a=?,b=?) = P(a=?) * (d + (1-d) * P(b=?))
 
83
 
 
84
Where 'd' is the degree of functional dependency (a => b).
 
85
 
 
86
With more than two equality clauses, this process happens recursively. For
 
87
example for (a,b,c) we first use (a,b => c) to break the computation into
 
88
 
 
89
    P(a=?,b=?,c=?) = P(a=?,b=?) * (e + (1-e) * P(c=?))
 
90
 
 
91
where 'e' is the degree of functional dependency (a,b => c); then we can
 
92
apply (a=>b) the same way on P(a=?,b=?).
 
93
 
 
94
 
 
95
Consistency of clauses
 
96
----------------------
 
97
 
 
98
Functional dependencies only express general dependencies between columns,
 
99
without referencing particular values. This assumes that the equality clauses
 
100
are in fact consistent with the functional dependency, i.e. that given a
 
101
dependency (a=>b), the value in (b=?) clause is the value determined by (a=?).
 
102
If that's not the case, the clauses are "inconsistent" with the functional
 
103
dependency and the result will be over-estimation.
 
104
 
 
105
This may happen, for example, when using conditions on the ZIP code and city
 
106
name with mismatching values (ZIP code for a different city), etc. In such a
 
107
case, the result set will be empty, but we'll estimate the selectivity using
 
108
the ZIP code condition.
 
109
 
 
110
In this case, the default estimation based on AVIA principle happens to work
 
111
better, but mostly by chance.
 
112
 
 
113
This issue is the price for the simplicity of functional dependencies. If the
 
114
application frequently constructs queries with clauses inconsistent with
 
115
functional dependencies present in the data, the best solution is not to
 
116
use functional dependencies, but one of the more complex types of statistics.