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