From 90451fe7f3bd7e180faa4abe89d5daeaa213bb60 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 26 Jul 2000 23:46:22 +0000
Subject: [PATCH] When dealing with OR-of-ANDs quals, extract multiple
 subclauses of an AND to use with a multiple-key index.  Formerly we would
 only extract clauses that had to do with the first key of the index, which
 was correct but didn't exploit the index fully.

---
 src/backend/optimizer/path/indxpath.c | 80 +++++++++++++++++++++++------------
 1 file changed, 54 insertions(+), 26 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 2042b4dac3..068ba771ea 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.88 2000/07/25 04:30:42 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.89 2000/07/26 23:46:22 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -40,9 +40,23 @@
 #include "utils/syscache.h"
 
 
+/*
+ * DoneMatchingIndexKeys() - MACRO
+ *
+ * Determine whether we should continue matching index keys in a clause.
+ * Depends on if there are more to match or if this is a functional index.
+ * In the latter case we stop after the first match since the there can
+ * be only key (i.e. the function's return value) and the attributes in
+ * keys list represent the arguments to the function.  -mer 3 Oct. 1991
+ */
+#define DoneMatchingIndexKeys(indexkeys, index) \
+		(indexkeys[0] == 0 || \
+		 (index->indproc != InvalidOid))
+
 #define is_indexable_operator(clause,opclass,relam,indexkey_on_left) \
 	(indexable_operator(clause,opclass,relam,indexkey_on_left) != InvalidOid)
 
+
 static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index,
 					  List *restrictinfo_list);
 static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index,
@@ -354,10 +368,11 @@ match_index_orclause(RelOptInfo *rel,
  * 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...
+ * For multi-key indexes, we only look for matches to the first key;
+ * without such a match the index is useless.  If the clause is an AND
+ * then we may be able to extract additional subclauses to use with the
+ * later indexkeys, but we need not worry about that until
+ * extract_or_indexqual_conditions() is called (if it ever is).
  */
 static bool
 match_or_subclause_to_indexkey(RelOptInfo *rel,
@@ -404,19 +419,45 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
 								Expr *orsubclause)
 {
 	List	   *quals = NIL;
-	int			indexkey = index->indexkeys[0];
-	Oid			opclass = index->classlist[0];
 
 	if (and_clause((Node *) orsubclause))
 	{
-		List	   *item;
+		/*
+		 * Extract relevant sub-subclauses in indexkey order.  This is just
+		 * like group_clauses_by_indexkey() except that the input and output
+		 * are lists of bare clauses, not of RestrictInfo nodes.
+		 */
+		int		   *indexkeys = index->indexkeys;
+		Oid		   *classes = index->classlist;
 
-		foreach(item, orsubclause->args)
+		do
 		{
-			if (match_clause_to_indexkey(rel, index, indexkey, opclass,
-										 lfirst(item), false))
-				quals = lappend(quals, lfirst(item));
-		}
+			int			curIndxKey = indexkeys[0];
+			Oid			curClass = classes[0];
+			List	   *clausegroup = NIL;
+			List	   *item;
+
+			foreach(item, orsubclause->args)
+			{
+				if (match_clause_to_indexkey(rel, index,
+											 curIndxKey, curClass,
+											 lfirst(item), false))
+					clausegroup = lappend(clausegroup, lfirst(item));
+			}
+
+			/*
+			 * If no clauses match this key, we're done; we don't want to look
+			 * at keys to its right.
+			 */
+			if (clausegroup == NIL)
+				break;
+
+			quals = nconc(quals, clausegroup);
+
+			indexkeys++;
+			classes++;
+		} while (!DoneMatchingIndexKeys(indexkeys, index));
+
 		if (quals == NIL)
 			elog(ERROR, "extract_or_indexqual_conditions: no matching clause");
 	}
@@ -436,19 +477,6 @@ extract_or_indexqual_conditions(RelOptInfo *rel,
 
 
 /*
- * DoneMatchingIndexKeys() - MACRO
- *
- * Determine whether we should continue matching index keys in a clause.
- * Depends on if there are more to match or if this is a functional index.
- * In the latter case we stop after the first match since the there can
- * be only key (i.e. the function's return value) and the attributes in
- * keys list represent the arguments to the function.  -mer 3 Oct. 1991
- */
-#define DoneMatchingIndexKeys(indexkeys, index) \
-		(indexkeys[0] == 0 || \
-		 (index->indproc != InvalidOid))
-
-/*
  * group_clauses_by_indexkey
  *	  Generates a list of restriction clauses that can be used with an index.
  *
-- 
2.11.0