PostgreSQL Source Code  git master
spgkdtreeproc.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * spgkdtreeproc.c
4  * implementation of k-d 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/spgkdtreeproc.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 
27 Datum
29 {
30  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
32 
33  cfg->prefixType = FLOAT8OID;
34  cfg->labelType = VOIDOID; /* we don't need node labels */
35  cfg->canReturnData = true;
36  cfg->longValuesOK = false;
38 }
39 
40 static int
41 getSide(double coord, bool isX, Point *tst)
42 {
43  double tstcoord = (isX) ? tst->x : tst->y;
44 
45  if (coord == tstcoord)
46  return 0;
47  else if (coord > tstcoord)
48  return 1;
49  else
50  return -1;
51 }
52 
53 Datum
55 {
58  Point *inPoint = DatumGetPointP(in->datum);
59  double coord;
60 
61  if (in->allTheSame)
62  elog(ERROR, "allTheSame should not occur for k-d trees");
63 
64  Assert(in->hasPrefix);
65  coord = DatumGetFloat8(in->prefixDatum);
66 
67  Assert(in->nNodes == 2);
68 
69  out->resultType = spgMatchNode;
70  out->result.matchNode.nodeN =
71  (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
72  out->result.matchNode.levelAdd = 1;
73  out->result.matchNode.restDatum = PointPGetDatum(inPoint);
74 
76 }
77 
78 typedef struct SortedPoint
79 {
80  Point *p;
81  int i;
83 
84 static int
85 x_cmp(const void *a, const void *b)
86 {
87  SortedPoint *pa = (SortedPoint *) a;
88  SortedPoint *pb = (SortedPoint *) b;
89 
90  if (pa->p->x == pb->p->x)
91  return 0;
92  return (pa->p->x > pb->p->x) ? 1 : -1;
93 }
94 
95 static int
96 y_cmp(const void *a, const void *b)
97 {
98  SortedPoint *pa = (SortedPoint *) a;
99  SortedPoint *pb = (SortedPoint *) b;
100 
101  if (pa->p->y == pb->p->y)
102  return 0;
103  return (pa->p->y > pb->p->y) ? 1 : -1;
104 }
105 
106 
107 Datum
109 {
112  int i;
113  int middle;
114  SortedPoint *sorted;
115  double coord;
116 
117  sorted = palloc(sizeof(*sorted) * in->nTuples);
118  for (i = 0; i < in->nTuples; i++)
119  {
120  sorted[i].p = DatumGetPointP(in->datums[i]);
121  sorted[i].i = i;
122  }
123 
124  qsort(sorted, in->nTuples, sizeof(*sorted),
125  (in->level % 2) ? x_cmp : y_cmp);
126  middle = in->nTuples >> 1;
127  coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
128 
129  out->hasPrefix = true;
130  out->prefixDatum = Float8GetDatum(coord);
131 
132  out->nNodes = 2;
133  out->nodeLabels = NULL; /* we don't need node labels */
134 
135  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
136  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
137 
138  /*
139  * Note: points that have coordinates exactly equal to coord may get
140  * classified into either node, depending on where they happen to fall in
141  * the sorted list. This is okay as long as the inner_consistent function
142  * descends into both sides for such cases. This is better than the
143  * alternative of trying to have an exact boundary, because it keeps the
144  * tree balanced even when we have many instances of the same point value.
145  * So we should never trigger the allTheSame logic.
146  */
147  for (i = 0; i < in->nTuples; i++)
148  {
149  Point *p = sorted[i].p;
150  int n = sorted[i].i;
151 
152  out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
153  out->leafTupleDatums[n] = PointPGetDatum(p);
154  }
155 
156  PG_RETURN_VOID();
157 }
158 
159 Datum
161 {
164  double coord;
165  int which;
166  int i;
167  BOX bboxes[2];
168 
169  Assert(in->hasPrefix);
170  coord = DatumGetFloat8(in->prefixDatum);
171 
172  if (in->allTheSame)
173  elog(ERROR, "allTheSame should not occur for k-d trees");
174 
175  Assert(in->nNodes == 2);
176 
177  /* "which" is a bitmask of children that satisfy all constraints */
178  which = (1 << 1) | (1 << 2);
179 
180  for (i = 0; i < in->nkeys; i++)
181  {
182  Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
183  BOX *boxQuery;
184 
185  switch (in->scankeys[i].sk_strategy)
186  {
188  if ((in->level % 2) != 0 && FPlt(query->x, coord))
189  which &= (1 << 1);
190  break;
192  if ((in->level % 2) != 0 && FPgt(query->x, coord))
193  which &= (1 << 2);
194  break;
196  if ((in->level % 2) != 0)
197  {
198  if (FPlt(query->x, coord))
199  which &= (1 << 1);
200  else if (FPgt(query->x, coord))
201  which &= (1 << 2);
202  }
203  else
204  {
205  if (FPlt(query->y, coord))
206  which &= (1 << 1);
207  else if (FPgt(query->y, coord))
208  which &= (1 << 2);
209  }
210  break;
213  if ((in->level % 2) == 0 && FPlt(query->y, coord))
214  which &= (1 << 1);
215  break;
218  if ((in->level % 2) == 0 && FPgt(query->y, coord))
219  which &= (1 << 2);
220  break;
222 
223  /*
224  * For this operator, the query is a box not a point. We
225  * cheat to the extent of assuming that DatumGetPointP won't
226  * do anything that would be bad for a pointer-to-box.
227  */
228  boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
229 
230  if ((in->level % 2) != 0)
231  {
232  if (FPlt(boxQuery->high.x, coord))
233  which &= (1 << 1);
234  else if (FPgt(boxQuery->low.x, coord))
235  which &= (1 << 2);
236  }
237  else
238  {
239  if (FPlt(boxQuery->high.y, coord))
240  which &= (1 << 1);
241  else if (FPgt(boxQuery->low.y, coord))
242  which &= (1 << 2);
243  }
244  break;
245  default:
246  elog(ERROR, "unrecognized strategy number: %d",
247  in->scankeys[i].sk_strategy);
248  break;
249  }
250 
251  if (which == 0)
252  break; /* no need to consider remaining conditions */
253  }
254 
255  /* We must descend into the children identified by which */
256  out->nNodes = 0;
257 
258  /* Fast-path for no matching children */
259  if (!which)
260  PG_RETURN_VOID();
261 
262  out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
263 
264  /*
265  * When ordering scan keys are specified, we've to calculate distance for
266  * them. In order to do that, we need calculate bounding boxes for both
267  * children nodes. Calculation of those bounding boxes on non-zero level
268  * require knowledge of bounding box of upper node. So, we save bounding
269  * boxes to traversalValues.
270  */
271  if (in->norderbys > 0)
272  {
273  BOX infArea;
274  BOX *area;
275 
276  out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
277  out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
278 
279  if (in->level == 0)
280  {
281  float8 inf = get_float8_infinity();
282 
283  infArea.high.x = inf;
284  infArea.high.y = inf;
285  infArea.low.x = -inf;
286  infArea.low.y = -inf;
287  area = &infArea;
288  }
289  else
290  {
291  area = (BOX *) in->traversalValue;
292  Assert(area);
293  }
294 
295  bboxes[0].low = area->low;
296  bboxes[1].high = area->high;
297 
298  if (in->level % 2)
299  {
300  /* split box by x */
301  bboxes[0].high.x = bboxes[1].low.x = coord;
302  bboxes[0].high.y = area->high.y;
303  bboxes[1].low.y = area->low.y;
304  }
305  else
306  {
307  /* split box by y */
308  bboxes[0].high.y = bboxes[1].low.y = coord;
309  bboxes[0].high.x = area->high.x;
310  bboxes[1].low.x = area->low.x;
311  }
312  }
313 
314  for (i = 1; i <= 2; i++)
315  {
316  if (which & (1 << i))
317  {
318  out->nodeNumbers[out->nNodes] = i - 1;
319 
320  if (in->norderbys > 0)
321  {
323  BOX *box = box_copy(&bboxes[i - 1]);
324 
325  MemoryContextSwitchTo(oldCtx);
326 
327  out->traversalValues[out->nNodes] = box;
328 
329  out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(box), false,
330  in->orderbys, in->norderbys);
331  }
332 
333  out->nNodes++;
334  }
335  }
336 
337  /* Set up level increments, too */
338  out->levelAdds = (int *) palloc(sizeof(int) * 2);
339  out->levelAdds[0] = 1;
340  out->levelAdds[1] = 1;
341 
342  PG_RETURN_VOID();
343 }
344 
345 /*
346  * spg_kd_leaf_consistent() is the same as spg_quad_leaf_consistent(),
347  * since we support the same operators and the same leaf data type.
348  * So we just borrow that function.
349  */
double float8
Definition: c.h:617
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
static float8 get_float8_infinity(void)
Definition: float.h:94
Datum Float8GetDatum(float8 X)
Definition: fmgr.c:1816
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
static bool FPlt(double A, double B)
Definition: geo_decls.h:59
static Point * DatumGetPointP(Datum X)
Definition: geo_decls.h:176
static BOX * DatumGetBoxP(Datum X)
Definition: geo_decls.h:234
static Datum PointPGetDatum(const Point *X)
Definition: geo_decls.h:181
static bool FPgt(double A, double B)
Definition: geo_decls.h:71
static Datum BoxPGetDatum(const BOX *X)
Definition: geo_decls.h:239
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int i
Definition: isn.c:73
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
Assert(fmt[strlen(fmt) - 1] !='\n')
void * palloc(Size size)
Definition: mcxt.c:1304
#define qsort(a, b, c, d)
Definition: port.h:449
uintptr_t Datum
Definition: postgres.h:64
static float8 DatumGetFloat8(Datum X)
Definition: postgres.h:494
MemoryContextSwitchTo(old_ctx)
@ spgMatchNode
Definition: spgist.h:69
Datum spg_kd_inner_consistent(PG_FUNCTION_ARGS)
static int x_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:85
Datum spg_kd_config(PG_FUNCTION_ARGS)
Definition: spgkdtreeproc.c:28
Datum spg_kd_choose(PG_FUNCTION_ARGS)
Definition: spgkdtreeproc.c:54
struct SortedPoint SortedPoint
static int y_cmp(const void *a, const void *b)
Definition: spgkdtreeproc.c:96
static int getSide(double coord, bool isX, Point *tst)
Definition: spgkdtreeproc.c:41
Datum spg_kd_picksplit(PG_FUNCTION_ARGS)
BOX * box_copy(BOX *orig)
Definition: spgproc.c:82
double * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys)
Definition: spgproc.c:63
#define RTLeftStrategyNumber
Definition: stratnum.h:51
#define RTRightStrategyNumber
Definition: stratnum.h:55
#define RTSameStrategyNumber
Definition: stratnum.h:56
#define RTOldBelowStrategyNumber
Definition: stratnum.h:79
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define RTOldAboveStrategyNumber
Definition: stratnum.h:80
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
Definition: geo_decls.h:141
Point low
Definition: geo_decls.h:143
Point high
Definition: geo_decls.h:142
float8 y
Definition: geo_decls.h:99
float8 x
Definition: geo_decls.h:98
Datum sk_argument
Definition: skey.h:72
StrategyNumber sk_strategy
Definition: skey.h:68
bool hasPrefix
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:62
int nNodes
Definition: spgist.h:63
Datum datum
Definition: spgist.h:55
int level
Definition: spgist.h:57
bool allTheSame
Definition: spgist.h:60
spgChooseResultType resultType
Definition: spgist.h:76
struct spgChooseOut::@49::@50 matchNode
union spgChooseOut::@49 result
bool longValuesOK
Definition: spgist.h:47
bool canReturnData
Definition: spgist.h:46
Oid labelType
Definition: spgist.h:44
Oid prefixType
Definition: spgist.h:43
void * traversalValue
Definition: spgist.h:141
ScanKey scankeys
Definition: spgist.h:134
ScanKey orderbys
Definition: spgist.h:135
MemoryContext traversalMemoryContext
Definition: spgist.h:142
void ** traversalValues
Definition: spgist.h:160
double ** distances
Definition: spgist.h:161
Datum * datums
Definition: spgist.h:113
bool hasPrefix
Definition: spgist.h:119
int * mapTuplesToNodes
Definition: spgist.h:125
Datum * nodeLabels
Definition: spgist.h:123
Datum * leafTupleDatums
Definition: spgist.h:126
Datum prefixDatum
Definition: spgist.h:120