Branch data 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-2026, 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 : 341181 : compareDoubles(const void *a, const void *b)
94 : : {
95 : 341181 : float8 x = *(float8 *) a;
96 : 341181 : float8 y = *(float8 *) b;
97 : :
98 [ + + ]: 341181 : if (x == y)
99 : 66656 : return 0;
100 : 274525 : return (x > y) ? 1 : -1;
101 : 341181 : }
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 : 145366 : getQuadrant(BOX *centroid, BOX *inBox)
131 : : {
132 : 145366 : uint8 quadrant = 0;
133 : :
134 [ + + ]: 145366 : if (inBox->low.x > centroid->low.x)
135 : 122603 : quadrant |= 0x8;
136 : :
137 [ + + ]: 145366 : if (inBox->high.x > centroid->high.x)
138 : 124864 : quadrant |= 0x4;
139 : :
140 [ + + ]: 145366 : if (inBox->low.y > centroid->low.y)
141 : 78484 : quadrant |= 0x2;
142 : :
143 [ + + ]: 145366 : if (inBox->high.y > centroid->high.y)
144 : 79035 : quadrant |= 0x1;
145 : :
146 : 290732 : return quadrant;
147 : 145366 : }
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 : 2694 : getRangeBox(BOX *box)
158 : : {
159 : 2694 : RangeBox *range_box = palloc_object(RangeBox);
160 : :
161 : 2694 : range_box->left.low = box->low.x;
162 : 2694 : range_box->left.high = box->high.x;
163 : :
164 : 2694 : range_box->right.low = box->low.y;
165 : 2694 : range_box->right.high = box->high.y;
166 : :
167 : 5388 : return range_box;
168 : 2694 : }
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 : 141 : initRectBox(void)
178 : : {
179 : 141 : RectBox *rect_box = palloc_object(RectBox);
180 : 141 : float8 infinity = get_float8_infinity();
181 : :
182 : 141 : rect_box->range_box_x.left.low = -infinity;
183 : 141 : rect_box->range_box_x.left.high = infinity;
184 : :
185 : 141 : rect_box->range_box_x.right.low = -infinity;
186 : 141 : rect_box->range_box_x.right.high = infinity;
187 : :
188 : 141 : rect_box->range_box_y.left.low = -infinity;
189 : 141 : rect_box->range_box_y.left.high = infinity;
190 : :
191 : 141 : rect_box->range_box_y.right.low = -infinity;
192 : 141 : rect_box->range_box_y.right.high = infinity;
193 : :
194 : 282 : return rect_box;
195 : 141 : }
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 : 22336 : nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
206 : : {
207 : 22336 : RectBox *next_rect_box = palloc_object(RectBox);
208 : :
209 : 22336 : memcpy(next_rect_box, rect_box, sizeof(RectBox));
210 : :
211 [ + + ]: 22336 : if (quadrant & 0x8)
212 : 11168 : next_rect_box->range_box_x.left.low = centroid->left.low;
213 : : else
214 : 11168 : next_rect_box->range_box_x.left.high = centroid->left.low;
215 : :
216 [ + + ]: 22336 : if (quadrant & 0x4)
217 : 11168 : next_rect_box->range_box_x.right.low = centroid->left.high;
218 : : else
219 : 11168 : next_rect_box->range_box_x.right.high = centroid->left.high;
220 : :
221 [ + + ]: 22336 : if (quadrant & 0x2)
222 : 11168 : next_rect_box->range_box_y.left.low = centroid->right.low;
223 : : else
224 : 11168 : next_rect_box->range_box_y.left.high = centroid->right.low;
225 : :
226 [ + + ]: 22336 : if (quadrant & 0x1)
227 : 11168 : next_rect_box->range_box_y.right.low = centroid->right.high;
228 : : else
229 : 11168 : next_rect_box->range_box_y.right.high = centroid->right.high;
230 : :
231 : 44672 : return next_rect_box;
232 : 22336 : }
233 : :
234 : : /* Can any range from range_box overlap with this argument? */
235 : : static bool
236 : 1800 : overlap2D(RangeBox *range_box, Range *query)
237 : : {
238 [ + + ]: 3388 : return FPge(range_box->right.high, query->low) &&
239 : 1588 : FPle(range_box->left.low, query->high);
240 : : }
241 : :
242 : : /* Can any rectangle from rect_box overlap with this argument? */
243 : : static bool
244 : 1056 : overlap4D(RectBox *rect_box, RangeBox *query)
245 : : {
246 [ + + ]: 1800 : return overlap2D(&rect_box->range_box_x, &query->left) &&
247 : 744 : overlap2D(&rect_box->range_box_y, &query->right);
248 : : }
249 : :
250 : : /* Can any range from range_box contain this argument? */
251 : : static bool
252 : 296 : contain2D(RangeBox *range_box, Range *query)
253 : : {
254 [ + + ]: 496 : return FPge(range_box->right.high, query->high) &&
255 : 200 : FPle(range_box->left.low, query->low);
256 : : }
257 : :
258 : : /* Can any rectangle from rect_box contain this argument? */
259 : : static bool
260 : 192 : contain4D(RectBox *rect_box, RangeBox *query)
261 : : {
262 [ + + ]: 296 : return contain2D(&rect_box->range_box_x, &query->left) &&
263 : 104 : 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 : 3500 : contained2D(RangeBox *range_box, Range *query)
269 : : {
270 [ + + ]: 6796 : return FPle(range_box->left.low, query->high) &&
271 [ + + ]: 3296 : FPge(range_box->left.high, query->low) &&
272 [ + + ]: 2788 : FPle(range_box->right.low, query->high) &&
273 : 2650 : 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 : 2240 : contained4D(RectBox *rect_box, RangeBox *query)
279 : : {
280 [ + + ]: 3500 : return contained2D(&rect_box->range_box_x, &query->left) &&
281 : 1260 : 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 : 2272 : lower2D(RangeBox *range_box, Range *query)
287 : : {
288 [ + + ]: 4072 : return FPlt(range_box->left.low, query->low) &&
289 : 1800 : 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 : 4048 : overLower2D(RangeBox *range_box, Range *query)
295 : : {
296 [ + + ]: 7784 : return FPle(range_box->left.low, query->high) &&
297 : 3736 : 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 : 5808 : higher2D(RangeBox *range_box, Range *query)
303 : : {
304 [ + + ]: 10312 : return FPgt(range_box->left.high, query->high) &&
305 : 4504 : 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 : 5152 : overHigher2D(RangeBox *range_box, Range *query)
311 : : {
312 [ + + ]: 9896 : return FPge(range_box->left.high, query->low) &&
313 : 4744 : 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 : 1552 : left4D(RectBox *rect_box, RangeBox *query)
319 : : {
320 : 1552 : 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 : 2448 : overLeft4D(RectBox *rect_box, RangeBox *query)
326 : : {
327 : 2448 : 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 : 4384 : right4D(RectBox *rect_box, RangeBox *query)
333 : : {
334 : 4384 : 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 : 2832 : overRight4D(RectBox *rect_box, RangeBox *query)
340 : : {
341 : 2832 : 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 : 720 : below4D(RectBox *rect_box, RangeBox *query)
347 : : {
348 : 720 : 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 : 1600 : overBelow4D(RectBox *rect_box, RangeBox *query)
354 : : {
355 : 1600 : 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 : 1424 : above4D(RectBox *rect_box, RangeBox *query)
361 : : {
362 : 1424 : 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 : 2320 : overAbove4D(RectBox *rect_box, RangeBox *query)
368 : : {
369 : 2320 : 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 : 2201 : pointToRectBoxDistance(Point *point, RectBox *rect_box)
375 : : {
376 : 2201 : double dx;
377 : 2201 : double dy;
378 : :
379 [ + + ]: 2201 : if (point->x < rect_box->range_box_x.left.low)
380 : 1704 : dx = rect_box->range_box_x.left.low - point->x;
381 [ + + ]: 497 : else if (point->x > rect_box->range_box_x.right.high)
382 : 96 : dx = point->x - rect_box->range_box_x.right.high;
383 : : else
384 : 401 : dx = 0;
385 : :
386 [ + + ]: 2201 : if (point->y < rect_box->range_box_y.left.low)
387 : 1064 : dy = rect_box->range_box_y.left.low - point->y;
388 [ + + ]: 1137 : else if (point->y > rect_box->range_box_y.right.high)
389 : 1035 : dy = point->y - rect_box->range_box_y.right.high;
390 : : else
391 : 102 : dy = 0;
392 : :
393 : 4402 : return hypot(dx, dy);
394 : 2201 : }
395 : :
396 : :
397 : : /*
398 : : * SP-GiST config function
399 : : */
400 : : Datum
401 : 11 : spg_box_quad_config(PG_FUNCTION_ARGS)
402 : : {
403 : 11 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
404 : :
405 : 11 : cfg->prefixType = BOXOID;
406 : 11 : cfg->labelType = VOIDOID; /* We don't need node labels. */
407 : 11 : cfg->canReturnData = true;
408 : 11 : cfg->longValuesOK = false;
409 : :
410 : 11 : PG_RETURN_VOID();
411 : 11 : }
412 : :
413 : : /*
414 : : * SP-GiST choose function
415 : : */
416 : : Datum
417 : 125775 : spg_box_quad_choose(PG_FUNCTION_ARGS)
418 : : {
419 : 125775 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
420 : 125775 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
421 : 125775 : BOX *centroid = DatumGetBoxP(in->prefixDatum),
422 : 125775 : *box = DatumGetBoxP(in->leafDatum);
423 : :
424 : 125775 : out->resultType = spgMatchNode;
425 : 125775 : out->result.matchNode.restDatum = BoxPGetDatum(box);
426 : :
427 : : /* nodeN will be set by core, when allTheSame. */
428 [ + + ]: 125775 : if (!in->allTheSame)
429 : 123567 : out->result.matchNode.nodeN = getQuadrant(centroid, box);
430 : :
431 : 125775 : PG_RETURN_VOID();
432 : 125775 : }
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 : 219 : spg_box_quad_picksplit(PG_FUNCTION_ARGS)
442 : : {
443 : 219 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
444 : 219 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
445 : 219 : BOX *centroid;
446 : 219 : int median,
447 : : i;
448 : 219 : float8 *lowXs = palloc_array(float8, in->nTuples);
449 : 219 : float8 *highXs = palloc_array(float8, in->nTuples);
450 : 219 : float8 *lowYs = palloc_array(float8, in->nTuples);
451 : 219 : float8 *highYs = palloc_array(float8, in->nTuples);
452 : :
453 : : /* Calculate median of all 4D coordinates */
454 [ + + ]: 22018 : for (i = 0; i < in->nTuples; i++)
455 : : {
456 : 21799 : BOX *box = DatumGetBoxP(in->datums[i]);
457 : :
458 : 21799 : lowXs[i] = box->low.x;
459 : 21799 : highXs[i] = box->high.x;
460 : 21799 : lowYs[i] = box->low.y;
461 : 21799 : highYs[i] = box->high.y;
462 : 21799 : }
463 : :
464 : 219 : qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
465 : 219 : qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
466 : 219 : qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
467 : 219 : qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
468 : :
469 : 219 : median = in->nTuples / 2;
470 : :
471 : 219 : centroid = palloc_object(BOX);
472 : :
473 : 219 : centroid->low.x = lowXs[median];
474 : 219 : centroid->high.x = highXs[median];
475 : 219 : centroid->low.y = lowYs[median];
476 : 219 : centroid->high.y = highYs[median];
477 : :
478 : : /* Fill the output */
479 : 219 : out->hasPrefix = true;
480 : 219 : out->prefixDatum = BoxPGetDatum(centroid);
481 : :
482 : 219 : out->nNodes = 16;
483 : 219 : out->nodeLabels = NULL; /* We don't need node labels. */
484 : :
485 : 219 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
486 : 219 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
487 : :
488 : : /*
489 : : * Assign ranges to corresponding nodes according to quadrants relative to
490 : : * the "centroid" range
491 : : */
492 [ + + ]: 22018 : for (i = 0; i < in->nTuples; i++)
493 : : {
494 : 21799 : BOX *box = DatumGetBoxP(in->datums[i]);
495 : 21799 : uint8 quadrant = getQuadrant(centroid, box);
496 : :
497 : 21799 : out->leafTupleDatums[i] = BoxPGetDatum(box);
498 : 21799 : out->mapTuplesToNodes[i] = quadrant;
499 : 21799 : }
500 : :
501 : 219 : PG_RETURN_VOID();
502 : 219 : }
503 : :
504 : : /*
505 : : * Check if result of consistent method based on bounding box is exact.
506 : : */
507 : : static bool
508 : 65340 : is_bounding_box_test_exact(StrategyNumber strategy)
509 : : {
510 [ + + ]: 65340 : 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 : 54169 : return true;
521 : :
522 : : default:
523 : 11171 : return false;
524 : : }
525 : 65340 : }
526 : :
527 : : /*
528 : : * Get bounding box for ScanKey.
529 : : */
530 : : static BOX *
531 : 131855 : spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
532 : : {
533 [ + + - ]: 131855 : switch (sk->sk_subtype)
534 : : {
535 : : case BOXOID:
536 : 65918 : return DatumGetBoxP(sk->sk_argument);
537 : :
538 : : case POLYGONOID:
539 [ + + + + ]: 65937 : if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
540 : 11171 : *recheck = true;
541 : 65937 : return &DatumGetPolygonP(sk->sk_argument)->boundbox;
542 : :
543 : : default:
544 [ # # # # ]: 0 : elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
545 : 0 : return NULL;
546 : : }
547 : 131855 : }
548 : :
549 : : /*
550 : : * SP-GiST inner consistent function
551 : : */
552 : : Datum
553 : 1521 : spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
554 : : {
555 : 1521 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
556 : 1521 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
557 : 1521 : int i;
558 : 1521 : MemoryContext old_ctx;
559 : 1521 : RectBox *rect_box;
560 : 1521 : uint8 quadrant;
561 : 1521 : 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 [ + + ]: 1521 : if (in->traversalValue)
569 : 1380 : rect_box = in->traversalValue;
570 : : else
571 : 141 : rect_box = initRectBox();
572 : :
573 [ + + ]: 1521 : if (in->allTheSame)
574 : : {
575 : : /* Report that all nodes should be visited */
576 : 125 : out->nNodes = in->nNodes;
577 : 125 : out->nodeNumbers = palloc_array(int, in->nNodes);
578 [ + + ]: 1125 : for (i = 0; i < in->nNodes; i++)
579 : 1000 : out->nodeNumbers[i] = i;
580 : :
581 [ + + - + ]: 125 : if (in->norderbys > 0 && in->nNodes > 0)
582 : : {
583 : 16 : double *distances = palloc_array(double, in->norderbys);
584 : 16 : int j;
585 : :
586 [ + + ]: 32 : for (j = 0; j < in->norderbys; j++)
587 : : {
588 : 16 : Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
589 : :
590 : 16 : distances[j] = pointToRectBoxDistance(pt, rect_box);
591 : 16 : }
592 : :
593 : 16 : out->distances = palloc_array(double *, in->nNodes);
594 : 16 : out->distances[0] = distances;
595 : :
596 [ + + ]: 128 : for (i = 1; i < in->nNodes; i++)
597 : : {
598 : 112 : out->distances[i] = palloc_array(double, in->norderbys);
599 : 112 : memcpy(out->distances[i], distances,
600 : : sizeof(double) * in->norderbys);
601 : 112 : }
602 : 16 : }
603 : :
604 : 125 : 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 : 1396 : centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
612 : 1396 : queries = palloc_array(RangeBox *, in->nkeys);
613 [ + + ]: 2694 : for (i = 0; i < in->nkeys; i++)
614 : : {
615 : 1298 : BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
616 : :
617 : 1298 : queries[i] = getRangeBox(box);
618 : 1298 : }
619 : :
620 : : /* Allocate enough memory for nodes */
621 : 1396 : out->nNodes = 0;
622 : 1396 : out->nodeNumbers = palloc_array(int, in->nNodes);
623 : 1396 : out->traversalValues = palloc_array(void *, in->nNodes);
624 [ + + ]: 1396 : if (in->norderbys > 0)
625 : 166 : out->distances = palloc_array(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 : 1396 : old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
633 : :
634 [ + + ]: 23732 : for (quadrant = 0; quadrant < in->nNodes; quadrant++)
635 : : {
636 : 22336 : RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
637 : 22336 : bool flag = true;
638 : :
639 [ + + ]: 37753 : for (i = 0; i < in->nkeys; i++)
640 : : {
641 : 20768 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
642 : :
643 [ + + + + : 20768 : switch (strategy)
+ + + + +
+ - + ]
644 : : {
645 : : case RTOverlapStrategyNumber:
646 : 1056 : flag = overlap4D(next_rect_box, queries[i]);
647 : 1056 : break;
648 : :
649 : : case RTContainsStrategyNumber:
650 : 192 : flag = contain4D(next_rect_box, queries[i]);
651 : 192 : break;
652 : :
653 : : case RTSameStrategyNumber:
654 : : case RTContainedByStrategyNumber:
655 : 2240 : flag = contained4D(next_rect_box, queries[i]);
656 : 2240 : break;
657 : :
658 : : case RTLeftStrategyNumber:
659 : 1552 : flag = left4D(next_rect_box, queries[i]);
660 : 1552 : break;
661 : :
662 : : case RTOverLeftStrategyNumber:
663 : 2448 : flag = overLeft4D(next_rect_box, queries[i]);
664 : 2448 : break;
665 : :
666 : : case RTRightStrategyNumber:
667 : 4384 : flag = right4D(next_rect_box, queries[i]);
668 : 4384 : break;
669 : :
670 : : case RTOverRightStrategyNumber:
671 : 2832 : flag = overRight4D(next_rect_box, queries[i]);
672 : 2832 : break;
673 : :
674 : : case RTAboveStrategyNumber:
675 : 1424 : flag = above4D(next_rect_box, queries[i]);
676 : 1424 : break;
677 : :
678 : : case RTOverAboveStrategyNumber:
679 : 2320 : flag = overAbove4D(next_rect_box, queries[i]);
680 : 2320 : break;
681 : :
682 : : case RTBelowStrategyNumber:
683 : 720 : flag = below4D(next_rect_box, queries[i]);
684 : 720 : break;
685 : :
686 : : case RTOverBelowStrategyNumber:
687 : 1600 : flag = overBelow4D(next_rect_box, queries[i]);
688 : 1600 : break;
689 : :
690 : : default:
691 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy: %d", strategy);
692 : 0 : }
693 : :
694 : : /* If any check is failed, we have found our answer. */
695 [ + + ]: 20768 : if (!flag)
696 : 5351 : break;
697 [ - + + ]: 20768 : }
698 : :
699 [ + + ]: 22336 : if (flag)
700 : : {
701 : 16985 : out->traversalValues[out->nNodes] = next_rect_box;
702 : 16985 : out->nodeNumbers[out->nNodes] = quadrant;
703 : :
704 [ + + ]: 16985 : if (in->norderbys > 0)
705 : : {
706 : 2185 : double *distances = palloc_array(double, in->norderbys);
707 : 2185 : int j;
708 : :
709 : 2185 : out->distances[out->nNodes] = distances;
710 : :
711 [ + + ]: 4370 : for (j = 0; j < in->norderbys; j++)
712 : : {
713 : 2185 : Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
714 : :
715 : 2185 : distances[j] = pointToRectBoxDistance(pt, next_rect_box);
716 : 2185 : }
717 : 2185 : }
718 : :
719 : 16985 : out->nNodes++;
720 : 16985 : }
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 : 5351 : pfree(next_rect_box);
728 : : }
729 : 22336 : }
730 : :
731 : : /* Switch back */
732 : 1396 : MemoryContextSwitchTo(old_ctx);
733 : :
734 : 1396 : PG_RETURN_VOID();
735 : 1521 : }
736 : :
737 : : /*
738 : : * SP-GiST inner consistent function
739 : : */
740 : : Datum
741 : 141560 : spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
742 : : {
743 : 141560 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
744 : 141560 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
745 : 141560 : Datum leaf = in->leafDatum;
746 : 141560 : bool flag = true;
747 : 141560 : int i;
748 : :
749 : : /* All tests are exact. */
750 : 141560 : 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 [ + + ]: 141560 : if (in->returnData)
758 : 971 : out->leafValue = leaf;
759 : :
760 : : /* Perform the required comparison(s) */
761 [ + + ]: 247919 : for (i = 0; i < in->nkeys; i++)
762 : : {
763 : 130557 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
764 : 261114 : BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
765 : 130557 : &out->recheck);
766 : 130557 : Datum query = BoxPGetDatum(box);
767 : :
768 [ + + + + : 130557 : switch (strategy)
+ + + + +
+ + - + ]
769 : : {
770 : : case RTOverlapStrategyNumber:
771 : 6053 : flag = DatumGetBool(DirectFunctionCall2(box_overlap, leaf,
772 : : query));
773 : 6053 : break;
774 : :
775 : : case RTContainsStrategyNumber:
776 : 1401 : flag = DatumGetBool(DirectFunctionCall2(box_contain, leaf,
777 : : query));
778 : 1401 : break;
779 : :
780 : : case RTContainedByStrategyNumber:
781 : 11542 : flag = DatumGetBool(DirectFunctionCall2(box_contained, leaf,
782 : : query));
783 : 11542 : break;
784 : :
785 : : case RTSameStrategyNumber:
786 : 2172 : flag = DatumGetBool(DirectFunctionCall2(box_same, leaf,
787 : : query));
788 : 2172 : break;
789 : :
790 : : case RTLeftStrategyNumber:
791 : 8032 : flag = DatumGetBool(DirectFunctionCall2(box_left, leaf,
792 : : query));
793 : 8032 : break;
794 : :
795 : : case RTOverLeftStrategyNumber:
796 : 16313 : flag = DatumGetBool(DirectFunctionCall2(box_overleft, leaf,
797 : : query));
798 : 16313 : break;
799 : :
800 : : case RTRightStrategyNumber:
801 : 21652 : flag = DatumGetBool(DirectFunctionCall2(box_right, leaf,
802 : : query));
803 : 21652 : break;
804 : :
805 : : case RTOverRightStrategyNumber:
806 : 18428 : flag = DatumGetBool(DirectFunctionCall2(box_overright, leaf,
807 : : query));
808 : 18428 : break;
809 : :
810 : : case RTAboveStrategyNumber:
811 : 9320 : flag = DatumGetBool(DirectFunctionCall2(box_above, leaf,
812 : : query));
813 : 9320 : break;
814 : :
815 : : case RTOverAboveStrategyNumber:
816 : 18225 : flag = DatumGetBool(DirectFunctionCall2(box_overabove, leaf,
817 : : query));
818 : 18225 : break;
819 : :
820 : : case RTBelowStrategyNumber:
821 : 4313 : flag = DatumGetBool(DirectFunctionCall2(box_below, leaf,
822 : : query));
823 : 4313 : break;
824 : :
825 : : case RTOverBelowStrategyNumber:
826 : 13106 : flag = DatumGetBool(DirectFunctionCall2(box_overbelow, leaf,
827 : : query));
828 : 13106 : break;
829 : :
830 : : default:
831 [ # # # # ]: 0 : elog(ERROR, "unrecognized strategy: %d", strategy);
832 : 0 : }
833 : :
834 : : /* If any check is failed, we have found our answer. */
835 [ + + ]: 130557 : if (!flag)
836 : 24198 : break;
837 [ - + + ]: 130557 : }
838 : :
839 [ + + + + ]: 141560 : if (flag && in->norderbys > 0)
840 : : {
841 : 14424 : Oid distfnoid = in->orderbys[0].sk_func.fn_oid;
842 : :
843 : 28848 : out->distances = spg_key_orderbys_distances(leaf, false,
844 : 14424 : in->orderbys, in->norderbys);
845 : :
846 : : /* Recheck is necessary when computing distance to polygon */
847 : 14424 : out->recheckDistances = distfnoid == F_DIST_POLYP;
848 : 14424 : }
849 : :
850 : 283120 : PG_RETURN_BOOL(flag);
851 : 141560 : }
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 : 4 : spg_bbox_quad_config(PG_FUNCTION_ARGS)
860 : : {
861 : 4 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
862 : :
863 : 4 : cfg->prefixType = BOXOID; /* A type represented by its bounding box */
864 : 4 : cfg->labelType = VOIDOID; /* We don't need node labels. */
865 : 4 : cfg->leafType = BOXOID;
866 : 4 : cfg->canReturnData = false;
867 : 4 : cfg->longValuesOK = false;
868 : :
869 : 4 : PG_RETURN_VOID();
870 : 4 : }
871 : :
872 : : /*
873 : : * SP-GiST compress function for polygons
874 : : */
875 : : Datum
876 : 11000 : spg_poly_quad_compress(PG_FUNCTION_ARGS)
877 : : {
878 : 11000 : POLYGON *polygon = PG_GETARG_POLYGON_P(0);
879 : 11000 : BOX *box;
880 : :
881 : 11000 : box = palloc_object(BOX);
882 : 11000 : *box = polygon->boundbox;
883 : :
884 : 22000 : PG_RETURN_BOX_P(box);
885 : 11000 : }
|
