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