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 optimizer
grossly 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 or by state.

I think
select attname,correlation from pg_stats where tablename = 'rt1';
will show you the same problem I had. My pg_stats
numbers 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 | 2nd St
[... a few more disk pages for 94105 ...]
[... tens more disk pages for San Francisco ...]
[... thousands more disk pages 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 have all people
of a given "firstname" on a relatively small
set of pages, but the current correlation value
wouldn't see that.

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(at)mohawksoft(dot)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
>