Re: Query optimizer 8.0.1 (and 8.0)

Short summary:
 I had the same problem - since the sort order of zip-codes, counties, city names, and states don't match, the
optimizergrossly overestimated the number of pages that would be read.
 
 I bet doing a CLUSTER by ZIP would solve that particular query, but would break similar queries by county or by city
orby state.
 
 I think   select attname,correlation from pg_stats where tablename = 'rt1'; will show you the same problem I had.  My
pg_statsnumbers are shown below.
 
 I had a couple ugly hacks that worked around the problem for myself.


Longer.

One interesting property of the TIGER data (and most geospatial
databases) is that the data for most of the columns are
"locally correlated" but not globally.  What I mean by that
is that even though data for those zip-codes probably only
resided in a few disk pages; the data was probably loaded
in order of Tiger File number (state,county), so the "correlation"
in pg_stats for zip-code was very low. With the low correlation
the optimizer couldn't see the fact that any given zip code's
data was all together on disk.  Because of this, it probably
vastly overestimated the number of pages that would be read.

Let me try a concrete example:   Zip | City          |   State  | County        | Street
------+---------------+----------+---------------+-------------99501 } Anchorage     }   AK     | Anchorage     | 1st
st.[...] 94105 | San Francisco |   CA     | San Francisco | 1st St 94105 | San Francisco |   CA     | San Francisco |
2ndSt [... a few more disk pages for 94105 ...] [... tens more disk pages for San Francisco ...] [... thousands more
diskpages for CA ...] 94501 | Alameda       |   CA     | Alameda       | 1st St 94501 | Alameda       |   CA     |
Alameda      | 2nd St [...] 02101 | Boston        |   MA     | Suffolk       | 1st St.
 

Note, that all the data for any geographical region (zip,
or city, or county) is located close together on disk.

If I do a query by City, or by State, or by Zip, I should
probably do an index scan.

But since the correlation statistic only looks the total
ordering; if we order the table so the correlation for
one column, it's statistic will look very good; but since
the columns have a different sort order the correlation
statistic for the others will be very poor.




In my copy of the TIGER data (loaded in order of
TIGER-file-number (which is ordered by state, and then
by county)), you can see the various relevant correlation
values in my database.

fl=# select  attname,correlation     from pg_stats     where tablename = 'tgr_rt1';  attname  | correlation
-----------+-------------- tigerfile |            1 rt        |            1 version   |     0.968349 tlid      |
0.151139[...] zipl      |     0.381979 zipr      |     0.376332 [...] statel    |     0.998373 stater    |      0.99855
countyl  |     0.111207 countyr   |     0.115345 cousubl   |   -0.0450375 cousubr   |   -0.0486589 [...] placel    |
0.304117 placer    |     0.306714 tractl    |     0.141538 tractr    |     0.134357 blockl    |   0.00599286 blockr
|-8.73298e-05 frlong    |    0.0857337 frlat     |     0.174396 tolong    |    0.0857399 tolat     |     0.174434
 
(45 rows)


Note, that even though the TIGER data is sorted by
State/County, "countyl" and "countyr" have some of the
worst correlations (in the stats table); because of
the way the FIPS codes work.  Every state re-cycles
the county codes starting with 1 and going up.    STATE FIPS CODE   | County FIPS code
------------------+-----------------   06 (california)   | 001 (alameda)    06 (california)   | 003 (alpine)    ...
25(massachusets) | 001 (Barnstable)
 




I have a hack for 7.4 that sets the numbers hidden
in pg_statistic used for correlation to 0.75 for these
columns; and the planner started making more reasonable
guesses.

In the end, though, I just resorted to uglier hacks
that make the planner favor index scans like setting
random_page_cost artificially low.


What I think I'd like to see is for there to be
another statistic similar to "correlation" but rather
than looking at the total-ordering of the table, to
look how correlated values within any single page are.
If someone pointed me in the right direction, I might
try doing this.
   Ron

PS:
  I think lots of other data has the same issues.  A very large name database ordered by  "lastname,firstname" will
haveall people  of a given "firstname" on a relatively small  set of pages, but the current correlation value  wouldn't
seethat.
 
  Firstname |  Lastname  |  Middlename  Adam      |  Brown     |  Albert  Adam      |  Brown     |  Alex  Adam      |
Brown    |  Bob  Bill      }  Brown     |  ....  ...  Adam      |  Smith     |  Albert  Adam      |  Smith     |  Alex
Adam     |  Smith     |  Bob  ...
 


Tom Lane wrote:
> pgsql@mohawksoft.com writes:
> 
>>   ->  Index Scan using rt1_zipr, rt1_zipl on rt1  (cost=0.00..121893.93
>>rows=30835 width=302)
>>         Index Cond: ((zipr = 2186) OR (zipl = 2186))
> 
> 
>> zipl      |        925 |
>> zipr      |        899 |
> 
> 
> Those n_distinct values for zipl and zipr seem aberrant --- too low
> compared to the estimated rowcount you're showing.  What are the
> true figures?  Also, how about some EXPLAIN ANALYZEs and not just
> EXPLAINs?
> 
>             regards, tom lane
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 8: explain analyze is your friend
>