1
/*-------------------------------------------------------------------------
4
* Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
7
* This gives R-tree behavior, with Guttman's poly-time split algorithm.
10
* Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
11
* Portions Copyright (c) 1994, Regents of the University of California
14
* src/backend/access/gist/gistproc.c
16
*-------------------------------------------------------------------------
23
#include "access/gist.h"
24
#include "access/stratnum.h"
25
#include "utils/builtins.h"
26
#include "utils/geo_decls.h"
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);
34
/* Minimum accepted ratio of split */
35
#define LIMIT_RATIO 0.3
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))
47
/**************************************************
49
**************************************************/
52
* Calculates union of two boxes, a and b. The result is stored in *n.
55
rt_box_union(BOX *n, const BOX *a, const BOX *b)
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);
64
* Size of a BOX for penalty-calculation purposes.
65
* The result can be +Infinity, but not NaN.
68
size_box(const BOX *box)
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.
75
* The less-than cases should not happen, but if they do, say "zero".
77
if (FLOAT8_LE(box->high.x, box->low.x) ||
78
FLOAT8_LE(box->high.y, box->low.y))
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.
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);
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.
96
box_penalty(const BOX *original, const BOX *new)
100
rt_box_union(&unionbox, original, new);
101
return size_box(&unionbox) - size_box(original);
105
* The GiST Consistent method for boxes
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.
112
gist_box_consistent(PG_FUNCTION_ARGS)
114
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
115
BOX *query = PG_GETARG_BOX_P(1);
116
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
118
/* Oid subtype = PG_GETARG_OID(3); */
119
bool *recheck = (bool *) PG_GETARG_POINTER(4);
121
/* All cases served by this function are exact */
124
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
125
PG_RETURN_BOOL(false);
128
* if entry is not leaf, use rtree_internal_consistent, else use
129
* gist_box_leaf_consistent
131
if (GIST_LEAF(entry))
132
PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
136
PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
142
* Increase BOX b to include addon.
145
adjustBox(BOX *b, const BOX *addon)
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;
158
* The GiST Union method for boxes
160
* returns the minimal bounding box that encloses all the entries in entryvec
163
gist_box_union(PG_FUNCTION_ARGS)
165
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
166
int *sizep = (int *) PG_GETARG_POINTER(1);
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));
177
for (i = 1; i < numranges; i++)
179
cur = DatumGetBoxP(entryvec->vector[i].key);
180
adjustBox(pageunion, cur);
182
*sizep = sizeof(BOX);
184
PG_RETURN_POINTER(pageunion);
188
* We store boxes as boxes in GiST indexes, so we do not need
189
* compress, decompress, or fetch functions.
193
* The GiST Penalty method for boxes (also used for points)
195
* As in the R-tree paper, we use change in area as our penalty metric
198
gist_box_penalty(PG_FUNCTION_ARGS)
200
GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
201
GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
202
float *result = (float *) PG_GETARG_POINTER(2);
203
BOX *origbox = DatumGetBoxP(origentry->key);
204
BOX *newbox = DatumGetBoxP(newentry->key);
206
*result = (float) box_penalty(origbox, newbox);
207
PG_RETURN_POINTER(result);
211
* Trivial split: half of entries will be placed on one page
212
* and another half - to another
215
fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
223
maxoff = entryvec->n - 1;
225
nbytes = (maxoff + 2) * sizeof(OffsetNumber);
226
v->spl_left = (OffsetNumber *) palloc(nbytes);
227
v->spl_right = (OffsetNumber *) palloc(nbytes);
228
v->spl_nleft = v->spl_nright = 0;
230
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
232
BOX *cur = DatumGetBoxP(entryvec->vector[i].key);
234
if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
236
v->spl_left[v->spl_nleft] = i;
239
unionL = (BOX *) palloc(sizeof(BOX));
243
adjustBox(unionL, cur);
249
v->spl_right[v->spl_nright] = i;
252
unionR = (BOX *) palloc(sizeof(BOX));
256
adjustBox(unionR, cur);
262
v->spl_ldatum = BoxPGetDatum(unionL);
263
v->spl_rdatum = BoxPGetDatum(unionR);
267
* Represents information about an entry that can be placed to either group
268
* without affecting overlap over selected axis ("common entry").
272
/* Index of entry in the initial array */
274
/* Delta between penalties of entry insertion into different groups */
279
* Context for g_box_consider_split. Contains information about currently
280
* selected split and some general information.
284
int entriesCount; /* total number of entries being split */
285
BOX boundingBox; /* minimum bounding box across all entries */
287
/* Information about currently selected split follows */
289
bool first; /* true if no split was selected yet */
291
double leftUpper; /* upper bound of left interval */
292
double rightLower; /* lower bound of right interval */
296
int dim; /* axis of this split */
297
double range; /* width of general MBR projection to the
299
} ConsiderSplitContext;
302
* Interval represents projection of box to axis.
311
* Interval comparison function by lower bound of the interval;
314
interval_cmp_lower(const void *i1, const void *i2)
316
double lower1 = ((const SplitInterval *) i1)->lower,
317
lower2 = ((const SplitInterval *) i2)->lower;
319
return float8_cmp_internal(lower1, lower2);
323
* Interval comparison function by upper bound of the interval;
326
interval_cmp_upper(const void *i1, const void *i2)
328
double upper1 = ((const SplitInterval *) i1)->upper,
329
upper2 = ((const SplitInterval *) i2)->upper;
331
return float8_cmp_internal(upper1, upper2);
335
* Replace negative (or NaN) value with zero.
338
non_negative(float val)
347
* Consider replacement of currently selected split with the better one.
350
g_box_consider_split(ConsiderSplitContext *context, int dimNum,
351
double rightLower, int minLeftCount,
352
double leftUpper, int maxLeftCount)
361
* Calculate entries distribution ratio assuming most uniform distribution
364
if (minLeftCount >= (context->entriesCount + 1) / 2)
366
leftCount = minLeftCount;
370
if (maxLeftCount <= context->entriesCount / 2)
371
leftCount = maxLeftCount;
373
leftCount = context->entriesCount / 2;
375
rightCount = context->entriesCount - leftCount;
378
* Ratio of split - quotient between size of lesser group and total
381
ratio = ((float4) Min(leftCount, rightCount)) /
382
((float4) context->entriesCount);
384
if (ratio > LIMIT_RATIO)
386
bool selectthis = false;
389
* The ratio is acceptable, so compare current split with previously
390
* selected one. Between splits of one dimension we search for minimal
391
* overlap (allowing negative values) and minimal ration (between same
392
* overlaps. We switch dimension if find less overlap (non-negative)
393
* or less range with same overlap.
396
range = context->boundingBox.high.x - context->boundingBox.low.x;
398
range = context->boundingBox.high.y - context->boundingBox.low.y;
400
overlap = (leftUpper - rightLower) / range;
402
/* If there is no previous selection, select this */
405
else if (context->dim == dimNum)
408
* Within the same dimension, choose the new split if it has a
409
* smaller overlap, or same overlap but better ratio.
411
if (overlap < context->overlap ||
412
(overlap == context->overlap && ratio > context->ratio))
418
* Across dimensions, choose the new split if it has a smaller
419
* *non-negative* overlap, or same *non-negative* overlap but
420
* bigger range. This condition differs from the one described in
421
* the article. On the datasets where leaf MBRs don't overlap
422
* themselves, non-overlapping splits (i.e. splits which have zero
423
* *non-negative* overlap) are frequently possible. In this case
424
* splits tends to be along one dimension, because most distant
425
* non-overlapping splits (i.e. having lowest negative overlap)
426
* appears to be in the same dimension as in the previous split.
427
* Therefore MBRs appear to be very prolonged along another
428
* dimension, which leads to bad search performance. Using range
429
* as the second split criteria makes MBRs more quadratic. Using
430
* *non-negative* overlap instead of overlap as the first split
431
* criteria gives to range criteria a chance to matter, because
432
* non-overlapping splits are equivalent in this criteria.
434
if (non_negative(overlap) < non_negative(context->overlap) ||
435
(range > context->range &&
436
non_negative(overlap) <= non_negative(context->overlap)))
442
/* save information about selected split */
443
context->first = false;
444
context->ratio = ratio;
445
context->range = range;
446
context->overlap = overlap;
447
context->rightLower = rightLower;
448
context->leftUpper = leftUpper;
449
context->dim = dimNum;
455
* Compare common entries by their deltas.
456
* (We assume the deltas can't be NaN.)
459
common_entry_cmp(const void *i1, const void *i2)
461
double delta1 = ((const CommonEntry *) i1)->delta,
462
delta2 = ((const CommonEntry *) i2)->delta;
466
else if (delta1 > delta2)
473
* --------------------------------------------------------------------------
474
* Double sorting split algorithm. This is used for both boxes and points.
476
* The algorithm finds split of boxes by considering splits along each axis.
477
* Each entry is first projected as an interval on the X-axis, and different
478
* ways to split the intervals into two groups are considered, trying to
479
* minimize the overlap of the groups. Then the same is repeated for the
480
* Y-axis, and the overall best split is chosen. The quality of a split is
481
* determined by overlap along that axis and some other criteria (see
482
* g_box_consider_split).
484
* After that, all the entries are divided into three groups:
486
* 1) Entries which should be placed to the left group
487
* 2) Entries which should be placed to the right group
488
* 3) "Common entries" which can be placed to any of groups without affecting
489
* of overlap along selected axis.
491
* The common entries are distributed by minimizing penalty.
494
* "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
495
* http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
496
* --------------------------------------------------------------------------
499
gist_box_picksplit(PG_FUNCTION_ARGS)
501
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
502
GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
505
ConsiderSplitContext context;
511
SplitInterval *intervalsLower,
513
CommonEntry *commonEntries;
516
memset(&context, 0, sizeof(ConsiderSplitContext));
518
maxoff = entryvec->n - 1;
519
nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
521
/* Allocate arrays for intervals along axes */
522
intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
523
intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
526
* Calculate the overall minimum bounding box over all the entries.
528
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
530
box = DatumGetBoxP(entryvec->vector[i].key);
531
if (i == FirstOffsetNumber)
532
context.boundingBox = *box;
534
adjustBox(&context.boundingBox, box);
538
* Iterate over axes for optimal split searching.
540
context.first = true; /* nothing selected yet */
541
for (dim = 0; dim < 2; dim++)
548
/* Project each entry as an interval on the selected axis. */
549
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
551
box = DatumGetBoxP(entryvec->vector[i].key);
554
intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
555
intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
559
intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
560
intervalsLower[i - FirstOffsetNumber].upper = box->high.y;
565
* Make two arrays of intervals: one sorted by lower bound and another
566
* sorted by upper bound.
568
memcpy(intervalsUpper, intervalsLower,
569
sizeof(SplitInterval) * nentries);
570
qsort(intervalsLower, nentries, sizeof(SplitInterval),
572
qsort(intervalsUpper, nentries, sizeof(SplitInterval),
576
* The goal is to form a left and right interval, so that every entry
577
* interval is contained by either left or right interval (or both).
579
* For example, with the intervals (0,1), (1,3), (2,3), (2,4):
587
* The left and right intervals are of the form (0,a) and (b,4).
588
* We first consider splits where b is the lower bound of an entry.
589
* We iterate through all entries, and for each b, calculate the
590
* smallest possible a. Then we consider splits where a is the
591
* upper bound of an entry, and for each a, calculate the greatest
594
* In the above example, the first loop would consider splits:
599
* And the second loop:
606
* Iterate over lower bound of right group, finding smallest possible
607
* upper bound of left group.
611
rightLower = intervalsLower[i1].lower;
612
leftUpper = intervalsUpper[i2].lower;
616
* Find next lower bound of right group.
618
while (i1 < nentries &&
619
FLOAT8_EQ(rightLower, intervalsLower[i1].lower))
621
if (FLOAT8_LT(leftUpper, intervalsLower[i1].upper))
622
leftUpper = intervalsLower[i1].upper;
627
rightLower = intervalsLower[i1].lower;
630
* Find count of intervals which anyway should be placed to the
633
while (i2 < nentries &&
634
FLOAT8_LE(intervalsUpper[i2].upper, leftUpper))
638
* Consider found split.
640
g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
644
* Iterate over upper bound of left group finding greatest possible
645
* lower bound of right group.
649
rightLower = intervalsLower[i1].upper;
650
leftUpper = intervalsUpper[i2].upper;
654
* Find next upper bound of left group.
656
while (i2 >= 0 && FLOAT8_EQ(leftUpper, intervalsUpper[i2].upper))
658
if (FLOAT8_GT(rightLower, intervalsUpper[i2].lower))
659
rightLower = intervalsUpper[i2].lower;
664
leftUpper = intervalsUpper[i2].upper;
667
* Find count of intervals which anyway should be placed to the
670
while (i1 >= 0 && FLOAT8_GE(intervalsLower[i1].lower, rightLower))
674
* Consider found split.
676
g_box_consider_split(&context, dim,
677
rightLower, i1 + 1, leftUpper, i2 + 1);
682
* If we failed to find any acceptable splits, use trivial split.
686
fallbackSplit(entryvec, v);
687
PG_RETURN_POINTER(v);
691
* Ok, we have now selected the split across one axis.
693
* While considering the splits, we already determined that there will be
694
* enough entries in both groups to reach the desired ratio, but we did
695
* not memorize which entries go to which group. So determine that now.
698
/* Allocate vectors for results */
699
v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
700
v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
704
/* Allocate bounding boxes of left and right groups */
705
leftBox = palloc0(sizeof(BOX));
706
rightBox = palloc0(sizeof(BOX));
709
* Allocate an array for "common entries" - entries which can be placed to
710
* either group without affecting overlap along selected axis.
712
commonEntriesCount = 0;
713
commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
715
/* Helper macros to place an entry in the left or right group */
716
#define PLACE_LEFT(box, off) \
718
if (v->spl_nleft > 0) \
719
adjustBox(leftBox, box); \
722
v->spl_left[v->spl_nleft++] = off; \
725
#define PLACE_RIGHT(box, off) \
727
if (v->spl_nright > 0) \
728
adjustBox(rightBox, box); \
730
*rightBox = *(box); \
731
v->spl_right[v->spl_nright++] = off; \
735
* Distribute entries which can be distributed unambiguously, and collect
738
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
744
* Get upper and lower bounds along selected axis.
746
box = DatumGetBoxP(entryvec->vector[i].key);
747
if (context.dim == 0)
758
if (FLOAT8_LE(upper, context.leftUpper))
760
/* Fits to the left group */
761
if (FLOAT8_GE(lower, context.rightLower))
763
/* Fits also to the right group, so "common entry" */
764
commonEntries[commonEntriesCount++].index = i;
768
/* Doesn't fit to the right group, so join to the left group */
775
* Each entry should fit on either left or right group. Since this
776
* entry didn't fit on the left group, it better fit in the right
779
Assert(FLOAT8_GE(lower, context.rightLower));
781
/* Doesn't fit to the left group, so join to the right group */
787
* Distribute "common entries", if any.
789
if (commonEntriesCount > 0)
792
* Calculate minimum number of entries that must be placed in both
793
* groups, to reach LIMIT_RATIO.
795
int m = ceil(LIMIT_RATIO * (double) nentries);
798
* Calculate delta between penalties of join "common entries" to
801
for (i = 0; i < commonEntriesCount; i++)
803
box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
804
commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
805
box_penalty(rightBox, box));
809
* Sort "common entries" by calculated deltas in order to distribute
810
* the most ambiguous entries first.
812
qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
815
* Distribute "common entries" between groups.
817
for (i = 0; i < commonEntriesCount; i++)
819
box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
822
* Check if we have to place this entry in either group to achieve
825
if (v->spl_nleft + (commonEntriesCount - i) <= m)
826
PLACE_LEFT(box, commonEntries[i].index);
827
else if (v->spl_nright + (commonEntriesCount - i) <= m)
828
PLACE_RIGHT(box, commonEntries[i].index);
831
/* Otherwise select the group by minimal penalty */
832
if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
833
PLACE_LEFT(box, commonEntries[i].index);
835
PLACE_RIGHT(box, commonEntries[i].index);
840
v->spl_ldatum = PointerGetDatum(leftBox);
841
v->spl_rdatum = PointerGetDatum(rightBox);
842
PG_RETURN_POINTER(v);
848
* This is used for boxes, points, circles, and polygons, all of which store
849
* boxes as GiST index entries.
851
* Returns true only when boxes are exactly the same. We can't use fuzzy
852
* comparisons here without breaking index consistency; therefore, this isn't
853
* equivalent to box_same().
856
gist_box_same(PG_FUNCTION_ARGS)
858
BOX *b1 = PG_GETARG_BOX_P(0);
859
BOX *b2 = PG_GETARG_BOX_P(1);
860
bool *result = (bool *) PG_GETARG_POINTER(2);
863
*result = (FLOAT8_EQ(b1->low.x, b2->low.x) &&
864
FLOAT8_EQ(b1->low.y, b2->low.y) &&
865
FLOAT8_EQ(b1->high.x, b2->high.x) &&
866
FLOAT8_EQ(b1->high.y, b2->high.y));
868
*result = (b1 == NULL && b2 == NULL);
869
PG_RETURN_POINTER(result);
873
* Leaf-level consistency for boxes: just apply the query operator
876
gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
882
case RTLeftStrategyNumber:
883
retval = DatumGetBool(DirectFunctionCall2(box_left,
884
PointerGetDatum(key),
885
PointerGetDatum(query)));
887
case RTOverLeftStrategyNumber:
888
retval = DatumGetBool(DirectFunctionCall2(box_overleft,
889
PointerGetDatum(key),
890
PointerGetDatum(query)));
892
case RTOverlapStrategyNumber:
893
retval = DatumGetBool(DirectFunctionCall2(box_overlap,
894
PointerGetDatum(key),
895
PointerGetDatum(query)));
897
case RTOverRightStrategyNumber:
898
retval = DatumGetBool(DirectFunctionCall2(box_overright,
899
PointerGetDatum(key),
900
PointerGetDatum(query)));
902
case RTRightStrategyNumber:
903
retval = DatumGetBool(DirectFunctionCall2(box_right,
904
PointerGetDatum(key),
905
PointerGetDatum(query)));
907
case RTSameStrategyNumber:
908
retval = DatumGetBool(DirectFunctionCall2(box_same,
909
PointerGetDatum(key),
910
PointerGetDatum(query)));
912
case RTContainsStrategyNumber:
913
case RTOldContainsStrategyNumber:
914
retval = DatumGetBool(DirectFunctionCall2(box_contain,
915
PointerGetDatum(key),
916
PointerGetDatum(query)));
918
case RTContainedByStrategyNumber:
919
case RTOldContainedByStrategyNumber:
920
retval = DatumGetBool(DirectFunctionCall2(box_contained,
921
PointerGetDatum(key),
922
PointerGetDatum(query)));
924
case RTOverBelowStrategyNumber:
925
retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
926
PointerGetDatum(key),
927
PointerGetDatum(query)));
929
case RTBelowStrategyNumber:
930
retval = DatumGetBool(DirectFunctionCall2(box_below,
931
PointerGetDatum(key),
932
PointerGetDatum(query)));
934
case RTAboveStrategyNumber:
935
retval = DatumGetBool(DirectFunctionCall2(box_above,
936
PointerGetDatum(key),
937
PointerGetDatum(query)));
939
case RTOverAboveStrategyNumber:
940
retval = DatumGetBool(DirectFunctionCall2(box_overabove,
941
PointerGetDatum(key),
942
PointerGetDatum(query)));
945
elog(ERROR, "unrecognized strategy number: %d", strategy);
946
retval = false; /* keep compiler quiet */
952
/*****************************************
953
* Common rtree functions (for boxes, polygons, and circles)
954
*****************************************/
957
* Internal-page consistency for all these types
959
* We can use the same function since all types use bounding boxes as the
960
* internal-page representation.
963
rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
969
case RTLeftStrategyNumber:
970
retval = !DatumGetBool(DirectFunctionCall2(box_overright,
971
PointerGetDatum(key),
972
PointerGetDatum(query)));
974
case RTOverLeftStrategyNumber:
975
retval = !DatumGetBool(DirectFunctionCall2(box_right,
976
PointerGetDatum(key),
977
PointerGetDatum(query)));
979
case RTOverlapStrategyNumber:
980
retval = DatumGetBool(DirectFunctionCall2(box_overlap,
981
PointerGetDatum(key),
982
PointerGetDatum(query)));
984
case RTOverRightStrategyNumber:
985
retval = !DatumGetBool(DirectFunctionCall2(box_left,
986
PointerGetDatum(key),
987
PointerGetDatum(query)));
989
case RTRightStrategyNumber:
990
retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
991
PointerGetDatum(key),
992
PointerGetDatum(query)));
994
case RTSameStrategyNumber:
995
case RTContainsStrategyNumber:
996
case RTOldContainsStrategyNumber:
997
retval = DatumGetBool(DirectFunctionCall2(box_contain,
998
PointerGetDatum(key),
999
PointerGetDatum(query)));
1001
case RTContainedByStrategyNumber:
1002
case RTOldContainedByStrategyNumber:
1003
retval = DatumGetBool(DirectFunctionCall2(box_overlap,
1004
PointerGetDatum(key),
1005
PointerGetDatum(query)));
1007
case RTOverBelowStrategyNumber:
1008
retval = !DatumGetBool(DirectFunctionCall2(box_above,
1009
PointerGetDatum(key),
1010
PointerGetDatum(query)));
1012
case RTBelowStrategyNumber:
1013
retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
1014
PointerGetDatum(key),
1015
PointerGetDatum(query)));
1017
case RTAboveStrategyNumber:
1018
retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
1019
PointerGetDatum(key),
1020
PointerGetDatum(query)));
1022
case RTOverAboveStrategyNumber:
1023
retval = !DatumGetBool(DirectFunctionCall2(box_below,
1024
PointerGetDatum(key),
1025
PointerGetDatum(query)));
1028
elog(ERROR, "unrecognized strategy number: %d", strategy);
1029
retval = false; /* keep compiler quiet */
1035
/**************************************************
1037
**************************************************/
1040
* GiST compress for polygons: represent a polygon by its bounding box
1043
gist_poly_compress(PG_FUNCTION_ARGS)
1045
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1050
POLYGON *in = DatumGetPolygonP(entry->key);
1053
r = (BOX *) palloc(sizeof(BOX));
1054
memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
1056
retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1057
gistentryinit(*retval, PointerGetDatum(r),
1058
entry->rel, entry->page,
1059
entry->offset, false);
1063
PG_RETURN_POINTER(retval);
1067
* The GiST Consistent method for polygons
1070
gist_poly_consistent(PG_FUNCTION_ARGS)
1072
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1073
POLYGON *query = PG_GETARG_POLYGON_P(1);
1074
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1076
/* Oid subtype = PG_GETARG_OID(3); */
1077
bool *recheck = (bool *) PG_GETARG_POINTER(4);
1080
/* All cases served by this function are inexact */
1083
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1084
PG_RETURN_BOOL(false);
1087
* Since the operators require recheck anyway, we can just use
1088
* rtree_internal_consistent even at leaf nodes. (This works in part
1089
* because the index entries are bounding boxes not polygons.)
1091
result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1092
&(query->boundbox), strategy);
1094
/* Avoid memory leak if supplied poly is toasted */
1095
PG_FREE_IF_COPY(query, 1);
1097
PG_RETURN_BOOL(result);
1100
/**************************************************
1102
**************************************************/
1105
* GiST compress for circles: represent a circle by its bounding box
1108
gist_circle_compress(PG_FUNCTION_ARGS)
1110
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1115
CIRCLE *in = DatumGetCircleP(entry->key);
1118
r = (BOX *) palloc(sizeof(BOX));
1119
r->high.x = in->center.x + in->radius;
1120
r->low.x = in->center.x - in->radius;
1121
r->high.y = in->center.y + in->radius;
1122
r->low.y = in->center.y - in->radius;
1124
retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1125
gistentryinit(*retval, PointerGetDatum(r),
1126
entry->rel, entry->page,
1127
entry->offset, false);
1131
PG_RETURN_POINTER(retval);
1135
* The GiST Consistent method for circles
1138
gist_circle_consistent(PG_FUNCTION_ARGS)
1140
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1141
CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1142
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1144
/* Oid subtype = PG_GETARG_OID(3); */
1145
bool *recheck = (bool *) PG_GETARG_POINTER(4);
1149
/* All cases served by this function are inexact */
1152
if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1153
PG_RETURN_BOOL(false);
1156
* Since the operators require recheck anyway, we can just use
1157
* rtree_internal_consistent even at leaf nodes. (This works in part
1158
* because the index entries are bounding boxes not circles.)
1160
bbox.high.x = query->center.x + query->radius;
1161
bbox.low.x = query->center.x - query->radius;
1162
bbox.high.y = query->center.y + query->radius;
1163
bbox.low.y = query->center.y - query->radius;
1165
result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1168
PG_RETURN_BOOL(result);
1171
/**************************************************
1173
**************************************************/
1176
gist_point_compress(PG_FUNCTION_ARGS)
1178
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1180
if (entry->leafkey) /* Point, actually */
1182
BOX *box = palloc(sizeof(BOX));
1183
Point *point = DatumGetPointP(entry->key);
1184
GISTENTRY *retval = palloc(sizeof(GISTENTRY));
1186
box->high = box->low = *point;
1188
gistentryinit(*retval, BoxPGetDatum(box),
1189
entry->rel, entry->page, entry->offset, false);
1191
PG_RETURN_POINTER(retval);
1194
PG_RETURN_POINTER(entry);
1198
* GiST Fetch method for point
1200
* Get point coordinates from its bounding box coordinates and form new
1204
gist_point_fetch(PG_FUNCTION_ARGS)
1206
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1207
BOX *in = DatumGetBoxP(entry->key);
1211
retval = palloc(sizeof(GISTENTRY));
1213
r = (Point *) palloc(sizeof(Point));
1216
gistentryinit(*retval, PointerGetDatum(r),
1217
entry->rel, entry->page,
1218
entry->offset, false);
1220
PG_RETURN_POINTER(retval);
1224
#define point_point_distance(p1,p2) \
1225
DatumGetFloat8(DirectFunctionCall2(point_distance, \
1226
PointPGetDatum(p1), PointPGetDatum(p2)))
1229
computeDistance(bool isLeaf, BOX *box, Point *point)
1231
double result = 0.0;
1235
/* simple point to point distance */
1236
result = point_point_distance(point, &box->low);
1238
else if (point->x <= box->high.x && point->x >= box->low.x &&
1239
point->y <= box->high.y && point->y >= box->low.y)
1241
/* point inside the box */
1244
else if (point->x <= box->high.x && point->x >= box->low.x)
1246
/* point is over or below box */
1247
Assert(box->low.y <= box->high.y);
1248
if (point->y > box->high.y)
1249
result = point->y - box->high.y;
1250
else if (point->y < box->low.y)
1251
result = box->low.y - point->y;
1253
elog(ERROR, "inconsistent point values");
1255
else if (point->y <= box->high.y && point->y >= box->low.y)
1257
/* point is to left or right of box */
1258
Assert(box->low.x <= box->high.x);
1259
if (point->x > box->high.x)
1260
result = point->x - box->high.x;
1261
else if (point->x < box->low.x)
1262
result = box->low.x - point->x;
1264
elog(ERROR, "inconsistent point values");
1268
/* closest point will be a vertex */
1272
result = point_point_distance(point, &box->low);
1274
subresult = point_point_distance(point, &box->high);
1275
if (result > subresult)
1280
subresult = point_point_distance(point, &p);
1281
if (result > subresult)
1286
subresult = point_point_distance(point, &p);
1287
if (result > subresult)
1295
gist_point_consistent_internal(StrategyNumber strategy,
1296
bool isLeaf, BOX *key, Point *query)
1298
bool result = false;
1302
case RTLeftStrategyNumber:
1303
result = FPlt(key->low.x, query->x);
1305
case RTRightStrategyNumber:
1306
result = FPgt(key->high.x, query->x);
1308
case RTAboveStrategyNumber:
1309
result = FPgt(key->high.y, query->y);
1311
case RTBelowStrategyNumber:
1312
result = FPlt(key->low.y, query->y);
1314
case RTSameStrategyNumber:
1317
/* key.high must equal key.low, so we can disregard it */
1318
result = (FPeq(key->low.x, query->x) &&
1319
FPeq(key->low.y, query->y));
1323
result = (FPle(query->x, key->high.x) &&
1324
FPge(query->x, key->low.x) &&
1325
FPle(query->y, key->high.y) &&
1326
FPge(query->y, key->low.y));
1330
elog(ERROR, "unrecognized strategy number: %d", strategy);
1331
result = false; /* keep compiler quiet */
1338
#define GeoStrategyNumberOffset 20
1339
#define PointStrategyNumberGroup 0
1340
#define BoxStrategyNumberGroup 1
1341
#define PolygonStrategyNumberGroup 2
1342
#define CircleStrategyNumberGroup 3
1345
gist_point_consistent(PG_FUNCTION_ARGS)
1347
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1348
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1349
bool *recheck = (bool *) PG_GETARG_POINTER(4);
1351
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1353
switch (strategyGroup)
1355
case PointStrategyNumberGroup:
1356
result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset,
1358
DatumGetBoxP(entry->key),
1359
PG_GETARG_POINT_P(1));
1362
case BoxStrategyNumberGroup:
1365
* The only operator in this group is point <@ box (on_pb), so
1366
* we needn't examine strategy again.
1368
* For historical reasons, on_pb uses exact rather than fuzzy
1369
* comparisons. We could use box_overlap when at an internal
1370
* page, but that would lead to possibly visiting child pages
1371
* uselessly, because box_overlap uses fuzzy comparisons.
1372
* Instead we write a non-fuzzy overlap test. The same code
1373
* will also serve for leaf-page tests, since leaf keys have
1379
query = PG_GETARG_BOX_P(1);
1380
key = DatumGetBoxP(entry->key);
1382
result = (key->high.x >= query->low.x &&
1383
key->low.x <= query->high.x &&
1384
key->high.y >= query->low.y &&
1385
key->low.y <= query->high.y);
1389
case PolygonStrategyNumberGroup:
1391
POLYGON *query = PG_GETARG_POLYGON_P(1);
1393
result = DatumGetBool(DirectFunctionCall5(
1394
gist_poly_consistent,
1395
PointerGetDatum(entry),
1396
PolygonPGetDatum(query),
1397
Int16GetDatum(RTOverlapStrategyNumber),
1398
0, PointerGetDatum(recheck)));
1400
if (GIST_LEAF(entry) && result)
1403
* We are on leaf page and quick check shows overlapping
1404
* of polygon's bounding box and point
1406
BOX *box = DatumGetBoxP(entry->key);
1408
Assert(box->high.x == box->low.x
1409
&& box->high.y == box->low.y);
1410
result = DatumGetBool(DirectFunctionCall2(
1412
PolygonPGetDatum(query),
1413
PointPGetDatum(&box->high)));
1418
case CircleStrategyNumberGroup:
1420
CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1422
result = DatumGetBool(DirectFunctionCall5(
1423
gist_circle_consistent,
1424
PointerGetDatum(entry),
1425
CirclePGetDatum(query),
1426
Int16GetDatum(RTOverlapStrategyNumber),
1427
0, PointerGetDatum(recheck)));
1429
if (GIST_LEAF(entry) && result)
1432
* We are on leaf page and quick check shows overlapping
1433
* of polygon's bounding box and point
1435
BOX *box = DatumGetBoxP(entry->key);
1437
Assert(box->high.x == box->low.x
1438
&& box->high.y == box->low.y);
1439
result = DatumGetBool(DirectFunctionCall2(
1441
CirclePGetDatum(query),
1442
PointPGetDatum(&box->high)));
1448
elog(ERROR, "unrecognized strategy number: %d", strategy);
1449
result = false; /* keep compiler quiet */
1453
PG_RETURN_BOOL(result);
1457
gist_point_distance(PG_FUNCTION_ARGS)
1459
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1460
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1462
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1464
switch (strategyGroup)
1466
case PointStrategyNumberGroup:
1467
distance = computeDistance(GIST_LEAF(entry),
1468
DatumGetBoxP(entry->key),
1469
PG_GETARG_POINT_P(1));
1472
elog(ERROR, "unrecognized strategy number: %d", strategy);
1473
distance = 0.0; /* keep compiler quiet */
1477
PG_RETURN_FLOAT8(distance);
1481
* The inexact GiST distance method for geometric types that store bounding
1484
* Compute lossy distance from point to index entries. The result is inexact
1485
* because index entries are bounding boxes, not the exact shapes of the
1486
* indexed geometric types. We use distance from point to MBR of index entry.
1487
* This is a lower bound estimate of distance from point to indexed geometric
1491
gist_bbox_distance(GISTENTRY *entry, Datum query,
1492
StrategyNumber strategy, bool *recheck)
1495
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1497
/* Bounding box distance is always inexact. */
1500
switch (strategyGroup)
1502
case PointStrategyNumberGroup:
1503
distance = computeDistance(false,
1504
DatumGetBoxP(entry->key),
1505
DatumGetPointP(query));
1508
elog(ERROR, "unrecognized strategy number: %d", strategy);
1509
distance = 0.0; /* keep compiler quiet */
1516
gist_circle_distance(PG_FUNCTION_ARGS)
1518
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1519
Datum query = PG_GETARG_DATUM(1);
1520
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1522
/* Oid subtype = PG_GETARG_OID(3); */
1523
bool *recheck = (bool *) PG_GETARG_POINTER(4);
1526
distance = gist_bbox_distance(entry, query, strategy, recheck);
1528
PG_RETURN_FLOAT8(distance);
1532
gist_poly_distance(PG_FUNCTION_ARGS)
1534
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1535
Datum query = PG_GETARG_DATUM(1);
1536
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1538
/* Oid subtype = PG_GETARG_OID(3); */
1539
bool *recheck = (bool *) PG_GETARG_POINTER(4);
1542
distance = gist_bbox_distance(entry, query, strategy, recheck);
1544
PG_RETURN_FLOAT8(distance);
added
removed
src/backend/access/gist/gistproc.c
