Allow index use with OR clauses.

3 files changed, 138 insertions, 192 deletions

diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index c372b6ce644..5f495d92a7f 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.9 1998/07/18 04:22:30 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.10 1998/08/01 22:12:11 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -159,19 +159,8 @@ set_rest_selec(Query *root, List *clauseinfo_list)
 Cost
 compute_clause_selec(Query *root, Node *clause, List *or_selectivities)
 {
-	if (!is_opclause(clause))
-	{
-
-		/*
-		 * if it's not an operator clause, then it is a boolean clause
-		 * -jolly
-		 */
-
-		/*
-		 * Boolean variables get a selectivity of 1/2.
-		 */
-		return (0.1);
-	}
+    if (is_opclause (clause))
+	    return compute_selec(root, lcons(clause,NIL), or_selectivities);
 	else if (not_clause(clause))
 	{
 
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 3722688a21b..b557d9d59b3 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.19 1998/07/31 15:10:40 vadim Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.20 1998/08/01 22:12:12 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,6 +21,7 @@
 #include "access/nbtree.h"
 #include "catalog/catname.h"
 #include "catalog/pg_amop.h"
+#include "catalog/pg_type.h"
 #include "executor/executor.h"
 #include "fmgr.h"
 #include "nodes/makefuncs.h"
@@ -77,10 +78,7 @@ create_index_paths(Query *root, RelOptInfo *rel, RelOptInfo *index,
 				   List *clausegroup_list, bool join);
 static List *add_index_paths(List *indexpaths, List *new_indexpaths);
 static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index);
-static bool SingleAttributeIndex(RelOptInfo *index);
 
-/* If Spyros can use a constant PRS2_BOOL_TYPEID, I can use this */
-#define BOOL_TYPEID ((Oid) 16)
 
 /*
  * find-index-paths--
@@ -121,91 +119,82 @@ find_index_paths(Query *root,
 	List	   *joinclausegroups = NIL;
 	List	   *joinpaths = NIL;
 	List	   *retval = NIL;
-
-	if (indices == NIL)
-		return (NULL);
-
-	index = (RelOptInfo *) lfirst(indices);
-
-	retval = find_index_paths(root,
-							  rel,
-							  lnext(indices),
-							  clauseinfo_list,
-							  joininfo_list);
-
-	/* If this is a partial index, return if it fails the predicate test */
-	if (index->indpred != NIL)
-		if (!pred_test(index->indpred, clauseinfo_list, joininfo_list))
-			return retval;
-
-	/*
-	 * 1. If this index has only one key, try matching it against
-	 * subclauses of an 'or' clause.  The fields of the clauseinfo nodes
-	 * are marked with lists of the matching indices no path are actually
-	 * created.
-	 *
-	 * XXX NOTE:  Currently btrees dos not support indices with > 1 key, so
-	 * the following test will always be true for now but we have decided
-	 * not to support index-scans on disjunction . -- lp
-	 */
-	if (SingleAttributeIndex(index))
+	List	   *ilist;
+	
+	foreach(ilist, indices)
 	{
+		index = (RelOptInfo *) lfirst(ilist);
+	
+		/* If this is a partial index, return if it fails the predicate test */
+		if (index->indpred != NIL)
+			if (!pred_test(index->indpred, clauseinfo_list, joininfo_list))
+				continue;
+	
+		/*
+		 * 1. Try matching the index against subclauses of an 'or' clause.
+		 * The fields of the clauseinfo nodes are marked with lists of the
+		 * matching indices.  No path 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.
+		 */
 		match_index_orclauses(rel,
-							  index,
-							  index->indexkeys[0],
-							  index->classlist[0],
-							  clauseinfo_list);
-	}
-
-	/*
-	 * 2. If the keys of this index match any of the available restriction
-	 * clauses, then create pathnodes corresponding to each group of
-	 * usable clauses.
-	 */
-	scanclausegroups = group_clauses_by_indexkey(rel,
-												 index,
-												 index->indexkeys,
-												 index->classlist,
-												 clauseinfo_list);
-
-	scanpaths = NIL;
-	if (scanclausegroups != NIL)
-		scanpaths = create_index_paths(root,
-									   rel,
-									   index,
-									   scanclausegroups,
-									   false);
-
-	/*
-	 * 3. If this index can be used with any join clause, then create
-	 * pathnodes for each group of usable clauses.	An index can be used
-	 * with a join clause if its ordering is useful for a mergejoin, or if
-	 * the index can possibly be used for scanning the inner relation of a
-	 * nestloop join.
-	 */
-	joinclausegroups = indexable_joinclauses(rel, index, joininfo_list, clauseinfo_list);
-	joinpaths = NIL;
-
-	if (joinclausegroups != NIL)
-	{
-		List	   *new_join_paths = create_index_paths(root, rel,
-														index,
-														joinclausegroups,
-														true);
-		List	   *innerjoin_paths = index_innerjoin(root, rel, joinclausegroups, index);
-
-		rel->innerjoin = nconc(rel->innerjoin, innerjoin_paths);
-		joinpaths = new_join_paths;
+								  index,
+								  index->indexkeys[0],
+								  index->classlist[0],
+								  clauseinfo_list);
+		}
+	
+		/*
+		 * 2. If the keys of this index match any of the available restriction
+		 * clauses, then create pathnodes corresponding to each group of
+		 * usable clauses.
+		 */
+		scanclausegroups = group_clauses_by_indexkey(rel,
+													 index,
+													 index->indexkeys,
+													 index->classlist,
+													 clauseinfo_list);
+	
+		scanpaths = NIL;
+		if (scanclausegroups != NIL)
+			scanpaths = create_index_paths(root,
+										   rel,
+										   index,
+										   scanclausegroups,
+										   false);
+	
+		/*
+		 * 3. If this index can be used with any join clause, then create
+		 * pathnodes for each group of usable clauses.	An index can be used
+		 * with a join clause if its ordering is useful for a mergejoin, or if
+		 * the index can possibly be used for scanning the inner relation of a
+		 * nestloop join.
+		 */
+		joinclausegroups = indexable_joinclauses(rel, index, joininfo_list, clauseinfo_list);
+		joinpaths = NIL;
+	
+		if (joinclausegroups != NIL)
+		{
+			List	   *new_join_paths = create_index_paths(root, rel,
+															index,
+															joinclausegroups,
+															true);
+			List	   *innerjoin_paths = index_innerjoin(root, rel, joinclausegroups, index);
+	
+			rel->innerjoin = nconc(rel->innerjoin, innerjoin_paths);
+			joinpaths = new_join_paths;
+		}
+	
+		/*
+		 * Some sanity checks to make sure that the indexpath is valid.
+		 */
+		if (joinpaths != NULL)
+			retval = add_index_paths(joinpaths, retval);
+		if (scanpaths != NULL)
+			retval = add_index_paths(scanpaths, retval);
 	}
-
-	/*
-	 * Some sanity checks to make sure that the indexpath is valid.
-	 */
-	if (joinpaths != NULL)
-		retval = add_index_paths(joinpaths, retval);
-	if (scanpaths != NULL)
-		retval = add_index_paths(scanpaths, retval);
-
+	
 	return retval;
 
 }
@@ -297,7 +286,7 @@ match_index_to_operand(int indexkey,
  *	  (1) the operator within the subclause can be used with one
  *				of the index's operator classes, and
  *	  (2) there is a usable key that matches the variable within a
- *				sargable clause.
+ *				searchable clause.
  *
  * 'or-clauses' are the remaining subclauses within the 'or' clause
  * 'other-matching-indices' is the list of information on other indices
@@ -322,30 +311,31 @@ match_index_orclause(RelOptInfo *rel,
 	List	   *matched_indices = other_matching_indices;
 	List	   *index_list = NIL;
 	List	   *clist;
-	List	   *ind;
-
-	if (!matched_indices)
-		matched_indices = lcons(NIL, NIL);
 
-	for (clist = or_clauses, ind = matched_indices;
-		 clist;
-		 clist = lnext(clist), ind = lnext(ind))
+	foreach(clist, or_clauses)
 	{
 		clause = lfirst(clist);
 		if (is_opclause(clause) &&
 			op_class(((Oper *) ((Expr *) clause)->oper)->opno,
 					 xclass, index->relam) &&
-			match_index_to_operand(indexkey,
+			((match_index_to_operand(indexkey,
+								   (Expr *) get_leftop((Expr *) clause),
+								   rel,
+								   index) &&
+			  IsA(get_rightop((Expr *) clause), Const)) ||
+			 (match_index_to_operand(indexkey,
 								   (Expr *) get_leftop((Expr *) clause),
 								   rel,
 								   index) &&
-			IsA(get_rightop((Expr *) clause), Const))
+			 IsA(get_rightop((Expr *) clause), Const))))
 		{
-
 			matched_indices = lcons(index, matched_indices);
-			index_list = lappend(index_list,
-								 matched_indices);
 		}
+		index_list = lappend(index_list, matched_indices);
+
+		/* for the first index, we are creating the indexids list */
+		if (matched_indices)
+			matched_indices = lnext(matched_indices);
 	}
 	return (index_list);
 
@@ -1061,7 +1051,7 @@ clause_pred_clause_test(Expr *predicate, Node *clause)
 	 */
 	test_oper = makeOper(test_op,		/* opno */
 						 InvalidOid,	/* opid */
-						 BOOL_TYPEID,	/* opresulttype */
+						 BOOLOID,	/* opresulttype */
 						 0,		/* opsize */
 						 NULL); /* op_fcache */
 	replace_opid(test_oper);
@@ -1176,7 +1166,8 @@ extract_restrict_clauses(List *clausegroup)
  *
  */
 static List *
-index_innerjoin(Query *root, RelOptInfo *rel, List *clausegroup_list, RelOptInfo *index)
+index_innerjoin(Query *root, RelOptInfo *rel, List *clausegroup_list,
+				RelOptInfo *index)
 {
 	List	   *clausegroup = NIL;
 	List	   *cg_list = NIL;
@@ -1366,29 +1357,3 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, RelOptInfo *index)
 
 	return true;
 }
-
-static bool
-SingleAttributeIndex(RelOptInfo *index)
-{
-
-	/*
-	 * return false for now as I don't know if we support index scans on
-	 * disjunction and the code doesn't work
-	 */
-	return (false);
-
-#if 0
-
-	/*
-	 * Non-functional indices.
-	 */
-	if (index->indproc == InvalidOid)
-		return (index->indexkeys[0] != 0 &&
-				index->indexkeys[1] == 0);
-
-	/*
-	 * We have a functional index which is a single attr index
-	 */
-	return true;
-#endif
-}
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index c697078e1b2..7f220fc54ba 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.7 1998/07/18 04:22:33 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.8 1998/08/01 22:12:13 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -55,10 +55,11 @@ create_or_index_paths(Query *root,
 					  RelOptInfo *rel, List *clauses)
 {
 	List	   *t_list = NIL;
+	List	   *clist;
 
-	if (clauses != NIL)
+	foreach(clist, clauses)
 	{
-		CInfo	   *clausenode = (CInfo *) (lfirst(clauses));
+		CInfo	   *clausenode = (CInfo *) (lfirst(clist));
 
 		/*
 		 * Check to see if this clause is an 'or' clause, and, if so,
@@ -77,8 +78,11 @@ create_or_index_paths(Query *root,
 			index_list = clausenode->indexids;
 			foreach(temp, index_list)
 			{
-				if (!temp)
+				if (!lfirst(temp))
+				{
 					index_flag = false;
+					break;
+				}
 			}
 			if (index_flag)
 			{					/* used to be a lisp every function */
@@ -100,8 +104,7 @@ create_or_index_paths(Query *root,
 
 				pathnode->path.pathtype = T_IndexScan;
 				pathnode->path.parent = rel;
-				pathnode->indexqual =
-					lcons(clausenode, NIL);
+				pathnode->indexqual = lcons(clausenode, NIL);
 				pathnode->indexid = indexids;
 				pathnode->path.path_cost = cost;
 
@@ -110,9 +113,8 @@ create_or_index_paths(Query *root,
 				 * processing	 -- JMH, 7/7/92
 				 */
 				pathnode->path.locclauseinfo =
-					set_difference(clauses,
-								   copyObject((Node *)
-											  rel->clauseinfo));
+					set_difference(copyObject((Node *)rel->clauseinfo),
+								   lcons(clausenode,NIL));
 
 #if 0							/* fix xfunc */
 				/* add in cost for expensive functions!  -- JMH, 7/7/92 */
@@ -123,12 +125,8 @@ create_or_index_paths(Query *root,
 				}
 #endif
 				clausenode->selectivity = (Cost) floatVal(selecs);
-				t_list =
-					lcons(pathnode,
-					   create_or_index_paths(root, rel, lnext(clauses)));
+				t_list = lappend(t_list, pathnode);
 			}
-			else
-				t_list = create_or_index_paths(root, rel, lnext(clauses));
 		}
 	}
 
@@ -167,32 +165,28 @@ best_or_subclause_indices(Query *root,
 						  Cost *cost,	/* return value */
 						  List **selecs)		/* return value */
 {
-	if (subclauses == NIL)
-	{
-		*indexids = nreverse(examined_indexids);
-		*cost = subcost;
-		*selecs = nreverse(selectivities);
-	}
-	else
+	List *slist;
+	
+	foreach (slist, subclauses)
 	{
 		int			best_indexid;
 		Cost		best_cost;
 		Cost		best_selec;
 
-		best_or_subclause_index(root, rel, lfirst(subclauses), lfirst(indices),
+		best_or_subclause_index(root, rel, lfirst(slist), lfirst(indices),
 								&best_indexid, &best_cost, &best_selec);
+								
+		examined_indexids = lappendi(examined_indexids, best_indexid);
+		subcost += best_cost;
+		selectivities = lappend(selectivities, makeFloat(best_selec));
 
-		best_or_subclause_indices(root,
-								  rel,
-								  lnext(subclauses),
-								  lnext(indices),
-								  lconsi(best_indexid, examined_indexids),
-								  subcost + best_cost,
-							 lcons(makeFloat(best_selec), selectivities),
-								  indexids,
-								  cost,
-								  selecs);
+		indices = lnext(indices);
 	}
+
+	*indexids = examined_indexids;
+	*cost = subcost;
+	*selecs = selectivities;
+
 	return;
 }
 
@@ -219,20 +213,21 @@ best_or_subclause_index(Query *root,
 						Cost *retCost,	/* return value */
 						Cost *retSelec) /* return value */
 {
-	if (indices != NIL)
+	List *ilist;
+	bool first_run = true;
+	
+	foreach (ilist, indices)
 	{
+		RelOptInfo		   *index = (RelOptInfo *) lfirst(ilist);
+		
 		Datum		value;
 		int			flag = 0;
 		Cost		subcost;
-		RelOptInfo		   *index = (RelOptInfo *) lfirst(indices);
 		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;
-		int			subclause_indexid;
-		Cost		subclause_cost;
-		Cost		subclause_selec;
 
 		if (constant_on_right)
 			value = ((Const *) get_rightop(subclause))->constvalue;
@@ -242,6 +237,7 @@ best_or_subclause_index(Query *root,
 			flag = (_SELEC_IS_CONSTANT_ || _SELEC_CONSTANT_RIGHT_);
 		else
 			flag = _SELEC_CONSTANT_RIGHT_;
+
 		index_selectivity(lfirsti(index->relids),
 						  index->classlist,
 						  lconsi(opno, NIL),
@@ -262,26 +258,22 @@ best_or_subclause_index(Query *root,
 							 index->pages,
 							 index->tuples,
 							 false);
-		best_or_subclause_index(root,
-								rel,
-								subclause,
-								lnext(indices),
-								&subclause_indexid,
-								&subclause_cost,
-								&subclause_selec);
 
-		if (subclause_indexid == 0 || subcost < subclause_cost)
+		if (first_run || subcost < *retCost)
 		{
 			*retIndexid = lfirsti(index->relids);
 			*retCost = subcost;
 			*retSelec = selec;
+			first_run = false;
 		}
-		else
-		{
-			*retIndexid = 0;
-			*retCost = 0.0;
-			*retSelec = 0.0;
-		}
+	}
+
+	/* we didn't get any indexes, so zero return values */
+	if (first_run)
+	{
+		*retIndexid = 0;
+		*retCost = 0.0;
+		*retSelec = 0.0;
 	}
 	return;
 }