Cross-data-type comparisons are now indexable by btrees, pursuant to my

pghackers proposal of 8-Nov.  All the existing cross-type comparison
operators (int2/int4/int8 and float4/float8) have appropriate support.
The original proposal of storing the right-hand-side datatype as part of
the primary key for pg_amop and pg_amproc got modified a bit in the event;
it is easier to store zero as the 'default' case and only store a nonzero
when the operator is actually cross-type.  Along the way, remove the
long-since-defunct bigbox_ops operator class.

12 files changed, 576 insertions, 341 deletions

diff --git a/src/backend/access/common/scankey.c b/src/backend/access/common/scankey.c
index 93741cbb84..2fa02b7d91 100644
--- a/src/backend/access/common/scankey.c
+++ b/src/backend/access/common/scankey.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/common/scankey.c,v 1.23 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/common/scankey.c,v 1.24 2003/11/12 21:15:46 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -31,15 +31,43 @@ ScanKeyEntryInitialize(ScanKey entry,
 					   int flags,
 					   AttrNumber attributeNumber,
 					   StrategyNumber strategy,
+					   Oid subtype,
 					   RegProcedure procedure,
-					   Datum argument,
-					   Oid argtype)
+					   Datum argument)
 {
 	entry->sk_flags = flags;
 	entry->sk_attno = attributeNumber;
 	entry->sk_strategy = strategy;
+	entry->sk_subtype = subtype;
+	entry->sk_argument = argument;
+	fmgr_info(procedure, &entry->sk_func);
+}
+
+/*
+ * ScanKeyInit
+ *		Shorthand version of ScanKeyEntryInitialize: flags and subtype
+ *		are assumed to be zero (the usual value).
+ *
+ * This is the recommended version for hardwired lookups in system catalogs.
+ * It cannot handle NULL arguments, unary operators, or nondefault operators,
+ * but we need none of those features for most hardwired lookups.
+ *
+ * Note: CurrentMemoryContext at call should be as long-lived as the ScanKey
+ * itself, because that's what will be used for any subsidiary info attached
+ * to the ScanKey's FmgrInfo record.
+ */
+void
+ScanKeyInit(ScanKey entry,
+			AttrNumber attributeNumber,
+			StrategyNumber strategy,
+			RegProcedure procedure,
+			Datum argument)
+{
+	entry->sk_flags = 0;
+	entry->sk_attno = attributeNumber;
+	entry->sk_strategy = strategy;
+	entry->sk_subtype = InvalidOid;
 	entry->sk_argument = argument;
-	entry->sk_argtype = argtype;
 	fmgr_info(procedure, &entry->sk_func);
 }
 
@@ -57,14 +85,14 @@ ScanKeyEntryInitializeWithInfo(ScanKey entry,
 							   int flags,
 							   AttrNumber attributeNumber,
 							   StrategyNumber strategy,
+							   Oid subtype,
 							   FmgrInfo *finfo,
-							   Datum argument,
-							   Oid argtype)
+							   Datum argument)
 {
 	entry->sk_flags = flags;
 	entry->sk_attno = attributeNumber;
 	entry->sk_strategy = strategy;
+	entry->sk_subtype = subtype;
 	entry->sk_argument = argument;
-	entry->sk_argtype = argtype;
 	fmgr_info_copy(&entry->sk_func, finfo, CurrentMemoryContext);
 }
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 24168c9926..5db69a6b40 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/gist/gistget.c,v 1.37 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/gist/gistget.c,v 1.38 2003/11/12 21:15:46 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -221,40 +221,50 @@ gistindex_keytest(IndexTuple tuple,
 				  Page p,
 				  OffsetNumber offset)
 {
-	bool		isNull;
-	Datum		datum;
-	Datum		test;
-	GISTENTRY	de;
-
 	IncrIndexProcessed();
 
 	while (scanKeySize > 0)
 	{
+		Datum		datum;
+		bool		isNull;
+		Datum		test;
+		GISTENTRY	de;
+
 		datum = index_getattr(tuple,
-							  key[0].sk_attno,
+							  key->sk_attno,
 							  giststate->tupdesc,
 							  &isNull);
+		/* is the index entry NULL? */
 		if (isNull)
 		{
 			/* XXX eventually should check if SK_ISNULL */
 			return false;
 		}
-
-/* this code from backend/access/common/indexvalid.c. But why and what???
-		if (key[0].sk_flags & SK_ISNULL)
+		/* is the compared-to datum NULL? */
+		if (key->sk_flags & SK_ISNULL)
 			return false;
-*/
-		gistdentryinit(giststate, key[0].sk_attno - 1, &de,
+
+		gistdentryinit(giststate, key->sk_attno - 1, &de,
 					   datum, r, p, offset,
 					   IndexTupleSize(tuple) - sizeof(IndexTupleData),
 					   FALSE, isNull);
 
-		test = FunctionCall3(&key[0].sk_func,
+		/*
+		 * Call the Consistent function to evaluate the test.  The arguments
+		 * are the index datum (as a GISTENTRY*), the comparison datum, and
+		 * the comparison operator's strategy number and subtype from pg_amop.
+		 *
+		 * (Presently there's no need to pass the subtype since it'll always
+		 * be zero, but might as well pass it for possible future use.)
+		 */
+		test = FunctionCall4(&key->sk_func,
 							 PointerGetDatum(&de),
-							 key[0].sk_argument,
-							 Int32GetDatum(key[0].sk_strategy));
+							 key->sk_argument,
+							 Int32GetDatum(key->sk_strategy),
+							 ObjectIdGetDatum(key->sk_subtype));
 
-		if (de.key != datum && !isAttByVal(giststate, key[0].sk_attno - 1))
+		/* if index datum had to be decompressed, free it */
+		if (de.key != datum && !isAttByVal(giststate, key->sk_attno - 1))
 			if (DatumGetPointer(de.key) != NULL)
 				pfree(DatumGetPointer(de.key));
 
@@ -264,6 +274,7 @@ gistindex_keytest(IndexTuple tuple,
 		scanKeySize--;
 		key++;
 	}
+
 	return true;
 }
 
diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
index 960d1c2f25..9b9d1f6034 100644
--- a/src/backend/access/gist/gistscan.c
+++ b/src/backend/access/gist/gistscan.c
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/gist/gistscan.c,v 1.48 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/gist/gistscan.c,v 1.49 2003/11/12 21:15:46 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -109,7 +109,8 @@ gistrescan(PG_FUNCTION_ARGS)
 		 * Modify the scan key so that the Consistent function is called
 		 * for all comparisons.  The original operator is passed to the
 		 * Consistent function in the form of its strategy number, which
-		 * is available from the sk_strategy field.
+		 * is available from the sk_strategy field, and its subtype from
+		 * the sk_subtype field.
 		 */
 		for (i = 0; i < s->numberOfKeys; i++)
 		{
diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 0bfe3c01b8..f643906da1 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/heap/tuptoaster.c,v 1.39 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/heap/tuptoaster.c,v 1.40 2003/11/12 21:15:46 tgl Exp $
  *
  *
  * INTERFACE ROUTINES
@@ -31,7 +31,6 @@
 #include "access/genam.h"
 #include "access/tuptoaster.h"
 #include "catalog/catalog.h"
-#include "catalog/pg_type.h"
 #include "utils/rel.h"
 #include "utils/builtins.h"
 #include "utils/fmgroids.h"
@@ -968,11 +967,10 @@ toast_delete_datum(Relation rel, Datum value)
 	 * Setup a scan key to fetch from the index by va_valueid (we don't
 	 * particularly care whether we see them in sequence or not)
 	 */
-	ScanKeyEntryInitialize(&toastkey, 0,
-						   (AttrNumber) 1,
-						   BTEqualStrategyNumber, F_OIDEQ,
-						   ObjectIdGetDatum(attr->va_content.va_external.va_valueid),
-						   OIDOID);
+	ScanKeyInit(&toastkey,
+				(AttrNumber) 1,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(attr->va_content.va_external.va_valueid));
 
 	/*
 	 * Find the chunks by index
@@ -1040,11 +1038,10 @@ toast_fetch_datum(varattrib *attr)
 	/*
 	 * Setup a scan key to fetch from the index by va_valueid
 	 */
-	ScanKeyEntryInitialize(&toastkey, 0,
-						   (AttrNumber) 1,
-						   BTEqualStrategyNumber, F_OIDEQ,
-						   ObjectIdGetDatum(attr->va_content.va_external.va_valueid),
-						   OIDOID);
+	ScanKeyInit(&toastkey,
+				(AttrNumber) 1,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(attr->va_content.va_external.va_valueid));
 
 	/*
 	 * Read the chunks by index
@@ -1195,33 +1192,32 @@ toast_fetch_datum_slice(varattrib *attr, int32 sliceoffset, int32 length)
 	 * Setup a scan key to fetch from the index. This is either two keys
 	 * or three depending on the number of chunks.
 	 */
-	ScanKeyEntryInitialize(&toastkey[0], 0,
-						   (AttrNumber) 1,
-						   BTEqualStrategyNumber, F_OIDEQ,
-						   ObjectIdGetDatum(attr->va_content.va_external.va_valueid),
-						   OIDOID);
+	ScanKeyInit(&toastkey[0],
+				(AttrNumber) 1,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(attr->va_content.va_external.va_valueid));
 
 	/*
 	 * Use equality condition for one chunk, a range condition otherwise:
 	 */
 	if (numchunks == 1)
 	{
-		ScanKeyEntryInitialize(&toastkey[1], 0,
-							   (AttrNumber) 2,
-							   BTEqualStrategyNumber, F_INT4EQ,
-							   Int32GetDatum(startchunk), INT4OID);
+		ScanKeyInit(&toastkey[1],
+					(AttrNumber) 2,
+					BTEqualStrategyNumber, F_INT4EQ,
+					Int32GetDatum(startchunk));
 		nscankeys = 2;
 	}
 	else
 	{
-		ScanKeyEntryInitialize(&toastkey[1], 0,
-							   (AttrNumber) 2,
-							   BTGreaterEqualStrategyNumber, F_INT4GE,
-							   Int32GetDatum(startchunk), INT4OID);
-		ScanKeyEntryInitialize(&toastkey[2], 0,
-							   (AttrNumber) 2,
-							   BTLessEqualStrategyNumber, F_INT4LE,
-							   Int32GetDatum(endchunk), INT4OID);
+		ScanKeyInit(&toastkey[1],
+					(AttrNumber) 2,
+					BTGreaterEqualStrategyNumber, F_INT4GE,
+					Int32GetDatum(startchunk));
+		ScanKeyInit(&toastkey[2],
+					(AttrNumber) 2,
+					BTLessEqualStrategyNumber, F_INT4LE,
+					Int32GetDatum(endchunk));
 		nscankeys = 3;
 	}
 
diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index 79756513ab..bd69885830 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtcompare.c,v 1.46 2003/08/04 02:39:57 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtcompare.c,v 1.47 2003/11/12 21:15:46 tgl Exp $
  *
  * NOTES
  *
@@ -98,6 +98,90 @@ btint8cmp(PG_FUNCTION_ARGS)
 }
 
 Datum
+btint48cmp(PG_FUNCTION_ARGS)
+{
+	int32		a = PG_GETARG_INT32(0);
+	int64		b = PG_GETARG_INT64(1);
+
+	if (a > b)
+		PG_RETURN_INT32(1);
+	else if (a == b)
+		PG_RETURN_INT32(0);
+	else
+		PG_RETURN_INT32(-1);
+}
+
+Datum
+btint84cmp(PG_FUNCTION_ARGS)
+{
+	int64		a = PG_GETARG_INT64(0);
+	int32		b = PG_GETARG_INT32(1);
+
+	if (a > b)
+		PG_RETURN_INT32(1);
+	else if (a == b)
+		PG_RETURN_INT32(0);
+	else
+		PG_RETURN_INT32(-1);
+}
+
+Datum
+btint24cmp(PG_FUNCTION_ARGS)
+{
+	int16		a = PG_GETARG_INT16(0);
+	int32		b = PG_GETARG_INT32(1);
+
+	if (a > b)
+		PG_RETURN_INT32(1);
+	else if (a == b)
+		PG_RETURN_INT32(0);
+	else
+		PG_RETURN_INT32(-1);
+}
+
+Datum
+btint42cmp(PG_FUNCTION_ARGS)
+{
+	int32		a = PG_GETARG_INT32(0);
+	int16		b = PG_GETARG_INT16(1);
+
+	if (a > b)
+		PG_RETURN_INT32(1);
+	else if (a == b)
+		PG_RETURN_INT32(0);
+	else
+		PG_RETURN_INT32(-1);
+}
+
+Datum
+btint28cmp(PG_FUNCTION_ARGS)
+{
+	int16		a = PG_GETARG_INT16(0);
+	int64		b = PG_GETARG_INT64(1);
+
+	if (a > b)
+		PG_RETURN_INT32(1);
+	else if (a == b)
+		PG_RETURN_INT32(0);
+	else
+		PG_RETURN_INT32(-1);
+}
+
+Datum
+btint82cmp(PG_FUNCTION_ARGS)
+{
+	int64		a = PG_GETARG_INT64(0);
+	int16		b = PG_GETARG_INT16(1);
+
+	if (a > b)
+		PG_RETURN_INT32(1);
+	else if (a == b)
+		PG_RETURN_INT32(0);
+	else
+		PG_RETURN_INT32(-1);
+}
+
+Datum
 btoidcmp(PG_FUNCTION_ARGS)
 {
 	Oid			a = PG_GETARG_OID(0);
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index 98f3abb511..719b1e1f0e 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.107 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.108 2003/11/12 21:15:46 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1577,26 +1577,27 @@ _bt_isequal(TupleDesc itupdesc, Page page, OffsetNumber offnum,
 
 	for (i = 1; i <= keysz; i++)
 	{
-		ScanKey		entry = &scankey[i - 1];
 		AttrNumber	attno;
 		Datum		datum;
 		bool		isNull;
 		int32		result;
 
-		attno = entry->sk_attno;
+		attno = scankey->sk_attno;
 		Assert(attno == i);
 		datum = index_getattr(itup, attno, itupdesc, &isNull);
 
 		/* NULLs are never equal to anything */
-		if ((entry->sk_flags & SK_ISNULL) || isNull)
+		if (isNull || (scankey->sk_flags & SK_ISNULL))
 			return false;
 
-		result = DatumGetInt32(FunctionCall2(&entry->sk_func,
-											 entry->sk_argument,
-											 datum));
+		result = DatumGetInt32(FunctionCall2(&scankey->sk_func,
+											 datum,
+											 scankey->sk_argument));
 
 		if (result != 0)
 			return false;
+
+		scankey++;
 	}
 
 	/* if we get here, the keys are equal */
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 3979f79c35..f920d2497e 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -12,7 +12,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.106 2003/09/29 23:40:26 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.107 2003/11/12 21:15:46 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -397,7 +397,6 @@ btrescan(PG_FUNCTION_ARGS)
 			so->keyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
 		else
 			so->keyData = (ScanKey) NULL;
-		so->numberOfKeys = scan->numberOfKeys;
 		scan->opaque = so;
 	}
 
@@ -423,38 +422,14 @@ btrescan(PG_FUNCTION_ARGS)
 	 * _bt_first.	   - vadim 05/05/97
 	 */
 	if (scankey && scan->numberOfKeys > 0)
-	{
 		memmove(scan->keyData,
 				scankey,
 				scan->numberOfKeys * sizeof(ScanKeyData));
-		so->numberOfKeys = scan->numberOfKeys;
-		memmove(so->keyData,
-				scankey,
-				so->numberOfKeys * sizeof(ScanKeyData));
-	}
+	so->numberOfKeys = 0;		/* until _bt_preprocess_keys sets it */
 
 	PG_RETURN_VOID();
 }
 
-void
-btmovescan(IndexScanDesc scan, Datum v)
-{
-	ItemPointer iptr;
-	BTScanOpaque so;
-
-	so = (BTScanOpaque) scan->opaque;
-
-	/* we aren't holding any read locks, but gotta drop the pin */
-	if (ItemPointerIsValid(iptr = &(scan->currentItemData)))
-	{
-		ReleaseBuffer(so->btso_curbuf);
-		so->btso_curbuf = InvalidBuffer;
-		ItemPointerSetInvalid(iptr);
-	}
-
-	so->keyData[0].sk_argument = v;
-}
-
 /*
  *	btendscan() -- close down a scan
  */
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 432a1ab0c2..87178d1242 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.81 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.82 2003/11/12 21:15:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,6 +17,7 @@
 
 #include "access/genam.h"
 #include "access/nbtree.h"
+#include "utils/lsyscache.h"
 
 
 static Buffer _bt_walk_left(Relation rel, Buffer buf);
@@ -325,17 +326,16 @@ _bt_compare(Relation rel,
 	 * (see _bt_first).
 	 */
 
-	for (i = 0; i < keysz; i++)
+	for (i = 1; i <= keysz; i++)
 	{
-		ScanKey		entry = &scankey[i];
 		Datum		datum;
 		bool		isNull;
 		int32		result;
 
-		datum = index_getattr(itup, entry->sk_attno, itupdesc, &isNull);
+		datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull);
 
 		/* see comments about NULLs handling in btbuild */
-		if (entry->sk_flags & SK_ISNULL)		/* key is NULL */
+		if (scankey->sk_flags & SK_ISNULL)		/* key is NULL */
 		{
 			if (isNull)
 				result = 0;		/* NULL "=" NULL */
@@ -348,14 +348,28 @@ _bt_compare(Relation rel,
 		}
 		else
 		{
-			result = DatumGetInt32(FunctionCall2(&entry->sk_func,
-												 entry->sk_argument,
-												 datum));
+			/*
+			 * The sk_func needs to be passed the index value as left arg
+			 * and the sk_argument as right arg (they might be of different
+			 * types).  Since it is convenient for callers to think of
+			 * _bt_compare as comparing the scankey to the index item,
+			 * we have to flip the sign of the comparison result.
+			 *
+			 * Note: curious-looking coding is to avoid overflow if
+			 * comparison function returns INT_MIN.  There is no risk of
+			 * overflow for positive results.
+			 */
+			result = DatumGetInt32(FunctionCall2(&scankey->sk_func,
+												 datum,
+												 scankey->sk_argument));
+			result = (result < 0) ? 1 : -result;
 		}
 
 		/* if the keys are unequal, return the difference */
 		if (result != 0)
 			return result;
+
+		scankey++;
 	}
 
 	/* if we get here, the keys are equal */
@@ -448,126 +462,203 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	StrategyNumber strat;
 	bool		res;
 	int32		result;
-	bool		scanFromEnd;
 	bool		continuescan;
 	ScanKey		scankeys = NULL;
+	ScanKey	   *startKeys = NULL;
 	int			keysCount = 0;
-	int		   *nKeyIs = NULL;
-	int			i,
-				j;
+	int			i;
 	StrategyNumber strat_total;
 
 	/*
-	 * Order the scan keys in our canonical fashion and eliminate any
-	 * redundant keys.
+	 * Examine the scan keys and eliminate any redundant keys; also
+	 * discover how many keys must be matched to continue the scan.
 	 */
-	_bt_orderkeys(scan);
+	_bt_preprocess_keys(scan);
 
 	/*
-	 * Quit now if _bt_orderkeys() discovered that the scan keys can never
-	 * be satisfied (eg, x == 1 AND x > 2).
+	 * Quit now if _bt_preprocess_keys() discovered that the scan keys can
+	 * never be satisfied (eg, x == 1 AND x > 2).
 	 */
 	if (!so->qual_ok)
 		return false;
 
-	/*
+	/*----------
 	 * Examine the scan keys to discover where we need to start the scan.
+	 *
+	 * We want to identify the keys that can be used as starting boundaries;
+	 * these are =, >, or >= keys for a forward scan or =, <, <= keys for
+	 * a backwards scan.  We can use keys for multiple attributes so long as
+	 * the prior attributes had only =, >= (resp. =, <=) keys.  Once we accept
+	 * a > or < boundary or find an attribute with no boundary (which can be
+	 * thought of as the same as "> -infinity"), we can't use keys for any
+	 * attributes to its right, because it would break our simplistic notion
+	 * of what initial positioning strategy to use.
+	 *
+	 * When the scan keys include non-default operators, _bt_preprocess_keys
+	 * may not be able to eliminate redundant keys; in such cases we will
+	 * arbitrarily pick a usable one for each attribute.  This is correct
+	 * but possibly not optimal behavior.  (For example, with keys like
+	 * "x >= 4 AND x >= 5" we would elect to scan starting at x=4 when
+	 * x=5 would be more efficient.)  Since the situation only arises in
+	 * hokily-worded queries, live with it.
+	 *
+	 * When both equality and inequality keys appear for a single attribute
+	 * (again, only possible when non-default operators appear), we *must*
+	 * select one of the equality keys for the starting point, because
+	 * _bt_checkkeys() will stop the scan as soon as an equality qual fails.
+	 * For example, if we have keys like "x >= 4 AND x = 10" and we elect to
+	 * start at x=4, we will fail and stop before reaching x=10.  If multiple
+	 * equality quals survive preprocessing, however, it doesn't matter which
+	 * one we use --- by definition, they are either redundant or
+	 * contradictory.
+	 *----------
 	 */
-	scanFromEnd = false;
 	strat_total = BTEqualStrategyNumber;
 	if (so->numberOfKeys > 0)
 	{
-		nKeyIs = (int *) palloc(so->numberOfKeys * sizeof(int));
-		for (i = 0; i < so->numberOfKeys; i++)
-		{
-			AttrNumber	attno = so->keyData[i].sk_attno;
-
-			/* ignore keys for already-determined attrs */
-			if (attno <= keysCount)
-				continue;
-			/* if we didn't find a boundary for the preceding attr, quit */
-			if (attno > keysCount + 1)
-				break;
+		AttrNumber	curattr;
+		ScanKey		chosen;
+		ScanKey		cur;
 
-			/*
-			 * Can we use this key as a starting boundary for this attr?
-			 *
-			 * We can use multiple keys if they look like, say, = >= = but we
-			 * have to stop after accepting a > or < boundary.
-			 */
-			strat = so->keyData[i].sk_strategy;
-			if (strat == strat_total ||
-				strat == BTEqualStrategyNumber)
-				nKeyIs[keysCount++] = i;
-			else if (ScanDirectionIsBackward(dir) &&
-					 (strat == BTLessStrategyNumber ||
-					  strat == BTLessEqualStrategyNumber))
+		startKeys = (ScanKey *) palloc(so->numberOfKeys * sizeof(ScanKey));
+		/*
+		 * chosen is the so-far-chosen key for the current attribute, if any.
+		 * We don't cast the decision in stone until we reach keys for the
+		 * next attribute.
+		 */
+		curattr = 1;
+		chosen = NULL;
+		/*
+		 * Loop iterates from 0 to numberOfKeys inclusive; we use the last
+		 * pass to handle after-last-key processing.  Actual exit from the
+		 * loop is at one of the "break" statements below.
+		 */
+		for (cur = so->keyData, i = 0;; cur++, i++)
+		{
+			if (i >= so->numberOfKeys || cur->sk_attno != curattr)
 			{
-				nKeyIs[keysCount++] = i;
-				strat_total = strat;
-				if (strat == BTLessStrategyNumber)
+				/*
+				 * Done looking at keys for curattr.  If we didn't find a
+				 * usable boundary key, quit; else save the boundary key
+				 * pointer in startKeys.
+				 */
+				if (chosen == NULL)
+					break;
+				startKeys[keysCount++] = chosen;
+				/*
+				 * Adjust strat_total, and quit if we have stored a > or < key.
+				 */
+				strat = chosen->sk_strategy;
+				if (strat != BTEqualStrategyNumber)
+				{
+					strat_total = strat;
+					if (strat == BTGreaterStrategyNumber ||
+						strat == BTLessStrategyNumber)
+						break;
+				}
+				/*
+				 * Done if that was the last attribute.
+				 */
+				if (i >= so->numberOfKeys)
 					break;
+				/*
+				 * Reset for next attr, which should be in sequence.
+				 */
+				Assert(cur->sk_attno == curattr + 1);
+				curattr = cur->sk_attno;
+				chosen = NULL;
 			}
-			else if (ScanDirectionIsForward(dir) &&
-					 (strat == BTGreaterStrategyNumber ||
-					  strat == BTGreaterEqualStrategyNumber))
+
+			/* Can we use this key as a starting boundary for this attr? */
+			switch (cur->sk_strategy)
 			{
-				nKeyIs[keysCount++] = i;
-				strat_total = strat;
-				if (strat == BTGreaterStrategyNumber)
+				case BTLessStrategyNumber:
+				case BTLessEqualStrategyNumber:
+					if (chosen == NULL && ScanDirectionIsBackward(dir))
+						chosen = cur;
+					break;
+				case BTEqualStrategyNumber:
+					/* override any non-equality choice */
+					chosen = cur;
+					break;
+				case BTGreaterEqualStrategyNumber:
+				case BTGreaterStrategyNumber:
+					if (chosen == NULL && ScanDirectionIsForward(dir))
+						chosen = cur;
 					break;
 			}
 		}
-		if (keysCount == 0)
-			scanFromEnd = true;
 	}
-	else
-		scanFromEnd = true;
 
-	/* if we just need to walk down one edge of the tree, do that */
-	if (scanFromEnd)
+	/*
+	 * If we found no usable boundary keys, we have to start from one end
+	 * of the tree.  Walk down that edge to the first or last key, and
+	 * scan from there.
+	 */
+	if (keysCount == 0)
 	{
-		if (nKeyIs)
-			pfree(nKeyIs);
+		if (startKeys)
+			pfree(startKeys);
 		return _bt_endpoint(scan, dir);
 	}
 
 	/*
 	 * We want to start the scan somewhere within the index.  Set up a
-	 * scankey we can use to search for the correct starting point.
+	 * 3-way-comparison scankey we can use to search for the boundary
+	 * point we identified above.
 	 */
 	scankeys = (ScanKey) palloc(keysCount * sizeof(ScanKeyData));
 	for (i = 0; i < keysCount; i++)
 	{
-		FmgrInfo   *procinfo;
-
-		j = nKeyIs[i];
+		ScanKey		cur = startKeys[i];
 
 		/*
-		 * _bt_orderkeys disallows it, but it's place to add some code
+		 * _bt_preprocess_keys disallows it, but it's place to add some code
 		 * later
 		 */
-		if (so->keyData[j].sk_flags & SK_ISNULL)
+		if (cur->sk_flags & SK_ISNULL)
 		{
-			pfree(nKeyIs);
+			pfree(startKeys);
 			pfree(scankeys);
 			elog(ERROR, "btree doesn't support is(not)null, yet");
 			return false;
 		}
 		/*
-		 * XXX what if sk_argtype is not same as index?
+		 * If scankey operator is of default subtype, we can use the
+		 * cached comparison procedure; otherwise gotta look it up in
+		 * the catalogs.
 		 */
-		procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
-		ScanKeyEntryInitializeWithInfo(scankeys + i,
-									   so->keyData[j].sk_flags,
-									   i + 1,
-									   InvalidStrategy,
-									   procinfo,
-									   so->keyData[j].sk_argument,
-									   so->keyData[j].sk_argtype);
+		if (cur->sk_subtype == InvalidOid)
+		{
+			FmgrInfo   *procinfo;
+
+			procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
+			ScanKeyEntryInitializeWithInfo(scankeys + i,
+										   cur->sk_flags,
+										   i + 1,
+										   InvalidStrategy,
+										   InvalidOid,
+										   procinfo,
+										   cur->sk_argument);
+		}
+		else
+		{
+			RegProcedure cmp_proc;
+
+			cmp_proc = get_opclass_proc(rel->rd_index->indclass[i],
+										cur->sk_subtype,
+										BTORDER_PROC);
+			ScanKeyEntryInitialize(scankeys + i,
+								   cur->sk_flags,
+								   i + 1,
+								   InvalidStrategy,
+								   cur->sk_subtype,
+								   cmp_proc,
+								   cur->sk_argument);
+		}
 	}
-	if (nKeyIs)
-		pfree(nKeyIs);
+
+	pfree(startKeys);
 
 	current = &(scan->currentItemData);
 
@@ -607,7 +698,8 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	 *
 	 * We could step forward in the latter case, but that'd be a waste of
 	 * time if we want to scan backwards.  So, it's now time to examine
-	 * the scan strategy to find the exact place to start the scan.
+	 * the initial-positioning strategy to find the exact place to start
+	 * the scan.
 	 *
 	 * Note: if _bt_step fails (meaning we fell off the end of the index in
 	 * one direction or the other), we either return false (no matches) or
@@ -855,8 +947,8 @@ _bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
 		}
 	}
 	else
-/* backwards scan */
 	{
+		/* backwards scan */
 		if (offnum > P_FIRSTDATAKEY(opaque))
 			offnum = OffsetNumberPrev(offnum);
 		else
@@ -1115,7 +1207,8 @@ _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
 }
 
 /*
- *	_bt_endpoint() -- Find the first or last key in the index.
+ *	_bt_endpoint() -- Find the first or last key in the index, and scan
+ * from there to the first key satisfying all the quals.
  *
  * This is used by _bt_first() to set up a scan when we've determined
  * that the scan must start at the beginning or end of the index (for
@@ -1205,7 +1298,9 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
 	btitem = (BTItem) PageGetItem(page, PageGetItemId(page, start));
 	itup = &(btitem->bti_itup);
 
-	/* see if we picked a winner */
+	/*
+	 * Okay, we are on the first or last tuple.  Does it pass all the quals?
+	 */
 	if (_bt_checkkeys(scan, itup, dir, &continuescan))
 	{
 		/* yes, return it */
@@ -1214,7 +1309,7 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
 	}
 	else if (continuescan)
 	{
-		/* no, but there might be another one that is */
+		/* no, but there might be another one that does */
 		res = _bt_next(scan, dir);
 	}
 	else
diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c
index a56665be5c..ed920eafd3 100644
--- a/src/backend/access/nbtree/nbtsort.c
+++ b/src/backend/access/nbtree/nbtsort.c
@@ -36,7 +36,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.77 2003/09/29 23:40:26 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.78 2003/11/12 21:15:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -594,33 +594,37 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2)
 		 * Another BTSpool for dead tuples exists. Now we have to merge
 		 * btspool and btspool2.
 		 */
-		ScanKey		entry;
-		Datum		attrDatum1,
-					attrDatum2;
-		bool		isFirstNull,
-					isSecondNull;
-		int32		compare;
 
 		/* the preparation of merge */
-		bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free);
-		bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate, true, &should_free2);
+		bti = (BTItem) tuplesort_getindextuple(btspool->sortstate,
+											   true, &should_free);
+		bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate,
+												true, &should_free2);
 		indexScanKey = _bt_mkscankey_nodata(index);
+
 		for (;;)
 		{
 			load1 = true;		/* load BTSpool next ? */
-			if (NULL == bti2)
+			if (bti2 == NULL)
 			{
-				if (NULL == bti)
+				if (bti == NULL)
 					break;
 			}
-			else if (NULL != bti)
+			else if (bti != NULL)
 			{
-
 				for (i = 1; i <= keysz; i++)
 				{
+					ScanKey		entry;
+					Datum		attrDatum1,
+								attrDatum2;
+					bool		isFirstNull,
+								isSecondNull;
+
 					entry = indexScanKey + i - 1;
-					attrDatum1 = index_getattr((IndexTuple) bti, i, tupdes, &isFirstNull);
-					attrDatum2 = index_getattr((IndexTuple) bti2, i, tupdes, &isSecondNull);
+					attrDatum1 = index_getattr((IndexTuple) bti, i, tupdes,
+											   &isFirstNull);
+					attrDatum2 = index_getattr((IndexTuple) bti2, i, tupdes,
+											   &isSecondNull);
 					if (isFirstNull)
 					{
 						if (!isSecondNull)
@@ -633,7 +637,11 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2)
 						break;
 					else
 					{
-						compare = DatumGetInt32(FunctionCall2(&entry->sk_func, attrDatum1, attrDatum2));
+						int32		compare;
+
+						compare = DatumGetInt32(FunctionCall2(&entry->sk_func,
+															  attrDatum1,
+															  attrDatum2));
 						if (compare > 0)
 						{
 							load1 = false;
@@ -656,14 +664,16 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2)
 				_bt_buildadd(index, state, bti);
 				if (should_free)
 					pfree((void *) bti);
-				bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free);
+				bti = (BTItem) tuplesort_getindextuple(btspool->sortstate,
+													   true, &should_free);
 			}
 			else
 			{
 				_bt_buildadd(index, state, bti2);
 				if (should_free2)
 					pfree((void *) bti2);
-				bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate, true, &should_free2);
+				bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate,
+														true, &should_free2);
 			}
 		}
 		_bt_freeskey(indexScanKey);
@@ -671,7 +681,8 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2)
 	else
 	{
 		/* merge is unnecessary */
-		while (bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free), bti != (BTItem) NULL)
+		while ((bti = (BTItem) tuplesort_getindextuple(btspool->sortstate,
+												true, &should_free)) != NULL)
 		{
 			/* When we see first tuple, create first index page */
 			if (state == NULL)
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 54cd7c8cd0..2c9fd741ff 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.55 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.56 2003/11/12 21:15:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,7 +19,6 @@
 #include "access/nbtree.h"
 #include "catalog/catalog.h"
 #include "executor/execdebug.h"
-#include "utils/lsyscache.h"
 
 
 /*
@@ -49,8 +48,8 @@ _bt_mkscankey(Relation rel, IndexTuple itup)
 		bool		null;
 
 		/*
-		 * We can use the cached support procs since no cross-type comparison
-		 * can be needed.
+		 * We can use the cached (default) support procs since no cross-type
+		 * comparison can be needed.
 		 */
 		procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
 		arg = index_getattr(itup, i + 1, itupdesc, &null);
@@ -58,9 +57,9 @@ _bt_mkscankey(Relation rel, IndexTuple itup)
 									   null ? SK_ISNULL : 0,
 									   (AttrNumber) (i + 1),
 									   InvalidStrategy,
+									   InvalidOid,
 									   procinfo,
-									   arg,
-									   itupdesc->attrs[i]->atttypid);
+									   arg);
 	}
 
 	return skey;
@@ -94,17 +93,17 @@ _bt_mkscankey_nodata(Relation rel)
 		FmgrInfo   *procinfo;
 
 		/*
-		 * We can use the cached support procs since no cross-type comparison
-		 * can be needed.
+		 * We can use the cached (default) support procs since no cross-type
+		 * comparison can be needed.
 		 */
 		procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
 		ScanKeyEntryInitializeWithInfo(&skey[i],
 									   SK_ISNULL,
 									   (AttrNumber) (i + 1),
 									   InvalidStrategy,
+									   InvalidOid,
 									   procinfo,
-									   (Datum) 0,
-									   itupdesc->attrs[i]->atttypid);
+									   (Datum) 0);
 	}
 
 	return skey;
@@ -161,105 +160,104 @@ _bt_formitem(IndexTuple itup)
 }
 
 /*----------
- *	_bt_orderkeys() -- Put keys in a sensible order for conjunctive quals.
+ *	_bt_preprocess_keys() -- Preprocess scan keys
  *
- * After this routine runs, the scan keys are ordered by index attribute
- * (all quals for attr 1, then all for attr 2, etc) and within each attr
- * the keys are ordered by constraint type: ">", ">=", "=", "<=", "<".
- * Furthermore, redundant keys are eliminated: we keep only the tightest
- * >/>= bound and the tightest </<= bound, and if there's an = key then
- * that's the only one returned.  (So, we return either a single = key,
- * or one or two boundary-condition keys for each attr.)
+ * The caller-supplied keys (in scan->keyData[]) are copied to
+ * so->keyData[] with possible transformation.  scan->numberOfKeys is
+ * the number of input keys, so->numberOfKeys gets the number of output
+ * keys (possibly less, never greater).
  *
- * As a byproduct of this work, we can detect contradictory quals such
- * as "x = 1 AND x > 2".  If we see that, we return so->quals_ok = FALSE,
- * indicating the scan need not be run at all since no tuples can match.
+ * The primary purpose of this routine is to discover how many scan keys
+ * must be satisfied to continue the scan.  It also attempts to eliminate
+ * redundant keys and detect contradictory keys.  At present, redundant and
+ * contradictory keys can only be detected for same-data-type comparisons,
+ * but that's the usual case so it seems worth doing.
+ *
+ * The output keys must be sorted by index attribute.  Presently we expect
+ * (but verify) that the input keys are already so sorted --- this is done
+ * by group_clauses_by_indexkey() in indxpath.c.  Some reordering of the keys
+ * within each attribute may be done as a byproduct of the processing here,
+ * but no other code depends on that.
  *
- * Another byproduct is to determine how many quals must be satisfied to
+ * Aside from preparing so->keyData[], this routine sets
+ * so->numberOfRequiredKeys to the number of quals that must be satisfied to
  * continue the scan.  _bt_checkkeys uses this.  For example, if the quals
  * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
  * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
  * But once we reach tuples like (1,4,z) we can stop scanning because no
  * later tuples could match.  This is reflected by setting
- * so->numberOfRequiredKeys to the number of leading keys that must be
- * matched to continue the scan.  numberOfRequiredKeys is equal to the
- * number of leading "=" keys plus the key(s) for the first non "="
- * attribute, which can be seen to be correct by considering the above
- * example.
+ * so->numberOfRequiredKeys to 2, the number of leading keys that must be
+ * matched to continue the scan.  In general, numberOfRequiredKeys is equal
+ * to the number of keys for leading attributes with "=" keys, plus the
+ * key(s) for the first non "=" attribute, which can be seen to be correct
+ * by considering the above example.
+ *
+ * If possible, redundant keys are eliminated: we keep only the tightest
+ * >/>= bound and the tightest </<= bound, and if there's an = key then
+ * that's the only one returned.  (So, we return either a single = key,
+ * or one or two boundary-condition keys for each attr.)  However, we can
+ * only detect redundant keys when the right-hand datatypes are all equal
+ * to the index datatype, because we do not know suitable operators for
+ * comparing right-hand values of two different datatypes.  (In theory
+ * we could handle comparison of a RHS of the index datatype with a RHS of
+ * another type, but that seems too much pain for too little gain.)  So,
+ * keys whose operator has a nondefault subtype (ie, its RHS is not of the
+ * index datatype) are ignored here, except for noting whether they impose
+ * an "=" condition or not.
+ *
+ * As a byproduct of this work, we can detect contradictory quals such
+ * as "x = 1 AND x > 2".  If we see that, we return so->quals_ok = FALSE,
+ * indicating the scan need not be run at all since no tuples can match.
+ * Again though, only keys with RHS datatype equal to the index datatype
+ * can be checked for contradictions.
  *
  * Furthermore, we detect the case where the index is unique and we have
  * equality quals for all columns.	In this case there can be at most one
  * (visible) matching tuple.  index_getnext uses this to avoid uselessly
  * continuing the scan after finding one match.
- *
- * The initial ordering of the keys is expected to be by attribute already
- * (see group_clauses_by_indexkey() in indxpath.c).  The task here is to
- * standardize the appearance of multiple keys for the same attribute.
  *----------
  */
 void
-_bt_orderkeys(IndexScanDesc scan)
+_bt_preprocess_keys(IndexScanDesc scan)
 {
 	Relation	relation = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
-	ScanKeyData xform[BTMaxStrategyNumber];
-	bool		init[BTMaxStrategyNumber];
-	int			numberOfKeys = so->numberOfKeys;
-	ScanKey		key;
+	int			numberOfKeys = scan->numberOfKeys;
+	int			new_numberOfKeys;
+	ScanKey		inkeys;
+	ScanKey		outkeys;
 	ScanKey		cur;
+	ScanKey		xform[BTMaxStrategyNumber];
+	bool		allEqualSoFar;
+	bool		hasOtherTypeEqual;
 	Datum		test;
 	int			i,
 				j;
 	AttrNumber	attno;
-	int			new_numberOfKeys;
-	bool		allEqualSoFar;
 
+	/* initialize result variables */
 	so->qual_ok = true;
+	so->numberOfKeys = 0;
 	so->numberOfRequiredKeys = 0;
 	scan->keys_are_unique = false;
 
 	if (numberOfKeys < 1)
 		return;					/* done if qual-less scan */
 
-	key = so->keyData;
-	cur = &key[0];
-	/* check input keys are correctly ordered */
+	inkeys = scan->keyData;
+	outkeys = so->keyData;
+	cur = &inkeys[0];
+	/* we check that input keys are correctly ordered */
 	if (cur->sk_attno != 1)
 		elog(ERROR, "key(s) for attribute 1 missed");
 
-#if 0
-	/* XXX verify that operator strategy info is correct */
-	/* XXX this is temporary for debugging; it's pretty expensive */
-	/* XXX can't do it during bootstrap, else will recurse infinitely */
-	{
-		extern bool criticalRelcachesBuilt;
-		static bool inRecursion = false;
-
-		if (criticalRelcachesBuilt && !inRecursion)
-		{
-			inRecursion = true;
-			for (i = 0; i < numberOfKeys; i++)
-			{
-				AttrNumber	attno = key[i].sk_attno;
-				Oid			opclass;
-				Oid			chk_oper;
-
-				opclass = relation->rd_index->indclass[attno-1];
-				chk_oper = get_opclass_member(opclass, key[i].sk_strategy);
-				Assert(key[i].sk_func.fn_oid == get_opcode(chk_oper));
-			}
-			inRecursion = false;
-		}
-	}
-#endif
-
 	/* We can short-circuit most of the work if there's just one key */
 	if (numberOfKeys == 1)
 	{
 		/*
 		 * We don't use indices for 'A is null' and 'A is not null'
 		 * currently and 'A < = > <> NULL' will always fail - so qual is
-		 * not Ok if comparison value is NULL.		- vadim 03/21/97
+		 * not OK if comparison value is NULL.		- vadim 03/21/97
 		 */
 		if (cur->sk_flags & SK_ISNULL)
 			so->qual_ok = false;
@@ -270,6 +268,8 @@ _bt_orderkeys(IndexScanDesc scan)
 			if (cur->sk_strategy == BTEqualStrategyNumber)
 				scan->keys_are_unique = true;
 		}
+		memcpy(outkeys, inkeys, sizeof(ScanKeyData));
+		so->numberOfKeys = 1;
 		so->numberOfRequiredKeys = 1;
 		return;
 	}
@@ -283,12 +283,15 @@ _bt_orderkeys(IndexScanDesc scan)
 	/*
 	 * Initialize for processing of keys for attr 1.
 	 *
-	 * xform[i] holds a copy of the current scan key of strategy type i+1, if
-	 * any; init[i] is TRUE if we have found such a key for this attr.
+	 * xform[i] points to the currently best scan key of strategy type i+1,
+	 * if any is found with a default operator subtype; it is NULL if we
+	 * haven't yet found such a key for this attr.  Scan keys of nondefault
+	 * subtypes are transferred to the output with no processing except for
+	 * noting if they are of "=" type.
 	 */
 	attno = 1;
-	MemSet(xform, 0, sizeof(xform));	/* not really necessary */
-	MemSet(init, 0, sizeof(init));
+	memset(xform, 0, sizeof(xform));
+	hasOtherTypeEqual = false;
 
 	/*
 	 * Loop iterates from 0 to numberOfKeys inclusive; we use the last
@@ -329,80 +332,78 @@ _bt_orderkeys(IndexScanDesc scan)
 			 * of key > 2 && key == 1 and so on we have to set qual_ok to
 			 * false before discarding the other keys.
 			 */
-			if (init[BTEqualStrategyNumber - 1])
+			if (xform[BTEqualStrategyNumber - 1])
 			{
-				ScanKeyData *eq,
-						   *chk;
+				ScanKey		eq = xform[BTEqualStrategyNumber - 1];
 
-				eq = &xform[BTEqualStrategyNumber - 1];
 				for (j = BTMaxStrategyNumber; --j >= 0;)
 				{
-					if (!init[j] ||
-						j == (BTEqualStrategyNumber - 1))
+					ScanKey		chk = xform[j];
+
+					if (!chk || j == (BTEqualStrategyNumber - 1))
 						continue;
-					chk = &xform[j];
 					test = FunctionCall2(&chk->sk_func,
 										 eq->sk_argument,
 										 chk->sk_argument);
 					if (!DatumGetBool(test))
+					{
 						so->qual_ok = false;
+						break;
+					}
 				}
-				init[BTLessStrategyNumber - 1] = false;
-				init[BTLessEqualStrategyNumber - 1] = false;
-				init[BTGreaterEqualStrategyNumber - 1] = false;
-				init[BTGreaterStrategyNumber - 1] = false;
+				xform[BTLessStrategyNumber - 1] = NULL;
+				xform[BTLessEqualStrategyNumber - 1] = NULL;
+				xform[BTGreaterEqualStrategyNumber - 1] = NULL;
+				xform[BTGreaterStrategyNumber - 1] = NULL;
 			}
 			else
 			{
 				/*
-				 * No "=" for this key, so we're done with required keys
+				 * If no "=" for this key, we're done with required keys
 				 */
-				allEqualSoFar = false;
+				if (! hasOtherTypeEqual)
+					allEqualSoFar = false;
 			}
 
 			/* keep only one of <, <= */
-			if (init[BTLessStrategyNumber - 1]
-				&& init[BTLessEqualStrategyNumber - 1])
+			if (xform[BTLessStrategyNumber - 1]
+				&& xform[BTLessEqualStrategyNumber - 1])
 			{
-				ScanKeyData *lt = &xform[BTLessStrategyNumber - 1];
-				ScanKeyData *le = &xform[BTLessEqualStrategyNumber - 1];
+				ScanKey lt = xform[BTLessStrategyNumber - 1];
+				ScanKey le = xform[BTLessEqualStrategyNumber - 1];
 
 				test = FunctionCall2(&le->sk_func,
 									 lt->sk_argument,
 									 le->sk_argument);
 				if (DatumGetBool(test))
-					init[BTLessEqualStrategyNumber - 1] = false;
+					xform[BTLessEqualStrategyNumber - 1] = NULL;
 				else
-					init[BTLessStrategyNumber - 1] = false;
+					xform[BTLessStrategyNumber - 1] = NULL;
 			}
 
 			/* keep only one of >, >= */
-			if (init[BTGreaterStrategyNumber - 1]
-				&& init[BTGreaterEqualStrategyNumber - 1])
+			if (xform[BTGreaterStrategyNumber - 1]
+				&& xform[BTGreaterEqualStrategyNumber - 1])
 			{
-				ScanKeyData *gt = &xform[BTGreaterStrategyNumber - 1];
-				ScanKeyData *ge = &xform[BTGreaterEqualStrategyNumber - 1];
+				ScanKey gt = xform[BTGreaterStrategyNumber - 1];
+				ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1];
 
 				test = FunctionCall2(&ge->sk_func,
 									 gt->sk_argument,
 									 ge->sk_argument);
 				if (DatumGetBool(test))
-					init[BTGreaterEqualStrategyNumber - 1] = false;
+					xform[BTGreaterEqualStrategyNumber - 1] = NULL;
 				else
-					init[BTGreaterStrategyNumber - 1] = false;
+					xform[BTGreaterStrategyNumber - 1] = NULL;
 			}
 
 			/*
-			 * Emit the cleaned-up keys back into the key[] array in the
-			 * correct order.  Note we are overwriting our input here!
-			 * It's OK because (a) xform[] is a physical copy of the keys
-			 * we want, (b) we cannot emit more keys than we input, so we
-			 * won't overwrite as-yet-unprocessed keys.
+			 * Emit the cleaned-up keys into the outkeys[] array.
 			 */
 			for (j = BTMaxStrategyNumber; --j >= 0;)
 			{
-				if (init[j])
-					memcpy(&key[new_numberOfKeys++], &xform[j],
+				if (xform[j])
+					memcpy(&outkeys[new_numberOfKeys++], xform[j],
 						   sizeof(ScanKeyData));
 			}
 
@@ -421,31 +422,43 @@ _bt_orderkeys(IndexScanDesc scan)
 
 			/* Re-initialize for new attno */
 			attno = cur->sk_attno;
-			MemSet(xform, 0, sizeof(xform));	/* not really necessary */
-			MemSet(init, 0, sizeof(init));
+			memset(xform, 0, sizeof(xform));
+			hasOtherTypeEqual = false;
 		}
 
-		/* figure out which strategy this key's operator corresponds to */
+		/* check strategy this key's operator corresponds to */
 		j = cur->sk_strategy - 1;
 
+		/* if wrong RHS data type, punt */
+		if (cur->sk_subtype != InvalidOid)
+		{
+			memcpy(&outkeys[new_numberOfKeys++], cur,
+				   sizeof(ScanKeyData));
+			if (j == (BTEqualStrategyNumber - 1))
+				hasOtherTypeEqual = true;
+			continue;
+		}
+
 		/* have we seen one of these before? */
-		if (init[j])
+		if (xform[j])
 		{
-			/* yup, keep the more restrictive value */
+			/* yup, keep the more restrictive key */
 			test = FunctionCall2(&cur->sk_func,
 								 cur->sk_argument,
-								 xform[j].sk_argument);
+								 xform[j]->sk_argument);
 			if (DatumGetBool(test))
-				xform[j].sk_argument = cur->sk_argument;
+				xform[j] = cur;
 			else if (j == (BTEqualStrategyNumber - 1))
+			{
+				/* key == a && key == b, but a != b */
 				so->qual_ok = false;
-			/* key == a && key == b, but a != b */
+				return;
+			}
 		}
 		else
 		{
 			/* nope, so remember this scankey */
-			memcpy(&xform[j], cur, sizeof(ScanKeyData));
-			init[j] = true;
+			xform[j] = cur;
 		}
 	}
 
@@ -465,8 +478,8 @@ _bt_orderkeys(IndexScanDesc scan)
  *
  * If the tuple fails to pass the qual, we also determine whether there's
  * any need to continue the scan beyond this tuple, and set *continuescan
- * accordingly.  See comments for _bt_orderkeys(), above, about how this is
- * done.
+ * accordingly.  See comments for _bt_preprocess_keys(), above, about how
+ * this is done.
  */
 bool
 _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
@@ -474,7 +487,7 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
 	int			keysz = so->numberOfKeys;
-	int			keysok;
+	int			ikey;
 	TupleDesc	tupdesc;
 	ScanKey		key;
 
@@ -484,13 +497,11 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 	if (keysz == 0)
 		return true;
 
-	tupdesc = RelationGetDescr(scan->indexRelation);
-	key = so->keyData;
-	keysok = 0;
-
 	IncrIndexProcessed();
 
-	while (keysz > 0)
+	tupdesc = RelationGetDescr(scan->indexRelation);
+
+	for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
 	{
 		Datum		datum;
 		bool		isNull;
@@ -504,7 +515,7 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 		/* btree doesn't support 'A is null' clauses, yet */
 		if (key->sk_flags & SK_ISNULL)
 		{
-			/* we shouldn't get here, really; see _bt_orderkeys() */
+			/* we shouldn't get here, really; see _bt_preprocess_keys() */
 			*continuescan = false;
 			return false;
 		}
@@ -518,7 +529,7 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 			 * one of the "must match" subset.	On a backward scan,
 			 * however, we should keep going.
 			 */
-			if (keysok < so->numberOfRequiredKeys &&
+			if (ikey < so->numberOfRequiredKeys &&
 				ScanDirectionIsForward(dir))
 				*continuescan = false;
 
@@ -534,16 +545,50 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 		{
 			/*
 			 * Tuple fails this qual.  If it's a required qual, then we
-			 * can conclude no further tuples will pass, either.
+			 * may be able to conclude no further tuples will pass, either.
+			 * We have to look at the scan direction and the qual type.
+			 *
+			 * Note: the only case in which we would keep going after failing
+			 * a required qual is if there are partially-redundant quals that
+			 * _bt_preprocess_keys() was unable to eliminate.  For example,
+			 * given "x > 4 AND x > 10" where both are cross-type comparisons
+			 * and so not removable, we might start the scan at the x = 4
+			 * boundary point.  The "x > 10" condition will fail until we
+			 * pass x = 10, but we must not stop the scan on its account.
+			 *
+			 * Note: because we stop the scan as soon as any required equality
+			 * qual fails, it is critical that equality quals be used for the
+			 * initial positioning in _bt_first() when they are available.
+			 * See comments in _bt_first().
+			 */
+			if (ikey < so->numberOfRequiredKeys)
+			{
+				switch (key->sk_strategy)
+				{
+					case BTLessStrategyNumber:
+					case BTLessEqualStrategyNumber:
+						if (ScanDirectionIsForward(dir))
+							*continuescan = false;
+						break;
+					case BTEqualStrategyNumber:
+						*continuescan = false;
+						break;
+					case BTGreaterEqualStrategyNumber:
+					case BTGreaterStrategyNumber:
+						if (ScanDirectionIsBackward(dir))
+							*continuescan = false;
+						break;
+					default:
+						elog(ERROR, "unrecognized StrategyNumber: %d",
+							 key->sk_strategy);
+				}
+			}
+
+			/*
+			 * In any case, this indextuple doesn't match the qual.
 			 */
-			if (keysok < so->numberOfRequiredKeys)
-				*continuescan = false;
 			return false;
 		}
-
-		keysok++;
-		key++;
-		keysz--;
 	}
 
 	/* If we get here, the tuple passes all quals. */
diff --git a/src/backend/access/rtree/rtproc.c b/src/backend/access/rtree/rtproc.c
index 790f6bc7b6..985993fb68 100644
--- a/src/backend/access/rtree/rtproc.c
+++ b/src/backend/access/rtree/rtproc.c
@@ -15,7 +15,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtproc.c,v 1.37 2003/08/04 02:39:57 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtproc.c,v 1.38 2003/11/12 21:15:48 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -82,20 +82,6 @@ rt_box_size(PG_FUNCTION_ARGS)
 	PG_RETURN_VOID();
 }
 
-/*
- *	rt_bigbox_size() -- Compute a size for big boxes.
- *
- *		In an earlier release of the system, this routine did something
- *		different from rt_box_size.  We now use floats, rather than ints,
- *		as the return type for the size routine, so we no longer need to
- *		have a special return type for big boxes.
- */
-Datum
-rt_bigbox_size(PG_FUNCTION_ARGS)
-{
-	return rt_box_size(fcinfo);
-}
-
 Datum
 rt_poly_union(PG_FUNCTION_ARGS)
 {
diff --git a/src/backend/access/rtree/rtscan.c b/src/backend/access/rtree/rtscan.c
index 263fff4bf2..5026bd78a7 100644
--- a/src/backend/access/rtree/rtscan.c
+++ b/src/backend/access/rtree/rtscan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtscan.c,v 1.48 2003/11/09 21:30:35 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtscan.c,v 1.49 2003/11/12 21:15:48 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -123,15 +123,17 @@ rtrescan(PG_FUNCTION_ARGS)
 
 			opclass = s->indexRelation->rd_index->indclass[attno-1];
 			int_strategy = RTMapToInternalOperator(s->keyData[i].sk_strategy);
-			int_oper = get_opclass_member(opclass, int_strategy);
+			int_oper = get_opclass_member(opclass,
+										  s->keyData[i].sk_subtype,
+										  int_strategy);
 			int_proc = get_opcode(int_oper);
 			ScanKeyEntryInitialize(&(p->s_internalKey[i]),
 								   s->keyData[i].sk_flags,
 								   attno,
 								   int_strategy,
+								   s->keyData[i].sk_subtype,
 								   int_proc,
-								   s->keyData[i].sk_argument,
-								   s->keyData[i].sk_argtype);
+								   s->keyData[i].sk_argument);
 		}
 	}