From ac4913a0dd433ac1c2207014f886338f2ccd5fef Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Sat, 24 Jul 1999 23:21:14 +0000
Subject: [PATCH] Clean up messy clause-selectivity code in clausesel.c; repair
 bug identified by Hiroshi (incorrect cost attributed to OR clauses after
 multiple passes through set_rest_selec()).  I think the code was trying to
 allow selectivities of OR subclauses to be passed in from outside, but
 noplace was actually passing any useful data, and set_rest_selec() was
 passing wrong data.

Restructure representation of "indexqual" in IndexPath nodes so that
it is the same as for indxqual in completed IndexScan nodes: namely,
a toplevel list with an entry for each pass of the index scan, having
sublists that are implicitly-ANDed index qual conditions for that pass.
You don't want to know what the old representation was :-(

Improve documentation of OR-clause indexscan functions.

Remove useless 'notclause' field from RestrictInfo nodes.  (This might
force an initdb for anyone who has stored rules containing RestrictInfos,
but I do not think that RestrictInfo ever appears in completed plans.)
---
 src/backend/nodes/copyfuncs.c             |   3 +-
 src/backend/nodes/equalfuncs.c            |   4 +-
 src/backend/nodes/outfuncs.c              |   7 +-
 src/backend/nodes/readfuncs.c             |  10 +-
 src/backend/optimizer/path/allpaths.c     |  24 +-
 src/backend/optimizer/path/clausesel.c    | 363 +++++++++-------------
 src/backend/optimizer/path/indxpath.c     |  57 ++--
 src/backend/optimizer/path/orindxpath.c   | 183 ++++++-----
 src/backend/optimizer/plan/createplan.c   | 108 ++++---
 src/backend/optimizer/plan/initsplan.c    | 121 +++-----
 src/backend/optimizer/util/clauses.c      |  49 +--
 src/backend/optimizer/util/pathnode.c     |   5 +-
 src/backend/optimizer/util/restrictinfo.c |  10 +-
 src/include/nodes/relation.h              |  33 +-
 src/include/optimizer/clauses.h           |   4 +-
 src/include/optimizer/cost.h              |   5 +-
 src/include/optimizer/restrictinfo.h      |   4 +-
 17 files changed, 471 insertions(+), 519 deletions(-)

diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 217bfc5447..ba41233205 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.86 1999/07/17 20:17:05 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.87 1999/07/24 23:21:06 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1317,7 +1317,6 @@ _copyRestrictInfo(RestrictInfo *from)
 	Node_Copy(from, newnode, clause);
 
 	newnode->selectivity = from->selectivity;
-	newnode->notclause = from->notclause;
 
 	Node_Copy(from, newnode, indexids);
 	Node_Copy(from, newnode, mergejoinorder);
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index 9f16875f34..5560deaea5 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.43 1999/07/17 20:17:05 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.44 1999/07/24 23:21:06 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -305,8 +305,6 @@ _equalRestrictInfo(RestrictInfo *a, RestrictInfo *b)
 		return false;
 	if (a->selectivity != b->selectivity)
 		return false;
-	if (a->notclause != b->notclause)
-		return false;
 #ifdef EqualMergeOrderExists
 	if (!EqualMergeOrder(a->mergejoinorder, b->mergejoinorder))
 		return false;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 23c10fed5e..4272bf04cc 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -5,7 +5,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- *	$Id: outfuncs.c,v 1.90 1999/07/18 19:02:49 tgl Exp $
+ *	$Id: outfuncs.c,v 1.91 1999/07/24 23:21:07 tgl Exp $
  *
  * NOTES
  *	  Every (plan) node in POSTGRES has an associated "out" routine which
@@ -1110,9 +1110,8 @@ _outRestrictInfo(StringInfo str, RestrictInfo *node)
 	_outNode(str, node->clause);
 
 	appendStringInfo(str,
-					 " :selectivity %f :notclause %s :indexids ",
-					 node->selectivity,
-					 node->notclause ? "true" : "false");
+					 " :selectivity %f :indexids ",
+					 node->selectivity);
 	_outNode(str, node->indexids);
 
 	appendStringInfo(str, " :mergejoinorder ");
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 9d46b7e39d..e16398fb85 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.69 1999/07/17 20:17:08 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.70 1999/07/24 23:21:08 tgl Exp $
  *
  * NOTES
  *	  Most of the read functions for plan nodes are tested. (In fact, they
@@ -1856,14 +1856,6 @@ _readRestrictInfo()
 
 	local_node->selectivity = atof(token);
 
-	token = lsptok(NULL, &length);		/* get :notclause */
-	token = lsptok(NULL, &length);		/* now read it */
-
-	if (!strncmp(token, "true", 4))
-		local_node->notclause = true;
-	else
-		local_node->notclause = false;
-
 	token = lsptok(NULL, &length);		/* get :indexids */
 	local_node->indexids = nodeRead(true);		/* now read it */
 
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 220b3cd047..373d982c49 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.50 1999/07/17 20:17:11 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.51 1999/07/24 23:21:08 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -86,8 +86,8 @@ make_one_rel(Query *root, List *rels)
  * set_base_rel_pathlist
  *	  Finds all paths available for scanning each relation entry in
  *	  'rels'.  Sequential scan and any available indices are considered
- *	  if possible(indices are not considered for lower nesting levels).
- *	  All unique paths are attached to the relation's 'pathlist' field.
+ *	  if possible (indices are not considered for lower nesting levels).
+ *	  All useful paths are attached to the relation's 'pathlist' field.
  *
  *	  MODIFIES: rels
  */
@@ -98,21 +98,32 @@ set_base_rel_pathlist(Query *root, List *rels)
 
 	foreach(temp, rels)
 	{
+		RelOptInfo *rel = (RelOptInfo *) lfirst(temp);
+		List	   *indices = find_relation_indices(root, rel);
 		List	   *sequential_scan_list;
 		List	   *rel_index_scan_list;
 		List	   *or_index_scan_list;
-		RelOptInfo *rel = (RelOptInfo *) lfirst(temp);
 
 		sequential_scan_list = lcons(create_seqscan_path(rel), NIL);
 
 		rel_index_scan_list = create_index_paths(root,
 												 rel,
-										find_relation_indices(root, rel),
+												 indices,
 												 rel->restrictinfo,
 												 rel->joininfo);
 
-		or_index_scan_list = create_or_index_paths(root, rel, rel->restrictinfo);
+		/* Note: create_or_index_paths depends on create_index_paths
+		 * to have marked OR restriction clauses with relevant indices;
+		 * this is why it doesn't need to be given the full list of indices.
+		 */
 
+		or_index_scan_list = create_or_index_paths(root, rel,
+												   rel->restrictinfo);
+
+		/* add_pathlist will discard any paths that are dominated by
+		 * another available path, keeping only those paths that are
+		 * superior along at least one dimension of cost or sortedness.
+		 */
 		rel->pathlist = add_pathlist(rel,
 									 sequential_scan_list,
 									 nconc(rel_index_scan_list,
@@ -128,7 +139,6 @@ set_base_rel_pathlist(Query *root, List *rels)
 		rel->size = compute_rel_size(rel);
 		rel->width = compute_rel_width(rel);
 	}
-	return;
 }
 
 /*
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index df0b4aabb4..00d3780a35 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.23 1999/07/16 04:59:14 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.24 1999/07/24 23:21:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,32 +23,26 @@
 #include "utils/lsyscache.h"
 
 
-static Cost compute_selec(Query *root, List *clauses, List *or_selectivities);
-
 /****************************************************************************
  *		ROUTINES TO SET CLAUSE SELECTIVITIES
  ****************************************************************************/
 
 /*
  * set_clause_selectivities -
- *	  Sets the selectivity field for each of clause in 'restrictinfo-list'
- *	  to 'new-selectivity'.  If the selectivity has already been set, reset
- *	  it only if the new one is better.
- *
- * Returns nothing of interest.
- *
+ *	  Sets the selectivity field for each clause in 'restrictinfo-list'
+ *	  to 'new-selectivity'.  If the selectivity has already been set,
+ *	  change it only if the new one is better.
  */
 void
 set_clause_selectivities(List *restrictinfo_list, Cost new_selectivity)
 {
-	List	   *temp;
-	RestrictInfo *clausenode;
-	Cost		cost_clause;
+	List	   *rlist;
 
-	foreach(temp, restrictinfo_list)
+	foreach(rlist, restrictinfo_list)
 	{
-		clausenode = (RestrictInfo *) lfirst(temp);
-		cost_clause = clausenode->selectivity;
+		RestrictInfo *clausenode = (RestrictInfo *) lfirst(rlist);
+		Cost		cost_clause = clausenode->selectivity;
+
 		if (cost_clause <= 0 || new_selectivity < cost_clause)
 			clausenode->selectivity = new_selectivity;
 	}
@@ -63,18 +57,12 @@ set_clause_selectivities(List *restrictinfo_list, Cost new_selectivity)
 Cost
 product_selec(List *restrictinfo_list)
 {
-	Cost		result = 1.0;
+	Cost		result = (Cost) 1.0;
+	List	   *rlist;
 
-	if (restrictinfo_list != NIL)
+	foreach(rlist, restrictinfo_list)
 	{
-		List	   *xclausenode = NIL;
-		Cost		temp;
-
-		foreach(xclausenode, restrictinfo_list)
-		{
-			temp = ((RestrictInfo *) lfirst(xclausenode))->selectivity;
-			result = result * temp;
-		}
+		result *= ((RestrictInfo *) lfirst(rlist))->selectivity;
 	}
 	return result;
 }
@@ -84,19 +72,16 @@ product_selec(List *restrictinfo_list)
  *	  Scans through clauses on each relation and assigns a selectivity to
  *	  those clauses that haven't been assigned a selectivity by an index.
  *
- * Returns nothing of interest.
- * MODIFIES: selectivities of the various rel's restrictinfo
- *		  slots.
+ * MODIFIES: selectivities of the various rel's restrictinfo slots.
  */
 void
 set_rest_relselec(Query *root, List *rel_list)
 {
-	RelOptInfo *rel;
 	List	   *x;
 
 	foreach(x, rel_list)
 	{
-		rel = (RelOptInfo *) lfirst(x);
+		RelOptInfo *rel = (RelOptInfo *) lfirst(x);
 		set_rest_selec(root, rel->restrictinfo);
 	}
 }
@@ -105,31 +90,20 @@ set_rest_relselec(Query *root, List *rel_list)
  * set_rest_selec -
  *	  Sets the selectivity fields for those clauses within a single
  *	  relation's 'restrictinfo-list' that haven't already been set.
- *
- * Returns nothing of interest.
- *
  */
 void
 set_rest_selec(Query *root, List *restrictinfo_list)
 {
-	List	   *temp = NIL;
-	RestrictInfo *clausenode = (RestrictInfo *) NULL;
-	Cost		cost_clause;
+	List	   *rlist;
 
-	foreach(temp, restrictinfo_list)
+	foreach(rlist, restrictinfo_list)
 	{
-		clausenode = (RestrictInfo *) lfirst(temp);
-		cost_clause = clausenode->selectivity;
+		RestrictInfo *clause = (RestrictInfo *) lfirst(rlist);
 
-		/*
-		 * Check to see if the selectivity of this clause or any 'or'
-		 * subclauses (if any) haven't been set yet.
-		 */
-		if (cost_clause <= 0 || valid_or_clause(clausenode))
+		if (clause->selectivity <= 0)
 		{
-			clausenode->selectivity = compute_clause_selec(root,
-											 (Node *) clausenode->clause,
-									 lcons(makeFloat(cost_clause), NIL));
+			clause->selectivity =
+				compute_clause_selec(root, (Node *) clause->clause);
 		}
 	}
 }
@@ -140,89 +114,29 @@ set_rest_selec(Query *root, List *restrictinfo_list)
 
 /*
  * compute_clause_selec -
- *	  Given a clause, this routine will compute the selectivity of the
- *	  clause by calling 'compute_selec' with the appropriate parameters
- *	  and possibly use that return value to compute the real selectivity
- *	  of a clause.
- *
- * 'or-selectivities' are selectivities that have already been assigned
- *		to subclauses of an 'or' clause.
- *
- * Returns a flonum corresponding to the clause selectivity.
- *
- */
-Cost
-compute_clause_selec(Query *root, Node *clause, List *or_selectivities)
-{
-	if (is_opclause(clause))
-		return compute_selec(root, lcons(clause, NIL), or_selectivities);
-	else if (not_clause(clause))
-	{
-
-		/*
-		 * 'not' gets "1.0 - selectivity-of-inner-clause".
-		 */
-		return (1.000000 - compute_selec(root,
-								 lcons(get_notclausearg((Expr *) clause),
-									   NIL),
-										 or_selectivities));
-	}
-	else if (or_clause(clause))
-	{
-
-		/*
-		 * Both 'or' and 'and' clauses are evaluated as described in
-		 * (compute_selec).
-		 */
-		return compute_selec(root, ((Expr *) clause)->args, or_selectivities);
-	}
-	else
-		return compute_selec(root, lcons(clause, NIL), or_selectivities);
-}
-
-/*
- * compute_selec -
  *	  Computes the selectivity of a clause.
- *
- *	  If there is more than one clause in the argument 'clauses', then the
- *	  desired selectivity is that of an 'or' clause.  Selectivities for an
- *	  'or' clause such as (OR a b) are computed by finding the selectivity
- *	  of a (s1) and b (s2) and computing s1+s2 - s1*s2.
- *
- *	  In addition, if the clause is an 'or' clause, individual selectivities
- *	  may have already been assigned by indices to subclauses.	These values
- *	  are contained in the list 'or-selectivities'.
- *
- * Returns the clause selectivity as a flonum.
- *
  */
-static Cost
-compute_selec(Query *root, List *clauses, List *or_selectivities)
+Cost
+compute_clause_selec(Query *root, Node *clause)
 {
-	Cost		s1 = 0;
-	List	   *clause = lfirst(clauses);
+	Cost		s1 = 1.0;		/* default for any unhandled clause type */
 
 	if (clause == NULL)
-		s1 = 1.0;
-	else if (IsA(clause, Param))
-	{
-		/* XXX How're we handling this before?? -ay */
-		s1 = 1.0;
-	}
-	else if (IsA(clause, Const))
-		s1 = ((bool) ((Const *) clause)->constvalue) ? 1.0 : 0.0;
-	else if (IsA(clause, Var))
+		return s1;
+	if (IsA(clause, Var))
 	{
-		Oid			relid = getrelid(((Var *) clause)->varno,
-									 root->rtable);
-
 		/*
 		 * we have a bool Var.	This is exactly equivalent to the clause:
 		 * reln.attribute = 't' so we compute the selectivity as if that
 		 * is what we have. The magic #define constants are a hack.  I
 		 * didn't want to have to do system cache look ups to find out all
 		 * of that info.
+		 *
+		 * XXX why are we using varno and varoattno?  Seems like it should
+		 * be varno/varattno or varnoold/varoattno, not mix & match...
 		 */
+		Oid			relid = getrelid(((Var *) clause)->varno,
+									 root->rtable);
 
 		s1 = restriction_selectivity(F_EQSEL,
 									 BooleanEqualOperator,
@@ -231,134 +145,141 @@ compute_selec(Query *root, List *clauses, List *or_selectivities)
 									 "t",
 									 _SELEC_CONSTANT_RIGHT_);
 	}
-	else if (or_selectivities)
+	else if (IsA(clause, Param))
 	{
-		/* If s1 has already been assigned by an index, use that value. */
-		List	   *this_sel = lfirst(or_selectivities);
-
-		s1 = floatVal(this_sel);
+		/* XXX any way to do better? */
+		s1 = 1.0;
 	}
-	else if (is_funcclause((Node *) clause))
+	else if (IsA(clause, Const))
+	{
+		/* bool constant is pretty easy... */
+		s1 = ((bool) ((Const *) clause)->constvalue) ? 1.0 : 0.0;
+	}
+	else if (not_clause(clause))
+	{
+		/* inverse of the selectivity of the underlying clause */
+		s1 = 1.0 - compute_clause_selec(root,
+										(Node *) get_notclausearg((Expr *) clause));
+	}
+	else if (and_clause(clause))
+	{
+		/* Use the product of the selectivities of the subclauses.
+		 * XXX this is probably too optimistic, since the subclauses
+		 * are very likely not independent...
+		 */
+		List   *arg;
+		s1 = 1.0;
+		foreach(arg, ((Expr *) clause)->args)
+		{
+			Cost		s2 = compute_clause_selec(root, (Node *) lfirst(arg));
+			s1 = s1 * s2;
+		}
+	}
+	else if (or_clause(clause))
+	{
+		/* Selectivities for an 'or' clause are computed as s1+s2 - s1*s2
+		 * to account for the probable overlap of selected tuple sets.
+		 * XXX is this too conservative?
+		 */
+		List   *arg;
+		s1 = 0.0;
+		foreach(arg, ((Expr *) clause)->args)
+		{
+			Cost		s2 = compute_clause_selec(root, (Node *) lfirst(arg));
+			s1 = s1 + s2 - s1 * s2;
+		}
+	}
+	else if (is_funcclause(clause))
 	{
-		/* this isn't an Oper, it's a Func!! */
-
 		/*
 		 * This is not an operator, so we guess at the selectivity. THIS
 		 * IS A HACK TO GET V4 OUT THE DOOR.  FUNCS SHOULD BE ABLE TO HAVE
 		 * SELECTIVITIES THEMSELVES.	   -- JMH 7/9/92
 		 */
-		s1 = 0.1;
+		s1 = (Cost) 0.3333333;
 	}
-	else if (not_clause((Node *) clause))
+	else if (is_subplan(clause))
 	{
-		/* negate this baby */
-		return 1 - compute_selec(root, ((Expr *) clause)->args, or_selectivities);
-	}
-	else if (is_subplan((Node *) clause))
-	{
-
 		/*
 		 * Just for the moment! FIX ME! - vadim 02/04/98
 		 */
 		s1 = 1.0;
 	}
-	else if (NumRelids((Node *) clause) == 1)
+	else if (is_opclause(clause))
 	{
-
-		/*
-		 * ...otherwise, calculate s1 from 'clauses'. The clause is not a
-		 * join clause, since there is only one relid in the clause.  The
-		 * clause selectivity will be based on the operator selectivity
-		 * and operand values.
-		 */
-		Oid			opno = ((Oper *) ((Expr *) clause)->oper)->opno;
-		RegProcedure oprrest = get_oprrest(opno);
-		Oid			relid;
-		int			relidx;
-		AttrNumber	attno;
-		Datum		constval;
-		int			flag;
-
-		get_relattval((Node *) clause, &relidx, &attno, &constval, &flag);
-		relid = getrelid(relidx, root->rtable);
-
-		/*
-		 * if the oprrest procedure is missing for whatever reason, use a
-		 * selectivity of 0.5
-		 */
-		if (!oprrest)
-			s1 = (Cost) (0.5);
-		else if (attno == InvalidAttrNumber)
+		if (NumRelids(clause) == 1)
 		{
+			/* The clause is not a join clause, since there is only one
+			 * relid in the clause.  The clause selectivity will be based on
+			 * the operator selectivity and operand values.
+			 */
+			Oid			opno = ((Oper *) ((Expr *) clause)->oper)->opno;
+			RegProcedure oprrest = get_oprrest(opno);
+			Oid			relid;
+			int			relidx;
+			AttrNumber	attno;
+			Datum		constval;
+			int			flag;
+
+			get_relattval(clause, &relidx, &attno, &constval, &flag);
+			relid = getrelid(relidx, root->rtable);
 
 			/*
-			 * attno can be Invalid if the clause had a function in it,
-			 * i.e.   WHERE myFunc(f) = 10
+			 * if the oprrest procedure is missing for whatever reason, use a
+			 * selectivity of 0.5
 			 */
-			/* this should be FIXED somehow to use function selectivity */
-			s1 = (Cost) (0.5);
+			if (!oprrest)
+				s1 = (Cost) 0.5;
+			else if (attno == InvalidAttrNumber)
+			{
+				/*
+				 * attno can be Invalid if the clause had a function in it,
+				 * i.e.   WHERE myFunc(f) = 10
+				 */
+				/* this should be FIXED somehow to use function selectivity */
+				s1 = (Cost) (0.5);
+			}
+			else
+				s1 = (Cost) restriction_selectivity(oprrest,
+													opno,
+													relid,
+													attno,
+													(char *) constval,
+													flag);
 		}
 		else
-			s1 = (Cost) restriction_selectivity(oprrest,
-												opno,
-												relid,
-												attno,
-												(char *) constval,
-												flag);
-
-	}
-	else
-	{
-
-		/*
-		 * The clause must be a join clause.  The clause selectivity will
-		 * be based on the relations to be scanned and the attributes they
-		 * are to be joined on.
-		 */
-		Oid			opno = ((Oper *) ((Expr *) clause)->oper)->opno;
-		RegProcedure oprjoin = get_oprjoin(opno);
-		int			relid1,
-					relid2;
-		AttrNumber	attno1,
-					attno2;
+		{
+			/*
+			 * The clause must be a join clause.  The clause selectivity will
+			 * be based on the relations to be scanned and the attributes they
+			 * are to be joined on.
+			 */
+			Oid			opno = ((Oper *) ((Expr *) clause)->oper)->opno;
+			RegProcedure oprjoin = get_oprjoin(opno);
+			int			relid1,
+						relid2;
+			AttrNumber	attno1,
+						attno2;
 
-		get_rels_atts((Node *) clause, &relid1, &attno1, &relid2, &attno2);
-		relid1 = getrelid(relid1, root->rtable);
-		relid2 = getrelid(relid2, root->rtable);
+			get_rels_atts(clause, &relid1, &attno1, &relid2, &attno2);
+			relid1 = getrelid(relid1, root->rtable);
+			relid2 = getrelid(relid2, root->rtable);
 
-		/*
-		 * if the oprjoin procedure is missing for whatever reason, use a
-		 * selectivity of 0.5
-		 */
-		if (!oprjoin)
-			s1 = (Cost) (0.5);
-		else
-			s1 = (Cost) join_selectivity(oprjoin,
-										 opno,
-										 relid1,
-										 attno1,
-										 relid2,
-										 attno2);
+			/*
+			 * if the oprjoin procedure is missing for whatever reason, use a
+			 * selectivity of 0.5
+			 */
+			if (!oprjoin)
+				s1 = (Cost) (0.5);
+			else
+				s1 = (Cost) join_selectivity(oprjoin,
+											 opno,
+											 relid1,
+											 attno1,
+											 relid2,
+											 attno2);
+		}
 	}
 
-	/*
-	 * A null clause list eliminates no tuples, so return a selectivity of
-	 * 1.0.  If there is only one clause, the selectivity is not that of
-	 * an 'or' clause, but rather that of the single clause.
-	 */
-
-	if (lnext(clauses) == NIL)
-		return s1;
-	else
-	{
-		/* Compute selectivity of the 'or'ed subclauses. */
-		/* Added check for taking lnext(NIL).  -- JMH 3/9/92 */
-		Cost		s2;
-
-		if (or_selectivities != NIL)
-			s2 = compute_selec(root, lnext(clauses), lnext(or_selectivities));
-		else
-			s2 = compute_selec(root, lnext(clauses), NIL);
-		return s1 + s2 - s1 * s2;
-	}
+	return s1;
 }
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c539b1f905..d2da20a5b3 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.62 1999/07/23 03:34:49 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.63 1999/07/24 23:21:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -109,12 +109,25 @@ create_index_paths(Query *root,
 				continue;
 
 		/*
-		 * 1. Try matching the index against subclauses of an 'or' clause.
-		 * The fields of the restrictinfo nodes are marked with lists of
-		 * the matching indices.  No paths are actually created.  We
-		 * currently only look to match the first key.	We don't find
-		 * multi-key index cases where an AND matches the first key, and
-		 * the OR matches the second key.
+		 * 1. Try matching the index against subclauses of restriction 'or'
+		 * clauses (ie, 'or' clauses that reference only this relation).
+		 * The restrictinfo nodes for the 'or' clauses are marked with lists
+		 * of the matching indices.  No paths are actually created now;
+		 * that will be done in orindxpath.c after all indexes for the rel
+		 * have been examined.  (We need to do it that way because we can
+		 * potentially use a different index for each subclause of an 'or',
+		 * so we can't build a path for an 'or' clause until all indexes have
+		 * been matched against it.)
+		 *
+		 * We currently only look to match the first key of each index against
+		 * 'or' subclauses.  There are cases where a later key of a multi-key
+		 * index could be used (if other top-level clauses match earlier keys
+		 * of the index), but our poor brains are hurting already...
+		 *
+		 * We don't even think about special handling of 'or' clauses that
+		 * involve more than one relation, since they can't be processed by
+		 * a single indexscan path anyway.  Currently, cnfify() is certain
+		 * to have restructured any such toplevel 'or' clauses anyway.
 		 */
 		match_index_orclauses(rel,
 							  index,
@@ -123,7 +136,7 @@ create_index_paths(Query *root,
 							  restrictinfo_list);
 
 		/*
-		 * 2. If the keys of this index match any of the available
+		 * 2. If the keys of this index match any of the available non-'or'
 		 * restriction clauses, then create a path using those clauses
 		 * as indexquals.
 		 */
@@ -179,11 +192,14 @@ create_index_paths(Query *root,
 /*
  * match_index_orclauses
  *	  Attempt to match an index against subclauses within 'or' clauses.
- *	  If the index does match, then the clause is marked with information
- *	  about the index.
+ *	  Each subclause that does match is marked with the index's node.
  *
- *	  Essentially, this adds 'index' to the list of indices in the
- *	  RestrictInfo field of each of the clauses which it matches.
+ *	  Essentially, this adds 'index' to the list of subclause indices in
+ *	  the RestrictInfo field of each of the 'or' clauses where it matches.
+ *	  NOTE: we can use storage in the RestrictInfo for this purpose because
+ *	  this processing is only done on single-relation restriction clauses.
+ *	  Therefore, we will never have indexes for more than one relation
+ *	  mentioned in the same RestrictInfo node's list.
  *
  * 'rel' is the node of the relation on which the index is defined.
  * 'index' is the index node.
@@ -204,12 +220,11 @@ match_index_orclauses(RelOptInfo *rel,
 	{
 		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
 
-		if (valid_or_clause(restrictinfo))
+		if (restriction_is_or_clause(restrictinfo))
 		{
 			/*
-			 * Mark the 'or' clause with a list of indices which match
-			 * each of its subclauses.	We add entries to the existing
-			 * list, if any.
+			 * Add this index to the subclause index list for each
+			 * subclause that it matches.
 			 */
 			restrictinfo->indexids =
 				match_index_orclause(rel, index,
@@ -253,7 +268,9 @@ match_index_orclause(RelOptInfo *rel,
 	List	   *index_list;
 	List	   *clist;
 
-	/* first time through, we create empty list of same length as OR clause */
+	/* first time through, we create list of same length as OR clause,
+	 * containing an empty sublist for each subclause.
+	 */
 	if (!other_matching_indices)
 	{
 		matching_indices = NIL;
@@ -1186,9 +1203,13 @@ index_innerjoin(Query *root, RelOptInfo *rel, List *clausegroup_list,
 		pathnode->path.pathorder->ord.sortop = index->ordering;
 		pathnode->path.pathkeys = NIL;
 
+		/* Note that we are making a pathnode for a single-scan indexscan;
+		 * therefore, both indexid and indexqual should be single-element
+		 * lists.
+		 */
 		pathnode->indexid = index->relids;
 		pathnode->indexkeys = index->indexkeys;
-		pathnode->indexqual = clausegroup;
+		pathnode->indexqual = lcons(get_actual_clauses(clausegroup), NIL);
 
 		pathnode->path.joinid = ((RestrictInfo *) lfirst(clausegroup))->restrictinfojoinid;
 
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index ceb8c3eb47..4a511372a5 100644
--- a/src/backend/optimizer/path/orindxpath.c
+++ b/src/backend/optimizer/path/orindxpath.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.28 1999/07/16 04:59:15 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.29 1999/07/24 23:21:10 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -26,61 +26,66 @@
 #include "parser/parsetree.h"
 
 
-static void best_or_subclause_indices(Query *root, RelOptInfo *rel, List *subclauses,
-				List *indices, List **indexids, Cost *cost, Cost *selec);
-static void best_or_subclause_index(Query *root, RelOptInfo *rel, Expr *subclause,
-				   List *indices, int *indexid, Cost *cost, Cost *selec);
+static void best_or_subclause_indices(Query *root, RelOptInfo *rel,
+									  List *subclauses, List *indices,
+									  List **indexids,
+									  Cost *cost, Cost *selec);
+static void best_or_subclause_index(Query *root, RelOptInfo *rel,
+									Expr *subclause, List *indices,
+									int *indexid, Cost *cost, Cost *selec);
 
 
 /*
  * create_or_index_paths
  *	  Creates index paths for indices that match 'or' clauses.
+ *	  create_index_paths() must already have been called.
  *
  * 'rel' is the relation entry for which the paths are to be defined on
  * 'clauses' is the list of available restriction clause nodes
  *
- * Returns a list of these index path nodes.
+ * Returns a list of index path nodes.
  *
  */
 List *
 create_or_index_paths(Query *root,
 					  RelOptInfo *rel, List *clauses)
 {
-	List	   *t_list = NIL;
+	List	   *path_list = NIL;
 	List	   *clist;
 
 	foreach(clist, clauses)
 	{
-		RestrictInfo *clausenode = (RestrictInfo *) (lfirst(clist));
+		RestrictInfo *clausenode = (RestrictInfo *) lfirst(clist);
 
 		/*
 		 * Check to see if this clause is an 'or' clause, and, if so,
 		 * whether or not each of the subclauses within the 'or' clause
-		 * has been matched by an index (the 'Index field was set in
-		 * (match_or)  if no index matches a given subclause, one of the
-		 * lists of index nodes returned by (get_index) will be 'nil').
+		 * has been matched by an index.  The information used was
+		 * saved by create_index_paths().
 		 */
-		if (valid_or_clause(clausenode) &&
+		if (restriction_is_or_clause(clausenode) &&
 			clausenode->indexids)
 		{
-			List	   *temp = NIL;
-			List	   *index_list = NIL;
-			bool		index_flag = true;
+			bool		all_indexable = true;
+			List	   *temp;
 
-			index_list = clausenode->indexids;
-			foreach(temp, index_list)
+			foreach(temp, clausenode->indexids)
 			{
-				if (!lfirst(temp))
+				if (lfirst(temp) == NIL)
 				{
-					index_flag = false;
+					all_indexable = false;
 					break;
 				}
 			}
-			/* do they all have indexes? */
-			if (index_flag)
-			{					/* used to be a lisp every function */
+			if (all_indexable)
+			{
+				/*
+				 * OK, build an IndexPath for this OR clause, using the
+				 * best available index for each subclause.
+				 */
 				IndexPath  *pathnode = makeNode(IndexPath);
-				List	   *indexids = NIL;
+				List	   *indexids;
+				List	   *orclause;
 				Cost		cost;
 				Cost		selec;
 
@@ -98,16 +103,35 @@ create_or_index_paths(Query *root,
 				pathnode->path.pathorder->ordtype = SORTOP_ORDER;
 
 				/*
-				 * This is an IndexScan, but it does index lookups based
-				 * on the order of the fields specified in the WHERE
-				 * clause, not in any order, so the sortop is NULL.
+				 * This is an IndexScan, but the overall result will consist
+				 * of tuples extracted in multiple passes (one for each
+				 * subclause of the OR), so the result cannot be claimed
+				 * to have any particular ordering.
 				 */
 				pathnode->path.pathorder->ord.sortop = NULL;
 				pathnode->path.pathkeys = NIL;
 
-				pathnode->indexqual = lcons(clausenode, NIL);
+				/*
+				 * Generate an indexqual list from the OR clause's args.
+				 * We want two levels of sublist: the first is implicit OR
+				 * and the second is implicit AND.  (Currently, we will never
+				 * see a sub-AND-clause because of cnfify(), but someday maybe
+				 * the code below will do something useful...)
+				 */
+				pathnode->indexqual = NIL;
+				foreach(orclause, clausenode->clause->args)
+				{
+					List	*sublist;
+					if (and_clause(lfirst(orclause)))
+						sublist = ((Expr *) lfirst(orclause))->args;
+					else
+						sublist = lcons(lfirst(orclause), NIL);
+					pathnode->indexqual = lappend(pathnode->indexqual,
+												  sublist);
+				}
 				pathnode->indexid = indexids;
 				pathnode->path.path_cost = cost;
+				clausenode->selectivity = (Cost) selec;
 
 				/*
 				 * copy restrictinfo list into path for expensive function
@@ -121,33 +145,28 @@ create_or_index_paths(Query *root,
 				if (XfuncMode != XFUNC_OFF)
 					((Path *) pathnode)->path_cost += xfunc_get_path_cost((Path) pathnode);
 #endif
-				clausenode->selectivity = (Cost) selec;
-				t_list = lappend(t_list, pathnode);
+				path_list = lappend(path_list, pathnode);
 			}
 		}
 	}
 
-	return t_list;
+	return path_list;
 }
 
 /*
  * best_or_subclause_indices
  *	  Determines the best index to be used in conjunction with each subclause
  *	  of an 'or' clause and the cost of scanning a relation using these
- *	  indices.	The cost is the sum of the individual index costs.
+ *	  indices.	The cost is the sum of the individual index costs, since
+ *	  the executor will perform a scan for each subclause of the 'or'.
  *
- * 'rel' is the node of the relation on which the index is defined
+ * 'rel' is the node of the relation on which the indexes are defined
  * 'subclauses' are the subclauses of the 'or' clause
- * 'indices' are those index nodes that matched subclauses of the 'or'
- *		clause
- * 'examined_indexids' is a list of those index ids to be used with
- *		subclauses that have already been examined
- * 'subcost' is the cost of using the indices in 'examined_indexids'
- * 'selec' is a list of all subclauses that have already been examined
- *
- * Returns a list of the indexids, cost, and selectivities of each
- * subclause, e.g., ((i1 i2 i3) cost (s1 s2 s3)), where 'i' is an OID,
- * 'cost' is a flonum, and 's' is a flonum.
+ * 'indices' is a list of sublists of the index nodes that matched each
+ *		subclause of the 'or' clause
+ * '*indexids' gets a list of the best index ID to use for each subclause
+ * '*cost' gets the total cost of the path
+ * '*selec' gets the total selectivity of the path.
  */
 static void
 best_or_subclause_indices(Query *root,
@@ -155,11 +174,12 @@ best_or_subclause_indices(Query *root,
 						  List *subclauses,
 						  List *indices,
 						  List **indexids,		/* return value */
-						  Cost *cost,	/* return value */
-						  Cost *selec)	/* return value */
+						  Cost *cost,			/* return value */
+						  Cost *selec)			/* return value */
 {
 	List	   *slist;
 
+	*indexids = NIL;
 	*selec = (Cost) 0.0;
 	*cost = (Cost) 0.0;
 
@@ -180,8 +200,6 @@ best_or_subclause_indices(Query *root,
 
 		indices = lnext(indices);
 	}
-
-	return;
 }
 
 /*
@@ -193,10 +211,9 @@ best_or_subclause_indices(Query *root,
  * 'rel' is the node of the relation on which the index is defined
  * 'subclause' is the subclause
  * 'indices' is a list of index nodes that match the subclause
- *
- * Returns a list (index_id index_subcost index_selectivity)
- * (a fixnum, a fixnum, and a flonum respectively).
- *
+ * '*retIndexid' gets the ID of the best index
+ * '*retCost' gets the cost of a scan with that index
+ * '*retSelec' gets the selectivity of that scan
  */
 static void
 best_or_subclause_index(Query *root,
@@ -207,49 +224,60 @@ best_or_subclause_index(Query *root,
 						Cost *retCost,	/* return value */
 						Cost *retSelec) /* return value */
 {
-	List	   *ilist;
+	Oid			relid = getrelid(lfirsti(rel->relids),
+								 root->rtable);
+	Oid			opno = ((Oper *) subclause->oper)->opno;
+	AttrNumber	attno = (get_leftop(subclause))->varattno;
+	bool		constant_on_right = non_null((Expr *) get_rightop(subclause));
+	Datum		value;
+	int			flag;
+	List	   *opnos,
+			   *attnos,
+			   *values,
+			   *flags;
 	bool		first_run = true;
+	List	   *ilist;
 
 	/* if we don't match anything, return zeros */
 	*retIndexid = 0;
-	*retCost = 0.0;
-	*retSelec = 0.0;
+	*retCost = (Cost) 0.0;
+	*retSelec = (Cost) 0.0;
+
+	if (constant_on_right)		/* XXX looks pretty bogus ... tgl */
+		value = ((Const *) get_rightop(subclause))->constvalue;
+	else
+		value = NameGetDatum("");
+	if (constant_on_right)
+		flag = (_SELEC_IS_CONSTANT_ || _SELEC_CONSTANT_RIGHT_);
+	else
+		flag = _SELEC_CONSTANT_RIGHT_;
+
+	/* prebuild lists since we will pass same list to each index */
+	opnos = lconsi(opno, NIL);
+	attnos = lconsi(attno, NIL);
+	values = lconsi(value, NIL);
+	flags = lconsi(flag, NIL);
 
 	foreach(ilist, indices)
 	{
 		RelOptInfo *index = (RelOptInfo *) lfirst(ilist);
-
-		Datum		value;
-		int			flag = 0;
+		Oid			indexid = (Oid) lfirsti(index->relids);
 		Cost		subcost;
-		AttrNumber	attno = (get_leftop(subclause))->varattno;
-		Oid			opno = ((Oper *) subclause->oper)->opno;
-		bool		constant_on_right = non_null((Expr *) get_rightop(subclause));
 		float		npages,
 					selec;
 
-		if (constant_on_right)
-			value = ((Const *) get_rightop(subclause))->constvalue;
-		else
-			value = NameGetDatum("");
-		if (constant_on_right)
-			flag = (_SELEC_IS_CONSTANT_ || _SELEC_CONSTANT_RIGHT_);
-		else
-			flag = _SELEC_CONSTANT_RIGHT_;
-
-		index_selectivity(lfirsti(index->relids),
+		index_selectivity(indexid,
 						  index->classlist,
-						  lconsi(opno, NIL),
-						  getrelid(lfirsti(rel->relids),
-								   root->rtable),
-						  lconsi(attno, NIL),
-						  lconsi(value, NIL),
-						  lconsi(flag, NIL),
+						  opnos,
+						  relid,
+						  attnos,
+						  values,
+						  flags,
 						  1,
 						  &npages,
 						  &selec);
 
-		subcost = cost_index((Oid) lfirsti(index->relids),
+		subcost = cost_index(indexid,
 							 (int) npages,
 							 (Cost) selec,
 							 rel->pages,
@@ -260,12 +288,11 @@ best_or_subclause_index(Query *root,
 
 		if (first_run || subcost < *retCost)
 		{
-			*retIndexid = lfirsti(index->relids);
+			*retIndexid = indexid;
 			*retCost = subcost;
 			*retSelec = selec;
 			first_run = false;
 		}
 	}
 
-	return;
 }
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 1dc0e9a0d5..0148d4912e 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.62 1999/07/17 20:17:13 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.63 1999/07/24 23:21:11 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -301,54 +301,30 @@ create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses)
  * create_indexscan_node
  *	  Returns a indexscan node for the base relation scanned by 'best_path'
  *	  with restriction clauses 'scan_clauses' and targetlist 'tlist'.
+ *
+ * If an 'or' clause is to be used with this index, the indxqual field
+ * will contain a list of the 'or' clause arguments, e.g., the
+ * clause(OR a b c) will generate: ((a) (b) (c)).  Otherwise, the
+ * indxqual will simply contain one conjunctive qualification: ((a)).
  */
 static IndexScan *
 create_indexscan_node(IndexPath *best_path,
 					  List *tlist,
 					  List *scan_clauses)
 {
-
-	/*
-	 * Extract the(first if conjunct, only if disjunct) clause from the
-	 * restrictinfo list.
-	 */
-	Expr	   *index_clause = (Expr *) NULL;
-	List	   *indxqual = NIL;
-	List	   *qpqual = NIL;
-	List	   *fixed_indxqual = NIL;
+	List	   *indxqual = best_path->indexqual;
+	List	   *qpqual;
+	List	   *fixed_indxqual;
 	List	   *ixid;
-	IndexScan  *scan_node = (IndexScan *) NULL;
-	bool		lossy = FALSE;
-	HeapTuple	indexTuple;
-	Form_pg_index index;
-
-	/*
-	 * If an 'or' clause is to be used with this index, the indxqual field
-	 * will contain a list of the 'or' clause arguments, e.g., the
-	 * clause(OR a b c) will generate: ((a) (b) (c)).  Otherwise, the
-	 * indxqual will simply contain one conjunctive qualification: ((a)).
-	 */
-	if (best_path->indexqual != NULL)
-		/* added call to fix_opids, JMH 6/23/92 */
-		index_clause = (Expr *)
-			lfirst(fix_opids(get_actual_clauses(best_path->indexqual)));
-
-	if (or_clause((Node *) index_clause))
-	{
-		List	   *temp = NIL;
-
-		foreach(temp, index_clause->args)
-			indxqual = lappend(indxqual, lcons(lfirst(temp), NIL));
-	}
-	else
-	{
-		indxqual = lcons(get_actual_clauses(best_path->indexqual),
-						 NIL);
-	}
+	IndexScan  *scan_node;
+	bool		lossy = false;
 
 	/* check and see if any indices are lossy */
 	foreach(ixid, best_path->indexid)
 	{
+		HeapTuple	indexTuple;
+		Form_pg_index index;
+
 		indexTuple = SearchSysCacheTuple(INDEXRELID,
 										 ObjectIdGetDatum(lfirsti(ixid)),
 										 0, 0, 0);
@@ -356,34 +332,70 @@ create_indexscan_node(IndexPath *best_path,
 			elog(ERROR, "create_plan: index %u not found", lfirsti(ixid));
 		index = (Form_pg_index) GETSTRUCT(indexTuple);
 		if (index->indislossy)
-			lossy = TRUE;
+		{
+			lossy = true;
+			break;
+		}
 	}
 
-
 	/*
-	 * The qpqual field contains all restrictions not automatically
+	 * The qpqual list must contain all restrictions not automatically
 	 * handled by the index.  Note that for non-lossy indices, the
 	 * predicates in the indxqual are handled by the index, while for
 	 * lossy indices the indxqual predicates need to be double-checked
 	 * after the index fetches the best-guess tuples.
+	 *
+	 * There should not be any clauses in scan_clauses that duplicate
+	 * expressions checked by the index, but just in case, we will
+	 * get rid of them via set_difference.
 	 */
-	if (or_clause((Node *) index_clause))
+	if (length(indxqual) > 1)
 	{
+		/*
+		 * Build an expression representation of the indexqual, expanding
+		 * the implicit OR and AND semantics of the first- and second-level
+		 * lists.  XXX Is it really necessary to do a deep copy here?
+		 */
+		List	   *orclauses = NIL;
+		List	   *orclause;
+		Expr	   *indxqual_expr;
+
+		foreach(orclause, indxqual)
+		{
+			orclauses = lappend(orclauses,
+								make_ands_explicit((List *) copyObject(lfirst(orclause))));
+		}
+		indxqual_expr = make_orclause(orclauses);
+
+		/* this set_difference is almost certainly a waste of time... */
 		qpqual = set_difference(scan_clauses,
-								lcons(index_clause, NIL));
+								lcons(indxqual_expr, NIL));
 
 		if (lossy)
-			qpqual = lappend(qpqual, (List *) copyObject(index_clause));
+			qpqual = lappend(qpqual, indxqual_expr);
 	}
-	else
+	else if (indxqual != NIL)
 	{
+		/* Here, we can simply treat the first sublist as an independent
+		 * set of qual expressions, since there is no top-level OR behavior.
+		 */
 		qpqual = set_difference(scan_clauses, lfirst(indxqual));
 		if (lossy)
-			qpqual = nconc(qpqual,
-						   (List *) copyObject(lfirst(indxqual)));
+			qpqual = nconc(qpqual, (List *) copyObject(lfirst(indxqual)));
 	}
+	else
+		qpqual = NIL;
+
+	/*
+	 * Fix opids in the completed indxqual.  We don't want to do this sooner
+	 * since it would screw up the set_difference calcs above.  Really,
+	 * this ought to only happen at final exit from the planner...
+	 */
+	indxqual = fix_opids(indxqual);
 
-	fixed_indxqual = (List *) fix_indxqual_references((Node *) indxqual, (Path *) best_path);
+	/* The executor needs a copy with index attrs substituted for table ones */
+	fixed_indxqual = (List *) fix_indxqual_references((Node *) indxqual,
+													  (Path *) best_path);
 
 	scan_node = make_indexscan(tlist,
 							   qpqual,
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 2270a0e4ea..08ed6a7316 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.34 1999/07/16 04:59:19 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.35 1999/07/24 23:21:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -25,12 +25,11 @@
 #include "optimizer/var.h"
 #include "utils/lsyscache.h"
 
-extern int	Quiet;
 
-static void add_restrict_and_join_to_rel(Query *root, List *clause);
+static void add_restrict_and_join_to_rel(Query *root, Node *clause);
 static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
 					  Relids join_relids);
-static void add_vars_to_targetlist(Query *root, List *vars, Relids join_relids);
+static void add_vars_to_targetlist(Query *root, List *vars);
 
 static MergeOrder *mergejoinop(Expr *clause);
 static Oid	hashjoinop(Expr *clause);
@@ -129,7 +128,7 @@ add_missing_vars_to_tlist(Query *root, List *tlist)
  *	  relations appearing within clauses.  Creates new relation entries if
  *	  necessary, adding them to *query_relation_list*.
  *
- *	  Returns nothing of interest.
+ * 'clauses': the list of clauses in the cnfify'd query qualification.
  */
 void
 add_restrict_and_join_to_rels(Query *root, List *clauses)
@@ -137,95 +136,71 @@ add_restrict_and_join_to_rels(Query *root, List *clauses)
 	List	   *clause;
 
 	foreach(clause, clauses)
-		add_restrict_and_join_to_rel(root, lfirst(clause));
-	return;
+		add_restrict_and_join_to_rel(root, (Node*) lfirst(clause));
 }
 
 /*
  * add_restrict_and_join_to_rel-
  *	  Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
- *	  of a relation entry(depending on whether or not the clause is a join)
+ *	  of a relation entry (depending on whether or not the clause is a join)
  *	  by creating a new RestrictInfo node and setting appropriate fields
  *	  within the nodes.
- *
- *	  Returns nothing of interest.
  */
 static void
-add_restrict_and_join_to_rel(Query *root, List *clause)
+add_restrict_and_join_to_rel(Query *root, Node *clause)
 {
+	RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 	Relids		relids;
 	List	   *vars;
-	RestrictInfo *restrictinfo = makeNode(RestrictInfo);
-
-	/*
-	 * Retrieve all relids and vars contained within the clause.
-	 */
-	clause_get_relids_vars((Node *) clause, &relids, &vars);
 
 	restrictinfo->clause = (Expr *) clause;
-	restrictinfo->notclause = contains_not((Node *) clause);
-	restrictinfo->selectivity = 0;
 	restrictinfo->indexids = NIL;
 	restrictinfo->mergejoinorder = (MergeOrder *) NULL;
 	restrictinfo->hashjoinoperator = (Oid) 0;
 
+	/*
+	 * The selectivity of the clause must be computed regardless of
+	 * whether it's a restriction or a join clause
+	 */
+	restrictinfo->selectivity = compute_clause_selec(root, clause);
+
+	/*
+	 * Retrieve all relids and vars contained within the clause.
+	 */
+	clause_get_relids_vars(clause, &relids, &vars);
+
 	if (length(relids) == 1)
 	{
-
 		/*
 		 * There is only one relation participating in 'clause', so
-		 * 'clause' must be a restriction clause.
+		 * 'clause' must be a restriction clause for that relation.
 		 */
 		RelOptInfo *rel = get_base_rel(root, lfirsti(relids));
 
-		/*
-		 * The selectivity of the clause must be computed regardless of
-		 * whether it's a restriction or a join clause
-		 */
-		if (is_funcclause((Node *) clause))
-
-			/*
-			 * XXX If we have a func clause set selectivity to 1/3, really
-			 * need a true selectivity function.
-			 */
-			restrictinfo->selectivity = (Cost) 0.3333333;
-		else
-			restrictinfo->selectivity = compute_clause_selec(root, (Node *) clause, NIL);
-
 		rel->restrictinfo = lcons(restrictinfo, rel->restrictinfo);
 	}
 	else
 	{
-
 		/*
 		 * 'clause' is a join clause, since there is more than one atom in
-		 * the relid list.
+		 * the relid list.  Add it to the join lists of all the relevant
+		 * relations.  (If, perchance, 'clause' contains NO vars, then
+		 * nothing will happen...)
 		 */
-		if (is_funcclause((Node *) clause))
-
-			/*
-			 * XXX If we have a func clause set selectivity to 1/3, really
-			 * need a true selectivity function.
-			 */
-			restrictinfo->selectivity = (Cost) 0.3333333;
-		else
-			restrictinfo->selectivity = compute_clause_selec(root, (Node *) clause, NIL);
-
 		add_join_info_to_rels(root, restrictinfo, relids);
-		/* we are going to be doing a join, so add var to targetlist */
-		add_vars_to_targetlist(root, vars, relids);
+		/* we are going to be doing a join, so add vars to targetlists */
+		add_vars_to_targetlist(root, vars);
 	}
 }
 
 /*
  * add_join_info_to_rels
  *	  For every relation participating in a join clause, add 'restrictinfo' to
- *	  the appropriate joininfo node(creating a new one and adding it to the
+ *	  the appropriate joininfo node (creating a new one and adding it to the
  *	  appropriate rel node if necessary).
  *
  * 'restrictinfo' describes the join clause
  * 'join_relids' is the list of relations participating in the join clause
- *
  */
 static void
 add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
@@ -233,7 +208,7 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
 {
 	List	   *join_relid;
 
-	/* For every relid, find the rel, and add the proper join entries */
+	/* For every relid, find the joininfo, and add the proper join entries */
 	foreach(join_relid, join_relids)
 	{
 		JoinInfo   *joininfo;
@@ -247,43 +222,39 @@ add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
 				unjoined_relids = lappendi(unjoined_relids, lfirsti(rel));
 		}
 
+		/*
+		 * Find or make the joininfo node for this combination of rels
+		 */
 		joininfo = find_joininfo_node(get_base_rel(root, lfirsti(join_relid)),
 									  unjoined_relids);
+
+		/*
+		 * And add the restrictinfo node to it.  NOTE that each joininfo
+		 * gets its own copy of the restrictinfo node!  (Is this really
+		 * necessary?  Possibly ... later parts of the optimizer destructively
+		 * modify restrict/join clauses...)
+		 */
 		joininfo->jinfo_restrictinfo = lcons(copyObject((void *) restrictinfo),
-										   joininfo->jinfo_restrictinfo);
+											 joininfo->jinfo_restrictinfo);
 	}
 }
 
 /*
  * add_vars_to_targetlist
- *	  For each variable appearing in a clause,
- *	  (1) If a targetlist entry for the variable is not already present in
- *		  the appropriate relation's target list, add one.
- *	  (2) If a targetlist entry is already present, but the var is part of a
- *		  join clause, add the relids of the join relations to the JoinList
- *		  entry of the targetlist entry.
- *
- *	  'vars' is the list of var nodes
- *	  'join_relids' is the list of relids appearing in the join clause
- *		(if this is a join clause)
- *
- *	  Returns nothing.
+ *	  For each variable appearing in a clause, add it to the relation's
+ *	  targetlist if not already present.
  */
 static void
-add_vars_to_targetlist(Query *root, List *vars, Relids join_relids)
+add_vars_to_targetlist(Query *root, List *vars)
 {
-	Var		   *var;
-	List	   *temp = NIL;
-	RelOptInfo *rel = (RelOptInfo *) NULL;
-	TargetEntry *tlistentry;
+	List	   *temp;
 
 	foreach(temp, vars)
 	{
-		var = (Var *) lfirst(temp);
-		rel = get_base_rel(root, var->varno);
-		tlistentry = tlistentry_member(var, rel->targetlist);
-		if (tlistentry == NULL)
-			/* add a new entry */
+		Var		   *var = (Var *) lfirst(temp);
+		RelOptInfo *rel = get_base_rel(root, var->varno);
+
+		if (tlistentry_member(var, rel->targetlist) == NULL)
 			add_var_to_tlist(rel, var);
 	}
 }
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 84db3df008..5c9e4175ad 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.40 1999/07/16 04:59:23 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.41 1999/07/24 23:21:13 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -290,6 +290,21 @@ make_andclause(List *andclauses)
 	return expr;
 }
 
+/*
+ * Sometimes (such as in the result of cnfify), we use lists of expression
+ * nodes with implicit AND semantics.  This function converts back to an
+ * explicit-AND representation.
+ */
+Expr *
+make_ands_explicit(List *andclauses)
+{
+	if (andclauses == NIL)
+		return NULL;
+	else if (length(andclauses) == 1)
+		return (Expr *) lfirst(andclauses);
+	else
+		return make_andclause(andclauses);
+}
 
 /*****************************************************************************
  *		CASE clause functions
@@ -410,38 +425,6 @@ NumRelids(Node *clause)
 	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.
- *
- * NOTE that only the top-level AND/OR structure is searched for NOTs;
- * we are not interested in buried substructure.
- */
-bool
-contains_not(Node *clause)
-{
-	if (single_node(clause))
-		return false;
-
-	if (not_clause(clause))
-		return true;
-
-	if (or_clause(clause) || and_clause(clause))
-	{
-		List	   *a;
-
-		foreach(a, ((Expr *) clause)->args)
-		{
-			if (contains_not(lfirst(a)))
-				return true;
-		}
-	}
-
-	return false;
-}
-
 /*
  * is_joinable
  *
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 3c9e0a4dc8..52689d96a4 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.46 1999/07/16 04:59:25 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.47 1999/07/24 23:21:14 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -426,7 +426,8 @@ create_index_path(Query *root,
 		/* each clause gets an equal selectivity */
 		clausesel = pow(selec, 1.0 / (double) length(restriction_clauses));
 
-		pathnode->indexqual = restriction_clauses;
+		pathnode->indexqual = lcons(get_actual_clauses(restriction_clauses),
+									NIL);
 		pathnode->path.path_cost = cost_index(lfirsti(index->relids),
 											  (int) npages,
 											  selec,
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index 12b95a61af..4dfdf66fcb 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.6 1999/07/16 04:59:27 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.7 1999/07/24 23:21:14 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,17 +20,15 @@
 #include "optimizer/restrictinfo.h"
 
 /*
- * valid_or_clause
+ * restriction_is_or_clause
  *
- * Returns t iff the restrictinfo node contains a 'normal' 'or' clause.
+ * Returns t iff the restrictinfo node contains an 'or' clause.
  *
  */
 bool
-valid_or_clause(RestrictInfo *restrictinfo)
+restriction_is_or_clause(RestrictInfo *restrictinfo)
 {
 	if (restrictinfo != NULL &&
-		!single_node((Node *) restrictinfo->clause) &&
-		!restrictinfo->notclause &&
 		or_clause((Node *) restrictinfo->clause))
 		return true;
 	else
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index e305870aa7..416cdb0c55 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.34 1999/07/15 23:03:56 momjian Exp $
+ * $Id: relation.h,v 1.35 1999/07/24 23:21:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -151,6 +151,23 @@ typedef struct Path
 	List	   *loc_restrictinfo;
 } Path;
 
+/*----------
+ * IndexPath represents an index scan.  Although an indexscan can only read
+ * a single relation, it can scan it more than once, potentially using a
+ * different index during each scan.  The result is the union (OR) of all the
+ * tuples matched during any scan.  (The executor is smart enough not to return
+ * the same tuple more than once, even if it is matched in multiple scans.)
+ * 'indexid' is a list of index relation OIDs, one per scan to be performed.
+ * 'indexqual' is a list of index qualifications, also one per scan.
+ * Each entry in 'indexqual' is a sublist of qualification expressions with
+ * implicit AND semantics across the sublist items.  Each one of the sublist
+ * items must be an operator expression of the form (var op something) or
+ * (something op var), where the var is a field the associated index keys on
+ * and the op is a member of the operator class of the index.
+ * NOTE that the semantics of the top-level list in 'indexqual' is OR
+ * combination, while the sublists are implicitly AND combinations!
+ *----------
+ */
 typedef struct IndexPath
 {
 	Path		path;
@@ -205,16 +222,20 @@ typedef struct JoinKey
 } JoinKey;
 
 /*
- * clause info
+ * Restriction clause info.
+ * We create one of these for each AND sub-clause of a restriction condition
+ * (WHERE clause).  Since the restriction clauses are logically ANDed, we
+ * can use any one of them or any subset of them to filter out tuples,
+ * without having to evaluate the rest.  The RestrictInfo node itself stores
+ * data used by the optimizer while choosing the best query plan.
  */
 
 typedef struct RestrictInfo
 {
 	NodeTag		type;
-	Expr	   *clause;			/* should be an OP clause */
-	Cost		selectivity;
-	bool		notclause;
-	List	   *indexids;
+	Expr	   *clause;			/* the represented subclause of WHERE cond */
+	Cost		selectivity;	/* estimated selectivity */
+	List	   *indexids;		/* subclause index IDs if clause is an OR */
 
 	/* mergejoin only */
 	MergeOrder *mergejoinorder;
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index de135ca1d5..e362b7c64d 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: clauses.h,v 1.21 1999/07/15 23:03:57 momjian Exp $
+ * $Id: clauses.h,v 1.22 1999/07/24 23:21:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -34,13 +34,13 @@ extern Expr *get_notclausearg(Expr *notclause);
 
 extern bool and_clause(Node *clause);
 extern Expr *make_andclause(List *andclauses);
+extern Expr *make_ands_explicit(List *andclauses);
 
 extern bool case_clause(Node *clause);
 
 extern List *pull_constant_clauses(List *quals, List **constantQual);
 extern void clause_get_relids_vars(Node *clause, Relids *relids, List **vars);
 extern int	NumRelids(Node *clause);
-extern bool contains_not(Node *clause);
 extern bool is_joinable(Node *clause);
 extern bool qual_clause_p(Node *clause);
 extern void fix_opid(Node *clause);
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index b9fc710370..1dfe975226 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: cost.h,v 1.21 1999/07/15 15:21:20 momjian Exp $
+ * $Id: cost.h,v 1.22 1999/07/24 23:21:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -59,7 +59,6 @@ extern void set_clause_selectivities(List *restrictinfo_list, Cost new_selectivi
 extern Cost product_selec(List *restrictinfo_list);
 extern void set_rest_relselec(Query *root, List *rel_list);
 extern void set_rest_selec(Query *root, List *restrictinfo_list);
-extern Cost compute_clause_selec(Query *root,
-					 Node *clause, List *or_selectivities);
+extern Cost compute_clause_selec(Query *root, Node *clause);
 
 #endif	 /* COST_H */
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 2f5c4dca20..7412ca46fa 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: restrictinfo.h,v 1.5 1999/07/15 15:21:23 momjian Exp $
+ * $Id: restrictinfo.h,v 1.6 1999/07/24 23:21:05 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -15,7 +15,7 @@
 
 #include "nodes/relation.h"
 
-extern bool valid_or_clause(RestrictInfo *restrictinfo);
+extern bool restriction_is_or_clause(RestrictInfo *restrictinfo);
 extern List *get_actual_clauses(List *restrictinfo_list);
 extern void get_relattvals(List *restrictinfo_list, List **attnos,
 			   List **values, List **flags);
-- 
2.40.0