range_spgist_quad-0.6.patch

*** a/src/backend/utils/adt/Makefile
--- b/src/backend/utils/adt/Makefile
***************
*** 30,36 **** 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
  
  like.o: like.c like_match.c
  
--- 30,36 ----
  	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 rangetypes_spgist.o
  
  like.o: like.c like_match.c
  
*** a/src/backend/utils/adt/rangetypes.c
--- b/src/backend/utils/adt/rangetypes.c
***************
*** 709,714 **** range_after(PG_FUNCTION_ARGS)
--- 709,758 ----
  	PG_RETURN_BOOL(range_after_internal(typcache, r1, r2));
  }
  
+ /*
+  * Check if two bounds A and B are "adjacent", i.e. each subtype value satisfy
+  * to strictly one of those bounds: there are no values which satisfy both
+  * bounds and there are no values between the bounds. For discrete ranges, we
+  * have to 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).
+  *
+  * And if A > B then the ranges cannot be adjacent in this order.
+  */
+ bool
+ bounds_adjacent(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper)
+ {
+ 	int 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,726 **** 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))
--- 763,768 ----
***************
*** 734,795 **** 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).
  	 */
! 	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;
  }
  
  /* adjacent to (but not overlapping)? */
--- 776,787 ----
  		return false;
  
  	/*
! 	 * Given two ranges A..B and C..D, the ranges are adjacent if and only if
! 	 * the pair of B and C bounds is adjacent or pair of D and A bounds is
! 	 * adjacent.
  	 */
! 	return (bounds_adjacent(typcache, &lower2, &upper1) ||
! 			bounds_adjacent(typcache, &lower1, &upper2));
  }
  
  /* adjacent to (but not overlapping)? */
***************
*** 2220,2226 **** range_contains_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
  	/* Different types should be prevented by ANYRANGE matching rules */
  	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
  		elog(ERROR, "range types do not match");
! 
  	range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
  	range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
  
--- 2212,2218 ----
  	/* Different types should be prevented by ANYRANGE matching rules */
  	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
  		elog(ERROR, "range types do not match");
! 	
  	range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
  	range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
  
*** a/src/backend/utils/adt/rangetypes_gist.c
--- b/src/backend/utils/adt/rangetypes_gist.c
***************
*** 20,39 ****
  #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
--- 20,25 ----
***************
*** 197,203 **** range_gist_consistent(PG_FUNCTION_ARGS)
  	*recheck = false;
  
  	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
! 
  	if (GIST_LEAF(entry))
  		PG_RETURN_BOOL(range_gist_consistent_leaf(typcache, strategy,
  												  key, query));
--- 183,189 ----
  	*recheck = false;
  
  	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
! 	
  	if (GIST_LEAF(entry))
  		PG_RETURN_BOOL(range_gist_consistent_leaf(typcache, strategy,
  												  key, query));
*** /dev/null
--- b/src/backend/utils/adt/rangetypes_spgist.c
***************
*** 0 ****
--- 1,808 ----
+ /*-------------------------------------------------------------------------
+  *
+  * rangetypes_spgist.c
+  *	  implementation of quad tree over ranges mapped to 2d-points for SP-GiST.
+  *
+  * Ranges are mapped into 2d-points as following. Lower bound of range assumed
+  * to be the horizontal axis. Upper bound of range assumed to be the vertical
+  * axis. This implementation of quad-tree uses only comparison function for
+  * range element datatype, therefore it works for any rangetype.
+  * 
+  * Quad tree is a data structure like a binary tree, but it is adopted to
+  * 2d data. Each node of quad-tree contain a point (centroid) which divides
+  * 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 is empty then 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);
+ 
+ /*
+  * Config SP-GiST 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. 
+  *
+  * Quadrants are identified 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 the
+  * quadrant 1. Empty ranges are taken to lie in the quadrant 5.
+  */
+ static int16
+ getQuadrant(TypeCacheEntry *typcache, RangeType *centroid, RangeType *tst)
+ {
+ 	RangeBound centroidLower, centroidUpper, lower, upper;
+ 	bool centroidEmpty, 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;		
+ 	}
+ 
+ 	elog(ERROR, "getQuadrant: impossible case");
+ 	return 0;
+ }
+ 
+ 
+ /*
+  * 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, j, 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. We've nothing better than put all the 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);
+ 
+ 	/* 
+ 	 * Add 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();
+ }
+ 
+ /*
+  * Inner consisted SP-GiST function: 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 in only 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;
+ 
+ 		/* Prefix is not null, get information about 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
+ 		 * should 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;
+ 			
+ 			/*
+ 			 * Deserialize range if argument is range. The only strategy when
+ 			 * second argument of operator is not range is
+ 			 * RANGESTRAT_CONTAINS_ELEM.
+ 			 */
+ 			if (strategy != RANGESTRAT_CONTAINS_ELEM)
+ 			{
+ 				range = DatumGetRangeType(in->scankeys[i].sk_argument);
+ 				range_deserialize(typcache, range, &lower, &upper, &empty);
+ 			}
+ 			
+ 			switch (strategy)
+ 			{
+ 				RangeBound	prevLower, prevUpper;
+ 				bool		prevEmpty, prevPresent;
+ 				RangeType  *prevCentroid;
+ 				int			cmp1, cmp2, cmp3, which1, which2;
+ 				
+ 				/*
+ 				 * Range A is before range B if upper bound of A is lower than
+ 				 * lower bound of B. If upper bound of "centroid" is greater
+ 				 * or equal to lower bound of argument then no ranges before
+ 				 * argument can be contained in quadrants 2 and 4.
+ 				 */
+ 				case RANGESTRAT_BEFORE:
+ 					if (empty)
+ 						which = 0;
+ 					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 lower
+ 				 * or equal to lower bound of B. If upper bound of "centroid" is
+ 				 * greater to upper bound of argument then no ranges overleft
+ 				 * argument can be contained in quadrants 1 and 4.
+ 				 */
+ 				case RANGESTRAT_OVERLEFT:
+ 					if (empty)
+ 						which = 0;
+ 					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 overlaps if lower bound of each range is
+ 				 * lower or equal to upper bound of another ranges.
+ 				 */
+ 				case RANGESTRAT_OVERLAPS:
+ 					if (empty)
+ 						which = 0;
+ 					else
+ 					{
+ 						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+ 						
+ 						/*
+ 						 * If lower bound of centroid is greater than upper
+ 						 * bound of argument then no overlapping ranges can be
+ 						 * in 1 and 2 quadrants.
+ 						 */
+ 						if (range_cmp_bounds(typcache, &centroidLower,
+ 																	&upper) > 0)
+ 							which &= (1 << 3) | (1 << 4);
+ 						
+ 						/*
+ 						 * If upper bound of centroid is lower or equal than
+ 						 * lower bound of argument then no overlapping ranges
+ 						 * can be in 2 and 3 quadrants.
+ 						 */
+ 						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 upper
+ 				 * or equal to upper bound of B. If lower bound of "centroid" is
+ 				 * lower or equal to lower bound of argument then no ranges
+ 				 * overright argument can be contained in quadrants 3 and 4.
+ 				 */
+ 				case RANGESTRAT_OVERRIGHT:
+ 					if (empty)
+ 						which = 0;
+ 					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. If lower bound of "centroid" is lower
+ 				 * or equal to upper bound of argument then no ranges after
+ 				 * argument can be contained in quadrants 3 and 4.
+ 				 */
+ 				case RANGESTRAT_AFTER:
+ 					if (empty)
+ 						which = 0;
+ 					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. */
+ 					prevPresent = (in->reconstructedValue != (Datum) 0);
+ 					if (prevPresent)
+ 					{
+ 						prevCentroid = DatumGetRangeType(in->reconstructedValue);
+ 						range_deserialize(typcache, prevCentroid, &prevLower,
+ 							&prevUpper, &prevEmpty);
+ 					}
+ 					
+ 					cmp2 = range_cmp_bounds(typcache, &upper, &centroidLower);
+ 					if (prevPresent)
+ 					{
+ 						/* 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;
+ 					}
+ 
+ 					if (cmp2 >= 0)
+ 						which1 &= (1 << 1) | (1 << 2);
+ 					else if (!bounds_adjacent(typcache, &centroidLower, &upper))
+ 						which1 &= (1 << 3) | (1 << 4);
+ 
+ 					cmp2 = range_cmp_bounds(typcache, &lower, &centroidUpper);
+ 					if (prevPresent)
+ 					{
+ 						/* 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 (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;
+ 				case RANGESTRAT_CONTAINS_ELEM:
+ 					/* 
+ 					 * Construct bound to pass then to bound comparison
+ 					 * functions
+ 					 */
+ 					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;
+ 					
+ 					which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+ 					
+ 					/*
+ 					 * If lower bound of centroid is greater than lower bound of
+ 					 * argument then ranges containing element can't be in 1 and 2
+ 					 * quadrants.
+ 					 */
+ 					if (range_cmp_bound_values(typcache, &centroidLower,
+ 																	&lower) > 0)
+ 							which &= (1 << 3) | (1 << 4);
+ 					
+ 					/*
+ 					 * If upper bound of centroid is lower or equal than upper
+ 					 * bound of argument then ranges containing element can't be
+ 					 * in 2 and 3 quadrants.
+ 					 */
+ 					if (range_cmp_bound_values(typcache, &centroidUpper,
+ 																   &upper) <= 0)
+ 							which &= (1 << 1) | (1 << 4);				
+ 					
+ 					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();
+ }
+ 
+ /*
+  * Leaf consistent SP-GiST function: 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);
+ 	bool		res;
+ 	int			i;
+ 	TypeCacheEntry *typcache;
+ 
+ 	/* all tests are exact */
+ 	out->recheck = false;
+ 
+ 	/* leafDatum is what it is... */
+ 	out->leafValue = in->leafDatum;
+ 
+ 	typcache = range_get_typcache(fcinfo, RangeTypeGetOid(
+ 											DatumGetRangeType(in->leafDatum)));
+ 	
+ 	/* Perform the required comparison(s) */
+ 	res = true;
+ 	for (i = 0; i < in->nkeys; i++)
+ 	{
+ 		/* Find the function which is corresponding to the scan strategy */
+ 		switch (in->scankeys[i].sk_strategy)
+ 		{
+ 			case RANGESTRAT_BEFORE:
+ 				res = range_before_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_OVERLEFT:
+ 				res = range_overleft_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_OVERLAPS:
+ 				res = range_overlaps_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_OVERRIGHT:
+ 				res = range_overright_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_AFTER:
+ 				res = range_after_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_ADJACENT:
+ 				res = range_adjacent_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_CONTAINS:
+ 				res = range_contains_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_CONTAINED_BY:
+ 				res = range_contained_by_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 							DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			case RANGESTRAT_CONTAINS_ELEM:
+ 				res = range_contains_elem_internal(typcache, 
+ 											DatumGetRangeType(in->leafDatum), 
+ 												in->scankeys[i].sk_argument);
+ 				break;
+ 			case RANGESTRAT_EQ:
+ 				res = range_eq_internal(typcache,
+ 											DatumGetRangeType(in->leafDatum), 
+ 								DatumGetRangeType(in->scankeys[i].sk_argument));
+ 				break;
+ 			default:
+ 				elog(ERROR, "unrecognized range strategy: %d", 
+ 												in->scankeys[i].sk_strategy);
+ 				res = false;
+ 				break;
+ 		}
+ 		
+ 		/* If leaf datum don't match to one query, we can don't check another */
+ 		if (!res)
+ 			break;
+ 	}
+ 
+ 	PG_RETURN_BOOL(res);
+ }
*** a/src/include/catalog/pg_amop.h
--- b/src/include/catalog/pg_amop.h
***************
*** 767,770 **** DATA(insert (	4017   25 25 12 s	665 4000 0 ));
--- 767,784 ----
  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 */
*** a/src/include/catalog/pg_amproc.h
--- b/src/include/catalog/pg_amproc.h
***************
*** 373,377 **** DATA(insert (	4017   25 25 2 4028 ));
--- 373,382 ----
  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 */
*** a/src/include/catalog/pg_opclass.h
--- b/src/include/catalog/pg_opclass.h
***************
*** 223,228 **** DATA(insert (	783		tsquery_ops			PGNSP PGUID 3702  3615 t 20 ));
--- 223,229 ----
  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 ));
*** a/src/include/catalog/pg_opfamily.h
--- b/src/include/catalog/pg_opfamily.h
***************
*** 142,147 **** DATA(insert OID = 3702 (	783		tsquery_ops		PGNSP PGUID ));
--- 142,148 ----
  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 ));
*** a/src/include/catalog/pg_proc.h
--- b/src/include/catalog/pg_proc.h
***************
*** 4653,4658 **** DESCR("SP-GiST support for suffix tree over text");
--- 4653,4669 ----
  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
*** a/src/include/utils/rangetypes.h
--- b/src/include/utils/rangetypes.h
***************
*** 75,80 **** typedef struct
--- 75,93 ----
  #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,193 **** extern int range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1,
--- 201,208 ----
  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);
*** a/src/test/regress/expected/opr_sanity.out
--- b/src/test/regress/expected/opr_sanity.out
***************
*** 1068,1079 **** ORDER BY 1, 2, 3;
--- 1068,1084 ----
         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,1087 **** ORDER BY 1, 2, 3;
         4000 |           12 | <=
         4000 |           14 | >=
         4000 |           15 | >
! (55 rows)
  
  -- Check that all opclass search operators have selectivity estimators.
  -- This is not absolutely required, but it seems a reasonable thing
--- 1086,1094 ----
         4000 |           12 | <=
         4000 |           14 | >=
         4000 |           15 | >
!        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
*** a/src/test/regress/expected/rangetypes.out
--- b/src/test/regress/expected/rangetypes.out
***************
*** 821,826 **** select count(*) from test_range_gist where ir -|- int4range(100,500);
--- 821,1045 ----
       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;
*** a/src/test/regress/expected/sanity_check.out
--- b/src/test/regress/expected/sanity_check.out
***************
*** 157,162 **** SELECT relname, relhasindex
--- 157,163 ----
   tenk2                   | t
   test_range_excl         | t
   test_range_gist         | t
+  test_range_spgist       | t
   test_tsvector           | f
   text_tbl                | f
   time_tbl                | f
***************
*** 165,171 **** SELECT relname, relhasindex
   timetz_tbl              | f
   tinterval_tbl           | f
   varchar_tbl             | f
! (154 rows)
  
  --
  -- another sanity check: every system catalog that has OIDs should have
--- 166,172 ----
   timetz_tbl              | f
   tinterval_tbl           | f
   varchar_tbl             | f
! (155 rows)
  
  --
  -- another sanity check: every system catalog that has OIDs should have
*** a/src/test/regress/output/misc.source
--- b/src/test/regress/output/misc.source
***************
*** 675,680 **** SELECT user_relns() AS user_relns
--- 675,681 ----
   tenk2
   test_range_excl
   test_range_gist
+  test_range_spgist
   test_tsvector
   text_tbl
   time_tbl
***************
*** 685,691 **** SELECT user_relns() AS user_relns
   toyemp
   varchar_tbl
   xacttest
! (107 rows)
  
  SELECT name(equipment(hobby_construct(text 'skywalking', text 'mer')));
   name 
--- 686,692 ----
   toyemp
   varchar_tbl
   xacttest
! (108 rows)
  
  SELECT name(equipment(hobby_construct(text 'skywalking', text 'mer')));
   name 
*** a/src/test/regress/sql/rangetypes.sql
--- b/src/test/regress/sql/rangetypes.sql
***************
*** 220,225 **** select count(*) from test_range_gist where ir &< int4range(100,500);
--- 220,287 ----
  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;