*_collapse_limit, geqo_threshold

*** a/doc/src/sgml/config.sgml
--- b/doc/src/sgml/config.sgml
***************
*** 2251,2313 **** SELECT * FROM parent WHERE key = 2400;
        </listitem>
       </varlistentry>
  
-      <varlistentry id="guc-from-collapse-limit" xreflabel="from_collapse_limit">
-       <term><varname>from_collapse_limit</varname> (<type>integer</type>)</term>
-       <indexterm>
-        <primary><varname>from_collapse_limit</> configuration parameter</primary>
-       </indexterm>
-       <listitem>
-        <para>
-         The planner will merge sub-queries into upper queries if the
-         resulting <literal>FROM</literal> list would have no more than
-         this many items.  Smaller values reduce planning time but might
-         yield inferior query plans.  The default is eight.
-         For more information see <xref linkend="explicit-joins">.
-        </para>
- 
-        <para>
-         Setting this value to <xref linkend="guc-geqo-threshold"> or more
-         may trigger use of the GEQO planner, resulting in nondeterministic
-         plans.  See <xref linkend="runtime-config-query-geqo">.
-        </para>
-       </listitem>
-      </varlistentry>
- 
-      <varlistentry id="guc-join-collapse-limit" xreflabel="join_collapse_limit">
-       <term><varname>join_collapse_limit</varname> (<type>integer</type>)</term>
-       <indexterm>
-        <primary><varname>join_collapse_limit</> configuration parameter</primary>
-       </indexterm>
-       <listitem>
-        <para>
-         The planner will rewrite explicit <literal>JOIN</>
-         constructs (except <literal>FULL JOIN</>s) into lists of
-         <literal>FROM</> items whenever a list of no more than this many items
-         would result.  Smaller values reduce planning time but might
-         yield inferior query plans.
-        </para>
- 
-        <para>
-         By default, this variable is set the same as
-         <varname>from_collapse_limit</varname>, which is appropriate
-         for most uses. Setting it to 1 prevents any reordering of
-         explicit <literal>JOIN</>s. Thus, the explicit join order
-         specified in the query will be the actual order in which the
-         relations are joined. The query planner does not always choose
-         the optimal join order; advanced users can elect to
-         temporarily set this variable to 1, and then specify the join
-         order they desire explicitly.
-         For more information see <xref linkend="explicit-joins">.
-        </para>
- 
-        <para>
-         Setting this value to <xref linkend="guc-geqo-threshold"> or more
-         may trigger use of the GEQO planner, resulting in nondeterministic
-         plans.  See <xref linkend="runtime-config-query-geqo">.
-        </para>
-       </listitem>
-      </varlistentry>
- 
       </variablelist>
      </sect2>
     </sect1>
--- 2251,2256 ----
*** a/doc/src/sgml/perform.sgml
--- b/doc/src/sgml/perform.sgml
***************
*** 599,606 **** WHERE tablename = 'road';
  
    <para>
     It is possible
!    to control the query planner to some extent by using the explicit <literal>JOIN</>
!    syntax.  To see why this matters, we first need some background.
    </para>
  
    <para>
--- 599,607 ----
  
    <para>
     It is possible
!    to control the query planner to some extent by using <literal>JOIN</>
!    with the <literal>FORCE</> keyword.  To see why this matters, we first need
!    some background.
    </para>
  
    <para>
***************
*** 675,681 **** SELECT * FROM a LEFT JOIN b ON (a.bid = b.id) LEFT JOIN c ON (a.cid = c.id);
    <para>
     Even though most kinds of <literal>JOIN</> don't completely constrain
     the join order, it is possible to instruct the
!    <productname>PostgreSQL</productname> query planner to treat all
     <literal>JOIN</> clauses as constraining the join order anyway.
     For example, these three queries are logically equivalent:
  <programlisting>
--- 676,682 ----
    <para>
     Even though most kinds of <literal>JOIN</> don't completely constrain
     the join order, it is possible to instruct the
!    <productname>PostgreSQL</productname> query planner to treat certain
     <literal>JOIN</> clauses as constraining the join order anyway.
     For example, these three queries are logically equivalent:
  <programlisting>
***************
*** 683,710 **** SELECT * FROM a, b, c WHERE a.id = b.id AND b.ref = c.id;
  SELECT * FROM a CROSS JOIN b CROSS JOIN c WHERE a.id = b.id AND b.ref = c.id;
  SELECT * FROM a JOIN (b JOIN c ON (b.ref = c.id)) ON (a.id = b.id);
  </programlisting>
-    But if we tell the planner to honor the <literal>JOIN</> order,
-    the second and third take less time to plan than the first.  This effect
-    is not worth worrying about for only three tables, but it can be a
-    lifesaver with many tables.
    </para>
  
    <para>
     To force the planner to follow the join order laid out by explicit
!    <literal>JOIN</>s,
!    set the <xref linkend="guc-join-collapse-limit"> run-time parameter to 1.
!    (Other possible values are discussed below.)
    </para>
  
    <para>
     You do not need to constrain the join order completely in order to
!    cut search time, because it's OK to use <literal>JOIN</> operators
!    within items of a plain <literal>FROM</> list.  For example, consider:
  <programlisting>
! SELECT * FROM a CROSS JOIN b, c, d, e WHERE ...;
  </programlisting>
!    With <varname>join_collapse_limit</> = 1, this
!    forces the planner to join A to B before joining them to other tables,
     but doesn't constrain its choices otherwise.  In this example, the
     number of possible join orders is reduced by a factor of 5.
    </para>
--- 684,710 ----
  SELECT * FROM a CROSS JOIN b CROSS JOIN c WHERE a.id = b.id AND b.ref = c.id;
  SELECT * FROM a JOIN (b JOIN c ON (b.ref = c.id)) ON (a.id = b.id);
  </programlisting>
    </para>
  
    <para>
     To force the planner to follow the join order laid out by explicit
!    <literal>JOIN</>s, use the <literal>FORCE</> keyword, like this:
! <programlisting>
! SELECT * FROM a INNER FORCE JOIN (b INNER FORCE JOIN c ON (b.ref = c.id)) ON (a.id = b.id);
! </programlisting>
!    Because there is only one possible join order, this query will take less
!    time to plan.  This effect is not worth worrying about for only three
!    tables, but it can be a lifesaver with many tables.
    </para>
  
    <para>
     You do not need to constrain the join order completely in order to
!    cut search time; <literal>FORCE</> can be specified for just some of
!    the joins in a given query.  For example, consider:
  <programlisting>
! SELECT * FROM a INNER FORCE JOIN b ON ..., c, d, e WHERE ...;
  </programlisting>
!    This forces the planner to join A to B before joining them to other tables,
     but doesn't constrain its choices otherwise.  In this example, the
     number of possible join orders is reduced by a factor of 5.
    </para>
***************
*** 713,719 **** SELECT * FROM a CROSS JOIN b, c, d, e WHERE ...;
     Constraining the planner's search in this way is a useful technique
     both for reducing planning time and for directing the planner to a
     good query plan.  If the planner chooses a bad join order by default,
!    you can force it to choose a better order via <literal>JOIN</> syntax
     &mdash; assuming that you know of a better order, that is.  Experimentation
     is recommended.
    </para>
--- 713,719 ----
     Constraining the planner's search in this way is a useful technique
     both for reducing planning time and for directing the planner to a
     good query plan.  If the planner chooses a bad join order by default,
!    you can force it to choose a better order using <literal>FORCE</>
     &mdash; assuming that you know of a better order, that is.  Experimentation
     is recommended.
    </para>
***************
*** 729,736 **** WHERE somethingelse;
  </programlisting>
     This situation might arise from use of a view that contains a join;
     the view's <literal>SELECT</> rule will be inserted in place of the view
!    reference, yielding a query much like the above.  Normally, the planner
!    will try to collapse the subquery into the parent, yielding:
  <programlisting>
  SELECT * FROM x, y, a, b, c WHERE something AND somethingelse;
  </programlisting>
--- 729,736 ----
  </programlisting>
     This situation might arise from use of a view that contains a join;
     the view's <literal>SELECT</> rule will be inserted in place of the view
!    reference, yielding a query much like the above.  The planner
!    will always try to collapse the subquery into the parent, yielding:
  <programlisting>
  SELECT * FROM x, y, a, b, c WHERE something AND somethingelse;
  </programlisting>
***************
*** 741,765 **** SELECT * FROM x, y, a, b, c WHERE something AND somethingelse;
     we have increased the planning time; here, we have a five-way join
     problem replacing two separate three-way join problems.  Because of the
     exponential growth of the number of possibilities, this makes a big
!    difference.  The planner tries to avoid getting stuck in huge join search
!    problems by not collapsing a subquery if more than <varname>from_collapse_limit</>
!    <literal>FROM</> items would result in the parent
!    query.  You can trade off planning time against quality of plan by
!    adjusting this run-time parameter up or down.
!   </para>
! 
!   <para>
!    <xref linkend="guc-from-collapse-limit"> and <xref
!    linkend="guc-join-collapse-limit">
!    are similarly named because they do almost the same thing: one controls
!    when the planner will <quote>flatten out</> subqueries, and the
!    other controls when it will flatten out explicit joins.  Typically
!    you would either set <varname>join_collapse_limit</> equal to
!    <varname>from_collapse_limit</> (so that explicit joins and subqueries
!    act similarly) or set <varname>join_collapse_limit</> to 1 (if you want
!    to control join order with explicit joins).  But you might set them
!    differently if you are trying to fine-tune the trade-off between planning
!    time and run time.
    </para>
   </sect1>
  
--- 741,748 ----
     we have increased the planning time; here, we have a five-way join
     problem replacing two separate three-way join problems.  Because of the
     exponential growth of the number of possibilities, this makes a big
!    difference.  For large join problems, you may need to constrain the join
!    order or use <xref linkend="guc-geqo-threshold">.
    </para>
   </sect1>
  
*** a/doc/src/sgml/ref/select.sgml
--- b/doc/src/sgml/ref/select.sgml
***************
*** 357,372 **** TABLE { [ ONLY ] <replaceable class="parameter">table_name</replaceable> [ * ] |
          One of
          <itemizedlist>
           <listitem>
!           <para><literal>[ INNER ] JOIN</literal></para>
           </listitem>
           <listitem>
!           <para><literal>LEFT [ OUTER ] JOIN</literal></para>
           </listitem>
           <listitem>
!           <para><literal>RIGHT [ OUTER ] JOIN</literal></para>
           </listitem>
           <listitem>
!           <para><literal>FULL [ OUTER ] JOIN</literal></para>
           </listitem>
           <listitem>
            <para><literal>CROSS JOIN</literal></para>
--- 357,372 ----
          One of
          <itemizedlist>
           <listitem>
!           <para><literal>[ INNER [ FORCE ] ] JOIN</literal></para>
           </listitem>
           <listitem>
!           <para><literal>LEFT [ OUTER ] [ FORCE ] JOIN</literal></para>
           </listitem>
           <listitem>
!           <para><literal>RIGHT [ OUTER ] [ FORCE ] JOIN</literal></para>
           </listitem>
           <listitem>
!           <para><literal>FULL [ OUTER ] [ FORCE ] JOIN</literal></para>
           </listitem>
           <listitem>
            <para><literal>CROSS JOIN</literal></para>
***************
*** 389,395 **** TABLE { [ ONLY ] <replaceable class="parameter">table_name</replaceable> [ * ] |
          determine the order of nesting.  In the absence of parentheses,
          <literal>JOIN</literal>s nest left-to-right.  In any case
          <literal>JOIN</literal> binds more tightly than the commas
!         separating <literal>FROM</> items.
         </para>
  
         <para>
--- 389,397 ----
          determine the order of nesting.  In the absence of parentheses,
          <literal>JOIN</literal>s nest left-to-right.  In any case
          <literal>JOIN</literal> binds more tightly than the commas
!         separating <literal>FROM</> items.  The keyword
!         <literal>FORCE</literal> constrains the join order
!         (see <xref linkend="explicit-joins">).
         </para>
  
         <para>
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
***************
*** 1542,1547 **** _copyJoinExpr(JoinExpr *from)
--- 1542,1548 ----
  
  	COPY_SCALAR_FIELD(jointype);
  	COPY_SCALAR_FIELD(isNatural);
+ 	COPY_SCALAR_FIELD(isForce);
  	COPY_NODE_FIELD(larg);
  	COPY_NODE_FIELD(rarg);
  	COPY_NODE_FIELD(using);
*** a/src/backend/nodes/equalfuncs.c
--- b/src/backend/nodes/equalfuncs.c
***************
*** 702,707 **** _equalJoinExpr(JoinExpr *a, JoinExpr *b)
--- 702,708 ----
  {
  	COMPARE_SCALAR_FIELD(jointype);
  	COMPARE_SCALAR_FIELD(isNatural);
+ 	COMPARE_SCALAR_FIELD(isForce);
  	COMPARE_NODE_FIELD(larg);
  	COMPARE_NODE_FIELD(rarg);
  	COMPARE_NODE_FIELD(using);
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
***************
*** 1257,1262 **** _outJoinExpr(StringInfo str, JoinExpr *node)
--- 1257,1263 ----
  
  	WRITE_ENUM_FIELD(jointype, JoinType);
  	WRITE_BOOL_FIELD(isNatural);
+ 	WRITE_BOOL_FIELD(isForce);
  	WRITE_NODE_FIELD(larg);
  	WRITE_NODE_FIELD(rarg);
  	WRITE_NODE_FIELD(using);
*** a/src/backend/nodes/readfuncs.c
--- b/src/backend/nodes/readfuncs.c
***************
*** 1068,1073 **** _readJoinExpr(void)
--- 1068,1074 ----
  
  	READ_ENUM_FIELD(jointype, JoinType);
  	READ_BOOL_FIELD(isNatural);
+ 	READ_BOOL_FIELD(isForce);
  	READ_NODE_FIELD(larg);
  	READ_NODE_FIELD(rarg);
  	READ_NODE_FIELD(using);
*** a/src/backend/optimizer/README
--- b/src/backend/optimizer/README
***************
*** 90,99 **** single join relation.
  2) Normally, any explicit JOIN clauses are "flattened" so that we just
  have a list of relations to join.  However, FULL OUTER JOIN clauses are
  never flattened, and other kinds of JOIN might not be either, if the
! flattening process is stopped by join_collapse_limit or from_collapse_limit
! restrictions.  Therefore, we end up with a planning problem that contains
! lists of relations to be joined in any order, where any individual item
! might be a sub-list that has to be joined together before we can consider
  joining it to its siblings.  We process these sub-problems recursively,
  bottom up.  Note that the join list structure constrains the possible join
  orders, but it doesn't constrain the join implementation method at each
--- 90,98 ----
  2) Normally, any explicit JOIN clauses are "flattened" so that we just
  have a list of relations to join.  However, FULL OUTER JOIN clauses are
  never flattened, and other kinds of JOIN might not be either, if the
! FORCE keyword is used.  Therefore, we end up with a planning problem that
! contains lists of relations to be joined in any order, where any individual
! item might be a sub-list that has to be joined together before we can consider
  joining it to its siblings.  We process these sub-problems recursively,
  bottom up.  Note that the join list structure constrains the possible join
  orders, but it doesn't constrain the join implementation method at each
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
***************
*** 32,43 ****
  #include "utils/lsyscache.h"
  #include "utils/syscache.h"
  
- 
- /* These parameters are set by GUC */
- int			from_collapse_limit;
- int			join_collapse_limit;
- 
- 
  static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
  					bool below_outer_join,
  					Relids *qualscope, Relids *inner_join_rels);
--- 32,37 ----
***************
*** 215,221 **** add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
   * (note that legal orders may be constrained by SpecialJoinInfo nodes).
   * A sub-joinlist represents a subproblem to be planned separately. Currently
   * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
!  * subproblems is stopped by join_collapse_limit or from_collapse_limit.
   *
   * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
   * be evaluated at the lowest level where all the variables it mentions are
--- 209,215 ----
   * (note that legal orders may be constrained by SpecialJoinInfo nodes).
   * A sub-joinlist represents a subproblem to be planned separately. Currently
   * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
!  * subproblems is stopped by the FORCE keyword.
   *
   * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
   * be evaluated at the lowest level where all the variables it mentions are
***************
*** 284,320 **** deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
  	else if (IsA(jtnode, FromExpr))
  	{
  		FromExpr   *f = (FromExpr *) jtnode;
- 		int			remaining;
  		ListCell   *l;
  
  		/*
  		 * First, recurse to handle child joins.  We collapse subproblems into
! 		 * a single joinlist whenever the resulting joinlist wouldn't exceed
! 		 * from_collapse_limit members.  Also, always collapse one-element
! 		 * subproblems, since that won't lengthen the joinlist anyway.
  		 */
  		*qualscope = NULL;
  		*inner_join_rels = NULL;
  		joinlist = NIL;
- 		remaining = list_length(f->fromlist);
  		foreach(l, f->fromlist)
  		{
  			Relids		sub_qualscope;
  			List	   *sub_joinlist;
- 			int			sub_members;
  
  			sub_joinlist = deconstruct_recurse(root, lfirst(l),
  											   below_outer_join,
  											   &sub_qualscope,
  											   inner_join_rels);
  			*qualscope = bms_add_members(*qualscope, sub_qualscope);
! 			sub_members = list_length(sub_joinlist);
! 			remaining--;
! 			if (sub_members <= 1 ||
! 				list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
! 				joinlist = list_concat(joinlist, sub_joinlist);
! 			else
! 				joinlist = lappend(joinlist, sub_joinlist);
  		}
  
  		/*
--- 278,303 ----
  	else if (IsA(jtnode, FromExpr))
  	{
  		FromExpr   *f = (FromExpr *) jtnode;
  		ListCell   *l;
  
  		/*
  		 * First, recurse to handle child joins.  We collapse subproblems into
! 		 * a single joinlist.
  		 */
  		*qualscope = NULL;
  		*inner_join_rels = NULL;
  		joinlist = NIL;
  		foreach(l, f->fromlist)
  		{
  			Relids		sub_qualscope;
  			List	   *sub_joinlist;
  
  			sub_joinlist = deconstruct_recurse(root, lfirst(l),
  											   below_outer_join,
  											   &sub_qualscope,
  											   inner_join_rels);
  			*qualscope = bms_add_members(*qualscope, sub_qualscope);
! 			joinlist = list_concat(joinlist, sub_joinlist);
  		}
  
  		/*
***************
*** 469,505 **** deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
  
  		/*
  		 * Finally, compute the output joinlist.  We fold subproblems together
! 		 * except at a FULL JOIN or where join_collapse_limit would be
! 		 * exceeded.
  		 */
! 		if (j->jointype == JOIN_FULL)
  		{
  			/* force the join order exactly at this node */
  			joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
  		}
! 		else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
! 				 join_collapse_limit)
  		{
  			/* OK to combine subproblems */
  			joinlist = list_concat(leftjoinlist, rightjoinlist);
  		}
- 		else
- 		{
- 			/* can't combine, but needn't force join order above here */
- 			Node	   *leftpart,
- 					   *rightpart;
- 
- 			/* avoid creating useless 1-element sublists */
- 			if (list_length(leftjoinlist) == 1)
- 				leftpart = (Node *) linitial(leftjoinlist);
- 			else
- 				leftpart = (Node *) leftjoinlist;
- 			if (list_length(rightjoinlist) == 1)
- 				rightpart = (Node *) linitial(rightjoinlist);
- 			else
- 				rightpart = (Node *) rightjoinlist;
- 			joinlist = list_make2(leftpart, rightpart);
- 		}
  	}
  	else
  	{
--- 452,469 ----
  
  		/*
  		 * Finally, compute the output joinlist.  We fold subproblems together
! 		 * except at a FULL JOIN or where FORCE has been specified.
  		 */
! 		if (j->jointype == JOIN_FULL || j->isForce)
  		{
  			/* force the join order exactly at this node */
  			joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
  		}
! 		else
  		{
  			/* OK to combine subproblems */
  			joinlist = list_concat(leftjoinlist, rightjoinlist);
  		}
  	}
  	else
  	{
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
***************
*** 1087,1092 **** convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
--- 1087,1093 ----
  	result = makeNode(JoinExpr);
  	result->jointype = JOIN_SEMI;
  	result->isNatural = false;
+ 	result->isForce = false;
  	result->larg = NULL;		/* caller must fill this in */
  	result->rarg = (Node *) rtr;
  	result->using = NIL;
***************
*** 1227,1232 **** convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
--- 1228,1234 ----
  	result = makeNode(JoinExpr);
  	result->jointype = under_not ? JOIN_ANTI : JOIN_SEMI;
  	result->isNatural = false;
+ 	result->isForce = false;
  	result->larg = NULL;		/* caller must fill this in */
  	/* flatten out the FromExpr node if it's useless */
  	if (list_length(subselect->jointree->fromlist) == 1)
*** a/src/backend/parser/gram.y
--- b/src/backend/parser/gram.y
***************
*** 7437,7459 **** joined_table:
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = JOIN_INNER;
  					n->isNatural = FALSE;
  					n->larg = $1;
  					n->rarg = $4;
  					n->using = NIL;
  					n->quals = NULL;
  					$$ = n;
  				}
! 			| table_ref join_type JOIN table_ref join_qual
  				{
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = $2;
  					n->isNatural = FALSE;
  					n->larg = $1;
! 					n->rarg = $4;
! 					if ($5 != NULL && IsA($5, List))
! 						n->using = (List *) $5; /* USING clause */
  					else
! 						n->quals = $5; /* ON clause */
  					$$ = n;
  				}
  			| table_ref JOIN table_ref join_qual
--- 7437,7461 ----
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = JOIN_INNER;
  					n->isNatural = FALSE;
+ 					n->isForce = FALSE;
  					n->larg = $1;
  					n->rarg = $4;
  					n->using = NIL;
  					n->quals = NULL;
  					$$ = n;
  				}
! 			| table_ref join_type opt_force JOIN table_ref join_qual
  				{
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = $2;
  					n->isNatural = FALSE;
+ 					n->isForce = $3;
  					n->larg = $1;
! 					n->rarg = $5;
! 					if ($6 != NULL && IsA($6, List))
! 						n->using = (List *) $6; /* USING clause */
  					else
! 						n->quals = $6; /* ON clause */
  					$$ = n;
  				}
  			| table_ref JOIN table_ref join_qual
***************
*** 7462,7467 **** joined_table:
--- 7464,7470 ----
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = JOIN_INNER;
  					n->isNatural = FALSE;
+ 					n->isForce = FALSE;
  					n->larg = $1;
  					n->rarg = $3;
  					if ($4 != NULL && IsA($4, List))
***************
*** 7475,7480 **** joined_table:
--- 7478,7484 ----
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = $3;
  					n->isNatural = TRUE;
+ 					n->isForce = FALSE;
  					n->larg = $1;
  					n->rarg = $5;
  					n->using = NIL; /* figure out which columns later... */
***************
*** 7487,7492 **** joined_table:
--- 7491,7497 ----
  					JoinExpr *n = makeNode(JoinExpr);
  					n->jointype = JOIN_INNER;
  					n->isNatural = TRUE;
+ 					n->isForce = FALSE;
  					n->larg = $1;
  					n->rarg = $4;
  					n->using = NIL; /* figure out which columns later... */
*** a/src/backend/utils/adt/ruleutils.c
--- b/src/backend/utils/adt/ruleutils.c
***************
*** 5824,5829 **** get_from_clause_item(Node *jtnode, Query *query, deparse_context *context)
--- 5824,5831 ----
  	{
  		JoinExpr   *j = (JoinExpr *) jtnode;
  		bool		need_paren_on_right;
+ 		char		buffer[64];
+ 		int			indentPlus;
  
  		need_paren_on_right = PRETTY_PAREN(context) &&
  			!IsA(j->rarg, RangeTblRef) &&
***************
*** 5834,5905 **** get_from_clause_item(Node *jtnode, Query *query, deparse_context *context)
  
  		get_from_clause_item(j->larg, query, context);
  
  		if (j->isNatural)
  		{
  			if (!PRETTY_INDENT(context))
  				appendStringInfoChar(buf, ' ');
! 			switch (j->jointype)
! 			{
! 				case JOIN_INNER:
! 					appendContextKeyword(context, "NATURAL JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 0);
! 					break;
! 				case JOIN_LEFT:
! 					appendContextKeyword(context, "NATURAL LEFT JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 0);
! 					break;
! 				case JOIN_FULL:
! 					appendContextKeyword(context, "NATURAL FULL JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 0);
! 					break;
! 				case JOIN_RIGHT:
! 					appendContextKeyword(context, "NATURAL RIGHT JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 0);
! 					break;
! 				default:
! 					elog(ERROR, "unrecognized join type: %d",
! 						 (int) j->jointype);
! 			}
  		}
  		else
  		{
! 			switch (j->jointype)
! 			{
! 				case JOIN_INNER:
! 					if (j->quals)
! 						appendContextKeyword(context, " JOIN ",
! 											 -PRETTYINDENT_JOIN,
! 											 PRETTYINDENT_JOIN, 2);
! 					else
! 						appendContextKeyword(context, " CROSS JOIN ",
! 											 -PRETTYINDENT_JOIN,
! 											 PRETTYINDENT_JOIN, 1);
! 					break;
! 				case JOIN_LEFT:
! 					appendContextKeyword(context, " LEFT JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 2);
! 					break;
! 				case JOIN_FULL:
! 					appendContextKeyword(context, " FULL JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 2);
! 					break;
! 				case JOIN_RIGHT:
! 					appendContextKeyword(context, " RIGHT JOIN ",
! 										 -PRETTYINDENT_JOIN,
! 										 PRETTYINDENT_JOIN, 2);
! 					break;
! 				default:
! 					elog(ERROR, "unrecognized join type: %d",
! 						 (int) j->jointype);
! 			}
  		}
  
  		if (need_paren_on_right)
  			appendStringInfoChar(buf, '(');
  		get_from_clause_item(j->rarg, query, context);
--- 5836,5891 ----
  
  		get_from_clause_item(j->larg, query, context);
  
+ 		buffer[0] = '\0';
  		if (j->isNatural)
  		{
  			if (!PRETTY_INDENT(context))
  				appendStringInfoChar(buf, ' ');
! 			strcat(buffer, "NATURAL ");
! 			indentPlus = 0;
  		}
  		else
  		{
! 			strcat(buffer, " ");
! 			indentPlus = 2;
! 		}
! 
! 		switch (j->jointype)
! 		{
! 			case JOIN_INNER:
! 				if (!j->quals && !j->isNatural)
! 				{
! 					strcat(buffer, "CROSS ");
! 					indentPlus = 1;
! 				}
! 				/*
! 				 * INNER is normally just decoration, but it's required when
! 				 * we also need to emit FORCE.
! 				 */
! 				if (j->isForce)
! 					strcat(buffer, "INNER ");
! 				break;
! 			case JOIN_LEFT:
! 				strcat(buffer, "LEFT ");
! 				break;
! 			case JOIN_FULL:
! 				strcat(buffer, "FULL ");
! 				break;
! 			case JOIN_RIGHT:
! 				strcat(buffer, "RIGHT ");
! 				break;
! 			default:
! 				elog(ERROR, "unrecognized join type: %d", (int) j->jointype);
  		}
  
+ 		if (j->isForce)
+ 			strcat(buffer, "FORCE JOIN ");
+ 		else
+ 			strcat(buffer, "JOIN ");
+ 
+ 		appendContextKeyword(context, buffer, -PRETTYINDENT_JOIN,
+ 							 PRETTYINDENT_JOIN, indentPlus);
+ 
  		if (need_paren_on_right)
  			appendStringInfoChar(buf, '(');
  		get_from_clause_item(j->rarg, query, context);
*** a/src/backend/utils/misc/guc.c
--- b/src/backend/utils/misc/guc.c
***************
*** 1259,1286 **** static struct config_int ConfigureNamesInt[] =
  		100, 1, 10000, NULL, NULL
  	},
  	{
- 		{"from_collapse_limit", PGC_USERSET, QUERY_TUNING_OTHER,
- 			gettext_noop("Sets the FROM-list size beyond which subqueries "
- 						 "are not collapsed."),
- 			gettext_noop("The planner will merge subqueries into upper "
- 				"queries if the resulting FROM list would have no more than "
- 						 "this many items.")
- 		},
- 		&from_collapse_limit,
- 		8, 1, INT_MAX, NULL, NULL
- 	},
- 	{
- 		{"join_collapse_limit", PGC_USERSET, QUERY_TUNING_OTHER,
- 			gettext_noop("Sets the FROM-list size beyond which JOIN "
- 						 "constructs are not flattened."),
- 			gettext_noop("The planner will flatten explicit JOIN "
- 						 "constructs into lists of FROM items whenever a "
- 						 "list of no more than this many items would result.")
- 		},
- 		&join_collapse_limit,
- 		8, 1, INT_MAX, NULL, NULL
- 	},
- 	{
  		{"geqo_threshold", PGC_USERSET, QUERY_TUNING_GEQO,
  			gettext_noop("Sets the threshold of FROM items beyond which GEQO is used."),
  			NULL
--- 1259,1264 ----
*** a/src/backend/utils/misc/postgresql.conf.sample
--- b/src/backend/utils/misc/postgresql.conf.sample
***************
*** 219,227 ****
  #default_statistics_target = 100	# range 1-10000
  #constraint_exclusion = partition	# on, off, or partition
  #cursor_tuple_fraction = 0.1		# range 0.0-1.0
- #from_collapse_limit = 8
- #join_collapse_limit = 8		# 1 disables collapsing of explicit 
- 					# JOIN clauses
  
  
  #------------------------------------------------------------------------------
--- 219,224 ----
*** a/src/include/nodes/primnodes.h
--- b/src/include/nodes/primnodes.h
***************
*** 1150,1155 **** typedef struct JoinExpr
--- 1150,1156 ----
  	NodeTag		type;
  	JoinType	jointype;		/* type of join */
  	bool		isNatural;		/* Natural join? Will need to shape table */
+ 	bool		isForce;		/* Join order forced? */
  	Node	   *larg;			/* left subtree */
  	Node	   *rarg;			/* right subtree */
  	List	   *using;			/* USING clause, if any (list of String) */
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
***************
*** 79,87 **** extern bool is_projection_capable_plan(Plan *plan);
  /*
   * prototypes for plan/initsplan.c
   */
- extern int	from_collapse_limit;
- extern int	join_collapse_limit;
- 
  extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
  extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
  extern void add_vars_to_targetlist(PlannerInfo *root, List *vars,
--- 79,84 ----

*** a/doc/src/sgml/config.sgml
--- b/doc/src/sgml/config.sgml
***************
*** 1798,1803 **** archive_command = 'copy "%p" "C:\\server\\archivedir\\%f"'  # Windows
--- 1798,1823 ----
        </listitem>
       </varlistentry>
  
+      <varlistentry id="guc-enable-join-ordering" xreflabel="enable_join_ordering">
+       <term><varname>enable_join_ordering</varname> (<type>boolean</type>)</term>
+       <indexterm>
+        <primary><varname>enable_join_ordering</> configuration parameter</primary>
+       </indexterm>
+       <listitem>
+        <para>
+         Allows the planner to reorder joins, which is generally appropriate
+         for most uses. Setting it to false prevents any reordering of
+         explicit <literal>JOIN</>s. Thus, the explicit join order
+         specified in the query will be the actual order in which the
+         relations are joined. The query planner does not always choose
+         the optimal join order; advanced users can elect to
+         temporarily set this variable to false, and then specify the join
+         order they desire explicitly.
+         For more information see <xref linkend="explicit-joins">.
+        </para>
+       </listitem>
+      </varlistentry>
+ 
       <varlistentry id="guc-enable-mergejoin" xreflabel="enable_mergejoin">
        <term><varname>enable_mergejoin</varname> (<type>boolean</type>)</term>
        <indexterm>
***************
*** 2251,2313 **** SELECT * FROM parent WHERE key = 2400;
        </listitem>
       </varlistentry>
  
-      <varlistentry id="guc-from-collapse-limit" xreflabel="from_collapse_limit">
-       <term><varname>from_collapse_limit</varname> (<type>integer</type>)</term>
-       <indexterm>
-        <primary><varname>from_collapse_limit</> configuration parameter</primary>
-       </indexterm>
-       <listitem>
-        <para>
-         The planner will merge sub-queries into upper queries if the
-         resulting <literal>FROM</literal> list would have no more than
-         this many items.  Smaller values reduce planning time but might
-         yield inferior query plans.  The default is eight.
-         For more information see <xref linkend="explicit-joins">.
-        </para>
- 
-        <para>
-         Setting this value to <xref linkend="guc-geqo-threshold"> or more
-         may trigger use of the GEQO planner, resulting in nondeterministic
-         plans.  See <xref linkend="runtime-config-query-geqo">.
-        </para>
-       </listitem>
-      </varlistentry>
- 
-      <varlistentry id="guc-join-collapse-limit" xreflabel="join_collapse_limit">
-       <term><varname>join_collapse_limit</varname> (<type>integer</type>)</term>
-       <indexterm>
-        <primary><varname>join_collapse_limit</> configuration parameter</primary>
-       </indexterm>
-       <listitem>
-        <para>
-         The planner will rewrite explicit <literal>JOIN</>
-         constructs (except <literal>FULL JOIN</>s) into lists of
-         <literal>FROM</> items whenever a list of no more than this many items
-         would result.  Smaller values reduce planning time but might
-         yield inferior query plans.
-        </para>
- 
-        <para>
-         By default, this variable is set the same as
-         <varname>from_collapse_limit</varname>, which is appropriate
-         for most uses. Setting it to 1 prevents any reordering of
-         explicit <literal>JOIN</>s. Thus, the explicit join order
-         specified in the query will be the actual order in which the
-         relations are joined. The query planner does not always choose
-         the optimal join order; advanced users can elect to
-         temporarily set this variable to 1, and then specify the join
-         order they desire explicitly.
-         For more information see <xref linkend="explicit-joins">.
-        </para>
- 
-        <para>
-         Setting this value to <xref linkend="guc-geqo-threshold"> or more
-         may trigger use of the GEQO planner, resulting in nondeterministic
-         plans.  See <xref linkend="runtime-config-query-geqo">.
-        </para>
-       </listitem>
-      </varlistentry>
- 
       </variablelist>
      </sect2>
     </sect1>
--- 2271,2276 ----
*** a/doc/src/sgml/perform.sgml
--- b/doc/src/sgml/perform.sgml
***************
*** 692,699 **** SELECT * FROM a JOIN (b JOIN c ON (b.ref = c.id)) ON (a.id = b.id);
    <para>
     To force the planner to follow the join order laid out by explicit
     <literal>JOIN</>s,
!    set the <xref linkend="guc-join-collapse-limit"> run-time parameter to 1.
!    (Other possible values are discussed below.)
    </para>
  
    <para>
--- 692,699 ----
    <para>
     To force the planner to follow the join order laid out by explicit
     <literal>JOIN</>s,
!    set the <xref linkend="guc-enable-join-ordering"> run-time parameter to
!    false.
    </para>
  
    <para>
***************
*** 703,710 **** SELECT * FROM a JOIN (b JOIN c ON (b.ref = c.id)) ON (a.id = b.id);
  <programlisting>
  SELECT * FROM a CROSS JOIN b, c, d, e WHERE ...;
  </programlisting>
!    With <varname>join_collapse_limit</> = 1, this
!    forces the planner to join A to B before joining them to other tables,
     but doesn't constrain its choices otherwise.  In this example, the
     number of possible join orders is reduced by a factor of 5.
    </para>
--- 703,709 ----
  <programlisting>
  SELECT * FROM a CROSS JOIN b, c, d, e WHERE ...;
  </programlisting>
!    This forces the planner to join A to B before joining them to other tables,
     but doesn't constrain its choices otherwise.  In this example, the
     number of possible join orders is reduced by a factor of 5.
    </para>
***************
*** 741,765 **** SELECT * FROM x, y, a, b, c WHERE something AND somethingelse;
     we have increased the planning time; here, we have a five-way join
     problem replacing two separate three-way join problems.  Because of the
     exponential growth of the number of possibilities, this makes a big
!    difference.  The planner tries to avoid getting stuck in huge join search
!    problems by not collapsing a subquery if more than <varname>from_collapse_limit</>
!    <literal>FROM</> items would result in the parent
!    query.  You can trade off planning time against quality of plan by
!    adjusting this run-time parameter up or down.
!   </para>
! 
!   <para>
!    <xref linkend="guc-from-collapse-limit"> and <xref
!    linkend="guc-join-collapse-limit">
!    are similarly named because they do almost the same thing: one controls
!    when the planner will <quote>flatten out</> subqueries, and the
!    other controls when it will flatten out explicit joins.  Typically
!    you would either set <varname>join_collapse_limit</> equal to
!    <varname>from_collapse_limit</> (so that explicit joins and subqueries
!    act similarly) or set <varname>join_collapse_limit</> to 1 (if you want
!    to control join order with explicit joins).  But you might set them
!    differently if you are trying to fine-tune the trade-off between planning
!    time and run time.
    </para>
   </sect1>
  
--- 740,746 ----
     we have increased the planning time; here, we have a five-way join
     problem replacing two separate three-way join problems.  Because of the
     exponential growth of the number of possibilities, this makes a big
!    difference.
    </para>
   </sect1>
  
*** a/src/backend/optimizer/README
--- b/src/backend/optimizer/README
***************
*** 89,106 **** single join relation.
  
  2) Normally, any explicit JOIN clauses are "flattened" so that we just
  have a list of relations to join.  However, FULL OUTER JOIN clauses are
! never flattened, and other kinds of JOIN might not be either, if the
! flattening process is stopped by join_collapse_limit or from_collapse_limit
! restrictions.  Therefore, we end up with a planning problem that contains
! lists of relations to be joined in any order, where any individual item
! might be a sub-list that has to be joined together before we can consider
! joining it to its siblings.  We process these sub-problems recursively,
! bottom up.  Note that the join list structure constrains the possible join
! orders, but it doesn't constrain the join implementation method at each
! join (nestloop, merge, hash), nor does it say which rel is considered outer
! or inner at each join.  We consider all these possibilities in building
! Paths. We generate a Path for each feasible join method, and select the
! cheapest Path.
  
  For each planning problem, therefore, we will have a list of relations
  that are either base rels or joinrels constructed per sub-join-lists.
--- 89,105 ----
  
  2) Normally, any explicit JOIN clauses are "flattened" so that we just
  have a list of relations to join.  However, FULL OUTER JOIN clauses are
! never flattened and other kinds of JOIN might not be either, if
! enable_join_ordering is set to false.  Therefore, we end up with a planning
! problem that contains lists of relations to be joined in any order, where
! any individual item might be a sub-list that has to be joined together
! before we can consider joining it to its siblings.  We process these
! sub-problems recursively, bottom up.  Note that the join list structure
! constrains the possible join orders, but it doesn't constrain the join
! implementation method at each join (nestloop, merge, hash), nor does it
! say which rel is considered outer or inner at each join.  We consider
! all these possibilities in building Paths. We generate a Path for each
! feasible join method, and select the cheapest Path.
  
  For each planning problem, therefore, we will have a list of relations
  that are either base rels or joinrels constructed per sub-join-lists.
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
***************
*** 33,41 ****
  #include "utils/syscache.h"
  
  
! /* These parameters are set by GUC */
! int			from_collapse_limit;
! int			join_collapse_limit;
  
  
  static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
--- 33,40 ----
  #include "utils/syscache.h"
  
  
! /* This parameter is set by GUC */
! bool		enable_join_ordering;
  
  
  static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
***************
*** 214,221 **** add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
   * joinlist must be joined in an order to be determined by make_one_rel()
   * (note that legal orders may be constrained by SpecialJoinInfo nodes).
   * A sub-joinlist represents a subproblem to be planned separately. Currently
!  * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
!  * subproblems is stopped by join_collapse_limit or from_collapse_limit.
   *
   * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
   * be evaluated at the lowest level where all the variables it mentions are
--- 213,220 ----
   * joinlist must be joined in an order to be determined by make_one_rel()
   * (note that legal orders may be constrained by SpecialJoinInfo nodes).
   * A sub-joinlist represents a subproblem to be planned separately. Currently
!  * sub-joinlists arise only from FULL OUTER JOIN or when enable_join_ordering
!  * is set to false.
   *
   * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
   * be evaluated at the lowest level where all the variables it mentions are
***************
*** 284,302 **** deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
  	else if (IsA(jtnode, FromExpr))
  	{
  		FromExpr   *f = (FromExpr *) jtnode;
- 		int			remaining;
  		ListCell   *l;
  
  		/*
  		 * First, recurse to handle child joins.  We collapse subproblems into
! 		 * a single joinlist whenever the resulting joinlist wouldn't exceed
! 		 * from_collapse_limit members.  Also, always collapse one-element
! 		 * subproblems, since that won't lengthen the joinlist anyway.
  		 */
  		*qualscope = NULL;
  		*inner_join_rels = NULL;
  		joinlist = NIL;
- 		remaining = list_length(f->fromlist);
  		foreach(l, f->fromlist)
  		{
  			Relids		sub_qualscope;
--- 283,297 ----
  	else if (IsA(jtnode, FromExpr))
  	{
  		FromExpr   *f = (FromExpr *) jtnode;
  		ListCell   *l;
  
  		/*
  		 * First, recurse to handle child joins.  We collapse subproblems into
! 		 * a single joinlist.
  		 */
  		*qualscope = NULL;
  		*inner_join_rels = NULL;
  		joinlist = NIL;
  		foreach(l, f->fromlist)
  		{
  			Relids		sub_qualscope;
***************
*** 309,320 **** deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
  											   inner_join_rels);
  			*qualscope = bms_add_members(*qualscope, sub_qualscope);
  			sub_members = list_length(sub_joinlist);
! 			remaining--;
! 			if (sub_members <= 1 ||
! 				list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
! 				joinlist = list_concat(joinlist, sub_joinlist);
! 			else
! 				joinlist = lappend(joinlist, sub_joinlist);
  		}
  
  		/*
--- 304,310 ----
  											   inner_join_rels);
  			*qualscope = bms_add_members(*qualscope, sub_qualscope);
  			sub_members = list_length(sub_joinlist);
! 			joinlist = list_concat(joinlist, sub_joinlist);
  		}
  
  		/*
***************
*** 469,484 **** deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
  
  		/*
  		 * Finally, compute the output joinlist.  We fold subproblems together
! 		 * except at a FULL JOIN or where join_collapse_limit would be
! 		 * exceeded.
  		 */
  		if (j->jointype == JOIN_FULL)
  		{
  			/* force the join order exactly at this node */
  			joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
  		}
! 		else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
! 				 join_collapse_limit)
  		{
  			/* OK to combine subproblems */
  			joinlist = list_concat(leftjoinlist, rightjoinlist);
--- 459,472 ----
  
  		/*
  		 * Finally, compute the output joinlist.  We fold subproblems together
! 		 * except at a FULL JOIN or when enable_join_ordering is false.
  		 */
  		if (j->jointype == JOIN_FULL)
  		{
  			/* force the join order exactly at this node */
  			joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
  		}
! 		else if (enable_join_ordering)
  		{
  			/* OK to combine subproblems */
  			joinlist = list_concat(leftjoinlist, rightjoinlist);
*** a/src/backend/utils/misc/guc.c
--- b/src/backend/utils/misc/guc.c
***************
*** 656,661 **** static struct config_bool ConfigureNamesBool[] =
--- 656,669 ----
  		true, NULL, NULL
  	},
  	{
+ 		{"enable_join_ordering", PGC_USERSET, QUERY_TUNING_METHOD,
+ 			gettext_noop("Enables the planner to reorder explicit joins."),
+ 			NULL
+ 		},
+ 		&enable_join_ordering,
+ 		true, NULL, NULL
+ 	},
+ 	{
  		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
  			gettext_noop("Enables genetic query optimization."),
  			gettext_noop("This algorithm attempts to do planning without "
***************
*** 1259,1286 **** static struct config_int ConfigureNamesInt[] =
  		100, 1, 10000, NULL, NULL
  	},
  	{
- 		{"from_collapse_limit", PGC_USERSET, QUERY_TUNING_OTHER,
- 			gettext_noop("Sets the FROM-list size beyond which subqueries "
- 						 "are not collapsed."),
- 			gettext_noop("The planner will merge subqueries into upper "
- 				"queries if the resulting FROM list would have no more than "
- 						 "this many items.")
- 		},
- 		&from_collapse_limit,
- 		8, 1, INT_MAX, NULL, NULL
- 	},
- 	{
- 		{"join_collapse_limit", PGC_USERSET, QUERY_TUNING_OTHER,
- 			gettext_noop("Sets the FROM-list size beyond which JOIN "
- 						 "constructs are not flattened."),
- 			gettext_noop("The planner will flatten explicit JOIN "
- 						 "constructs into lists of FROM items whenever a "
- 						 "list of no more than this many items would result.")
- 		},
- 		&join_collapse_limit,
- 		8, 1, INT_MAX, NULL, NULL
- 	},
- 	{
  		{"geqo_threshold", PGC_USERSET, QUERY_TUNING_GEQO,
  			gettext_noop("Sets the threshold of FROM items beyond which GEQO is used."),
  			NULL
--- 1267,1272 ----
*** a/src/backend/utils/misc/postgresql.conf.sample
--- b/src/backend/utils/misc/postgresql.conf.sample
***************
*** 190,195 ****
--- 190,196 ----
  #enable_hashagg = on
  #enable_hashjoin = on
  #enable_indexscan = on
+ #enable_join_reordering = on
  #enable_mergejoin = on
  #enable_nestloop = on
  #enable_seqscan = on
***************
*** 219,227 ****
  #default_statistics_target = 100	# range 1-10000
  #constraint_exclusion = partition	# on, off, or partition
  #cursor_tuple_fraction = 0.1		# range 0.0-1.0
- #from_collapse_limit = 8
- #join_collapse_limit = 8		# 1 disables collapsing of explicit 
- 					# JOIN clauses
  
  
  #------------------------------------------------------------------------------
--- 220,225 ----
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
***************
*** 79,86 **** extern bool is_projection_capable_plan(Plan *plan);
  /*
   * prototypes for plan/initsplan.c
   */
! extern int	from_collapse_limit;
! extern int	join_collapse_limit;
  
  extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
  extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
--- 79,85 ----
  /*
   * prototypes for plan/initsplan.c
   */
! extern bool	enable_join_ordering;
  
  extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
  extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
*** a/src/test/regress/expected/rangefuncs.out
--- b/src/test/regress/expected/rangefuncs.out
***************
*** 1,16 ****
  SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%';
!        name        | setting 
! -------------------+---------
!  enable_bitmapscan | on
!  enable_hashagg    | on
!  enable_hashjoin   | on
!  enable_indexscan  | on
!  enable_mergejoin  | on
!  enable_nestloop   | on
!  enable_seqscan    | on
!  enable_sort       | on
!  enable_tidscan    | on
! (9 rows)
  
  CREATE TABLE foo2(fooid int, f2 int);
  INSERT INTO foo2 VALUES(1, 11);
--- 1,17 ----
  SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%';
!          name         | setting 
! ----------------------+---------
!  enable_bitmapscan    | on
!  enable_hashagg       | on
!  enable_hashjoin      | on
!  enable_indexscan     | on
!  enable_join_ordering | on
!  enable_mergejoin     | on
!  enable_nestloop      | on
!  enable_seqscan       | on
!  enable_sort          | on
!  enable_tidscan       | on
! (10 rows)
  
  CREATE TABLE foo2(fooid int, f2 int);
  INSERT INTO foo2 VALUES(1, 11);

From 7d4d96e68f9e6740c7034acc9da5e511001c2aa7 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Tue, 14 Jul 2009 02:25:18 +0200
Subject: [PATCH] Support a 'geqo_seed' GUC to make planning via GEQO repeatable.

---
 src/backend/optimizer/geqo/Makefile             |    1 +
 src/backend/optimizer/geqo/geqo_copy.c          |    4 +-
 src/backend/optimizer/geqo/geqo_cx.c            |    6 +-
 src/backend/optimizer/geqo/geqo_erx.c           |   47 ++++++------
 src/backend/optimizer/geqo/geqo_eval.c          |   28 ++++----
 src/backend/optimizer/geqo/geqo_main.c          |   90 ++++++++++++-----------
 src/backend/optimizer/geqo/geqo_mutation.c      |   10 +-
 src/backend/optimizer/geqo/geqo_ox1.c           |    8 +-
 src/backend/optimizer/geqo/geqo_ox2.c           |    7 +-
 src/backend/optimizer/geqo/geqo_pmx.c           |    7 +-
 src/backend/optimizer/geqo/geqo_pool.c          |   23 +++---
 src/backend/optimizer/geqo/geqo_px.c            |    8 +-
 src/backend/optimizer/geqo/geqo_random.c        |   42 +++++++++++
 src/backend/optimizer/geqo/geqo_recombination.c |    9 +-
 src/backend/optimizer/geqo/geqo_selection.c     |   19 +++--
 src/backend/optimizer/path/allpaths.c           |    2 +
 src/backend/utils/misc/guc.c                    |    9 ++
 src/include/nodes/relation.h                    |    3 +
 src/include/optimizer/geqo.h                    |   17 ++---
 src/include/optimizer/geqo_copy.h               |    3 +-
 src/include/optimizer/geqo_mutation.h           |    3 +-
 src/include/optimizer/geqo_pool.h               |   14 ++--
 src/include/optimizer/geqo_random.h             |    9 +-
 src/include/optimizer/geqo_recombination.h      |   33 +++++---
 src/include/optimizer/geqo_selection.h          |    4 +-
 25 files changed, 244 insertions(+), 162 deletions(-)
 create mode 100644 src/backend/optimizer/geqo/geqo_random.c

diff --git a/src/backend/optimizer/geqo/Makefile b/src/backend/optimizer/geqo/Makefile
index dbc6c28..e5a01d7 100644
*** a/src/backend/optimizer/geqo/Makefile
--- b/src/backend/optimizer/geqo/Makefile
*************** top_builddir = ../../../..
*** 14,19 ****
--- 14,20 ----
  include $(top_builddir)/src/Makefile.global
  
  OBJS =	geqo_copy.o geqo_eval.o geqo_main.o geqo_misc.o \
+ 	geqo_random.o \
  	geqo_mutation.o geqo_pool.o geqo_recombination.o \
  	geqo_selection.o \
  	geqo_erx.o geqo_pmx.o geqo_cx.o geqo_px.o geqo_ox1.o geqo_ox2.o
diff --git a/src/backend/optimizer/geqo/geqo_copy.c b/src/backend/optimizer/geqo/geqo_copy.c
index 83af33a..373a924 100644
*** a/src/backend/optimizer/geqo/geqo_copy.c
--- b/src/backend/optimizer/geqo/geqo_copy.c
***************
*** 35,40 ****
--- 35,41 ----
  
  #include "postgres.h"
  #include "optimizer/geqo_copy.h"
+ #include "optimizer/geqo_copy.h"
  
  /* geqo_copy
   *
***************
*** 42,48 ****
   *
   */
  void
! geqo_copy(Chromosome *chromo1, Chromosome *chromo2, int string_length)
  {
  	int			i;
  
--- 43,50 ----
   *
   */
  void
! geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2,
! 		  int string_length)
  {
  	int			i;
  
diff --git a/src/backend/optimizer/geqo/geqo_cx.c b/src/backend/optimizer/geqo/geqo_cx.c
index 3d5102f..ad861ce 100644
*** a/src/backend/optimizer/geqo/geqo_cx.c
--- b/src/backend/optimizer/geqo/geqo_cx.c
***************
*** 35,40 ****
--- 35,41 ----
  
  
  #include "postgres.h"
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_recombination.h"
  #include "optimizer/geqo_random.h"
  
***************
*** 44,50 ****
   *	 cycle crossover
   */
  int
! cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
  {
  
  	int			i,
--- 45,52 ----
   *	 cycle crossover
   */
  int
! cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
!    int num_gene, City *city_table)
  {
  
  	int			i,
*************** cx(Gene *tour1, Gene *tour2, Gene *offsp
*** 62,68 ****
  	}
  
  	/* choose random cycle starting position */
! 	start_pos = geqo_randint(num_gene - 1, 0);
  
  	/* child inherits first city  */
  	offspring[start_pos] = tour1[start_pos];
--- 64,70 ----
  	}
  
  	/* choose random cycle starting position */
! 	start_pos = geqo_randint(root, num_gene - 1, 0);
  
  	/* child inherits first city  */
  	offspring[start_pos] = tour1[start_pos];
diff --git a/src/backend/optimizer/geqo/geqo_erx.c b/src/backend/optimizer/geqo/geqo_erx.c
index 35e1a28..5bae059 100644
*** a/src/backend/optimizer/geqo/geqo_erx.c
--- b/src/backend/optimizer/geqo/geqo_erx.c
***************
*** 36,46 ****
  #include "optimizer/geqo_random.h"
  
  
! static int	gimme_edge(Gene gene1, Gene gene2, Edge *edge_table);
! static void remove_gene(Gene gene, Edge edge, Edge *edge_table);
! static Gene gimme_gene(Edge edge, Edge *edge_table);
  
! static Gene edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene);
  
  
  /* alloc_edge_table
--- 36,46 ----
  #include "optimizer/geqo_random.h"
  
  
! static int	gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
! static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
! static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
  
! static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene);
  
  
  /* alloc_edge_table
*************** static Gene edge_failure(Gene *gene, int
*** 50,56 ****
   */
  
  Edge *
! alloc_edge_table(int num_gene)
  {
  	Edge	   *edge_table;
  
--- 50,56 ----
   */
  
  Edge *
! alloc_edge_table(PlannerInfo *root, int num_gene)
  {
  	Edge	   *edge_table;
  
*************** alloc_edge_table(int num_gene)
*** 70,76 ****
   *
   */
  void
! free_edge_table(Edge *edge_table)
  {
  	pfree(edge_table);
  }
--- 70,76 ----
   *
   */
  void
! free_edge_table(PlannerInfo *root, Edge *edge_table)
  {
  	pfree(edge_table);
  }
*************** free_edge_table(Edge *edge_table)
*** 89,95 ****
   *
   */
  float
! gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
  {
  	int			i,
  				index1,
--- 89,96 ----
   *
   */
  float
! gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
! 				 int num_gene, Edge *edge_table)
  {
  	int			i,
  				index1,
*************** gimme_edge_table(Gene *tour1, Gene *tour
*** 121,131 ****
  		 * twice per edge
  		 */
  
! 		edge_total += gimme_edge(tour1[index1], tour1[index2], edge_table);
! 		gimme_edge(tour1[index2], tour1[index1], edge_table);
  
! 		edge_total += gimme_edge(tour2[index1], tour2[index2], edge_table);
! 		gimme_edge(tour2[index2], tour2[index1], edge_table);
  	}
  
  	/* return average number of edges per index */
--- 122,132 ----
  		 * twice per edge
  		 */
  
! 		edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
! 		gimme_edge(root, tour1[index2], tour1[index1], edge_table);
  
! 		edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
! 		gimme_edge(root, tour2[index2], tour2[index1], edge_table);
  	}
  
  	/* return average number of edges per index */
*************** gimme_edge_table(Gene *tour1, Gene *tour
*** 147,153 ****
   *			  0 if edge was already registered and edge_table is unchanged
   */
  static int
! gimme_edge(Gene gene1, Gene gene2, Edge *edge_table)
  {
  	int			i;
  	int			edges;
--- 148,154 ----
   *			  0 if edge was already registered and edge_table is unchanged
   */
  static int
! gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
  {
  	int			i;
  	int			edges;
*************** gimme_edge(Gene gene1, Gene gene2, Edge 
*** 189,200 ****
   *
   */
  int
! gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene)
  {
  	int			i;
  	int			edge_failures = 0;
  
! 	new_gene[0] = (Gene) geqo_randint(num_gene, 1);		/* choose int between 1
  														 * and num_gene */
  
  	for (i = 1; i < num_gene; i++)
--- 190,201 ----
   *
   */
  int
! gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
  {
  	int			i;
  	int			edge_failures = 0;
  
! 	new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);		/* choose int between 1
  														 * and num_gene */
  
  	for (i = 1; i < num_gene; i++)
*************** gimme_tour(Edge *edge_table, Gene *new_g
*** 204,221 ****
  		 * table
  		 */
  
! 		remove_gene(new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
  
  		/* find destination for the newly entered point */
  
  		if (edge_table[new_gene[i - 1]].unused_edges > 0)
! 			new_gene[i] = gimme_gene(edge_table[(int) new_gene[i - 1]], edge_table);
  
  		else
  		{						/* cope with fault */
  			edge_failures++;
  
! 			new_gene[i] = edge_failure(new_gene, i - 1, edge_table, num_gene);
  		}
  
  		/* mark this node as incorporated */
--- 205,222 ----
  		 * table
  		 */
  
! 		remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
  
  		/* find destination for the newly entered point */
  
  		if (edge_table[new_gene[i - 1]].unused_edges > 0)
! 			new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
  
  		else
  		{						/* cope with fault */
  			edge_failures++;
  
! 			new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
  		}
  
  		/* mark this node as incorporated */
*************** gimme_tour(Edge *edge_table, Gene *new_g
*** 235,241 ****
   *
   */
  static void
! remove_gene(Gene gene, Edge edge, Edge *edge_table)
  {
  	int			i,
  				j;
--- 236,242 ----
   *
   */
  static void
! remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
  {
  	int			i,
  				j;
*************** remove_gene(Gene gene, Edge edge, Edge *
*** 277,283 ****
   *
   */
  static Gene
! gimme_gene(Edge edge, Edge *edge_table)
  {
  	int			i;
  	Gene		friend;
--- 278,284 ----
   *
   */
  static Gene
! gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
  {
  	int			i;
  	Gene		friend;
*************** gimme_gene(Edge edge, Edge *edge_table)
*** 340,346 ****
  
  
  	/* random decision of the possible candidates to use */
! 	rand_decision = (int) geqo_randint(minimum_count - 1, 0);
  
  
  	for (i = 0; i < edge.unused_edges; i++)
--- 341,347 ----
  
  
  	/* random decision of the possible candidates to use */
! 	rand_decision = geqo_randint(root, minimum_count - 1, 0);
  
  
  	for (i = 0; i < edge.unused_edges; i++)
*************** gimme_gene(Edge edge, Edge *edge_table)
*** 368,374 ****
   *
   */
  static Gene
! edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene)
  {
  	int			i;
  	Gene		fail_gene = gene[index];
--- 369,375 ----
   *
   */
  static Gene
! edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
  {
  	int			i;
  	Gene		fail_gene = gene[index];
*************** edge_failure(Gene *gene, int index, Edge
*** 401,407 ****
  	if (four_count != 0)
  	{
  
! 		rand_decision = (int) geqo_randint(four_count - 1, 0);
  
  		for (i = 1; i <= num_gene; i++)
  		{
--- 402,408 ----
  	if (four_count != 0)
  	{
  
! 		rand_decision = geqo_randint(root, four_count - 1, 0);
  
  		for (i = 1; i <= num_gene; i++)
  		{
*************** edge_failure(Gene *gene, int index, Edge
*** 423,429 ****
  	else if (remaining_edges != 0)
  	{
  		/* random decision of the gene with remaining edges */
! 		rand_decision = (int) geqo_randint(remaining_edges - 1, 0);
  
  		for (i = 1; i <= num_gene; i++)
  		{
--- 424,430 ----
  	else if (remaining_edges != 0)
  	{
  		/* random decision of the gene with remaining edges */
! 		rand_decision = geqo_randint(root, remaining_edges - 1, 0);
  
  		for (i = 1; i <= num_gene; i++)
  		{
diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c
index 04b3bfe..11903a5 100644
*** a/src/backend/optimizer/geqo/geqo_eval.c
--- b/src/backend/optimizer/geqo/geqo_eval.c
*************** static bool desirable_join(PlannerInfo *
*** 42,48 ****
   * Returns cost of a query tree as an individual of the population.
   */
  Cost
! geqo_eval(Gene *tour, int num_gene, GeqoEvalData *evaldata)
  {
  	MemoryContext mycontext;
  	MemoryContext oldcxt;
--- 42,48 ----
   * Returns cost of a query tree as an individual of the population.
   */
  Cost
! geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
  {
  	MemoryContext mycontext;
  	MemoryContext oldcxt;
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 94,106 ****
  	 * (If we are dealing with enough join rels, which we very likely are, a
  	 * new hash table will get built and used locally.)
  	 */
! 	savelength = list_length(evaldata->root->join_rel_list);
! 	savehash = evaldata->root->join_rel_hash;
  
! 	evaldata->root->join_rel_hash = NULL;
  
  	/* construct the best path for the given combination of relations */
! 	joinrel = gimme_tree(tour, num_gene, evaldata);
  
  	/*
  	 * compute fitness
--- 94,106 ----
  	 * (If we are dealing with enough join rels, which we very likely are, a
  	 * new hash table will get built and used locally.)
  	 */
! 	savelength = list_length(root->join_rel_list);
! 	savehash = root->join_rel_hash;
  
! 	root->join_rel_hash = NULL;
  
  	/* construct the best path for the given combination of relations */
! 	joinrel = gimme_tree(root, tour, num_gene);
  
  	/*
  	 * compute fitness
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 117,125 ****
  	 * Restore join_rel_list to its former state, and put back original
  	 * hashtable if any.
  	 */
! 	evaldata->root->join_rel_list = list_truncate(evaldata->root->join_rel_list,
! 												  savelength);
! 	evaldata->root->join_rel_hash = savehash;
  
  	/* release all the memory acquired within gimme_tree */
  	MemoryContextSwitchTo(oldcxt);
--- 117,125 ----
  	 * Restore join_rel_list to its former state, and put back original
  	 * hashtable if any.
  	 */
! 	root->join_rel_list = list_truncate(root->join_rel_list,
! 										savelength);
! 	root->join_rel_hash = savehash;
  
  	/* release all the memory acquired within gimme_tree */
  	MemoryContextSwitchTo(oldcxt);
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 134,140 ****
   *	  order.
   *
   *	 'tour' is the proposed join order, of length 'num_gene'
-  *	 'evaldata' contains the context we need
   *
   * 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.
--- 134,139 ----
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 153,159 ****
   * plans.
   */
  RelOptInfo *
! gimme_tree(Gene *tour, int num_gene, GeqoEvalData *evaldata)
  {
  	RelOptInfo **stack;
  	int			stack_depth;
--- 152,158 ----
   * plans.
   */
  RelOptInfo *
! gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
  {
  	RelOptInfo **stack;
  	int			stack_depth;
*************** gimme_tree(Gene *tour, int num_gene, Geq
*** 193,200 ****
  
  		/* Get the next input relation and push it */
  		cur_rel_index = (int) tour[rel_count];
! 		stack[stack_depth] = (RelOptInfo *) list_nth(evaldata->initial_rels,
! 													 cur_rel_index - 1);
  		stack_depth++;
  
  		/*
--- 192,200 ----
  
  		/* Get the next input relation and push it */
  		cur_rel_index = (int) tour[rel_count];
! 		stack[stack_depth] = (RelOptInfo *) list_nth(
! 			((GeqoPrivateData*)root->join_search_private)->initial_rels,
! 			cur_rel_index - 1);
  		stack_depth++;
  
  		/*
*************** gimme_tree(Gene *tour, int num_gene, Geq
*** 211,217 ****
  			 * have exhausted the input, the heuristics can't prevent popping.
  			 */
  			if (rel_count < num_gene - 1 &&
! 				!desirable_join(evaldata->root, outer_rel, inner_rel))
  				break;
  
  			/*
--- 211,217 ----
  			 * have exhausted the input, the heuristics can't prevent popping.
  			 */
  			if (rel_count < num_gene - 1 &&
! 				!desirable_join(root, outer_rel, inner_rel))
  				break;
  
  			/*
*************** gimme_tree(Gene *tour, int num_gene, Geq
*** 220,226 ****
  			 * root->join_rel_list yet, and so the paths constructed for it
  			 * will only include the ones we want.
  			 */
! 			joinrel = make_join_rel(evaldata->root, outer_rel, inner_rel);
  
  			/* Can't pop stack here if join order is not valid */
  			if (!joinrel)
--- 220,226 ----
  			 * 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)
diff --git a/src/backend/optimizer/geqo/geqo_main.c b/src/backend/optimizer/geqo/geqo_main.c
index 72b0b57..10f64f4 100644
*** a/src/backend/optimizer/geqo/geqo_main.c
--- b/src/backend/optimizer/geqo/geqo_main.c
***************
*** 29,34 ****
--- 29,35 ----
  #include "optimizer/geqo_misc.h"
  #include "optimizer/geqo_pool.h"
  #include "optimizer/geqo_selection.h"
+ #include "optimizer/geqo_random.h"
  
  
  /*
*************** int			Geqo_effort;
*** 38,43 ****
--- 39,45 ----
  int			Geqo_pool_size;
  int			Geqo_generations;
  double		Geqo_selection_bias;
+ double		Geqo_seed;
  
  
  static int	gimme_pool_size(int nr_rel);
*************** static int	gimme_number_generations(int 
*** 63,69 ****
  RelOptInfo *
  geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
  {
- 	GeqoEvalData evaldata;
  	int			generation;
  	Chromosome *momma;
  	Chromosome *daddy;
--- 65,70 ----
*************** geqo(PlannerInfo *root, int number_of_re
*** 88,96 ****
  	int			mutations = 0;
  #endif
  
! /* set up evaldata */
! 	evaldata.root = root;
! 	evaldata.initial_rels = initial_rels;
  
  /* set GA parameters */
  	pool_size = gimme_pool_size(number_of_rels);
--- 89,102 ----
  	int			mutations = 0;
  #endif
  
! /* setup private information */
! 	root->join_search_private = (GeqoPrivateData*)palloc0(sizeof(GeqoPrivateData));
! 	((GeqoPrivateData*)root->join_search_private)->initial_rels = initial_rels;
! 
! /* initialize private number generator */
! 	if(Geqo_seed != 0){
! 		geqo_seed(root, Geqo_seed);
! 	}
  
  /* set GA parameters */
  	pool_size = gimme_pool_size(number_of_rels);
*************** geqo(PlannerInfo *root, int number_of_re
*** 98,110 ****
  	status_interval = 10;
  
  /* allocate genetic pool memory */
! 	pool = alloc_pool(pool_size, number_of_rels);
  
  /* random initialization of the pool */
! 	random_init_pool(pool, &evaldata);
  
  /* sort the pool according to cheapest path as fitness */
! 	sort_pool(pool);			/* we have to do it only one time, since all
  								 * kids replace the worst individuals in
  								 * future (-> geqo_pool.c:spread_chromo ) */
  
--- 104,116 ----
  	status_interval = 10;
  
  /* allocate genetic pool memory */
! 	pool = alloc_pool(root, pool_size, number_of_rels);
  
  /* random initialization of the pool */
! 	random_init_pool(root, pool);
  
  /* sort the pool according to cheapest path as fitness */
! 	sort_pool(root, pool);			/* we have to do it only one time, since all
  								 * kids replace the worst individuals in
  								 * future (-> geqo_pool.c:spread_chromo ) */
  
*************** geqo(PlannerInfo *root, int number_of_re
*** 116,164 ****
  #endif
  
  /* allocate chromosome momma and daddy memory */
! 	momma = alloc_chromo(pool->string_length);
! 	daddy = alloc_chromo(pool->string_length);
  
  #if defined (ERX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using edge recombination crossover [ERX]");
  #endif
  /* allocate edge table memory */
! 	edge_table = alloc_edge_table(pool->string_length);
  #elif defined(PMX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using partially matched crossover [PMX]");
  #endif
  /* allocate chromosome kid memory */
! 	kid = alloc_chromo(pool->string_length);
  #elif defined(CX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using cycle crossover [CX]");
  #endif
  /* allocate city table memory */
! 	kid = alloc_chromo(pool->string_length);
! 	city_table = alloc_city_table(pool->string_length);
  #elif defined(PX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using position crossover [PX]");
  #endif
  /* allocate city table memory */
! 	kid = alloc_chromo(pool->string_length);
! 	city_table = alloc_city_table(pool->string_length);
  #elif defined(OX1)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using order crossover [OX1]");
  #endif
  /* allocate city table memory */
  	kid = alloc_chromo(pool->string_length);
! 	city_table = alloc_city_table(pool->string_length);
  #elif defined(OX2)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using order crossover [OX2]");
  #endif
  /* allocate city table memory */
  	kid = alloc_chromo(pool->string_length);
! 	city_table = alloc_city_table(pool->string_length);
  #endif
  
  
--- 122,170 ----
  #endif
  
  /* allocate chromosome momma and daddy memory */
! 	momma = alloc_chromo(root, pool->string_length);
! 	daddy = alloc_chromo(root, pool->string_length);
  
  #if defined (ERX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using edge recombination crossover [ERX]");
  #endif
  /* allocate edge table memory */
! 	edge_table = alloc_edge_table(root, pool->string_length);
  #elif defined(PMX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using partially matched crossover [PMX]");
  #endif
  /* allocate chromosome kid memory */
! 	kid = alloc_chromo(root, pool->string_length);
  #elif defined(CX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using cycle crossover [CX]");
  #endif
  /* allocate city table memory */
! 	kid = alloc_chromo(root, pool->string_length);
! 	city_table = alloc_city_table(root, pool->string_length);
  #elif defined(PX)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using position crossover [PX]");
  #endif
  /* allocate city table memory */
! 	kid = alloc_chromo(root, pool->string_length);
! 	city_table = alloc_city_table(root, pool->string_length);
  #elif defined(OX1)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using order crossover [OX1]");
  #endif
  /* allocate city table memory */
  	kid = alloc_chromo(pool->string_length);
! 	city_table = alloc_city_table(root, pool->string_length);
  #elif defined(OX2)
  #ifdef GEQO_DEBUG
  	elog(DEBUG2, "using order crossover [OX2]");
  #endif
  /* allocate city table memory */
  	kid = alloc_chromo(pool->string_length);
! 	city_table = alloc_city_table(root, pool->string_length);
  #endif
  
  
*************** geqo(PlannerInfo *root, int number_of_re
*** 168,212 ****
  	for (generation = 0; generation < number_generations; generation++)
  	{
  		/* SELECTION: using linear bias function */
! 		geqo_selection(momma, daddy, pool, Geqo_selection_bias);
  
  #if defined (ERX)
  		/* EDGE RECOMBINATION CROSSOVER */
! 		difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);
  
  		kid = momma;
  
  		/* are there any edge failures ? */
! 		edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
  #elif defined(PMX)
  		/* PARTIALLY MATCHED CROSSOVER */
! 		pmx(momma->string, daddy->string, kid->string, pool->string_length);
  #elif defined(CX)
  		/* CYCLE CROSSOVER */
! 		cycle_diffs = cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
  		/* mutate the child */
  		if (cycle_diffs == 0)
  		{
  			mutations++;
! 			geqo_mutation(kid->string, pool->string_length);
  		}
  #elif defined(PX)
  		/* POSITION CROSSOVER */
! 		px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
  #elif defined(OX1)
  		/* ORDER CROSSOVER */
! 		ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
  #elif defined(OX2)
  		/* ORDER CROSSOVER */
! 		ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
  #endif
  
  
  		/* EVALUATE FITNESS */
! 		kid->worth = geqo_eval(kid->string, pool->string_length, &evaldata);
  
  		/* push the kid into the wilderness of life according to its worth */
! 		spread_chromo(kid, pool);
  
  
  #ifdef GEQO_DEBUG
--- 174,218 ----
  	for (generation = 0; generation < number_generations; generation++)
  	{
  		/* SELECTION: using linear bias function */
! 		geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
  
  #if defined (ERX)
  		/* EDGE RECOMBINATION CROSSOVER */
! 		difference = gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
  
  		kid = momma;
  
  		/* are there any edge failures ? */
! 		edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
  #elif defined(PMX)
  		/* PARTIALLY MATCHED CROSSOVER */
! 		pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
  #elif defined(CX)
  		/* CYCLE CROSSOVER */
! 		cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
  		/* mutate the child */
  		if (cycle_diffs == 0)
  		{
  			mutations++;
! 			geqo_mutation(root, kid->string, pool->string_length);
  		}
  #elif defined(PX)
  		/* POSITION CROSSOVER */
! 		px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
  #elif defined(OX1)
  		/* ORDER CROSSOVER */
! 		ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
  #elif defined(OX2)
  		/* ORDER CROSSOVER */
! 		ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
  #endif
  
  
  		/* EVALUATE FITNESS */
! 		kid->worth = geqo_eval(root, kid->string, pool->string_length);
  
  		/* push the kid into the wilderness of life according to its worth */
! 		spread_chromo(root, kid, pool);
  
  
  #ifdef GEQO_DEBUG
*************** geqo(PlannerInfo *root, int number_of_re
*** 249,255 ****
  	 */
  	best_tour = (Gene *) pool->data[0].string;
  
! 	best_rel = gimme_tree(best_tour, pool->string_length, &evaldata);
  
  	if (best_rel == NULL)
  		elog(ERROR, "failed to make a valid plan");
--- 255,261 ----
  	 */
  	best_tour = (Gene *) pool->data[0].string;
  
! 	best_rel = gimme_tree(root, best_tour, pool->string_length);
  
  	if (best_rel == NULL)
  		elog(ERROR, "failed to make a valid plan");
*************** geqo(PlannerInfo *root, int number_of_re
*** 260,287 ****
  #endif
  
  	/* ... free memory stuff */
! 	free_chromo(momma);
! 	free_chromo(daddy);
  
  #if defined (ERX)
! 	free_edge_table(edge_table);
  #elif defined(PMX)
! 	free_chromo(kid);
  #elif defined(CX)
! 	free_chromo(kid);
! 	free_city_table(city_table);
  #elif defined(PX)
! 	free_chromo(kid);
! 	free_city_table(city_table);
  #elif defined(OX1)
! 	free_chromo(kid);
! 	free_city_table(city_table);
  #elif defined(OX2)
! 	free_chromo(kid);
! 	free_city_table(city_table);
  #endif
  
! 	free_pool(pool);
  
  	return best_rel;
  }
--- 266,293 ----
  #endif
  
  	/* ... free memory stuff */
! 	free_chromo(root, momma);
! 	free_chromo(root, daddy);
  
  #if defined (ERX)
! 	free_edge_table(root, edge_table);
  #elif defined(PMX)
! 	free_chromo(root, kid);
  #elif defined(CX)
! 	free_chromo(root, kid);
! 	free_city_table(root, city_table);
  #elif defined(PX)
! 	free_chromo(root, kid);
! 	free_city_table(root, city_table);
  #elif defined(OX1)
! 	free_chromo(root, kid);
! 	free_city_table(root, city_table);
  #elif defined(OX2)
! 	free_chromo(root, kid);
! 	free_city_table(root, city_table);
  #endif
  
! 	free_pool(root, pool);
  
  	return best_rel;
  }
diff --git a/src/backend/optimizer/geqo/geqo_mutation.c b/src/backend/optimizer/geqo/geqo_mutation.c
index 899410c..acf3b34 100644
*** a/src/backend/optimizer/geqo/geqo_mutation.c
--- b/src/backend/optimizer/geqo/geqo_mutation.c
***************
*** 36,56 ****
  #include "optimizer/geqo_random.h"
  
  void
! geqo_mutation(Gene *tour, int num_gene)
  {
  	int			swap1;
  	int			swap2;
! 	int			num_swaps = geqo_randint(num_gene / 3, 0);
  	Gene		temp;
  
  
  	while (num_swaps > 0)
  	{
! 		swap1 = geqo_randint(num_gene - 1, 0);
! 		swap2 = geqo_randint(num_gene - 1, 0);
  
  		while (swap1 == swap2)
! 			swap2 = geqo_randint(num_gene - 1, 0);
  
  		temp = tour[swap1];
  		tour[swap1] = tour[swap2];
--- 36,56 ----
  #include "optimizer/geqo_random.h"
  
  void
! geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
  {
  	int			swap1;
  	int			swap2;
! 	int			num_swaps = geqo_randint(root, num_gene / 3, 0);
  	Gene		temp;
  
  
  	while (num_swaps > 0)
  	{
! 		swap1 = geqo_randint(root, num_gene - 1, 0);
! 		swap2 = geqo_randint(root, num_gene - 1, 0);
  
  		while (swap1 == swap2)
! 			swap2 = geqo_randint(root, num_gene - 1, 0);
  
  		temp = tour[swap1];
  		tour[swap1] = tour[swap2];
diff --git a/src/backend/optimizer/geqo/geqo_ox1.c b/src/backend/optimizer/geqo/geqo_ox1.c
index cd979df..d292e98 100644
*** a/src/backend/optimizer/geqo/geqo_ox1.c
--- b/src/backend/optimizer/geqo/geqo_ox1.c
***************
*** 34,39 ****
--- 34,40 ----
  /*************************************************************/
  
  #include "postgres.h"
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_recombination.h"
  
***************
*** 43,49 ****
   *	 position crossover
   */
  void
! ox1(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
  {
  	int			left,
  				right,
--- 44,51 ----
   *	 position crossover
   */
  void
! ox1(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
! 	City *city_table)
  {
  	int			left,
  				right,
*************** ox1(Gene *tour1, Gene *tour2, Gene *offs
*** 56,63 ****
  		city_table[k].used = 0;
  
  	/* select portion to copy from tour1 */
! 	left = geqo_randint(num_gene - 1, 0);
! 	right = geqo_randint(num_gene - 1, 0);
  
  	if (left > right)
  	{
--- 58,65 ----
  		city_table[k].used = 0;
  
  	/* select portion to copy from tour1 */
! 	left = geqo_randint(root, num_gene - 1, 0);
! 	right = geqo_randint(root, num_gene - 1, 0);
  
  	if (left > right)
  	{
diff --git a/src/backend/optimizer/geqo/geqo_ox2.c b/src/backend/optimizer/geqo/geqo_ox2.c
index 0d2e0de..a2fdfe8 100644
*** a/src/backend/optimizer/geqo/geqo_ox2.c
--- b/src/backend/optimizer/geqo/geqo_ox2.c
***************
*** 34,39 ****
--- 34,40 ----
  /*************************************************************/
  
  #include "postgres.h"
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_recombination.h"
  
***************
*** 43,49 ****
   *	 position crossover
   */
  void
! ox2(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
  {
  	int			k,
  				j,
--- 44,50 ----
   *	 position crossover
   */
  void
! ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
  {
  	int			k,
  				j,
*************** ox2(Gene *tour1, Gene *tour2, Gene *offs
*** 60,71 ****
  	}
  
  	/* determine the number of positions to be inherited from tour1  */
! 	num_positions = geqo_randint(2 * num_gene / 3, num_gene / 3);
  
  	/* make a list of selected cities */
  	for (k = 0; k < num_positions; k++)
  	{
! 		pos = geqo_randint(num_gene - 1, 0);
  		city_table[pos].select_list = (int) tour1[pos];
  		city_table[(int) tour1[pos]].used = 1;	/* mark used */
  	}
--- 61,72 ----
  	}
  
  	/* determine the number of positions to be inherited from tour1  */
! 	num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
  
  	/* make a list of selected cities */
  	for (k = 0; k < num_positions; k++)
  	{
! 		pos = geqo_randint(root, num_gene - 1, 0);
  		city_table[pos].select_list = (int) tour1[pos];
  		city_table[(int) tour1[pos]].used = 1;	/* mark used */
  	}
diff --git a/src/backend/optimizer/geqo/geqo_pmx.c b/src/backend/optimizer/geqo/geqo_pmx.c
index fe9d4b4..a8d18c5 100644
*** a/src/backend/optimizer/geqo/geqo_pmx.c
--- b/src/backend/optimizer/geqo/geqo_pmx.c
***************
*** 34,39 ****
--- 34,40 ----
  /*************************************************************/
  
  #include "postgres.h"
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_recombination.h"
  
***************
*** 43,49 ****
   *	 partially matched crossover
   */
  void
! pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
  {
  	int		   *failed = (int *) palloc((num_gene + 1) * sizeof(int));
  	int		   *from = (int *) palloc((num_gene + 1) * sizeof(int));
--- 44,50 ----
   *	 partially matched crossover
   */
  void
! pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
  {
  	int		   *failed = (int *) palloc((num_gene + 1) * sizeof(int));
  	int		   *from = (int *) palloc((num_gene + 1) * sizeof(int));
*************** pmx(Gene *tour1, Gene *tour2, Gene *offs
*** 71,78 ****
  	}
  
  /* locate crossover points */
! 	left = geqo_randint(num_gene - 1, 0);
! 	right = geqo_randint(num_gene - 1, 0);
  
  	if (left > right)
  	{
--- 72,79 ----
  	}
  
  /* locate crossover points */
! 	left = geqo_randint(root, num_gene - 1, 0);
! 	right = geqo_randint(root, num_gene - 1, 0);
  
  	if (left > right)
  	{
diff --git a/src/backend/optimizer/geqo/geqo_pool.c b/src/backend/optimizer/geqo/geqo_pool.c
index 72eb34f..64e23ba 100644
*** a/src/backend/optimizer/geqo/geqo_pool.c
--- b/src/backend/optimizer/geqo/geqo_pool.c
*************** static int	compare(const void *arg1, con
*** 39,45 ****
   *		allocates memory for GA pool
   */
  Pool *
! alloc_pool(int pool_size, int string_length)
  {
  	Pool	   *new_pool;
  	Chromosome *chromo;
--- 39,45 ----
   *		allocates memory for GA pool
   */
  Pool *
! alloc_pool(PlannerInfo *root, int pool_size, int string_length)
  {
  	Pool	   *new_pool;
  	Chromosome *chromo;
*************** alloc_pool(int pool_size, int string_len
*** 66,72 ****
   *		deallocates memory for GA pool
   */
  void
! free_pool(Pool *pool)
  {
  	Chromosome *chromo;
  	int			i;
--- 66,72 ----
   *		deallocates memory for GA pool
   */
  void
! free_pool(PlannerInfo *root, Pool *pool)
  {
  	Chromosome *chromo;
  	int			i;
*************** free_pool(Pool *pool)
*** 88,94 ****
   *		initialize genetic pool
   */
  void
! random_init_pool(Pool *pool, GeqoEvalData *evaldata)
  {
  	Chromosome *chromo = (Chromosome *) pool->data;
  	int			i;
--- 88,94 ----
   *		initialize genetic pool
   */
  void
! random_init_pool(PlannerInfo *root, Pool *pool)
  {
  	Chromosome *chromo = (Chromosome *) pool->data;
  	int			i;
*************** random_init_pool(Pool *pool, GeqoEvalDat
*** 105,114 ****
  	i = 0;
  	while (i < pool->size)
  	{
! 		init_tour(chromo[i].string, pool->string_length);
! 		pool->data[i].worth = geqo_eval(chromo[i].string,
! 										pool->string_length,
! 										evaldata);
  		if (pool->data[i].worth < DBL_MAX)
  			i++;
  		else
--- 105,113 ----
  	i = 0;
  	while (i < pool->size)
  	{
! 		init_tour(root, chromo[i].string, pool->string_length);
! 		pool->data[i].worth = geqo_eval(root, chromo[i].string,
! 										pool->string_length);
  		if (pool->data[i].worth < DBL_MAX)
  			i++;
  		else
*************** random_init_pool(Pool *pool, GeqoEvalDat
*** 133,139 ****
   *	 maybe you have to change compare() for different ordering ...
   */
  void
! sort_pool(Pool *pool)
  {
  	qsort(pool->data, pool->size, sizeof(Chromosome), compare);
  }
--- 132,138 ----
   *	 maybe you have to change compare() for different ordering ...
   */
  void
! sort_pool(PlannerInfo *root, Pool *pool)
  {
  	qsort(pool->data, pool->size, sizeof(Chromosome), compare);
  }
*************** compare(const void *arg1, const void *ar
*** 160,166 ****
   *	  allocates a chromosome and string space
   */
  Chromosome *
! alloc_chromo(int string_length)
  {
  	Chromosome *chromo;
  
--- 159,165 ----
   *	  allocates a chromosome and string space
   */
  Chromosome *
! alloc_chromo(PlannerInfo *root, int string_length)
  {
  	Chromosome *chromo;
  
*************** alloc_chromo(int string_length)
*** 174,180 ****
   *	  deallocates a chromosome and string space
   */
  void
! free_chromo(Chromosome *chromo)
  {
  	pfree(chromo->string);
  	pfree(chromo);
--- 173,179 ----
   *	  deallocates a chromosome and string space
   */
  void
! free_chromo(PlannerInfo *root, Chromosome *chromo)
  {
  	pfree(chromo->string);
  	pfree(chromo);
*************** free_chromo(Chromosome *chromo)
*** 185,191 ****
   *	 assumes best->worst = smallest->largest
   */
  void
! spread_chromo(Chromosome *chromo, Pool *pool)
  {
  	int			top,
  				mid,
--- 184,190 ----
   *	 assumes best->worst = smallest->largest
   */
  void
! spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
  {
  	int			top,
  				mid,
*************** spread_chromo(Chromosome *chromo, Pool *
*** 247,253 ****
  	 * copy new gene into pool storage; always replace worst gene in pool
  	 */
  
! 	geqo_copy(&pool->data[pool->size - 1], chromo, pool->string_length);
  
  	swap_chromo.string = pool->data[pool->size - 1].string;
  	swap_chromo.worth = pool->data[pool->size - 1].worth;
--- 246,252 ----
  	 * copy new gene into pool storage; always replace worst gene in pool
  	 */
  
! 	geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
  
  	swap_chromo.string = pool->data[pool->size - 1].string;
  	swap_chromo.worth = pool->data[pool->size - 1].worth;
diff --git a/src/backend/optimizer/geqo/geqo_px.c b/src/backend/optimizer/geqo/geqo_px.c
index 07f41cd..9e9cee2 100644
*** a/src/backend/optimizer/geqo/geqo_px.c
--- b/src/backend/optimizer/geqo/geqo_px.c
***************
*** 34,39 ****
--- 34,40 ----
  /*************************************************************/
  
  #include "postgres.h"
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_recombination.h"
  
***************
*** 43,49 ****
   *	 position crossover
   */
  void
! px(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
  {
  
  	int			num_positions;
--- 44,51 ----
   *	 position crossover
   */
  void
! px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
!    City *city_table)
  {
  
  	int			num_positions;
*************** px(Gene *tour1, Gene *tour2, Gene *offsp
*** 57,68 ****
  		city_table[i].used = 0;
  
  	/* choose random positions that will be inherited directly from parent */
! 	num_positions = geqo_randint(2 * num_gene / 3, num_gene / 3);
  
  	/* choose random position */
  	for (i = 0; i < num_positions; i++)
  	{
! 		pos = geqo_randint(num_gene - 1, 0);
  
  		offspring[pos] = tour1[pos];	/* transfer cities to child */
  		city_table[(int) tour1[pos]].used = 1;	/* mark city used */
--- 59,70 ----
  		city_table[i].used = 0;
  
  	/* choose random positions that will be inherited directly from parent */
! 	num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
  
  	/* choose random position */
  	for (i = 0; i < num_positions; i++)
  	{
! 		pos = geqo_randint(root, num_gene - 1, 0);
  
  		offspring[pos] = tour1[pos];	/* transfer cities to child */
  		city_table[(int) tour1[pos]].used = 1;	/* mark city used */
diff --git a/src/backend/optimizer/geqo/geqo_random.c b/src/backend/optimizer/geqo/geqo_random.c
index ...59d5e42 .
*** a/src/backend/optimizer/geqo/geqo_random.c
--- b/src/backend/optimizer/geqo/geqo_random.c
***************
*** 0 ****
--- 1,42 ----
+ /*------------------------------------------------------------------------
+  *
+  * geqo_misc.c
+  *	   misc. printout and debug stuff
+  *
+  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
+  * Portions Copyright (c) 1994, Regents of the University of California
+  *
+  * $PostgreSQL$
+  *
+  *-------------------------------------------------------------------------
+  */
+ 
+ #include "postgres.h"
+ 
+ #include "optimizer/geqo.h"
+ #include "optimizer/geqo_random.h"
+ 
+ 
+ static unsigned short global_random_state[3];
+ 
+ void geqo_seed(PlannerInfo *root, double seed){
+ 	GeqoPrivateData *private = (GeqoPrivateData*)root->join_search_private;
+ 
+ 	private->random_state = palloc(sizeof(global_random_state));
+ 
+ 	/*
+ 	 * XXX. This seeding algorithm could certainly be improved - but
+ 	 * it is not critical to do so.
+ 	 */
+ 	memcpy(private->random_state,
+ 		   &seed,
+ 		   Min(sizeof(global_random_state),
+ 			   sizeof(seed))
+ 		);
+ }
+ 
+ double geqo_rand(PlannerInfo *root){
+ 	if(!((GeqoPrivateData*)root->join_search_private)->random_state)
+ 		return erand48(global_random_state);
+ 	return erand48(((GeqoPrivateData*)root->join_search_private)->random_state);
+ };
diff --git a/src/backend/optimizer/geqo/geqo_recombination.c b/src/backend/optimizer/geqo/geqo_recombination.c
index 3972fb1..e2b69a3 100644
*** a/src/backend/optimizer/geqo/geqo_recombination.c
--- b/src/backend/optimizer/geqo/geqo_recombination.c
***************
*** 20,25 ****
--- 20,26 ----
  
  #include "postgres.h"
  
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_recombination.h"
  
***************
*** 35,41 ****
   *	 and the procedure repeated.
   */
  void
! init_tour(Gene *tour, int num_gene)
  {
  	Gene	   *tmp;
  	int			remainder;
--- 36,42 ----
   *	 and the procedure repeated.
   */
  void
! init_tour(PlannerInfo *root, Gene *tour, int num_gene)
  {
  	Gene	   *tmp;
  	int			remainder;
*************** init_tour(Gene *tour, int num_gene)
*** 53,59 ****
  	for (i = 0; i < num_gene; i++)
  	{
  		/* choose value between 0 and remainder inclusive */
! 		next = (int) geqo_randint(remainder, 0);
  		/* output that element of the tmp array */
  		tour[i] = tmp[next];
  		/* and delete it */
--- 54,60 ----
  	for (i = 0; i < num_gene; i++)
  	{
  		/* choose value between 0 and remainder inclusive */
! 		next = (int) geqo_randint(root, remainder, 0);
  		/* output that element of the tmp array */
  		tour[i] = tmp[next];
  		/* and delete it */
*************** init_tour(Gene *tour, int num_gene)
*** 81,87 ****
   *	 allocate memory for city table
   */
  City *
! alloc_city_table(int num_gene)
  {
  	City	   *city_table;
  
--- 82,88 ----
   *	 allocate memory for city table
   */
  City *
! alloc_city_table(PlannerInfo *root, int num_gene)
  {
  	City	   *city_table;
  
*************** alloc_city_table(int num_gene)
*** 99,105 ****
   *	  deallocate memory of city table
   */
  void
! free_city_table(City *city_table)
  {
  	pfree(city_table);
  }
--- 100,106 ----
   *	  deallocate memory of city table
   */
  void
! free_city_table(PlannerInfo *root, City *city_table)
  {
  	pfree(city_table);
  }
diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c
index d4f2c4d..2cd7402 100644
*** a/src/backend/optimizer/geqo/geqo_selection.c
--- b/src/backend/optimizer/geqo/geqo_selection.c
***************
*** 42,48 ****
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_selection.h"
  
! static int	linear(int max, double bias);
  
  
  /*
--- 42,48 ----
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_selection.h"
  
! static int	linear(PlannerInfo *root, int max, double bias);
  
  
  /*
*************** static int	linear(int max, double bias);
*** 51,72 ****
   *	 first and second genes are selected from the pool
   */
  void
! geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
  {
  	int			first,
  				second;
  
! 	first = linear(pool->size, bias);
! 	second = linear(pool->size, bias);
  
  	if (pool->size > 1)
  	{
  		while (first == second)
! 			second = linear(pool->size, bias);
  	}
  
! 	geqo_copy(momma, &pool->data[first], pool->string_length);
! 	geqo_copy(daddy, &pool->data[second], pool->string_length);
  }
  
  /*
--- 51,73 ----
   *	 first and second genes are selected from the pool
   */
  void
! geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
! 			   Pool *pool, double bias)
  {
  	int			first,
  				second;
  
! 	first = linear(root, pool->size, bias);
! 	second = linear(root, pool->size, bias);
  
  	if (pool->size > 1)
  	{
  		while (first == second)
! 			second = linear(root, pool->size, bias);
  	}
  
! 	geqo_copy(root, momma, &pool->data[first], pool->string_length);
! 	geqo_copy(root, daddy, &pool->data[second], pool->string_length);
  }
  
  /*
*************** geqo_selection(Chromosome *momma, Chromo
*** 78,84 ****
   *			 bias = (prob of first rule) / (prob of middle rule)
   */
  static int
! linear(int pool_size, double bias)		/* bias is y-intercept of linear
  										 * distribution */
  {
  	double		index;			/* index between 0 and pop_size */
--- 79,85 ----
   *			 bias = (prob of first rule) / (prob of middle rule)
   */
  static int
! linear(PlannerInfo *root, int pool_size, double bias)		/* bias is y-intercept of linear
  										 * distribution */
  {
  	double		index;			/* index between 0 and pop_size */
*************** linear(int pool_size, double bias)		/* b
*** 95,101 ****
  	{
  		double		sqrtval;
  
! 		sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand();
  		if (sqrtval > 0.0)
  			sqrtval = sqrt(sqrtval);
  		index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
--- 96,102 ----
  	{
  		double		sqrtval;
  
! 		sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
  		if (sqrtval > 0.0)
  			sqrtval = sqrt(sqrtval);
  		index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b375902..777d75d 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** standard_join_search(PlannerInfo *root, 
*** 901,906 ****
--- 901,908 ----
  	int			lev;
  	RelOptInfo *rel;
  
+ 	Assert(root->join_search_private == 0);
+ 
  	/*
  	 * We employ a simple "dynamic programming" algorithm: we first find all
  	 * ways to build joins of two jointree items, then all ways to build joins
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 2430185..4126516 100644
*** a/src/backend/utils/misc/guc.c
--- b/src/backend/utils/misc/guc.c
*************** static struct config_real ConfigureNames
*** 2026,2031 ****
--- 2026,2040 ----
  		DEFAULT_GEQO_SELECTION_BIAS, MIN_GEQO_SELECTION_BIAS,
  		MAX_GEQO_SELECTION_BIAS, NULL, NULL
  	},
+ 	{
+ 		{"geqo_seed", PGC_USERSET, QUERY_TUNING_GEQO,
+ 			gettext_noop("GEQO: seed for random path selection for repeatable plan generation."),
+ 			gettext_noop("If zero planning will not be repeatable"),
+ 			GUC_NOT_IN_SAMPLE
+ 		},
+ 		&Geqo_seed,
+ 		0, 0, 1, NULL, NULL
+ 	},
  
  	{
  		{"bgwriter_lru_multiplier", PGC_SIGHUP, RESOURCES,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index ea48889..8f82d71 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 192,197 ****
--- 192,200 ----
  	/* These fields are used only when hasRecursion is true: */
  	int			wt_param_id;	/* PARAM_EXEC ID for the work table */
  	struct Plan *non_recursive_plan;	/* plan for non-recursive term */
+ 
+ 	/* private data for join-order implementation, i.e. GEQO */
+ 	void		*join_search_private;
  } PlannerInfo;
  
  
diff --git a/src/include/optimizer/geqo.h b/src/include/optimizer/geqo.h
index ea4c812..7a9b6a4 100644
*** a/src/include/optimizer/geqo.h
--- b/src/include/optimizer/geqo.h
*************** extern int	Geqo_pool_size;		/* 2 .. inf,
*** 59,88 ****
  extern int	Geqo_generations;	/* 1 .. inf, or 0 to use default */
  
  extern double Geqo_selection_bias;
  
  #define DEFAULT_GEQO_SELECTION_BIAS 2.0
  #define MIN_GEQO_SELECTION_BIAS 1.5
  #define MAX_GEQO_SELECTION_BIAS 2.0
  
  
- /*
-  * Data structure to encapsulate information needed for building plan trees
-  * (i.e., geqo_eval and gimme_tree).
-  */
  typedef struct
  {
! 	PlannerInfo *root;			/* the query we are planning */
! 	List	   *initial_rels;	/* the base relations */
! } GeqoEvalData;
! 
  
  /* routines in geqo_main.c */
  extern RelOptInfo *geqo(PlannerInfo *root,
  	 int number_of_rels, List *initial_rels);
  
  /* routines in geqo_eval.c */
! extern Cost geqo_eval(Gene *tour, int num_gene, GeqoEvalData *evaldata);
! extern RelOptInfo *gimme_tree(Gene *tour, int num_gene,
! 		   GeqoEvalData *evaldata);
  
  #endif   /* GEQO_H */
--- 59,83 ----
  extern int	Geqo_generations;	/* 1 .. inf, or 0 to use default */
  
  extern double Geqo_selection_bias;
+ extern double Geqo_seed;
  
  #define DEFAULT_GEQO_SELECTION_BIAS 2.0
  #define MIN_GEQO_SELECTION_BIAS 1.5
  #define MAX_GEQO_SELECTION_BIAS 2.0
  
  
  typedef struct
  {
! 	List *initial_rels;
! 	unsigned short *random_state;
! } GeqoPrivateData;
  
  /* routines in geqo_main.c */
  extern RelOptInfo *geqo(PlannerInfo *root,
  	 int number_of_rels, List *initial_rels);
  
  /* routines in geqo_eval.c */
! extern Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_geneo);
! extern RelOptInfo *gimme_tree(PlannerInfo *root, Gene *tour, int num_gene);
  
  #endif   /* GEQO_H */
diff --git a/src/include/optimizer/geqo_copy.h b/src/include/optimizer/geqo_copy.h
index ae13059..63b7c83 100644
*** a/src/include/optimizer/geqo_copy.h
--- b/src/include/optimizer/geqo_copy.h
***************
*** 22,29 ****
  #ifndef GEQO_COPY_H
  #define GEQO_COPY_H
  
  #include "optimizer/geqo_gene.h"
  
! extern void geqo_copy(Chromosome *chromo1, Chromosome *chromo2, int string_length);
  
  #endif   /* GEQO_COPY_H */
--- 22,30 ----
  #ifndef GEQO_COPY_H
  #define GEQO_COPY_H
  
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_gene.h"
  
! extern void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length);
  
  #endif   /* GEQO_COPY_H */
diff --git a/src/include/optimizer/geqo_mutation.h b/src/include/optimizer/geqo_mutation.h
index 0384de8..3ada430 100644
*** a/src/include/optimizer/geqo_mutation.h
--- b/src/include/optimizer/geqo_mutation.h
***************
*** 22,29 ****
  #ifndef GEQO_MUTATION_H
  #define GEQO_MUTATION_H
  
  #include "optimizer/geqo_gene.h"
  
! extern void geqo_mutation(Gene *tour, int num_gene);
  
  #endif   /* GEQO_MUTATION_H */
--- 22,30 ----
  #ifndef GEQO_MUTATION_H
  #define GEQO_MUTATION_H
  
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_gene.h"
  
! extern void geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene);
  
  #endif   /* GEQO_MUTATION_H */
diff --git a/src/include/optimizer/geqo_pool.h b/src/include/optimizer/geqo_pool.h
index 950e667..dbc6a01 100644
*** a/src/include/optimizer/geqo_pool.h
--- b/src/include/optimizer/geqo_pool.h
***************
*** 26,40 ****
  #include "optimizer/geqo.h"
  
  
! extern Pool *alloc_pool(int pool_size, int string_length);
! extern void free_pool(Pool *pool);
  
! extern void random_init_pool(Pool *pool, GeqoEvalData *evaldata);
! extern Chromosome *alloc_chromo(int string_length);
! extern void free_chromo(Chromosome *chromo);
  
! extern void spread_chromo(Chromosome *chromo, Pool *pool);
  
! extern void sort_pool(Pool *pool);
  
  #endif   /* GEQO_POOL_H */
--- 26,40 ----
  #include "optimizer/geqo.h"
  
  
! extern Pool *alloc_pool(PlannerInfo *root, int pool_size, int string_length);
! extern void free_pool(PlannerInfo *root, Pool *pool);
  
! extern void random_init_pool(PlannerInfo *root, Pool *pool);
! extern Chromosome *alloc_chromo(PlannerInfo *root, int string_length);
! extern void free_chromo(PlannerInfo *root, Chromosome *chromo);
  
! extern void spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool);
  
! extern void sort_pool(PlannerInfo *root, Pool *pool);
  
  #endif   /* GEQO_POOL_H */
diff --git a/src/include/optimizer/geqo_random.h b/src/include/optimizer/geqo_random.h
index fab0728..6fcfa7f 100644
*** a/src/include/optimizer/geqo_random.h
--- b/src/include/optimizer/geqo_random.h
***************
*** 27,38 ****
  #include <math.h>
  
  /* geqo_rand returns a random float value between 0 and 1 inclusive */
! 
! #define geqo_rand() ((double) random() / (double) MAX_RANDOM_VALUE)
  
  /* geqo_randint returns integer value between lower and upper inclusive */
! 
! #define geqo_randint(upper,lower) \
! 	( (int) floor( geqo_rand()*(((upper)-(lower))+0.999999) ) + (lower) )
  
  #endif   /* GEQO_RANDOM_H */
--- 27,37 ----
  #include <math.h>
  
  /* geqo_rand returns a random float value between 0 and 1 inclusive */
! double geqo_rand(PlannerInfo *root);
! void geqo_seed(PlannerInfo *root, double);
  
  /* geqo_randint returns integer value between lower and upper inclusive */
! #define geqo_randint(root, upper,lower)						\
! 	( (int) floor( geqo_rand(root)*(((upper)-(lower))+0.999999) ) + (lower) )
  
  #endif   /* GEQO_RANDOM_H */
diff --git a/src/include/optimizer/geqo_recombination.h b/src/include/optimizer/geqo_recombination.h
index 2c4a338..2484259 100644
*** a/src/include/optimizer/geqo_recombination.h
--- b/src/include/optimizer/geqo_recombination.h
***************
*** 24,32 ****
  #ifndef GEQO_RECOMBINATION_H
  #define GEQO_RECOMBINATION_H
  
  #include "optimizer/geqo_gene.h"
  
! extern void init_tour(Gene *tour, int num_gene);
  
  
  /* edge recombination crossover [ERX] */
--- 24,33 ----
  #ifndef GEQO_RECOMBINATION_H
  #define GEQO_RECOMBINATION_H
  
+ #include "optimizer/geqo.h"
  #include "optimizer/geqo_gene.h"
  
! extern void init_tour(PlannerInfo *root, Gene *tour, int num_gene);
  
  
  /* edge recombination crossover [ERX] */
*************** typedef struct Edge
*** 38,49 ****
  	int			unused_edges;
  } Edge;
  
! extern Edge *alloc_edge_table(int num_gene);
! extern void free_edge_table(Edge *edge_table);
  
! extern float gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table);
  
! extern int	gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene);
  
  
  /* partially matched crossover [PMX] */
--- 39,52 ----
  	int			unused_edges;
  } Edge;
  
! extern Edge *alloc_edge_table(PlannerInfo *root, int num_gene);
! extern void free_edge_table(PlannerInfo *root, Edge *edge_table);
  
! extern float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
! 							  int num_gene, Edge *edge_table);
  
! extern int	gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene,
! 					   int num_gene);
  
  
  /* partially matched crossover [PMX] */
*************** extern int	gimme_tour(Edge *edge_table, 
*** 51,57 ****
  #define DAD 1					/* indicator for gene from dad */
  #define MOM 0					/* indicator for gene from mom */
  
! extern void pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene);
  
  
  typedef struct City
--- 54,62 ----
  #define DAD 1					/* indicator for gene from dad */
  #define MOM 0					/* indicator for gene from mom */
  
! extern void pmx(PlannerInfo *root,
! 				Gene *tour1, Gene *tour2,
! 				Gene *offspring, int num_gene);
  
  
  typedef struct City
*************** typedef struct City
*** 62,80 ****
  	int			select_list;
  } City;
  
! extern City *alloc_city_table(int num_gene);
! extern void free_city_table(City *city_table);
  
  /* cycle crossover [CX] */
! extern int	cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table);
  
  /* position crossover [PX] */
! extern void px(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table);
  
  /* order crossover [OX1] according to Davis */
! extern void ox1(Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table);
  
  /* order crossover [OX2] according to Syswerda */
! extern void ox2(Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table);
  
  #endif   /* GEQO_RECOMBINATION_H */
--- 67,89 ----
  	int			select_list;
  } City;
  
! extern City *alloc_city_table(PlannerInfo *root, int num_gene);
! extern void free_city_table(PlannerInfo *root, City *city_table);
  
  /* cycle crossover [CX] */
! extern int	cx(PlannerInfo *root, Gene *tour1, Gene *tour2,
! 			   Gene *offspring, int num_gene, City *city_table);
  
  /* position crossover [PX] */
! extern void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
! 			   int num_gene, City *city_table);
  
  /* order crossover [OX1] according to Davis */
! extern void ox1(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring,
! 				int num_gene, City *city_table);
  
  /* order crossover [OX2] according to Syswerda */
! extern void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring,
! 				int num_gene, City *city_table);
  
  #endif   /* GEQO_RECOMBINATION_H */
diff --git a/src/include/optimizer/geqo_selection.h b/src/include/optimizer/geqo_selection.h
index 4b336d1..7e93cb4 100644
*** a/src/include/optimizer/geqo_selection.h
--- b/src/include/optimizer/geqo_selection.h
***************
*** 25,30 ****
  
  #include "optimizer/geqo_gene.h"
  
! extern void geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias);
  
  #endif   /* GEQO_SELECTION_H */
--- 25,32 ----
  
  #include "optimizer/geqo_gene.h"
  
! extern void geqo_selection(PlannerInfo *root,
! 						   Chromosome *momma, Chromosome *daddy,
! 						   Pool *pool, double bias);
  
  #endif   /* GEQO_SELECTION_H */
-- 
1.6.3.3.335.ge09a8