How the planner uses statistics

Поиск
Список
Период
Сортировка
Искать

How the planner uses statistics

От:
Mark Kirkwood <markir@coretech.co.nz>
Дата:
I wanted to understand how the planner 'knows' how many rows are likely
to be emitted in a given stage of a query, and wrote down some examples
for my own benefit - I then wondered if this would be a good addition to
the 'Performance Tips' chapter. So... err here it is.

Comments welcome.

best wishes

Mark

--- perform.sgml.orig	Sat Feb  5 12:45:36 2005
+++ perform.sgml	Tue Feb  8 15:08:02 2005
@@ -470,6 +470,288 @@
 
  
 
+
+ 
+  How the Planner Uses Statistics
+
+  
+   statistics
+   of the planner
+  
+
+  
+   This section builds on the material covered in the previous two and 
+   shows how the planner uses the system statistics to estimate the number of
+   rows each stage of a query might return. We will adopt the approach of 
+   showing by example, which should provide a good feel for how this works.
+  
+
+  
+   Continuing with the examples drawn from the regression test
+   database (and 8.0 sources), let's start with a simple query which has 
+   one restriction 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 - 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 = 10000 * 0.1031
+     = 1031
+
+
+  
+
+  
+   Next let's consider an example with a WHERE clause using
+   the = operator :
+
+
+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  | n_distinct |
+                           most_common_vals                              |
+                           most_common_freqs
+-------------------------------------------------------------------------+-----
+          0 |        672 |
+ {FDAAAA,NHAAAA,ATAAAA,BGAAAA,EBAAAA,MOAAAA,NDAAAA,OWAAAA,BHAAAA,BJAAAA} |
+ {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 frequency corresponding to 'ATAAAA': 
+
+
+selectivity = 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.0 - (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
+
+
+  
+
+  
+   In the case where there is more than one condition in the 
+   WHERE clause, for example :
+
+
+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))
+
+
+   then independence is assumed 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
+
+  
+ 
+  
+   Let's examine a query that includes a JOIN :
+
+
+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 initial 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 = ((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 - 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 = 51 * 10000 * 0.0001
+     = 51
+
+  
+
+ 
+
  
   Controlling the Planner with Explicit <literal>JOIN</> Clauses
 

Re: How the planner uses statistics

От:
Mark Kirkwood <markir@coretech.co.nz>
Дата:
Post feedback changes - thanks to all who commented!

Mark Kirkwood wrote:
> I wanted to understand how the planner 'knows' how many rows are likely
> to be emitted in a given stage of a query, and wrote down some examples
> for my own benefit - I then wondered if this would be a good addition to
> the 'Performance Tips' chapter. So... err here it is.
> 
> Comments welcome.
> 


--- perform.sgml.orig	Sat Feb  5 12:45:36 2005
+++ perform.sgml	Tue Feb  8 17:15:48 2005
@@ -470,6 +470,286 @@
 
  
 
+
+ 
+  How the Planner Uses Statistics
+
+  
+   statistics
+   of the planner
+  
+
+  
+   This section builds on the material covered in the previous two and 
+   shows how the planner uses the system statistics to estimate the number of
+   rows each stage of a query might return. We will adopt the approach of 
+   showing by example, which should provide a good feel for how this works.
+  
+
+  
+   Continuing with the examples drawn from the regression test
+   database (and 8.0 sources), let's start with a simple query which has 
+   one restriction 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 - 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 = 10000 * 0.1031
+     = 1031
+
+
+  
+
+  
+   Next let's consider an example with a WHERE clause using
+   the = operator:
+
+
+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 frequency corresponding to 'ATAAAA': 
+
+
+selectivity = 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.0 - (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
+
+
+  
+
+  
+   In the case where there is more than one condition in the 
+   WHERE clause, for example:
+
+
+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))
+
+
+   then independence is assumed 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
+
+  
+ 
+  
+   Let's examine a query that includes a JOIN :
+
+
+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 initial 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 = ((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 - 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 = 51 * 10000 * 0.0001
+     = 51
+
+  
+
+ 
+
  
   Controlling the Planner with Explicit <literal>JOIN</> Clauses
 


Re: How the planner uses statistics

От:
Josh Berkus <josh@agliodbs.com>
Дата:
Mark,

> > I wanted to understand how the planner 'knows' how many rows are likely
> > to be emitted in a given stage of a query, and wrote down some examples
> > for my own benefit - I then wondered if this would be a good addition to
> > the 'Performance Tips' chapter. So... err here it is.
> >
> > Comments welcome.

Terrific.   I'd be happy to post this at www.powerpostgresql.org, if you want; 
I think a lot of people would be interested.

-- 
Josh Berkus
Aglio Database Solutions
San Francisco

Re: How the planner uses statistics

От:
Michael Fuhr <mike@fuhr.org>
Дата:
On Sat, Feb 12, 2005 at 03:22:10PM -0800, Josh Berkus wrote:
> 
> Terrific.   I'd be happy to post this at www.powerpostgresql.org, if you want; 

Shouldn't that be www.powerpostgresql.com?

-- 
Michael Fuhr
http://www.fuhr.org/~mfuhr/

Re: How the planner uses statistics

От:
Mark Kirkwood <markir@coretech.co.nz>
Дата:
Josh Berkus wrote:
> Mark,
> 
> 
> Terrific.   I'd be happy to post this at www.powerpostgresql.org, if you want; 
> I think a lot of people would be interested.
>
Absolutely, that is an excellent spot for it, do you need it reformatted 
in html first?

BTW - in fact a community site may well be more appropriate for it than 
the docs, as someone has to remember to change it if (when) the 
optimizer row estimation algorithms or stats design are altered.

Mark


Re: How the planner uses statistics

От:
Josh Berkus <josh@agliodbs.com>
Дата:
Mark, Mike,

Yeah, right, powerpostgresql.com

> Absolutely, that is an excellent spot for it, do you need it reformatted
> in html first?

Or plain text, if that's easier.

> BTW - in fact a community site may well be more appropriate for it than
> the docs, as someone has to remember to change it if (when) the
> optimizer row estimation algorithms or stats design are altered.

Mind you, the Docs are versioned with each version of PostgreSQL.   So it's 
not like they wouldn't be updated.  The question is remembering to do so ...

-- 
Josh Berkus
Aglio Database Solutions
San Francisco

Re: How the planner uses statistics

От:
Mark Kirkwood <markir@coretech.co.nz>
Дата:
Josh Berkus wrote:
>
> Or plain text, if that's easier.
> 

Probably the easiest way is for me to generate the sgml -> html and send
you that. It would look like a Pg docs html page. I guess the header and
heading information might need a bit of editing (if it is obvious what
should be removed I will do the edit).

How does that sound?

At Tom's suggestion, I am going to amend the page to fit into the
'internals' chapter as opposed to 'performance tips' one. I might do
this first, and send you the resulting page.

regards

Mark


Re: How the planner uses statistics

От:
Bruce Momjian <pgman@candle.pha.pa.us>
Дата:
Mark Kirkwood wrote:
> Josh Berkus wrote:
> >
> > Or plain text, if that's easier.
> > 
> 
> Probably the easiest way is for me to generate the sgml -> html and send
> you that. It would look like a Pg docs html page. I guess the header and
> heading information might need a bit of editing (if it is obvious what
> should be removed I will do the edit).
> 
> How does that sound?
> 
> At Tom's suggestion, I am going to amend the page to fit into the
> 'internals' chapter as opposed to 'performance tips' one. I might do
> this first, and send you the resulting page.

That sounds good, that this become part of the developer docs.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: How the planner uses statistics

От:
Mark Kirkwood <markir@coretech.co.nz>
Дата:
Bruce Momjian wrote:
> Mark Kirkwood wrote:
>
>>At Tom's suggestion, I am going to amend the page to fit into the
>>'internals' chapter as opposed to 'performance tips' one. I might do
>>this first, and send you the resulting page.
>  
> That sounds good, that this become part of the developer docs.
>

Here is the amended version. I have placed it in its own chapter located
immediately after 'bki Backend Interface', however there is nothing
special about that location... feel free to move it around :-)

Mark





diff -Naur sgml.orig/filelist.sgml sgml/filelist.sgml
--- sgml.orig/filelist.sgml	Mon Feb 14 15:02:16 2005
+++ sgml/filelist.sgml	Tue Feb 15 09:52:33 2005
@@ -77,6 +77,7 @@
 
 
 
+
 
 
 
diff -Naur sgml.orig/howplanstats.sgml sgml/howplanstats.sgml
--- sgml.orig/howplanstats.sgml	Thu Jan  1 12:00:00 1970
+++ sgml/howplanstats.sgml	Tue Feb 15 17:18:30 2005
@@ -0,0 +1,370 @@
+
+
+
+ How the Planner Uses Statistics
+
+  
+   This chapter builds on the material covered in 
+   and , 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.
+  
+
+  
+   The intent of this chapter is not to document the code — 
+   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. 
+  
+
+  
+   The outputs and algorithms shown below are taken from version 8.0. 
+   The behaviour of earlier (or later) versions may vary.
+  
+
+ 
+  Row Estimation Examples
+
+  
+   row estimation
+   planner
+  
+
+  
+   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 , 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.
+  
+
+ 
+
+
+
+
+
diff -Naur sgml.orig/postgres.sgml sgml/postgres.sgml
--- sgml.orig/postgres.sgml	Mon Feb 14 14:53:24 2005
+++ sgml/postgres.sgml	Tue Feb 15 09:51:31 2005
@@ -239,6 +239,7 @@
   &gist;
   &storage;
   &bki;
+  &howplanstats;
 
  
 

Re: How the planner uses statistics

От:
Robert Treat <xzilla@users.sourceforge.net>
Дата:
On Tuesday 15 February 2005 02:34, Mark Kirkwood wrote:
> Bruce Momjian wrote:
> > Mark Kirkwood wrote:
> >>At Tom's suggestion, I am going to amend the page to fit into the
> >>'internals' chapter as opposed to 'performance tips' one. I might do
> >>this first, and send you the resulting page.
> >
> > That sounds good, that this become part of the developer docs.
>
> Here is the amended version. I have placed it in its own chapter located
> immediately after 'bki Backend Interface', however there is nothing
> special about that location... feel free to move it around :-)
>
> Mark

I thought it was more correct to use < rather than < inside of 
 tags? 

-- 
Robert Treat
Build A Brighter Lamp :: Linux Apache {middleware} PostgreSQL

Re: How the planner uses statistics

От:
Mark Kirkwood <markir@coretech.co.nz>
Дата:
Robert Treat wrote:
> 
> 
> I thought it was more correct to use < rather than < inside of 
>  tags? 
> 

I am unsure about this myself (I copied the usage from perform.sgml).

Mark

Re: How the planner uses statistics

От:
Bruce Momjian <pgman@candle.pha.pa.us>
Дата:
Robert Treat wrote:
> On Tuesday 15 February 2005 02:34, Mark Kirkwood wrote:
> > Bruce Momjian wrote:
> > > Mark Kirkwood wrote:
> > >>At Tom's suggestion, I am going to amend the page to fit into the
> > >>'internals' chapter as opposed to 'performance tips' one. I might do
> > >>this first, and send you the resulting page.
> > >
> > > That sounds good, that this become part of the developer docs.
> >
> > Here is the amended version. I have placed it in its own chapter located
> > immediately after 'bki Backend Interface', however there is nothing
> > special about that location... feel free to move it around :-)
> >
> > Mark
> 
> I thought it was more correct to use < rather than < inside of 
>  tags? 

Uh, why would you think that?  Can't you put  markup inside
 blocks?  I thought we should always use < for
literal "<" characters.

Acording to section 11 at this URL, we do need to use <

	http://newbiedoc.sourceforge.net/metadoc/docbook-guide.html

I have added reference to it in the SGML docs.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Re: How the planner uses statistics

От:
Peter Eisentraut <peter_e@gmx.net>
Дата:
Robert Treat wrote:
> I thought it was more correct to use < rather than < inside of
>  tags?

Using < is never allowed in "plain text".

-- 
Peter Eisentraut
http://developer.postgresql.org/~petere/

Re: How the planner uses statistics

От:
Bruce Momjian <pgman@candle.pha.pa.us>
Дата:

Patch applied.  Thanks.  Your documentation changes can be viewed in
five minutes using links on the developer's page,
http://www.postgresql.org/developer/testing.


---------------------------------------------------------------------------


Mark Kirkwood wrote:
> Bruce Momjian wrote:
> > Mark Kirkwood wrote:
> >
> >>At Tom's suggestion, I am going to amend the page to fit into the
> >>'internals' chapter as opposed to 'performance tips' one. I might do
> >>this first, and send you the resulting page.
> >  
> > That sounds good, that this become part of the developer docs.
> >
> 
> Here is the amended version. I have placed it in its own chapter located
> immediately after 'bki Backend Interface', however there is nothing
> special about that location... feel free to move it around :-)
> 
> Mark
> 
> 
> 
> 
> 

> diff -Naur sgml.orig/filelist.sgml sgml/filelist.sgml
> --- sgml.orig/filelist.sgml	Mon Feb 14 15:02:16 2005
> +++ sgml/filelist.sgml	Tue Feb 15 09:52:33 2005
> @@ -77,6 +77,7 @@
>  
>  
>  
> +
>  
>  
>  
> diff -Naur sgml.orig/howplanstats.sgml sgml/howplanstats.sgml
> --- sgml.orig/howplanstats.sgml	Thu Jan  1 12:00:00 1970
> +++ sgml/howplanstats.sgml	Tue Feb 15 17:18:30 2005
> @@ -0,0 +1,370 @@
> +
> +
> +
> + How the Planner Uses Statistics
> +
> +  
> +   This chapter builds on the material covered in 
> +   and , 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.
> +  
> +
> +  
> +   The intent of this chapter is not to document the code — 
> +   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. 
> +  
> +
> +  
> +   The outputs and algorithms shown below are taken from version 8.0. 
> +   The behaviour of earlier (or later) versions may vary.
> +  
> +
> + 
> +  Row Estimation Examples
> +
> +  
> +   row estimation
> +   planner
> +  
> +
> +  
> +   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 , 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.
> +  
> +
> + 
> +
> +
> +
> +
> +
> diff -Naur sgml.orig/postgres.sgml sgml/postgres.sgml
> --- sgml.orig/postgres.sgml	Mon Feb 14 14:53:24 2005
> +++ sgml/postgres.sgml	Tue Feb 15 09:51:31 2005
> @@ -239,6 +239,7 @@
>    &gist;
>    &storage;
>    &bki;
> +  &howplanstats;
>  
>   
>  
> 

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073
FAQ