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-2024, 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 108 : spg_quad_config(PG_FUNCTION_ARGS)
28 : {
29 : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
30 108 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
31 :
32 108 : cfg->prefixType = POINTOID;
33 108 : cfg->labelType = VOIDOID; /* we don't need node labels */
34 108 : cfg->canReturnData = true;
35 108 : cfg->longValuesOK = false;
36 108 : PG_RETURN_VOID();
37 : }
38 :
39 : #define SPTEST(f, x, y) \
40 : DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))
41 :
42 : /*
43 : * Determine which quadrant a point falls into, relative to the centroid.
44 : *
45 : * Quadrants are identified like this:
46 : *
47 : * 4 | 1
48 : * ----+-----
49 : * 3 | 2
50 : *
51 : * Points on one of the axes are taken to lie in the lowest-numbered
52 : * adjacent quadrant.
53 : */
54 : static int16
55 16629662 : getQuadrant(Point *centroid, Point *tst)
56 : {
57 16973392 : if ((SPTEST(point_above, tst, centroid) ||
58 16639930 : SPTEST(point_horiz, tst, centroid)) &&
59 16492330 : (SPTEST(point_right, tst, centroid) ||
60 196130 : SPTEST(point_vert, tst, centroid)))
61 16110338 : return 1;
62 :
63 852786 : if (SPTEST(point_below, tst, centroid) &&
64 633612 : (SPTEST(point_right, tst, centroid) ||
65 300150 : SPTEST(point_vert, tst, centroid)))
66 33312 : return 2;
67 :
68 671874 : if ((SPTEST(point_below, tst, centroid) ||
69 486012 : SPTEST(point_horiz, tst, centroid)) &&
70 300150 : SPTEST(point_left, tst, centroid))
71 300150 : return 3;
72 :
73 371724 : if (SPTEST(point_above, tst, centroid) &&
74 185862 : SPTEST(point_left, tst, centroid))
75 185862 : return 4;
76 :
77 0 : elog(ERROR, "getQuadrant: impossible case");
78 : return 0;
79 : }
80 :
81 : /* Returns bounding box of a given quadrant inside given bounding box */
82 : static BOX *
83 3402 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
84 : {
85 3402 : BOX *result = (BOX *) palloc(sizeof(BOX));
86 :
87 3402 : switch (quadrant)
88 : {
89 840 : case 1:
90 840 : result->high = bbox->high;
91 840 : result->low = *centroid;
92 840 : break;
93 846 : case 2:
94 846 : result->high.x = bbox->high.x;
95 846 : result->high.y = centroid->y;
96 846 : result->low.x = centroid->x;
97 846 : result->low.y = bbox->low.y;
98 846 : break;
99 858 : case 3:
100 858 : result->high = *centroid;
101 858 : result->low = bbox->low;
102 858 : break;
103 858 : case 4:
104 858 : result->high.x = centroid->x;
105 858 : result->high.y = bbox->high.y;
106 858 : result->low.x = bbox->low.x;
107 858 : result->low.y = centroid->y;
108 858 : break;
109 : }
110 :
111 3402 : return result;
112 : }
113 :
114 : Datum
115 16367246 : spg_quad_choose(PG_FUNCTION_ARGS)
116 : {
117 16367246 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
118 16367246 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
119 16367246 : Point *inPoint = DatumGetPointP(in->datum),
120 : *centroid;
121 :
122 16367246 : if (in->allTheSame)
123 : {
124 114348 : out->resultType = spgMatchNode;
125 : /* nodeN will be set by core */
126 114348 : out->result.matchNode.levelAdd = 0;
127 114348 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
128 114348 : PG_RETURN_VOID();
129 : }
130 :
131 : Assert(in->hasPrefix);
132 16252898 : centroid = DatumGetPointP(in->prefixDatum);
133 :
134 : Assert(in->nNodes == 4);
135 :
136 16252898 : out->resultType = spgMatchNode;
137 16252898 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
138 16252898 : out->result.matchNode.levelAdd = 0;
139 16252898 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
140 :
141 16252898 : PG_RETURN_VOID();
142 : }
143 :
144 : #ifdef USE_MEDIAN
145 : static int
146 : x_cmp(const void *a, const void *b, void *arg)
147 : {
148 : Point *pa = *(Point **) a;
149 : Point *pb = *(Point **) b;
150 :
151 : if (pa->x == pb->x)
152 : return 0;
153 : return (pa->x > pb->x) ? 1 : -1;
154 : }
155 :
156 : static int
157 : y_cmp(const void *a, const void *b, void *arg)
158 : {
159 : Point *pa = *(Point **) a;
160 : Point *pb = *(Point **) b;
161 :
162 : if (pa->y == pb->y)
163 : return 0;
164 : return (pa->y > pb->y) ? 1 : -1;
165 : }
166 : #endif
167 :
168 : Datum
169 2680 : spg_quad_picksplit(PG_FUNCTION_ARGS)
170 : {
171 2680 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
172 2680 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
173 : int i;
174 : Point *centroid;
175 :
176 : #ifdef USE_MEDIAN
177 : /* Use the median values of x and y as the centroid point */
178 : Point **sorted;
179 :
180 : sorted = palloc(sizeof(*sorted) * in->nTuples);
181 : for (i = 0; i < in->nTuples; i++)
182 : sorted[i] = DatumGetPointP(in->datums[i]);
183 :
184 : centroid = palloc(sizeof(*centroid));
185 :
186 : qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
187 : centroid->x = sorted[in->nTuples >> 1]->x;
188 : qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
189 : centroid->y = sorted[in->nTuples >> 1]->y;
190 : #else
191 : /* Use the average values of x and y as the centroid point */
192 2680 : centroid = palloc0(sizeof(*centroid));
193 :
194 378928 : for (i = 0; i < in->nTuples; i++)
195 : {
196 376248 : centroid->x += DatumGetPointP(in->datums[i])->x;
197 376248 : centroid->y += DatumGetPointP(in->datums[i])->y;
198 : }
199 :
200 2680 : centroid->x /= in->nTuples;
201 2680 : centroid->y /= in->nTuples;
202 : #endif
203 :
204 2680 : out->hasPrefix = true;
205 2680 : out->prefixDatum = PointPGetDatum(centroid);
206 :
207 2680 : out->nNodes = 4;
208 2680 : out->nodeLabels = NULL; /* we don't need node labels */
209 :
210 2680 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
211 2680 : out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
212 :
213 378928 : for (i = 0; i < in->nTuples; i++)
214 : {
215 376248 : Point *p = DatumGetPointP(in->datums[i]);
216 376248 : int quadrant = getQuadrant(centroid, p) - 1;
217 :
218 376248 : out->leafTupleDatums[i] = PointPGetDatum(p);
219 376248 : out->mapTuplesToNodes[i] = quadrant;
220 : }
221 :
222 2680 : PG_RETURN_VOID();
223 : }
224 :
225 :
226 : Datum
227 5760 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
228 : {
229 5760 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
230 5760 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
231 : Point *centroid;
232 : BOX infbbox;
233 5760 : BOX *bbox = NULL;
234 : int which;
235 : int i;
236 :
237 : Assert(in->hasPrefix);
238 5760 : centroid = DatumGetPointP(in->prefixDatum);
239 :
240 : /*
241 : * When ordering scan keys are specified, we've to calculate distance for
242 : * them. In order to do that, we need calculate bounding boxes for all
243 : * children nodes. Calculation of those bounding boxes on non-zero level
244 : * require knowledge of bounding box of upper node. So, we save bounding
245 : * boxes to traversalValues.
246 : */
247 5760 : if (in->norderbys > 0)
248 : {
249 984 : out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
250 984 : out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
251 :
252 984 : if (in->level == 0)
253 : {
254 24 : double inf = get_float8_infinity();
255 :
256 24 : infbbox.high.x = inf;
257 24 : infbbox.high.y = inf;
258 24 : infbbox.low.x = -inf;
259 24 : infbbox.low.y = -inf;
260 24 : bbox = &infbbox;
261 : }
262 : else
263 : {
264 960 : bbox = in->traversalValue;
265 : Assert(bbox);
266 : }
267 : }
268 :
269 5760 : if (in->allTheSame)
270 : {
271 : /* Report that all nodes should be visited */
272 600 : out->nNodes = in->nNodes;
273 600 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
274 5400 : for (i = 0; i < in->nNodes; i++)
275 : {
276 4800 : out->nodeNumbers[i] = i;
277 :
278 4800 : if (in->norderbys > 0)
279 : {
280 960 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
281 :
282 : /* Use parent quadrant box as traversalValue */
283 960 : BOX *quadrant = box_copy(bbox);
284 :
285 960 : MemoryContextSwitchTo(oldCtx);
286 :
287 960 : out->traversalValues[i] = quadrant;
288 960 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
289 : in->orderbys, in->norderbys);
290 : }
291 : }
292 600 : PG_RETURN_VOID();
293 : }
294 :
295 : Assert(in->nNodes == 4);
296 :
297 : /* "which" is a bitmask of quadrants that satisfy all constraints */
298 5160 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
299 :
300 7860 : for (i = 0; i < in->nkeys; i++)
301 : {
302 2700 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
303 : BOX *boxQuery;
304 :
305 2700 : switch (in->scankeys[i].sk_strategy)
306 : {
307 468 : case RTLeftStrategyNumber:
308 468 : if (SPTEST(point_right, centroid, query))
309 60 : which &= (1 << 3) | (1 << 4);
310 468 : break;
311 420 : case RTRightStrategyNumber:
312 420 : if (SPTEST(point_left, centroid, query))
313 12 : which &= (1 << 1) | (1 << 2);
314 420 : break;
315 36 : case RTSameStrategyNumber:
316 36 : which &= (1 << getQuadrant(centroid, query));
317 36 : break;
318 804 : case RTBelowStrategyNumber:
319 : case RTOldBelowStrategyNumber:
320 804 : if (SPTEST(point_above, centroid, query))
321 336 : which &= (1 << 2) | (1 << 3);
322 804 : break;
323 792 : case RTAboveStrategyNumber:
324 : case RTOldAboveStrategyNumber:
325 792 : if (SPTEST(point_below, centroid, query))
326 444 : which &= (1 << 1) | (1 << 4);
327 792 : break;
328 180 : case RTContainedByStrategyNumber:
329 :
330 : /*
331 : * For this operator, the query is a box not a point. We
332 : * cheat to the extent of assuming that DatumGetPointP won't
333 : * do anything that would be bad for a pointer-to-box.
334 : */
335 180 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
336 :
337 180 : if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
338 : PointerGetDatum(boxQuery),
339 : PointerGetDatum(centroid))))
340 : {
341 : /* centroid is in box, so all quadrants are OK */
342 : }
343 : else
344 : {
345 : /* identify quadrant(s) containing all corners of box */
346 : Point p;
347 120 : int r = 0;
348 :
349 120 : p = boxQuery->low;
350 120 : r |= 1 << getQuadrant(centroid, &p);
351 120 : p.y = boxQuery->high.y;
352 120 : r |= 1 << getQuadrant(centroid, &p);
353 120 : p = boxQuery->high;
354 120 : r |= 1 << getQuadrant(centroid, &p);
355 120 : p.x = boxQuery->low.x;
356 120 : r |= 1 << getQuadrant(centroid, &p);
357 :
358 120 : which &= r;
359 : }
360 180 : break;
361 0 : default:
362 0 : elog(ERROR, "unrecognized strategy number: %d",
363 : in->scankeys[i].sk_strategy);
364 : break;
365 : }
366 :
367 2700 : if (which == 0)
368 0 : break; /* no need to consider remaining conditions */
369 : }
370 :
371 5160 : out->levelAdds = palloc(sizeof(int) * 4);
372 25800 : for (i = 0; i < 4; ++i)
373 20640 : out->levelAdds[i] = 1;
374 :
375 : /* We must descend into the quadrant(s) identified by which */
376 5160 : out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
377 5160 : out->nNodes = 0;
378 :
379 25800 : for (i = 1; i <= 4; i++)
380 : {
381 20640 : if (which & (1 << i))
382 : {
383 18558 : out->nodeNumbers[out->nNodes] = i - 1;
384 :
385 18558 : if (in->norderbys > 0)
386 : {
387 3402 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
388 3402 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
389 :
390 3402 : MemoryContextSwitchTo(oldCtx);
391 :
392 3402 : out->traversalValues[out->nNodes] = quadrant;
393 :
394 3402 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
395 : in->orderbys, in->norderbys);
396 : }
397 :
398 18558 : out->nNodes++;
399 : }
400 : }
401 :
402 5160 : PG_RETURN_VOID();
403 : }
404 :
405 :
406 : Datum
407 1230824 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
408 : {
409 1230824 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
410 1230824 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
411 1230824 : Point *datum = DatumGetPointP(in->leafDatum);
412 : bool res;
413 : int i;
414 :
415 : /* all tests are exact */
416 1230824 : out->recheck = false;
417 :
418 : /* leafDatum is what it is... */
419 1230824 : out->leafValue = in->leafDatum;
420 :
421 : /* Perform the required comparison(s) */
422 1230824 : res = true;
423 1822220 : for (i = 0; i < in->nkeys; i++)
424 : {
425 700164 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
426 :
427 700164 : switch (in->scankeys[i].sk_strategy)
428 : {
429 151908 : case RTLeftStrategyNumber:
430 151908 : res = SPTEST(point_left, datum, query);
431 151908 : break;
432 123252 : case RTRightStrategyNumber:
433 123252 : res = SPTEST(point_right, datum, query);
434 123252 : break;
435 2040 : case RTSameStrategyNumber:
436 2040 : res = SPTEST(point_eq, datum, query);
437 2040 : break;
438 174348 : case RTBelowStrategyNumber:
439 : case RTOldBelowStrategyNumber:
440 174348 : res = SPTEST(point_below, datum, query);
441 174348 : break;
442 173556 : case RTAboveStrategyNumber:
443 : case RTOldAboveStrategyNumber:
444 173556 : res = SPTEST(point_above, datum, query);
445 173556 : break;
446 75060 : case RTContainedByStrategyNumber:
447 :
448 : /*
449 : * For this operator, the query is a box not a point. We
450 : * cheat to the extent of assuming that DatumGetPointP won't
451 : * do anything that would be bad for a pointer-to-box.
452 : */
453 75060 : res = SPTEST(box_contain_pt, query, datum);
454 75060 : break;
455 0 : default:
456 0 : elog(ERROR, "unrecognized strategy number: %d",
457 : in->scankeys[i].sk_strategy);
458 : break;
459 : }
460 :
461 700164 : if (!res)
462 108768 : break;
463 : }
464 :
465 1230824 : if (res && in->norderbys > 0)
466 : /* ok, it passes -> let's compute the distances */
467 279344 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
468 : in->orderbys, in->norderbys);
469 :
470 1230824 : PG_RETURN_BOOL(res);
471 : }
|
