*
* We are using traversal values provided by SP-GiST to calculate and
* to store the bounds of the quadrants, while traversing into the tree.
- * Traversal value has all the boundaries in the 4D space, and is is
- * capable of transferring the required boundaries to the following
- * traversal values. In conclusion, three things are necessary
- * to calculate the next traversal value:
+ * Traversal value has all the boundaries in the 4D space, and is capable
+ * of transferring the required boundaries to the following traversal
+ * values. In conclusion, three things are necessary to calculate the
+ * next traversal value:
*
* (1) the traversal value of the parent
* (2) the quadrant of the current node
* (3) the prefix of the current node
*
* If we visualize them on our simplified drawing (see the drawing above);
- * transfered boundaries of (1) would be the outer axis, relevant part
+ * transferred boundaries of (1) would be the outer axis, relevant part
* of (2) would be the up right part of the other axis, and (3) would be
* the inner axis.
*
* except the root. For the root node, we are setting the boundaries
* that we don't yet have as infinity.
*
- * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
#include "postgres.h"
#include "access/spgist.h"
+#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
-#include "utils/builtins.h"
+#include "utils/float.h"
+#include "utils/fmgroids.h"
+#include "utils/fmgrprotos.h"
#include "utils/geo_decls.h"
/*
* Comparator for qsort
*
* We don't need to use the floating point macros in here, because this
- * is going only going to be used in a place to effect the performance
+ * is only going to be used in a place to effect the performance
* of the index, not the correctness.
*/
static int
compareDoubles(const void *a, const void *b)
{
- double x = *(double *) a;
- double y = *(double *) b;
+ float8 x = *(float8 *) a;
+ float8 y = *(float8 *) b;
if (x == y)
return 0;
typedef struct
{
- double low;
- double high;
-} Range;
+ float8 low;
+ float8 high;
+} Range;
typedef struct
{
Range left;
Range right;
-} RangeBox;
+} RangeBox;
typedef struct
{
RangeBox range_box_x;
RangeBox range_box_y;
-} RectBox;
+} RectBox;
/*
* Calculate the quadrant
* initialize the struct to cover the whole 4D space.
*/
static RectBox *
-initRectBox()
+initRectBox(void)
{
- RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
- double infinity = get_float8_infinity();
+ RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
+ float8 infinity = get_float8_infinity();
rect_box->range_box_x.left.low = -infinity;
rect_box->range_box_x.left.high = infinity;
static RectBox *
nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
{
- RectBox *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
+ RectBox *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
memcpy(next_rect_box, rect_box, sizeof(RectBox));
overlap2D(RangeBox *range_box, Range *query)
{
return FPge(range_box->right.high, query->low) &&
- FPle(range_box->left.low, query->high);
+ FPle(range_box->left.low, query->high);
}
/* Can any rectangle from rect_box overlap with this argument? */
overlap4D(RectBox *rect_box, RangeBox *query)
{
return overlap2D(&rect_box->range_box_x, &query->left) &&
- overlap2D(&rect_box->range_box_y, &query->right);
+ overlap2D(&rect_box->range_box_y, &query->right);
}
/* Can any range from range_box contain this argument? */
contain2D(RangeBox *range_box, Range *query)
{
return FPge(range_box->right.high, query->high) &&
- FPle(range_box->left.low, query->low);
+ FPle(range_box->left.low, query->low);
}
/* Can any rectangle from rect_box contain this argument? */
static bool
-contain4D(RectBox *rect_box, RangeBox * query)
+contain4D(RectBox *rect_box, RangeBox *query)
{
return contain2D(&rect_box->range_box_x, &query->left) &&
- contain2D(&rect_box->range_box_y, &query->right);
+ contain2D(&rect_box->range_box_y, &query->right);
}
/* Can any range from range_box be contained by this argument? */
contained2D(RangeBox *range_box, Range *query)
{
return FPle(range_box->left.low, query->high) &&
- FPge(range_box->left.high, query->low) &&
- FPle(range_box->right.low, query->high) &&
- FPge(range_box->right.high, query->low);
+ FPge(range_box->left.high, query->low) &&
+ FPle(range_box->right.low, query->high) &&
+ FPge(range_box->right.high, query->low);
}
/* Can any rectangle from rect_box be contained by this argument? */
contained4D(RectBox *rect_box, RangeBox *query)
{
return contained2D(&rect_box->range_box_x, &query->left) &&
- contained2D(&rect_box->range_box_y, &query->right);
+ contained2D(&rect_box->range_box_y, &query->right);
}
/* Can any range from range_box to be lower than this argument? */
lower2D(RangeBox *range_box, Range *query)
{
return FPlt(range_box->left.low, query->low) &&
- FPlt(range_box->right.low, query->low);
+ FPlt(range_box->right.low, query->low);
+}
+
+/* Can any range from range_box not extend to the right side of the query? */
+static bool
+overLower2D(RangeBox *range_box, Range *query)
+{
+ return FPle(range_box->left.low, query->high) &&
+ FPle(range_box->right.low, query->high);
}
/* Can any range from range_box to be higher than this argument? */
higher2D(RangeBox *range_box, Range *query)
{
return FPgt(range_box->left.high, query->high) &&
- FPgt(range_box->right.high, query->high);
+ FPgt(range_box->right.high, query->high);
+}
+
+/* Can any range from range_box not extend to the left side of the query? */
+static bool
+overHigher2D(RangeBox *range_box, Range *query)
+{
+ return FPge(range_box->left.high, query->low) &&
+ FPge(range_box->right.high, query->low);
}
/* Can any rectangle from rect_box be left of this argument? */
static bool
overLeft4D(RectBox *rect_box, RangeBox *query)
{
- return lower2D(&rect_box->range_box_x, &query->right);
+ return overLower2D(&rect_box->range_box_x, &query->left);
}
/* Can any rectangle from rect_box be right of this argument? */
static bool
overRight4D(RectBox *rect_box, RangeBox *query)
{
- return higher2D(&rect_box->range_box_x, &query->right);
+ return overHigher2D(&rect_box->range_box_x, &query->left);
}
/* Can any rectangle from rect_box be below of this argument? */
static bool
overBelow4D(RectBox *rect_box, RangeBox *query)
{
- return lower2D(&rect_box->range_box_y, &query->left);
+ return overLower2D(&rect_box->range_box_y, &query->right);
}
/* Can any rectangle from rect_box be above of this argument? */
static bool
overAbove4D(RectBox *rect_box, RangeBox *query)
{
- return higher2D(&rect_box->range_box_y, &query->right);
+ return overHigher2D(&rect_box->range_box_y, &query->right);
}
+/* Lower bound for the distance between point and rect_box */
+static double
+pointToRectBoxDistance(Point *point, RectBox *rect_box)
+{
+ double dx;
+ double dy;
+
+ if (point->x < rect_box->range_box_x.left.low)
+ dx = rect_box->range_box_x.left.low - point->x;
+ else if (point->x > rect_box->range_box_x.right.high)
+ dx = point->x - rect_box->range_box_x.right.high;
+ else
+ dx = 0;
+
+ if (point->y < rect_box->range_box_y.left.low)
+ dy = rect_box->range_box_y.left.low - point->y;
+ else if (point->y > rect_box->range_box_y.right.high)
+ dy = point->y - rect_box->range_box_y.right.high;
+ else
+ dy = 0;
+
+ return HYPOT(dx, dy);
+}
+
+
/*
* SP-GiST config function
*/
spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
BOX *centroid = DatumGetBoxP(in->prefixDatum),
- *box = DatumGetBoxP(in->datum);
+ *box = DatumGetBoxP(in->leafDatum);
out->resultType = spgMatchNode;
out->result.matchNode.restDatum = BoxPGetDatum(box);
Datum
spg_box_quad_picksplit(PG_FUNCTION_ARGS)
{
- spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
- spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
+ spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
+ spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
BOX *centroid;
int median,
i;
- double *lowXs = palloc(sizeof(double) * in->nTuples);
- double *highXs = palloc(sizeof(double) * in->nTuples);
- double *lowYs = palloc(sizeof(double) * in->nTuples);
- double *highYs = palloc(sizeof(double) * in->nTuples);
+ float8 *lowXs = palloc(sizeof(float8) * in->nTuples);
+ float8 *highXs = palloc(sizeof(float8) * in->nTuples);
+ float8 *lowYs = palloc(sizeof(float8) * in->nTuples);
+ float8 *highYs = palloc(sizeof(float8) * in->nTuples);
/* Calculate median of all 4D coordinates */
for (i = 0; i < in->nTuples; i++)
{
- BOX *box = DatumGetBoxP(in->datums[i]);
+ BOX *box = DatumGetBoxP(in->datums[i]);
lowXs[i] = box->low.x;
highXs[i] = box->high.x;
highYs[i] = box->high.y;
}
- qsort(lowXs, in->nTuples, sizeof(double), compareDoubles);
- qsort(highXs, in->nTuples, sizeof(double), compareDoubles);
- qsort(lowYs, in->nTuples, sizeof(double), compareDoubles);
- qsort(highYs, in->nTuples, sizeof(double), compareDoubles);
+ qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
+ qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
+ qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
+ qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
median = in->nTuples / 2;
out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
/*
- * Assign ranges to corresponding nodes according to quadrants
- * relative to the "centroid" range
+ * Assign ranges to corresponding nodes according to quadrants relative to
+ * the "centroid" range
*/
for (i = 0; i < in->nTuples; i++)
{
- BOX *box = DatumGetBoxP(in->datums[i]);
- uint8 quadrant = getQuadrant(centroid, box);
+ BOX *box = DatumGetBoxP(in->datums[i]);
+ uint8 quadrant = getQuadrant(centroid, box);
out->leafTupleDatums[i] = BoxPGetDatum(box);
out->mapTuplesToNodes[i] = quadrant;
PG_RETURN_VOID();
}
+/*
+ * Check if result of consistent method based on bounding box is exact.
+ */
+static bool
+is_bounding_box_test_exact(StrategyNumber strategy)
+{
+ switch (strategy)
+ {
+ case RTLeftStrategyNumber:
+ case RTOverLeftStrategyNumber:
+ case RTOverRightStrategyNumber:
+ case RTRightStrategyNumber:
+ case RTOverBelowStrategyNumber:
+ case RTBelowStrategyNumber:
+ case RTAboveStrategyNumber:
+ case RTOverAboveStrategyNumber:
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+/*
+ * Get bounding box for ScanKey.
+ */
+static BOX *
+spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
+{
+ switch (sk->sk_subtype)
+ {
+ case BOXOID:
+ return DatumGetBoxP(sk->sk_argument);
+
+ case POLYGONOID:
+ if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
+ *recheck = true;
+ return &DatumGetPolygonP(sk->sk_argument)->boundbox;
+
+ default:
+ elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
+ return NULL;
+ }
+}
+
/*
* SP-GiST inner consistent function
*/
{
spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
- int i;
- MemoryContext old_ctx;
- RectBox *rect_box;
- uint8 quadrant;
- RangeBox *centroid,
- **queries;
+ int i;
+ MemoryContext old_ctx;
+ RectBox *rect_box;
+ uint8 quadrant;
+ RangeBox *centroid,
+ **queries;
+
+ /*
+ * We are saving the traversal value or initialize it an unbounded one, if
+ * we have just begun to walk the tree.
+ */
+ if (in->traversalValue)
+ rect_box = in->traversalValue;
+ else
+ rect_box = initRectBox();
if (in->allTheSame)
{
for (i = 0; i < in->nNodes; i++)
out->nodeNumbers[i] = i;
+ if (in->norderbys > 0 && in->nNodes > 0)
+ {
+ double *distances = palloc(sizeof(double) * in->norderbys);
+ int j;
+
+ for (j = 0; j < in->norderbys; j++)
+ {
+ Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
+
+ distances[j] = pointToRectBoxDistance(pt, rect_box);
+ }
+
+ out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
+ out->distances[0] = distances;
+
+ for (i = 1; i < in->nNodes; i++)
+ {
+ out->distances[i] = palloc(sizeof(double) * in->norderbys);
+ memcpy(out->distances[i], distances,
+ sizeof(double) * in->norderbys);
+ }
+ }
+
PG_RETURN_VOID();
}
/*
- * We are saving the traversal value or initialize it an unbounded
- * one, if we have just begun to walk the tree.
- */
- if (in->traversalValue)
- rect_box = in->traversalValue;
- else
- rect_box = initRectBox();
-
- /*
- * We are casting the prefix and queries to RangeBoxes for ease of
- * the following operations.
+ * We are casting the prefix and queries to RangeBoxes for ease of the
+ * following operations.
*/
centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
for (i = 0; i < in->nkeys; i++)
- queries[i] = getRangeBox(DatumGetBoxP(in->scankeys[i].sk_argument));
+ {
+ BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
+
+ queries[i] = getRangeBox(box);
+ }
/* Allocate enough memory for nodes */
out->nNodes = 0;
out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
+ if (in->norderbys > 0)
+ out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
/*
- * We switch memory context, because we want to allocate memory for
- * new traversal values (next_rect_box) and pass these pieces of
- * memory to further call of this function.
+ * We switch memory context, because we want to allocate memory for new
+ * traversal values (next_rect_box) and pass these pieces of memory to
+ * further call of this function.
*/
old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
for (quadrant = 0; quadrant < in->nNodes; quadrant++)
{
- RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
+ RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
bool flag = true;
for (i = 0; i < in->nkeys; i++)
{
out->traversalValues[out->nNodes] = next_rect_box;
out->nodeNumbers[out->nNodes] = quadrant;
+
+ if (in->norderbys > 0)
+ {
+ double *distances = palloc(sizeof(double) * in->norderbys);
+ int j;
+
+ out->distances[out->nNodes] = distances;
+
+ for (j = 0; j < in->norderbys; j++)
+ {
+ Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
+
+ distances[j] = pointToRectBoxDistance(pt, next_rect_box);
+ }
+ }
+
out->nNodes++;
}
else
{
/*
- * If this node is not selected, we don't need to keep
- * the next traversal value in the memory context.
+ * If this node is not selected, we don't need to keep the next
+ * traversal value in the memory context.
*/
pfree(next_rect_box);
}
for (i = 0; i < in->nkeys; i++)
{
StrategyNumber strategy = in->scankeys[i].sk_strategy;
- Datum query = in->scankeys[i].sk_argument;
+ BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
+ &out->recheck);
+ Datum query = BoxPGetDatum(box);
switch (strategy)
{
break;
}
+ if (flag && in->norderbys > 0)
+ {
+ Oid distfnoid = in->orderbys[0].sk_func.fn_oid;
+
+ out->distances = spg_key_orderbys_distances(leaf, false,
+ in->orderbys, in->norderbys);
+
+ /* Recheck is necessary when computing distance to polygon */
+ out->recheckDistances = distfnoid == F_DIST_POLYP;
+ }
+
PG_RETURN_BOOL(flag);
}
+
+
+/*
+ * SP-GiST config function for 2-D types that are lossy represented by their
+ * bounding boxes
+ */
+Datum
+spg_bbox_quad_config(PG_FUNCTION_ARGS)
+{
+ spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
+
+ cfg->prefixType = BOXOID; /* A type represented by its bounding box */
+ cfg->labelType = VOIDOID; /* We don't need node labels. */
+ cfg->leafType = BOXOID;
+ cfg->canReturnData = false;
+ cfg->longValuesOK = false;
+
+ PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST compress function for polygons
+ */
+Datum
+spg_poly_quad_compress(PG_FUNCTION_ARGS)
+{
+ POLYGON *polygon = PG_GETARG_POLYGON_P(0);
+ BOX *box;
+
+ box = (BOX *) palloc(sizeof(BOX));
+ *box = polygon->boundbox;
+
+ PG_RETURN_BOX_P(box);
+}
projects / postgresql / blobdiff