Age Owner Branch data 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-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
4502 tgl@sss.pgh.pa.us 27 :CBC 56 : spg_quad_config(PG_FUNCTION_ARGS)
28 : : {
29 : : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
30 : 56 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
31 : :
32 : 56 : cfg->prefixType = POINTOID;
33 : 56 : cfg->labelType = VOIDOID; /* we don't need node labels */
4500 34 : 56 : cfg->canReturnData = true;
4502 35 : 56 : cfg->longValuesOK = false;
36 : 56 : 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 : 8320610 : getQuadrant(Point *centroid, Point *tst)
56 : : {
57 [ + + + + ]: 8492434 : if ((SPTEST(point_above, tst, centroid) ||
58 [ + + ]: 8325637 : SPTEST(point_horiz, tst, centroid)) &&
59 [ + + ]: 8251977 : (SPTEST(point_right, tst, centroid) ||
60 : 98164 : SPTEST(point_vert, tst, centroid)))
61 : 8060676 : return 1;
62 : :
63 [ + + + + ]: 426731 : if (SPTEST(point_below, tst, centroid) &&
64 [ - + ]: 316670 : (SPTEST(point_right, tst, centroid) ||
65 : 149873 : SPTEST(point_vert, tst, centroid)))
66 : 16924 : return 2;
67 : :
68 [ + + - + ]: 336147 : if ((SPTEST(point_below, tst, centroid) ||
69 [ + - ]: 243010 : SPTEST(point_horiz, tst, centroid)) &&
70 : 149873 : SPTEST(point_left, tst, centroid))
71 : 149873 : return 3;
72 : :
73 [ + - + - ]: 186274 : if (SPTEST(point_above, tst, centroid) &&
74 : 93137 : SPTEST(point_left, tst, centroid))
75 : 93137 : return 4;
76 : :
4502 tgl@sss.pgh.pa.us 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 *
2034 akorotkov@postgresql 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
4502 tgl@sss.pgh.pa.us 115 : 8188549 : spg_quad_choose(PG_FUNCTION_ARGS)
116 : : {
117 : 8188549 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
118 : 8188549 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
119 : 8188549 : Point *inPoint = DatumGetPointP(in->datum),
120 : : *centroid;
121 : :
122 [ + + ]: 8188549 : if (in->allTheSame)
123 : : {
124 : 55796 : out->resultType = spgMatchNode;
125 : : /* nodeN will be set by core */
126 : 55796 : out->result.matchNode.levelAdd = 0;
127 : 55796 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
128 : 55796 : PG_RETURN_VOID();
129 : : }
130 : :
131 [ - + ]: 8132753 : Assert(in->hasPrefix);
132 : 8132753 : centroid = DatumGetPointP(in->prefixDatum);
133 : :
134 [ - + ]: 8132753 : Assert(in->nNodes == 4);
135 : :
136 : 8132753 : out->resultType = spgMatchNode;
137 : 8132753 : out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
138 : 8132753 : out->result.matchNode.levelAdd = 0;
139 : 8132753 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
140 : :
141 : 8132753 : 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 : 1330 : spg_quad_picksplit(PG_FUNCTION_ARGS)
170 : : {
171 : 1330 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
172 : 1330 : 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 : 1330 : centroid = palloc0(sizeof(*centroid));
193 : :
194 [ + + ]: 188929 : for (i = 0; i < in->nTuples; i++)
195 : : {
196 : 187599 : centroid->x += DatumGetPointP(in->datums[i])->x;
197 : 187599 : centroid->y += DatumGetPointP(in->datums[i])->y;
198 : : }
199 : :
200 : 1330 : centroid->x /= in->nTuples;
201 : 1330 : centroid->y /= in->nTuples;
202 : : #endif
203 : :
204 : 1330 : out->hasPrefix = true;
205 : 1330 : out->prefixDatum = PointPGetDatum(centroid);
206 : :
207 : 1330 : out->nNodes = 4;
208 : 1330 : out->nodeLabels = NULL; /* we don't need node labels */
209 : :
210 : 1330 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
211 : 1330 : out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
212 : :
213 [ + + ]: 188929 : for (i = 0; i < in->nTuples; i++)
214 : : {
215 : 187599 : Point *p = DatumGetPointP(in->datums[i]);
216 : 187599 : int quadrant = getQuadrant(centroid, p) - 1;
217 : :
218 : 187599 : out->leafTupleDatums[i] = PointPGetDatum(p);
219 : 187599 : out->mapTuplesToNodes[i] = quadrant;
220 : : }
221 : :
222 : 1330 : 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;
2034 akorotkov@postgresql 233 : 2850 : BOX *bbox = NULL;
234 : : int which;
235 : : int i;
236 : :
4502 tgl@sss.pgh.pa.us 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 : : */
2034 akorotkov@postgresql 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 : :
4502 tgl@sss.pgh.pa.us 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 : :
2034 akorotkov@postgresql 278 [ + + ]: 2160 : if (in->norderbys > 0)
279 : : {
2026 280 : 432 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
281 : :
282 : : /* Use parent quadrant box as traversalValue */
2034 283 : 432 : BOX *quadrant = box_copy(bbox);
284 : :
285 : 432 : MemoryContextSwitchTo(oldCtx);
286 : :
287 : 432 : out->traversalValues[i] = quadrant;
2026 288 : 432 : out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
289 : : in->orderbys, in->norderbys);
290 : : }
291 : : }
4502 tgl@sss.pgh.pa.us 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 */
4418 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;
4418 tgl@sss.pgh.pa.us 361 :UBC 0 : default:
362 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
363 : : in->scankeys[i].sk_strategy);
364 : : break;
365 : : }
366 : :
4418 tgl@sss.pgh.pa.us 367 [ - + ]:CBC 1350 : if (which == 0)
4418 tgl@sss.pgh.pa.us 368 :UBC 0 : break; /* no need to consider remaining conditions */
369 : : }
370 : :
2034 akorotkov@postgresql 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 */
4418 tgl@sss.pgh.pa.us 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 : : {
2034 akorotkov@postgresql 383 : 9279 : out->nodeNumbers[out->nNodes] = i - 1;
384 : :
385 [ + + ]: 9279 : if (in->norderbys > 0)
386 : : {
2026 387 : 1701 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
2034 388 : 1701 : BOX *quadrant = getQuadrantArea(bbox, centroid, i);
389 : :
390 : 1701 : MemoryContextSwitchTo(oldCtx);
391 : :
392 : 1701 : out->traversalValues[out->nNodes] = quadrant;
393 : :
2026 394 : 1701 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
395 : : in->orderbys, in->norderbys);
396 : : }
397 : :
2034 398 : 9279 : out->nNodes++;
399 : : }
400 : : }
401 : :
4502 tgl@sss.pgh.pa.us 402 : 2580 : PG_RETURN_VOID();
403 : : }
404 : :
405 : :
406 : : Datum
407 : 615390 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
408 : : {
409 : 615390 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
410 : 615390 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
411 : 615390 : Point *datum = DatumGetPointP(in->leafDatum);
412 : : bool res;
413 : : int i;
414 : :
415 : : /* all tests are exact */
416 : 615390 : out->recheck = false;
417 : :
418 : : /* leafDatum is what it is... */
4500 419 : 615390 : out->leafValue = in->leafDatum;
420 : :
421 : : /* Perform the required comparison(s) */
4418 422 : 615390 : res = true;
423 [ + + ]: 911088 : 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;
4418 tgl@sss.pgh.pa.us 455 :UBC 0 : default:
456 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
457 : : in->scankeys[i].sk_strategy);
458 : : break;
459 : : }
460 : :
4418 tgl@sss.pgh.pa.us 461 [ + + ]:CBC 350082 : if (!res)
4502 462 : 54384 : break;
463 : : }
464 : :
2034 akorotkov@postgresql 465 [ + + + + ]: 615390 : if (res && in->norderbys > 0)
466 : : /* ok, it passes -> let's compute the distances */
2026 467 : 139650 : out->distances = spg_key_orderbys_distances(in->leafDatum, true,
468 : : in->orderbys, in->norderbys);
469 : :
4502 tgl@sss.pgh.pa.us 470 : 615390 : PG_RETURN_BOOL(res);
471 : : }
|
