pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedDoes "correlation" mislead the optimizer on large tables?
8+ messages / 4 participants
[nested] [flat]
* Does "correlation" mislead the optimizer on large tables?
@ 2003-01-24 04:16 Ron Mayer <ron@intervideo.com>
0 siblings, 1 reply; 8+ messages in thread
From: Ron Mayer @ 2003-01-24 04:16 UTC (permalink / raw)
To: pgsql-performance; +Cc: Ron Mayer <ron@intervideo.com>
Short summary:
On a large tables, I think the "correlation" pg_stats field as calculated
by "vacuum analyze" or "analyze" can mislead the optimizer.
By forcing index scans on some queries shown below, some queries
in my database speed up from 197 seconds to under 30 seconds.
I'd like feedback on whether or not having a smarter "analyze"
function (which I think I could write as a separate utility) would
help me situations like this.
Longer:
In particular, if I have a large table t with columns 'a','b','c', etc,
and I cluster the table as follows:
create table t_ordered as select * from t order by a,b;
vacuum analyze t_ordered;
Column "b" will (correctly) get a very low "correlation" in
the pg_stats table -- but I think the optimizer would do better
assuming a high correlation because similar 'b' values are still
grouped closely on the same disk pages.
Below is a real-world example of this issue.
The table "fact" is a large one (reltuples = 1e8, relpages = 1082385)
and contains about 1 years worth of data. The data was loaded
sequentialy (ordered by dat,tim).
logs=# \d fact;
Table "fact"
Column | Type | Modifiers
--------+------------------------+-----------
dat | date |
tim | time without time zone |
ip_id | integer |
bid_id | integer |
req_id | integer |
ref_id | integer |
uag_id | integer |
Indexes: i_fact_2__bid_id,
i_fact_2__dat,
i_fact_2__tim,
i_fact_2__ip_id,
i_fact_2__ref_id,
i_fact_2__req_id
With a table this large, each day's worth of data contains
about 3000 pages; or conversely, each page contains only about
a 30 second range of values for "tim".
As shown in the queries below, the optimizer wanted to do
a sequential scan when looking at a 10 minute part of the day.
However also as shown, forcing an index scan did much better.
I'm guessing this happened because the optimizer saw the
horrible correlation, and decided it would have to read
an enormous number of pages if it did an index scan.
===========================================
logs=# select tablename,attname,n_distinct,correlation from pg_stats where tablename='fact';
tablename | attname | n_distinct | correlation
-----------+---------+------------+-------------
fact | dat | 365 | 1
fact | tim | 80989 | -0.00281447
fact | ip_id | 44996 | 0.660689
fact | bid_id | 742850 | 0.969026
fact | req_id | 2778 | 0.67896
fact | ref_id | 595 | 0.258023
fact | uag_id | 633 | 0.234216
(7 rows)
logs=# explain analyze select * from fact where tim<'00:10:00';
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Seq Scan on fact (cost=0.00..1949838.40 rows=526340 width=32) (actual time=0.39..197447.50 rows=402929 loops=1)
Filter: (tim < '00:10:00'::time without time zone)
Total runtime: 197810.01 msec
(3 rows)
logs=# explain analyze select * from fact where tim<'00:10:00';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Seq Scan on fact (cost=0.00..1949838.40 rows=526340 width=32) (actual time=15.25..156705.76 rows=402929 loops=1)
Filter: (tim < '00:10:00'::time without time zone)
Total runtime: 157089.15 msec
(3 rows)
logs=# set enable_seqscan = off;
SET
logs=# explain analyze select * from fact where tim<'00:10:00';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
Index Scan using i__fact__tim on fact (cost=0.00..2110978.39 rows=526340 width=32) (actual time=104.41..23307.84 rows=402929 loops=1)
Index Cond: (tim < '00:10:00'::time without time zone)
Total runtime: 23660.95 msec
(3 rows)
logs=# explain analyze select * from fact where tim<'00:10:00';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------
Index Scan using i__fact__tim on fact (cost=0.00..2110978.39 rows=526340 width=32) (actual time=0.03..1477.35 rows=402929 loops=1)
Index Cond: (tim < '00:10:00'::time without time zone)
Total runtime: 1827.94 msec
(3 rows)
logs=#
*******************************************************************************
*******************************************************************************
So two questions:
a) Am I on to something.... or is something else the reason why
the optimizer chose the much slower sequential scan?
b) If I did write an "analyze" that tried to set "correlation" values
that took into account such local grouping of data, would anyone
be interested?
Ron
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large tables?
@ 2003-01-24 06:48 Tom Lane <tgl@sss.pgh.pa.us>
parent: Ron Mayer <ron@intervideo.com>
0 siblings, 2 replies; 8+ messages in thread
From: Tom Lane @ 2003-01-24 06:48 UTC (permalink / raw)
To: Ron Mayer <ron@intervideo.com>; +Cc: pgsql-performance
Ron Mayer <ron@intervideo.com> writes:
> On a large tables, I think the "correlation" pg_stats field as calculated
> by "vacuum analyze" or "analyze" can mislead the optimizer.
If you look in the pghackers archives, you will find some discussion
about changing the equation that cost_index() uses to estimate the
impact of correlation on indexscan cost. The existing equation is
ad-hoc and surely wrong, but so far no one's proposed a replacement
that can be justified any better. If you've got such a replacement
then we're all ears...
> In particular, if I have a large table t with columns 'a','b','c', etc,
> and I cluster the table as follows:
> create table t_ordered as select * from t order by a,b;
> vacuum analyze t_ordered;
> Column "b" will (correctly) get a very low "correlation" in
> the pg_stats table -- but I think the optimizer would do better
> assuming a high correlation because similar 'b' values are still
> grouped closely on the same disk pages.
How would that be? They'll be separated by the stride of 'a'.
It seems likely to me that a one-dimensional correlation statistic may
be inadequate, but I haven't seen any proposals for better stats.
regards, tom lane
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large
@ 2003-01-24 16:27 Stephan Szabo <sszabo@megazone23.bigpanda.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 8+ messages in thread
From: Stephan Szabo @ 2003-01-24 16:27 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Ron Mayer <ron@intervideo.com>; pgsql-performance
On Fri, 24 Jan 2003, Tom Lane wrote:
> Ron Mayer <ron@intervideo.com> writes:
> > In particular, if I have a large table t with columns 'a','b','c', etc,
> > and I cluster the table as follows:
> > create table t_ordered as select * from t order by a,b;
> > vacuum analyze t_ordered;
> > Column "b" will (correctly) get a very low "correlation" in
> > the pg_stats table -- but I think the optimizer would do better
> > assuming a high correlation because similar 'b' values are still
> > grouped closely on the same disk pages.
>
> How would that be? They'll be separated by the stride of 'a'.
I think it's a clumping effect.
For example, I made a table (ordered) with 20 values of a, 50 values of b
(each showing up in each a) and 100 values of c (not used, just means 100
rows for each (a,b) combination. It's got 541 pages it looks like. Analyze
sets the correlation to about 0.08 on the table and so a query like:
select * from test1 where b=1; prefers a sequence scan (1791 vs 2231)
while the index scan actually performs about 5 times better.
I guess the reason is that in general, the index scan *really* is reading
something on the order of 40 pages rather than the much larger estimate
(I'd guess something on the order of say 300-400? I'm not sure how to
find that except by trying to reverse engineer the estimate number),
because pretty much each value of a will probably have 1 or 2 pages with
b=1.
I'm not really sure how to measure that, however.
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large
@ 2003-01-24 19:36 Ron Mayer <ron@intervideo.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 8+ messages in thread
From: Ron Mayer @ 2003-01-24 19:36 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance
On Fri, 24 Jan 2003, Tom Lane wrote:
>
> Ron Mayer <ron@intervideo.com> writes:
> > On a large tables, I think the "correlation" pg_stats field as calculated
> > by "vacuum analyze" or "analyze" can mislead the optimizer.
>
> If you look in the pghackers archives, you will find some discussion
> about changing the equation that cost_index() uses to estimate the
> impact of correlation on indexscan cost. The existing equation is
> ad-hoc and surely wrong, but so far no one's proposed a replacement
> that can be justified any better. If you've got such a replacement
> then we're all ears...
I've got a very slow one (full table scan perl script) that helps
my database... I don't know if it's a good general purpose solution.
That's why I'm asking if the concept is good here. :-)
> > In particular, if I have a large table t with columns 'a','b','c', etc,
> > and I cluster the table as follows:
> > create table t_ordered as select * from t order by a,b;
> > vacuum analyze t_ordered;
> > Column "b" will (correctly) get a very low "correlation" in
> > the pg_stats table -- but I think the optimizer would do better
> > assuming a high correlation because similar 'b' values are still
> > grouped closely on the same disk pages.
>
> How would that be? They'll be separated by the stride of 'a'.
In the case of date/time (for the queries I showed) the issue was
that 'a's were not at all unique so I had data like this:
dat | time | value
------------|----------|--------------------------------
2002-01-01 | 00:00:00 | whatever
2002-01-01 | 00:00:00 |
2002-01-01 | 00:00:00 |
2002-01-01 | 00:00:01 |
2002-01-01 | 00:00:01 | [many pages of 12am]
2002-01-01 | 00:00:01 |
2002-01-01 | 00:00:01 |
... thousands more rows....
2002-01-01 | 00:00:59 |
2002-01-01 | 00:01:00 | [many pages of 1am]
... tens of thousands of rows.
2002-01-01 | 23:59:59 |
2002-01-01 | 23:59:59 |
2002-01-01 | 23:59:59 | [many pages of 11pm]
2002-01-02 | 00:00:00 | [many *MORE* pages of 12am]
2002-01-02 | 00:00:00 |
2002-01-02 | 00:00:00 |
... tens of thousands of rows...
2002-01-02 | 23:59:59 | [many pages of 11pm]
2002-01-03 | 00:00:00 | [many *MORE* pages of 12am]
... millions more rows ...
A similar problem actually shows up again in the dimention tables
of my database; where I bulk load many pages at a time (which can
easily be ordered to give a good correlation for a single load) ...
but then the next week's data gets appended to the end.
id | value
------|----------------------------------
1 | aalok mehta [many pages of all 'a's]
2 | aamir khan
3 | aaron beall
| [...]
6234 | axel rose
6234 | austin wolf
6123 | barbara boxer [many pages of all 'b's]
| [...]
123456 | young
123457 | zebra
| [...data loaded later..]
123458 | aaron whatever [more pages of all 'a's]
123458 | aaron something else
123458 | aaron something else
| [...]
512344 | zelany
In this case I get many clustered blocks of "a" values, but these
clustered blocks happen at many different times across the table.
> It seems likely to me that a one-dimensional correlation statistic may
> be inadequate, but I haven't seen any proposals for better stats.
The idea is it walks the whole table and looks for more local
correlations and replaces the correlation value with a "good"
value if values "close" to each other on the disk are similar.
This way a single "correlation" value still works ... so I didn't
have to change the optimizer logic, just the "analyze" logic.
Basically if data within each block is highly correlated, it doesn't
matter as much (yeah, I now the issue about sequential reads vs. random
reads).
Ron
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large
@ 2003-01-24 20:04 Ron Mayer <ron@intervideo.com>
parent: Stephan Szabo <sszabo@megazone23.bigpanda.com>
0 siblings, 1 reply; 8+ messages in thread
From: Ron Mayer @ 2003-01-24 20:04 UTC (permalink / raw)
To: Stephan Szabo <sszabo@megazone23.bigpanda.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-performance
On Fri, 24 Jan 2003, Stephan Szabo wrote:
>
> I think it's a clumping effect.
Yup, I think that's exactly the effect.
A proposal.... (yes I I'm volunteering if people point me in the right
direction)... would be to have a "plugable" set of analyze functions so that a
huge database that runs analyze infrequently could choose to have a very slow
analyze that might work better for it's data.
I see no reason different analyze functions would to be compiled into
the source code ... but could probably exists as PL/pgSQL languages.
The one thing compiling it in would help with is to let me know
the exact number of tuples on each individual page, but I guess
reltuples/relpages from pg_class is a good estimate.
> For example, I made a table (ordered) with 20 values of a, 50 values of b
> (each showing up in each a) and 100 values of c (not used, just means 100
> rows for each (a,b) combination. It's got 541 pages it looks like. Analyze
> sets the correlation to about 0.08 on the table and so a query like:
> select * from test1 where b=1; prefers a sequence scan (1791 vs 2231)
> while the index scan actually performs about 5 times better.
That sounds like the same situation I was in. If my logic is right, this
means you had about 184 tuples/page (200*50*100/541), so it looks to me
like for each "a", you get half-a-page where "b=1".
If you had 'c' have 200 values, I think you'd get even a bigger speedup
because half the page is still "wasted" with b=2 values.
If you had 'c' have 10000 values, I think you'd get even a slightly bigger
speedup because you'd have so many b=1 pages next to each other you'd
benefit from more sequential disk access.
> I guess the reason is that in general, the index scan *really* is reading
> something on the order of 40 pages rather than the much larger estimate
> (I'd guess something on the order of say 300-400? I'm not sure how to
> find that except by trying to reverse engineer the estimate number),
Or by adding a printf()... I think it'd be in cost_index in costsize.c.
> because pretty much each value of a will probably have 1 or 2 pages with
> b=1.
>
> I'm not really sure how to measure that, however.
As I said... I'm happy to volunteer and experiment if people point
me in a good direction.
Ron
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large
@ 2003-01-24 20:22 Tom Lane <tgl@sss.pgh.pa.us>
parent: Ron Mayer <ron@intervideo.com>
0 siblings, 2 replies; 8+ messages in thread
From: Tom Lane @ 2003-01-24 20:22 UTC (permalink / raw)
To: Ron Mayer <ron@intervideo.com>; +Cc: Stephan Szabo <sszabo@megazone23.bigpanda.com>; pgsql-performance
Ron Mayer <ron@intervideo.com> writes:
> A proposal.... (yes I I'm volunteering if people point me in the right
> direction)... would be to have a "plugable" set of analyze functions so that a
> huge database that runs analyze infrequently could choose to have a very slow
> analyze that might work better for it's data.
I do not think ANALYZE is the problem here; at least, it's premature to
worry about that end of things until you've defined (a) what's to be
stored in pg_statistic, and (b) what computation the planner needs to
make to derive a cost estimate given the stats.
regards, tom lane
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large
@ 2003-01-24 21:55 Noah Silverman <noah@allresearch.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 8+ messages in thread
From: Noah Silverman @ 2003-01-24 21:55 UTC (permalink / raw)
To: pgsql-performance; +Cc: pgsql-performance
Hi!
Another fun question in our ongoing analysis on whether to switch from
mysql to postgres. (Just as an update, Postgres has performed
flawlessly on all of our stress tests so far.)
We have a situation where we will be creating two fairly large and
complex databases with many tables (thousands) each. From what I
understand, postgres keeps everything in one big data directory.
Would there be an advantage to putting each of the two databases into a
separate directory and starting two instances of postgres? Is it
better to just lump everything together.
In a perfect world, we would buy another database server and raid for
the second database, but being a small company, we just don't have the
budget right now. The raid on our current server is much bigger than we
need.
Thanks,
-N
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Does "correlation" mislead the optimizer on large
@ 2003-01-24 23:09 Ron Mayer <ron@intervideo.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 8+ messages in thread
From: Ron Mayer @ 2003-01-24 23:09 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Stephan Szabo <sszabo@megazone23.bigpanda.com>; pgsql-performance
On Fri, 24 Jan 2003, Tom Lane wrote:
>
> Ron Mayer <ron@intervideo.com> writes:
> > A proposal.... (yes I I'm volunteering if people point me in the right
> > direction)...
>
> I do not think ANALYZE is the problem here; at least, it's premature to
> worry about that end of things until you've defined (a) what's to be
> stored in pg_statistic, and (b) what computation the planner needs to
> make to derive a cost estimate given the stats.
Cool. Thanks for a good starting point. If I wanted to brainstorm
further, should I do so here, or should I encourage interested people
to take it off line with me (ron@intervideo.com) and I can post
a summary of the conversation?
Ron
For those who do want to brainstorm with me, my starting point is this:
With my particular table, I think the main issue is still that I have a
lot of data that looks like:
values: aaaaaaaaaaabbbbbbbbccccccccddddddddddaaaabbbbbbbccccccccddddd...
disk page: |page 1|page 2|page 3|page 4|page 5|page 6|page 7|page 8|page 9|
The problem I'm trying to address is that the current planner guesses
that most of the pages will need to be read; however the local clustering
means that in fact only a small subset need to be accessed. My first
guess is that modifying the definition of "correlation" to account for
page-sizes would be a good approach.
I.e. Instead of the correlation across the whole table, for each row
perform an auto-correlation
(http://astronomy.swin.edu.au/~pbourke/analysis/correlate/)
and keep only the values with a "delay" of less than 1 page-size.
If you want to share thoughts offline (ron@intervideo.com), I'll gladly
post a summary of responses here to save the bandwidth of the group.
^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2003-01-24 23:09 UTC | newest]
Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-01-24 04:16 Does "correlation" mislead the optimizer on large tables? Ron Mayer <ron@intervideo.com>
2003-01-24 06:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-01-24 16:27 ` Re: Does "correlation" mislead the optimizer on large Stephan Szabo <sszabo@megazone23.bigpanda.com>
2003-01-24 20:04 ` Re: Does "correlation" mislead the optimizer on large Ron Mayer <ron@intervideo.com>
2003-01-24 20:22 ` Re: Does "correlation" mislead the optimizer on large Tom Lane <tgl@sss.pgh.pa.us>
2003-01-24 21:55 ` Re: Does "correlation" mislead the optimizer on large Noah Silverman <noah@allresearch.com>
2003-01-24 23:09 ` Re: Does "correlation" mislead the optimizer on large Ron Mayer <ron@intervideo.com>
2003-01-24 19:36 ` Re: Does "correlation" mislead the optimizer on large Ron Mayer <ron@intervideo.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox