Re: GEQO vs join order restrictions

Andres Freund <andres(at)anarazel(dot)de> writes:
> On Saturday 18 July 2009 17:48:14 Tom Lane wrote:
>> I'm inclined to address this by rewriting gimme_tree so that it *always*
>> finds a valid join order based on the given tour. This would involve
>> searching the whole stack for a possible join partner instead of
>> considering only the topmost stack entry. It sounds inefficient, but
>> it's not nearly as bad as wasting the entire cycle by failing near
>> the end, which is what happens now.

> I guess this should be relatively easy to implement and test?

I wrote a prototype patch for this (attached --- it works, but isn't
terribly well commented). It definitely helps, but it's not the whole
answer. I did some testing using your example query. This table shows
PREPARE times in seconds on a 2.8GHz Xeon EM64T for various settings of
join_collapse_limit and from_collapse_limit (I kept them the same for
each test):

COLLAPSE_LIMITS
8 10 12 14 20 100

GEQO off 16.6 32.1 70.6 (starts to swap)
GEQO, CVS HEAD 2641.6 2849.7 >42000* (failed to make a valid plan)
GEQO, with patch 589.3 596.9 736.1 800.8 1052.4 3735.2

* I left the HEAD/12 case running overnight and it still isn't done...

The regular planner becomes essentially useless at collapse limit 14 or
more; at 14 its memory consumption approaches 2GB which is more than
this box has got, and drives the machine into swap hell. I didn't
try larger settings, but they'd be worse.

The CVS-HEAD version of GEQO dies with "failed to make a valid plan"
at collapse limit 14, because random_init_pool gives up after 10000
failed attempts. It would get worse with higher limits because of
having more join order constraints in the same problem. I think the
reason the runtime goes to the moon at 12 is that a very large
percentage of tours fail, but not quite enough to trigger the 10000-
failures sanity check.

With the patch, GEQO manages to bumble through and produce a plan
even at high collapse limits. It's a whole lot slower than the
regular planner, and I found out that this time consists largely
of desirable_join() checks in gimme_tree(). I said earlier that
the regular planner does that too ... but GEQO is doing it a lot
more, because it repeats the whole planning cycle 500 times.
In previous tests we've seen regular planner runtime cross over
GEQO time around collapse_limit 12. It seems the reason that
this case is so different is that the total problem is so much
larger, and so there is a very large equivalence-class list
(1289 items!) that gets trawled through in each desirable_join check.
That's why have_relevant_eclass_joinclause shows up so high in oprofile.

A very important property not directly exposed in the above table
is that GEQO manages to produce the plan with bounded memory usage.
The process size was consistently 160-200MB for all of the bottom
table row. This is because it throws away the joinrel information
for all the join paths explored and not taken.

My conclusions are:

1. I should clean up and apply the attached patch. Even though it's
not the whole answer, it clearly makes things a good deal better.

2. We need to look into a more efficient representation for making
have_relevant_joinclause and have_join_order_restriction tests.
This is obviously not material for this commitfest, though. An
important point is that we can't just throw memory at the problem,
or we'll be giving up one of GEQO's advantages.

3. I think this puts the final nail in the coffin of the idea that
we can get rid of the collapse_limits altogether. I confess to having
forgotten that one of their major functions was to bound memory usage in
the regular planner, but this set of test runs adequately reminded me.
I still think that we could look at revisiting their default values,
but we'll probably want to fix GEQO per point 2 before we do any more
testing.

Barring objections, I'm going to mark the "remove collapse limits"
patch as rejected.

regards, tom lane