Patches for Vadim's multikey indexing...

9 files changed, 414 insertions, 248 deletions

diff --git a/src/backend/access/common/indexvalid.c b/src/backend/access/common/indexvalid.c
index df72a69de47..aff9af42f8d 100644
--- a/src/backend/access/common/indexvalid.c
+++ b/src/backend/access/common/indexvalid.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *    $Header: /cvsroot/pgsql/src/backend/access/common/Attic/indexvalid.c,v 1.13 1997/03/12 20:56:32 scrappy Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/access/common/Attic/indexvalid.c,v 1.14 1997/03/18 18:38:19 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -48,7 +48,7 @@ index_keytest(IndexTuple tuple,
     
     while (scanKeySize > 0) {
 	datum = index_getattr(tuple,
-			      1,
+			      key[0].sk_attno,
 			      tupdesc,
 			      &isNull);
 	
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 8317789a94a..0fe6787c010 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *    $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.15 1997/02/22 10:04:14 vadim Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.16 1997/03/18 18:38:35 scrappy Exp $
  *
  * NOTES
  *    This file contains only the public interface routines.
@@ -423,6 +423,7 @@ btrescan(IndexScanDesc scan, bool fromEnd, ScanKey scankey)
     
     /* reset the scan key */
     so->numberOfKeys = scan->numberOfKeys;
+    so->numberOfFirstKeys = 0;
     so->qual_ok = 1;			/* may be changed by _bt_orderkeys */
     if (scan->numberOfKeys > 0) {
 	memmove(scan->keyData,
@@ -433,7 +434,9 @@ btrescan(IndexScanDesc scan, bool fromEnd, ScanKey scankey)
 		so->numberOfKeys * sizeof(ScanKeyData));
 	/* order the keys in the qualification */
 	if (so->numberOfKeys > 1)
-		_bt_orderkeys(scan->relation, &so->numberOfKeys, so->keyData, &so->qual_ok);
+	    _bt_orderkeys(scan->relation, so);
+	else
+	    so->numberOfFirstKeys = 1;
     }
     
     /* finally, be sure that the scan exploits the tree order */
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 94521ff1c0b..2e802ee8527 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *    $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.14 1997/02/18 17:13:48 momjian Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.15 1997/03/18 18:38:41 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -562,7 +562,6 @@ _bt_next(IndexScanDesc scan, ScanDirection dir)
     Page page;
     OffsetNumber offnum;
     RetrieveIndexResult res;
-    BlockNumber blkno;
     ItemPointer current;
     BTItem btitem;
     IndexTuple itup;
@@ -584,31 +583,35 @@ _bt_next(IndexScanDesc scan, ScanDirection dir)
     
     /* we still have the buffer pinned and locked */
     buf = so->btso_curbuf;
-    blkno = BufferGetBlockNumber(buf);
     
-    /* step one tuple in the appropriate direction */
-    if (!_bt_step(scan, &buf, dir))
-	return ((RetrieveIndexResult) NULL);
+    do
+    {
+    	/* step one tuple in the appropriate direction */
+    	if (!_bt_step(scan, &buf, dir))
+	    return ((RetrieveIndexResult) NULL);
     
-    /* by here, current is the tuple we want to return */
-    offnum = ItemPointerGetOffsetNumber(current);
-    page = BufferGetPage(buf);
-    btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
-    itup = &btitem->bti_itup;
+    	/* by here, current is the tuple we want to return */
+    	offnum = ItemPointerGetOffsetNumber(current);
+    	page = BufferGetPage(buf);
+    	btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
+    	itup = &btitem->bti_itup;
     
-    if (_bt_checkqual(scan, itup)) {
-	res = FormRetrieveIndexResult(current, &(itup->t_tid));
+    	if (_bt_checkqual(scan, itup)) 
+    	{
+	    res = FormRetrieveIndexResult(current, &(itup->t_tid));
 	
-	/* remember which buffer we have pinned and locked */
-	so->btso_curbuf = buf;
-    } else {
-	ItemPointerSetInvalid(current);
-	so->btso_curbuf = InvalidBuffer;
-	_bt_relbuf(rel, buf, BT_READ);
-	res = (RetrieveIndexResult) NULL;
-    }
+	    /* remember which buffer we have pinned and locked */
+	    so->btso_curbuf = buf;
+	    return (res);
+	}
+
+    } while ( _bt_checkforkeys (scan, itup, so->numberOfFirstKeys) );
+
+    ItemPointerSetInvalid(current);
+    so->btso_curbuf = InvalidBuffer;
+    _bt_relbuf(rel, buf, BT_READ);
     
-    return (res);
+    return ((RetrieveIndexResult) NULL);
 }
 
 /*
@@ -660,13 +663,6 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
      *  ordered to take advantage of index ordering) to position ourselves
      *  at the right place in the scan.
      */
-    
-    /*
-     *  XXX -- The attribute number stored in the scan key is the attno
-     *	       in the heap relation.  We need to transmogrify this into
-     *         the index relation attno here.  For the moment, we have
-     *	       hardwired attno == 1.
-     */
     proc = index_getprocid(rel, 1, BTORDER_PROC);
     ScanKeyEntryInitialize(&skdata, so->keyData[0].sk_flags, 1, proc,
 			   so->keyData[0].sk_argument);
@@ -802,12 +798,20 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
     btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
     itup = &btitem->bti_itup;
     
-    if (_bt_checkqual(scan, itup)) {
+    if ( _bt_checkqual(scan, itup) )
+    {
 	res = FormRetrieveIndexResult(current, &(itup->t_tid));
 	
 	/* remember which buffer we have pinned */
 	so->btso_curbuf = buf;
-    } else {
+    }
+    else if ( _bt_checkforkeys (scan, itup, so->numberOfFirstKeys) )
+    {
+	so->btso_curbuf = buf;
+	return (_bt_next (scan, dir));
+    }
+    else
+    {
 	ItemPointerSetInvalid(current);
 	so->btso_curbuf = InvalidBuffer;
 	_bt_relbuf(rel, buf, BT_READ);
@@ -1224,7 +1228,14 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
 	
 	/* remember which buffer we have pinned */
 	so->btso_curbuf = buf;
-    } else {
+    }
+    else if ( _bt_checkforkeys (scan, itup, so->numberOfFirstKeys) )
+    {
+	so->btso_curbuf = buf;
+	return (_bt_next (scan, dir));
+    }
+    else
+    {
 	_bt_relbuf(rel, buf, BT_READ);
 	res = (RetrieveIndexResult) NULL;
     }
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 703acd62fa2..6d0a40ef132 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *    $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.7 1996/11/05 10:35:38 scrappy Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.8 1997/03/18 18:38:46 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -80,7 +80,7 @@ _bt_freestack(BTStack stack)
  *	more than one qual clauses using this index.
  */
 void
-_bt_orderkeys(Relation relation, uint16 *numberOfKeys, ScanKey key, uint16 *qual_ok)
+_bt_orderkeys(Relation relation, BTScanOpaque so)
 {
     ScanKey xform;
     ScanKeyData *cur;
@@ -89,42 +89,137 @@ _bt_orderkeys(Relation relation, uint16 *numberOfKeys, ScanKey key, uint16 *qual
     long test;
     int i, j;
     int init[BTMaxStrategyNumber+1];
+    ScanKey key;
+    uint16 numberOfKeys, new_numberOfKeys = 0;
+    AttrNumber attno = 1;
     
-    /* haven't looked at any strategies yet */
-    for (i = 0; i <= BTMaxStrategyNumber; i++)
-	init[i] = 0;
+    numberOfKeys = so->numberOfKeys;
+    key = so->keyData;
+    
+    if ( numberOfKeys <= 1 )
+    	return;
     
     /* get space for the modified array of keys */
     nbytes = BTMaxStrategyNumber * sizeof(ScanKeyData);
     xform = (ScanKey) palloc(nbytes);
-    memset(xform, 0, nbytes); 
     
-    
-    /* get the strategy map for this index/attribute pair */
-    /*
-     *  XXX
-     *  When we support multiple keys in a single index, this is what
-     *  we'll want to do.  At present, the planner is hosed, so we
-     *  hard-wire the attribute number below.  Postgres only does single-
-     *  key indices...
-     * map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
-     * 				    BTMaxStrategyNumber,
-     * 				    key->data[0].attributeNumber);
-     */
+    cur = &key[0];
+    if ( cur->sk_attno != 1 )
+	elog (WARN, "_bt_orderkeys: key(s) for attribute 1 missed");
+
+    memset(xform, 0, nbytes); 
     map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
 				      BTMaxStrategyNumber,
-				      1 /* XXX */ );
+				      attno);
+    for (j = 0; j <= BTMaxStrategyNumber; j++)
+	init[j] = 0;
     
     /* check each key passed in */
-    for (i = *numberOfKeys; --i >= 0; ) {
-	cur = &key[i];
-	for (j = BTMaxStrategyNumber; --j >= 0; ) {
+    for (i = 0; ; )
+    {
+	if ( i < numberOfKeys )
+	    cur = &key[i];
+	if ( i == numberOfKeys || cur->sk_attno != attno )
+	{
+	    if ( cur->sk_attno != attno + 1 && i < numberOfKeys )
+	    {
+	    	elog (WARN, "_bt_orderkeys: key(s) for attribute %d missed", attno + 1);
+	    }
+	    /* 
+	     * If = has been specified, no other key will be used.
+	     * In case of key < 2 && key == 1 and so on 
+     	     * we have to set qual_ok to 0
+     	     */
+	    if (init[BTEqualStrategyNumber - 1])
+	    {
+		ScanKeyData *eq, *chk;
+
+		eq = &xform[BTEqualStrategyNumber - 1];
+		for (j = BTMaxStrategyNumber; --j >= 0; )
+		{
+		    if ( j == (BTEqualStrategyNumber - 1) || init[j] == 0 )
+			continue;
+		    chk = &xform[j];
+		    test = (long) fmgr(chk->sk_procedure, eq->sk_argument, chk->sk_argument);
+		    if (!test)
+			so->qual_ok = 0;
+		}
+		init[BTLessStrategyNumber - 1] = 0;
+		init[BTLessEqualStrategyNumber - 1] = 0;
+		init[BTGreaterEqualStrategyNumber - 1] = 0;
+		init[BTGreaterStrategyNumber - 1] = 0;
+	    }
+    
+	    /* only one of <, <= */
+	    if (init[BTLessStrategyNumber - 1]
+			&& init[BTLessEqualStrategyNumber - 1])
+	    {
+		ScanKeyData *lt, *le;
+	
+		lt = &xform[BTLessStrategyNumber - 1];
+		le = &xform[BTLessEqualStrategyNumber - 1];
+		/*
+		 *  DO NOT use the cached function stuff here -- this is key
+		 *  ordering, happens only when the user expresses a hokey
+		 *  qualification, and gets executed only once, anyway.  The
+		 *  transform maps are hard-coded, and can't be initialized
+		 *  in the correct way.
+		 */
+		test = (long) fmgr(le->sk_procedure, lt->sk_argument, le->sk_argument);
+		if (test)
+	    	    init[BTLessEqualStrategyNumber - 1] = 0;
+		else
+		    init[BTLessStrategyNumber - 1] = 0;
+    	    }
+    
+	    /* only one of >, >= */
+	    if (init[BTGreaterStrategyNumber - 1]
+			&& init[BTGreaterEqualStrategyNumber - 1])
+	    {
+	    	ScanKeyData *gt, *ge;
+	
+		gt = &xform[BTGreaterStrategyNumber - 1];
+		ge = &xform[BTGreaterEqualStrategyNumber - 1];
+	
+		/* see note above on function cache */
+		test = (long) fmgr(ge->sk_procedure, gt->sk_argument, ge->sk_argument);
+		if (test)
+	    	    init[BTGreaterEqualStrategyNumber - 1] = 0;
+		else
+	    	    init[BTGreaterStrategyNumber - 1] = 0;
+    	    }
+    
+    	    /* okay, reorder and count */
+    	    for (j = BTMaxStrategyNumber; --j >= 0; )
+	    	if (init[j])
+		    key[new_numberOfKeys++] = xform[j];
+    
+    	    if ( attno == 1 )
+    		so->numberOfFirstKeys = new_numberOfKeys;
+    	    
+    	    if ( i == numberOfKeys )
+    	    	break;
+
+	    /* initialization for new attno */    	    
+    	    attno = cur->sk_attno;
+    	    memset(xform, 0, nbytes); 
+	    map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
+				      BTMaxStrategyNumber,
+				      attno);
+	    /* haven't looked at any strategies yet */
+	    for (j = 0; j <= BTMaxStrategyNumber; j++)
+		init[j] = 0;
+	}
+
+	for (j = BTMaxStrategyNumber; --j >= 0; )
+	{
 	    if (cur->sk_procedure == map->entry[j].sk_procedure)
-		break;
+	    	break;
 	}
 	
 	/* have we seen one of these before? */
-	if (init[j]) {
+	if (init[j])
+	{
 	    /* yup, use the appropriate value */
 	    test =
 		(long) FMGR_PTR2(cur->sk_func, cur->sk_procedure,
@@ -132,97 +227,18 @@ _bt_orderkeys(Relation relation, uint16 *numberOfKeys, ScanKey key, uint16 *qual
 	    if (test)
 		xform[j].sk_argument = cur->sk_argument;
 	    else if ( j == (BTEqualStrategyNumber - 1) )
-	    	*qual_ok = 0;		/* key == a && key == b, but a != b */
-	} else {
+	    	so->qual_ok = 0;	/* key == a && key == b, but a != b */
+	} else
+	{
 	    /* nope, use this value */
 	    memmove(&xform[j], cur, sizeof(*cur));
-	   
 	    init[j] = 1;
 	}
-    }
-    
-    /* if = has been specified, no other key will be used */
-    /*
-     * XXX
-     * But in case of key < 2 && key == 1 and so on 
-     * we have to set qual_ok to 0
-     */
-    if (init[BTEqualStrategyNumber - 1]) {
-
-	ScanKeyData *eq, *chk;
-
-	eq = &xform[BTEqualStrategyNumber - 1];
-
-	for (j = BTMaxStrategyNumber; --j >= 0; )
-	{
-		if ( j == (BTEqualStrategyNumber - 1) || init[j] == 0 )
-			continue;
-
-		chk = &xform[j];
-
-		test = (long) fmgr(chk->sk_procedure, eq->sk_argument, chk->sk_argument);
 	
-		if (!test)
-			*qual_ok = 0;
-	}
-
-	init[BTLessStrategyNumber - 1] = 0;
-	init[BTLessEqualStrategyNumber - 1] = 0;
-	init[BTGreaterEqualStrategyNumber - 1] = 0;
-	init[BTGreaterStrategyNumber - 1] = 0;
+	i++;
     }
     
-    /* only one of <, <= */
-    if (init[BTLessStrategyNumber - 1]
-	&& init[BTLessEqualStrategyNumber - 1]) {
-	
-	ScanKeyData *lt, *le;
-	
-	lt = &xform[BTLessStrategyNumber - 1];
-	le = &xform[BTLessEqualStrategyNumber - 1];
-	
-	/*
-	 *  DO NOT use the cached function stuff here -- this is key
-	 *  ordering, happens only when the user expresses a hokey
-	 *  qualification, and gets executed only once, anyway.  The
-	 *  transform maps are hard-coded, and can't be initialized
-	 *  in the correct way.
-	 */
-	
-	test = (long) fmgr(le->sk_procedure, lt->sk_argument, le->sk_argument);
-	
-	if (test)
-	    init[BTLessEqualStrategyNumber - 1] = 0;
-	else
-	    init[BTLessStrategyNumber - 1] = 0;
-    }
-    
-    /* only one of >, >= */
-    if (init[BTGreaterStrategyNumber - 1]
-	&& init[BTGreaterEqualStrategyNumber - 1]) {
-	
-	ScanKeyData *gt, *ge;
-	
-	gt = &xform[BTGreaterStrategyNumber - 1];
-	ge = &xform[BTGreaterEqualStrategyNumber - 1];
-	
-	/* see note above on function cache */
-	test = (long) fmgr(ge->sk_procedure, gt->sk_argument, ge->sk_argument);
-	
-	if (test)
-	    init[BTGreaterEqualStrategyNumber - 1] = 0;
-	else
-	    init[BTGreaterStrategyNumber - 1] = 0;
-    }
-    
-    /* okay, reorder and count */
-    j = 0;
-    
-    for (i = BTMaxStrategyNumber; --i >= 0; )
-	if (init[i])
-	    key[j++] = xform[i];
-    
-    *numberOfKeys = j;
+    so->numberOfKeys = new_numberOfKeys;
     
     pfree(xform);
 }
@@ -230,9 +246,25 @@ _bt_orderkeys(Relation relation, uint16 *numberOfKeys, ScanKey key, uint16 *qual
 bool
 _bt_checkqual(IndexScanDesc scan, IndexTuple itup)
 {
-    if (scan->numberOfKeys > 0)
+    BTScanOpaque so;
+    
+    so = (BTScanOpaque) scan->opaque;
+    if (so->numberOfKeys > 0)
+	return (index_keytest(itup, RelationGetTupleDescriptor(scan->relation),
+			      so->numberOfKeys, so->keyData));
+    else
+	return (true);
+}
+
+bool
+_bt_checkforkeys(IndexScanDesc scan, IndexTuple itup, Size keysz)
+{
+    BTScanOpaque so;
+    
+    so = (BTScanOpaque) scan->opaque;
+    if ( keysz > 0 && so->numberOfKeys >= keysz )
 	return (index_keytest(itup, RelationGetTupleDescriptor(scan->relation),
-			      scan->numberOfKeys, scan->keyData));
+			      keysz, so->keyData));
     else
 	return (true);
 }
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 5a86749a66f..db836e9ab17 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.6 1997/03/12 21:00:17 scrappy Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.7 1997/03/18 18:39:40 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,8 +53,9 @@ static bool match_index_to_operand(int indexkey, Expr *operand,
 static List *match_index_orclause(Rel *rel, Rel *index, int indexkey,
     int xclass, List *or_clauses, List *other_matching_indices);
 static List *group_clauses_by_indexkey(Rel *rel, Rel *index,
-    int *indexkeys, Oid *classes, List *clauseinfo_list,
-    bool join);
+    int *indexkeys, Oid *classes, List *clauseinfo_list);
+static List *group_clauses_by_ikey_for_joins(Rel *rel, Rel *index,
+    int *indexkeys, Oid *classes, List *join_cinfo_list, List *restr_cinfo_list);
 static CInfo *match_clause_to_indexkey(Rel *rel, Rel *index, int indexkey,
     int xclass, CInfo *clauseInfo, bool join);
 static bool pred_test(List *predicate_list, List *clauseinfo_list,
@@ -63,7 +64,8 @@ static bool one_pred_test(Expr *predicate, List *clauseinfo_list);
 static bool one_pred_clause_expr_test(Expr *predicate, Node *clause);
 static bool one_pred_clause_test(Expr *predicate, Node *clause);
 static bool clause_pred_clause_test(Expr *predicate, Node *clause);
-static List *indexable_joinclauses(Rel *rel, Rel *index, List *joininfo_list);
+static List *indexable_joinclauses (Rel *rel, Rel *index, 
+		List *joininfo_list, List *clauseinfo_list);
 static List *index_innerjoin(Query *root, Rel *rel, 
 			     List *clausegroup_list, Rel *index);
 static List *create_index_paths(Query *root, Rel *rel, Rel *index,
@@ -114,7 +116,6 @@ find_index_paths (Query *root,
     List *joinclausegroups = NIL;
     List *joinpaths = NIL;
     List *retval = NIL;
-    extern List *add_index_paths();
     
     if(indices == NIL)
 	return(NULL);
@@ -160,8 +161,7 @@ find_index_paths (Query *root,
 						 index,
 						 index->indexkeys,
 						 index->classlist,
-						 clauseinfo_list,
-						 false);
+						 clauseinfo_list);
     
     scanpaths = NIL;
     if (scanclausegroups != NIL)
@@ -178,7 +178,7 @@ find_index_paths (Query *root,
      * 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);
+    joinclausegroups = indexable_joinclauses(rel,index,joininfo_list, clauseinfo_list);
     joinpaths = NIL;
 
     if (joinclausegroups != NIL)
@@ -375,10 +375,8 @@ match_index_orclause(Rel *rel,
  * 	(2) a list of join clauses between 'rel' and a fixed set of
  * 		relations,
  * 	depending on the value of 'join'.
- * 'startlist' is a list of those clause nodes that have matched the keys 
- * 	that have already been checked.
- * 'join' is a flag indicating that the clauses being checked are join
- * 	clauses.
+ *
+ *	NOTE: it works now for restriction clauses only. - vadim 03/18/97
  *    
  * Returns all possible groups of clauses that will match (given that
  * one or more clauses can match any of the remaining keys).
@@ -391,45 +389,144 @@ group_clauses_by_indexkey(Rel *rel,
 			  Rel *index,
 			  int *indexkeys,
 			  Oid *classes,
-			  List *clauseinfo_list,
-			  bool join)
+			  List *clauseinfo_list)
 {
     List *curCinfo		= NIL;
     CInfo *matched_clause	= (CInfo*)NULL;
     List *clausegroup	= NIL;
-
+    int curIndxKey;
+    Oid curClass;
 
     if (clauseinfo_list == NIL)
 	return NIL;
 
-    foreach (curCinfo,clauseinfo_list) {
-	CInfo *temp	= (CInfo*)lfirst(curCinfo);
-	int *curIndxKey	= indexkeys;
-	Oid *curClass	= classes;
+    while ( !DoneMatchingIndexKeys(indexkeys, index) )
+    {
+    	List *tempgroup = NIL;
+    	
+    	curIndxKey = indexkeys[0];
+	curClass = classes[0];
+
+    	foreach (curCinfo,clauseinfo_list) 
+    	{
+	    CInfo *temp	= (CInfo*)lfirst(curCinfo);
+
+	    matched_clause = match_clause_to_indexkey (rel, 
+						       index, 
+						       curIndxKey,
+						       curClass,
+						       temp,
+						       false);
+	    if (!matched_clause)
+		continue;
+
+	    tempgroup = lappend(tempgroup, matched_clause);
+	}
+	if ( tempgroup == NIL )
+	    break;
+
+	clausegroup = nconc (clausegroup, tempgroup);
+	
+	indexkeys++;
+	classes++;
+	
+    }
+
+    /* clausegroup holds all matched clauses ordered by indexkeys */
+
+    if (clausegroup != NIL)
+	return(lcons(clausegroup, NIL));
+    return NIL;
+}
+
+/*    
+ * group-clauses-by-ikey-for-joins--
+ *    special edition of group-clauses-by-indexkey - will
+ *    match join & restriction clauses. See comment in indexable_joinclauses.
+ *	- vadim 03/18/97
+ *    
+ */
+static List *
+group_clauses_by_ikey_for_joins(Rel *rel,
+			  Rel *index,
+			  int *indexkeys,
+			  Oid *classes,
+			  List *join_cinfo_list,
+			  List *restr_cinfo_list)
+{
+    List *curCinfo		= NIL;
+    CInfo *matched_clause	= (CInfo*)NULL;
+    List *clausegroup	= NIL;
+    int curIndxKey;
+    Oid curClass;
+    bool jfound = false;
+
+    if (join_cinfo_list == NIL)
+	return NIL;
+
+    while ( !DoneMatchingIndexKeys(indexkeys, index) )
+    {
+    	List *tempgroup = NIL;
+    	
+    	curIndxKey = indexkeys[0];
+	curClass = classes[0];
+
+    	foreach (curCinfo,join_cinfo_list) 
+    	{
+	    CInfo *temp	= (CInfo*)lfirst(curCinfo);
+
+	    matched_clause = match_clause_to_indexkey (rel, 
+						       index, 
+						       curIndxKey,
+						       curClass,
+						       temp,
+						       true);
+	    if (!matched_clause)
+		continue;
+
+	    tempgroup = lappend(tempgroup, matched_clause);
+	    jfound = true;
+	}
+    	foreach (curCinfo,restr_cinfo_list) 
+    	{
+	    CInfo *temp	= (CInfo*)lfirst(curCinfo);
 
-	do {
-	    /*
-	     * If we can't find any matching clauses for the first of 
-	     * the remaining keys, give up.
-	     */
 	    matched_clause = match_clause_to_indexkey (rel, 
 						       index, 
-						       curIndxKey[0],
-						       curClass[0],
+						       curIndxKey,
+						       curClass,
 						       temp,
-						       join);
+						       false);
 	    if (!matched_clause)
-		break;
+		continue;
 
-	    clausegroup = lcons(matched_clause, clausegroup);
-	    curIndxKey++;
-	    curClass++;
+	    tempgroup = lappend(tempgroup, matched_clause);
+	}
+	if ( tempgroup == NIL )
+	    break;
 
-	} while ( !DoneMatchingIndexKeys(curIndxKey, index) );
+	clausegroup = nconc (clausegroup, tempgroup);
+	
+	indexkeys++;
+	classes++;
+	
     }
 
+    /* clausegroup holds all matched clauses ordered by indexkeys */
+
     if (clausegroup != NIL)
+    {
+	/* 
+	 * if no one join clause was matched then there ain't clauses
+	 * for joins at all.
+	 */
+    	if ( !jfound )
+    	{
+    	    freeList (clausegroup);
+    	    return NIL;
+    	}
 	return(lcons(clausegroup, NIL));
+    }
     return NIL;
 }
 
@@ -482,6 +579,7 @@ match_clause_to_indexkey(Rel *rel,
     Expr *clause = clauseInfo->clause;
     Var *leftop, *rightop;
     Oid join_op = InvalidOid;
+    Oid restrict_op = InvalidOid;
     bool isIndexable = false;
 
     if (or_clause((Node*)clause) ||
@@ -495,90 +593,87 @@ match_clause_to_indexkey(Rel *rel,
      * (operator var/func constant) and (operator constant var/func)
      */
     if (!join) 
-	{
-	    Oid restrict_op = InvalidOid;
-
-	    /*
-	     * Check for standard s-argable clause
-	     */
+    {
+	/*
+	 * Check for standard s-argable clause
+	 */
 #ifdef INDEXSCAN_PATCH
 	    /* Handle also function parameters.  DZ - 27-8-1996 */ 
-	    if ((rightop && IsA(rightop,Const)) ||
+	if ((rightop && IsA(rightop,Const)) ||
 		(rightop && IsA(rightop,Param)))
 #else
-	    if (rightop && IsA(rightop,Const))
+	if (rightop && IsA(rightop,Const))
 #endif
-		{
-		    restrict_op = ((Oper*)((Expr*)clause)->oper)->opno;
-		    isIndexable =
-			( op_class(restrict_op, xclass, index->relam) &&
+	{
+	    restrict_op = ((Oper*)((Expr*)clause)->oper)->opno;
+	    isIndexable =
+		( op_class(restrict_op, xclass, index->relam) &&
 			 IndexScanableOperand(leftop,
 					      indexkey,
 					      rel,
 					      index) );
-		}
+	}
 
-	    /*
-	     * Must try to commute the clause to standard s-arg format.
-	     */
+	/*
+	 * Must try to commute the clause to standard s-arg format.
+	 */
 #ifdef INDEXSCAN_PATCH
 	    /* ...And here...  - vadim 01/22/97 */ 
-	    else if ((leftop && IsA(leftop,Const)) ||
+	else if ((leftop && IsA(leftop,Const)) ||
 			(leftop && IsA(leftop,Param)))
 #else
-	    else if (leftop && IsA(leftop,Const))
+	else if (leftop && IsA(leftop,Const))
 #endif
-		{
-		    restrict_op =
-			get_commutator(((Oper*)((Expr*)clause)->oper)->opno);
+	{
+	    restrict_op =
+		get_commutator(((Oper*)((Expr*)clause)->oper)->opno);
 
-		    if ( (restrict_op != InvalidOid) &&
+	    if ( (restrict_op != InvalidOid) &&
 			op_class(restrict_op, xclass, index->relam) &&
 			IndexScanableOperand(rightop,
 					     indexkey,rel,index) )
-			{
-			    isIndexable = true;
-			    /*
-			     * In place list modification.
-			     * (op const var/func) -> (op var/func const)
-			     */
-			    /* BUG!  Old version:
-			       CommuteClause(clause, restrict_op);
-			       */
-			    CommuteClause((Node*)clause);
-			}
-		}
-	} 
+	    {
+		isIndexable = true;
+		/*
+		 * In place list modification.
+		 * (op const var/func) -> (op var/func const)
+		 */
+		CommuteClause((Node*)clause);
+	    }
+	}
+    } 
     /*
      * Check for an indexable scan on one of the join relations.
      * clause is of the form (operator var/func var/func)
      */
     else
+    {
+	if (rightop
+		&& match_index_to_operand(indexkey,(Expr*)rightop,rel,index))
 	{
-	    if (rightop
-		&& match_index_to_operand(indexkey,(Expr*)rightop,rel,index)) {
 					
 		join_op = get_commutator(((Oper*)((Expr*)clause)->oper)->opno);
 
-	    } else if (leftop
+	} else if (leftop
 		       && match_index_to_operand(indexkey,
-						 (Expr*)leftop,rel,index)) {
+						 (Expr*)leftop,rel,index))
+	{
 		join_op = ((Oper*)((Expr*)clause)->oper)->opno;
-	    }
+	}
 
-	    if ( join_op && op_class(join_op,xclass,index->relam) &&
+	if ( join_op && op_class(join_op,xclass,index->relam) &&
 		join_clause_p((Node*)clause))
-		{
-		    isIndexable = true;
-
-		    /*
-		     * If we're using the operand's commutator we must
-		     * commute the clause.
-		     */
-		    if (join_op != ((Oper*)((Expr*)clause)->oper)->opno)
+	{
+	    isIndexable = true;
+
+	    /*
+	     * If we're using the operand's commutator we must
+	     * commute the clause.
+	     */
+	    if (join_op != ((Oper*)((Expr*)clause)->oper)->opno)
 			CommuteClause((Node*)clause);
-		}
 	}
+    }
 
     if (isIndexable)
 	return(clauseInfo);
@@ -955,10 +1050,15 @@ clause_pred_clause_test(Expr *predicate, Node *clause)
  *    in the join clause as its outer join relation.
  *    
  * Returns a list of these clause groups.
+ *
+ *    Added: clauseinfo_list - list of restriction CInfos. It's to
+ *	support multi-column indices in joins and for cases
+ *	when a key is in both join & restriction clauses. - vadim 03/18/97
  *    
  */
 static List *
-indexable_joinclauses(Rel *rel, Rel *index, List *joininfo_list)
+indexable_joinclauses(Rel *rel, Rel *index, 
+			List *joininfo_list, List *clauseinfo_list)
 {
     JInfo *joininfo = (JInfo*)NULL;
     List *cg_list = NIL;
@@ -967,13 +1067,16 @@ indexable_joinclauses(Rel *rel, Rel *index, List *joininfo_list)
 
     foreach(i,joininfo_list) { 
 	joininfo = (JInfo*)lfirst(i);
+	
+	if ( joininfo->jinfoclauseinfo == NIL )
+	    continue;
 	clausegroups = 
-	    group_clauses_by_indexkey (rel,
+	    group_clauses_by_ikey_for_joins (rel,
 				       index,
 				       index->indexkeys,
 				       index->classlist,
 				       joininfo->jinfoclauseinfo,
-				       true);
+				       clauseinfo_list);
 
 	if (clausegroups != NIL) {
 	    List *clauses = lfirst(clausegroups);
@@ -1056,6 +1159,7 @@ index_innerjoin(Query *root, Rel *rel, List *clausegroup_list, Rel *index)
 	pathnode->path.pathtype = T_IndexScan;
 	pathnode->path.parent = rel;
 	pathnode->indexid = index->relids;
+	pathnode->indexkeys = index->indexkeys;
 	pathnode->indexqual = clausegroup;
 
 	pathnode->path.joinid = ((CInfo*)lfirst(clausegroup))->cinfojoinid;
@@ -1130,7 +1234,7 @@ create_index_paths(Query *root,
 		temp = false;
 	    }
 	}
-	  
+
 	if (!join || temp) {	/* restriction, ordering scan */
 	    temp_path = create_index_path (root, rel,index,clausegroup,join);
 	    temp_node = 
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 463cc2448e3..2783e3917f4 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.8 1997/03/12 21:05:56 scrappy Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.9 1997/03/18 18:40:05 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -417,22 +417,35 @@ create_nestloop_node(JoinPath *best_path,
     NestLoop *join_node = (NestLoop*)NULL;
 
     if (IsA(inner_node,IndexScan)) {
-	/*  An index is being used to reduce the number of tuples scanned in 
-	 *    the inner relation.
-	 * There will never be more than one index used in the inner 
-	 * scan path, so we need only consider the first set of 
-	 *    qualifications in indxqual. 
+	/* An index is being used to reduce the number of tuples scanned in 
+	 * the inner relation. There will never be more than one index used 
+	 * in the inner scan path, so we need only consider the first set of 
+	 * qualifications in indxqual. 
+	 *
+	 * But there may be more than one clauses in this "first set" 
+	 * in the case of multi-column indices. - vadim 03/18/97
 	 */
 
 	List *inner_indxqual = lfirst(((IndexScan*)inner_node)->indxqual);
-	List *inner_qual = (inner_indxqual == NULL)? NULL:lfirst(inner_indxqual);
+	List *inner_qual;
+	bool found = false;
+
+	foreach (inner_qual, inner_indxqual)
+	{
+	    if ( !(qual_clause_p ((Node*)inner_qual)) )
+	    {
+	    	found = true;
+	    	break;
+	    }
+	}
 
 	/* If we have in fact found a join index qualification, remove these
 	 * index clauses from the nestloop's join clauses and reset the 
 	 * inner(index) scan's qualification so that the var nodes refer to
 	 * the proper outer join relation attributes.
 	 */
-	if  (!(qual_clause_p((Node*)inner_qual))) {
+	if  ( found )
+	{
 	    List *new_inner_qual = NIL;
 	    
 	    clauses = set_difference(clauses,inner_indxqual);
@@ -613,7 +626,7 @@ fix_indxqual_references(Node *clause, Path *index_path)
 	if (lfirsti(index_path->parent->relids) == ((Var*)clause)->varno) {
 	    int pos = 0;
 	    int varatt = ((Var*)clause)->varattno;
-	    int *indexkeys = index_path->parent->indexkeys;
+	    int *indexkeys = ((IndexPath*)index_path)->indexkeys;
 	    
 	    if (indexkeys) {
 		while (indexkeys[pos] != 0) {
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 728ac9b422e..3362367dace 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.1.1.1 1996/07/09 06:21:38 scrappy Exp $
+ *    $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.2 1997/03/18 18:40:40 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -248,10 +248,11 @@ create_index_path(Query *root,
     
     pathnode->path.pathtype = T_IndexScan;
     pathnode->path.parent = rel;
-    pathnode->indexid = index->relids;
-
     pathnode->path.p_ordering.ordtype = SORTOP_ORDER;
     pathnode->path.p_ordering.ord.sortop = index->ordering;
+
+    pathnode->indexid = index->relids;
+    pathnode->indexkeys = index->indexkeys;
     pathnode->indexqual = NIL;
 
     /* copy clauseinfo list into path for expensive function processing 
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 5b602705d5c..ab32fbd8238 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nbtree.h,v 1.9 1997/02/22 10:08:27 vadim Exp $
+ * $Id: nbtree.h,v 1.10 1997/03/18 18:41:16 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -68,6 +68,7 @@ typedef struct BTScanOpaqueData {
     Buffer	btso_mrkbuf;
     uint16	qual_ok;		/* 0 for quals like key == 1 && key > 2 */
     uint16	numberOfKeys;		/* number of key attributes */
+    uint16	numberOfFirstKeys;	/* number of first key attributes */
     ScanKey	keyData;		/* key descriptor */
 } BTScanOpaqueData;
 
@@ -270,9 +271,9 @@ extern bool _bt_invokestrat(Relation rel, AttrNumber attno,
 extern ScanKey  _bt_mkscankey(Relation rel, IndexTuple itup);
 extern void _bt_freeskey(ScanKey skey);
 extern void _bt_freestack(BTStack stack);
-extern void _bt_orderkeys(Relation relation, uint16 *numberOfKeys,
-			  ScanKey key, uint16 *qual_ok);
+extern void _bt_orderkeys(Relation relation, BTScanOpaque so);
 extern bool _bt_checkqual(IndexScanDesc scan, IndexTuple itup);
+extern bool _bt_checkforkeys(IndexScanDesc scan, IndexTuple itup, Size keysz);
 extern BTItem _bt_formitem(IndexTuple itup);
 
 /*
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 7c0bce12e2c..16c7dd29955 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.3 1996/11/06 07:44:18 scrappy Exp $
+ * $Id: relation.h,v 1.4 1997/03/18 18:41:37 scrappy Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -150,6 +150,7 @@ typedef struct IndexPath {
     Path	path;
     List	*indexid;
     List	*indexqual;
+    int		*indexkeys;	/* to transform heap attnos into index ones */
 } IndexPath;
 
 typedef struct JoinPath {