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

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