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