Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * rangetypes_spgist.c
4 : : * implementation of quad tree over ranges mapped to 2d-points for SP-GiST.
5 : : *
6 : : * Quad tree is a data structure similar to a binary tree, but is adapted to
7 : : * 2d data. Each inner node of a quad tree contains a point (centroid) which
8 : : * divides the 2d-space into 4 quadrants. Each quadrant is associated with a
9 : : * child node.
10 : : *
11 : : * Ranges are mapped to 2d-points so that the lower bound is one dimension,
12 : : * and the upper bound is another. By convention, we visualize the lower bound
13 : : * to be the horizontal axis, and upper bound the vertical axis.
14 : : *
15 : : * One quirk with this mapping is the handling of empty ranges. An empty range
16 : : * doesn't have lower and upper bounds, so it cannot be mapped to 2d space in
17 : : * a straightforward way. To cope with that, the root node can have a 5th
18 : : * quadrant, which is reserved for empty ranges. Furthermore, there can be
19 : : * inner nodes in the tree with no centroid. They contain only two child nodes,
20 : : * one for empty ranges and another for non-empty ones. Such a node can appear
21 : : * as the root node, or in the tree under the 5th child of the root node (in
22 : : * which case it will only contain empty nodes).
23 : : *
24 : : * The SP-GiST picksplit function uses medians along both axes as the centroid.
25 : : * This implementation only uses the comparison function of the range element
26 : : * datatype, therefore it works for any range type.
27 : : *
28 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
29 : : * Portions Copyright (c) 1994, Regents of the University of California
30 : : *
31 : : * IDENTIFICATION
32 : : * src/backend/utils/adt/rangetypes_spgist.c
33 : : *
34 : : *-------------------------------------------------------------------------
35 : : */
36 : :
37 : : #include "postgres.h"
38 : :
39 : : #include "access/spgist.h"
40 : : #include "access/stratnum.h"
41 : : #include "catalog/pg_type.h"
42 : : #include "utils/datum.h"
43 : : #include "utils/fmgrprotos.h"
44 : : #include "utils/rangetypes.h"
45 : :
46 : : static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid,
47 : : const RangeType *tst);
48 : : static int bound_cmp(const void *a, const void *b, void *arg);
49 : :
50 : : static int adjacent_inner_consistent(TypeCacheEntry *typcache,
51 : : const RangeBound *arg, const RangeBound *centroid,
52 : : const RangeBound *prev);
53 : : static int adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg,
54 : : const RangeBound *centroid);
55 : :
56 : : /*
57 : : * SP-GiST 'config' interface function.
58 : : */
59 : : Datum
4769 heikki.linnakangas@i 60 :CBC 55 : spg_range_quad_config(PG_FUNCTION_ARGS)
61 : : {
62 : : /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
63 : 55 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
64 : :
65 : 55 : cfg->prefixType = ANYRANGEOID;
66 : 55 : cfg->labelType = VOIDOID; /* we don't need node labels */
67 : 55 : cfg->canReturnData = true;
68 : 55 : cfg->longValuesOK = false;
69 : 55 : PG_RETURN_VOID();
70 : : }
71 : :
72 : : /*----------
73 : : * Determine which quadrant a 2d-mapped range falls into, relative to the
74 : : * centroid.
75 : : *
76 : : * Quadrants are numbered like this:
77 : : *
78 : : * 4 | 1
79 : : * ----+----
80 : : * 3 | 2
81 : : *
82 : : * Where the lower bound of range is the horizontal axis and upper bound the
83 : : * vertical axis.
84 : : *
85 : : * Ranges on one of the axes are taken to lie in the quadrant with higher value
86 : : * along perpendicular axis. That is, a value on the horizontal axis is taken
87 : : * to belong to quadrant 1 or 4, and a value on the vertical axis is taken to
88 : : * belong to quadrant 1 or 2. A range equal to centroid is taken to lie in
89 : : * quadrant 1.
90 : : *
91 : : * Empty ranges are taken to lie in the special quadrant 5.
92 : : *----------
93 : : */
94 : : static int16
2137 peter@eisentraut.org 95 : 379467 : getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
96 : : {
97 : : RangeBound centroidLower,
98 : : centroidUpper;
99 : : bool centroidEmpty;
100 : : RangeBound lower,
101 : : upper;
102 : : bool empty;
103 : :
4769 heikki.linnakangas@i 104 : 379467 : range_deserialize(typcache, centroid, ¢roidLower, ¢roidUpper,
105 : : ¢roidEmpty);
106 : 379467 : range_deserialize(typcache, tst, &lower, &upper, &empty);
107 : :
108 [ + + ]: 379467 : if (empty)
109 : 6000 : return 5;
110 : :
111 [ + + ]: 373467 : if (range_cmp_bounds(typcache, &lower, ¢roidLower) >= 0)
112 : : {
113 [ + + ]: 340197 : if (range_cmp_bounds(typcache, &upper, ¢roidUpper) >= 0)
114 : 339849 : return 1;
115 : : else
116 : 348 : return 2;
117 : : }
118 : : else
119 : : {
120 [ + + ]: 33270 : if (range_cmp_bounds(typcache, &upper, ¢roidUpper) >= 0)
121 : 7305 : return 4;
122 : : else
123 : 25965 : return 3;
124 : : }
125 : : }
126 : :
127 : : /*
128 : : * Choose SP-GiST function: choose path for addition of new range.
129 : : */
130 : : Datum
131 : 357472 : spg_range_quad_choose(PG_FUNCTION_ARGS)
132 : : {
133 : 357472 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
134 : 357472 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
2910 tgl@sss.pgh.pa.us 135 : 357472 : RangeType *inRange = DatumGetRangeTypeP(in->datum),
136 : : *centroid;
137 : : int16 quadrant;
138 : : TypeCacheEntry *typcache;
139 : :
4769 heikki.linnakangas@i 140 [ + + ]: 357472 : if (in->allTheSame)
141 : : {
142 : 6565 : out->resultType = spgMatchNode;
143 : : /* nodeN will be set by core */
144 : 6565 : out->result.matchNode.levelAdd = 0;
2910 tgl@sss.pgh.pa.us 145 : 6565 : out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
4769 heikki.linnakangas@i 146 : 6565 : PG_RETURN_VOID();
147 : : }
148 : :
149 : 350907 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(inRange));
150 : :
151 : : /*
152 : : * A node with no centroid divides ranges purely on whether they're empty
153 : : * or not. All empty ranges go to child node 0, all non-empty ranges go to
154 : : * node 1.
155 : : */
156 [ - + ]: 350907 : if (!in->hasPrefix)
157 : : {
4769 heikki.linnakangas@i 158 :UBC 0 : out->resultType = spgMatchNode;
159 [ # # ]: 0 : if (RangeIsEmpty(inRange))
160 : 0 : out->result.matchNode.nodeN = 0;
161 : : else
162 : 0 : out->result.matchNode.nodeN = 1;
163 : 0 : out->result.matchNode.levelAdd = 1;
2910 tgl@sss.pgh.pa.us 164 : 0 : out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
4769 heikki.linnakangas@i 165 : 0 : PG_RETURN_VOID();
166 : : }
167 : :
2910 tgl@sss.pgh.pa.us 168 :CBC 350907 : centroid = DatumGetRangeTypeP(in->prefixDatum);
4769 heikki.linnakangas@i 169 : 350907 : quadrant = getQuadrant(typcache, centroid, inRange);
170 : :
171 [ - + ]: 350907 : Assert(quadrant <= in->nNodes);
172 : :
173 : : /* Select node matching to quadrant number */
174 : 350907 : out->resultType = spgMatchNode;
175 : 350907 : out->result.matchNode.nodeN = quadrant - 1;
176 : 350907 : out->result.matchNode.levelAdd = 1;
2910 tgl@sss.pgh.pa.us 177 : 350907 : out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
178 : :
4769 heikki.linnakangas@i 179 : 350907 : PG_RETURN_VOID();
180 : : }
181 : :
182 : : /*
183 : : * Bound comparison for sorting.
184 : : */
185 : : static int
186 : 352262 : bound_cmp(const void *a, const void *b, void *arg)
187 : : {
188 : 352262 : RangeBound *ba = (RangeBound *) a;
189 : 352262 : RangeBound *bb = (RangeBound *) b;
190 : 352262 : TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
191 : :
192 : 352262 : return range_cmp_bounds(typcache, ba, bb);
193 : : }
194 : :
195 : : /*
196 : : * Picksplit SP-GiST function: split ranges into nodes. Select "centroid"
197 : : * range and distribute ranges according to quadrants.
198 : : */
199 : : Datum
200 : 245 : spg_range_quad_picksplit(PG_FUNCTION_ARGS)
201 : : {
202 : 245 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
203 : 245 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
204 : : int i;
205 : : int j;
206 : : int nonEmptyCount;
207 : : RangeType *centroid;
208 : : bool empty;
209 : : TypeCacheEntry *typcache;
210 : :
211 : : /* Use the median values of lower and upper bounds as the centroid range */
212 : : RangeBound *lowerBounds,
213 : : *upperBounds;
214 : :
215 : 245 : typcache = range_get_typcache(fcinfo,
2910 tgl@sss.pgh.pa.us 216 : 245 : RangeTypeGetOid(DatumGetRangeTypeP(in->datums[0])));
217 : :
218 : : /* Allocate memory for bounds */
4769 heikki.linnakangas@i 219 : 245 : lowerBounds = palloc(sizeof(RangeBound) * in->nTuples);
220 : 245 : upperBounds = palloc(sizeof(RangeBound) * in->nTuples);
221 : 245 : j = 0;
222 : :
223 : : /* Deserialize bounds of ranges, count non-empty ranges */
224 [ + + ]: 32353 : for (i = 0; i < in->nTuples; i++)
225 : : {
2910 tgl@sss.pgh.pa.us 226 : 32108 : range_deserialize(typcache, DatumGetRangeTypeP(in->datums[i]),
4769 heikki.linnakangas@i 227 : 32108 : &lowerBounds[j], &upperBounds[j], &empty);
228 [ + + ]: 32108 : if (!empty)
229 : 28548 : j++;
230 : : }
231 : 245 : nonEmptyCount = j;
232 : :
233 : : /*
234 : : * All the ranges are empty. The best we can do is to construct an inner
235 : : * node with no centroid, and put all ranges into node 0. If non-empty
236 : : * ranges are added later, they will be routed to node 1.
237 : : */
238 [ + + ]: 245 : if (nonEmptyCount == 0)
239 : : {
240 : 39 : out->nNodes = 2;
241 : 39 : out->hasPrefix = false;
242 : : /* Prefix is empty */
243 : 39 : out->prefixDatum = PointerGetDatum(NULL);
244 : 39 : out->nodeLabels = NULL;
245 : :
246 : 39 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
247 : 39 : out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
248 : :
249 : : /* Place all ranges into node 0 */
250 [ + + ]: 3599 : for (i = 0; i < in->nTuples; i++)
251 : : {
2910 tgl@sss.pgh.pa.us 252 : 3560 : RangeType *range = DatumGetRangeTypeP(in->datums[i]);
253 : :
254 : 3560 : out->leafTupleDatums[i] = RangeTypePGetDatum(range);
4769 heikki.linnakangas@i 255 : 3560 : out->mapTuplesToNodes[i] = 0;
256 : : }
257 : 39 : PG_RETURN_VOID();
258 : : }
259 : :
260 : : /* Sort range bounds in order to find medians */
261 : 206 : qsort_arg(lowerBounds, nonEmptyCount, sizeof(RangeBound),
262 : : bound_cmp, typcache);
263 : 206 : qsort_arg(upperBounds, nonEmptyCount, sizeof(RangeBound),
264 : : bound_cmp, typcache);
265 : :
266 : : /* Construct "centroid" range from medians of lower and upper bounds */
267 : 206 : centroid = range_serialize(typcache, &lowerBounds[nonEmptyCount / 2],
996 tgl@sss.pgh.pa.us 268 : 206 : &upperBounds[nonEmptyCount / 2], false, NULL);
4769 heikki.linnakangas@i 269 : 206 : out->hasPrefix = true;
2910 tgl@sss.pgh.pa.us 270 : 206 : out->prefixDatum = RangeTypePGetDatum(centroid);
271 : :
272 : : /* Create node for empty ranges only if it is a root node */
4769 heikki.linnakangas@i 273 [ + + ]: 206 : out->nNodes = (in->level == 0) ? 5 : 4;
274 : 206 : out->nodeLabels = NULL; /* we don't need node labels */
275 : :
276 : 206 : out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
277 : 206 : out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
278 : :
279 : : /*
280 : : * Assign ranges to corresponding nodes according to quadrants relative to
281 : : * "centroid" range.
282 : : */
283 [ + + ]: 28754 : for (i = 0; i < in->nTuples; i++)
284 : : {
2910 tgl@sss.pgh.pa.us 285 : 28548 : RangeType *range = DatumGetRangeTypeP(in->datums[i]);
4769 heikki.linnakangas@i 286 : 28548 : int16 quadrant = getQuadrant(typcache, centroid, range);
287 : :
2910 tgl@sss.pgh.pa.us 288 : 28548 : out->leafTupleDatums[i] = RangeTypePGetDatum(range);
4769 heikki.linnakangas@i 289 : 28548 : out->mapTuplesToNodes[i] = quadrant - 1;
290 : : }
291 : :
292 : 206 : PG_RETURN_VOID();
293 : : }
294 : :
295 : : /*
296 : : * SP-GiST consistent function for inner nodes: check which nodes are
297 : : * consistent with given set of queries.
298 : : */
299 : : Datum
300 : 906 : spg_range_quad_inner_consistent(PG_FUNCTION_ARGS)
301 : : {
302 : 906 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
303 : 906 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
304 : : int which;
305 : : int i;
306 : : MemoryContext oldCtx;
307 : :
308 : : /*
309 : : * For adjacent search we need also previous centroid (if any) to improve
310 : : * the precision of the consistent check. In this case needPrevious flag
311 : : * is set and centroid is passed into traversalValue.
312 : : */
4565 313 : 906 : bool needPrevious = false;
314 : :
4769 315 [ + + ]: 906 : if (in->allTheSame)
316 : : {
317 : : /* Report that all nodes should be visited */
318 : 78 : out->nNodes = in->nNodes;
319 : 78 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
320 [ + + ]: 702 : for (i = 0; i < in->nNodes; i++)
321 : 624 : out->nodeNumbers[i] = i;
322 : 78 : PG_RETURN_VOID();
323 : : }
324 : :
325 [ - + ]: 828 : if (!in->hasPrefix)
326 : : {
327 : : /*
328 : : * No centroid on this inner node. Such a node has two child nodes,
329 : : * the first for empty ranges, and the second for non-empty ones.
330 : : */
4769 heikki.linnakangas@i 331 [ # # ]:UBC 0 : Assert(in->nNodes == 2);
332 : :
333 : : /*
334 : : * Nth bit of which variable means that (N - 1)th node should be
335 : : * visited. Initially all bits are set. Bits of nodes which should be
336 : : * skipped will be unset.
337 : : */
338 : 0 : which = (1 << 1) | (1 << 2);
339 [ # # ]: 0 : for (i = 0; i < in->nkeys; i++)
340 : : {
341 : 0 : StrategyNumber strategy = in->scankeys[i].sk_strategy;
342 : : bool empty;
343 : :
344 : : /*
345 : : * The only strategy when second argument of operator is not range
346 : : * is RANGESTRAT_CONTAINS_ELEM.
347 : : */
348 [ # # ]: 0 : if (strategy != RANGESTRAT_CONTAINS_ELEM)
2046 alvherre@alvh.no-ip. 349 : 0 : empty = RangeIsEmpty(DatumGetRangeTypeP(in->scankeys[i].sk_argument));
350 : : else
4769 heikki.linnakangas@i 351 : 0 : empty = false;
352 : :
353 [ # # # # : 0 : switch (strategy)
# # ]
354 : : {
355 : 0 : case RANGESTRAT_BEFORE:
356 : : case RANGESTRAT_OVERLEFT:
357 : : case RANGESTRAT_OVERLAPS:
358 : : case RANGESTRAT_OVERRIGHT:
359 : : case RANGESTRAT_AFTER:
360 : : case RANGESTRAT_ADJACENT:
361 : : /* These strategies return false if any argument is empty */
362 [ # # ]: 0 : if (empty)
363 : 0 : which = 0;
364 : : else
365 : 0 : which &= (1 << 2);
366 : 0 : break;
367 : :
368 : 0 : case RANGESTRAT_CONTAINS:
369 : :
370 : : /*
371 : : * All ranges contain an empty range. Only non-empty
372 : : * ranges can contain a non-empty range.
373 : : */
374 [ # # ]: 0 : if (!empty)
375 : 0 : which &= (1 << 2);
376 : 0 : break;
377 : :
378 : 0 : case RANGESTRAT_CONTAINED_BY:
379 : :
380 : : /*
381 : : * Only an empty range is contained by an empty range.
382 : : * Both empty and non-empty ranges can be contained by a
383 : : * non-empty range.
384 : : */
385 [ # # ]: 0 : if (empty)
386 : 0 : which &= (1 << 1);
387 : 0 : break;
388 : :
389 : 0 : case RANGESTRAT_CONTAINS_ELEM:
390 : 0 : which &= (1 << 2);
391 : 0 : break;
392 : :
393 : 0 : case RANGESTRAT_EQ:
394 [ # # ]: 0 : if (empty)
395 : 0 : which &= (1 << 1);
396 : : else
397 : 0 : which &= (1 << 2);
398 : 0 : break;
399 : :
400 : 0 : default:
401 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
402 : : break;
403 : : }
404 [ # # ]: 0 : if (which == 0)
405 : 0 : break; /* no need to consider remaining conditions */
406 : : }
407 : : }
408 : : else
409 : : {
410 : : RangeBound centroidLower,
411 : : centroidUpper;
412 : : bool centroidEmpty;
413 : : TypeCacheEntry *typcache;
414 : : RangeType *centroid;
415 : :
416 : : /* This node has a centroid. Fetch it. */
2910 tgl@sss.pgh.pa.us 417 :CBC 828 : centroid = DatumGetRangeTypeP(in->prefixDatum);
4769 heikki.linnakangas@i 418 : 828 : typcache = range_get_typcache(fcinfo,
419 : : RangeTypeGetOid(centroid));
420 : 828 : range_deserialize(typcache, centroid, ¢roidLower, ¢roidUpper,
421 : : ¢roidEmpty);
422 : :
423 [ + + - + ]: 828 : Assert(in->nNodes == 4 || in->nNodes == 5);
424 : :
425 : : /*
426 : : * Nth bit of which variable means that (N - 1)th node (Nth quadrant)
427 : : * should be visited. Initially all bits are set. Bits of nodes which
428 : : * can be skipped will be unset.
429 : : */
430 : 828 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
431 : :
432 [ + + ]: 1656 : for (i = 0; i < in->nkeys; i++)
433 : : {
434 : : StrategyNumber strategy;
435 : : RangeBound lower,
436 : : upper;
437 : : bool empty;
tgl@sss.pgh.pa.us 438 : 828 : RangeType *range = NULL;
439 : :
4070 heikki.linnakangas@i 440 : 828 : RangeType *prevCentroid = NULL;
441 : : RangeBound prevLower,
442 : : prevUpper;
443 : : bool prevEmpty;
444 : :
445 : : /* Restrictions on range bounds according to scan strategy */
4769 446 : 828 : RangeBound *minLower = NULL,
447 : 828 : *maxLower = NULL,
448 : 828 : *minUpper = NULL,
449 : 828 : *maxUpper = NULL;
450 : :
451 : : /* Are the restrictions on range bounds inclusive? */
452 : 828 : bool inclusive = true;
453 : 828 : bool strictEmpty = true;
454 : : int cmp,
455 : : which1,
456 : : which2;
457 : :
458 : 828 : strategy = in->scankeys[i].sk_strategy;
459 : :
460 : : /*
461 : : * RANGESTRAT_CONTAINS_ELEM is just like RANGESTRAT_CONTAINS, but
462 : : * the argument is a single element. Expand the single element to
463 : : * a range containing only the element, and treat it like
464 : : * RANGESTRAT_CONTAINS.
465 : : */
466 [ + + ]: 828 : if (strategy == RANGESTRAT_CONTAINS_ELEM)
467 : : {
468 : 24 : lower.inclusive = true;
469 : 24 : lower.infinite = false;
470 : 24 : lower.lower = true;
471 : 24 : lower.val = in->scankeys[i].sk_argument;
472 : :
473 : 24 : upper.inclusive = true;
474 : 24 : upper.infinite = false;
475 : 24 : upper.lower = false;
476 : 24 : upper.val = in->scankeys[i].sk_argument;
477 : :
478 : 24 : empty = false;
479 : :
480 : 24 : strategy = RANGESTRAT_CONTAINS;
481 : : }
482 : : else
483 : : {
2910 tgl@sss.pgh.pa.us 484 : 804 : range = DatumGetRangeTypeP(in->scankeys[i].sk_argument);
4769 heikki.linnakangas@i 485 : 804 : range_deserialize(typcache, range, &lower, &upper, &empty);
486 : : }
487 : :
488 : : /*
489 : : * Most strategies are handled by forming a bounding box from the
490 : : * search key, defined by a minLower, maxLower, minUpper,
491 : : * maxUpper. Some modify 'which' directly, to specify exactly
492 : : * which quadrants need to be visited.
493 : : *
494 : : * For most strategies, nothing matches an empty search key, and
495 : : * an empty range never matches a non-empty key. If a strategy
496 : : * does not behave like that wrt. empty ranges, set strictEmpty to
497 : : * false.
498 : : */
499 [ + + + + : 828 : switch (strategy)
+ + + + +
- ]
500 : : {
501 : 12 : case RANGESTRAT_BEFORE:
502 : :
503 : : /*
504 : : * Range A is before range B if upper bound of A is lower
505 : : * than lower bound of B.
506 : : */
507 : 12 : maxUpper = &lower;
508 : 12 : inclusive = false;
509 : 12 : break;
510 : :
511 : 66 : case RANGESTRAT_OVERLEFT:
512 : :
513 : : /*
514 : : * Range A is overleft to range B if upper bound of A is
515 : : * less than or equal to upper bound of B.
516 : : */
517 : 66 : maxUpper = &upper;
518 : 66 : break;
519 : :
520 : 24 : case RANGESTRAT_OVERLAPS:
521 : :
522 : : /*
523 : : * Non-empty ranges overlap, if lower bound of each range
524 : : * is lower or equal to upper bound of the other range.
525 : : */
526 : 24 : maxLower = &upper;
527 : 24 : minUpper = &lower;
528 : 24 : break;
529 : :
530 : 200 : case RANGESTRAT_OVERRIGHT:
531 : :
532 : : /*
533 : : * Range A is overright to range B if lower bound of A is
534 : : * greater than or equal to lower bound of B.
535 : : */
536 : 200 : minLower = &lower;
537 : 200 : break;
538 : :
539 : 182 : case RANGESTRAT_AFTER:
540 : :
541 : : /*
542 : : * Range A is after range B if lower bound of A is greater
543 : : * than upper bound of B.
544 : : */
545 : 182 : minLower = &upper;
546 : 182 : inclusive = false;
547 : 182 : break;
548 : :
4565 549 : 66 : case RANGESTRAT_ADJACENT:
550 [ - + ]: 66 : if (empty)
4483 bruce@momjian.us 551 :UBC 0 : break; /* Skip to strictEmpty check. */
552 : :
553 : : /*
554 : : * Previously selected quadrant could exclude possibility
555 : : * for lower or upper bounds to be adjacent. Deserialize
556 : : * previous centroid range if present for checking this.
557 : : */
2849 tgl@sss.pgh.pa.us 558 [ + + ]:CBC 66 : if (in->traversalValue)
559 : : {
1105 peter@eisentraut.org 560 : 57 : prevCentroid = in->traversalValue;
4565 heikki.linnakangas@i 561 : 57 : range_deserialize(typcache, prevCentroid,
562 : : &prevLower, &prevUpper, &prevEmpty);
563 : : }
564 : :
565 : : /*
566 : : * For a range's upper bound to be adjacent to the
567 : : * argument's lower bound, it will be found along the line
568 : : * adjacent to (and just below) Y=lower. Therefore, if the
569 : : * argument's lower bound is less than the centroid's
570 : : * upper bound, the line falls in quadrants 2 and 3; if
571 : : * greater, the line falls in quadrants 1 and 4. (see
572 : : * adjacent_cmp_bounds for description of edge cases).
573 : : */
4070 574 [ + + ]: 66 : cmp = adjacent_inner_consistent(typcache, &lower,
575 : : ¢roidUpper,
576 : : prevCentroid ? &prevUpper : NULL);
577 [ + + ]: 66 : if (cmp > 0)
578 : 6 : which1 = (1 << 1) | (1 << 4);
579 [ + + ]: 60 : else if (cmp < 0)
580 : 15 : which1 = (1 << 2) | (1 << 3);
581 : : else
582 : 45 : which1 = 0;
583 : :
584 : : /*
585 : : * Also search for ranges's adjacent to argument's upper
586 : : * bound. They will be found along the line adjacent to
587 : : * (and just right of) X=upper, which falls in quadrants 3
588 : : * and 4, or 1 and 2.
589 : : */
590 [ + + ]: 66 : cmp = adjacent_inner_consistent(typcache, &upper,
591 : : ¢roidLower,
592 : : prevCentroid ? &prevLower : NULL);
593 [ + + ]: 66 : if (cmp > 0)
594 : 39 : which2 = (1 << 1) | (1 << 2);
595 [ + + ]: 27 : else if (cmp < 0)
596 : 21 : which2 = (1 << 3) | (1 << 4);
597 : : else
598 : 6 : which2 = 0;
599 : :
600 : : /* We must chase down ranges adjacent to either bound. */
4565 601 : 66 : which &= which1 | which2;
602 : :
603 : 66 : needPrevious = true;
604 : 66 : break;
605 : :
4769 606 : 254 : case RANGESTRAT_CONTAINS:
607 : :
608 : : /*
609 : : * Non-empty range A contains non-empty range B if lower
610 : : * bound of A is lower or equal to lower bound of range B
611 : : * and upper bound of range A is greater than or equal to
612 : : * upper bound of range A.
613 : : *
614 : : * All non-empty ranges contain an empty range.
615 : : */
616 : 254 : strictEmpty = false;
617 [ + + ]: 254 : if (!empty)
618 : : {
619 : 48 : which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
620 : 48 : maxLower = &lower;
621 : 48 : minUpper = &upper;
622 : : }
623 : 254 : break;
624 : :
625 : 12 : case RANGESTRAT_CONTAINED_BY:
626 : : /* The opposite of contains. */
627 : 12 : strictEmpty = false;
628 [ - + ]: 12 : if (empty)
629 : : {
630 : : /* An empty range is only contained by an empty range */
4769 heikki.linnakangas@i 631 :UBC 0 : which &= (1 << 5);
632 : : }
633 : : else
634 : : {
4769 heikki.linnakangas@i 635 :CBC 12 : minLower = &lower;
636 : 12 : maxUpper = &upper;
637 : : }
638 : 12 : break;
639 : :
640 : 12 : case RANGESTRAT_EQ:
641 : :
642 : : /*
643 : : * Equal range can be only in the same quadrant where
644 : : * argument would be placed to.
645 : : */
646 : 12 : strictEmpty = false;
647 : 12 : which &= (1 << getQuadrant(typcache, centroid, range));
648 : 12 : break;
649 : :
4769 heikki.linnakangas@i 650 :UBC 0 : default:
651 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
652 : : break;
653 : : }
654 : :
4769 heikki.linnakangas@i 655 [ + + ]:CBC 828 : if (strictEmpty)
656 : : {
657 [ - + ]: 550 : if (empty)
658 : : {
659 : : /* Scan key is empty, no branches are satisfying */
4769 heikki.linnakangas@i 660 :UBC 0 : which = 0;
661 : 0 : break;
662 : : }
663 : : else
664 : : {
665 : : /* Shouldn't visit tree branch with empty ranges */
4769 heikki.linnakangas@i 666 :CBC 550 : which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
667 : : }
668 : : }
669 : :
670 : : /*
671 : : * Using the bounding box, see which quadrants we have to descend
672 : : * into.
673 : : */
674 [ + + ]: 828 : if (minLower)
675 : : {
676 : : /*
677 : : * If the centroid's lower bound is less than or equal to the
678 : : * minimum lower bound, anything in the 3rd and 4th quadrants
679 : : * will have an even smaller lower bound, and thus can't
680 : : * match.
681 : : */
682 [ + + ]: 394 : if (range_cmp_bounds(typcache, ¢roidLower, minLower) <= 0)
683 : 48 : which &= (1 << 1) | (1 << 2) | (1 << 5);
684 : : }
685 [ + + ]: 828 : if (maxLower)
686 : : {
687 : : /*
688 : : * If the centroid's lower bound is greater than the maximum
689 : : * lower bound, anything in the 1st and 2nd quadrants will
690 : : * also have a greater than or equal lower bound, and thus
691 : : * can't match. If the centroid's lower bound is equal to the
692 : : * maximum lower bound, we can still exclude the 1st and 2nd
693 : : * quadrants if we're looking for a value strictly greater
694 : : * than the maximum.
695 : : */
696 : :
697 : 72 : cmp = range_cmp_bounds(typcache, ¢roidLower, maxLower);
698 [ + + - + : 72 : if (cmp > 0 || (!inclusive && cmp == 0))
- - ]
699 : 54 : which &= (1 << 3) | (1 << 4) | (1 << 5);
700 : : }
701 [ + + ]: 828 : if (minUpper)
702 : : {
703 : : /*
704 : : * If the centroid's upper bound is less than or equal to the
705 : : * minimum upper bound, anything in the 2nd and 3rd quadrants
706 : : * will have an even smaller upper bound, and thus can't
707 : : * match.
708 : : */
709 [ - + ]: 72 : if (range_cmp_bounds(typcache, ¢roidUpper, minUpper) <= 0)
4769 heikki.linnakangas@i 710 :UBC 0 : which &= (1 << 1) | (1 << 4) | (1 << 5);
711 : : }
4769 heikki.linnakangas@i 712 [ + + ]:CBC 828 : if (maxUpper)
713 : : {
714 : : /*
715 : : * If the centroid's upper bound is greater than the maximum
716 : : * upper bound, anything in the 1st and 4th quadrants will
717 : : * also have a greater than or equal upper bound, and thus
718 : : * can't match. If the centroid's upper bound is equal to the
719 : : * maximum upper bound, we can still exclude the 1st and 4th
720 : : * quadrants if we're looking for a value strictly greater
721 : : * than the maximum.
722 : : */
723 : :
724 : 90 : cmp = range_cmp_bounds(typcache, ¢roidUpper, maxUpper);
725 [ + + + + : 90 : if (cmp > 0 || (!inclusive && cmp == 0))
- + ]
726 : 42 : which &= (1 << 2) | (1 << 3) | (1 << 5);
727 : : }
728 : :
729 [ - + ]: 828 : if (which == 0)
4769 heikki.linnakangas@i 730 :UBC 0 : break; /* no need to consider remaining conditions */
731 : : }
732 : : }
733 : :
734 : : /* We must descend into the quadrant(s) identified by 'which' */
4769 heikki.linnakangas@i 735 :CBC 828 : out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
4565 736 [ + + ]: 828 : if (needPrevious)
3447 teodor@sigaev.ru 737 : 66 : out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
4769 heikki.linnakangas@i 738 : 828 : out->nNodes = 0;
739 : :
740 : : /*
741 : : * Elements of traversalValues should be allocated in
742 : : * traversalMemoryContext
743 : : */
3447 teodor@sigaev.ru 744 : 828 : oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
745 : :
4769 heikki.linnakangas@i 746 [ + + ]: 4209 : for (i = 1; i <= in->nNodes; i++)
747 : : {
748 [ + + ]: 3381 : if (which & (1 << i))
749 : : {
750 : : /* Save previous prefix if needed */
4565 751 [ + + ]: 2883 : if (needPrevious)
752 : : {
753 : : Datum previousCentroid;
754 : :
755 : : /*
756 : : * We know, that in->prefixDatum in this place is varlena,
757 : : * because it's range
758 : : */
3447 teodor@sigaev.ru 759 : 147 : previousCentroid = datumCopy(in->prefixDatum, false, -1);
29 peter@eisentraut.org 760 :GNC 147 : out->traversalValues[out->nNodes] = DatumGetPointer(previousCentroid);
761 : : }
3447 teodor@sigaev.ru 762 :CBC 2883 : out->nodeNumbers[out->nNodes] = i - 1;
763 : 2883 : out->nNodes++;
764 : : }
765 : : }
766 : :
767 : 828 : MemoryContextSwitchTo(oldCtx);
768 : :
4769 heikki.linnakangas@i 769 : 828 : PG_RETURN_VOID();
770 : : }
771 : :
772 : : /*
773 : : * adjacent_cmp_bounds
774 : : *
775 : : * Given an argument and centroid bound, this function determines if any
776 : : * bounds that are adjacent to the argument are smaller than, or greater than
777 : : * or equal to centroid. For brevity, we call the arg < centroid "left", and
778 : : * arg >= centroid case "right". This corresponds to how the quadrants are
779 : : * arranged, if you imagine that "left" is equivalent to "down" and "right"
780 : : * is equivalent to "up".
781 : : *
782 : : * For the "left" case, returns -1, and for the "right" case, returns 1.
783 : : */
784 : : static int
2137 peter@eisentraut.org 785 : 195 : adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg,
786 : : const RangeBound *centroid)
787 : : {
788 : : int cmp;
789 : :
4070 heikki.linnakangas@i 790 [ - + ]: 195 : Assert(arg->lower != centroid->lower);
791 : :
3759 bruce@momjian.us 792 : 195 : cmp = range_cmp_bounds(typcache, arg, centroid);
793 : :
4070 heikki.linnakangas@i 794 [ + + ]: 195 : if (centroid->lower)
795 : : {
796 : : /*------
797 : : * The argument is an upper bound, we are searching for adjacent lower
798 : : * bounds. A matching adjacent lower bound must be *larger* than the
799 : : * argument, but only just.
800 : : *
801 : : * The following table illustrates the desired result with a fixed
802 : : * argument bound, and different centroids. The CMP column shows
803 : : * the value of 'cmp' variable, and ADJ shows whether the argument
804 : : * and centroid are adjacent, per bounds_adjacent(). (N) means we
805 : : * don't need to check for that case, because it's implied by CMP.
806 : : * With the argument range [..., 500), the adjacent range we're
807 : : * searching for is [500, ...):
808 : : *
809 : : * ARGUMENT CENTROID CMP ADJ
810 : : * [..., 500) [498, ...) > (N) [500, ...) is to the right
811 : : * [..., 500) [499, ...) = (N) [500, ...) is to the right
812 : : * [..., 500) [500, ...) < Y [500, ...) is to the right
813 : : * [..., 500) [501, ...) < N [500, ...) is to the left
814 : : *
815 : : * So, we must search left when the argument is smaller than, and not
816 : : * adjacent, to the centroid. Otherwise search right.
817 : : *------
818 : : */
819 [ + + + - ]: 117 : if (cmp < 0 && !bounds_adjacent(typcache, *arg, *centroid))
820 : 36 : return -1;
821 : : else
822 : 81 : return 1;
823 : : }
824 : : else
825 : : {
826 : : /*------
827 : : * The argument is a lower bound, we are searching for adjacent upper
828 : : * bounds. A matching adjacent upper bound must be *smaller* than the
829 : : * argument, but only just.
830 : : *
831 : : * ARGUMENT CENTROID CMP ADJ
832 : : * [500, ...) [..., 499) > (N) [..., 500) is to the right
833 : : * [500, ...) [..., 500) > (Y) [..., 500) is to the right
834 : : * [500, ...) [..., 501) = (N) [..., 500) is to the left
835 : : * [500, ...) [..., 502) < (N) [..., 500) is to the left
836 : : *
837 : : * We must search left when the argument is smaller than or equal to
838 : : * the centroid. Otherwise search right. We don't need to check
839 : : * whether the argument is adjacent with the centroid, because it
840 : : * doesn't matter.
841 : : *------
842 : : */
843 [ + + ]: 78 : if (cmp <= 0)
844 : 72 : return -1;
845 : : else
846 : 6 : return 1;
847 : : }
848 : : }
849 : :
850 : : /*----------
851 : : * adjacent_inner_consistent
852 : : *
853 : : * Like adjacent_cmp_bounds, but also takes into account the previous
854 : : * level's centroid. We might've traversed left (or right) at the previous
855 : : * node, in search for ranges adjacent to the other bound, even though we
856 : : * already ruled out the possibility for any matches in that direction for
857 : : * this bound. By comparing the argument with the previous centroid, and
858 : : * the previous centroid with the current centroid, we can determine which
859 : : * direction we should've moved in at previous level, and which direction we
860 : : * actually moved.
861 : : *
862 : : * If there can be any matches to the left, returns -1. If to the right,
863 : : * returns 1. If there can be no matches below this centroid, because we
864 : : * already ruled them out at the previous level, returns 0.
865 : : *
866 : : * XXX: Comparing just the previous and current level isn't foolproof; we
867 : : * might still search some branches unnecessarily. For example, imagine that
868 : : * we are searching for value 15, and we traverse the following centroids
869 : : * (only considering one bound for the moment):
870 : : *
871 : : * Level 1: 20
872 : : * Level 2: 50
873 : : * Level 3: 25
874 : : *
875 : : * At this point, previous centroid is 50, current centroid is 25, and the
876 : : * target value is to the left. But because we already moved right from
877 : : * centroid 20 to 50 in the first level, there cannot be any values < 20 in
878 : : * the current branch. But we don't know that just by looking at the previous
879 : : * and current centroid, so we traverse left, unnecessarily. The reason we are
880 : : * down this branch is that we're searching for matches with the *other*
881 : : * bound. If we kept track of which bound we are searching for explicitly,
882 : : * instead of deducing that from the previous and current centroid, we could
883 : : * avoid some unnecessary work.
884 : : *----------
885 : : */
886 : : static int
2137 peter@eisentraut.org 887 : 132 : adjacent_inner_consistent(TypeCacheEntry *typcache, const RangeBound *arg,
888 : : const RangeBound *centroid, const RangeBound *prev)
889 : : {
4070 heikki.linnakangas@i 890 [ + + ]: 132 : if (prev)
891 : : {
892 : : int prevcmp;
893 : : int cmp;
894 : :
895 : : /*
896 : : * Which direction were we supposed to traverse at previous level,
897 : : * left or right?
898 : : */
899 : 114 : prevcmp = adjacent_cmp_bounds(typcache, arg, prev);
900 : :
901 : : /* and which direction did we actually go? */
902 : 114 : cmp = range_cmp_bounds(typcache, centroid, prev);
903 : :
904 : : /* if the two don't agree, there's nothing to see here */
905 [ + + + + : 114 : if ((prevcmp < 0 && cmp >= 0) || (prevcmp > 0 && cmp < 0))
+ + + + ]
906 : 51 : return 0;
907 : : }
908 : :
909 : 81 : return adjacent_cmp_bounds(typcache, arg, centroid);
910 : : }
911 : :
912 : : /*
913 : : * SP-GiST consistent function for leaf nodes: check leaf value against query
914 : : * using corresponding function.
915 : : */
916 : : Datum
4769 917 : 113867 : spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
918 : : {
919 : 113867 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
920 : 113867 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
2910 tgl@sss.pgh.pa.us 921 : 113867 : RangeType *leafRange = DatumGetRangeTypeP(in->leafDatum);
922 : : TypeCacheEntry *typcache;
923 : : bool res;
924 : : int i;
925 : :
926 : : /* all tests are exact */
4769 heikki.linnakangas@i 927 : 113867 : out->recheck = false;
928 : :
929 : : /* leafDatum is what it is... */
930 : 113867 : out->leafValue = in->leafDatum;
931 : :
932 : 113867 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
933 : :
934 : : /* Perform the required comparison(s) */
935 : 113867 : res = true;
936 [ + + ]: 217313 : for (i = 0; i < in->nkeys; i++)
937 : : {
938 : 113867 : Datum keyDatum = in->scankeys[i].sk_argument;
939 : :
940 : : /* Call the function corresponding to the scan strategy */
941 [ + + + + : 113867 : switch (in->scankeys[i].sk_strategy)
+ + + + +
+ - ]
942 : : {
943 : 1428 : case RANGESTRAT_BEFORE:
944 : 1428 : res = range_before_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 945 : 1428 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 946 : 1428 : break;
947 : 9114 : case RANGESTRAT_OVERLEFT:
948 : 9114 : res = range_overleft_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 949 : 9114 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 950 : 9114 : break;
951 : 1470 : case RANGESTRAT_OVERLAPS:
952 : 1470 : res = range_overlaps_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 953 : 1470 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 954 : 1470 : break;
955 : 29730 : case RANGESTRAT_OVERRIGHT:
956 : 29730 : res = range_overright_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 957 : 29730 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 958 : 29730 : break;
959 : 21714 : case RANGESTRAT_AFTER:
960 : 21714 : res = range_after_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 961 : 21714 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 962 : 21714 : break;
4565 963 : 2663 : case RANGESTRAT_ADJACENT:
964 : 2663 : res = range_adjacent_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 965 : 2663 : DatumGetRangeTypeP(keyDatum));
4565 heikki.linnakangas@i 966 : 2663 : break;
4769 967 : 38670 : case RANGESTRAT_CONTAINS:
968 : 38670 : res = range_contains_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 969 : 38670 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 970 : 38670 : break;
971 : 6972 : case RANGESTRAT_CONTAINED_BY:
972 : 6972 : res = range_contained_by_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 973 : 6972 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 974 : 6972 : break;
975 : 1470 : case RANGESTRAT_CONTAINS_ELEM:
976 : 1470 : res = range_contains_elem_internal(typcache, leafRange,
977 : : keyDatum);
978 : 1470 : break;
979 : 636 : case RANGESTRAT_EQ:
980 : 636 : res = range_eq_internal(typcache, leafRange,
2910 tgl@sss.pgh.pa.us 981 : 636 : DatumGetRangeTypeP(keyDatum));
4769 heikki.linnakangas@i 982 : 636 : break;
4769 heikki.linnakangas@i 983 :UBC 0 : default:
984 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d",
985 : : in->scankeys[i].sk_strategy);
986 : : break;
987 : : }
988 : :
989 : : /*
990 : : * If leaf datum doesn't match to a query key, no need to check
991 : : * subsequent keys.
992 : : */
4769 heikki.linnakangas@i 993 [ + + ]:CBC 113867 : if (!res)
994 : 10421 : break;
995 : : }
996 : :
997 : 113867 : PG_RETURN_BOOL(res);
998 : : }
|
