PostgreSQL Source Code  git master
rangetypes_spgist.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * rangetypes_spgist.c
4  * implementation of quad tree over ranges mapped to 2d-points for SP-GiST.
5  *
6  * Quad tree is a data structure similar to a binary tree, but is adapted to
7  * 2d data. Each inner node of a quad tree contains a point (centroid) which
8  * divides the 2d-space into 4 quadrants. Each quadrant is associated with a
9  * child node.
10  *
11  * Ranges are mapped to 2d-points so that the lower bound is one dimension,
12  * and the upper bound is another. By convention, we visualize the lower bound
13  * to be the horizontal axis, and upper bound the vertical axis.
14  *
15  * One quirk with this mapping is the handling of empty ranges. An empty range
16  * doesn't have lower and upper bounds, so it cannot be mapped to 2d space in
17  * a straightforward way. To cope with that, the root node can have a 5th
18  * quadrant, which is reserved for empty ranges. Furthermore, there can be
19  * inner nodes in the tree with no centroid. They contain only two child nodes,
20  * one for empty ranges and another for non-empty ones. Such a node can appear
21  * as the root node, or in the tree under the 5th child of the root node (in
22  * which case it will only contain empty nodes).
23  *
24  * The SP-GiST picksplit function uses medians along both axes as the centroid.
25  * This implementation only uses the comparison function of the range element
26  * datatype, therefore it works for any range type.
27  *
28  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
29  * Portions Copyright (c) 1994, Regents of the University of California
30  *
31  * IDENTIFICATION
32  * src/backend/utils/adt/rangetypes_spgist.c
33  *
34  *-------------------------------------------------------------------------
35  */
36 
37 #include "postgres.h"
38 
39 #include "access/spgist.h"
40 #include "access/stratnum.h"
41 #include "catalog/pg_type.h"
42 #include "utils/datum.h"
43 #include "utils/fmgrprotos.h"
44 #include "utils/rangetypes.h"
45 
46 static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid,
47  const RangeType *tst);
48 static int bound_cmp(const void *a, const void *b, void *arg);
49 
50 static int adjacent_inner_consistent(TypeCacheEntry *typcache,
51  const RangeBound *arg, const RangeBound *centroid,
52  const RangeBound *prev);
53 static int adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg,
54  const RangeBound *centroid);
55 
56 /*
57  * SP-GiST 'config' interface function.
58  */
59 Datum
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 }
71 
72 /*----------
73  * Determine which quadrant a 2d-mapped range falls into, relative to the
74  * centroid.
75  *
76  * Quadrants are numbered like this:
77  *
78  * 4 | 1
79  * ----+----
80  * 3 | 2
81  *
82  * Where the lower bound of range is the horizontal axis and upper bound the
83  * vertical axis.
84  *
85  * Ranges on one of the axes are taken to lie in the quadrant with higher value
86  * along perpendicular axis. That is, a value on the horizontal axis is taken
87  * to belong to quadrant 1 or 4, and a value on the vertical axis is taken to
88  * belong to quadrant 1 or 2. A range equal to centroid is taken to lie in
89  * quadrant 1.
90  *
91  * Empty ranges are taken to lie in the special quadrant 5.
92  *----------
93  */
94 static int16
95 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
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 }
126 
127 /*
128  * Choose SP-GiST function: choose path for addition of new range.
129  */
130 Datum
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 }
181 
182 /*
183  * Bound comparison for sorting.
184  */
185 static int
186 bound_cmp(const void *a, const void *b, void *arg)
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 }
194 
195 /*
196  * Picksplit SP-GiST function: split ranges into nodes. Select "centroid"
197  * range and distribute ranges according to quadrants.
198  */
199 Datum
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, 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 
292  PG_RETURN_VOID();
293 }
294 
295 /*
296  * SP-GiST consistent function for inner nodes: check which nodes are
297  * consistent with given set of queries.
298  */
299 Datum
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 }
771 
772 /*
773  * adjacent_cmp_bounds
774  *
775  * Given an argument and centroid bound, this function determines if any
776  * bounds that are adjacent to the argument are smaller than, or greater than
777  * or equal to centroid. For brevity, we call the arg < centroid "left", and
778  * arg >= centroid case "right". This corresponds to how the quadrants are
779  * arranged, if you imagine that "left" is equivalent to "down" and "right"
780  * is equivalent to "up".
781  *
782  * For the "left" case, returns -1, and for the "right" case, returns 1.
783  */
784 static int
786  const RangeBound *centroid)
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 }
849 
850 /*----------
851  * adjacent_inner_consistent
852  *
853  * Like adjacent_cmp_bounds, but also takes into account the previous
854  * level's centroid. We might've traversed left (or right) at the previous
855  * node, in search for ranges adjacent to the other bound, even though we
856  * already ruled out the possibility for any matches in that direction for
857  * this bound. By comparing the argument with the previous centroid, and
858  * the previous centroid with the current centroid, we can determine which
859  * direction we should've moved in at previous level, and which direction we
860  * actually moved.
861  *
862  * If there can be any matches to the left, returns -1. If to the right,
863  * returns 1. If there can be no matches below this centroid, because we
864  * already ruled them out at the previous level, returns 0.
865  *
866  * XXX: Comparing just the previous and current level isn't foolproof; we
867  * might still search some branches unnecessarily. For example, imagine that
868  * we are searching for value 15, and we traverse the following centroids
869  * (only considering one bound for the moment):
870  *
871  * Level 1: 20
872  * Level 2: 50
873  * Level 3: 25
874  *
875  * At this point, previous centroid is 50, current centroid is 25, and the
876  * target value is to the left. But because we already moved right from
877  * centroid 20 to 50 in the first level, there cannot be any values < 20 in
878  * the current branch. But we don't know that just by looking at the previous
879  * and current centroid, so we traverse left, unnecessarily. The reason we are
880  * down this branch is that we're searching for matches with the *other*
881  * bound. If we kept track of which bound we are searching for explicitly,
882  * instead of deducing that from the previous and current centroid, we could
883  * avoid some unnecessary work.
884  *----------
885  */
886 static int
888  const RangeBound *centroid, const RangeBound *prev)
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 }
911 
912 /*
913  * SP-GiST consistent function for leaf nodes: check leaf value against query
914  * using corresponding function.
915  */
916 Datum
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 }
signed short int16
Definition: c.h:480
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void * palloc(Size size)
Definition: mcxt.c:1304
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
void * arg
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:322
uintptr_t Datum
Definition: postgres.h:64
int range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1, const RangeBound *b2)
Definition: rangetypes.c:2016
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 bounds_adjacent(TypeCacheEntry *typcache, RangeBound boundA, RangeBound boundB)
Definition: rangetypes.c:757
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
void range_deserialize(TypeCacheEntry *typcache, const RangeType *range, RangeBound *lower, RangeBound *upper, bool *empty)
Definition: rangetypes.c:1856
TypeCacheEntry * range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
Definition: rangetypes.c:1703
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
RangeType * range_serialize(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper, bool empty, struct Node *escontext)
Definition: rangetypes.c:1727
#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 RangeIsEmpty(r)
Definition: rangetypes.h:55
static Datum RangeTypePGetDatum(const RangeType *X)
Definition: rangetypes.h:85
#define RANGESTRAT_EQ
Definition: rangetypes.h:105
#define RANGESTRAT_ADJACENT
Definition: rangetypes.h:101
static RangeType * DatumGetRangeTypeP(Datum X)
Definition: rangetypes.h:73
#define RANGESTRAT_CONTAINS_ELEM
Definition: rangetypes.h:104
#define RANGESTRAT_CONTAINS
Definition: rangetypes.h:102
#define RangeTypeGetOid(r)
Definition: rangetypes.h:35
static int adjacent_inner_consistent(TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid, const RangeBound *prev)
Datum spg_range_quad_config(PG_FUNCTION_ARGS)
Datum spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
Datum spg_range_quad_picksplit(PG_FUNCTION_ARGS)
static int adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg, const RangeBound *centroid)
Datum spg_range_quad_inner_consistent(PG_FUNCTION_ARGS)
Datum spg_range_quad_choose(PG_FUNCTION_ARGS)
static int bound_cmp(const void *a, const void *b, void *arg)
static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
@ spgMatchNode
Definition: spgist.h:69
uint16 StrategyNumber
Definition: stratnum.h:22
bool lower
Definition: rangetypes.h:66
Datum sk_argument
Definition: skey.h:72
StrategyNumber sk_strategy
Definition: skey.h:68
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::@47 result
struct spgChooseOut::@47::@48 matchNode
bool longValuesOK
Definition: spgist.h:47
bool canReturnData
Definition: spgist.h:46
Oid labelType
Definition: spgist.h:44
Oid prefixType
Definition: spgist.h:43
void * traversalValue
Definition: spgist.h:141
ScanKey scankeys
Definition: spgist.h:134
MemoryContext traversalMemoryContext
Definition: spgist.h:142
void ** traversalValues
Definition: spgist.h:160
ScanKey scankeys
Definition: spgist.h:169
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