range_spgist_quad-0.6-heikki.patch

diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile
index c5b0a75..a692086 100644
--- a/src/backend/utils/adt/Makefile
+++ b/src/backend/utils/adt/Makefile
@@ -30,7 +30,7 @@ OBJS = acl.o arrayfuncs.o array_selfuncs.o array_typanalyze.o \
 	tsginidx.o tsgistidx.o tsquery.o tsquery_cleanup.o tsquery_gist.o \
 	tsquery_op.o tsquery_rewrite.o tsquery_util.o tsrank.o \
 	tsvector.o tsvector_op.o tsvector_parser.o \
-	txid.o uuid.o windowfuncs.o xml.o
+	txid.o uuid.o windowfuncs.o xml.o rangetypes_spgist.o
 
 like.o: like.c like_match.c
 
diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index c2f0b25..bab9861 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -709,6 +709,49 @@ range_after(PG_FUNCTION_ARGS)
 	PG_RETURN_BOOL(range_after_internal(typcache, r1, r2));
 }
 
+/*
+ * Check if two bounds are "adjacent". Bounds are adjacent when each subtype
+ * value belongs to strictly one of the bounds: there are no values which
+ * satisfy both bounds, and there are no values between the bounds.
+ *
+ * For discrete ranges, we rely on the canonicalization function to normalize
+ * A..B to empty if it contains no elements of the subtype.  (If there is no
+ * canonicalization function, it's impossible for such a range to normalize to
+ * empty, so we needn't bother to try.)
+ *
+ * If A == B, the ranges are adjacent only if these bounds have different
+ * inclusive flags (i.e., exactly one of the ranges includes the common
+ * boundary point).
+ *
+ * If A > B, the ranges cannot be adjacent in this order.
+ */
+bool
+bounds_adjacent(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper)
+{
+	int cmp;
+
+	cmp = range_cmp_bound_values(typcache, upper, lower);
+	if (cmp < 0)
+	{
+		RangeType *r;
+		/* in a continuous subtype, there are assumed to be points between */
+		if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
+			return false;
+		/* flip the inclusion flags */
+		upper->inclusive = !upper->inclusive;
+		lower->inclusive = !lower->inclusive;
+		/* change upper/lower labels to avoid Assert failures */
+		upper->lower = true;
+		lower->lower = false;
+		r = make_range(typcache, upper, lower, false);
+		PG_RETURN_BOOL(RangeIsEmpty(r));
+	}
+	else if (cmp == 0)
+		PG_RETURN_BOOL(upper->inclusive != lower->inclusive);
+	else
+		PG_RETURN_BOOL(false);
+}
+
 /* adjacent to (but not overlapping)? (internal version) */
 bool
 range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
@@ -719,8 +762,6 @@ range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 				upper2;
 	bool		empty1,
 				empty2;
-	RangeType  *r3;
-	int			cmp;
 
 	/* Different types should be prevented by ANYRANGE matching rules */
 	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
@@ -734,62 +775,11 @@ range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 		return false;
 
 	/*
-	 * Given two ranges A..B and C..D, where B < C, the ranges are adjacent if
-	 * and only if the range B..C is empty, where inclusivity of these two
-	 * bounds is inverted compared to the original bounds.	For discrete
-	 * ranges, we have to rely on the canonicalization function to normalize
-	 * B..C to empty if it contains no elements of the subtype.  (If there is
-	 * no canonicalization function, it's impossible for such a range to
-	 * normalize to empty, so we needn't bother to try.)
-	 *
-	 * If B == C, the ranges are adjacent only if these bounds have different
-	 * inclusive flags (i.e., exactly one of the ranges includes the common
-	 * boundary point).
-	 *
-	 * And if B > C then the ranges cannot be adjacent in this order, but we
-	 * must consider the other order (i.e., check D <= A).
+	 * Given two ranges A..B and C..D, the ranges are adjacent if and only if
+	 * the bounds B and C are adjacent, or D and A are adjacent.
 	 */
-	cmp = range_cmp_bound_values(typcache, &upper1, &lower2);
-	if (cmp < 0)
-	{
-		/* in a continuous subtype, there are assumed to be points between */
-		if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
-			return (false);
-		/* flip the inclusion flags */
-		upper1.inclusive = !upper1.inclusive;
-		lower2.inclusive = !lower2.inclusive;
-		/* change upper/lower labels to avoid Assert failures */
-		upper1.lower = true;
-		lower2.lower = false;
-		r3 = make_range(typcache, &upper1, &lower2, false);
-		return RangeIsEmpty(r3);
-	}
-	if (cmp == 0)
-	{
-		return (upper1.inclusive != lower2.inclusive);
-	}
-
-	cmp = range_cmp_bound_values(typcache, &upper2, &lower1);
-	if (cmp < 0)
-	{
-		/* in a continuous subtype, there are assumed to be points between */
-		if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
-			return (false);
-		/* flip the inclusion flags */
-		upper2.inclusive = !upper2.inclusive;
-		lower1.inclusive = !lower1.inclusive;
-		/* change upper/lower labels to avoid Assert failures */
-		upper2.lower = true;
-		lower1.lower = false;
-		r3 = make_range(typcache, &upper2, &lower1, false);
-		return RangeIsEmpty(r3);
-	}
-	if (cmp == 0)
-	{
-		return (upper2.inclusive != lower1.inclusive);
-	}
-
-	return false;
+	return (bounds_adjacent(typcache, &lower2, &upper1) ||
+			bounds_adjacent(typcache, &lower1, &upper2));
 }
 
 /* adjacent to (but not overlapping)? */
diff --git a/src/backend/utils/adt/rangetypes_gist.c b/src/backend/utils/adt/rangetypes_gist.c
index 21f0eba..190b506 100644
--- a/src/backend/utils/adt/rangetypes_gist.c
+++ b/src/backend/utils/adt/rangetypes_gist.c
@@ -20,20 +20,6 @@
 #include "utils/datum.h"
 #include "utils/rangetypes.h"
 
-
-/* Operator strategy numbers used in the GiST range opclass */
-/* Numbers are chosen to match up operator names with existing usages */
-#define RANGESTRAT_BEFORE				1
-#define RANGESTRAT_OVERLEFT				2
-#define RANGESTRAT_OVERLAPS				3
-#define RANGESTRAT_OVERRIGHT			4
-#define RANGESTRAT_AFTER				5
-#define RANGESTRAT_ADJACENT				6
-#define RANGESTRAT_CONTAINS				7
-#define RANGESTRAT_CONTAINED_BY			8
-#define RANGESTRAT_CONTAINS_ELEM		16
-#define RANGESTRAT_EQ					18
-
 /*
  * Range class properties used to segregate different classes of ranges in
  * GiST.  Each unique combination of properties is a class.  CLS_EMPTY cannot
diff --git a/src/backend/utils/adt/rangetypes_spgist.c b/src/backend/utils/adt/rangetypes_spgist.c
new file mode 100644
index 0000000..a30c231
--- /dev/null
+++ b/src/backend/utils/adt/rangetypes_spgist.c
@@ -0,0 +1,827 @@
+/*-------------------------------------------------------------------------
+ *
+ * rangetypes_spgist.c
+ *	  implementation of quad tree over ranges mapped to 2d-points for SP-GiST.
+ *
+ * Ranges are mapped to 2d-points as following: Lower bound of range is mapped
+ * to the horizontal axis. Upper bound is mapped to the vertical axis. This
+ * implementation of quad-tree uses only comparison function for range element
+ * datatype, therefore it works for any range type.
+ *
+ * Quad tree is a data structure like a binary tree, but it is adopted to
+ * 2d data. Each node of quad-tree contains a point (centroid) which divides
+ * the 2d-space into 4 quadrants, which are associated with children nodes.
+ *
+ * SP-GiST implementation of quad-tree have some speciality. SP-GiST
+ * accumulates leaf index tuples in pages until it overflows. Then it calls
+ * picksplit function of operator class for them. Picksplit function of this
+ * Quad-tree implementation uses medians along both axes as the centroid.
+ *
+ * Another speciality of this quad-tree implementation is handling of empty
+ * ranges. Idea is to have only one path in tree for empty ranges. If all the
+ * ranges at the moment of first picksplit are empty, we put all empty ranges
+ * into one node and create another node for further non-empty nodes. All
+ * further empty nodes will be put into same path as initial ones. If not all
+ * ranges in first picksplit are empty then we create special node number 5 for
+ * empty nodes. All further empty nodes will be put into node number 5 from
+ * root.
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *			src/backend/utils/adt/rangetypes_spgist.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "access/spgist.h"
+#include "access/skey.h"
+#include "catalog/pg_type.h"
+#include "utils/builtins.h"
+#include "utils/datum.h"
+#include "utils/rangetypes.h"
+
+Datum spg_range_quad_config(PG_FUNCTION_ARGS);
+Datum spg_range_quad_choose(PG_FUNCTION_ARGS);
+Datum spg_range_quad_picksplit(PG_FUNCTION_ARGS);
+Datum spg_range_quad_inner_consistent(PG_FUNCTION_ARGS);
+Datum spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS);
+
+static int16 getQuadrant(TypeCacheEntry *typcache, RangeType *centroid,
+			RangeType *tst);
+static int bound_cmp(const void *a, const void *b, void *arg);
+
+/*
+ * SP-GiST 'config' interface function.
+ */
+Datum
+spg_range_quad_config(PG_FUNCTION_ARGS)
+{
+	/* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
+	spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
+
+	cfg->prefixType = ANYRANGEOID;
+	cfg->labelType = VOIDOID;	/* we don't need node labels */
+	cfg->canReturnData = true;
+	cfg->longValuesOK = false;
+	PG_RETURN_VOID();
+}
+
+/*----------
+ * Determine which quadrant a 2d-mapped range falls into, relative to the
+ * centroid.
+ *
+ * Lower bound of range is mapped to the horizontal axis and upper bound to
+ * the vertical axis. Quadrants are numbered like this:
+ *
+ *	 4	|  1
+ *	----+-----
+ *	 3	|  2
+ *
+ * Ranges on one of the axes are taken to lie in the quadrant with higher value
+ * along perpendicular axis. Range equal to centroid is taken to lie in
+ * quadrant 1. Empty ranges are taken to lie in quadrant 5.
+ *----------
+ */
+static int16
+getQuadrant(TypeCacheEntry *typcache, RangeType *centroid, RangeType *tst)
+{
+	RangeBound	centroidLower,
+				centroidUpper;
+	bool		centroidEmpty;
+	RangeBound	lower,
+				upper;
+	bool		empty;
+
+	range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
+					  &centroidEmpty);
+	range_deserialize(typcache, tst, &lower, &upper, &empty);
+
+	if (empty)
+		return 5;
+
+	if (range_cmp_bounds(typcache, &lower, &centroidLower) >= 0)
+	{
+		if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
+			return 1;
+		else
+			return 2;
+	}
+	else
+	{
+		if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
+			return 4;
+		else
+			return 3;
+	}
+}
+
+/*
+ * Choose SP-GiST function: choose path for addition of new range.
+ */
+Datum
+spg_range_quad_choose(PG_FUNCTION_ARGS)
+{
+	spgChooseIn	   *in = (spgChooseIn *) PG_GETARG_POINTER(0);
+	spgChooseOut   *out = (spgChooseOut *) PG_GETARG_POINTER(1);
+	RangeType	   *inRange = DatumGetRangeType(in->datum), *centroid;
+	int16			quadrant;
+	TypeCacheEntry *typcache;
+
+	if (in->allTheSame)
+	{
+		out->resultType = spgMatchNode;
+		/* nodeN will be set by core */
+		out->result.matchNode.levelAdd = 0;
+		out->result.matchNode.restDatum = RangeTypeGetDatum(inRange);
+		PG_RETURN_VOID();
+	}
+
+	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(inRange));
+
+	/*
+	 * Absence of prefix datum divides ranges by empty sign. All empty ranges
+	 * are taken into node 0, all non-empty ranges are taken into node 1.
+	 */
+	if (!in->hasPrefix)
+	{
+		out->resultType = spgMatchNode;
+		if (RangeIsEmpty(inRange))
+			out->result.matchNode.nodeN = 0;
+		else
+			out->result.matchNode.nodeN = 1;
+		out->result.matchNode.levelAdd = 1;
+		out->result.matchNode.restDatum = RangeTypeGetDatum(inRange);
+		PG_RETURN_VOID();
+	}
+
+	centroid = DatumGetRangeType(in->prefixDatum);
+	quadrant = getQuadrant(typcache, centroid, inRange);
+
+	Assert(quadrant <= in->nNodes);
+
+	/* Select node matching to quadrant number */
+	out->resultType = spgMatchNode;
+	out->result.matchNode.nodeN = quadrant - 1;
+	out->result.matchNode.levelAdd = 1;
+	out->result.matchNode.restDatum = RangeTypeGetDatum(inRange);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * Bound comparison for sorting.
+ */
+static int
+bound_cmp(const void *a, const void *b, void *arg)
+{
+	RangeBound *ba = (RangeBound *) a;
+	RangeBound *bb = (RangeBound *) b;
+	TypeCacheEntry *typcache = (TypeCacheEntry *)arg;
+
+	return range_cmp_bounds(typcache, ba, bb);
+}
+
+/*
+ * Picksplit SP-GiST function: split ranges into nodes. Select "centroid"
+ * range and distribute ranges according to quadrants.
+ */
+Datum
+spg_range_quad_picksplit(PG_FUNCTION_ARGS)
+{
+	spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
+	spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
+	int			i;
+	int			j;
+	int			nonEmptyCount;
+	RangeType  *centroid;
+	bool		empty;
+	TypeCacheEntry *typcache;
+
+	/* Use the median values of lower and upper bounds as the centroid range */
+	RangeBound	   *lowerBounds,
+				   *upperBounds;
+
+	typcache = range_get_typcache(fcinfo,
+							RangeTypeGetOid(DatumGetRangeType(in->datums[0])));
+
+	/* Allocate memory for bounds */
+	lowerBounds = palloc(sizeof(RangeBound) * in->nTuples);
+	upperBounds = palloc(sizeof(RangeBound) * in->nTuples);
+	j = 0;
+
+	/* Deserialize bounds of ranges, count non-empty ranges */
+	for (i = 0; i < in->nTuples; i++)
+	{
+		range_deserialize(typcache, DatumGetRangeType(in->datums[i]),
+									&lowerBounds[j], &upperBounds[j], &empty);
+		if (!empty)
+			j++;
+	}
+	nonEmptyCount = j;
+
+	/*
+	 * All the ranges are empty. The best we can do is put all ranges
+	 * into node 0. Non-empty range will be routed to node 1.
+	 */
+	if (nonEmptyCount == 0)
+	{
+		out->nNodes = 2;
+		out->hasPrefix = false;
+		/* Prefix is empty */
+		out->prefixDatum = PointerGetDatum(NULL);
+		out->nodeLabels = NULL;
+
+		out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
+		out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
+
+		/* Place all ranges into node 0 */
+		for (i = 0; i < in->nTuples; i++)
+		{
+			RangeType	   *range = DatumGetRangeType(in->datums[i]);
+
+			out->leafTupleDatums[i] = RangeTypeGetDatum(range);
+			out->mapTuplesToNodes[i] = 0;
+		}
+		PG_RETURN_VOID();
+	}
+
+	/* Sort range bounds in order to find medians */
+	qsort_arg(lowerBounds, nonEmptyCount, sizeof(RangeBound),
+			  bound_cmp, typcache);
+	qsort_arg(upperBounds, nonEmptyCount, sizeof(RangeBound),
+			  bound_cmp, typcache);
+
+	/* Construct "centroid" range from medians of lower and upper bounds */
+	centroid = range_serialize(typcache, &lowerBounds[nonEmptyCount / 2],
+							   &upperBounds[nonEmptyCount / 2], false);
+
+	out->hasPrefix = true;
+	out->prefixDatum = RangeTypeGetDatum(centroid);
+
+	/* Create node for empty ranges only if it is a root node */
+	out->nNodes = (in->level == 0) ? 5 : 4;
+	out->nodeLabels = NULL;		/* we don't need node labels */
+
+	out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
+	out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
+
+	/*
+	 * Assign ranges to corresponding nodes according to quadrants relative to
+	 * "centroid" range.
+	 */
+	for (i = 0; i < in->nTuples; i++)
+	{
+		RangeType	   *range = DatumGetRangeType(in->datums[i]);
+		int16			quadrant = getQuadrant(typcache, centroid, range);
+
+		out->leafTupleDatums[i] = RangeTypeGetDatum(range);
+		out->mapTuplesToNodes[i] = quadrant - 1;
+	}
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST consistent function for inner nodes: check which nodes are
+ * consistent with given set of queries.
+ */
+Datum
+spg_range_quad_inner_consistent(PG_FUNCTION_ARGS)
+{
+	spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
+	spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
+	int			which;
+	int			i;
+	bool		needPrevious = false;
+
+	if (in->allTheSame)
+	{
+		/* Report that all nodes should be visited */
+		out->nNodes = in->nNodes;
+		out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
+		for (i = 0; i < in->nNodes; i++)
+			out->nodeNumbers[i] = i;
+		PG_RETURN_VOID();
+	}
+
+	if (!in->hasPrefix)
+	{
+		/*
+		 * Empty "centroid". We can use only information about emptiness of
+		 * ranges in nodes.
+		 */
+		Assert(in->nNodes == 2);
+
+		/*
+		 * Nth bit of which variable means that (N - 1)th node should be
+		 * visited. Initially all bits are set. Bits of nodes which should be
+		 * skipped will be unset.
+		 */
+		which = (1 << 1) | (1 << 2);
+		for (i = 0; i < in->nkeys; i++)
+		{
+			StrategyNumber strategy;
+			bool empty;
+
+			strategy = in->scankeys[i].sk_strategy;
+
+			/*
+			 * The only strategy when second argument of operator is not
+			 * range is RANGESTRAT_CONTAINS_ELEM.
+			 */
+			if (strategy != RANGESTRAT_CONTAINS_ELEM)
+				empty = RangeIsEmpty(
+								DatumGetRangeType(in->scankeys[i].sk_argument));
+
+			switch (strategy)
+			{
+				/* These strategies return false if any argument is empty */
+				case RANGESTRAT_BEFORE:
+				case RANGESTRAT_OVERLEFT:
+				case RANGESTRAT_OVERLAPS:
+				case RANGESTRAT_OVERRIGHT:
+				case RANGESTRAT_AFTER:
+				case RANGESTRAT_ADJACENT:
+					if (empty)
+						which = 0;
+					else
+						which &= (1 << 2);
+					break;
+				/*
+				 * "Empty" range is contained in any range. Non-empty ranges
+				 * can be contained only in non-empty ranges.
+				 */
+				case RANGESTRAT_CONTAINS:
+					if (!empty)
+						which &= (1 << 2);
+					break;
+				case RANGESTRAT_CONTAINED_BY:
+					if (empty)
+						which &= (1 << 1);
+					break;
+				/* Empty range can't contain any element */
+				case RANGESTRAT_CONTAINS_ELEM:
+					which &= (1 << 2);
+					break;
+				case RANGESTRAT_EQ:
+					if (empty)
+						which &= (1 << 1);
+					else
+						which &= (1 << 2);
+					break;
+				default:
+					elog(ERROR, "unrecognized range strategy: %d", strategy);
+					break;
+			}
+			if (which == 0)
+				break;			/* no need to consider remaining conditions */
+		}
+	}
+	else
+	{
+		RangeBound		centroidLower, centroidUpper;
+		bool			centroidEmpty;
+		TypeCacheEntry *typcache;
+		RangeType	   *centroid;
+
+		/* This node has a centroid. Fetch it. */
+		centroid = DatumGetRangeType(in->prefixDatum);
+		typcache = range_get_typcache(fcinfo,
+								RangeTypeGetOid(DatumGetRangeType(centroid)));
+		range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
+						  &centroidEmpty);
+
+		Assert(in->nNodes == 4 || in->nNodes == 5);
+
+		/*
+		 * Nth bit of which variable means that (N - 1)th node (Nth quadrant)
+		 * should be visited. Initially all bits are set. Bits of nodes which
+		 * can be skipped will be unset.
+		 */
+		which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
+
+		for (i = 0; i < in->nkeys; i++)
+		{
+			StrategyNumber strategy;
+			RangeBound	lower, upper;
+			bool		empty;
+			RangeType  *range = NULL;
+
+			strategy = in->scankeys[i].sk_strategy;
+
+			/*
+			 * RANGESTRAT_CONTAINS_ELEM is just like RANGESTRAT_CONTAINS,
+			 * but the argument is a single element. Expand the single element
+			 * to a range containing only the element, and treat it like
+			 * RANGESTRAT_CONTAINS.
+			 */
+			if (strategy == RANGESTRAT_CONTAINS_ELEM)
+			{
+				lower.inclusive = true;
+				lower.infinite = false;
+				lower.lower = true;
+				lower.val = in->scankeys[i].sk_argument;
+
+				upper.inclusive = true;
+				upper.infinite = false;
+				upper.lower = false;
+				upper.val = in->scankeys[i].sk_argument;
+
+				empty = false;
+
+				strategy = RANGESTRAT_CONTAINS;
+			}
+			else
+			{
+				range = DatumGetRangeType(in->scankeys[i].sk_argument);
+				range_deserialize(typcache, range, &lower, &upper, &empty);
+			}
+
+			switch (strategy)
+			{
+				int			which1, which2;
+
+				/*
+				 * Range A is before range B if upper bound of A is lower than
+				 * lower bound of B. The geometrical interpretation is that
+				 * the lower bound of the scan key (B) specifies a horizontal
+				 * line, and points below the line match the query. If the
+				 * centroid lies above (or on) the line, then all points above
+				 * or equal to the centroid, in quadrants 1 and 4, are also
+				 * above the line and cannot match.
+				 */
+				case RANGESTRAT_BEFORE:
+					if (empty)
+						which = 0; /* nothing can be before 'empty' */
+					else if (range_cmp_bounds(typcache, &centroidUpper,
+											  &lower) >= 0)
+						which &= (1 << 2) | (1 << 3);
+					else
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+					break;
+
+				/*
+				 * Range A is overleft to range B if upper bound of A is less
+				 * or equal to upper bound of B. The geometrical interpretation
+				 * is that the upper bound of the scan key (B) specifies a
+				 * horizontal line, and points below or on the line match the
+				 * query.
+				 */
+				case RANGESTRAT_OVERLEFT:
+					if (empty)
+						which = 0;
+					/*
+					 * If the centroid is above the scan key point, then any
+					 * points above or equal to the centroid (in quadrants 1
+					 * and 4) must also be above the scan key point and cannot
+					 * match.
+					 */
+					 else if (range_cmp_bounds(typcache, &centroidUpper,
+											  &upper) > 0)
+						which = (1 << 2) | (1 << 3);
+					else
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+					break;
+
+				/*
+				 * Non-empty ranges overlap, if lower bound of each range is
+				 * lower or equal to upper bound of the other range. The
+				 * geometrical interpretation is that the scan key specifies
+				 * a point, so that the scan key's upper bound is the X
+				 * coordinate, and lower bound the Y coordinate. Note that this
+				 * is reverse to usual mapping. Everything to the left and
+				 * above (or equal) the scan key point match.
+				 */
+				case RANGESTRAT_OVERLAPS:
+					if (empty)
+						which = 0;
+					else
+					{
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+
+						/*
+						 * If centroid is to the right of the scan key point,
+						 * then nothing right of (or equal to) the centroid can
+						 * match.
+						 */
+						if (range_cmp_bounds(typcache, &centroidLower,
+											 &upper) > 0)
+							which &= (1 << 3) | (1 << 4);
+
+						/*
+						 * If centroid is below the scan key point, then
+						 * nothing below the centroid can match.
+						 */
+						if (range_cmp_bounds(typcache, &centroidUpper,
+											 &lower) <= 0)
+							which &= (1 << 1) | (1 << 4);
+					}
+					break;
+
+				/*
+				 * Range A is overright to range B if lower bound of A is
+				 * greater or equal to lower bound of B. The geometrical
+				 * interpretation is that the lower bound of the scan key (B)
+				 * forms a vertical line, and points at or to the right of the
+				 * line match.
+				 */
+				case RANGESTRAT_OVERRIGHT:
+					if (empty)
+						which = 0;
+					/*
+					 * If the centroid is to the left or equal to the
+					 * scan key line, then any points to the left of the
+					 * centroid (in quadrants 3 and 4) are to the left of
+					 * the scan key point, and cannot match.
+					 */
+					else if (range_cmp_bounds(typcache, &centroidLower,
+											  &lower) <= 0)
+						which = (1 << 1) | (1 << 2);
+					else
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+					break;
+
+				/*
+				 * Range A is after range B if lower bound of A is greater than
+				 * upper bound of B. The geometric interpretation is that upper
+				 * bound of the scan key (B) forms a vertical line, and any
+				 * points to the right of the line match.
+				 */
+				case RANGESTRAT_AFTER:
+					if (empty)
+						which = 0;
+					/*
+					 * If the centroid is to the left of or equal to the scan
+					 * key line, then anything to the left of the centroid
+					 * (in quadrants 3 and 4) must also be to the left of the
+					 * line and cannot match.
+					 */
+					else if (range_cmp_bounds(typcache, &centroidLower,
+											  &upper) <= 0)
+						which &= (1 << 1) | (1 << 2);
+					else
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+					break;
+
+				/*
+				 * Ranges are adjacent if lower bound of one range is adjacent
+				 * to upper bound of another range.
+				 */
+				case RANGESTRAT_ADJACENT:
+					if (empty)
+					{
+						which = 0;
+						break;
+					}
+
+					lower.lower = false;
+					lower.inclusive = !lower.inclusive;
+					upper.lower = true;
+					upper.inclusive = !upper.inclusive;
+
+					/*
+					 * which1 is bitmask for possibility to be adjacent with
+					 * lower bound of argument. which2 is bitmask for
+					 * possibility to be adjacent with upper bound of
+					 * argument.
+					 */
+					which1 = which2 = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+
+					/* Deserialize previous centroid range if present. */
+					if (in->reconstructedValue != (Datum) 0)
+					{
+						RangeType  *prevCentroid;
+						RangeBound	prevLower, prevUpper;
+						bool		prevEmpty;
+						int			cmp1, cmp3;
+
+						prevCentroid = DatumGetRangeType(in->reconstructedValue);
+						range_deserialize(typcache, prevCentroid, &prevLower,
+										  &prevUpper, &prevEmpty);
+
+						/* Do comparison with previous centroid */
+						cmp1 = range_cmp_bounds(typcache, &upper, &prevLower);
+						cmp3 = range_cmp_bounds(typcache, &centroidLower,
+												&prevLower);
+
+						/*
+						 * Check if lower bound of argument is not in
+						 * a quadrant we visit in previous step.
+						 */
+						if ((cmp3 < 0 && cmp1 > 0) || (cmp3 > 0 && cmp1 < 0))
+							which1 = 0;
+
+						/* Do comparison with previous centroid */
+						cmp1 = range_cmp_bounds(typcache, &lower, &prevUpper);
+						cmp3 = range_cmp_bounds(typcache, &centroidUpper, &prevUpper);
+						/*
+						 * Check if upper bound of argument is not in
+						 * a quadrant we visit in previous step.
+						 */
+						if ((cmp3 < 0 && cmp1 > 0) || (cmp3 > 0 && cmp1 < 0))
+							which2 = 0;
+					}
+
+					if (which1)
+					{
+						if (range_cmp_bounds(typcache, &upper, &centroidLower) >= 0)
+							which1 &= (1 << 1) | (1 << 2);
+						else if (!bounds_adjacent(typcache, &centroidLower, &upper))
+							which1 &= (1 << 3) | (1 << 4);
+					}
+
+					if (which2)
+					{
+						int cmp2 = range_cmp_bounds(typcache, &lower, &centroidUpper);
+						if (cmp2 > 0)
+							which2 &= (1 << 1) | (1 << 4);
+						else if (cmp2 < 0)
+							which2 &= (1 << 2) | (1 << 3);
+					}
+
+					which &= which1 | which2;
+
+					needPrevious = true;
+					break;
+
+				/*
+				 * Non-empty range A contains non-empty range B if lower bound
+				 * of A is lower or equal to lower bound of range B and upper
+				 * bound of range A is greater or equal to upper bound of range
+				 * A.
+				 */
+				case RANGESTRAT_CONTAINS:
+					if (!empty)
+					{
+						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+						/*
+						 * If lower bound of centroid is greater than lower
+						 * bound of argument then no ranges which contain
+						 * argument can be in quadrants 1 and 2.
+						 */
+						if (range_cmp_bounds(typcache, &centroidLower,
+																	&lower) > 0)
+							which &= (1 << 3) | (1 << 4);
+						/*
+						 * If upper bound of centroid is lower or equal to upper
+						 * bound of argument then no ranges which contain
+						 * argument can be in quadrants 2 and 3.
+						 */
+						if (range_cmp_bounds(typcache, &centroidUpper,
+																   &upper) <= 0)
+							which &= (1 << 1) | (1 << 4);
+					}
+					break;
+
+				case RANGESTRAT_CONTAINED_BY:
+					if (empty)
+						which = (1 << 5);
+					else
+					{
+						/*
+						 * If lower bound of centroid is lower or equal to lower
+						 * bound of argument then no ranges which are contained
+						 * in argument can be in quadrants 3 and 4.
+						 */
+						if (range_cmp_bounds(typcache, &centroidLower,
+																   &lower) <= 0)
+							which &= (1 << 1) | (1 << 2) | (1 << 5);
+						/*
+						 * If upper bound of centroid is greater than upper
+						 * bound of argument then no ranges which are contained
+						 * in argument can be in quadrants 1 and 4.
+						 */
+						if (range_cmp_bounds(typcache, &centroidUpper,
+																	&upper) > 0)
+							which &= (1 << 2) | (1 << 3) | (1 << 5);
+					}
+					break;
+
+				/*
+				 * Equal range can be only in the same quadrant where argument
+				 * would be placed to.
+				 */
+				case RANGESTRAT_EQ:
+					which &= (1 << getQuadrant(typcache, centroid, range));
+					break;
+
+				default:
+					elog(ERROR, "unrecognized range strategy: %d", strategy);
+					break;
+			}
+
+			if (which == 0)
+				break;			/* no need to consider remaining conditions */
+		}
+	}
+
+	/* We must descend into the quadrant(s) identified by 'which' */
+	out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
+	if (needPrevious)
+		out->reconstructedValues = (Datum *) palloc(sizeof(Datum) * in->nNodes);
+	out->nNodes = 0;
+	for (i = 1; i <= in->nNodes; i++)
+	{
+		if (which & (1 << i))
+		{
+			/* Save previous prefix if needed */
+			if (needPrevious)
+				out->reconstructedValues[out->nNodes] = in->prefixDatum;
+			out->nodeNumbers[out->nNodes++] = i - 1;
+		}
+	}
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST consistent function for leaf nodes: check leaf value against query
+ * using corresponding function.
+ */
+Datum
+spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
+{
+	spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
+	spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
+	RangeType  *leafRange = DatumGetRangeType(in->leafDatum);
+	TypeCacheEntry *typcache;
+	bool		res;
+	int			i;
+
+	/* all tests are exact */
+	out->recheck = false;
+
+	/* leafDatum is what it is... */
+	out->leafValue = in->leafDatum;
+
+	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
+
+	/* Perform the required comparison(s) */
+	res = true;
+	for (i = 0; i < in->nkeys; i++)
+	{
+		Datum	keyDatum = in->scankeys[i].sk_argument;
+
+		/* Call the function corresponding to the scan strategy */
+		switch (in->scankeys[i].sk_strategy)
+		{
+			case RANGESTRAT_BEFORE:
+				res = range_before_internal(typcache, leafRange,
+											DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_OVERLEFT:
+				res = range_overleft_internal(typcache, leafRange,
+											  DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_OVERLAPS:
+				res = range_overlaps_internal(typcache, leafRange,
+											  DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_OVERRIGHT:
+				res = range_overright_internal(typcache, leafRange,
+											   DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_AFTER:
+				res = range_after_internal(typcache, leafRange,
+										   DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_ADJACENT:
+				res = range_adjacent_internal(typcache, leafRange,
+											  DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_CONTAINS:
+				res = range_contains_internal(typcache, leafRange,
+											  DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_CONTAINED_BY:
+				res = range_contained_by_internal(typcache, leafRange,
+												  DatumGetRangeType(keyDatum));
+				break;
+			case RANGESTRAT_CONTAINS_ELEM:
+				res = range_contains_elem_internal(typcache, leafRange,
+												   keyDatum);
+				break;
+			case RANGESTRAT_EQ:
+				res = range_eq_internal(typcache, leafRange,
+										DatumGetRangeType(keyDatum));
+				break;
+			default:
+				elog(ERROR, "unrecognized range strategy: %d",
+					 in->scankeys[i].sk_strategy);
+				break;
+		}
+
+		/*
+		 * If leaf datum doesn't match to a query key, no need to check
+		 * subsequent keys.
+		 */
+		if (!res)
+			break;
+	}
+
+	PG_RETURN_BOOL(res);
+}
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index ee6ac8f..74db745 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -767,4 +767,18 @@ DATA(insert (	4017   25 25 12 s	665 4000 0 ));
 DATA(insert (	4017   25 25 14 s	667 4000 0 ));
 DATA(insert (	4017   25 25 15 s	666 4000 0 ));
 
+/*
+ * SP-GiST range_ops
+ */
+DATA(insert (	3474   3831 3831 1 s	3893 4000 0 ));
+DATA(insert (	3474   3831 3831 2 s	3895 4000 0 ));
+DATA(insert (	3474   3831 3831 3 s	3888 4000 0 ));
+DATA(insert (	3474   3831 3831 4 s	3896 4000 0 ));
+DATA(insert (	3474   3831 3831 5 s	3894 4000 0 ));
+DATA(insert (	3474   3831 3831 6 s	3897 4000 0 ));
+DATA(insert (	3474   3831 3831 7 s	3890 4000 0 ));
+DATA(insert (	3474   3831 3831 8 s	3892 4000 0 ));
+DATA(insert (	3474   3831 2283 16 s	3889 4000 0 ));
+DATA(insert (	3474   3831 3831 18 s	3882 4000 0 ));
+
 #endif   /* PG_AMOP_H */
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index 99d4676..984f1ec 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -373,5 +373,10 @@ DATA(insert (	4017   25 25 2 4028 ));
 DATA(insert (	4017   25 25 3 4029 ));
 DATA(insert (	4017   25 25 4 4030 ));
 DATA(insert (	4017   25 25 5 4031 ));
+DATA(insert (	3474   3831 3831 1 3469 ));
+DATA(insert (	3474   3831 3831 2 3470 ));
+DATA(insert (	3474   3831 3831 3 3471 ));
+DATA(insert (	3474   3831 3831 4 3472 ));
+DATA(insert (	3474   3831 3831 5 3473 ));
 
 #endif   /* PG_AMPROC_H */
diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h
index 638f808..2ed98d5 100644
--- a/src/include/catalog/pg_opclass.h
+++ b/src/include/catalog/pg_opclass.h
@@ -223,6 +223,7 @@ DATA(insert (	783		tsquery_ops			PGNSP PGUID 3702  3615 t 20 ));
 DATA(insert (	403		range_ops			PGNSP PGUID 3901  3831 t 0 ));
 DATA(insert (	405		range_ops			PGNSP PGUID 3903  3831 t 0 ));
 DATA(insert (	783		range_ops			PGNSP PGUID 3919  3831 t 0 ));
+DATA(insert (	4000	range_ops			PGNSP PGUID 3474  3831 t 0 ));
 DATA(insert (	4000	quad_point_ops		PGNSP PGUID 4015  600 t 0 ));
 DATA(insert (	4000	kd_point_ops		PGNSP PGUID 4016  600 f 0 ));
 DATA(insert (	4000	text_ops			PGNSP PGUID 4017  25 t 0 ));
diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h
index 41ebccc..b1340ca 100644
--- a/src/include/catalog/pg_opfamily.h
+++ b/src/include/catalog/pg_opfamily.h
@@ -142,6 +142,7 @@ DATA(insert OID = 3702 (	783		tsquery_ops		PGNSP PGUID ));
 DATA(insert OID = 3901 (	403		range_ops		PGNSP PGUID ));
 DATA(insert OID = 3903 (	405		range_ops		PGNSP PGUID ));
 DATA(insert OID = 3919 (	783		range_ops		PGNSP PGUID ));
+DATA(insert OID = 3474 (	4000	range_ops		PGNSP PGUID ));
 DATA(insert OID = 4015 (	4000	quad_point_ops	PGNSP PGUID ));
 DATA(insert OID = 4016 (	4000	kd_point_ops	PGNSP PGUID ));
 DATA(insert OID = 4017 (	4000	text_ops		PGNSP PGUID ));
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 665918f..51449a4 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -4653,6 +4653,17 @@ DESCR("SP-GiST support for suffix tree over text");
 DATA(insert OID = 4031 (  spg_text_leaf_consistent	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_  spg_text_leaf_consistent _null_ _null_ _null_ ));
 DESCR("SP-GiST support for suffix tree over text");
 
+DATA(insert OID = 3469 (  spg_range_quad_config	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_range_quad_config _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over range");
+DATA(insert OID = 3470 (  spg_range_quad_choose	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_range_quad_choose _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over range");
+DATA(insert OID = 3471 (  spg_range_quad_picksplit	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_range_quad_picksplit _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over range");
+DATA(insert OID = 3472 (  spg_range_quad_inner_consistent	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_  spg_range_quad_inner_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over range");
+DATA(insert OID = 3473 (  spg_range_quad_leaf_consistent	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_  spg_range_quad_leaf_consistent _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over range");
+
 
 /*
  * Symbolic values for provolatile column: these indicate whether the result
diff --git a/src/include/utils/rangetypes.h b/src/include/utils/rangetypes.h
index a37401c..992054d 100644
--- a/src/include/utils/rangetypes.h
+++ b/src/include/utils/rangetypes.h
@@ -75,6 +75,19 @@ typedef struct
 #define PG_GETARG_RANGE_COPY(n)		DatumGetRangeTypeCopy(PG_GETARG_DATUM(n))
 #define PG_RETURN_RANGE(x)			return RangeTypeGetDatum(x)
 
+/* Operator strategy numbers used in the GiST range opclass */
+/* Numbers are chosen to match up operator names with existing usages */
+#define RANGESTRAT_BEFORE				1
+#define RANGESTRAT_OVERLEFT				2
+#define RANGESTRAT_OVERLAPS				3
+#define RANGESTRAT_OVERRIGHT			4
+#define RANGESTRAT_AFTER				5
+#define RANGESTRAT_ADJACENT				6
+#define RANGESTRAT_CONTAINS				7
+#define RANGESTRAT_CONTAINED_BY			8
+#define RANGESTRAT_CONTAINS_ELEM		16
+#define RANGESTRAT_EQ					18
+
 /*
  * prototypes for functions defined in rangetypes.c
  */
@@ -188,6 +201,8 @@ extern int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1,
 extern int range_cmp_bound_values(TypeCacheEntry *typcache, RangeBound *b1,
 					   RangeBound *b2);
 extern RangeType *make_empty_range(TypeCacheEntry *typcache);
+extern bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound *lower,
+						RangeBound *upper);
 
 /* GiST support (in rangetypes_gist.c) */
 extern Datum range_gist_consistent(PG_FUNCTION_ARGS);
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index 110ea41..256b719 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -1068,12 +1068,17 @@ ORDER BY 1, 2, 3;
        2742 |            4 | =
        4000 |            1 | <<
        4000 |            1 | ~<~
+       4000 |            2 | &<
        4000 |            2 | ~<=~
+       4000 |            3 | &&
        4000 |            3 | =
+       4000 |            4 | &>
        4000 |            4 | ~>=~
        4000 |            5 | >>
        4000 |            5 | ~>~
+       4000 |            6 | -|-
        4000 |            6 | ~=
+       4000 |            7 | @>
        4000 |            8 | <@
        4000 |           10 | <^
        4000 |           11 | <
@@ -1081,7 +1086,9 @@ ORDER BY 1, 2, 3;
        4000 |           12 | <=
        4000 |           14 | >=
        4000 |           15 | >
-(55 rows)
+       4000 |           16 | @>
+       4000 |           18 | =
+(62 rows)
 
 -- Check that all opclass search operators have selectivity estimators.
 -- This is not absolutely required, but it seems a reasonable thing
diff --git a/src/test/regress/expected/rangetypes.out b/src/test/regress/expected/rangetypes.out
index e37fab3..1023c4e 100644
--- a/src/test/regress/expected/rangetypes.out
+++ b/src/test/regress/expected/rangetypes.out
@@ -821,6 +821,225 @@ select count(*) from test_range_gist where ir -|- int4range(100,500);
      5
 (1 row)
 
+-- test SP-GiST index that's been built incrementally
+create table test_range_spgist(ir int4range);
+create index test_range_spgist_idx on test_range_spgist using spgist (ir);
+insert into test_range_spgist select int4range(g, g+10) from generate_series(1,2000) g;
+insert into test_range_spgist select 'empty'::int4range from generate_series(1,500) g;
+insert into test_range_spgist select int4range(g, g+10000) from generate_series(1,1000) g;
+insert into test_range_spgist select 'empty'::int4range from generate_series(1,500) g;
+insert into test_range_spgist select int4range(NULL,g*10,'(]') from generate_series(1,100) g;
+insert into test_range_spgist select int4range(g*10,NULL,'(]') from generate_series(1,100) g;
+insert into test_range_spgist select int4range(g, g+10) from generate_series(1,2000) g;
+-- first, verify non-indexed results
+SET enable_seqscan    = t;
+SET enable_indexscan  = f;
+SET enable_bitmapscan = f;
+select count(*) from test_range_spgist where ir @> 'empty'::int4range;
+ count 
+-------
+  6200
+(1 row)
+
+select count(*) from test_range_spgist where ir = int4range(10,20);
+ count 
+-------
+     2
+(1 row)
+
+select count(*) from test_range_spgist where ir @> 10;
+ count 
+-------
+   130
+(1 row)
+
+select count(*) from test_range_spgist where ir @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_range_spgist where ir && int4range(10,20);
+ count 
+-------
+   158
+(1 row)
+
+select count(*) from test_range_spgist where ir <@ int4range(10,50);
+ count 
+-------
+  1062
+(1 row)
+
+select count(*) from test_range_spgist where ir << int4range(100,500);
+ count 
+-------
+   189
+(1 row)
+
+select count(*) from test_range_spgist where ir >> int4range(100,500);
+ count 
+-------
+  3554
+(1 row)
+
+select count(*) from test_range_spgist where ir &< int4range(100,500);
+ count 
+-------
+  1029
+(1 row)
+
+select count(*) from test_range_spgist where ir &> int4range(100,500);
+ count 
+-------
+  4794
+(1 row)
+
+select count(*) from test_range_spgist where ir -|- int4range(100,500);
+ count 
+-------
+     5
+(1 row)
+
+-- now check same queries using index
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+SET enable_bitmapscan = f;
+select count(*) from test_range_spgist where ir @> 'empty'::int4range;
+ count 
+-------
+  6200
+(1 row)
+
+select count(*) from test_range_spgist where ir = int4range(10,20);
+ count 
+-------
+     2
+(1 row)
+
+select count(*) from test_range_spgist where ir @> 10;
+ count 
+-------
+   130
+(1 row)
+
+select count(*) from test_range_spgist where ir @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_range_spgist where ir && int4range(10,20);
+ count 
+-------
+   158
+(1 row)
+
+select count(*) from test_range_spgist where ir <@ int4range(10,50);
+ count 
+-------
+  1062
+(1 row)
+
+select count(*) from test_range_spgist where ir << int4range(100,500);
+ count 
+-------
+   189
+(1 row)
+
+select count(*) from test_range_spgist where ir >> int4range(100,500);
+ count 
+-------
+  3554
+(1 row)
+
+select count(*) from test_range_spgist where ir &< int4range(100,500);
+ count 
+-------
+  1029
+(1 row)
+
+select count(*) from test_range_spgist where ir &> int4range(100,500);
+ count 
+-------
+  4794
+(1 row)
+
+select count(*) from test_range_spgist where ir -|- int4range(100,500);
+ count 
+-------
+     5
+(1 row)
+
+-- now check same queries using a bulk-loaded index
+drop index test_range_spgist_idx;
+create index test_range_spgist_idx on test_range_spgist using spgist (ir);
+select count(*) from test_range_spgist where ir @> 'empty'::int4range;
+ count 
+-------
+  6200
+(1 row)
+
+select count(*) from test_range_spgist where ir = int4range(10,20);
+ count 
+-------
+     2
+(1 row)
+
+select count(*) from test_range_spgist where ir @> 10;
+ count 
+-------
+   130
+(1 row)
+
+select count(*) from test_range_spgist where ir @> int4range(10,20);
+ count 
+-------
+   111
+(1 row)
+
+select count(*) from test_range_spgist where ir && int4range(10,20);
+ count 
+-------
+   158
+(1 row)
+
+select count(*) from test_range_spgist where ir <@ int4range(10,50);
+ count 
+-------
+  1062
+(1 row)
+
+select count(*) from test_range_spgist where ir << int4range(100,500);
+ count 
+-------
+   189
+(1 row)
+
+select count(*) from test_range_spgist where ir >> int4range(100,500);
+ count 
+-------
+  3554
+(1 row)
+
+select count(*) from test_range_spgist where ir &< int4range(100,500);
+ count 
+-------
+  1029
+(1 row)
+
+select count(*) from test_range_spgist where ir &> int4range(100,500);
+ count 
+-------
+  4794
+(1 row)
+
+select count(*) from test_range_spgist where ir -|- int4range(100,500);
+ count 
+-------
+     5
+(1 row)
+
 RESET enable_seqscan;
 RESET enable_indexscan;
 RESET enable_bitmapscan;
diff --git a/src/test/regress/expected/sanity_check.out b/src/test/regress/expected/sanity_check.out
index d4b3361..3f04442 100644
--- a/src/test/regress/expected/sanity_check.out
+++ b/src/test/regress/expected/sanity_check.out
@@ -157,6 +157,7 @@ SELECT relname, relhasindex
  tenk2                   | t
  test_range_excl         | t
  test_range_gist         | t
+ test_range_spgist       | t
  test_tsvector           | f
  text_tbl                | f
  time_tbl                | f
@@ -165,7 +166,7 @@ SELECT relname, relhasindex
  timetz_tbl              | f
  tinterval_tbl           | f
  varchar_tbl             | f
-(154 rows)
+(155 rows)
 
 --
 -- another sanity check: every system catalog that has OIDs should have
diff --git a/src/test/regress/output/misc.source b/src/test/regress/output/misc.source
index 979ed33..4353d0b 100644
--- a/src/test/regress/output/misc.source
+++ b/src/test/regress/output/misc.source
@@ -675,6 +675,7 @@ SELECT user_relns() AS user_relns
  tenk2
  test_range_excl
  test_range_gist
+ test_range_spgist
  test_tsvector
  text_tbl
  time_tbl
@@ -685,7 +686,7 @@ SELECT user_relns() AS user_relns
  toyemp
  varchar_tbl
  xacttest
-(107 rows)
+(108 rows)
 
 SELECT name(equipment(hobby_construct(text 'skywalking', text 'mer')));
  name 
diff --git a/src/test/regress/sql/rangetypes.sql b/src/test/regress/sql/rangetypes.sql
index 08d6976..035fcec 100644
--- a/src/test/regress/sql/rangetypes.sql
+++ b/src/test/regress/sql/rangetypes.sql
@@ -220,6 +220,68 @@ select count(*) from test_range_gist where ir &< int4range(100,500);
 select count(*) from test_range_gist where ir &> int4range(100,500);
 select count(*) from test_range_gist where ir -|- int4range(100,500);
 
+-- test SP-GiST index that's been built incrementally
+create table test_range_spgist(ir int4range);
+create index test_range_spgist_idx on test_range_spgist using spgist (ir);
+
+insert into test_range_spgist select int4range(g, g+10) from generate_series(1,2000) g;
+insert into test_range_spgist select 'empty'::int4range from generate_series(1,500) g;
+insert into test_range_spgist select int4range(g, g+10000) from generate_series(1,1000) g;
+insert into test_range_spgist select 'empty'::int4range from generate_series(1,500) g;
+insert into test_range_spgist select int4range(NULL,g*10,'(]') from generate_series(1,100) g;
+insert into test_range_spgist select int4range(g*10,NULL,'(]') from generate_series(1,100) g;
+insert into test_range_spgist select int4range(g, g+10) from generate_series(1,2000) g;
+
+-- first, verify non-indexed results
+SET enable_seqscan    = t;
+SET enable_indexscan  = f;
+SET enable_bitmapscan = f;
+
+select count(*) from test_range_spgist where ir @> 'empty'::int4range;
+select count(*) from test_range_spgist where ir = int4range(10,20);
+select count(*) from test_range_spgist where ir @> 10;
+select count(*) from test_range_spgist where ir @> int4range(10,20);
+select count(*) from test_range_spgist where ir && int4range(10,20);
+select count(*) from test_range_spgist where ir <@ int4range(10,50);
+select count(*) from test_range_spgist where ir << int4range(100,500);
+select count(*) from test_range_spgist where ir >> int4range(100,500);
+select count(*) from test_range_spgist where ir &< int4range(100,500);
+select count(*) from test_range_spgist where ir &> int4range(100,500);
+select count(*) from test_range_spgist where ir -|- int4range(100,500);
+
+-- now check same queries using index
+SET enable_seqscan    = f;
+SET enable_indexscan  = t;
+SET enable_bitmapscan = f;
+
+select count(*) from test_range_spgist where ir @> 'empty'::int4range;
+select count(*) from test_range_spgist where ir = int4range(10,20);
+select count(*) from test_range_spgist where ir @> 10;
+select count(*) from test_range_spgist where ir @> int4range(10,20);
+select count(*) from test_range_spgist where ir && int4range(10,20);
+select count(*) from test_range_spgist where ir <@ int4range(10,50);
+select count(*) from test_range_spgist where ir << int4range(100,500);
+select count(*) from test_range_spgist where ir >> int4range(100,500);
+select count(*) from test_range_spgist where ir &< int4range(100,500);
+select count(*) from test_range_spgist where ir &> int4range(100,500);
+select count(*) from test_range_spgist where ir -|- int4range(100,500);
+
+-- now check same queries using a bulk-loaded index
+drop index test_range_spgist_idx;
+create index test_range_spgist_idx on test_range_spgist using spgist (ir);
+
+select count(*) from test_range_spgist where ir @> 'empty'::int4range;
+select count(*) from test_range_spgist where ir = int4range(10,20);
+select count(*) from test_range_spgist where ir @> 10;
+select count(*) from test_range_spgist where ir @> int4range(10,20);
+select count(*) from test_range_spgist where ir && int4range(10,20);
+select count(*) from test_range_spgist where ir <@ int4range(10,50);
+select count(*) from test_range_spgist where ir << int4range(100,500);
+select count(*) from test_range_spgist where ir >> int4range(100,500);
+select count(*) from test_range_spgist where ir &< int4range(100,500);
+select count(*) from test_range_spgist where ir &> int4range(100,500);
+select count(*) from test_range_spgist where ir -|- int4range(100,500);
+
 RESET enable_seqscan;
 RESET enable_indexscan;
 RESET enable_bitmapscan;