range_spgist_kd-0.1.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_spgistkd.o
  
  like.o: like.c like_match.c
  
*** 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 ----
***************
*** 792,798 **** range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
   * part of the relcache entry for the index, typically) this essentially
   * eliminates lookup overhead during operations on a GiST range index.
   */
! static Datum
  TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2)
  {
  	FunctionCallInfoData fcinfo;
--- 778,784 ----
   * part of the relcache entry for the index, typically) this essentially
   * eliminates lookup overhead during operations on a GiST range index.
   */
! Datum
  TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2)
  {
  	FunctionCallInfoData fcinfo;
*** /dev/null
--- b/src/backend/utils/adt/rangetypes_spgistkd.c
***************
*** 0 ****
--- 1,860 ----
+ /*-------------------------------------------------------------------------
+  *
+  * rangetypes_spgistkd.c
+  *	  implementation of k-d tree over ranges mapped to 2d-points for SP-GiST
+  *
+  *
+  * 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_spgistkd.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"
+ 
+ static int2 getNodeNumber(TypeCacheEntry *typcache, RangeType *centroid, RangeType *tst, int level);
+ static int bound_cmp(const void *a, const void *b, void *arg);
+ static bool bounds_connected(TypeCacheEntry *typcache, RangeBound lower, RangeBound upper);
+ 
+ /*
+  * Config SP-GiST interface function.
+  */
+ Datum
+ spg_range_kd_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();
+ }
+ 
+ /*
+  * Returns node number for k-d tree by given coordinate of split.
+  */
+ static int2
+ getNodeNumber(TypeCacheEntry *typcache, RangeType *coord, 
+ 													RangeType *tst, int level)
+ {
+ 	RangeBound centroidLower, centroidUpper, lower, upper;
+ 	bool centroidEmpty, empty;
+ 	
+ 	range_deserialize(typcache, tst, &lower, &upper, &empty);
+ 	
+ 	/* Empty ranges are going to node 3 */
+ 	if (empty)
+ 		return 3;
+ 	
+ 	range_deserialize(typcache, coord, &centroidLower, &centroidUpper, 
+ 																&centroidEmpty);
+ 	
+ 	if (level % 2 == 0)
+ 	{
+ 		/* Even level number, split by lower bound of range */
+ 		if (range_cmp_bounds(typcache, &lower, &centroidLower) < 0)
+ 			return 1;
+ 		else
+ 			return 2;
+ 	}
+ 	else
+ 	{
+ 		/* Odd level number, split by lower bound of range */
+ 		if (range_cmp_bounds(typcache, &upper, &centroidUpper) < 0)
+ 			return 1;
+ 		else
+ 			return 2;
+ 	}
+ 
+ 	elog(ERROR, "getQuadrant: impossible case");
+ 	return 0;
+ }
+ 
+ 
+ /*
+  * Choose SP-GiST function: choose path for addition of new range.
+  */
+ Datum
+ spg_range_kd_choose(PG_FUNCTION_ARGS)
+ {
+ 	spgChooseIn	   *in = (spgChooseIn *) PG_GETARG_POINTER(0);
+ 	spgChooseOut   *out = (spgChooseOut *) PG_GETARG_POINTER(1);
+ 	RangeType	   *inRange = DatumGetRangeType(in->datum), *centroid;
+ 	int2			nodeNumber;
+ 	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));
+ 
+ 	Assert(in->hasPrefix);
+ 	centroid = DatumGetRangeType(in->prefixDatum);
+ 	
+ 	/*
+ 	 * Empty 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 (RangeIsEmpty(centroid))
+ 	{
+ 		out->resultType = spgMatchNode;
+ 		if (RangeIsEmpty(inRange))
+ 			out->result.matchNode.nodeN = 0;
+ 		else
+ 			out->result.matchNode.nodeN = 1;
+ 		out->result.matchNode.levelAdd = 0;
+ 		out->result.matchNode.restDatum = RangeTypeGetDatum(inRange);
+ 		PG_RETURN_VOID();
+ 	}
+ 	
+ 	nodeNumber = getNodeNumber(typcache, centroid, inRange, in->level);
+ 
+ 	/* Node for empty range is possibly not exist, create it if so */
+ 	if (nodeNumber == 3 && in->nNodes == 2)
+ 	{
+ 		out->resultType = spgAddNode;
+ 		out->result.addNode.nodeN = nodeNumber - 1;
+ 	}
+ 
+ 	Assert(nodeNumber <= in->nNodes);
+ 
+ 	/* Select node */
+ 	out->resultType = spgMatchNode;
+ 	out->result.matchNode.nodeN = nodeNumber - 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 "median"
+  * of bound corresponding to level number.
+  */
+ Datum
+ spg_range_kd_picksplit(PG_FUNCTION_ARGS)
+ {
+ 	spgPickSplitIn  *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
+ 	spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
+ 	int				 i, j, nonEmptyCount;
+ 	RangeType		*coord;
+ 	bool			 empty;
+ 	TypeCacheEntry  *typcache;
+ 
+ 	/* Use the median values of lower or upper bounds for split */
+ 	RangeBound *bounds, otherBound;
+ 
+ 	typcache = range_get_typcache(fcinfo, 
+ 							RangeTypeGetOid(DatumGetRangeType(in->datums[0])));
+ 
+ 	/* Allocate memory for bounds */
+ 	bounds = palloc(sizeof(RangeBound) * in->nTuples);
+ 	j = 0;
+ 	
+ 	/* Deserialize bounds of ranges, count non-empty ranges */
+ 	for (i = 0; i < in->nTuples; i++)
+ 	{
+ 		if (in->level % 2 == 0)
+ 			range_deserialize(typcache, DatumGetRangeType(in->datums[i]),
+ 									&bounds[j], &otherBound, &empty);
+ 		else
+ 			range_deserialize(typcache, DatumGetRangeType(in->datums[i]),
+ 									&otherBound, &bounds[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 = true;
+ 		/* Prefix is empty */
+ 		out->prefixDatum = RangeTypeGetDatum(
+ 								range_serialize(typcache, NULL, NULL, true));
+ 		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 median */
+ 	qsort_arg(bounds, nonEmptyCount, sizeof(RangeBound), bound_cmp, typcache);
+ 	
+ 	
+ 	otherBound.inclusive = false;
+ 	otherBound.infinite = true;
+ 	otherBound.val = PointerGetDatum(NULL);
+ 	
+ 	/* 
+ 	 * Construct range representing coordinate of split, another bound of this
+ 	 * range is infinity for space saving.
+ 	 */
+ 	if (in->level % 2 == 0)
+ 	{
+ 		otherBound.lower = false;
+ 		coord = range_serialize(typcache, &bounds[nonEmptyCount / 2],
+ 			&otherBound, false);
+ 	}
+ 	else
+ 	{
+ 		otherBound.lower = true;
+ 		coord = range_serialize(typcache, &otherBound,
+ 			&bounds[nonEmptyCount / 2], false);
+ 	}
+ 	
+ 	
+ 	out->hasPrefix = true;
+ 	out->prefixDatum = RangeTypeGetDatum(coord);
+ 	
+ 	/* Create node for empty ranges only if it is actually needed */
+ 	out->nNodes = (nonEmptyCount == in->nTuples) ? 2 : 3;
+ 	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 their position relative
+ 	 * to split coordinate
+ 	 */
+ 	for (i = 0; i < in->nTuples; i++)
+ 	{
+ 		RangeType *range = DatumGetRangeType(in->datums[i]);
+ 		int2	   nodeNumber = getNodeNumber(typcache, coord, range, in->level);
+ 
+ 		out->leafTupleDatums[i] = RangeTypeGetDatum(range);
+ 		out->mapTuplesToNodes[i] = nodeNumber - 1;
+ 	}
+ 
+ 	PG_RETURN_VOID();
+ }
+ 
+ /*
+  * Check if two bounds are "connected", i.e. there are no values which satisfy
+  * both bounds and there are no values between the bounds.
+  */
+ static bool
+ bounds_connected(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);
+ 	}
+ }
+ 
+ /*
+  * Inner consisted SP-GiST function: check which nodes are consistent with
+  * given set of queries.
+  */
+ Datum
+ spg_range_kd_inner_consistent(PG_FUNCTION_ARGS)
+ {
+ 	spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
+ 	spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
+ 	RangeBound		prevLower, prevUpper, coordLower, coordUpper;
+ 	RangeType	   *coord, *reconstructed = NULL;
+ 	bool			centroidEmpty;
+ 	TypeCacheEntry *typcache;
+ 	int				which, i;
+ 	bool			needPrevious = false;
+ 
+ 	Assert(in->hasPrefix);
+ 	coord = DatumGetRangeType(in->prefixDatum);
+ 
+ 	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 (RangeIsEmpty(coord))
+ 	{
+ 		/*
+ 		 * Empty "coordinate". 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
+ 	{
+ 
+ 		/* Coordinate is not empty, get information about it. */
+ 		typcache = range_get_typcache(fcinfo,
+ 								RangeTypeGetOid(DatumGetRangeType(coord)));
+ 		range_deserialize(typcache, coord, &coordLower, &coordUpper, 
+ 			&centroidEmpty);
+ 		
+ 		Assert(in->nNodes == 2 || in->nNodes == 3);
+ 		
+ 		/* 
+ 		 * 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)
+ 			{
+ 				bool		prevEmpty, prevPresent;
+ 				RangeType  *prevCentroid;
+ 				int			cmp1, cmp2, cmp3;
+ 				
+ 				/*
+ 				 * Range A is before range B if upper bound of A is lower than
+ 				 * lower bound of B. If upper bound "coordinate" is greater
+ 				 * or equal to lower bound of argument then no ranges before
+ 				 * argument can be contained in node 2.
+ 				 */
+ 				case RANGESTRAT_BEFORE:
+ 					if (empty)
+ 						which = 0;
+ 					else if (range_cmp_bounds(typcache, &coordUpper,
+ 											&lower) >= 0 && in->level % 2 == 1)
+ 						which &= (1 << 1);
+ 					else
+ 						which &= (1 << 1) | (1 << 2);
+ 					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 "coordinate" is
+ 				 * greater to upper bound of argument then no ranges overleft
+ 				 * argument can be contained in node 2.
+ 				 */
+ 				case RANGESTRAT_OVERLEFT:
+ 					if (empty)
+ 						which = 0;
+ 					else if (range_cmp_bounds(typcache, &coordUpper,
+ 											&upper) > 0 && in->level % 2 == 1)
+ 						which = (1 << 1);
+ 					else
+ 						which &= (1 << 1) | (1 << 2);
+ 					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);
+ 
+ 						if (in->level % 2 == 0)
+ 						{
+ 							/*
+ 							 * If lower bound "coordinate" is greater than upper
+ 							 * bound of argument then no overlapping ranges can
+ 							 * be in node 2.
+ 							 */
+ 							if (range_cmp_bounds(typcache, &coordLower,
+ 																	&upper) > 0)
+ 								which &= (1 << 1);
+ 						}
+ 						else
+ 						{
+ 							/*
+ 							 * If upper bound "coordinate" is lower or equal than
+ 							 * lower bound of argument then no overlapping
+ 							 * ranges can be in node 1.
+ 							 */
+ 							if (range_cmp_bounds(typcache, &coordUpper,
+ 																	&lower) <= 0)
+ 								which &= (1 << 2);
+ 						}
+ 					}
+ 					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 "coordinate" is
+ 				 * lower or equal to lower bound of argument then no ranges
+ 				 * overright argument can be contained in node 1.
+ 				 */
+ 				case RANGESTRAT_OVERRIGHT:
+ 					if (empty)
+ 						which = 0;
+ 					else if (range_cmp_bounds(typcache, &coordLower,
+ 											&lower) <= 0 && in->level % 2 == 0)
+ 						which = (1 << 2);
+ 					else
+ 						which &= (1 << 1) | (1 << 2);
+ 					break;
+ 				/*
+ 				 * Range A is after range B if lower bound of A is greater than
+ 				 * upper bound of B. If lower bound "coordinate" is lower
+ 				 * or equal to upper bound of argument then no ranges after
+ 				 * argument can be contained in node 1.
+ 				 */
+ 				case RANGESTRAT_AFTER:
+ 					if (empty)
+ 						which = 0;
+ 					else if (range_cmp_bounds(typcache, &coordLower, 
+ 											&upper) <= 0 && in->level % 2 == 0)
+ 						which &= (1 << 2);
+ 					else
+ 						which &= (1 << 1) | (1 << 2);
+ 					break;
+ 				/*
+ 				 * Ranges are adjacent if lower bound of one range is connected
+ 				 * to upper bound of another range.
+ 				 */
+ 				case RANGESTRAT_ADJACENT:
+ 					/* Deserialize previous "coordinate" if present. */
+ 					prevPresent = (in->reconstructedValue != (Datum) 0);
+ 					if (prevPresent)
+ 					{
+ 						prevCentroid = DatumGetRangeType(in->reconstructedValue);
+ 						range_deserialize(typcache, prevCentroid, &prevLower,
+ 							&prevUpper, &prevEmpty);
+ 					}
+ 					
+ 					if (in->level %2 == 0)
+ 					{
+ 						cmp2 = range_cmp_bounds(typcache, &upper, &coordLower);
+ 						if (prevPresent)
+ 						{
+ 							/* 
+ 							 * Do comparison with previous "coordinate" of
+ 							 * lower bound.
+ 							 */
+ 							cmp1 = range_cmp_bounds(typcache, &upper, &prevLower);
+ 							cmp3 = range_cmp_bounds(typcache, &coordLower,
+ 																		&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))
+ 								which = 0;
+ 						}
+ 
+ 						if (cmp2 >= 0)
+ 							which &= (1 >> 2);
+ 						else if (!bounds_connected(typcache, coordLower, upper))
+ 							which &= (1 >> 1);
+ 					}
+ 					else
+ 					{
+ 						cmp2 = range_cmp_bounds(typcache, &lower, &coordUpper);
+ 						if (prevPresent)
+ 						{
+ 							/* 
+ 							 * Do comparison with previous "coordinate" of
+ 							 * upper bound.
+ 							 */
+ 							cmp1 = range_cmp_bounds(typcache, &lower, &prevUpper);
+ 							cmp3 = range_cmp_bounds(typcache, &coordUpper, &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))
+ 								which = 0;
+ 						}
+ 
+ 						if (cmp2 > 0)
+ 							which &= (1 >> 2);
+ 						else if (cmp2 < 0)
+ 							which &= (1 >> 1);
+ 					}
+ 
+ 					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 = 0;
+ 					else
+ 					{
+ 						which &= (1 << 1) | (1 << 2);
+ 						if (in->level % 2 == 0)
+ 						{
+ 							/* 
+ 							 * If lower bound "coordinate" is greater than lower
+ 							 * bound of argument then no ranges which contain
+ 							 * argument can be in node 2.
+ 							 */
+ 							if (range_cmp_bounds(typcache, &coordLower,
+ 																		&lower) > 0)
+ 								which &= (1 << 1);
+ 						}
+ 						else
+ 						{
+ 							/* 
+ 							 * If upper bound "coordinate" is lower or equal to
+ 							 * upper bound of argument then no ranges which
+ 							 * contain argument can be in node 1.
+ 							 */
+ 							if (range_cmp_bounds(typcache, &coordUpper,
+ 																	&upper) <= 0)
+ 								which &= (1 << 2);
+ 						}
+ 					}
+ 					break;
+ 				case RANGESTRAT_CONTAINED_BY:
+ 					if (empty)
+ 						which = 0;
+ 					else
+ 					{
+ 						which &= (1 << 1) | (1 << 2);
+ 						if (in->level % 2 == 0)
+ 						{
+ 							/* 
+ 							 * If lower bound "coordinate" is lower or equal to
+ 							 * lower bound of argument then no ranges which are
+ 							 * contained in argument can be in node 1.
+ 							 */
+ 							if (range_cmp_bounds(typcache, &coordLower,
+ 																&lower) <= 0)
+ 								which &= (1 << 2);
+ 						}
+ 						else
+ 						{
+ 							/* 
+ 							 * If upper bound "coordinate" is greater than upper
+ 							 * bound of argument then no ranges which are
+ 							 * contained in argument can be in node 2.
+ 							 */
+ 							if (range_cmp_bounds(typcache, &coordUpper,
+ 																	&upper) > 0)
+ 								which &= (1 << 1);
+ 						}
+ 					}
+ 					break;
+ 				case RANGESTRAT_CONTAINS_ELEM:
+ 					which &= (1 << 1) | (1 << 2);
+ 					
+ 					if (in->level % 2 == 0)
+ 					{
+ 						/* 
+ 						 * 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;
+ 						
+ 						/*
+ 						 * If lower bound "coordinate" is greater than element
+ 						 * then ranges containing element can't be in node 2.
+ 						 */
+ 						if (range_cmp_bound_values(typcache, &coordLower,
+ 																	&lower) > 0)
+ 								which &= (1 << 1);
+ 					}
+ 					else
+ 					{
+ 						/* 
+ 						 * Construct bound to pass then to bound comparison
+ 						 * functions
+ 						 */
+ 						upper.inclusive = true;
+ 						upper.infinite = false;
+ 						upper.lower = false;
+ 						upper.val = in->scankeys[i].sk_argument;
+ 						
+ 						/*
+ 						 * If upper bound "coordinate" is lower or equal than
+ 						 * element then ranges containing element can't be in
+ 						 * node 1.
+ 						 */
+ 						if (range_cmp_bound_values(typcache, &coordUpper,
+ 																&upper) <= 0)
+ 								which &= (1 << 2);
+ 					}
+ 					
+ 					break;
+ 				/*
+ 				 * Equal range can be only in the same node where argument
+ 				 * would be placed to.
+ 				 */
+ 				case RANGESTRAT_EQ:
+ 					which &= (1 << getNodeNumber(typcache, coord, range, 
+ 																	in->level));
+ 					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 node(s) identified by which */
+ 	out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
+ 	out->levelAdds = (int *) palloc(sizeof(int) * in->nNodes);
+ 	
+ 	/* Need to save this coordinate in reconstructed value for next checks? */
+ 	if (needPrevious)
+ 	{
+ 		out->reconstructedValues = (Datum *) palloc(sizeof(Datum) * in->nNodes);
+ 		if (in->level == 0)
+ 		{
+ 			reconstructed = coord;
+ 		}
+ 		else
+ 		{
+ 			/* Replace corresponding bound of current reconstructed value*/
+ 			if (in->level % 2 == 0)
+ 				reconstructed = range_serialize(typcache, &coordLower, 
+ 															&prevUpper, false);
+ 			else
+ 				reconstructed = range_serialize(typcache, &coordUpper, 
+ 															&prevLower, false);
+ 		}		
+ 	}
+ 	out->nNodes = 0;
+ 	for (i = 1; i <= in->nNodes; i++)
+ 	{
+ 		if (which & (1 << i))
+ 		{
+ 			/* Save this "coordinate" if needed */
+ 			if (needPrevious)
+ 				out->reconstructedValues[out->nNodes] = 
+ 											RangeTypeGetDatum(reconstructed);
+ 			out->nodeNumbers[out->nNodes++] = i - 1;
+ 			out->levelAdds[out->nNodes] = RangeIsEmpty(coord) ? 0 : 1;
+ 		}
+ 	}
+ 
+ 	PG_RETURN_VOID();
+ }
+ 
+ /*
+  * Leaf consistent SP-GiST function: check leaf value against query using
+  * corresponding function.
+  */
+ Datum
+ spg_range_kd_leaf_consistent(PG_FUNCTION_ARGS)
+ {
+ 	spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
+ 	spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
+ 	bool		res;
+ 	int			i;
+ 
+ 	/* all tests are exact */
+ 	out->recheck = false;
+ 
+ 	/* leafDatum is what it is... */
+ 	out->leafValue = in->leafDatum;
+ 
+ 	/* Perform the required comparison(s) */
+ 	res = true;
+ 	for (i = 0; i < in->nkeys; i++)
+ 	{
+ 		PGFunction	proc;
+ 		
+ 		/* Find the function which is corresponding to the scan strategy */
+ 		switch (in->scankeys[i].sk_strategy)
+ 		{
+ 			case RANGESTRAT_BEFORE:
+ 				proc = range_before;
+ 				break;
+ 			case RANGESTRAT_OVERLEFT:
+ 				proc = range_overleft;
+ 				break;
+ 			case RANGESTRAT_OVERLAPS:
+ 				proc = range_overlaps;
+ 				break;
+ 			case RANGESTRAT_OVERRIGHT:
+ 				proc = range_overright;
+ 				break;
+ 			case RANGESTRAT_AFTER:
+ 				proc = range_after;
+ 				break;
+ 			case RANGESTRAT_ADJACENT:
+ 				proc = range_adjacent;
+ 				break;
+ 			case RANGESTRAT_CONTAINS:
+ 				proc = range_contains;
+ 				break;
+ 			case RANGESTRAT_CONTAINED_BY:
+ 				proc = range_contained_by;
+ 				break;
+ 			case RANGESTRAT_CONTAINS_ELEM:
+ 				proc = range_contains_elem;
+ 				break;
+ 			case RANGESTRAT_EQ:
+ 				proc = range_eq;
+ 				break;
+ 			default:
+ 				elog(ERROR, "unrecognized range strategy: %d", 
+ 												in->scankeys[i].sk_strategy);
+ 				proc = InvalidOid;
+ 				break;
+ 		}
+ 		res = DatumGetBool(TrickFunctionCall2(proc, fcinfo->flinfo,
+ 								in->leafDatum, in->scankeys[i].sk_argument));
+ 		
+ 		/* 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 (	3475   3831 3831 1 s	3893 4000 0 ));
+ DATA(insert (	3475   3831 3831 2 s	3895 4000 0 ));
+ DATA(insert (	3475   3831 3831 3 s	3888 4000 0 ));
+ DATA(insert (	3475   3831 3831 4 s	3896 4000 0 ));
+ DATA(insert (	3475   3831 3831 5 s	3894 4000 0 ));
+ DATA(insert (	3475   3831 3831 6 s	3897 4000 0 ));
+ DATA(insert (	3475   3831 3831 7 s	3890 4000 0 ));
+ DATA(insert (	3475   3831 3831 8 s	3892 4000 0 ));
+ DATA(insert (	3475   3831 2283 16 s	3889 4000 0 ));
+ DATA(insert (	3475   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 (	3475   3831 3831 1 3476 ));
+ DATA(insert (	3475   3831 3831 2 3477 ));
+ DATA(insert (	3475   3831 3831 3 3478 ));
+ DATA(insert (	3475   3831 3831 4 3479 ));
+ DATA(insert (	3475   3831 3831 5 3480 ));
  
  #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 3475  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 = 3475 (	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
***************
*** 4645,4650 **** DESCR("SP-GiST support for suffix tree over text");
--- 4645,4661 ----
  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 = 3476 (  spg_range_kd_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_kd_config _null_ _null_ _null_ ));
+ DESCR("SP-GiST support for k-d tree over range");
+ DATA(insert OID = 3477 (  spg_range_kd_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_kd_choose _null_ _null_ _null_ ));
+ DESCR("SP-GiST support for k-d tree over range");
+ DATA(insert OID = 3478 (  spg_range_kd_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_kd_picksplit _null_ _null_ _null_ ));
+ DESCR("SP-GiST support for k-d tree over range");
+ DATA(insert OID = 3479 (  spg_range_kd_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_kd_inner_consistent _null_ _null_ _null_ ));
+ DESCR("SP-GiST support for k-d tree over range");
+ DATA(insert OID = 3480 (  spg_range_kd_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_kd_leaf_consistent _null_ _null_ _null_ ));
+ DESCR("SP-GiST support for k-d 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
   */
***************
*** 166,171 **** extern int range_cmp_bound_values(TypeCacheEntry *typcache, RangeBound *b1,
--- 179,186 ----
  extern RangeType *make_empty_range(TypeCacheEntry *typcache);
  
  /* GiST support (in rangetypes_gist.c) */
+ extern Datum TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, 
+ 																	Datum arg2);
  extern Datum range_gist_consistent(PG_FUNCTION_ARGS);
  extern Datum range_gist_compress(PG_FUNCTION_ARGS);
  extern Datum range_gist_decompress(PG_FUNCTION_ARGS);
***************
*** 174,177 **** extern Datum range_gist_penalty(PG_FUNCTION_ARGS);
--- 189,199 ----
  extern Datum range_gist_picksplit(PG_FUNCTION_ARGS);
  extern Datum range_gist_same(PG_FUNCTION_ARGS);
  
+ /* SP-GiST k-d tree support (in rangetypes_spgistkd.c */
+ Datum spg_range_kd_config(PG_FUNCTION_ARGS);
+ Datum spg_range_kd_choose(PG_FUNCTION_ARGS);
+ Datum spg_range_kd_picksplit(PG_FUNCTION_ARGS);
+ Datum spg_range_kd_inner_consistent(PG_FUNCTION_ARGS);
+ Datum spg_range_kd_leaf_consistent(PG_FUNCTION_ARGS);
+ 
  #endif   /* RANGETYPES_H */