Postgres95 1.01 Distribution - Virgin SourcesPG95-1_01

13 files changed, 3545 insertions, 0 deletions

diff --git a/src/backend/optimizer/util/Makefile.inc b/src/backend/optimizer/util/Makefile.inc
new file mode 100644
index 00000000000..18955d282c8
--- /dev/null
+++ b/src/backend/optimizer/util/Makefile.inc
@@ -0,0 +1,15 @@
+#-------------------------------------------------------------------------
+#
+# Makefile.inc--
+#    Makefile for optimizer/util
+#
+# Copyright (c) 1994, Regents of the University of California
+#
+#
+# IDENTIFICATION
+#    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/Makefile.inc,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+#
+#-------------------------------------------------------------------------
+
+SUBSRCS+= clauseinfo.c clauses.c indexnode.c internal.c plancat.c \
+	joininfo.c keys.c ordering.c pathnode.c relnode.c tlist.c var.c
diff --git a/src/backend/optimizer/util/clauseinfo.c b/src/backend/optimizer/util/clauseinfo.c
new file mode 100644
index 00000000000..1ab747ee176
--- /dev/null
+++ b/src/backend/optimizer/util/clauseinfo.c
@@ -0,0 +1,187 @@
+/*-------------------------------------------------------------------------
+ *
+ * clauseinfo.c--
+ *    ClauseInfo node manipulation routines.
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/clauseinfo.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/relation.h"
+#include "nodes/nodeFuncs.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/clauses.h"
+#include "optimizer/clauseinfo.h"
+
+/*    
+ * valid-or-clause--
+ *    
+ * Returns t iff the clauseinfo node contains a 'normal' 'or' clause.
+ *    
+ */
+bool
+valid_or_clause(CInfo *clauseinfo)
+{
+     if (clauseinfo != NULL && 
+	 !single_node((Node*)clauseinfo->clause) && 
+	 !clauseinfo->notclause &&
+	 or_clause((Node*)clauseinfo->clause)) 
+       return(true);
+     else
+       return(false);
+}
+
+/*    
+ * get-actual-clauses--
+ *    
+ * Returns a list containing the clauses from 'clauseinfo-list'.
+ *    
+ */
+List *
+get_actual_clauses(List *clauseinfo_list)
+{
+    List *temp = NIL;
+    List *result = NIL;
+    CInfo *clause = (CInfo *)NULL;
+
+    foreach(temp,clauseinfo_list) {
+	clause = (CInfo *)lfirst(temp);
+	result = lappend(result,clause->clause);
+    }
+    return(result);
+}
+
+/*    
+ * XXX NOTE:
+ *  	The following routines must return their contents in the same order
+ *    	(e.g., the first clause's info should be first, and so on) or else
+ *    	get_index_sel() won't work.
+ *    
+ */
+
+/*    
+ * get_relattvals--
+ *    For each member of  a list of clauseinfo nodes to be used with an
+ *    index, create a vectori-long specifying:
+ *    		the attnos,
+ *    		the values of the clause constants, and 
+ *    		flags indicating the type and location of the constant within
+ *    			each clause.
+ *    Each clause is of the form (op var some_type_of_constant), thus the
+ *    flag indicating whether the constant is on the left or right should
+ *    always be *SELEC-CONSTANT-RIGHT*.
+ *    
+ * 'clauseinfo-list' is a list of clauseinfo nodes
+ *    
+ * Returns a list of vectori-longs.
+ *    
+ */
+void
+get_relattvals(List *clauseinfo_list,
+	       List **attnos,
+	       List **values,
+	       List **flags)
+{
+    List *result1 = NIL;
+    List *result2 = NIL;
+    List *result3 = NIL;
+    CInfo *temp = (CInfo *)NULL;
+    List *i = NIL;
+
+    foreach (i,clauseinfo_list) {
+	int dummy;
+	AttrNumber attno;
+	Datum constval;
+	int flag;
+
+	temp = (CInfo *)lfirst(i);
+	get_relattval((Node*)temp->clause, &dummy, &attno, &constval, &flag);
+	result1 = lappendi(result1, attno);
+	result2 = lappendi(result2, constval);
+	result3 = lappendi(result3, flag);
+    }
+
+    *attnos = result1;
+    *values = result2;
+    *flags = result3;
+    return;
+}
+
+/*    
+ * get_joinvars --
+ *    Given a list of join clauseinfo nodes to be used with the index
+ *    of an inner join relation, return three lists consisting of:
+ *    		the attributes corresponding to the inner join relation
+ *    		the value of the inner var clause (always "")
+ *    		whether the attribute appears on the left or right side of
+ *    			the operator.
+ *    
+ * 'relid' is the inner join relation
+ * 'clauseinfo-list' is a list of qualification clauses to be used with
+ * 	'rel'
+ *    
+ */
+void
+get_joinvars(Oid relid,
+	     List *clauseinfo_list,
+	     List **attnos,
+	     List **values,
+	     List **flags)
+{
+    List *result1 = NIL;
+    List *result2 = NIL;
+    List *result3 = NIL;
+    List *temp;
+     
+    foreach(temp, clauseinfo_list) {
+	CInfo *clauseinfo = lfirst(temp);
+	Expr *clause = clauseinfo->clause;
+
+	if( IsA (get_leftop(clause),Var) &&
+	   (relid == (get_leftop(clause))->varno)) {
+
+	    result1 = lappendi(result1, (get_leftop(clause))->varattno);
+	    result2 = lappend(result2, "");
+	    result3 = lappendi(result3, _SELEC_CONSTANT_RIGHT_);
+	} else {
+	    result1 = lappendi(result1, (get_rightop(clause))->varattno);
+	    result2 = lappend(result2, "");
+	    result3 = lappendi(result3, _SELEC_CONSTANT_LEFT_);
+	}
+    }
+    *attnos = result1;
+    *values = result2;
+    *flags = result3;
+    return;
+}
+
+/*    
+ * get_opnos--
+ *    Create and return a list containing the clause operators of each member
+ *    of a list of clauseinfo nodes to be used with an index.
+ *    
+ */
+List *
+get_opnos(List *clauseinfo_list)
+{
+    CInfo *temp = (CInfo *)NULL;
+    List *result = NIL;
+    List *i = NIL;
+
+    foreach(i,clauseinfo_list) {
+	temp = (CInfo *)lfirst(i);
+	result =
+	    lappendi(result,
+		     (((Oper*)temp->clause->oper)->opno));
+    }
+    return(result);
+}
+
+
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
new file mode 100644
index 00000000000..daba4d8fdb0
--- /dev/null
+++ b/src/backend/optimizer/util/clauses.c
@@ -0,0 +1,736 @@
+/*-------------------------------------------------------------------------
+ *
+ * clauses.c--
+ *    routines to manipulate qualification clauses
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ * HISTORY
+ *    AUTHOR		DATE		MAJOR EVENT
+ *    Andrew Yu		Nov 3, 1994	clause.c and clauses.c combined
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "nodes/pg_list.h"
+#include "nodes/primnodes.h"
+#include "nodes/relation.h"
+#include "nodes/parsenodes.h"
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+
+#include "catalog/pg_aggregate.h"
+
+#include "utils/elog.h"
+#include "utils/syscache.h"
+#include "utils/lsyscache.h"
+
+#include "optimizer/clauses.h"
+#include "optimizer/internal.h"
+#include "optimizer/var.h"
+
+
+Expr *
+make_clause(int type, Node *oper, List *args)
+{
+    if (type == AND_EXPR || type == OR_EXPR || type == NOT_EXPR ||
+	type == OP_EXPR || type == FUNC_EXPR) {
+	Expr *expr = makeNode(Expr);
+
+	/*
+	 * assume type checking already done and we don't need the type of
+	 * the expr any more.
+	 */
+	expr->typeOid = InvalidOid;
+	expr->opType = type;
+	expr->oper = oper;	/* ignored for AND, OR, NOT */
+	expr->args = args;
+	return expr;
+    }else {
+	/* will this ever happen? translated from lispy C code - ay 10/94 */
+	return((Expr*)args);
+    }
+}
+
+
+/*****************************************************************************
+ *	OPERATOR clause functions
+ *****************************************************************************/
+
+
+/*    
+ * is_opclause--
+ *    
+ * Returns t iff the clause is an operator clause:
+ *    		(op expr expr) or (op expr).
+ *
+ * [historical note: is_clause has the exact functionality and is used
+ *	throughout the code. They're renamed to is_opclause for clarity.
+ *						- ay 10/94.]
+ */
+bool
+is_opclause(Node *clause)
+{
+    return 
+	(clause!=NULL &&
+	 nodeTag(clause)==T_Expr && ((Expr*)clause)->opType==OP_EXPR);
+}
+
+/*    
+ * make_opclause--
+ *    Creates a clause given its operator left operand and right
+ *    operand (if it is non-null).
+ *    
+ */
+Expr *
+make_opclause(Oper *op, Var *leftop, Var *rightop)
+{
+    Expr *expr = makeNode(Expr);
+
+    expr->typeOid = InvalidOid;	/* assume type checking done */
+    expr->opType = OP_EXPR;
+    expr->oper = (Node*)op;
+    expr->args = makeList(leftop, rightop, -1);
+    return expr;
+}
+
+/*    
+ * get_leftop--
+ *    
+ * Returns the left operand of a clause of the form (op expr expr)
+ *   	or (op expr)
+ * NB: it is assumed (for now) that all expr must be Var nodes    
+ */
+Var *
+get_leftop(Expr *clause)
+{
+    if (clause->args!=NULL)
+	return(lfirst(clause->args));
+    else
+	return NULL;
+}
+
+/*    
+ * get_rightop
+ *    
+ * Returns the right operand in a clause of the form (op expr expr).
+ *    
+ */
+Var *
+get_rightop(Expr *clause)
+{
+    if (clause->args!=NULL && lnext(clause->args)!=NULL)
+	return (lfirst(lnext(clause->args)));
+    else
+	return NULL;
+}
+
+/*****************************************************************************
+ *    	AGG clause functions
+ *****************************************************************************/
+
+bool
+agg_clause(Node *clause)
+{
+    return
+	(clause!=NULL && nodeTag(clause)==T_Aggreg);
+}
+
+/*****************************************************************************
+ *    	FUNC clause functions
+ *****************************************************************************/
+
+/*    
+ * is_funcclause--
+ *    
+ * Returns t iff the clause is a function clause: (func { expr }).
+ *    
+ */
+bool
+is_funcclause(Node *clause)
+{
+    return
+	(clause!=NULL &&
+	 nodeTag(clause)==T_Expr && ((Expr*)clause)->opType==FUNC_EXPR);
+}
+
+/*    
+ * make_funcclause--
+ *    
+ * Creates a function clause given the FUNC node and the functional
+ * arguments.
+ *    
+ */
+Expr *
+make_funcclause(Func *func, List *funcargs)
+{
+    Expr *expr = makeNode(Expr);
+
+    expr->typeOid = InvalidOid;	/* assume type checking done */
+    expr->opType = FUNC_EXPR;
+    expr->oper = (Node*)func;
+    expr->args = funcargs;
+    return expr;
+}
+
+/*****************************************************************************
+ *    	OR clause functions
+ *****************************************************************************/
+
+/*    
+ * or_clause--
+ *    
+ * Returns t iff the clause is an 'or' clause: (OR { expr }).
+ *    
+ */
+bool
+or_clause(Node *clause)
+{
+    return
+	(clause!=NULL &&
+	 nodeTag(clause)==T_Expr && ((Expr*)clause)->opType==OR_EXPR);
+}
+
+/*    
+ * make_orclause--
+ *    
+ * Creates an 'or' clause given a list of its subclauses.
+ *    
+ */
+Expr *
+make_orclause(List *orclauses)
+{
+    Expr *expr = makeNode(Expr);
+
+    expr->typeOid = InvalidOid;	/* assume type checking done */
+    expr->opType = OR_EXPR;
+    expr->oper = NULL;
+    expr->args = orclauses;
+    return expr;
+}
+
+/*****************************************************************************
+ *    	NOT clause functions
+ *****************************************************************************/
+
+/*    
+ * not_clause--
+ *    
+ * Returns t iff this is a 'not' clause: (NOT expr).
+ *    
+ */
+bool
+not_clause(Node *clause)
+{
+    return
+	(clause!=NULL &&
+	 nodeTag(clause)==T_Expr && ((Expr*)clause)->opType == NOT_EXPR);
+}
+
+/*    
+ * make_notclause--
+ *    
+ * Create a 'not' clause given the expression to be negated.
+ *    
+ */
+Expr *
+make_notclause(Expr *notclause)
+{
+    Expr *expr = makeNode(Expr);
+
+    expr->typeOid = InvalidOid;	/* assume type checking done */
+    expr->opType = NOT_EXPR;
+    expr->oper = NULL;
+    expr->args = lcons(notclause, NIL);
+    return expr;
+}
+
+/*    
+ * get_notclausearg--
+ *    
+ * Retrieve the clause within a 'not' clause
+ *    
+ */
+Expr *
+get_notclausearg(Expr *notclause)
+{
+     return(lfirst(notclause->args));
+}
+
+/*****************************************************************************
+ *    	AND clause functions
+ *****************************************************************************/
+
+
+/*    
+ * and_clause--
+ *    
+ * Returns t iff its argument is an 'and' clause: (AND { expr }).
+ *    
+ */
+bool
+and_clause(Node *clause)
+{
+    return
+	(clause!=NULL &&
+	 nodeTag(clause)==T_Expr && ((Expr*)clause)->opType == AND_EXPR);
+}
+/*    		 
+ * make_andclause--
+ *    
+ * Create an 'and' clause given its arguments in a list.
+ *    
+ */
+Expr *
+make_andclause(List *andclauses)
+{
+    Expr *expr = makeNode(Expr);
+
+    expr->typeOid = InvalidOid;	/* assume type checking done */
+    expr->opType = AND_EXPR;
+    expr->oper = NULL;
+    expr->args = andclauses;
+    return expr;
+}
+
+/*****************************************************************************
+ *                                                                           *
+ *                                                                           *
+ *                                                                           *
+ *****************************************************************************/
+
+
+/*    
+ * pull-constant-clauses--
+ *    Scans through a list of qualifications and find those that
+ *    contain no variables.
+ *    
+ * Returns a list of the constant clauses in constantQual and the remaining
+ * quals as the return value.
+ *    
+ */
+List *
+pull_constant_clauses(List *quals, List **constantQual)
+{
+    List *q;
+    List *constqual=NIL;
+    List *restqual=NIL;
+
+    foreach(q, quals) {
+	if (!contain_var_clause(lfirst(q))) {
+	    constqual = lcons(lfirst(q), constqual);
+	}else {
+	    restqual = lcons(lfirst(q), restqual);
+	}
+    }
+    freeList(quals);
+    *constantQual = constqual;
+    return restqual;
+}
+
+/*    
+ * clause-relids-vars--
+ *    Retrieves relids and vars appearing within a clause.
+ *    Returns ((relid1 relid2 ... relidn) (var1 var2 ... varm)) where 
+ *    vars appear in the clause  this is done by recursively searching
+ *    through the left and right operands of a clause.
+ *    
+ * Returns the list of relids and vars.
+ *    
+ * XXX take the nreverse's out later
+ *    
+ */
+void
+clause_relids_vars(Node *clause, List **relids, List **vars)
+{
+    List *clvars = pull_var_clause(clause);
+    List *var_list = NIL;
+    List *varno_list = NIL;
+    List *i = NIL;
+
+    foreach (i, clvars) {
+	Var *var = (Var *)lfirst(i);
+
+	if (!intMember(var->varno, varno_list)) {
+	    varno_list = lappendi(varno_list, var->varno);
+	    var_list = lappend(var_list, var);
+	}
+    }
+
+    *relids = varno_list;
+    *vars = var_list;
+    return;
+}
+
+/*    
+ * NumRelids--
+ *    	(formerly clause-relids)
+ *    
+ * Returns the number of different relations referenced in 'clause'.
+ */
+int
+NumRelids(Node *clause)
+{
+    List *vars = pull_var_clause(clause);
+    List *i = NIL;
+    List *var_list = NIL;
+
+    foreach (i, vars) {
+	Var *var = (Var *)lfirst(i);
+
+	if (!intMember(var->varno, var_list)) {
+	    var_list = lconsi(var->varno, var_list);
+	}
+    }
+
+    return(length(var_list));
+}
+
+/*    
+ * contains-not--
+ *
+ * Returns t iff the clause is a 'not' clause or if any of the
+ * subclauses within an 'or' clause contain 'not's.
+ *    
+ */
+bool
+contains_not(Node *clause)
+{
+    if (single_node(clause))
+	return (false);
+
+    if (not_clause(clause))
+	return (true);
+
+    if (or_clause(clause)) {
+	List *a;
+	foreach(a, ((Expr*)clause)->args) {
+	    if (contains_not(lfirst(a)))
+		return (true);
+	}
+    }
+	
+    return(false);
+}
+
+/*    
+ * join-clause-p--
+ *    
+ * Returns t iff 'clause' is a valid join clause.
+ *    
+ */
+bool
+join_clause_p(Node *clause)
+{
+    Node *leftop, *rightop;
+
+    if (!is_opclause(clause))
+	return false;
+
+    leftop = (Node*)get_leftop((Expr*)clause);
+    rightop = (Node*)get_rightop((Expr*)clause);
+
+    /*
+     * One side of the clause (i.e. left or right operands)
+     * must either be a var node ...
+     */
+    if (IsA(leftop,Var) || IsA(rightop,Var))
+	return true;
+
+    /*
+     * ... or a func node.
+     */
+    if (is_funcclause(leftop) || is_funcclause(rightop))
+	return(true);
+
+    return(false);
+}
+
+/*    
+ * qual-clause-p--
+ *    
+ * Returns t iff 'clause' is a valid qualification clause.
+ *    
+ */
+bool
+qual_clause_p(Node *clause)
+{
+    if (!is_opclause(clause))
+	return false;
+
+    if (IsA (get_leftop((Expr*)clause),Var) &&
+	IsA (get_rightop((Expr*)clause),Const))
+	{
+	    return(true);
+	}
+    else if (IsA (get_rightop((Expr*)clause),Var) &&
+	     IsA (get_leftop((Expr*)clause),Const))
+	{
+	    return(true);
+	}
+    return(false);
+}
+
+/*    
+ * fix-opid--
+ *    Calculate the opfid from the opno...
+ *    
+ * Returns nothing.
+ *    
+ */
+void
+fix_opid(Node *clause)
+{
+    if (clause==NULL || single_node(clause)) {
+	;
+    } 
+    else if (or_clause (clause)) {
+	fix_opids(((Expr*)clause)->args);
+    } 
+    else if (is_funcclause (clause)) {
+	fix_opids(((Expr*)clause)->args);
+    } 
+    else if (IsA(clause,ArrayRef)) {
+	ArrayRef *aref = (ArrayRef *)clause;
+	
+	fix_opids(aref->refupperindexpr);
+	fix_opids(aref->reflowerindexpr);
+	fix_opid(aref->refexpr);
+	fix_opid(aref->refassgnexpr);
+    }
+    else if (not_clause(clause)) {
+	fix_opid((Node*)get_notclausearg((Expr*)clause));
+    } 
+    else if (is_opclause (clause)) {
+	replace_opid((Oper*)((Expr*)clause)->oper);
+	fix_opid((Node*)get_leftop((Expr*)clause));
+	fix_opid((Node*)get_rightop((Expr*)clause));
+    }
+
+}
+
+/*    
+ * fix-opids--
+ *    Calculate the opfid from the opno for all the clauses...
+ *    
+ * Returns its argument.
+ *    
+ */
+List *
+fix_opids(List *clauses)
+{
+    List *clause;
+
+    foreach(clause, clauses)
+	fix_opid(lfirst(clause));
+
+    return(clauses);
+}
+
+/*    
+ * get_relattval--
+ *    	For a non-join clause, returns a list consisting of the 
+ *    		relid,
+ *    		attno,
+ *    		value of the CONST node (if any), and a
+ *    		flag indicating whether the value appears on the left or right
+ *    			of the operator and whether the value varied.
+ *
+ * OLD OBSOLETE COMMENT FOLLOWS:
+ *    	If 'clause' is not of the format (op var node) or (op node var),
+ *    	or if the var refers to a nested attribute, then -1's are returned for
+ *    	everything but the value  a blank string "" (pointer to \0) is
+ *    	returned for the value if it is unknown or null.
+ * END OF OLD OBSOLETE COMMENT.
+ * NEW COMMENT:
+ * when defining rules one of the attibutes of the operator can
+ * be a Param node (which is supposed to be treated as a constant).
+ * However as there is no value specified for a parameter until run time
+ * this routine used to return "" as value, which made 'compute_selec'
+ * to bomb (because it was expecting a lisp integer and got back a lisp
+ * string). Now the code returns a plain old good "lispInteger(0)".
+ *    
+ */
+void
+get_relattval(Node *clause,
+	      int *relid,
+	      AttrNumber *attno,
+	      Datum *constval,
+	      int *flag)
+{
+    Var *left = get_leftop((Expr*)clause);
+    Var *right = get_rightop((Expr*)clause);
+    
+    if(is_opclause(clause) && IsA(left,Var) && 
+       IsA(right,Const)) {
+
+	if(right!=NULL) {
+
+	    *relid = left->varno;
+	    *attno = left->varattno;
+	    *constval = ((Const *)right)->constvalue;
+	    *flag = (_SELEC_CONSTANT_RIGHT_ | _SELEC_IS_CONSTANT_);
+
+	} else {
+
+	    *relid = left->varno;
+	    *attno = left->varattno;
+	    *constval = 0;
+	    *flag = (_SELEC_CONSTANT_RIGHT_ | _SELEC_NOT_CONSTANT_);
+	
+	} 
+    }else if (is_opclause(clause) &&
+	      is_funcclause((Node*)left) &&
+	      IsA(right,Const)) {
+	List *args = ((Expr*)left)->args;
+
+
+	*relid = ((Var*)lfirst(args))->varno;
+	*attno = InvalidAttrNumber;
+	*constval = ((Const*)right)->constvalue;
+	*flag = (_SELEC_CONSTANT_RIGHT_ | _SELEC_IS_CONSTANT_);
+    
+	/*
+	 * XXX both of these func clause handling if's seem wrong to me.
+	 *     they assume that the first argument is the Var.  It could
+	 *     not handle (for example) f(1, emp.name).  I think I may have
+	 *     been assuming no constants in functional index scans when I
+	 *     implemented this originally (still currently true).
+	 *     -mer 10 Aug 1992
+	 */
+    } else if (is_opclause(clause) &&
+	     is_funcclause((Node*)right) &&
+	       IsA(left,Const)) {
+	List *args = ((Expr*)right)->args;
+
+	*relid = ((Var*)lfirst(args))->varno;
+	*attno = InvalidAttrNumber;
+	*constval = ((Const*)left)->constvalue;
+	*flag = ( _SELEC_IS_CONSTANT_);
+    
+    } else if (is_opclause (clause) && IsA (right,Var) &&
+	      IsA (left,Const)) {
+	if (left!=NULL) {
+
+	    *relid = right->varno;
+	    *attno = right->varattno;
+	    *constval = ((Const*)left)->constvalue;
+	    *flag = (_SELEC_IS_CONSTANT_);
+	} else {
+
+	    *relid = right->varno;
+	    *attno = right->varattno;
+	    *constval = 0;
+	    *flag = (_SELEC_NOT_CONSTANT_);
+	} 
+    } else {
+	/* One or more of the operands are expressions 
+	 * (e.g., oper clauses)
+	 */
+	*relid = _SELEC_VALUE_UNKNOWN_;
+	*attno = _SELEC_VALUE_UNKNOWN_;
+	*constval = 0;
+	*flag = (_SELEC_NOT_CONSTANT_);
+    }		       
+}
+
+/*    
+ * get_relsatts--
+ *    
+ * Returns a list 
+ *    		( relid1 attno1 relid2 attno2 )
+ *    	for a joinclause.
+ *    
+ * If the clause is not of the form (op var var) or if any of the vars
+ * refer to nested attributes, then -1's are returned.
+ *    
+ */
+void
+get_rels_atts(Node *clause,
+	      int *relid1,
+	      AttrNumber *attno1,
+	      int *relid2,
+	      AttrNumber *attno2)
+{
+    Var *left = get_leftop((Expr*)clause);
+    Var *right = get_rightop((Expr*)clause);
+    bool var_left = (IsA(left,Var));
+    bool var_right = (IsA(right,Var));
+    bool varexpr_left = (bool)((IsA(left,Func) || IsA (left,Oper)) &&
+			       contain_var_clause((Node*)left));
+    bool varexpr_right = (bool)(( IsA(right,Func) || IsA (right,Oper)) &&
+				contain_var_clause((Node*)right));
+    
+    if (is_opclause(clause)) {
+	if(var_left && var_right) {
+
+	    *relid1 = left->varno;
+	    *attno1 = left->varoattno;
+	    *relid2 = right->varno;
+	    *attno2 = right->varoattno;
+	    return;
+	} else if (var_left && varexpr_right ) {
+
+	    *relid1 = left->varno;
+	    *attno1 = left->varoattno;
+	    *relid2 = _SELEC_VALUE_UNKNOWN_;
+	    *attno2 = _SELEC_VALUE_UNKNOWN_;
+	    return;
+	} else if (varexpr_left && var_right) {
+
+	    *relid1 = _SELEC_VALUE_UNKNOWN_;
+	    *attno1 = _SELEC_VALUE_UNKNOWN_;
+	    *relid2 = right->varno;
+	    *attno2 = right->varoattno;
+	    return;
+	}
+    }
+
+    *relid1 = _SELEC_VALUE_UNKNOWN_;
+    *attno1 = _SELEC_VALUE_UNKNOWN_;
+    *relid2 = _SELEC_VALUE_UNKNOWN_;
+    *attno2 = _SELEC_VALUE_UNKNOWN_;
+    return;
+}
+
+void
+CommuteClause(Node *clause)
+{
+    Node *temp;
+    Oper *commu;
+    OperatorTupleForm commuTup;
+    HeapTuple heapTup;
+
+    if (!is_opclause(clause))
+	return;
+
+    heapTup = (HeapTuple)
+	get_operator_tuple(get_commutator(((Oper*)((Expr*)clause)->oper)->opno));
+
+    if (heapTup == (HeapTuple)NULL)
+	return;
+
+    commuTup = (OperatorTupleForm)GETSTRUCT(heapTup);
+
+    commu = makeOper(heapTup->t_oid,
+		     InvalidOid,
+		     commuTup->oprresult,
+		     ((Oper*)((Expr*)clause)->oper)->opsize,
+		     NULL);
+
+    /*
+     * reform the clause -> (operator func/var constant)
+     */
+    ((Expr*)clause)->oper = (Node*)commu;
+    temp = lfirst(((Expr*)clause)->args);
+    lfirst(((Expr*)clause)->args) = lsecond(((Expr*)clause)->args);
+    lsecond(((Expr*)clause)->args) = temp;
+}
+
+
diff --git a/src/backend/optimizer/util/indexnode.c b/src/backend/optimizer/util/indexnode.c
new file mode 100644
index 00000000000..7fd74889202
--- /dev/null
+++ b/src/backend/optimizer/util/indexnode.c
@@ -0,0 +1,92 @@
+/*-------------------------------------------------------------------------
+ *
+ * indexnode.c--
+ *    Routines to find all indices on a relation
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/indexnode.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/plannodes.h"
+#include "nodes/parsenodes.h"
+#include "nodes/relation.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/plancat.h"
+#include "optimizer/pathnode.h"		/* where the decls go */
+
+
+static List *find_secondary_index(Query *root, Oid relid);
+
+/*    
+ * find-relation-indices--
+ *    Returns a list of index nodes containing appropriate information for
+ *    each (secondary) index defined on a relation.
+ *    
+ */
+List *
+find_relation_indices(Query *root, Rel *rel)
+{
+    if (rel->indexed) {
+	return (find_secondary_index(root, lfirsti(rel->relids)));
+    } else {
+	return (NIL);
+    }
+}
+
+/*    
+ * find-secondary-index--
+ *    Creates a list of index path nodes containing information for each
+ *    secondary index defined on a relation by searching through the index
+ *    catalog.
+ *    
+ * 'relid' is the OID of the relation for which indices are being located
+ *    
+ * Returns a list of new index nodes.
+ *    
+ */
+static List *
+find_secondary_index(Query *root, Oid relid)
+{
+    IdxInfoRetval indexinfo;
+    List *indexes = NIL;
+    bool first = TRUE;
+
+    while (index_info(root, first, relid,&indexinfo)) {
+	Rel *indexnode = makeNode(Rel);
+
+	indexnode->relids = lconsi(indexinfo.relid,NIL);
+	indexnode->relam = indexinfo.relam;
+	indexnode->pages = indexinfo.pages;
+	indexnode->tuples = indexinfo.tuples;
+	indexnode->indexkeys = indexinfo.indexkeys;
+	indexnode->ordering = indexinfo.orderOprs;
+	indexnode->classlist = indexinfo.classlist;
+	indexnode->indproc= indexinfo.indproc;
+	indexnode->indpred = (List*)indexinfo.indpred;
+	
+	indexnode->indexed= false; /* not indexed itself */
+	indexnode->size = 0;
+	indexnode->width= 0;
+	indexnode->targetlist= NIL;
+	indexnode->pathlist= NIL;
+	indexnode->unorderedpath= NULL;
+	indexnode->cheapestpath= NULL;
+	indexnode->pruneable= true;
+	indexnode->clauseinfo= NIL;
+	indexnode->joininfo= NIL;
+	indexnode->innerjoin= NIL;
+
+	indexes = lcons(indexnode, indexes);
+	first = FALSE;
+    }
+
+    return indexes;
+}
+
diff --git a/src/backend/optimizer/util/internal.c b/src/backend/optimizer/util/internal.c
new file mode 100644
index 00000000000..1db22f2b949
--- /dev/null
+++ b/src/backend/optimizer/util/internal.c
@@ -0,0 +1,61 @@
+/*-------------------------------------------------------------------------
+ *
+ * internal.c--
+ *    Definitions required throughout the query optimizer.
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/internal.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/*    
+ *    	---------- SHARED MACROS
+ *    
+ *     	Macros common to modules for creating, accessing, and modifying
+ *    	query tree and query plan components.
+ *    	Shared with the executor.
+ *    
+ */
+
+
+#include "optimizer/internal.h"
+
+#include "nodes/relation.h"
+#include "nodes/plannodes.h"
+#include "nodes/primnodes.h"
+#include "utils/elog.h"
+#include "utils/palloc.h"
+
+#if 0 
+/*****************************************************************************
+ *
+ *****************************************************************************/
+
+/* the following should probably be moved elsewhere -ay */
+
+TargetEntry *
+MakeTLE(Resdom *resdom, Node *expr)
+{
+    TargetEntry *rt = makeNode(TargetEntry);
+    rt->resdom = resdom;
+    rt->expr = expr;
+    return rt;
+}
+
+Var *
+get_expr(TargetEntry *tle)
+{
+    Assert(tle!=NULL);
+    Assert(tle->expr!=NULL);
+
+    return ((Var *)tle->expr); 
+}
+
+#endif /* 0 */
+
+
+
diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c
new file mode 100644
index 00000000000..85416db8b33
--- /dev/null
+++ b/src/backend/optimizer/util/joininfo.c
@@ -0,0 +1,107 @@
+/*-------------------------------------------------------------------------
+ *
+ * joininfo.c--
+ *    JoinInfo node manipulation routines
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/relation.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/var.h"
+#include "optimizer/clauses.h"
+
+
+/*    
+ * joininfo-member--
+ *    Determines whether a node has already been created for a join
+ *    between a set of join relations and the relation described by
+ *    'joininfo-list'.
+ *    
+ * 'join-relids' is a list of relids corresponding to the join relation
+ * 'joininfo-list' is the list of joininfo nodes against which this is 
+ *   		checked
+ *    
+ * Returns the corresponding node in 'joininfo-list' if such a node
+ * exists.
+ *    
+ */
+JInfo *
+joininfo_member(List *join_relids, List *joininfo_list)
+{
+    List *i = NIL;
+    List *other_rels = NIL;
+
+    foreach(i,joininfo_list) {
+	other_rels = lfirst(i);
+	if(same(join_relids, ((JInfo*)other_rels)->otherrels))
+	    return((JInfo*)other_rels);
+    }
+    return((JInfo*)NULL);
+}
+
+
+/*    
+ * find-joininfo-node--
+ *    Find the joininfo node within a relation entry corresponding
+ *    to a join between 'this_rel' and the relations in 'join-relids'.  A
+ *    new node is created and added to the relation entry's joininfo
+ *    field if the desired one can't be found.
+ *    
+ * Returns a joininfo node.
+ *    
+ */
+JInfo *
+find_joininfo_node(Rel *this_rel, List *join_relids)
+{
+    JInfo *joininfo = joininfo_member(join_relids,
+				      this_rel->joininfo);
+    if( joininfo == NULL ) {
+	joininfo = makeNode(JInfo);
+	joininfo->otherrels = join_relids;
+	joininfo->jinfoclauseinfo = NIL;
+	joininfo->mergesortable = false;
+	joininfo->hashjoinable = false;
+	joininfo->inactive = false;
+	this_rel->joininfo = lcons(joininfo, this_rel->joininfo);
+    }
+    return(joininfo);
+}
+
+/*    
+ * other-join-clause-var--
+ *    Determines whether a var node is contained within a joinclause
+ *    of the form(op var var).
+ *    
+ * Returns the other var node in the joinclause if it is, nil if not.
+ *    
+ */
+Var *
+other_join_clause_var(Var *var, Expr *clause)
+{
+     Var *retval;
+     Var *l, *r;
+
+     retval = (Var*) NULL;
+
+     if( var != NULL  && join_clause_p((Node*)clause)) {
+	  l = (Var *) get_leftop(clause);
+	  r = (Var *) get_rightop(clause);
+
+	  if(var_equal(var, l)) {
+	       retval = r;
+	  } else if(var_equal(var, r)) {
+	       retval = l;
+	  }
+     }
+
+     return(retval);
+}
diff --git a/src/backend/optimizer/util/keys.c b/src/backend/optimizer/util/keys.c
new file mode 100644
index 00000000000..ac0915b9096
--- /dev/null
+++ b/src/backend/optimizer/util/keys.c
@@ -0,0 +1,193 @@
+/*-------------------------------------------------------------------------
+ *
+ * keys.c--
+ *    Key manipulation routines
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+#include "nodes/pg_list.h"
+#include "nodes/nodes.h"
+#include "nodes/relation.h"
+#include "utils/elog.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/keys.h"
+#include "optimizer/tlist.h"
+
+
+static Expr *matching2_tlvar(int var, List *tlist, bool (*test)());
+
+/*    
+ * 1. index key
+ * 	one of:
+ * 		attnum
+ * 		(attnum arrayindex)
+ * 2. path key
+ * 	(subkey1 ... subkeyN)
+ * 	where subkeyI is a var node
+ *    	note that the 'Keys field is a list of these
+ * 3. join key
+ * 	(outer-subkey inner-subkey)
+ * 		where each subkey is a var node
+ * 4. sort key
+ * 	one of:
+ * 		SortKey node
+ * 		number
+ * 		nil
+ * 	(may also refer to the 'SortKey field of a SortKey node,
+ * 	 which looks exactly like an index key)
+ *    
+ */
+
+/*    
+ * match-indexkey-operand--
+ *    Returns t iff an index key 'index-key' matches the given clause 
+ *    operand.
+ *    
+ */
+bool
+match_indexkey_operand(int indexkey, Var *operand, Rel *rel)
+{
+    if (IsA (operand,Var) &&
+	(lfirsti(rel->relids) == operand->varno) &&
+	equal_indexkey_var(indexkey,operand))
+	return(true);
+    else
+	return(false);
+}
+
+/*    
+ * equal_indexkey_var--
+ *    Returns t iff an index key 'index-key' matches the corresponding 
+ *    fields of var node 'var'.
+ *    
+ */
+bool
+equal_indexkey_var(int index_key, Var *var)
+{
+    if (index_key == var->varattno)
+	return(true);
+    else
+	return(false);
+}
+
+/*    
+ * extract-subkey--
+ *   Returns the subkey in a join key corresponding to the outer or inner
+ *   lelation.
+ *    
+ */
+Var *
+extract_subkey(JoinKey *jk, int which_subkey)
+{
+    Var *retval;
+
+    switch (which_subkey) {
+    case OUTER: 
+	retval = jk->outer;
+	break;
+    case INNER: 
+	retval = jk->inner;
+	break;
+    default:			/* do nothing */
+	elog(DEBUG,"extract_subkey with neither INNER or OUTER");
+	retval = NULL;
+    }
+    return(retval);
+}
+
+/*    
+ * samekeys--
+ *    Returns t iff two sets of path keys are equivalent.  They are 
+ *    equivalent if the first subkey (var node) within each sublist of 
+ *    list 'keys1' is contained within the corresponding sublist of 'keys2'.
+ *    
+ *    XXX 	It isn't necessary to check that each sublist exactly contain 
+ *    		the same elements because if the routine that built these
+ *    		sublists together is correct, having one element in common 
+ *    		implies having all elements in common.
+ *    
+ */
+bool
+samekeys(List *keys1, List *keys2)
+{
+    bool allmember = true;
+    List *key1, *key2;
+
+    for(key1=keys1,key2=keys2 ; key1 != NIL && key2 !=NIL ; 
+	key1=lnext(key1), key2=lnext(key2)) 
+	if (!member(lfirst(key1), lfirst(key2)))
+	    allmember = false;
+
+    if ( (length (keys2) >= length (keys1)) && allmember)
+	return(true);
+    else
+	return(false);
+}
+
+/*    
+ * collect-index-pathkeys--
+ *    Creates a list of subkeys by retrieving var nodes corresponding to
+ *    each index key in 'index-keys' from the relation's target list
+ *    'tlist'.  If the key is not in the target list, the key is irrelevant
+ *    and is thrown away.  The returned subkey list is of the form:
+ *    		((var1) (var2) ... (varn))
+ *    
+ * 'index-keys' is a list of index keys
+ * 'tlist' is a relation target list
+ *    
+ * Returns the list of cons'd subkeys.
+ *    
+ */
+/* This function is identical to matching_tlvar and tlistentry_member.
+ * They should be merged.
+ */
+static Expr *
+matching2_tlvar(int var, List *tlist, bool (*test)())
+{
+    TargetEntry *tlentry = NULL;
+
+    if (var) {
+	List *temp;
+	foreach (temp,tlist) {
+	    if ((*test)(var, get_expr(lfirst(temp)))) {
+		tlentry = lfirst(temp);
+		break;
+	    }
+	}
+    }
+
+    if (tlentry) 
+	return((Expr*)get_expr(tlentry));
+    else
+	return((Expr*)NULL);
+}
+
+
+List *
+collect_index_pathkeys(int *index_keys, List *tlist)
+{
+    List *retval = NIL;
+
+    Assert (index_keys != NULL);
+
+    while(index_keys[0] != 0) {
+	Expr *mvar;
+	mvar = matching2_tlvar(index_keys[0],
+			       tlist,
+			       equal_indexkey_var);
+	if (mvar) 
+	    retval = nconc(retval,lcons(lcons(mvar,NIL),
+					NIL));
+	index_keys++;
+    }
+    return(retval);
+}
+
diff --git a/src/backend/optimizer/util/ordering.c b/src/backend/optimizer/util/ordering.c
new file mode 100644
index 00000000000..3dffbff9f3c
--- /dev/null
+++ b/src/backend/optimizer/util/ordering.c
@@ -0,0 +1,117 @@
+/*-------------------------------------------------------------------------
+ *
+ * ordering.c--
+ *    Routines to manipulate and compare merge and path orderings
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/ordering.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "optimizer/internal.h"
+#include "optimizer/ordering.h"
+
+
+/*    
+ * equal-path-path-ordering--
+ *    Returns t iff two path orderings are equal.
+ *    
+ */
+bool
+equal_path_path_ordering(PathOrder *path_ordering1,
+			 PathOrder *path_ordering2)
+{
+    if (path_ordering1 == path_ordering2)
+	return true;
+
+    if (!path_ordering1 || !path_ordering2)
+	return false;
+
+    if (path_ordering1->ordtype == MERGE_ORDER &&
+	path_ordering2->ordtype == MERGE_ORDER) {
+
+	return equal(path_ordering1->ord.merge, path_ordering2->ord.merge);
+
+    } else if (path_ordering1->ordtype == SORTOP_ORDER &&
+	       path_ordering2->ordtype == SORTOP_ORDER) {
+
+	return
+	    (equal_sortops_order(path_ordering1->ord.sortop,
+				 path_ordering2->ord.sortop));
+    } else if (path_ordering1->ordtype == MERGE_ORDER &&
+	       path_ordering2->ordtype == SORTOP_ORDER) {
+
+	return (path_ordering2->ord.sortop &&
+		(path_ordering1->ord.merge->left_operator ==
+		 path_ordering2->ord.sortop[0]));
+    } else {
+
+	return (path_ordering1->ord.sortop &&
+		(path_ordering1->ord.sortop[0] ==
+		 path_ordering2->ord.merge->left_operator));
+    }
+}
+
+/*    
+ * equal-path-merge-ordering--
+ *    Returns t iff a path ordering is usable for ordering a merge join.
+ *
+ * XXX	Presently, this means that the first sortop of the path matches
+ *    	either of the merge sortops.  Is there a "right" and "wrong"
+ *    	sortop to match?
+ *    
+ */
+bool
+equal_path_merge_ordering(Oid *path_ordering,
+			  MergeOrder *merge_ordering)
+{
+    if (path_ordering == NULL || merge_ordering == NULL)
+	return(false);
+
+    if (path_ordering[0] == merge_ordering->left_operator ||
+	path_ordering[0] == merge_ordering->right_operator)
+	return(true);
+    else
+	return(false);
+}
+
+/*    
+ * equal-merge-merge-ordering--
+ *    Returns t iff two merge orderings are equal.
+ *    
+ */
+bool
+equal_merge_merge_ordering(MergeOrder *merge_ordering1,
+			   MergeOrder *merge_ordering2)
+{
+    return (equal(merge_ordering1, merge_ordering2));
+}
+
+/*****************************************************************************
+ *
+ *****************************************************************************/
+
+/*
+ * equal_sort_ops_order -
+ *    Returns true iff the sort operators are in the same order.
+ */
+bool
+equal_sortops_order(Oid *ordering1, Oid *ordering2)
+{
+    int i = 0;
+
+    if (ordering1 == NULL || ordering2 == NULL)
+	return (ordering1==ordering2);
+    
+    while (ordering1[i]!=0 && ordering2[i]!=0) {
+	if (ordering1[i] != ordering2[i])
+	    break;
+	i++;
+    }
+
+    return (ordering1[i]==0 && ordering2[i]==0);
+}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
new file mode 100644
index 00000000000..728ac9b422e
--- /dev/null
+++ b/src/backend/optimizer/util/pathnode.c
@@ -0,0 +1,566 @@
+/*-------------------------------------------------------------------------
+ *
+ * pathnode.c--
+ *    Routines to manipulate pathlists and create path nodes
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include <math.h>
+
+#include "postgres.h"
+
+#include "nodes/relation.h"
+#include "utils/elog.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/clauseinfo.h"
+#include "optimizer/plancat.h"
+#include "optimizer/cost.h"
+#include "optimizer/keys.h"
+#include "optimizer/xfunc.h"
+#include "optimizer/ordering.h"
+
+#include "parser/parsetree.h"		/* for getrelid() */
+
+static Path *better_path(Path *new_path, List *unique_paths, bool *noOther);
+
+
+/*****************************************************************************
+ *    	MISC. PATH UTILITIES
+ *****************************************************************************/
+
+/*    
+ * path-is-cheaper--
+ *    Returns t iff 'path1' is cheaper than 'path2'.
+ *    
+ */
+bool
+path_is_cheaper(Path *path1, Path *path2)
+{
+    Cost cost1 = path1->path_cost;
+    Cost cost2 = path2->path_cost;
+
+    return((bool)(cost1 < cost2));
+}
+
+/*    
+ * set_cheapest--
+ *    Finds the minimum cost path from among a relation's paths.  
+ *    
+ * 'parent-rel' is the parent relation
+ * 'pathlist' is a list of path nodes corresponding to 'parent-rel'
+ *    
+ * Returns and sets the relation entry field with the pathnode that 
+ * is minimum.
+ *    
+ */
+Path *
+set_cheapest(Rel *parent_rel, List *pathlist)
+{
+    List *p;
+    Path *cheapest_so_far;
+
+    Assert(pathlist!=NIL);
+    Assert(IsA(parent_rel,Rel));
+
+    cheapest_so_far = (Path*)lfirst(pathlist);
+
+    foreach (p, lnext(pathlist)) {
+	Path *path = (Path*)lfirst(p);
+
+	if (path_is_cheaper(path, cheapest_so_far)) {
+	    cheapest_so_far = path;
+	}
+    }
+
+    parent_rel->cheapestpath = cheapest_so_far;
+
+    return(cheapest_so_far);
+}
+
+/*    
+ * add_pathlist--
+ *    For each path in the list 'new-paths', add to the list 'unique-paths' 
+ *    only those paths that are unique (i.e., unique ordering and ordering 
+ *    keys).  Should a conflict arise, the more expensive path is thrown out,
+ *    thereby pruning the plan space.  But we don't prune if xfunc
+ *    told us not to.
+ *    
+ * 'parent-rel' is the relation entry to which these paths correspond.
+ *    
+ * Returns the list of unique pathnodes.
+ *    
+ */
+List *
+add_pathlist(Rel *parent_rel, List *unique_paths, List *new_paths)
+{
+    List *x;
+    Path *new_path;
+    Path *old_path;
+    bool noOther;
+
+    foreach (x, new_paths) {
+	new_path = (Path*)lfirst(x);
+	if (member(new_path, unique_paths)) 
+	    continue;
+	old_path = better_path(new_path,unique_paths,&noOther);
+
+	if (noOther) {
+	    /*  Is a brand new path.  */
+	    new_path->parent = parent_rel;
+	    unique_paths = lcons(new_path, unique_paths);
+	} else if (old_path==NULL) {
+	    ;	/* do nothing if path is not cheaper */
+	} else if (old_path != NULL) { /* (IsA(old_path,Path)) { */
+	    new_path->parent = parent_rel;
+	    if (!parent_rel->pruneable) {
+		unique_paths = lcons(new_path, unique_paths);
+	    }else
+		unique_paths = lcons(new_path,
+				    LispRemove(old_path,unique_paths));
+	}
+    }
+    return(unique_paths);
+}
+
+/*    
+ * better_path--
+ *    Determines whether 'new-path' has the same ordering and keys as some 
+ *    path in the list 'unique-paths'.  If there is a redundant path,
+ *    eliminate the more expensive path.
+ *    
+ * Returns:
+ *    The old path - if 'new-path' matches some path in 'unique-paths' and is
+ *    		cheaper
+ *    nil - if 'new-path' matches but isn't cheaper
+ *    t - if there is no path in the list with the same ordering and keys
+ *    
+ */
+static Path *
+better_path(Path *new_path, List *unique_paths, bool *noOther)
+{
+    Path *old_path = (Path*)NULL;
+    Path *path = (Path*)NULL;
+    List *temp = NIL;
+    Path *retval = NULL;
+
+    /* XXX - added the following two lines which weren't int
+     * the lisp planner, but otherwise, doesn't seem to work
+     * for the case where new_path is 'nil
+     */
+    foreach (temp,unique_paths) {
+	path = (Path*) lfirst(temp);
+
+	if ((equal_path_path_ordering(&new_path->p_ordering,
+				      &path->p_ordering) &&
+	     samekeys(new_path->keys, path->keys))) {
+	    old_path = path;
+	    break;
+	}
+    }
+
+    if (old_path==NULL) {
+	*noOther = true;
+    } else { 
+	*noOther = false;
+	if (path_is_cheaper(new_path,old_path)) {
+	    retval = old_path;
+	}
+    }
+     
+    return(retval);
+}
+
+
+
+/*****************************************************************************
+ *    	PATH NODE CREATION ROUTINES
+ *****************************************************************************/
+
+/*    
+ * create_seqscan_path--
+ *    Creates a path corresponding to a sequential scan, returning the
+ *    pathnode.
+ *    
+ */
+Path *
+create_seqscan_path(Rel *rel)
+{
+    int relid=0;
+
+    Path *pathnode = makeNode(Path);
+
+    pathnode->pathtype = T_SeqScan; 
+    pathnode->parent = rel;
+    pathnode->path_cost = 0.0;
+    pathnode->p_ordering.ordtype = SORTOP_ORDER;
+    pathnode->p_ordering.ord.sortop = NULL;
+    pathnode->keys = NIL;
+    /* copy clauseinfo list into path for expensive function processing 
+     * -- JMH, 7/7/92
+     */
+    pathnode->locclauseinfo= 
+	(List*)copyObject((Node*)rel->clauseinfo);
+
+    if (rel->relids !=NULL)
+	relid = lfirsti(rel->relids);
+
+    pathnode->path_cost = cost_seqscan (relid,
+					rel->pages, rel->tuples);
+    /* add in expensive functions cost!  -- JMH, 7/7/92 */
+#if 0
+    if (XfuncMode != XFUNC_OFF) {
+	pathnode->path_cost +=
+	    xfunc_get_path_cost(pathnode));
+    }
+#endif
+    return (pathnode);
+}
+
+/*    
+ * create_index_path--
+ *    Creates a single path node for an index scan.
+ *    
+ * 'rel' is the parent rel
+ * 'index' is the pathnode for the index on 'rel'
+ * 'restriction-clauses' is a list of restriction clause nodes.
+ * 'is-join-scan' is a flag indicating whether or not the index is being
+ * 	considered because of its sort order.
+ *    
+ * Returns the new path node.
+ *    
+ */
+IndexPath *
+create_index_path(Query *root,
+                  Rel *rel,
+		  Rel *index,
+		  List *restriction_clauses,
+		  bool is_join_scan)
+{
+    IndexPath *pathnode = makeNode(IndexPath);
+    
+    pathnode->path.pathtype = T_IndexScan;
+    pathnode->path.parent = rel;
+    pathnode->indexid = index->relids;
+
+    pathnode->path.p_ordering.ordtype = SORTOP_ORDER;
+    pathnode->path.p_ordering.ord.sortop = index->ordering;
+    pathnode->indexqual = NIL;
+
+    /* copy clauseinfo list into path for expensive function processing 
+     *  -- JMH, 7/7/92
+     */
+    pathnode->path.locclauseinfo =
+	set_difference((List*) copyObject((Node*)rel->clauseinfo),
+		       (List*) restriction_clauses);
+
+    /*
+     * The index must have an ordering for the path to have (ordering) keys, 
+     * and vice versa.
+     */
+    if (pathnode->path.p_ordering.ord.sortop) {
+	pathnode->path.keys = collect_index_pathkeys(index->indexkeys,
+						     rel->targetlist);
+	/*
+	 * Check that the keys haven't 'disappeared', since they may 
+	 * no longer be in the target list (i.e., index keys that are not 
+	 * relevant to the scan are not applied to the scan path node,
+	 * so if no index keys were found, we can't order the path).
+	 */
+	if (pathnode->path.keys==NULL) {
+	    pathnode->path.p_ordering.ord.sortop = NULL;
+	}
+    } else {
+	pathnode->path.keys = NULL;
+    }
+
+    if (is_join_scan || restriction_clauses==NULL) {
+	/*
+	 * Indices used for joins or sorting result nodes don't
+	 * restrict the result at all, they simply order it,
+	 * so compute the scan cost 
+	 * accordingly -- use a selectivity of 1.0.
+	 */
+/* is the statement above really true?  what about IndexScan as the 
+   inner of a join? */
+	pathnode->path.path_cost =
+	    cost_index (lfirsti(index->relids),
+			index->pages,
+			1.0,
+			rel->pages,
+			rel->tuples,
+			index->pages,
+			index->tuples,
+			false);
+	/* add in expensive functions cost!  -- JMH, 7/7/92 */
+#if 0
+	if (XfuncMode != XFUNC_OFF) {
+	    pathnode->path_cost =
+		(pathnode->path_cost +
+		 xfunc_get_path_cost((Path*)pathnode));
+	}
+#endif
+    } else  {
+	/*
+	 * Compute scan cost for the case when 'index' is used with a 
+	 * restriction clause.
+	 */
+	List *attnos;
+	List *values;
+	List *flags;
+	float npages;
+	float selec;
+	Cost clausesel;
+
+	get_relattvals(restriction_clauses,
+		       &attnos,
+		       &values,
+		       &flags);
+	index_selectivity(lfirsti(index->relids),
+			  index->classlist,
+			  get_opnos(restriction_clauses),
+			  getrelid(lfirsti(rel->relids),
+				   root->rtable),
+			  attnos,
+			  values,
+			  flags,
+			  length(restriction_clauses),
+			  &npages,
+			  &selec);
+	/*   each clause gets an equal selectivity */
+	clausesel = 
+	    pow(selec, 
+		1.0 / (double) length(restriction_clauses));
+    
+	pathnode->indexqual = restriction_clauses;
+	pathnode->path.path_cost =
+	    cost_index (lfirsti(index->relids),
+			(int)npages,
+			selec,
+			rel->pages,
+			rel->tuples,
+			index->pages,
+			index->tuples,
+			false);
+
+#if 0
+	/* add in expensive functions cost!  -- JMH, 7/7/92 */
+	if (XfuncMode != XFUNC_OFF) {
+	    pathnode->path_cost += 
+		xfunc_get_path_cost((Path*)pathnode);
+	}
+#endif
+	/* Set selectivities of clauses used with index to the selectivity 
+	 * of this index, subdividing the selectivity equally over each of 
+	 * the clauses. 
+	 */
+
+	/* XXX Can this divide the selectivities in a better way? */
+	set_clause_selectivities(restriction_clauses, clausesel);
+    }
+    return(pathnode);
+}
+
+/*    
+ * create_nestloop_path--
+ *    Creates a pathnode corresponding to a nestloop join between two 
+ *    relations.
+ *    
+ * 'joinrel' is the join relation.
+ * 'outer_rel' is the outer join relation
+ * 'outer_path' is the outer join path.
+ * 'inner_path' is the inner join path.
+ * 'keys' are the keys of the path
+ *    	
+ * Returns the resulting path node.
+ *    
+ */
+JoinPath *
+create_nestloop_path(Rel *joinrel,
+		     Rel *outer_rel,
+		     Path *outer_path,
+		     Path *inner_path,
+		     List *keys)
+{
+    JoinPath *pathnode = makeNode(JoinPath);
+     
+    pathnode->path.pathtype = T_NestLoop;
+    pathnode->path.parent  = joinrel;
+    pathnode->outerjoinpath = outer_path;
+    pathnode->innerjoinpath = inner_path;
+    pathnode->pathclauseinfo = joinrel->clauseinfo;
+    pathnode->path.keys = keys;
+    pathnode->path.joinid = NIL;
+    pathnode->path.outerjoincost = (Cost)0.0;
+    pathnode->path.locclauseinfo = NIL;
+
+    if (keys) {
+	pathnode->path.p_ordering.ordtype =
+	    outer_path->p_ordering.ordtype;
+	if (outer_path->p_ordering.ordtype == SORTOP_ORDER) {
+	    pathnode->path.p_ordering.ord.sortop =
+		outer_path->p_ordering.ord.sortop;
+	} else {
+	    pathnode->path.p_ordering.ord.merge =
+		outer_path->p_ordering.ord.merge;
+	}
+    } else {
+	pathnode->path.p_ordering.ordtype = SORTOP_ORDER;
+	pathnode->path.p_ordering.ord.sortop = NULL;
+    }
+
+    pathnode->path.path_cost  = 
+	cost_nestloop(outer_path->path_cost,
+		      inner_path->path_cost,
+		      outer_rel->size,
+		      inner_path->parent->size,
+		      page_size(outer_rel->size,
+				outer_rel->width),
+		      IsA(inner_path,IndexPath));
+    /* add in expensive function costs -- JMH 7/7/92 */
+#if 0
+    if (XfuncMode != XFUNC_OFF) {
+	pathnode->path_cost += xfunc_get_path_cost((Path*)pathnode);
+    }
+#endif
+    return(pathnode);
+}
+
+/*    
+ * create_mergesort_path--
+ *    Creates a pathnode corresponding to a mergesort join between
+ *    two relations
+ *    
+ * 'joinrel' is the join relation
+ * 'outersize' is the number of tuples in the outer relation
+ * 'innersize' is the number of tuples in the inner relation
+ * 'outerwidth' is the number of bytes per tuple in the outer relation
+ * 'innerwidth' is the number of bytes per tuple in the inner relation
+ * 'outer_path' is the outer path
+ * 'inner_path' is the inner path
+ * 'keys' are the new keys of the join relation
+ * 'order' is the sort order required for the merge
+ * 'mergeclauses' are the applicable join/restriction clauses
+ * 'outersortkeys' are the sort varkeys for the outer relation
+ * 'innersortkeys' are the sort varkeys for the inner relation
+ *    
+ */
+MergePath *
+create_mergesort_path(Rel *joinrel,
+		      int outersize,
+		      int innersize,
+		      int outerwidth,
+		      int innerwidth,
+		      Path *outer_path,
+		      Path *inner_path,
+		      List *keys,
+		      MergeOrder *order,
+		      List *mergeclauses,
+		      List *outersortkeys,
+		      List *innersortkeys)
+{
+    MergePath *pathnode = makeNode(MergePath);
+
+    pathnode->jpath.path.pathtype  = T_MergeJoin;
+    pathnode->jpath.path.parent  = joinrel;
+    pathnode->jpath.outerjoinpath = outer_path;
+    pathnode->jpath.innerjoinpath = inner_path;
+    pathnode->jpath.pathclauseinfo = joinrel->clauseinfo;
+    pathnode->jpath.path.keys = keys;
+    pathnode->jpath.path.p_ordering.ordtype = MERGE_ORDER;
+    pathnode->jpath.path.p_ordering.ord.merge  = order;
+    pathnode->path_mergeclauses = mergeclauses;
+    pathnode->jpath.path.locclauseinfo = NIL;
+    pathnode->outersortkeys = outersortkeys;
+    pathnode->innersortkeys = innersortkeys;
+    pathnode->jpath.path.path_cost  =
+	cost_mergesort(outer_path->path_cost,
+		       inner_path->path_cost,
+		       outersortkeys,
+		       innersortkeys,
+		       outersize,
+		       innersize,
+		       outerwidth,
+		       innerwidth);
+    /* add in expensive function costs -- JMH 7/7/92 */
+#if 0
+    if (XfuncMode != XFUNC_OFF) {
+	pathnode->path_cost +=
+	    xfunc_get_path_cost((Path*)pathnode);
+    }
+#endif
+    return(pathnode);
+}
+
+/*    
+ * create_hashjoin_path--		 	XXX HASH
+ *    Creates a pathnode corresponding to a hash join between two relations.
+ *    
+ * 'joinrel' is the join relation
+ * 'outersize' is the number of tuples in the outer relation
+ * 'innersize' is the number of tuples in the inner relation
+ * 'outerwidth' is the number of bytes per tuple in the outer relation
+ * 'innerwidth' is the number of bytes per tuple in the inner relation
+ * 'outer_path' is the outer path
+ * 'inner_path' is the inner path
+ * 'keys' are the new keys of the join relation
+ * 'operator' is the hashjoin operator
+ * 'hashclauses' are the applicable join/restriction clauses
+ * 'outerkeys' are the sort varkeys for the outer relation
+ * 'innerkeys' are the sort varkeys for the inner relation
+ *    
+ */
+HashPath *
+create_hashjoin_path(Rel *joinrel,
+		     int outersize,
+		     int innersize,
+		     int outerwidth,
+		     int innerwidth,
+		     Path *outer_path,
+		     Path *inner_path,
+		     List *keys,
+		     Oid operator,
+		     List *hashclauses,
+		     List *outerkeys,
+		     List *innerkeys)
+{
+    HashPath *pathnode = makeNode(HashPath);
+
+    pathnode->jpath.path.pathtype  = T_HashJoin; 
+    pathnode->jpath.path.parent  = joinrel;
+    pathnode->jpath.outerjoinpath = outer_path;
+    pathnode->jpath.innerjoinpath = inner_path;
+    pathnode->jpath.pathclauseinfo = joinrel->clauseinfo;
+    pathnode->jpath.path.locclauseinfo = NIL;
+    pathnode->jpath.path.keys = keys;
+    pathnode->jpath.path.p_ordering.ordtype = SORTOP_ORDER;
+    pathnode->jpath.path.p_ordering.ord.sortop = NULL;
+    pathnode->jpath.path.outerjoincost = (Cost)0.0;
+    pathnode->jpath.path.joinid =  (Relid)NULL;
+    /*    pathnode->hashjoinoperator = operator;  */ 
+    pathnode->path_hashclauses = hashclauses;
+    pathnode->outerhashkeys = outerkeys;
+    pathnode->innerhashkeys = innerkeys;
+    pathnode->jpath.path.path_cost  =
+	cost_hashjoin(outer_path->path_cost,
+		      inner_path->path_cost,
+		      outerkeys,
+		      innerkeys,
+		      outersize,innersize,
+		      outerwidth,innerwidth);
+    /* add in expensive function costs -- JMH 7/7/92 */
+#if 0
+    if (XfuncMode != XFUNC_OFF) {
+	pathnode->path_cost += 
+	    xfunc_get_path_cost((Path*)pathnode);
+    }
+#endif
+    return(pathnode);
+}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
new file mode 100644
index 00000000000..4dca017f95a
--- /dev/null
+++ b/src/backend/optimizer/util/plancat.c
@@ -0,0 +1,582 @@
+/*-------------------------------------------------------------------------
+ *
+ * plancat.c--
+ *     routines for accessing the system catalogs
+ *
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.1.1.1 1996/07/09 06:21:39 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include <stdio.h>
+#include "postgres.h"
+
+#include "access/heapam.h"
+#include "access/genam.h"
+#include "access/htup.h"
+#include "access/itup.h"
+
+#include "catalog/catname.h"
+#include "catalog/pg_amop.h"
+#include "catalog/pg_index.h"
+#include "catalog/pg_inherits.h"
+#include "catalog/pg_version.h"
+
+#include "nodes/pg_list.h"
+#include "parser/parsetree.h"		/* for getrelid() */
+#include "fmgr.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/plancat.h"
+
+#include "utils/tqual.h"
+#include "utils/elog.h"
+#include "utils/palloc.h"
+#include "utils/syscache.h"
+
+
+static void IndexSelectivity(Oid indexrelid, Oid indrelid, int32 nIndexKeys,
+	Oid AccessMethodOperatorClasses[], Oid operatorObjectIds[],
+	int32 varAttributeNumbers[], char *constValues[], int32 constFlags[],
+	float *idxPages, float *idxSelec);		     
+
+
+/*
+ * relation-info -
+ *    Retrieves catalog information for a given relation. Given the oid of
+ *    the relation, return the following information:
+ *		whether the relation has secondary indices
+ *		number of pages 
+ *		number of tuples
+ */
+void
+relation_info(Query *root, Index relid,
+	      bool *hasindex, int *pages, int *tuples)
+{
+    HeapTuple		relationTuple;
+    Form_pg_class	relation;
+    Oid                 relationObjectId;
+
+    relationObjectId = getrelid(relid, root->rtable);
+    relationTuple = SearchSysCacheTuple(RELOID, 
+					ObjectIdGetDatum(relationObjectId),
+					0,0,0);
+    if (HeapTupleIsValid(relationTuple)) {
+	relation = (Form_pg_class)GETSTRUCT(relationTuple);
+
+	*hasindex = (relation->relhasindex) ? TRUE : FALSE;
+	*pages = relation->relpages;
+	*tuples = relation->reltuples;
+    } else {
+	elog(WARN, "RelationCatalogInformation: Relation %d not found",
+	     relationObjectId);
+    }
+
+    return;
+}
+
+
+/*    
+ * index-info--
+ *    Retrieves catalog information on an index on a given relation.
+ *    
+ *    The index relation is opened on the first invocation. The current
+ *    retrieves the next index relation within the catalog that has not 
+ *    already been retrieved by a previous call.  The index catalog 
+ *    is closed when no more indices for 'relid' can be found.
+ *    
+ * 'first' is 1 if this is the first call 
+ *    
+ * Returns true if successful and false otherwise. Index info is returned
+ * via the transient data structure 'info'.
+ *    
+ */
+bool
+index_info(Query *root, bool first, int relid, IdxInfoRetval *info)
+{
+    register		i;
+    HeapTuple		indexTuple, amopTuple;
+    IndexTupleForm	index;
+    Relation		indexRelation;
+    uint16		amstrategy;
+    Oid			relam;
+    Oid			indrelid;
+
+    static Relation	relation = (Relation) NULL;
+    static HeapScanDesc	scan = (HeapScanDesc) NULL;
+    static ScanKeyData indexKey;
+
+
+    /* find the oid of the indexed relation */
+    indrelid = getrelid(relid, root->rtable);
+    
+    memset(info, 0, sizeof(IdxInfoRetval));
+
+    /*
+     * the maximum number of elements in each of the following arrays is
+     * 8. We allocate one more for a terminating 0 to indicate the end
+     * of the array.
+     */
+    info->indexkeys = (int *)palloc(sizeof(int)*9);
+    memset(info->indexkeys, 0, sizeof(int)*9);
+    info->orderOprs = (Oid *)palloc(sizeof(Oid)*9);
+    memset(info->orderOprs, 0, sizeof(Oid)*9);
+    info->classlist = (Oid *)palloc(sizeof(Oid)*9);
+    memset(info->classlist, 0, sizeof(Oid)*9);
+
+    /* Find an index on the given relation */
+    if (first) {
+	if (RelationIsValid(relation))
+	    heap_close(relation);
+	if (HeapScanIsValid(scan))
+	    heap_endscan(scan);
+
+	ScanKeyEntryInitialize(&indexKey, 0,
+			       Anum_pg_index_indrelid,
+			       F_OIDEQ,
+			       ObjectIdGetDatum(indrelid));
+
+	relation = heap_openr(IndexRelationName);
+	scan = heap_beginscan(relation, 0, NowTimeQual,
+			      1, &indexKey);
+    }
+    if (!HeapScanIsValid(scan))
+	elog(WARN, "index_info: scan not started");
+    indexTuple = heap_getnext(scan, 0, (Buffer *) NULL);
+    if (!HeapTupleIsValid(indexTuple)) {
+	heap_endscan(scan);
+	heap_close(relation);
+	scan = (HeapScanDesc) NULL;
+	relation = (Relation) NULL;
+	return(0);
+    }
+
+    /* Extract info from the index tuple */
+    index = (IndexTupleForm)GETSTRUCT(indexTuple);
+    info->relid = index->indexrelid; /* index relation */
+    for (i = 0; i < 8; i++)
+	info->indexkeys[i] = index->indkey[i];
+    for (i = 0; i < 8; i++)
+	info->classlist[i] = index->indclass[i];
+
+    info->indproc = index->indproc; /* functional index ?? */
+
+    /* partial index ?? */
+    if (VARSIZE(&index->indpred) != 0) {
+	/*
+	 * The memory allocated here for the predicate (in lispReadString)
+	 * only needs to stay around until it's used in find_index_paths,
+	 * which is all within a command, so the automatic pfree at end
+	 * of transaction should be ok.
+	 */
+	char *predString;
+
+	predString = fmgr(F_TEXTOUT, &index->indpred);
+	info->indpred = (Node*)stringToNode(predString);
+	pfree(predString);
+    }
+
+    /* Extract info from the relation descriptor for the index */
+    indexRelation = index_open(index->indexrelid);
+#ifdef notdef
+    /* XXX should iterate through strategies -- but how?  use #1 for now */
+    amstrategy = indexRelation->rd_am->amstrategies;
+#endif /* notdef */
+    amstrategy = 1;
+    relam = indexRelation->rd_rel->relam;
+    info->relam = relam;
+    info->pages = indexRelation->rd_rel->relpages;
+    info->tuples = indexRelation->rd_rel->reltuples;
+    heap_close(indexRelation);
+	
+    /* 
+     * Find the index ordering keys 
+     *
+     * Must use indclass to know when to stop looking since with
+     * functional indices there could be several keys (args) for
+     * one opclass. -mer 27 Sept 1991
+     */
+    for (i = 0; i < 8 && index->indclass[i]; ++i) {
+	amopTuple = SearchSysCacheTuple(AMOPSTRATEGY,
+					ObjectIdGetDatum(relam),
+					ObjectIdGetDatum(index->indclass[i]),
+					UInt16GetDatum(amstrategy),
+					0);
+	if (!HeapTupleIsValid(amopTuple))
+	    elog(WARN, "index_info: no amop %d %d %d",
+		 relam, index->indclass[i], amstrategy);
+	info->orderOprs[i] =
+	    ((Form_pg_amop)GETSTRUCT(amopTuple))->amopopr;
+    }
+    return(TRUE);
+}
+
+/*    
+ * index-selectivity--
+ *    
+ *    Call util/plancat.c:IndexSelectivity with the indicated arguments.
+ *    
+ * 'indid' is the index OID
+ * 'classes' is a list of index key classes
+ * 'opnos' is a list of index key operator OIDs
+ * 'relid' is the OID of the relation indexed
+ * 'attnos' is a list of the relation attnos which the index keys over
+ * 'values' is a list of the values of the clause's constants
+ * 'flags' is a list of fixnums which describe the constants
+ * 'nkeys' is the number of index keys
+ *    
+ * Returns two floats: index pages and index selectivity in 'idxPages' and
+ * 	'idxSelec'.
+ *    
+ */
+void
+index_selectivity(Oid indid,
+		  Oid *classes,
+		  List *opnos,
+		  Oid relid,
+		  List *attnos,
+		  List *values,
+		  List *flags,
+		  int32 nkeys,
+		  float *idxPages,
+		  float *idxSelec)
+{
+    Oid *opno_array;
+    int *attno_array, *flag_array;
+    char **value_array;
+    int i = 0;
+    List *xopno, *xattno, *value, *flag;
+
+    if (length(opnos)!=nkeys || length(attnos)!=nkeys ||
+	length(values)!=nkeys || length(flags)!=nkeys) {
+
+	*idxPages = 0.0;
+	*idxSelec = 1.0;
+	return;
+    }
+	
+    opno_array = (Oid *)palloc(nkeys*sizeof(Oid));
+    attno_array = (int *)palloc(nkeys*sizeof(int32));
+    value_array = (char **)palloc(nkeys*sizeof(char *));
+    flag_array = (int *)palloc(nkeys*sizeof(int32));
+    
+    i = 0;
+    foreach(xopno, opnos) {
+	opno_array[i++] = (int)lfirst(xopno);
+    }
+
+    i = 0;
+    foreach(xattno,attnos) {
+	attno_array[i++] = (int)lfirst(xattno);
+    }
+
+    i = 0;
+    foreach(value, values) {
+	value_array[i++] = (char *)lfirst(value);
+    }
+
+    i = 0;
+    foreach(flag,flags) {
+	flag_array[i++] = (int)lfirst(flag);
+    }
+    
+    IndexSelectivity(indid,
+		     relid,
+		     nkeys,
+		     classes,	/* not used */
+		     opno_array,
+		     attno_array,
+		     value_array,
+		     flag_array,
+		     idxPages,
+		     idxSelec);
+    return;
+}
+
+/*
+ * restriction_selectivity in lisp system.--
+ *
+ *    NOTE: The routine is now merged with RestrictionClauseSelectivity
+ *    as defined in plancat.c
+ *
+ * Returns the selectivity of a specified operator.
+ * This code executes registered procedures stored in the
+ * operator relation, by calling the function manager.
+ *
+ * XXX The assumption in the selectivity procedures is that if the
+ *	relation OIDs or attribute numbers are -1, then the clause
+ *	isn't of the form (op var const).
+ */
+Cost
+restriction_selectivity(Oid functionObjectId,
+			Oid operatorObjectId,
+			Oid relationObjectId,
+			AttrNumber attributeNumber,
+			char *constValue,
+			int32 constFlag)
+{
+    float64 result;
+
+    result = (float64) fmgr(functionObjectId,
+			    (char *) operatorObjectId,
+			    (char *) relationObjectId, 
+			    (char *) attributeNumber,
+			    (char *) constValue,
+			    (char *) constFlag,
+			    NULL);
+    if (!PointerIsValid(result))
+	elog(WARN, "RestrictionClauseSelectivity: bad pointer");
+
+    if (*result < 0.0 || *result > 1.0)
+	elog(WARN, "RestrictionClauseSelectivity: bad value %lf",
+	     *result);
+
+    return ((Cost)*result);
+}
+
+/*
+ * join_selectivity--
+ *    Similarly, this routine is merged with JoinClauseSelectivity in
+ *    plancat.c
+ *
+ *    Returns the selectivity of an operator, given the join clause
+ *    information.
+ *
+ * XXX The assumption in the selectivity procedures is that if the
+ *	relation OIDs or attribute numbers are -1, then the clause
+ *	isn't of the form (op var var).
+ */
+Cost
+join_selectivity (Oid functionObjectId,
+		  Oid operatorObjectId,
+		  Oid relationObjectId1,
+		  AttrNumber attributeNumber1,
+		  Oid relationObjectId2,
+		  AttrNumber attributeNumber2)
+{
+    float64 result;
+    
+    result = (float64) fmgr(functionObjectId,
+			    (char *) operatorObjectId,
+			    (char *) relationObjectId1,
+			    (char *) attributeNumber1,
+			    (char *) relationObjectId2,
+			    (char *) attributeNumber2,
+			    NULL);
+    if (!PointerIsValid(result))
+	elog(WARN, "JoinClauseSelectivity: bad pointer");
+
+    if (*result < 0.0 || *result > 1.0)
+	elog(WARN, "JoinClauseSelectivity: bad value %lf",
+	     *result);
+
+    return((Cost)*result);
+}
+
+/*
+ * find_all_inheritors--
+ *
+ * Returns a LISP list containing the OIDs of all relations which
+ * inherits from the relation with OID 'inhparent'.
+ */
+List *
+find_inheritance_children(Oid inhparent)
+{
+    static ScanKeyData	key[1] = {
+	{ 0, Anum_pg_inherits_inhparent, F_OIDEQ }
+    };
+
+    HeapTuple	inheritsTuple;
+    Relation	relation;
+    HeapScanDesc scan;
+    List  	*list = NIL;
+    Oid		inhrelid;
+
+    fmgr_info(F_OIDEQ, &key[0].sk_func, &key[0].sk_nargs);
+
+    key[0].sk_argument = ObjectIdGetDatum((Oid)inhparent);
+    relation = heap_openr(InheritsRelationName);
+    scan = heap_beginscan(relation, 0, NowTimeQual, 1, key);
+    while (HeapTupleIsValid(inheritsTuple =
+			    heap_getnext(scan, 0,
+					 (Buffer *) NULL))) {
+	inhrelid = ((InheritsTupleForm)GETSTRUCT(inheritsTuple))->inhrel;
+	list = lappendi(list, inhrelid);
+    }
+    heap_endscan(scan);
+    heap_close(relation);
+    return(list);
+}
+
+/*
+ * VersionGetParents--
+ *
+ * Returns a LISP list containing the OIDs of all relations which are
+ * base relations of the relation with OID 'verrelid'.
+ */
+List *
+VersionGetParents(Oid verrelid)
+{
+    static ScanKeyData	key[1] = {
+	{ 0, Anum_pg_version_verrelid, F_OIDEQ }
+    };
+
+    HeapTuple		versionTuple;
+    Relation		relation;
+    HeapScanDesc	scan;
+    Oid			verbaseid;
+    List 		*list= NIL;
+
+    fmgr_info(F_OIDEQ, &key[0].sk_func, &key[0].sk_nargs);
+    relation = heap_openr(VersionRelationName);
+    key[0].sk_argument = ObjectIdGetDatum(verrelid);
+    scan = heap_beginscan(relation, 0, NowTimeQual, 1, key);
+    for (;;) {
+	versionTuple = heap_getnext(scan, 0,
+				    (Buffer *) NULL);
+	if (!HeapTupleIsValid(versionTuple))
+	    break;
+	verbaseid = ((VersionTupleForm)
+		     GETSTRUCT(versionTuple))->verbaseid;
+
+	list = lconsi(verbaseid, list);
+
+	key[0].sk_argument = ObjectIdGetDatum(verbaseid);
+	heap_rescan(scan, 0, key);
+    }
+    heap_endscan(scan);
+    heap_close(relation);
+    return(list);
+}
+
+/*****************************************************************************
+ *
+ *****************************************************************************/
+
+/*
+ * IdexSelectivity--
+ *
+ *    Retrieves the 'amopnpages' and 'amopselect' parameters for each
+ *    AM operator when a given index (specified by 'indexrelid') is used.
+ *    These two parameters are returned by copying them to into an array of
+ *    floats.
+ *
+ *    Assumption: the attribute numbers and operator ObjectIds are in order
+ *    WRT to each other (otherwise, you have no way of knowing which
+ *    AM operator class or attribute number corresponds to which operator.
+ *
+ * 'varAttributeNumbers' contains attribute numbers for variables
+ * 'constValues' contains the constant values
+ * 'constFlags' describes how to treat the constants in each clause
+ * 'nIndexKeys' describes how many keys the index actually has
+ *
+ * Returns 'selectivityInfo' filled with the sum of all pages touched
+ * and the product of each clause's selectivity.
+ *
+ */
+static void
+IndexSelectivity(Oid indexrelid,
+		 Oid indrelid,
+		 int32 nIndexKeys,
+		 Oid AccessMethodOperatorClasses[], /* XXX not used? */
+		 Oid operatorObjectIds[],
+		 int32 varAttributeNumbers[],
+		 char *constValues[],
+		 int32 constFlags[],
+		 float *idxPages,
+		 float *idxSelec)
+{
+    register	i, n;
+    HeapTuple	indexTuple, amopTuple, indRel;
+    IndexTupleForm	index;
+    Form_pg_amop	amop;
+    Oid		indclass;
+    float64data	npages, select;
+    float64	amopnpages, amopselect;
+    Oid relam;
+
+    indRel = SearchSysCacheTuple(RELOID,
+				 ObjectIdGetDatum(indexrelid),
+				 0,0,0);
+    if (!HeapTupleIsValid(indRel))
+	elog(WARN, "IndexSelectivity: index %d not found",
+	     indexrelid);
+    relam = ((Form_pg_class)GETSTRUCT(indRel))->relam;
+
+    indexTuple = SearchSysCacheTuple(INDEXRELID,
+				     ObjectIdGetDatum(indexrelid),
+				     0,0,0);
+    if (!HeapTupleIsValid(indexTuple))
+	elog(WARN, "IndexSelectivity: index %d not found",
+	     indexrelid);
+    index = (IndexTupleForm)GETSTRUCT(indexTuple);
+
+    npages = 0.0;
+    select = 1.0;
+    for (n = 0; n < nIndexKeys; ++n) {
+	/* 
+	 * Find the AM class for this key. 
+	 *
+	 * If the first attribute number is invalid then we have a
+	 * functional index, and AM class is the first one defined
+	 * since functional indices have exactly one key.
+	 */
+	indclass = (varAttributeNumbers[0] == InvalidAttrNumber) ?
+	    index->indclass[0] : InvalidOid;
+	i = 0;
+	while ((i < nIndexKeys) && (indclass == InvalidOid)) {
+	    if (varAttributeNumbers[n] == index->indkey[i]) {
+		indclass = index->indclass[i];
+		break;
+	    }
+	    i++;
+	}
+	if (!OidIsValid(indclass)) {
+	    /*
+	     * Presumably this means that we are using a functional
+	     * index clause and so had no variable to match to
+	     * the index key ... if not we are in trouble.
+	     */
+	    elog(NOTICE, "IndexSelectivity: no key %d in index %d",
+		 varAttributeNumbers[n], indexrelid);
+	    continue;
+	}
+
+	amopTuple = SearchSysCacheTuple(AMOPOPID,
+					ObjectIdGetDatum(indclass),
+					ObjectIdGetDatum(operatorObjectIds[n]),
+					ObjectIdGetDatum(relam),
+					0);
+	if (!HeapTupleIsValid(amopTuple))
+	    elog(WARN, "IndexSelectivity: no amop %d %d",
+		 indclass, operatorObjectIds[n]);
+	amop = (Form_pg_amop)GETSTRUCT(amopTuple);
+	amopnpages = (float64) fmgr(amop->amopnpages,
+				    (char *) operatorObjectIds[n],
+				    (char *) indrelid,
+				    (char *) varAttributeNumbers[n],
+				    (char *) constValues[n],
+				    (char *) constFlags[n],
+				    (char *) nIndexKeys, 
+				    (char *) indexrelid);
+	npages += PointerIsValid(amopnpages) ? *amopnpages : 0.0;
+	if ((i = npages) < npages) /* ceil(npages)? */
+	    npages += 1.0;
+	amopselect = (float64) fmgr(amop->amopselect,
+				    (char *) operatorObjectIds[n],
+				    (char *) indrelid,
+				    (char *) varAttributeNumbers[n],
+				    (char *) constValues[n],
+				    (char *) constFlags[n],
+				    (char *) nIndexKeys,
+				    (char *) indexrelid);
+	select *= PointerIsValid(amopselect) ? *amopselect : 1.0;
+    }
+    *idxPages = npages;
+    *idxSelec = select;
+}
+
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
new file mode 100644
index 00000000000..351fb182107
--- /dev/null
+++ b/src/backend/optimizer/util/relnode.c
@@ -0,0 +1,123 @@
+/*-------------------------------------------------------------------------
+ *
+ * relnode.c--
+ *    Relation manipulation routines
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.1.1.1 1996/07/09 06:21:39 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/relation.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/pathnode.h"		/* where the decls go */
+#include "optimizer/plancat.h"
+
+
+
+/*    
+ * get_base_rel--
+ *    Returns relation entry corresponding to 'relid', creating a new one if
+ *    necessary. This is for base relations.
+ *    
+ */
+Rel *get_base_rel(Query* root, int relid)
+{
+    List *relids;
+    Rel *rel;
+
+    relids = lconsi(relid, NIL);
+    rel = rel_member(relids, root->base_relation_list_);
+    if (rel==NULL) {
+	rel = makeNode(Rel);
+	rel->relids = relids;
+	rel->indexed = false;
+	rel->pages =  0;
+	rel->tuples = 0;
+	rel->width = 0;
+	rel->targetlist = NIL;
+	rel->pathlist = NIL;
+	rel->unorderedpath = (Path *)NULL;
+	rel->cheapestpath = (Path *)NULL;
+	rel->pruneable = true;
+	rel->classlist = NULL;
+	rel->ordering = NULL;
+	rel->relam = InvalidOid;
+	rel->clauseinfo = NIL;
+	rel->joininfo = NIL;
+	rel->innerjoin = NIL;
+	rel->superrels = NIL;
+	
+	root->base_relation_list_ = lcons(rel,
+				    root->base_relation_list_);
+	
+	/*
+	 * ??? the old lispy C code (get_rel) do a listp(relid) here but
+	 * that can never happen since we already established relid is not
+	 * a list.				-ay 10/94
+	 */
+	if(relid < 0) {
+	    /*
+	     * If the relation is a materialized relation, assume 
+	     * constants for sizes.
+	     */
+	    rel->pages = _TEMP_RELATION_PAGES_;
+	    rel->tuples = _TEMP_RELATION_TUPLES_;
+	    
+	} else {
+	    bool hasindex;
+	    int pages, tuples;
+	    
+	    /*
+	     * Otherwise, retrieve relation characteristics from the
+	     * system catalogs.
+	     */
+	    relation_info(root, relid, &hasindex, &pages, &tuples);
+	    rel->indexed = hasindex;
+	    rel->pages = pages;
+	    rel->tuples = tuples;
+	} 
+    }
+    return rel;
+}
+
+/*    
+ * get_join_rel--
+ *    Returns relation entry corresponding to 'relid' (a list of relids),
+ *    creating a new one if necessary. This is for join relations.
+ *    
+ */
+Rel *get_join_rel(Query *root, List *relid)
+{
+    return rel_member(relid, root->join_relation_list_);
+}
+
+/*    
+ * rel-member--
+ *    Determines whether a relation of id 'relid' is contained within a list
+ *    'rels'.  
+ *    
+ * Returns the corresponding entry in 'rels' if it is there.
+ *    
+ */
+Rel *
+rel_member(List *relid, List *rels)
+{
+    List *temp = NIL;
+    List *temprelid = NIL;
+    
+    if (relid!=NIL && rels!=NIL) {
+	foreach(temp,rels) {
+	    temprelid = ((Rel*)lfirst(temp))->relids;
+	    if(same(temprelid, relid))   
+		return((Rel*)(lfirst(temp)));
+	}
+    } 
+    return(NULL);
+}
diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
new file mode 100644
index 00000000000..073c2a08231
--- /dev/null
+++ b/src/backend/optimizer/util/tlist.c
@@ -0,0 +1,577 @@
+/*-------------------------------------------------------------------------
+ *
+ * tlist.c--
+ *    Target list manipulation routines
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/tlist.c,v 1.1.1.1 1996/07/09 06:21:39 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/relation.h"
+#include "nodes/primnodes.h"
+#include "nodes/pg_list.h"
+#include "nodes/nodeFuncs.h"
+#include "utils/elog.h"
+#include "utils/lsyscache.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/var.h"
+#include "optimizer/tlist.h"
+#include "optimizer/clauses.h"
+
+#include "nodes/makefuncs.h"
+#include "parser/catalog_utils.h"
+
+static Node *flatten_tlistentry(Node *tlistentry, List *flat_tlist);
+
+/*****************************************************************************
+ *  ---------- RELATION node target list routines ----------
+ *****************************************************************************/
+
+/*    
+ * tlistentry-member--
+ *    
+ * RETURNS:  the leftmost member of sequence "targetlist" that satisfies
+ *           the predicate "var_equal"
+ * MODIFIES: nothing
+ * REQUIRES: test = function which can operate on a lispval union
+ *           var = valid var-node
+ *	     targetlist = valid sequence
+ */
+TargetEntry *
+tlistentry_member(Var *var, List *targetlist)
+{
+    if (var) {
+	List *temp = NIL;
+
+	foreach (temp,targetlist) {
+	    if (var_equal(var,
+			  get_expr(lfirst(temp))))
+		return((TargetEntry*)lfirst(temp));
+	}
+    }
+    return (NULL);
+}
+
+/*    
+ * matching_tlvar--
+ *    
+ * RETURNS:  var node in a target list which is var_equal to 'var',
+ *    	     if one exists.
+ * REQUIRES: "test" operates on lispval unions,
+ * 
+ */
+Expr *
+matching_tlvar(Var *var, List *targetlist)
+{
+    TargetEntry *tlentry;
+
+    tlentry = tlistentry_member(var,targetlist);
+    if (tlentry) 
+	return((Expr*)get_expr (tlentry) );
+
+    return((Expr*) NULL);
+}
+
+/*    
+ * add_tl_element--
+ *    Creates a targetlist entry corresponding to the supplied var node
+ *
+ * 'var' and adds the new targetlist entry to the targetlist field of
+ * 'rel' 
+ *    
+ * RETURNS: nothing
+ * MODIFIES: vartype and varid fields of leftmost varnode that matches
+ *           argument "var" (sometimes).
+ * CREATES:  new var-node iff no matching var-node exists in targetlist
+ */
+void
+add_tl_element(Rel *rel, Var *var)
+{
+    Expr *oldvar = (Expr *)NULL;
+    
+    oldvar = matching_tlvar(var, rel->targetlist);
+    
+    /*
+     * If 'var' is not already in 'rel's target list, add a new node. 
+     */
+    if (oldvar==NULL) {
+	List *tlist = rel->targetlist;
+	Var *newvar = makeVar(var->varno,
+			      var->varattno,
+			      var->vartype,
+			      var->varno,
+			      var->varoattno);
+
+	rel->targetlist =
+	    lappend (tlist,
+		      create_tl_element(newvar,
+					length(tlist) + 1));
+
+    }
+}
+
+/*    
+ * create_tl_element--
+ *    Creates a target list entry node and its associated (resdom var) pair
+ *    with its resdom number equal to 'resdomno' and the joinlist field set
+ *    to 'joinlist'.
+ *    
+ * RETURNS:  newly created tlist-entry
+ * CREATES:  new targetlist entry (always).
+ */
+TargetEntry*
+create_tl_element(Var *var, int resdomno)
+{
+    TargetEntry *tlelement= makeNode(TargetEntry);
+    
+    tlelement->resdom =
+	makeResdom(resdomno, 
+		   var->vartype,
+		   get_typlen(var->vartype),
+		   NULL,
+		   (Index)0,
+		   (Oid)0,
+		   0);
+    tlelement->expr = (Node*)var;
+    
+    return(tlelement);
+}
+
+/*    
+ * get-actual-tlist--
+ *    Returns the targetlist elements from a relation tlist.
+ *    
+ */
+List *
+get_actual_tlist(List *tlist)
+{
+    /*
+     * this function is not making sense. - ay 10/94
+     */
+#if 0 
+    List *element = NIL;
+    List *result = NIL;
+    
+    if (tlist==NULL) {
+	elog(DEBUG,"calling get_actual_tlist with empty tlist");
+	return(NIL);
+    }
+    /* XXX - it is unclear to me what exactly get_entry 
+       should be doing, as it is unclear to me the exact
+       relationship between "TL" "TLE" and joinlists */
+
+    foreach(element,tlist)
+	result = lappend(result, lfirst((List*)lfirst(element)));
+    
+    return(result);
+#endif
+    return tlist;
+}
+
+/*****************************************************************************
+ *    	---------- GENERAL target list routines ----------
+ *****************************************************************************/
+
+/*    
+ * tlist-member--
+ *    Determines whether a var node is already contained within a
+ *    target list.
+ *    
+ * 'var' is the var node
+ * 'tlist' is the target list
+ * 'dots' is t if we must match dotfields to determine uniqueness
+ *    
+ * Returns the resdom entry of the matching var node.
+ *    
+ */
+Resdom *
+tlist_member(Var *var, List *tlist)
+{
+    List *i = NIL;
+    TargetEntry *temp_tle = (TargetEntry *)NULL;
+    TargetEntry *tl_elt = (TargetEntry *)NULL;
+
+    if (var) {
+	foreach (i,tlist) {
+	    temp_tle = (TargetEntry *)lfirst(i);
+	    if (var_equal(var, get_expr(temp_tle))) {
+		tl_elt = temp_tle;
+		break;
+	    }
+	}
+
+	if (tl_elt != NULL)
+	    return(tl_elt->resdom);
+	else 
+	    return((Resdom*)NULL);
+    }
+    return ((Resdom*)NULL);
+}
+
+/*
+ *   Routine to get the resdom out of a targetlist.
+ */
+Resdom *
+tlist_resdom(List *tlist, Resdom *resnode)
+{
+    Resdom *resdom = (Resdom*)NULL;
+    List *i = NIL;
+    TargetEntry *temp_tle = (TargetEntry *)NULL;
+
+    foreach(i,tlist) {
+	temp_tle = (TargetEntry *)lfirst(i);
+	resdom = temp_tle->resdom;
+	/*  Since resnos are supposed to be unique */
+	if (resnode->resno == resdom->resno)  
+	    return(resdom);
+    }
+    return((Resdom*)NULL);
+}
+
+
+/*    
+ * match_varid--
+ *    Searches a target list for an entry with some desired varid.
+ *    
+ * 'varid' is the desired id
+ * 'tlist' is the target list that is searched
+ *    
+ * Returns the target list entry (resdom var) of the matching var.
+ *
+ * Now checks to make sure array references (in addition to range
+ * table indices) are identical - retrieve (a.b[1],a.b[2]) should
+ * not be turned into retrieve (a.b[1],a.b[1]).
+ *    
+ * [what used to be varid is now broken up into two fields varnoold and
+ *  varoattno. Also, nested attnos are long gone. - ay 2/95]
+ */
+TargetEntry *
+match_varid(Var *test_var, List *tlist)
+{
+    List *tl;
+    Oid type_var;
+
+    type_var = (Oid) test_var->vartype;
+
+    foreach (tl, tlist) {
+	TargetEntry *entry;
+	Var *tlvar;
+
+	entry = lfirst(tl);
+	tlvar = get_expr(entry);
+
+	/*
+	 * we test the original varno (instead of varno which might
+	 * be changed to INNER/OUTER.
+	 */
+	if (tlvar->varnoold == test_var->varnoold &&
+	    tlvar->varoattno == test_var->varoattno) {
+
+	    if (tlvar->vartype == type_var)
+		return(entry);
+	}
+    }
+
+    return (NULL);
+}
+
+
+/*    
+ * new-unsorted-tlist--
+ *    Creates a copy of a target list by creating new resdom nodes
+ *    without sort information.
+ *    
+ * 'targetlist' is the target list to be copied.
+ *    
+ * Returns the resulting target list.
+ *    
+ */
+List *
+new_unsorted_tlist(List *targetlist)
+{
+    List *new_targetlist = (List*)copyObject ((Node*)targetlist);
+    List *x = NIL;
+
+    foreach (x, new_targetlist) {
+	TargetEntry *tle = (TargetEntry *)lfirst(x);
+	tle->resdom->reskey = 0;
+	tle->resdom->reskeyop = (Oid)0;
+    }
+    return(new_targetlist);
+}
+
+/*    
+ * copy-vars--
+ *    Replaces the var nodes in the first target list with those from
+ *    the second target list.  The two target lists are assumed to be
+ *    identical except their actual resdoms and vars are different.
+ *    
+ * 'target' is the target list to be replaced
+ * 'source' is the target list to be copied
+ *    
+ * Returns a new target list.
+ *    
+ */
+List *
+copy_vars(List *target, List *source)
+{
+    List *result = NIL;
+    List *src = NIL;
+    List *dest = NIL;
+    
+    for ( src = source, dest = target; src != NIL &&
+	 dest != NIL; src = lnext(src), dest = lnext(dest)) {
+	TargetEntry *temp = MakeTLE(((TargetEntry *)lfirst(dest))->resdom,
+				 (Node*)get_expr(lfirst(src)));
+	result = lappend(result,temp);
+    }
+    return(result);
+}
+
+/*    
+ * flatten-tlist--
+ *    Create a target list that only contains unique variables.
+ *
+ *
+ * 'tlist' is the current target list
+ *    
+ * Returns the "flattened" new target list.
+ *    
+ */
+List *
+flatten_tlist(List *tlist)
+{
+    int last_resdomno = 1;
+    List *new_tlist = NIL;
+    List *tlist_vars = NIL;
+    List *temp;
+
+    foreach (temp, tlist)  {
+	TargetEntry *temp_entry = NULL;
+	List *vars;
+
+	temp_entry = lfirst(temp);
+	vars = pull_var_clause((Node*)get_expr(temp_entry));
+	if(vars != NULL) {
+	    tlist_vars = nconc(tlist_vars, vars);
+	}
+    }
+
+    foreach (temp, tlist_vars) {
+	Var *var = lfirst(temp);
+	if (!(tlist_member(var, new_tlist))) {
+	    Resdom *r;
+
+	    r = makeResdom(last_resdomno,
+			   var->vartype,
+			   get_typlen(var->vartype),
+			   NULL,
+			   (Index)0,
+			   (Oid)0,
+			   0);
+	    last_resdomno++;
+	    new_tlist = lappend(new_tlist, MakeTLE (r, (Node*)var));
+	}
+    }
+
+    return new_tlist;
+}
+
+/*    
+ * flatten-tlist-vars--
+ *    Redoes the target list of a query with no nested attributes by
+ *    replacing vars within computational expressions with vars from
+ *    the 'flattened' target list of the query.
+ *    
+ * 'full-tlist' is the actual target list
+ * 'flat-tlist' is the flattened (var-only) target list
+ *    
+ * Returns the modified actual target list.
+ *    
+ */
+List *
+flatten_tlist_vars(List *full_tlist, List *flat_tlist)
+{
+    List *x = NIL;
+    List *result = NIL;
+    
+    foreach(x,full_tlist) {
+	TargetEntry *tle= lfirst(x);
+	result =
+	    lappend(result,
+		     MakeTLE(tle->resdom,
+			     flatten_tlistentry((Node*)get_expr(tle),
+						flat_tlist)));
+    }
+
+    return(result);
+}
+
+/*    
+ * flatten-tlistentry--
+ *    Replaces vars within a target list entry with vars from a flattened
+ *    target list.
+ *    
+ * 'tlistentry' is the target list entry to be modified
+ * 'flat-tlist' is the flattened target list
+ *    
+ * Returns the (modified) target_list entry from the target list.
+ *    
+ */
+static Node *
+flatten_tlistentry(Node *tlistentry, List *flat_tlist)
+{
+    if (tlistentry==NULL) {
+
+	return NULL;
+
+    } else if (IsA (tlistentry,Var)) {
+
+	return
+	    ((Node *)get_expr(match_varid((Var*)tlistentry,
+					  flat_tlist)));
+    } else if (IsA (tlistentry,Iter)) {
+
+	((Iter*)tlistentry)->iterexpr = 
+	    flatten_tlistentry((Node*)((Iter*)tlistentry)->iterexpr,
+			       flat_tlist);
+	return tlistentry;
+
+    } else if (single_node(tlistentry)) {
+
+	return tlistentry;
+
+    } else if (is_funcclause (tlistentry)) {
+	Expr *expr = (Expr*)tlistentry;
+	List *temp_result = NIL;
+	List *elt = NIL;
+	
+	foreach(elt, expr->args)
+	    temp_result = lappend(temp_result,
+				   flatten_tlistentry(lfirst(elt),flat_tlist));
+	
+	return
+	    ((Node *)make_funcclause((Func*)expr->oper, temp_result));
+
+    } else if (IsA(tlistentry,Aggreg)) {
+
+	return tlistentry;
+
+    } else if (IsA(tlistentry,ArrayRef)) {
+	ArrayRef *aref = (ArrayRef *)tlistentry;
+	List *temp = NIL;
+	List *elt = NIL;
+
+	foreach(elt, aref->refupperindexpr)
+	    temp = lappend(temp, flatten_tlistentry(lfirst(elt), flat_tlist));
+	aref->refupperindexpr = temp;
+
+	temp = NIL;
+	foreach(elt, aref->reflowerindexpr)
+	    temp = lappend(temp, flatten_tlistentry(lfirst(elt), flat_tlist));
+	aref->reflowerindexpr = temp;
+
+	aref->refexpr = 
+	    flatten_tlistentry(aref->refexpr, flat_tlist);
+
+	aref->refassgnexpr = 
+	    flatten_tlistentry(aref->refassgnexpr, flat_tlist);
+
+	return tlistentry;
+    } else {
+	Expr *expr = (Expr*)tlistentry;
+	Var *left =
+	    (Var*)flatten_tlistentry((Node*)get_leftop(expr),
+				     flat_tlist);
+	Var *right =
+	    (Var*)flatten_tlistentry((Node*)get_rightop(expr),
+				     flat_tlist);
+
+	return((Node *)
+	       make_opclause((Oper*)expr->oper, left, right));
+    }
+}
+
+
+TargetEntry *
+MakeTLE(Resdom *resdom, Node *expr)
+{
+    TargetEntry *rt = makeNode(TargetEntry);
+
+    rt->resdom = resdom;
+    rt->expr = expr;
+    return rt;
+}
+
+Var *
+get_expr(TargetEntry *tle)
+{
+    Assert(tle!=NULL);
+    Assert(tle->expr!=NULL);
+
+    return ((Var *)tle->expr); 
+}
+
+
+/*****************************************************************************
+ *
+ *****************************************************************************/
+
+/*
+ * AddGroupAttrToTlist -
+ *    append the group attribute to the target list if it's not already
+ *    in there.
+ */
+void
+AddGroupAttrToTlist(List *tlist, List *grpCl)
+{
+    List *gl;
+    int last_resdomno = length(tlist) + 1;
+    
+    foreach (gl, grpCl) {
+	GroupClause *gc = (GroupClause*)lfirst(gl);
+	Var *var = gc->grpAttr;
+
+	if (!(tlist_member(var, tlist))) {
+	    Resdom *r;
+
+	    r = makeResdom(last_resdomno,
+			   var->vartype,
+			   get_typlen(var->vartype),
+			   NULL,
+			   (Index)0,
+			   (Oid)0,
+			   0);
+	    last_resdomno++;
+	    tlist = lappend(tlist, MakeTLE(r, (Node*)var));
+	}
+    }
+}
+
+/* was ExecTargetListLength() in execQual.c, 
+   moved here to reduce dependencies on the executor module */
+int
+exec_tlist_length(List *targetlist)
+{
+    int len;
+    List *tl;
+    TargetEntry *curTle;
+    
+    len = 0;
+    foreach (tl, targetlist) {
+	curTle = lfirst(tl);
+	
+	if (curTle->resdom != NULL)
+	    len++;
+    }
+    return len;
+}
+
+
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
new file mode 100644
index 00000000000..b4f8436c775
--- /dev/null
+++ b/src/backend/optimizer/util/var.c
@@ -0,0 +1,189 @@
+/*-------------------------------------------------------------------------
+ *
+ * var.c--
+ *    Var node manipulation routines
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.1.1.1 1996/07/09 06:21:39 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "nodes/primnodes.h"
+#include "nodes/nodeFuncs.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/clauses.h"
+#include "optimizer/var.h"
+
+#include "parser/parsetree.h"
+
+/*
+ *	find_varnos
+ *
+ *	Descends down part of a parsetree (qual or tlist),
+ *
+ *	XXX assumes varno's are always integers, which shouldn't be true...
+ *	(though it currently is, see primnodes.h)
+ */
+List *
+pull_varnos(Node *me)
+{
+    List *i, *result = NIL;
+	
+    if (me == NULL)
+	return (NIL);
+
+    switch (nodeTag(me)) {
+    case T_List:
+	foreach (i, (List*)me) {
+	    result = nconc(result, pull_varnos(lfirst(i)));
+	}
+	break;
+    case T_ArrayRef:
+	foreach (i, ((ArrayRef*) me)->refupperindexpr) 
+	    result = nconc(result, pull_varnos(lfirst(i)));
+	foreach (i, ((ArrayRef*) me)->reflowerindexpr)
+	    result = nconc(result, pull_varnos(lfirst(i)));
+	result = nconc(result, pull_varnos(((ArrayRef*) me)->refassgnexpr));
+	break;
+    case T_Var:
+	result = lconsi(((Var*) me)->varno, NIL);
+	break;
+    default:
+	break;
+    }
+    return(result);
+}
+
+/*    
+ * contain_var_clause--
+ *    Recursively find var nodes from a clause by pulling vars from the
+ *    left and right operands of the clause.  
+ *    
+ *    Returns true if any varnode found.
+ */
+bool contain_var_clause(Node *clause)
+{
+    if (clause==NULL) 
+	return FALSE;
+    else if (IsA(clause,Var))
+	return TRUE;
+    else if (IsA(clause,Iter))
+	return contain_var_clause(((Iter*)clause)->iterexpr);
+    else if (single_node(clause)) 
+	return FALSE;
+    else if (or_clause(clause)) {
+	List *temp;
+
+	foreach (temp, ((Expr*)clause)->args) {
+	    if (contain_var_clause(lfirst(temp)))
+		return TRUE;
+	}
+	return FALSE;
+    } else if (is_funcclause (clause)) {
+	List *temp;
+
+	foreach(temp, ((Expr *)clause)->args) {
+	    if (contain_var_clause(lfirst(temp)))
+		return TRUE;
+	}
+	return FALSE;
+    } else if (IsA(clause,ArrayRef)) {
+	List *temp;
+
+	foreach(temp, ((ArrayRef*)clause)->refupperindexpr)  {
+	    if (contain_var_clause(lfirst(temp)))
+		return TRUE;
+	}
+	foreach(temp, ((ArrayRef*)clause)->reflowerindexpr) {
+	    if (contain_var_clause(lfirst(temp)))
+		return TRUE;
+	}
+	if (contain_var_clause(((ArrayRef*)clause)->refexpr))
+	    return TRUE;
+	if (contain_var_clause(((ArrayRef*)clause)->refassgnexpr))
+	    return TRUE;
+	return FALSE;
+    } else if (not_clause(clause))
+	return contain_var_clause((Node*)get_notclausearg((Expr*)clause));
+    else if (is_opclause(clause))
+	return (contain_var_clause((Node*)get_leftop((Expr*)clause)) ||
+		contain_var_clause((Node*)get_rightop((Expr*)clause)));
+
+    return FALSE;
+}
+
+/*    
+ * pull_var_clause--
+ *    Recursively pulls all var nodes from a clause by pulling vars from the
+ *    left and right operands of the clause.  
+ *    
+ *    Returns list of varnodes found.
+ */
+List *
+pull_var_clause(Node *clause)
+{
+    List *retval = NIL;
+
+    if (clause==NULL) 
+	return(NIL);
+    else if (IsA(clause,Var))
+	retval = lcons(clause,NIL);
+    else if (IsA(clause,Iter))
+	retval = pull_var_clause(((Iter*)clause)->iterexpr);
+    else if (single_node(clause)) 
+	retval = NIL;
+    else if (or_clause(clause)) {
+	List *temp;
+
+	foreach (temp, ((Expr*)clause)->args)
+	    retval = nconc(retval, pull_var_clause(lfirst(temp)));
+    } else if (is_funcclause (clause)) {
+	List *temp;
+
+	foreach(temp, ((Expr *)clause)->args)
+	    retval = nconc (retval,pull_var_clause(lfirst(temp)));
+    } else if (IsA(clause,Aggreg)) {
+	retval = pull_var_clause(((Aggreg*)clause)->target);
+    } else if (IsA(clause,ArrayRef)) {
+	List *temp;
+
+	foreach(temp, ((ArrayRef*)clause)->refupperindexpr) 
+	    retval = nconc (retval,pull_var_clause(lfirst(temp)));
+	foreach(temp, ((ArrayRef*)clause)->reflowerindexpr)
+	    retval = nconc (retval,pull_var_clause(lfirst(temp)));
+	retval = nconc(retval,
+		       pull_var_clause(((ArrayRef*)clause)->refexpr));
+	retval = nconc(retval,
+		       pull_var_clause(((ArrayRef*)clause)->refassgnexpr));
+    } else if (not_clause(clause))
+	retval = pull_var_clause((Node*)get_notclausearg((Expr*)clause));
+    else if (is_opclause(clause)) 
+	retval = nconc(pull_var_clause((Node*)get_leftop((Expr*)clause)),
+		       pull_var_clause((Node*)get_rightop((Expr*)clause)));
+    else
+	retval = NIL;
+
+    return (retval);
+}
+
+/*    
+ *    	var_equal
+ *    
+ *    	Returns t iff two var nodes correspond to the same attribute.
+ */
+bool
+var_equal(Var *var1, Var *var2)
+{
+    if (IsA (var1,Var) && IsA (var2,Var) &&
+	(((Var*)var1)->varno ==  ((Var*)var2)->varno) &&
+	(((Var*)var1)->vartype == ((Var*)var2)->vartype) && 
+	(((Var*)var1)->varattno == ((Var*)var2)->varattno)) {
+
+	return(true);
+    } else 
+	return(false);
+}