Re: GEQO vs join order restrictions

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;
  }

  /*