PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
gistproc.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * gistproc.c
4  * Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
5  * points).
6  *
7  * This gives R-tree behavior, with Guttman's poly-time split algorithm.
8  *
9  *
10  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
11  * Portions Copyright (c) 1994, Regents of the University of California
12  *
13  * IDENTIFICATION
14  * src/backend/access/gist/gistproc.c
15  *
16  *-------------------------------------------------------------------------
17  */
18 #include "postgres.h"
19 
20 #include <float.h>
21 #include <math.h>
22 
23 #include "access/gist.h"
24 #include "access/stratnum.h"
25 #include "utils/builtins.h"
26 #include "utils/geo_decls.h"
27 
28 
29 static bool gist_box_leaf_consistent(BOX *key, BOX *query,
30  StrategyNumber strategy);
31 static bool rtree_internal_consistent(BOX *key, BOX *query,
32  StrategyNumber strategy);
33 
34 /* Minimum accepted ratio of split */
35 #define LIMIT_RATIO 0.3
36 
37 /* Convenience macros for NaN-aware comparisons */
38 #define FLOAT8_EQ(a,b) (float8_cmp_internal(a, b) == 0)
39 #define FLOAT8_LT(a,b) (float8_cmp_internal(a, b) < 0)
40 #define FLOAT8_LE(a,b) (float8_cmp_internal(a, b) <= 0)
41 #define FLOAT8_GT(a,b) (float8_cmp_internal(a, b) > 0)
42 #define FLOAT8_GE(a,b) (float8_cmp_internal(a, b) >= 0)
43 #define FLOAT8_MAX(a,b) (FLOAT8_GT(a, b) ? (a) : (b))
44 #define FLOAT8_MIN(a,b) (FLOAT8_LT(a, b) ? (a) : (b))
45 
46 
47 /**************************************************
48  * Box ops
49  **************************************************/
50 
51 /*
52  * Calculates union of two boxes, a and b. The result is stored in *n.
53  */
54 static void
55 rt_box_union(BOX *n, const BOX *a, const BOX *b)
56 {
57  n->high.x = FLOAT8_MAX(a->high.x, b->high.x);
58  n->high.y = FLOAT8_MAX(a->high.y, b->high.y);
59  n->low.x = FLOAT8_MIN(a->low.x, b->low.x);
60  n->low.y = FLOAT8_MIN(a->low.y, b->low.y);
61 }
62 
63 /*
64  * Size of a BOX for penalty-calculation purposes.
65  * The result can be +Infinity, but not NaN.
66  */
67 static double
68 size_box(const BOX *box)
69 {
70  /*
71  * Check for zero-width cases. Note that we define the size of a zero-
72  * by-infinity box as zero. It's important to special-case this somehow,
73  * as naively multiplying infinity by zero will produce NaN.
74  *
75  * The less-than cases should not happen, but if they do, say "zero".
76  */
77  if (FLOAT8_LE(box->high.x, box->low.x) ||
78  FLOAT8_LE(box->high.y, box->low.y))
79  return 0.0;
80 
81  /*
82  * We treat NaN as larger than +Infinity, so any distance involving a NaN
83  * and a non-NaN is infinite. Note the previous check eliminated the
84  * possibility that the low fields are NaNs.
85  */
86  if (isnan(box->high.x) || isnan(box->high.y))
87  return get_float8_infinity();
88  return (box->high.x - box->low.x) * (box->high.y - box->low.y);
89 }
90 
91 /*
92  * Return amount by which the union of the two boxes is larger than
93  * the original BOX's area. The result can be +Infinity, but not NaN.
94  */
95 static double
96 box_penalty(const BOX *original, const BOX *new)
97 {
98  BOX unionbox;
99 
100  rt_box_union(&unionbox, original, new);
101  return size_box(&unionbox) - size_box(original);
102 }
103 
104 /*
105  * The GiST Consistent method for boxes
106  *
107  * Should return false if for all data items x below entry,
108  * the predicate x op query must be FALSE, where op is the oper
109  * corresponding to strategy in the pg_amop table.
110  */
111 Datum
113 {
114  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
115  BOX *query = PG_GETARG_BOX_P(1);
117 
118  /* Oid subtype = PG_GETARG_OID(3); */
119  bool *recheck = (bool *) PG_GETARG_POINTER(4);
120 
121  /* All cases served by this function are exact */
122  *recheck = false;
123 
124  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
126 
127  /*
128  * if entry is not leaf, use rtree_internal_consistent, else use
129  * gist_box_leaf_consistent
130  */
131  if (GIST_LEAF(entry))
133  query,
134  strategy));
135  else
137  query,
138  strategy));
139 }
140 
141 /*
142  * Increase BOX b to include addon.
143  */
144 static void
145 adjustBox(BOX *b, const BOX *addon)
146 {
147  if (FLOAT8_LT(b->high.x, addon->high.x))
148  b->high.x = addon->high.x;
149  if (FLOAT8_GT(b->low.x, addon->low.x))
150  b->low.x = addon->low.x;
151  if (FLOAT8_LT(b->high.y, addon->high.y))
152  b->high.y = addon->high.y;
153  if (FLOAT8_GT(b->low.y, addon->low.y))
154  b->low.y = addon->low.y;
155 }
156 
157 /*
158  * The GiST Union method for boxes
159  *
160  * returns the minimal bounding box that encloses all the entries in entryvec
161  */
162 Datum
164 {
166  int *sizep = (int *) PG_GETARG_POINTER(1);
167  int numranges,
168  i;
169  BOX *cur,
170  *pageunion;
171 
172  numranges = entryvec->n;
173  pageunion = (BOX *) palloc(sizeof(BOX));
174  cur = DatumGetBoxP(entryvec->vector[0].key);
175  memcpy((void *) pageunion, (void *) cur, sizeof(BOX));
176 
177  for (i = 1; i < numranges; i++)
178  {
179  cur = DatumGetBoxP(entryvec->vector[i].key);
180  adjustBox(pageunion, cur);
181  }
182  *sizep = sizeof(BOX);
183 
184  PG_RETURN_POINTER(pageunion);
185 }
186 
187 /*
188  * GiST Compress methods for boxes
189  *
190  * do not do anything.
191  */
192 Datum
194 {
196 }
197 
198 /*
199  * GiST DeCompress method for boxes (also used for points, polygons
200  * and circles)
201  *
202  * do not do anything --- we just use the stored box as is.
203  */
204 Datum
206 {
208 }
209 
210 /*
211  * GiST Fetch method for boxes
212  * do not do anything --- we just return the stored box as is.
213  */
214 Datum
216 {
218 }
219 
220 /*
221  * The GiST Penalty method for boxes (also used for points)
222  *
223  * As in the R-tree paper, we use change in area as our penalty metric
224  */
225 Datum
227 {
228  GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
229  GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
230  float *result = (float *) PG_GETARG_POINTER(2);
231  BOX *origbox = DatumGetBoxP(origentry->key);
232  BOX *newbox = DatumGetBoxP(newentry->key);
233 
234  *result = (float) box_penalty(origbox, newbox);
235  PG_RETURN_POINTER(result);
236 }
237 
238 /*
239  * Trivial split: half of entries will be placed on one page
240  * and another half - to another
241  */
242 static void
244 {
245  OffsetNumber i,
246  maxoff;
247  BOX *unionL = NULL,
248  *unionR = NULL;
249  int nbytes;
250 
251  maxoff = entryvec->n - 1;
252 
253  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
254  v->spl_left = (OffsetNumber *) palloc(nbytes);
255  v->spl_right = (OffsetNumber *) palloc(nbytes);
256  v->spl_nleft = v->spl_nright = 0;
257 
258  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
259  {
260  BOX *cur = DatumGetBoxP(entryvec->vector[i].key);
261 
262  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
263  {
264  v->spl_left[v->spl_nleft] = i;
265  if (unionL == NULL)
266  {
267  unionL = (BOX *) palloc(sizeof(BOX));
268  *unionL = *cur;
269  }
270  else
271  adjustBox(unionL, cur);
272 
273  v->spl_nleft++;
274  }
275  else
276  {
277  v->spl_right[v->spl_nright] = i;
278  if (unionR == NULL)
279  {
280  unionR = (BOX *) palloc(sizeof(BOX));
281  *unionR = *cur;
282  }
283  else
284  adjustBox(unionR, cur);
285 
286  v->spl_nright++;
287  }
288  }
289 
290  v->spl_ldatum = BoxPGetDatum(unionL);
291  v->spl_rdatum = BoxPGetDatum(unionR);
292 }
293 
294 /*
295  * Represents information about an entry that can be placed to either group
296  * without affecting overlap over selected axis ("common entry").
297  */
298 typedef struct
299 {
300  /* Index of entry in the initial array */
301  int index;
302  /* Delta between penalties of entry insertion into different groups */
303  double delta;
304 } CommonEntry;
305 
306 /*
307  * Context for g_box_consider_split. Contains information about currently
308  * selected split and some general information.
309  */
310 typedef struct
311 {
312  int entriesCount; /* total number of entries being split */
313  BOX boundingBox; /* minimum bounding box across all entries */
314 
315  /* Information about currently selected split follows */
316 
317  bool first; /* true if no split was selected yet */
318 
319  double leftUpper; /* upper bound of left interval */
320  double rightLower; /* lower bound of right interval */
321 
324  int dim; /* axis of this split */
325  double range; /* width of general MBR projection to the
326  * selected axis */
328 
329 /*
330  * Interval represents projection of box to axis.
331  */
332 typedef struct
333 {
334  double lower,
335  upper;
336 } SplitInterval;
337 
338 /*
339  * Interval comparison function by lower bound of the interval;
340  */
341 static int
342 interval_cmp_lower(const void *i1, const void *i2)
343 {
344  double lower1 = ((const SplitInterval *) i1)->lower,
345  lower2 = ((const SplitInterval *) i2)->lower;
346 
347  return float8_cmp_internal(lower1, lower2);
348 }
349 
350 /*
351  * Interval comparison function by upper bound of the interval;
352  */
353 static int
354 interval_cmp_upper(const void *i1, const void *i2)
355 {
356  double upper1 = ((const SplitInterval *) i1)->upper,
357  upper2 = ((const SplitInterval *) i2)->upper;
358 
359  return float8_cmp_internal(upper1, upper2);
360 }
361 
362 /*
363  * Replace negative (or NaN) value with zero.
364  */
365 static inline float
367 {
368  if (val >= 0.0f)
369  return val;
370  else
371  return 0.0f;
372 }
373 
374 /*
375  * Consider replacement of currently selected split with the better one.
376  */
377 static inline void
379  double rightLower, int minLeftCount,
380  double leftUpper, int maxLeftCount)
381 {
382  int leftCount,
383  rightCount;
384  float4 ratio,
385  overlap;
386  double range;
387 
388  /*
389  * Calculate entries distribution ratio assuming most uniform distribution
390  * of common entries.
391  */
392  if (minLeftCount >= (context->entriesCount + 1) / 2)
393  {
394  leftCount = minLeftCount;
395  }
396  else
397  {
398  if (maxLeftCount <= context->entriesCount / 2)
399  leftCount = maxLeftCount;
400  else
401  leftCount = context->entriesCount / 2;
402  }
403  rightCount = context->entriesCount - leftCount;
404 
405  /*
406  * Ratio of split - quotient between size of lesser group and total
407  * entries count.
408  */
409  ratio = ((float4) Min(leftCount, rightCount)) /
410  ((float4) context->entriesCount);
411 
412  if (ratio > LIMIT_RATIO)
413  {
414  bool selectthis = false;
415 
416  /*
417  * The ratio is acceptable, so compare current split with previously
418  * selected one. Between splits of one dimension we search for minimal
419  * overlap (allowing negative values) and minimal ration (between same
420  * overlaps. We switch dimension if find less overlap (non-negative)
421  * or less range with same overlap.
422  */
423  if (dimNum == 0)
424  range = context->boundingBox.high.x - context->boundingBox.low.x;
425  else
426  range = context->boundingBox.high.y - context->boundingBox.low.y;
427 
428  overlap = (leftUpper - rightLower) / range;
429 
430  /* If there is no previous selection, select this */
431  if (context->first)
432  selectthis = true;
433  else if (context->dim == dimNum)
434  {
435  /*
436  * Within the same dimension, choose the new split if it has a
437  * smaller overlap, or same overlap but better ratio.
438  */
439  if (overlap < context->overlap ||
440  (overlap == context->overlap && ratio > context->ratio))
441  selectthis = true;
442  }
443  else
444  {
445  /*
446  * Across dimensions, choose the new split if it has a smaller
447  * *non-negative* overlap, or same *non-negative* overlap but
448  * bigger range. This condition differs from the one described in
449  * the article. On the datasets where leaf MBRs don't overlap
450  * themselves, non-overlapping splits (i.e. splits which have zero
451  * *non-negative* overlap) are frequently possible. In this case
452  * splits tends to be along one dimension, because most distant
453  * non-overlapping splits (i.e. having lowest negative overlap)
454  * appears to be in the same dimension as in the previous split.
455  * Therefore MBRs appear to be very prolonged along another
456  * dimension, which leads to bad search performance. Using range
457  * as the second split criteria makes MBRs more quadratic. Using
458  * *non-negative* overlap instead of overlap as the first split
459  * criteria gives to range criteria a chance to matter, because
460  * non-overlapping splits are equivalent in this criteria.
461  */
462  if (non_negative(overlap) < non_negative(context->overlap) ||
463  (range > context->range &&
464  non_negative(overlap) <= non_negative(context->overlap)))
465  selectthis = true;
466  }
467 
468  if (selectthis)
469  {
470  /* save information about selected split */
471  context->first = false;
472  context->ratio = ratio;
473  context->range = range;
474  context->overlap = overlap;
475  context->rightLower = rightLower;
476  context->leftUpper = leftUpper;
477  context->dim = dimNum;
478  }
479  }
480 }
481 
482 /*
483  * Compare common entries by their deltas.
484  * (We assume the deltas can't be NaN.)
485  */
486 static int
487 common_entry_cmp(const void *i1, const void *i2)
488 {
489  double delta1 = ((const CommonEntry *) i1)->delta,
490  delta2 = ((const CommonEntry *) i2)->delta;
491 
492  if (delta1 < delta2)
493  return -1;
494  else if (delta1 > delta2)
495  return 1;
496  else
497  return 0;
498 }
499 
500 /*
501  * --------------------------------------------------------------------------
502  * Double sorting split algorithm. This is used for both boxes and points.
503  *
504  * The algorithm finds split of boxes by considering splits along each axis.
505  * Each entry is first projected as an interval on the X-axis, and different
506  * ways to split the intervals into two groups are considered, trying to
507  * minimize the overlap of the groups. Then the same is repeated for the
508  * Y-axis, and the overall best split is chosen. The quality of a split is
509  * determined by overlap along that axis and some other criteria (see
510  * g_box_consider_split).
511  *
512  * After that, all the entries are divided into three groups:
513  *
514  * 1) Entries which should be placed to the left group
515  * 2) Entries which should be placed to the right group
516  * 3) "Common entries" which can be placed to any of groups without affecting
517  * of overlap along selected axis.
518  *
519  * The common entries are distributed by minimizing penalty.
520  *
521  * For details see:
522  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
523  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
524  * --------------------------------------------------------------------------
525  */
526 Datum
528 {
531  OffsetNumber i,
532  maxoff;
533  ConsiderSplitContext context;
534  BOX *box,
535  *leftBox,
536  *rightBox;
537  int dim,
538  commonEntriesCount;
539  SplitInterval *intervalsLower,
540  *intervalsUpper;
541  CommonEntry *commonEntries;
542  int nentries;
543 
544  memset(&context, 0, sizeof(ConsiderSplitContext));
545 
546  maxoff = entryvec->n - 1;
547  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
548 
549  /* Allocate arrays for intervals along axes */
550  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
551  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
552 
553  /*
554  * Calculate the overall minimum bounding box over all the entries.
555  */
556  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
557  {
558  box = DatumGetBoxP(entryvec->vector[i].key);
559  if (i == FirstOffsetNumber)
560  context.boundingBox = *box;
561  else
562  adjustBox(&context.boundingBox, box);
563  }
564 
565  /*
566  * Iterate over axes for optimal split searching.
567  */
568  context.first = true; /* nothing selected yet */
569  for (dim = 0; dim < 2; dim++)
570  {
571  double leftUpper,
572  rightLower;
573  int i1,
574  i2;
575 
576  /* Project each entry as an interval on the selected axis. */
577  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
578  {
579  box = DatumGetBoxP(entryvec->vector[i].key);
580  if (dim == 0)
581  {
582  intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
583  intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
584  }
585  else
586  {
587  intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
588  intervalsLower[i - FirstOffsetNumber].upper = box->high.y;
589  }
590  }
591 
592  /*
593  * Make two arrays of intervals: one sorted by lower bound and another
594  * sorted by upper bound.
595  */
596  memcpy(intervalsUpper, intervalsLower,
597  sizeof(SplitInterval) * nentries);
598  qsort(intervalsLower, nentries, sizeof(SplitInterval),
600  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
602 
603  /*----
604  * The goal is to form a left and right interval, so that every entry
605  * interval is contained by either left or right interval (or both).
606  *
607  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
608  *
609  * 0 1 2 3 4
610  * +-+
611  * +---+
612  * +-+
613  * +---+
614  *
615  * The left and right intervals are of the form (0,a) and (b,4).
616  * We first consider splits where b is the lower bound of an entry.
617  * We iterate through all entries, and for each b, calculate the
618  * smallest possible a. Then we consider splits where a is the
619  * upper bound of an entry, and for each a, calculate the greatest
620  * possible b.
621  *
622  * In the above example, the first loop would consider splits:
623  * b=0: (0,1)-(0,4)
624  * b=1: (0,1)-(1,4)
625  * b=2: (0,3)-(2,4)
626  *
627  * And the second loop:
628  * a=1: (0,1)-(1,4)
629  * a=3: (0,3)-(2,4)
630  * a=4: (0,4)-(2,4)
631  */
632 
633  /*
634  * Iterate over lower bound of right group, finding smallest possible
635  * upper bound of left group.
636  */
637  i1 = 0;
638  i2 = 0;
639  rightLower = intervalsLower[i1].lower;
640  leftUpper = intervalsUpper[i2].lower;
641  while (true)
642  {
643  /*
644  * Find next lower bound of right group.
645  */
646  while (i1 < nentries &&
647  FLOAT8_EQ(rightLower, intervalsLower[i1].lower))
648  {
649  if (FLOAT8_LT(leftUpper, intervalsLower[i1].upper))
650  leftUpper = intervalsLower[i1].upper;
651  i1++;
652  }
653  if (i1 >= nentries)
654  break;
655  rightLower = intervalsLower[i1].lower;
656 
657  /*
658  * Find count of intervals which anyway should be placed to the
659  * left group.
660  */
661  while (i2 < nentries &&
662  FLOAT8_LE(intervalsUpper[i2].upper, leftUpper))
663  i2++;
664 
665  /*
666  * Consider found split.
667  */
668  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
669  }
670 
671  /*
672  * Iterate over upper bound of left group finding greatest possible
673  * lower bound of right group.
674  */
675  i1 = nentries - 1;
676  i2 = nentries - 1;
677  rightLower = intervalsLower[i1].upper;
678  leftUpper = intervalsUpper[i2].upper;
679  while (true)
680  {
681  /*
682  * Find next upper bound of left group.
683  */
684  while (i2 >= 0 && FLOAT8_EQ(leftUpper, intervalsUpper[i2].upper))
685  {
686  if (FLOAT8_GT(rightLower, intervalsUpper[i2].lower))
687  rightLower = intervalsUpper[i2].lower;
688  i2--;
689  }
690  if (i2 < 0)
691  break;
692  leftUpper = intervalsUpper[i2].upper;
693 
694  /*
695  * Find count of intervals which anyway should be placed to the
696  * right group.
697  */
698  while (i1 >= 0 && FLOAT8_GE(intervalsLower[i1].lower, rightLower))
699  i1--;
700 
701  /*
702  * Consider found split.
703  */
704  g_box_consider_split(&context, dim,
705  rightLower, i1 + 1, leftUpper, i2 + 1);
706  }
707  }
708 
709  /*
710  * If we failed to find any acceptable splits, use trivial split.
711  */
712  if (context.first)
713  {
714  fallbackSplit(entryvec, v);
716  }
717 
718  /*
719  * Ok, we have now selected the split across one axis.
720  *
721  * While considering the splits, we already determined that there will be
722  * enough entries in both groups to reach the desired ratio, but we did
723  * not memorize which entries go to which group. So determine that now.
724  */
725 
726  /* Allocate vectors for results */
727  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
728  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
729  v->spl_nleft = 0;
730  v->spl_nright = 0;
731 
732  /* Allocate bounding boxes of left and right groups */
733  leftBox = palloc0(sizeof(BOX));
734  rightBox = palloc0(sizeof(BOX));
735 
736  /*
737  * Allocate an array for "common entries" - entries which can be placed to
738  * either group without affecting overlap along selected axis.
739  */
740  commonEntriesCount = 0;
741  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
742 
743  /* Helper macros to place an entry in the left or right group */
744 #define PLACE_LEFT(box, off) \
745  do { \
746  if (v->spl_nleft > 0) \
747  adjustBox(leftBox, box); \
748  else \
749  *leftBox = *(box); \
750  v->spl_left[v->spl_nleft++] = off; \
751  } while(0)
752 
753 #define PLACE_RIGHT(box, off) \
754  do { \
755  if (v->spl_nright > 0) \
756  adjustBox(rightBox, box); \
757  else \
758  *rightBox = *(box); \
759  v->spl_right[v->spl_nright++] = off; \
760  } while(0)
761 
762  /*
763  * Distribute entries which can be distributed unambiguously, and collect
764  * common entries.
765  */
766  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
767  {
768  double lower,
769  upper;
770 
771  /*
772  * Get upper and lower bounds along selected axis.
773  */
774  box = DatumGetBoxP(entryvec->vector[i].key);
775  if (context.dim == 0)
776  {
777  lower = box->low.x;
778  upper = box->high.x;
779  }
780  else
781  {
782  lower = box->low.y;
783  upper = box->high.y;
784  }
785 
786  if (FLOAT8_LE(upper, context.leftUpper))
787  {
788  /* Fits to the left group */
789  if (FLOAT8_GE(lower, context.rightLower))
790  {
791  /* Fits also to the right group, so "common entry" */
792  commonEntries[commonEntriesCount++].index = i;
793  }
794  else
795  {
796  /* Doesn't fit to the right group, so join to the left group */
797  PLACE_LEFT(box, i);
798  }
799  }
800  else
801  {
802  /*
803  * Each entry should fit on either left or right group. Since this
804  * entry didn't fit on the left group, it better fit in the right
805  * group.
806  */
807  Assert(FLOAT8_GE(lower, context.rightLower));
808 
809  /* Doesn't fit to the left group, so join to the right group */
810  PLACE_RIGHT(box, i);
811  }
812  }
813 
814  /*
815  * Distribute "common entries", if any.
816  */
817  if (commonEntriesCount > 0)
818  {
819  /*
820  * Calculate minimum number of entries that must be placed in both
821  * groups, to reach LIMIT_RATIO.
822  */
823  int m = ceil(LIMIT_RATIO * (double) nentries);
824 
825  /*
826  * Calculate delta between penalties of join "common entries" to
827  * different groups.
828  */
829  for (i = 0; i < commonEntriesCount; i++)
830  {
831  box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
832  commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
833  box_penalty(rightBox, box));
834  }
835 
836  /*
837  * Sort "common entries" by calculated deltas in order to distribute
838  * the most ambiguous entries first.
839  */
840  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
841 
842  /*
843  * Distribute "common entries" between groups.
844  */
845  for (i = 0; i < commonEntriesCount; i++)
846  {
847  box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
848 
849  /*
850  * Check if we have to place this entry in either group to achieve
851  * LIMIT_RATIO.
852  */
853  if (v->spl_nleft + (commonEntriesCount - i) <= m)
854  PLACE_LEFT(box, commonEntries[i].index);
855  else if (v->spl_nright + (commonEntriesCount - i) <= m)
856  PLACE_RIGHT(box, commonEntries[i].index);
857  else
858  {
859  /* Otherwise select the group by minimal penalty */
860  if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
861  PLACE_LEFT(box, commonEntries[i].index);
862  else
863  PLACE_RIGHT(box, commonEntries[i].index);
864  }
865  }
866  }
867 
868  v->spl_ldatum = PointerGetDatum(leftBox);
869  v->spl_rdatum = PointerGetDatum(rightBox);
871 }
872 
873 /*
874  * Equality method
875  *
876  * This is used for boxes, points, circles, and polygons, all of which store
877  * boxes as GiST index entries.
878  *
879  * Returns true only when boxes are exactly the same. We can't use fuzzy
880  * comparisons here without breaking index consistency; therefore, this isn't
881  * equivalent to box_same().
882  */
883 Datum
885 {
886  BOX *b1 = PG_GETARG_BOX_P(0);
887  BOX *b2 = PG_GETARG_BOX_P(1);
888  bool *result = (bool *) PG_GETARG_POINTER(2);
889 
890  if (b1 && b2)
891  *result = (FLOAT8_EQ(b1->low.x, b2->low.x) &&
892  FLOAT8_EQ(b1->low.y, b2->low.y) &&
893  FLOAT8_EQ(b1->high.x, b2->high.x) &&
894  FLOAT8_EQ(b1->high.y, b2->high.y));
895  else
896  *result = (b1 == NULL && b2 == NULL);
897  PG_RETURN_POINTER(result);
898 }
899 
900 /*
901  * Leaf-level consistency for boxes: just apply the query operator
902  */
903 static bool
905 {
906  bool retval;
907 
908  switch (strategy)
909  {
912  PointerGetDatum(key),
913  PointerGetDatum(query)));
914  break;
917  PointerGetDatum(key),
918  PointerGetDatum(query)));
919  break;
922  PointerGetDatum(key),
923  PointerGetDatum(query)));
924  break;
927  PointerGetDatum(key),
928  PointerGetDatum(query)));
929  break;
932  PointerGetDatum(key),
933  PointerGetDatum(query)));
934  break;
937  PointerGetDatum(key),
938  PointerGetDatum(query)));
939  break;
943  PointerGetDatum(key),
944  PointerGetDatum(query)));
945  break;
949  PointerGetDatum(key),
950  PointerGetDatum(query)));
951  break;
954  PointerGetDatum(key),
955  PointerGetDatum(query)));
956  break;
959  PointerGetDatum(key),
960  PointerGetDatum(query)));
961  break;
964  PointerGetDatum(key),
965  PointerGetDatum(query)));
966  break;
969  PointerGetDatum(key),
970  PointerGetDatum(query)));
971  break;
972  default:
973  elog(ERROR, "unrecognized strategy number: %d", strategy);
974  retval = false; /* keep compiler quiet */
975  break;
976  }
977  return retval;
978 }
979 
980 /*****************************************
981  * Common rtree functions (for boxes, polygons, and circles)
982  *****************************************/
983 
984 /*
985  * Internal-page consistency for all these types
986  *
987  * We can use the same function since all types use bounding boxes as the
988  * internal-page representation.
989  */
990 static bool
992 {
993  bool retval;
994 
995  switch (strategy)
996  {
999  PointerGetDatum(key),
1000  PointerGetDatum(query)));
1001  break;
1004  PointerGetDatum(key),
1005  PointerGetDatum(query)));
1006  break;
1009  PointerGetDatum(key),
1010  PointerGetDatum(query)));
1011  break;
1014  PointerGetDatum(key),
1015  PointerGetDatum(query)));
1016  break;
1017  case RTRightStrategyNumber:
1019  PointerGetDatum(key),
1020  PointerGetDatum(query)));
1021  break;
1022  case RTSameStrategyNumber:
1026  PointerGetDatum(key),
1027  PointerGetDatum(query)));
1028  break;
1032  PointerGetDatum(key),
1033  PointerGetDatum(query)));
1034  break;
1037  PointerGetDatum(key),
1038  PointerGetDatum(query)));
1039  break;
1040  case RTBelowStrategyNumber:
1042  PointerGetDatum(key),
1043  PointerGetDatum(query)));
1044  break;
1045  case RTAboveStrategyNumber:
1047  PointerGetDatum(key),
1048  PointerGetDatum(query)));
1049  break;
1052  PointerGetDatum(key),
1053  PointerGetDatum(query)));
1054  break;
1055  default:
1056  elog(ERROR, "unrecognized strategy number: %d", strategy);
1057  retval = false; /* keep compiler quiet */
1058  break;
1059  }
1060  return retval;
1061 }
1062 
1063 /**************************************************
1064  * Polygon ops
1065  **************************************************/
1066 
1067 /*
1068  * GiST compress for polygons: represent a polygon by its bounding box
1069  */
1070 Datum
1072 {
1073  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1074  GISTENTRY *retval;
1075 
1076  if (entry->leafkey)
1077  {
1078  POLYGON *in = DatumGetPolygonP(entry->key);
1079  BOX *r;
1080 
1081  r = (BOX *) palloc(sizeof(BOX));
1082  memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
1083 
1084  retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1085  gistentryinit(*retval, PointerGetDatum(r),
1086  entry->rel, entry->page,
1087  entry->offset, FALSE);
1088  }
1089  else
1090  retval = entry;
1091  PG_RETURN_POINTER(retval);
1092 }
1093 
1094 /*
1095  * The GiST Consistent method for polygons
1096  */
1097 Datum
1099 {
1100  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1101  POLYGON *query = PG_GETARG_POLYGON_P(1);
1103 
1104  /* Oid subtype = PG_GETARG_OID(3); */
1105  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1106  bool result;
1107 
1108  /* All cases served by this function are inexact */
1109  *recheck = true;
1110 
1111  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1113 
1114  /*
1115  * Since the operators require recheck anyway, we can just use
1116  * rtree_internal_consistent even at leaf nodes. (This works in part
1117  * because the index entries are bounding boxes not polygons.)
1118  */
1119  result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1120  &(query->boundbox), strategy);
1121 
1122  /* Avoid memory leak if supplied poly is toasted */
1123  PG_FREE_IF_COPY(query, 1);
1124 
1125  PG_RETURN_BOOL(result);
1126 }
1127 
1128 /**************************************************
1129  * Circle ops
1130  **************************************************/
1131 
1132 /*
1133  * GiST compress for circles: represent a circle by its bounding box
1134  */
1135 Datum
1137 {
1138  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1139  GISTENTRY *retval;
1140 
1141  if (entry->leafkey)
1142  {
1143  CIRCLE *in = DatumGetCircleP(entry->key);
1144  BOX *r;
1145 
1146  r = (BOX *) palloc(sizeof(BOX));
1147  r->high.x = in->center.x + in->radius;
1148  r->low.x = in->center.x - in->radius;
1149  r->high.y = in->center.y + in->radius;
1150  r->low.y = in->center.y - in->radius;
1151 
1152  retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1153  gistentryinit(*retval, PointerGetDatum(r),
1154  entry->rel, entry->page,
1155  entry->offset, FALSE);
1156  }
1157  else
1158  retval = entry;
1159  PG_RETURN_POINTER(retval);
1160 }
1161 
1162 /*
1163  * The GiST Consistent method for circles
1164  */
1165 Datum
1167 {
1168  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1169  CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1171 
1172  /* Oid subtype = PG_GETARG_OID(3); */
1173  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1174  BOX bbox;
1175  bool result;
1176 
1177  /* All cases served by this function are inexact */
1178  *recheck = true;
1179 
1180  if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1182 
1183  /*
1184  * Since the operators require recheck anyway, we can just use
1185  * rtree_internal_consistent even at leaf nodes. (This works in part
1186  * because the index entries are bounding boxes not circles.)
1187  */
1188  bbox.high.x = query->center.x + query->radius;
1189  bbox.low.x = query->center.x - query->radius;
1190  bbox.high.y = query->center.y + query->radius;
1191  bbox.low.y = query->center.y - query->radius;
1192 
1193  result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1194  &bbox, strategy);
1195 
1196  PG_RETURN_BOOL(result);
1197 }
1198 
1199 /**************************************************
1200  * Point ops
1201  **************************************************/
1202 
1203 Datum
1205 {
1206  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1207 
1208  if (entry->leafkey) /* Point, actually */
1209  {
1210  BOX *box = palloc(sizeof(BOX));
1211  Point *point = DatumGetPointP(entry->key);
1212  GISTENTRY *retval = palloc(sizeof(GISTENTRY));
1213 
1214  box->high = box->low = *point;
1215 
1216  gistentryinit(*retval, BoxPGetDatum(box),
1217  entry->rel, entry->page, entry->offset, FALSE);
1218 
1219  PG_RETURN_POINTER(retval);
1220  }
1221 
1222  PG_RETURN_POINTER(entry);
1223 }
1224 
1225 /*
1226  * GiST Fetch method for point
1227  *
1228  * Get point coordinates from its bounding box coordinates and form new
1229  * gistentry.
1230  */
1231 Datum
1233 {
1234  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1235  BOX *in = DatumGetBoxP(entry->key);
1236  Point *r;
1237  GISTENTRY *retval;
1238 
1239  retval = palloc(sizeof(GISTENTRY));
1240 
1241  r = (Point *) palloc(sizeof(Point));
1242  r->x = in->high.x;
1243  r->y = in->high.y;
1244  gistentryinit(*retval, PointerGetDatum(r),
1245  entry->rel, entry->page,
1246  entry->offset, FALSE);
1247 
1248  PG_RETURN_POINTER(retval);
1249 }
1250 
1251 
1252 #define point_point_distance(p1,p2) \
1253  DatumGetFloat8(DirectFunctionCall2(point_distance, \
1254  PointPGetDatum(p1), PointPGetDatum(p2)))
1255 
1256 static double
1257 computeDistance(bool isLeaf, BOX *box, Point *point)
1258 {
1259  double result = 0.0;
1260 
1261  if (isLeaf)
1262  {
1263  /* simple point to point distance */
1264  result = point_point_distance(point, &box->low);
1265  }
1266  else if (point->x <= box->high.x && point->x >= box->low.x &&
1267  point->y <= box->high.y && point->y >= box->low.y)
1268  {
1269  /* point inside the box */
1270  result = 0.0;
1271  }
1272  else if (point->x <= box->high.x && point->x >= box->low.x)
1273  {
1274  /* point is over or below box */
1275  Assert(box->low.y <= box->high.y);
1276  if (point->y > box->high.y)
1277  result = point->y - box->high.y;
1278  else if (point->y < box->low.y)
1279  result = box->low.y - point->y;
1280  else
1281  elog(ERROR, "inconsistent point values");
1282  }
1283  else if (point->y <= box->high.y && point->y >= box->low.y)
1284  {
1285  /* point is to left or right of box */
1286  Assert(box->low.x <= box->high.x);
1287  if (point->x > box->high.x)
1288  result = point->x - box->high.x;
1289  else if (point->x < box->low.x)
1290  result = box->low.x - point->x;
1291  else
1292  elog(ERROR, "inconsistent point values");
1293  }
1294  else
1295  {
1296  /* closest point will be a vertex */
1297  Point p;
1298  double subresult;
1299 
1300  result = point_point_distance(point, &box->low);
1301 
1302  subresult = point_point_distance(point, &box->high);
1303  if (result > subresult)
1304  result = subresult;
1305 
1306  p.x = box->low.x;
1307  p.y = box->high.y;
1308  subresult = point_point_distance(point, &p);
1309  if (result > subresult)
1310  result = subresult;
1311 
1312  p.x = box->high.x;
1313  p.y = box->low.y;
1314  subresult = point_point_distance(point, &p);
1315  if (result > subresult)
1316  result = subresult;
1317  }
1318 
1319  return result;
1320 }
1321 
1322 static bool
1324  bool isLeaf, BOX *key, Point *query)
1325 {
1326  bool result = false;
1327 
1328  switch (strategy)
1329  {
1330  case RTLeftStrategyNumber:
1331  result = FPlt(key->low.x, query->x);
1332  break;
1333  case RTRightStrategyNumber:
1334  result = FPgt(key->high.x, query->x);
1335  break;
1336  case RTAboveStrategyNumber:
1337  result = FPgt(key->high.y, query->y);
1338  break;
1339  case RTBelowStrategyNumber:
1340  result = FPlt(key->low.y, query->y);
1341  break;
1342  case RTSameStrategyNumber:
1343  if (isLeaf)
1344  {
1345  /* key.high must equal key.low, so we can disregard it */
1346  result = (FPeq(key->low.x, query->x) &&
1347  FPeq(key->low.y, query->y));
1348  }
1349  else
1350  {
1351  result = (FPle(query->x, key->high.x) &&
1352  FPge(query->x, key->low.x) &&
1353  FPle(query->y, key->high.y) &&
1354  FPge(query->y, key->low.y));
1355  }
1356  break;
1357  default:
1358  elog(ERROR, "unrecognized strategy number: %d", strategy);
1359  result = false; /* keep compiler quiet */
1360  break;
1361  }
1362 
1363  return result;
1364 }
1365 
1366 #define GeoStrategyNumberOffset 20
1367 #define PointStrategyNumberGroup 0
1368 #define BoxStrategyNumberGroup 1
1369 #define PolygonStrategyNumberGroup 2
1370 #define CircleStrategyNumberGroup 3
1371 
1372 Datum
1374 {
1375  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1377  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1378  bool result;
1379  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1380 
1381  switch (strategyGroup)
1382  {
1385  GIST_LEAF(entry),
1386  DatumGetBoxP(entry->key),
1387  PG_GETARG_POINT_P(1));
1388  *recheck = false;
1389  break;
1391  {
1392  /*
1393  * The only operator in this group is point <@ box (on_pb), so
1394  * we needn't examine strategy again.
1395  *
1396  * For historical reasons, on_pb uses exact rather than fuzzy
1397  * comparisons. We could use box_overlap when at an internal
1398  * page, but that would lead to possibly visiting child pages
1399  * uselessly, because box_overlap uses fuzzy comparisons.
1400  * Instead we write a non-fuzzy overlap test. The same code
1401  * will also serve for leaf-page tests, since leaf keys have
1402  * high == low.
1403  */
1404  BOX *query,
1405  *key;
1406 
1407  query = PG_GETARG_BOX_P(1);
1408  key = DatumGetBoxP(entry->key);
1409 
1410  result = (key->high.x >= query->low.x &&
1411  key->low.x <= query->high.x &&
1412  key->high.y >= query->low.y &&
1413  key->low.y <= query->high.y);
1414  *recheck = false;
1415  }
1416  break;
1418  {
1419  POLYGON *query = PG_GETARG_POLYGON_P(1);
1420 
1423  PointerGetDatum(entry),
1424  PolygonPGetDatum(query),
1426  0, PointerGetDatum(recheck)));
1427 
1428  if (GIST_LEAF(entry) && result)
1429  {
1430  /*
1431  * We are on leaf page and quick check shows overlapping
1432  * of polygon's bounding box and point
1433  */
1434  BOX *box = DatumGetBoxP(entry->key);
1435 
1436  Assert(box->high.x == box->low.x
1437  && box->high.y == box->low.y);
1440  PolygonPGetDatum(query),
1441  PointPGetDatum(&box->high)));
1442  *recheck = false;
1443  }
1444  }
1445  break;
1447  {
1448  CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1449 
1452  PointerGetDatum(entry),
1453  CirclePGetDatum(query),
1455  0, PointerGetDatum(recheck)));
1456 
1457  if (GIST_LEAF(entry) && result)
1458  {
1459  /*
1460  * We are on leaf page and quick check shows overlapping
1461  * of polygon's bounding box and point
1462  */
1463  BOX *box = DatumGetBoxP(entry->key);
1464 
1465  Assert(box->high.x == box->low.x
1466  && box->high.y == box->low.y);
1469  CirclePGetDatum(query),
1470  PointPGetDatum(&box->high)));
1471  *recheck = false;
1472  }
1473  }
1474  break;
1475  default:
1476  elog(ERROR, "unrecognized strategy number: %d", strategy);
1477  result = false; /* keep compiler quiet */
1478  break;
1479  }
1480 
1481  PG_RETURN_BOOL(result);
1482 }
1483 
1484 Datum
1486 {
1487  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1489  double distance;
1490  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1491 
1492  switch (strategyGroup)
1493  {
1495  distance = computeDistance(GIST_LEAF(entry),
1496  DatumGetBoxP(entry->key),
1497  PG_GETARG_POINT_P(1));
1498  break;
1499  default:
1500  elog(ERROR, "unrecognized strategy number: %d", strategy);
1501  distance = 0.0; /* keep compiler quiet */
1502  break;
1503  }
1504 
1505  PG_RETURN_FLOAT8(distance);
1506 }
1507 
1508 /*
1509  * The inexact GiST distance method for geometric types that store bounding
1510  * boxes.
1511  *
1512  * Compute lossy distance from point to index entries. The result is inexact
1513  * because index entries are bounding boxes, not the exact shapes of the
1514  * indexed geometric types. We use distance from point to MBR of index entry.
1515  * This is a lower bound estimate of distance from point to indexed geometric
1516  * type.
1517  */
1518 static double
1520  StrategyNumber strategy, bool *recheck)
1521 {
1522  double distance;
1523  StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1524 
1525  /* Bounding box distance is always inexact. */
1526  *recheck = true;
1527 
1528  switch (strategyGroup)
1529  {
1531  distance = computeDistance(false,
1532  DatumGetBoxP(entry->key),
1533  DatumGetPointP(query));
1534  break;
1535  default:
1536  elog(ERROR, "unrecognized strategy number: %d", strategy);
1537  distance = 0.0; /* keep compiler quiet */
1538  }
1539 
1540  return distance;
1541 }
1542 
1543 Datum
1545 {
1546  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1547  Datum query = PG_GETARG_DATUM(1);
1549 
1550  /* Oid subtype = PG_GETARG_OID(3); */
1551  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1552  double distance;
1553 
1554  distance = gist_bbox_distance(entry, query, strategy, recheck);
1555 
1556  PG_RETURN_FLOAT8(distance);
1557 }
1558 
1559 Datum
1561 {
1562  GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1563  Datum query = PG_GETARG_DATUM(1);
1565 
1566  /* Oid subtype = PG_GETARG_OID(3); */
1567  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1568  double distance;
1569 
1570  distance = gist_bbox_distance(entry, query, strategy, recheck);
1571 
1572  PG_RETURN_FLOAT8(distance);
1573 }
#define GIST_LEAF(entry)
Definition: gist.h:133
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:564
Relation rel
Definition: gist.h:124
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:636
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:991
#define GeoStrategyNumberOffset
Definition: gistproc.c:1366
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:504
Definition: geo_decls.h:102
#define PLACE_LEFT(box, off)
#define BoxStrategyNumberGroup
Definition: gistproc.c:1368
static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:904
Datum gist_box_decompress(PG_FUNCTION_ARGS)
Definition: gistproc.c:205
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:161
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:538
Datum gist_box_fetch(PG_FUNCTION_ARGS)
Definition: gistproc.c:215
#define RTOldContainsStrategyNumber
Definition: stratnum.h:56
#define RTOldContainedByStrategyNumber
Definition: stratnum.h:57
#define RTLeftStrategyNumber
Definition: stratnum.h:44
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
static int interval_cmp_lower(const void *i1, const void *i2)
Definition: gistproc.c:342
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:579
#define CircleStrategyNumberGroup
Definition: gistproc.c:1370
#define PointerGetDatum(X)
Definition: postgres.h:562
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:233
static int interval_cmp_upper(const void *i1, const void *i2)
Definition: gistproc.c:354
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:326
#define Min(x, y)
Definition: c.h:806
double radius
Definition: geo_decls.h:127
#define PolygonPGetDatum(X)
Definition: geo_decls.h:166
#define FLOAT8_MAX(a, b)
Definition: gistproc.c:43
Datum gist_point_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1373
double y
Definition: geo_decls.h:60
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:518
OffsetNumber * spl_left
Definition: gist.h:105
Datum spl_rdatum
Definition: gist.h:112
#define Int16GetDatum(X)
Definition: postgres.h:457
#define RTOverBelowStrategyNumber
Definition: stratnum.h:52
static int common_entry_cmp(const void *i1, const void *i2)
Definition: gistproc.c:487
int32 n
Definition: gist.h:160
Datum gist_box_same(PG_FUNCTION_ARGS)
Definition: gistproc.c:884
Datum gist_box_picksplit(PG_FUNCTION_ARGS)
Definition: gistproc.c:527
struct cursor * cur
Definition: ecpg.c:28
uint16 StrategyNumber
Definition: stratnum.h:22
return result
Definition: formatting.c:1618
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
Datum poly_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3984
Datum gist_point_fetch(PG_FUNCTION_ARGS)
Definition: gistproc.c:1232
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
int spl_nleft
Definition: gist.h:106
#define PLACE_RIGHT(box, off)
#define RTBelowStrategyNumber
Definition: stratnum.h:53
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:167
Datum gist_box_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:112
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:1052
#define PointStrategyNumberGroup
Definition: gistproc.c:1367
Datum gist_poly_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1071
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:125
double delta
Definition: gistproc.c:303
#define Abs(x)
Definition: c.h:812
double x
Definition: geo_decls.h:60
Definition: type.h:90
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:161
#define RTOverAboveStrategyNumber
Definition: stratnum.h:55
#define CirclePGetDatum(X)
Definition: geo_decls.h:172
#define FPgt(A, B)
Definition: geo_decls.h:41
Datum gist_point_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1485
#define point_point_distance(p1, p2)
Definition: gistproc.c:1252
#define FLOAT8_GE(a, b)
Definition: gistproc.c:42
#define ERROR
Definition: elog.h:43
#define FALSE
Definition: c.h:221
int spl_nright
Definition: gist.h:111
#define PG_GETARG_POINT_P(n)
Definition: geo_decls.h:139
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, double rightLower, int minLeftCount, double leftUpper, int maxLeftCount)
Definition: gistproc.c:378
#define FLOAT8_LE(a, b)
Definition: gistproc.c:40
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:650
Datum key
Definition: gist.h:123
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:613
#define DatumGetCircleP(X)
Definition: geo_decls.h:171
static double size_box(const BOX *box)
Definition: gistproc.c:68
#define FirstOffsetNumber
Definition: off.h:27
static void rt_box_union(BOX *n, const BOX *a, const BOX *b)
Definition: gistproc.c:55
#define DatumGetBool(X)
Definition: postgres.h:399
#define RTSameStrategyNumber
Definition: stratnum.h:49
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
Definition: gistproc.c:243
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
#define RTOverRightStrategyNumber
Definition: stratnum.h:47
static double gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy, bool *recheck)
Definition: gistproc.c:1519
static bool gist_point_consistent_internal(StrategyNumber strategy, bool isLeaf, BOX *key, Point *query)
Definition: gistproc.c:1323
double lower
Definition: gistproc.c:334
#define FLOAT8_EQ(a, b)
Definition: gistproc.c:38
bool leafkey
Definition: gist.h:127
#define DirectFunctionCall5(func, arg1, arg2, arg3, arg4, arg5)
Definition: fmgr.h:592
double get_float8_infinity(void)
Definition: float.c:121
#define FPeq(A, B)
Definition: geo_decls.h:37
static void adjustBox(BOX *b, const BOX *addon)
Definition: gistproc.c:145
Point low
Definition: geo_decls.h:104
float float4
Definition: c.h:380
#define RTOverLeftStrategyNumber
Definition: stratnum.h:45
void * palloc0(Size size)
Definition: mcxt.c:878
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:319
uintptr_t Datum
Definition: postgres.h:372
Datum circle_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5013
Datum gist_circle_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1166
Datum gist_box_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:193
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:602
#define PolygonStrategyNumberGroup
Definition: gistproc.c:1369
#define LIMIT_RATIO
Definition: gistproc.c:35
#define PG_GETARG_CIRCLE_P(n)
Definition: geo_decls.h:173
#define BoxPGetDatum(X)
Definition: geo_decls.h:160
Datum gist_box_penalty(PG_FUNCTION_ARGS)
Definition: gistproc.c:226
BOX boundbox
Definition: geo_decls.h:117
Datum gist_circle_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1136
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:590
#define RTAboveStrategyNumber
Definition: stratnum.h:54
static double computeDistance(bool isLeaf, BOX *box, Point *point)
Definition: gistproc.c:1257
#define FPlt(A, B)
Definition: geo_decls.h:39
Datum spl_ldatum
Definition: gist.h:107
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:169
#define FLOAT8_MIN(a, b)
Definition: gistproc.c:44
#define RTRightStrategyNumber
Definition: stratnum.h:48
#define DatumGetPointP(X)
Definition: geo_decls.h:137
static float non_negative(float val)
Definition: gistproc.c:366
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:553
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
OffsetNumber * spl_right
Definition: gist.h:110
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:225
#define RTContainsStrategyNumber
Definition: stratnum.h:50
Datum gist_poly_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1098
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
Datum gist_point_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1204
Point high
Definition: geo_decls.h:104
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:237
#define DatumGetPolygonP(X)
Definition: geo_decls.h:164
Point center
Definition: geo_decls.h:126
Datum gist_circle_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1544
static double box_penalty(const BOX *original, const BOX *new)
Definition: gistproc.c:96
void * palloc(Size size)
Definition: mcxt.c:849
Datum gist_box_union(PG_FUNCTION_ARGS)
Definition: gistproc.c:163
#define FPge(A, B)
Definition: geo_decls.h:42
int i
#define FLOAT8_GT(a, b)
Definition: gistproc.c:41
#define RTOverlapStrategyNumber
Definition: stratnum.h:46
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:625
#define elog
Definition: elog.h:219
#define FPle(A, B)
Definition: geo_decls.h:40
#define qsort(a, b, c, d)
Definition: port.h:440
#define FLOAT8_LT(a, b)
Definition: gistproc.c:39
double upper
Definition: gistproc.c:334
OffsetNumber offset
Definition: gist.h:126
Datum gist_poly_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1560
long val
Definition: informix.c:689
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:586
#define PointPGetDatum(X)
Definition: geo_decls.h:138