Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * spgquadtreeproc.c
4 : : * implementation of quad tree over points for SP-GiST
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/spgist/spgquadtreeproc.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : :
16 : : #include "postgres.h"
17 : :
18 : : #include "access/spgist.h"
19 : : #include "access/spgist_private.h"
20 : : #include "access/stratnum.h"
21 : : #include "catalog/pg_type.h"
22 : : #include "utils/float.h"
23 : : #include "utils/fmgrprotos.h"
24 : : #include "utils/geo_decls.h"
25 : :
26 : : Datum
27 : 83 : spg_quad_config(PG_FUNCTION_ARGS)
28 : : {
29 : : #ifdef NOT_USED
30 : : spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
31 : : #endif
32 : 83 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
33 : :
34 : 83 : cfg->prefixType = POINTOID;
35 : 83 : cfg->labelType = VOIDOID; /* we don't need node labels */
36 : 83 : cfg->canReturnData = true;
37 : 83 : cfg->longValuesOK = false;
38 : 83 : PG_RETURN_VOID();
39 : : }
40 : :
41 : : #define SPTEST(f, x, y) \
42 : : DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))
43 : :
44 : : /*
45 : : * Compare one coordinate of a point against that of the centroid
46 : : */
47 : : static int
48 : 24 : getAxisSide(float8 tst, float8 centroid)
49 : : {
50 : : /*
51 : : * Test FPeq first so that points on a centroid axis get the same result
52 : : * as getQuadrant.
53 : : */
54 [ + + ]: 24 : if (FPeq(tst, centroid))
55 : 4 : return 0;
56 [ - + ]: 20 : if (FPgt(tst, centroid))
57 : 0 : return 1;
58 [ + + ]: 20 : if (FPlt(tst, centroid))
59 : 8 : return -1;
60 : : /* fall back to exact comparison */
61 [ + - ]: 12 : if (tst > centroid)
62 : 12 : return 1;
63 [ # # ]: 0 : if (tst < centroid)
64 : 0 : return -1;
65 : :
66 [ # # ]: 0 : elog(ERROR, "getQuadrant: impossible case");
67 : : return 0;
68 : : }
69 : :
70 : : /*
71 : : * Determine which quadrant a point falls into, relative to the centroid.
72 : : *
73 : : * Quadrants are identified like this:
74 : : *
75 : : * 4 | 1
76 : : * ----+-----
77 : : * 3 | 2
78 : : *
79 : : * Points on one of the axes are taken to lie in the lowest-numbered
80 : : * adjacent quadrant.
81 : : */
82 : : static int16
83 : 11091813 : getQuadrant(Point *centroid, Point *tst)
84 : : {
85 : : int xside;
86 : : int yside;
87 : :
88 [ + + + + ]: 11323027 : if ((SPTEST(point_above, tst, centroid) ||
89 [ + + ]: 11100572 : SPTEST(point_horiz, tst, centroid)) &&
90 [ + + ]: 11000661 : (SPTEST(point_right, tst, centroid) ||
91 : 131303 : SPTEST(point_vert, tst, centroid)))
92 : 10744873 : return 1;
93 : :
94 [ + + + + ]: 569383 : if (SPTEST(point_below, tst, centroid) &&
95 [ - + ]: 422841 : (SPTEST(point_right, tst, centroid) ||
96 : 200398 : SPTEST(point_vert, tst, centroid)))
97 : 22045 : return 2;
98 : :
99 [ + + + + ]: 449392 : if ((SPTEST(point_below, tst, centroid) ||
100 [ + - ]: 325579 : SPTEST(point_horiz, tst, centroid)) &&
101 : 201082 : SPTEST(point_left, tst, centroid))
102 : 201082 : return 3;
103 : :
104 [ + + + - ]: 247614 : if (SPTEST(point_above, tst, centroid) &&
105 : 123801 : SPTEST(point_left, tst, centroid))
106 : 123801 : return 4;
107 : :
108 : : /*
109 : : * The fuzzy tests above can all fail on one axis, because FPeq() rounds a
110 : : * difference while FPlt() and FPgt() round a sum. Compare exactly only
111 : : * on that axis. On the other axis, keep the result of the fuzzy tests,
112 : : * because searches route by that result too.
113 : : */
114 : 12 : xside = getAxisSide(tst->x, centroid->x);
115 : 12 : yside = getAxisSide(tst->y, centroid->y);
116 : :
117 [ + + ]: 12 : if (xside >= 0)
118 [ + - ]: 4 : return (yside >= 0) ? 1 : 2;
119 [ - + ]: 8 : return (yside <= 0) ? 3 : 4;
120 : : }
121 : :
122 : : /* Returns bounding box of a given quadrant inside given bounding box */
123 : : static BOX *
124 : 2268 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
125 : : {
126 : 2268 : BOX *result = palloc_object(BOX);
127 : :
128 [ + + + + : 2268 : switch (quadrant)
- ]
129 : : {
130 : 560 : case 1:
131 : 560 : result->high = bbox->high;
132 : 560 : result->low = *centroid;
133 : 560 : break;
134 : 564 : case 2:
135 : 564 : result->high.x = bbox->high.x;
136 : 564 : result->high.y = centroid->y;
137 : 564 : result->low.x = centroid->x;
138 : 564 : result->low.y = bbox->low.y;
139 : 564 : break;
140 : 572 : case 3:
141 : 572 : result->high = *centroid;
142 : 572 : result->low = bbox->low;
143 : 572 : break;
144 : 572 : case 4:
145 : 572 : result->high.x = centroid->x;
146 : 572 : result->high.y = bbox->high.y;
147 : 572 : result->low.x = bbox->low.x;
148 : 572 : result->low.y = centroid->y;
149 : 572 : break;
150 : : }
151 : :
152 : 2268 : return result;
153 : : }
154 : :
155 : : Datum
156 : 10915092 : spg_quad_choose(PG_FUNCTION_ARGS)
157 : : {
158 : 10915092 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
159 : 10915092 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
160 : 10915092 : Point *inPoint = DatumGetPointP(in->datum),
161 : : *centroid;
162 : :
163 [ + + ]: 10915092 : if (in->allTheSame)
164 : : {
165 : 76732 : out->resultType = spgMatchNode;
166 : : /* nodeN will be set by core */
167 : 76732 : out->result.matchNode.levelAdd = 0;
168 : 76732 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
169 : 76732 : PG_RETURN_VOID();
170 : : }
171 : :
172 : : Assert(in->hasPrefix);
173 : 10838360 : centroid = DatumGetPointP(in->prefixDatum);
174 : :
175 : : Assert(in->nNodes == 4);
176 : :
177 : 10838360 : out->resultType = spgMatchNode;
178 : 10838360 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
179 : 10838360 : out->result.matchNode.levelAdd = 0;
180 : 10838360 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
181 : :
182 : 10838360 : PG_RETURN_VOID();
183 : : }
184 : :
185 : : #ifdef USE_MEDIAN
186 : : static int
187 : : x_cmp(const void *a, const void *b, void *arg)
188 : : {
189 : : Point *pa = *(Point *const *) a;
190 : : Point *pb = *(Point *const *) b;
191 : :
192 : : if (pa->x == pb->x)
193 : : return 0;
194 : : return (pa->x > pb->x) ? 1 : -1;
195 : : }
196 : :
197 : : static int
198 : : y_cmp(const void *a, const void *b, void *arg)
199 : : {
200 : : Point *pa = *(Point *const *) a;
201 : : Point *pb = *(Point *const *) b;
202 : :
203 : : if (pa->y == pb->y)
204 : : return 0;
205 : : return (pa->y > pb->y) ? 1 : -1;
206 : : }
207 : : #endif
208 : :
209 : : Datum
210 : 1795 : spg_quad_picksplit(PG_FUNCTION_ARGS)
211 : : {
212 : 1795 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
213 : 1795 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
214 : : int i;
215 : : Point *centroid;
216 : :
217 : : #ifdef USE_MEDIAN
218 : : /* Use the median values of x and y as the centroid point */
219 : : Point **sorted;
220 : :
221 : : sorted = palloc_array(Point *, in->nTuples);
222 : : for (i = 0; i < in->nTuples; i++)
223 : : sorted[i] = DatumGetPointP(in->datums[i]);
224 : :
225 : : centroid = palloc_object(Point);
226 : :
227 : : qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
228 : : centroid->x = sorted[in->nTuples >> 1]->x;
229 : : qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
230 : : centroid->y = sorted[in->nTuples >> 1]->y;
231 : : #else
232 : : /* Use the average values of x and y as the centroid point */
233 : 1795 : centroid = palloc0_object(Point);
234 : :
235 [ + + ]: 254872 : for (i = 0; i < in->nTuples; i++)
236 : : {
237 : 253077 : centroid->x += DatumGetPointP(in->datums[i])->x;
238 : 253077 : centroid->y += DatumGetPointP(in->datums[i])->y;
239 : : }
240 : :
241 : 1795 : centroid->x /= in->nTuples;
242 : 1795 : centroid->y /= in->nTuples;
243 : : #endif
244 : :
245 : 1795 : out->hasPrefix = true;
246 : 1795 : out->prefixDatum = PointPGetDatum(centroid);
247 : :
248 : 1795 : out->nNodes = 4;
249 : 1795 : out->nodeLabels = NULL; /* we don't need node labels */
250 : :
251 : 1795 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
252 : 1795 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
253 : :
254 [ + + ]: 254872 : for (i = 0; i < in->nTuples; i++)
255 : : {
256 : 253077 : Point *p = DatumGetPointP(in->datums[i]);
257 : 253077 : int quadrant = getQuadrant(centroid, p) - 1;
258 : :
259 : 253077 : out->leafTupleDatums[i] = PointPGetDatum(p);
260 : 253077 : out->mapTuplesToNodes[i] = quadrant;
261 : : }
262 : :
263 : 1795 : PG_RETURN_VOID();
264 : : }
265 : :
266 : :
267 : : Datum
268 : 3838 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
269 : : {
270 : 3838 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
271 : 3838 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
272 : : Point *centroid;
273 : : BOX infbbox;
274 : 3838 : BOX *bbox = NULL;
275 : : int which;
276 : : int i;
277 : :
278 : : Assert(in->hasPrefix);
279 : 3838 : centroid = DatumGetPointP(in->prefixDatum);
280 : :
281 : : /*
282 : : * When ordering scan keys are specified, we've to calculate distance for
283 : : * them. In order to do that, we need calculate bounding boxes for all
284 : : * children nodes. Calculation of those bounding boxes on non-zero level
285 : : * require knowledge of bounding box of upper node. So, we save bounding
286 : : * boxes to traversalValues.
287 : : */
288 [ + + ]: 3838 : if (in->norderbys > 0)
289 : : {
290 : 654 : out->distances = palloc_array(double *, in->nNodes);
291 : 654 : out->traversalValues = palloc_array(void *, in->nNodes);
292 : :
293 [ + + ]: 654 : if (in->level == 0)
294 : : {
295 : 16 : double inf = get_float8_infinity();
296 : :
297 : 16 : infbbox.high.x = inf;
298 : 16 : infbbox.high.y = inf;
299 : 16 : infbbox.low.x = -inf;
300 : 16 : infbbox.low.y = -inf;
301 : 16 : bbox = &infbbox;
302 : : }
303 : : else
304 : : {
305 : 638 : bbox = in->traversalValue;
306 : : Assert(bbox);
307 : : }
308 : : }
309 : :
310 [ + + ]: 3838 : if (in->allTheSame)
311 : : {
312 : : /* Report that all nodes should be visited */
313 : 390 : out->nNodes = in->nNodes;
314 : 390 : out->nodeNumbers = palloc_array(int, in->nNodes);
315 [ + + ]: 3510 : for (i = 0; i < in->nNodes; i++)
316 : : {
317 : 3120 : out->nodeNumbers[i] = i;
318 : :
319 [ + + ]: 3120 : if (in->norderbys > 0)
320 : : {
321 : 624 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
322 : :
323 : : /* Use parent quadrant box as traversalValue */
324 : 624 : BOX *quadrant = box_copy(bbox);
325 : :
326 : 624 : MemoryContextSwitchTo(oldCtx);
327 : :
328 : 624 : out->traversalValues[i] = quadrant;
329 : 624 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
330 : : in->orderbys, in->norderbys);
331 : : }
332 : : }
333 : 390 : PG_RETURN_VOID();
334 : : }
335 : :
336 : : Assert(in->nNodes == 4);
337 : :
338 : : /* "which" is a bitmask of quadrants that satisfy all constraints */
339 : 3448 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
340 : :
341 [ + + ]: 5256 : for (i = 0; i < in->nkeys; i++)
342 : : {
343 : 1808 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
344 : : BOX *boxQuery;
345 : :
346 [ + + + + : 1808 : switch (in->scankeys[i].sk_strategy)
+ + - ]
347 : : {
348 : 312 : case RTLeftStrategyNumber:
349 [ + + ]: 312 : if (SPTEST(point_right, centroid, query))
350 : 40 : which &= (1 << 3) | (1 << 4);
351 : 312 : break;
352 : 280 : case RTRightStrategyNumber:
353 [ + + ]: 280 : if (SPTEST(point_left, centroid, query))
354 : 8 : which &= (1 << 1) | (1 << 2);
355 : 280 : break;
356 : 24 : case RTSameStrategyNumber:
357 : 24 : which &= (1 << getQuadrant(centroid, query));
358 : 24 : break;
359 : 536 : case RTBelowStrategyNumber:
360 : : case RTOldBelowStrategyNumber:
361 [ + + ]: 536 : if (SPTEST(point_above, centroid, query))
362 : 224 : which &= (1 << 2) | (1 << 3);
363 : 536 : break;
364 : 528 : case RTAboveStrategyNumber:
365 : : case RTOldAboveStrategyNumber:
366 [ + + ]: 528 : if (SPTEST(point_below, centroid, query))
367 : 296 : which &= (1 << 1) | (1 << 4);
368 : 528 : break;
369 : 128 : case RTContainedByStrategyNumber:
370 : :
371 : : /*
372 : : * For this operator, the query is a box not a point. We
373 : : * cheat to the extent of assuming that DatumGetPointP won't
374 : : * do anything that would be bad for a pointer-to-box.
375 : : */
376 : 128 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
377 : :
378 [ + + ]: 128 : if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
379 : : PointerGetDatum(boxQuery),
380 : : PointerGetDatum(centroid))))
381 : : {
382 : : /* centroid is in box, so all quadrants are OK */
383 : : }
384 : : else
385 : : {
386 : : /* identify quadrant(s) containing all corners of box */
387 : : Point p;
388 : 88 : int r = 0;
389 : :
390 : 88 : p = boxQuery->low;
391 : 88 : r |= 1 << getQuadrant(centroid, &p);
392 : 88 : p.y = boxQuery->high.y;
393 : 88 : r |= 1 << getQuadrant(centroid, &p);
394 : 88 : p = boxQuery->high;
395 : 88 : r |= 1 << getQuadrant(centroid, &p);
396 : 88 : p.x = boxQuery->low.x;
397 : 88 : r |= 1 << getQuadrant(centroid, &p);
398 : :
399 : 88 : which &= r;
400 : : }
401 : 128 : break;
402 : 0 : default:
403 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
404 : : in->scankeys[i].sk_strategy);
405 : : break;
406 : : }
407 : :
408 [ - + ]: 1808 : if (which == 0)
409 : 0 : break; /* no need to consider remaining conditions */
410 : : }
411 : :
412 : 3448 : out->levelAdds = palloc_array(int, 4);
413 [ + + ]: 17240 : for (i = 0; i < 4; ++i)
414 : 13792 : out->levelAdds[i] = 1;
415 : :
416 : : /* We must descend into the quadrant(s) identified by which */
417 : 3448 : out->nodeNumbers = palloc_array(int, 4);
418 : 3448 : out->nNodes = 0;
419 : :
420 [ + + ]: 17240 : for (i = 1; i <= 4; i++)
421 : : {
422 [ + + ]: 13792 : if (which & (1 << i))
423 : : {
424 : 12384 : out->nodeNumbers[out->nNodes] = i - 1;
425 : :
426 [ + + ]: 12384 : if (in->norderbys > 0)
427 : : {
428 : 2268 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
429 : 2268 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
430 : :
431 : 2268 : MemoryContextSwitchTo(oldCtx);
432 : :
433 : 2268 : out->traversalValues[out->nNodes] = quadrant;
434 : :
435 : 2268 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
436 : : in->orderbys, in->norderbys);
437 : : }
438 : :
439 : 12384 : out->nNodes++;
440 : : }
441 : : }
442 : :
443 : 3448 : PG_RETURN_VOID();
444 : : }
445 : :
446 : :
447 : : Datum
448 : 820787 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
449 : : {
450 : 820787 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
451 : 820787 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
452 : 820787 : Point *datum = DatumGetPointP(in->leafDatum);
453 : : bool res;
454 : : int i;
455 : :
456 : : /* all tests are exact */
457 : 820787 : out->recheck = false;
458 : :
459 : : /* leafDatum is what it is... */
460 : 820787 : out->leafValue = in->leafDatum;
461 : :
462 : : /* Perform the required comparison(s) */
463 : 820787 : res = true;
464 [ + + ]: 1215055 : for (i = 0; i < in->nkeys; i++)
465 : : {
466 : 467008 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
467 : :
468 [ + + + + : 467008 : switch (in->scankeys[i].sk_strategy)
+ + - ]
469 : : {
470 : 101272 : case RTLeftStrategyNumber:
471 : 101272 : res = SPTEST(point_left, datum, query);
472 : 101272 : break;
473 : 82168 : case RTRightStrategyNumber:
474 : 82168 : res = SPTEST(point_right, datum, query);
475 : 82168 : break;
476 : 1360 : case RTSameStrategyNumber:
477 : 1360 : res = SPTEST(point_eq, datum, query);
478 : 1360 : break;
479 : 116232 : case RTBelowStrategyNumber:
480 : : case RTOldBelowStrategyNumber:
481 : 116232 : res = SPTEST(point_below, datum, query);
482 : 116232 : break;
483 : 115704 : case RTAboveStrategyNumber:
484 : : case RTOldAboveStrategyNumber:
485 : 115704 : res = SPTEST(point_above, datum, query);
486 : 115704 : break;
487 : 50272 : case RTContainedByStrategyNumber:
488 : :
489 : : /*
490 : : * For this operator, the query is a box not a point. We
491 : : * cheat to the extent of assuming that DatumGetPointP won't
492 : : * do anything that would be bad for a pointer-to-box.
493 : : */
494 : 50272 : res = SPTEST(box_contain_pt, query, datum);
495 : 50272 : break;
496 : 0 : default:
497 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
498 : : in->scankeys[i].sk_strategy);
499 : : break;
500 : : }
501 : :
502 [ + + ]: 467008 : if (!res)
503 : 72740 : break;
504 : : }
505 : :
506 [ + + + + ]: 820787 : if (res && in->norderbys > 0)
507 : : /* ok, it passes -> let's compute the distances */
508 : 186235 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
509 : : in->orderbys, in->norderbys);
510 : :
511 : 820787 : PG_RETURN_BOOL(res);
512 : : }
|
