path: root/doc/src/sgml/planstats.sgml

<!-- $PostgreSQL: pgsql/doc/src/sgml/planstats.sgml,v 1.6 2006/03/10 19:10:48 momjian Exp $ -->

<chapter id="planner-stats-details">
 <title>How the Planner Uses Statistics</title>

  <para>
   This chapter builds on the material covered in <xref linkend="using-explain">
   and <xref linkend="planner-stats">, and shows how the planner uses the 
   system statistics to estimate the number of rows each stage in a query might
   return. This is a significant part of the planning / optimizing process,
   providing much of the raw material for cost calculation.
  </para>

  <para>
   The intent of this chapter is not to document the code &mdash; 
   better done in the code itself, but to present an overview of how it works.
   This will perhaps ease the learning curve for someone who subsequently 
   wishes to read the code. As a consequence, the approach chosen is to analyze
   a series of incrementally more complex examples. 
  </para>

  <para>
   The outputs and algorithms shown below are taken from version 8.0. 
   The behavior of earlier (or later) versions may vary.
  </para>

 <sect1 id="row-estimation-examples">
  <title>Row Estimation Examples</title>

  <indexterm zone="row-estimation-examples">
   <primary>row estimation</primary>
   <secondary>planner</secondary>
  </indexterm>

  <para>
   Using examples drawn from the regression test database, let's start with a 
   very simple query:
<programlisting>
EXPLAIN SELECT * FROM tenk1;

                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..445.00 rows=10000 width=244)
</programlisting>
   
   How the planner determines the cardinality of <classname>tenk1</classname>
   is covered in <xref linkend="using-explain">, but is repeated here for
   completeness. The number of rows is looked up from 
   <classname>pg_class</classname>:

<programlisting>
SELECT reltuples, relpages FROM pg_class WHERE relname = 'tenk1';

 relpages | reltuples
----------+-----------
      345 |     10000
</programlisting>
    The planner will check the <structfield>relpages</structfield>
    estimate (this is a cheap operation) and if incorrect may scale
    <structfield>reltuples</structfield> to obtain a row estimate. In this
    case it does not, thus:

<programlisting>
rows = 10000
</programlisting>

  </para>
   
  <para>
   let's move on to an example with a range condition in its 
   <literal>WHERE</literal> clause:

<programlisting>
EXPLAIN SELECT * FROM tenk1 WHERE unique1 &lt; 1000;

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..470.00 rows=1031 width=244)
   Filter: (unique1 &lt; 1000)
</programlisting>

   The planner examines the <literal>WHERE</literal> clause condition: 

<programlisting>
unique1 &lt; 1000
</programlisting>

   and looks up the restriction function for the operator 
   <literal>&lt;</literal> in <classname>pg_operator</classname>. 
   This is held in the column <structfield>oprrest</structfield>, 
   and the result in this case is <function>scalarltsel</function>.
   The <function>scalarltsel</function> function retrieves the histogram for 
   <structfield>unique1</structfield> from <classname>pg_statistics</classname>
   - we can follow this by using the simpler <classname>pg_stats</classname> 
   view:

<programlisting>
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}
</programlisting>

   Next the fraction of the histogram occupied by <quote>&lt; 1000</quote> 
   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 <emphasis>part</emphasis> of it and 
   <emphasis>all</emphasis> 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:

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

   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 
   <classname>tenk1</classname>:

<programlisting>
rows = rel_cardinality * selectivity
     = 10000 * 0.1031
     = 1031
</programlisting>

  </para>

  <para>
   Next let's consider an example with equality condition in its 
   <literal>WHERE</literal> clause:

<programlisting>
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)
</programlisting>

   Again the planner examines the <literal>WHERE</literal> clause condition: 

<programlisting>
stringu1 = 'ATAAAA'
</programlisting>

   and looks up the restriction function for <literal>=</literal>, which is 
   <function>eqsel</function>. This case is a bit different, as the most
   common values &mdash; <acronym>MCV</acronym>s, are used to determine the 
   selectivity. Let's have a look at these, with some extra columns that will
   be useful later:

<programlisting>
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}
</programlisting>

   The selectivity is merely the most common frequency (<acronym>MCF</acronym>)
   corresponding to the third <acronym>MCV</acronym> &mdash; 'ATAAAA': 

<programlisting>
selectivity = mcf[3]
            = 0.003
</programlisting>

   The estimated number of rows is just the product of this with the 
   cardinality of <classname>tenk1</classname> as before:

<programlisting>
rows = 10000 * 0.003
     = 30
</programlisting>

   The number displayed by <command>EXPLAIN</command> is one more than this,
   due to some post estimation checks.
  </para>

  <para>
   Now consider the same query, but with a constant that is not in the 
   <acronym>MCV</acronym> list:

<programlisting>
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)
</programlisting>

   This is quite a different problem, how to estimate the selectivity when the
   value is <emphasis>not</emphasis> in the <acronym>MCV</acronym> 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
   <acronym>MCV</acronym>s:

<programlisting>
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
</programlisting>

   That is, add up all the frequencies for the <acronym>MCV</acronym>s and 
   subtract them from one &mdash; because it is <emphasis>not</emphasis> one 
   of these, and divide by the <emphasis>remaining</emphasis> 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:

<programlisting>
rows = 10000 * 0.001465
     = 15
</programlisting>

  </para>

  <para>
   Let's increase the complexity to consider a case with more than one 
   condition in the <literal>WHERE</literal> clause:

<programlisting>
EXPLAIN SELECT * FROM tenk1 WHERE unique1 &lt; 1000 AND stringu1 = 'xxx';

                       QUERY PLAN
-----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..495.00 rows=2 width=244)
   Filter: ((unique1 &lt; 1000) AND (stringu1 = 'xxx'::name))
</programlisting>

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

<programlisting>
selectivity = selectivity(unique1 &lt; 1000) * selectivity(stringu1 = 'xxx')
            = 0.1031 * 0.001465
            = 0.00015104
</programlisting>

   The row estimates are calculated as before:

<programlisting>
rows = 10000 * 0.00015104
     = 2
</programlisting>
  </para>
 
  <para>
   Finally we will examine a query that includes a <literal>JOIN</literal> 
   together with a <literal>WHERE</literal> clause:

<programlisting>
EXPLAIN SELECT *  FROM tenk1 t1, tenk2 t2 
WHERE t1.unique1 &lt; 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 &lt; 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..3.01 rows=1 width=244)
         Index Cond: ("outer".unique2 = t2.unique2)
</programlisting>

   The restriction on <classname>tenk1</classname> 
   <quote>unique1 &lt; 50</quote> is evaluated before the nested-loop join. 
   This is handled analogously to the previous range example. The restriction 
   operator for <literal>&lt;</literal> is <function>scalarlteqsel</function> 
   as before, but this time the value 50 is in the first bucket of the 
   <structfield>unique1</structfield> histogram:

<programlisting>
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
</programlisting>

   The restriction for the join is:

<programlisting>
t2.unique2 = t1.unique2
</programlisting>

   This is due to the join method being nested-loop, with 
   <classname>tenk1</classname> being in the outer loop. The operator is just 
   our familiar <literal>=</literal>, however the restriction function is 
   obtained from the <structfield>oprjoin</structfield> column of 
   <classname>pg_operator</classname> - and is <function>eqjoinsel</function>.
   Additionally we use the statistical information for both 
   <classname>tenk2</classname> and <classname>tenk1</classname>:

<programlisting>
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 |
</programlisting>

   In this case there is no <acronym>MCV</acronym> information for 
   <structfield>unique2</structfield> 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:

<programlisting>
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
</programlisting>

   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:

<programlisting>
rows = (outer_cardinality * inner_cardinality) * selectivity
     = (51 * 10000) * 0.0001
     = 51
</programlisting>
  </para>

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

 </sect1>


</chapter>

<!-- Keep this comment at the end of the file
Local variables:
mode:sgml
sgml-omittag:nil
sgml-shorttag:t
sgml-minimize-attributes:nil
sgml-always-quote-attributes:t
sgml-indent-step:1
sgml-indent-data:t
sgml-parent-document:nil
sgml-default-dtd-file:"./reference.ced"
sgml-exposed-tags:nil
sgml-local-catalogs:("/usr/lib/sgml/catalog")
sgml-local-ecat-files:nil
End:
-->