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