Improve GiST range-contained-by searches by adding a flag for empty ranges.

In the original implementation, a range-contained-by search had to scan
the entire index because an empty range could be lurking anywhere.
Improve that by adding a flag to upper GiST entries that says whether the
represented subtree contains any empty ranges.

Also, make a simple mod to the penalty function to discourage empty ranges
from getting pushed into subtrees without any.  This needs more work, and
the picksplit function should be taught about it too, but that code can be
improved without causing an on-disk compatibility break; so we'll leave it
for another day.

Since we're breaking on-disk compatibility of range values anyway, I took
the opportunity to reorganize the range flags bits; the unused
RANGE_xB_NULL bits are now adjacent, which might open the door for using
them in some other way later.

In passing, remove the GiST range opclass entry for <>, which doesn't seem
like it can really be indexed usefully.

Alexander Korotkov, with some editorializing by Tom

3 files changed, 14 insertions, 10 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 088c3076607..5a73726ba31 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	201111241
+#define CATALOG_VERSION_NO	201111271
 
 #endif
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index a95cf5fa50d..1e8c9a289f9 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -736,6 +736,5 @@ DATA(insert (	3919   3831 3831 7 s	3890 783 0 ));
 DATA(insert (	3919   3831 3831 8 s	3892 783 0 ));
 DATA(insert (	3919   3831 2283 16 s	3889 783 0 ));
 DATA(insert (	3919   3831 3831 18 s	3882 783 0 ));
-DATA(insert (	3919   3831 3831 19 s	3883 783 0 ));
 
 #endif   /* PG_AMOP_H */
diff --git a/src/include/utils/rangetypes.h b/src/include/utils/rangetypes.h
index c9a6834e6db..307476d9762 100644
--- a/src/include/utils/rangetypes.h
+++ b/src/include/utils/rangetypes.h
@@ -33,13 +33,15 @@ typedef struct
 #define RangeTypeGetOid(r)  ((r)->rangetypid)
 
 /* A range's flags byte contains these bits: */
-#define RANGE_EMPTY		0x01	/* range is empty */
-#define RANGE_LB_INC	0x02	/* lower bound is inclusive (vs exclusive) */
-#define RANGE_LB_NULL	0x04	/* lower bound is null (NOT CURRENTLY USED) */
-#define RANGE_LB_INF	0x08	/* lower bound is +/- infinity */
-#define RANGE_UB_INC	0x10	/* upper bound is inclusive (vs exclusive) */
-#define RANGE_UB_NULL	0x20	/* upper bound is null (NOT CURRENTLY USED) */
-#define RANGE_UB_INF	0x40	/* upper bound is +/- infinity */
+#define RANGE_EMPTY			0x01	/* range is empty */
+#define RANGE_LB_INC		0x02	/* lower bound is inclusive */
+#define RANGE_UB_INC		0x04	/* upper bound is inclusive */
+#define RANGE_LB_INF		0x08	/* lower bound is -infinity */
+#define RANGE_UB_INF		0x10	/* upper bound is +infinity */
+#define RANGE_LB_NULL		0x20	/* lower bound is null (NOT USED) */
+#define RANGE_UB_NULL		0x40	/* upper bound is null (NOT USED) */
+#define RANGE_CONTAIN_EMPTY	0x80	/* marks a GiST internal-page entry whose
+									 * subtree contains some empty ranges */
 
 #define RANGE_HAS_LBOUND(flags) (!((flags) & (RANGE_EMPTY | \
 											  RANGE_LB_NULL | \
@@ -49,7 +51,9 @@ typedef struct
 											  RANGE_UB_NULL | \
 											  RANGE_UB_INF)))
 
-#define RangeIsEmpty(r)  (range_get_flags(r) & RANGE_EMPTY)
+#define RangeIsEmpty(r)  ((range_get_flags(r) & RANGE_EMPTY) != 0)
+#define RangeIsOrContainsEmpty(r)  \
+	((range_get_flags(r) & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY)) != 0)
 
 
 /* Internal representation of either bound of a range (not what's on disk) */
@@ -152,6 +156,7 @@ extern void range_deserialize(TypeCacheEntry *typcache, RangeType *range,
 							  RangeBound *lower, RangeBound *upper,
 							  bool *empty);
 extern char range_get_flags(RangeType *range);
+extern void range_set_contain_empty(RangeType *range);
 extern RangeType *make_range(TypeCacheEntry *typcache, RangeBound *lower,
 						RangeBound *upper, bool empty);
 extern int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1,