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