Debian Codegraph @

src/backend/access/gist/gistproc.c

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