correlation in pg_stats

Short summary:
 * It looks to me like the planner vastly overestimates    the # of pages read by index scan in quite a few of my
tableseven though stats collected by ANALYZE are correct.
 
 * The problem happens any time you have multiple columns   that have a number of repeated values in them, and   you
CLUSTERthe table by a sort using both columns   (like "city,state,zip,phone#" or "firstname,lastname").
 
 * I think this is the problem that Mark Kirkwood is seeing   in his threads Query optimizer 8.0.1 and "One Big trend
vsmultiple smaller trends" in hackers.
 
 * A test script demonstrating the issue also follows.
 * I think keeping one more stat per attribute in   pg_stastic that could describe this behavior.


Longer:  

 If I understand the optimizer correctly,  correlation is used to both guess how much random disk access will be
requiredin a query; as well as estimate how many pages will be read.
 
 Unfortunately, many tables in my larger databases have columns with values that are tightly packed on a few pages;
eventhough there is no total-ordering across the whole table. Stephan Szabo described this as a "clumping effect":
http://archives.postgresql.org/pgsql-performance/2003-01/msg00286.php

 The test script below shows a table with 6 columns and  1 million rows.
 Note that ANALYZE correctly observes that the correlation for all the columns except "A" is near zero.
 However, also note that columns A,B,C,and even D will have extremely few UNIQUE values on any given page of data.  And
conversely,an index scan on any of those columns be a good choice (as seen by EXPLAIN ANALYZE output below).
 

 Instead of just storing "correlation",  I would also like to store a variation of "correlation" that "pretends" that
thedisk-pages for a particular column were sorted by the min value for that column.  Wherever the optimizer would use
theexisting 'correlation' to estimate the number of pages that would be accesses; it could use this  "correlation
discountingthe order of blocks" value instead. All the math/stastics/theory that suggests correlation is good at
estimating# of pages would remain intact. Anyway... I've talked too much...
 

The test script showing   1) the tables  2) the values in pg_stats  3) EXPLAIN ANALYZE of columns showing the problem
follows:


********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************

fli=# create temporary table tmp1mil as     select * from            (select generate_series as a from
generate_series(0,9))as a,            (select generate_series as b from generate_series(0,9)) as b,            (select
generate_seriesas c from generate_series(0,9)) as c,            (select generate_series as d from generate_series(0,9))
asd,            (select generate_series as e from generate_series(0,9)) as e,            (select generate_series as f
fromgenerate_series(0,9)) as f     order by a,b,c,d,e,f;
 
fli-# fli-# fli-# fli-# fli-# fli-# fli-# fli-# 
SELECT
fli=# fli=# vacuum analyze tmp1mil;
VACUUM
fli=# select * from pg_stats where tablename='tmp1mil';schemaname | tablename | attname | null_frac | avg_width |
n_distinct|   most_common_vals    |                                       most_common_freqs
          | histogram_bounds | correlation 
 

------------+-----------+---------+-----------+-----------+------------+-----------------------+------------------------------------------------------------------------------------------------+------------------+-------------pg_temp_4
| tmp1mil   | a       |         0 |         4 |         10 | {7,8,5,0,6,3,4,1,2,9} |
{0.113,0.106667,0.105667,0.104333,0.101333,0.097,0.095,0.0936667,0.092,0.0913333}             |                  |
    1pg_temp_4  | tmp1mil   | b       |         0 |         4 |         10 | {1,4,0,5,6,2,9,7,3,8} |
{0.119333,0.112667,0.107,0.101,0.099,0.0976667,0.0946667,0.092,0.0886667,0.088}               |                  |
0.229754pg_temp_4 | tmp1mil   | c       |         0 |         4 |         10 | {9,5,0,1,8,6,4,7,3,2} |
{0.114667,0.107,0.103,0.101667,0.101667,0.0996667,0.0956667,0.094,0.0933333,0.0893333}        |                  |
0.142119pg_temp_4 | tmp1mil   | d       |         0 |         4 |         10 | {4,3,2,8,7,9,5,6,1,0} |
{0.114667,0.11,0.108,0.104,0.102667,0.099,0.098,0.0903333,0.0893333,0.084}                    |                  |
0.0930835pg_temp_4 | tmp1mil   | e       |         0 |         4 |         10 | {0,5,1,9,4,7,8,2,3,6} |
{0.109333,0.109333,0.108333,0.100667,0.100333,0.0983333,0.0966667,0.0936667,0.092,0.0913333}  |                  |
0.138575pg_temp_4 | tmp1mil   | f       |         0 |         4 |         10 | {2,8,6,0,3,5,9,1,7,4} |
{0.104667,0.103667,0.102667,0.102333,0.101667,0.100667,0.100667,0.0986667,0.0943333,0.0906667}|                  |
0.139991
(6 rows)

fli=# create index tmp1mil__c on tmp1mil(c);
CREATE INDEX
fli=# explain analyze select * from tmp1mil where c=5;                                                   QUERY PLAN
                                              
 
------------------------------------------------------------------------------------------------------------------Seq
Scanon tmp1mil  (cost=0.00..19853.00 rows=107001 width=24) (actual time=2.164..480.863 rows=100000 loops=1)  Filter: (c
=5)Total runtime: 531.345 ms
 
(3 rows)

fli=# explain analyze select * from tmp1mil where c=5;                                                   QUERY PLAN
                                              
 
------------------------------------------------------------------------------------------------------------------Seq
Scanon tmp1mil  (cost=0.00..19853.00 rows=107001 width=24) (actual time=2.191..481.849 rows=100000 loops=1)  Filter: (c
=5)Total runtime: 531.858 ms
 
(3 rows)


fli=# set enable_seqscan=false;
SET
fli=# explain analyze select * from tmp1mil where c=5;
QUERYPLAN                                                              
 

--------------------------------------------------------------------------------------------------------------------------------------Index
Scanusing tmp1mil__c on tmp1mil  (cost=0.00..364309.19 rows=107001 width=24) (actual time=0.102..101.460 rows=100000
loops=1) Index Cond: (c = 5)Total runtime: 152.103 ms
 
(3 rows)

fli=# explain analyze select * from tmp1mil where c=5;
QUERYPLAN                                                              
 

--------------------------------------------------------------------------------------------------------------------------------------Index
Scanusing tmp1mil__c on tmp1mil  (cost=0.00..364309.19 rows=107001 width=24) (actual time=0.082..101.298 rows=100000
loops=1) Index Cond: (c = 5)Total runtime: 151.914 ms
 
(3 rows)

fli=#