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 73 : spg_quad_config(PG_FUNCTION_ARGS)
28 : {
29 : #ifdef NOT_USED
30 : spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
31 : #endif
32 73 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
33 :
34 73 : cfg->prefixType = POINTOID;
35 73 : cfg->labelType = VOIDOID; /* we don't need node labels */
36 73 : cfg->canReturnData = true;
37 73 : cfg->longValuesOK = false;
38 73 : 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 11126699 : getQuadrant(Point *centroid, Point *tst)
58 : {
59 11356972 : if ((SPTEST(point_above, tst, centroid) ||
60 11133198 : SPTEST(point_horiz, tst, centroid)) &&
61 11034452 : (SPTEST(point_right, tst, centroid) ||
62 131527 : SPTEST(point_vert, tst, centroid)))
63 10777897 : return 1;
64 :
65 572576 : if (SPTEST(point_below, tst, centroid) &&
66 424279 : (SPTEST(point_right, tst, centroid) ||
67 200505 : SPTEST(point_vert, tst, centroid)))
68 23269 : return 2;
69 :
70 450561 : if ((SPTEST(point_below, tst, centroid) ||
71 325533 : SPTEST(point_horiz, tst, centroid)) &&
72 200505 : SPTEST(point_left, tst, centroid))
73 200505 : return 3;
74 :
75 250056 : if (SPTEST(point_above, tst, centroid) &&
76 125028 : SPTEST(point_left, tst, centroid))
77 125028 : 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 10947630 : spg_quad_choose(PG_FUNCTION_ARGS)
118 : {
119 10947630 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
120 10947630 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
121 10947630 : Point *inPoint = DatumGetPointP(in->datum),
122 : *centroid;
123 :
124 10947630 : if (in->allTheSame)
125 : {
126 72939 : out->resultType = spgMatchNode;
127 : /* nodeN will be set by core */
128 72939 : out->result.matchNode.levelAdd = 0;
129 72939 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
130 72939 : PG_RETURN_VOID();
131 : }
132 :
133 : Assert(in->hasPrefix);
134 10874691 : centroid = DatumGetPointP(in->prefixDatum);
135 :
136 : Assert(in->nNodes == 4);
137 :
138 10874691 : out->resultType = spgMatchNode;
139 10874691 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
140 10874691 : out->result.matchNode.levelAdd = 0;
141 10874691 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
142 :
143 10874691 : 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 1789 : spg_quad_picksplit(PG_FUNCTION_ARGS)
172 : {
173 1789 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
174 1789 : 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 1789 : centroid = palloc0_object(Point);
195 :
196 253453 : for (i = 0; i < in->nTuples; i++)
197 : {
198 251664 : centroid->x += DatumGetPointP(in->datums[i])->x;
199 251664 : centroid->y += DatumGetPointP(in->datums[i])->y;
200 : }
201 :
202 1789 : centroid->x /= in->nTuples;
203 1789 : centroid->y /= in->nTuples;
204 : #endif
205 :
206 1789 : out->hasPrefix = true;
207 1789 : out->prefixDatum = PointPGetDatum(centroid);
208 :
209 1789 : out->nNodes = 4;
210 1789 : out->nodeLabels = NULL; /* we don't need node labels */
211 :
212 1789 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
213 1789 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
214 :
215 253453 : for (i = 0; i < in->nTuples; i++)
216 : {
217 251664 : Point *p = DatumGetPointP(in->datums[i]);
218 251664 : int quadrant = getQuadrant(centroid, p) - 1;
219 :
220 251664 : out->leafTupleDatums[i] = PointPGetDatum(p);
221 251664 : out->mapTuplesToNodes[i] = quadrant;
222 : }
223 :
224 1789 : PG_RETURN_VOID();
225 : }
226 :
227 :
228 : Datum
229 3815 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
230 : {
231 3815 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
232 3815 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
233 : Point *centroid;
234 : BOX infbbox;
235 3815 : BOX *bbox = NULL;
236 : int which;
237 : int i;
238 :
239 : Assert(in->hasPrefix);
240 3815 : 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 3815 : if (in->norderbys > 0)
250 : {
251 651 : out->distances = palloc_array(double *, in->nNodes);
252 651 : out->traversalValues = palloc_array(void *, in->nNodes);
253 :
254 651 : 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 635 : bbox = in->traversalValue;
267 : Assert(bbox);
268 : }
269 : }
270 :
271 3815 : if (in->allTheSame)
272 : {
273 : /* Report that all nodes should be visited */
274 375 : out->nNodes = in->nNodes;
275 375 : out->nodeNumbers = palloc_array(int, in->nNodes);
276 3375 : for (i = 0; i < in->nNodes; i++)
277 : {
278 3000 : out->nodeNumbers[i] = i;
279 :
280 3000 : if (in->norderbys > 0)
281 : {
282 600 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
283 :
284 : /* Use parent quadrant box as traversalValue */
285 600 : BOX *quadrant = box_copy(bbox);
286 :
287 600 : MemoryContextSwitchTo(oldCtx);
288 :
289 600 : out->traversalValues[i] = quadrant;
290 600 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
291 : in->orderbys, in->norderbys);
292 : }
293 : }
294 375 : 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 820534 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
410 : {
411 820534 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
412 820534 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
413 820534 : Point *datum = DatumGetPointP(in->leafDatum);
414 : bool res;
415 : int i;
416 :
417 : /* all tests are exact */
418 820534 : out->recheck = false;
419 :
420 : /* leafDatum is what it is... */
421 820534 : out->leafValue = in->leafDatum;
422 :
423 : /* Perform the required comparison(s) */
424 820534 : res = true;
425 1214798 : 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 820534 : if (res && in->norderbys > 0)
468 : /* ok, it passes -> let's compute the distances */
469 186214 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
470 : in->orderbys, in->norderbys);
471 :
472 820534 : PG_RETURN_BOOL(res);
473 : }
|
