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
60 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
97 379563 : 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 :
106 379563 : range_deserialize(typcache, centroid, ¢roidLower, ¢roidUpper,
107 : ¢roidEmpty);
108 379563 : range_deserialize(typcache, tst, &lower, &upper, &empty);
109 :
110 379563 : if (empty)
111 6000 : return 5;
112 :
113 373563 : if (range_cmp_bounds(typcache, &lower, ¢roidLower) >= 0)
114 : {
115 340258 : if (range_cmp_bounds(typcache, &upper, ¢roidUpper) >= 0)
116 339916 : return 1;
117 : else
118 342 : return 2;
119 : }
120 : else
121 : {
122 33305 : if (range_cmp_bounds(typcache, &upper, ¢roidUpper) >= 0)
123 7304 : return 4;
124 : else
125 26001 : return 3;
126 : }
127 : }
128 :
129 : /*
130 : * Choose SP-GiST function: choose path for addition of new range.
131 : */
132 : Datum
133 357364 : spg_range_quad_choose(PG_FUNCTION_ARGS)
134 : {
135 357364 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
136 357364 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
137 357364 : RangeType *inRange = DatumGetRangeTypeP(in->datum),
138 : *centroid;
139 : int16 quadrant;
140 : TypeCacheEntry *typcache;
141 :
142 357364 : if (in->allTheSame)
143 : {
144 6436 : out->resultType = spgMatchNode;
145 : /* nodeN will be set by core */
146 6436 : out->result.matchNode.levelAdd = 0;
147 6436 : out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
148 6436 : PG_RETURN_VOID();
149 : }
150 :
151 350928 : 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 350928 : if (!in->hasPrefix)
159 : {
160 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;
166 0 : out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
167 0 : PG_RETURN_VOID();
168 : }
169 :
170 350928 : centroid = DatumGetRangeTypeP(in->prefixDatum);
171 350928 : quadrant = getQuadrant(typcache, centroid, inRange);
172 :
173 : Assert(quadrant <= in->nNodes);
174 :
175 : /* Select node matching to quadrant number */
176 350928 : out->resultType = spgMatchNode;
177 350928 : out->result.matchNode.nodeN = quadrant - 1;
178 350928 : out->result.matchNode.levelAdd = 1;
179 350928 : out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
180 :
181 350928 : PG_RETURN_VOID();
182 : }
183 :
184 : /*
185 : * Bound comparison for sorting.
186 : */
187 : static int
188 353284 : bound_cmp(const void *a, const void *b, void *arg)
189 : {
190 353284 : const RangeBound *ba = a;
191 353284 : const RangeBound *bb = b;
192 353284 : TypeCacheEntry *typcache = arg;
193 :
194 353284 : 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 241 : spg_range_quad_picksplit(PG_FUNCTION_ARGS)
203 : {
204 241 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
205 241 : 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 241 : typcache = range_get_typcache(fcinfo,
218 241 : RangeTypeGetOid(DatumGetRangeTypeP(in->datums[0])));
219 :
220 : /* Allocate memory for bounds */
221 241 : lowerBounds = palloc_array(RangeBound, in->nTuples);
222 241 : upperBounds = palloc_array(RangeBound, in->nTuples);
223 241 : j = 0;
224 :
225 : /* Deserialize bounds of ranges, count non-empty ranges */
226 31919 : for (i = 0; i < in->nTuples; i++)
227 : {
228 31678 : range_deserialize(typcache, DatumGetRangeTypeP(in->datums[i]),
229 31678 : &lowerBounds[j], &upperBounds[j], &empty);
230 31678 : if (!empty)
231 28623 : j++;
232 : }
233 241 : 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 241 : if (nonEmptyCount == 0)
241 : {
242 34 : out->nNodes = 2;
243 34 : out->hasPrefix = false;
244 : /* Prefix is empty */
245 34 : out->prefixDatum = PointerGetDatum(NULL);
246 34 : out->nodeLabels = NULL;
247 :
248 34 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
249 34 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
250 :
251 : /* Place all ranges into node 0 */
252 3089 : for (i = 0; i < in->nTuples; i++)
253 : {
254 3055 : RangeType *range = DatumGetRangeTypeP(in->datums[i]);
255 :
256 3055 : out->leafTupleDatums[i] = RangeTypePGetDatum(range);
257 3055 : out->mapTuplesToNodes[i] = 0;
258 : }
259 34 : PG_RETURN_VOID();
260 : }
261 :
262 : /* Sort range bounds in order to find medians */
263 207 : qsort_arg(lowerBounds, nonEmptyCount, sizeof(RangeBound),
264 : bound_cmp, typcache);
265 207 : qsort_arg(upperBounds, nonEmptyCount, sizeof(RangeBound),
266 : bound_cmp, typcache);
267 :
268 : /* Construct "centroid" range from medians of lower and upper bounds */
269 207 : centroid = range_serialize(typcache, &lowerBounds[nonEmptyCount / 2],
270 207 : &upperBounds[nonEmptyCount / 2], false, NULL);
271 207 : out->hasPrefix = true;
272 207 : out->prefixDatum = RangeTypePGetDatum(centroid);
273 :
274 : /* Create node for empty ranges only if it is a root node */
275 207 : out->nNodes = (in->level == 0) ? 5 : 4;
276 207 : out->nodeLabels = NULL; /* we don't need node labels */
277 :
278 207 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
279 207 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
280 :
281 : /*
282 : * Assign ranges to corresponding nodes according to quadrants relative to
283 : * "centroid" range.
284 : */
285 28830 : for (i = 0; i < in->nTuples; i++)
286 : {
287 28623 : RangeType *range = DatumGetRangeTypeP(in->datums[i]);
288 28623 : int16 quadrant = getQuadrant(typcache, centroid, range);
289 :
290 28623 : out->leafTupleDatums[i] = RangeTypePGetDatum(range);
291 28623 : out->mapTuplesToNodes[i] = quadrant - 1;
292 : }
293 :
294 207 : 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 899 : spg_range_quad_inner_consistent(PG_FUNCTION_ARGS)
303 : {
304 899 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
305 899 : 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 : */
315 899 : bool needPrevious = false;
316 :
317 899 : if (in->allTheSame)
318 : {
319 : /* Report that all nodes should be visited */
320 68 : out->nNodes = in->nNodes;
321 68 : out->nodeNumbers = palloc_array(int, in->nNodes);
322 612 : for (i = 0; i < in->nNodes; i++)
323 544 : out->nodeNumbers[i] = i;
324 68 : PG_RETURN_VOID();
325 : }
326 :
327 831 : 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 : */
333 : 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)
351 0 : empty = RangeIsEmpty(DatumGetRangeTypeP(in->scankeys[i].sk_argument));
352 : else
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. */
419 831 : centroid = DatumGetRangeTypeP(in->prefixDatum);
420 831 : typcache = range_get_typcache(fcinfo,
421 : RangeTypeGetOid(centroid));
422 831 : range_deserialize(typcache, centroid, ¢roidLower, ¢roidUpper,
423 : ¢roidEmpty);
424 :
425 : 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 831 : which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
433 :
434 1662 : for (i = 0; i < in->nkeys; i++)
435 : {
436 : StrategyNumber strategy;
437 : RangeBound lower,
438 : upper;
439 : bool empty;
440 831 : RangeType *range = NULL;
441 :
442 831 : RangeType *prevCentroid = NULL;
443 : RangeBound prevLower,
444 : prevUpper;
445 : bool prevEmpty;
446 :
447 : /* Restrictions on range bounds according to scan strategy */
448 831 : RangeBound *minLower = NULL,
449 831 : *maxLower = NULL,
450 831 : *minUpper = NULL,
451 831 : *maxUpper = NULL;
452 :
453 : /* Are the restrictions on range bounds inclusive? */
454 831 : bool inclusive = true;
455 831 : bool strictEmpty = true;
456 : int cmp,
457 : which1,
458 : which2;
459 :
460 831 : 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 831 : 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 : {
486 807 : range = DatumGetRangeTypeP(in->scankeys[i].sk_argument);
487 807 : 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 831 : 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 201 : 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 201 : minLower = &lower;
539 201 : break;
540 :
541 183 : 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 183 : minLower = &upper;
548 183 : inclusive = false;
549 183 : break;
550 :
551 66 : case RANGESTRAT_ADJACENT:
552 66 : if (empty)
553 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 : */
560 66 : if (in->traversalValue)
561 : {
562 57 : prevCentroid = in->traversalValue;
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 : */
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. */
603 66 : which &= which1 | which2;
604 :
605 66 : needPrevious = true;
606 66 : break;
607 :
608 255 : 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 255 : strictEmpty = false;
619 255 : if (!empty)
620 : {
621 48 : which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
622 48 : maxLower = &lower;
623 48 : minUpper = &upper;
624 : }
625 255 : 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 */
633 0 : which &= (1 << 5);
634 : }
635 : else
636 : {
637 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 :
652 0 : default:
653 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
654 : break;
655 : }
656 :
657 831 : if (strictEmpty)
658 : {
659 552 : if (empty)
660 : {
661 : /* Scan key is empty, no branches are satisfying */
662 0 : which = 0;
663 0 : break;
664 : }
665 : else
666 : {
667 : /* Shouldn't visit tree branch with empty ranges */
668 552 : 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 831 : 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 396 : if (range_cmp_bounds(typcache, ¢roidLower, minLower) <= 0)
685 48 : which &= (1 << 1) | (1 << 2) | (1 << 5);
686 : }
687 831 : 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 831 : 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)
712 0 : which &= (1 << 1) | (1 << 4) | (1 << 5);
713 : }
714 831 : 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 831 : if (which == 0)
732 0 : break; /* no need to consider remaining conditions */
733 : }
734 : }
735 :
736 : /* We must descend into the quadrant(s) identified by 'which' */
737 831 : out->nodeNumbers = palloc_array(int, in->nNodes);
738 831 : if (needPrevious)
739 66 : out->traversalValues = palloc_array(void *, in->nNodes);
740 831 : out->nNodes = 0;
741 :
742 : /*
743 : * Elements of traversalValues should be allocated in
744 : * traversalMemoryContext
745 : */
746 831 : oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
747 :
748 4224 : for (i = 1; i <= in->nNodes; i++)
749 : {
750 3393 : if (which & (1 << i))
751 : {
752 : /* Save previous prefix if needed */
753 2895 : 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 : */
761 147 : previousCentroid = datumCopy(in->prefixDatum, false, -1);
762 147 : out->traversalValues[out->nNodes] = DatumGetPointer(previousCentroid);
763 : }
764 2895 : out->nodeNumbers[out->nNodes] = i - 1;
765 2895 : out->nNodes++;
766 : }
767 : }
768 :
769 831 : MemoryContextSwitchTo(oldCtx);
770 :
771 831 : 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
787 195 : adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg,
788 : const RangeBound *centroid)
789 : {
790 : int cmp;
791 :
792 : Assert(arg->lower != centroid->lower);
793 :
794 195 : cmp = range_cmp_bounds(typcache, arg, centroid);
795 :
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
889 132 : adjacent_inner_consistent(TypeCacheEntry *typcache, const RangeBound *arg,
890 : const RangeBound *centroid, const RangeBound *prev)
891 : {
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
919 113842 : spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
920 : {
921 113842 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
922 113842 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
923 113842 : RangeType *leafRange = DatumGetRangeTypeP(in->leafDatum);
924 : TypeCacheEntry *typcache;
925 : bool res;
926 : int i;
927 :
928 : /* all tests are exact */
929 113842 : out->recheck = false;
930 :
931 : /* leafDatum is what it is... */
932 113842 : out->leafValue = in->leafDatum;
933 :
934 113842 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
935 :
936 : /* Perform the required comparison(s) */
937 113842 : res = true;
938 217288 : for (i = 0; i < in->nkeys; i++)
939 : {
940 113842 : Datum keyDatum = in->scankeys[i].sk_argument;
941 :
942 : /* Call the function corresponding to the scan strategy */
943 113842 : switch (in->scankeys[i].sk_strategy)
944 : {
945 1428 : case RANGESTRAT_BEFORE:
946 1428 : res = range_before_internal(typcache, leafRange,
947 1428 : DatumGetRangeTypeP(keyDatum));
948 1428 : break;
949 9108 : case RANGESTRAT_OVERLEFT:
950 9108 : res = range_overleft_internal(typcache, leafRange,
951 9108 : DatumGetRangeTypeP(keyDatum));
952 9108 : break;
953 1459 : case RANGESTRAT_OVERLAPS:
954 1459 : res = range_overlaps_internal(typcache, leafRange,
955 1459 : DatumGetRangeTypeP(keyDatum));
956 1459 : break;
957 29741 : case RANGESTRAT_OVERRIGHT:
958 29741 : res = range_overright_internal(typcache, leafRange,
959 29741 : DatumGetRangeTypeP(keyDatum));
960 29741 : break;
961 21714 : case RANGESTRAT_AFTER:
962 21714 : res = range_after_internal(typcache, leafRange,
963 21714 : DatumGetRangeTypeP(keyDatum));
964 21714 : break;
965 2666 : case RANGESTRAT_ADJACENT:
966 2666 : res = range_adjacent_internal(typcache, leafRange,
967 2666 : DatumGetRangeTypeP(keyDatum));
968 2666 : break;
969 38659 : case RANGESTRAT_CONTAINS:
970 38659 : res = range_contains_internal(typcache, leafRange,
971 38659 : DatumGetRangeTypeP(keyDatum));
972 38659 : break;
973 6972 : case RANGESTRAT_CONTAINED_BY:
974 6972 : res = range_contained_by_internal(typcache, leafRange,
975 6972 : DatumGetRangeTypeP(keyDatum));
976 6972 : break;
977 1459 : case RANGESTRAT_CONTAINS_ELEM:
978 1459 : res = range_contains_elem_internal(typcache, leafRange,
979 : keyDatum);
980 1459 : break;
981 636 : case RANGESTRAT_EQ:
982 636 : res = range_eq_internal(typcache, leafRange,
983 636 : DatumGetRangeTypeP(keyDatum));
984 636 : break;
985 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 : */
995 113842 : if (!res)
996 10396 : break;
997 : }
998 :
999 113842 : PG_RETURN_BOOL(res);
1000 : }
|
