PostgreSQL Source Code: src/backend/access/gist/gistproc.c Source File

PostgreSQL Source Code git master
gistproc.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * gistproc.c
4 * Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
5 * points).
6 *
7 * This gives R-tree behavior, with Guttman's poly-time split algorithm.
8 *
9 *
10 * Portions Copyright (c) 1996-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
30static bool gist_box_leaf_consistent(BOX *key, BOX *query,
31 StrategyNumber strategy);
32static bool rtree_internal_consistent(BOX *key, BOX *query,
33 StrategyNumber strategy);
34
35static uint64 point_zorder_internal(float4 x, float4 y);
36static uint64 part_bits32_by2(uint32 x);
37static uint32 ieee_float32_to_uint32(float f);
38static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup);
39static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup);
40static 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 */
54static 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 */
67static 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 */
96static 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 */
112Datum
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 */
145static 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 */
163Datum
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 */
198Datum
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 */
215static 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 */
314static 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 */
326static 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 */
338static 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 */
350static 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 */
459static 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 */
494Datum
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 */
851Datum
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 */
871static 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 */
956static 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 */
1034Datum
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 */
1061Datum
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 */
1099Datum
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 */
1129Datum
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
1167Datum
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 */
1195Datum
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
1220static 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
1286static 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
1336Datum
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
1454Datum
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
1478static 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
1499Datum
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 */
1525Datum
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
1542Datum
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 */
1574static 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 */
1585static 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 */
1602static 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 */
1680static 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. Now that sizeof(Datum) is always 8, the 64-bit Z-order value
1711 * always fits fully in the abbreviated Datum.
1712 */
1713static 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 return UInt64GetDatum(z);
1722}
1723
1724/*
1725 * We never consider aborting the abbreviation.
1726 *
1727 * On 64-bit systems, the abbreviation is not lossy so it is always
1728 * worthwhile. (Perhaps it's not on 32-bit systems, but we don't bother
1729 * with logic to decide.)
1730 */
1731static bool
1732 gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
1733{
1734 return false;
1735}
1736
1737/*
1738 * Sort support routine for fast GiST index build by sorting.
1739 */
1740Datum
1741 gist_point_sortsupport(PG_FUNCTION_ARGS)
1742{
1743 SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
1744
1745 if (ssup->abbreviate)
1746 {
1747 ssup->comparator = ssup_datum_unsigned_cmp;
1748 ssup->abbrev_converter = gist_bbox_zorder_abbrev_convert;
1749 ssup->abbrev_abort = gist_bbox_zorder_abbrev_abort;
1750 ssup->abbrev_full_comparator = gist_bbox_zorder_cmp;
1751 }
1752 else
1753 {
1754 ssup->comparator = gist_bbox_zorder_cmp;
1755 }
1756 PG_RETURN_VOID();
1757}
#define Min(x, y)
Definition: c.h:1003
double float8
Definition: c.h:635
uint64_t uint64
Definition: c.h:539
uint32_t uint32
Definition: c.h:538
float float4
Definition: c.h:634
#define UINT64CONST(x)
Definition: c.h:553
struct cursor * cur
Definition: ecpg.c:29
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:910
static float8 float8_min(const float8 val1, const float8 val2)
Definition: float.h:340
static float8 float8_mul(const float8 val1, const float8 val2)
Definition: float.h:208
static float4 float4_div(const float4 val1, const float4 val2)
Definition: float.h:222
static float8 float8_pl(const float8 val1, const float8 val2)
Definition: float.h:158
static float8 float8_mi(const float8 val1, const float8 val2)
Definition: float.h:182
static float8 get_float8_infinity(void)
Definition: float.h:94
static bool float8_ge(const float8 val1, const float8 val2)
Definition: float.h:328
static float8 float8_max(const float8 val1, const float8 val2)
Definition: float.h:352
static bool float8_le(const float8 val1, const float8 val2)
Definition: float.h:304
static bool float8_eq(const float8 val1, const float8 val2)
Definition: float.h:268
static float8 float8_div(const float8 val1, const float8 val2)
Definition: float.h:238
static bool float8_lt(const float8 val1, const float8 val2)
Definition: float.h:292
static bool float8_gt(const float8 val1, const float8 val2)
Definition: float.h:316
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:684
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_GETARG_UINT16(n)
Definition: fmgr.h:272
#define DirectFunctionCall5(func, arg1, arg2, arg3, arg4, arg5)
Definition: fmgr.h:690
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
static bool FPlt(double A, double B)
Definition: geo_decls.h:59
#define PG_GETARG_POINT_P(n)
Definition: geo_decls.h:185
static bool FPge(double A, double B)
Definition: geo_decls.h:77
static Datum PolygonPGetDatum(const POLYGON *X)
Definition: geo_decls.h:257
static Point * DatumGetPointP(Datum X)
Definition: geo_decls.h:176
static Datum PointPGetDatum(const Point *X)
Definition: geo_decls.h:181
static POLYGON * DatumGetPolygonP(Datum X)
Definition: geo_decls.h:247
static BOX * DatumGetBoxP(Datum X)
Definition: geo_decls.h:234
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:243
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:261
static CIRCLE * DatumGetCircleP(Datum X)
Definition: geo_decls.h:266
static Datum CirclePGetDatum(const CIRCLE *X)
Definition: geo_decls.h:271
#define PG_GETARG_CIRCLE_P(n)
Definition: geo_decls.h:275
static bool FPgt(double A, double B)
Definition: geo_decls.h:71
static bool FPle(double A, double B)
Definition: geo_decls.h:65
static Datum BoxPGetDatum(const BOX *X)
Definition: geo_decls.h:239
static bool FPeq(double A, double B)
Definition: geo_decls.h:47
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:583
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:609
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:551
Datum poly_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4008
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:635
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:624
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:670
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:563
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:692
Datum circle_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5082
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:647
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:681
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:598
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:658
#define GIST_LEAF(entry)
Definition: gist.h:171
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:245
static void adjustBox(BOX *b, const BOX *addon)
Definition: gistproc.c:146
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
Definition: gistproc.c:216
Datum gist_box_penalty(PG_FUNCTION_ARGS)
Definition: gistproc.c:199
#define BoxStrategyNumberGroup
Definition: gistproc.c:1332
Datum gist_box_picksplit(PG_FUNCTION_ARGS)
Definition: gistproc.c:495
Datum gist_circle_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1100
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:957
Datum gist_box_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:113
static int interval_cmp_upper(const void *i1, const void *i2)
Definition: gistproc.c:327
static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup)
Definition: gistproc.c:1681
Datum gist_box_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1500
#define point_point_distance(p1, p2)
Definition: gistproc.c:1216
#define LIMIT_RATIO
Definition: gistproc.c:44
static float8 gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
Definition: gistproc.c:1479
Datum gist_poly_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1035
static void rt_box_union(BOX *n, const BOX *a, const BOX *b)
Definition: gistproc.c:55
#define GeoStrategyNumberOffset
Definition: gistproc.c:1330
#define PLACE_RIGHT(box, off)
Datum gist_poly_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1543
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float8 rightLower, int minLeftCount, float8 leftUpper, int maxLeftCount)
Definition: gistproc.c:351
Datum gist_point_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1455
static float8 box_penalty(const BOX *original, const BOX *new)
Definition: gistproc.c:97
Datum gist_circle_distance(PG_FUNCTION_ARGS)
Definition: gistproc.c:1526
static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
Definition: gistproc.c:1714
#define CircleStrategyNumberGroup
Definition: gistproc.c:1334
static uint64 part_bits32_by2(uint32 x)
Definition: gistproc.c:1586
Datum gist_point_sortsupport(PG_FUNCTION_ARGS)
Definition: gistproc.c:1741
#define PointStrategyNumberGroup
Definition: gistproc.c:1331
Datum gist_box_union(PG_FUNCTION_ARGS)
Definition: gistproc.c:164
static int interval_cmp_lower(const void *i1, const void *i2)
Definition: gistproc.c:315
static float8 size_box(const BOX *box)
Definition: gistproc.c:68
static uint32 ieee_float32_to_uint32(float f)
Definition: gistproc.c:1603
Datum gist_circle_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1130
static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Definition: gistproc.c:872
static int common_entry_cmp(const void *i1, const void *i2)
Definition: gistproc.c:460
#define PolygonStrategyNumberGroup
Definition: gistproc.c:1333
Datum gist_poly_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1062
Datum gist_point_compress(PG_FUNCTION_ARGS)
Definition: gistproc.c:1168
static uint64 point_zorder_internal(float4 x, float4 y)
Definition: gistproc.c:1575
Datum gist_point_consistent(PG_FUNCTION_ARGS)
Definition: gistproc.c:1337
static bool gist_point_consistent_internal(StrategyNumber strategy, bool isLeaf, BOX *key, Point *query)
Definition: gistproc.c:1287
Datum gist_box_same(PG_FUNCTION_ARGS)
Definition: gistproc.c:852
#define PLACE_LEFT(box, off)
static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
Definition: gistproc.c:1732
static float8 computeDistance(bool isLeaf, BOX *box, Point *point)
Definition: gistproc.c:1221
Datum gist_point_fetch(PG_FUNCTION_ARGS)
Definition: gistproc.c:1196
static float non_negative(float val)
Definition: gistproc.c:339
Assert(PointerIsAligned(start, uint64))
long val
Definition: informix.c:689
y
int y
Definition: isn.c:76
b
int b
Definition: isn.c:74
x
int x
Definition: isn.c:75
a
int a
Definition: isn.c:73
i
int i
Definition: isn.c:77
void * palloc0(Size size)
Definition: mcxt.c:1395
void * palloc(Size size)
Definition: mcxt.c:1365
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
#define qsort(a, b, c, d)
Definition: port.h:479
static bool DatumGetBool(Datum X)
Definition: postgres.h:100
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:332
static Datum UInt64GetDatum(uint64 X)
Definition: postgres.h:423
static Datum Int16GetDatum(int16 X)
Definition: postgres.h:182
uint64_t Datum
Definition: postgres.h:70
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTOverlapStrategyNumber
Definition: stratnum.h:53
#define RTLeftStrategyNumber
Definition: stratnum.h:51
#define RTOverRightStrategyNumber
Definition: stratnum.h:54
#define RTRightStrategyNumber
Definition: stratnum.h:55
#define RTSameStrategyNumber
Definition: stratnum.h:56
#define RTOverAboveStrategyNumber
Definition: stratnum.h:62
#define RTOldBelowStrategyNumber
Definition: stratnum.h:79
#define RTContainsStrategyNumber
Definition: stratnum.h:57
#define RTOverBelowStrategyNumber
Definition: stratnum.h:59
#define RTBelowStrategyNumber
Definition: stratnum.h:60
#define RTOldAboveStrategyNumber
Definition: stratnum.h:80
#define RTAboveStrategyNumber
Definition: stratnum.h:61
#define RTOverLeftStrategyNumber
Definition: stratnum.h:52
#define RTContainedByStrategyNumber
Definition: stratnum.h:58
Definition: geo_decls.h:141
Point low
Definition: geo_decls.h:143
Point high
Definition: geo_decls.h:142
Definition: geo_decls.h:163
float8 radius
Definition: geo_decls.h:165
Point center
Definition: geo_decls.h:164
int index
Definition: gistproc.c:274
float8 delta
Definition: gistproc.c:276
float8 rightLower
Definition: gistproc.c:293
float8 leftUpper
Definition: gistproc.c:292
Definition: gist.h:160
OffsetNumber offset
Definition: gist.h:164
Datum key
Definition: gist.h:161
Page page
Definition: gist.h:163
Relation rel
Definition: gist.h:162
bool leafkey
Definition: gist.h:165
Definition: gist.h:142
int spl_nleft
Definition: gist.h:144
OffsetNumber * spl_right
Definition: gist.h:148
Datum spl_ldatum
Definition: gist.h:145
Datum spl_rdatum
Definition: gist.h:150
int spl_nright
Definition: gist.h:149
OffsetNumber * spl_left
Definition: gist.h:143
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:237
int32 n
Definition: gist.h:236
BOX boundbox
Definition: geo_decls.h:155
Definition: geo_decls.h:97
float8 y
Definition: geo_decls.h:99
float8 x
Definition: geo_decls.h:98
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182
float8 upper
Definition: gistproc.c:308
float8 lower
Definition: gistproc.c:307
Definition: type.h:96
int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)
Definition: tuplesort.c:3133

AltStyle によって変換されたページ (->オリジナル) /