PostgreSQL Source Code  git master
spgquadtreeproc.c
Go to the documentation of this file.
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 
27 Datum
29 {
30  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
32 
33  cfg->prefixType = POINTOID;
34  cfg->labelType = VOIDOID; /* we don't need node labels */
35  cfg->canReturnData = true;
36  cfg->longValuesOK = false;
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  */
55 static int16
56 getQuadrant(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 */
83 static BOX *
84 getQuadrantArea(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 
115 Datum
117 {
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
146 static int
147 x_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 
157 static int
158 y_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 
169 Datum
171 {
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 
227 Datum
229 {
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  {
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  {
309  if (SPTEST(point_right, centroid, query))
310  which &= (1 << 3) | (1 << 4);
311  break;
313  if (SPTEST(point_left, centroid, query))
314  which &= (1 << 1) | (1 << 2);
315  break;
317  which &= (1 << getQuadrant(centroid, query));
318  break;
320  if (SPTEST(point_above, centroid, query))
321  which &= (1 << 2) | (1 << 3);
322  break;
324  if (SPTEST(point_below, centroid, query))
325  which &= (1 << 1) | (1 << 4);
326  break;
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 
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  {
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 
405 Datum
407 {
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  {
429  res = SPTEST(point_left, datum, query);
430  break;
432  res = SPTEST(point_right, datum, query);
433  break;
435  res = SPTEST(point_eq, datum, query);
436  break;
438  res = SPTEST(point_below, datum, query);
439  break;
441  res = SPTEST(point_above, datum, query);
442  break;
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 */
465  in->orderbys, in->norderbys);
466 
467  PG_RETURN_BOOL(res);
468 }
signed short int16
Definition: c.h:345
Datum spg_quad_picksplit(PG_FUNCTION_ARGS)
static BOX * getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
Definition: geo_decls.h:99
Datum datum
Definition: spgist.h:58
bool hasPrefix
Definition: spgist.h:64
static float8 get_float8_infinity(void)
Definition: float.h:90
bool canReturnData
Definition: spgist.h:49
float8 x
Definition: geo_decls.h:57
Datum * leafTupleDatums
Definition: spgist.h:129
#define RTLeftStrategyNumber
Definition: stratnum.h:51
Datum * datums
Definition: spgist.h:116
struct spgChooseOut::@48::@49 matchNode
#define PointerGetDatum(X)
Definition: postgres.h:556
Datum box_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3195
ScanKey orderbys
Definition: spgist.h:138
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * traversalValue
Definition: spgist.h:144
Datum prefixDatum
Definition: spgist.h:65
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define RTBelowStrategyNumber
Definition: stratnum.h:60
Datum spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
Datum point_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1886
Datum point_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1868
MemoryContext traversalMemoryContext
Definition: spgist.h:145
#define ERROR
Definition: elog.h:43
ScanKey orderbys
Definition: spgist.h:173
Datum * nodeLabels
Definition: spgist.h:126
StrategyNumber sk_strategy
Definition: skey.h:68
ScanKey scankeys
Definition: spgist.h:172
Datum point_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1859
double * distances
Definition: spgist.h:191
#define SPTEST(f, x, y)
#define DatumGetBool(X)
Definition: postgres.h:393
#define RTSameStrategyNumber
Definition: stratnum.h:56
static int16 getQuadrant(Point *centroid, Point *tst)
void ** traversalValues
Definition: spgist.h:163
static int x_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:85
int nNodes
Definition: spgist.h:66
Point low
Definition: geo_decls.h:101
Datum spg_quad_inner_consistent(PG_FUNCTION_ARGS)
void * palloc0(Size size)
Definition: mcxt.c:980
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:349
bool longValuesOK
Definition: spgist.h:50
uintptr_t Datum
Definition: postgres.h:367
double ** distances
Definition: spgist.h:164
Datum point_vert(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1895
Oid prefixType
Definition: spgist.h:46
spgChooseResultType resultType
Definition: spgist.h:79
BOX * box_copy(BOX *orig)
Definition: spgproc.c:82
Datum spg_quad_choose(PG_FUNCTION_ARGS)
#define BoxPGetDatum(X)
Definition: geo_decls.h:157
#define PG_RETURN_VOID()
Definition: fmgr.h:339
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define Assert(condition)
Definition: c.h:732
float8 y
Definition: geo_decls.h:57
#define RTRightStrategyNumber
Definition: stratnum.h:55
#define DatumGetPointP(X)
Definition: geo_decls.h:134
bool hasPrefix
Definition: spgist.h:122
union spgChooseOut::@48 result
ScanKey scankeys
Definition: spgist.h:137
#define DatumGetBoxP(X)
Definition: geo_decls.h:156
Point high
Definition: geo_decls.h:101
Datum point_horiz(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1904
void * palloc(Size size)
Definition: mcxt.c:949
double * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys)
Definition: spgproc.c:63
Datum point_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1913
#define elog(elevel,...)
Definition: elog.h:226
Oid labelType
Definition: spgist.h:47
int i
int * mapTuplesToNodes
Definition: spgist.h:128
Datum point_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1877
bool allTheSame
Definition: spgist.h:63
void * arg
Datum prefixDatum
Definition: spgist.h:123
#define PG_FUNCTION_ARGS
Definition: fmgr.h:188
Datum spg_quad_config(PG_FUNCTION_ARGS)
#define qsort(a, b, c, d)
Definition: port.h:492
Datum sk_argument
Definition: skey.h:72
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:619
#define PointPGetDatum(X)
Definition: geo_decls.h:135
static int y_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:96