1 /*-------------------------------------------------------------------------
2 *
3 * geo_spgist.c
4 * SP-GiST implementation of 4-dimensional quad tree over boxes
5 *
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".
13 *
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
16 * two times into 4:
17 *
18 * | |
19 * | |
20 * | -----+-----
21 * | |
22 * | |
23 * -------------+-------------
24 * |
25 * |
26 * |
27 * |
28 * |
29 *
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
34 * quadrant.
35 *
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:
42 *
43 * (1) the traversal value of the parent
44 * (2) the quadrant of the current node
45 * (3) the prefix of the current node
46 *
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
50 * the inner axis.
51 *
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.
59 *
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.
64 *
65 * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
66 * Portions Copyright (c) 1994, Regents of the University of California
67 *
68 * IDENTIFICATION
69 * src/backend/utils/adt/geo_spgist.c
70 *
71 *-------------------------------------------------------------------------
72 */
73
74 #include "postgres.h"
75
76 #include "access/spgist.h"
77 #include "access/spgist_private.h"
78 #include "access/stratnum.h"
79 #include "catalog/pg_type.h"
80 #include "utils/float.h"
81 #include "utils/fmgroids.h"
82 #include "utils/fmgrprotos.h"
83 #include "utils/geo_decls.h"
84
85 /*
86 * Comparator for qsort
87 *
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.
91 */
92 static int
compareDoubles(const void * a,const void * b)93 compareDoubles(const void *a, const void *b)
94 {
95 float8 x = *(float8 *) a;
96 float8 y = *(float8 *) b;
97
98 if (x == y)
99 return 0;
100 return (x > y) ? 1 : -1;
101 }
102
103 typedef struct
104 {
105 float8 low;
106 float8 high;
107 } Range;
108
109 typedef struct
110 {
111 Range left;
112 Range right;
113 } RangeBox;
114
115 typedef struct
116 {
117 RangeBox range_box_x;
118 RangeBox range_box_y;
119 } RectBox;
120
121 /*
122 * Calculate the quadrant
123 *
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.
128 */
129 static uint8
getQuadrant(BOX * centroid,BOX * inBox)130 getQuadrant(BOX *centroid, BOX *inBox)
131 {
132 uint8 quadrant = 0;
133
134 if (inBox->low.x > centroid->low.x)
135 quadrant |= 0x8;
136
137 if (inBox->high.x > centroid->high.x)
138 quadrant |= 0x4;
139
140 if (inBox->low.y > centroid->low.y)
141 quadrant |= 0x2;
142
143 if (inBox->high.y > centroid->high.y)
144 quadrant |= 0x1;
145
146 return quadrant;
147 }
148
149 /*
150 * Get RangeBox using BOX
151 *
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.
155 */
156 static RangeBox *
getRangeBox(BOX * box)157 getRangeBox(BOX *box)
158 {
159 RangeBox *range_box = (RangeBox *) palloc(sizeof(RangeBox));
160
161 range_box->left.low = box->low.x;
162 range_box->left.high = box->high.x;
163
164 range_box->right.low = box->low.y;
165 range_box->right.high = box->high.y;
166
167 return range_box;
168 }
169
170 /*
171 * Initialize the traversal value
172 *
173 * In the beginning, we don't have any restrictions. We have to
174 * initialize the struct to cover the whole 4D space.
175 */
176 static RectBox *
initRectBox(void)177 initRectBox(void)
178 {
179 RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
180 float8 infinity = get_float8_infinity();
181
182 rect_box->range_box_x.left.low = -infinity;
183 rect_box->range_box_x.left.high = infinity;
184
185 rect_box->range_box_x.right.low = -infinity;
186 rect_box->range_box_x.right.high = infinity;
187
188 rect_box->range_box_y.left.low = -infinity;
189 rect_box->range_box_y.left.high = infinity;
190
191 rect_box->range_box_y.right.low = -infinity;
192 rect_box->range_box_y.right.high = infinity;
193
194 return rect_box;
195 }
196
197 /*
198 * Calculate the next traversal value
199 *
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.
203 */
204 static RectBox *
nextRectBox(RectBox * rect_box,RangeBox * centroid,uint8 quadrant)205 nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
206 {
207 RectBox *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
208
209 memcpy(next_rect_box, rect_box, sizeof(RectBox));
210
211 if (quadrant & 0x8)
212 next_rect_box->range_box_x.left.low = centroid->left.low;
213 else
214 next_rect_box->range_box_x.left.high = centroid->left.low;
215
216 if (quadrant & 0x4)
217 next_rect_box->range_box_x.right.low = centroid->left.high;
218 else
219 next_rect_box->range_box_x.right.high = centroid->left.high;
220
221 if (quadrant & 0x2)
222 next_rect_box->range_box_y.left.low = centroid->right.low;
223 else
224 next_rect_box->range_box_y.left.high = centroid->right.low;
225
226 if (quadrant & 0x1)
227 next_rect_box->range_box_y.right.low = centroid->right.high;
228 else
229 next_rect_box->range_box_y.right.high = centroid->right.high;
230
231 return next_rect_box;
232 }
233
234 /* Can any range from range_box overlap with this argument? */
235 static bool
overlap2D(RangeBox * range_box,Range * query)236 overlap2D(RangeBox *range_box, Range *query)
237 {
238 return FPge(range_box->right.high, query->low) &&
239 FPle(range_box->left.low, query->high);
240 }
241
242 /* Can any rectangle from rect_box overlap with this argument? */
243 static bool
overlap4D(RectBox * rect_box,RangeBox * query)244 overlap4D(RectBox *rect_box, RangeBox *query)
245 {
246 return overlap2D(&rect_box->range_box_x, &query->left) &&
247 overlap2D(&rect_box->range_box_y, &query->right);
248 }
249
250 /* Can any range from range_box contain this argument? */
251 static bool
contain2D(RangeBox * range_box,Range * query)252 contain2D(RangeBox *range_box, Range *query)
253 {
254 return FPge(range_box->right.high, query->high) &&
255 FPle(range_box->left.low, query->low);
256 }
257
258 /* Can any rectangle from rect_box contain this argument? */
259 static bool
contain4D(RectBox * rect_box,RangeBox * query)260 contain4D(RectBox *rect_box, RangeBox *query)
261 {
262 return contain2D(&rect_box->range_box_x, &query->left) &&
263 contain2D(&rect_box->range_box_y, &query->right);
264 }
265
266 /* Can any range from range_box be contained by this argument? */
267 static bool
contained2D(RangeBox * range_box,Range * query)268 contained2D(RangeBox *range_box, Range *query)
269 {
270 return FPle(range_box->left.low, query->high) &&
271 FPge(range_box->left.high, query->low) &&
272 FPle(range_box->right.low, query->high) &&
273 FPge(range_box->right.high, query->low);
274 }
275
276 /* Can any rectangle from rect_box be contained by this argument? */
277 static bool
contained4D(RectBox * rect_box,RangeBox * query)278 contained4D(RectBox *rect_box, RangeBox *query)
279 {
280 return contained2D(&rect_box->range_box_x, &query->left) &&
281 contained2D(&rect_box->range_box_y, &query->right);
282 }
283
284 /* Can any range from range_box to be lower than this argument? */
285 static bool
lower2D(RangeBox * range_box,Range * query)286 lower2D(RangeBox *range_box, Range *query)
287 {
288 return FPlt(range_box->left.low, query->low) &&
289 FPlt(range_box->right.low, query->low);
290 }
291
292 /* Can any range from range_box not extend to the right side of the query? */
293 static bool
overLower2D(RangeBox * range_box,Range * query)294 overLower2D(RangeBox *range_box, Range *query)
295 {
296 return FPle(range_box->left.low, query->high) &&
297 FPle(range_box->right.low, query->high);
298 }
299
300 /* Can any range from range_box to be higher than this argument? */
301 static bool
higher2D(RangeBox * range_box,Range * query)302 higher2D(RangeBox *range_box, Range *query)
303 {
304 return FPgt(range_box->left.high, query->high) &&
305 FPgt(range_box->right.high, query->high);
306 }
307
308 /* Can any range from range_box not extend to the left side of the query? */
309 static bool
overHigher2D(RangeBox * range_box,Range * query)310 overHigher2D(RangeBox *range_box, Range *query)
311 {
312 return FPge(range_box->left.high, query->low) &&
313 FPge(range_box->right.high, query->low);
314 }
315
316 /* Can any rectangle from rect_box be left of this argument? */
317 static bool
left4D(RectBox * rect_box,RangeBox * query)318 left4D(RectBox *rect_box, RangeBox *query)
319 {
320 return lower2D(&rect_box->range_box_x, &query->left);
321 }
322
323 /* Can any rectangle from rect_box does not extend the right of this argument? */
324 static bool
overLeft4D(RectBox * rect_box,RangeBox * query)325 overLeft4D(RectBox *rect_box, RangeBox *query)
326 {
327 return overLower2D(&rect_box->range_box_x, &query->left);
328 }
329
330 /* Can any rectangle from rect_box be right of this argument? */
331 static bool
right4D(RectBox * rect_box,RangeBox * query)332 right4D(RectBox *rect_box, RangeBox *query)
333 {
334 return higher2D(&rect_box->range_box_x, &query->left);
335 }
336
337 /* Can any rectangle from rect_box does not extend the left of this argument? */
338 static bool
overRight4D(RectBox * rect_box,RangeBox * query)339 overRight4D(RectBox *rect_box, RangeBox *query)
340 {
341 return overHigher2D(&rect_box->range_box_x, &query->left);
342 }
343
344 /* Can any rectangle from rect_box be below of this argument? */
345 static bool
below4D(RectBox * rect_box,RangeBox * query)346 below4D(RectBox *rect_box, RangeBox *query)
347 {
348 return lower2D(&rect_box->range_box_y, &query->right);
349 }
350
351 /* Can any rectangle from rect_box does not extend above this argument? */
352 static bool
overBelow4D(RectBox * rect_box,RangeBox * query)353 overBelow4D(RectBox *rect_box, RangeBox *query)
354 {
355 return overLower2D(&rect_box->range_box_y, &query->right);
356 }
357
358 /* Can any rectangle from rect_box be above of this argument? */
359 static bool
above4D(RectBox * rect_box,RangeBox * query)360 above4D(RectBox *rect_box, RangeBox *query)
361 {
362 return higher2D(&rect_box->range_box_y, &query->right);
363 }
364
365 /* Can any rectangle from rect_box does not extend below of this argument? */
366 static bool
overAbove4D(RectBox * rect_box,RangeBox * query)367 overAbove4D(RectBox *rect_box, RangeBox *query)
368 {
369 return overHigher2D(&rect_box->range_box_y, &query->right);
370 }
371
372 /* Lower bound for the distance between point and rect_box */
373 static double
pointToRectBoxDistance(Point * point,RectBox * rect_box)374 pointToRectBoxDistance(Point *point, RectBox *rect_box)
375 {
376 double dx;
377 double dy;
378
379 if (point->x < rect_box->range_box_x.left.low)
380 dx = rect_box->range_box_x.left.low - point->x;
381 else if (point->x > rect_box->range_box_x.right.high)
382 dx = point->x - rect_box->range_box_x.right.high;
383 else
384 dx = 0;
385
386 if (point->y < rect_box->range_box_y.left.low)
387 dy = rect_box->range_box_y.left.low - point->y;
388 else if (point->y > rect_box->range_box_y.right.high)
389 dy = point->y - rect_box->range_box_y.right.high;
390 else
391 dy = 0;
392
393 return HYPOT(dx, dy);
394 }
395
396
397 /*
398 * SP-GiST config function
399 */
400 Datum
spg_box_quad_config(PG_FUNCTION_ARGS)401 spg_box_quad_config(PG_FUNCTION_ARGS)
402 {
403 spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
404
405 cfg->prefixType = BOXOID;
406 cfg->labelType = VOIDOID; /* We don't need node labels. */
407 cfg->canReturnData = true;
408 cfg->longValuesOK = false;
409
410 PG_RETURN_VOID();
411 }
412
413 /*
414 * SP-GiST choose function
415 */
416 Datum
spg_box_quad_choose(PG_FUNCTION_ARGS)417 spg_box_quad_choose(PG_FUNCTION_ARGS)
418 {
419 spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
420 spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
421 BOX *centroid = DatumGetBoxP(in->prefixDatum),
422 *box = DatumGetBoxP(in->leafDatum);
423
424 out->resultType = spgMatchNode;
425 out->result.matchNode.restDatum = BoxPGetDatum(box);
426
427 /* nodeN will be set by core, when allTheSame. */
428 if (!in->allTheSame)
429 out->result.matchNode.nodeN = getQuadrant(centroid, box);
430
431 PG_RETURN_VOID();
432 }
433
434 /*
435 * SP-GiST pick-split function
436 *
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.
439 */
440 Datum
spg_box_quad_picksplit(PG_FUNCTION_ARGS)441 spg_box_quad_picksplit(PG_FUNCTION_ARGS)
442 {
443 spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
444 spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
445 BOX *centroid;
446 int median,
447 i;
448 float8 *lowXs = palloc(sizeof(float8) * in->nTuples);
449 float8 *highXs = palloc(sizeof(float8) * in->nTuples);
450 float8 *lowYs = palloc(sizeof(float8) * in->nTuples);
451 float8 *highYs = palloc(sizeof(float8) * in->nTuples);
452
453 /* Calculate median of all 4D coordinates */
454 for (i = 0; i < in->nTuples; i++)
455 {
456 BOX *box = DatumGetBoxP(in->datums[i]);
457
458 lowXs[i] = box->low.x;
459 highXs[i] = box->high.x;
460 lowYs[i] = box->low.y;
461 highYs[i] = box->high.y;
462 }
463
464 qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
465 qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
466 qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
467 qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
468
469 median = in->nTuples / 2;
470
471 centroid = palloc(sizeof(BOX));
472
473 centroid->low.x = lowXs[median];
474 centroid->high.x = highXs[median];
475 centroid->low.y = lowYs[median];
476 centroid->high.y = highYs[median];
477
478 /* Fill the output */
479 out->hasPrefix = true;
480 out->prefixDatum = BoxPGetDatum(centroid);
481
482 out->nNodes = 16;
483 out->nodeLabels = NULL; /* We don't need node labels. */
484
485 out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
486 out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
487
488 /*
489 * Assign ranges to corresponding nodes according to quadrants relative to
490 * the "centroid" range
491 */
492 for (i = 0; i < in->nTuples; i++)
493 {
494 BOX *box = DatumGetBoxP(in->datums[i]);
495 uint8 quadrant = getQuadrant(centroid, box);
496
497 out->leafTupleDatums[i] = BoxPGetDatum(box);
498 out->mapTuplesToNodes[i] = quadrant;
499 }
500
501 PG_RETURN_VOID();
502 }
503
504 /*
505 * Check if result of consistent method based on bounding box is exact.
506 */
507 static bool
is_bounding_box_test_exact(StrategyNumber strategy)508 is_bounding_box_test_exact(StrategyNumber strategy)
509 {
510 switch (strategy)
511 {
512 case RTLeftStrategyNumber:
513 case RTOverLeftStrategyNumber:
514 case RTOverRightStrategyNumber:
515 case RTRightStrategyNumber:
516 case RTOverBelowStrategyNumber:
517 case RTBelowStrategyNumber:
518 case RTAboveStrategyNumber:
519 case RTOverAboveStrategyNumber:
520 return true;
521
522 default:
523 return false;
524 }
525 }
526
527 /*
528 * Get bounding box for ScanKey.
529 */
530 static BOX *
spg_box_quad_get_scankey_bbox(ScanKey sk,bool * recheck)531 spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
532 {
533 switch (sk->sk_subtype)
534 {
535 case BOXOID:
536 return DatumGetBoxP(sk->sk_argument);
537
538 case POLYGONOID:
539 if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
540 *recheck = true;
541 return &DatumGetPolygonP(sk->sk_argument)->boundbox;
542
543 default:
544 elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
545 return NULL;
546 }
547 }
548
549 /*
550 * SP-GiST inner consistent function
551 */
552 Datum
spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)553 spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
554 {
555 spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
556 spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
557 int i;
558 MemoryContext old_ctx;
559 RectBox *rect_box;
560 uint8 quadrant;
561 RangeBox *centroid,
562 **queries;
563
564 /*
565 * We are saving the traversal value or initialize it an unbounded one, if
566 * we have just begun to walk the tree.
567 */
568 if (in->traversalValue)
569 rect_box = in->traversalValue;
570 else
571 rect_box = initRectBox();
572
573 if (in->allTheSame)
574 {
575 /* Report that all nodes should be visited */
576 out->nNodes = in->nNodes;
577 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
578 for (i = 0; i < in->nNodes; i++)
579 out->nodeNumbers[i] = i;
580
581 if (in->norderbys > 0 && in->nNodes > 0)
582 {
583 double *distances = palloc(sizeof(double) * in->norderbys);
584 int j;
585
586 for (j = 0; j < in->norderbys; j++)
587 {
588 Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
589
590 distances[j] = pointToRectBoxDistance(pt, rect_box);
591 }
592
593 out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
594 out->distances[0] = distances;
595
596 for (i = 1; i < in->nNodes; i++)
597 {
598 out->distances[i] = palloc(sizeof(double) * in->norderbys);
599 memcpy(out->distances[i], distances,
600 sizeof(double) * in->norderbys);
601 }
602 }
603
604 PG_RETURN_VOID();
605 }
606
607 /*
608 * We are casting the prefix and queries to RangeBoxes for ease of the
609 * following operations.
610 */
611 centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
612 queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
613 for (i = 0; i < in->nkeys; i++)
614 {
615 BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
616
617 queries[i] = getRangeBox(box);
618 }
619
620 /* Allocate enough memory for nodes */
621 out->nNodes = 0;
622 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
623 out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
624 if (in->norderbys > 0)
625 out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
626
627 /*
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.
631 */
632 old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
633
634 for (quadrant = 0; quadrant < in->nNodes; quadrant++)
635 {
636 RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
637 bool flag = true;
638
639 for (i = 0; i < in->nkeys; i++)
640 {
641 StrategyNumber strategy = in->scankeys[i].sk_strategy;
642
643 switch (strategy)
644 {
645 case RTOverlapStrategyNumber:
646 flag = overlap4D(next_rect_box, queries[i]);
647 break;
648
649 case RTContainsStrategyNumber:
650 flag = contain4D(next_rect_box, queries[i]);
651 break;
652
653 case RTSameStrategyNumber:
654 case RTContainedByStrategyNumber:
655 flag = contained4D(next_rect_box, queries[i]);
656 break;
657
658 case RTLeftStrategyNumber:
659 flag = left4D(next_rect_box, queries[i]);
660 break;
661
662 case RTOverLeftStrategyNumber:
663 flag = overLeft4D(next_rect_box, queries[i]);
664 break;
665
666 case RTRightStrategyNumber:
667 flag = right4D(next_rect_box, queries[i]);
668 break;
669
670 case RTOverRightStrategyNumber:
671 flag = overRight4D(next_rect_box, queries[i]);
672 break;
673
674 case RTAboveStrategyNumber:
675 flag = above4D(next_rect_box, queries[i]);
676 break;
677
678 case RTOverAboveStrategyNumber:
679 flag = overAbove4D(next_rect_box, queries[i]);
680 break;
681
682 case RTBelowStrategyNumber:
683 flag = below4D(next_rect_box, queries[i]);
684 break;
685
686 case RTOverBelowStrategyNumber:
687 flag = overBelow4D(next_rect_box, queries[i]);
688 break;
689
690 default:
691 elog(ERROR, "unrecognized strategy: %d", strategy);
692 }
693
694 /* If any check is failed, we have found our answer. */
695 if (!flag)
696 break;
697 }
698
699 if (flag)
700 {
701 out->traversalValues[out->nNodes] = next_rect_box;
702 out->nodeNumbers[out->nNodes] = quadrant;
703
704 if (in->norderbys > 0)
705 {
706 double *distances = palloc(sizeof(double) * in->norderbys);
707 int j;
708
709 out->distances[out->nNodes] = distances;
710
711 for (j = 0; j < in->norderbys; j++)
712 {
713 Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
714
715 distances[j] = pointToRectBoxDistance(pt, next_rect_box);
716 }
717 }
718
719 out->nNodes++;
720 }
721 else
722 {
723 /*
724 * If this node is not selected, we don't need to keep the next
725 * traversal value in the memory context.
726 */
727 pfree(next_rect_box);
728 }
729 }
730
731 /* Switch back */
732 MemoryContextSwitchTo(old_ctx);
733
734 PG_RETURN_VOID();
735 }
736
737 /*
738 * SP-GiST inner consistent function
739 */
740 Datum
spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)741 spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
742 {
743 spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
744 spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
745 Datum leaf = in->leafDatum;
746 bool flag = true;
747 int i;
748
749 /* All tests are exact. */
750 out->recheck = false;
751
752 /*
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.
756 */
757 if (in->returnData)
758 out->leafValue = leaf;
759
760 /* Perform the required comparison(s) */
761 for (i = 0; i < in->nkeys; i++)
762 {
763 StrategyNumber strategy = in->scankeys[i].sk_strategy;
764 BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
765 &out->recheck);
766 Datum query = BoxPGetDatum(box);
767
768 switch (strategy)
769 {
770 case RTOverlapStrategyNumber:
771 flag = DatumGetBool(DirectFunctionCall2(box_overlap, leaf,
772 query));
773 break;
774
775 case RTContainsStrategyNumber:
776 flag = DatumGetBool(DirectFunctionCall2(box_contain, leaf,
777 query));
778 break;
779
780 case RTContainedByStrategyNumber:
781 flag = DatumGetBool(DirectFunctionCall2(box_contained, leaf,
782 query));
783 break;
784
785 case RTSameStrategyNumber:
786 flag = DatumGetBool(DirectFunctionCall2(box_same, leaf,
787 query));
788 break;
789
790 case RTLeftStrategyNumber:
791 flag = DatumGetBool(DirectFunctionCall2(box_left, leaf,
792 query));
793 break;
794
795 case RTOverLeftStrategyNumber:
796 flag = DatumGetBool(DirectFunctionCall2(box_overleft, leaf,
797 query));
798 break;
799
800 case RTRightStrategyNumber:
801 flag = DatumGetBool(DirectFunctionCall2(box_right, leaf,
802 query));
803 break;
804
805 case RTOverRightStrategyNumber:
806 flag = DatumGetBool(DirectFunctionCall2(box_overright, leaf,
807 query));
808 break;
809
810 case RTAboveStrategyNumber:
811 flag = DatumGetBool(DirectFunctionCall2(box_above, leaf,
812 query));
813 break;
814
815 case RTOverAboveStrategyNumber:
816 flag = DatumGetBool(DirectFunctionCall2(box_overabove, leaf,
817 query));
818 break;
819
820 case RTBelowStrategyNumber:
821 flag = DatumGetBool(DirectFunctionCall2(box_below, leaf,
822 query));
823 break;
824
825 case RTOverBelowStrategyNumber:
826 flag = DatumGetBool(DirectFunctionCall2(box_overbelow, leaf,
827 query));
828 break;
829
830 default:
831 elog(ERROR, "unrecognized strategy: %d", strategy);
832 }
833
834 /* If any check is failed, we have found our answer. */
835 if (!flag)
836 break;
837 }
838
839 if (flag && in->norderbys > 0)
840 {
841 Oid distfnoid = in->orderbys[0].sk_func.fn_oid;
842
843 out->distances = spg_key_orderbys_distances(leaf, false,
844 in->orderbys, in->norderbys);
845
846 /* Recheck is necessary when computing distance to polygon */
847 out->recheckDistances = distfnoid == F_DIST_POLYP;
848 }
849
850 PG_RETURN_BOOL(flag);
851 }
852
853
854 /*
855 * SP-GiST config function for 2-D types that are lossy represented by their
856 * bounding boxes
857 */
858 Datum
spg_bbox_quad_config(PG_FUNCTION_ARGS)859 spg_bbox_quad_config(PG_FUNCTION_ARGS)
860 {
861 spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
862
863 cfg->prefixType = BOXOID; /* A type represented by its bounding box */
864 cfg->labelType = VOIDOID; /* We don't need node labels. */
865 cfg->leafType = BOXOID;
866 cfg->canReturnData = false;
867 cfg->longValuesOK = false;
868
869 PG_RETURN_VOID();
870 }
871
872 /*
873 * SP-GiST compress function for polygons
874 */
875 Datum
spg_poly_quad_compress(PG_FUNCTION_ARGS)876 spg_poly_quad_compress(PG_FUNCTION_ARGS)
877 {
878 POLYGON *polygon = PG_GETARG_POLYGON_P(0);
879 BOX *box;
880
881 box = (BOX *) palloc(sizeof(BOX));
882 *box = polygon->boundbox;
883
884 PG_RETURN_BOX_P(box);
885 }
886