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