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