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