Hi there, pg-Hackers! Here I go with the patch which brings up the possibility to perform nearest-neighbour searches on SP-GiSTs (as of now includes implementation for quad and kd trees). Pre-reviewed by my GSoC mentor Alexander Korotkov. Sample benchmarking script included in the attachment (dumps the current geonames archive and runs several searches on the (latitude, longitude) points), which demonstrates the dramatic improvements against plain searches and sorting. Regression tests included, compiles and runs successfully under both of my Ubuntu 12.04 Server and 08/2014 Arch Linux.
Vlad Sterzhanov / Quadrocube
diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml
index 56827e5..5214770 100644
--- a/doc/src/sgml/spgist.sgml
+++ b/doc/src/sgml/spgist.sgml
@@ -83,6 +83,7 @@
<literal>>></>
<literal>>^</>
<literal>~=</>
+ <literal><-></>
</entry>
</row>
<row>
@@ -95,6 +96,7 @@
<literal>>></>
<literal>>^</>
<literal>~=</>
+ <literal><-></>
</entry>
</row>
<row>
@@ -137,6 +139,10 @@
supports the same operators but uses a different index data structure which
may offer better performance in some applications.
</para>
+ <para>
+ By supporting the ordering <-> operator the quad_point_ops and kd_point_ops provide
+ a user with the ability to perform a K-nearest-neighbour search over the indexed point dataset.
+ </para>
</sect1>
@@ -539,9 +545,12 @@ CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
typedef struct spgInnerConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
+ ScanKey orderbyKeys; /* array of ordering operators and comparison values */
int nkeys; /* length of array */
+ int norderbys; /* length of array */
Datum reconstructedValue; /* value reconstructed at parent */
+ Datum suppValue /* supplimentary value of parent */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
@@ -559,6 +568,8 @@ typedef struct spgInnerConsistentOut
int *nodeNumbers; /* their indexes in the node array */
int *levelAdds; /* increment level by this much for each */
Datum *reconstructedValues; /* associated reconstructed values */
+ Datum *suppValues; /* any additional data implementation needs to be stored in the child nodes */
+ double **distances; /* associated distances */
} spgInnerConsistentOut;
</programlisting>
@@ -573,10 +584,15 @@ typedef struct spgInnerConsistentOut
In particular it is not necessary to check <structfield>sk_flags</> to
see if the comparison value is NULL, because the SP-GiST core code
will filter out such conditions.
+ <structfield>orderbyKeys</>, of length <structfield>norderbys</>,
+ describes ordering operators (if any) in the same fashion.
<structfield>reconstructedValue</> is the value reconstructed for the
parent tuple; it is <literal>(Datum) 0</> at the root level or if the
<function>inner_consistent</> function did not provide a value at the
parent level.
+ <structfield>suppValue</> is any additional value that an implementation
+ decided to store for the parent node (<literal>(Datum) 0</> in case the
+ current node is root).
<structfield>level</> is the current inner tuple's level, starting at
zero for the root level.
<structfield>returnData</> is <literal>true</> if reconstructed data is
@@ -592,7 +608,6 @@ typedef struct spgInnerConsistentOut
<structfield>nNodes</> is the number of child nodes contained in the
inner tuple, and
<structfield>nodeLabels</> is an array of their label values, or
- NULL if the nodes do not have labels.
</para>
<para>
@@ -608,9 +623,17 @@ typedef struct spgInnerConsistentOut
<structfield>reconstructedValues</> to an array of the values
reconstructed for each child node to be visited; otherwise, leave
<structfield>reconstructedValues</> as NULL.
+ <structfield>suppValues</> serves the similiar purpose of holding
+ the implementation-defined data for the inner nodes.
+ <structfield>distances</> if the ordered search is carried out,
+ the implementation is supposed to fill them in accordance to the
+ ordering operators provided in <structfield>orderbyKeys</>
+ (nodes with lowest distances will be processed first). Leave it
+ NULL otherwise.
Note that the <function>inner_consistent</> function is
responsible for palloc'ing the
- <structfield>nodeNumbers</>, <structfield>levelAdds</> and
+ <structfield>nodeNumbers</>, <structfield>levelAdds</>,
+ <structfield>distances</>, <structfield>suppValues</> and
<structfield>reconstructedValues</> arrays.
</para>
</listitem>
@@ -636,7 +659,9 @@ CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
typedef struct spgLeafConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
+ ScanKey orderbykeys; /* array of ordering operators and comparison values */
int nkeys; /* length of array */
+ int norderbys; /* length of array */
Datum reconstructedValue; /* value reconstructed at parent */
int level; /* current level (counting from zero) */
@@ -649,6 +674,7 @@ typedef struct spgLeafConsistentOut
{
Datum leafValue; /* reconstructed original data, if any */
bool recheck; /* set true if operator must be rechecked */
+ double *distances; /* associated distances */
} spgLeafConsistentOut;
</programlisting>
@@ -663,6 +689,8 @@ typedef struct spgLeafConsistentOut
In particular it is not necessary to check <structfield>sk_flags</> to
see if the comparison value is NULL, because the SP-GiST core code
will filter out such conditions.
+ The array <structfield>orderbykeys>, of length <structfield>norderbys</>,
+ describes the ordering operators in the same fashion.
<structfield>reconstructedValue</> is the value reconstructed for the
parent tuple; it is <literal>(Datum) 0</> at the root level or if the
<function>inner_consistent</> function did not provide a value at the
@@ -685,6 +713,9 @@ typedef struct spgLeafConsistentOut
<structfield>recheck</> may be set to <literal>true</> if the match
is uncertain and so the operator(s) must be re-applied to the actual
heap tuple to verify the match.
+ In case when the ordered search is performed, <structfield>distances</>
+ should be set in accordance with the ordering operator provided, otherwise
+ implementation is supposed to set it to NULL.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/spgist/Makefile b/src/backend/access/spgist/Makefile
index 918da1f..c149f6b 100644
--- a/src/backend/access/spgist/Makefile
+++ b/src/backend/access/spgist/Makefile
@@ -14,6 +14,7 @@ include $(top_builddir)/src/Makefile.global
OBJS = spgutils.o spginsert.o spgscan.o spgvacuum.o \
spgdoinsert.o spgxlog.o \
- spgtextproc.o spgquadtreeproc.o spgkdtreeproc.o
+ spgtextproc.o spgquadtreeproc.o spgkdtreeproc.o \
+ spgproc.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/access/spgist/README b/src/backend/access/spgist/README
index 09ab21a..6e6f029 100644
--- a/src/backend/access/spgist/README
+++ b/src/backend/access/spgist/README
@@ -41,7 +41,12 @@ contain exactly one inner tuple.
When the search traversal algorithm reaches an inner tuple, it chooses a set
of nodes to continue tree traverse in depth. If it reaches a leaf page it
-scans a list of leaf tuples to find the ones that match the query.
+scans a list of leaf tuples to find the ones that match the query. SP-GiSTs
+also support ordered searches - that is during the scan is performed,
+implementation can choose to map floating-point distances to inner and leaf
+tuples and the traversal will be performed by the closest-first model. It
+can be usefull e.g. for performing nearest-neighbour searches on the dataset.
+
The insertion algorithm descends the tree similarly, except it must choose
just one node to descend to from each inner tuple. Insertion might also have
@@ -371,3 +376,4 @@ AUTHORS
Teodor Sigaev <teo...@sigaev.ru>
Oleg Bartunov <o...@sai.msu.su>
+ Vlad Sterzhanov <glide...@gmail.com>
diff --git a/src/backend/access/spgist/spgkdtreeproc.c b/src/backend/access/spgist/spgkdtreeproc.c
index a056563..bdfa60f 100644
--- a/src/backend/access/spgist/spgkdtreeproc.c
+++ b/src/backend/access/spgist/spgkdtreeproc.c
@@ -17,11 +17,11 @@
#include "access/gist.h" /* for RTree strategy numbers */
#include "access/spgist.h"
+#include "access/spgist_proc.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/geo_decls.h"
-
Datum
spg_kd_config(PG_FUNCTION_ARGS)
{
@@ -32,13 +32,14 @@ spg_kd_config(PG_FUNCTION_ARGS)
cfg->labelType = VOIDOID; /* we don't need node labels */
cfg->canReturnData = true;
cfg->longValuesOK = false;
+ cfg->suppLen = sizeof (BOX);
PG_RETURN_VOID();
}
static int
getSide(double coord, bool isX, Point *tst)
{
- double tstcoord = (isX) ? tst->x : tst->y;
+ double tstcoord = (isX) ? tst->x : tst->y;
if (coord == tstcoord)
return 0;
@@ -53,8 +54,8 @@ spg_kd_choose(PG_FUNCTION_ARGS)
{
spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
- Point *inPoint = DatumGetPointP(in->datum);
- double coord;
+ Point *inPoint = DatumGetPointP(in->datum);
+ double coord;
if (in->allTheSame)
elog(ERROR, "allTheSame should not occur for k-d trees");
@@ -75,8 +76,8 @@ spg_kd_choose(PG_FUNCTION_ARGS)
typedef struct SortedPoint
{
- Point *p;
- int i;
+ Point *p;
+ int i;
} SortedPoint;
static int
@@ -107,10 +108,10 @@ spg_kd_picksplit(PG_FUNCTION_ARGS)
{
spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
- int i;
- int middle;
+ int i;
+ int middle;
SortedPoint *sorted;
- double coord;
+ double coord;
sorted = palloc(sizeof(*sorted) * in->nTuples);
for (i = 0; i < in->nTuples; i++)
@@ -144,8 +145,8 @@ spg_kd_picksplit(PG_FUNCTION_ARGS)
*/
for (i = 0; i < in->nTuples; i++)
{
- Point *p = sorted[i].p;
- int n = sorted[i].i;
+ Point *p = sorted[i].p;
+ int n = sorted[i].i;
out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
out->leafTupleDatums[n] = PointPGetDatum(p);
@@ -159,9 +160,11 @@ spg_kd_inner_consistent(PG_FUNCTION_ARGS)
{
spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
- double coord;
- int which;
- int i;
+ double coord;
+ int which;
+ int i;
+ Datum *boxes = NULL;
+ out->distances = NULL;
Assert(in->hasPrefix);
coord = DatumGetFloat8(in->prefixDatum);
@@ -171,13 +174,18 @@ spg_kd_inner_consistent(PG_FUNCTION_ARGS)
Assert(in->nNodes == 2);
+ if (in->norderbys > 0)
+ {
+ out->distances = palloc(in->nNodes * sizeof (double *));
+ }
+
/* "which" is a bitmask of children that satisfy all constraints */
which = (1 << 1) | (1 << 2);
for (i = 0; i < in->nkeys; i++)
{
- Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
- BOX *boxQuery;
+ Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
+ BOX *boxQuery;
switch (in->scankeys[i].sk_strategy)
{
@@ -250,10 +258,61 @@ spg_kd_inner_consistent(PG_FUNCTION_ARGS)
/* We must descend into the children identified by which */
out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
out->nNodes = 0;
+
+ if (in->level == 0 && in->norderbys > 0)
+ {
+ BOX *newbox = palloc(sizeof(BOX));
+ Point newp;
+ newp.x = newp.y = get_float8_infinity();
+ newbox->high = newp;
+ newp.x = newp.y = -get_float8_infinity();
+ newbox->low = newp;
+ in->suppValue = PointerGetDatum(newbox);
+ }
+ if (DatumGetBoxP(in->suppValue) != NULL)
+ {
+ Point p1, p2;
+ BOX *area = DatumGetBoxP(in->suppValue);
+ BOX *newbox1 = (BOX *) palloc0(sizeof(BOX));
+ BOX *newbox2 = (BOX *) palloc0(sizeof(BOX));
+ boxes = (Datum *) palloc(sizeof(Datum) * 2);
+ out->suppValues = (Datum *) palloc(sizeof(Datum) * 2);
+ switch (in->level % 2)
+ {
+ case 0:
+ p1.x = p2.x = coord;
+ p1.y = area->high.y;
+ p2.y = area->low.y;
+ break;
+ case 1:
+ p1.y = p2.y = coord;
+ p1.x = area->high.x;
+ p2.x = area->low.x;
+ break;
+ }
+ newbox1->low = area->low;
+ newbox1->high = p1;
+ boxes[0] = BoxPGetDatum(newbox1);
+ newbox2->low = p2;
+ newbox2->high = area->high;
+ boxes[1] = BoxPGetDatum(newbox2);
+ }
+
for (i = 1; i <= 2; i++)
{
if (which & (1 << i))
+ {
out->nodeNumbers[out->nNodes++] = i - 1;
+ if (DatumGetBoxP(in->suppValue) != NULL)
+ {
+ out->suppValues[out->nNodes-1] = boxes[i-1];
+ }
+ if (in->norderbys > 0)
+ {
+ spg_point_distance(out->suppValues[out->nNodes-1],
+ in->norderbys, in->orderbyKeys, &out->distances[out->nNodes-1], false);
+ }
+ }
}
/* Set up level increments, too */
diff --git a/src/backend/access/spgist/spgproc.c b/src/backend/access/spgist/spgproc.c
new file mode 100644
index 0000000..601fdc9
--- /dev/null
+++ b/src/backend/access/spgist/spgproc.c
@@ -0,0 +1,167 @@
+#include "access/spgist_proc.h"
+
+int
+SpGistSearchTreeItemComparator(const RBNode *a, const RBNode *b, void *arg)
+{
+ const SpGistSearchTreeItem *sa = (const SpGistSearchTreeItem *) a;
+ const SpGistSearchTreeItem *sb = (const SpGistSearchTreeItem *) b;
+ IndexScanDesc scan = (IndexScanDesc) arg;
+ int i;
+
+ /* Order according to distance comparison */
+ for (i = 0; i < scan->numberOfOrderBys; i++)
+ {
+ if (sa->distances[i] != sb->distances[i])
+ return (sa->distances[i] > sb->distances[i]) ? 1 : -1;
+ }
+
+ return 0;
+}
+
+void
+SpGistSearchTreeItemCombiner(RBNode *existing, const RBNode *newrb, void *arg)
+{
+ SpGistSearchTreeItem *scurrent = (SpGistSearchTreeItem *) existing;
+ const SpGistSearchTreeItem *snew = (const SpGistSearchTreeItem *) newrb;
+ SpGistSearchItem *newitem = snew->head;
+
+ /* snew should have just one item in its chain */
+ Assert(newitem && newitem->next == NULL);
+
+ /*
+ * If new item is heap tuple, it goes to front of chain; otherwise insert
+ * it before the first index-page item, so that index pages are visited in
+ * LIFO order, ensuring depth-first search of index pages. See comments
+ * in gist_private.h.
+ */
+ if (SPGISTSearchItemIsHeap(*newitem))
+ {
+ newitem->next = scurrent->head;
+ scurrent->head = newitem;
+ if (scurrent->lastHeap == NULL)
+ scurrent->lastHeap = newitem;
+ }
+ else if (scurrent->lastHeap == NULL)
+ {
+ newitem->next = scurrent->head;
+ scurrent->head = newitem;
+ }
+ else
+ {
+ newitem->next = scurrent->lastHeap->next;
+ scurrent->lastHeap->next = newitem;
+ }
+}
+
+RBNode *
+SpGistSearchTreeItemAllocator(void *arg)
+{
+ IndexScanDesc scan = (IndexScanDesc) arg;
+
+ return (RBNode *) palloc(SPGISTHDRSZ + sizeof(double) * scan->numberOfOrderBys);
+}
+
+void
+SpGistSearchTreeItemDeleter(RBNode *rb, void *arg)
+{
+ pfree(rb);
+}
+
+/*
+ * Construct SpGistSearchTreeItem storing item and add it to queue
+ *
+ * Called in queue context
+ */
+void
+addSearchItemToQueue(IndexScanDesc scan, SpGistSearchItem *item, double *distances)
+{
+ bool isNew;
+ SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
+ SpGistSearchTreeItem *newItem = so->tmpTreeItem;
+ memcpy(newItem->distances, distances, scan->numberOfOrderBys * sizeof (double));
+ newItem->head = item;
+ item->next = NULL;
+ newItem->lastHeap = SPGISTSearchItemIsHeap(*item) ? item : NULL;
+ rb_insert(so->queue, (RBNode *) newItem, &isNew);
+}
+
+/*
+ * Leaf SpGistSearchItem constructor, called in queue context
+ */
+SpGistSearchItem *
+newHeapItem(SpGistScanOpaque so, int level,
+ ItemPointerData heapPtr, Datum leafValue, bool recheck, bool isnull)
+{
+ SpGistSearchItem *newItem = (SpGistSearchItem *) palloc(sizeof(SpGistSearchItem));
+ newItem->next = NULL;
+ newItem->level = level;
+ newItem->heap = heapPtr;
+ /* copy value to queue cxt out of tmp cxt */
+ newItem->value = datumCopy(leafValue, so->state.attType.attbyval,
+ so->state.attType.attlen);
+ newItem->itemState = recheck ? HEAP_RECHECK : HEAP_NORECHECK;
+ newItem->suppValue = (Datum) 0;
+ newItem->isnull = isnull;
+ return newItem;
+}
+
+void
+freeSearchTreeItem(SpGistScanOpaque so, SpGistSearchItem *item)
+{
+ if (so->state.config.suppLen > 0
+ && DatumGetPointer(item->suppValue) != NULL
+ && item->itemState == INNER)
+ {
+ pfree(DatumGetPointer(item->suppValue));
+ }
+ if (!so->state.attType.attbyval &&
+ DatumGetPointer(item->value) != NULL)
+ {
+ pfree(DatumGetPointer(item->value));
+ }
+
+ pfree(item);
+}
+
+/* Point-box distance in the assumption that box is aligned by axis */
+double
+dist_pb_simplified(Datum p, Datum b)
+{
+ Point *point = DatumGetPointP(p);
+ BOX *box = DatumGetBoxP(b);
+ double dx = 0.0, dy = 0.0;
+
+ if (point->x < box->low.x)
+ dx = box->low.x - point->x;
+ if (point->x > box->high.x)
+ dx = point->x - box->high.x;
+ if (point->y < box->low.y)
+ dy = box->low.y - point->y;
+ if (point->y > box->high.y)
+ dy = point->y - box->high.y;
+ return HYPOT(dx,dy);
+}
+
+void
+spg_point_distance(Datum to, int norderbys,
+ ScanKey orderbyKeys, double **distances, bool isLeaf)
+{
+ int sk_num;
+ double *distance;
+ *distances = (double *) malloc(norderbys * sizeof (double *));
+ distance = *distances;
+ for (sk_num = 0; sk_num < norderbys; ++sk_num)
+ {
+ Datum from_point = orderbyKeys[sk_num].sk_argument;
+ if (isLeaf)
+ {
+ *distance = DatumGetFloat8 (
+ DirectFunctionCall2(point_distance, from_point, to) );
+ }
+ else
+ {
+ *distance = dist_pb_simplified(from_point, to);
+ }
+ distance++;
+ }
+}
diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c
index 055f6b5..ca38de7 100644
--- a/src/backend/access/spgist/spgquadtreeproc.c
+++ b/src/backend/access/spgist/spgquadtreeproc.c
@@ -17,6 +17,7 @@
#include "access/gist.h" /* for RTree strategy numbers */
#include "access/spgist.h"
+#include "access/spgist_proc.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/geo_decls.h"
@@ -32,6 +33,7 @@ spg_quad_config(PG_FUNCTION_ARGS)
cfg->labelType = VOIDOID; /* we don't need node labels */
cfg->canReturnData = true;
cfg->longValuesOK = false;
+ cfg->suppLen = sizeof (BOX);
PG_RETURN_VOID();
}
@@ -83,8 +85,7 @@ spg_quad_choose(PG_FUNCTION_ARGS)
{
spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
- Point *inPoint = DatumGetPointP(in->datum),
- *centroid;
+ Point *inPoint = DatumGetPointP(in->datum), *centroid;
if (in->allTheSame)
{
@@ -112,8 +113,8 @@ spg_quad_choose(PG_FUNCTION_ARGS)
static int
x_cmp(const void *a, const void *b, void *arg)
{
- Point *pa = *(Point **) a;
- Point *pb = *(Point **) b;
+ Point *pa = *(Point **) a;
+ Point *pb = *(Point **) b;
if (pa->x == pb->x)
return 0;
@@ -123,8 +124,8 @@ x_cmp(const void *a, const void *b, void *arg)
static int
y_cmp(const void *a, const void *b, void *arg)
{
- Point *pa = *(Point **) a;
- Point *pb = *(Point **) b;
+ Point *pa = *(Point **) a;
+ Point *pb = *(Point **) b;
if (pa->y == pb->y)
return 0;
@@ -137,8 +138,8 @@ spg_quad_picksplit(PG_FUNCTION_ARGS)
{
spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
- int i;
- Point *centroid;
+ int i;
+ Point *centroid;
#ifdef USE_MEDIAN
/* Use the median values of x and y as the centroid point */
@@ -179,8 +180,8 @@ spg_quad_picksplit(PG_FUNCTION_ARGS)
for (i = 0; i < in->nTuples; i++)
{
- Point *p = DatumGetPointP(in->datums[i]);
- int quadrant = getQuadrant(centroid, p) - 1;
+ Point *p = DatumGetPointP(in->datums[i]);
+ int quadrant = getQuadrant(centroid, p) - 1;
out->leafTupleDatums[i] = PointPGetDatum(p);
out->mapTuplesToNodes[i] = quadrant;
@@ -195,12 +196,13 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
{
spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
- Point *centroid;
- int which;
- int i;
+ Point *centroid;
+ int which;
+ int i;
Assert(in->hasPrefix);
centroid = DatumGetPointP(in->prefixDatum);
+ out->distances = NULL;
if (in->allTheSame)
{
@@ -213,14 +215,19 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
}
Assert(in->nNodes == 4);
+
+ if (in->norderbys > 0)
+ {
+ out->distances = palloc(in->nNodes * sizeof (double *));
+ }
/* "which" is a bitmask of quadrants that satisfy all constraints */
which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
for (i = 0; i < in->nkeys; i++)
{
- Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
- BOX *boxQuery;
+ Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
+ BOX *boxQuery;
switch (in->scankeys[i].sk_strategy)
{
@@ -253,8 +260,8 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
- PointerGetDatum(boxQuery),
- PointerGetDatum(centroid))))
+ PointerGetDatum(boxQuery),
+ PointerGetDatum(centroid))))
{
/* centroid is in box, so all quadrants are OK */
}
@@ -283,16 +290,73 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
}
if (which == 0)
- break; /* no need to consider remaining conditions */
+ break; /* no need to consider remaining conditions */
}
+ out->levelAdds = palloc(sizeof(int) * 4);
+ for (i = 0; i < 4; ++i) out->levelAdds[i] = 1;
+
/* We must descend into the quadrant(s) identified by which */
out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
out->nNodes = 0;
+ if (in->level == 0 && in->norderbys > 0)
+ {
+ BOX *newbox = palloc(sizeof(BOX));
+ Point newp;
+ newp.x = newp.y = get_float8_infinity();
+ newbox->high = newp;
+ newp.x = newp.y = -get_float8_infinity();
+ newbox->low = newp;
+ in->suppValue = PointerGetDatum(newbox);
+ }
+ if (DatumGetBoxP(in->suppValue) != NULL)
+ out->suppValues = (Datum *) palloc(sizeof(Datum) * 4);
+
for (i = 1; i <= 4; i++)
{
if (which & (1 << i))
+ {
out->nodeNumbers[out->nNodes++] = i - 1;
+ if (DatumGetBoxP(in->suppValue) != NULL)
+ {
+ BOX *area = DatumGetBoxP(in->suppValue);
+ BOX *newbox = (BOX *) palloc0(sizeof(BOX));
+ Point p1, p2;
+ switch (i)
+ {
+ case 1:
+ newbox->high = area->high;
+ newbox->low = *centroid;
+ break;
+ case 2:
+ p1.y = centroid->y;
+ p1.x = area->high.x;
+ p2.y = area->low.y;
+ p2.x = centroid->x;
+ newbox->high = p1;
+ newbox->low = p2;
+ break;
+ case 3:
+ newbox->high = *centroid;
+ newbox->low = area->low;
+ break;
+ case 4:
+ p1.x = centroid->x;
+ p1.y = area->high.y;
+ p2.x = area->low.x;
+ p2.y = centroid->y;
+ newbox->high = p1;
+ newbox->low = p2;
+ break;
+ }
+ out->suppValues[out->nNodes-1] = BoxPGetDatum(newbox);
+ }
+ if (in->norderbys > 0)
+ {
+ spg_point_distance(out->suppValues[out->nNodes-1],
+ in->norderbys, in->orderbyKeys, &out->distances[out->nNodes-1], false);
+ }
+ }
}
PG_RETURN_VOID();
@@ -304,9 +368,10 @@ spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
{
spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
- Point *datum = DatumGetPointP(in->leafDatum);
- bool res;
- int i;
+ Point *datum = DatumGetPointP(in->leafDatum);
+ bool res;
+ int i;
+ out->distances = NULL;
/* all tests are exact */
out->recheck = false;
@@ -318,7 +383,7 @@ spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
res = true;
for (i = 0; i < in->nkeys; i++)
{
- Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
+ Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
switch (in->scankeys[i].sk_strategy)
{
@@ -355,6 +420,13 @@ spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
if (!res)
break;
}
+
+ if (res && in->norderbys > 0)
+ {
+ /* ok, it passes -> let's compute the distances */
+ spg_point_distance(in->leafDatum,
+ in->norderbys, in->orderbykeys, &out->distances, true);
+ }
PG_RETURN_BOOL(res);
}
diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c
index 35cc41b..0bf979e 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -17,79 +17,59 @@
#include "access/relscan.h"
#include "access/spgist_private.h"
+#include "access/spgist_proc.h"
#include "miscadmin.h"
#include "storage/bufmgr.h"
#include "utils/datum.h"
#include "utils/memutils.h"
#include "utils/rel.h"
-
typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr,
Datum leafValue, bool isnull, bool recheck);
-typedef struct ScanStackEntry
-{
- Datum reconstructedValue; /* value reconstructed from parent */
- int level; /* level of items on this page */
- ItemPointerData ptr; /* block and offset to scan from */
-} ScanStackEntry;
-
-
-/* Free a ScanStackEntry */
-static void
-freeScanStackEntry(SpGistScanOpaque so, ScanStackEntry *stackEntry)
-{
- if (!so->state.attType.attbyval &&
- DatumGetPointer(stackEntry->reconstructedValue) != NULL)
- pfree(DatumGetPointer(stackEntry->reconstructedValue));
- pfree(stackEntry);
-}
-
-/* Free the entire stack */
-static void
-freeScanStack(SpGistScanOpaque so)
-{
- ListCell *lc;
-
- foreach(lc, so->scanStack)
- {
- freeScanStackEntry(so, (ScanStackEntry *) lfirst(lc));
- }
- list_free(so->scanStack);
- so->scanStack = NIL;
-}
-
/*
- * Initialize scanStack to search the root page, resetting
+ * Initialize queue to search the root page, resetting
* any previously active scan
*/
static void
-resetSpGistScanOpaque(SpGistScanOpaque so)
+resetSpGistScanOpaque(IndexScanDesc scan)
{
- ScanStackEntry *startEntry;
+ SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
+ SpGistSearchItem *startEntry;
- freeScanStack(so);
+ MemoryContext oldCtx;
+ oldCtx = MemoryContextSwitchTo(so->queueCxt);
+ memset(so->distances, 0, sizeof(double) * scan->numberOfOrderBys);
+
if (so->searchNulls)
{
- /* Stack a work item to scan the null index entries */
- startEntry = (ScanStackEntry *) palloc0(sizeof(ScanStackEntry));
- ItemPointerSet(&startEntry->ptr, SPGIST_NULL_BLKNO, FirstOffsetNumber);
- so->scanStack = lappend(so->scanStack, startEntry);
+ /* Add a work item to scan the null index entries */
+ startEntry = (SpGistSearchItem *) palloc0(sizeof(SpGistSearchItem));
+ ItemPointerSet(&startEntry->heap, SPGIST_NULL_BLKNO, FirstOffsetNumber);
+ startEntry->itemState = INNER;
+ startEntry->level = 0;
+ startEntry->isnull = true;
+ addSearchItemToQueue(scan, startEntry, so->distances);
}
if (so->searchNonNulls)
{
- /* Stack a work item to scan the non-null index entries */
- startEntry = (ScanStackEntry *) palloc0(sizeof(ScanStackEntry));
- ItemPointerSet(&startEntry->ptr, SPGIST_ROOT_BLKNO, FirstOffsetNumber);
- so->scanStack = lappend(so->scanStack, startEntry);
+ /* Add a work item to scan the non-null index entries */
+ startEntry = (SpGistSearchItem *) palloc0(sizeof(SpGistSearchItem));
+ ItemPointerSet(&startEntry->heap, SPGIST_ROOT_BLKNO, FirstOffsetNumber);
+ startEntry->itemState = INNER;
+ startEntry->level = 0;
+ startEntry->isnull = false;
+ addSearchItemToQueue(scan, startEntry, so->distances);
}
+
+ MemoryContextSwitchTo(oldCtx);
if (so->want_itup)
{
/* Must pfree IndexTuples to avoid memory leak */
- int i;
+ int i;
for (i = 0; i < so->nPtrs; i++)
pfree(so->indexTups[i]);
@@ -103,7 +83,7 @@ resetSpGistScanOpaque(SpGistScanOpaque so)
* Sets searchNulls, searchNonNulls, numberOfKeys, keyData fields of *so.
*
* The point here is to eliminate null-related considerations from what the
- * opclass consistent functions need to deal with. We assume all SPGiST-
+ * opclass consistent functions need to deal with. We assume all SPGiST-
* indexable operators are strict, so any null RHS value makes the scan
* condition unsatisfiable. We also pull out any IS NULL/IS NOT NULL
* conditions; their effect is reflected into searchNulls/searchNonNulls.
@@ -112,11 +92,11 @@ static void
spgPrepareScanKeys(IndexScanDesc scan)
{
SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
- bool qual_ok;
- bool haveIsNull;
- bool haveNotNull;
- int nkeys;
- int i;
+ bool qual_ok;
+ bool haveIsNull;
+ bool haveNotNull;
+ int nkeys;
+ int i;
if (scan->numberOfKeys <= 0)
{
@@ -133,7 +113,7 @@ spgPrepareScanKeys(IndexScanDesc scan)
nkeys = 0;
for (i = 0; i < scan->numberOfKeys; i++)
{
- ScanKey skey = &scan->keyData[i];
+ ScanKey skey = &scan->keyData[i];
if (skey->sk_flags & SK_SEARCHNULL)
haveIsNull = true;
@@ -176,14 +156,14 @@ spgPrepareScanKeys(IndexScanDesc scan)
Datum
spgbeginscan(PG_FUNCTION_ARGS)
{
- Relation rel = (Relation) PG_GETARG_POINTER(0);
- int keysz = PG_GETARG_INT32(1);
+ Relation rel = (Relation) PG_GETARG_POINTER(0);
+ int keysz = PG_GETARG_INT32(1);
+ int orderbys = PG_GETARG_INT32(2);
- /* ScanKey scankey = (ScanKey) PG_GETARG_POINTER(2); */
IndexScanDesc scan;
SpGistScanOpaque so;
- scan = RelationGetIndexScan(rel, keysz, 0);
+ scan = RelationGetIndexScan(rel, keysz, orderbys);
so = (SpGistScanOpaque) palloc0(sizeof(SpGistScanOpaqueData));
if (keysz > 0)
@@ -191,6 +171,7 @@ spgbeginscan(PG_FUNCTION_ARGS)
else
so->keyData = NULL;
initSpGistState(&so->state, scan->indexRelation);
+
so->tempCxt = AllocSetContextCreate(CurrentMemoryContext,
"SP-GiST search temporary context",
ALLOCSET_DEFAULT_MINSIZE,
@@ -199,9 +180,17 @@ spgbeginscan(PG_FUNCTION_ARGS)
/* Set up indexTupDesc and xs_itupdesc in case it's an index-only scan */
so->indexTupDesc = scan->xs_itupdesc = RelationGetDescr(rel);
+ so->tmpTreeItem = palloc(SPGISTHDRSZ + sizeof(double) * scan->numberOfOrderBys);
+ so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
scan->opaque = so;
+ so->queueCxt = AllocSetContextCreate(CurrentMemoryContext,
+ "SP-GiST queue context",
+ ALLOCSET_DEFAULT_MINSIZE,
+ ALLOCSET_DEFAULT_INITSIZE,
+ ALLOCSET_DEFAULT_MAXSIZE);
+
PG_RETURN_POINTER(scan);
}
@@ -210,20 +199,40 @@ spgrescan(PG_FUNCTION_ARGS)
{
IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
- ScanKey scankey = (ScanKey) PG_GETARG_POINTER(1);
+ ScanKey scankeys = (ScanKey) PG_GETARG_POINTER(1);
+ ScanKey orderbys = (ScanKey) PG_GETARG_POINTER(3);
+
+ MemoryContext oldCxt;
/* copy scankeys into local storage */
- if (scankey && scan->numberOfKeys > 0)
+ if (scankeys && scan->numberOfKeys > 0)
{
- memmove(scan->keyData, scankey,
+ memmove(scan->keyData, scankeys,
scan->numberOfKeys * sizeof(ScanKeyData));
}
/* preprocess scankeys, set up the representation in *so */
spgPrepareScanKeys(scan);
- /* set up starting stack entries */
- resetSpGistScanOpaque(so);
+ MemoryContextReset(so->queueCxt);
+ oldCxt = MemoryContextSwitchTo(so->queueCxt);
+ so->queue = rb_create(SPGISTHDRSZ + sizeof (double) * scan->numberOfOrderBys,
+ SpGistSearchTreeItemComparator,
+ SpGistSearchTreeItemCombiner,
+ SpGistSearchTreeItemAllocator,
+ SpGistSearchTreeItemDeleter,
+ scan);
+ MemoryContextSwitchTo(oldCxt);
+
+ /* set up starting queue entries */
+ resetSpGistScanOpaque(scan);
+ so->curTreeItem = NULL;
+
+ if (orderbys && scan->numberOfOrderBys > 0)
+ {
+ memmove(scan->orderByData, orderbys,
+ scan->numberOfOrderBys * sizeof(ScanKeyData));
+ }
PG_RETURN_VOID();
}
@@ -235,6 +244,9 @@ spgendscan(PG_FUNCTION_ARGS)
SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
MemoryContextDelete(so->tempCxt);
+ MemoryContextDelete(so->queueCxt);
+ pfree(so->tmpTreeItem);
+ if(scan->numberOfOrderBys > 0) pfree(so->distances);
PG_RETURN_VOID();
}
@@ -255,43 +267,47 @@ spgrestrpos(PG_FUNCTION_ARGS)
/*
* Test whether a leaf tuple satisfies all the scan keys
- *
- * *leafValue is set to the reconstructed datum, if provided
- * *recheck is set true if any of the operators are lossy
+ *
+ * *reportedSome is set to true if:
+ * the scan is not ordered AND the item satisfies the scankeys
*/
static bool
-spgLeafTest(Relation index, SpGistScanOpaque so,
+spgLeafTest(Relation index, IndexScanDesc scan,
SpGistLeafTuple leafTuple, bool isnull,
int level, Datum reconstructedValue,
- Datum *leafValue, bool *recheck)
+ bool *reportedSome, storeRes_func storeRes)
{
- bool result;
- Datum leafDatum;
+ bool result;
+ Datum leafDatum;
spgLeafConsistentIn in;
spgLeafConsistentOut out;
- FmgrInfo *procinfo;
- MemoryContext oldCtx;
+ FmgrInfo *procinfo;
+ SpGistScanOpaque so = scan->opaque;
+ Datum leafValue;
+ bool recheck;
+ /* use temp context for calling leaf_consistent */
+ MemoryContext oldCtx = MemoryContextSwitchTo(so->tempCxt);
if (isnull)
{
/* Should not have arrived on a nulls page unless nulls are wanted */
Assert(so->searchNulls);
- *leafValue = (Datum) 0;
- *recheck = false;
- return true;
+ leafValue = (Datum) 0;
+ recheck = false;
+ result = true;
+ goto report;
}
leafDatum = SGLTDATUM(leafTuple, &so->state);
- /* use temp context for calling leaf_consistent */
- oldCtx = MemoryContextSwitchTo(so->tempCxt);
-
in.scankeys = so->keyData;
in.nkeys = so->numberOfKeys;
in.reconstructedValue = reconstructedValue;
in.level = level;
in.returnData = so->want_itup;
in.leafDatum = leafDatum;
+ in.orderbykeys = scan->orderByData;
+ in.norderbys = scan->numberOfOrderBys;
out.leafValue = (Datum) 0;
out.recheck = false;
@@ -301,15 +317,215 @@ spgLeafTest(Relation index, SpGistScanOpaque so,
index->rd_indcollation[0],
PointerGetDatum(&in),
PointerGetDatum(&out)));
-
- *leafValue = out.leafValue;
- *recheck = out.recheck;
-
+ recheck = out.recheck;
+ leafValue = out.leafValue;
+
+report:
+ if (result)
+ {
+ /* item passes the scankeys */
+ if (scan->numberOfOrderBys > 0)
+ {
+ /* the scan is ordered -> add the item to the queue */
+ if (isnull)
+ {
+ /* Assume that all distances for null entries are infinities */
+ int i;
+ out.distances = palloc(scan->numberOfOrderBys * sizeof(double));
+ for (i = 0; i < scan->numberOfOrderBys; ++i)
+ out.distances[i] = get_float8_infinity();
+ }
+ MemoryContextSwitchTo(so->queueCxt);
+ addSearchItemToQueue(scan,
+ newHeapItem(so, level, leafTuple->heapPtr, leafValue, recheck, isnull),
+ out.distances);
+ }
+ else
+ {
+ /* non-ordered scan, so report the item right away */
+ MemoryContextSwitchTo(oldCtx);
+ storeRes(so, &leafTuple->heapPtr, leafValue, isnull, recheck);
+ *reportedSome = true;
+ }
+ }
MemoryContextSwitchTo(oldCtx);
return result;
}
+void
+spgInnerTest(Relation index, IndexScanDesc scan, SpGistSearchItem *item,
+ SpGistInnerTuple innerTuple, bool isnull)
+{
+ spgInnerConsistentIn in;
+ spgInnerConsistentOut out;
+ FmgrInfo *consistent_procinfo;
+ SpGistNodeTuple *nodes;
+ SpGistNodeTuple node;
+ int i;
+ SpGistScanOpaque so = scan->opaque;
+ MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
+ double *inf_distances = palloc(scan->numberOfOrderBys * sizeof (double));
+ for (i = 0; i < scan->numberOfOrderBys; ++i)
+ inf_distances[i] = get_float8_infinity();
+
+ inner_consistent_input_init(&in, scan, item, innerTuple);
+
+ /* collect node pointers */
+ nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * in.nNodes);
+ SGITITERATE(innerTuple, i, node)
+ {
+ nodes[i] = node;
+ }
+
+ memset(&out, 0, sizeof(out));
+
+ if (!isnull)
+ {
+ /* use user-defined inner consistent method */
+ consistent_procinfo = index_getprocinfo(index, 1, SPGIST_INNER_CONSISTENT_PROC);
+ FunctionCall2Coll(consistent_procinfo,
+ index->rd_indcollation[0],
+ PointerGetDatum(&in),
+ PointerGetDatum(&out));
+ }
+ else
+ {
+ /* force all children to 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;
+ }
+ }
+
+ MemoryContextSwitchTo(so->queueCxt);
+
+ /* If allTheSame, they should all or none of 'em match */
+ if (innerTuple->allTheSame)
+ if (out.nNodes != 0 && out.nNodes != in.nNodes)
+ elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
+
+ for (i = 0; i < out.nNodes; i++)
+ {
+ int nodeN = out.nodeNumbers[i];
+
+ Assert(nodeN >= 0 && nodeN < in.nNodes);
+ if (ItemPointerIsValid(&nodes[nodeN]->t_tid))
+ {
+ double *distances;
+ SpGistSearchItem *newItem;
+
+ /* Create new work item for this node */
+ newItem = palloc(sizeof(SpGistSearchItem));
+ newItem->heap = nodes[nodeN]->t_tid;
+ if (out.levelAdds)
+ newItem->level = item->level + out.levelAdds[i];
+ else
+ newItem->level = item->level;
+ /* Must copy value out of temp context */
+ if (out.reconstructedValues)
+ {
+ newItem->value =
+ datumCopy(out.reconstructedValues[i],
+ so->state.attType.attbyval,
+ so->state.attType.attlen);
+ }
+ else
+ {
+ newItem->value = (Datum) 0;
+ }
+
+ if (out.suppValues)
+ {
+ newItem->suppValue =
+ datumCopy(out.suppValues[i], false,
+ so->state.config.suppLen);
+ }
+ else
+ {
+ newItem->suppValue = (Datum) 0;
+ }
+
+ if (out.distances != NULL)
+ {
+ /* Will copy out the distances in addSearchItemToQueue anyway */
+ distances = out.distances[i];
+ }
+ else
+ {
+ distances = inf_distances;
+ }
+ newItem->itemState = INNER;
+ newItem->isnull = isnull;
+ addSearchItemToQueue(scan, newItem, distances);
+ }
+ }
+ MemoryContextSwitchTo(oldCxt);
+}
+
+/* A bundle initializer for inner_consistent methods */
+void
+inner_consistent_input_init(spgInnerConsistentIn *in, IndexScanDesc scan,
+ SpGistSearchItem *item, SpGistInnerTuple innerTuple)
+{
+ SpGistScanOpaque so = scan->opaque;
+ in->scankeys = so->keyData;
+ in->nkeys = so->numberOfKeys;
+ in->reconstructedValue = item->value;
+ in->level = item->level;
+ in->returnData = so->want_itup;
+ in->allTheSame = innerTuple->allTheSame;
+ in->hasPrefix = (innerTuple->prefixSize > 0);
+ in->prefixDatum = SGITDATUM(innerTuple, &so->state);
+ in->nNodes = innerTuple->nNodes;
+ in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
+ in->norderbys = scan->numberOfOrderBys;
+ in->orderbyKeys = scan->orderByData;
+ in->suppValue = item->suppValue;
+}
+
+/* Returns a next item in an (ordered) scan or null if the index is exhausted */
+SpGistSearchItem *
+getNextQueueItem(SpGistScanOpaque so)
+{
+ MemoryContext oldCxt = MemoryContextSwitchTo(so->queueCxt);
+ SpGistSearchItem *item = NULL;
+
+ while (item == NULL)
+ {
+ /* Update curTreeItem if we don't have one */
+ if (so->curTreeItem == NULL)
+ {
+ so->curTreeItem = (SpGistSearchTreeItem *) rb_leftmost(so->queue);
+ /* Done when tree is empty */
+ if (so->curTreeItem == NULL)
+ {
+ break;
+ }
+ }
+
+ item = so->curTreeItem->head;
+ if (item != NULL)
+ {
+ /* Delink item from chain */
+ so->curTreeItem->head = item->next;
+ if (item == so->curTreeItem->lastHeap)
+ so->curTreeItem->lastHeap = NULL;
+ }
+ else
+ {
+ /* curTreeItem is exhausted, so remove it from rbtree */
+ rb_delete(so->queue, (RBNode *) so->curTreeItem);
+ so->curTreeItem = NULL;
+ }
+ }
+
+ MemoryContextSwitchTo(oldCxt);
+ return item;
+}
+
/*
* Walk the tree and report all tuples passing the scan quals to the storeRes
* subroutine.
@@ -318,250 +534,162 @@ spgLeafTest(Relation index, SpGistScanOpaque so,
* next page boundary once we have reported at least one tuple.
*/
static void
-spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
+spgWalk(Relation index, IndexScanDesc scan, bool scanWholeIndex,
storeRes_func storeRes)
{
Buffer buffer = InvalidBuffer;
bool reportedSome = false;
-
+ SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
+
while (scanWholeIndex || !reportedSome)
{
- ScanStackEntry *stackEntry;
BlockNumber blkno;
OffsetNumber offset;
Page page;
bool isnull;
- /* Pull next to-do item from the list */
- if (so->scanStack == NIL)
- break; /* there are no more pages to scan */
-
- stackEntry = (ScanStackEntry *) linitial(so->scanStack);
- so->scanStack = list_delete_first(so->scanStack);
+ SpGistSearchItem *item = getNextQueueItem(so);
+ if (item == NULL)
+ {
+ /* No more items in queue -> done */
+ if (buffer != InvalidBuffer)
+ UnlockReleaseBuffer(buffer);
+ return;
+ }
redirect:
/* Check for interrupts, just in case of infinite loop */
CHECK_FOR_INTERRUPTS();
- blkno = ItemPointerGetBlockNumber(&stackEntry->ptr);
- offset = ItemPointerGetOffsetNumber(&stackEntry->ptr);
-
- if (buffer == InvalidBuffer)
+ if (SPGISTSearchItemIsHeap(*item))
{
- buffer = ReadBuffer(index, blkno);
- LockBuffer(buffer, BUFFER_LOCK_SHARE);
- }
- else if (blkno != BufferGetBlockNumber(buffer))
+ /* We store heap items in the queue only in case of ordered search */
+ Assert(scan->numberOfOrderBys > 0);
+ storeRes(so, &item->heap, item->value, item->isnull,
+ item->itemState == HEAP_RECHECK);
+ reportedSome = true;
+ }
+ else
{
- UnlockReleaseBuffer(buffer);
- buffer = ReadBuffer(index, blkno);
- LockBuffer(buffer, BUFFER_LOCK_SHARE);
- }
- /* else new pointer points to the same page, no work needed */
+ blkno = ItemPointerGetBlockNumber(&item->heap);
+ offset = ItemPointerGetOffsetNumber(&item->heap);
- page = BufferGetPage(buffer);
+ if (buffer == InvalidBuffer)
+ {
+ buffer = ReadBuffer(index, blkno);
+ LockBuffer(buffer, BUFFER_LOCK_SHARE);
+ }
+ else if (blkno != BufferGetBlockNumber(buffer))
+ {
+ UnlockReleaseBuffer(buffer);
+ buffer = ReadBuffer(index, blkno);
+ LockBuffer(buffer, BUFFER_LOCK_SHARE);
+ }
- isnull = SpGistPageStoresNulls(page) ? true : false;
+ /* else new pointer points to the same page, no work needed */
- if (SpGistPageIsLeaf(page))
- {
- SpGistLeafTuple leafTuple;
- OffsetNumber max = PageGetMaxOffsetNumber(page);
- Datum leafValue = (Datum) 0;
- bool recheck = false;
+ page = BufferGetPage(buffer);
+
+ isnull = SpGistPageStoresNulls(page) ? true : false;
- if (SpGistBlockIsRoot(blkno))
+ if (SpGistPageIsLeaf(page))
{
- /* When root is a leaf, examine all its tuples */
- for (offset = FirstOffsetNumber; offset <= max; offset++)
+ /* Page is a leaf - that is, all it's tuples are heap items */
+ SpGistLeafTuple leafTuple;
+ OffsetNumber max = PageGetMaxOffsetNumber(page);
+
+ if (SpGistBlockIsRoot(blkno))
{
- leafTuple = (SpGistLeafTuple)
- PageGetItem(page, PageGetItemId(page, offset));
- if (leafTuple->tupstate != SPGIST_LIVE)
+ /* When root is a leaf, examine all its tuples */
+ for (offset = FirstOffsetNumber; offset <= max; offset++)
{
- /* all tuples on root should be live */
- elog(ERROR, "unexpected SPGiST tuple state: %d",
- leafTuple->tupstate);
- }
+ leafTuple = (SpGistLeafTuple)
+ PageGetItem(page, PageGetItemId(page, offset));
+ if (leafTuple->tupstate != SPGIST_LIVE)
+ {
+ /* all tuples on root should be live */
+ elog(ERROR, "unexpected SPGiST tuple state: %d",
+ leafTuple->tupstate);
+ }
- Assert(ItemPointerIsValid(&leafTuple->heapPtr));
- if (spgLeafTest(index, so,
- leafTuple, isnull,
- stackEntry->level,
- stackEntry->reconstructedValue,
- &leafValue,
- &recheck))
- {
- storeRes(so, &leafTuple->heapPtr,
- leafValue, isnull, recheck);
- reportedSome = true;
+ Assert(ItemPointerIsValid(&leafTuple->heapPtr));
+ spgLeafTest(index, scan, leafTuple, isnull, item->level,
+ item->value, &reportedSome, storeRes);
}
}
- }
- else
- {
- /* Normal case: just examine the chain we arrived at */
- while (offset != InvalidOffsetNumber)
+ else
{
- Assert(offset >= FirstOffsetNumber && offset <= max);
- leafTuple = (SpGistLeafTuple)
- PageGetItem(page, PageGetItemId(page, offset));
- if (leafTuple->tupstate != SPGIST_LIVE)
+ /* Normal case: just examine the chain we arrived at */
+ while (offset != InvalidOffsetNumber)
{
- if (leafTuple->tupstate == SPGIST_REDIRECT)
- {
- /* redirection tuple should be first in chain */
- Assert(offset == ItemPointerGetOffsetNumber(&stackEntry->ptr));
- /* transfer attention to redirect point */
- stackEntry->ptr = ((SpGistDeadTuple) leafTuple)->pointer;
- Assert(ItemPointerGetBlockNumber(&stackEntry->ptr) != SPGIST_METAPAGE_BLKNO);
- goto redirect;
- }
- if (leafTuple->tupstate == SPGIST_DEAD)
+ Assert(offset >= FirstOffsetNumber && offset <= max);
+ leafTuple = (SpGistLeafTuple)
+ PageGetItem(page, PageGetItemId(page, offset));
+ if (leafTuple->tupstate != SPGIST_LIVE)
{
- /* dead tuple should be first in chain */
- Assert(offset == ItemPointerGetOffsetNumber(&stackEntry->ptr));
- /* No live entries on this page */
- Assert(leafTuple->nextOffset == InvalidOffsetNumber);
- break;
+ if (leafTuple->tupstate == SPGIST_REDIRECT)
+ {
+ /* redirection tuple should be first in chain */
+ Assert(offset == ItemPointerGetOffsetNumber(&item->heap));
+ /* transfer attention to redirect point */
+ item->heap = ((SpGistDeadTuple) leafTuple)->pointer;
+ Assert(ItemPointerGetBlockNumber(&item->heap) != SPGIST_METAPAGE_BLKNO);
+ goto redirect;
+ }
+ if (leafTuple->tupstate == SPGIST_DEAD)
+ {
+ /* dead tuple should be first in chain */
+ Assert(offset == ItemPointerGetOffsetNumber(&item->heap));
+ /* No live entries on this page */
+ Assert(leafTuple->nextOffset == InvalidOffsetNumber);
+ break;
+ }
+ /* We should not arrive at a placeholder */
+ elog(ERROR, "unexpected SPGiST tuple state: %d",
+ leafTuple->tupstate);
}
- /* We should not arrive at a placeholder */
- elog(ERROR, "unexpected SPGiST tuple state: %d",
- leafTuple->tupstate);
- }
- Assert(ItemPointerIsValid(&leafTuple->heapPtr));
- if (spgLeafTest(index, so,
- leafTuple, isnull,
- stackEntry->level,
- stackEntry->reconstructedValue,
- &leafValue,
- &recheck))
- {
- storeRes(so, &leafTuple->heapPtr,
- leafValue, isnull, recheck);
- reportedSome = true;
+ Assert(ItemPointerIsValid(&leafTuple->heapPtr));
+ spgLeafTest(index, scan, leafTuple, isnull, item->level,
+ item->value, &reportedSome, storeRes);
+ offset = leafTuple->nextOffset;
}
-
- offset = leafTuple->nextOffset;
}
}
- }
- else /* page is inner */
- {
- SpGistInnerTuple innerTuple;
- spgInnerConsistentIn in;
- spgInnerConsistentOut out;
- FmgrInfo *procinfo;
- SpGistNodeTuple *nodes;
- SpGistNodeTuple node;
- int i;
- MemoryContext oldCtx;
-
- innerTuple = (SpGistInnerTuple) PageGetItem(page,
- PageGetItemId(page, offset));
-
- if (innerTuple->tupstate != SPGIST_LIVE)
- {
- if (innerTuple->tupstate == SPGIST_REDIRECT)
- {
- /* transfer attention to redirect point */
- stackEntry->ptr = ((SpGistDeadTuple) innerTuple)->pointer;
- Assert(ItemPointerGetBlockNumber(&stackEntry->ptr) != SPGIST_METAPAGE_BLKNO);
- goto redirect;
- }
- elog(ERROR, "unexpected SPGiST tuple state: %d",
- innerTuple->tupstate);
- }
-
- /* use temp context for calling inner_consistent */
- oldCtx = MemoryContextSwitchTo(so->tempCxt);
-
- in.scankeys = so->keyData;
- in.nkeys = so->numberOfKeys;
- in.reconstructedValue = stackEntry->reconstructedValue;
- in.level = stackEntry->level;
- in.returnData = so->want_itup;
- in.allTheSame = innerTuple->allTheSame;
- in.hasPrefix = (innerTuple->prefixSize > 0);
- in.prefixDatum = SGITDATUM(innerTuple, &so->state);
- in.nNodes = innerTuple->nNodes;
- in.nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
-
- /* collect node pointers */
- nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * in.nNodes);
- SGITITERATE(innerTuple, i, node)
- {
- nodes[i] = node;
- }
-
- memset(&out, 0, sizeof(out));
-
- if (!isnull)
- {
- /* use user-defined inner consistent method */
- procinfo = index_getprocinfo(index, 1, SPGIST_INNER_CONSISTENT_PROC);
- FunctionCall2Coll(procinfo,
- index->rd_indcollation[0],
- PointerGetDatum(&in),
- PointerGetDatum(&out));
- }
- else
+ else /* page is inner */
{
- /* force all children to 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;
- }
-
- MemoryContextSwitchTo(oldCtx);
+ SpGistInnerTuple innerTuple =
+ (SpGistInnerTuple) PageGetItem(page,
+ PageGetItemId(page, offset));
- /* If allTheSame, they should all or none of 'em match */
- if (innerTuple->allTheSame)
- if (out.nNodes != 0 && out.nNodes != in.nNodes)
- elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
-
- for (i = 0; i < out.nNodes; i++)
- {
- int nodeN = out.nodeNumbers[i];
-
- Assert(nodeN >= 0 && nodeN < in.nNodes);
- if (ItemPointerIsValid(&nodes[nodeN]->t_tid))
+ if (innerTuple->tupstate != SPGIST_LIVE)
{
- ScanStackEntry *newEntry;
-
- /* Create new work item for this node */
- newEntry = palloc(sizeof(ScanStackEntry));
- newEntry->ptr = nodes[nodeN]->t_tid;
- if (out.levelAdds)
- newEntry->level = stackEntry->level + out.levelAdds[i];
- else
- newEntry->level = stackEntry->level;
- /* Must copy value out of temp context */
- if (out.reconstructedValues)
- newEntry->reconstructedValue =
- datumCopy(out.reconstructedValues[i],
- so->state.attType.attbyval,
- so->state.attType.attlen);
- else
- newEntry->reconstructedValue = (Datum) 0;
-
- so->scanStack = lcons(newEntry, so->scanStack);
+ if (innerTuple->tupstate == SPGIST_REDIRECT)
+ {
+ /* transfer attention to redirect point */
+ item->heap = ((SpGistDeadTuple) innerTuple)->pointer;
+ Assert(ItemPointerGetBlockNumber(&item->heap) != SPGIST_METAPAGE_BLKNO);
+ goto redirect;
+ }
+ elog(ERROR, "unexpected SPGiST tuple state: %d",
+ innerTuple->tupstate);
}
+
+ spgInnerTest(index, scan, item, innerTuple, isnull);
}
}
- /* done with this scan stack entry */
- freeScanStackEntry(so, stackEntry);
+ /* done with this scan entry */
+ freeSearchTreeItem(so, item);
/* clear temp context before proceeding to the next one */
MemoryContextReset(so->tempCxt);
}
- if (buffer != InvalidBuffer)
+ if (buffer != InvalidBuffer)
UnlockReleaseBuffer(buffer);
}
+
/* storeRes subroutine for getbitmap case */
static void
storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr,
@@ -584,7 +712,7 @@ spggetbitmap(PG_FUNCTION_ARGS)
so->tbm = tbm;
so->ntids = 0;
- spgWalk(scan->indexRelation, so, true, storeBitmap);
+ spgWalk(scan->indexRelation, scan, true, storeBitmap);
PG_RETURN_INT64(so->ntids);
}
@@ -600,7 +728,7 @@ storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
if (so->want_itup)
{
/*
- * Reconstruct desired IndexTuple. We have to copy the datum out of
+ * Reconstruct desired IndexTuple. We have to copy the datum out of
* the temp context anyway, so we may as well create the tuple here.
*/
so->indexTups[so->nPtrs] = index_form_tuple(so->indexTupDesc,
@@ -627,7 +755,7 @@ spggettuple(PG_FUNCTION_ARGS)
{
if (so->iPtr < so->nPtrs)
{
- /* continuing to return tuples from a leaf page */
+ /* continuing to return reported tuples */
scan->xs_ctup.t_self = so->heapPtrs[so->iPtr];
scan->xs_recheck = so->recheck[so->iPtr];
scan->xs_itup = so->indexTups[so->iPtr];
@@ -641,11 +769,13 @@ spggettuple(PG_FUNCTION_ARGS)
int i;
for (i = 0; i < so->nPtrs; i++)
+ {
pfree(so->indexTups[i]);
+ }
}
so->iPtr = so->nPtrs = 0;
- spgWalk(scan->indexRelation, so, false, storeGettuple);
+ spgWalk(scan->indexRelation, scan, false, storeGettuple);
if (so->nPtrs == 0)
break; /* must have completed scan */
@@ -657,7 +787,7 @@ spggettuple(PG_FUNCTION_ARGS)
Datum
spgcanreturn(PG_FUNCTION_ARGS)
{
- Relation index = (Relation) PG_GETARG_POINTER(0);
+ Relation index = (Relation) PG_GETARG_POINTER(0);
SpGistCache *cache;
/* We can do it if the opclass config function says so */
diff --git a/src/backend/access/spgist/spgtextproc.c b/src/backend/access/spgist/spgtextproc.c
index 1ea1dd1..bb9e2e6 100644
--- a/src/backend/access/spgist/spgtextproc.c
+++ b/src/backend/access/spgist/spgtextproc.c
@@ -85,6 +85,7 @@ spg_text_config(PG_FUNCTION_ARGS)
cfg->labelType = INT2OID;
cfg->canReturnData = true;
cfg->longValuesOK = true; /* suffixing will shorten long values */
+ cfg->suppLen = 0; /* we don't need any supplimentary data */
PG_RETURN_VOID();
}
diff --git a/src/backend/utils/adt/rangetypes_spgist.c b/src/backend/utils/adt/rangetypes_spgist.c
index 1b83941..fde78d8 100644
--- a/src/backend/utils/adt/rangetypes_spgist.c
+++ b/src/backend/utils/adt/rangetypes_spgist.c
@@ -73,6 +73,7 @@ spg_range_quad_config(PG_FUNCTION_ARGS)
cfg->labelType = VOIDOID; /* we don't need node labels */
cfg->canReturnData = true;
cfg->longValuesOK = false;
+ cfg->suppLen = 0; /* we don't need any supplimentary data */
PG_RETURN_VOID();
}
diff --git a/src/include/access/spgist.h b/src/include/access/spgist.h
index 7f8655c..19a676a 100644
--- a/src/include/access/spgist.h
+++ b/src/include/access/spgist.h
@@ -45,6 +45,9 @@ typedef struct spgConfigOut
Oid labelType; /* Data type of inner-tuple node labels */
bool canReturnData; /* Opclass can reconstruct original data */
bool longValuesOK; /* Opclass can cope with values > 1 page */
+ /* If opclass needs to store any supplimentary data in nodes during the
+ scan - the size of the structure */
+ int suppLen;
} spgConfigOut;
/*
@@ -129,18 +132,21 @@ typedef struct spgPickSplitOut
typedef struct spgInnerConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
- int nkeys; /* length of array */
+ ScanKey orderbyKeys;
+ int nkeys; /* length of array */
+ int norderbys;
Datum reconstructedValue; /* value reconstructed at parent */
+ Datum suppValue; /* supplimentary value of parent */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
- Datum prefixDatum; /* if so, the prefix value */
+ Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
- Datum *nodeLabels; /* node label values (NULL if none) */
+ Datum *nodeLabels; /* node label values (NULL if none) */
} spgInnerConsistentIn;
typedef struct spgInnerConsistentOut
@@ -149,6 +155,8 @@ typedef struct spgInnerConsistentOut
int *nodeNumbers; /* their indexes in the node array */
int *levelAdds; /* increment level by this much for each */
Datum *reconstructedValues; /* associated reconstructed values */
+ Datum *suppValues; /* any additional data implementation needs to be stored in the child nodes */
+ double **distances; /* associated distances */
} spgInnerConsistentOut;
/*
@@ -157,7 +165,9 @@ typedef struct spgInnerConsistentOut
typedef struct spgLeafConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
- int nkeys; /* length of array */
+ ScanKey orderbykeys; /* array of ordering operators and comparison values */
+ int nkeys; /* length of array */
+ int norderbys;
Datum reconstructedValue; /* value reconstructed at parent */
int level; /* current level (counting from zero) */
@@ -170,6 +180,7 @@ typedef struct spgLeafConsistentOut
{
Datum leafValue; /* reconstructed original data, if any */
bool recheck; /* set true if operator must be rechecked */
+ double *distances; /* associated distances */
} spgLeafConsistentOut;
diff --git a/src/include/access/spgist_private.h b/src/include/access/spgist_private.h
index d092029..79b2dba 100644
--- a/src/include/access/spgist_private.h
+++ b/src/include/access/spgist_private.h
@@ -18,6 +18,7 @@
#include "access/spgist.h"
#include "nodes/tidbitmap.h"
#include "storage/relfilenode.h"
+#include "utils/rbtree.h"
#include "utils/relcache.h"
@@ -127,13 +128,40 @@ typedef struct SpGistState
bool isBuild; /* true if doing index build */
} SpGistState;
+typedef enum SPGistSEARCHITEMSTATE {
+ HEAP_RECHECK, /* SearchItem is heap item and rechek is needed before reporting */
+ HEAP_NORECHECK, /* SearchItem is heap item and no rechek is needed */
+ INNER /* SearchItem is inner tree item - rechek irrelevant */
+} SPGistSEARCHITEMSTATE;
+
+typedef struct SpGistSearchItem
+{
+ SPGistSEARCHITEMSTATE itemState; /* see above */
+ Datum value; /* value reconstructed from parent or leafValue if heaptuple */
+ Datum suppValue; /* any additional value an opclass needs to be stored */
+ int level; /* level of items on this page */
+ struct SpGistSearchItem *next; /* list link */
+ ItemPointerData heap; /* heap info, if heap tuple */
+ bool isnull;
+} SpGistSearchItem;
+
+typedef struct SpGistSearchTreeItem
+{
+ RBNode rbnode; /* this is an RBTree item */
+ SpGistSearchItem *head; /* first chain member */
+ SpGistSearchItem *lastHeap; /* last heap-tuple member, if any */
+ double distances[1]; /* array with numberOfOrderBys entries */
+} SpGistSearchTreeItem;
/*
* Private state of an index scan
*/
typedef struct SpGistScanOpaqueData
{
SpGistState state; /* see above */
+ RBTree *queue; /* queue of unvisited items */
+ MemoryContext queueCxt; /* context holding the queue */
MemoryContext tempCxt; /* short-lived memory context */
+ SpGistSearchTreeItem *curTreeItem;
/* Control flags showing whether to search nulls and/or non-nulls */
bool searchNulls; /* scan matches (all) null entries */
@@ -143,8 +171,9 @@ typedef struct SpGistScanOpaqueData
int numberOfKeys; /* number of index qualifier conditions */
ScanKey keyData; /* array of index qualifier descriptors */
- /* Stack of yet-to-be-visited pages */
- List *scanStack; /* List of ScanStackEntrys */
+ /* Pre-allocated workspace arrays: */
+ SpGistSearchTreeItem *tmpTreeItem; /* workspace to pass to rb_insert */
+ double *distances; /* output area for gistindex_keytest */
/* These fields are only used in amgetbitmap scans: */
TIDBitmap *tbm; /* bitmap being filled */
diff --git a/src/include/access/spgist_proc.h b/src/include/access/spgist_proc.h
new file mode 100644
index 0000000..d1d08b5
--- /dev/null
+++ b/src/include/access/spgist_proc.h
@@ -0,0 +1,52 @@
+#ifndef SPGIST_SEARCH_H
+#define SPGIST_SEARCH_H
+#include "postgres.h"
+
+#include "access/relscan.h"
+#include "access/spgist_private.h"
+#include "miscadmin.h"
+#include "storage/bufmgr.h"
+#include "utils/datum.h"
+#include "utils/geo_decls.h"
+#include "utils/memutils.h"
+#include "utils/rel.h"
+
+#define SPGISTHDRSZ offsetof(SpGistSearchTreeItem, distances)
+#define SPGISTSearchItemIsHeap(item) ((item).itemState == HEAP_RECHECK \
+ || (item).itemState == HEAP_NORECHECK)
+
+extern double get_float8_infinity();
+
+void inner_consistent_input_init(spgInnerConsistentIn *in, IndexScanDesc scan,
+ SpGistSearchItem *item, SpGistInnerTuple innerTuple);
+
+void spgInnerTest(Relation index, IndexScanDesc scan, SpGistSearchItem *item,
+ SpGistInnerTuple innerTuple, bool isnull);
+
+SpGistSearchItem *getNextQueueItem(SpGistScanOpaque so);
+
+extern int SpGistSearchTreeItemComparator(const RBNode *a, const RBNode *b, void *arg);
+
+extern void SpGistSearchTreeItemCombiner(RBNode *existing, const RBNode *newrb, void *arg);
+
+#define GSTIHDRSZ offsetof(SpGistSearchTreeItem, distances)
+
+extern RBNode * SpGistSearchTreeItemAllocator(void *arg);
+
+extern void SpGistSearchTreeItemDeleter(RBNode *rb, void *arg);
+
+extern void addSearchItemToQueue(IndexScanDesc scan, SpGistSearchItem *item, double *distances);
+
+extern SpGistSearchItem *newHeapItem(SpGistScanOpaque so, int level,
+ ItemPointerData heapPtr, Datum leafValue, bool recheck, bool isnull);
+
+extern void spg_point_distance(Datum to, int norderbys,
+ ScanKey orderbyKeys, double **distances, bool isLeaf);
+
+extern void freeSearchTreeItem(SpGistScanOpaque so, SpGistSearchItem *item);
+
+extern double dist_pb_simplified(Datum p, Datum b);
+
+
+#endif /* SPGIST_SEARCH_H */
+
diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h
index 759ea70..5e96178 100644
--- a/src/include/catalog/pg_am.h
+++ b/src/include/catalog/pg_am.h
@@ -129,7 +129,7 @@ DESCR("GiST index access method");
DATA(insert OID = 2742 ( gin 0 6 f f f f t t f f t f f 0 gininsert ginbeginscan - gingetbitmap ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbuildempty ginbulkdelete ginvacuumcleanup - gincostestimate ginoptions ));
DESCR("GIN index access method");
#define GIN_AM_OID 2742
-DATA(insert OID = 4000 ( spgist 0 5 f f f f f t f t f f f 0 spginsert spgbeginscan spggettuple spggetbitmap spgrescan spgendscan spgmarkpos spgrestrpos spgbuild spgbuildempty spgbulkdelete spgvacuumcleanup spgcanreturn spgcostestimate spgoptions ));
+DATA(insert OID = 4000 ( spgist 0 5 f t f f f t f t f f f 0 spginsert spgbeginscan spggettuple spggetbitmap spgrescan spgendscan spgmarkpos spgrestrpos spgbuild spgbuildempty spgbulkdelete spgvacuumcleanup spgcanreturn spgcostestimate spgoptions ));
DESCR("SP-GiST index access method");
#define SPGIST_AM_OID 4000
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index 3ef5a49..d453606 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -765,6 +765,7 @@ DATA(insert ( 4015 600 600 5 s 508 4000 0 ));
DATA(insert ( 4015 600 600 10 s 509 4000 0 ));
DATA(insert ( 4015 600 600 6 s 510 4000 0 ));
DATA(insert ( 4015 600 603 8 s 511 4000 0 ));
+DATA(insert ( 4015 600 600 15 o 517 4000 1970 ));
/*
* SP-GiST kd_point_ops
@@ -775,6 +776,7 @@ DATA(insert ( 4016 600 600 5 s 508 4000 0 ));
DATA(insert ( 4016 600 600 10 s 509 4000 0 ));
DATA(insert ( 4016 600 600 6 s 510 4000 0 ));
DATA(insert ( 4016 600 603 8 s 511 4000 0 ));
+DATA(insert ( 4016 600 600 15 o 517 4000 1970 ));
/*
* SP-GiST text_ops
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index f6f5516..90b6549 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -2782,3 +2782,193 @@ explain (costs off)
Index Cond: ((thousand = 1) AND (tenthous = 1001))
(2 rows)
+--
+-- Check KNN on sp-gist
+--
+SET enable_seqscan = OFF;
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+DROP INDEX gpointind;
+CREATE INDEX spgqpointind ON point_tbl USING spgist (f1 quad_point_ops);
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+
+(7 rows)
+
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+(6 rows)
+
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+ f1
+---------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+(4 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+ QUERY PLAN
+-------------------------------------------------
+ Index Only Scan using spgqpointind on point_tbl
+ Order By: (f1 <-> '(0,1)'::point)
+(2 rows)
+
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+
+(7 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+ QUERY PLAN
+-------------------------------------------------
+ Index Only Scan using spgqpointind on point_tbl
+ Index Cond: (f1 IS NOT NULL)
+ Order By: (f1 <-> '(0,1)'::point)
+(3 rows)
+
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+(6 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+ QUERY PLAN
+-------------------------------------------------
+ Index Only Scan using spgqpointind on point_tbl
+ Index Cond: (f1 <@ '(10,10),(-10,-10)'::box)
+ Order By: (f1 <-> '(0,1)'::point)
+(3 rows)
+
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+ f1
+---------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+(4 rows)
+
+DROP INDEX spgqpointind;
+CREATE INDEX spgkpointind ON point_tbl USING spgist (f1 kd_point_ops);
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+
+(7 rows)
+
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+(6 rows)
+
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+ f1
+---------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+(4 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+ QUERY PLAN
+-------------------------------------------------
+ Index Only Scan using spgkpointind on point_tbl
+ Order By: (f1 <-> '(0,1)'::point)
+(2 rows)
+
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+
+(7 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+ QUERY PLAN
+-------------------------------------------------
+ Index Only Scan using spgkpointind on point_tbl
+ Index Cond: (f1 IS NOT NULL)
+ Order By: (f1 <-> '(0,1)'::point)
+(3 rows)
+
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+ f1
+------------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+ (-5,-12)
+ (5.1,34.5)
+(6 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+ QUERY PLAN
+-------------------------------------------------
+ Index Only Scan using spgkpointind on point_tbl
+ Index Cond: (f1 <@ '(10,10),(-10,-10)'::box)
+ Order By: (f1 <-> '(0,1)'::point)
+(3 rows)
+
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+ f1
+---------
+ (0,0)
+ (-3,4)
+ (-10,0)
+ (10,10)
+(4 rows)
+
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index 992522e..ecd249c 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -1677,10 +1677,11 @@ ORDER BY 1, 2, 3;
4000 | 11 | >^
4000 | 12 | <=
4000 | 14 | >=
+ 4000 | 15 | <->
4000 | 15 | >
4000 | 16 | @>
4000 | 18 | =
-(80 rows)
+(81 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/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index d4d24ef..9ea0ccc 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -938,3 +938,44 @@ ORDER BY thousand;
explain (costs off)
select * from tenk1 where (thousand, tenthous) in ((1,1001), (null,null));
+
+--
+-- Check KNN on sp-gist
+--
+
+SET enable_seqscan = OFF;
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+
+DROP INDEX gpointind;
+CREATE INDEX spgqpointind ON point_tbl USING spgist (f1 quad_point_ops);
+
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+
+DROP INDEX spgqpointind;
+CREATE INDEX spgkpointind ON point_tbl USING spgist (f1 kd_point_ops);
+
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
+EXPLAIN (COSTS OFF)
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+SELECT * FROM point_tbl WHERE f1 <@ '(-10,-10),(10,10)':: box ORDER BY f1 <-> '0,1';
+
knn_spgist_benchmark.sh
Description: Bourne shell script
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
