pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: choose_bitmap_and again (was Re: [PERFORM] StrangelyVariable Query Performance)
10+ messages / 5 participants
[nested] [flat]
* Re: choose_bitmap_and again (was Re: [PERFORM] StrangelyVariable Query Performance)
@ 2007-04-14 08:24 Simon Riggs <simon@2ndquadrant.com>
2 siblings, 0 replies; 10+ messages in thread
From: Simon Riggs @ 2007-04-14 08:24 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-hackers@postgreSQL.org; pgsql-performance; Steve <cheetah@tanabi.org>
On Fri, 2007-04-13 at 18:48 -0400, Tom Lane wrote:
> Has anyone got any thoughts about the best way to do this?
I don't think we know enough to pick one variant that works in all
cases. This requires more detailed analysis of various cases.
Lets put in a parameter to allow the options to be varied. The purpose
would be to look for some more information that allows us to see what
the pre-conditions would be for each heuristic.
Initially, we say this is a beta-only feature and may be withdrawn in
the production version.
Why did it not pick my index? is a tiring game, but one that must be
played. I hope that the ORDER LIMIT optimization should reduce the
number of indexes chosen to maintain sort order in the output.
--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-14 09:04 Dann Corbit <DCorbit@connx.com>
2 siblings, 0 replies; 10+ messages in thread
From: Dann Corbit @ 2007-04-14 09:04 UTC (permalink / raw)
To: Alvaro Herrera <alvherre@commandprompt.com>; Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-hackers@postgreSQL.org; pgsql-performance; Steve <cheetah@tanabi.org>
> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> owner@postgresql.org] On Behalf Of Alvaro Herrera
> Sent: Friday, April 13, 2007 4:24 PM
> To: Tom Lane
> Cc: pgsql-hackers@postgreSQL.org; PostgreSQL Performance; Steve
> Subject: Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM]
> Strangely Variable Query Performance)
>
> Tom Lane wrote:
>
> > One idea I thought about was to sort by index scan cost, using
> > selectivity only as a tiebreaker for cost, rather than the other way
> > around as is currently done. This seems fairly plausible because
> > indexscans that are cheaper than other indexscans likely return
fewer
> > rows too, and so selectivity is already accounted for to some extent
---
> > at least you can't have an enormously worse selectivity at lower
cost,
> > whereas Steve's example proves it doesn't work the other way. But
I'm
> > worried about breaking the reasoning about redundant indexes that's
> > mentioned in the comments.
> >
> > Another alternative that would respond to the immediate problem is
to
> > maintain the current sort order, but as we come to each index,
consider
> > using that one alone, and throw away whatever AND we might have
built up
> > if that one alone beats the AND-so-far. This seems more
conservative,
> > as it's unlikely to break any cases that work well now, but on the
other
> > hand it feels like plastering another wart atop a structure that's
> > already rather rickety.
> >
> > Has anyone got any thoughts about the best way to do this?
>
> How about doing both: sort the index by index scan cost; then pick the
> first index on the list and start adding indexes when they lower the
> cost. When adding each index, consider it by itself against the
> already stacked indexes. If the cost is lower, put this index at the
> top of the list, and restart the algorithm (after the sorting step of
> course).
>
> I think the concern about condition redundancy should be attacked
> separately. How about just comparing whether they have common
prefixes
> of conditions? I admit I don't understand what would happen with
> indexes defined like (lower(A), B, C) versus (A, B) for example.
Instead of sorting, I suggest the quickselect() algorithm, which is
O(n).
Probably, if the list is small, it won't matter much, but it might offer
some tangible benefit.
Here is an example of the algorithm:
#include <stdlib.h>
typedef double Etype; /* Season to taste. */
extern Etype RandomSelect(Etype * A, size_t p, size_t r, size_t i);
extern size_t RandRange(size_t a, size_t b);
extern size_t RandomPartition(Etype * A, size_t p, size_t r);
extern size_t Partition(Etype * A, size_t p, size_t r);
/*
**
** In the following code, every reference to CLR means:
**
** "Introduction to Algorithms"
** By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
** ISBN 0-07-013143-0
*/
/*
** CLR, page 187
*/
Etype RandomSelect(Etype A[], size_t p, size_t r, size_t i)
{
size_t q,
k;
if (p == r)
return A[p];
q = RandomPartition(A, p, r);
k = q - p + 1;
if (i <= k)
return RandomSelect(A, p, q, i);
else
return RandomSelect(A, q + 1, r, i - k);
}
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1) * (b
- a));
return c + a;
}
/*
** CLR, page 162
*/
size_t RandomPartition(Etype A[], size_t p, size_t r)
{
size_t i = RandRange(p, r);
Etype Temp;
Temp = A[p];
A[p] = A[i];
A[i] = Temp;
return Partition(A, p, r);
}
/*
** CLR, page 154
*/
size_t Partition(Etype A[], size_t p, size_t r)
{
Etype x,
temp;
size_t i,
j;
x = A[p];
i = p - 1;
j = r + 1;
for (;;) {
do {
j--;
} while (!(A[j] <= x));
do {
i++;
} while (!(A[i] >= x));
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
} else
return j;
}
}
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-14 22:02 Tom Lane <tgl@sss.pgh.pa.us>
2 siblings, 1 reply; 10+ messages in thread
From: Tom Lane @ 2007-04-14 22:02 UTC (permalink / raw)
To: pgsql-patches@postgreSQL.org; +Cc: Alvaro Herrera <alvherre@commandprompt.com>; Steve <cheetah@tanabi.org>
I wrote:
> Thinking more about this leads me to the following proposal:
> 1. Explicitly group the indexes according to the subset of
> WHERE-conditions (and partial index conditions, if any) they use.
> Within each such group, discard all but the cheapest-scan-cost one.
> 2. Sort the remaining indexes according to scan cost.
> 3. For each index in order, consider it as a standalone scan, and also
> consider adding it on to the AND-group led by each preceding index,
> using the same logic as now: reject using any WHERE-condition twice
> in a group, and then add on only if the total cost of the AND-group
> scan is reduced.
Here is a patch along these lines, in fact two patches (HEAD and 8.2
versions). The 8.2 version picks up some additional partial-index
intelligence that I added to HEAD on Mar 21 but did not at that time
risk back-patching --- since this is a fairly large rewrite of the
routine, keeping the branches in sync seems best.
Steve, can you try this out on your queries and see if it makes better
or worse decisions? It seems to fix your initial complaint but I do
not have a large stock of test cases to try.
regards, tom lane
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-14 22:55 Steve <cheetah@tanabi.org>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 10+ messages in thread
From: Steve @ 2007-04-14 22:55 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-patches@postgreSQL.org, Alvaro Herrera <alvherre@commandprompt.com>
> Steve, can you try this out on your queries and see if it makes better
> or worse decisions? It seems to fix your initial complaint but I do
> not have a large stock of test cases to try.
>
Wow, this is a remarkable difference. Queries that were taking
minutes to complete are coming up in seconds. Good work, I think this'll
solve my customer's needs for their demo on the 19th :)
Thank you so much!
Steve
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-15 05:11 Tom Lane <tgl@sss.pgh.pa.us>
parent: Steve <cheetah@tanabi.org>
0 siblings, 2 replies; 10+ messages in thread
From: Tom Lane @ 2007-04-15 05:11 UTC (permalink / raw)
To: Steve <cheetah@tanabi.org>; +Cc: pgsql-patches@postgreSQL.org, Alvaro Herrera <alvherre@commandprompt.com>
Steve <cheetah@tanabi.org> writes:
>> Steve, can you try this out on your queries and see if it makes better
>> or worse decisions? It seems to fix your initial complaint but I do
>> not have a large stock of test cases to try.
> Wow, this is a remarkable difference. Queries that were taking
> minutes to complete are coming up in seconds. Good work, I think this'll
> solve my customer's needs for their demo on the 19th :)
Can you find any cases where it makes a worse choice than before?
Another thing to pay attention to is whether the planning time gets
noticeably worse. If we can't find any cases where it loses badly
on those measures, I'll feel comfortable in applying it...
regards, tom lane
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-15 08:13 Steve <cheetah@tanabi.org>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 10+ messages in thread
From: Steve @ 2007-04-15 08:13 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-patches@postgreSQL.org, Alvaro Herrera <alvherre@commandprompt.com>
>
> Can you find any cases where it makes a worse choice than before?
> Another thing to pay attention to is whether the planning time gets
> noticeably worse. If we can't find any cases where it loses badly
> on those measures, I'll feel comfortable in applying it...
>
I'll see what I can find -- I'll let you know on Monday if I can
find any queries that perform worse. My tests so far have shown
equivalent or better performance so far but I've only done sort of a
survey so far ... I've got plenty of special cases to test that should
put this through the paces.
Steve
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-16 22:13 Steve <cheetah@tanabi.org>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 10+ messages in thread
From: Steve @ 2007-04-16 22:13 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-patches@postgreSQL.org, Alvaro Herrera <alvherre@commandprompt.com>
>
> Can you find any cases where it makes a worse choice than before?
> Another thing to pay attention to is whether the planning time gets
> noticeably worse. If we can't find any cases where it loses badly
> on those measures, I'll feel comfortable in applying it...
>
Okay, here's the vedict; all the "extremely slow" queries (i.e.
queries that took more than 30 seconds and upwards of several minutes to
complete) are now running in the realm of reason. In fact, most queries
that took between 1 and 4 minutes are now down to taking about 9 seconds
which is obviously a tremendous improvement.
A few of the queries that were taking 9 seconds or less are
"slightly slower" -- meaning a second or two slower. However most of them
are running at the same speed they were before, or better.
So I'd say as far as I can tell with my application and my
dataset, this change is solid and an obvious improvement.
Talk to you later,
Steve
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-16 23:01 Alvaro Herrera <alvherre@commandprompt.com>
parent: Steve <cheetah@tanabi.org>
0 siblings, 1 reply; 10+ messages in thread
From: Alvaro Herrera @ 2007-04-16 23:01 UTC (permalink / raw)
To: Steve <cheetah@tanabi.org>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-patches@postgreSQL.org
Steve wrote:
> >Can you find any cases where it makes a worse choice than before?
> >Another thing to pay attention to is whether the planning time gets
> >noticeably worse. If we can't find any cases where it loses badly
> >on those measures, I'll feel comfortable in applying it...
>
> Okay, here's the vedict; all the "extremely slow" queries (i.e.
> queries that took more than 30 seconds and upwards of several minutes to
> complete) are now running in the realm of reason. In fact, most queries
> that took between 1 and 4 minutes are now down to taking about 9 seconds
> which is obviously a tremendous improvement.
>
> A few of the queries that were taking 9 seconds or less are
> "slightly slower" -- meaning a second or two slower. However most of them
> are running at the same speed they were before, or better.
>
> So I'd say as far as I can tell with my application and my
> dataset, this change is solid and an obvious improvement.
Maybe it would be interesting to see in detail those cases that got a
bit slower, to further tweak the heuristic if necessary. Is the extra
time, time spent in planning or in execution?
--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-17 19:04 Tom Lane <tgl@sss.pgh.pa.us>
parent: Alvaro Herrera <alvherre@commandprompt.com>
0 siblings, 1 reply; 10+ messages in thread
From: Tom Lane @ 2007-04-17 19:04 UTC (permalink / raw)
To: Alvaro Herrera <alvherre@commandprompt.com>; +Cc: Steve <cheetah@tanabi.org>; pgsql-patches@postgresql.org
Alvaro Herrera <alvherre@commandprompt.com> writes:
> Steve wrote:
>> So I'd say as far as I can tell with my application and my
>> dataset, this change is solid and an obvious improvement.
> Maybe it would be interesting to see in detail those cases that got a
> bit slower, to further tweak the heuristic if necessary. Is the extra
> time, time spent in planning or in execution?
Since there doesn't seem to be vast interest out there in testing this
further, I'm going to go ahead and apply the patch to get it out of my
working directory. We can always tweak it more later if new info
surfaces.
regards, tom lane
^ permalink raw reply [nested|flat] 10+ messages in thread
* Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance)
@ 2007-04-17 19:19 Steve <cheetah@tanabi.org>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 10+ messages in thread
From: Steve @ 2007-04-17 19:19 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alvaro Herrera <alvherre@commandprompt.com>; pgsql-patches@postgresql.org
>> Maybe it would be interesting to see in detail those cases that got a
>> bit slower, to further tweak the heuristic if necessary. Is the extra
>> time, time spent in planning or in execution?
>
> Since there doesn't seem to be vast interest out there in testing this
> further, I'm going to go ahead and apply the patch to get it out of my
> working directory. We can always tweak it more later if new info
> surfaces.
>
Doing my routine patching seems to have exploded my mail server,
sorry for not replying sooner!
I don't actually have planning vs. execution time statistics from
the older version for the queries in question -- there were not 'problem
queries' and therefore were never really analyzed. My customer's already
dragging me off to another issue, so I've got to shift gears.
Appreciate all your work -- thanks again!!! :)
Steve
^ permalink raw reply [nested|flat] 10+ messages in thread
end of thread, other threads:[~2007-04-17 19:19 UTC | newest]
Thread overview: 10+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2007-04-14 08:24 ` Simon Riggs <simon@2ndquadrant.com>
2007-04-14 09:04 ` Re: choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Dann Corbit <DCorbit@connx.com>
2007-04-14 22:02 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Tom Lane <tgl@sss.pgh.pa.us>
2007-04-14 22:55 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Steve <cheetah@tanabi.org>
2007-04-15 05:11 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Tom Lane <tgl@sss.pgh.pa.us>
2007-04-15 08:13 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Steve <cheetah@tanabi.org>
2007-04-16 22:13 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Steve <cheetah@tanabi.org>
2007-04-16 23:01 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Alvaro Herrera <alvherre@commandprompt.com>
2007-04-17 19:04 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Tom Lane <tgl@sss.pgh.pa.us>
2007-04-17 19:19 ` Re: [HACKERS] choose_bitmap_and again (was Re: [PERFORM] Strangely Variable Query Performance) Steve <cheetah@tanabi.org>
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