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