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