1/*-------------------------------------------------------------------------
4 * SP-GiST implementation of 4-dimensional quad tree over boxes
6 * This module provides SP-GiST implementation for boxes using quad tree
7 * analogy in 4-dimensional space. SP-GiST doesn't allow indexing of
8 * overlapping objects. We are making 2D objects never-overlapping in
9 * 4D space. This technique has some benefits compared to traditional
10 * R-Tree which is implemented as GiST. The performance tests reveal
11 * that this technique especially beneficial with too much overlapping
12 * objects, so called "spaghetti data".
14 * Unlike the original quad tree, we are splitting the tree into 16
15 * quadrants in 4D space. It is easier to imagine it as splitting space
23 * -------------+-------------
30 * We are using box datatype as the prefix, but we are treating them
31 * as points in 4-dimensional space, because 2D boxes are not enough
32 * to represent the quadrant boundaries in 4D space. They however are
33 * sufficient to point out the additional boundaries of the next
36 * We are using traversal values provided by SP-GiST to calculate and
37 * to store the bounds of the quadrants, while traversing into the tree.
38 * Traversal value has all the boundaries in the 4D space, and is capable
39 * of transferring the required boundaries to the following traversal
40 * values. In conclusion, three things are necessary to calculate the
41 * next traversal value:
43 * (1) the traversal value of the parent
44 * (2) the quadrant of the current node
45 * (3) the prefix of the current node
47 * If we visualize them on our simplified drawing (see the drawing above);
48 * transferred boundaries of (1) would be the outer axis, relevant part
49 * of (2) would be the up right part of the other axis, and (3) would be
52 * For example, consider the case of overlapping. When recursion
53 * descends deeper and deeper down the tree, all quadrants in
54 * the current node will be checked for overlapping. The boundaries
55 * will be re-calculated for all quadrants. Overlap check answers
56 * the question: can any box from this quadrant overlap with the given
57 * box? If yes, then this quadrant will be walked. If no, then this
58 * quadrant will be skipped.
60 * This method provides restrictions for minimum and maximum values of
61 * every dimension of every corner of the box on every level of the tree
62 * except the root. For the root node, we are setting the boundaries
63 * that we don't yet have as infinity.
65 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
66 * Portions Copyright (c) 1994, Regents of the University of California
69 * src/backend/utils/adt/geo_spgist.c
71 *-------------------------------------------------------------------------
81#include "utils/fmgroids.h"
82#include "utils/fmgrprotos.h"
86 * Comparator for qsort
88 * We don't need to use the floating point macros in here, because this
89 * is only going to be used in a place to effect the performance
90 * of the index, not the correctness.
100 return (
x >
y) ? 1 : -1;
122 * Calculate the quadrant
124 * The quadrant is 8 bit unsigned integer with 4 least bits in use.
125 * This function accepts BOXes as input. They are not casted to
126 * RangeBoxes, yet. All 4 bits are set by comparing a corner of the box.
127 * This makes 16 quadrants in total.
150 * Get RangeBox using BOX
152 * We are turning the BOX to our structures to emphasize their function
153 * of representing points in 4D space. It also is more convenient to
154 * access the values with this structure.
171 * Initialize the traversal value
173 * In the beginning, we don't have any restrictions. We have to
174 * initialize the struct to cover the whole 4D space.
198 * Calculate the next traversal value
200 * All centroids are bounded by RectBox, but SP-GiST only keeps
201 * boxes. When we are traversing the tree, we must calculate RectBox,
202 * using centroid and quadrant.
209 memcpy(next_rect_box, rect_box,
sizeof(
RectBox));
231 return next_rect_box;
234/* Can any range from range_box overlap with this argument? */
242/* Can any rectangle from rect_box overlap with this argument? */
250/* Can any range from range_box contain this argument? */
258/* Can any rectangle from rect_box contain this argument? */
266/* Can any range from range_box be contained by this argument? */
276/* Can any rectangle from rect_box be contained by this argument? */
284/* Can any range from range_box to be lower than this argument? */
292/* Can any range from range_box not extend to the right side of the query? */
300/* Can any range from range_box to be higher than this argument? */
308/* Can any range from range_box not extend to the left side of the query? */
316/* Can any rectangle from rect_box be left of this argument? */
323/* Can any rectangle from rect_box does not extend the right of this argument? */
330/* Can any rectangle from rect_box be right of this argument? */
337/* Can any rectangle from rect_box does not extend the left of this argument? */
344/* Can any rectangle from rect_box be below of this argument? */
351/* Can any rectangle from rect_box does not extend above this argument? */
358/* Can any rectangle from rect_box be above of this argument? */
365/* Can any rectangle from rect_box does not extend below of this argument? */
372/* Lower bound for the distance between point and rect_box */
393 return HYPOT(dx, dy);
398 * SP-GiST config function
406 cfg->
labelType = VOIDOID;
/* We don't need node labels. */
414 * SP-GiST choose function
427 /* nodeN will be set by core, when allTheSame. */
435 * SP-GiST pick-split function
437 * It splits a list of boxes into quadrants by choosing a central 4D
438 * point as the median of the coordinates of the boxes.
453 /* Calculate median of all 4D coordinates */
458 lowXs[
i] = box->
low.
x;
460 lowYs[
i] = box->
low.
y;
473 centroid->
low.
x = lowXs[median];
474 centroid->
high.
x = highXs[median];
475 centroid->
low.
y = lowYs[median];
476 centroid->
high.
y = highYs[median];
478 /* Fill the output */
483 out->
nodeLabels = NULL;
/* We don't need node labels. */
489 * Assign ranges to corresponding nodes according to quadrants relative to
490 * the "centroid" range
505 * Check if result of consistent method based on bounding box is exact.
528 * Get bounding box for ScanKey.
550 * SP-GiST inner consistent function
565 * We are saving the traversal value or initialize it an unbounded one, if
566 * we have just begun to walk the tree.
575 /* Report that all nodes should be visited */
608 * We are casting the prefix and queries to RangeBoxes for ease of the
609 * following operations.
620 /* Allocate enough memory for nodes */
628 * We switch memory context, because we want to allocate memory for new
629 * traversal values (next_rect_box) and pass these pieces of memory to
630 * further call of this function.
634 for (quadrant = 0; quadrant < in->
nNodes; quadrant++)
691 elog(
ERROR,
"unrecognized strategy: %d", strategy);
694 /* If any check is failed, we have found our answer. */
724 * If this node is not selected, we don't need to keep the next
725 * traversal value in the memory context.
727 pfree(next_rect_box);
738 * SP-GiST inner consistent function
749 /* All tests are exact. */
753 * Don't return leafValue unless told to; this is used for both box and
754 * polygon opclasses, and in the latter case the leaf datum is not even of
755 * the right type to return.
760 /* Perform the required comparison(s) */
831 elog(
ERROR,
"unrecognized strategy: %d", strategy);
834 /* If any check is failed, we have found our answer. */
846 /* Recheck is necessary when computing distance to polygon */
855 * SP-GiST config function for 2-D types that are lossy represented by their
863 cfg->
prefixType = BOXOID;
/* A type represented by its bounding box */
864 cfg->
labelType = VOIDOID;
/* We don't need node labels. */
873 * SP-GiST compress function for polygons
static float8 get_float8_infinity(void)
#define DirectFunctionCall2(func, arg1, arg2)
#define PG_GETARG_POINTER(n)
#define PG_RETURN_BOOL(x)
static bool FPlt(double A, double B)
static bool FPge(double A, double B)
#define PG_RETURN_BOX_P(x)
static Point * DatumGetPointP(Datum X)
static POLYGON * DatumGetPolygonP(Datum X)
static BOX * DatumGetBoxP(Datum X)
#define PG_GETARG_POLYGON_P(n)
static bool FPgt(double A, double B)
static bool FPle(double A, double B)
static Datum BoxPGetDatum(const BOX *X)
Datum box_left(PG_FUNCTION_ARGS)
Datum box_right(PG_FUNCTION_ARGS)
Datum box_same(PG_FUNCTION_ARGS)
Datum box_below(PG_FUNCTION_ARGS)
Datum box_overright(PG_FUNCTION_ARGS)
Datum box_overabove(PG_FUNCTION_ARGS)
Datum box_overlap(PG_FUNCTION_ARGS)
Datum box_contain(PG_FUNCTION_ARGS)
Datum box_overbelow(PG_FUNCTION_ARGS)
Datum box_contained(PG_FUNCTION_ARGS)
Datum box_overleft(PG_FUNCTION_ARGS)
Datum box_above(PG_FUNCTION_ARGS)
static bool right4D(RectBox *rect_box, RangeBox *query)
Datum spg_box_quad_choose(PG_FUNCTION_ARGS)
static double pointToRectBoxDistance(Point *point, RectBox *rect_box)
static bool contain4D(RectBox *rect_box, RangeBox *query)
static bool overLower2D(RangeBox *range_box, Range *query)
static bool overRight4D(RectBox *rect_box, RangeBox *query)
static uint8 getQuadrant(BOX *centroid, BOX *inBox)
Datum spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
Datum spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
static RectBox * initRectBox(void)
static RangeBox * getRangeBox(BOX *box)
static bool overlap2D(RangeBox *range_box, Range *query)
Datum spg_box_quad_picksplit(PG_FUNCTION_ARGS)
static int compareDoubles(const void *a, const void *b)
Datum spg_bbox_quad_config(PG_FUNCTION_ARGS)
Datum spg_box_quad_config(PG_FUNCTION_ARGS)
static bool overLeft4D(RectBox *rect_box, RangeBox *query)
static bool lower2D(RangeBox *range_box, Range *query)
static bool above4D(RectBox *rect_box, RangeBox *query)
static BOX * spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
static bool contained4D(RectBox *rect_box, RangeBox *query)
static bool overBelow4D(RectBox *rect_box, RangeBox *query)
static bool higher2D(RangeBox *range_box, Range *query)
static bool overlap4D(RectBox *rect_box, RangeBox *query)
static RectBox * nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
static bool left4D(RectBox *rect_box, RangeBox *query)
static bool contained2D(RangeBox *range_box, Range *query)
static bool overAbove4D(RectBox *rect_box, RangeBox *query)
static bool is_bounding_box_test_exact(StrategyNumber strategy)
static bool below4D(RectBox *rect_box, RangeBox *query)
Datum spg_poly_quad_compress(PG_FUNCTION_ARGS)
static bool overHigher2D(RangeBox *range_box, Range *query)
static bool contain2D(RangeBox *range_box, Range *query)
if(TABLE==NULL||TABLE_index==NULL)
void pfree(void *pointer)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
#define qsort(a, b, c, d)
static bool DatumGetBool(Datum X)
double * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys)
#define RTOverlapStrategyNumber
#define RTLeftStrategyNumber
#define RTOverRightStrategyNumber
#define RTRightStrategyNumber
#define RTSameStrategyNumber
#define RTOverAboveStrategyNumber
#define RTContainsStrategyNumber
#define RTOverBelowStrategyNumber
#define RTBelowStrategyNumber
#define RTAboveStrategyNumber
#define RTOverLeftStrategyNumber
#define RTContainedByStrategyNumber
StrategyNumber sk_strategy
spgChooseResultType resultType
struct spgChooseOut::@53::@54 matchNode
union spgChooseOut::@53 result
MemoryContext traversalMemoryContext