PostgreSQL Source Code  git master
rangetypes_spgist.c File Reference
#include "postgres.h"
#include "access/spgist.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/datum.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 }
Assert(fmt[strlen(fmt) - 1] !='\n')
void * arg
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1924
bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound boundA, RangeBound boundB)
Definition: rangetypes.c:739
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:747
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:70
int a
Definition: isn.c:69

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:48
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:79
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1788

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  {
142  out->resultType = spgMatchNode;
143  /* nodeN will be set by core */
144  out->result.matchNode.levelAdd = 0;
145  out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
146  PG_RETURN_VOID();
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  {
158  out->resultType = spgMatchNode;
159  if (RangeIsEmpty(inRange))
160  out->result.matchNode.nodeN = 0;
161  else
162  out->result.matchNode.nodeN = 1;
163  out->result.matchNode.levelAdd = 1;
164  out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
165  PG_RETURN_VOID();
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 */
174  out->resultType = spgMatchNode;
175  out->result.matchNode.nodeN = quadrant - 1;
176  out->result.matchNode.levelAdd = 1;
177  out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
178 
179  PG_RETURN_VOID();
180 }
signed short int16
Definition: c.h:429
#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:1635
#define RangeIsEmpty(r)
Definition: rangetypes.h:55
static Datum RangeTypePGetDatum(const RangeType *X)
Definition: rangetypes.h:85
static RangeType * DatumGetRangeTypeP(Datum X)
Definition: rangetypes.h:73
#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
union spgChooseOut::@46 result
struct spgChooseOut::@46::@47 matchNode

References spgChooseIn::allTheSame, Assert(), spgChooseIn::datum, DatumGetRangeTypeP(), getQuadrant(), spgChooseIn::hasPrefix, spgChooseOut::matchNode, PG_GETARG_POINTER, PG_RETURN_VOID, spgChooseIn::prefixDatum, range_get_typcache(), RangeIsEmpty, RangeTypeGetOid, RangeTypePGetDatum(), 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;
322  PG_RETURN_VOID();
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  {
355  case RANGESTRAT_BEFORE:
356  case RANGESTRAT_OVERLEFT:
357  case RANGESTRAT_OVERLAPS:
359  case RANGESTRAT_AFTER:
360  case RANGESTRAT_ADJACENT:
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 
368  case RANGESTRAT_CONTAINS:
369 
370  /*
371  * All ranges contain an empty range. Only non-empty
372  * ranges can contain a non-empty range.
373  */
374  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  {
501  case RANGESTRAT_BEFORE:
502 
503  /*
504  * Range A is before range B if upper bound of A is lower
505  * than lower bound of B.
506  */
507  maxUpper = &lower;
508  inclusive = false;
509  break;
510 
511  case RANGESTRAT_OVERLEFT:
512 
513  /*
514  * Range A is overleft to range B if upper bound of A is
515  * less than or equal to upper bound of B.
516  */
517  maxUpper = &upper;
518  break;
519 
520  case RANGESTRAT_OVERLAPS:
521 
522  /*
523  * Non-empty ranges overlap, if lower bound of each range
524  * is lower or equal to upper bound of the other range.
525  */
526  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 
549  case RANGESTRAT_ADJACENT:
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  */
574  cmp = adjacent_inner_consistent(typcache, &lower,
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  */
590  cmp = adjacent_inner_consistent(typcache, &upper,
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 
606  case RANGESTRAT_CONTAINS:
607 
608  /*
609  * Non-empty range A contains non-empty range B if lower
610  * bound of A is lower or equal to lower bound of range B
611  * and upper bound of range A is greater than or equal to
612  * upper bound of range A.
613  *
614  * All non-empty ranges contain an empty range.
615  */
616  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 
769  PG_RETURN_VOID();
770 }
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
#define ERROR
Definition: elog.h:35
int i
Definition: isn.c:73
void * palloc(Size size)
Definition: mcxt.c:1199
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:135
uintptr_t Datum
Definition: postgres.h:412
#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  {
943  case RANGESTRAT_BEFORE:
944  res = range_before_internal(typcache, leafRange,
945  DatumGetRangeTypeP(keyDatum));
946  break;
947  case RANGESTRAT_OVERLEFT:
948  res = range_overleft_internal(typcache, leafRange,
949  DatumGetRangeTypeP(keyDatum));
950  break;
951  case RANGESTRAT_OVERLAPS:
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;
963  case RANGESTRAT_ADJACENT:
964  res = range_adjacent_internal(typcache, leafRange,
965  DatumGetRangeTypeP(keyDatum));
966  break;
967  case RANGESTRAT_CONTAINS:
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:2464
bool range_contains_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:2432
bool range_after_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:684
bool range_overlaps_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:823
bool range_before_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:646
bool range_overright_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:910
bool range_contains_elem_internal(TypeCacheEntry *typcache, const RangeType *r, Datum val)
Definition: rangetypes.c:2473
bool range_eq_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:555
bool range_adjacent_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:780
bool range_overleft_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:869
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  }
257  PG_RETURN_VOID();
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);
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 
292  PG_RETURN_VOID();
293 }
int j
Definition: isn.c:74
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:670
RangeType * range_serialize(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty)
Definition: rangetypes.c:1659
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().