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 787 of file rangetypes_spgist.c.

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

Referenced by adjacent_inner_consistent().

789 {
790  int cmp;
791 
792  Assert(arg->lower != centroid->lower);
793 
794  cmp = range_cmp_bounds(typcache, arg, centroid);
795 
796  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  if (cmp < 0 && !bounds_adjacent(typcache, *arg, *centroid))
822  return -1;
823  else
824  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  if (cmp <= 0)
846  return -1;
847  else
848  return 1;
849  }
850 }
bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound boundA, RangeBound boundB)
Definition: rangetypes.c:741
bool lower
Definition: rangetypes.h:65
#define Assert(condition)
Definition: c.h:738
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1835
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ adjacent_inner_consistent()

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

Definition at line 889 of file rangetypes_spgist.c.

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

Referenced by spg_range_quad_inner_consistent().

891 {
892  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  prevcmp = adjacent_cmp_bounds(typcache, arg, prev);
902 
903  /* and which direction did we actually go? */
904  cmp = range_cmp_bounds(typcache, centroid, prev);
905 
906  /* if the two don't agree, there's nothing to see here */
907  if ((prevcmp < 0 && cmp >= 0) || (prevcmp > 0 && cmp < 0))
908  return 0;
909  }
910 
911  return adjacent_cmp_bounds(typcache, arg, centroid);
912 }
static int adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid)
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1835
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ bound_cmp()

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

Definition at line 186 of file rangetypes_spgist.c.

References range_cmp_bounds().

Referenced by spg_range_quad_picksplit().

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 }
void * arg
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1835

◆ getQuadrant()

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

Definition at line 95 of file rangetypes_spgist.c.

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().

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 }
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1699
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1835

◆ spg_range_quad_choose()

Datum spg_range_quad_choose ( PG_FUNCTION_ARGS  )

Definition at line 131 of file rangetypes_spgist.c.

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.

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:354
#define RangeIsEmpty(r)
Definition: rangetypes.h:54
Datum datum
Definition: spgist.h:54
bool hasPrefix
Definition: spgist.h:60
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1546
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
struct spgChooseOut::@48::@49 matchNode
Datum prefixDatum
Definition: spgist.h:61
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define RangeTypePGetDatum(X)
Definition: rangetypes.h:73
spgChooseResultType resultType
Definition: spgist.h:75
#define PG_RETURN_VOID()
Definition: fmgr.h:339
#define Assert(condition)
Definition: c.h:738
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
union spgChooseOut::@48 result
bool allTheSame
Definition: spgist.h:59
static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)

◆ spg_range_quad_config()

Datum spg_range_quad_config ( PG_FUNCTION_ARGS  )

Definition at line 60 of file rangetypes_spgist.c.

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

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 canReturnData
Definition: spgist.h:45
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
bool longValuesOK
Definition: spgist.h:46
Oid prefixType
Definition: spgist.h:42
#define PG_RETURN_VOID()
Definition: fmgr.h:339
Oid labelType
Definition: spgist.h:43

◆ spg_range_quad_inner_consistent()

Datum spg_range_quad_inner_consistent ( PG_FUNCTION_ARGS  )

Definition at line 300 of file rangetypes_spgist.c.

References adjacent_inner_consistent(), spgInnerConsistentIn::allTheSame, Assert, cmp(), datumCopy(), DatumGetRangeTypeP, elog, ERROR, getQuadrant(), spgInnerConsistentIn::hasPrefix, i, RangeBound::inclusive, RangeBound::infinite, lower(), RangeBound::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, upper(), and RangeBound::val.

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,
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  {
484  range = DatumGetRangeTypeP(in->scankeys[i].sk_argument);
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 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 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 = DatumGetRangeTypeP(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 or equal to upper
612  * 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  int cmp;
697 
698  cmp = range_cmp_bounds(typcache, &centroidLower, maxLower);
699  if (cmp > 0 || (!inclusive && cmp == 0))
700  which &= (1 << 3) | (1 << 4) | (1 << 5);
701  }
702  if (minUpper)
703  {
704  /*
705  * If the centroid's upper bound is less than or equal to the
706  * minimum upper bound, anything in the 2nd and 3rd quadrants
707  * will have an even smaller upper bound, and thus can't
708  * match.
709  */
710  if (range_cmp_bounds(typcache, &centroidUpper, minUpper) <= 0)
711  which &= (1 << 1) | (1 << 4) | (1 << 5);
712  }
713  if (maxUpper)
714  {
715  /*
716  * If the centroid's upper bound is greater than the maximum
717  * upper bound, anything in the 1st and 4th quadrants will
718  * also have a greater than or equal upper bound, and thus
719  * can't match. If the centroid's upper bound is equal to the
720  * maximum upper bound, we can still exclude the 1st and 4th
721  * quadrants if we're looking for a value strictly greater
722  * than the maximum.
723  */
724  int cmp;
725 
726  cmp = range_cmp_bounds(typcache, &centroidUpper, maxUpper);
727  if (cmp > 0 || (!inclusive && cmp == 0))
728  which &= (1 << 2) | (1 << 3) | (1 << 5);
729  }
730 
731  if (which == 0)
732  break; /* no need to consider remaining conditions */
733  }
734  }
735 
736  /* We must descend into the quadrant(s) identified by 'which' */
737  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
738  if (needPrevious)
739  out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
740  out->nNodes = 0;
741 
742  /*
743  * Elements of traversalValues should be allocated in
744  * traversalMemoryContext
745  */
747 
748  for (i = 1; i <= in->nNodes; i++)
749  {
750  if (which & (1 << i))
751  {
752  /* Save previous prefix if needed */
753  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  previousCentroid = datumCopy(in->prefixDatum, false, -1);
762  out->traversalValues[out->nNodes] = (void *) previousCentroid;
763  }
764  out->nodeNumbers[out->nNodes] = i - 1;
765  out->nNodes++;
766  }
767  }
768 
769  MemoryContextSwitchTo(oldCtx);
770 
771  PG_RETURN_VOID();
772 }
#define RangeIsEmpty(r)
Definition: rangetypes.h:54
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1699
#define RANGESTRAT_OVERRIGHT
Definition: rangetypes.h:83
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1546
#define RANGESTRAT_ADJACENT
Definition: rangetypes.h:85
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
static int adjacent_inner_consistent(TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid, const RangeBound *prev)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * traversalValue
Definition: spgist.h:140
Datum val
Definition: rangetypes.h:62
uint16 StrategyNumber
Definition: stratnum.h:22
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
bool inclusive
Definition: rangetypes.h:64
MemoryContext traversalMemoryContext
Definition: spgist.h:141
#define ERROR
Definition: elog.h:43
#define RANGESTRAT_CONTAINS_ELEM
Definition: rangetypes.h:88
#define RANGESTRAT_BEFORE
Definition: rangetypes.h:80
StrategyNumber sk_strategy
Definition: skey.h:68
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
void ** traversalValues
Definition: spgist.h:159
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:130
bool lower
Definition: rangetypes.h:65
#define RANGESTRAT_CONTAINS
Definition: rangetypes.h:86
uintptr_t Datum
Definition: postgres.h:367
#define PG_RETURN_VOID()
Definition: fmgr.h:339
#define Assert(condition)
Definition: c.h:738
#define RANGESTRAT_CONTAINED_BY
Definition: rangetypes.h:87
#define RANGESTRAT_OVERLEFT
Definition: rangetypes.h:81
#define RANGESTRAT_EQ
Definition: rangetypes.h:89
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
bool infinite
Definition: rangetypes.h:63
ScanKey scankeys
Definition: spgist.h:133
void * palloc(Size size)
Definition: mcxt.c:949
#define RANGESTRAT_OVERLAPS
Definition: rangetypes.h:82
#define elog(elevel,...)
Definition: elog.h:228
int i
#define RANGESTRAT_AFTER
Definition: rangetypes.h:84
Datum sk_argument
Definition: skey.h:72
static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:1835
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ spg_range_quad_leaf_consistent()

Datum spg_range_quad_leaf_consistent ( PG_FUNCTION_ARGS  )

Definition at line 919 of file rangetypes_spgist.c.

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, spgLeafConsistentIn::scankeys, ScanKeyData::sk_argument, and ScanKeyData::sk_strategy.

920 {
923  RangeType *leafRange = DatumGetRangeTypeP(in->leafDatum);
924  TypeCacheEntry *typcache;
925  bool res;
926  int i;
927 
928  /* all tests are exact */
929  out->recheck = false;
930 
931  /* leafDatum is what it is... */
932  out->leafValue = in->leafDatum;
933 
934  typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
935 
936  /* Perform the required comparison(s) */
937  res = true;
938  for (i = 0; i < in->nkeys; i++)
939  {
940  Datum keyDatum = in->scankeys[i].sk_argument;
941 
942  /* Call the function corresponding to the scan strategy */
943  switch (in->scankeys[i].sk_strategy)
944  {
945  case RANGESTRAT_BEFORE:
946  res = range_before_internal(typcache, leafRange,
947  DatumGetRangeTypeP(keyDatum));
948  break;
949  case RANGESTRAT_OVERLEFT:
950  res = range_overleft_internal(typcache, leafRange,
951  DatumGetRangeTypeP(keyDatum));
952  break;
953  case RANGESTRAT_OVERLAPS:
954  res = range_overlaps_internal(typcache, leafRange,
955  DatumGetRangeTypeP(keyDatum));
956  break;
958  res = range_overright_internal(typcache, leafRange,
959  DatumGetRangeTypeP(keyDatum));
960  break;
961  case RANGESTRAT_AFTER:
962  res = range_after_internal(typcache, leafRange,
963  DatumGetRangeTypeP(keyDatum));
964  break;
965  case RANGESTRAT_ADJACENT:
966  res = range_adjacent_internal(typcache, leafRange,
967  DatumGetRangeTypeP(keyDatum));
968  break;
969  case RANGESTRAT_CONTAINS:
970  res = range_contains_internal(typcache, leafRange,
971  DatumGetRangeTypeP(keyDatum));
972  break;
974  res = range_contained_by_internal(typcache, leafRange,
975  DatumGetRangeTypeP(keyDatum));
976  break;
978  res = range_contains_elem_internal(typcache, leafRange,
979  keyDatum);
980  break;
981  case RANGESTRAT_EQ:
982  res = range_eq_internal(typcache, leafRange,
983  DatumGetRangeTypeP(keyDatum));
984  break;
985  default:
986  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  if (!res)
996  break;
997  }
998 
999  PG_RETURN_BOOL(res);
1000 }
bool range_overlaps_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:825
#define RANGESTRAT_OVERRIGHT
Definition: rangetypes.h:83
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1546
#define RANGESTRAT_ADJACENT
Definition: rangetypes.h:85
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
bool range_after_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:686
bool range_contains_elem_internal(TypeCacheEntry *typcache, const RangeType *r, Datum val)
Definition: rangetypes.c:2344
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define ERROR
Definition: elog.h:43
#define RANGESTRAT_CONTAINS_ELEM
Definition: rangetypes.h:88
#define RANGESTRAT_BEFORE
Definition: rangetypes.h:80
StrategyNumber sk_strategy
Definition: skey.h:68
ScanKey scankeys
Definition: spgist.h:168
bool range_contains_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:2303
#define RANGESTRAT_CONTAINS
Definition: rangetypes.h:86
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:349
uintptr_t Datum
Definition: postgres.h:367
bool range_overleft_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:871
bool range_before_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:648
bool range_contained_by_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:2335
#define RANGESTRAT_CONTAINED_BY
Definition: rangetypes.h:87
#define RANGESTRAT_OVERLEFT
Definition: rangetypes.h:81
#define RANGESTRAT_EQ
Definition: rangetypes.h:89
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
bool range_overright_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:912
#define RANGESTRAT_OVERLAPS
Definition: rangetypes.h:82
#define elog(elevel,...)
Definition: elog.h:228
int i
bool range_adjacent_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:782
#define RANGESTRAT_AFTER
Definition: rangetypes.h:84
Datum sk_argument
Definition: skey.h:72
bool range_eq_internal(TypeCacheEntry *typcache, const RangeType *r1, const RangeType *r2)
Definition: rangetypes.c:557

◆ spg_range_quad_picksplit()

Datum spg_range_quad_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 200 of file rangetypes_spgist.c.

References bound_cmp(), DatumGetRangeTypeP, spgPickSplitIn::datums, getQuadrant(), spgPickSplitOut::hasPrefix, i, 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.

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  {
226  range_deserialize(typcache, DatumGetRangeTypeP(in->datums[i]),
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 
254  out->leafTupleDatums[i] = RangeTypePGetDatum(range);
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 
288  out->leafTupleDatums[i] = RangeTypePGetDatum(range);
289  out->mapTuplesToNodes[i] = quadrant - 1;
290  }
291 
292  PG_RETURN_VOID();
293 }
signed short int16
Definition: c.h:354
static int bound_cmp(const void *a, const void *b, void *arg)
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1699
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1546
#define RangeTypeGetOid(r)
Definition: rangetypes.h:33
Datum * leafTupleDatums
Definition: spgist.h:125
Datum * datums
Definition: spgist.h:112
#define PointerGetDatum(X)
Definition: postgres.h:556
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:271
#define RangeTypePGetDatum(X)
Definition: rangetypes.h:73
Datum * nodeLabels
Definition: spgist.h:122
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
RangeType * range_serialize(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty)
Definition: rangetypes.c:1570
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
uintptr_t Datum
Definition: postgres.h:367
#define PG_RETURN_VOID()
Definition: fmgr.h:339
bool hasPrefix
Definition: spgist.h:118
#define DatumGetRangeTypeP(X)
Definition: rangetypes.h:71
void * palloc(Size size)
Definition: mcxt.c:949
int i
int * mapTuplesToNodes
Definition: spgist.h:124
Datum prefixDatum
Definition: spgist.h:119
static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)