2d_map_range_indexing.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,37 ----
  	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_gist2.o \
! 	rangetypes_spgist.o rangetypes_spgistkd.o
  
  like.o: like.c like_match.c
  
*** a/src/backend/utils/adt/rangetypes.c
--- b/src/backend/utils/adt/rangetypes.c
***************
*** 40,60 ****
  #include "utils/rangetypes.h"
  #include "utils/timestamp.h"
  
- 
- #define RANGE_EMPTY_LITERAL "empty"
- 
- /* fn_extra cache entry for one of the range I/O functions */
- typedef struct RangeIOData
- {
- 	TypeCacheEntry *typcache;	/* range type's typcache entry */
- 	Oid			typiofunc;		/* element type's I/O function */
- 	Oid			typioparam;		/* element type's I/O parameter */
- 	FmgrInfo	proc;			/* lookup result for typiofunc */
- } RangeIOData;
- 
- 
- static RangeIOData *get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid,
- 				  IOFuncSelector func);
  static char range_parse_flags(const char *flags_str);
  static void range_parse(const char *input_str, char *flags, char **lbound_str,
  			char **ubound_str);
--- 40,45 ----
***************
*** 62,76 **** static const char *range_parse_bound(const char *string, const char *ptr,
  				  char **bound_str, bool *infinite);
  static char *range_deparse(char flags, const char *lbound_str,
  			  const char *ubound_str);
- static char *range_bound_escape(const char *value);
  static bool range_contains_internal(TypeCacheEntry *typcache,
  						RangeType *r1, RangeType *r2);
  static bool range_contains_elem_internal(TypeCacheEntry *typcache,
  							 RangeType *r, Datum val);
- static Size datum_compute_size(Size sz, Datum datum, bool typbyval,
- 				   char typalign, int16 typlen, char typstorage);
- static Pointer datum_write(Pointer ptr, Datum datum, bool typbyval,
- 			char typalign, int16 typlen, char typstorage);
  
  
  /*
--- 47,56 ----
***************
*** 292,298 **** range_send(PG_FUNCTION_ARGS)
   * functions, so they store a RangeIOData struct in fn_extra, not just a
   * pointer to a type cache entry.
   */
! static RangeIOData *
  get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, IOFuncSelector func)
  {
  	RangeIOData *cache = (RangeIOData *) fcinfo->flinfo->fn_extra;
--- 272,278 ----
   * functions, so they store a RangeIOData struct in fn_extra, not just a
   * pointer to a type cache entry.
   */
! RangeIOData *
  get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, IOFuncSelector func)
  {
  	RangeIOData *cache = (RangeIOData *) fcinfo->flinfo->fn_extra;
***************
*** 2103,2109 **** range_deparse(char flags, const char *lbound_str, const char *ubound_str)
   *
   * Result is a palloc'd string
   */
! static char *
  range_bound_escape(const char *value)
  {
  	bool		nq;
--- 2083,2089 ----
   *
   * Result is a palloc'd string
   */
! char *
  range_bound_escape(const char *value)
  {
  	bool		nq;
***************
*** 2238,2244 **** range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val)
   * Increment data_length by the space needed by the datum, including any
   * preceding alignment padding.
   */
! static Size
  datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign,
  				   int16 typlen, char typstorage)
  {
--- 2218,2224 ----
   * Increment data_length by the space needed by the datum, including any
   * preceding alignment padding.
   */
! Size
  datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign,
  				   int16 typlen, char typstorage)
  {
***************
*** 2264,2270 **** datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign,
   * Write the given datum beginning at ptr (after advancing to correct
   * alignment, if needed).  Return the pointer incremented by space used.
   */
! static Pointer
  datum_write(Pointer ptr, Datum datum, bool typbyval, char typalign,
  			int16 typlen, char typstorage)
  {
--- 2244,2250 ----
   * Write the given datum beginning at ptr (after advancing to correct
   * alignment, if needed).  Return the pointer incremented by space used.
   */
! Pointer
  datum_write(Pointer ptr, Datum datum, bool typbyval, char typalign,
  			int16 typlen, char typstorage)
  {
*** 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_gist2.c
***************
*** 0 ****
--- 1,1597 ----
+ /*-------------------------------------------------------------------------
+  *
+  * rangetypes_gist2.c
+  *	  GiST support for range types based on mapping range to 2d-space.
+  *
+  * 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_gist2.c
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "access/gist.h"
+ #include "access/tupmacs.h"
+ #include "access/skey.h"
+ #include "utils/builtins.h"
+ #include "utils/datum.h"
+ #include "utils/rangetypes.h"
+ 
+ /* Flags for GiST key representation */
+ #define RANGE_GIST_KEY_EMPTY			0x0001	/* all ranges in subtree are
+ 												 * empty */
+ #define RANGE_GIST_KEY_CONTAIN_EMPTY	0x0002	/* subtree may contain some
+ 												 * empty ranges */
+ #define RANGE_GIST_KEY_LEAF				0x0004	/* key are in short
+ 												 * representation for leaf
+ 												 * pages: single values for
+ 												 * both lower and upper bounds */
+ #define RANGE_GIST_KEY_LOWER_MIN_INC	0x0008	/* minimum value of lower
+ 												 * bound in subtree is
+ 												 * inclusive */
+ #define RANGE_GIST_KEY_LOWER_MIN_INF	0x0010	/* minimum value of lower
+ 												 * bound in subtree is
+ 												 * infinite */
+ #define RANGE_GIST_KEY_LOWER_MAX_INC	0x0020	/* maximum value of lower
+ 												 * bound in subtree is
+ 												 * inclusive */
+ #define RANGE_GIST_KEY_LOWER_MAX_INF	0x0040	/* maximum value of lower
+ 												 * bound in subtree is
+ 												 * infinite */
+ #define RANGE_GIST_KEY_UPPER_MIN_INC	0x0080	/* minimum value of upper
+ 												 * bound in subtree is
+ 												 * inclusive */
+ #define RANGE_GIST_KEY_UPPER_MIN_INF	0x0100	/* minimum value of upper
+ 												 * bound in subtree is
+ 												 * infinite */
+ #define RANGE_GIST_KEY_UPPER_MAX_INC	0x0200	/* maximum value of upper
+ 												 * bound in subtree is
+ 												 * inclusive */
+ #define RANGE_GIST_KEY_UPPER_MAX_INF	0x0400	/* maximum value of upper
+ 												 * bound in subtree is
+ 												 * infinite */
+ 
+ #define LIMIT_RATIO 0.3
+ 
+ /*
+  * GiST index key datatype. Represents box in virtual 2d-space.
+  */
+ typedef struct
+ {
+ 	int32		vl_len_;		/* varlena header (do not touch directly!) */
+ 	Oid			rangetypid;		/* range type's own OID */
+ 
+ 	/*
+ 	 * Following the OID are zero to four bound values, then a two bytes of
+ 	 * flags
+ 	 */
+ }	RangeGiSTKey;
+ 
+ #define DatumGetRangeGiSTKey(X)		((RangeGiSTKey *) PG_DETOAST_DATUM(X))
+ 
+ /* Structure of minimum and maximum values of bound in subtree */
+ typedef struct
+ {
+ 	RangeBound	min;
+ 	RangeBound	max;
+ }	RangeBoundMinMax;
+ 
+ /* Deserialized representation of GiST key */
+ typedef struct
+ {
+ 	bool		empty;			/* all ranges in subtree are empty */
+ 	bool		containEmpty;	/* subtree may contain some empty ranges */
+ 	bool		leaf;			/* key is leaf: minimum and maximum values are
+ 								 * equal */
+ 	RangeBoundMinMax lower;		/* minimum and maximum for lower bound value */
+ 	RangeBoundMinMax upper;		/* minimum and maximum for upper bound value */
+ }	RangeGiSTKeyDeserialized;
+ 
+ #define RangeBoundIntervalBoundHasValue(b) (!(b).infinite)
+ 
+ #define RangeBoundIntervalBoundAddValueSize(b) \
+ 	if (RangeBoundIntervalBoundHasValue(b)) \
+ 	{ \
+ 		if (typlen == -1) \
+ 			b.val = PointerGetDatum(PG_DETOAST_DATUM_PACKED(b.val)); \
+ 		msize = datum_compute_size(msize, b.val, typbyval, typalign, \
+ 								typlen, typstorage); \
+ 	}
+ 
+ #define RangeBoundIntervalBoundWriteValue(b) \
+ 	if (RangeBoundIntervalBoundHasValue(b)) \
+ 	{ \
+ 		ptr = datum_write(ptr, b.val, typbyval, typalign, typlen, \
+ 						  typstorage); \
+ 	}
+ 
+ static void range_gist_key_deserialize(TypeCacheEntry *typcache,
+ 					 RangeGiSTKey * gistKey, RangeGiSTKeyDeserialized * key);
+ static RangeGiSTKey *range_gist_key_serialize(TypeCacheEntry *typcache,
+ 						 RangeGiSTKeyDeserialized * key);
+ static RangeGiSTKey *range_get_gist_key(TypeCacheEntry *typcache,
+ 				   RangeType *range);
+ static void extend_gist_key(TypeCacheEntry *typcache,
+ 		  RangeGiSTKeyDeserialized * target, RangeGiSTKeyDeserialized * new);
+ static float8 get_bounds_extension(TypeCacheEntry *typcache, RangeBound *min, 
+ 					RangeBound *max, RangeBound *newmin, RangeBound *newmax);
+ static float8 get_bounds_size(TypeCacheEntry *typcache, RangeBound *min,
+ 															RangeBound *max);
+ 
+ /*
+  * Input function for GiST key type. We never allow to construct key from a
+  * string, so trigger an error.
+  */
+ Datum
+ grange_in(PG_FUNCTION_ARGS)
+ {
+ 	ereport(ERROR,
+ 			(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ 			 errmsg("grange_it not implemented")));
+ 	PG_RETURN_DATUM(0);
+ }
+ 
+ /*
+  * Output function for GiST key type. Can be useful for debugging.
+  */
+ Datum
+ grange_out(PG_FUNCTION_ARGS)
+ {
+ 	RangeGiSTKey *gistKey = DatumGetRangeGiSTKey(PG_GETARG_DATUM(0));
+ 	RangeIOData *cache;
+ 	char	   *lbound_min_str = NULL;
+ 	char	   *lbound_max_str = NULL;
+ 	char	   *ubound_min_str = NULL;
+ 	char	   *ubound_max_str = NULL;
+ 	RangeGiSTKeyDeserialized key;
+ 	StringInfoData buf;
+ 
+ 	cache = get_range_io_data(fcinfo, gistKey->rangetypid, IOFunc_output);
+ 
+ 	/* deserialize */
+ 	range_gist_key_deserialize(cache->typcache, gistKey, &key);
+ 
+ 	if (key.empty)
+ 		PG_RETURN_CSTRING(pstrdup(RANGE_EMPTY_LITERAL));
+ 	
+ 	/* call element type's output function */
+ 	if (!key.lower.min.infinite)
+ 		lbound_min_str = OutputFunctionCall(&cache->proc, key.lower.min.val);
+ 	if (!key.lower.max.infinite)
+ 		lbound_max_str = OutputFunctionCall(&cache->proc, key.lower.max.val);
+ 	if (!key.lower.min.infinite)
+ 		ubound_min_str = OutputFunctionCall(&cache->proc, key.upper.min.val);
+ 	if (!key.lower.max.infinite)
+ 		ubound_max_str = OutputFunctionCall(&cache->proc, key.upper.max.val);
+ 	
+ 	initStringInfo(&buf);	
+ 	appendStringInfoChar(&buf, '<');
+ 	appendStringInfoChar(&buf, key.lower.min.inclusive ? '[' : '(');
+ 	if (!key.lower.min.infinite)
+ 		appendStringInfoString(&buf, range_bound_escape(lbound_min_str));
+ 	appendStringInfoString(&buf, " - ");
+ 	if (!key.lower.max.infinite)
+ 		appendStringInfoString(&buf, range_bound_escape(lbound_max_str));
+ 	appendStringInfoChar(&buf, key.lower.max.inclusive ? '[' : '(');
+ 	appendStringInfoString(&buf, ">, <");
+ 	appendStringInfoChar(&buf, key.upper.min.inclusive ? '[' : '(');
+ 	if (!key.upper.min.infinite)
+ 		appendStringInfoString(&buf, range_bound_escape(ubound_min_str));
+ 	appendStringInfoString(&buf, " - ");
+ 	if (!key.upper.max.infinite)
+ 		appendStringInfoString(&buf, range_bound_escape(ubound_max_str));
+ 	appendStringInfoChar(&buf, key.upper.max.inclusive ? '[' : '(');
+ 	appendStringInfoChar(&buf, '>');
+ 
+ 	if (key.containEmpty)
+ 	{
+ 		appendStringInfoString(&buf, " | ");
+ 		appendStringInfoString(&buf, RANGE_EMPTY_LITERAL);
+ 	}
+ 
+ 	PG_RETURN_CSTRING(buf.data);
+ }
+ 
+ /*
+  * Get deserialized representation of GiST key.
+  */
+ static void
+ range_gist_key_deserialize(TypeCacheEntry *typcache, RangeGiSTKey * gistKey,
+ 						   RangeGiSTKeyDeserialized * key)
+ {
+ 	uint16		flags;
+ 	Pointer		ptr;
+ 	int16		typlen;
+ 	bool		typbyval;
+ 	char		typalign;
+ 
+ 	memset(key, 0, sizeof(RangeGiSTKeyDeserialized));
+ 
+ 	/* get flags from end of key */
+ 	flags = *((uint16 *) ((char *) gistKey + VARSIZE(gistKey)) - 1);
+ 
+ 	/* if empty flag is set no useful information in the rest of key */
+ 	if (flags & RANGE_GIST_KEY_EMPTY)
+ 	{
+ 		key->empty = true;
+ 		key->containEmpty = true;
+ 		return;
+ 	}
+ 
+ 	/* read other flag values */
+ 	if (flags & RANGE_GIST_KEY_CONTAIN_EMPTY)
+ 		key->containEmpty = true;
+ 
+ 	if (flags & RANGE_GIST_KEY_LOWER_MIN_INC)
+ 		key->lower.min.inclusive = true;
+ 	if (flags & RANGE_GIST_KEY_LOWER_MIN_INF)
+ 		key->lower.min.infinite = true;
+ 	key->lower.min.lower = true;
+ 
+ 	if (flags & RANGE_GIST_KEY_LOWER_MAX_INC)
+ 		key->lower.max.inclusive = true;
+ 	if (flags & RANGE_GIST_KEY_LOWER_MAX_INF)
+ 		key->lower.max.infinite = true;
+ 	key->lower.max.lower = true;
+ 
+ 	if (flags & RANGE_GIST_KEY_UPPER_MIN_INC)
+ 		key->upper.min.inclusive = true;
+ 	if (flags & RANGE_GIST_KEY_UPPER_MIN_INF)
+ 		key->upper.min.infinite = true;
+ 	key->upper.min.lower = false;
+ 
+ 	if (flags & RANGE_GIST_KEY_UPPER_MAX_INC)
+ 		key->upper.max.inclusive = true;
+ 	if (flags & RANGE_GIST_KEY_UPPER_MAX_INF)
+ 		key->upper.max.infinite = true;
+ 	key->upper.max.lower = false;
+ 
+ 	/* Fetch information about range's element type */
+ 	typlen = typcache->rngelemtype->typlen;
+ 	typbyval = typcache->rngelemtype->typbyval;
+ 	typalign = typcache->rngelemtype->typalign;
+ 
+ 	/* read bound values */
+ 	ptr = (Pointer) (gistKey + 1);
+ 	if (flags & RANGE_GIST_KEY_LEAF)
+ 	{
+ 		/* Leaf key contain single values for lower and upper bounds. */
+ 		key->leaf = true;
+ 		if (RangeBoundIntervalBoundHasValue(key->lower.min))
+ 		{
+ 			key->lower.min.val = fetch_att(ptr, typbyval, typlen);
+ 			key->lower.max.val = key->lower.min.val;
+ 			ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+ 		}
+ 		if (RangeBoundIntervalBoundHasValue(key->upper.min))
+ 		{
+ 			ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
+ 			key->upper.min.val = fetch_att(ptr, typbyval, typlen);
+ 			key->upper.max.val = key->upper.min.val;
+ 		}
+ 	}
+ 	else
+ 	{
+ 		/*
+ 		 * Internal key contain minimum and maximum bounds for lower and upper
+ 		 * bounds.
+ 		 */
+ 		if (RangeBoundIntervalBoundHasValue(key->lower.min))
+ 		{
+ 			key->lower.min.val = fetch_att(ptr, typbyval, typlen);
+ 			ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+ 		}
+ 		if (RangeBoundIntervalBoundHasValue(key->lower.max))
+ 		{
+ 			ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
+ 			key->lower.max.val = fetch_att(ptr, typbyval, typlen);
+ 			ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+ 		}
+ 		if (RangeBoundIntervalBoundHasValue(key->upper.min))
+ 		{
+ 			ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
+ 			key->upper.min.val = fetch_att(ptr, typbyval, typlen);
+ 			ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
+ 		}
+ 		if (RangeBoundIntervalBoundHasValue(key->upper.max))
+ 		{
+ 			ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
+ 			key->upper.max.val = fetch_att(ptr, typbyval, typlen);
+ 		}
+ 	}
+ }
+ 
+ /*
+  * Get serialized representation of GiST key.
+  */
+ static RangeGiSTKey *
+ range_gist_key_serialize(TypeCacheEntry *typcache, RangeGiSTKeyDeserialized * key)
+ {
+ 	uint16		flags = 0;
+ 	Size		msize;
+ 	int16		typlen;
+ 	bool		typbyval;
+ 	char		typalign;
+ 	char		typstorage;
+ 	RangeGiSTKey *gistKey;
+ 	Pointer		ptr;
+ 
+ 	/* Set flags */
+ 	if (key->empty)
+ 	{
+ 		flags |= RANGE_GIST_KEY_EMPTY;
+ 		flags |= RANGE_GIST_KEY_CONTAIN_EMPTY;
+ 	}
+ 	else
+ 	{
+ 		if (key->containEmpty)
+ 			flags |= RANGE_GIST_KEY_CONTAIN_EMPTY;
+ 
+ 		if (key->lower.min.inclusive)
+ 			flags |= RANGE_GIST_KEY_LOWER_MIN_INC;
+ 		if (key->lower.min.infinite)
+ 			flags |= RANGE_GIST_KEY_LOWER_MIN_INF;
+ 
+ 		if (key->lower.max.inclusive)
+ 			flags |= RANGE_GIST_KEY_LOWER_MAX_INC;
+ 		if (key->lower.max.infinite)
+ 			flags |= RANGE_GIST_KEY_LOWER_MAX_INF;
+ 
+ 		if (key->upper.min.inclusive)
+ 			flags |= RANGE_GIST_KEY_UPPER_MIN_INC;
+ 		if (key->upper.min.infinite)
+ 			flags |= RANGE_GIST_KEY_UPPER_MIN_INF;
+ 
+ 		if (key->upper.max.inclusive)
+ 			flags |= RANGE_GIST_KEY_UPPER_MAX_INC;
+ 		if (key->upper.max.infinite)
+ 			flags |= RANGE_GIST_KEY_UPPER_MAX_INF;
+ 	}
+ 
+ 	/* Fetch information about range's element type */
+ 	typlen = typcache->rngelemtype->typlen;
+ 	typbyval = typcache->rngelemtype->typbyval;
+ 	typalign = typcache->rngelemtype->typalign;
+ 	typstorage = typcache->rngelemtype->typstorage;
+ 
+ 	/* Calculate required memory size */
+ 	msize = sizeof(RangeGiSTKey);
+ 	if (!key->empty)
+ 	{
+ 		RangeBoundIntervalBoundAddValueSize(key->lower.min);
+ 		RangeBoundIntervalBoundAddValueSize(key->lower.max);
+ 		RangeBoundIntervalBoundAddValueSize(key->upper.min);
+ 		RangeBoundIntervalBoundAddValueSize(key->upper.max);
+ 	}
+ 	msize = SHORTALIGN(msize);
+ 	msize += sizeof(flags);
+ 
+ 	/* Allocate memory and write serialized value */
+ 	gistKey = (RangeGiSTKey *) palloc0(msize);
+ 	SET_VARSIZE(gistKey, msize);
+ 
+ 	gistKey->rangetypid = typcache->type_id;
+ 
+ 	ptr = (Pointer) (gistKey + 1);
+ 
+ 	if (!key->empty)
+ 	{
+ 		RangeBoundIntervalBoundWriteValue(key->lower.min);
+ 		RangeBoundIntervalBoundWriteValue(key->lower.max);
+ 		RangeBoundIntervalBoundWriteValue(key->upper.min);
+ 		RangeBoundIntervalBoundWriteValue(key->upper.max);
+ 	}
+ 
+ 	ptr = (Pointer) SHORTALIGN(ptr);
+ 	*((uint16 *) ptr) = flags;
+ 
+ 	return gistKey;
+ }
+ 
+ /*
+  * Get leaf GiST key by range value.
+  */
+ static RangeGiSTKey *
+ range_get_gist_key(TypeCacheEntry *typcache, RangeType *range)
+ {
+ 	uint16		flags = 0;
+ 	Size		msize;
+ 	int16		typlen;
+ 	bool		typbyval;
+ 	char		typalign;
+ 	char		typstorage;
+ 	Pointer		ptr;
+ 	RangeBound	upper,
+ 				lower;
+ 	bool		empty;
+ 	RangeGiSTKey *gistKey;
+ 
+ 	range_deserialize(typcache, range, &lower, &upper, &empty);
+ 
+ 	/* Fill flags */
+ 	if (empty)
+ 	{
+ 		flags |= RANGE_GIST_KEY_EMPTY;
+ 		flags |= RANGE_GIST_KEY_CONTAIN_EMPTY;
+ 	}
+ 	else
+ 	{
+ 		flags |= RANGE_GIST_KEY_LEAF;
+ 		if (lower.inclusive)
+ 		{
+ 			flags |= RANGE_GIST_KEY_LOWER_MIN_INC;
+ 			flags |= RANGE_GIST_KEY_LOWER_MAX_INC;
+ 		}
+ 		if (lower.infinite)
+ 		{
+ 			flags |= RANGE_GIST_KEY_LOWER_MIN_INF;
+ 			flags |= RANGE_GIST_KEY_LOWER_MAX_INF;
+ 		}
+ 		if (upper.inclusive)
+ 		{
+ 			flags |= RANGE_GIST_KEY_UPPER_MIN_INC;
+ 			flags |= RANGE_GIST_KEY_UPPER_MAX_INC;
+ 		}
+ 		if (upper.infinite)
+ 		{
+ 			flags |= RANGE_GIST_KEY_UPPER_MIN_INF;
+ 			flags |= RANGE_GIST_KEY_UPPER_MAX_INF;
+ 		}
+ 	}
+ 
+ 	/* Fetch information about range's element type */
+ 	typlen = typcache->rngelemtype->typlen;
+ 	typbyval = typcache->rngelemtype->typbyval;
+ 	typalign = typcache->rngelemtype->typalign;
+ 	typstorage = typcache->rngelemtype->typstorage;
+ 
+ 	/* Calculate required memory size */
+ 	msize = sizeof(RangeGiSTKey);
+ 
+ 	if (!empty)
+ 	{
+ 		RangeBoundIntervalBoundAddValueSize(lower);
+ 		RangeBoundIntervalBoundAddValueSize(upper);
+ 	}
+ 
+ 	msize = SHORTALIGN(msize);
+ 	msize += sizeof(flags);
+ 
+ 	/* Allocate memory and write value */
+ 	gistKey = (RangeGiSTKey *) palloc0(msize);
+ 	SET_VARSIZE(gistKey, msize);
+ 
+ 	gistKey->rangetypid = typcache->type_id;
+ 
+ 	ptr = (Pointer) (gistKey + 1);
+ 
+ 	if (!empty)
+ 	{
+ 		RangeBoundIntervalBoundWriteValue(lower);
+ 		RangeBoundIntervalBoundWriteValue(upper);
+ 	}
+ 
+ 	ptr = (Pointer) SHORTALIGN(ptr);
+ 	*((uint16 *) ptr) = flags;
+ 
+ 	return gistKey;
+ }
+ 
+ /*
+  * GiST compress function. Converts input ranges to key type.
+  */
+ Datum
+ range_gist2_compress(PG_FUNCTION_ARGS)
+ {
+ 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ 	GISTENTRY  *retval = entry;
+ 
+ 	if (entry->leafkey)
+ 	{
+ 		RangeType  *range;
+ 		RangeGiSTKey *key;
+ 		TypeCacheEntry *typcache;
+ 
+ 		range = DatumGetRangeType(entry->key);
+ 		typcache = range_get_typcache(fcinfo, RangeTypeGetOid(range));
+ 		key = range_get_gist_key(typcache, range);
+ 		retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
+ 		gistentryinit(*retval, PointerGetDatum(key),
+ 					  entry->rel, entry->page,
+ 					  entry->offset, FALSE);
+ 	}
+ 	PG_RETURN_POINTER(retval);
+ }
+ 
+ /*
+  * GiST decompress function. Do nothing.
+  */
+ Datum
+ range_gist2_decompress(PG_FUNCTION_ARGS)
+ {
+ 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ 
+ 	PG_RETURN_POINTER(entry);
+ }
+ 
+ /*
+  * Extends deserialized GiST key with another deserialized GiST key. As the
+  * result "target" key will contain "new" key.
+  */
+ static void
+ extend_gist_key(TypeCacheEntry *typcache, RangeGiSTKeyDeserialized * target,
+ 				RangeGiSTKeyDeserialized * new)
+ {
+ 	/* Take care about "empty" and "containEmpty" flags */
+ 	if (new->empty)
+ 	{
+ 		target->containEmpty = true;
+ 		return;
+ 	}
+ 	if (target->empty)
+ 	{
+ 		target->lower = new->lower;
+ 		target->upper = new->upper;
+ 		target->empty = false;
+ 		target->containEmpty = true;
+ 		return;
+ 	}
+ 	if (new->containEmpty)
+ 		target->containEmpty = true;
+ 
+ 	/* Replace interval values with wider ones */
+ 	if (range_cmp_bounds(typcache, &target->lower.min, &new->lower.min) > 0)
+ 		target->lower.min = new->lower.min;
+ 	if (range_cmp_bounds(typcache, &target->lower.max, &new->lower.max) < 0)
+ 		target->lower.max = new->lower.max;
+ 	if (range_cmp_bounds(typcache, &target->upper.min, &new->upper.min) > 0)
+ 		target->upper.min = new->upper.min;
+ 	if (range_cmp_bounds(typcache, &target->upper.max, &new->upper.max) < 0)
+ 		target->upper.max = new->upper.max;
+ }
+ 
+ /*
+  * GiST union function.
+  */
+ Datum
+ range_gist2_union(PG_FUNCTION_ARGS)
+ {
+ 	GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
+ 	GISTENTRY  *ent = entryvec->vector;
+ 	RangeGiSTKeyDeserialized target,
+ 				new;
+ 	TypeCacheEntry *typcache;
+ 	int			i;
+ 
+ 	typcache = range_get_typcache(fcinfo, DatumGetRangeGiSTKey(ent[0].key)->rangetypid);
+ 	range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(ent[0].key), &target);
+ 
+ 	for (i = 1; i < entryvec->n; i++)
+ 	{
+ 		range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(ent[i].key), &new);
+ 		extend_gist_key(typcache, &target, &new);
+ 	}
+ 
+ 	PG_RETURN_POINTER(range_gist_key_serialize(typcache, &target));
+ }
+ 
+ /*
+  * Represents information about an entry that can be placed to either group
+  * without affecting overlap over selected axis ("common entry").
+  */
+ typedef struct
+ {
+ 	/* Index of entry in the initial array */
+ 	int			index;
+ 	/* Delta between penalties of entry insertion into different groups */
+ 	float8		delta;
+ } CommonEntry;
+ 
+ /*
+  * Context for g_box_consider_split. Contains information about currently
+  * selected split and some general information.
+  */
+ typedef struct
+ {
+ 	int			entriesCount;	/* total number of entries being split */
+ 	TypeCacheEntry *typcache;
+ 	bool		has_subtype_diff;
+ 	RangeGiSTKeyDeserialized boundingBox;		/* minimum bounding box across
+ 												 * all entries */
+ 
+ 	/* Information about currently selected split follows */
+ 
+ 	bool		first;			/* true if no split was selected yet */
+ 
+ 	RangeBound	leftMax;		/* upper bound of left interval */
+ 	RangeBound	rightMin;		/* lower bound of right interval */
+ 
+ 	float4		ratio;
+ 	float8		overlap;
+ 	int			dim;			/* axis of this split */
+ 	double		range;			/* width of general MBR projection to the
+ 								 * selected axis */
+ } ConsiderSplitContext;
+ 
+ /*
+  * Interval comparison function by lower bound of the interval;
+  */
+ static int
+ interval_cmp_lower(const void *i1, const void *i2, void *arg)
+ {
+ 	RangeBound *min1 = &((RangeBoundMinMax *) i1)->min,
+ 			   *min2 = &((RangeBoundMinMax *) i2)->min;
+ 
+ 	return range_cmp_bounds((TypeCacheEntry *) arg, min1, min2);
+ }
+ 
+ /*
+  * Interval comparison function by upper bound of the interval;
+  */
+ static int
+ interval_cmp_upper(const void *i1, const void *i2, void *arg)
+ {
+ 	RangeBound *max1 = &((RangeBoundMinMax *) i1)->max,
+ 			   *max2 = &((RangeBoundMinMax *) i2)->max;
+ 
+ 	return range_cmp_bounds((TypeCacheEntry *) arg, max1, max2);
+ }
+ 
+ /*
+  * Replace negative value with zero.
+  */
+ static inline float8
+ non_negative(float8 val)
+ {
+ 	if (val >= 0.0f)
+ 		return val;
+ 	else
+ 		return 0.0f;
+ }
+ 
+ /*
+  * Convenience function to invoke type-specific subtype_diff function.
+  * Caller must have already checked that there is one for the range type.
+  */
+ static float8
+ call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
+ {
+ 	float8		value;
+ 
+ 	value = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
+ 											 typcache->rng_collation,
+ 											 val1, val2));
+ 	/* Cope with buggy subtype_diff function by returning zero */
+ 	if (value >= 0.0)
+ 		return value;
+ 	return 0.0;
+ }
+ 
+ /*
+  * Consider replacement of currently selected split with the better one.
+  */
+ static void inline
+ range_gist2_consider_split(ConsiderSplitContext *context, int dimNum,
+ 						   RangeBound rightMin, int minLeftCount,
+ 						   RangeBound leftMax, int maxLeftCount,
+ 						   float8 range)
+ {
+ 	int			leftCount,
+ 				rightCount;
+ 	float4		ratio;
+ 	float8		overlap;
+ 
+ 	/*
+ 	 * Calculate entries distribution ratio assuming most uniform distribution
+ 	 * of common entries.
+ 	 */
+ 	if (minLeftCount >= (context->entriesCount + 1) / 2)
+ 	{
+ 		leftCount = minLeftCount;
+ 	}
+ 	else
+ 	{
+ 		if (maxLeftCount <= context->entriesCount / 2)
+ 			leftCount = maxLeftCount;
+ 		else
+ 			leftCount = context->entriesCount / 2;
+ 	}
+ 	rightCount = context->entriesCount - leftCount;
+ 
+ 	/*
+ 	 * Ratio of split - quotient between size of lesser group and total
+ 	 * entries count.
+ 	 */
+ 	ratio = ((float4) Min(leftCount, rightCount)) /
+ 		((float4) context->entriesCount);
+ 
+ 	if (ratio > LIMIT_RATIO)
+ 	{
+ 		bool		selectthis = false;
+ 
+ 		/*
+ 		 * The ratio is acceptable, so compare current split with previously
+ 		 * selected one. Between splits of one dimension we search for minimal
+ 		 * overlap (allowing negative values) and minimal ration (between same
+ 		 * overlaps. We switch dimension if find less overlap (non-negative)
+ 		 * or less range with same overlap.
+ 		 */
+ 		if (range_cmp_bounds(context->typcache, &leftMax, &rightMin) > 0)
+ 			overlap = get_bounds_size(context->typcache, &leftMax, &rightMin) / range;
+ 		else
+ 			overlap = 0.0;
+ 
+ 		/* If there is no previous selection, select this */
+ 		if (context->first)
+ 			selectthis = true;
+ 		else if (context->dim == dimNum)
+ 		{
+ 			/*
+ 			 * Within the same dimension, choose the new split if it has a
+ 			 * smaller overlap, or same overlap but better ratio.
+ 			 */
+ 			if (overlap < context->overlap ||
+ 				(overlap == context->overlap && ratio > context->ratio))
+ 				selectthis = true;
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * Across dimensions, choose the new split if it has a smaller
+ 			 * *non-negative* overlap, or same *non-negative* overlap but
+ 			 * bigger range. This condition differs from the one described in
+ 			 * the article. On the datasets where leaf MBRs don't overlap
+ 			 * themselves, non-overlapping splits (i.e. splits which have zero
+ 			 * *non-negative* overlap) are frequently possible. In this case
+ 			 * splits tends to be along one dimension, because most distant
+ 			 * non-overlapping splits (i.e. having lowest negative overlap)
+ 			 * appears to be in the same dimension as in the previous split.
+ 			 * Therefore MBRs appear to be very prolonged along another
+ 			 * dimension, which leads to bad search performance. Using range
+ 			 * as the second split criteria makes MBRs more quadratic. Using
+ 			 * *non-negative* overlap instead of overlap as the first split
+ 			 * criteria gives to range criteria a chance to matter, because
+ 			 * non-overlapping splits are equivalent in this criteria.
+ 			 */
+ 			if (non_negative(overlap) < non_negative(context->overlap) ||
+ 				(range > context->range &&
+ 				 non_negative(overlap) <= non_negative(context->overlap)))
+ 				selectthis = true;
+ 		}
+ 
+ 		if (selectthis)
+ 		{
+ 			/* save information about selected split */
+ 			context->first = false;
+ 			context->ratio = ratio;
+ 			context->range = range;
+ 			context->overlap = overlap;
+ 			context->rightMin = rightMin;
+ 			context->leftMax = leftMax;
+ 			context->dim = dimNum;
+ 		}
+ 	}
+ }
+ 
+ /*
+  * Return increase of original GiST key "area" by new range insertion.
+  */
+ static float8
+ range_gist_key_penalty(TypeCacheEntry *typcache, RangeGiSTKeyDeserialized * orig, RangeGiSTKeyDeserialized * new)
+ {
+ 	float8 lower_size, upper_size, lower_extent, upper_extent;
+ 	
+ 	lower_size = get_bounds_size(typcache, &orig->lower.min, &orig->lower.max);
+ 	upper_size = get_bounds_size(typcache, &orig->upper.min, &orig->upper.max);
+ 	
+ 	lower_extent = get_bounds_extension(typcache, &orig->lower.min, &orig->lower.max, 
+ 												&new->lower.min, &new->lower.max);
+ 	upper_extent = get_bounds_extension(typcache, &orig->upper.min, &orig->upper.max,
+ 												&new->upper.min, &new->upper.max);
+ 	
+ 	/* get area of extension with accurate handling of infinities */
+ 	if (lower_extent > 0 && upper_extent > 0)
+ 	{
+ 		if (is_infinite(lower_size) || is_infinite(upper_size))
+ 			return get_float8_infinity();
+ 		else
+ 			return (lower_size + lower_extent) * (upper_size + upper_extent)
+ 				   - lower_size * upper_size;
+ 	}
+ 	else if (lower_extent > 0)
+ 	{
+ 		if (upper_size > 0)
+ 			return lower_extent * upper_size;
+ 		else
+ 			return 0.0;
+ 	}
+ 	else if (upper_extent > 0)
+ 	{
+ 		if (lower_size > 0)
+ 			return upper_extent * lower_size;
+ 		else
+ 			return 0.0;
+ 	}
+ 	else
+ 	{
+ 		return 0.0;
+ 	}
+ }
+ 
+ /*
+  * Compare common entries by their deltas.
+  */
+ static int
+ common_entry_cmp(const void *i1, const void *i2)
+ {
+ 	double		delta1 = ((const CommonEntry *) i1)->delta,
+ 				delta2 = ((const CommonEntry *) i2)->delta;
+ 
+ 	if (delta1 < delta2)
+ 		return -1;
+ 	else if (delta1 > delta2)
+ 		return 1;
+ 	else
+ 		return 0;
+ }
+ 
+  /* Helper macros to place an entry in the left or right group */
+ #define PLACE_LEFT(key, off)					\
+ 	do {										\
+ 		if (v->spl_nleft > 0)					\
+ 			extend_gist_key(typcache, &leftKey, &key);			\
+ 		else									\
+ 			leftKey = key;					\
+ 		v->spl_left[v->spl_nleft++] = off;		\
+ 	} while(0)
+ 
+ #define PLACE_RIGHT(key, off)					\
+ 	do {										\
+ 		if (v->spl_nright > 0)					\
+ 			extend_gist_key(typcache, &rightKey, &key);			\
+ 		else									\
+ 			rightKey = key;					\
+ 		v->spl_right[v->spl_nright++] = off;	\
+ 	} while(0)
+ 
+ /*
+  * Trivial split: half of entries will be placed on one page
+  * and the other half on the other page.
+  */
+ static void
+ range_gist2_fallback_split(TypeCacheEntry *typcache,
+ 						   GistEntryVector *entryvec,
+ 						   GIST_SPLITVEC *v)
+ {
+ 	RangeGiSTKeyDeserialized leftKey;
+ 	RangeGiSTKeyDeserialized rightKey;
+ 	OffsetNumber i,
+ 				maxoff,
+ 				splitIdx;
+ 
+ 	maxoff = entryvec->n - 1;
+ 	/* Split entries before this to left page, after to right: */
+ 	splitIdx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;
+ 
+ 	v->spl_nleft = 0;
+ 	v->spl_nright = 0;
+ 	for (i = FirstOffsetNumber; i <= maxoff; i++)
+ 	{
+ 		RangeGiSTKeyDeserialized key;
+ 
+ 		range_gist_key_deserialize(typcache,
+ 						DatumGetRangeGiSTKey(entryvec->vector[i].key), &key);
+ 
+ 		if (i < splitIdx)
+ 			PLACE_LEFT(key, i);
+ 		else
+ 			PLACE_RIGHT(key, i);
+ 	}
+ 
+ 	v->spl_ldatum = PointerGetDatum(range_gist_key_serialize(typcache, &leftKey));
+ 	v->spl_rdatum = PointerGetDatum(range_gist_key_serialize(typcache, &rightKey));
+ }
+ 
+ /*
+  * Empty entries will be placed to one page and non-empty entries will be
+  * placed to another page.
+  */
+ static void
+ range_gist2_empty_split(TypeCacheEntry *typcache,
+ 						GistEntryVector *entryvec,
+ 						GIST_SPLITVEC *v)
+ {
+ 	RangeGiSTKeyDeserialized leftKey;
+ 	RangeGiSTKeyDeserialized rightKey;
+ 	OffsetNumber i,
+ 				maxoff;
+ 
+ 	maxoff = entryvec->n - 1;
+ 	v->spl_nleft = 0;
+ 	v->spl_nright = 0;
+ 	for (i = FirstOffsetNumber; i <= maxoff; i++)
+ 	{
+ 		RangeGiSTKeyDeserialized key;
+ 
+ 		range_gist_key_deserialize(typcache,
+ 						DatumGetRangeGiSTKey(entryvec->vector[i].key), &key);
+ 
+ 		if (key.empty)
+ 			PLACE_LEFT(key, i);
+ 		else
+ 			PLACE_RIGHT(key, i);
+ 	}
+ 
+ 	v->spl_ldatum = PointerGetDatum(range_gist_key_serialize(typcache, &leftKey));
+ 	v->spl_rdatum = PointerGetDatum(range_gist_key_serialize(typcache, &rightKey));
+ }
+ 
+ /*
+  * GiST picksplit function.
+  */
+ Datum
+ range_gist2_picksplit(PG_FUNCTION_ARGS)
+ {
+ 	GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
+ 	GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
+ 	OffsetNumber i,
+ 				maxoff;
+ 	ConsiderSplitContext context;
+ 	RangeGiSTKeyDeserialized key,
+ 				leftKey,
+ 				rightKey;
+ 	int			dim,
+ 				commonEntriesCount;
+ 	RangeBoundMinMax *intervalsLower,
+ 			   *intervalsUpper;
+ 	CommonEntry *commonEntries;
+ 	int			nentries,
+ 				emptyCount = 0;
+ 	TypeCacheEntry *typcache;
+ 
+ 	typcache = range_get_typcache(fcinfo, DatumGetRangeGiSTKey(
+ 					   entryvec->vector[FirstOffsetNumber].key)->rangetypid);
+ 
+ 	memset(&context, 0, sizeof(ConsiderSplitContext));
+ 
+ 	maxoff = entryvec->n - 1;
+ 	nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
+ 
+ 	/*
+ 	 * Calculate the overall minimum bounding box over all the entries.
+ 	 */
+ 	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ 	{
+ 		range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[i].key), &key);
+ 
+ 		if (key.empty)
+ 			emptyCount++;
+ 
+ 		if (i == FirstOffsetNumber)
+ 			context.boundingBox = key;
+ 		else
+ 			extend_gist_key(typcache, &context.boundingBox, &key);
+ 	}
+ 
+ 	/* Allocate vectors for results */
+ 	v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
+ 	v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
+ 	v->spl_nleft = 0;
+ 	v->spl_nright = 0;
+ 
+ 	if (emptyCount > 0)
+ 	{
+ 		if (emptyCount == nentries)
+ 		{
+ 			range_gist2_fallback_split(typcache, entryvec, v);
+ 			PG_RETURN_POINTER(v);
+ 		}
+ 		else
+ 		{
+ 			range_gist2_empty_split(typcache, entryvec, v);
+ 			PG_RETURN_POINTER(v);
+ 		}
+ 	}
+ 
+ 
+ 	/*
+ 	 * Iterate over axes for optimal split searching.
+ 	 */
+ 	context.first = true;		/* nothing selected yet */
+ 	context.typcache = typcache;
+ 	context.has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
+ 	/* Allocate arrays for intervals along axes */
+ 	intervalsLower = (RangeBoundMinMax *) palloc(nentries * sizeof(RangeBoundMinMax));
+ 	intervalsUpper = (RangeBoundMinMax *) palloc(nentries * sizeof(RangeBoundMinMax));
+ 
+ 	for (dim = 0; dim < 2; dim++)
+ 	{
+ 		RangeBound	leftUpper,
+ 					rightLower;
+ 		int			i1,
+ 					i2;
+ 		float8		range;
+ 
+ 		if (dim == 0)
+ 			range = get_bounds_size(typcache,
+ 									  &context.boundingBox.lower.max,
+ 									  &context.boundingBox.lower.min);
+ 		else
+ 			range = get_bounds_size(typcache,
+ 									  &context.boundingBox.upper.max,
+ 									  &context.boundingBox.upper.min);
+ 
+ 		/* Project each entry as an interval on the selected axis. */
+ 		for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ 		{
+ 			range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[i].key), &key);
+ 
+ 			if (dim == 0)
+ 				intervalsLower[i - FirstOffsetNumber] = key.lower;
+ 			else
+ 				intervalsLower[i - FirstOffsetNumber] = key.upper;
+ 		}
+ 
+ 		/*
+ 		 * Make two arrays of intervals: one sorted by lower bound and another
+ 		 * sorted by upper bound.
+ 		 */
+ 		memcpy(intervalsUpper, intervalsLower,
+ 			   sizeof(RangeBoundMinMax) * nentries);
+ 		qsort_arg(intervalsLower, nentries, sizeof(RangeBoundMinMax),
+ 				  interval_cmp_lower, typcache);
+ 		qsort_arg(intervalsUpper, nentries, sizeof(RangeBoundMinMax),
+ 				  interval_cmp_upper, typcache);
+ 
+ 		/*----
+ 		 * The goal is to form a left and right interval, so that every entry
+ 		 * interval is contained by either left or right interval (or both).
+ 		 *
+ 		 * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
+ 		 *
+ 		 * 0 1 2 3 4
+ 		 * +-+
+ 		 *	 +---+
+ 		 *	   +-+
+ 		 *	   +---+
+ 		 *
+ 		 * The left and right intervals are of the form (0,a) and (b,4).
+ 		 * We first consider splits where b is the lower bound of an entry.
+ 		 * We iterate through all entries, and for each b, calculate the
+ 		 * smallest possible a. Then we consider splits where a is the
+ 		 * uppper bound of an entry, and for each a, calculate the greatest
+ 		 * possible b.
+ 		 *
+ 		 * In the above example, the first loop would consider splits:
+ 		 * b=0: (0,1)-(0,4)
+ 		 * b=1: (0,1)-(1,4)
+ 		 * b=2: (0,3)-(2,4)
+ 		 *
+ 		 * And the second loop:
+ 		 * a=1: (0,1)-(1,4)
+ 		 * a=3: (0,3)-(2,4)
+ 		 * a=4: (0,4)-(2,4)
+ 		 */
+ 
+ 		/*
+ 		 * Iterate over lower bound of right group, finding smallest possible
+ 		 * upper bound of left group.
+ 		 */
+ 		i1 = 0;
+ 		i2 = 0;
+ 		rightLower = intervalsLower[i1].min;
+ 		leftUpper = intervalsUpper[i2].min;
+ 		while (true)
+ 		{
+ 			/*
+ 			 * Find next lower bound of right group.
+ 			 */
+ 			while (i1 < nentries && range_cmp_bounds(typcache, &rightLower, &intervalsLower[i1].min) == 0)
+ 			{
+ 				if (range_cmp_bounds(typcache, &leftUpper, &intervalsLower[i1].max) < 0)
+ 					leftUpper = intervalsLower[i1].max;
+ 				i1++;
+ 			}
+ 			if (i1 >= nentries)
+ 				break;
+ 			rightLower = intervalsLower[i1].min;
+ 
+ 			/*
+ 			 * Find count of intervals which anyway should be placed to the
+ 			 * left group.
+ 			 */
+ 			while (i2 < nentries && range_cmp_bounds(typcache, &intervalsUpper[i2].max, &leftUpper) <= 0)
+ 				i2++;
+ 
+ 			/*
+ 			 * Consider found split.
+ 			 */
+ 			range_gist2_consider_split(&context, dim, rightLower, i1, leftUpper, i2, range);
+ 		}
+ 
+ 		/*
+ 		 * Iterate over upper bound of left group finding greates possible
+ 		 * lower bound of right group.
+ 		 */
+ 		i1 = nentries - 1;
+ 		i2 = nentries - 1;
+ 		rightLower = intervalsLower[i1].max;
+ 		leftUpper = intervalsUpper[i2].max;
+ 		while (true)
+ 		{
+ 			/*
+ 			 * Find next upper bound of left group.
+ 			 */
+ 			while (i2 >= 0 && range_cmp_bounds(typcache, &leftUpper, &intervalsUpper[i2].max) == 0)
+ 			{
+ 				if (range_cmp_bounds(typcache, &rightLower, &intervalsUpper[i2].min) > 0)
+ 					rightLower = intervalsUpper[i2].min;
+ 				i2--;
+ 			}
+ 			if (i2 < 0)
+ 				break;
+ 			leftUpper = intervalsUpper[i2].max;
+ 
+ 			/*
+ 			 * Find count of intervals which anyway should be placed to the
+ 			 * right group.
+ 			 */
+ 			while (i1 >= 0 &&
+ 				   range_cmp_bounds(typcache, &intervalsLower[i1].min, &rightLower) >= 0)
+ 				i1--;
+ 
+ 			/*
+ 			 * Consider found split.
+ 			 */
+ 			range_gist2_consider_split(&context, dim,
+ 							   rightLower, i1 + 1, leftUpper, i2 + 1, range);
+ 		}
+ 	}
+ 
+ 	/*
+ 	 * If we failed to find any acceptable splits, use trivial split.
+ 	 */
+ 	if (context.first)
+ 	{
+ 		range_gist2_fallback_split(typcache, entryvec, v);
+ 		PG_RETURN_POINTER(v);
+ 	}
+ 
+ 	/*
+ 	 * Ok, we have now selected the split across one axis.
+ 	 *
+ 	 * While considering the splits, we already determined that there will be
+ 	 * enough entries in both groups to reach the desired ratio, but we did
+ 	 * not memorize which entries go to which group. So determine that now.
+ 	 */
+ 
+ 	/*
+ 	 * Allocate an array for "common entries" - entries which can be placed to
+ 	 * either group without affecting overlap along selected axis.
+ 	 */
+ 	commonEntriesCount = 0;
+ 	commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
+ 
+ 	/*
+ 	 * Distribute entries which can be distributed unambiguously, and collect
+ 	 * common entries.
+ 	 */
+ 	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ 	{
+ 		RangeBound	lower,
+ 					upper;
+ 
+ 		/*
+ 		 * Get upper and lower bounds along selected axis.
+ 		 */
+ 		range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[i].key), &key);
+ 		if (context.dim == 0)
+ 		{
+ 			lower = key.lower.min;
+ 			upper = key.lower.max;
+ 		}
+ 		else
+ 		{
+ 			lower = key.upper.min;
+ 			upper = key.upper.max;
+ 		}
+ 
+ 		if (range_cmp_bounds(typcache, &upper, &context.leftMax) <= 0)
+ 		{
+ 			/* Fits to the left group */
+ 			if (range_cmp_bounds(typcache, &lower, &context.rightMin) >= 0)
+ 			{
+ 				/* Fits also to the right group, so "common entry" */
+ 				commonEntries[commonEntriesCount++].index = i;
+ 			}
+ 			else
+ 			{
+ 				/* Doesn't fit to the right group, so join to the left group */
+ 				PLACE_LEFT(key, i);
+ 			}
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * Each entry should fit on either left or right group. Since this
+ 			 * entry didn't fit on the left group, it better fit in the right
+ 			 * group.
+ 			 */
+ 			Assert(range_cmp_bounds(typcache, &lower, &context.rightMin) >= 0);
+ 
+ 			/* Doesn't fit to the left group, so join to the right group */
+ 			PLACE_RIGHT(key, i);
+ 		}
+ 	}
+ 
+ 	/*
+ 	 * Distribute "common entries", if any.
+ 	 */
+ 	if (commonEntriesCount > 0)
+ 	{
+ 		/*
+ 		 * Calculate minimum number of entries that must be placed in both
+ 		 * groups, to reach LIMIT_RATIO.
+ 		 */
+ 		int			m = ceil(LIMIT_RATIO * (double) nentries);
+ 
+ 		/*
+ 		 * Calculate delta between penalties of join "common entries" to
+ 		 * different groups.
+ 		 */
+ 		for (i = 0; i < commonEntriesCount; i++)
+ 		{
+ 			range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[commonEntries[i].index].key), &key);
+ 			commonEntries[i].delta = Abs(range_gist_key_penalty(typcache, &leftKey, &key) -
+ 						  range_gist_key_penalty(typcache, &rightKey, &key));
+ 		}
+ 
+ 		/*
+ 		 * Sort "common entries" by calculated deltas in order to distribute
+ 		 * the most ambiguous entries first.
+ 		 */
+ 		qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
+ 
+ 		/*
+ 		 * Distribute "common entries" between groups.
+ 		 */
+ 		for (i = 0; i < commonEntriesCount; i++)
+ 		{
+ 			range_gist_key_deserialize(typcache, DatumGetRangeGiSTKey(entryvec->vector[commonEntries[i].index].key), &key);
+ 
+ 			/*
+ 			 * Check if we have to place this entry in either group to achieve
+ 			 * LIMIT_RATIO.
+ 			 */
+ 			if (v->spl_nleft + (commonEntriesCount - i) <= m)
+ 				PLACE_LEFT(key, commonEntries[i].index);
+ 			else if (v->spl_nright + (commonEntriesCount - i) <= m)
+ 				PLACE_RIGHT(key, commonEntries[i].index);
+ 			else
+ 			{
+ 				/* Otherwise select the group by minimal penalty */
+ 				if (range_gist_key_penalty(typcache, &leftKey, &key) <
+ 					range_gist_key_penalty(typcache, &rightKey, &key))
+ 					PLACE_LEFT(key, commonEntries[i].index);
+ 				else
+ 					PLACE_RIGHT(key, commonEntries[i].index);
+ 			}
+ 		}
+ 	}
+ 
+ 	v->spl_ldatum = PointerGetDatum(range_gist_key_serialize(typcache, &leftKey));
+ 	v->spl_rdatum = PointerGetDatum(range_gist_key_serialize(typcache, &rightKey));
+ 	PG_RETURN_POINTER(v);
+ }
+ 
+ /*
+  * Get extension of bounds by inclusion of new bound value using subtype_diff
+  * function.
+  */
+ static float8
+ get_bounds_extension(TypeCacheEntry *typcache, RangeBound *min, 
+ 						 RangeBound *max, RangeBound *newmin, RangeBound *newmax)
+ {
+ 	if (range_cmp_bounds(typcache, newmin, min) < 0)
+ 	{
+ 		if ((newmin->infinite && !min->infinite) || (!newmin->infinite && min->infinite))
+ 			return get_float8_infinity();
+ 		if (!OidIsValid(typcache->rng_subdiff_finfo.fn_oid))
+ 			return 1.0;
+ 		return call_subtype_diff(typcache, min->val, newmin->val);
+ 	}
+ 	else if (range_cmp_bounds(typcache, newmax, max) > 0)
+ 	{
+ 		if ((newmax->infinite && !max->infinite) || (!newmax->infinite && max->infinite))
+ 			return get_float8_infinity();
+ 		if (!OidIsValid(typcache->rng_subdiff_finfo.fn_oid))
+ 			return 1.0;
+ 		return call_subtype_diff(typcache, newmax->val, max->val);
+ 	}
+ 	else
+ 		return 0.0;
+ }
+ 
+ /*
+  * Get size of space between range bounds using subtype_diff function.
+  */
+ static float8
+ get_bounds_size(TypeCacheEntry *typcache, RangeBound *min, 
+ 						 RangeBound *max)
+ {
+ 	if ((min->infinite && !max->infinite) || (!min->infinite && max->infinite))
+ 		return get_float8_infinity();
+ 	else if (min->infinite && max->infinite)
+ 		return 0.0;
+ 	else
+ 		return call_subtype_diff(typcache, max->val, min->val);
+ }
+ 
+ /*
+  * GiST penalty function
+  */
+ Datum
+ range_gist2_penalty(PG_FUNCTION_ARGS)
+ {
+ 	GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ 	GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
+ 	float	   *penalty = (float *) PG_GETARG_POINTER(2);
+ 	TypeCacheEntry *typcache;
+ 
+ 	RangeGiSTKey *origkey = DatumGetRangeGiSTKey(origentry->key);
+ 	RangeGiSTKey *newkey = DatumGetRangeGiSTKey(newentry->key);
+ 	RangeGiSTKeyDeserialized orig,
+ 				new;
+ 
+ 	typcache = range_get_typcache(fcinfo, origkey->rangetypid);
+ 
+ 	range_gist_key_deserialize(typcache, origkey, &orig);
+ 	range_gist_key_deserialize(typcache, newkey, &new);
+ 	
+ 	*penalty = range_gist_key_penalty(typcache, &orig, &new);
+ 
+ 	PG_RETURN_POINTER(penalty);
+ }
+ 
+ /* GiST query consistency check */
+ Datum
+ range_gist2_consistent(PG_FUNCTION_ARGS)
+ {
+ 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ 	Datum		query = PG_GETARG_DATUM(1);
+ 	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+ 
+ 	/* Oid subtype = PG_GETARG_OID(3); */
+ 	bool	   *recheck = (bool *) PG_GETARG_POINTER(4);
+ 	RangeGiSTKey *gistkey = DatumGetRangeGiSTKey(entry->key);
+ 	RangeGiSTKeyDeserialized key;
+ 	TypeCacheEntry *typcache;
+ 	RangeBound	lower,
+ 				upper;
+ 	bool		empty;
+ 	int32		cmp;
+ 
+ 	typcache = range_get_typcache(fcinfo, gistkey->rangetypid);
+ 	range_gist_key_deserialize(typcache, gistkey, &key);
+ 
+ 	if (strategy != RANGESTRAT_CONTAINS_ELEM)
+ 	{
+ 		range_deserialize(typcache, DatumGetRangeType(query), &lower, &upper, &empty);
+ 	}
+ 
+ 	/* All operators served by this function are exact */
+ 	*recheck = false;
+ 
+ 	switch (strategy)
+ 	{
+ 		case RANGESTRAT_BEFORE:
+ 			/* If query is empty or all keys in subtree are empty, then skip */
+ 			if (empty || key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for upper bound inside subtree to be
+ 			 * lower than query lower bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 					 range_cmp_bounds(typcache, &key.upper.min, &lower) < 0);
+ 			break;
+ 		case RANGESTRAT_AFTER:
+ 			/* If query is empty or all keys in subtree are empty, then skip */
+ 			if (empty || key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be
+ 			 * greater than query upper bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 					 range_cmp_bounds(typcache, &key.lower.max, &upper) > 0);
+ 			break;
+ 		case RANGESTRAT_OVERLEFT:
+ 			/* If query is empty or all keys in subtree are empty, then skip */
+ 			if (empty || key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for upper bound inside subtree to be
+ 			 * lower than query lower bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 					range_cmp_bounds(typcache, &key.upper.min, &upper) <= 0);
+ 			break;
+ 		case RANGESTRAT_OVERRIGHT:
+ 			/* If query is empty or all keys in subtree are empty, then skip */
+ 			if (empty || key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			PG_RETURN_BOOL(
+ 					range_cmp_bounds(typcache, &key.lower.max, &lower) >= 0);
+ 			break;
+ 		case RANGESTRAT_ADJACENT:
+ 			/* If query is empty or all keys in subtree are empty, then skip */
+ 			if (empty || key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			if (!key.leaf)
+ 			{
+ 				/* 
+ 				 * It should be possible for upper bound inside subtree to be
+ 				 * equal to query lower bound or for lower bound inside subtree
+ 				 * to be equal to query upper bound.
+ 				 */
+ 				PG_RETURN_BOOL(
+ 							   (range_cmp_bound_values(typcache, &key.lower.min, &upper) <= 0 &&
+ 								range_cmp_bound_values(typcache, &key.lower.max, &upper) >= 0) ||
+ 							   (range_cmp_bound_values(typcache, &key.upper.min, &lower) <= 0 &&
+ 								range_cmp_bound_values(typcache, &key.upper.max, &lower) >= 0)
+ 					);
+ 			}
+ 			else
+ 			{
+ 				/* Do direct check for leaf key */
+ 				PG_RETURN_DATUM(
+ 						   TrickFunctionCall2(range_adjacent, fcinfo->flinfo,
+ 				  RangeTypeGetDatum(range_serialize(typcache, &key.lower.min,
+ 												 &key.upper.max, key.empty)),
+ 											  query)
+ 					);
+ 			}
+ 			break;
+ 		case RANGESTRAT_EQ:
+ 			/* Subtree can contain empty only if key have "containEmpty" flag */
+ 			if (empty)
+ 				PG_RETURN_BOOL(key.containEmpty);
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be
+ 			 * equal to query lower bound and for upper bound inside subtree
+ 			 * to be equal to query upper bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 				  (range_cmp_bounds(typcache, &key.lower.min, &lower) <= 0 &&
+ 				   range_cmp_bounds(typcache, &key.lower.max, &lower) >= 0) ||
+ 				  (range_cmp_bounds(typcache, &key.upper.min, &upper) <= 0 &&
+ 				   range_cmp_bounds(typcache, &key.upper.max, &upper) >= 0)
+ 				);
+ 			break;
+ 		case RANGESTRAT_CONTAINS_ELEM:
+ 			/* 
+ 			 * If whole subtree contain only empty elements then it can't
+ 			 * contain any element.
+ 			 */
+ 			if (key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be less
+ 			 * than query element.
+ 			 */
+ 			if (!key.lower.min.infinite)
+ 			{
+ 				cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
+ 													  typcache->rng_collation,
+ 												  key.lower.min.val, query));
+ 				if (cmp > 0)
+ 					PG_RETURN_BOOL(false);
+ 				if (cmp == 0 && !key.lower.min.inclusive)
+ 					PG_RETURN_BOOL(false);
+ 			}
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be
+ 			 * greater than query element.
+ 			 */
+ 			if (!key.upper.max.infinite)
+ 			{
+ 				cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
+ 													  typcache->rng_collation,
+ 												  key.upper.max.val, query));
+ 				if (cmp < 0)
+ 					PG_RETURN_BOOL(false);
+ 				if (cmp == 0 && !key.upper.max.inclusive)
+ 					PG_RETURN_BOOL(false);
+ 			}
+ 			PG_RETURN_BOOL(true);
+ 			break;
+ 		case RANGESTRAT_OVERLAPS:
+ 			/* If query is empty or all keys in subtree are empty, then skip */
+ 			if (empty || key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be less
+ 			 * or equal to query upper bound and for upper bound inside subtree
+ 			 * to be greater or equal to query lower bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 				   range_cmp_bounds(typcache, &key.lower.min, &upper) <= 0 &&
+ 					range_cmp_bounds(typcache, &key.upper.max, &lower) >= 0);
+ 			break;
+ 		case RANGESTRAT_CONTAINS:
+ 			/* Empty query is contained in everything */
+ 			if (empty)
+ 				PG_RETURN_BOOL(true);
+ 			/* If all key in subtree are empty then it can contain anything */
+ 			if (key.empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be less
+ 			 * or equal to query lower bound and for upper bound inside subtree
+ 			 * to be greater or equal to query upper bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 				   range_cmp_bounds(typcache, &key.lower.min, &lower) <= 0 &&
+ 					range_cmp_bounds(typcache, &key.upper.max, &upper) >= 0);
+ 			break;
+ 		case RANGESTRAT_CONTAINED_BY:
+ 			/* Empty keys are contained in everything */
+ 			if (key.containEmpty)
+ 				PG_RETURN_BOOL(true);
+ 			/* Empty query can't contain anything */
+ 			if (empty)
+ 				PG_RETURN_BOOL(false);
+ 			/* 
+ 			 * It should be possible for lower bound inside subtree to be
+ 			 * greater or equal to query lower bound and for upper bound inside
+ 			 * subtree to be less or equal to query upper bound.
+ 			 */
+ 			PG_RETURN_BOOL(
+ 				   range_cmp_bounds(typcache, &key.lower.max, &lower) >= 0 &&
+ 					range_cmp_bounds(typcache, &key.upper.min, &upper) <= 0);
+ 			break;
+ 		default:
+ 			elog(ERROR, "unrecognized range strategy: %d", strategy);
+ 			break;
+ 	}
+ 
+ 	PG_RETURN_BOOL(true);
+ }
+ 
+ /* equality comparator for GiST */
+ Datum
+ range_gist2_same(PG_FUNCTION_ARGS)
+ {
+ 	RangeGiSTKey *gistKey1 = DatumGetRangeGiSTKey(PG_GETARG_DATUM(0));
+ 	RangeGiSTKey *gistKey2 = DatumGetRangeGiSTKey(PG_GETARG_DATUM(1));
+ 	bool	   *result = (bool *) PG_GETARG_POINTER(2);
+ 	RangeGiSTKeyDeserialized key1, key2;
+ 	TypeCacheEntry *typcache;
+ 	
+ 	typcache = range_get_typcache(fcinfo, gistKey1->rangetypid);
+ 	
+ 	/* deserialize gist keys */
+ 	range_gist_key_deserialize(typcache, gistKey1, &key1);
+ 	range_gist_key_deserialize(typcache, gistKey2, &key2);
+ 	
+ 	/* compare flags first, then compare bounds */
+ 	if (key1.containEmpty != key2.containEmpty || key1.empty != key2.empty)
+ 		*result = false;
+ 	else if (range_cmp_bounds(typcache, &key1.lower.min, &key2.lower.min) != 0)
+ 		*result = false;
+ 	else if (range_cmp_bounds(typcache, &key1.lower.max, &key2.lower.max) != 0)
+ 		*result = false;
+ 	else if (range_cmp_bounds(typcache, &key1.upper.min, &key2.upper.min) != 0)
+ 		*result = false;
+ 	else if (range_cmp_bounds(typcache, &key1.upper.max, &key2.upper.max) != 0)
+ 		*result = false;
+ 	else
+ 		*result = true;
+ 
+ 	PG_RETURN_POINTER(result);
+ }
*** /dev/null
--- b/src/backend/utils/adt/rangetypes_spgist.c
***************
*** 0 ****
--- 1,807 ----
+ /*-------------------------------------------------------------------------
+  *
+  * rangetypes_spgist.c
+  *	  implementation of quad 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_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);
+ static bool bounds_connected(TypeCacheEntry *typcache, RangeBound lower, RangeBound upper);
+ 
+ 
+ /*
+  * 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. Lower bound of range assumed to be the horizontal axis. Upper
+  * bound of range assumed to be the vertical axis.
+  *
+  * 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));
+ 
+ 	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();
+ 	}
+ 	
+ 	quadrant = getQuadrant(typcache, centroid, inRange);
+ 
+ 	/* Node for empty range is possibly not exist, create it if so */
+ 	if (quadrant == 5 && in->nNodes == 4)
+ 	{
+ 		out->resultType = spgAddNode;
+ 		out->result.addNode.nodeN = quadrant - 1;
+ 	}
+ 
+ 	Assert(quadrant <= in->nNodes);
+ 
+ 	/* Select node matching to quadrant number */
+ 	out->resultType = spgMatchNode;
+ 	out->result.matchNode.nodeN = quadrant - 1;
+ 	out->result.matchNode.levelAdd = 0;
+ 	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 = 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 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 actually needed */
+ 	out->nNodes = (nonEmptyCount == in->nTuples) ? 4 : 5;
+ 	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();
+ }
+ 
+ /*
+  * 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_quad_inner_consistent(PG_FUNCTION_ARGS)
+ {
+ 	spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
+ 	spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
+ 	RangeType   *centroid;
+ 	int			which;
+ 	int			i;
+ 	bool		needPrevious = false;
+ 
+ 	Assert(in->hasPrefix);
+ 	centroid = 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(centroid))
+ 	{
+ 		/*
+ 		 * 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;
+ 
+ 		/* Centroid is not empty, get information about it. */
+ 		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;
+ 
+ 			/*
+ 			 * 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);
+ 			}
+ 			
+ 			strategy = in->scankeys[i].sk_strategy;
+ 			
+ 			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 connected
+ 				 * to upper bound of another range.
+ 				 */
+ 				case RANGESTRAT_ADJACENT:
+ 					/*
+ 					 * which1 is bitmask for possibility to be connected with
+ 					 * lower bound of argument. which2 is bitmask for
+ 					 * possibility to be connected 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_connected(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 = 0;
+ 					else
+ 					{
+ 						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 = 0;
+ 					else
+ 					{
+ 						which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+ 						/* 
+ 						 * 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);
+ 						/* 
+ 						 * 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);
+ 					}
+ 					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] = RangeTypeGetDatum(centroid);
+ 			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;
+ 
+ 	/* 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);
+ }
*** /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 int16 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 int16
+ 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;
+ 	int16			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]);
+ 		int16	   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
***************
*** 734,739 **** DATA(insert (	3919   3831 3831 8 s	3892 783 0 ));
--- 734,750 ----
  DATA(insert (	3919   3831 2283 16 s	3889 783 0 ));
  DATA(insert (	3919   3831 3831 18 s	3882 783 0 ));
  
+ DATA(insert (	3457   3831 3831 1 s	3893 783 0 ));
+ DATA(insert (	3457   3831 3831 2 s	3895 783 0 ));
+ DATA(insert (	3457   3831 3831 3 s	3888 783 0 ));
+ DATA(insert (	3457   3831 3831 4 s	3896 783 0 ));
+ DATA(insert (	3457   3831 3831 5 s	3894 783 0 ));
+ DATA(insert (	3457   3831 3831 6 s	3897 783 0 ));
+ DATA(insert (	3457   3831 3831 7 s	3890 783 0 ));
+ DATA(insert (	3457   3831 3831 8 s	3892 783 0 ));
+ DATA(insert (	3457   3831 2283 16 s	3889 783 0 ));
+ DATA(insert (	3457   3831 3831 18 s	3882 783 0 ));
+ 
  /*
   * SP-GiST quad_point_ops
   */
***************
*** 767,770 **** DATA(insert (	4017   25 25 12 s	665 4000 0 ));
--- 778,805 ----
  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 ));
+ 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
***************
*** 355,360 **** DATA(insert (	3919   3831 3831 4 3878 ));
--- 355,367 ----
  DATA(insert (	3919   3831 3831 5 3879 ));
  DATA(insert (	3919   3831 3831 6 3880 ));
  DATA(insert (	3919   3831 3831 7 3881 ));
+ DATA(insert (	3457   3831 3831 1 3458 ));
+ DATA(insert (	3457   3831 3831 2 3459 ));
+ DATA(insert (	3457   3831 3831 3 3460 ));
+ DATA(insert (	3457   3831 3831 4 3461 ));
+ DATA(insert (	3457   3831 3831 5 3462 ));
+ DATA(insert (	3457   3831 3831 6 3463 ));
+ DATA(insert (	3457   3831 3831 7 3464 ));
  
  
  /* sp-gist */
***************
*** 373,377 **** DATA(insert (	4017   25 25 2 4028 ));
--- 380,394 ----
  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 ));
+ 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,231 ----
  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 (	783		range_ops2			PGNSP PGUID 3457  3831 f 3465 ));
+ DATA(insert (	4000	range_ops_quad		PGNSP PGUID 3474  3831 t 0 ));
+ DATA(insert (	4000	range_ops_kd		PGNSP PGUID 3475  3831 f 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,150 ----
  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 = 3457 (	783		range_ops2		PGNSP PGUID ));
+ DATA(insert OID = 3474 (	4000	range_ops_quad	PGNSP PGUID ));
+ DATA(insert OID = 3475 (	4000	range_ops_kd	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
***************
*** 4165,4170 **** DATA(insert OID =  3646 (  gtsvectorin			PGNSP PGUID 12 1 0 0 0 f f f f t f i 1
--- 4165,4174 ----
  DESCR("I/O");
  DATA(insert OID =  3647 (  gtsvectorout			PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2275 "3642" _null_ _null_ _null_ _null_ gtsvectorout _null_ _null_ _null_ ));
  DESCR("I/O");
+ DATA(insert OID =  3467 (  grange_in			PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 3465 "2275" _null_ _null_ _null_ _null_ grange_in _null_ _null_ _null_ ));
+ DESCR("I/O");
+ DATA(insert OID =  3468 (  grange_out			PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2275 "3465" _null_ _null_ _null_ _null_ grange_out _null_ _null_ _null_ ));
+ DESCR("I/O");
  
  DATA(insert OID = 3616 (  tsvector_lt			PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "3614 3614" _null_ _null_ _null_ _null_ tsvector_lt _null_ _null_ _null_ ));
  DATA(insert OID = 3617 (  tsvector_le			PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "3614 3614" _null_ _null_ _null_ _null_ tsvector_le _null_ _null_ _null_ ));
***************
*** 4532,4537 **** DATA(insert OID = 3880 (  range_gist_picksplit	PGNSP PGUID 12 1 0 0 0 f f f f t
--- 4536,4555 ----
  DESCR("GiST support");
  DATA(insert OID = 3881 (  range_gist_same		PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "3831 3831 2281" _null_ _null_ _null_ _null_ range_gist_same _null_ _null_ _null_ ));
  DESCR("GiST support");
+ DATA(insert OID = 3458 (  range_gist2_consistent	PGNSP PGUID 12 1 0 0 0 f f f f t f i 5 0 16 "2281 3831 23 26 2281" _null_ _null_ _null_ _null_ range_gist2_consistent _null_ _null_ _null_ ));
+ DESCR("GiST support");
+ DATA(insert OID = 3459 (  range_gist2_union		PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ range_gist2_union _null_ _null_ _null_ ));
+ DESCR("GiST support");
+ DATA(insert OID = 3460 (  range_gist2_compress	PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2281 "2281" _null_ _null_ _null_ _null_ range_gist2_compress _null_ _null_ _null_ ));
+ DESCR("GiST support");
+ DATA(insert OID = 3461 (  range_gist2_decompress	PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 2281 "2281" _null_ _null_ _null_ _null_ range_gist2_decompress _null_ _null_ _null_ ));
+ DESCR("GiST support");
+ DATA(insert OID = 3462 (  range_gist2_penalty	PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "2281 2281 2281" _null_ _null_ _null_ _null_ range_gist2_penalty _null_ _null_ _null_ ));
+ DESCR("GiST support");
+ DATA(insert OID = 3463 (  range_gist2_picksplit	PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2281 "2281 2281" _null_ _null_ _null_ _null_ range_gist2_picksplit _null_ _null_ _null_ ));
+ DESCR("GiST support");
+ DATA(insert OID = 3464 (  range_gist2_same		PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 2281 "3831 3831 2281" _null_ _null_ _null_ _null_ range_gist2_same _null_ _null_ _null_ ));
+ DESCR("GiST support");
  DATA(insert OID = 3902 (  hash_range			PGNSP PGUID 12 1 0 0 0 f f f f t f i 1 0 23 "3831" _null_ _null_ _null_ _null_ hash_range _null_ _null_ _null_ ));
  DESCR("hash a range");
  DATA(insert OID = 3916 (  range_typanalyze		PGNSP PGUID 12 1 0 0 0 f f f f t f s 1 0 16 "2281" _null_ _null_ _null_ _null_ range_typanalyze _null_ _null_ _null_ ));
***************
*** 4645,4650 **** DESCR("SP-GiST support for suffix tree over text");
--- 4663,4689 ----
  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");
+ 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/catalog/pg_type.h
--- b/src/include/catalog/pg_type.h
***************
*** 582,587 **** DESCR("text representation for text search");
--- 582,590 ----
  DATA(insert OID = 3642 ( gtsvector		PGNSP PGUID -1 f b U f t \054 0 0 3644 gtsvectorin gtsvectorout - - - - - i p f 0 -1 0 0 _null_ _null_ _null_ ));
  DESCR("GiST index internal text representation for text search");
  #define GTSVECTOROID	3642
+ DATA(insert OID = 3465 ( grange			PGNSP PGUID -1 f b U f t \054 0 0 3466 grange_in grange_out - - - - - i p f 0 -1 0 0 _null_ _null_ _null_ ));
+ DESCR("GiST index key type for ranges");
+ #define GRANGEOID	3465
  DATA(insert OID = 3615 ( tsquery		PGNSP PGUID -1 f b U f t \054 0 0 3645 tsqueryin tsqueryout tsqueryrecv tsquerysend - - - i p f 0 -1 0 0 _null_ _null_ _null_ ));
  DESCR("query representation for text search");
  #define TSQUERYOID		3615
***************
*** 594,599 **** DESCR("registered text search dictionary");
--- 597,603 ----
  
  DATA(insert OID = 3643 ( _tsvector		PGNSP PGUID -1 f b A f t \054 0 3614 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ ));
  DATA(insert OID = 3644 ( _gtsvector		PGNSP PGUID -1 f b A f t \054 0 3642 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ ));
+ DATA(insert OID = 3466 ( _grange		PGNSP PGUID -1 f b A f t \054 0 3465 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ ));
  DATA(insert OID = 3645 ( _tsquery		PGNSP PGUID -1 f b A f t \054 0 3615 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ ));
  DATA(insert OID = 3735 ( _regconfig		PGNSP PGUID -1 f b A f t \054 0 3734 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ ));
  DATA(insert OID = 3770 ( _regdictionary PGNSP PGUID -1 f b A f t \054 0 3769 0 array_in array_out array_recv array_send - - array_typanalyze i x f 0 -1 0 0 _null_ _null_ _null_ ));
*** a/src/include/utils/rangetypes.h
--- b/src/include/utils/rangetypes.h
***************
*** 15,20 ****
--- 15,21 ----
  #define RANGETYPES_H
  
  #include "utils/typcache.h"
+ #include "utils/lsyscache.h"
  
  
  /*
***************
*** 65,70 **** typedef struct
--- 66,82 ----
  	bool		lower;			/* this is the lower (vs upper) bound */
  } RangeBound;
  
+ #define RANGE_EMPTY_LITERAL "empty"
+ 
+ /* fn_extra cache entry for one of the range I/O functions */
+ typedef struct RangeIOData
+ {
+ 	TypeCacheEntry *typcache;	/* range type's typcache entry */
+ 	Oid			typiofunc;		/* element type's I/O function */
+ 	Oid			typioparam;		/* element type's I/O parameter */
+ 	FmgrInfo	proc;			/* lookup result for typiofunc */
+ } RangeIOData;
+ 
  /*
   * fmgr macros for range type objects
   */
***************
*** 75,80 **** typedef struct
--- 87,105 ----
  #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
   */
***************
*** 84,89 **** extern Datum range_in(PG_FUNCTION_ARGS);
--- 109,123 ----
  extern Datum range_out(PG_FUNCTION_ARGS);
  extern Datum range_recv(PG_FUNCTION_ARGS);
  extern Datum range_send(PG_FUNCTION_ARGS);
+ extern Size datum_compute_size(Size data_length, Datum val, bool typbyval,
+ 								char typalign, int16 typlen, char typstorage);
+ extern Pointer datum_write(Pointer ptr, Datum datum, bool typbyval,
+ 								char typalign, int16 typlen, char typstorage);
+ extern RangeIOData *get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid,
+ 									  IOFuncSelector func);
+ char *range_bound_escape(const char *value);
+ 
+ 
  
  /* constructors */
  extern Datum range_constructor2(PG_FUNCTION_ARGS);
***************
*** 165,171 **** extern int range_cmp_bound_values(TypeCacheEntry *typcache, RangeBound *b1,
--- 199,223 ----
  					   RangeBound *b2);
  extern RangeType *make_empty_range(TypeCacheEntry *typcache);
  
+ /* 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
+ 
+ Datum TrickFunctionCall2(PGFunction proc, FmgrInfo *flinfo, Datum arg1, Datum arg2);
+ 
+ 
  /* 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);
--- 226,246 ----
  extern Datum range_gist_picksplit(PG_FUNCTION_ARGS);
  extern Datum range_gist_same(PG_FUNCTION_ARGS);
  
+ /* GiST support (in rangetypes_gist2.c) */
+ extern Datum grange_in(PG_FUNCTION_ARGS);
+ extern Datum grange_out(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_consistent(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_compress(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_decompress(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_union(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_penalty(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_picksplit(PG_FUNCTION_ARGS);
+ extern Datum range_gist2_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 */
*** 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