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