Line data Source code
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-2024, 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
93 2047566 : compareDoubles(const void *a, const void *b)
94 : {
95 2047566 : float8 x = *(float8 *) a;
96 2047566 : float8 y = *(float8 *) b;
97 :
98 2047566 : if (x == y)
99 400416 : return 0;
100 1647150 : 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
130 872202 : getQuadrant(BOX *centroid, BOX *inBox)
131 : {
132 872202 : uint8 quadrant = 0;
133 :
134 872202 : if (inBox->low.x > centroid->low.x)
135 735618 : quadrant |= 0x8;
136 :
137 872202 : if (inBox->high.x > centroid->high.x)
138 749184 : quadrant |= 0x4;
139 :
140 872202 : if (inBox->low.y > centroid->low.y)
141 470904 : quadrant |= 0x2;
142 :
143 872202 : if (inBox->high.y > centroid->high.y)
144 474210 : quadrant |= 0x1;
145 :
146 872202 : 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 *
157 16164 : getRangeBox(BOX *box)
158 : {
159 16164 : RangeBox *range_box = (RangeBox *) palloc(sizeof(RangeBox));
160 :
161 16164 : range_box->left.low = box->low.x;
162 16164 : range_box->left.high = box->high.x;
163 :
164 16164 : range_box->right.low = box->low.y;
165 16164 : range_box->right.high = box->high.y;
166 :
167 16164 : 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 *
177 846 : initRectBox(void)
178 : {
179 846 : RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
180 846 : float8 infinity = get_float8_infinity();
181 :
182 846 : rect_box->range_box_x.left.low = -infinity;
183 846 : rect_box->range_box_x.left.high = infinity;
184 :
185 846 : rect_box->range_box_x.right.low = -infinity;
186 846 : rect_box->range_box_x.right.high = infinity;
187 :
188 846 : rect_box->range_box_y.left.low = -infinity;
189 846 : rect_box->range_box_y.left.high = infinity;
190 :
191 846 : rect_box->range_box_y.right.low = -infinity;
192 846 : rect_box->range_box_y.right.high = infinity;
193 :
194 846 : 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 *
205 134016 : nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
206 : {
207 134016 : RectBox *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
208 :
209 134016 : memcpy(next_rect_box, rect_box, sizeof(RectBox));
210 :
211 134016 : if (quadrant & 0x8)
212 67008 : next_rect_box->range_box_x.left.low = centroid->left.low;
213 : else
214 67008 : next_rect_box->range_box_x.left.high = centroid->left.low;
215 :
216 134016 : if (quadrant & 0x4)
217 67008 : next_rect_box->range_box_x.right.low = centroid->left.high;
218 : else
219 67008 : next_rect_box->range_box_x.right.high = centroid->left.high;
220 :
221 134016 : if (quadrant & 0x2)
222 67008 : next_rect_box->range_box_y.left.low = centroid->right.low;
223 : else
224 67008 : next_rect_box->range_box_y.left.high = centroid->right.low;
225 :
226 134016 : if (quadrant & 0x1)
227 67008 : next_rect_box->range_box_y.right.low = centroid->right.high;
228 : else
229 67008 : next_rect_box->range_box_y.right.high = centroid->right.high;
230 :
231 134016 : return next_rect_box;
232 : }
233 :
234 : /* Can any range from range_box overlap with this argument? */
235 : static bool
236 10800 : overlap2D(RangeBox *range_box, Range *query)
237 : {
238 20328 : return FPge(range_box->right.high, query->low) &&
239 9528 : FPle(range_box->left.low, query->high);
240 : }
241 :
242 : /* Can any rectangle from rect_box overlap with this argument? */
243 : static bool
244 6336 : overlap4D(RectBox *rect_box, RangeBox *query)
245 : {
246 10800 : return overlap2D(&rect_box->range_box_x, &query->left) &&
247 4464 : overlap2D(&rect_box->range_box_y, &query->right);
248 : }
249 :
250 : /* Can any range from range_box contain this argument? */
251 : static bool
252 1776 : contain2D(RangeBox *range_box, Range *query)
253 : {
254 2976 : return FPge(range_box->right.high, query->high) &&
255 1200 : FPle(range_box->left.low, query->low);
256 : }
257 :
258 : /* Can any rectangle from rect_box contain this argument? */
259 : static bool
260 1152 : contain4D(RectBox *rect_box, RangeBox *query)
261 : {
262 1776 : return contain2D(&rect_box->range_box_x, &query->left) &&
263 624 : 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
268 21000 : contained2D(RangeBox *range_box, Range *query)
269 : {
270 40776 : return FPle(range_box->left.low, query->high) &&
271 36504 : FPge(range_box->left.high, query->low) &&
272 57504 : FPle(range_box->right.low, query->high) &&
273 15900 : FPge(range_box->right.high, query->low);
274 : }
275 :
276 : /* Can any rectangle from rect_box be contained by this argument? */
277 : static bool
278 13440 : contained4D(RectBox *rect_box, RangeBox *query)
279 : {
280 21000 : return contained2D(&rect_box->range_box_x, &query->left) &&
281 7560 : 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
286 13632 : lower2D(RangeBox *range_box, Range *query)
287 : {
288 24432 : return FPlt(range_box->left.low, query->low) &&
289 10800 : 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
294 24288 : overLower2D(RangeBox *range_box, Range *query)
295 : {
296 46704 : return FPle(range_box->left.low, query->high) &&
297 22416 : 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
302 34848 : higher2D(RangeBox *range_box, Range *query)
303 : {
304 61872 : return FPgt(range_box->left.high, query->high) &&
305 27024 : 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
310 30912 : overHigher2D(RangeBox *range_box, Range *query)
311 : {
312 59376 : return FPge(range_box->left.high, query->low) &&
313 28464 : FPge(range_box->right.high, query->low);
314 : }
315 :
316 : /* Can any rectangle from rect_box be left of this argument? */
317 : static bool
318 9312 : left4D(RectBox *rect_box, RangeBox *query)
319 : {
320 9312 : 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
325 14688 : overLeft4D(RectBox *rect_box, RangeBox *query)
326 : {
327 14688 : 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
332 26304 : right4D(RectBox *rect_box, RangeBox *query)
333 : {
334 26304 : 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
339 16992 : overRight4D(RectBox *rect_box, RangeBox *query)
340 : {
341 16992 : 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
346 4320 : below4D(RectBox *rect_box, RangeBox *query)
347 : {
348 4320 : 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
353 9600 : overBelow4D(RectBox *rect_box, RangeBox *query)
354 : {
355 9600 : 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
360 8544 : above4D(RectBox *rect_box, RangeBox *query)
361 : {
362 8544 : 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
367 13920 : overAbove4D(RectBox *rect_box, RangeBox *query)
368 : {
369 13920 : 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
374 13206 : pointToRectBoxDistance(Point *point, RectBox *rect_box)
375 : {
376 : double dx;
377 : double dy;
378 :
379 13206 : if (point->x < rect_box->range_box_x.left.low)
380 10224 : dx = rect_box->range_box_x.left.low - point->x;
381 2982 : else if (point->x > rect_box->range_box_x.right.high)
382 576 : dx = point->x - rect_box->range_box_x.right.high;
383 : else
384 2406 : dx = 0;
385 :
386 13206 : if (point->y < rect_box->range_box_y.left.low)
387 6384 : dy = rect_box->range_box_y.left.low - point->y;
388 6822 : else if (point->y > rect_box->range_box_y.right.high)
389 6210 : dy = point->y - rect_box->range_box_y.right.high;
390 : else
391 612 : dy = 0;
392 :
393 13206 : return HYPOT(dx, dy);
394 : }
395 :
396 :
397 : /*
398 : * SP-GiST config function
399 : */
400 : Datum
401 72 : spg_box_quad_config(PG_FUNCTION_ARGS)
402 : {
403 72 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
404 :
405 72 : cfg->prefixType = BOXOID;
406 72 : cfg->labelType = VOIDOID; /* We don't need node labels. */
407 72 : cfg->canReturnData = true;
408 72 : cfg->longValuesOK = false;
409 :
410 72 : PG_RETURN_VOID();
411 : }
412 :
413 : /*
414 : * SP-GiST choose function
415 : */
416 : Datum
417 754556 : spg_box_quad_choose(PG_FUNCTION_ARGS)
418 : {
419 754556 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
420 754556 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
421 754556 : BOX *centroid = DatumGetBoxP(in->prefixDatum),
422 754556 : *box = DatumGetBoxP(in->leafDatum);
423 :
424 754556 : out->resultType = spgMatchNode;
425 754556 : out->result.matchNode.restDatum = BoxPGetDatum(box);
426 :
427 : /* nodeN will be set by core, when allTheSame. */
428 754556 : if (!in->allTheSame)
429 741402 : out->result.matchNode.nodeN = getQuadrant(centroid, box);
430 :
431 754556 : 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
441 1314 : spg_box_quad_picksplit(PG_FUNCTION_ARGS)
442 : {
443 1314 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
444 1314 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
445 : BOX *centroid;
446 : int median,
447 : i;
448 1314 : float8 *lowXs = palloc(sizeof(float8) * in->nTuples);
449 1314 : float8 *highXs = palloc(sizeof(float8) * in->nTuples);
450 1314 : float8 *lowYs = palloc(sizeof(float8) * in->nTuples);
451 1314 : float8 *highYs = palloc(sizeof(float8) * in->nTuples);
452 :
453 : /* Calculate median of all 4D coordinates */
454 132114 : for (i = 0; i < in->nTuples; i++)
455 : {
456 130800 : BOX *box = DatumGetBoxP(in->datums[i]);
457 :
458 130800 : lowXs[i] = box->low.x;
459 130800 : highXs[i] = box->high.x;
460 130800 : lowYs[i] = box->low.y;
461 130800 : highYs[i] = box->high.y;
462 : }
463 :
464 1314 : qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
465 1314 : qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
466 1314 : qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
467 1314 : qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
468 :
469 1314 : median = in->nTuples / 2;
470 :
471 1314 : centroid = palloc(sizeof(BOX));
472 :
473 1314 : centroid->low.x = lowXs[median];
474 1314 : centroid->high.x = highXs[median];
475 1314 : centroid->low.y = lowYs[median];
476 1314 : centroid->high.y = highYs[median];
477 :
478 : /* Fill the output */
479 1314 : out->hasPrefix = true;
480 1314 : out->prefixDatum = BoxPGetDatum(centroid);
481 :
482 1314 : out->nNodes = 16;
483 1314 : out->nodeLabels = NULL; /* We don't need node labels. */
484 :
485 1314 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
486 1314 : 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 132114 : for (i = 0; i < in->nTuples; i++)
493 : {
494 130800 : BOX *box = DatumGetBoxP(in->datums[i]);
495 130800 : uint8 quadrant = getQuadrant(centroid, box);
496 :
497 130800 : out->leafTupleDatums[i] = BoxPGetDatum(box);
498 130800 : out->mapTuplesToNodes[i] = quadrant;
499 : }
500 :
501 1314 : PG_RETURN_VOID();
502 : }
503 :
504 : /*
505 : * Check if result of consistent method based on bounding box is exact.
506 : */
507 : static bool
508 392040 : is_bounding_box_test_exact(StrategyNumber strategy)
509 : {
510 392040 : switch (strategy)
511 : {
512 325014 : case RTLeftStrategyNumber:
513 : case RTOverLeftStrategyNumber:
514 : case RTOverRightStrategyNumber:
515 : case RTRightStrategyNumber:
516 : case RTOverBelowStrategyNumber:
517 : case RTBelowStrategyNumber:
518 : case RTAboveStrategyNumber:
519 : case RTOverAboveStrategyNumber:
520 325014 : return true;
521 :
522 67026 : default:
523 67026 : return false;
524 : }
525 : }
526 :
527 : /*
528 : * Get bounding box for ScanKey.
529 : */
530 : static BOX *
531 791130 : spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
532 : {
533 791130 : switch (sk->sk_subtype)
534 : {
535 395508 : case BOXOID:
536 395508 : return DatumGetBoxP(sk->sk_argument);
537 :
538 395622 : case POLYGONOID:
539 395622 : if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
540 67026 : *recheck = true;
541 395622 : return &DatumGetPolygonP(sk->sk_argument)->boundbox;
542 :
543 0 : default:
544 0 : 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
553 9126 : spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
554 : {
555 9126 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
556 9126 : 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 9126 : if (in->traversalValue)
569 8280 : rect_box = in->traversalValue;
570 : else
571 846 : rect_box = initRectBox();
572 :
573 9126 : if (in->allTheSame)
574 : {
575 : /* Report that all nodes should be visited */
576 750 : out->nNodes = in->nNodes;
577 750 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
578 6750 : for (i = 0; i < in->nNodes; i++)
579 6000 : out->nodeNumbers[i] = i;
580 :
581 750 : if (in->norderbys > 0 && in->nNodes > 0)
582 : {
583 96 : double *distances = palloc(sizeof(double) * in->norderbys);
584 : int j;
585 :
586 192 : for (j = 0; j < in->norderbys; j++)
587 : {
588 96 : Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
589 :
590 96 : distances[j] = pointToRectBoxDistance(pt, rect_box);
591 : }
592 :
593 96 : out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
594 96 : out->distances[0] = distances;
595 :
596 768 : for (i = 1; i < in->nNodes; i++)
597 : {
598 672 : out->distances[i] = palloc(sizeof(double) * in->norderbys);
599 672 : memcpy(out->distances[i], distances,
600 672 : sizeof(double) * in->norderbys);
601 : }
602 : }
603 :
604 750 : 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 8376 : centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
612 8376 : queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
613 16164 : for (i = 0; i < in->nkeys; i++)
614 : {
615 7788 : BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
616 :
617 7788 : queries[i] = getRangeBox(box);
618 : }
619 :
620 : /* Allocate enough memory for nodes */
621 8376 : out->nNodes = 0;
622 8376 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
623 8376 : out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
624 8376 : if (in->norderbys > 0)
625 996 : 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 8376 : old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
633 :
634 142392 : for (quadrant = 0; quadrant < in->nNodes; quadrant++)
635 : {
636 134016 : RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
637 134016 : bool flag = true;
638 :
639 226518 : for (i = 0; i < in->nkeys; i++)
640 : {
641 124608 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
642 :
643 124608 : switch (strategy)
644 : {
645 6336 : case RTOverlapStrategyNumber:
646 6336 : flag = overlap4D(next_rect_box, queries[i]);
647 6336 : break;
648 :
649 1152 : case RTContainsStrategyNumber:
650 1152 : flag = contain4D(next_rect_box, queries[i]);
651 1152 : break;
652 :
653 13440 : case RTSameStrategyNumber:
654 : case RTContainedByStrategyNumber:
655 13440 : flag = contained4D(next_rect_box, queries[i]);
656 13440 : break;
657 :
658 9312 : case RTLeftStrategyNumber:
659 9312 : flag = left4D(next_rect_box, queries[i]);
660 9312 : break;
661 :
662 14688 : case RTOverLeftStrategyNumber:
663 14688 : flag = overLeft4D(next_rect_box, queries[i]);
664 14688 : break;
665 :
666 26304 : case RTRightStrategyNumber:
667 26304 : flag = right4D(next_rect_box, queries[i]);
668 26304 : break;
669 :
670 16992 : case RTOverRightStrategyNumber:
671 16992 : flag = overRight4D(next_rect_box, queries[i]);
672 16992 : break;
673 :
674 8544 : case RTAboveStrategyNumber:
675 8544 : flag = above4D(next_rect_box, queries[i]);
676 8544 : break;
677 :
678 13920 : case RTOverAboveStrategyNumber:
679 13920 : flag = overAbove4D(next_rect_box, queries[i]);
680 13920 : break;
681 :
682 4320 : case RTBelowStrategyNumber:
683 4320 : flag = below4D(next_rect_box, queries[i]);
684 4320 : break;
685 :
686 9600 : case RTOverBelowStrategyNumber:
687 9600 : flag = overBelow4D(next_rect_box, queries[i]);
688 9600 : break;
689 :
690 0 : default:
691 0 : elog(ERROR, "unrecognized strategy: %d", strategy);
692 : }
693 :
694 : /* If any check is failed, we have found our answer. */
695 124608 : if (!flag)
696 32106 : break;
697 : }
698 :
699 134016 : if (flag)
700 : {
701 101910 : out->traversalValues[out->nNodes] = next_rect_box;
702 101910 : out->nodeNumbers[out->nNodes] = quadrant;
703 :
704 101910 : if (in->norderbys > 0)
705 : {
706 13110 : double *distances = palloc(sizeof(double) * in->norderbys);
707 : int j;
708 :
709 13110 : out->distances[out->nNodes] = distances;
710 :
711 26220 : for (j = 0; j < in->norderbys; j++)
712 : {
713 13110 : Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
714 :
715 13110 : distances[j] = pointToRectBoxDistance(pt, next_rect_box);
716 : }
717 : }
718 :
719 101910 : 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 32106 : pfree(next_rect_box);
728 : }
729 : }
730 :
731 : /* Switch back */
732 8376 : MemoryContextSwitchTo(old_ctx);
733 :
734 8376 : PG_RETURN_VOID();
735 : }
736 :
737 : /*
738 : * SP-GiST inner consistent function
739 : */
740 : Datum
741 849360 : spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
742 : {
743 849360 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
744 849360 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
745 849360 : Datum leaf = in->leafDatum;
746 849360 : bool flag = true;
747 : int i;
748 :
749 : /* All tests are exact. */
750 849360 : 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 849360 : if (in->returnData)
758 5826 : out->leafValue = leaf;
759 :
760 : /* Perform the required comparison(s) */
761 1487514 : for (i = 0; i < in->nkeys; i++)
762 : {
763 783342 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
764 783342 : BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
765 : &out->recheck);
766 783342 : Datum query = BoxPGetDatum(box);
767 :
768 783342 : switch (strategy)
769 : {
770 36318 : case RTOverlapStrategyNumber:
771 36318 : flag = DatumGetBool(DirectFunctionCall2(box_overlap, leaf,
772 : query));
773 36318 : break;
774 :
775 8406 : case RTContainsStrategyNumber:
776 8406 : flag = DatumGetBool(DirectFunctionCall2(box_contain, leaf,
777 : query));
778 8406 : break;
779 :
780 69252 : case RTContainedByStrategyNumber:
781 69252 : flag = DatumGetBool(DirectFunctionCall2(box_contained, leaf,
782 : query));
783 69252 : break;
784 :
785 13032 : case RTSameStrategyNumber:
786 13032 : flag = DatumGetBool(DirectFunctionCall2(box_same, leaf,
787 : query));
788 13032 : break;
789 :
790 48192 : case RTLeftStrategyNumber:
791 48192 : flag = DatumGetBool(DirectFunctionCall2(box_left, leaf,
792 : query));
793 48192 : break;
794 :
795 97878 : case RTOverLeftStrategyNumber:
796 97878 : flag = DatumGetBool(DirectFunctionCall2(box_overleft, leaf,
797 : query));
798 97878 : break;
799 :
800 129912 : case RTRightStrategyNumber:
801 129912 : flag = DatumGetBool(DirectFunctionCall2(box_right, leaf,
802 : query));
803 129912 : break;
804 :
805 110568 : case RTOverRightStrategyNumber:
806 110568 : flag = DatumGetBool(DirectFunctionCall2(box_overright, leaf,
807 : query));
808 110568 : break;
809 :
810 55920 : case RTAboveStrategyNumber:
811 55920 : flag = DatumGetBool(DirectFunctionCall2(box_above, leaf,
812 : query));
813 55920 : break;
814 :
815 109350 : case RTOverAboveStrategyNumber:
816 109350 : flag = DatumGetBool(DirectFunctionCall2(box_overabove, leaf,
817 : query));
818 109350 : break;
819 :
820 25878 : case RTBelowStrategyNumber:
821 25878 : flag = DatumGetBool(DirectFunctionCall2(box_below, leaf,
822 : query));
823 25878 : break;
824 :
825 78636 : case RTOverBelowStrategyNumber:
826 78636 : flag = DatumGetBool(DirectFunctionCall2(box_overbelow, leaf,
827 : query));
828 78636 : break;
829 :
830 0 : default:
831 0 : elog(ERROR, "unrecognized strategy: %d", strategy);
832 : }
833 :
834 : /* If any check is failed, we have found our answer. */
835 783342 : if (!flag)
836 145188 : break;
837 : }
838 :
839 849360 : if (flag && in->norderbys > 0)
840 : {
841 86544 : Oid distfnoid = in->orderbys[0].sk_func.fn_oid;
842 :
843 86544 : out->distances = spg_key_orderbys_distances(leaf, false,
844 : in->orderbys, in->norderbys);
845 :
846 : /* Recheck is necessary when computing distance to polygon */
847 86544 : out->recheckDistances = distfnoid == F_DIST_POLYP;
848 : }
849 :
850 849360 : 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
859 26 : spg_bbox_quad_config(PG_FUNCTION_ARGS)
860 : {
861 26 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
862 :
863 26 : cfg->prefixType = BOXOID; /* A type represented by its bounding box */
864 26 : cfg->labelType = VOIDOID; /* We don't need node labels. */
865 26 : cfg->leafType = BOXOID;
866 26 : cfg->canReturnData = false;
867 26 : cfg->longValuesOK = false;
868 :
869 26 : PG_RETURN_VOID();
870 : }
871 :
872 : /*
873 : * SP-GiST compress function for polygons
874 : */
875 : Datum
876 66000 : spg_poly_quad_compress(PG_FUNCTION_ARGS)
877 : {
878 66000 : POLYGON *polygon = PG_GETARG_POLYGON_P(0);
879 : BOX *box;
880 :
881 66000 : box = (BOX *) palloc(sizeof(BOX));
882 66000 : *box = polygon->boundbox;
883 :
884 66000 : PG_RETURN_BOX_P(box);
885 : }
|
