Fix rtree and contrib/rtree_gist search behavior for the 1-D box and

polygon operators (<<, &<, >>, &>).  Per ideas originally put forward
by andrew@supernews and later rediscovered by moi.  This patch just
fixes the existing opclasses, and does not add any new behavior as I
proposed earlier; that can be sorted out later.  In principle this
could be back-patched, since it changes only search behavior and not
system catalog entries nor rtree index contents.  I'm not currently
planning to do that, though, since I think it could use more testing.

5 files changed, 63 insertions, 26 deletions

diff --git a/src/backend/access/common/indexvalid.c b/src/backend/access/common/indexvalid.c
index 2dcea775274..29ee54c3bfe 100644
--- a/src/backend/access/common/indexvalid.c
+++ b/src/backend/access/common/indexvalid.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/common/indexvalid.c,v 1.33 2004/12/31 21:59:07 pgsql Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/common/indexvalid.c,v 1.34 2005/06/24 00:18:52 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -59,8 +59,16 @@ index_keytest(IndexTuple tuple,
 
 		test = FunctionCall2(&key->sk_func, datum, key->sk_argument);
 
-		if (!DatumGetBool(test))
-			return false;
+		if (key->sk_flags & SK_NEGATE)
+		{
+			if (DatumGetBool(test))
+				return false;
+		}
+		else
+		{
+			if (!DatumGetBool(test))
+				return false;
+		}
 
 		key++;
 		scanKeySize--;
diff --git a/src/backend/access/rtree/rtscan.c b/src/backend/access/rtree/rtscan.c
index f6656a23b9e..3f9f81befb0 100644
--- a/src/backend/access/rtree/rtscan.c
+++ b/src/backend/access/rtree/rtscan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/rtree/rtscan.c,v 1.58 2005/03/29 00:16:53 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/rtree/rtscan.c,v 1.59 2005/06/24 00:18:52 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -125,27 +125,36 @@ rtrescan(PG_FUNCTION_ARGS)
 		 * Scans on internal pages use different operators than they do on
 		 * leaf pages.	For example, if the user wants all boxes that
 		 * exactly match (x1,y1,x2,y2), then on internal pages we need to
-		 * find all boxes that contain (x1,y1,x2,y2).
+		 * find all boxes that contain (x1,y1,x2,y2).  rtstrat.c knows
+		 * how to pick the opclass member to use for internal pages.
+		 * In some cases we need to negate the result of the opclass member.
 		 */
 		for (i = 0; i < s->numberOfKeys; i++)
 		{
 			AttrNumber	attno = s->keyData[i].sk_attno;
 			Oid			opclass;
+			Oid			subtype;
+			StrategyNumber orig_strategy;
 			StrategyNumber int_strategy;
 			Oid			int_oper;
 			RegProcedure int_proc;
+			int			int_flags;
 
 			opclass = s->indexRelation->rd_indclass->values[attno - 1];
-			int_strategy = RTMapToInternalOperator(s->keyData[i].sk_strategy);
-			int_oper = get_opclass_member(opclass,
-										  s->keyData[i].sk_subtype,
-										  int_strategy);
+			subtype = s->keyData[i].sk_subtype;
+			orig_strategy = s->keyData[i].sk_strategy;
+			int_strategy = RTMapToInternalOperator(orig_strategy);
+			int_oper = get_opclass_member(opclass, subtype, int_strategy);
+			Assert(OidIsValid(int_oper));
 			int_proc = get_opcode(int_oper);
+			int_flags = s->keyData[i].sk_flags;
+			if (RTMapToInternalNegate(orig_strategy))
+				int_flags |= SK_NEGATE;
 			ScanKeyEntryInitialize(&(p->s_internalKey[i]),
-								   s->keyData[i].sk_flags,
+								   int_flags,
 								   attno,
 								   int_strategy,
-								   s->keyData[i].sk_subtype,
+								   subtype,
 								   int_proc,
 								   s->keyData[i].sk_argument);
 		}
diff --git a/src/backend/access/rtree/rtstrat.c b/src/backend/access/rtree/rtstrat.c
index d5f59fed6e6..c7104c9520c 100644
--- a/src/backend/access/rtree/rtstrat.c
+++ b/src/backend/access/rtree/rtstrat.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/rtree/rtstrat.c,v 1.25 2004/12/31 21:59:26 pgsql Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/rtree/rtstrat.c,v 1.26 2005/06/24 00:18:52 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -28,20 +28,31 @@
  *	the leaf we search for equality.
  *
  *	This array maps leaf search operators to the internal search operators.
- *	We assume the normal ordering on operators:
- *
- *		left, left-or-overlap, overlap, right-or-overlap, right, same,
- *		contains, contained-by
  */
 static const StrategyNumber RTOperMap[RTNStrategies] = {
-	RTOverLeftStrategyNumber,
-	RTOverLeftStrategyNumber,
-	RTOverlapStrategyNumber,
-	RTOverRightStrategyNumber,
-	RTOverRightStrategyNumber,
-	RTContainsStrategyNumber,
-	RTContainsStrategyNumber,
-	RTOverlapStrategyNumber
+	RTOverRightStrategyNumber,	/* left */
+	RTRightStrategyNumber,		/* overleft */
+	RTOverlapStrategyNumber,	/* overlap */
+	RTLeftStrategyNumber,		/* overright */
+	RTOverLeftStrategyNumber,	/* right */
+	RTContainsStrategyNumber,	/* same */
+	RTContainsStrategyNumber,	/* contains */
+	RTOverlapStrategyNumber		/* contained-by */
+};
+
+/*
+ * We may need to negate the result of the selected operator.  (This could
+ * be avoided by expanding the set of operators required for an opclass.)
+ */
+static const bool RTNegateMap[RTNStrategies] = {
+	true,						/* left */
+	true,						/* overleft */
+	false,						/* overlap */
+	true,						/* overright */
+	true,						/* right */
+	false,						/* same */
+	false,						/* contains */
+	false						/* contained-by */
 };
 
 
@@ -51,3 +62,10 @@ RTMapToInternalOperator(StrategyNumber strat)
 	Assert(strat > 0 && strat <= RTNStrategies);
 	return RTOperMap[strat - 1];
 }
+
+bool
+RTMapToInternalNegate(StrategyNumber strat)
+{
+	Assert(strat > 0 && strat <= RTNStrategies);
+	return RTNegateMap[strat - 1];
+}
diff --git a/src/include/access/rtree.h b/src/include/access/rtree.h
index 14a13f4b3a4..744f116fe37 100644
--- a/src/include/access/rtree.h
+++ b/src/include/access/rtree.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/rtree.h,v 1.39 2005/06/06 17:01:24 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/access/rtree.h,v 1.40 2005/06/24 00:18:52 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -136,5 +136,6 @@ extern void ReleaseResources_rtree(void);
 
 /* rtstrat.c */
 extern StrategyNumber RTMapToInternalOperator(StrategyNumber strat);
+extern bool RTMapToInternalNegate(StrategyNumber strat);
 
 #endif   /* RTREE_H */
diff --git a/src/include/access/skey.h b/src/include/access/skey.h
index a160f7b39eb..61a8e81a835 100644
--- a/src/include/access/skey.h
+++ b/src/include/access/skey.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/skey.h,v 1.28 2004/12/31 22:03:21 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/access/skey.h,v 1.29 2005/06/24 00:18:52 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -72,6 +72,7 @@ typedef ScanKeyData *ScanKey;
 /* ScanKeyData sk_flags */
 #define SK_ISNULL		0x0001	/* sk_argument is NULL */
 #define SK_UNARY		0x0002	/* unary operator (currently unsupported) */
+#define SK_NEGATE		0x0004	/* must negate the function result */
 
 
 /*