Age Owner Branch data TLA 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-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
4502 tgl@sss.pgh.pa.us 28 :CBC 13 : spg_kd_config(PG_FUNCTION_ARGS)
29 : : {
30 : : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
31 : 13 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
32 : :
33 : 13 : cfg->prefixType = FLOAT8OID;
34 : 13 : cfg->labelType = VOIDOID; /* we don't need node labels */
4500 35 : 13 : cfg->canReturnData = true;
4502 36 : 13 : cfg->longValuesOK = false;
37 : 13 : PG_RETURN_VOID();
38 : : }
39 : :
40 : : static int
41 : 290751 : getSide(double coord, bool isX, Point *tst)
42 : : {
43 [ + + ]: 290751 : double tstcoord = (isX) ? tst->x : tst->y;
44 : :
45 [ + + ]: 290751 : if (coord == tstcoord)
46 : 16089 : return 0;
47 [ + + ]: 274662 : else if (coord > tstcoord)
48 : 71916 : return 1;
49 : : else
50 : 202746 : return -1;
51 : : }
52 : :
53 : : Datum
54 : 290751 : spg_kd_choose(PG_FUNCTION_ARGS)
55 : : {
56 : 290751 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
57 : 290751 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
58 : 290751 : Point *inPoint = DatumGetPointP(in->datum);
59 : : double coord;
60 : :
61 [ - + ]: 290751 : if (in->allTheSame)
4502 tgl@sss.pgh.pa.us 62 [ # # ]:UBC 0 : elog(ERROR, "allTheSame should not occur for k-d trees");
63 : :
4502 tgl@sss.pgh.pa.us 64 [ - + ]:CBC 290751 : Assert(in->hasPrefix);
65 : 290751 : coord = DatumGetFloat8(in->prefixDatum);
66 : :
67 [ - + ]: 290751 : Assert(in->nNodes == 2);
68 : :
69 : 290751 : out->resultType = spgMatchNode;
70 : 290751 : out->result.matchNode.nodeN =
71 : 290751 : (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
72 : 290751 : out->result.matchNode.levelAdd = 1;
73 : 290751 : out->result.matchNode.restDatum = PointPGetDatum(inPoint);
74 : :
75 : 290751 : PG_RETURN_VOID();
76 : : }
77 : :
78 : : typedef struct SortedPoint
79 : : {
80 : : Point *p;
81 : : int i;
82 : : } SortedPoint;
83 : :
84 : : static int
85 : 153813 : x_cmp(const void *a, const void *b)
86 : : {
87 : 153813 : SortedPoint *pa = (SortedPoint *) a;
88 : 153813 : SortedPoint *pb = (SortedPoint *) b;
89 : :
90 [ + + ]: 153813 : if (pa->p->x == pb->p->x)
91 : 4431 : return 0;
92 [ + + ]: 149382 : return (pa->p->x > pb->p->x) ? 1 : -1;
93 : : }
94 : :
95 : : static int
96 : 158487 : y_cmp(const void *a, const void *b)
97 : : {
98 : 158487 : SortedPoint *pa = (SortedPoint *) a;
99 : 158487 : SortedPoint *pb = (SortedPoint *) b;
100 : :
101 [ + + ]: 158487 : if (pa->p->y == pb->p->y)
102 : 2709 : return 0;
103 [ + + ]: 155778 : return (pa->p->y > pb->p->y) ? 1 : -1;
104 : : }
105 : :
106 : :
107 : : Datum
108 : 345 : spg_kd_picksplit(PG_FUNCTION_ARGS)
109 : : {
110 : 345 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
111 : 345 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
112 : : int i;
113 : : int middle;
114 : : SortedPoint *sorted;
115 : : double coord;
116 : :
117 : 345 : sorted = palloc(sizeof(*sorted) * in->nTuples);
118 [ + + ]: 53037 : for (i = 0; i < in->nTuples; i++)
119 : : {
120 : 52692 : sorted[i].p = DatumGetPointP(in->datums[i]);
121 : 52692 : sorted[i].i = i;
122 : : }
123 : :
124 [ + + ]: 345 : qsort(sorted, in->nTuples, sizeof(*sorted),
125 : : (in->level % 2) ? x_cmp : y_cmp);
126 : 345 : middle = in->nTuples >> 1;
127 [ + + ]: 345 : coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
128 : :
129 : 345 : out->hasPrefix = true;
130 : 345 : out->prefixDatum = Float8GetDatum(coord);
131 : :
132 : 345 : out->nNodes = 2;
133 : 345 : out->nodeLabels = NULL; /* we don't need node labels */
134 : :
135 : 345 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
136 : 345 : 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 [ + + ]: 53037 : for (i = 0; i < in->nTuples; i++)
148 : : {
149 : 52692 : Point *p = sorted[i].p;
150 : 52692 : int n = sorted[i].i;
151 : :
152 : 52692 : out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
153 : 52692 : out->leafTupleDatums[n] = PointPGetDatum(p);
154 : : }
155 : :
156 : 345 : PG_RETURN_VOID();
157 : : }
158 : :
159 : : Datum
160 : 3042 : spg_kd_inner_consistent(PG_FUNCTION_ARGS)
161 : : {
162 : 3042 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
163 : 3042 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
164 : : double coord;
165 : : int which;
166 : : int i;
167 : : BOX bboxes[2];
168 : :
169 [ - + ]: 3042 : Assert(in->hasPrefix);
170 : 3042 : coord = DatumGetFloat8(in->prefixDatum);
171 : :
172 [ - + ]: 3042 : if (in->allTheSame)
4502 tgl@sss.pgh.pa.us 173 [ # # ]:UBC 0 : elog(ERROR, "allTheSame should not occur for k-d trees");
174 : :
4502 tgl@sss.pgh.pa.us 175 [ - + ]:CBC 3042 : Assert(in->nNodes == 2);
176 : :
177 : : /* "which" is a bitmask of children that satisfy all constraints */
4418 178 : 3042 : which = (1 << 1) | (1 << 2);
179 : :
180 [ + + ]: 5352 : for (i = 0; i < in->nkeys; i++)
181 : : {
182 : 2310 : Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
183 : : BOX *boxQuery;
184 : :
185 [ + + + + : 2310 : switch (in->scankeys[i].sk_strategy)
+ + - ]
186 : : {
187 : 420 : case RTLeftStrategyNumber:
188 [ + + + + ]: 420 : if ((in->level % 2) != 0 && FPlt(query->x, coord))
189 : 18 : which &= (1 << 1);
190 : 420 : break;
191 : 336 : case RTRightStrategyNumber:
192 [ + + + + ]: 336 : if ((in->level % 2) != 0 && FPgt(query->x, coord))
193 : 12 : which &= (1 << 2);
194 : 336 : break;
195 : 18 : case RTSameStrategyNumber:
196 [ + + ]: 18 : if ((in->level % 2) != 0)
197 : : {
198 [ + - ]: 6 : if (FPlt(query->x, coord))
199 : 6 : which &= (1 << 1);
4418 tgl@sss.pgh.pa.us 200 [ # # ]:UBC 0 : else if (FPgt(query->x, coord))
201 : 0 : which &= (1 << 2);
202 : : }
203 : : else
204 : : {
4418 tgl@sss.pgh.pa.us 205 [ + + ]:CBC 12 : if (FPlt(query->y, coord))
206 : 6 : which &= (1 << 1);
207 [ + - ]: 6 : else if (FPgt(query->y, coord))
208 : 6 : which &= (1 << 2);
209 : : }
210 : 18 : break;
211 : 624 : case RTBelowStrategyNumber:
212 : : case RTOldBelowStrategyNumber:
213 [ + + + + ]: 624 : if ((in->level % 2) == 0 && FPlt(query->y, coord))
214 : 126 : which &= (1 << 1);
215 : 624 : break;
216 : 612 : case RTAboveStrategyNumber:
217 : : case RTOldAboveStrategyNumber:
218 [ + + + + ]: 612 : if ((in->level % 2) == 0 && FPgt(query->y, coord))
219 : 210 : which &= (1 << 2);
220 : 612 : break;
221 : 300 : case RTContainedByStrategyNumber:
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 : 300 : boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
229 : :
230 [ + + ]: 300 : if ((in->level % 2) != 0)
231 : : {
232 [ + + ]: 150 : if (FPlt(boxQuery->high.x, coord))
233 : 45 : which &= (1 << 1);
234 [ - + ]: 105 : else if (FPgt(boxQuery->low.x, coord))
4418 tgl@sss.pgh.pa.us 235 :UBC 0 : which &= (1 << 2);
236 : : }
237 : : else
238 : : {
4418 tgl@sss.pgh.pa.us 239 [ + + ]:CBC 150 : if (FPlt(boxQuery->high.y, coord))
240 : 15 : which &= (1 << 1);
241 [ + + ]: 135 : else if (FPgt(boxQuery->low.y, coord))
242 : 15 : which &= (1 << 2);
243 : : }
244 : 300 : break;
4418 tgl@sss.pgh.pa.us 245 :UBC 0 : default:
246 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
247 : : in->scankeys[i].sk_strategy);
248 : : break;
249 : : }
250 : :
4418 tgl@sss.pgh.pa.us 251 [ - + ]:CBC 2310 : if (which == 0)
4418 tgl@sss.pgh.pa.us 252 :UBC 0 : break; /* no need to consider remaining conditions */
253 : : }
254 : :
255 : : /* We must descend into the children identified by which */
4418 tgl@sss.pgh.pa.us 256 :CBC 3042 : out->nNodes = 0;
257 : :
258 : : /* Fast-path for no matching children */
2034 akorotkov@postgresql 259 [ - + ]: 3042 : if (!which)
2034 akorotkov@postgresql 260 :UBC 0 : PG_RETURN_VOID();
261 : :
2034 akorotkov@postgresql 262 :CBC 3042 : 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 [ + + ]: 3042 : if (in->norderbys > 0)
272 : : {
273 : : BOX infArea;
274 : : BOX *area;
275 : :
276 : 792 : out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
277 : 792 : out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
278 : :
279 [ + + ]: 792 : if (in->level == 0)
280 : : {
281 : 18 : float8 inf = get_float8_infinity();
282 : :
283 : 18 : infArea.high.x = inf;
284 : 18 : infArea.high.y = inf;
285 : 18 : infArea.low.x = -inf;
286 : 18 : infArea.low.y = -inf;
287 : 18 : area = &infArea;
288 : : }
289 : : else
290 : : {
291 : 774 : area = (BOX *) in->traversalValue;
292 [ - + ]: 774 : Assert(area);
293 : : }
294 : :
295 : 792 : bboxes[0].low = area->low;
296 : 792 : bboxes[1].high = area->high;
297 : :
298 [ + + ]: 792 : if (in->level % 2)
299 : : {
300 : : /* split box by x */
301 : 366 : bboxes[0].high.x = bboxes[1].low.x = coord;
302 : 366 : bboxes[0].high.y = area->high.y;
303 : 366 : bboxes[1].low.y = area->low.y;
304 : : }
305 : : else
306 : : {
307 : : /* split box by y */
308 : 426 : bboxes[0].high.y = bboxes[1].low.y = coord;
309 : 426 : bboxes[0].high.x = area->high.x;
310 : 426 : bboxes[1].low.x = area->low.x;
311 : : }
312 : : }
313 : :
4418 tgl@sss.pgh.pa.us 314 [ + + ]: 9126 : for (i = 1; i <= 2; i++)
315 : : {
316 [ + + ]: 6084 : if (which & (1 << i))
317 : : {
2034 akorotkov@postgresql 318 : 5625 : out->nodeNumbers[out->nNodes] = i - 1;
319 : :
320 [ + + ]: 5625 : if (in->norderbys > 0)
321 : : {
2026 322 : 1569 : MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
2034 323 : 1569 : BOX *box = box_copy(&bboxes[i - 1]);
324 : :
325 : 1569 : MemoryContextSwitchTo(oldCtx);
326 : :
327 : 1569 : out->traversalValues[out->nNodes] = box;
328 : :
2026 329 : 1569 : out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(box), false,
330 : : in->orderbys, in->norderbys);
331 : : }
332 : :
2034 333 : 5625 : out->nNodes++;
334 : : }
335 : : }
336 : :
337 : : /* Set up level increments, too */
4418 tgl@sss.pgh.pa.us 338 : 3042 : out->levelAdds = (int *) palloc(sizeof(int) * 2);
339 : 3042 : out->levelAdds[0] = 1;
340 : 3042 : out->levelAdds[1] = 1;
341 : :
4502 342 : 3042 : 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 : : */
|
