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