TLA 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-2023, 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/builtins.h"
23 : #include "utils/float.h"
24 : #include "utils/geo_decls.h"
25 :
26 : Datum
27 CBC 54 : spg_quad_config(PG_FUNCTION_ARGS)
28 : {
29 : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
30 54 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
31 :
32 54 : cfg->prefixType = POINTOID;
33 54 : cfg->labelType = VOIDOID; /* we don't need node labels */
34 54 : cfg->canReturnData = true;
35 54 : cfg->longValuesOK = false;
36 54 : 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 8323647 : getQuadrant(Point *centroid, Point *tst)
56 : {
57 8495524 : if ((SPTEST(point_above, tst, centroid) ||
58 8328500 : SPTEST(point_horiz, tst, centroid)) &&
59 8255391 : (SPTEST(point_right, tst, centroid) ||
60 98768 : SPTEST(point_vert, tst, centroid)))
61 8062708 : return 1;
62 :
63 427963 : if (SPTEST(point_below, tst, centroid) &&
64 316416 : (SPTEST(point_right, tst, centroid) ||
65 149392 : SPTEST(point_vert, tst, centroid)))
66 17632 : return 2;
67 :
68 337222 : if ((SPTEST(point_below, tst, centroid) ||
69 243307 : SPTEST(point_horiz, tst, centroid)) &&
70 149392 : SPTEST(point_left, tst, centroid))
71 149392 : return 3;
72 :
73 187830 : if (SPTEST(point_above, tst, centroid) &&
74 93915 : SPTEST(point_left, tst, centroid))
75 93915 : return 4;
76 :
77 UBC 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 CBC 1701 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
84 : {
85 1701 : BOX *result = (BOX *) palloc(sizeof(BOX));
86 :
87 1701 : switch (quadrant)
88 : {
89 420 : case 1:
90 420 : result->high = bbox->high;
91 420 : result->low = *centroid;
92 420 : break;
93 423 : case 2:
94 423 : result->high.x = bbox->high.x;
95 423 : result->high.y = centroid->y;
96 423 : result->low.x = centroid->x;
97 423 : result->low.y = bbox->low.y;
98 423 : break;
99 429 : case 3:
100 429 : result->high = *centroid;
101 429 : result->low = bbox->low;
102 429 : break;
103 429 : case 4:
104 429 : result->high.x = centroid->x;
105 429 : result->high.y = bbox->high.y;
106 429 : result->low.x = bbox->low.x;
107 429 : result->low.y = centroid->y;
108 429 : break;
109 : }
110 :
111 1701 : return result;
112 : }
113 :
114 : Datum
115 8190625 : spg_quad_choose(PG_FUNCTION_ARGS)
116 : {
117 8190625 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
118 8190625 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
119 8190625 : Point *inPoint = DatumGetPointP(in->datum),
120 : *centroid;
121 :
122 8190625 : if (in->allTheSame)
123 : {
124 54506 : out->resultType = spgMatchNode;
125 : /* nodeN will be set by core */
126 54506 : out->result.matchNode.levelAdd = 0;
127 54506 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
128 54506 : PG_RETURN_VOID();
129 : }
130 :
131 8136119 : Assert(in->hasPrefix);
132 8136119 : centroid = DatumGetPointP(in->prefixDatum);
133 :
134 8136119 : Assert(in->nNodes == 4);
135 :
136 8136119 : out->resultType = spgMatchNode;
137 8136119 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
138 8136119 : out->result.matchNode.levelAdd = 0;
139 8136119 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
140 :
141 8136119 : 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 1334 : spg_quad_picksplit(PG_FUNCTION_ARGS)
170 : {
171 1334 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
172 1334 : 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 1334 : centroid = palloc0(sizeof(*centroid));
193 :
194 188604 : for (i = 0; i < in->nTuples; i++)
195 : {
196 187270 : centroid->x += DatumGetPointP(in->datums[i])->x;
197 187270 : centroid->y += DatumGetPointP(in->datums[i])->y;
198 : }
199 :
200 1334 : centroid->x /= in->nTuples;
201 1334 : centroid->y /= in->nTuples;
202 : #endif
203 :
204 1334 : out->hasPrefix = true;
205 1334 : out->prefixDatum = PointPGetDatum(centroid);
206 :
207 1334 : out->nNodes = 4;
208 1334 : out->nodeLabels = NULL; /* we don't need node labels */
209 :
210 1334 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
211 1334 : out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
212 :
213 188604 : for (i = 0; i < in->nTuples; i++)
214 : {
215 187270 : Point *p = DatumGetPointP(in->datums[i]);
216 187270 : int quadrant = getQuadrant(centroid, p) - 1;
217 :
218 187270 : out->leafTupleDatums[i] = PointPGetDatum(p);
219 187270 : out->mapTuplesToNodes[i] = quadrant;
220 : }
221 :
222 1334 : PG_RETURN_VOID();
223 : }
224 :
225 :
226 : Datum
227 2850 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
228 : {
229 2850 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
230 2850 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
231 : Point *centroid;
232 : BOX infbbox;
233 2850 : BOX *bbox = NULL;
234 : int which;
235 : int i;
236 :
237 2850 : Assert(in->hasPrefix);
238 2850 : 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 2850 : if (in->norderbys > 0)
248 : {
249 486 : out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
250 486 : out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
251 :
252 486 : if (in->level == 0)
253 : {
254 12 : double inf = get_float8_infinity();
255 :
256 12 : infbbox.high.x = inf;
257 12 : infbbox.high.y = inf;
258 12 : infbbox.low.x = -inf;
259 12 : infbbox.low.y = -inf;
260 12 : bbox = &infbbox;
261 : }
262 : else
263 : {
264 474 : bbox = in->traversalValue;
265 474 : Assert(bbox);
266 : }
267 : }
268 :
269 2850 : if (in->allTheSame)
270 : {
271 : /* Report that all nodes should be visited */
272 270 : out->nNodes = in->nNodes;
273 270 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
274 2430 : for (i = 0; i < in->nNodes; i++)
275 : {
276 2160 : out->nodeNumbers[i] = i;
277 :
278 2160 : if (in->norderbys > 0)
279 : {
280 432 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
281 :
282 : /* Use parent quadrant box as traversalValue */
283 432 : BOX *quadrant = box_copy(bbox);
284 :
285 432 : MemoryContextSwitchTo(oldCtx);
286 :
287 432 : out->traversalValues[i] = quadrant;
288 432 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
289 : in->orderbys, in->norderbys);
290 : }
291 : }
292 270 : PG_RETURN_VOID();
293 : }
294 :
295 2580 : Assert(in->nNodes == 4);
296 :
297 : /* "which" is a bitmask of quadrants that satisfy all constraints */
298 2580 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
299 :
300 3930 : for (i = 0; i < in->nkeys; i++)
301 : {
302 1350 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
303 : BOX *boxQuery;
304 :
305 1350 : switch (in->scankeys[i].sk_strategy)
306 : {
307 234 : case RTLeftStrategyNumber:
308 234 : if (SPTEST(point_right, centroid, query))
309 30 : which &= (1 << 3) | (1 << 4);
310 234 : break;
311 210 : case RTRightStrategyNumber:
312 210 : if (SPTEST(point_left, centroid, query))
313 6 : which &= (1 << 1) | (1 << 2);
314 210 : break;
315 18 : case RTSameStrategyNumber:
316 18 : which &= (1 << getQuadrant(centroid, query));
317 18 : break;
318 402 : case RTBelowStrategyNumber:
319 : case RTOldBelowStrategyNumber:
320 402 : if (SPTEST(point_above, centroid, query))
321 168 : which &= (1 << 2) | (1 << 3);
322 402 : break;
323 396 : case RTAboveStrategyNumber:
324 : case RTOldAboveStrategyNumber:
325 396 : if (SPTEST(point_below, centroid, query))
326 222 : which &= (1 << 1) | (1 << 4);
327 396 : break;
328 90 : 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 90 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
336 :
337 90 : 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 60 : int r = 0;
348 :
349 60 : p = boxQuery->low;
350 60 : r |= 1 << getQuadrant(centroid, &p);
351 60 : p.y = boxQuery->high.y;
352 60 : r |= 1 << getQuadrant(centroid, &p);
353 60 : p = boxQuery->high;
354 60 : r |= 1 << getQuadrant(centroid, &p);
355 60 : p.x = boxQuery->low.x;
356 60 : r |= 1 << getQuadrant(centroid, &p);
357 :
358 60 : which &= r;
359 : }
360 90 : break;
361 UBC 0 : default:
362 0 : elog(ERROR, "unrecognized strategy number: %d",
363 : in->scankeys[i].sk_strategy);
364 : break;
365 : }
366 :
367 CBC 1350 : if (which == 0)
368 UBC 0 : break; /* no need to consider remaining conditions */
369 : }
370 :
371 CBC 2580 : out->levelAdds = palloc(sizeof(int) * 4);
372 12900 : for (i = 0; i < 4; ++i)
373 10320 : out->levelAdds[i] = 1;
374 :
375 : /* We must descend into the quadrant(s) identified by which */
376 2580 : out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
377 2580 : out->nNodes = 0;
378 :
379 12900 : for (i = 1; i <= 4; i++)
380 : {
381 10320 : if (which & (1 << i))
382 : {
383 9279 : out->nodeNumbers[out->nNodes] = i - 1;
384 :
385 9279 : if (in->norderbys > 0)
386 : {
387 1701 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
388 1701 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
389 :
390 1701 : MemoryContextSwitchTo(oldCtx);
391 :
392 1701 : out->traversalValues[out->nNodes] = quadrant;
393 :
394 1701 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
395 : in->orderbys, in->norderbys);
396 : }
397 :
398 9279 : out->nNodes++;
399 : }
400 : }
401 :
402 2580 : PG_RETURN_VOID();
403 : }
404 :
405 :
406 : Datum
407 615402 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
408 : {
409 615402 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
410 615402 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
411 615402 : Point *datum = DatumGetPointP(in->leafDatum);
412 : bool res;
413 : int i;
414 :
415 : /* all tests are exact */
416 615402 : out->recheck = false;
417 :
418 : /* leafDatum is what it is... */
419 615402 : out->leafValue = in->leafDatum;
420 :
421 : /* Perform the required comparison(s) */
422 615402 : res = true;
423 911100 : for (i = 0; i < in->nkeys; i++)
424 : {
425 350082 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
426 :
427 350082 : switch (in->scankeys[i].sk_strategy)
428 : {
429 75954 : case RTLeftStrategyNumber:
430 75954 : res = SPTEST(point_left, datum, query);
431 75954 : break;
432 61626 : case RTRightStrategyNumber:
433 61626 : res = SPTEST(point_right, datum, query);
434 61626 : break;
435 1020 : case RTSameStrategyNumber:
436 1020 : res = SPTEST(point_eq, datum, query);
437 1020 : break;
438 87174 : case RTBelowStrategyNumber:
439 : case RTOldBelowStrategyNumber:
440 87174 : res = SPTEST(point_below, datum, query);
441 87174 : break;
442 86778 : case RTAboveStrategyNumber:
443 : case RTOldAboveStrategyNumber:
444 86778 : res = SPTEST(point_above, datum, query);
445 86778 : break;
446 37530 : 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 37530 : res = SPTEST(box_contain_pt, query, datum);
454 37530 : break;
455 UBC 0 : default:
456 0 : elog(ERROR, "unrecognized strategy number: %d",
457 : in->scankeys[i].sk_strategy);
458 : break;
459 : }
460 :
461 CBC 350082 : if (!res)
462 54384 : break;
463 : }
464 :
465 615402 : if (res && in->norderbys > 0)
466 : /* ok, it passes -> let's compute the distances */
467 139662 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
468 : in->orderbys, in->norderbys);
469 :
470 615402 : PG_RETURN_BOOL(res);
471 : }
|
