*
* 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
* except the root. For the root node, we are setting the boundaries
* that we don't yet have as infinity.
*
- * Portions Copyright (c) 1996-2017, 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;
+ float8 low;
+ float8 high;
} Range;
typedef struct
initRectBox(void)
{
RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
- double infinity = get_float8_infinity();
+ float8 infinity = get_float8_infinity();
rect_box->range_box_x.left.low = -infinity;
rect_box->range_box_x.left.high = infinity;
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);
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++)
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;
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
*/
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)
{
/* Report that all nodes should be visited */
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.
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
{
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
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