Convert HTML docs to more streamlined TXT

[ai-pg] / full-docs / txt / row-estimation-examples.txt

69.1. Row Estimation Examples #

   The examples shown below use tables in the PostgreSQL regression test
   database. Note also that since ANALYZE uses random sampling while
   producing statistics, the results will change slightly after any new
   ANALYZE.

   Let's start with a very simple query:
EXPLAIN SELECT * FROM tenk1;

                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)

   How the planner determines the cardinality of tenk1 is covered in
   Section 14.2, but is repeated here for completeness. The number of
   pages and rows is looked up in pg_class:
SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1';

 relpages | reltuples
----------+-----------
      358 |     10000

   These numbers are current as of the last VACUUM or ANALYZE on the
   table. The planner then fetches the actual current number of pages in
   the table (this is a cheap operation, not requiring a table scan). If
   that is different from relpages then reltuples is scaled accordingly to
   arrive at a current number-of-rows estimate. In the example above, the
   value of relpages is up-to-date so the rows estimate is the same as
   reltuples.

   Let's move on to an example with a range condition in its WHERE clause:
EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                                   QUERY PLAN
-------------------------------------------------------------------​------------
-
 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
   Recheck Cond: (unique1 < 1000)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

   The planner examines the WHERE clause condition and looks up the
   selectivity function for the operator < in pg_operator. This is held in
   the column oprrest, and the entry in this case is scalarltsel. The
   scalarltsel function retrieves the histogram for unique1 from
   pg_statistic. For manual queries it is more convenient to look in the
   simpler pg_stats view:
SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='unique1';

                   histogram_bounds
------------------------------------------------------
 {0,993,1997,3050,4040,5036,5957,7057,8029,9016,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 bucket (993–1997). Assuming a linear
   distribution of values inside each bucket, we can calculate the
   selectivity as:
selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_b
uckets
            = (1 + (1000 - 993)/(1997 - 993))/10
            = 0.100697

   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.100697
     = 1007  (rounding off)

   Next let's consider an example with an equality condition in its WHERE
   clause:
EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
   Filter: (stringu1 = 'CRAAAA'::name)

   Again the planner examines the WHERE clause condition and looks up the
   selectivity function for =, which is eqsel. For equality estimation the
   histogram is not useful; instead the list of most common values (MCVs)
   is used to determine the selectivity. Let's have a look at the MCVs,
   with some additional 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        | 676
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,​JOAAAA,MCAAAA,NA
AAAA,WGAAAA}
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,​0.003,0.003,0.003
,0.003}


   Since CRAAAA appears in the list of MCVs, the selectivity is merely the
   corresponding entry in the list of most common frequencies (MCFs):
selectivity = mcf[3]
            = 0.003

   As before, the estimated number of rows is just the product of this
   with the cardinality of tenk1:
rows = 10000 * 0.003
     = 30

   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..483.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(mcv_freqs))/(num_distinct - num_mcv)
            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
                    0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)
            = 0.0014559

   That is, add up all the frequencies for the MCVs and subtract them from
   one, then divide by the number of other distinct values. This amounts
   to assuming that the fraction of the column that is not any of the MCVs
   is evenly distributed among all the other distinct values. Notice that
   there are no null values so we don't have to worry about those
   (otherwise we'd subtract the null fraction from the numerator as well).
   The estimated number of rows is then calculated as usual:
rows = 10000 * 0.0014559
     = 15  (rounding off)

   The previous example with unique1 < 1000 was an oversimplification of
   what scalarltsel really does; now that we have seen an example of the
   use of MCVs, we can fill in some more detail. The example was correct
   as far as it went, because since unique1 is a unique column it has no
   MCVs (obviously, no value is any more common than any other value). For
   a non-unique column, there will normally be both a histogram and an MCV
   list, and the histogram does not include the portion of the column
   population represented by the MCVs. We do things this way because it
   allows more precise estimation. In this situation scalarltsel directly
   applies the condition (e.g., “< 1000”) to each value of the MCV list,
   and adds up the frequencies of the MCVs for which the condition is
   true. This gives an exact estimate of the selectivity within the
   portion of the table that is MCVs. The histogram is then used in the
   same way as above to estimate the selectivity in the portion of the
   table that is not MCVs, and then the two numbers are combined to
   estimate the overall selectivity. For example, consider
EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA';

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
   Filter: (stringu1 < 'IAAAAA'::name)

   We already saw the MCV information for stringu1, and here is its
   histogram:
SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='stringu1';

                                histogram_bounds
-------------------------------------------------------------------​------------
-
 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,​XLAAAA,ZZAAAA}

   Checking the MCV list, we find that the condition stringu1 < 'IAAAAA'
   is satisfied by the first six entries and not the last four, so the
   selectivity within the MCV part of the population is
selectivity = sum(relevant mvfs)
            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
            = 0.01833333

   Summing all the MCFs also tells us that the total fraction of the
   population represented by MCVs is 0.03033333, and therefore the
   fraction represented by the histogram is 0.96966667 (again, there are
   no nulls, else we'd have to exclude them here). We can see that the
   value IAAAAA falls nearly at the end of the third histogram bucket.
   Using some rather cheesy assumptions about the frequency of different
   characters, the planner arrives at the estimate 0.298387 for the
   portion of the histogram population that is less than IAAAAA. We then
   combine the estimates for the MCV and non-MCV populations:
selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
            = 0.01833333 + 0.298387 * 0.96966667
            = 0.307669

rows        = 10000 * 0.307669
            = 3077  (rounding off)

   In this particular example, the correction from the MCV list is fairly
   small, because the column distribution is actually quite flat (the
   statistics showing these particular values as being more common than
   others are mostly due to sampling error). In a more typical case where
   some values are significantly more common than others, this complicated
   process gives a useful improvement in accuracy because the selectivity
   for the most common values is found exactly.

   Now let's consider a case with more than one condition in the WHERE
   clause:
EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx';

                                   QUERY PLAN
-------------------------------------------------------------------​------------
-
 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
   Recheck Cond: (unique1 < 1000)
   Filter: (stringu1 = 'xxx'::name)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

   The planner assumes that the two conditions are independent, so that
   the individual selectivities of the clauses can be multiplied together:
selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.100697 * 0.0014559
            = 0.0001466

rows        = 10000 * 0.0001466
            = 1  (rounding off)

   Notice that the number of rows estimated to be returned from the bitmap
   index scan reflects only the condition used with the index; this is
   important since it affects the cost estimate for the subsequent heap
   fetches.

   Finally we will examine a query that involves a join:
EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2
WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2;

                                      QUERY PLAN
-------------------------------------------------------------------​------------
-------
 Nested Loop  (cost=4.64..456.23 rows=50 width=488)
   ->  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
         Recheck Cond: (unique1 < 50)
         ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=
0)
               Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width
=244)
         Index Cond: (unique2 = t1.unique2)

   The restriction on tenk1, unique1 < 50, is evaluated before the
   nested-loop join. This is handled analogously to the previous range
   example. This time the value 50 falls into the first bucket of the
   unique1 histogram:
selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buc
kets
            = (0 + (50 - 0)/(993 - 0))/10
            = 0.005035

rows        = 10000 * 0.005035
            = 50  (rounding off)

   The restriction for the join is t2.unique2 = t1.unique2. The operator
   is just our familiar =, however the selectivity function is obtained
   from the oprjoin column of pg_operator, and is eqjoinsel. eqjoinsel
   looks up 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 and all the values
   appear to be unique (n_distinct = -1), so we use an algorithm that
   relies on the row count estimates for both relations (num_rows, not
   shown, but "tenk") together with the column null fractions (zero for
   both):
selectivity = (1 - null_frac1) * (1 - null_frac2) / max(num_rows1, num_rows2)
            = (1 - 0) * (1 - 0) / max(10000, 10000)
            = 0.0001

   This is, subtract the null fraction from one for each of the relations,
   and divide by the row count of the larger relation (this value does get
   scaled in the non-unique case). The number of rows that the join is
   likely to emit is calculated as the cardinality of the Cartesian
   product of the two inputs, multiplied by the selectivity:
rows = (outer_cardinality * inner_cardinality) * selectivity
     = (50 * 10000) * 0.0001
     = 50

   Had there been MCV lists for the two columns, eqjoinsel would have used
   direct comparison of the MCV lists to determine the join selectivity
   within the part of the column populations represented by the MCVs. The
   estimate for the remainder of the populations follows the same approach
   shown here.

   Notice that we showed inner_cardinality as 10000, that is, the
   unmodified size of tenk2. It might appear from inspection of the
   EXPLAIN output that the estimate of join rows comes from 50 * 1, that
   is, the number of outer rows times the estimated number of rows
   obtained by each inner index scan on tenk2. But this is not the case:
   the join relation size is estimated before any particular join plan has
   been considered. If everything is working well then the two ways of
   estimating the join size will produce about the same answer, but due to
   round-off error and other factors they sometimes diverge significantly.

   For those interested in further details, estimation of the size of a
   table (before any WHERE clauses) is done in
   src/backend/optimizer/util/plancat.c. The generic logic for clause
   selectivities is in src/backend/optimizer/path/clausesel.c. The
   operator-specific selectivity functions are mostly found in
   src/backend/utils/adt/selfuncs.c.