PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
rangetypes_spgist.c File Reference
#include "postgres.h"
#include "access/spgist.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/datum.h"
#include "utils/fmgrprotos.h"
#include "utils/rangetypes.h"
Include dependency graph for rangetypes_spgist.c:

Go to the source code of this file.

Functions

static int16 getQuadrant (TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
 
static int bound_cmp (const void *a, const void *b, void *arg)
 
static int adjacent_inner_consistent (TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid, const RangeBound *prev)
 
static int adjacent_cmp_bounds (TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid)
 
Datum spg_range_quad_config (PG_FUNCTION_ARGS)
 
Datum spg_range_quad_choose (PG_FUNCTION_ARGS)
 
Datum spg_range_quad_picksplit (PG_FUNCTION_ARGS)
 
Datum spg_range_quad_inner_consistent (PG_FUNCTION_ARGS)
 
Datum spg_range_quad_leaf_consistent (PG_FUNCTION_ARGS)
 

Function Documentation

◆ adjacent_cmp_bounds()

static int adjacent_cmp_bounds ( TypeCacheEntry typcache,
const RangeBound arg,
const RangeBound centroid 
)
static

Definition at line 785 of file rangetypes_spgist.c.

787{
788 int cmp;
789
790 Assert(arg->lower != centroid->lower);
791
792 cmp = range_cmp_bounds(typcache, arg, centroid);
793
794 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 if (cmp < 0 && !bounds_adjacent(typcache, *arg, *centroid))
820 return -1;
821 else
822 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 if (cmp <= 0)
844 return -1;
845 else
846 return 1;
847 }
848}
#define Assert(condition)
Definition: c.h:815
void * arg
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:2016
bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound boundA, RangeBound boundB)
Definition: rangetypes.c:757
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
bool lower
Definition: rangetypes.h:66

References arg, Assert, bounds_adjacent(), cmp(), RangeBound::lower, and range_cmp_bounds().

Referenced by adjacent_inner_consistent().

◆ adjacent_inner_consistent()

static int adjacent_inner_consistent ( TypeCacheEntry typcache,
const RangeBound arg,
const RangeBound centroid,
const RangeBound prev 
)
static

Definition at line 887 of file rangetypes_spgist.c.

889{
890 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 prevcmp = adjacent_cmp_bounds(typcache, arg, prev);
900
901 /* and which direction did we actually go? */
902 cmp = range_cmp_bounds(typcache, centroid, prev);
903
904 /* if the two don't agree, there's nothing to see here */
905 if ((prevcmp < 0 && cmp >= 0) || (prevcmp > 0 && cmp < 0))
906 return 0;
907 }
908
909 return adjacent_cmp_bounds(typcache, arg, centroid);
910}
static int adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid)

References adjacent_cmp_bounds(), arg, cmp(), and range_cmp_bounds().

Referenced by spg_range_quad_inner_consistent().

◆ bound_cmp()

static int bound_cmp ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 186 of file rangetypes_spgist.c.

187{
188 RangeBound *ba = (RangeBound *) a;
189 RangeBound *bb = (RangeBound *) b;
190 TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
191
192 return range_cmp_bounds(typcache, ba, bb);
193}
int b
Definition: isn.c:69
int a
Definition: isn.c:68

References a, arg, b, and range_cmp_bounds().

Referenced by spg_range_quad_picksplit().

◆ getQuadrant()

static int16 getQuadrant ( TypeCacheEntry typcache,
const RangeType centroid,
const RangeType tst 
)
static

Definition at line 95 of file rangetypes_spgist.c.

96{
97 RangeBound centroidLower,
98 centroidUpper;
99 bool centroidEmpty;
101 upper;
102 bool empty;
103
104 range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
105 &centroidEmpty);
106 range_deserialize(typcache, tst, &lower, &upper, &empty);
107
108 if (empty)
109 return 5;
110
111 if (range_cmp_bounds(typcache, &lower, &centroidLower) >= 0)
112 {
113 if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
114 return 1;
115 else
116 return 2;
117 }
118 else
119 {
120 if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
121 return 4;
122 else
123 return 3;
124 }
125}
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1856

References lower(), range_cmp_bounds(), range_deserialize(), and upper().

Referenced by spg_range_quad_choose(), spg_range_quad_inner_consistent(), and spg_range_quad_picksplit().

◆ spg_range_quad_choose()

Datum spg_range_quad_choose ( PG_FUNCTION_ARGS  )

Definition at line 131 of file rangetypes_spgist.c.

132{
135 RangeType *inRange = DatumGetRangeTypeP(in->datum),
136 *centroid;
137 int16 quadrant;
138 TypeCacheEntry *typcache;
139
140 if (in->allTheSame)
141 {
143 /* nodeN will be set by core */
144 out->result.matchNode.levelAdd = 0;
147 }
148
149 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 if (!in->hasPrefix)
157 {
159 if (RangeIsEmpty(inRange))
160 out->result.matchNode.nodeN = 0;
161 else
162 out->result.matchNode.nodeN = 1;
163 out->result.matchNode.levelAdd = 1;
166 }
167
168 centroid = DatumGetRangeTypeP(in->prefixDatum);
169 quadrant = getQuadrant(typcache, centroid, inRange);
170
171 Assert(quadrant <= in->nNodes);
172
173 /* Select node matching to quadrant number */
175 out->result.matchNode.nodeN = quadrant - 1;
176 out->result.matchNode.levelAdd = 1;
178
180}
int16_t int16
Definition: c.h:483
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1703
static RangeType * DatumGetRangeTypeP(Datum X)
Definition: rangetypes.h:73
#define RangeIsEmpty(r)
Definition: rangetypes.h:55
static Datum RangeTypePGetDatum(const RangeType *X)
Definition: rangetypes.h:85
#define RangeTypeGetOid(r)
Definition: rangetypes.h:35
static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
@ spgMatchNode
Definition: spgist.h:69
bool hasPrefix
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:62
Datum datum
Definition: spgist.h:55
bool allTheSame
Definition: spgist.h:60
spgChooseResultType resultType
Definition: spgist.h:76
int levelAdd
Definition: spgist.h:82
Datum restDatum
Definition: spgist.h:83
int nodeN
Definition: spgist.h:81
struct spgChooseOut::@51::@52 matchNode
union spgChooseOut::@51 result

References spgChooseIn::allTheSame, Assert, spgChooseIn::datum, DatumGetRangeTypeP(), getQuadrant(), spgChooseIn::hasPrefix, spgChooseOut::levelAdd, spgChooseOut::matchNode, spgChooseOut::nodeN, PG_GETARG_POINTER, PG_RETURN_VOID, spgChooseIn::prefixDatum, range_get_typcache(), RangeIsEmpty, RangeTypeGetOid, RangeTypePGetDatum(), spgChooseOut::restDatum, spgChooseOut::result, spgChooseOut::resultType, and spgMatchNode.

◆ spg_range_quad_config()

Datum spg_range_quad_config ( PG_FUNCTION_ARGS  )

Definition at line 60 of file rangetypes_spgist.c.

61{
62 /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
64
65 cfg->prefixType = ANYRANGEOID;
66 cfg->labelType = VOIDOID; /* we don't need node labels */
67 cfg->canReturnData = true;
68 cfg->longValuesOK = false;
70}
bool longValuesOK
Definition: spgist.h:47
bool canReturnData
Definition: spgist.h:46
Oid labelType
Definition: spgist.h:44
Oid prefixType
Definition: spgist.h:43

References spgConfigOut::canReturnData, spgConfigOut::labelType, spgConfigOut::longValuesOK, PG_GETARG_POINTER, PG_RETURN_VOID, and spgConfigOut::prefixType.

◆ spg_range_quad_inner_consistent()

Datum spg_range_quad_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 300 of file rangetypes_spgist.c.

301{
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 */
313 bool needPrevious = false;
314
315 if (in->allTheSame)
316 {
317 /* Report that all nodes should be visited */
318 out->nNodes = in->nNodes;
319 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
320 for (i = 0; i < in->nNodes; i++)
321 out->nodeNumbers[i] = i;
323 }
324
325 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 */
331 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 which = (1 << 1) | (1 << 2);
339 for (i = 0; i < in->nkeys; i++)
340 {
341 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 if (strategy != RANGESTRAT_CONTAINS_ELEM)
350 else
351 empty = false;
352
353 switch (strategy)
354 {
359 case RANGESTRAT_AFTER:
361 /* These strategies return false if any argument is empty */
362 if (empty)
363 which = 0;
364 else
365 which &= (1 << 2);
366 break;
367
369
370 /*
371 * All ranges contain an empty range. Only non-empty
372 * ranges can contain a non-empty range.
373 */
374 if (!empty)
375 which &= (1 << 2);
376 break;
377
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 if (empty)
386 which &= (1 << 1);
387 break;
388
390 which &= (1 << 2);
391 break;
392
393 case RANGESTRAT_EQ:
394 if (empty)
395 which &= (1 << 1);
396 else
397 which &= (1 << 2);
398 break;
399
400 default:
401 elog(ERROR, "unrecognized range strategy: %d", strategy);
402 break;
403 }
404 if (which == 0)
405 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. */
417 centroid = DatumGetRangeTypeP(in->prefixDatum);
418 typcache = range_get_typcache(fcinfo,
419 RangeTypeGetOid(centroid));
420 range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
421 &centroidEmpty);
422
423 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 which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
431
432 for (i = 0; i < in->nkeys; i++)
433 {
434 StrategyNumber strategy;
436 upper;
437 bool empty;
438 RangeType *range = NULL;
439
440 RangeType *prevCentroid = NULL;
441 RangeBound prevLower,
442 prevUpper;
443 bool prevEmpty;
444
445 /* Restrictions on range bounds according to scan strategy */
446 RangeBound *minLower = NULL,
447 *maxLower = NULL,
448 *minUpper = NULL,
449 *maxUpper = NULL;
450
451 /* Are the restrictions on range bounds inclusive? */
452 bool inclusive = true;
453 bool strictEmpty = true;
454 int cmp,
455 which1,
456 which2;
457
458 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 if (strategy == RANGESTRAT_CONTAINS_ELEM)
467 {
468 lower.inclusive = true;
469 lower.infinite = false;
470 lower.lower = true;
471 lower.val = in->scankeys[i].sk_argument;
472
473 upper.inclusive = true;
474 upper.infinite = false;
475 upper.lower = false;
476 upper.val = in->scankeys[i].sk_argument;
477
478 empty = false;
479
480 strategy = RANGESTRAT_CONTAINS;
481 }
482 else
483 {
485 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 switch (strategy)
500 {
502
503 /*
504 * Range A is before range B if upper bound of A is lower
505 * than lower bound of B.
506 */
507 maxUpper = &lower;
508 inclusive = false;
509 break;
510
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 maxUpper = &upper;
518 break;
519
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 maxLower = &upper;
527 minUpper = &lower;
528 break;
529
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 minLower = &lower;
537 break;
538
539 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 minLower = &upper;
546 inclusive = false;
547 break;
548
550 if (empty)
551 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 */
558 if (in->traversalValue)
559 {
560 prevCentroid = in->traversalValue;
561 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 */
575 &centroidUpper,
576 prevCentroid ? &prevUpper : NULL);
577 if (cmp > 0)
578 which1 = (1 << 1) | (1 << 4);
579 else if (cmp < 0)
580 which1 = (1 << 2) | (1 << 3);
581 else
582 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 */
591 &centroidLower,
592 prevCentroid ? &prevLower : NULL);
593 if (cmp > 0)
594 which2 = (1 << 1) | (1 << 2);
595 else if (cmp < 0)
596 which2 = (1 << 3) | (1 << 4);
597 else
598 which2 = 0;
599
600 /* We must chase down ranges adjacent to either bound. */
601 which &= which1 | which2;
602
603 needPrevious = true;
604 break;
605
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 strictEmpty = false;
617 if (!empty)
618 {
619 which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
620 maxLower = &lower;
621 minUpper = &upper;
622 }
623 break;
624
626 /* The opposite of contains. */
627 strictEmpty = false;
628 if (empty)
629 {
630 /* An empty range is only contained by an empty range */
631 which &= (1 << 5);
632 }
633 else
634 {
635 minLower = &lower;
636 maxUpper = &upper;
637 }
638 break;
639
640 case RANGESTRAT_EQ:
641
642 /*
643 * Equal range can be only in the same quadrant where
644 * argument would be placed to.
645 */
646 strictEmpty = false;
647 which &= (1 << getQuadrant(typcache, centroid, range));
648 break;
649
650 default:
651 elog(ERROR, "unrecognized range strategy: %d", strategy);
652 break;
653 }
654
655 if (strictEmpty)
656 {
657 if (empty)
658 {
659 /* Scan key is empty, no branches are satisfying */
660 which = 0;
661 break;
662 }
663 else
664 {
665 /* Shouldn't visit tree branch with empty ranges */
666 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 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 if (range_cmp_bounds(typcache, &centroidLower, minLower) <= 0)
683 which &= (1 << 1) | (1 << 2) | (1 << 5);
684 }
685 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 cmp = range_cmp_bounds(typcache, &centroidLower, maxLower);
698 if (cmp > 0 || (!inclusive && cmp == 0))
699 which &= (1 << 3) | (1 << 4) | (1 << 5);
700 }
701 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 if (range_cmp_bounds(typcache, &centroidUpper, minUpper) <= 0)
710 which &= (1 << 1) | (1 << 4) | (1 << 5);
711 }
712 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 cmp = range_cmp_bounds(typcache, &centroidUpper, maxUpper);
725 if (cmp > 0 || (!inclusive && cmp == 0))
726 which &= (1 << 2) | (1 << 3) | (1 << 5);
727 }
728
729 if (which == 0)
730 break; /* no need to consider remaining conditions */
731 }
732 }
733
734 /* We must descend into the quadrant(s) identified by 'which' */
735 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
736 if (needPrevious)
737 out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
738 out->nNodes = 0;
739
740 /*
741 * Elements of traversalValues should be allocated in
742 * traversalMemoryContext
743 */
745
746 for (i = 1; i <= in->nNodes; i++)
747 {
748 if (which & (1 << i))
749 {
750 /* Save previous prefix if needed */
751 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 */
759 previousCentroid = datumCopy(in->prefixDatum, false, -1);
760 out->traversalValues[out->nNodes] = (void *) previousCentroid;
761 }
762 out->nodeNumbers[out->nNodes] = i - 1;
763 out->nNodes++;
764 }
765 }
766
767 MemoryContextSwitchTo(oldCtx);
768
770}
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
int i
Definition: isn.c:72
void * palloc(Size size)
Definition: mcxt.c:1317
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
uintptr_t Datum
Definition: postgres.h:69
#define RANGESTRAT_OVERLAPS
Definition: rangetypes.h:98
#define RANGESTRAT_AFTER
Definition: rangetypes.h:100
#define RANGESTRAT_BEFORE
Definition: rangetypes.h:96
#define RANGESTRAT_OVERRIGHT
Definition: rangetypes.h:99
#define RANGESTRAT_OVERLEFT
Definition: rangetypes.h:97
#define RANGESTRAT_CONTAINED_BY
Definition: rangetypes.h:103
#define RANGESTRAT_EQ
Definition: rangetypes.h:105
#define RANGESTRAT_ADJACENT
Definition: rangetypes.h:101
#define RANGESTRAT_CONTAINS_ELEM
Definition: rangetypes.h:104
#define RANGESTRAT_CONTAINS
Definition: rangetypes.h:102
static int adjacent_inner_consistent(TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid, const RangeBound *prev)
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
uint16 StrategyNumber
Definition: stratnum.h:22
Datum sk_argument
Definition: skey.h:72
StrategyNumber sk_strategy
Definition: skey.h:68
void * traversalValue
Definition: spgist.h:141
ScanKey scankeys
Definition: spgist.h:134
MemoryContext traversalMemoryContext
Definition: spgist.h:142
void ** traversalValues
Definition: spgist.h:160

References adjacent_inner_consistent(), spgInnerConsistentIn::allTheSame, Assert, cmp(), datumCopy(), DatumGetRangeTypeP(), elog, ERROR, getQuadrant(), spgInnerConsistentIn::hasPrefix, i, lower(), MemoryContextSwitchTo(), spgInnerConsistentIn::nkeys, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nNodes, spgInnerConsistentOut::nodeNumbers, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, spgInnerConsistentIn::prefixDatum, range(), range_cmp_bounds(), range_deserialize(), range_get_typcache(), RangeIsEmpty, RANGESTRAT_ADJACENT, RANGESTRAT_AFTER, RANGESTRAT_BEFORE, RANGESTRAT_CONTAINED_BY, RANGESTRAT_CONTAINS, RANGESTRAT_CONTAINS_ELEM, RANGESTRAT_EQ, RANGESTRAT_OVERLAPS, RANGESTRAT_OVERLEFT, RANGESTRAT_OVERRIGHT, RangeTypeGetOid, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, spgInnerConsistentIn::traversalMemoryContext, spgInnerConsistentIn::traversalValue, spgInnerConsistentOut::traversalValues, and upper().

◆ spg_range_quad_leaf_consistent()

Datum spg_range_quad_leaf_consistent ( PG_FUNCTION_ARGS  )

Definition at line 917 of file rangetypes_spgist.c.

918{
921 RangeType *leafRange = DatumGetRangeTypeP(in->leafDatum);
922 TypeCacheEntry *typcache;
923 bool res;
924 int i;
925
926 /* all tests are exact */
927 out->recheck = false;
928
929 /* leafDatum is what it is... */
930 out->leafValue = in->leafDatum;
931
932 typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
933
934 /* Perform the required comparison(s) */
935 res = true;
936 for (i = 0; i < in->nkeys; i++)
937 {
938 Datum keyDatum = in->scankeys[i].sk_argument;
939
940 /* Call the function corresponding to the scan strategy */
941 switch (in->scankeys[i].sk_strategy)
942 {
944 res = range_before_internal(typcache, leafRange,
945 DatumGetRangeTypeP(keyDatum));
946 break;
948 res = range_overleft_internal(typcache, leafRange,
949 DatumGetRangeTypeP(keyDatum));
950 break;
952 res = range_overlaps_internal(typcache, leafRange,
953 DatumGetRangeTypeP(keyDatum));
954 break;
956 res = range_overright_internal(typcache, leafRange,
957 DatumGetRangeTypeP(keyDatum));
958 break;
959 case RANGESTRAT_AFTER:
960 res = range_after_internal(typcache, leafRange,
961 DatumGetRangeTypeP(keyDatum));
962 break;
964 res = range_adjacent_internal(typcache, leafRange,
965 DatumGetRangeTypeP(keyDatum));
966 break;
968 res = range_contains_internal(typcache, leafRange,
969 DatumGetRangeTypeP(keyDatum));
970 break;
972 res = range_contained_by_internal(typcache, leafRange,
973 DatumGetRangeTypeP(keyDatum));
974 break;
976 res = range_contains_elem_internal(typcache, leafRange,
977 keyDatum);
978 break;
979 case RANGESTRAT_EQ:
980 res = range_eq_internal(typcache, leafRange,
981 DatumGetRangeTypeP(keyDatum));
982 break;
983 default:
984 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 */
993 if (!res)
994 break;
995 }
996
998}
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
bool range_contained_by_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:2618
bool range_contains_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:2586
bool range_after_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:702
bool range_overlaps_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:841
bool range_before_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:664
bool range_overright_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:928
bool range_contains_elem_internal(TypeCacheEntry *typcache, const RangeType *r, Datum val)
Definition: rangetypes.c:2627
bool range_eq_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:573
bool range_adjacent_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:798
bool range_overleft_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:887
ScanKey scankeys
Definition: spgist.h:169

References DatumGetRangeTypeP(), elog, ERROR, i, spgLeafConsistentIn::leafDatum, spgLeafConsistentOut::leafValue, spgLeafConsistentIn::nkeys, PG_GETARG_POINTER, PG_RETURN_BOOL, range_adjacent_internal(), range_after_internal(), range_before_internal(), range_contained_by_internal(), range_contains_elem_internal(), range_contains_internal(), range_eq_internal(), range_get_typcache(), range_overlaps_internal(), range_overleft_internal(), range_overright_internal(), RANGESTRAT_ADJACENT, RANGESTRAT_AFTER, RANGESTRAT_BEFORE, RANGESTRAT_CONTAINED_BY, RANGESTRAT_CONTAINS, RANGESTRAT_CONTAINS_ELEM, RANGESTRAT_EQ, RANGESTRAT_OVERLAPS, RANGESTRAT_OVERLEFT, RANGESTRAT_OVERRIGHT, RangeTypeGetOid, spgLeafConsistentOut::recheck, res, spgLeafConsistentIn::scankeys, ScanKeyData::sk_argument, and ScanKeyData::sk_strategy.

◆ spg_range_quad_picksplit()

Datum spg_range_quad_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 200 of file rangetypes_spgist.c.

201{
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 typcache = range_get_typcache(fcinfo,
217
218 /* Allocate memory for bounds */
219 lowerBounds = palloc(sizeof(RangeBound) * in->nTuples);
220 upperBounds = palloc(sizeof(RangeBound) * in->nTuples);
221 j = 0;
222
223 /* Deserialize bounds of ranges, count non-empty ranges */
224 for (i = 0; i < in->nTuples; i++)
225 {
227 &lowerBounds[j], &upperBounds[j], &empty);
228 if (!empty)
229 j++;
230 }
231 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 if (nonEmptyCount == 0)
239 {
240 out->nNodes = 2;
241 out->hasPrefix = false;
242 /* Prefix is empty */
243 out->prefixDatum = PointerGetDatum(NULL);
244 out->nodeLabels = NULL;
245
246 out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
247 out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
248
249 /* Place all ranges into node 0 */
250 for (i = 0; i < in->nTuples; i++)
251 {
253
255 out->mapTuplesToNodes[i] = 0;
256 }
258 }
259
260 /* Sort range bounds in order to find medians */
261 qsort_arg(lowerBounds, nonEmptyCount, sizeof(RangeBound),
262 bound_cmp, typcache);
263 qsort_arg(upperBounds, nonEmptyCount, sizeof(RangeBound),
264 bound_cmp, typcache);
265
266 /* Construct "centroid" range from medians of lower and upper bounds */
267 centroid = range_serialize(typcache, &lowerBounds[nonEmptyCount / 2],
268 &upperBounds[nonEmptyCount / 2], false, NULL);
269 out->hasPrefix = true;
270 out->prefixDatum = RangeTypePGetDatum(centroid);
271
272 /* Create node for empty ranges only if it is a root node */
273 out->nNodes = (in->level == 0) ? 5 : 4;
274 out->nodeLabels = NULL; /* we don't need node labels */
275
276 out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
277 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 for (i = 0; i < in->nTuples; i++)
284 {
286 int16 quadrant = getQuadrant(typcache, centroid, range);
287
289 out->mapTuplesToNodes[i] = quadrant - 1;
290 }
291
293}
int j
Definition: isn.c:73
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:327
RangeType * range_serialize(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty, struct Node *escontext)
Definition: rangetypes.c:1727
static int bound_cmp(const void *a, const void *b, void *arg)
Datum * datums
Definition: spgist.h:113
bool hasPrefix
Definition: spgist.h:119
int * mapTuplesToNodes
Definition: spgist.h:125
Datum * nodeLabels
Definition: spgist.h:123
Datum * leafTupleDatums
Definition: spgist.h:126
Datum prefixDatum
Definition: spgist.h:120

References bound_cmp(), DatumGetRangeTypeP(), spgPickSplitIn::datums, getQuadrant(), spgPickSplitOut::hasPrefix, i, j, spgPickSplitOut::leafTupleDatums, spgPickSplitIn::level, spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, PointerGetDatum(), spgPickSplitOut::prefixDatum, qsort_arg(), range(), range_deserialize(), range_get_typcache(), range_serialize(), RangeTypeGetOid, and RangeTypePGetDatum().