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@postgresql.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@postgresql.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@anarazel.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@postgresql.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@anarazel.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@postgresql.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@anarazel.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@anarazel.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@postgresql.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@gmail.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@anarazel.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@anarazel.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@postgresql.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@gmail.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@sss.pgh.pa.us> wrote:
Robert Haas <robertmhaas@gmail.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@gmail.com> writes:
On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl@sss.pgh.pa.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@sss.pgh.pa.us> wrote:
Robert Haas <robertmhaas@gmail.com> writes:
On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl@sss.pgh.pa.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, 18Yowza. 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@gmail.com> wrote:
On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Robert Haas <robertmhaas@gmail.com> writes:
On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl@sss.pgh.pa.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, 18Yowza. 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
Attachments:
Robert Haas <robertmhaas@gmail.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@gmail.com> wrote:
On Mon, Nov 9, 2009 at 1:42 PM, Robert Haas <robertmhaas@gmail.com> wrote:
On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Robert Haas <robertmhaas@gmail.com> writes:
On Mon, Nov 9, 2009 at 10:57 AM, Tom Lane <tgl@sss.pgh.pa.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, 18Yowza. 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@sss.pgh.pa.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@gmail.com> writes:
On Mon, Nov 9, 2009 at 1:10 PM, Tom Lane <tgl@sss.pgh.pa.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.mank@gmail.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@sss.pgh.pa.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_invariantswhich 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@turnstep.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-----