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

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