range_spgist_adjacent-0.1.patch

diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
new file mode 100644
index fe9e0c4..cf3627b
*** a/src/backend/utils/adt/rangetypes.c
--- b/src/backend/utils/adt/rangetypes.c
*************** range_after(PG_FUNCTION_ARGS)
*** 709,714 ****
--- 709,761 ----
  	PG_RETURN_BOOL(range_after_internal(typcache, r1, r2));
  }
  
+ /*
+  * Check if two bounds A and B are "adjacent", i.e. each subtype value satisfy
+  * to strictly one of those bounds: there are no values which satisfy both
+  * bounds and there are no values between the bounds. For discrete ranges, we
+  * have to rely on the canonicalization function to normalize A..B to empty if
+  * it contains no elements of the subtype.  (If there is no canonicalization
+  * function, it's impossible for such a range to normalize to empty, so we
+  * needn't bother to try.)
+  *
+  * If A == B, the ranges are adjacent only if these bounds have different
+  * inclusive flags (i.e., exactly one of the ranges includes the common
+  * boundary point).
+  *
+  * And if A > B then the ranges cannot be adjacent in this order.
+  */
+ bool
+ bounds_adjacent(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper)
+ {
+ 	int cmp = range_cmp_bound_values(typcache, upper, lower);
+ 	if (cmp < 0)
+ 	{
+ 		RangeType *r;
+ 		/* in a continuous subtype, there are assumed to be points between */
+ 		if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
+ 			return false;
+ 		/* flip the inclusion flags */
+ 		upper->inclusive = !upper->inclusive;
+ 		lower->inclusive = !lower->inclusive;
+ 		/* change upper/lower labels to avoid Assert failures */
+ 		upper->lower = true;
+ 		lower->lower = false;
+ 		r = make_range(typcache, upper, lower, false);
+ 		/* turn labels back */
+ 		upper->lower = false;
+ 		lower->lower = true;
+ 		PG_RETURN_BOOL(RangeIsEmpty(r));
+ 	}
+ 	else if (cmp == 0)
+ 	{
+ 		PG_RETURN_BOOL(upper->inclusive != lower->inclusive);
+ 	}
+ 	else
+ 	{
+ 		PG_RETURN_BOOL(false);
+ 	}
+ }
+ 
  /* adjacent to (but not overlapping)? (internal version) */
  bool
  range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
*************** range_adjacent_internal(TypeCacheEntry *
*** 719,726 ****
  				upper2;
  	bool		empty1,
  				empty2;
- 	RangeType  *r3;
- 	int			cmp;
  
  	/* Different types should be prevented by ANYRANGE matching rules */
  	if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
--- 766,771 ----
*************** range_adjacent_internal(TypeCacheEntry *
*** 734,795 ****
  		return false;
  
  	/*
! 	 * Given two ranges A..B and C..D, where B < C, the ranges are adjacent if
! 	 * and only if the range B..C is empty, where inclusivity of these two
! 	 * bounds is inverted compared to the original bounds.	For discrete
! 	 * ranges, we have to rely on the canonicalization function to normalize
! 	 * B..C to empty if it contains no elements of the subtype.  (If there is
! 	 * no canonicalization function, it's impossible for such a range to
! 	 * normalize to empty, so we needn't bother to try.)
! 	 *
! 	 * If B == C, the ranges are adjacent only if these bounds have different
! 	 * inclusive flags (i.e., exactly one of the ranges includes the common
! 	 * boundary point).
! 	 *
! 	 * And if B > C then the ranges cannot be adjacent in this order, but we
! 	 * must consider the other order (i.e., check D <= A).
  	 */
! 	cmp = range_cmp_bound_values(typcache, &upper1, &lower2);
! 	if (cmp < 0)
! 	{
! 		/* in a continuous subtype, there are assumed to be points between */
! 		if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
! 			return (false);
! 		/* flip the inclusion flags */
! 		upper1.inclusive = !upper1.inclusive;
! 		lower2.inclusive = !lower2.inclusive;
! 		/* change upper/lower labels to avoid Assert failures */
! 		upper1.lower = true;
! 		lower2.lower = false;
! 		r3 = make_range(typcache, &upper1, &lower2, false);
! 		return RangeIsEmpty(r3);
! 	}
! 	if (cmp == 0)
! 	{
! 		return (upper1.inclusive != lower2.inclusive);
! 	}
! 
! 	cmp = range_cmp_bound_values(typcache, &upper2, &lower1);
! 	if (cmp < 0)
! 	{
! 		/* in a continuous subtype, there are assumed to be points between */
! 		if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
! 			return (false);
! 		/* flip the inclusion flags */
! 		upper2.inclusive = !upper2.inclusive;
! 		lower1.inclusive = !lower1.inclusive;
! 		/* change upper/lower labels to avoid Assert failures */
! 		upper2.lower = true;
! 		lower1.lower = false;
! 		r3 = make_range(typcache, &upper2, &lower1, false);
! 		return RangeIsEmpty(r3);
! 	}
! 	if (cmp == 0)
! 	{
! 		return (upper2.inclusive != lower1.inclusive);
! 	}
! 
! 	return false;
  }
  
  /* adjacent to (but not overlapping)? */
--- 779,790 ----
  		return false;
  
  	/*
! 	 * Given two ranges A..B and C..D, the ranges are adjacent if and only if
! 	 * the pair of B and C bounds is adjacent or pair of D and A bounds is
! 	 * adjacent.
  	 */
! 	return (bounds_adjacent(typcache, &lower2, &upper1) ||
! 			bounds_adjacent(typcache, &lower1, &upper2));
  }
  
  /* adjacent to (but not overlapping)? */
diff --git a/src/backend/utils/adt/rangetypes_spgist.c b/src/backend/utils/adt/rangetypes_spgist.c
new file mode 100644
index b69fbfc..9e56ae1
*** a/src/backend/utils/adt/rangetypes_spgist.c
--- b/src/backend/utils/adt/rangetypes_spgist.c
*************** spg_range_quad_inner_consistent(PG_FUNCT
*** 304,309 ****
--- 304,310 ----
  	spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
  	int			which;
  	int			i;
+ 	bool		needPrevious = false;
  
  	if (in->allTheSame)
  	{
*************** spg_range_quad_inner_consistent(PG_FUNCT
*** 351,356 ****
--- 352,358 ----
  				case RANGESTRAT_OVERLAPS:
  				case RANGESTRAT_OVERRIGHT:
  				case RANGESTRAT_AFTER:
+ 				case RANGESTRAT_ADJACENT:
  					/* These strategies return false if any argument is empty */
  					if (empty)
  						which = 0;
*************** spg_range_quad_inner_consistent(PG_FUNCT
*** 479,484 ****
--- 481,488 ----
  			 */
  			switch (strategy)
  			{
+ 				int cmp, which1, which2;
+ 
  				case RANGESTRAT_BEFORE:
  					/*
  					 * Range A is before range B if upper bound of A is lower
*************** spg_range_quad_inner_consistent(PG_FUNCT
*** 522,527 ****
--- 526,670 ----
  					inclusive = false;
  					break;
  
+ 				case RANGESTRAT_ADJACENT:
+ 					/*
+ 					 * Skip to strictEmpty check.
+ 					 */
+ 					if (empty)
+ 						break;
+ 
+ 					/*
+ 					 * Inverse bounds of arguments for comparison with
+ 					 * opposite bounds.
+ 					 */
+ 					lower.lower = false;
+ 					lower.inclusive = !lower.inclusive;
+ 					upper.lower = true;
+ 					upper.inclusive = !upper.inclusive;
+ 
+ 					/*
+ 					 * which1 is bitmask for possibility to be adjacent with
+ 					 * lower bound of argument. which2 is bitmask for
+ 					 * possibility to be adjacent with upper bound of
+ 					 * argument.
+ 					 */
+ 					which1 = which2 = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+ 
+ 					/*
+ 					 * Previously selected quadrant could exclude possibility
+ 					 * for lower or upper bounds to be adjacent. Deserialize
+ 					 * previous centroid range if present for checking this.
+ 					 */
+ 					if (in->reconstructedValue != (Datum) 0)
+ 					{
+ 						RangeType  *prevCentroid;
+ 						RangeBound	prevLower,
+ 									prevUpper;
+ 						bool		prevEmpty;
+ 						int			cmp1, cmp2;
+ 
+ 						prevCentroid = DatumGetRangeType(in->reconstructedValue);
+ 						range_deserialize(typcache, prevCentroid, &prevLower,
+ 							&prevUpper, &prevEmpty);
+ 
+ 						/*
+ 						 * Check if lower bound of argument is not in
+ 						 * a quadrant we visit in previous step.
+ 						 */
+ 						cmp1 = range_cmp_bounds(typcache, &upper, &prevLower);
+ 						cmp2 = range_cmp_bounds(typcache, &centroidLower,
+ 																	&prevLower);
+ 						if ((cmp2 < 0 && cmp1 > 0) || (cmp2 > 0 && cmp1 < 0))
+ 							which1 = 0;
+ 
+ 						/*
+ 						 * Check if upper bound of argument is not in
+ 						 * a quadrant we visit in previous step.
+ 						 */
+ 						cmp1 = range_cmp_bounds(typcache, &lower, &prevUpper);
+ 						cmp2 = range_cmp_bounds(typcache, &centroidUpper,
+ 																	&prevUpper);
+ 						if ((cmp2 < 0 && cmp1 > 0) || (cmp2 > 0 && cmp1 < 0))
+ 							which2 = 0;
+ 					}
+ 
+ 					if (which1)
+ 					{
+ 						cmp = range_cmp_bounds(typcache, &centroidLower,
+ 																		&upper);
+ 						if (cmp <= 0)
+ 						{
+ 							/*
+ 							 * If the centroid's lower bound is less or equal
+ 							 * to argument's upper bound then any bound from
+ 							 * 3rd or 4th quadrant is less than centroid's
+ 							 * lower and also less than argument's upper bound.
+ 							 * Thus, even in corner case, centroid's lower
+ 							 * bound is adjacent to argument's upper bound and
+ 							 * any bound from 3rd or 4th quadrant is even
+ 							 * less and can't match.
+ 							 */
+ 							which1 &= (1 << 1) | (1 << 2);
+ 						}
+ 						else if (!bounds_adjacent(typcache, &centroidLower,
+ 																		&upper))
+ 						{
+ 							/*
+ 							 * If the centroid's lower bound is greater than
+ 							 * argument's upper bound then any bound from
+ 							 * 1st or 2nd quadrant is greater or equal to
+ 							 * centroid's lower and greater than argument's
+ 							 * upper bound. But, in corner case, centroid's
+ 							 * lower bound is adjacent to argument's upper bound
+ 							 * and bound from 1st or 2nd quadrant is equal to
+ 							 * it. Thus, we can exclude 1st and 2nd quardrants
+ 							 * only if centroid's lower bound and argument's
+ 							 * upper bound aren't adjacent.
+ 							 */
+ 							which1 &= (1 << 3) | (1 << 4);
+ 						}
+ 					}
+ 
+ 					if (which2)
+ 					{
+ 						cmp = range_cmp_bounds(typcache, &centroidUpper,
+ 																		&lower);
+ 						if (cmp <= 0)
+ 						{
+ 							/*
+ 							 * If the centroid's upper bound is less or equal
+ 							 * than argument's lower bound then any bound from
+ 							 * 2nd or 3rd quadrant is less than centroid's
+ 							 * upper bound. Thus, even in corner case,
+ 							 * centroid's upper bound is equal to argument's
+ 							 * lower bound, and any bound from 2nd or 3rd
+ 							 * quadrant is even less and can't match.
+ 							 */
+ 							which2 &= (1 << 1) | (1 << 4);
+ 						}
+ 						else if (bounds_adjacent(typcache, &lower,
+ 																&centroidUpper))
+ 						{
+ 							/*
+ 							 * If the centroid's upper bound is greater than
+ 							 * argument's lower bound then any bound from
+ 							 * 1st or 4th quadrant is greater or equal to
+ 							 * centroid's upper bound. Thus, in corner case,
+ 							 * centroid's upper bound is adjacent to argument's
+ 							 * lower bound, and bound from 1st or 4th quadrant
+ 							 * is equal to it. Thus, we can exclude 1st and 4th
+ 							 * quardrants only if centroid's upper bound and
+ 							 * argument's lower bound aren't adjacent.							 *
+ 							 */
+ 							which2 &= (1 << 2) | (1 << 3);
+ 						}
+ 					}
+ 
+ 					which &= which1 | which2;
+ 
+ 					needPrevious = true;
+ 					break;
+ 
  				case RANGESTRAT_CONTAINS:
  					/*
  					 * Non-empty range A contains non-empty range B if lower
*************** spg_range_quad_inner_consistent(PG_FUNCT
*** 652,662 ****
--- 795,812 ----
  
  	/* We must descend into the quadrant(s) identified by 'which' */
  	out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
+ 	if (needPrevious)
+ 		out->reconstructedValues = (Datum *) palloc(sizeof(Datum) * in->nNodes);
  	out->nNodes = 0;
  	for (i = 1; i <= in->nNodes; i++)
  	{
  		if (which & (1 << i))
+ 		{
+ 			/* Save previous prefix if needed */
+ 			if (needPrevious)
+ 				out->reconstructedValues[out->nNodes] = in->prefixDatum;
  			out->nodeNumbers[out->nNodes++] = i - 1;
+ 		}
  	}
  
  	PG_RETURN_VOID();
*************** spg_range_quad_leaf_consistent(PG_FUNCTI
*** 713,718 ****
--- 863,872 ----
  				res = range_after_internal(typcache, leafRange,
  										   DatumGetRangeType(keyDatum));
  				break;
+ 			case RANGESTRAT_ADJACENT:
+ 				res = range_adjacent_internal(typcache, leafRange,
+ 										   DatumGetRangeType(keyDatum));
+ 				break;
  			case RANGESTRAT_CONTAINS:
  				res = range_contains_internal(typcache, leafRange,
  											  DatumGetRangeType(keyDatum));
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
new file mode 100644
index aeee87e..74db745
*** a/src/include/catalog/pg_amop.h
--- b/src/include/catalog/pg_amop.h
*************** DATA(insert (	3474   3831 3831 2 s	3895
*** 775,780 ****
--- 775,781 ----
  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 ));
diff --git a/src/include/utils/rangetypes.h b/src/include/utils/rangetypes.h
new file mode 100644
index fb0b23b..b6f900b
*** a/src/include/utils/rangetypes.h
--- b/src/include/utils/rangetypes.h
*************** extern int range_cmp_bounds(TypeCacheEnt
*** 201,206 ****
--- 201,208 ----
  extern int range_cmp_bound_values(TypeCacheEntry *typcache, RangeBound *b1,
  					   RangeBound *b2);
  extern RangeType *make_empty_range(TypeCacheEntry *typcache);
+ extern bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound *lower,
+ 						RangeBound *upper);
  
  /* GiST support (in rangetypes_gist.c) */
  extern Datum range_gist_consistent(PG_FUNCTION_ARGS);
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
new file mode 100644
index 6faaf42..256b719
*** a/src/test/regress/expected/opr_sanity.out
--- b/src/test/regress/expected/opr_sanity.out
*************** ORDER BY 1, 2, 3;
*** 1076,1081 ****
--- 1076,1082 ----
         4000 |            4 | ~>=~
         4000 |            5 | >>
         4000 |            5 | ~>~
+        4000 |            6 | -|-
         4000 |            6 | ~=
         4000 |            7 | @>
         4000 |            8 | <@
*************** ORDER BY 1, 2, 3;
*** 1087,1093 ****
         4000 |           15 | >
         4000 |           16 | @>
         4000 |           18 | =
! (61 rows)
  
  -- Check that all opclass search operators have selectivity estimators.
  -- This is not absolutely required, but it seems a reasonable thing
--- 1088,1094 ----
         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