Major optimizer improvement for joining a large number of tables.

21 files changed, 277 insertions, 139 deletions

diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 52ea65abfe1..23f9e424d14 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.63 1999/02/08 04:29:03 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.64 1999/02/09 03:51:12 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1093,25 +1093,26 @@ CopyPathFields(Path *from, Path *newnode)
 
 	newnode->path_cost = from->path_cost;
 
-	newnode->path_order.ordtype = from->path_order.ordtype;
-	if (from->path_order.ordtype == SORTOP_ORDER)
+	newnode->path_order = makeNode(PathOrder);
+	newnode->path_order->ordtype = from->path_order->ordtype;
+	if (from->path_order->ordtype == SORTOP_ORDER)
 	{
 		int			len,
 					i;
-		Oid		   *ordering = from->path_order.ord.sortop;
+		Oid		   *ordering = from->path_order->ord.sortop;
 
 		if (ordering)
 		{
 			for (len = 0; ordering[len] != 0; len++)
 				;
-			newnode->path_order.ord.sortop = (Oid *) palloc(sizeof(Oid) * (len + 1));
+			newnode->path_order->ord.sortop = (Oid *) palloc(sizeof(Oid) * (len + 1));
 			for (i = 0; i < len; i++)
-				newnode->path_order.ord.sortop[i] = ordering[i];
-			newnode->path_order.ord.sortop[len] = 0;
+				newnode->path_order->ord.sortop[i] = ordering[i];
+			newnode->path_order->ord.sortop[len] = 0;
 		}
 	}
 	else
-		Node_Copy(from, newnode, path_order.ord.merge);
+		Node_Copy(from, newnode, path_order->ord.merge);
 
 	Node_Copy(from, newnode, keys);
 
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index cefe56bc6a7..bbb56fff04e 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.26 1999/02/08 04:29:04 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.27 1999/02/09 03:51:12 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -337,33 +337,33 @@ _equalPath(Path *a, Path *b)
 	/*
 	 * if (a->path_cost != b->path_cost) return(false);
 	 */
-	if (a->path_order.ordtype == SORTOP_ORDER)
+	if (a->path_order->ordtype == SORTOP_ORDER)
 	{
 		int			i = 0;
 
-		if (a->path_order.ord.sortop == NULL ||
-			b->path_order.ord.sortop == NULL)
+		if (a->path_order->ord.sortop == NULL ||
+			b->path_order->ord.sortop == NULL)
 		{
-			if (a->path_order.ord.sortop != b->path_order.ord.sortop)
+			if (a->path_order->ord.sortop != b->path_order->ord.sortop)
 				return false;
 		}
 		else
 		{
-			while (a->path_order.ord.sortop[i] != 0 &&
-				   b->path_order.ord.sortop[i] != 0)
+			while (a->path_order->ord.sortop[i] != 0 &&
+				   b->path_order->ord.sortop[i] != 0)
 			{
-				if (a->path_order.ord.sortop[i] != b->path_order.ord.sortop[i])
+				if (a->path_order->ord.sortop[i] != b->path_order->ord.sortop[i])
 					return false;
 				i++;
 			}
-			if (a->path_order.ord.sortop[i] != 0 ||
-				b->path_order.ord.sortop[i] != 0)
+			if (a->path_order->ord.sortop[i] != 0 ||
+				b->path_order->ord.sortop[i] != 0)
 				return false;
 		}
 	}
 	else
 	{
-		if (!equal(a->path_order.ord.merge, b->path_order.ord.merge))
+		if (!equal(a->path_order->ord.merge, b->path_order->ord.merge))
 			return false;
 	}
 	if (!equal(a->keys, b->keys))
@@ -433,9 +433,9 @@ _equalHashPath(HashPath *a, HashPath *b)
 		return false;
 	if (!equal((a->path_hashclauses), (b->path_hashclauses)))
 		return false;
-	if (!equal((a->outerhashkeys), (b->outerhashkeys)))
+	if (!equal(a->outerhashkeys, b->outerhashkeys))
 		return false;
-	if (!equal((a->innerhashkeys), (b->innerhashkeys)))
+	if (!equal(a->innerhashkeys, b->innerhashkeys))
 		return false;
 	return true;
 }
diff --git a/src/backend/nodes/freefuncs.c b/src/backend/nodes/freefuncs.c
index af69573055d..1a0b2ca7547 100644
--- a/src/backend/nodes/freefuncs.c
+++ b/src/backend/nodes/freefuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/Attic/freefuncs.c,v 1.2 1999/02/08 04:29:04 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/Attic/freefuncs.c,v 1.3 1999/02/09 03:51:12 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -756,13 +756,16 @@ _freeRelOptInfo(RelOptInfo * node)
 static void
 FreePathFields(Path *node)
 {
-	if (node->path_order.ordtype == SORTOP_ORDER)
+	if (node->path_order->ordtype == SORTOP_ORDER)
 	{
-		if (node->path_order.ord.sortop)
-			pfree(node->path_order.ord.sortop);
+		if (node->path_order->ord.sortop)
+			pfree(node->path_order->ord.sortop);
 	}
 	else
-		freeObject(node->path_order.ord.merge);
+		freeObject(node->path_order->ord.merge);
+
+	pfree(node->path_order);	/* is it an object, but we don't have
+								   separate free for it */
 
 	freeObject(node->keys);
 
@@ -1171,7 +1174,6 @@ freeObject(void *node)
 
 	switch (nodeTag(node))
 	{
-
 			/*
 			 * PLAN NODES
 			 */
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 19ebe881b16..aabdd88c1b1 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.15 1998/09/01 04:29:05 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.16 1999/02/09 03:51:13 momjian Exp $
  *
  * NOTES
  *	  XXX a few of the following functions are duplicated to handle
@@ -368,8 +368,8 @@ member(void *l1, List *l2)
 	List	   *i;
 
 	foreach(i, l2)
-		if (equal((Node *) (lfirst(i)), (Node *) l1))
-		return true;
+		if (equal((Node *) l1, (Node *) lfirst(i)))
+			return true;
 	return false;
 }
 
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index fd2bb20f554..ef3dccab35d 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -5,7 +5,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- *  $Id: outfuncs.c,v 1.65 1999/02/05 19:59:25 momjian Exp $
+ *  $Id: outfuncs.c,v 1.66 1999/02/09 03:51:13 momjian Exp $
  *
  * NOTES
  *	  Every (plan) node in POSTGRES has an associated "out" routine which
@@ -855,7 +855,7 @@ _outEState(StringInfo str, EState *node)
  *	Stuff from relation.h
  */
 static void
-_outRelOptInfo(StringInfo str, RelOptInfo * node)
+_outRelOptInfo(StringInfo str, RelOptInfo *node)
 {
 	appendStringInfo(str, " RELOPTINFO :relids ");
 	_outIntList(str, node->relids);
@@ -928,12 +928,44 @@ _outRowMark(StringInfo str, RowMark *node)
  *	Path is a subclass of Node.
  */
 static void
+_outPathOrder(StringInfo str, PathOrder *node)
+{
+	appendStringInfo(str, " PATHORDER :ordtype %d ",
+			node->ordtype);
+	if (node->ordtype == SORTOP_ORDER)
+	{
+		int i;
+		
+		appendStringInfo(str, " :sortop ");
+		if (node->ord.sortop == NULL)
+			appendStringInfo(str, "<>");
+		else
+		{
+			for (i=0; node->ord.sortop[i] != 0; i++)
+				appendStringInfo(str, " %d ", node->ord.sortop[i]);
+			appendStringInfo(str, " %d ", 0);
+		}
+	}
+	else
+	{
+		appendStringInfo(str, " :merge ");
+		_outNode(str,node->ord.merge);
+	}
+}
+
+/*
+ *	Path is a subclass of Node.
+ */
+static void
 _outPath(StringInfo str, Path *node)
 {
 	appendStringInfo(str, " PATH :pathtype %d :cost %f :keys ",
 			node->pathtype,
 			node->path_cost);
 	_outNode(str, node->keys);
+
+	appendStringInfo(str, " :path_order ");
+	_outNode(str, node->path_order);
 }
 
 /*
@@ -948,6 +980,9 @@ _outIndexPath(StringInfo str, IndexPath *node)
 			node->path.path_cost);
 	_outNode(str, node->path.keys);
 
+	appendStringInfo(str, " :path_order ");
+	_outNode(str, node->path.path_order);
+
 	appendStringInfo(str, " :indexid ");
 	_outIntList(str, node->indexid);
 
@@ -967,6 +1002,9 @@ _outJoinPath(StringInfo str, JoinPath *node)
 			node->path.path_cost);
 	_outNode(str, node->path.keys);
 
+	appendStringInfo(str, " :path_order ");
+	_outNode(str, node->path.path_order);
+	
 	appendStringInfo(str, " :pathinfo ");
 	_outNode(str, node->pathinfo);
 
@@ -995,6 +1033,9 @@ _outMergePath(StringInfo str, MergePath *node)
 			node->jpath.path.path_cost);
 	_outNode(str, node->jpath.path.keys);
 
+	appendStringInfo(str, " :path_order ");
+	_outNode(str, node->jpath.path.path_order);
+	
 	appendStringInfo(str, " :pathinfo ");
 	_outNode(str, node->jpath.pathinfo);
 
@@ -1032,6 +1073,9 @@ _outHashPath(StringInfo str, HashPath *node)
 			node->jpath.path.path_cost);
 	_outNode(str, node->jpath.path.keys);
 
+	appendStringInfo(str, " :path_order ");
+	_outNode(str, node->jpath.path.path_order);
+
 	appendStringInfo(str, " :pathinfo ");
 	_outNode(str, node->jpath.pathinfo);
 
@@ -1548,6 +1592,9 @@ _outNode(StringInfo str, void *obj)
 			case T_RowMark:
 				_outRowMark(str, obj);
 				break;
+			case T_PathOrder:
+				_outPathOrder(str, obj);
+				break;
 			case T_Path:
 				_outPath(str, obj);
 				break;
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index bfbd9436d3a..caebc29b1d7 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.50 1999/02/08 04:29:04 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.51 1999/02/09 03:51:13 momjian Exp $
  *
  * NOTES
  *	  Most of the read functions for plan nodes are tested. (In fact, they
@@ -37,6 +37,7 @@
 
 #include "utils/lsyscache.h"
 #include "utils/syscache.h"
+#include "catalog/pg_index.h"
 #include "catalog/pg_type.h"
 
 #include "nodes/primnodes.h"
@@ -1451,6 +1452,54 @@ _readRowMark()
 }
 
 /* ----------------
+ *		_readPathOrder
+ *
+ *	PathOrder is part of Path and it's subclasses.
+ * ----------------
+ */
+static PathOrder *
+_readPathOrder()
+{
+	PathOrder   *local_node;
+	char	   *token;
+	int			length;
+
+	local_node = makeNode(PathOrder);
+
+	token = lsptok(NULL, &length);		/* get :ordtype */
+	token = lsptok(NULL, &length);		/* now read it */
+	local_node->ordtype = atol(token);
+
+	if (local_node->ordtype == SORTOP_ORDER)
+	{
+		token = lsptok(NULL, &length);		/* get :sortop */
+
+		if (length == 0)
+			local_node->ord.sortop = NULL;
+		else
+		{
+			int i = -1;
+	
+			local_node->ord.sortop = palloc(sizeof(Oid) * (INDEX_MAX_KEYS+1));
+	
+			do {
+				i++;
+				Assert(i <= INDEX_MAX_KEYS);
+				token = lsptok(NULL, &length);	/* now read it */
+				local_node->ord.sortop[i] = strtoul(token, NULL, 10);
+			} while (local_node->ord.sortop[i] != 0);
+		}
+	}
+	else
+	{
+		token = lsptok(NULL, &length);		/* get :merge */
+		local_node->ord.merge = nodeRead(true); /* now read it */
+	}
+
+	return local_node;
+}
+
+/* ----------------
  *		_readPath
  *
  *	Path is a subclass of Node.
@@ -1473,10 +1522,8 @@ _readPath()
 	token = lsptok(NULL, &length);		/* now read it */
 	local_node->path_cost = (Cost) atof(token);
 
-#if 0
 	token = lsptok(NULL, &length);		/* get :path_order */
-	local_node->path_order = nodeRead(true);			/* now read it */
-#endif
+	local_node->path_order = nodeRead(true); /* now read it */
 
 	token = lsptok(NULL, &length);		/* get :keys */
 	local_node->keys = nodeRead(true);	/* now read it */
@@ -1507,10 +1554,8 @@ _readIndexPath()
 	token = lsptok(NULL, &length);		/* now read it */
 	local_node->path.path_cost = (Cost) atof(token);
 
-#if 0
 	token = lsptok(NULL, &length);		/* get :path_order */
-	local_node->path.path_order = nodeRead(true);		/* now read it */
-#endif
+ 	local_node->path.path_order = nodeRead(true);		/* now read it */
 
 	token = lsptok(NULL, &length);		/* get :keys */
 	local_node->path.keys = nodeRead(true);		/* now read it */
@@ -1548,10 +1593,8 @@ _readJoinPath()
 	token = lsptok(NULL, &length);		/* now read it */
 	local_node->path.path_cost = (Cost) atof(token);
 
-#if 0
 	token = lsptok(NULL, &length);		/* get :path_order */
 	local_node->path.path_order = nodeRead(true);		/* now read it */
-#endif
 
 	token = lsptok(NULL, &length);		/* get :keys */
 	local_node->path.keys = nodeRead(true);		/* now read it */
@@ -1615,10 +1658,8 @@ _readMergePath()
 
 	local_node->jpath.path.path_cost = (Cost) atof(token);
 
-#if 0
 	token = lsptok(NULL, &length);		/* get :path_order */
 	local_node->jpath.path.path_order = nodeRead(true); /* now read it */
-#endif
 
 	token = lsptok(NULL, &length);		/* get :keys */
 	local_node->jpath.path.keys = nodeRead(true);		/* now read it */
@@ -1691,10 +1732,8 @@ _readHashPath()
 
 	local_node->jpath.path.path_cost = (Cost) atof(token);
 
-#if 0
 	token = lsptok(NULL, &length);		/* get :path_order */
 	local_node->jpath.path.path_order = nodeRead(true); /* now read it */
-#endif
 
 	token = lsptok(NULL, &length);		/* get :keys */
 	local_node->jpath.path.keys = nodeRead(true);		/* now read it */
@@ -2071,6 +2110,8 @@ parsePlanString(void)
 		return_value = _readTargetEntry();
 	else if (!strncmp(token, "RTE", length))
 		return_value = _readRangeTblEntry();
+	else if (!strncmp(token, "PATHORDER", length))
+		return_value = _readPathOrder();
 	else if (!strncmp(token, "PATH", length))
 		return_value = _readPath();
 	else if (!strncmp(token, "INDEXPATH", length))
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index 18b534191e3..65c95884201 100644
--- a/src/backend/optimizer/README
+++ b/src/backend/optimizer/README
@@ -1,10 +1,56 @@
+Summary
+-------
+
 The optimizer generates optimial query plans by doing several steps:
 
-Take each relation in a query, and make a RelOptInfo structure for it. 
+1) Take each relation in a query, and make a RelOptInfo structure for it. 
 Find each way of accessing the relation, called a Path, including
 sequential and index scans, and add it to the RelOptInfo.path_order
 list.
 
+2) Join each RelOptInfo to each other RelOptInfo as specified in the
+WHERE clause.  At this point each RelOptInfo is a single relation, so
+you are joining every relation to every relation it is joined to in the
+WHERE clause.
+
+Joins occur using two RelOptInfos.  One is outer, the other inner. 
+Outers drive lookups of values in the inner.  In a nested loop, lookups
+of values in the inner occur by scanning to find each matching inner
+row.  In a mergejoin, inner rows are ordered, and are accessed in order,
+so only one scan of inner is required to perform the entire join.  In a
+hashjoin, inner rows are hashed for lookups.
+
+Each unique join combination becomes a new RelOptInfo.  The RelOptInfo
+is now the joining of two relations.  RelOptInfo.path_order are various
+paths to create the joined result, having different orderings depending
+on the join method used.
+
+3) At this point, every RelOptInfo is joined to each other again, with
+a new relation added to each RelOptInfo.  This continues until all
+relations have been joined into one RelOptInfo, and the cheapest Path is
+chosen.
+
+	SELECT 	*
+	FROM 	tab1, tab2, tab3, tab4
+	WHERE 	tab1.col = tab2.col AND
+		tab2.col = tab3.col AND
+		tab3.col = tab4.col
+
+	Tables 1, 2, 3, and 4 are joined as:
+	{1 2},{2 3},{3 4}
+	{1 2 3},{2 3 4}
+	{1 2 3 4}
+
+	SELECT 	*
+	FROM 	tab1, tab2, tab3, tab4
+	WHERE 	tab1.col = tab2.col AND
+		tab1.col = tab3.col AND
+		tab1.col = tab4.col
+
+	Tables 1, 2, 3, and 4 are joined as:
+	{1 2},{1 3},{1 4}
+	{1 2 3},{1 3 4},{1,2,4}
+	{1 2 3 4}
 
 Optimizer Functions
 -------------------
@@ -56,28 +102,6 @@ planner()
      one relation, return
      find selectivity of columns used in joins
 -----find_join_paths()
-      Summary:  With OPTIMIZER_DEBUG defined, you see:
-
-      Tables 1, 2, 3, and 4 are joined as:
-         {1 2},{1 3},{1 4},{2 3},{2 4}
-         {1 2 3},{1 2 4},{2 3 4}
-         {1 2 3 4}
-
-      Actual output tests show combinations:
-         {4 2},{3 2},{1 4},{1 3},{1 2}
-         {4 2 3},{1 4 2},{1 3 2}
-         {4 2 3 1}
-
-      Cheapest join order shows:
-         {4 2},{3 2},{1 4},{1 3},{1 2}
-         {3 2 4},{1 4 2},{1 3 2}
-         {1 4 2 3}
-
-      It first finds the best way to join each table to every other
-      table.  It then takes those joined table combinations, and joins
-      them to the other joined table combinations, until all tables are
-      joined.
-
       jump to geqo if needed
       again:
        find_join_rels():
diff --git a/src/backend/optimizer/geqo/geqo_paths.c b/src/backend/optimizer/geqo/geqo_paths.c
index 9d80ff67f63..3cd518c26d6 100644
--- a/src/backend/optimizer/geqo/geqo_paths.c
+++ b/src/backend/optimizer/geqo/geqo_paths.c
@@ -5,7 +5,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: geqo_paths.c,v 1.13 1999/02/08 04:29:06 momjian Exp $
+ * $Id: geqo_paths.c,v 1.14 1999/02/09 03:51:15 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -113,7 +113,7 @@ geqo_rel_paths(RelOptInfo * rel)
 	{
 		path = (Path *) lfirst(y);
 
-		if (!path->path_order.ord.sortop)
+		if (!path->path_order->ord.sortop)
 			break;
 	}
 
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 9040b32ccf8..770614eec04 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.39 1999/02/08 04:29:08 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.40 1999/02/09 03:51:17 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1290,8 +1290,9 @@ index_innerjoin(Query *root, RelOptInfo * rel, List *clausegroup_list,
 
 		pathnode->path.pathtype = T_IndexScan;
 		pathnode->path.parent = rel;
-	    pathnode->path.path_order.ordtype = SORTOP_ORDER;
-	    pathnode->path.path_order.ord.sortop = index->ordering;
+		pathnode->path.path_order = makeNode(PathOrder);
+	    pathnode->path.path_order->ordtype = SORTOP_ORDER;
+	    pathnode->path.path_order->ord.sortop = index->ordering;
 	    pathnode->path.keys = NIL;	/* not sure about this, bjm 1998/09/21 */
 
 		pathnode->indexid = index->relids;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index d57b861de2a..76b4fd81e8f 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.15 1999/02/08 04:29:11 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.16 1999/02/09 03:51:19 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -324,11 +324,11 @@ match_unsorted_outer(RelOptInfo * joinrel,
 		List	   *clauses = NIL;
 		List	   *matchedJoinKeys = NIL;
 		List	   *matchedJoinClauses = NIL;
-		MergeInfo	   *xmergeinfo = (MergeInfo *) NULL;
+		MergeInfo  *xmergeinfo = (MergeInfo *) NULL;
 
 		outerpath = (Path *) lfirst(i);
 
-		outerpath_ordering = &outerpath->path_order;
+		outerpath_ordering = outerpath->path_order;
 
 		if (outerpath_ordering)
 		{
@@ -464,14 +464,14 @@ match_unsorted_inner(RelOptInfo * joinrel,
 
 	foreach(i, innerpath_list)
 	{
-		MergeInfo	   *xmergeinfo = (MergeInfo *) NULL;
+		MergeInfo  *xmergeinfo = (MergeInfo *) NULL;
 		List	   *clauses = NIL;
 		List	   *matchedJoinKeys = NIL;
 		List	   *matchedJoinClauses = NIL;
 
 		innerpath = (Path *) lfirst(i);
 
-		innerpath_ordering = &innerpath->path_order;
+		innerpath_ordering = innerpath->path_order;
 
 		if (innerpath_ordering)
 		{
diff --git a/src/backend/optimizer/path/joinutils.c b/src/backend/optimizer/path/joinutils.c
index d90097404a8..8dc1ecb1771 100644
--- a/src/backend/optimizer/path/joinutils.c
+++ b/src/backend/optimizer/path/joinutils.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/joinutils.c,v 1.11 1999/02/08 04:29:12 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/joinutils.c,v 1.12 1999/02/09 03:51:20 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -218,8 +218,7 @@ match_paths_joinkeys(List *joinkeys,
 
 		key_match = every_func(joinkeys, path->keys, which_subkey);
 
-		if (equal_path_ordering(ordering,
-								&path->path_order) &&
+		if (equal_path_ordering(ordering, path->path_order) &&
 			length(joinkeys) == length(path->keys) &&
 			key_match)
 		{
diff --git a/src/backend/optimizer/path/mergeutils.c b/src/backend/optimizer/path/mergeutils.c
index d4d20dd5495..70c230aef3a 100644
--- a/src/backend/optimizer/path/mergeutils.c
+++ b/src/backend/optimizer/path/mergeutils.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/mergeutils.c,v 1.14 1999/02/08 04:29:12 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/mergeutils.c,v 1.15 1999/02/09 03:51:20 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -52,16 +52,17 @@ group_clauses_by_order(List *restrictinfo_list,
 			 * Create a new mergeinfo node and add it to 'mergeinfo-list'
 			 * if one does not yet exist for this merge ordering.
 			 */
-			PathOrder	path_order;
-			MergeInfo	   *xmergeinfo;
+			PathOrder	*path_order;
+			MergeInfo	*xmergeinfo;
 			Expr	   *clause = restrictinfo->clause;
 			Var		   *leftop = get_leftop(clause);
 			Var		   *rightop = get_rightop(clause);
 			JoinKey    *keys;
 
-			path_order.ordtype = MERGE_ORDER;
-			path_order.ord.merge = merge_ordering;
-			xmergeinfo = match_order_mergeinfo(&path_order, mergeinfo_list);
+			path_order = makeNode(PathOrder);
+			path_order->ordtype = MERGE_ORDER;
+			path_order->ord.merge = merge_ordering;
+			xmergeinfo = match_order_mergeinfo(path_order, mergeinfo_list);
 			if (inner_relid == leftop->varno)
 			{
 				keys = makeNode(JoinKey);
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index 5cfb5e00dd7..1414a3f8237 100644
--- a/src/backend/optimizer/path/orindxpath.c
+++ b/src/backend/optimizer/path/orindxpath.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.15 1999/02/08 04:29:12 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.16 1999/02/09 03:51:20 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -104,13 +104,14 @@ create_or_index_paths(Query *root,
 
 				pathnode->path.pathtype = T_IndexScan;
 				pathnode->path.parent = rel;
-			    pathnode->path.path_order.ordtype = SORTOP_ORDER;
+				pathnode->path.path_order = makeNode(PathOrder);
+			    pathnode->path.path_order->ordtype = SORTOP_ORDER;
 			    /*
 				 *	This is an IndexScan, but it does index lookups based
 				 *	on the order of the fields specified in the WHERE clause,
 				 *	not in any order, so the sortop is NULL.
 				 */
-			    pathnode->path.path_order.ord.sortop = NULL;
+			    pathnode->path.path_order->ord.sortop = NULL;
 			    pathnode->path.keys = NIL;	/* not sure about this, bjm 1998/09/21 */
 
 				pathnode->indexqual = lcons(clausenode, NIL);
diff --git a/src/backend/optimizer/path/prune.c b/src/backend/optimizer/path/prune.c
index e3cbaec7d5a..2a4ba783c00 100644
--- a/src/backend/optimizer/path/prune.c
+++ b/src/backend/optimizer/path/prune.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.24 1999/02/08 04:29:12 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.25 1999/02/09 03:51:21 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -109,7 +109,7 @@ prune_rel_paths(List *rel_list)
 		{
 			path = (Path *) lfirst(y);
 
-			if (!path->path_order.ord.sortop)
+			if (!path->path_order->ord.sortop)
 				break;
 		}
 		cheapest = (JoinPath *) prune_rel_path(rel, path);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 0d16d2b5b25..8df92e7edd8 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.38 1999/02/08 04:29:17 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.39 1999/02/09 03:51:21 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -529,14 +529,14 @@ create_mergejoin_node(MergePath *best_path,
 												outer_tlist,
 												inner_tlist));
 
-	opcode = get_opcode((best_path->jpath.path.path_order.ord.merge)->join_operator);
+	opcode = get_opcode((best_path->jpath.path.path_order->ord.merge)->join_operator);
 
 	outer_order = (Oid *) palloc(sizeof(Oid) * 2);
-	outer_order[0] = (best_path->jpath.path.path_order.ord.merge)->left_operator;
+	outer_order[0] = (best_path->jpath.path.path_order->ord.merge)->left_operator;
 	outer_order[1] = 0;
 
 	inner_order = (Oid *) palloc(sizeof(Oid) * 2);
-	inner_order[0] = (best_path->jpath.path.path_order.ord.merge)->right_operator;
+	inner_order[0] = (best_path->jpath.path.path_order->ord.merge)->right_operator;
 	inner_order[1] = 0;
 
 	/*
@@ -825,7 +825,6 @@ set_temp_tlist_operators(List *tlist, List *pathkeys, Oid *operators)
 		resdom = tlist_member((Var *) keys, tlist);
 		if (resdom)
 		{
-
 			/*
 			 * Order the resdom keys and replace the operator OID for each
 			 * key with the regproc OID.
diff --git a/src/backend/optimizer/util/keys.c b/src/backend/optimizer/util/keys.c
index 685e01cbafd..0b89db898bc 100644
--- a/src/backend/optimizer/util/keys.c
+++ b/src/backend/optimizer/util/keys.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.10 1999/02/01 04:20:50 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.11 1999/02/09 03:51:26 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -125,7 +125,7 @@ samekeys(List *keys1, List *keys2)
 
 	for (key1 = keys1, key2 = keys2; key1 != NIL && key2 != NIL;
 		 key1 = lnext(key1), key2 = lnext(key2))
-		if (!member(lfirst(key1), lfirst(key2)))
+		if (!member(lfirst((List *)lfirst(key1)), lfirst(key2)))
 			return false;
 
 	/* Now the result should be true if list keys2 has at least as many
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index cf48ecc6819..82dc20f5455 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.20 1999/02/08 04:29:21 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.21 1999/02/09 03:51:27 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -164,9 +164,31 @@ better_path(Path *new_path, List *unique_paths, bool *noOther)
 	{
 		path = (Path *) lfirst(temp);
 
+#ifdef OPTDUP_DEBUG
+		if (!samekeys(path->keys, new_path->keys))
+		{
+			printf("oldpath\n");
+			pprint(path->keys);
+			printf("newpath\n");
+			pprint(new_path->keys);
+			if (path->keys && new_path->keys &&
+				length(lfirst(path->keys)) >= 2 &&
+				length(lfirst(path->keys)) < length(lfirst(new_path->keys)))
+				sleep(0); /* set breakpoint here */
+		}
+		if (!equal_path_ordering(path->path_order,
+								new_path->path_order))
+		{
+			printf("oldord\n");
+			pprint(path->path_order);
+			printf("neword\n");
+			pprint(new_path->path_order);
+		}
+#endif
+		
 		if (samekeys(path->keys, new_path->keys) &&
-			equal_path_ordering(&path->path_order,
-								&new_path->path_order))
+			equal_path_ordering(path->path_order,
+								new_path->path_order))
 		{
 			old_path = path;
 			break;
@@ -207,8 +229,9 @@ create_seqscan_path(RelOptInfo * rel)
 	pathnode->pathtype = T_SeqScan;
 	pathnode->parent = rel;
 	pathnode->path_cost = 0.0;
-	pathnode->path_order.ordtype = SORTOP_ORDER;
-	pathnode->path_order.ord.sortop = NULL;
+	pathnode->path_order = makeNode(PathOrder);
+	pathnode->path_order->ordtype = SORTOP_ORDER;
+	pathnode->path_order->ord.sortop = NULL;
 	pathnode->keys = NIL;
 
 	/*
@@ -256,8 +279,9 @@ create_index_path(Query *root,
 
 	pathnode->path.pathtype = T_IndexScan;
 	pathnode->path.parent = rel;
-	pathnode->path.path_order.ordtype = SORTOP_ORDER;
-	pathnode->path.path_order.ord.sortop = index->ordering;
+	pathnode->path.path_order = makeNode(PathOrder);
+	pathnode->path.path_order->ordtype = SORTOP_ORDER;
+	pathnode->path.path_order->ord.sortop = index->ordering;
 
 	pathnode->indexid = index->relids;
 	pathnode->indexkeys = index->indexkeys;
@@ -274,7 +298,7 @@ create_index_path(Query *root,
 	 * The index must have an ordering for the path to have (ordering)
 	 * keys, and vice versa.
 	 */
-	if (pathnode->path.path_order.ord.sortop)
+	if (pathnode->path.path_order->ord.sortop)
 	{
 		pathnode->path.keys = collect_index_pathkeys(index->indexkeys,
 													 rel->targetlist);
@@ -286,7 +310,7 @@ create_index_path(Query *root,
 		 * if no index keys were found, we can't order the path).
 		 */
 		if (pathnode->path.keys == NULL)
-			pathnode->path.path_order.ord.sortop = NULL;
+			pathnode->path.path_order->ord.sortop = NULL;
 	}
 	else
 		pathnode->path.keys = NULL;
@@ -412,23 +436,20 @@ create_nestloop_path(RelOptInfo * joinrel,
 	pathnode->path.joinid = NIL;
 	pathnode->path.outerjoincost = (Cost) 0.0;
 	pathnode->path.loc_restrictinfo = NIL;
-
+	pathnode->path.path_order = makeNode(PathOrder);
+	
 	if (keys)
 	{
-		pathnode->path.path_order.ordtype = outer_path->path_order.ordtype;
-		if (outer_path->path_order.ordtype == SORTOP_ORDER)
-		{
-			pathnode->path.path_order.ord.sortop = outer_path->path_order.ord.sortop;
-		}
+		pathnode->path.path_order->ordtype = outer_path->path_order->ordtype;
+		if (outer_path->path_order->ordtype == SORTOP_ORDER)
+			pathnode->path.path_order->ord.sortop = outer_path->path_order->ord.sortop;
 		else
-		{
-			pathnode->path.path_order.ord.merge = outer_path->path_order.ord.merge;
-		}
+			pathnode->path.path_order->ord.merge = outer_path->path_order->ord.merge;
 	}
 	else
 	{
-		pathnode->path.path_order.ordtype = SORTOP_ORDER;
-		pathnode->path.path_order.ord.sortop = NULL;
+		pathnode->path.path_order->ordtype = SORTOP_ORDER;
+		pathnode->path.path_order->ord.sortop = NULL;
 	}
 
 	pathnode->path.path_cost = cost_nestloop(outer_path->path_cost,
@@ -487,8 +508,9 @@ create_mergejoin_path(RelOptInfo * joinrel,
 	pathnode->jpath.innerjoinpath = inner_path;
 	pathnode->jpath.pathinfo = joinrel->restrictinfo;
 	pathnode->jpath.path.keys = keys;
-	pathnode->jpath.path.path_order.ordtype = MERGE_ORDER;
-	pathnode->jpath.path.path_order.ord.merge = order;
+	pathnode->jpath.path.path_order = makeNode(PathOrder);
+	pathnode->jpath.path.path_order->ordtype = MERGE_ORDER;
+	pathnode->jpath.path.path_order->ord.merge = order;
 	pathnode->path_mergeclauses = mergeclauses;
 	pathnode->jpath.path.loc_restrictinfo = NIL;
 	pathnode->outersortkeys = outersortkeys;
@@ -552,8 +574,9 @@ create_hashjoin_path(RelOptInfo * joinrel,
 	pathnode->jpath.pathinfo = joinrel->restrictinfo;
 	pathnode->jpath.path.loc_restrictinfo = NIL;
 	pathnode->jpath.path.keys = keys;
-	pathnode->jpath.path.path_order.ordtype = SORTOP_ORDER;
-	pathnode->jpath.path.path_order.ord.sortop = NULL;
+	pathnode->jpath.path.path_order = makeNode(PathOrder);
+	pathnode->jpath.path.path_order->ordtype = SORTOP_ORDER;
+	pathnode->jpath.path.path_order->ord.sortop = NULL;
 	pathnode->jpath.path.outerjoincost = (Cost) 0.0;
 	pathnode->jpath.path.joinid = (Relid) NULL;
 	/* pathnode->hashjoinoperator = operator;  */
diff --git a/src/backend/parser/gram.c b/src/backend/parser/gram.c
index fde0741c59b..5df3bb6b223 100644
--- a/src/backend/parser/gram.c
+++ b/src/backend/parser/gram.c
@@ -240,7 +240,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/parser/Attic/gram.c,v 2.69 1999/02/07 19:04:59 wieck Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/parser/Attic/gram.c,v 2.70 1999/02/09 03:51:30 momjian Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -4802,7 +4802,7 @@ static const short yycheck[] = {     3,
     -1,    -1,    -1,    -1,    -1,    -1,    -1,    -1,    -1,   215
 };
 /* -*-C-*-  Note some compilers choke on comments on `#line' lines.  */
-#line 3 "/usr/share/bison.simple"
+#line 3 "/usr/local/bison/bison.simple"
 
 /* Skeleton output parser for bison,
    Copyright (C) 1984, 1989, 1990 Free Software Foundation, Inc.
@@ -4951,13 +4951,9 @@ int yydebug;			/*  nonzero means print parse trace	*/
 #define YYMAXDEPTH 10000
 #endif
 
-#ifndef YYPARSE_RETURN_TYPE
-#define YYPARSE_RETURN_TYPE int
-#endif
-
 /* Prevent warning if -Wstrict-prototypes.  */
 #ifdef __GNUC__
-YYPARSE_RETURN_TYPE yyparse (void);
+int yyparse (void);
 #endif
 
 #if __GNUC__ > 1		/* GNU C and GNU C++ define this.  */
@@ -4999,7 +4995,7 @@ __yy_memcpy (char *to, char *from, int count)
 #endif
 #endif
 
-#line 196 "/usr/share/bison.simple"
+#line 196 "/usr/local/bison/bison.simple"
 
 /* The user can define YYPARSE_PARAM as the name of an argument to be passed
    into yyparse.  The argument should have type void *.
@@ -5020,7 +5016,7 @@ __yy_memcpy (char *to, char *from, int count)
 #define YYPARSE_PARAM_DECL
 #endif /* not YYPARSE_PARAM */
 
-YYPARSE_RETURN_TYPE
+int
 yyparse(YYPARSE_PARAM_ARG)
      YYPARSE_PARAM_DECL
 {
@@ -11126,7 +11122,7 @@ case 969:
     break;}
 }
    /* the action file gets copied in in place of this dollarsign */
-#line 498 "/usr/share/bison.simple"
+#line 498 "/usr/local/bison/bison.simple"
 
   yyvsp -= yylen;
   yyssp -= yylen;
diff --git a/src/backend/parser/scan.c b/src/backend/parser/scan.c
index b2594639121..4ef045c4651 100644
--- a/src/backend/parser/scan.c
+++ b/src/backend/parser/scan.c
@@ -1,7 +1,7 @@
 /* A lexical scanner generated by flex */
 
 /* Scanner skeleton version:
- * $Header: /cvsroot/pgsql/src/backend/parser/Attic/scan.c,v 1.33 1999/02/07 23:58:52 tgl Exp $
+ * /master/usr.bin/lex/skel.c,v 1.3 1997/09/25 00:10:23 jch Exp
  */
 
 #define FLEX_SCANNER
@@ -556,7 +556,7 @@ char *yytext;
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/parser/Attic/scan.c,v 1.33 1999/02/07 23:58:52 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/parser/Attic/scan.c,v 1.34 1999/02/09 03:51:39 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 2635f1d7603..4ce89d0e4e8 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nodes.h,v 1.39 1999/02/06 16:50:31 wieck Exp $
+ * $Id: nodes.h,v 1.40 1999/02/09 03:51:41 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -71,6 +71,7 @@ typedef enum NodeTag
 	 *---------------------
 	 */
 	T_RelOptInfo = 200,
+	T_PathOrder,
 	T_Path,
 	T_IndexPath,
 	T_JoinPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index aaee1637cf3..7df407f5671 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.16 1999/02/08 04:29:25 momjian Exp $
+ * $Id: relation.h,v 1.17 1999/02/09 03:51:42 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -127,6 +127,8 @@ typedef enum OrderType
 
 typedef struct PathOrder
 {
+	NodeTag		type;
+
 	OrderType	ordtype;
 	union
 	{
@@ -144,9 +146,9 @@ typedef struct Path
 
 	NodeTag		pathtype;
 
-	PathOrder	path_order;
+	PathOrder	*path_order;
 
-	List	   *keys;
+	List	   *keys;		/* this is a List of List of keys */
 	Cost		outerjoincost;
 	Relid		joinid;
 	List	   *loc_restrictinfo;