Re: Re: [COMMITTERS] pgsql: Rewrite GEQO's gimme_tree function so that it always finds a

Log Message:
-----------
Rewrite GEQO's gimme_tree function so that it always finds a legal join
sequence, even when the input "tour" doesn't lead directly to such a sequence.
The stack logic that was added in 2004 only supported cases where relations
that had to be joined to each other (due to join order restrictions) were
adjacent in the tour. However, relying on a random search to figure that out
is tremendously inefficient in large join problems, and could even fail
completely (leading to "failed to make a valid plan" errors) if
random_init_pool ran out of patience. It seems better to make the
tour-to-plan transformation a little bit fuzzier so that every tour can form
a legal plan, even though this means that apparently different tours will
sometimes yield the same plan.

In the same vein, get rid of the logic that knew that tours (a,b,c,d,...)
are the same as tours (b,a,c,d,...), and therefore insisted the latter
are invalid. The chance of generating two tours that differ only in
this way isn't that high, and throwing out 50% of possible tours to
avoid such duplication seems more likely to waste valuable genetic-
refinement generations than to do anything useful.

This leaves us with no cases in which geqo_eval will deem a tour invalid,
so get rid of assorted kluges that tried to deal with such cases, in
particular the undocumented assumption that DBL_MAX is an impossible
plan cost.

This is all per testing of Robert Haas' lets-remove-the-collapse-limits
patch. That idea has crashed and burned, at least for now, but we still
got something useful out of it.

It's possible we should back-patch this change, since the "failed to make a
valid plan" error can happen in existing releases; but I'd rather not until
it has gotten more testing.

Modified Files:
--------------
pgsql/src/backend/optimizer/geqo:
geqo_eval.c (r1.89 -> r1.90)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/geqo/geqo_eval.c?r1=1.89&r2=1.90)
geqo_main.c (r1.57 -> r1.58)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/geqo/geqo_main.c?r1=1.57&r2=1.58)
geqo_pool.c (r1.34 -> r1.35)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/geqo/geqo_pool.c?r1=1.34&r2=1.35)
geqo_recombination.c (r1.16 -> r1.17)
(http://anoncvs.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/geqo/geqo_recombination.c?r1=1.16&r2=1.17)

On Sun, Jul 19, 2009 at 4:00 PM, Tom Lane <tgl(at)postgresql(dot)org> wrote:
> Log Message:
> -----------
> Rewrite GEQO's gimme_tree function so that it always finds a legal join
> sequence, even when the input "tour" doesn't lead directly to such a sequence.
> The stack logic that was added in 2004 only supported cases where relations
> that had to be joined to each other (due to join order restrictions) were
> adjacent in the tour.  However, relying on a random search to figure that out
> is tremendously inefficient in large join problems, and could even fail
> completely (leading to "failed to make a valid plan" errors) if
> random_init_pool ran out of patience.  It seems better to make the
> tour-to-plan transformation a little bit fuzzier so that every tour can form
> a legal plan, even though this means that apparently different tours will
> sometimes yield the same plan.
>
> In the same vein, get rid of the logic that knew that tours (a,b,c,d,...)
> are the same as tours (b,a,c,d,...), and therefore insisted the latter
> are invalid.  The chance of generating two tours that differ only in
> this way isn't that high, and throwing out 50% of possible tours to
> avoid such duplication seems more likely to waste valuable genetic-
> refinement generations than to do anything useful.
>
> This leaves us with no cases in which geqo_eval will deem a tour invalid,
> so get rid of assorted kluges that tried to deal with such cases, in
> particular the undocumented assumption that DBL_MAX is an impossible
> plan cost.
>
> This is all per testing of Robert Haas' lets-remove-the-collapse-limits
> patch.  That idea has crashed and burned, at least for now, but we still
> got something useful out of it.
>
> It's possible we should back-patch this change, since the "failed to make a
> valid plan" error can happen in existing releases; but I'd rather not until
> it has gotten more testing.

I think I just ran smack dab into this bug on 8.3.8 (RPM:
postgresql-8.3.8-1.fc10.i386). I had a query that wasn't coming out
very well with the default settings so I raised the collapse limits
and let GEQO have a crack at it. This was not a rousing success.
It didn't actually fail, but it did this sort of thing for a real long
time.

#0 0x08192c6b in bms_overlap ()
#1 0x081b6046 in have_join_order_restriction ()
#2 0x081a9438 in gimme_tree ()
#3 0x081a9515 in geqo_eval ()
#4 0x081a9d6c in random_init_pool ()
#5 0x081a9728 in geqo ()
#6 0x081abf8d in ?? ()
#7 0x081be4c3 in query_planner ()
#8 0x081beedb in ?? ()
#9 0x081c00ce in subquery_planner ()
#10 0x081c057c in standard_planner ()
#11 0x08207caa in pg_plan_query ()
#12 0x08207df4 in pg_plan_queries ()
#13 0x082083d4 in ?? ()
#14 0x08209b3f in PostgresMain ()
#15 0x081dc1e5 in ?? ()
#16 0x081dd20a in PostmasterMain ()
#17 0x08190f96 in main ()

Nothing makes you appreciate a query that takes 3564.709 ms to run
like one that takes 272302.799 ms...

...Robert

On Monday 09 November 2009 16:18:10 Robert Haas wrote:
> On Sun, Jul 19, 2009 at 4:00 PM, Tom Lane <tgl(at)postgresql(dot)org> wrote:
> > Log Message:
> > -----------
> > Rewrite GEQO's gimme_tree function so that it always finds a legal join
> > sequence, even when the input "tour" doesn't lead directly to such a
> > sequence. The stack logic that was added in 2004 only supported cases
> > where relations that had to be joined to each other (due to join order
> > restrictions) were adjacent in the tour. However, relying on a random
> > search to figure that out is tremendously inefficient in large join
> > problems, and could even fail completely (leading to "failed to make a
> > valid plan" errors) if
> > random_init_pool ran out of patience. It seems better to make the
> > tour-to-plan transformation a little bit fuzzier so that every tour can
> > form a legal plan, even though this means that apparently different tours
> > will sometimes yield the same plan.
> >
> > In the same vein, get rid of the logic that knew that tours (a,b,c,d,...)
> > are the same as tours (b,a,c,d,...), and therefore insisted the latter
> > are invalid. The chance of generating two tours that differ only in
> > this way isn't that high, and throwing out 50% of possible tours to
> > avoid such duplication seems more likely to waste valuable genetic-
> > refinement generations than to do anything useful.
> >
> > This leaves us with no cases in which geqo_eval will deem a tour invalid,
> > so get rid of assorted kluges that tried to deal with such cases, in
> > particular the undocumented assumption that DBL_MAX is an impossible
> > plan cost.
> >
> > This is all per testing of Robert Haas' lets-remove-the-collapse-limits
> > patch. That idea has crashed and burned, at least for now, but we still
> > got something useful out of it.
> >
> > It's possible we should back-patch this change, since the "failed to make
> > a valid plan" error can happen in existing releases; but I'd rather not
> > until it has gotten more testing.
> I think I just ran smack dab into this bug on 8.3.8 (RPM:
> postgresql-8.3.8-1.fc10.i386). I had a query that wasn't coming out
> very well with the default settings so I raised the collapse limits
> and let GEQO have a crack at it. This was not a rousing success.
> It didn't actually fail, but it did this sort of thing for a real long
> time.
Yea. Seeing those backtraces all the time was what lead me to use 64bit
bitmapsets...

The problem with that change is that it might change existing queries that
work well today to get very slow - I have one such case. Its just a
happenstance, but...

Andres

On Mon, Nov 9, 2009 at 10:21 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> On Monday 09 November 2009 16:18:10 Robert Haas wrote:
>> On Sun, Jul 19, 2009 at 4:00 PM, Tom Lane <tgl(at)postgresql(dot)org> wrote:
>> > Log Message:
>> > -----------
>> > Rewrite GEQO's gimme_tree function so that it always finds a legal join
>> > sequence, even when the input "tour" doesn't lead directly to such a
>> > sequence. The stack logic that was added in 2004 only supported cases
>> > where relations that had to be joined to each other (due to join order
>> > restrictions) were adjacent in the tour.  However, relying on a random
>> > search to figure that out is tremendously inefficient in large join
>> > problems, and could even fail completely (leading to "failed to make a
>> > valid plan" errors) if
>> > random_init_pool ran out of patience.  It seems better to make the
>> > tour-to-plan transformation a little bit fuzzier so that every tour can
>> > form a legal plan, even though this means that apparently different tours
>> > will sometimes yield the same plan.
>> >
>> > In the same vein, get rid of the logic that knew that tours (a,b,c,d,...)
>> > are the same as tours (b,a,c,d,...), and therefore insisted the latter
>> > are invalid.  The chance of generating two tours that differ only in
>> > this way isn't that high, and throwing out 50% of possible tours to
>> > avoid such duplication seems more likely to waste valuable genetic-
>> > refinement generations than to do anything useful.
>> >
>> > This leaves us with no cases in which geqo_eval will deem a tour invalid,
>> > so get rid of assorted kluges that tried to deal with such cases, in
>> > particular the undocumented assumption that DBL_MAX is an impossible
>> > plan cost.
>> >
>> > This is all per testing of Robert Haas' lets-remove-the-collapse-limits
>> > patch.  That idea has crashed and burned, at least for now, but we still
>> > got something useful out of it.
>> >
>> > It's possible we should back-patch this change, since the "failed to make
>> > a valid plan" error can happen in existing releases; but I'd rather not
>> > until it has gotten more testing.
>> I think I just ran smack dab into this bug on 8.3.8 (RPM:
>> postgresql-8.3.8-1.fc10.i386).  I had a query that wasn't coming out
>> very well with the default settings so I raised the collapse limits
>> and let GEQO have a crack at it.  This was not a rousing success.
>> It didn't actually fail, but it did this sort of thing for a real long
>> time.
> Yea. Seeing those backtraces all the time was what lead me to use 64bit
> bitmapsets...
>
> The problem with that change is that it might change existing queries that
> work well today to get very slow - I have one such case. Its just a
> happenstance, but...

Wait, which change can make existing queries slow? My original
change, this fix by Tom, or 64-bit bitmapsets?

...Robert

On Monday 09 November 2009 16:23:52 Robert Haas wrote:
> On Mon, Nov 9, 2009 at 10:21 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> > On Monday 09 November 2009 16:18:10 Robert Haas wrote:
> >> On Sun, Jul 19, 2009 at 4:00 PM, Tom Lane <tgl(at)postgresql(dot)org> wrote:
> >> > Log Message:
> >> > -----------
> >> > Rewrite GEQO's gimme_tree function so that it always finds a legal
> >> > join sequence, even when the input "tour" doesn't lead directly to
> >> > such a sequence. The stack logic that was added in 2004 only supported
> >> > cases where relations that had to be joined to each other (due to join
> >> > order restrictions) were adjacent in the tour. However, relying on a
> >> > random search to figure that out is tremendously inefficient in large
> >> > join problems, and could even fail completely (leading to "failed to
> >> > make a valid plan" errors) if
> >> > random_init_pool ran out of patience. It seems better to make the
> >> > tour-to-plan transformation a little bit fuzzier so that every tour
> >> > can form a legal plan, even though this means that apparently
> >> > different tours will sometimes yield the same plan.
> >> >
> >> > In the same vein, get rid of the logic that knew that tours
> >> > (a,b,c,d,...) are the same as tours (b,a,c,d,...), and therefore
> >> > insisted the latter are invalid. The chance of generating two tours
> >> > that differ only in this way isn't that high, and throwing out 50% of
> >> > possible tours to avoid such duplication seems more likely to waste
> >> > valuable genetic- refinement generations than to do anything useful.
> >> >
> >> > This leaves us with no cases in which geqo_eval will deem a tour
> >> > invalid, so get rid of assorted kluges that tried to deal with such
> >> > cases, in particular the undocumented assumption that DBL_MAX is an
> >> > impossible plan cost.
> >> >
> >> > This is all per testing of Robert Haas'
> >> > lets-remove-the-collapse-limits patch. That idea has crashed and
> >> > burned, at least for now, but we still got something useful out of it.
> >> >
> >> > It's possible we should back-patch this change, since the "failed to
> >> > make a valid plan" error can happen in existing releases; but I'd
> >> > rather not until it has gotten more testing.
> >>
> >> I think I just ran smack dab into this bug on 8.3.8 (RPM:
> >> postgresql-8.3.8-1.fc10.i386). I had a query that wasn't coming out
> >> very well with the default settings so I raised the collapse limits
> >> and let GEQO have a crack at it. This was not a rousing success.
> >> It didn't actually fail, but it did this sort of thing for a real long
> >> time.
> >
> > Yea. Seeing those backtraces all the time was what lead me to use 64bit
> > bitmapsets...
> >
> > The problem with that change is that it might change existing queries
> > that work well today to get very slow - I have one such case. Its just a
> > happenstance, but...
> Wait, which change can make existing queries slow? My original
> change, this fix by Tom, or 64-bit bitmapsets?
The fix by Tom - it completely changes which plans will get produced (Oh, well.
Your change did as well, but nobody thought of backpatching those)

Although even the old plans were not really reproducable, so I guess my
argument isnt that strong.

Andres

On Mon, Nov 9, 2009 at 10:27 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> On Monday 09 November 2009 16:23:52 Robert Haas wrote:
>> On Mon, Nov 9, 2009 at 10:21 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
>> > On Monday 09 November 2009 16:18:10 Robert Haas wrote:
>> >> On Sun, Jul 19, 2009 at 4:00 PM, Tom Lane <tgl(at)postgresql(dot)org> wrote:
>> >> > Log Message:
>> >> > -----------
>> >> > Rewrite GEQO's gimme_tree function so that it always finds a legal
>> >> > join sequence, even when the input "tour" doesn't lead directly to
>> >> > such a sequence. The stack logic that was added in 2004 only supported
>> >> > cases where relations that had to be joined to each other (due to join
>> >> > order restrictions) were adjacent in the tour.  However, relying on a
>> >> > random search to figure that out is tremendously inefficient in large
>> >> > join problems, and could even fail completely (leading to "failed to
>> >> > make a valid plan" errors) if
>> >> > random_init_pool ran out of patience.  It seems better to make the
>> >> > tour-to-plan transformation a little bit fuzzier so that every tour
>> >> > can form a legal plan, even though this means that apparently
>> >> > different tours will sometimes yield the same plan.
>> >> >
>> >> > In the same vein, get rid of the logic that knew that tours
>> >> > (a,b,c,d,...) are the same as tours (b,a,c,d,...), and therefore
>> >> > insisted the latter are invalid.  The chance of generating two tours
>> >> > that differ only in this way isn't that high, and throwing out 50% of
>> >> > possible tours to avoid such duplication seems more likely to waste
>> >> > valuable genetic- refinement generations than to do anything useful.
>> >> >
>> >> > This leaves us with no cases in which geqo_eval will deem a tour
>> >> > invalid, so get rid of assorted kluges that tried to deal with such
>> >> > cases, in particular the undocumented assumption that DBL_MAX is an
>> >> > impossible plan cost.
>> >> >
>> >> > This is all per testing of Robert Haas'
>> >> > lets-remove-the-collapse-limits patch.  That idea has crashed and
>> >> > burned, at least for now, but we still got something useful out of it.
>> >> >
>> >> > It's possible we should back-patch this change, since the "failed to
>> >> > make a valid plan" error can happen in existing releases; but I'd
>> >> > rather not until it has gotten more testing.
>> >>
>> >> I think I just ran smack dab into this bug on 8.3.8 (RPM:
>> >> postgresql-8.3.8-1.fc10.i386).  I had a query that wasn't coming out
>> >> very well with the default settings so I raised the collapse limits
>> >> and let GEQO have a crack at it.  This was not a rousing success.
>> >> It didn't actually fail, but it did this sort of thing for a real long
>> >> time.
>> >
>> > Yea. Seeing those backtraces all the time was what lead me to use 64bit
>> > bitmapsets...
>> >
>> > The problem with that change is that it might change existing queries
>> > that work well today to get very slow - I have one such case. Its just a
>> > happenstance, but...
>> Wait, which change can make existing queries slow?  My original
>> change, this fix by Tom, or 64-bit bitmapsets?
> The fix by Tom - it completely changes which plans will get produced (Oh, well.
> Your change did as well, but nobody thought of backpatching those)
>
> Although even the old plans were not really reproducable, so I guess my
> argument isnt that strong.

Well, we might want to look at your example then - this wasn't
backpatched, but it's in HEAD.

...Robert

On Mon, Nov 9, 2009 at 10:18 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> I think I just ran smack dab into this bug on 8.3.8 (RPM:
> postgresql-8.3.8-1.fc10.i386).  I had a query that wasn't coming out
> very well with the default settings so I raised the collapse limits
> and let GEQO have a crack at it.  This was not a rousing success.
> It didn't actually fail, but it did this sort of thing for a real long
> time.
>
> #0  0x08192c6b in bms_overlap ()
> #1  0x081b6046 in have_join_order_restriction ()
> #2  0x081a9438 in gimme_tree ()
> #3  0x081a9515 in geqo_eval ()
> #4  0x081a9d6c in random_init_pool ()
> #5  0x081a9728 in geqo ()
[snip]

That backtrace actually bounced around a little bit - it was always in
gimme_tree(), but the rest varied. If I raise the collapse limits AND
disable GEQO, then I get backtraces that CONSISTENTLY look like this.

#0 0x081923bc in list_concat_unique_ptr ()
#1 0x081b6922 in join_search_one_level ()
#2 0x081ab22b in standard_join_search ()
#3 0x081abf72 in ?? ()
#4 0x081be4c3 in query_planner ()
#5 0x081beedb in ?? ()
#6 0x081c00ce in subquery_planner ()
#7 0x081c057c in standard_planner ()
#8 0x08207caa in pg_plan_query ()
#9 0x08207df4 in pg_plan_queries ()
#10 0x082083d4 in ?? ()
#11 0x08209b3f in PostgresMain ()
#12 0x081dc1e5 in ?? ()
#13 0x081dd20a in PostmasterMain ()
#14 0x08190f96 in main ()

I've stopped the query more than 10 times now and EVERY SINGLE ONE
finds it in list_concat_unique_ptr(). :-(

It's also using about 12x as much RAM as the GEQO version.

...Robert

On Monday 09 November 2009 16:28:46 Robert Haas wrote:
> On Mon, Nov 9, 2009 at 10:27 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> > On Monday 09 November 2009 16:23:52 Robert Haas wrote:
> >> On Mon, Nov 9, 2009 at 10:21 AM, Andres Freund <andres(at)anarazel(dot)de>
wrote:
> >> > On Monday 09 November 2009 16:18:10 Robert Haas wrote:
> >> >> On Sun, Jul 19, 2009 at 4:00 PM, Tom Lane <tgl(at)postgresql(dot)org> wrote:
> >> >> > Log Message:
> >> >> > -----------
> >> >> > Rewrite GEQO's gimme_tree function so that it always finds a legal
> >> >> > join sequence, even when the input "tour" doesn't lead directly to
> >> >> > such a sequence. The stack logic that was added in 2004 only
> >> >> > supported cases where relations that had to be joined to each other
> >> >> > (due to join order restrictions) were adjacent in the tour.
> >> >> > However, relying on a random search to figure that out is
> >> >> > tremendously inefficient in large join problems, and could even
> >> >> > fail completely (leading to "failed to make a valid plan" errors)
> >> >> > if
> >> >> > random_init_pool ran out of patience. It seems better to make the
> >> >> > tour-to-plan transformation a little bit fuzzier so that every tour
> >> >> > can form a legal plan, even though this means that apparently
> >> >> > different tours will sometimes yield the same plan.
> >> >> >
> >> >> > In the same vein, get rid of the logic that knew that tours
> >> >> > (a,b,c,d,...) are the same as tours (b,a,c,d,...), and therefore
> >> >> > insisted the latter are invalid. The chance of generating two
> >> >> > tours that differ only in this way isn't that high, and throwing
> >> >> > out 50% of possible tours to avoid such duplication seems more
> >> >> > likely to waste valuable genetic- refinement generations than to do
> >> >> > anything useful.
> >> >> >
> >> >> > This leaves us with no cases in which geqo_eval will deem a tour
> >> >> > invalid, so get rid of assorted kluges that tried to deal with such
> >> >> > cases, in particular the undocumented assumption that DBL_MAX is an
> >> >> > impossible plan cost.
> >> >> >
> >> >> > This is all per testing of Robert Haas'
> >> >> > lets-remove-the-collapse-limits patch. That idea has crashed and
> >> >> > burned, at least for now, but we still got something useful out of
> >> >> > it.
> >> >> >
> >> >> > It's possible we should back-patch this change, since the "failed
> >> >> > to make a valid plan" error can happen in existing releases; but
> >> >> > I'd rather not until it has gotten more testing.
> >> >>
> >> >> I think I just ran smack dab into this bug on 8.3.8 (RPM:
> >> >> postgresql-8.3.8-1.fc10.i386). I had a query that wasn't coming out
> >> >> very well with the default settings so I raised the collapse limits
> >> >> and let GEQO have a crack at it. This was not a rousing success.
> >> >> It didn't actually fail, but it did this sort of thing for a real
> >> >> long time.
> >> >
> >> > Yea. Seeing those backtraces all the time was what lead me to use
> >> > 64bit bitmapsets...
> >> >
> >> > The problem with that change is that it might change existing queries
> >> > that work well today to get very slow - I have one such case. Its just
> >> > a happenstance, but...
> >>
> >> Wait, which change can make existing queries slow? My original
> >> change, this fix by Tom, or 64-bit bitmapsets?
> >
> > The fix by Tom - it completely changes which plans will get produced (Oh,
> > well. Your change did as well, but nobody thought of backpatching those)
> > Although even the old plans were not really reproducable, so I guess my
> > argument isnt that strong.
> Well, we might want to look at your example then - this wasn't
> backpatched, but it's in HEAD.
Hm. Its a heuristic search - so its not surprising it does find a good plan
with some sort of heuristic (<=8.4 behaviour) and not in another.
I guess my point is just that different plans will be found which are currently
not found (because the old geqo gives up quite early)

Fixing this will probably require a way much more intelligent/new heuristic
planner - which is a relatively big untertaking I see nobody really doing
right now.

Andres

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> I've stopped the query more than 10 times now and EVERY SINGLE ONE
> finds it in list_concat_unique_ptr(). :-(

Too bad you don't have debug symbols ... it'd be interesting to see
how long that list is.

> It's also using about 12x as much RAM as the GEQO version.

No surprise. GEQO is designed to constrain its memory use, the
exhaustive planner not so much.

regards, tom lane

On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> I've stopped the query more than 10 times now and EVERY SINGLE ONE
>> finds it in list_concat_unique_ptr().  :-(
>
> Too bad you don't have debug symbols ... it'd be interesting to see
> how long that list is.

[ teaches self how to install debug symbols ]

I stopped it a couple of times. Lengths of list1, list2 respectively:

8876, 20
14649, 18
15334, 10
17148, 18
18173, 18

...Robert

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Too bad you don't have debug symbols ... it'd be interesting to see
>> how long that list is.

> I stopped it a couple of times. Lengths of list1, list2 respectively:

> 8876, 20
> 14649, 18
> 15334, 10
> 17148, 18
> 18173, 18

Yowza. 18000 distinct paths for one relation? Could we see the test
case?

regards, tom lane

On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> Too bad you don't have debug symbols ... it'd be interesting to see
>>> how long that list is.
>
>> I stopped it a couple of times.  Lengths of list1, list2 respectively:
>
>> 8876, 20
>> 14649, 18
>> 15334, 10
>> 17148, 18
>> 18173, 18
>
> Yowza.  18000 distinct paths for one relation?  Could we see the test
> case?

Well, the test case isn't simple, and I'm not sure that my employer
would be pleased if I posted it to a public mailing list. The general
thrust of it is that there is a view, let's call it foo_view, of the
following form, where foo[1-6] are base tables:

foo1 JOIN bar_view JOIN baz_view JOIN foo3 LEFT JOIN foo4 LEFT JOIN
foo5 LEFT JOIN foo6

bar_view is of the following form, bar[1-14] being base tables:

bar1, bletch_view, bar2, bar3, bar4, bar5, bar6, bar7 LEFT JOIN bar8
LEFT JOIN bar9 LEFT JOIN bar10 LEFT JOIN bar11 LEFT JOIN bar12 LEFT
JOIN bar13 LEFT JOIN bar14

baz_view is of the following form, baz[1-9] being base tables:

baz1, baz2, baz3 JOIN baz4 LEFT JOIN baz5 LEFT JOIN baz6 LEFT JOIN
baz7 LEFT JOIN baz8 LEFT JOIN baz9

bletch_view is of the following form, bletch[1-9] being base tables:

bletch1, bletch2 LEFT JOIN bletch3 LEFT JOIN bletch4 LEFT JOIN bletch5
LEFT JOIN bletch6 LEFT JOIN bletch7 LEFT JOIN bletch8 LEFT JOIN
bletch9

Since the webapp front-end gives users a choice of which columns to
pull down, values from most of these tables can potentially appear in
the output. There are a handful of rels in bar_view none of whose
attributes can possibly be needed in the output, so I may make a
slightly stripped down version of bar_view just for this purpose, and
keep the original one around for other queries. I've already done
this for bletch_view, which is a significantly stripped-down version
of a more complex view that is used in other queries.

Most if not all of the joins are from some random column of the
left-hand relation to the primary key of the right-hand relation.
There are no Cartesian products. Most of the base tables have a
unique index on the primary key and no other indices, although a few
of them have one or two additional indices.

...Robert

On Mon, Nov 9, 2009 at 1:42 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>>> On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>>> Too bad you don't have debug symbols ... it'd be interesting to see
>>>> how long that list is.
>>
>>> I stopped it a couple of times.  Lengths of list1, list2 respectively:
>>
>>> 8876, 20
>>> 14649, 18
>>> 15334, 10
>>> 17148, 18
>>> 18173, 18
>>
>> Yowza.  18000 distinct paths for one relation?  Could we see the test
>> case?
>
> Well, the test case isn't simple, and I'm not sure that my employer
> would be pleased if I posted it to a public mailing list. The general
> thrust of it is that [...]

Test case attached. Load this into an empty database and then:

set geqo to off;
set join_collapse_limit to 100;
set from_collapse_limit to 100;
select * from foo_view order by name;

I guess it's somewhat unsurprising that you can make the planner get
into trouble with the above settings - we've been over that ground
before. But it might be possibly interesting that such a simple
schema is capable of generating so many paths. This breaks 40,000
without finishing.

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> I guess it's somewhat unsurprising that you can make the planner get
> into trouble with the above settings - we've been over that ground
> before. But it might be possibly interesting that such a simple
> schema is capable of generating so many paths.

It's not so much so-many-paths as so-many-join-relations that's killing
it. I put some instrumentation into join_search_one_level to count the
number of joinrels it was creating, and got this before getting bored:

join_search_one_level(2): 36 total, 36 by clause, 0 by clauseless, 0 bushy, 0 lastditch; paths/rel min 1 max 4 avg 3.06
join_search_one_level(3): 192 total, 384 by clause, 0 by clauseless, 0 bushy, 0 lastditch; paths/rel min 1 max 6 avg 4.70
join_search_one_level(4): 865 total, 2373 by clause, 0 by clauseless, 222 bushy, 0 lastditch; paths/rel min 1 max 8 avg 6.20
join_search_one_level(5): 3719 total, 12637 by clause, 0 by clauseless, 2239 bushy, 0 lastditch; paths/rel min 2 max 10 avg 7.81
join_search_one_level(6): 15387 total, 62373 by clause, 0 by clauseless, 14562 bushy, 0 lastditch; paths/rel min 3 max 12 avg 9.43
join_search_one_level(7): 59857 total, 283371 by clause, 0 by clauseless, 75771 bushy, 0 lastditch; paths/rel min 4 max 15 avg 10.92

So the number of paths per relation seems to be staying manageable, but
the number of join relations is going through the roof. On the other
hand, you've got 37 base relations here, and (37 choose 7) is 10295472,
so the planner is doing reasonably well at pruning the search tree.

Anyway, the immediate problem is that list_concat_unique_ptr is a bad
way of forming the lists of relations with a certain number of members.
It strikes me that that's easily fixable given that we know when we are
constructing a new RelOptInfo how many members it has. We could add the
rel to the right list at that time, instead of waiting until we get back
up to join_search_one_level. It implies making the joinrels[] array
part of the planner's global state instead of local to make_one_rel and
join_search_one_level, but for the sorts of list lengths we're seeing
here it seems clearly worthwhile. Maybe I'll go try that while I'm
sitting here digesting leftover turkey.

regards, tom lane

On Fri, Nov 27, 2009 at 3:05 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Mon, Nov 9, 2009 at 1:42 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>>>> On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>>>> Too bad you don't have debug symbols ... it'd be interesting to see
>>>>> how long that list is.
>>>
>>>> I stopped it a couple of times.  Lengths of list1, list2 respectively:
>>>
>>>> 8876, 20
>>>> 14649, 18
>>>> 15334, 10
>>>> 17148, 18
>>>> 18173, 18
>>>
>>> Yowza.  18000 distinct paths for one relation?  Could we see the test
>>> case?
>>
>> Well, the test case isn't simple, and I'm not sure that my employer
>> would be pleased if I posted it to a public mailing list. The general
>> thrust of it is that [...]
>
> Test case attached.  Load this into an empty database and then:
>
> set geqo to off;
> set join_collapse_limit to 100;
> set from_collapse_limit to 100;
> select * from foo_view order by name;
>
> I guess it's somewhat unsurprising that you can make the planner get
> into trouble with the above settings - we've been over that ground
> before.  But it might be possibly interesting that such a simple
> schema is capable of generating so many paths.  This breaks 40,000
> without finishing.

Hey, wait a minute. Unless I'm missing something, the items being
accumulated here are not paths (as Tom said upthread and I naively
believed), but RelOptInfos. It looks like we create a RelOptInfo for
every legal join order, so this is going to happen on any large-ish
query where the joins can be reordered relatively freely.

I don't think there's any easy fix for this. When the joins can be
reordered relatively freely, the number of legal join orders is
roughly n!. It might be possible to reduce the overhead associated
with a single one of those join orderings (which consists of a
RelOptInfo, some supporting data structures, and however many paths)
but given the explosive growth of n! that won't buy very much at all,
and it won't make the lists shorter in any case.

Playing around with this a bit, I was easily able to get 2-second
planing times on 15 table join, 6-second planning times on a 16 table
join and 30-second planning times on a 17 table join. This makes it
hard to support raising the GEQO threshold, as most recently suggested
by Greg Sabino Mullane here (and previously by me on an earlier
thread):

http://archives.postgresql.org/pgsql-hackers/2009-11/msg01106.php

What sucks about the current geqo_threshold mechanism is that the
number of tables is a fairly coarse predictor of the number of legal
join orders. On some queries it is close to n! - on others it is far
less. It would be nice if we had a way to either (1) approximate the
number of legal join orders before we start planning the query, and
base the GEQO decision on that number rather than on the number of
tables, or (2) always start with the standard (exhaustive) planner,
and switch to some kind of approximation algorithm (GEQO or otherwise)
if we find that to be impractical. But neither of these seems at all
straightforward.

...Robert

On Sat, Nov 28, 2009 at 12:04 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> It's not so much so-many-paths as so-many-join-relations that's killing
> it.  I put some instrumentation into join_search_one_level to count the
> number of joinrels it was creating, and got this before getting bored:

This is pretty off-topic, but if we had some upper bound on the cost
of the complete plan, we could discard pieces of the plan that already
cost more.

One way to get the upper bound is to generate the plan in depth-first
fashion, instead of the current breadth-first. Instead of bottom-up
dynamic programming, employ memoization.

The doubt I have is that this could show to not be a win because to
discard a sub-plan we would have to consider the startup cost, not the
total cost, and therefore we would be discarding not enough to make it
worthwile. But I thought I`d mention it anyway, in case someone has a
better idea :)

Greetings
Marcin Mańk

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Yowza. 18000 distinct paths for one relation? Could we see the test
>> case?

> Hey, wait a minute. Unless I'm missing something, the items being
> accumulated here are not paths (as Tom said upthread and I naively
> believed), but RelOptInfos.

Yeah, I failed to think carefully about that.

> It looks like we create a RelOptInfo for
> every legal join order, so this is going to happen on any large-ish
> query where the joins can be reordered relatively freely.

Actually, it's more like a RelOptInfo for every combination of base
rels that could be formed along any legal join path (where "legal"
includes the heuristics that avoid clauseless joins when possible).
So the worst case is 2^n for n base rels, but usually considerably
fewer. Nonetheless, even a small fraction of 2^37 is Too Many.

> I don't think there's any easy fix for this.

Nope :-(. I was able to get rid of the specific O(N^2) behavior that
you were running into, but that just pushes the problem out a bit.
FWIW, a profile of CVS HEAD running on this query looks like

samples % symbol name
208189 15.9398 compare_fuzzy_path_costs
116260 8.9014 add_path
97509 7.4657 AllocSetAlloc
78354 5.9991 make_canonical_pathkey
69027 5.2850 generate_join_implied_equalities
65153 4.9884 cost_nestloop
59689 4.5700 bms_is_subset
49176 3.7651 add_paths_to_joinrel
39720 3.0411 bms_overlap
32562 2.4931 cost_mergejoin
30101 2.3047 pathkeys_useful_for_merging
26409 2.0220 AllocSetFree
24459 1.8727 MemoryContextAllocZeroAligned
23247 1.7799 hash_search_with_hash_value
16018 1.2264 check_list_invariants

which is at least unsurprising. However, it eats memory fast enough
to start swapping after level 7 or so, so there is no way that the
exhaustive planner is ever going to finish this problem.

> Playing around with this a bit, I was easily able to get 2-second
> planing times on 15 table join, 6-second planning times on a 16 table
> join and 30-second planning times on a 17 table join. This makes it
> hard to support raising the GEQO threshold, as most recently suggested
> by Greg Sabino Mullane here (and previously by me on an earlier
> thread):

Yeah. I think GEQO or other approximate methods are the only hope for
very large join problems. We could however hope to get to the point of
being able to raise the collapse limits, rather than keeping them
below the geqo_threshold by default. In principle that should result
in better plans ...

regards, tom lane

marcin mank <marcin(dot)mank(at)gmail(dot)com> writes:
> This is pretty off-topic, but if we had some upper bound on the cost
> of the complete plan, we could discard pieces of the plan that already
> cost more.

> One way to get the upper bound is to generate the plan in depth-first
> fashion, instead of the current breadth-first. Instead of bottom-up
> dynamic programming, employ memoization.

Well, the breadth-first approach also allows elimination of large parts
of the search space. It's not immediately obvious to me that the above
would be better. You should be able to try it if you want though ---
these days, there's even a hook to allow replacement of the join search
strategy at runtime.

regards, tom lane

On Fri, Nov 27, 2009 at 8:23 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> I don't think there's any easy fix for this.
>
> Nope :-(.  I was able to get rid of the specific O(N^2) behavior that
> you were running into, but that just pushes the problem out a bit.

Yeah. Testing a couple of the cases I was looking at last night
suggests that your patch shaved off close to 30%, which isn't bad for
a Friday's evening's work. My original email was really about some
GEQO difficulties under 8.3.x, but I think the effort towards
improving the standard planner is well-spent, because the empirical
evidence suggests that everyone always prefers to use the standard
planner whenever possible.

> FWIW, a profile of CVS HEAD running on this query looks like
>
> samples  %        symbol name
> 208189   15.9398  compare_fuzzy_path_costs
> 116260    8.9014  add_path
> 97509     7.4657  AllocSetAlloc
> 78354     5.9991  make_canonical_pathkey
> 69027     5.2850  generate_join_implied_equalities
> 65153     4.9884  cost_nestloop
> 59689     4.5700  bms_is_subset
> 49176     3.7651  add_paths_to_joinrel
> 39720     3.0411  bms_overlap
> 32562     2.4931  cost_mergejoin
> 30101     2.3047  pathkeys_useful_for_merging
> 26409     2.0220  AllocSetFree
> 24459     1.8727  MemoryContextAllocZeroAligned
> 23247     1.7799  hash_search_with_hash_value
> 16018     1.2264  check_list_invariants
>
> which is at least unsurprising.  However, it eats memory fast enough
> to start swapping after level 7 or so, so there is no way that the
> exhaustive planner is ever going to finish this problem.

Yes, that looks similar to what I've seen in the past. The thing
about this is that in a case like this one, the actual join order
barely matters at all because the joins are mostly equivalent. None
of them change the cardinality of the output set, and while in a real
application the various foo{i}, bar{i}, baz{i}, and bletch{i} would be
of somewhat different sizes, it typically doesn't matter very much
which one you do first. If there were a filter criteria on say
bar7_id, you'd want to do the joins necessary to allow the filter to
be applied as early as possible, and then the order of the rest
doesn't matter. Unfortunately, it's hard to know how to formalize
that.

>> Playing around with this a bit, I was easily able to get 2-second
>> planing times on 15 table join, 6-second planning times on a 16 table
>> join and 30-second planning times on a 17 table join.  This makes it
>> hard to support raising the GEQO threshold, as most recently suggested
>> by Greg Sabino Mullane here (and previously by me on an earlier
>> thread):
>
> Yeah.  I think GEQO or other approximate methods are the only hope for
> very large join problems.  We could however hope to get to the point of
> being able to raise the collapse limits, rather than keeping them
> below the geqo_threshold by default.  In principle that should result
> in better plans ...

Yes. from_collapse_limit implementation is all-but-guaranteed to
generate bad plans on queries like "SELECT * FROM foo_view WHERE id =
1". It would be OK to constrain the search space at any given step by
considering joins to only a subset of the relations to which a join
would actually be legal - what we need to avoid is anything that
encourages joining relations to each other before they've been joined
to foo1, which is exactly what from_collapse_limit does. If
from_collapse_limit could be read to mean "once you've joined anything
to a relation within bar_view, you must finish joining to everything
else in bar_view before you can think about joining to anything else",
it would generate tolerable plans. Of course it also wouldn't
constrain the search space nearly as effectively.

...Robert

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

> Playing around with this a bit, I was easily able to get 2-second
> planing times on 15 table join, 6-second planning times on a 16 table
> join and 30-second planning times on a 17 table join. This makes it
> hard to support raising the GEQO threshold, as most recently suggested
> by Greg Sabino Mullane here (and previously by me on an earlier
> thread):

What about 14? Could we at least raise it to 14? 1/2 :)

I'm worried this is going to get bogged down like so many of our
threads, where we worry about verified test cases and getting
things exactly right and end up not making any changes at all
(see also: random_page_cost). Robert, any ideas on a way to fix
this overall process problem, outside of this particular geqo
issue? (If we had a bug tracker, this would certainly be a place
to stick something like this).

- --
Greg Sabino Mullane greg(at)turnstep(dot)com
End Point Corporation
PGP Key: 0x14964AC8 200912011139
http://biglumber.com/x/web?pk=2529DF6AB8F79407E94445B4BC9B906714964AC8
-----BEGIN PGP SIGNATURE-----

iEYEAREDAAYFAksVRroACgkQvJuQZxSWSsjXKgCgk1LEtvDr1mIfUjN9ez/lw60/
HcAAoPSGyqzAXL6hE1YSMb2bQoOm+oKL
=eAYb
-----END PGP SIGNATURE-----

On Tue, Dec 1, 2009 at 11:39 AM, Greg Sabino Mullane <greg(at)turnstep(dot)com> wrote:
>> Playing around with this a bit, I was easily able to get 2-second
>> planing times on 15 table join, 6-second planning times on a 16 table
>> join and 30-second planning times on a 17 table join.  This makes it
>> hard to support raising the GEQO threshold, as most recently suggested
>> by Greg Sabino Mullane here (and previously by me on an earlier
>> thread):
>
> What about 14? Could we at least raise it to 14? 1/2 :)

I doubt we can raise it at all without lying to ourselves about the
likely results of so doing. The GEQO planning times are in the low
double digits of milliseconds. My apps typically have a budget of at
most ~200 ms to plan and execute the query, and I'm not always
operating on empty tables.

> I'm worried this is going to get bogged down like so many of our
> threads, where we worry about verified test cases and getting
> things exactly right and end up not making any changes at all
> (see also: random_page_cost). Robert, any ideas on a way to fix
> this overall process problem, outside of this particular geqo
> issue? (If we had a bug tracker, this would certainly be a place
> to stick something like this).

I'm not sure I agree with the premise that there is a problem in need
of fixing. I think we're usually pretty good about fixing things
when there is a simple, straightforward fix. When the only real fixes
involve writing a lot of code, we tend to be good about fixing them
when - and only when - someone is willing and able to write that code.
Often that's not the case, but that's an economic problem more than a
process problem. And then there are cases (like CRCs) where we can't
even figure out what the code would look like, and then we tend to do
nothing, but what's the other choice?

Obviously you see this issue differently so I'd like to hear more of
your thoughts.

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Tue, Dec 1, 2009 at 11:39 AM, Greg Sabino Mullane <greg(at)turnstep(dot)com> wrote:
>> What about 14? Could we at least raise it to 14? 1/2 :)

> I doubt we can raise it at all without lying to ourselves about the
> likely results of so doing. The GEQO planning times are in the low
> double digits of milliseconds. My apps typically have a budget of at
> most ~200 ms to plan and execute the query, and I'm not always
> operating on empty tables.

The reason this is a configurable parameter is so that people can tune
it to their own needs. I think the current default fits all right with
our usual policy of being conservative about hardware requirements.

regards, tom lane

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

> The reason this is a configurable parameter is so that
> people can tune it to their own needs. I think the current
> default fits all right with our usual policy of being
> conservative about hardware requirements.

That only makes sense if you adjust it accordingly over time.
It's been 12 for a long time - since January 2004 - while
hardware has radically improved in that time, which means that
either 12 was too high five years ago, is too low now, or is very
insensitive to the speed of the hardware. I submit it's probably
more of the second option.

The postgresql.conf file has been supporting "a toaster" for a
long time now, but we don't seem to recognize that the minimum
toaster^H^Hhardware encountered in the wild changes quite a
bit from year to year. IMHO.

- --
Greg Sabino Mullane greg(at)turnstep(dot)com
End Point Corporation
PGP Key: 0x14964AC8 200912021651
http://biglumber.com/x/web?pk=2529DF6AB8F79407E94445B4BC9B906714964AC8
-----BEGIN PGP SIGNATURE-----

iEYEAREDAAYFAksW4YMACgkQvJuQZxSWSsg7gACggzmyKkudzomoleil3PYMnB+z
j+UAoMhi9yEAi8iPBVnailm8jKTe+z39
=++Jr
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

>> What about 14? Could we at least raise it to 14? 1/2 :)

> I doubt we can raise it at all without lying to ourselves about the
> likely results of so doing. The GEQO planning times are in the low
> double digits of milliseconds. My apps typically have a budget of at
> most ~200 ms to plan and execute the query, and I'm not always
> operating on empty tables.

Well, this might be addressed elsewhere, but it's not just the planning
time, it's the non-repeatable plans when you hit geqo. That tends to
drive my clients mad (as in very confused, and then angry). And the plans
that geqo comes up with are seldom very good ones either. So yes, it's an
adjustable knob, but I'd rather see it default to 0 or >= 14.

>> I'm not sure I agree with the premise that there is a problem in need
>> of fixing. I think we're usually pretty good about fixing things
>> when there is a simple, straightforward fix. When the only real fixes
>> involve writing a lot of code, we tend to be good about fixing them
>> when - and only when - someone is willing and able to write that code.
>> Often that's not the case, but that's an economic problem more than a
>> process problem. And then there are cases (like CRCs) where we can't
>> even figure out what the code would look like, and then we tend to do
>> nothing, but what's the other choice?

>> Obviously you see this issue differently so I'd like to hear more of
>> your thoughts.

Well, it's more a matter of consensus on the Right Thing To Do rather
than a Simple Matter of Coding. Some of the more interesting conversations
over the years has been on what to set the defaults to (random_page_cost
anyone?). The conflict is then "real world anecdotes" versus "test-backed,
data-driven numbers". It's hard to get real numbers on many things,
especially when people are using Postgres on a staggeringly large collection
of hardware, database size, activity, etc. There's always a balance to
hit the sweet spot for many knobs (both in postgresql.conf and elsewhere)
between benefitting the most people while adversely impacting the least
number of people. The project has been very, very conservative in this
respect, which is why they need people like me who keep pushing in the
other direction. Even if I secretly agree with Tom 99% of the time. :)

- --
Greg Sabino Mullane greg(at)turnstep(dot)com
End Point Corporation
PGP Key: 0x14964AC8 200912021705
http://biglumber.com/x/web?pk=2529DF6AB8F79407E94445B4BC9B906714964AC8
-----BEGIN PGP SIGNATURE-----

iEYEAREDAAYFAksW5SoACgkQvJuQZxSWSsjmlQCePLKdyrCLpv86tIQtDbazKe+4
l5EAn3KfOy+ySxqhIe9UG2Jtshlb93Up
=U7PP
-----END PGP SIGNATURE-----

"Greg Sabino Mullane" <greg(at)turnstep(dot)com> writes:
>> The reason this is a configurable parameter is so that
>> people can tune it to their own needs. I think the current
>> default fits all right with our usual policy of being
>> conservative about hardware requirements.

> That only makes sense if you adjust it accordingly over time.
> It's been 12 for a long time - since January 2004 - while
> hardware has radically improved in that time, which means that
> either 12 was too high five years ago, is too low now, or is very
> insensitive to the speed of the hardware. I submit it's probably
> more of the second option.

I don't have a problem with the third explanation ;-). The issue here
is really planner speed relative to execution speed, and that's not so
hardware-sensitive as all that. Yeah, you can plan a 12-join query
way faster than ten years ago, but you can execute it way faster too,
and that's what drives expectations for planning speed. Flat-planning
a 15-way query costs just as much more relative to a 12-way query as
it did ten years ago.

regards, tom lane

On Wed, Dec 2, 2009 at 5:08 PM, Greg Sabino Mullane <greg(at)turnstep(dot)com> wrote:
>>> What about 14? Could we at least raise it to 14? 1/2 :)
>
>> I doubt we can raise it at all without lying to ourselves about the
>> likely results of so doing.  The GEQO planning times are in the low
>> double digits of milliseconds.  My apps typically have a budget of at
>> most ~200 ms to plan and execute the query, and I'm not always
>> operating on empty tables.
>
> Well, this might be addressed elsewhere, but it's not just the planning
> time, it's the non-repeatable plans when you hit geqo. That tends to
> drive my clients mad (as in very confused, and then angry). And the plans
> that geqo comes up with are seldom very good ones either. So yes, it's an
> adjustable knob, but I'd rather see it default to 0 or >= 14.

Actually, I think Tom made some changes for 8.5 that should eliminate
the randomness, if not the badness. Or am I misremembering?

One other thing I'm noticing about the current implementation is that
it seems to spend an entirely excessive amount of brain power
considering the best order in which to execute cross-joins. If I do
X, A JOIN B ON Pab JOIN C ON Pac JOIN D ON Pad JOIN E ON Pae, it looks
to me like join_search_one_level() will try joining X to each of A-E.
That seems fairly pointless; why would I ever want to join X to
anything other than {A B C D E}?

> Well, it's more a matter of consensus on the Right Thing To Do rather
> than a Simple Matter of Coding. Some of the more interesting conversations
> over the years has been on what to set the defaults to (random_page_cost
> anyone?). The conflict is then "real world anecdotes" versus "test-backed,
> data-driven numbers". It's hard to get real numbers on many things,
> especially when people are using Postgres on a staggeringly large collection
> of hardware, database size, activity, etc. There's always a balance to
> hit the sweet spot for many knobs (both in postgresql.conf and elsewhere)
> between benefitting the most people while adversely impacting the least
> number of people. The project has been very, very conservative in this
> respect, which is why they need people like me who keep pushing in the
> other direction. Even if I secretly agree with Tom 99% of the time. :)

Heh. Well, we did raise default_statistics_target quite a bit for
8.4. I suggested raising from_collapse_threshold,
join_collapse_threshold, and geqo_threshold, but diligent
experimenation by Tom and Andres Freund revealed this idea to suck. I
think it's an interesting area for more work to try to eliminate the
suckage, but I don't think we're there yet. I don't think I remember
the last round of debates about random_page_cost and seq_page_cost;
the current values probably are too high for most people, because
typically you've got a lot of stuff cached. We should maybe also
think about raising the default value for work_mem. It's hard for me
to believe that the average Postgres user wants a sort that takes more
than 1MB of memory to spill to disk; there certainly are people who
probably want that, but I doubt there are very many. I believe we've
been using that value for a decade, and memory size has increased a
lot in that time.

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> Actually, I think Tom made some changes for 8.5 that should eliminate
> the randomness, if not the badness. Or am I misremembering?

It was mostly Andres' work, see
http://archives.postgresql.org/pgsql-committers/2009-07/msg00148.php

> One other thing I'm noticing about the current implementation is that
> it seems to spend an entirely excessive amount of brain power
> considering the best order in which to execute cross-joins. If I do
> X, A JOIN B ON Pab JOIN C ON Pac JOIN D ON Pad JOIN E ON Pae, it looks
> to me like join_search_one_level() will try joining X to each of A-E.
> That seems fairly pointless; why would I ever want to join X to
> anything other than {A B C D E}?

Not sure that a lot of cross joins with no conditions is the case to
design around. Usually queries aren't that devoid of features of
interest, and so different join paths are actually usefully different.

> ... We should maybe also
> think about raising the default value for work_mem. It's hard for me
> to believe that the average Postgres user wants a sort that takes more
> than 1MB of memory to spill to disk; there certainly are people who
> probably want that, but I doubt there are very many. I believe we've
> been using that value for a decade, and memory size has increased a
> lot in that time.

Maybe. I'll certainly grant that machines have more memory, but is the
average Postgres installation using that to run bigger sorts, or to run
more sorts (either more concurrent queries or more complex queries
containing more sorts)? We know that increasing work_mem too much
can be counterproductive, and much sooner than one might think.

regards, tom lane

On Wed, Dec 2, 2009 at 9:55 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> One other thing I'm noticing about the current implementation is that
>> it seems to spend an entirely excessive amount of brain power
>> considering the best order in which to execute cross-joins.  If I do
>> X, A JOIN B ON Pab JOIN C ON Pac JOIN D ON Pad JOIN E ON Pae, it looks
>> to me like join_search_one_level() will try joining X to each of A-E.
>> That seems fairly pointless; why would I ever want to join X to
>> anything other than {A B C D E}?
>
> Not sure that a lot of cross joins with no conditions is the case to
> design around.  Usually queries aren't that devoid of features of
> interest, and so different join paths are actually usefully different.

Not sure what you mean. There's already a special-case code path for
cross joins; but I think it's probably considering a lot of silly
paths. Is there a case where it makes sense to do cross joins at some
stage of the process other than last?

>> ...  We should maybe also
>> think about raising the default value for work_mem.  It's hard for me
>> to believe that the average Postgres user wants a sort that takes more
>> than 1MB of memory to spill to disk; there certainly are people who
>> probably want that, but I doubt there are very many.  I believe we've
>> been using that value for a decade, and memory size has increased a
>> lot in that time.
>
> Maybe.  I'll certainly grant that machines have more memory, but is the
> average Postgres installation using that to run bigger sorts, or to run
> more sorts (either more concurrent queries or more complex queries
> containing more sorts)?  We know that increasing work_mem too much
> can be counterproductive, and much sooner than one might think.

A further confounding factor is that work_mem also controls memory
usage for hash tables - whereas the original sort_mem did not - and at
least in my experience it's more common to have multiple hashes in a
query than multiple sorts. It would be nice to have some data on
this rather than just hand-waving, but I'm not sure how to get it.
For default_statistics_target, *_collapse_threshold, and
geqo_threshold, we were able to construct worst-case queries and
benchmark them. I have no idea how to do something comparable for
work_mem.

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> Not sure what you mean. There's already a special-case code path for
> cross joins; but I think it's probably considering a lot of silly
> paths. Is there a case where it makes sense to do cross joins at some
> stage of the process other than last?

They *are* done last, as a rule, because of the heuristic that prefers to
join where there's a join clause. (However I've gotten negative comments
about that --- some people think that when joining small detail tables
to a big fact table, it'd be better to cross-join the detail tables and
then do one multi-clause join to the big table. I'm unconvinced myself
but there does seem to be more than one school of thought about it.)

regards, tom lane

On Wed, Dec 2, 2009 at 10:32 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> Not sure what you mean.  There's already a special-case code path for
>> cross joins; but I think it's probably considering a lot of silly
>> paths.  Is there a case where it makes sense to do cross joins at some
>> stage of the process other than last?
>
> They *are* done last, as a rule, because of the heuristic that prefers to
> join where there's a join clause.

Well, when I was testing, I believe I observed that an n-way join with
1 cross join was slower to plan than an n-way join with no cross
joins. ISTM that it should actually be faster, because you should
plan it like an (n-1)-way join and then do the cross join at the end.

> (However I've gotten negative comments
> about that --- some people think that when joining small detail tables
> to a big fact table, it'd be better to cross-join the detail tables and
> then do one multi-clause join to the big table.  I'm unconvinced myself
> but there does seem to be more than one school of thought about it.)

Sounds weird to me. There might be a sweet spot where that's true (3
or 4 detail tables with 2 or 3 rows each, that aren't too wide?) but
even if there is, I bet it's not very big. If someone cares though it
should be possible to convince the planner to execute the query that
way (using OFFSET 0, maybe) and benchmark it vs. whatever the planner
wants to do otherwise.

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> Well, when I was testing, I believe I observed that an n-way join with
> 1 cross join was slower to plan than an n-way join with no cross
> joins. ISTM that it should actually be faster, because you should
> plan it like an (n-1)-way join and then do the cross join at the end.

It's not entirely clear to me what case you're describing, but I wonder
whether this was a "flat" join problem or restricted by the collapse
limits.

regards, tom lane

On Wed, Dec 2, 2009 at 10:53 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> Well, when I was testing, I believe I observed that an n-way join with
>> 1 cross join was slower to plan than an n-way join with no cross
>> joins.  ISTM that it should actually be faster, because you should
>> plan it like an (n-1)-way join and then do the cross join at the end.
>
> It's not entirely clear to me what case you're describing, but I wonder
> whether this was a "flat" join problem or restricted by the collapse
> limits.

Argh. I can't reproduce exactly what I thought I was seeing before.
However, with the attached schema, geqo off, and the collapse
thresholds set to 100, "explain select * from bar2_view" and "explain
select * from bar3_view" have roughly the same run time. They are
identical except that one of the join clauses has been omitted in the
second case. One would think that the second case could be planned
faster, if we plan to just leave the cross join to the end.

(And in fact on my system if you remove bar8 from the second view
entirely the plan time improves by a factor of six.)

...Robert

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

> I don't have a problem with the third explanation ;-). The issue here
> is really planner speed relative to execution speed, and that's not so
> hardware-sensitive as all that. Yeah, you can plan a 12-join query
> way faster than ten years ago, but you can execute it way faster too,
> and that's what drives expectations for planning speed. Flat-planning
> a 15-way query costs just as much more relative to a 12-way query as
> it did ten years ago.

Even granted that ratio has stayed the same (and I'd think the planning
speed would increase slightly faster than the execution speed, no?), the
underlying factor is that there is a magic sweet spot at which we start
making tradeoffs for the user. Even if a flat 15-way is the same relative to a
12-way, the absolute numbers should be the prime consideration. In other
words, if the average flat plan/execute speed for a 13-way on an average
box was 15 seconds in 2000, but 2 seconds in 2009, I would presume that
it would now be worth it to consider 13 as needing default geqo coverage.

- --
Greg Sabino Mullane greg(at)turnstep(dot)com
End Point Corporation
PGP Key: 0x14964AC8 200912040823
http://biglumber.com/x/web?pk=2529DF6AB8F79407E94445B4BC9B906714964AC8
-----BEGIN PGP SIGNATURE-----

iEYEAREDAAYFAksZDbkACgkQvJuQZxSWSsjjLgCeKIFStyakHzCQljeqtX2Ie5wi
8fgAoM8ZsXHrVWgmM7UsSP6dKGslQVWK
=g6ET
-----END PGP SIGNATURE-----