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 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 */
36 55 : cfg->canReturnData = true;
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 8312208 : getQuadrant(Point *centroid, Point *tst)
58 : {
59 8483870 : if ((SPTEST(point_above, tst, centroid) ||
60 8317777 : SPTEST(point_horiz, tst, centroid)) &&
61 8244777 : (SPTEST(point_right, tst, centroid) ||
62 98662 : SPTEST(point_vert, tst, centroid)))
63 8053022 : return 1;
64 :
65 425279 : if (SPTEST(point_below, tst, centroid) &&
66 316078 : (SPTEST(point_right, tst, centroid) ||
67 149985 : SPTEST(point_vert, tst, centroid)))
68 16108 : return 2;
69 :
70 336171 : if ((SPTEST(point_below, tst, centroid) ||
71 243078 : SPTEST(point_horiz, tst, centroid)) &&
72 149985 : SPTEST(point_left, tst, centroid))
73 149985 : return 3;
74 :
75 186186 : if (SPTEST(point_above, tst, centroid) &&
76 93093 : SPTEST(point_left, tst, centroid))
77 93093 : 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 1701 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
86 : {
87 1701 : BOX *result = palloc_object(BOX);
88 :
89 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
117 8182655 : spg_quad_choose(PG_FUNCTION_ARGS)
118 : {
119 8182655 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
120 8182655 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
121 8182655 : Point *inPoint = DatumGetPointP(in->datum),
122 : *centroid;
123 :
124 8182655 : if (in->allTheSame)
125 : {
126 59419 : out->resultType = spgMatchNode;
127 : /* nodeN will be set by core */
128 59419 : out->result.matchNode.levelAdd = 0;
129 59419 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
130 59419 : PG_RETURN_VOID();
131 : }
132 :
133 : Assert(in->hasPrefix);
134 8123236 : centroid = DatumGetPointP(in->prefixDatum);
135 :
136 : Assert(in->nNodes == 4);
137 :
138 8123236 : out->resultType = spgMatchNode;
139 8123236 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
140 8123236 : out->result.matchNode.levelAdd = 0;
141 8123236 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
142 :
143 8123236 : 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 1344 : spg_quad_picksplit(PG_FUNCTION_ARGS)
172 : {
173 1344 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
174 1344 : 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 1344 : centroid = palloc0_object(Point);
195 :
196 190058 : for (i = 0; i < in->nTuples; i++)
197 : {
198 188714 : centroid->x += DatumGetPointP(in->datums[i])->x;
199 188714 : centroid->y += DatumGetPointP(in->datums[i])->y;
200 : }
201 :
202 1344 : centroid->x /= in->nTuples;
203 1344 : centroid->y /= in->nTuples;
204 : #endif
205 :
206 1344 : out->hasPrefix = true;
207 1344 : out->prefixDatum = PointPGetDatum(centroid);
208 :
209 1344 : out->nNodes = 4;
210 1344 : out->nodeLabels = NULL; /* we don't need node labels */
211 :
212 1344 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
213 1344 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
214 :
215 190058 : for (i = 0; i < in->nTuples; i++)
216 : {
217 188714 : Point *p = DatumGetPointP(in->datums[i]);
218 188714 : int quadrant = getQuadrant(centroid, p) - 1;
219 :
220 188714 : out->leafTupleDatums[i] = PointPGetDatum(p);
221 188714 : out->mapTuplesToNodes[i] = quadrant;
222 : }
223 :
224 1344 : PG_RETURN_VOID();
225 : }
226 :
227 :
228 : Datum
229 2895 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
230 : {
231 2895 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
232 2895 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
233 : Point *centroid;
234 : BOX infbbox;
235 2895 : BOX *bbox = NULL;
236 : int which;
237 : int i;
238 :
239 : Assert(in->hasPrefix);
240 2895 : 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 2895 : if (in->norderbys > 0)
250 : {
251 495 : out->distances = palloc_array(double *, in->nNodes);
252 495 : out->traversalValues = palloc_array(void *, in->nNodes);
253 :
254 495 : 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 483 : bbox = in->traversalValue;
267 : Assert(bbox);
268 : }
269 : }
270 :
271 2895 : if (in->allTheSame)
272 : {
273 : /* Report that all nodes should be visited */
274 315 : out->nNodes = in->nNodes;
275 315 : out->nodeNumbers = palloc_array(int, in->nNodes);
276 2835 : for (i = 0; i < in->nNodes; i++)
277 : {
278 2520 : out->nodeNumbers[i] = i;
279 :
280 2520 : if (in->norderbys > 0)
281 : {
282 504 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
283 :
284 : /* Use parent quadrant box as traversalValue */
285 504 : BOX *quadrant = box_copy(bbox);
286 :
287 504 : MemoryContextSwitchTo(oldCtx);
288 :
289 504 : out->traversalValues[i] = quadrant;
290 504 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
291 : in->orderbys, in->norderbys);
292 : }
293 : }
294 315 : PG_RETURN_VOID();
295 : }
296 :
297 : Assert(in->nNodes == 4);
298 :
299 : /* "which" is a bitmask of quadrants that satisfy all constraints */
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;
363 0 : default:
364 0 : elog(ERROR, "unrecognized strategy number: %d",
365 : in->scankeys[i].sk_strategy);
366 : break;
367 : }
368 :
369 1350 : if (which == 0)
370 0 : break; /* no need to consider remaining conditions */
371 : }
372 :
373 2580 : out->levelAdds = palloc_array(int, 4);
374 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 */
378 2580 : out->nodeNumbers = palloc_array(int, 4);
379 2580 : out->nNodes = 0;
380 :
381 12900 : for (i = 1; i <= 4; i++)
382 : {
383 10320 : if (which & (1 << i))
384 : {
385 9279 : out->nodeNumbers[out->nNodes] = i - 1;
386 :
387 9279 : if (in->norderbys > 0)
388 : {
389 1701 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
390 1701 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
391 :
392 1701 : MemoryContextSwitchTo(oldCtx);
393 :
394 1701 : out->traversalValues[out->nNodes] = quadrant;
395 :
396 1701 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
397 : in->orderbys, in->norderbys);
398 : }
399 :
400 9279 : out->nNodes++;
401 : }
402 : }
403 :
404 2580 : PG_RETURN_VOID();
405 : }
406 :
407 :
408 : Datum
409 615401 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
410 : {
411 615401 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
412 615401 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
413 615401 : Point *datum = DatumGetPointP(in->leafDatum);
414 : bool res;
415 : int i;
416 :
417 : /* all tests are exact */
418 615401 : out->recheck = false;
419 :
420 : /* leafDatum is what it is... */
421 615401 : out->leafValue = in->leafDatum;
422 :
423 : /* Perform the required comparison(s) */
424 615401 : res = true;
425 911099 : 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;
457 0 : default:
458 0 : elog(ERROR, "unrecognized strategy number: %d",
459 : in->scankeys[i].sk_strategy);
460 : break;
461 : }
462 :
463 350082 : if (!res)
464 54384 : break;
465 : }
466 :
467 615401 : if (res && in->norderbys > 0)
468 : /* ok, it passes -> let's compute the distances */
469 139661 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
470 : in->orderbys, in->norderbys);
471 :
472 615401 : PG_RETURN_BOOL(res);
473 : }
|
