Age Owner TLA 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-2023, PostgreSQL Global Development Group
11 : * Portions Copyright (c) 1994, Regents of the University of California
12 : *
13 : * IDENTIFICATION
14 : * src/backend/access/gist/gistproc.c
15 : *
16 : *-------------------------------------------------------------------------
17 : */
18 : #include "postgres.h"
19 :
20 : #include <math.h>
21 :
22 : #include "access/gist.h"
23 : #include "access/stratnum.h"
24 : #include "utils/builtins.h"
25 : #include "utils/float.h"
26 : #include "utils/geo_decls.h"
27 : #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
2460 tgl 55 CBC 20176448 : rt_box_union(BOX *n, const BOX *a, const BOX *b)
56 : {
1715 tomas.vondra 57 20176448 : n->high.x = float8_max(a->high.x, b->high.x);
58 20176448 : n->high.y = float8_max(a->high.y, b->high.y);
59 20176448 : n->low.x = float8_min(a->low.x, b->low.x);
60 20176448 : n->low.y = float8_min(a->low.y, b->low.y);
2460 tgl 61 20176448 : }
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 40352896 : 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 : */
1715 tomas.vondra 77 80705774 : if (float8_le(box->high.x, box->low.x) ||
78 40352878 : float8_le(box->high.y, box->low.y))
2460 tgl 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 40352878 : if (isnan(box->high.x) || isnan(box->high.y))
2460 tgl 87 UBC 0 : return get_float8_infinity();
1697 tomas.vondra 88 CBC 40352878 : return float8_mul(float8_mi(box->high.x, box->low.x),
89 40352878 : 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
2460 tgl 97 20176448 : box_penalty(const BOX *original, const BOX *new)
98 : {
99 : BOX unionbox;
100 :
101 20176448 : rt_box_union(&unionbox, original, new);
1697 tomas.vondra 102 20176448 : 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
6491 tgl 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 :
119 : /* Oid subtype = PG_GETARG_OID(3); */
5473 120 4083 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
121 :
122 : /* All cases served by this function are exact */
123 4083 : *recheck = false;
124 :
6491 125 4083 : if (DatumGetBoxP(entry->key) == NULL || query == NULL)
2062 peter_e 126 UBC 0 : PG_RETURN_BOOL(false);
127 :
128 : /*
129 : * if entry is not leaf, use rtree_internal_consistent, else use
130 : * gist_box_leaf_consistent
131 : */
6491 tgl 132 CBC 4083 : if (GIST_LEAF(entry))
133 2346 : PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
134 : query,
135 : strategy));
136 : else
137 1737 : PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
138 : query,
139 : strategy));
140 : }
141 :
142 : /*
143 : * Increase BOX b to include addon.
144 : */
145 : static void
2460 146 2502669 : adjustBox(BOX *b, const BOX *addon)
147 : {
1715 tomas.vondra 148 2502669 : if (float8_lt(b->high.x, addon->high.x))
6129 teodor 149 2117936 : b->high.x = addon->high.x;
1715 tomas.vondra 150 2502669 : if (float8_gt(b->low.x, addon->low.x))
6129 teodor 151 68417 : b->low.x = addon->low.x;
1715 tomas.vondra 152 2502669 : if (float8_lt(b->high.y, addon->high.y))
6129 teodor 153 2116730 : b->high.y = addon->high.y;
1715 tomas.vondra 154 2502669 : if (float8_gt(b->low.y, addon->low.y))
6129 teodor 155 68761 : b->low.y = addon->low.y;
156 2502669 : }
157 :
158 : /*
159 : * The GiST Union method for boxes
160 : *
161 : * returns the minimal bounding box that encloses all the entries in entryvec
162 : */
163 : Datum
6491 tgl 164 492225 : gist_box_union(PG_FUNCTION_ARGS)
165 : {
166 492225 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
167 492225 : int *sizep = (int *) PG_GETARG_POINTER(1);
168 : int numranges,
169 : i;
170 : BOX *cur,
171 : *pageunion;
172 :
173 492225 : numranges = entryvec->n;
174 492225 : pageunion = (BOX *) palloc(sizeof(BOX));
175 492225 : cur = DatumGetBoxP(entryvec->vector[0].key);
61 peter 176 GNC 492225 : memcpy(pageunion, cur, sizeof(BOX));
177 :
6491 tgl 178 CBC 1221744 : for (i = 1; i < numranges; i++)
179 : {
180 729519 : cur = DatumGetBoxP(entryvec->vector[i].key);
6031 bruce 181 729519 : adjustBox(pageunion, cur);
182 : }
6491 tgl 183 492225 : *sizep = sizeof(BOX);
184 :
185 492225 : PG_RETURN_POINTER(pageunion);
186 : }
187 :
188 : /*
189 : * We store boxes as boxes in GiST indexes, so we do not need
190 : * compress, decompress, or fetch functions.
191 : */
192 :
193 : /*
194 : * The GiST Penalty method for boxes (also used for points)
195 : *
196 : * As in the R-tree paper, we use change in area as our penalty metric
197 : */
198 : Datum
199 20176448 : gist_box_penalty(PG_FUNCTION_ARGS)
200 : {
201 20176448 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
202 20176448 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
203 20176448 : float *result = (float *) PG_GETARG_POINTER(2);
4200 heikki.linnakangas 204 20176448 : BOX *origbox = DatumGetBoxP(origentry->key);
205 20176448 : BOX *newbox = DatumGetBoxP(newentry->key);
206 :
2460 tgl 207 20176448 : *result = (float) box_penalty(origbox, newbox);
6491 208 20176448 : PG_RETURN_POINTER(result);
209 : }
210 :
211 : /*
212 : * Trivial split: half of entries will be placed on one page
213 : * and another half - to another
214 : */
215 : static void
5116 teodor 216 15 : fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
217 : {
218 : OffsetNumber i,
219 : maxoff;
5050 bruce 220 15 : BOX *unionL = NULL,
221 15 : *unionR = NULL;
222 : int nbytes;
223 :
5116 teodor 224 15 : maxoff = entryvec->n - 1;
225 :
226 15 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
227 15 : v->spl_left = (OffsetNumber *) palloc(nbytes);
228 15 : v->spl_right = (OffsetNumber *) palloc(nbytes);
229 15 : v->spl_nleft = v->spl_nright = 0;
230 :
231 5796 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
232 : {
5050 bruce 233 5781 : BOX *cur = DatumGetBoxP(entryvec->vector[i].key);
234 :
5116 teodor 235 5781 : if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
236 : {
237 2889 : v->spl_left[v->spl_nleft] = i;
238 2889 : if (unionL == NULL)
239 : {
240 15 : unionL = (BOX *) palloc(sizeof(BOX));
241 15 : *unionL = *cur;
242 : }
243 : else
244 2874 : adjustBox(unionL, cur);
245 :
246 2889 : v->spl_nleft++;
247 : }
248 : else
249 : {
250 2892 : v->spl_right[v->spl_nright] = i;
251 2892 : if (unionR == NULL)
252 : {
253 15 : unionR = (BOX *) palloc(sizeof(BOX));
254 15 : *unionR = *cur;
255 : }
256 : else
257 2877 : adjustBox(unionR, cur);
258 :
259 2892 : v->spl_nright++;
260 : }
261 : }
262 :
263 15 : v->spl_ldatum = BoxPGetDatum(unionL);
264 15 : v->spl_rdatum = BoxPGetDatum(unionR);
265 15 : }
266 :
267 : /*
268 : * Represents information about an entry that can be placed to either group
269 : * without affecting overlap over selected axis ("common entry").
270 : */
271 : typedef struct
272 : {
273 : /* Index of entry in the initial array */
274 : int index;
275 : /* Delta between penalties of entry insertion into different groups */
276 : float8 delta;
277 : } CommonEntry;
278 :
279 : /*
280 : * Context for g_box_consider_split. Contains information about currently
281 : * selected split and some general information.
282 : */
283 : typedef struct
284 : {
285 : int entriesCount; /* total number of entries being split */
286 : BOX boundingBox; /* minimum bounding box across all entries */
287 :
288 : /* Information about currently selected split follows */
289 :
290 : bool first; /* true if no split was selected yet */
291 :
292 : float8 leftUpper; /* upper bound of left interval */
293 : float8 rightLower; /* lower bound of right interval */
294 :
295 : float4 ratio;
296 : float4 overlap;
297 : int dim; /* axis of this split */
298 : float8 range; /* width of general MBR projection to the
299 : * selected axis */
300 : } ConsiderSplitContext;
301 :
302 : /*
303 : * Interval represents projection of box to axis.
304 : */
305 : typedef struct
306 : {
307 : float8 lower,
308 : upper;
309 : } SplitInterval;
310 :
311 : /*
312 : * Interval comparison function by lower bound of the interval;
313 : */
314 : static int
4203 heikki.linnakangas 315 4309728 : interval_cmp_lower(const void *i1, const void *i2)
316 : {
1697 tomas.vondra 317 4309728 : float8 lower1 = ((const SplitInterval *) i1)->lower,
4058 peter_e 318 4309728 : lower2 = ((const SplitInterval *) i2)->lower;
319 :
2460 tgl 320 4309728 : return float8_cmp_internal(lower1, lower2);
321 : }
322 :
323 : /*
324 : * Interval comparison function by upper bound of the interval;
325 : */
326 : static int
4203 heikki.linnakangas 327 4306418 : interval_cmp_upper(const void *i1, const void *i2)
328 : {
1697 tomas.vondra 329 4306418 : float8 upper1 = ((const SplitInterval *) i1)->upper,
4058 peter_e 330 4306418 : upper2 = ((const SplitInterval *) i2)->upper;
331 :
2460 tgl 332 4306418 : return float8_cmp_internal(upper1, upper2);
333 : }
334 :
335 : /*
336 : * Replace negative (or NaN) value with zero.
337 : */
338 : static inline float
4203 heikki.linnakangas 339 1354580 : non_negative(float val)
340 : {
341 1354580 : if (val >= 0.0f)
342 363854 : return val;
343 : else
344 990726 : return 0.0f;
345 : }
346 :
347 : /*
348 : * Consider replacement of currently selected split with the better one.
349 : */
350 : static inline void
351 3525241 : 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 3525241 : if (minLeftCount >= (context->entriesCount + 1) / 2)
366 : {
367 1767287 : leftCount = minLeftCount;
368 : }
369 : else
370 : {
371 1757954 : if (maxLeftCount <= context->entriesCount / 2)
372 1757555 : leftCount = maxLeftCount;
373 : else
374 399 : leftCount = context->entriesCount / 2;
375 : }
376 3525241 : rightCount = context->entriesCount - leftCount;
377 :
378 : /*
379 : * Ratio of split - quotient between size of lesser group and total
380 : * entries count.
381 : */
1697 tomas.vondra 382 3525241 : ratio = float4_div(Min(leftCount, rightCount), context->entriesCount);
383 :
4203 heikki.linnakangas 384 3525241 : if (ratio > LIMIT_RATIO)
385 : {
386 1422608 : 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 1422608 : if (dimNum == 0)
1697 tomas.vondra 396 711189 : range = float8_mi(context->boundingBox.high.x,
397 : context->boundingBox.low.x);
398 : else
399 711419 : range = float8_mi(context->boundingBox.high.y,
400 : context->boundingBox.low.y);
401 :
402 1422608 : overlap = float8_div(float8_mi(leftUpper, rightLower), range);
403 :
404 : /* If there is no previous selection, select this */
4203 heikki.linnakangas 405 1422608 : if (context->first)
406 5545 : selectthis = true;
407 1417063 : 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 740228 : if (overlap < context->overlap ||
414 737565 : (overlap == context->overlap && ratio > context->ratio))
415 108523 : 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 676835 : if (non_negative(overlap) < non_negative(context->overlap) ||
437 677290 : (range > context->range &&
438 455 : non_negative(overlap) <= non_negative(context->overlap)))
439 265 : selectthis = true;
440 : }
441 :
442 1422608 : if (selectthis)
443 : {
444 : /* save information about selected split */
445 114333 : context->first = false;
446 114333 : context->ratio = ratio;
447 114333 : context->range = range;
448 114333 : context->overlap = overlap;
449 114333 : context->rightLower = rightLower;
450 114333 : context->leftUpper = leftUpper;
451 114333 : context->dim = dimNum;
452 : }
453 : }
454 3525241 : }
455 :
456 : /*
457 : * Compare common entries by their deltas.
458 : */
459 : static int
4203 heikki.linnakangas 460 UBC 0 : common_entry_cmp(const void *i1, const void *i2)
461 : {
1697 tomas.vondra 462 0 : float8 delta1 = ((const CommonEntry *) i1)->delta,
4058 peter_e 463 0 : delta2 = ((const CommonEntry *) i2)->delta;
464 :
1697 tomas.vondra 465 0 : return float8_cmp_internal(delta1, delta2);
466 : }
467 :
468 : /*
469 : * --------------------------------------------------------------------------
470 : * Double sorting split algorithm. This is used for both boxes and points.
471 : *
472 : * The algorithm finds split of boxes by considering splits along each axis.
473 : * Each entry is first projected as an interval on the X-axis, and different
474 : * ways to split the intervals into two groups are considered, trying to
475 : * minimize the overlap of the groups. Then the same is repeated for the
476 : * Y-axis, and the overall best split is chosen. The quality of a split is
477 : * determined by overlap along that axis and some other criteria (see
478 : * g_box_consider_split).
479 : *
480 : * After that, all the entries are divided into three groups:
481 : *
482 : * 1) Entries which should be placed to the left group
483 : * 2) Entries which should be placed to the right group
484 : * 3) "Common entries" which can be placed to any of groups without affecting
485 : * of overlap along selected axis.
486 : *
487 : * The common entries are distributed by minimizing penalty.
488 : *
489 : * For details see:
490 : * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
491 : * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
492 : * --------------------------------------------------------------------------
493 : */
494 : Datum
6491 tgl 495 CBC 5560 : gist_box_picksplit(PG_FUNCTION_ARGS)
496 : {
497 5560 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
498 5560 : 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 :
4203 heikki.linnakangas 512 5560 : memset(&context, 0, sizeof(ConsiderSplitContext));
513 :
6491 tgl 514 5560 : maxoff = entryvec->n - 1;
4203 heikki.linnakangas 515 5560 : nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
516 :
517 : /* Allocate arrays for intervals along axes */
518 5560 : intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
519 5560 : intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
520 :
521 : /*
522 : * Calculate the overall minimum bounding box over all the entries.
523 : */
524 900475 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
525 : {
526 894915 : box = DatumGetBoxP(entryvec->vector[i].key);
527 894915 : if (i == FirstOffsetNumber)
528 5560 : context.boundingBox = *box;
529 : else
530 889355 : adjustBox(&context.boundingBox, box);
531 : }
532 :
533 : /*
534 : * Iterate over axes for optimal split searching.
535 : */
536 5560 : context.first = true; /* nothing selected yet */
537 16680 : 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 1800950 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
546 : {
547 1789830 : box = DatumGetBoxP(entryvec->vector[i].key);
548 1789830 : if (dim == 0)
549 : {
550 894915 : intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
551 894915 : intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
552 : }
553 : else
554 : {
555 894915 : intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
556 894915 : 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 11120 : memcpy(intervalsUpper, intervalsLower,
565 : sizeof(SplitInterval) * nentries);
566 11120 : qsort(intervalsLower, nentries, sizeof(SplitInterval),
567 : interval_cmp_lower);
568 11120 : 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 11120 : i1 = 0;
606 11120 : i2 = 0;
607 11120 : rightLower = intervalsLower[i1].lower;
608 11120 : leftUpper = intervalsUpper[i2].lower;
609 : while (true)
610 : {
611 : /*
612 : * Find next lower bound of right group.
613 : */
2460 tgl 614 7116120 : while (i1 < nentries &&
1715 tomas.vondra 615 3552500 : float8_eq(rightLower, intervalsLower[i1].lower))
616 : {
617 1789830 : if (float8_lt(leftUpper, intervalsLower[i1].upper))
2460 tgl 618 1745283 : leftUpper = intervalsLower[i1].upper;
4203 heikki.linnakangas 619 1789830 : i1++;
620 : }
621 1773790 : if (i1 >= nentries)
622 11120 : break;
623 1762670 : rightLower = intervalsLower[i1].lower;
624 :
625 : /*
626 : * Find count of intervals which anyway should be placed to the
627 : * left group.
628 : */
2460 tgl 629 7061990 : while (i2 < nentries &&
1715 tomas.vondra 630 3530924 : float8_le(intervalsUpper[i2].upper, leftUpper))
4203 heikki.linnakangas 631 1768396 : i2++;
632 :
633 : /*
634 : * Consider found split.
635 : */
636 1762670 : 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 11120 : i1 = nentries - 1;
644 11120 : i2 = nentries - 1;
645 11120 : rightLower = intervalsLower[i1].upper;
646 11120 : leftUpper = intervalsUpper[i2].upper;
647 : while (true)
648 : {
649 : /*
650 : * Find next upper bound of left group.
651 : */
1715 tomas.vondra 652 3563521 : while (i2 >= 0 && float8_eq(leftUpper, intervalsUpper[i2].upper))
653 : {
654 1789830 : if (float8_gt(rightLower, intervalsUpper[i2].lower))
2460 tgl 655 1745209 : rightLower = intervalsUpper[i2].lower;
4203 heikki.linnakangas 656 1789830 : i2--;
657 : }
658 1773691 : if (i2 < 0)
659 11120 : break;
660 1762571 : leftUpper = intervalsUpper[i2].upper;
661 :
662 : /*
663 : * Find count of intervals which anyway should be placed to the
664 : * right group.
665 : */
1715 tomas.vondra 666 3529731 : while (i1 >= 0 && float8_ge(intervalsLower[i1].lower, rightLower))
4203 heikki.linnakangas 667 1767160 : i1--;
668 :
669 : /*
670 : * Consider found split.
671 : */
672 1762571 : 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 5560 : if (context.first)
681 : {
5116 teodor 682 15 : fallbackSplit(entryvec, v);
683 15 : 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 */
4203 heikki.linnakangas 695 5545 : v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
696 5545 : v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
697 5545 : v->spl_nleft = 0;
698 5545 : v->spl_nright = 0;
699 :
700 : /* Allocate bounding boxes of left and right groups */
701 5545 : leftBox = palloc0(sizeof(BOX));
702 5545 : 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 5545 : commonEntriesCount = 0;
709 5545 : 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 894679 : 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 889134 : box = DatumGetBoxP(entryvec->vector[i].key);
743 889134 : if (context.dim == 0)
744 : {
745 844879 : lower = box->low.x;
746 844879 : upper = box->high.x;
747 : }
748 : else
749 : {
750 44255 : lower = box->low.y;
751 44255 : upper = box->high.y;
752 : }
753 :
1715 tomas.vondra 754 889134 : if (float8_le(upper, context.leftUpper))
755 : {
756 : /* Fits to the left group */
757 410022 : if (float8_ge(lower, context.rightLower))
758 : {
759 : /* Fits also to the right group, so "common entry" */
4203 heikki.linnakangas 760 UBC 0 : commonEntries[commonEntriesCount++].index = i;
761 : }
762 : else
763 : {
764 : /* Doesn't fit to the right group, so join to the left group */
4203 heikki.linnakangas 765 CBC 410022 : 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 : */
1715 tomas.vondra 775 479112 : Assert(float8_ge(lower, context.rightLower));
776 :
777 : /* Doesn't fit to the left group, so join to the right group */
4203 heikki.linnakangas 778 479112 : PLACE_RIGHT(box, i);
779 : }
780 : }
781 :
782 : /*
783 : * Distribute "common entries", if any.
784 : */
785 5545 : if (commonEntriesCount > 0)
786 : {
787 : /*
788 : * Calculate minimum number of entries that must be placed in both
789 : * groups, to reach LIMIT_RATIO.
790 : */
1697 tomas.vondra 791 UBC 0 : int m = ceil(LIMIT_RATIO * nentries);
792 :
793 : /*
794 : * Calculate delta between penalties of join "common entries" to
795 : * different groups.
796 : */
4203 heikki.linnakangas 797 0 : for (i = 0; i < commonEntriesCount; i++)
798 : {
799 0 : box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
184 peter 800 UNC 0 : 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 : */
4203 heikki.linnakangas 808 UBC 0 : qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
809 :
810 : /*
811 : * Distribute "common entries" between groups.
812 : */
813 0 : for (i = 0; i < commonEntriesCount; i++)
814 : {
815 0 : 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 0 : if (v->spl_nleft + (commonEntriesCount - i) <= m)
822 0 : PLACE_LEFT(box, commonEntries[i].index);
823 0 : else if (v->spl_nright + (commonEntriesCount - i) <= m)
824 0 : PLACE_RIGHT(box, commonEntries[i].index);
825 : else
826 : {
827 : /* Otherwise select the group by minimal penalty */
828 0 : if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
829 0 : PLACE_LEFT(box, commonEntries[i].index);
830 : else
831 0 : PLACE_RIGHT(box, commonEntries[i].index);
832 : }
833 : }
834 : }
835 :
4203 heikki.linnakangas 836 CBC 5545 : v->spl_ldatum = PointerGetDatum(leftBox);
837 5545 : v->spl_rdatum = PointerGetDatum(rightBox);
6491 tgl 838 5545 : PG_RETURN_POINTER(v);
839 : }
840 :
841 : /*
842 : * Equality method
843 : *
844 : * This is used for boxes, points, circles, and polygons, all of which store
845 : * boxes as GiST index entries.
846 : *
847 : * Returns true only when boxes are exactly the same. We can't use fuzzy
848 : * comparisons here without breaking index consistency; therefore, this isn't
849 : * equivalent to box_same().
850 : */
851 : Datum
852 396936 : gist_box_same(PG_FUNCTION_ARGS)
853 : {
854 396936 : BOX *b1 = PG_GETARG_BOX_P(0);
855 396936 : BOX *b2 = PG_GETARG_BOX_P(1);
856 396936 : bool *result = (bool *) PG_GETARG_POINTER(2);
857 :
858 396936 : if (b1 && b2)
1715 tomas.vondra 859 771040 : *result = (float8_eq(b1->low.x, b2->low.x) &&
860 747654 : float8_eq(b1->low.y, b2->low.y) &&
861 1144590 : float8_eq(b1->high.x, b2->high.x) &&
862 95796 : float8_eq(b1->high.y, b2->high.y));
863 : else
3712 tgl 864 UBC 0 : *result = (b1 == NULL && b2 == NULL);
6491 tgl 865 CBC 396936 : PG_RETURN_POINTER(result);
866 : }
867 :
868 : /*
869 : * Leaf-level consistency for boxes: just apply the query operator
870 : */
871 : static bool
872 2346 : gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
873 : {
874 : bool retval;
875 :
876 2346 : switch (strategy)
877 : {
6491 tgl 878 UBC 0 : case RTLeftStrategyNumber:
879 0 : retval = DatumGetBool(DirectFunctionCall2(box_left,
880 : PointerGetDatum(key),
881 : PointerGetDatum(query)));
882 0 : break;
883 0 : case RTOverLeftStrategyNumber:
884 0 : retval = DatumGetBool(DirectFunctionCall2(box_overleft,
885 : PointerGetDatum(key),
886 : PointerGetDatum(query)));
887 0 : break;
6491 tgl 888 CBC 813 : case RTOverlapStrategyNumber:
889 813 : retval = DatumGetBool(DirectFunctionCall2(box_overlap,
890 : PointerGetDatum(key),
891 : PointerGetDatum(query)));
892 813 : break;
6491 tgl 893 UBC 0 : case RTOverRightStrategyNumber:
894 0 : retval = DatumGetBool(DirectFunctionCall2(box_overright,
895 : PointerGetDatum(key),
896 : PointerGetDatum(query)));
897 0 : break;
898 0 : case RTRightStrategyNumber:
899 0 : retval = DatumGetBool(DirectFunctionCall2(box_right,
900 : PointerGetDatum(key),
901 : PointerGetDatum(query)));
902 0 : break;
903 0 : case RTSameStrategyNumber:
904 0 : retval = DatumGetBool(DirectFunctionCall2(box_same,
905 : PointerGetDatum(key),
906 : PointerGetDatum(query)));
907 0 : break;
908 0 : case RTContainsStrategyNumber:
909 0 : retval = DatumGetBool(DirectFunctionCall2(box_contain,
910 : PointerGetDatum(key),
911 : PointerGetDatum(query)));
912 0 : break;
6491 tgl 913 CBC 1533 : case RTContainedByStrategyNumber:
914 1533 : retval = DatumGetBool(DirectFunctionCall2(box_contained,
915 : PointerGetDatum(key),
916 : PointerGetDatum(query)));
917 1533 : break;
6491 tgl 918 UBC 0 : case RTOverBelowStrategyNumber:
919 0 : retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
920 : PointerGetDatum(key),
921 : PointerGetDatum(query)));
922 0 : break;
923 0 : case RTBelowStrategyNumber:
924 0 : retval = DatumGetBool(DirectFunctionCall2(box_below,
925 : PointerGetDatum(key),
926 : PointerGetDatum(query)));
927 0 : break;
928 0 : case RTAboveStrategyNumber:
929 0 : retval = DatumGetBool(DirectFunctionCall2(box_above,
930 : PointerGetDatum(key),
931 : PointerGetDatum(query)));
932 0 : break;
933 0 : case RTOverAboveStrategyNumber:
934 0 : retval = DatumGetBool(DirectFunctionCall2(box_overabove,
935 : PointerGetDatum(key),
936 : PointerGetDatum(query)));
937 0 : break;
938 0 : default:
3282 939 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
940 : retval = false; /* keep compiler quiet */
941 : break;
942 : }
6491 tgl 943 CBC 2346 : return retval;
944 : }
945 :
946 : /*****************************************
947 : * Common rtree functions (for boxes, polygons, and circles)
948 : *****************************************/
949 :
950 : /*
951 : * Internal-page consistency for all these types
952 : *
953 : * We can use the same function since all types use bounding boxes as the
954 : * internal-page representation.
955 : */
956 : static bool
957 3180 : rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
958 : {
959 : bool retval;
960 :
961 3180 : switch (strategy)
962 : {
6491 tgl 963 UBC 0 : case RTLeftStrategyNumber:
964 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overright,
965 : PointerGetDatum(key),
966 : PointerGetDatum(query)));
967 0 : break;
968 0 : case RTOverLeftStrategyNumber:
969 0 : retval = !DatumGetBool(DirectFunctionCall2(box_right,
970 : PointerGetDatum(key),
971 : PointerGetDatum(query)));
972 0 : break;
6491 tgl 973 CBC 1305 : case RTOverlapStrategyNumber:
974 1305 : retval = DatumGetBool(DirectFunctionCall2(box_overlap,
975 : PointerGetDatum(key),
976 : PointerGetDatum(query)));
977 1305 : break;
6491 tgl 978 UBC 0 : case RTOverRightStrategyNumber:
979 0 : retval = !DatumGetBool(DirectFunctionCall2(box_left,
980 : PointerGetDatum(key),
981 : PointerGetDatum(query)));
982 0 : break;
983 0 : case RTRightStrategyNumber:
984 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
985 : PointerGetDatum(key),
986 : PointerGetDatum(query)));
987 0 : break;
6491 tgl 988 CBC 300 : case RTSameStrategyNumber:
989 : case RTContainsStrategyNumber:
990 300 : retval = DatumGetBool(DirectFunctionCall2(box_contain,
991 : PointerGetDatum(key),
992 : PointerGetDatum(query)));
993 300 : break;
994 1575 : case RTContainedByStrategyNumber:
995 1575 : retval = DatumGetBool(DirectFunctionCall2(box_overlap,
996 : PointerGetDatum(key),
997 : PointerGetDatum(query)));
998 1575 : break;
6491 tgl 999 UBC 0 : case RTOverBelowStrategyNumber:
1000 0 : retval = !DatumGetBool(DirectFunctionCall2(box_above,
1001 : PointerGetDatum(key),
1002 : PointerGetDatum(query)));
1003 0 : break;
1004 0 : case RTBelowStrategyNumber:
1005 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
1006 : PointerGetDatum(key),
1007 : PointerGetDatum(query)));
1008 0 : break;
1009 0 : case RTAboveStrategyNumber:
1010 0 : retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
1011 : PointerGetDatum(key),
1012 : PointerGetDatum(query)));
1013 0 : break;
1014 0 : case RTOverAboveStrategyNumber:
1015 0 : retval = !DatumGetBool(DirectFunctionCall2(box_below,
1016 : PointerGetDatum(key),
1017 : PointerGetDatum(query)));
1018 0 : break;
1019 0 : default:
3282 1020 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1021 : retval = false; /* keep compiler quiet */
1022 : break;
1023 : }
6491 tgl 1024 CBC 3180 : return retval;
1025 : }
1026 :
1027 : /**************************************************
1028 : * Polygon ops
1029 : **************************************************/
1030 :
1031 : /*
1032 : * GiST compress for polygons: represent a polygon by its bounding box
1033 : */
1034 : Datum
1035 19766 : gist_poly_compress(PG_FUNCTION_ARGS)
1036 : {
1037 19766 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1038 : GISTENTRY *retval;
1039 :
1040 19766 : if (entry->leafkey)
1041 : {
2993 heikki.linnakangas 1042 18633 : POLYGON *in = DatumGetPolygonP(entry->key);
1043 : BOX *r;
1044 :
1045 18633 : r = (BOX *) palloc(sizeof(BOX));
61 peter 1046 GNC 18633 : memcpy(r, &(in->boundbox), sizeof(BOX));
1047 :
2993 heikki.linnakangas 1048 CBC 18633 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1049 18633 : gistentryinit(*retval, PointerGetDatum(r),
1050 : entry->rel, entry->page,
1051 : entry->offset, false);
1052 : }
1053 : else
6491 tgl 1054 1133 : retval = entry;
1055 19766 : PG_RETURN_POINTER(retval);
1056 : }
1057 :
1058 : /*
1059 : * The GiST Consistent method for polygons
1060 : */
1061 : Datum
1062 393 : gist_poly_consistent(PG_FUNCTION_ARGS)
1063 : {
1064 393 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1065 393 : POLYGON *query = PG_GETARG_POLYGON_P(1);
1066 393 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1067 :
1068 : /* Oid subtype = PG_GETARG_OID(3); */
5473 1069 393 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1070 : bool result;
1071 :
1072 : /* All cases served by this function are inexact */
1073 393 : *recheck = true;
1074 :
6491 1075 393 : if (DatumGetBoxP(entry->key) == NULL || query == NULL)
2062 peter_e 1076 UBC 0 : 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 : */
6491 tgl 1083 CBC 393 : result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1084 : &(query->boundbox), strategy);
1085 :
1086 : /* Avoid memory leak if supplied poly is toasted */
1087 393 : PG_FREE_IF_COPY(query, 1);
1088 :
1089 393 : PG_RETURN_BOOL(result);
1090 : }
1091 :
1092 : /**************************************************
1093 : * Circle ops
1094 : **************************************************/
1095 :
1096 : /*
1097 : * GiST compress for circles: represent a circle by its bounding box
1098 : */
1099 : Datum
1100 173868 : gist_circle_compress(PG_FUNCTION_ARGS)
1101 : {
1102 173868 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1103 : GISTENTRY *retval;
1104 :
1105 173868 : if (entry->leafkey)
1106 : {
2993 heikki.linnakangas 1107 78702 : CIRCLE *in = DatumGetCircleP(entry->key);
1108 : BOX *r;
1109 :
1110 78702 : r = (BOX *) palloc(sizeof(BOX));
1697 tomas.vondra 1111 78702 : r->high.x = float8_pl(in->center.x, in->radius);
1112 78702 : r->low.x = float8_mi(in->center.x, in->radius);
1113 78702 : r->high.y = float8_pl(in->center.y, in->radius);
1114 78702 : r->low.y = float8_mi(in->center.y, in->radius);
1115 :
2993 heikki.linnakangas 1116 78702 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1117 78702 : gistentryinit(*retval, PointerGetDatum(r),
1118 : entry->rel, entry->page,
1119 : entry->offset, false);
1120 : }
1121 : else
6491 tgl 1122 95166 : retval = entry;
1123 173868 : PG_RETURN_POINTER(retval);
1124 : }
1125 :
1126 : /*
1127 : * The GiST Consistent method for circles
1128 : */
1129 : Datum
1130 1050 : gist_circle_consistent(PG_FUNCTION_ARGS)
1131 : {
1132 1050 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
6408 bruce 1133 1050 : CIRCLE *query = PG_GETARG_CIRCLE_P(1);
6491 tgl 1134 1050 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1135 :
1136 : /* Oid subtype = PG_GETARG_OID(3); */
5473 1137 1050 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1138 : BOX bbox;
1139 : bool result;
1140 :
1141 : /* All cases served by this function are inexact */
1142 1050 : *recheck = true;
1143 :
6491 1144 1050 : if (DatumGetBoxP(entry->key) == NULL || query == NULL)
2062 peter_e 1145 UBC 0 : 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 : */
1697 tomas.vondra 1152 CBC 1050 : bbox.high.x = float8_pl(query->center.x, query->radius);
1153 1050 : bbox.low.x = float8_mi(query->center.x, query->radius);
1154 1050 : bbox.high.y = float8_pl(query->center.y, query->radius);
1155 1050 : bbox.low.y = float8_mi(query->center.y, query->radius);
1156 :
6491 tgl 1157 1050 : result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1158 : &bbox, strategy);
1159 :
1160 1050 : PG_RETURN_BOOL(result);
1161 : }
1162 :
1163 : /**************************************************
1164 : * Point ops
1165 : **************************************************/
1166 :
1167 : Datum
4833 teodor 1168 515423 : gist_point_compress(PG_FUNCTION_ARGS)
1169 : {
1170 515423 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1171 :
1172 515423 : if (entry->leafkey) /* Point, actually */
1173 : {
4790 bruce 1174 293644 : BOX *box = palloc(sizeof(BOX));
1175 293644 : Point *point = DatumGetPointP(entry->key);
4833 teodor 1176 293644 : GISTENTRY *retval = palloc(sizeof(GISTENTRY));
1177 :
1178 293644 : box->high = box->low = *point;
1179 :
1180 293644 : gistentryinit(*retval, BoxPGetDatum(box),
1181 : entry->rel, entry->page, entry->offset, false);
1182 :
1183 293644 : PG_RETURN_POINTER(retval);
1184 : }
1185 :
1186 221779 : PG_RETURN_POINTER(entry);
1187 : }
1188 :
1189 : /*
1190 : * GiST Fetch method for point
1191 : *
1192 : * Get point coordinates from its bounding box coordinates and form new
1193 : * gistentry.
1194 : */
1195 : Datum
2936 heikki.linnakangas 1196 50488 : gist_point_fetch(PG_FUNCTION_ARGS)
1197 : {
1198 50488 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1199 50488 : BOX *in = DatumGetBoxP(entry->key);
1200 : Point *r;
1201 : GISTENTRY *retval;
1202 :
1203 50488 : retval = palloc(sizeof(GISTENTRY));
1204 :
1205 50488 : r = (Point *) palloc(sizeof(Point));
1206 50488 : r->x = in->high.x;
1207 50488 : r->y = in->high.y;
1208 50488 : gistentryinit(*retval, PointerGetDatum(r),
1209 : entry->rel, entry->page,
1210 : entry->offset, false);
1211 :
1212 50488 : PG_RETURN_POINTER(retval);
1213 : }
1214 :
1215 :
1216 : #define point_point_distance(p1,p2) \
1217 : DatumGetFloat8(DirectFunctionCall2(point_distance, \
1218 : PointPGetDatum(p1), PointPGetDatum(p2)))
1219 :
1220 : static float8
4510 tgl 1221 5580 : computeDistance(bool isLeaf, BOX *box, Point *point)
1222 : {
1697 tomas.vondra 1223 5580 : float8 result = 0.0;
1224 :
4510 tgl 1225 5580 : if (isLeaf)
1226 : {
1227 : /* simple point to point distance */
1228 207 : result = point_point_distance(point, &box->low);
1229 : }
1230 5373 : else if (point->x <= box->high.x && point->x >= box->low.x &&
1231 246 : point->y <= box->high.y && point->y >= box->low.y)
1232 : {
1233 : /* point inside the box */
1234 165 : result = 0.0;
1235 : }
1236 5208 : else if (point->x <= box->high.x && point->x >= box->low.x)
1237 : {
1238 : /* point is over or below box */
1239 81 : Assert(box->low.y <= box->high.y);
1240 81 : if (point->y > box->high.y)
1697 tomas.vondra 1241 6 : result = float8_mi(point->y, box->high.y);
4510 tgl 1242 75 : else if (point->y < box->low.y)
1697 tomas.vondra 1243 75 : result = float8_mi(box->low.y, point->y);
1244 : else
4510 tgl 1245 UBC 0 : elog(ERROR, "inconsistent point values");
1246 : }
4510 tgl 1247 CBC 5127 : else if (point->y <= box->high.y && point->y >= box->low.y)
1248 : {
1249 : /* point is to left or right of box */
1250 27 : Assert(box->low.x <= box->high.x);
1251 27 : if (point->x > box->high.x)
1697 tomas.vondra 1252 UBC 0 : result = float8_mi(point->x, box->high.x);
4510 tgl 1253 CBC 27 : else if (point->x < box->low.x)
1697 tomas.vondra 1254 27 : result = float8_mi(box->low.x, point->x);
1255 : else
4510 tgl 1256 UBC 0 : elog(ERROR, "inconsistent point values");
1257 : }
1258 : else
1259 : {
1260 : /* closest point will be a vertex */
1261 : Point p;
1262 : float8 subresult;
1263 :
4510 tgl 1264 CBC 5100 : result = point_point_distance(point, &box->low);
1265 :
1266 5100 : subresult = point_point_distance(point, &box->high);
1267 5100 : if (result > subresult)
4510 tgl 1268 UBC 0 : result = subresult;
1269 :
4510 tgl 1270 CBC 5100 : p.x = box->low.x;
1271 5100 : p.y = box->high.y;
1272 5100 : subresult = point_point_distance(point, &p);
1273 5100 : if (result > subresult)
1274 9 : result = subresult;
1275 :
1276 5100 : p.x = box->high.x;
1277 5100 : p.y = box->low.y;
1278 5100 : subresult = point_point_distance(point, &p);
1279 5100 : if (result > subresult)
1280 6 : result = subresult;
1281 : }
1282 :
1283 5580 : return result;
1284 : }
1285 :
1286 : static bool
4833 teodor 1287 27581 : gist_point_consistent_internal(StrategyNumber strategy,
1288 : bool isLeaf, BOX *key, Point *query)
1289 : {
4790 bruce 1290 27581 : bool result = false;
1291 :
4833 teodor 1292 27581 : switch (strategy)
1293 : {
1294 9750 : case RTLeftStrategyNumber:
1295 9750 : result = FPlt(key->low.x, query->x);
1296 9750 : break;
1297 14414 : case RTRightStrategyNumber:
1298 14414 : result = FPgt(key->high.x, query->x);
1299 14414 : break;
1300 30 : case RTAboveStrategyNumber:
1301 30 : result = FPgt(key->high.y, query->y);
1302 30 : break;
1303 30 : case RTBelowStrategyNumber:
1304 30 : result = FPlt(key->low.y, query->y);
1305 30 : break;
1306 3357 : case RTSameStrategyNumber:
1307 3357 : if (isLeaf)
1308 : {
1309 : /* key.high must equal key.low, so we can disregard it */
3712 tgl 1310 6327 : result = (FPeq(key->low.x, query->x) &&
1311 3012 : FPeq(key->low.y, query->y));
1312 : }
1313 : else
1314 : {
1315 108 : result = (FPle(query->x, key->high.x) &&
1316 48 : FPge(query->x, key->low.x) &&
1317 90 : FPle(query->y, key->high.y) &&
1318 24 : FPge(query->y, key->low.y));
1319 : }
4833 teodor 1320 3357 : break;
4833 teodor 1321 UBC 0 : default:
3282 tgl 1322 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1323 : result = false; /* keep compiler quiet */
1324 : break;
1325 : }
1326 :
4833 teodor 1327 CBC 27581 : return result;
1328 : }
1329 :
1330 : #define GeoStrategyNumberOffset 20
1331 : #define PointStrategyNumberGroup 0
1332 : #define BoxStrategyNumberGroup 1
1333 : #define PolygonStrategyNumberGroup 2
1334 : #define CircleStrategyNumberGroup 3
1335 :
1336 : Datum
1337 32999 : gist_point_consistent(PG_FUNCTION_ARGS)
1338 : {
1339 32999 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
4790 bruce 1340 32999 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
4833 teodor 1341 32999 : 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 : */
867 tgl 1349 32999 : if (strategy == RTOldBelowStrategyNumber)
867 tgl 1350 UBC 0 : strategy = RTBelowStrategyNumber;
867 tgl 1351 CBC 32999 : else if (strategy == RTOldAboveStrategyNumber)
867 tgl 1352 UBC 0 : strategy = RTAboveStrategyNumber;
1353 :
867 tgl 1354 CBC 32999 : strategyGroup = strategy / GeoStrategyNumberOffset;
4833 teodor 1355 32999 : switch (strategyGroup)
1356 : {
1357 27581 : case PointStrategyNumberGroup:
1358 27581 : result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset,
1359 27581 : GIST_LEAF(entry),
1360 : DatumGetBoxP(entry->key),
1361 : PG_GETARG_POINT_P(1));
1362 27581 : *recheck = false;
1363 27581 : break;
1364 5358 : 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 :
3712 tgl 1381 5358 : query = PG_GETARG_BOX_P(1);
1382 5358 : key = DatumGetBoxP(entry->key);
1383 :
1384 15636 : result = (key->high.x >= query->low.x &&
1385 4920 : key->low.x <= query->high.x &&
1386 10617 : key->high.y >= query->low.y &&
1387 339 : key->low.y <= query->high.y);
1388 5358 : *recheck = false;
1389 : }
4833 teodor 1390 5358 : break;
1391 30 : case PolygonStrategyNumberGroup:
1392 : {
1393 30 : POLYGON *query = PG_GETARG_POLYGON_P(1);
1394 :
1165 alvherre 1395 30 : result = DatumGetBool(DirectFunctionCall5(gist_poly_consistent,
1396 : PointerGetDatum(entry),
1397 : PolygonPGetDatum(query),
1398 : Int16GetDatum(RTOverlapStrategyNumber),
1399 : 0, PointerGetDatum(recheck)));
1400 :
4833 teodor 1401 30 : 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 : */
4790 bruce 1407 12 : BOX *box = DatumGetBoxP(entry->key);
1408 :
4833 teodor 1409 12 : Assert(box->high.x == box->low.x
1410 : && box->high.y == box->low.y);
1165 alvherre 1411 12 : result = DatumGetBool(DirectFunctionCall2(poly_contain_pt,
1412 : PolygonPGetDatum(query),
1413 : PointPGetDatum(&box->high)));
4833 teodor 1414 12 : *recheck = false;
1415 : }
1416 : }
1417 30 : break;
1418 30 : case CircleStrategyNumberGroup:
1419 : {
4790 bruce 1420 30 : CIRCLE *query = PG_GETARG_CIRCLE_P(1);
1421 :
1165 alvherre 1422 30 : result = DatumGetBool(DirectFunctionCall5(gist_circle_consistent,
1423 : PointerGetDatum(entry),
1424 : CirclePGetDatum(query),
1425 : Int16GetDatum(RTOverlapStrategyNumber),
1426 : 0, PointerGetDatum(recheck)));
1427 :
4833 teodor 1428 30 : 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 : */
4790 bruce 1434 12 : BOX *box = DatumGetBoxP(entry->key);
1435 :
4833 teodor 1436 12 : Assert(box->high.x == box->low.x
1437 : && box->high.y == box->low.y);
1165 alvherre 1438 12 : result = DatumGetBool(DirectFunctionCall2(circle_contain_pt,
1439 : CirclePGetDatum(query),
1440 : PointPGetDatum(&box->high)));
4833 teodor 1441 12 : *recheck = false;
1442 : }
1443 : }
1444 30 : break;
4833 teodor 1445 UBC 0 : default:
3282 tgl 1446 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1447 : result = false; /* keep compiler quiet */
1448 : break;
1449 : }
1450 :
4833 teodor 1451 CBC 32999 : PG_RETURN_BOOL(result);
1452 : }
1453 :
1454 : Datum
4510 tgl 1455 222 : gist_point_distance(PG_FUNCTION_ARGS)
1456 : {
1457 222 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1458 222 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1459 : float8 distance;
1460 222 : StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1461 :
1462 222 : switch (strategyGroup)
1463 : {
1464 222 : case PointStrategyNumberGroup:
1465 222 : distance = computeDistance(GIST_LEAF(entry),
1466 : DatumGetBoxP(entry->key),
1467 : PG_GETARG_POINT_P(1));
1468 222 : break;
4510 tgl 1469 UBC 0 : default:
3282 1470 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1471 : distance = 0.0; /* keep compiler quiet */
1472 : break;
1473 : }
1474 :
4510 tgl 1475 CBC 222 : PG_RETURN_FLOAT8(distance);
1476 : }
1477 :
1478 : static float8
1365 akorotkov 1479 5358 : gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
1480 : {
1481 : float8 distance;
2886 heikki.linnakangas 1482 5358 : StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1483 :
1484 5358 : switch (strategyGroup)
1485 : {
1486 5358 : case PointStrategyNumberGroup:
1487 5358 : distance = computeDistance(false,
1488 : DatumGetBoxP(entry->key),
1489 : DatumGetPointP(query));
1490 5358 : break;
2886 heikki.linnakangas 1491 UBC 0 : default:
2637 tgl 1492 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
1493 : distance = 0.0; /* keep compiler quiet */
1494 : }
1495 :
2637 tgl 1496 CBC 5358 : return distance;
1497 : }
1498 :
1499 : Datum
1365 akorotkov 1500 132 : gist_box_distance(PG_FUNCTION_ARGS)
1501 : {
1502 132 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1503 132 : Datum query = PG_GETARG_DATUM(1);
1504 132 : 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 132 : distance = gist_bbox_distance(entry, query, strategy);
1511 :
1512 132 : PG_RETURN_FLOAT8(distance);
1513 : }
1514 :
1515 : /*
1516 : * The inexact GiST distance methods for geometric types that store bounding
1517 : * boxes.
1518 : *
1519 : * Compute lossy distance from point to index entries. The result is inexact
1520 : * because index entries are bounding boxes, not the exact shapes of the
1521 : * indexed geometric types. We use distance from point to MBR of index entry.
1522 : * This is a lower bound estimate of distance from point to indexed geometric
1523 : * type.
1524 : */
1525 : Datum
2637 tgl 1526 870 : gist_circle_distance(PG_FUNCTION_ARGS)
1527 : {
1528 870 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1529 870 : Datum query = PG_GETARG_DATUM(1);
1530 870 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1531 :
1532 : /* Oid subtype = PG_GETARG_OID(3); */
1533 870 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1534 : float8 distance;
1535 :
1365 akorotkov 1536 870 : distance = gist_bbox_distance(entry, query, strategy);
1537 870 : *recheck = true;
1538 :
2637 tgl 1539 870 : PG_RETURN_FLOAT8(distance);
1540 : }
1541 :
1542 : Datum
1543 4356 : gist_poly_distance(PG_FUNCTION_ARGS)
1544 : {
1545 4356 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1546 4356 : Datum query = PG_GETARG_DATUM(1);
1547 4356 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1548 :
1549 : /* Oid subtype = PG_GETARG_OID(3); */
1550 4356 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
1551 : float8 distance;
1552 :
1365 akorotkov 1553 4356 : distance = gist_bbox_distance(entry, query, strategy);
1554 4356 : *recheck = true;
1555 :
2886 heikki.linnakangas 1556 4356 : PG_RETURN_FLOAT8(distance);
1557 : }
1558 :
1559 : /*
1560 : * Z-order routines for fast index build
1561 : */
1562 :
1563 : /*
1564 : * Compute Z-value of a point
1565 : *
1566 : * Z-order (also known as Morton Code) maps a two-dimensional point to a
1567 : * single integer, in a way that preserves locality. Points that are close in
1568 : * the two-dimensional space are mapped to integer that are not far from each
1569 : * other. We do that by interleaving the bits in the X and Y components.
1570 : *
1571 : * Morton Code is normally defined only for integers, but the X and Y values
1572 : * of a point are floating point. We expect floats to be in IEEE format.
1573 : */
1574 : static uint64
934 1575 97078 : point_zorder_internal(float4 x, float4 y)
1576 : {
1577 97078 : uint32 ix = ieee_float32_to_uint32(x);
1578 97078 : uint32 iy = ieee_float32_to_uint32(y);
1579 :
1580 : /* Interleave the bits */
1581 97078 : return part_bits32_by2(ix) | (part_bits32_by2(iy) << 1);
1582 : }
1583 :
1584 : /* Interleave 32 bits with zeroes */
1585 : static uint64
1586 194156 : part_bits32_by2(uint32 x)
1587 : {
1588 194156 : uint64 n = x;
1589 :
1590 194156 : n = (n | (n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
1591 194156 : n = (n | (n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
1592 194156 : n = (n | (n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
1593 194156 : n = (n | (n << 2)) & UINT64CONST(0x3333333333333333);
1594 194156 : n = (n | (n << 1)) & UINT64CONST(0x5555555555555555);
1595 :
1596 194156 : return n;
1597 : }
1598 :
1599 : /*
1600 : * Convert a 32-bit IEEE float to uint32 in a way that preserves the ordering
1601 : */
1602 : static uint32
1603 194156 : 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 194156 : if (isnan(f))
1646 12 : return 0xFFFFFFFF;
1647 : else
1648 : {
1649 : union
1650 : {
1651 : float f;
1652 : uint32 i;
1653 : } u;
1654 :
1655 194144 : u.f = f;
1656 :
1657 : /* Check the sign bit */
1658 194144 : 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 30 : Assert(f <= 0); /* can be -0 */
1665 30 : u.i ^= 0xFFFFFFFF;
1666 : }
1667 : else
1668 : {
1669 : /* Map the positive value (or 0) to range 80000000-FFFFFFFF */
1670 194114 : u.i |= 0x80000000;
1671 : }
1672 :
1673 194144 : return u.i;
1674 : }
1675 : }
1676 :
1677 : /*
1678 : * Compare the Z-order of points
1679 : */
1680 : static int
1681 3006 : gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup)
1682 : {
1683 3006 : Point *p1 = &(DatumGetBoxP(a)->low);
1684 3006 : 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 3006 : if (p1->x == p2->x && p1->y == p2->y)
1694 3000 : return 0;
1695 :
1696 6 : z1 = point_zorder_internal(p1->x, p1->y);
1697 6 : z2 = point_zorder_internal(p2->x, p2->y);
1698 6 : if (z1 > z2)
934 heikki.linnakangas 1699 UBC 0 : return 1;
934 heikki.linnakangas 1700 CBC 6 : else if (z1 < z2)
934 heikki.linnakangas 1701 UBC 0 : return -1;
1702 : else
934 heikki.linnakangas 1703 CBC 6 : return 0;
1704 : }
1705 :
1706 : /*
1707 : * Abbreviated version of Z-order comparison
1708 : *
1709 : * The abbreviated format is a Z-order value computed from the two 32-bit
1710 : * floats. If SIZEOF_DATUM == 8, the 64-bit Z-order value fits fully in the
1711 : * abbreviated Datum, otherwise use its most significant bits.
1712 : */
1713 : static Datum
1714 97066 : gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
1715 : {
1716 97066 : Point *p = &(DatumGetBoxP(original)->low);
1717 : uint64 z;
1718 :
1719 97066 : z = point_zorder_internal(p->x, p->y);
1720 :
1721 : #if SIZEOF_DATUM == 8
1722 97066 : return (Datum) z;
1723 : #else
1724 : return (Datum) (z >> 32);
1725 : #endif
1726 : }
1727 :
1728 : /*
1729 : * We never consider aborting the abbreviation.
1730 : *
1731 : * On 64-bit systems, the abbreviation is not lossy so it is always
1732 : * worthwhile. (Perhaps it's not on 32-bit systems, but we don't bother
1733 : * with logic to decide.)
1734 : */
1735 : static bool
1736 112 : gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
1737 : {
1738 112 : return false;
1739 : }
1740 :
1741 : /*
1742 : * Sort support routine for fast GiST index build by sorting.
1743 : */
1744 : Datum
1745 69 : gist_point_sortsupport(PG_FUNCTION_ARGS)
1746 : {
1747 69 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
1748 :
1749 69 : if (ssup->abbreviate)
1750 : {
372 john.naylor 1751 69 : ssup->comparator = ssup_datum_unsigned_cmp;
934 heikki.linnakangas 1752 69 : ssup->abbrev_converter = gist_bbox_zorder_abbrev_convert;
1753 69 : ssup->abbrev_abort = gist_bbox_zorder_abbrev_abort;
1754 69 : ssup->abbrev_full_comparator = gist_bbox_zorder_cmp;
1755 : }
1756 : else
1757 : {
934 heikki.linnakangas 1758 UBC 0 : ssup->comparator = gist_bbox_zorder_cmp;
1759 : }
934 heikki.linnakangas 1760 CBC 69 : PG_RETURN_VOID();
1761 : }
|
