Thread: GEQO vs join order restrictions
I spent a bit of time looking into why GEQO behaves so miserably on the test case Andres Freund presented here: http://archives.postgresql.org/message-id/200907091700.43411.andres@anarazel.de The difficulty seems to be that the problem query is full of join order restrictions; in particular lots of joins inside the right side of a LEFT JOIN. So those sub-joins have to occur before their relations can be joined to anything else. When GEQO generates a random join sequence, it is very likely indeed that such pairs of relations will not be adjacent in the raw join sequence. There is some code in gimme_tree() (the "stack" business I added here: http://archives.postgresql.org/pgsql-committers/2004-01/msg00186.php ) that was meant to try to deal with that, but I now realize that it entirely fails to do so. Given two relations that have to be joined to each other first, if they are not already adjacent in the input then they just create two separate stack entries and the algorithm never tries to join them to each other. So the failure rate in the presence of join order restrictions is very high, and it gets rapidly worse as the join problem size increases. This explains Andres' observation of random_init_pool() reporting complete failure at high collapse_limit settings. We can't really expect a random search process to be efficient at discovering that two out of a hundred items must be adjacent --- especially not if the problem has multiple restrictions like that and the only feedback it gets is overall success or failure. 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. A different line of thought is to add some knowledge about join order restrictions to tour generation, such that the code never generates an invalid join order to start with. Unfortunately it's not at all clear how to do that. Ideas, comments? regards, tom lane
On Saturday 18 July 2009 17:48:14 Tom Lane wrote: > I spent a bit of time looking into why GEQO behaves so miserably on the > test case Andres Freund presented here: > http://archives.postgresql.org/message-id/200907091700.43411.andres@anaraze >l.de > > The difficulty seems to be that the problem query is full of join order > restrictions; in particular lots of joins inside the right side of a > LEFT JOIN. So those sub-joins have to occur before their relations > can be joined to anything else. When GEQO generates a random join > sequence, it is very likely indeed that such pairs of relations will > not be adjacent in the raw join sequence. There is some code in > gimme_tree() (the "stack" business I added here: > http://archives.postgresql.org/pgsql-committers/2004-01/msg00186.php > ) that was meant to try to deal with that, but I now realize that it > entirely fails to do so. Given two relations that have to be joined > to each other first, if they are not already adjacent in the input > then they just create two separate stack entries and the algorithm > never tries to join them to each other. So the failure rate in the > presence of join order restrictions is very high, and it gets rapidly > worse as the join problem size increases. This explains Andres' > observation of random_init_pool() reporting complete failure at high > collapse_limit settings. We can't really expect a random search process > to be efficient at discovering that two out of a hundred items must be > adjacent --- especially not if the problem has multiple restrictions > like that and the only feedback it gets is overall success or failure. Yes, this sound sensible and follows the same line of thought I started to have after you suggested the problem is in random_init_pool. This also explains why I saw nearly no improvement during the genetic search itself. The paths out of random_init_pool were already hugely selected, so there were not that many improvements to find and a change was relatively like to yield a impossible ordering. > 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? > A different line of thought is to add some knowledge about join order > restrictions to tour generation, such that the code never generates an > invalid join order to start with. Unfortunately it's not at all clear > how to do that. I haven't really thought much about that yet, but wouldn't it be possible to iteratively check the current path during tour generation for every relation added? If the next relation yields a impossible ordering, choose another relation as next, if no more left, restart? I do even less know how feasible this is, but given that joins in the right hand side of a LEFT JOIN are not really useful to study from the outside in the general case, would it be possible to "hide" them below the join during join order planning? If yes, that should be applicable for the normal planner as well. I do realize that this is nothing one could fastly cook up and that it would require changes in lots of places, but as a general idea... Andres
Andres Freund <andres@anarazel.de> writes:
> This also explains why I saw nearly no improvement during the genetic search
> itself. The paths out of random_init_pool were already hugely selected, so
> there were not that many improvements to find and a change was relatively like
> to yield a impossible ordering.
Yeah, I suspect most of the variants tried during that phase simply
failed.
> I do even less know how feasible this is, but given that joins in the right
> hand side of a LEFT JOIN are not really useful to study from the outside in
> the general case, would it be possible to "hide" them below the join during
> join order planning?
We could refrain from collapsing the sub-problem during joinlist
formation. But the trouble with that is it creates a "hard" join order
restriction. Most of the restrictions are "soft" to some extent, ie,
you can do some rearrangements but not others. It might be worth
looking at though; in the cases where there is no chance of a
rearrangement, it would save cycles for either regular or GEQO planning.
regards, tom lane
On Sat, Jul 18, 2009 at 12:49 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:
> We could refrain from collapsing the sub-problem during joinlist
> formation. But the trouble with that is it creates a "hard" join order
> restriction. Most of the restrictions are "soft" to some extent, ie,
> you can do some rearrangements but not others. It might be worth
> looking at though; in the cases where there is no chance of a
> rearrangement, it would save cycles for either regular or GEQO planning.
This seems very promising, although the proof of the pudding is in the
eating. As a slight refinement of this idea, it's not exactly that
the join order is totally fixed, but rather that in a large join nest
there may be groups of tables that can be planned as independent
subproblems. The obvious example of this is something like:
(...lots of stuff...) FULL JOIN (...lots of things...)
...where there isn't any point in considering any joins between stuff
and things, regardless of whether you are using GEQO or the standard
planner (and maybe we handle this case already?). My brain is a
little foggy at the moment, but I think this would also apply to
Andres' example query, because I believe with anything of the form...
A LEFT JOIN (B1 INNER JOIN B2 INNER JOIN B3 ... INNER JOIN Bn) LEFT JOIN C
...the set of all Bi can be planned as an independent subproblem and
then joined to A either before or after C. But (I think):
A LEFT JOIN (B1 INNER JOIN B2 LEFT JOIN B3) LEFT JOIN C
= A LEFT JOIN (B1 INNER JOIN B2) LEFT JOIN C LEFT JOIN B3
Here {B1, B2} is an independent subproblem, but {B1, B2, B3} is not.
Still, given that the planning time for the standard planner at least
can grow exponentially in the number of relations, even a small
reduction in the problem size is potentially a big win.
...Robert
Andres Freund <andres@anarazel.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
*** src/backend/optimizer/geqo/geqo_eval.c.orig Thu Jul 16 16:55:44 2009
--- src/backend/optimizer/geqo/geqo_eval.c Sat Jul 18 16:42:07 2009
***************
*** 128,133 ****
--- 128,214 ----
return fitness;
}
+ typedef struct
+ {
+ RelOptInfo *joinrel;
+ int size;
+ } Clump;
+
+ static List *
+ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, bool force)
+ {
+ ListCell *prev;
+ ListCell *lc;
+
+ /* Look for a clump it can join to, allowing only desirable joins */
+ prev = NULL;
+ foreach(lc, clumps)
+ {
+ Clump *old_clump = (Clump *) lfirst(lc);
+
+ if (force ||
+ desirable_join(root, old_clump->joinrel, new_clump->joinrel))
+ {
+ RelOptInfo *joinrel;
+
+ /*
+ * Construct a RelOptInfo representing the join of these two input
+ * relations. Note that we expect the joinrel not to exist in
+ * root->join_rel_list yet, and so the paths constructed for it
+ * will only include the ones we want.
+ */
+ joinrel = make_join_rel(root,
+ old_clump->joinrel,
+ new_clump->joinrel);
+
+ /* Keep searching if join order is not valid */
+ if (joinrel)
+ {
+ /* Find and save the cheapest paths for this joinrel */
+ set_cheapest(joinrel);
+
+ /* Absorb new clump into old */
+ old_clump->joinrel = joinrel;
+ old_clump->size += new_clump->size;
+ pfree(new_clump);
+
+ /* Temporarily remove old_clump from list */
+ clumps = list_delete_cell(clumps, lc, prev);
+
+ /*
+ * Recursively try to merge the enlarged old_clump with
+ * others. When no further merge is possible, we'll reinsert
+ * it into the list.
+ */
+ return merge_clump(root, clumps, old_clump, force);
+ }
+ }
+ prev = lc;
+ }
+
+ /*
+ * No merging is possible, so add new_clump as an independent clump, in
+ * proper order according to size. We can be fast for the common case
+ * where it has size 1 --- it should always go at the end.
+ */
+ if (clumps == NIL || new_clump->size == 1)
+ return lappend(clumps, new_clump);
+
+ /* Else search for the place to insert it */
+ lc = list_head(clumps);
+ for (;;)
+ {
+ ListCell *nxt = lnext(lc);
+
+ if (nxt == NULL || new_clump->size > ((Clump *) lfirst(nxt))->size)
+ break; /* it belongs after 'lc', before 'nxt' */
+ lc = nxt;
+ }
+ lappend_cell(clumps, lc, new_clump);
+
+ return clumps;
+ }
+
/*
* gimme_tree
* Form planner estimates for a join tree constructed in the specified
***************
*** 136,249 ****
* 'tour' is the proposed join order, of length 'num_gene'
*
* Returns a new join relation whose cheapest path is the best plan for
! * this join order. NB: will return NULL if join order is invalid.
*
* The original implementation of this routine always joined in the specified
* order, and so could only build left-sided plans (and right-sided and
* mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
* It could never produce a "bushy" plan. This had a couple of big problems,
! * of which the worst was that as of 7.4, there are situations involving IN
! * subqueries where the only valid plans are bushy.
*
* The present implementation takes the given tour as a guideline, but
! * postpones joins that seem unsuitable according to some heuristic rules.
! * This allows correct bushy plans to be generated at need, and as a nice
! * side-effect it seems to materially improve the quality of the generated
! * plans.
*/
RelOptInfo *
gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
{
GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
! RelOptInfo **stack;
! int stack_depth;
! RelOptInfo *joinrel;
int rel_count;
/*
! * Create a stack to hold not-yet-joined relations.
*/
! stack = (RelOptInfo **) palloc(num_gene * sizeof(RelOptInfo *));
! stack_depth = 0;
- /*
- * Push each relation onto the stack in the specified order. After
- * pushing each relation, see whether the top two stack entries are
- * joinable according to the desirable_join() heuristics. If so, join
- * them into one stack entry, and try again to combine with the next stack
- * entry down (if any). When the stack top is no longer joinable,
- * continue to the next input relation. After we have pushed the last
- * input relation, the heuristics are disabled and we force joining all
- * the remaining stack entries.
- *
- * If desirable_join() always returns true, this produces a straight
- * left-to-right join just like the old code. Otherwise we may produce a
- * bushy plan or a left/right-sided plan that really corresponds to some
- * tour other than the one given. To the extent that the heuristics are
- * helpful, however, this will be a better plan than the raw tour.
- *
- * Also, when a join attempt fails (because of OJ or IN constraints), we
- * may be able to recover and produce a workable plan, where the old code
- * just had to give up. This case acts the same as a false result from
- * desirable_join().
- */
for (rel_count = 0; rel_count < num_gene; rel_count++)
{
int cur_rel_index;
! /* Get the next input relation and push it */
cur_rel_index = (int) tour[rel_count];
! stack[stack_depth] = (RelOptInfo *) list_nth(private->initial_rels,
! cur_rel_index - 1);
! stack_depth++;
!
! /*
! * While it's feasible, pop the top two stack entries and replace with
! * their join.
! */
! while (stack_depth >= 2)
! {
! RelOptInfo *outer_rel = stack[stack_depth - 2];
! RelOptInfo *inner_rel = stack[stack_depth - 1];
! /*
! * Don't pop if heuristics say not to join now. However, once we
! * have exhausted the input, the heuristics can't prevent popping.
! */
! if (rel_count < num_gene - 1 &&
! !desirable_join(root, outer_rel, inner_rel))
! break;
! /*
! * Construct a RelOptInfo representing the join of these two input
! * relations. Note that we expect the joinrel not to exist in
! * root->join_rel_list yet, and so the paths constructed for it
! * will only include the ones we want.
! */
! joinrel = make_join_rel(root, outer_rel, inner_rel);
! /* Can't pop stack here if join order is not valid */
! if (!joinrel)
! break;
!
! /* Find and save the cheapest paths for this rel */
! set_cheapest(joinrel);
!
! /* Pop the stack and replace the inputs with their join */
! stack_depth--;
! stack[stack_depth - 1] = joinrel;
}
}
/* Did we succeed in forming a single join relation? */
! if (stack_depth == 1)
! joinrel = stack[0];
! else
! joinrel = NULL;
!
! pfree(stack);
! return joinrel;
}
/*
--- 217,299 ----
* 'tour' is the proposed join order, of length 'num_gene'
*
* Returns a new join relation whose cheapest path is the best plan for
! * this join order.
*
* The original implementation of this routine always joined in the specified
* order, and so could only build left-sided plans (and right-sided and
* mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
* It could never produce a "bushy" plan. This had a couple of big problems,
! * of which the worst was that there are situations involving join order
! * restrictions where the only valid plans are bushy.
*
* The present implementation takes the given tour as a guideline, but
! * postpones joins that are illegal or seem unsuitable according to some
! * heuristic rules. This allows correct bushy plans to be generated at need,
! * and as a nice side-effect it seems to materially improve the quality of the
! * generated plans.
*/
RelOptInfo *
gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
{
GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
! List *clumps;
int rel_count;
/*
! * Sometimes, a relation can't yet be joined to others due to heuristics
! * or actual semantic restrictions. We maintain a list of "clumps" of
! * successfully joined relations, with larger clumps at the front.
! * Each new relation from the tour is added to the first clump it can
! * be joined to; if there is none then it becomes a new clump of its own.
! * When we enlarge an existing clump we check to see if it can now be
! * merged with any other clumps. After the tour is all scanned, we
! * forget about the heuristics and try to forcibly join any remaining
! * clumps. Some forced joins might still fail due to semantics, but
! * we should always be able to find some join order that works.
*/
! clumps = NIL;
for (rel_count = 0; rel_count < num_gene; rel_count++)
{
int cur_rel_index;
+ RelOptInfo *cur_rel;
+ Clump *cur_clump;
! /* Get the next input relation */
cur_rel_index = (int) tour[rel_count];
! cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
! cur_rel_index - 1);
! /* Make it into a single-rel clump */
! cur_clump = (Clump *) palloc(sizeof(Clump));
! cur_clump->joinrel = cur_rel;
! cur_clump->size = 1;
! /* Merge it into the clumps list, using only desirable joins */
! clumps = merge_clump(root, clumps, cur_clump, false);
! }
! if (list_length(clumps) > 1)
! {
! /* Force-join the remaining clumps in some legal order */
! List *fclumps;
! ListCell *lc;
!
! fclumps = NIL;
! foreach(lc, clumps)
! {
! Clump *clump = (Clump *) lfirst(lc);
!
! fclumps = merge_clump(root, fclumps, clump, true);
}
+ clumps = fclumps;
}
/* Did we succeed in forming a single join relation? */
! if (list_length(clumps) != 1)
! elog(ERROR, "gimme_tree failed to form single join relation");
! return ((Clump *) linitial(clumps))->joinrel;
}
/*
On Sun, Jul 19, 2009 at 1:23 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote: > 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. Yeah, I think that's probably right. I still have some hope that we will be able to get rid of these limits or dramatically raise them at some point in the future, but it sounds like we have a good chunk of work to do first. I really appreciate the testing that went into finding and starting to fix these problems. Many thanks to both Andres and Tom. Tom, do you think the "independent subproblem" stuff from last night would be worth pursuing? I haven't really looked at the code yet but I would be willing to work on it when I have time; it would be useful to have your thoughts on the approach before starting, though. ...Robert
Robert Haas <robertmhaas@gmail.com> writes:
> Tom, do you think the "independent subproblem" stuff from last night
> would be worth pursuing?
It's worth looking into. I'm not certain if it will end up being a good
idea or not. Right now the joinlist collapse code is pretty stupid
(as you know --- it only thinks about the collapse_limit variables,
plus IIRC it knows about FULL JOIN). Making it smarter might result in
duplication of logic, or require unpleasant refactoring to avoid such
duplication, or even add more cycles than it's likely to save later on.
Another issue is order of operations: I'm not sure if all the
information needed to make such decisions has been computed at that
point. But we won't know unless we try it. It seems at least
potentially useful.
regards, tom lane
Hi Tom, Robert, Hi all, nks, On Sunday 19 July 2009 19:23:18 Tom Lane wrote: > Andres Freund <andres@anarazel.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? > 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. > 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. I did some testing with the original queries and the unsurprising result is, that the planning time is *hugely* smaller (multiple orders of magnitude) and the execution time is bigger (~15% ) with the few variation of settings I tested. Many unplanable queries are now planable. Thanks, Andres
On Sun, Jul 19, 2009 at 3:08 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> Tom, do you think the "independent subproblem" stuff from last night
>> would be worth pursuing?
>
> It's worth looking into. I'm not certain if it will end up being a good
> idea or not. Right now the joinlist collapse code is pretty stupid
> (as you know --- it only thinks about the collapse_limit variables,
> plus IIRC it knows about FULL JOIN). Making it smarter might result in
> duplication of logic, or require unpleasant refactoring to avoid such
> duplication, or even add more cycles than it's likely to save later on.
> Another issue is order of operations: I'm not sure if all the
> information needed to make such decisions has been computed at that
> point. But we won't know unless we try it. It seems at least
> potentially useful.
I thought about this a little more and I don't think it's going to
work. The problem is that LEFT joins can be reordered VERY freely.
So if you have something like:
A LJ (B IJ C IJ D)
Then, sure, {B C D} is a subproblem. But if you have:
A LJ (B IJ C IJ D) LJ E
...then it's not, any more. Suppose E is being joined against B, for
example. You could decide to do this:
A LJ (B LJ E IJ C IJ D)
So I think this idea has crashed and burned, as Tom would say, unless
someone has an idea for resurrecting it.
...Robert