pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedIncorrect estimates on correlated filters
7+ messages / 5 participants
[nested] [flat]
* Incorrect estimates on correlated filters
@ 2008-08-12 21:59 Chris Kratz <chris.kratz@vistashare.com>
0 siblings, 1 reply; 7+ messages in thread
From: Chris Kratz @ 2008-08-12 21:59 UTC (permalink / raw)
To: pgsql-performance
Hello All,
Ran into a re-occuring performance problem with some report queries again
today. In a nutshell, we have filters on either multiple joined tables, or
multiple columns on a single table that are highly correlated. So, the
estimates come out grossly incorrect (the planner has no way to know they
are correlated). 2000:1 for one I'm looking at right now. Generally this
doesn't matter, except in complex reporting queries like these when this is
the first join of 40 other joins. Because the estimate is wrong at the
lowest level, it snowballs up through the rest of the joins causing the
query to run very, very slowly. In many of these cases, forcing nested
loops off for the duration of the query fixes the problem. But I have a
couple that still are painfully slow and shouldn't be.
I've been reading through the archives with others having similar problems
(including myself a year ago). Am I right in assuming that at this point
there is still little we can do in postgres to speed up this kind of query?
Right now the planner has no way to know the correlation between different
columns in the same table, let alone columns in different tables. So, it
just assumes no correlation and returns incorrectly low estimates in cases
like these.
The only solution I've come up with so far is to materialize portions of the
larger query into subqueries with these correlated filters which are indexed
and analyzed before joining into the larger query. This would keep the
incorrect estimates from snowballing up through the chain of joins.
Are there any other solutions to this problem?
Thanks,
-Chris
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Incorrect estimates on correlated filters
@ 2008-08-13 14:59 Decibel! <decibel@decibel.org>
parent: Chris Kratz <chris.kratz@vistashare.com>
0 siblings, 2 replies; 7+ messages in thread
From: Decibel! @ 2008-08-13 14:59 UTC (permalink / raw)
To: Chris Kratz <chris.kratz@vistashare.com>; +Cc: pgsql-performance
On Aug 12, 2008, at 4:59 PM, Chris Kratz wrote:
> Ran into a re-occuring performance problem with some report queries
> again today. In a nutshell, we have filters on either multiple
> joined tables, or multiple columns on a single table that are
> highly correlated. So, the estimates come out grossly incorrect
> (the planner has no way to know they are correlated). 2000:1 for
> one I'm looking at right now. Generally this doesn't matter,
> except in complex reporting queries like these when this is the
> first join of 40 other joins. Because the estimate is wrong at the
> lowest level, it snowballs up through the rest of the joins causing
> the query to run very, very slowly. In many of these cases,
> forcing nested loops off for the duration of the query fixes the
> problem. But I have a couple that still are painfully slow and
> shouldn't be.
>
> I've been reading through the archives with others having similar
> problems (including myself a year ago). Am I right in assuming
> that at this point there is still little we can do in postgres to
> speed up this kind of query? Right now the planner has no way to
> know the correlation between different columns in the same table,
> let alone columns in different tables. So, it just assumes no
> correlation and returns incorrectly low estimates in cases like these.
>
> The only solution I've come up with so far is to materialize
> portions of the larger query into subqueries with these correlated
> filters which are indexed and analyzed before joining into the
> larger query. This would keep the incorrect estimates from
> snowballing up through the chain of joins.
>
> Are there any other solutions to this problem?
Well... you could try and convince certain members of the community
that we actually do need some kind of a query hint mechanism... ;)
I did make a suggestion a few months ago that involved sorting a
table on different columns and recording the correlation of other
columns. The scheme isn't perfect, but it would help detect cases
like a field populated by a sequence and another field that's insert
timestamp; those two fields would correlate highly, and you should
even be able to correlate the two histograms; that would allow you to
infer that most of the insert times for _id's between 100 and 200
will be between 2008-01-01 00:10 and 2008-01-01 00:20, for example.
--
Decibel!, aka Jim C. Nasby, Database Architect decibel@decibel.org
Give your computer some brain candy! www.distributed.net Team #1828
Attachments:
smime.p7s (application/pkcs7-signature, 2.5K) download
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Incorrect estimates on correlated filters
@ 2008-08-13 18:45 Chris Kratz <chris.kratz@vistashare.com>
parent: Decibel! <decibel@decibel.org>
1 sibling, 2 replies; 7+ messages in thread
From: Chris Kratz @ 2008-08-13 18:45 UTC (permalink / raw)
To: Decibel! <decibel@decibel.org>; +Cc: pgsql-performance
On Wed, Aug 13, 2008 at 10:59 AM, Decibel! <decibel@decibel.org> wrote:
> On Aug 12, 2008, at 4:59 PM, Chris Kratz wrote:
>
>> Ran into a re-occuring performance problem with some report queries again
>> today. In a nutshell, we have filters on either multiple joined tables, or
>> multiple columns on a single table that are highly correlated. So, the
>> estimates come out grossly incorrect (the planner has no way to know they
>> are correlated). 2000:1 for one I'm looking at right now. Generally this
>> doesn't matter, except in complex reporting queries like these when this is
>> the first join of 40 other joins. Because the estimate is wrong at the
>> lowest level, it snowballs up through the rest of the joins causing the
>> query to run very, very slowly. In many of these cases, forcing nested
>> loops off for the duration of the query fixes the problem. But I have a
>> couple that still are painfully slow and shouldn't be.
>>
>> I've been reading through the archives with others having similar problems
>> (including myself a year ago). Am I right in assuming that at this point
>> there is still little we can do in postgres to speed up this kind of query?
>> Right now the planner has no way to know the correlation between different
>> columns in the same table, let alone columns in different tables. So, it
>> just assumes no correlation and returns incorrectly low estimates in cases
>> like these.
>>
>> The only solution I've come up with so far is to materialize portions of
>> the larger query into subqueries with these correlated filters which are
>> indexed and analyzed before joining into the larger query. This would keep
>> the incorrect estimates from snowballing up through the chain of joins.
>>
>> Are there any other solutions to this problem?
>>
>
>
> Well... you could try and convince certain members of the community that we
> actually do need some kind of a query hint mechanism... ;)
>
> I did make a suggestion a few months ago that involved sorting a table on
> different columns and recording the correlation of other columns. The scheme
> isn't perfect, but it would help detect cases like a field populated by a
> sequence and another field that's insert timestamp; those two fields would
> correlate highly, and you should even be able to correlate the two
> histograms; that would allow you to infer that most of the insert times for
> _id's between 100 and 200 will be between 2008-01-01 00:10 and 2008-01-01
> 00:20, for example.
> --
> Decibel!, aka Jim C. Nasby, Database Architect decibel@decibel.org
> Give your computer some brain candy! www.distributed.net Team #1828
>
>
> Thanks for the reply,
Yes, I know hints are frowned upon around here. Though, I'd love to have
them or something equivalent on this particular query just so the customer
can run their important reports. As it is, it's unrunnable.
Unfortunately, if I don't think the sorting idea would help in the one case
I'm looking at which involves filters on two tables that are joined
together. The filters happen to be correlated such that about 95% of the
rows from each filtered table are actually returned after the join.
Unfortunately, the planner thinks we will get 1 row back.
I do have to find a way to make these queries runnable. I'll keep looking.
Thanks,
-Chris
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Incorrect estimates on correlated filters
@ 2008-08-13 20:58 Alvaro Herrera <alvherre@commandprompt.com>
parent: Chris Kratz <chris.kratz@vistashare.com>
1 sibling, 0 replies; 7+ messages in thread
From: Alvaro Herrera @ 2008-08-13 20:58 UTC (permalink / raw)
To: Chris Kratz <chris.kratz@vistashare.com>; +Cc: Decibel! <decibel@decibel.org>; pgsql-performance
Chris Kratz wrote:
> Unfortunately, if I don't think the sorting idea would help in the one case
> I'm looking at which involves filters on two tables that are joined
> together. The filters happen to be correlated such that about 95% of the
> rows from each filtered table are actually returned after the join.
> Unfortunately, the planner thinks we will get 1 row back.
Maybe you can wrap that part of the query in a SQL function and set its
estimated cost to the real values with ALTER FUNCTION ... ROWS.
--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Incorrect estimates on correlated filters
@ 2008-08-14 01:48 Craig Ringer <craig@postnewspapers.com.au>
parent: Decibel! <decibel@decibel.org>
1 sibling, 1 reply; 7+ messages in thread
From: Craig Ringer @ 2008-08-14 01:48 UTC (permalink / raw)
To: Decibel! <decibel@decibel.org>; +Cc: Chris Kratz <chris.kratz@vistashare.com>; pgsql-performance
Decibel! wrote:
> Well... you could try and convince certain members of the community that
> we actually do need some kind of a query hint mechanism... ;)
It strikes me that there are really two types of query hint possible here.
One tells the planner (eg) "prefer a merge join here".
The other gives the planner more information that it might not otherwise
have to work with, so it can improve its decisions. "The values used in
this join condition are highly correlated".
Is there anything wrong with the second approach? It shouldn't tend to
suppress planner bug reports etc. Well, not unless people use it to lie
to the planner, and I expect results from that would be iffy at best. It
just provides information to supplement Pg's existing stats system to
handle cases where it's not able to reasonably collect the required
information.
--
Craig Ringer
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Incorrect estimates on correlated filters
@ 2008-08-14 10:12 Gregory Stark <stark@enterprisedb.com>
parent: Craig Ringer <craig@postnewspapers.com.au>
0 siblings, 0 replies; 7+ messages in thread
From: Gregory Stark @ 2008-08-14 10:12 UTC (permalink / raw)
To: Craig Ringer <craig@postnewspapers.com.au>; +Cc: Decibel! <decibel@decibel.org>; Chris Kratz <chris.kratz@vistashare.com>; pgsql-performance
"Craig Ringer" <craig@postnewspapers.com.au> writes:
> It strikes me that there are really two types of query hint possible here.
>
> One tells the planner (eg) "prefer a merge join here".
>
> The other gives the planner more information that it might not otherwise
> have to work with, so it can improve its decisions. "The values used in
> this join condition are highly correlated".
This sounds familiar:
http://article.gmane.org/gmane.comp.db.postgresql.devel.general/55730/match=hints
Plus ça change...
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's On-Demand Production Tuning
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Incorrect estimates on correlated filters
@ 2008-08-16 18:21 Decibel! <decibel@decibel.org>
parent: Chris Kratz <chris.kratz@vistashare.com>
1 sibling, 0 replies; 7+ messages in thread
From: Decibel! @ 2008-08-16 18:21 UTC (permalink / raw)
To: Chris Kratz <chris.kratz@vistashare.com>; +Cc: pgsql-performance
On Aug 13, 2008, at 1:45 PM, Chris Kratz wrote:
> Yes, I know hints are frowned upon around here. Though, I'd love
> to have them or something equivalent on this particular query just
> so the customer can run their important reports. As it is, it's
> unrunnable.
Actually, now that I think about it the last time this was brought up
there was discussion about something that doesn't force a particular
execution method, but instead provides improved information to the
planner. It might be worth pursuing that, as I think there was less
opposition to it.
--
Decibel!, aka Jim C. Nasby, Database Architect decibel@decibel.org
Give your computer some brain candy! www.distributed.net Team #1828
Attachments:
smime.p7s (application/pkcs7-signature, 2.5K) download
^ permalink raw reply [nested|flat] 7+ messages in thread
end of thread, other threads:[~2008-08-16 18:21 UTC | newest]
Thread overview: 7+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2008-08-12 21:59 Incorrect estimates on correlated filters Chris Kratz <chris.kratz@vistashare.com>
2008-08-13 14:59 ` Decibel! <decibel@decibel.org>
2008-08-13 18:45 ` Chris Kratz <chris.kratz@vistashare.com>
2008-08-13 20:58 ` Alvaro Herrera <alvherre@commandprompt.com>
2008-08-16 18:21 ` Decibel! <decibel@decibel.org>
2008-08-14 01:48 ` Craig Ringer <craig@postnewspapers.com.au>
2008-08-14 10:12 ` Gregory Stark <stark@enterprisedb.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