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

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