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 : 72 : spg_quad_config(PG_FUNCTION_ARGS)
28 : : {
29 : : #ifdef NOT_USED
30 : : spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
31 : : #endif
32 : 72 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
33 : :
34 : 72 : cfg->prefixType = POINTOID;
35 : 72 : cfg->labelType = VOIDOID; /* we don't need node labels */
36 : 72 : cfg->canReturnData = true;
37 : 72 : cfg->longValuesOK = false;
38 : 72 : 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 : 11102079 : getQuadrant(Point *centroid, Point *tst)
58 : : {
59 [ + + + + ]: 11330638 : if ((SPTEST(point_above, tst, centroid) ||
60 [ + + ]: 11108391 : SPTEST(point_horiz, tst, centroid)) &&
61 [ + + ]: 11011539 : (SPTEST(point_right, tst, centroid) ||
62 : 131707 : SPTEST(point_vert, tst, centroid)))
63 : 10754439 : return 1;
64 : :
65 [ + + + + ]: 569887 : if (SPTEST(point_below, tst, centroid) &&
66 [ - + ]: 420935 : (SPTEST(point_right, tst, centroid) ||
67 : 198688 : SPTEST(point_vert, tst, centroid)))
68 : 23559 : return 2;
69 : :
70 [ + + - + ]: 449474 : if ((SPTEST(point_below, tst, centroid) ||
71 [ + - ]: 324081 : SPTEST(point_horiz, tst, centroid)) &&
72 : 198688 : SPTEST(point_left, tst, centroid))
73 : 198688 : return 3;
74 : :
75 [ + - + - ]: 250786 : if (SPTEST(point_above, tst, centroid) &&
76 : 125393 : SPTEST(point_left, tst, centroid))
77 : 125393 : return 4;
78 : :
79 [ # # ]: 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 *
85 : 2268 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
86 : : {
87 : 2268 : BOX *result = palloc_object(BOX);
88 : :
89 [ + + + + : 2268 : switch (quadrant)
- ]
90 : : {
91 : 560 : case 1:
92 : 560 : result->high = bbox->high;
93 : 560 : result->low = *centroid;
94 : 560 : break;
95 : 564 : case 2:
96 : 564 : result->high.x = bbox->high.x;
97 : 564 : result->high.y = centroid->y;
98 : 564 : result->low.x = centroid->x;
99 : 564 : result->low.y = bbox->low.y;
100 : 564 : break;
101 : 572 : case 3:
102 : 572 : result->high = *centroid;
103 : 572 : result->low = bbox->low;
104 : 572 : break;
105 : 572 : case 4:
106 : 572 : result->high.x = centroid->x;
107 : 572 : result->high.y = bbox->high.y;
108 : 572 : result->low.x = bbox->low.x;
109 : 572 : result->low.y = centroid->y;
110 : 572 : break;
111 : : }
112 : :
113 : 2268 : return result;
114 : : }
115 : :
116 : : Datum
117 : 10925127 : spg_quad_choose(PG_FUNCTION_ARGS)
118 : : {
119 : 10925127 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
120 : 10925127 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
121 : 10925127 : Point *inPoint = DatumGetPointP(in->datum),
122 : : *centroid;
123 : :
124 [ + + ]: 10925127 : if (in->allTheSame)
125 : : {
126 : 71640 : out->resultType = spgMatchNode;
127 : : /* nodeN will be set by core */
128 : 71640 : out->result.matchNode.levelAdd = 0;
129 : 71640 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
130 : 71640 : PG_RETURN_VOID();
131 : : }
132 : :
133 : : Assert(in->hasPrefix);
134 : 10853487 : centroid = DatumGetPointP(in->prefixDatum);
135 : :
136 : : Assert(in->nNodes == 4);
137 : :
138 : 10853487 : out->resultType = spgMatchNode;
139 : 10853487 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
140 : 10853487 : out->result.matchNode.levelAdd = 0;
141 : 10853487 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
142 : :
143 : 10853487 : 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 : 1767 : spg_quad_picksplit(PG_FUNCTION_ARGS)
172 : : {
173 : 1767 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
174 : 1767 : 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 */
194 : 1767 : centroid = palloc0_object(Point);
195 : :
196 [ + + ]: 250015 : for (i = 0; i < in->nTuples; i++)
197 : : {
198 : 248248 : centroid->x += DatumGetPointP(in->datums[i])->x;
199 : 248248 : centroid->y += DatumGetPointP(in->datums[i])->y;
200 : : }
201 : :
202 : 1767 : centroid->x /= in->nTuples;
203 : 1767 : centroid->y /= in->nTuples;
204 : : #endif
205 : :
206 : 1767 : out->hasPrefix = true;
207 : 1767 : out->prefixDatum = PointPGetDatum(centroid);
208 : :
209 : 1767 : out->nNodes = 4;
210 : 1767 : out->nodeLabels = NULL; /* we don't need node labels */
211 : :
212 : 1767 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
213 : 1767 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
214 : :
215 [ + + ]: 250015 : for (i = 0; i < in->nTuples; i++)
216 : : {
217 : 248248 : Point *p = DatumGetPointP(in->datums[i]);
218 : 248248 : int quadrant = getQuadrant(centroid, p) - 1;
219 : :
220 : 248248 : out->leafTupleDatums[i] = PointPGetDatum(p);
221 : 248248 : out->mapTuplesToNodes[i] = quadrant;
222 : : }
223 : :
224 : 1767 : PG_RETURN_VOID();
225 : : }
226 : :
227 : :
228 : : Datum
229 : 3800 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
230 : : {
231 : 3800 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
232 : 3800 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
233 : : Point *centroid;
234 : : BOX infbbox;
235 : 3800 : BOX *bbox = NULL;
236 : : int which;
237 : : int i;
238 : :
239 : : Assert(in->hasPrefix);
240 : 3800 : 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 : : */
249 [ + + ]: 3800 : if (in->norderbys > 0)
250 : : {
251 : 648 : out->distances = palloc_array(double *, in->nNodes);
252 : 648 : out->traversalValues = palloc_array(void *, in->nNodes);
253 : :
254 [ + + ]: 648 : if (in->level == 0)
255 : : {
256 : 16 : double inf = get_float8_infinity();
257 : :
258 : 16 : infbbox.high.x = inf;
259 : 16 : infbbox.high.y = inf;
260 : 16 : infbbox.low.x = -inf;
261 : 16 : infbbox.low.y = -inf;
262 : 16 : bbox = &infbbox;
263 : : }
264 : : else
265 : : {
266 : 632 : bbox = in->traversalValue;
267 : : Assert(bbox);
268 : : }
269 : : }
270 : :
271 [ + + ]: 3800 : if (in->allTheSame)
272 : : {
273 : : /* Report that all nodes should be visited */
274 : 360 : out->nNodes = in->nNodes;
275 : 360 : out->nodeNumbers = palloc_array(int, in->nNodes);
276 [ + + ]: 3240 : for (i = 0; i < in->nNodes; i++)
277 : : {
278 : 2880 : out->nodeNumbers[i] = i;
279 : :
280 [ + + ]: 2880 : if (in->norderbys > 0)
281 : : {
282 : 576 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
283 : :
284 : : /* Use parent quadrant box as traversalValue */
285 : 576 : BOX *quadrant = box_copy(bbox);
286 : :
287 : 576 : MemoryContextSwitchTo(oldCtx);
288 : :
289 : 576 : out->traversalValues[i] = quadrant;
290 : 576 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
291 : : in->orderbys, in->norderbys);
292 : : }
293 : : }
294 : 360 : PG_RETURN_VOID();
295 : : }
296 : :
297 : : Assert(in->nNodes == 4);
298 : :
299 : : /* "which" is a bitmask of quadrants that satisfy all constraints */
300 : 3440 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
301 : :
302 [ + + ]: 5240 : for (i = 0; i < in->nkeys; i++)
303 : : {
304 : 1800 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
305 : : BOX *boxQuery;
306 : :
307 [ + + + + : 1800 : switch (in->scankeys[i].sk_strategy)
+ + - ]
308 : : {
309 : 312 : case RTLeftStrategyNumber:
310 [ + + ]: 312 : if (SPTEST(point_right, centroid, query))
311 : 40 : which &= (1 << 3) | (1 << 4);
312 : 312 : break;
313 : 280 : case RTRightStrategyNumber:
314 [ + + ]: 280 : if (SPTEST(point_left, centroid, query))
315 : 8 : which &= (1 << 1) | (1 << 2);
316 : 280 : break;
317 : 24 : case RTSameStrategyNumber:
318 : 24 : which &= (1 << getQuadrant(centroid, query));
319 : 24 : break;
320 : 536 : case RTBelowStrategyNumber:
321 : : case RTOldBelowStrategyNumber:
322 [ + + ]: 536 : if (SPTEST(point_above, centroid, query))
323 : 224 : which &= (1 << 2) | (1 << 3);
324 : 536 : break;
325 : 528 : case RTAboveStrategyNumber:
326 : : case RTOldAboveStrategyNumber:
327 [ + + ]: 528 : if (SPTEST(point_below, centroid, query))
328 : 296 : which &= (1 << 1) | (1 << 4);
329 : 528 : break;
330 : 120 : 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 : 120 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
338 : :
339 [ + + ]: 120 : 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 : 80 : int r = 0;
350 : :
351 : 80 : p = boxQuery->low;
352 : 80 : r |= 1 << getQuadrant(centroid, &p);
353 : 80 : p.y = boxQuery->high.y;
354 : 80 : r |= 1 << getQuadrant(centroid, &p);
355 : 80 : p = boxQuery->high;
356 : 80 : r |= 1 << getQuadrant(centroid, &p);
357 : 80 : p.x = boxQuery->low.x;
358 : 80 : r |= 1 << getQuadrant(centroid, &p);
359 : :
360 : 80 : which &= r;
361 : : }
362 : 120 : break;
363 : 0 : default:
364 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
365 : : in->scankeys[i].sk_strategy);
366 : : break;
367 : : }
368 : :
369 [ - + ]: 1800 : if (which == 0)
370 : 0 : break; /* no need to consider remaining conditions */
371 : : }
372 : :
373 : 3440 : out->levelAdds = palloc_array(int, 4);
374 [ + + ]: 17200 : for (i = 0; i < 4; ++i)
375 : 13760 : out->levelAdds[i] = 1;
376 : :
377 : : /* We must descend into the quadrant(s) identified by which */
378 : 3440 : out->nodeNumbers = palloc_array(int, 4);
379 : 3440 : out->nNodes = 0;
380 : :
381 [ + + ]: 17200 : for (i = 1; i <= 4; i++)
382 : : {
383 [ + + ]: 13760 : if (which & (1 << i))
384 : : {
385 : 12372 : out->nodeNumbers[out->nNodes] = i - 1;
386 : :
387 [ + + ]: 12372 : if (in->norderbys > 0)
388 : : {
389 : 2268 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
390 : 2268 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
391 : :
392 : 2268 : MemoryContextSwitchTo(oldCtx);
393 : :
394 : 2268 : out->traversalValues[out->nNodes] = quadrant;
395 : :
396 : 2268 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
397 : : in->orderbys, in->norderbys);
398 : : }
399 : :
400 : 12372 : out->nNodes++;
401 : : }
402 : : }
403 : :
404 : 3440 : PG_RETURN_VOID();
405 : : }
406 : :
407 : :
408 : : Datum
409 : 820538 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
410 : : {
411 : 820538 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
412 : 820538 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
413 : 820538 : Point *datum = DatumGetPointP(in->leafDatum);
414 : : bool res;
415 : : int i;
416 : :
417 : : /* all tests are exact */
418 : 820538 : out->recheck = false;
419 : :
420 : : /* leafDatum is what it is... */
421 : 820538 : out->leafValue = in->leafDatum;
422 : :
423 : : /* Perform the required comparison(s) */
424 : 820538 : res = true;
425 [ + + ]: 1214802 : for (i = 0; i < in->nkeys; i++)
426 : : {
427 : 466776 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
428 : :
429 [ + + + + : 466776 : switch (in->scankeys[i].sk_strategy)
+ + - ]
430 : : {
431 : 101272 : case RTLeftStrategyNumber:
432 : 101272 : res = SPTEST(point_left, datum, query);
433 : 101272 : break;
434 : 82168 : case RTRightStrategyNumber:
435 : 82168 : res = SPTEST(point_right, datum, query);
436 : 82168 : break;
437 : 1360 : case RTSameStrategyNumber:
438 : 1360 : res = SPTEST(point_eq, datum, query);
439 : 1360 : break;
440 : 116232 : case RTBelowStrategyNumber:
441 : : case RTOldBelowStrategyNumber:
442 : 116232 : res = SPTEST(point_below, datum, query);
443 : 116232 : break;
444 : 115704 : case RTAboveStrategyNumber:
445 : : case RTOldAboveStrategyNumber:
446 : 115704 : res = SPTEST(point_above, datum, query);
447 : 115704 : break;
448 : 50040 : 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 : 50040 : res = SPTEST(box_contain_pt, query, datum);
456 : 50040 : break;
457 : 0 : default:
458 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
459 : : in->scankeys[i].sk_strategy);
460 : : break;
461 : : }
462 : :
463 [ + + ]: 466776 : if (!res)
464 : 72512 : break;
465 : : }
466 : :
467 [ + + + + ]: 820538 : if (res && in->norderbys > 0)
468 : : /* ok, it passes -> let's compute the distances */
469 : 186218 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
470 : : in->orderbys, in->norderbys);
471 : :
472 : 820538 : PG_RETURN_BOOL(res);
473 : : }
|
