Further cleanup for OR-of-AND WHERE-clauses. orindxpath can now handle

extracting from an AND subclause just those opclauses that are relevant
for a particular index.  For example, we can now consider using an index
on x to process WHERE (x = 1 AND y = 2) OR (x = 2 AND y = 4) OR ...

3 files changed, 102 insertions, 62 deletions

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 8dd91179422..4c2b0109bc0 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.78 2000/01/26 05:56:34 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.79 2000/02/05 18:26:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -51,15 +51,12 @@ typedef enum {
 } Prefix_Status;
 
 static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index,
-								  int indexkey, Oid opclass,
 								  List *restrictinfo_list);
 static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index,
-								  int indexkey, Oid opclass,
 								  List *or_clauses,
 								  List *other_matching_indices);
 static bool match_or_subclause_to_indexkey(RelOptInfo *rel,
 										   IndexOptInfo *index,
-										   int indexkey, Oid opclass,
 										   Expr *clause);
 static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index,
 									   int *indexkeys, Oid *classes,
@@ -174,20 +171,11 @@ create_index_paths(Query *root,
 		 * 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 (ie, are join clauses).
 		 * Can we do anything useful with those?
 		 */
-		match_index_orclauses(rel,
-							  index,
-							  index->indexkeys[0],
-							  index->classlist[0],
-							  restrictinfo_list);
+		match_index_orclauses(rel, index, restrictinfo_list);
 
 		/*
 		 * 2. If the keys of this index match any of the available non-'or'
@@ -267,15 +255,11 @@ create_index_paths(Query *root,
  *
  * 'rel' is the node of the relation on which the index is defined.
  * 'index' is the index node.
- * 'indexkey' is the (single) key of the index that we will consider.
- * 'class' is the class of the operator corresponding to 'indexkey'.
  * 'restrictinfo_list' is the list of available restriction clauses.
  */
 static void
 match_index_orclauses(RelOptInfo *rel,
 					  IndexOptInfo *index,
-					  int indexkey,
-					  Oid opclass,
 					  List *restrictinfo_list)
 {
 	List	   *i;
@@ -292,7 +276,6 @@ match_index_orclauses(RelOptInfo *rel,
 			 */
 			restrictinfo->subclauseindices =
 				match_index_orclause(rel, index,
-									 indexkey, opclass,
 									 restrictinfo->clause->args,
 									 restrictinfo->subclauseindices);
 		}
@@ -305,9 +288,12 @@ match_index_orclauses(RelOptInfo *rel,
  *
  *	  A match means that:
  *	  (1) the operator within the subclause can be used with the
- *				index's specified operator class, and
+ *		  index's specified operator class, and
  *	  (2) one operand of the subclause matches the index key.
  *
+ *	  If a subclause is an 'and' clause, then it matches if any of its
+ *	  subclauses is an opclause that matches.
+ *
  * 'or_clauses' is the list of subclauses within the 'or' clause
  * 'other_matching_indices' is the list of information on other indices
  *		that have already been matched to subclauses within this
@@ -323,8 +309,6 @@ match_index_orclauses(RelOptInfo *rel,
 static List *
 match_index_orclause(RelOptInfo *rel,
 					 IndexOptInfo *index,
-					 int indexkey,
-					 Oid opclass,
 					 List *or_clauses,
 					 List *other_matching_indices)
 {
@@ -350,8 +334,7 @@ match_index_orclause(RelOptInfo *rel,
 	{
 		Expr	   *clause = lfirst(clist);
 
-		if (match_or_subclause_to_indexkey(rel, index, indexkey, opclass,
-										   clause))
+		if (match_or_subclause_to_indexkey(rel, index, clause))
 		{
 			/* OK to add this index to sublist for this subclause */
 			lfirst(matching_indices) = lcons(index,
@@ -368,33 +351,84 @@ match_index_orclause(RelOptInfo *rel,
  * See if a subclause of an OR clause matches an index.
  *
  * We accept the subclause if it is an operator clause that matches the
- * index, or if it is an AND clause all of whose members are operators
- * that match the index.  (XXX Would accepting a single match be useful?)
+ * index, or if it is an AND clause any of whose members is an opclause
+ * that matches the index.
+ *
+ * We currently only look to match the first key of an 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...
  */
 static bool
 match_or_subclause_to_indexkey(RelOptInfo *rel,
 							   IndexOptInfo *index,
-							   int indexkey,
-							   Oid opclass,
 							   Expr *clause)
 {
+	int		indexkey = index->indexkeys[0];
+	Oid		opclass = index->classlist[0];
+
 	if (and_clause((Node *) clause))
 	{
 		List	   *item;
 
 		foreach(item, clause->args)
 		{
-			if (! match_clause_to_indexkey(rel, index, indexkey, opclass,
-										   lfirst(item), false))
-				return false;
+			if (match_clause_to_indexkey(rel, index, indexkey, opclass,
+										 lfirst(item), false))
+				return true;
 		}
-		return true;
+		return false;
 	}
 	else
 		return match_clause_to_indexkey(rel, index, indexkey, opclass,
 										clause, false);
 }
 
+/*
+ * Given an OR subclause that has previously been determined to match
+ * the specified index, extract a list of specific opclauses that can be
+ * used as indexquals.
+ *
+ * In the simplest case this just means making a one-element list of the
+ * given opclause.  However, if the OR subclause is an AND, we have to
+ * scan it to find the opclause(s) that match the index.  (There should
+ * be at least one, if match_or_subclause_to_indexkey succeeded, but there
+ * could be more.)  Also, we apply expand_indexqual_conditions() to convert
+ * any special matching opclauses to indexable operators.
+ *
+ * The passed-in clause is not changed.
+ */
+List *
+extract_or_indexqual_conditions(RelOptInfo *rel,
+								IndexOptInfo *index,
+								Expr *orsubclause)
+{
+	List   *quals = NIL;
+	int		indexkey = index->indexkeys[0];
+	Oid		opclass = index->classlist[0];
+
+	if (and_clause((Node *) orsubclause))
+	{
+		List	   *item;
+
+		foreach(item, orsubclause->args)
+		{
+			if (match_clause_to_indexkey(rel, index, indexkey, opclass,
+										 lfirst(item), false))
+				quals = lappend(quals, lfirst(item));
+		}
+		if (quals == NIL)
+			elog(ERROR, "extract_or_indexqual_conditions: no matching clause");
+	}
+	else
+	{
+		/* we assume the caller passed a valid indexable qual */
+		quals = lcons(orsubclause, NIL);
+	}
+
+	return expand_indexqual_conditions(quals);
+}
+
 
 /****************************************************************************
  *				----  ROUTINES TO CHECK RESTRICTIONS  ----
@@ -614,8 +648,8 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel,
  *
  * Returns true if the clause can be used with this index key.
  *
- * NOTE:  returns false if clause is an OR or AND clause; to the extent
- * we cope with those at all, it is done by higher-level routines.
+ * NOTE:  returns false if clause is an OR or AND clause; it is the
+ * responsibility of higher-level routines to cope with those.
  */
 static bool
 match_clause_to_indexkey(RelOptInfo *rel,
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index 2cc1c2467f3..9eb0484fc2f 100644
--- a/src/backend/optimizer/path/orindxpath.c
+++ b/src/backend/optimizer/path/orindxpath.c
@@ -8,14 +8,12 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.35 2000/01/26 05:56:34 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.36 2000/02/05 18:26:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
-#include "postgres.h"
-
-
 
+#include "postgres.h"
 
 #include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
@@ -33,7 +31,8 @@ static void best_or_subclause_indices(Query *root, RelOptInfo *rel,
 									  List **indexids,
 									  Cost *cost);
 static void best_or_subclause_index(Query *root, RelOptInfo *rel,
-									List *indexqual, List *indices,
+									Expr *subclause, List *indices,
+									List **retIndexQual,
 									Oid *retIndexid,
 									Cost *retCost);
 
@@ -43,7 +42,7 @@ static void best_or_subclause_index(Query *root, RelOptInfo *rel,
  *	  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
+ * 'rel' is the relation entry for which the paths are to be created
  * 'clauses' is the list of available restriction clause nodes
  *
  * Returns a list of index path nodes.
@@ -164,21 +163,16 @@ best_or_subclause_indices(Query *root,
 	foreach(slist, subclauses)
 	{
 		Expr	   *subclause = lfirst(slist);
-		List	   *indexqual;
+		List	   *best_indexqual;
 		Oid			best_indexid;
 		Cost		best_cost;
 
-		/* Convert this 'or' subclause to an indexqual list */
-		indexqual = make_ands_implicit(subclause);
-		/* expand special operators to indexquals the executor can handle */
-		indexqual = expand_indexqual_conditions(indexqual);
-
-		best_or_subclause_index(root, rel, indexqual, lfirst(indices),
-								&best_indexid, &best_cost);
+		best_or_subclause_index(root, rel, subclause, lfirst(indices),
+								&best_indexqual, &best_indexid, &best_cost);
 
 		Assert(best_indexid != InvalidOid);
 
-		*indexquals = lappend(*indexquals, indexqual);
+		*indexquals = lappend(*indexquals, best_indexqual);
 		*indexids = lappendi(*indexids, best_indexid);
 		*cost += best_cost;
 
@@ -193,41 +187,49 @@ best_or_subclause_indices(Query *root,
  *	  the least expensive.
  *
  * 'rel' is the node of the relation on which the index is defined
- * 'indexqual' is the indexqual list derived from the subclause
+ * 'subclause' is the OR subclause being considered
  * 'indices' is a list of IndexOptInfo nodes that match the subclause
+ * '*retIndexQual' gets a list of the indexqual conditions for the best index
  * '*retIndexid' gets the OID of the best index
  * '*retCost' gets the cost of a scan with that index
  */
 static void
 best_or_subclause_index(Query *root,
 						RelOptInfo *rel,
-						List *indexqual,
+						Expr *subclause,
 						List *indices,
+						List **retIndexQual,	/* return value */
 						Oid *retIndexid,		/* return value */
 						Cost *retCost)			/* return value */
 {
-	bool		first_run = true;
+	bool		first_time = true;
 	List	   *ilist;
 
 	/* if we don't match anything, return zeros */
+	*retIndexQual = NIL;
 	*retIndexid = InvalidOid;
 	*retCost = 0.0;
 
 	foreach(ilist, indices)
 	{
 		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
+		List	   *indexqual;
 		Cost		subcost;
 
 		Assert(IsA(index, IndexOptInfo));
 
+		/* Convert this 'or' subclause to an indexqual list */
+		indexqual = extract_or_indexqual_conditions(rel, index, subclause);
+
 		subcost = cost_index(root, rel, index, indexqual,
 							 false);
 
-		if (first_run || subcost < *retCost)
+		if (first_time || subcost < *retCost)
 		{
+			*retIndexQual = indexqual;
 			*retIndexid = index->indexoid;
 			*retCost = subcost;
-			first_run = false;
+			first_time = false;
 		}
 	}
 }
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 3ba443f4392..c422654c5ad 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: paths.h,v 1.39 2000/01/26 05:58:20 momjian Exp $
+ * $Id: paths.h,v 1.40 2000/02/05 18:26:07 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -38,9 +38,19 @@ extern List *create_index_paths(Query *root, RelOptInfo *rel, List *indices,
 				   List *joininfo_list);
 extern Oid indexable_operator(Expr *clause, Oid opclass, Oid relam,
 							  bool indexkey_on_left);
+extern List *extract_or_indexqual_conditions(RelOptInfo *rel,
+											 IndexOptInfo *index,
+											 Expr *orsubclause);
 extern List *expand_indexqual_conditions(List *indexquals);
 
 /*
+ * orindxpath.c
+ *	  additional routines for indexable OR clauses
+ */
+extern List *create_or_index_paths(Query *root, RelOptInfo *rel,
+								   List *clauses);
+
+/*
  * tidpath.h
  *	  routines to generate tid paths
  */
@@ -52,12 +62,6 @@ extern List *create_tidscan_paths(Query *root, RelOptInfo *rel);
  */
 extern void update_rels_pathlist_for_joins(Query *root, List *joinrels);
 
-
-/*
- * orindxpath.c
- */
-extern List *create_or_index_paths(Query *root, RelOptInfo *rel, List *clauses);
-
 /*
  * pathkeys.c
  *	  utilities for matching and building path keys
@@ -100,7 +104,7 @@ extern bool nonoverlap_sets(List *s1, List *s2);
 extern bool is_subset(List *s1, List *s2);
 
 /*
- * prototypes for path/prune.c
+ * prune.c
  */
 extern void merge_rels_with_same_relids(List *rel_list);
 extern void rels_set_cheapest(Query *root, List *rel_list);