Age Owner Branch data TLA 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
5202 tgl@sss.pgh.pa.us 27 :CBC 55 : spg_quad_config(PG_FUNCTION_ARGS)
28 : : {
29 : : #ifdef NOT_USED
30 : : spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
31 : : #endif
32 : 55 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
33 : :
34 : 55 : cfg->prefixType = POINTOID;
35 : 55 : cfg->labelType = VOIDOID; /* we don't need node labels */
5200 36 : 55 : cfg->canReturnData = true;
5202 37 : 55 : cfg->longValuesOK = false;
38 : 55 : PG_RETURN_VOID();
39 : : }
40 : :
41 : : #define SPTEST(f, x, y) \
42 : : DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))
43 : :
44 : : /*
45 : : * Determine which quadrant a point falls into, relative to the centroid.
46 : : *
47 : : * Quadrants are identified like this:
48 : : *
49 : : * 4 | 1
50 : : * ----+-----
51 : : * 3 | 2
52 : : *
53 : : * Points on one of the axes are taken to lie in the lowest-numbered
54 : : * adjacent quadrant.
55 : : */
56 : : static int16
57 : 8323544 : getQuadrant(Point *centroid, Point *tst)
58 : : {
59 [ + + + + ]: 8495764 : if ((SPTEST(point_above, tst, centroid) ||
60 [ + + ]: 8328392 : SPTEST(point_horiz, tst, centroid)) &&
61 [ + + ]: 8254534 : (SPTEST(point_right, tst, centroid) ||
62 : 98362 : SPTEST(point_vert, tst, centroid)))
63 : 8062659 : return 1;
64 : :
65 [ + + + + ]: 428257 : if (SPTEST(point_below, tst, centroid) &&
66 [ - + ]: 317492 : (SPTEST(point_right, tst, centroid) ||
67 : 150120 : SPTEST(point_vert, tst, centroid)))
68 : 17252 : return 2;
69 : :
70 [ + + - + ]: 337146 : if ((SPTEST(point_below, tst, centroid) ||
71 [ + - ]: 243633 : SPTEST(point_horiz, tst, centroid)) &&
72 : 150120 : SPTEST(point_left, tst, centroid))
73 : 150120 : return 3;
74 : :
75 [ + - + - ]: 187026 : if (SPTEST(point_above, tst, centroid) &&
76 : 93513 : SPTEST(point_left, tst, centroid))
77 : 93513 : return 4;
78 : :
5202 tgl@sss.pgh.pa.us 79 [ # # ]:UBC 0 : elog(ERROR, "getQuadrant: impossible case");
80 : : return 0;
81 : : }
82 : :
83 : : /* Returns bounding box of a given quadrant inside given bounding box */
84 : : static BOX *
2734 akorotkov@postgresql 85 :CBC 1701 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
86 : : {
95 michael@paquier.xyz 87 :GNC 1701 : BOX *result = palloc_object(BOX);
88 : :
2734 akorotkov@postgresql 89 [ + + + + :CBC 1701 : switch (quadrant)
- ]
90 : : {
91 : 420 : case 1:
92 : 420 : result->high = bbox->high;
93 : 420 : result->low = *centroid;
94 : 420 : break;
95 : 423 : case 2:
96 : 423 : result->high.x = bbox->high.x;
97 : 423 : result->high.y = centroid->y;
98 : 423 : result->low.x = centroid->x;
99 : 423 : result->low.y = bbox->low.y;
100 : 423 : break;
101 : 429 : case 3:
102 : 429 : result->high = *centroid;
103 : 429 : result->low = bbox->low;
104 : 429 : break;
105 : 429 : case 4:
106 : 429 : result->high.x = centroid->x;
107 : 429 : result->high.y = bbox->high.y;
108 : 429 : result->low.x = bbox->low.x;
109 : 429 : result->low.y = centroid->y;
110 : 429 : break;
111 : : }
112 : :
113 : 1701 : return result;
114 : : }
115 : :
116 : : Datum
5202 tgl@sss.pgh.pa.us 117 : 8189900 : spg_quad_choose(PG_FUNCTION_ARGS)
118 : : {
119 : 8189900 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
120 : 8189900 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
121 : 8189900 : Point *inPoint = DatumGetPointP(in->datum),
122 : : *centroid;
123 : :
124 [ + + ]: 8189900 : if (in->allTheSame)
125 : : {
126 : 54688 : out->resultType = spgMatchNode;
127 : : /* nodeN will be set by core */
128 : 54688 : out->result.matchNode.levelAdd = 0;
129 : 54688 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
130 : 54688 : PG_RETURN_VOID();
131 : : }
132 : :
133 [ - + ]: 8135212 : Assert(in->hasPrefix);
134 : 8135212 : centroid = DatumGetPointP(in->prefixDatum);
135 : :
136 [ - + ]: 8135212 : Assert(in->nNodes == 4);
137 : :
138 : 8135212 : out->resultType = spgMatchNode;
139 : 8135212 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
140 : 8135212 : out->result.matchNode.levelAdd = 0;
141 : 8135212 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
142 : :
143 : 8135212 : PG_RETURN_VOID();
144 : : }
145 : :
146 : : #ifdef USE_MEDIAN
147 : : static int
148 : : x_cmp(const void *a, const void *b, void *arg)
149 : : {
150 : : Point *pa = *(Point *const *) a;
151 : : Point *pb = *(Point *const *) b;
152 : :
153 : : if (pa->x == pb->x)
154 : : return 0;
155 : : return (pa->x > pb->x) ? 1 : -1;
156 : : }
157 : :
158 : : static int
159 : : y_cmp(const void *a, const void *b, void *arg)
160 : : {
161 : : Point *pa = *(Point *const *) a;
162 : : Point *pb = *(Point *const *) b;
163 : :
164 : : if (pa->y == pb->y)
165 : : return 0;
166 : : return (pa->y > pb->y) ? 1 : -1;
167 : : }
168 : : #endif
169 : :
170 : : Datum
171 : 1332 : spg_quad_picksplit(PG_FUNCTION_ARGS)
172 : : {
173 : 1332 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
174 : 1332 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
175 : : int i;
176 : : Point *centroid;
177 : :
178 : : #ifdef USE_MEDIAN
179 : : /* Use the median values of x and y as the centroid point */
180 : : Point **sorted;
181 : :
182 : : sorted = palloc_array(Point *, in->nTuples);
183 : : for (i = 0; i < in->nTuples; i++)
184 : : sorted[i] = DatumGetPointP(in->datums[i]);
185 : :
186 : : centroid = palloc_object(Point);
187 : :
188 : : qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
189 : : centroid->x = sorted[in->nTuples >> 1]->x;
190 : : qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
191 : : centroid->y = sorted[in->nTuples >> 1]->y;
192 : : #else
193 : : /* Use the average values of x and y as the centroid point */
95 michael@paquier.xyz 194 :GNC 1332 : centroid = palloc0_object(Point);
195 : :
5202 tgl@sss.pgh.pa.us 196 [ + + ]:CBC 189406 : for (i = 0; i < in->nTuples; i++)
197 : : {
198 : 188074 : centroid->x += DatumGetPointP(in->datums[i])->x;
199 : 188074 : centroid->y += DatumGetPointP(in->datums[i])->y;
200 : : }
201 : :
202 : 1332 : centroid->x /= in->nTuples;
203 : 1332 : centroid->y /= in->nTuples;
204 : : #endif
205 : :
206 : 1332 : out->hasPrefix = true;
207 : 1332 : out->prefixDatum = PointPGetDatum(centroid);
208 : :
209 : 1332 : out->nNodes = 4;
210 : 1332 : out->nodeLabels = NULL; /* we don't need node labels */
211 : :
95 michael@paquier.xyz 212 :GNC 1332 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
213 : 1332 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
214 : :
5202 tgl@sss.pgh.pa.us 215 [ + + ]:CBC 189406 : for (i = 0; i < in->nTuples; i++)
216 : : {
217 : 188074 : Point *p = DatumGetPointP(in->datums[i]);
218 : 188074 : int quadrant = getQuadrant(centroid, p) - 1;
219 : :
220 : 188074 : out->leafTupleDatums[i] = PointPGetDatum(p);
221 : 188074 : out->mapTuplesToNodes[i] = quadrant;
222 : : }
223 : :
224 : 1332 : PG_RETURN_VOID();
225 : : }
226 : :
227 : :
228 : : Datum
229 : 2850 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
230 : : {
231 : 2850 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
232 : 2850 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
233 : : Point *centroid;
234 : : BOX infbbox;
2734 akorotkov@postgresql 235 : 2850 : BOX *bbox = NULL;
236 : : int which;
237 : : int i;
238 : :
5202 tgl@sss.pgh.pa.us 239 [ - + ]: 2850 : Assert(in->hasPrefix);
240 : 2850 : centroid = DatumGetPointP(in->prefixDatum);
241 : :
242 : : /*
243 : : * When ordering scan keys are specified, we've to calculate distance for
244 : : * them. In order to do that, we need calculate bounding boxes for all
245 : : * children nodes. Calculation of those bounding boxes on non-zero level
246 : : * require knowledge of bounding box of upper node. So, we save bounding
247 : : * boxes to traversalValues.
248 : : */
2734 akorotkov@postgresql 249 [ + + ]: 2850 : if (in->norderbys > 0)
250 : : {
95 michael@paquier.xyz 251 :GNC 486 : out->distances = palloc_array(double *, in->nNodes);
252 : 486 : out->traversalValues = palloc_array(void *, in->nNodes);
253 : :
2734 akorotkov@postgresql 254 [ + + ]:CBC 486 : if (in->level == 0)
255 : : {
256 : 12 : double inf = get_float8_infinity();
257 : :
258 : 12 : infbbox.high.x = inf;
259 : 12 : infbbox.high.y = inf;
260 : 12 : infbbox.low.x = -inf;
261 : 12 : infbbox.low.y = -inf;
262 : 12 : bbox = &infbbox;
263 : : }
264 : : else
265 : : {
266 : 474 : bbox = in->traversalValue;
267 [ - + ]: 474 : Assert(bbox);
268 : : }
269 : : }
270 : :
5202 tgl@sss.pgh.pa.us 271 [ + + ]: 2850 : if (in->allTheSame)
272 : : {
273 : : /* Report that all nodes should be visited */
274 : 270 : out->nNodes = in->nNodes;
95 michael@paquier.xyz 275 :GNC 270 : out->nodeNumbers = palloc_array(int, in->nNodes);
5202 tgl@sss.pgh.pa.us 276 [ + + ]:CBC 2430 : for (i = 0; i < in->nNodes; i++)
277 : : {
278 : 2160 : out->nodeNumbers[i] = i;
279 : :
2734 akorotkov@postgresql 280 [ + + ]: 2160 : if (in->norderbys > 0)
281 : : {
2726 282 : 432 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
283 : :
284 : : /* Use parent quadrant box as traversalValue */
2734 285 : 432 : BOX *quadrant = box_copy(bbox);
286 : :
287 : 432 : MemoryContextSwitchTo(oldCtx);
288 : :
289 : 432 : out->traversalValues[i] = quadrant;
2726 290 : 432 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
291 : : in->orderbys, in->norderbys);
292 : : }
293 : : }
5202 tgl@sss.pgh.pa.us 294 : 270 : PG_RETURN_VOID();
295 : : }
296 : :
297 [ - + ]: 2580 : Assert(in->nNodes == 4);
298 : :
299 : : /* "which" is a bitmask of quadrants that satisfy all constraints */
5118 300 : 2580 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
301 : :
302 [ + + ]: 3930 : for (i = 0; i < in->nkeys; i++)
303 : : {
304 : 1350 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
305 : : BOX *boxQuery;
306 : :
307 [ + + + + : 1350 : switch (in->scankeys[i].sk_strategy)
+ + - ]
308 : : {
309 : 234 : case RTLeftStrategyNumber:
310 [ + + ]: 234 : if (SPTEST(point_right, centroid, query))
311 : 30 : which &= (1 << 3) | (1 << 4);
312 : 234 : break;
313 : 210 : case RTRightStrategyNumber:
314 [ + + ]: 210 : if (SPTEST(point_left, centroid, query))
315 : 6 : which &= (1 << 1) | (1 << 2);
316 : 210 : break;
317 : 18 : case RTSameStrategyNumber:
318 : 18 : which &= (1 << getQuadrant(centroid, query));
319 : 18 : break;
320 : 402 : case RTBelowStrategyNumber:
321 : : case RTOldBelowStrategyNumber:
322 [ + + ]: 402 : if (SPTEST(point_above, centroid, query))
323 : 168 : which &= (1 << 2) | (1 << 3);
324 : 402 : break;
325 : 396 : case RTAboveStrategyNumber:
326 : : case RTOldAboveStrategyNumber:
327 [ + + ]: 396 : if (SPTEST(point_below, centroid, query))
328 : 222 : which &= (1 << 1) | (1 << 4);
329 : 396 : break;
330 : 90 : case RTContainedByStrategyNumber:
331 : :
332 : : /*
333 : : * For this operator, the query is a box not a point. We
334 : : * cheat to the extent of assuming that DatumGetPointP won't
335 : : * do anything that would be bad for a pointer-to-box.
336 : : */
337 : 90 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
338 : :
339 [ + + ]: 90 : if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
340 : : PointerGetDatum(boxQuery),
341 : : PointerGetDatum(centroid))))
342 : : {
343 : : /* centroid is in box, so all quadrants are OK */
344 : : }
345 : : else
346 : : {
347 : : /* identify quadrant(s) containing all corners of box */
348 : : Point p;
349 : 60 : int r = 0;
350 : :
351 : 60 : p = boxQuery->low;
352 : 60 : r |= 1 << getQuadrant(centroid, &p);
353 : 60 : p.y = boxQuery->high.y;
354 : 60 : r |= 1 << getQuadrant(centroid, &p);
355 : 60 : p = boxQuery->high;
356 : 60 : r |= 1 << getQuadrant(centroid, &p);
357 : 60 : p.x = boxQuery->low.x;
358 : 60 : r |= 1 << getQuadrant(centroid, &p);
359 : :
360 : 60 : which &= r;
361 : : }
362 : 90 : break;
5118 tgl@sss.pgh.pa.us 363 :UBC 0 : default:
364 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
365 : : in->scankeys[i].sk_strategy);
366 : : break;
367 : : }
368 : :
5118 tgl@sss.pgh.pa.us 369 [ - + ]:CBC 1350 : if (which == 0)
5118 tgl@sss.pgh.pa.us 370 :UBC 0 : break; /* no need to consider remaining conditions */
371 : : }
372 : :
95 michael@paquier.xyz 373 :GNC 2580 : out->levelAdds = palloc_array(int, 4);
2734 akorotkov@postgresql 374 [ + + ]:CBC 12900 : for (i = 0; i < 4; ++i)
375 : 10320 : out->levelAdds[i] = 1;
376 : :
377 : : /* We must descend into the quadrant(s) identified by which */
95 michael@paquier.xyz 378 :GNC 2580 : out->nodeNumbers = palloc_array(int, 4);
5118 tgl@sss.pgh.pa.us 379 :CBC 2580 : out->nNodes = 0;
380 : :
381 [ + + ]: 12900 : for (i = 1; i <= 4; i++)
382 : : {
383 [ + + ]: 10320 : if (which & (1 << i))
384 : : {
2734 akorotkov@postgresql 385 : 9279 : out->nodeNumbers[out->nNodes] = i - 1;
386 : :
387 [ + + ]: 9279 : if (in->norderbys > 0)
388 : : {
2726 389 : 1701 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
2734 390 : 1701 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
391 : :
392 : 1701 : MemoryContextSwitchTo(oldCtx);
393 : :
394 : 1701 : out->traversalValues[out->nNodes] = quadrant;
395 : :
2726 396 : 1701 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
397 : : in->orderbys, in->norderbys);
398 : : }
399 : :
2734 400 : 9279 : out->nNodes++;
401 : : }
402 : : }
403 : :
5202 tgl@sss.pgh.pa.us 404 : 2580 : PG_RETURN_VOID();
405 : : }
406 : :
407 : :
408 : : Datum
409 : 615411 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
410 : : {
411 : 615411 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
412 : 615411 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
413 : 615411 : Point *datum = DatumGetPointP(in->leafDatum);
414 : : bool res;
415 : : int i;
416 : :
417 : : /* all tests are exact */
418 : 615411 : out->recheck = false;
419 : :
420 : : /* leafDatum is what it is... */
5200 421 : 615411 : out->leafValue = in->leafDatum;
422 : :
423 : : /* Perform the required comparison(s) */
5118 424 : 615411 : res = true;
425 [ + + ]: 911109 : for (i = 0; i < in->nkeys; i++)
426 : : {
427 : 350082 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
428 : :
429 [ + + + + : 350082 : switch (in->scankeys[i].sk_strategy)
+ + - ]
430 : : {
431 : 75954 : case RTLeftStrategyNumber:
432 : 75954 : res = SPTEST(point_left, datum, query);
433 : 75954 : break;
434 : 61626 : case RTRightStrategyNumber:
435 : 61626 : res = SPTEST(point_right, datum, query);
436 : 61626 : break;
437 : 1020 : case RTSameStrategyNumber:
438 : 1020 : res = SPTEST(point_eq, datum, query);
439 : 1020 : break;
440 : 87174 : case RTBelowStrategyNumber:
441 : : case RTOldBelowStrategyNumber:
442 : 87174 : res = SPTEST(point_below, datum, query);
443 : 87174 : break;
444 : 86778 : case RTAboveStrategyNumber:
445 : : case RTOldAboveStrategyNumber:
446 : 86778 : res = SPTEST(point_above, datum, query);
447 : 86778 : break;
448 : 37530 : case RTContainedByStrategyNumber:
449 : :
450 : : /*
451 : : * For this operator, the query is a box not a point. We
452 : : * cheat to the extent of assuming that DatumGetPointP won't
453 : : * do anything that would be bad for a pointer-to-box.
454 : : */
455 : 37530 : res = SPTEST(box_contain_pt, query, datum);
456 : 37530 : break;
5118 tgl@sss.pgh.pa.us 457 :UBC 0 : default:
458 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
459 : : in->scankeys[i].sk_strategy);
460 : : break;
461 : : }
462 : :
5118 tgl@sss.pgh.pa.us 463 [ + + ]:CBC 350082 : if (!res)
5202 464 : 54384 : break;
465 : : }
466 : :
2734 akorotkov@postgresql 467 [ + + + + ]: 615411 : if (res && in->norderbys > 0)
468 : : /* ok, it passes -> let's compute the distances */
2726 469 : 139671 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
470 : : in->orderbys, in->norderbys);
471 : :
5202 tgl@sss.pgh.pa.us 472 : 615411 : PG_RETURN_BOOL(res);
473 : : }
|
