15th April 2019: PostgreSQL Code of Conduct Committee 2018 Annual Report

Development Versions:
devel

PostgreSQL 8.2.23 Documentation | ||||
---|---|---|---|---|

Prev | Fast Backward | Chapter 54. How the Planner Uses Statistics | Fast Forward | Next |

Using examples drawn from the regression test database, let's start with a very simple query:

EXPLAIN SELECT * FROM tenk1; QUERY PLAN ------------------------------------------------------------- Seq Scan on tenk1 (cost=0.00..445.00 rows=10000 width=244)

How the planner determines the cardinality of `tenk1`

is covered in Section 13.1, but is repeated here for
completeness. The number of rows is looked up from `pg_class`

:

SELECT reltuples, relpages FROM pg_class WHERE relname = 'tenk1'; relpages | reltuples ----------+----------- 345 | 10000

The planner will check the `relpages` estimate (this is a cheap operation)
and if incorrect may scale `reltuples`
to obtain a row estimate. In this case it does not, thus:

rows = 10000

let's move on to an example with a range condition in its
`WHERE` clause:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000; QUERY PLAN ------------------------------------------------------------ Seq Scan on tenk1 (cost=0.00..470.00 rows=1031 width=244) Filter: (unique1 < 1000)

The planner examines the `WHERE` clause
condition:

unique1 < 1000

and looks up the restriction function for the operator
`<` in `pg_operator`

. This is held in the column
`oprrest`, and the result in this case
is `scalarltsel`

. The `scalarltsel`

function retrieves the histogram
for `unique1` from `pg_statistics`

- we can follow this by using
the simpler `pg_stats`

view:

SELECT histogram_bounds FROM pg_stats WHERE tablename='tenk1' AND attname='unique1'; histogram_bounds ------------------------------------------------------ {1,970,1943,2958,3971,5069,6028,7007,7919,8982,9995}

Next the fraction of the histogram occupied by "< 1000" is worked out. This is the selectivity. The histogram divides the range into equal frequency buckets, so all we have to do is locate the bucket that our value is in and count part of it and all of the ones before. The value 1000 is clearly in the second (970 - 1943) bucket, so by assuming a linear distribution of values inside each bucket we can calculate the selectivity as:

selectivity = (1 + (1000 - bckt[2].min)/(bckt[2].max - bckt[2].min))/num_bckts = (1 + (1000 - 970)/(1943 - 970))/10 = 0.1031

that is, one whole bucket plus a linear fraction of the
second, divided by the number of buckets. The estimated number of
rows can now be calculated as the product of the selectivity and
the cardinality of `tenk1`

:

rows = rel_cardinality * selectivity = 10000 * 0.1031 = 1031

Next let's consider an example with equality condition in its
`WHERE` clause:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'ATAAAA'; QUERY PLAN ---------------------------------------------------------- Seq Scan on tenk1 (cost=0.00..470.00 rows=31 width=244) Filter: (stringu1 = 'ATAAAA'::name)

Again the planner examines the `WHERE`
clause condition:

stringu1 = 'ATAAAA'

and looks up the restriction function for `=`, which is `eqsel`

.
This case is a bit different, as the most common values —
MCVs, are used to determine
the selectivity. Let's have a look at these, with some extra
columns that will be useful later:

SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats WHERE tablename='tenk1' AND attname='stringu1'; null_frac | 0 n_distinct | 672 most_common_vals | {FDAAAA,NHAAAA,ATAAAA,BGAAAA,EBAAAA,MOAAAA,NDAAAA,OWAAAA,BHAAAA,BJAAAA} most_common_freqs | {0.00333333,0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.00266667,0.00266667}

The selectivity is merely the most common frequency (MCF) corresponding to the third MCV — 'ATAAAA':

selectivity = mcf[3] = 0.003

The estimated number of rows is just the product of this with
the cardinality of `tenk1`

as
before:

rows = 10000 * 0.003 = 30

The number displayed by `EXPLAIN` is
one more than this, due to some post estimation checks.

Now consider the same query, but with a constant that is not in the MCV list:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx'; QUERY PLAN ---------------------------------------------------------- Seq Scan on tenk1 (cost=0.00..470.00 rows=15 width=244) Filter: (stringu1 = 'xxx'::name)

This is quite a different problem, how to estimate the selectivity when the value is not in the MCV list. The approach is to use the fact that the value is not in the list, combined with the knowledge of the frequencies for all of the MCVs:

selectivity = (1 - sum(mvf))/(num_distinct - num_mcv) = (1 - (0.00333333 + 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 + 0.00266667 + 0.00266667))/(672 - 10) = 0.001465

That is, add up all the frequencies for the MCVs and subtract them from one — because it is not one of these, and divide by the remaining distinct values. Notice that there are no null values so we don't have to worry about those. The estimated number of rows is calculated as usual:

rows = 10000 * 0.001465 = 15

Let's increase the complexity to consider a case with more
than one condition in the `WHERE`
clause:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx'; QUERY PLAN ----------------------------------------------------------- Seq Scan on tenk1 (cost=0.00..495.00 rows=2 width=244) Filter: ((unique1 < 1000) AND (stringu1 = 'xxx'::name))

An assumption of independence is made and the selectivities of the individual restrictions are multiplied together:

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx') = 0.1031 * 0.001465 = 0.00015104

The row estimates are calculated as before:

rows = 10000 * 0.00015104 = 2

Finally we will examine a query that includes a `JOIN` together with a `WHERE` clause:

EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2 WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2; QUERY PLAN ----------------------------------------------------------------------------------------- Nested Loop (cost=0.00..346.90 rows=51 width=488) -> Index Scan using tenk1_unique1 on tenk1 t1 (cost=0.00..192.57 rows=51 width=244) Index Cond: (unique1 < 50) -> Index Scan using tenk2_unique2 on tenk2 t2 (cost=0.00..3.01 rows=1 width=244) Index Cond: ("outer".unique2 = t2.unique2)

The restriction on `tenk1`

"unique1 < 50" is evaluated before
the nested-loop join. This is handled analogously to the previous
range example. The restriction operator for `<` is `scalarlteqsel`

as before, but this time the
value 50 is in the first bucket of the `unique1` histogram:

selectivity = (0 + (50 - bckt[1].min)/(bckt[1].max - bckt[1].min))/num_bckts = (0 + (50 - 1)/(970 - 1))/10 = 0.005057 rows = 10000 * 0.005057 = 51

The restriction for the join is:

t2.unique2 = t1.unique2

This is due to the join method being nested-loop, with
`tenk1`

being in the outer loop. The
operator is just our familiar `=`, however
the restriction function is obtained from the `oprjoin` column of `pg_operator`

- and is `eqjoinsel`

. Additionally we use the statistical
information for both `tenk2`

and
`tenk1`

:

SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2'; tablename | null_frac | n_distinct | most_common_vals -----------+-----------+------------+------------------ tenk1 | 0 | -1 | tenk2 | 0 | -1 |

In this case there is no MCV information for `unique2` because all the values appear to be
unique, so we can use an algorithm that relies only on the number
of distinct values for both relations together with their null
fractions:

selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2) = (1 - 0) * (1 - 0) * min(1/10000, 1/1000) = 0.0001

This is, subtract the null fraction from one for each of the relations, and divide by the maximum of the two distinct values. The number of rows that the join is likely to emit is calculated as the cardinality of Cartesian product of the two nodes in the nested-loop, multiplied by the selectivity:

rows = (outer_cardinality * inner_cardinality) * selectivity = (51 * 10000) * 0.0001 = 51

For those interested in further details, estimation of the
number of rows in a relation is covered in `src/backend/optimizer/util/plancat.c`. The
calculation logic for clause selectivities is in `src/backend/optimizer/path/clausesel.c`. The
actual implementations of the operator and join restriction
functions can be found in `src/backend/utils/adt/selfuncs.c`.