Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * rangetypes_gist.c
4 : : * GiST support for range types.
5 : : *
6 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/utils/adt/rangetypes_gist.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include "access/gist.h"
18 : : #include "access/stratnum.h"
19 : : #include "utils/datum.h"
20 : : #include "utils/float.h"
21 : : #include "utils/fmgrprotos.h"
22 : : #include "utils/multirangetypes.h"
23 : : #include "utils/rangetypes.h"
24 : :
25 : : /*
26 : : * Range class properties used to segregate different classes of ranges in
27 : : * GiST. Each unique combination of properties is a class. CLS_EMPTY cannot
28 : : * be combined with anything else.
29 : : */
30 : : #define CLS_NORMAL 0 /* Ordinary finite range (no bits set) */
31 : : #define CLS_LOWER_INF 1 /* Lower bound is infinity */
32 : : #define CLS_UPPER_INF 2 /* Upper bound is infinity */
33 : : #define CLS_CONTAIN_EMPTY 4 /* Contains underlying empty ranges */
34 : : #define CLS_EMPTY 8 /* Special class for empty ranges */
35 : :
36 : : #define CLS_COUNT 9 /* # of classes; includes all combinations of
37 : : * properties. CLS_EMPTY doesn't combine with
38 : : * anything else, so it's only 2^3 + 1. */
39 : :
40 : : /*
41 : : * Minimum accepted ratio of split for items of the same class. If the items
42 : : * are of different classes, we will separate along those lines regardless of
43 : : * the ratio.
44 : : */
45 : : #define LIMIT_RATIO 0.3
46 : :
47 : : /* Constants for fixed penalty values */
48 : : #define INFINITE_BOUND_PENALTY 2.0
49 : : #define CONTAIN_EMPTY_PENALTY 1.0
50 : : #define DEFAULT_SUBTYPE_DIFF_PENALTY 1.0
51 : :
52 : : /*
53 : : * Per-item data for range_gist_single_sorting_split.
54 : : */
55 : : typedef struct
56 : : {
57 : : int index;
58 : : RangeBound bound;
59 : : } SingleBoundSortItem;
60 : :
61 : : /* place on left or right side of split? */
62 : : typedef enum
63 : : {
64 : : SPLIT_LEFT = 0, /* makes initialization to SPLIT_LEFT easier */
65 : : SPLIT_RIGHT,
66 : : } SplitLR;
67 : :
68 : : /*
69 : : * Context for range_gist_consider_split.
70 : : */
71 : : typedef struct
72 : : {
73 : : TypeCacheEntry *typcache; /* typcache for range type */
74 : : bool has_subtype_diff; /* does it have subtype_diff? */
75 : : int entries_count; /* total number of entries being split */
76 : :
77 : : /* Information about currently selected split follows */
78 : :
79 : : bool first; /* true if no split was selected yet */
80 : :
81 : : RangeBound *left_upper; /* upper bound of left interval */
82 : : RangeBound *right_lower; /* lower bound of right interval */
83 : :
84 : : float4 ratio; /* split ratio */
85 : : float4 overlap; /* overlap between left and right predicate */
86 : : int common_left; /* # common entries destined for each side */
87 : : int common_right;
88 : : } ConsiderSplitContext;
89 : :
90 : : /*
91 : : * Bounds extracted from a non-empty range, for use in
92 : : * range_gist_double_sorting_split.
93 : : */
94 : : typedef struct
95 : : {
96 : : RangeBound lower;
97 : : RangeBound upper;
98 : : } NonEmptyRange;
99 : :
100 : : /*
101 : : * Represents information about an entry that can be placed in either group
102 : : * without affecting overlap over selected axis ("common entry").
103 : : */
104 : : typedef struct
105 : : {
106 : : /* Index of entry in the initial array */
107 : : int index;
108 : : /* Delta between closeness of range to each of the two groups */
109 : : double delta;
110 : : } CommonEntry;
111 : :
112 : : /* Helper macros to place an entry in the left or right group during split */
113 : : /* Note direct access to variables v, typcache, left_range, right_range */
114 : : #define PLACE_LEFT(range, off) \
115 : : do { \
116 : : if (v->spl_nleft > 0) \
117 : : left_range = range_super_union(typcache, left_range, range); \
118 : : else \
119 : : left_range = (range); \
120 : : v->spl_left[v->spl_nleft++] = (off); \
121 : : } while(0)
122 : :
123 : : #define PLACE_RIGHT(range, off) \
124 : : do { \
125 : : if (v->spl_nright > 0) \
126 : : right_range = range_super_union(typcache, right_range, range); \
127 : : else \
128 : : right_range = (range); \
129 : : v->spl_right[v->spl_nright++] = (off); \
130 : : } while(0)
131 : :
132 : : /* Copy a RangeType datum (hardwires typbyval and typlen for ranges...) */
133 : : #define rangeCopy(r) \
134 : : ((RangeType *) DatumGetPointer(datumCopy(PointerGetDatum(r), \
135 : : false, -1)))
136 : :
137 : : static RangeType *range_super_union(TypeCacheEntry *typcache, RangeType *r1,
138 : : RangeType *r2);
139 : : static bool range_gist_consistent_int_range(TypeCacheEntry *typcache,
140 : : StrategyNumber strategy,
141 : : const RangeType *key,
142 : : const RangeType *query);
143 : : static bool range_gist_consistent_int_multirange(TypeCacheEntry *typcache,
144 : : StrategyNumber strategy,
145 : : const RangeType *key,
146 : : const MultirangeType *query);
147 : : static bool range_gist_consistent_int_element(TypeCacheEntry *typcache,
148 : : StrategyNumber strategy,
149 : : const RangeType *key,
150 : : Datum query);
151 : : static bool range_gist_consistent_leaf_range(TypeCacheEntry *typcache,
152 : : StrategyNumber strategy,
153 : : const RangeType *key,
154 : : const RangeType *query);
155 : : static bool range_gist_consistent_leaf_multirange(TypeCacheEntry *typcache,
156 : : StrategyNumber strategy,
157 : : const RangeType *key,
158 : : const MultirangeType *query);
159 : : static bool range_gist_consistent_leaf_element(TypeCacheEntry *typcache,
160 : : StrategyNumber strategy,
161 : : const RangeType *key,
162 : : Datum query);
163 : : static void range_gist_fallback_split(TypeCacheEntry *typcache,
164 : : GistEntryVector *entryvec,
165 : : GIST_SPLITVEC *v);
166 : : static void range_gist_class_split(TypeCacheEntry *typcache,
167 : : GistEntryVector *entryvec,
168 : : GIST_SPLITVEC *v,
169 : : SplitLR *classes_groups);
170 : : static void range_gist_single_sorting_split(TypeCacheEntry *typcache,
171 : : GistEntryVector *entryvec,
172 : : GIST_SPLITVEC *v,
173 : : bool use_upper_bound);
174 : : static void range_gist_double_sorting_split(TypeCacheEntry *typcache,
175 : : GistEntryVector *entryvec,
176 : : GIST_SPLITVEC *v);
177 : : static void range_gist_consider_split(ConsiderSplitContext *context,
178 : : RangeBound *right_lower, int min_left_count,
179 : : RangeBound *left_upper, int max_left_count);
180 : : static int get_gist_range_class(RangeType *range);
181 : : static int single_bound_cmp(const void *a, const void *b, void *arg);
182 : : static int interval_cmp_lower(const void *a, const void *b, void *arg);
183 : : static int interval_cmp_upper(const void *a, const void *b, void *arg);
184 : : static int common_entry_cmp(const void *i1, const void *i2);
185 : : static float8 call_subtype_diff(TypeCacheEntry *typcache,
186 : : Datum val1, Datum val2);
187 : :
188 : :
189 : : /* GiST query consistency check */
190 : : Datum
5158 heikki.linnakangas@i 191 :CBC 320851 : range_gist_consistent(PG_FUNCTION_ARGS)
192 : : {
5147 bruce@momjian.us 193 : 320851 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
5139 tgl@sss.pgh.pa.us 194 : 320851 : Datum query = PG_GETARG_DATUM(1);
5147 bruce@momjian.us 195 : 320851 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
196 : : bool result;
1814 akorotkov@postgresql 197 : 320851 : Oid subtype = PG_GETARG_OID(3);
5147 bruce@momjian.us 198 : 320851 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
3012 tgl@sss.pgh.pa.us 199 : 320851 : RangeType *key = DatumGetRangeTypeP(entry->key);
200 : : TypeCacheEntry *typcache;
201 : :
202 : : /* All operators served by this function are exact */
5158 heikki.linnakangas@i 203 : 320851 : *recheck = false;
204 : :
4900 205 : 320851 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
206 : :
207 : : /*
208 : : * Perform consistent checking using function corresponding to key type
209 : : * (leaf or internal) and query subtype (range, multirange, or element).
210 : : * Note that invalid subtype means that query type matches key type
211 : : * (range).
212 : : */
5158 213 [ + + ]: 320851 : if (GIST_LEAF(entry))
214 : : {
1814 akorotkov@postgresql 215 [ + + + + ]: 317311 : if (!OidIsValid(subtype) || subtype == ANYRANGEOID)
216 : 162404 : result = range_gist_consistent_leaf_range(typcache, strategy, key,
217 : 162404 : DatumGetRangeTypeP(query));
218 [ + + ]: 154907 : else if (subtype == ANYMULTIRANGEOID)
219 : 151331 : result = range_gist_consistent_leaf_multirange(typcache, strategy, key,
220 : 151331 : DatumGetMultirangeTypeP(query));
221 : : else
222 : 3576 : result = range_gist_consistent_leaf_element(typcache, strategy,
223 : : key, query);
224 : : }
225 : : else
226 : : {
227 [ + - + + ]: 3540 : if (!OidIsValid(subtype) || subtype == ANYRANGEOID)
228 : 1770 : result = range_gist_consistent_int_range(typcache, strategy, key,
229 : 1770 : DatumGetRangeTypeP(query));
230 [ + + ]: 1770 : else if (subtype == ANYMULTIRANGEOID)
231 : 1593 : result = range_gist_consistent_int_multirange(typcache, strategy, key,
232 : 1593 : DatumGetMultirangeTypeP(query));
233 : : else
234 : 177 : result = range_gist_consistent_int_element(typcache, strategy,
235 : : key, query);
236 : : }
237 : 320851 : PG_RETURN_BOOL(result);
238 : : }
239 : :
240 : : /*
241 : : * GiST compress method for multiranges: multirange is approximated as union
242 : : * range with no gaps.
243 : : */
244 : : Datum
245 : 20195 : multirange_gist_compress(PG_FUNCTION_ARGS)
246 : : {
247 : 20195 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
248 : :
249 [ + + ]: 20195 : if (entry->leafkey)
250 : : {
251 : 11553 : MultirangeType *mr = DatumGetMultirangeTypeP(entry->key);
252 : : RangeType *r;
253 : : TypeCacheEntry *typcache;
7 michael@paquier.xyz 254 :GNC 11553 : GISTENTRY *retval = palloc_object(GISTENTRY);
255 : :
1814 akorotkov@postgresql 256 :CBC 11553 : typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
257 : 11553 : r = multirange_get_union_range(typcache->rngtype, mr);
258 : :
259 : 11553 : gistentryinit(*retval, RangeTypePGetDatum(r),
260 : : entry->rel, entry->page, entry->offset, false);
261 : :
262 : 11553 : PG_RETURN_POINTER(retval);
263 : : }
264 : :
265 : 8642 : PG_RETURN_POINTER(entry);
266 : : }
267 : :
268 : : /* GiST query consistency check for multiranges */
269 : : Datum
270 : 137105 : multirange_gist_consistent(PG_FUNCTION_ARGS)
271 : : {
272 : 137105 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
273 : 137105 : Datum query = PG_GETARG_DATUM(1);
274 : 137105 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
275 : : bool result;
276 : 137105 : Oid subtype = PG_GETARG_OID(3);
277 : 137105 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
278 : 137105 : RangeType *key = DatumGetRangeTypeP(entry->key);
279 : : TypeCacheEntry *typcache;
280 : :
281 : : /*
282 : : * All operators served by this function are inexact because multirange is
283 : : * approximated by union range with no gaps.
284 : : */
285 : 137105 : *recheck = true;
286 : :
287 : 137105 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(key));
288 : :
289 : : /*
290 : : * Perform consistent checking using function corresponding to key type
291 : : * (leaf or internal) and query subtype (range, multirange, or element).
292 : : * Note that invalid subtype means that query type matches key type
293 : : * (multirange).
294 : : */
295 [ + + ]: 137105 : if (GIST_LEAF(entry))
296 : : {
297 [ + + + + ]: 133989 : if (!OidIsValid(subtype) || subtype == ANYMULTIRANGEOID)
298 : 74016 : result = range_gist_consistent_leaf_multirange(typcache, strategy, key,
299 : 74016 : DatumGetMultirangeTypeP(query));
300 [ + + ]: 59973 : else if (subtype == ANYRANGEOID)
301 : 58591 : result = range_gist_consistent_leaf_range(typcache, strategy, key,
302 : 58591 : DatumGetRangeTypeP(query));
303 : : else
304 : 1382 : result = range_gist_consistent_leaf_element(typcache, strategy,
305 : : key, query);
306 : : }
307 : : else
308 : : {
309 [ + - + + ]: 3116 : if (!OidIsValid(subtype) || subtype == ANYMULTIRANGEOID)
310 : 1640 : result = range_gist_consistent_int_multirange(typcache, strategy, key,
311 : 1640 : DatumGetMultirangeTypeP(query));
312 [ + + ]: 1476 : else if (subtype == ANYRANGEOID)
313 : 1394 : result = range_gist_consistent_int_range(typcache, strategy, key,
314 : 1394 : DatumGetRangeTypeP(query));
315 : : else
316 : 82 : result = range_gist_consistent_int_element(typcache, strategy,
317 : : key, query);
318 : : }
319 : 137105 : PG_RETURN_BOOL(result);
320 : : }
321 : :
322 : : /* form union range */
323 : : Datum
5158 heikki.linnakangas@i 324 : 28149 : range_gist_union(PG_FUNCTION_ARGS)
325 : : {
5147 bruce@momjian.us 326 : 28149 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
327 : 28149 : GISTENTRY *ent = entryvec->vector;
328 : : RangeType *result_range;
329 : : TypeCacheEntry *typcache;
330 : : int i;
331 : :
3012 tgl@sss.pgh.pa.us 332 : 28149 : result_range = DatumGetRangeTypeP(ent[0].key);
333 : :
5146 334 : 28149 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(result_range));
335 : :
5158 heikki.linnakangas@i 336 [ + + ]: 83862 : for (i = 1; i < entryvec->n; i++)
337 : : {
5146 tgl@sss.pgh.pa.us 338 : 55713 : result_range = range_super_union(typcache, result_range,
3012 339 : 55713 : DatumGetRangeTypeP(ent[i].key));
340 : : }
341 : :
342 : 28149 : PG_RETURN_RANGE_P(result_range);
343 : : }
344 : :
345 : : /*
346 : : * We store ranges as ranges in GiST indexes, so we do not need
347 : : * compress, decompress, or fetch functions. Note this implies a limit
348 : : * on the size of range values that can be indexed.
349 : : */
350 : :
351 : : /*
352 : : * GiST page split penalty function.
353 : : *
354 : : * The penalty function has the following goals (in order from most to least
355 : : * important):
356 : : * - Keep normal ranges separate
357 : : * - Avoid broadening the class of the original predicate
358 : : * - Avoid broadening (as determined by subtype_diff) the original predicate
359 : : * - Favor adding ranges to narrower original predicates
360 : : */
361 : : Datum
5158 heikki.linnakangas@i 362 : 370542 : range_gist_penalty(PG_FUNCTION_ARGS)
363 : : {
5147 bruce@momjian.us 364 : 370542 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
365 : 370542 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
366 : 370542 : float *penalty = (float *) PG_GETARG_POINTER(2);
3012 tgl@sss.pgh.pa.us 367 : 370542 : RangeType *orig = DatumGetRangeTypeP(origentry->key);
368 : 370542 : RangeType *new = DatumGetRangeTypeP(newentry->key);
369 : : TypeCacheEntry *typcache;
370 : : bool has_subtype_diff;
371 : : RangeBound orig_lower,
372 : : new_lower,
373 : : orig_upper,
374 : : new_upper;
375 : : bool orig_empty,
376 : : new_empty;
377 : :
5146 378 [ - + ]: 370542 : if (RangeTypeGetOid(orig) != RangeTypeGetOid(new))
5146 tgl@sss.pgh.pa.us 379 [ # # ]:UBC 0 : elog(ERROR, "range types do not match");
380 : :
5146 tgl@sss.pgh.pa.us 381 :CBC 370542 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(orig));
382 : :
5036 383 : 370542 : has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
384 : :
385 : 370542 : range_deserialize(typcache, orig, &orig_lower, &orig_upper, &orig_empty);
386 : 370542 : range_deserialize(typcache, new, &new_lower, &new_upper, &new_empty);
387 : :
388 : : /*
389 : : * Distinct branches for handling distinct classes of ranges. Note that
390 : : * penalty values only need to be commensurate within the same class of
391 : : * new range.
392 : : */
393 [ + + ]: 370542 : if (new_empty)
394 : : {
395 : : /* Handle insertion of empty range */
396 [ + + ]: 70223 : if (orig_empty)
397 : : {
398 : : /*
399 : : * The best case is to insert it to empty original range.
400 : : * Insertion here means no broadening of original range. Also
401 : : * original range is the most narrow.
402 : : */
403 : 4668 : *penalty = 0.0;
404 : : }
405 [ + + ]: 65555 : else if (RangeIsOrContainsEmpty(orig))
406 : : {
407 : : /*
408 : : * The second case is to insert empty range into range which
409 : : * contains at least one underlying empty range. There is still
410 : : * no broadening of original range, but original range is not as
411 : : * narrow as possible.
412 : : */
413 : 1158 : *penalty = CONTAIN_EMPTY_PENALTY;
414 : : }
415 [ - + - - ]: 64397 : else if (orig_lower.infinite && orig_upper.infinite)
416 : : {
417 : : /*
418 : : * Original range requires broadening. (-inf; +inf) is most far
419 : : * from normal range in this case.
420 : : */
5036 tgl@sss.pgh.pa.us 421 :UBC 0 : *penalty = 2 * CONTAIN_EMPTY_PENALTY;
422 : : }
5036 tgl@sss.pgh.pa.us 423 [ + - - + ]:CBC 64397 : else if (orig_lower.infinite || orig_upper.infinite)
424 : : {
425 : : /*
426 : : * (-inf, x) or (x, +inf) original ranges are closer to normal
427 : : * ranges, so it's worse to mix it with empty ranges.
428 : : */
5036 tgl@sss.pgh.pa.us 429 :UBC 0 : *penalty = 3 * CONTAIN_EMPTY_PENALTY;
430 : : }
431 : : else
432 : : {
433 : : /*
434 : : * The least preferred case is broadening of normal range.
435 : : */
5036 tgl@sss.pgh.pa.us 436 :CBC 64397 : *penalty = 4 * CONTAIN_EMPTY_PENALTY;
437 : : }
438 : : }
439 [ + + - + ]: 300319 : else if (new_lower.infinite && new_upper.infinite)
440 : : {
441 : : /* Handle insertion of (-inf, +inf) range */
5036 tgl@sss.pgh.pa.us 442 [ # # # # ]:UBC 0 : if (orig_lower.infinite && orig_upper.infinite)
443 : : {
444 : : /*
445 : : * Best case is inserting to (-inf, +inf) original range.
446 : : */
447 : 0 : *penalty = 0.0;
448 : : }
449 [ # # # # ]: 0 : else if (orig_lower.infinite || orig_upper.infinite)
450 : : {
451 : : /*
452 : : * When original range is (-inf, x) or (x, +inf) it requires
453 : : * broadening of original range (extension of one bound to
454 : : * infinity).
455 : : */
456 : 0 : *penalty = INFINITE_BOUND_PENALTY;
457 : : }
458 : : else
459 : : {
460 : : /*
461 : : * Insertion to normal original range is least preferred.
462 : : */
463 : 0 : *penalty = 2 * INFINITE_BOUND_PENALTY;
464 : : }
465 : :
466 [ # # ]: 0 : if (RangeIsOrContainsEmpty(orig))
467 : : {
468 : : /*
469 : : * Original range is narrower when it doesn't contain empty
470 : : * ranges. Add additional penalty otherwise.
471 : : */
472 : 0 : *penalty += CONTAIN_EMPTY_PENALTY;
473 : : }
474 : : }
5036 tgl@sss.pgh.pa.us 475 [ + + ]:CBC 300319 : else if (new_lower.infinite)
476 : : {
477 : : /* Handle insertion of (-inf, x) range */
478 [ + + + + ]: 13187 : if (!orig_empty && orig_lower.infinite)
479 : : {
480 [ - + ]: 594 : if (orig_upper.infinite)
481 : : {
482 : : /*
483 : : * (-inf, +inf) range won't be extended by insertion of (-inf,
484 : : * x) range. It's a less desirable case than insertion to
485 : : * (-inf, y) original range without extension, because in that
486 : : * case original range is narrower. But we can't express that
487 : : * in single float value.
488 : : */
5036 tgl@sss.pgh.pa.us 489 :UBC 0 : *penalty = 0.0;
490 : : }
491 : : else
492 : : {
5036 tgl@sss.pgh.pa.us 493 [ + + ]:CBC 594 : if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
494 : : {
495 : : /*
496 : : * Get extension of original range using subtype_diff. Use
497 : : * constant if subtype_diff unavailable.
498 : : */
499 [ + - ]: 387 : if (has_subtype_diff)
500 : 387 : *penalty = call_subtype_diff(typcache,
501 : : new_upper.val,
502 : : orig_upper.val);
503 : : else
5036 tgl@sss.pgh.pa.us 504 :UBC 0 : *penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
505 : : }
506 : : else
507 : : {
508 : : /* No extension of original range */
5036 tgl@sss.pgh.pa.us 509 :CBC 207 : *penalty = 0.0;
510 : : }
511 : : }
512 : : }
513 : : else
514 : : {
515 : : /*
516 : : * If lower bound of original range is not -inf, then extension of
517 : : * it is infinity.
518 : : */
519 : 12593 : *penalty = get_float4_infinity();
520 : : }
521 : : }
522 [ + + ]: 287132 : else if (new_upper.infinite)
523 : : {
524 : : /* Handle insertion of (x, +inf) range */
525 [ + + + + ]: 9697 : if (!orig_empty && orig_upper.infinite)
526 : : {
527 [ + + ]: 594 : if (orig_lower.infinite)
528 : : {
529 : : /*
530 : : * (-inf, +inf) range won't be extended by insertion of (x,
531 : : * +inf) range. It's a less desirable case than insertion to
532 : : * (y, +inf) original range without extension, because in that
533 : : * case original range is narrower. But we can't express that
534 : : * in single float value.
535 : : */
536 : 99 : *penalty = 0.0;
537 : : }
538 : : else
539 : : {
540 [ - + ]: 495 : if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
541 : : {
542 : : /*
543 : : * Get extension of original range using subtype_diff. Use
544 : : * constant if subtype_diff unavailable.
545 : : */
5036 tgl@sss.pgh.pa.us 546 [ # # ]:UBC 0 : if (has_subtype_diff)
547 : 0 : *penalty = call_subtype_diff(typcache,
548 : : orig_lower.val,
549 : : new_lower.val);
550 : : else
551 : 0 : *penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
552 : : }
553 : : else
554 : : {
555 : : /* No extension of original range */
5036 tgl@sss.pgh.pa.us 556 :CBC 495 : *penalty = 0.0;
557 : : }
558 : : }
559 : : }
560 : : else
561 : : {
562 : : /*
563 : : * If upper bound of original range is not +inf, then extension of
564 : : * it is infinity.
565 : : */
566 : 9103 : *penalty = get_float4_infinity();
567 : : }
568 : : }
569 : : else
570 : : {
571 : : /* Handle insertion of normal (non-empty, non-infinite) range */
572 [ + + + + : 277435 : if (orig_empty || orig_lower.infinite || orig_upper.infinite)
+ + ]
573 : : {
574 : : /*
575 : : * Avoid mixing normal ranges with infinite and empty ranges.
576 : : */
577 : 27033 : *penalty = get_float4_infinity();
578 : : }
579 : : else
580 : : {
581 : : /*
582 : : * Calculate extension of original range by calling subtype_diff.
583 : : * Use constant if subtype_diff unavailable.
584 : : */
585 : 250402 : float8 diff = 0.0;
586 : :
587 [ + + ]: 250402 : if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
588 : : {
589 [ + - ]: 81754 : if (has_subtype_diff)
590 : 81754 : diff += call_subtype_diff(typcache,
591 : : orig_lower.val,
592 : : new_lower.val);
593 : : else
5036 tgl@sss.pgh.pa.us 594 :UBC 0 : diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
595 : : }
5036 tgl@sss.pgh.pa.us 596 [ + + ]:CBC 250402 : if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
597 : : {
598 [ + - ]: 215951 : if (has_subtype_diff)
599 : 215951 : diff += call_subtype_diff(typcache,
600 : : new_upper.val,
601 : : orig_upper.val);
602 : : else
5036 tgl@sss.pgh.pa.us 603 :UBC 0 : diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
604 : : }
5036 tgl@sss.pgh.pa.us 605 :CBC 250402 : *penalty = diff;
606 : : }
607 : : }
608 : :
5158 heikki.linnakangas@i 609 : 370542 : PG_RETURN_POINTER(penalty);
610 : : }
611 : :
612 : : /*
613 : : * The GiST PickSplit method for ranges
614 : : *
615 : : * Primarily, we try to segregate ranges of different classes. If splitting
616 : : * ranges of the same class, use the appropriate split method for that class.
617 : : */
618 : : Datum
619 : 235 : range_gist_picksplit(PG_FUNCTION_ARGS)
620 : : {
5147 bruce@momjian.us 621 : 235 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
622 : 235 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
623 : : TypeCacheEntry *typcache;
624 : : OffsetNumber i;
625 : : RangeType *pred_left;
626 : : int nbytes;
627 : : OffsetNumber maxoff;
628 : : int count_in_classes[CLS_COUNT];
629 : : int j;
5036 tgl@sss.pgh.pa.us 630 : 235 : int non_empty_classes_count = 0;
631 : 235 : int biggest_class = -1;
632 : 235 : int biggest_class_count = 0;
633 : : int total_count;
634 : :
635 : : /* use first item to look up range type's info */
3012 636 : 235 : pred_left = DatumGetRangeTypeP(entryvec->vector[FirstOffsetNumber].key);
5146 637 : 235 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(pred_left));
638 : :
5158 heikki.linnakangas@i 639 : 235 : maxoff = entryvec->n - 1;
640 : 235 : nbytes = (maxoff + 1) * sizeof(OffsetNumber);
641 : 235 : v->spl_left = (OffsetNumber *) palloc(nbytes);
642 : 235 : v->spl_right = (OffsetNumber *) palloc(nbytes);
643 : :
644 : : /*
645 : : * Get count distribution of range classes.
646 : : */
5036 tgl@sss.pgh.pa.us 647 : 235 : memset(count_in_classes, 0, sizeof(count_in_classes));
5158 heikki.linnakangas@i 648 [ + + ]: 102353 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
649 : : {
3012 tgl@sss.pgh.pa.us 650 : 102118 : RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
651 : :
5036 652 : 102118 : count_in_classes[get_gist_range_class(range)]++;
653 : : }
654 : :
655 : : /*
656 : : * Count non-empty classes and find biggest class.
657 : : */
658 : 235 : total_count = maxoff;
659 [ + + ]: 2350 : for (j = 0; j < CLS_COUNT; j++)
660 : : {
661 [ + + ]: 2115 : if (count_in_classes[j] > 0)
662 : : {
663 [ + + ]: 267 : if (count_in_classes[j] > biggest_class_count)
664 : : {
665 : 247 : biggest_class_count = count_in_classes[j];
666 : 247 : biggest_class = j;
667 : : }
668 : 267 : non_empty_classes_count++;
669 : : }
670 : : }
671 : :
672 [ - + ]: 235 : Assert(non_empty_classes_count > 0);
673 : :
674 [ + + ]: 235 : if (non_empty_classes_count == 1)
675 : : {
676 : : /* One non-empty class, so split inside class */
677 [ + + ]: 213 : if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_NORMAL)
678 : : {
679 : : /* double sorting split for normal ranges */
680 : 192 : range_gist_double_sorting_split(typcache, entryvec, v);
681 : : }
682 [ - + ]: 21 : else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_LOWER_INF)
683 : : {
684 : : /* upper bound sorting split for (-inf, x) ranges */
5036 tgl@sss.pgh.pa.us 685 :UBC 0 : range_gist_single_sorting_split(typcache, entryvec, v, true);
686 : : }
5036 tgl@sss.pgh.pa.us 687 [ - + ]:CBC 21 : else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_UPPER_INF)
688 : : {
689 : : /* lower bound sorting split for (x, +inf) ranges */
5036 tgl@sss.pgh.pa.us 690 :UBC 0 : range_gist_single_sorting_split(typcache, entryvec, v, false);
691 : : }
692 : : else
693 : : {
694 : : /* trivial split for all (-inf, +inf) or all empty ranges */
5036 tgl@sss.pgh.pa.us 695 :CBC 21 : range_gist_fallback_split(typcache, entryvec, v);
696 : : }
697 : : }
698 : : else
699 : : {
700 : : /*
701 : : * Class based split.
702 : : *
703 : : * To which side of the split should each class go? Initialize them
704 : : * all to go to the left side.
705 : : */
706 : : SplitLR classes_groups[CLS_COUNT];
707 : :
708 : 22 : memset(classes_groups, 0, sizeof(classes_groups));
709 : :
710 [ + + ]: 22 : if (count_in_classes[CLS_NORMAL] > 0)
711 : : {
712 : : /* separate normal ranges if any */
713 : 19 : classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
714 : : }
715 : : else
716 : : {
717 : : /*----------
718 : : * Try to split classes in one of two ways:
719 : : * 1) containing infinities - not containing infinities
720 : : * 2) containing empty - not containing empty
721 : : *
722 : : * Select the way which balances the ranges between left and right
723 : : * the best. If split in these ways is not possible, there are at
724 : : * most 3 classes, so just separate biggest class.
725 : : *----------
726 : : */
727 : : int infCount,
728 : : nonInfCount;
729 : : int emptyCount,
730 : : nonEmptyCount;
731 : :
732 : 3 : nonInfCount =
733 : 3 : count_in_classes[CLS_NORMAL] +
734 : 3 : count_in_classes[CLS_CONTAIN_EMPTY] +
735 : 3 : count_in_classes[CLS_EMPTY];
736 : 3 : infCount = total_count - nonInfCount;
737 : :
738 : 3 : nonEmptyCount =
4938 bruce@momjian.us 739 : 3 : count_in_classes[CLS_NORMAL] +
5036 tgl@sss.pgh.pa.us 740 : 3 : count_in_classes[CLS_LOWER_INF] +
741 : 3 : count_in_classes[CLS_UPPER_INF] +
742 : 3 : count_in_classes[CLS_LOWER_INF | CLS_UPPER_INF];
743 : 3 : emptyCount = total_count - nonEmptyCount;
744 : :
745 [ + - + - ]: 3 : if (infCount > 0 && nonInfCount > 0 &&
1167 peter@eisentraut.org 746 : 3 : (abs(infCount - nonInfCount) <=
747 [ + - ]: 3 : abs(emptyCount - nonEmptyCount)))
748 : : {
4938 bruce@momjian.us 749 : 3 : classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
5036 tgl@sss.pgh.pa.us 750 : 3 : classes_groups[CLS_CONTAIN_EMPTY] = SPLIT_RIGHT;
4938 bruce@momjian.us 751 : 3 : classes_groups[CLS_EMPTY] = SPLIT_RIGHT;
752 : : }
5036 tgl@sss.pgh.pa.us 753 [ # # # # ]:UBC 0 : else if (emptyCount > 0 && nonEmptyCount > 0)
754 : : {
4938 bruce@momjian.us 755 : 0 : classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
756 : 0 : classes_groups[CLS_LOWER_INF] = SPLIT_RIGHT;
757 : 0 : classes_groups[CLS_UPPER_INF] = SPLIT_RIGHT;
5036 tgl@sss.pgh.pa.us 758 : 0 : classes_groups[CLS_LOWER_INF | CLS_UPPER_INF] = SPLIT_RIGHT;
759 : : }
760 : : else
761 : : {
762 : : /*
763 : : * Either total_count == emptyCount or total_count ==
764 : : * infCount.
765 : : */
766 : 0 : classes_groups[biggest_class] = SPLIT_RIGHT;
767 : : }
768 : : }
769 : :
5036 tgl@sss.pgh.pa.us 770 :CBC 22 : range_gist_class_split(typcache, entryvec, v, classes_groups);
771 : : }
772 : :
5158 heikki.linnakangas@i 773 : 235 : PG_RETURN_POINTER(v);
774 : : }
775 : :
776 : : /* equality comparator for GiST */
777 : : Datum
778 : 28038 : range_gist_same(PG_FUNCTION_ARGS)
779 : : {
3012 tgl@sss.pgh.pa.us 780 : 28038 : RangeType *r1 = PG_GETARG_RANGE_P(0);
781 : 28038 : RangeType *r2 = PG_GETARG_RANGE_P(1);
5147 bruce@momjian.us 782 : 28038 : bool *result = (bool *) PG_GETARG_POINTER(2);
783 : :
784 : : /*
785 : : * range_eq will ignore the RANGE_CONTAIN_EMPTY flag, so we have to check
786 : : * that for ourselves. More generally, if the entries have been properly
787 : : * normalized, then unequal flags bytes must mean unequal ranges ... so
788 : : * let's just test all the flag bits at once.
789 : : */
5134 tgl@sss.pgh.pa.us 790 [ + + ]: 28038 : if (range_get_flags(r1) != range_get_flags(r2))
791 : 18 : *result = false;
792 : : else
793 : : {
794 : : TypeCacheEntry *typcache;
795 : :
4900 heikki.linnakangas@i 796 : 28020 : typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
797 : :
798 : 28020 : *result = range_eq_internal(typcache, r1, r2);
799 : : }
800 : :
5158 801 : 28038 : PG_RETURN_POINTER(result);
802 : : }
803 : :
804 : : /*
805 : : *----------------------------------------------------------
806 : : * STATIC FUNCTIONS
807 : : *----------------------------------------------------------
808 : : */
809 : :
810 : : /*
811 : : * Return the smallest range that contains r1 and r2
812 : : *
813 : : * This differs from regular range_union in two critical ways:
814 : : * 1. It won't throw an error for non-adjacent r1 and r2, but just absorb
815 : : * the intervening values into the result range.
816 : : * 2. We track whether any empty range has been union'd into the result,
817 : : * so that contained_by searches can be indexed. Note that this means
818 : : * that *all* unions formed within the GiST index must go through here.
819 : : */
820 : : static RangeType *
4938 bruce@momjian.us 821 : 157415 : range_super_union(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
822 : : {
823 : : RangeType *result;
824 : : RangeBound lower1,
825 : : lower2;
826 : : RangeBound upper1,
827 : : upper2;
828 : : bool empty1,
829 : : empty2;
830 : : char flags1,
831 : : flags2;
832 : : RangeBound *result_lower;
833 : : RangeBound *result_upper;
834 : :
5146 tgl@sss.pgh.pa.us 835 : 157415 : range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
836 : 157415 : range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
5134 837 : 157415 : flags1 = range_get_flags(r1);
838 : 157415 : flags2 = range_get_flags(r2);
839 : :
5158 heikki.linnakangas@i 840 [ + + ]: 157415 : if (empty1)
841 : : {
842 : : /* We can return r2 as-is if it already is or contains empty */
5134 tgl@sss.pgh.pa.us 843 [ + + ]: 21222 : if (flags2 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
844 : 21219 : return r2;
845 : : /* Else we'd better copy it (modify-in-place isn't safe) */
846 : 3 : r2 = rangeCopy(r2);
847 : 3 : range_set_contain_empty(r2);
5158 heikki.linnakangas@i 848 : 3 : return r2;
849 : : }
850 [ + + ]: 136193 : if (empty2)
851 : : {
852 : : /* We can return r1 as-is if it already is or contains empty */
5134 tgl@sss.pgh.pa.us 853 [ + + ]: 1164 : if (flags1 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
854 : 1158 : return r1;
855 : : /* Else we'd better copy it (modify-in-place isn't safe) */
856 : 6 : r1 = rangeCopy(r1);
857 : 6 : range_set_contain_empty(r1);
5158 heikki.linnakangas@i 858 : 6 : return r1;
859 : : }
860 : :
5146 tgl@sss.pgh.pa.us 861 [ + + ]: 135029 : if (range_cmp_bounds(typcache, &lower1, &lower2) <= 0)
5158 heikki.linnakangas@i 862 : 134990 : result_lower = &lower1;
863 : : else
864 : 39 : result_lower = &lower2;
865 : :
5146 tgl@sss.pgh.pa.us 866 [ + + ]: 135029 : if (range_cmp_bounds(typcache, &upper1, &upper2) >= 0)
5158 heikki.linnakangas@i 867 : 52020 : result_upper = &upper1;
868 : : else
869 : 83009 : result_upper = &upper2;
870 : :
871 : : /* optimization to avoid constructing a new range */
5134 tgl@sss.pgh.pa.us 872 [ + + + + : 135029 : if (result_lower == &lower1 && result_upper == &upper1 &&
+ + ]
873 [ + - ]: 51984 : ((flags1 & RANGE_CONTAIN_EMPTY) || !(flags2 & RANGE_CONTAIN_EMPTY)))
5158 heikki.linnakangas@i 874 : 52014 : return r1;
5134 tgl@sss.pgh.pa.us 875 [ + + + + : 83015 : if (result_lower == &lower2 && result_upper == &upper2 &&
+ - ]
876 [ + - ]: 33 : ((flags2 & RANGE_CONTAIN_EMPTY) || !(flags1 & RANGE_CONTAIN_EMPTY)))
5158 heikki.linnakangas@i 877 : 33 : return r2;
878 : :
1098 tgl@sss.pgh.pa.us 879 : 82982 : result = make_range(typcache, result_lower, result_upper, false, NULL);
880 : :
5134 881 [ + + - + ]: 82982 : if ((flags1 & RANGE_CONTAIN_EMPTY) || (flags2 & RANGE_CONTAIN_EMPTY))
882 : 300 : range_set_contain_empty(result);
883 : :
884 : 82982 : return result;
885 : : }
886 : :
887 : : static bool
1814 akorotkov@postgresql 888 : 2969 : multirange_union_range_equal(TypeCacheEntry *typcache,
889 : : const RangeType *r,
890 : : const MultirangeType *mr)
891 : : {
892 : : RangeBound lower1,
893 : : upper1,
894 : : lower2,
895 : : upper2,
896 : : tmp;
897 : : bool empty;
898 : :
899 [ + + - + ]: 2969 : if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
900 [ + - + - ]: 1500 : return (RangeIsEmpty(r) && MultirangeIsEmpty(mr));
901 : :
902 : 1469 : range_deserialize(typcache, r, &lower1, &upper1, &empty);
903 [ - + ]: 1469 : Assert(!empty);
904 : 1469 : multirange_get_bounds(typcache, mr, 0, &lower2, &tmp);
905 : 1469 : multirange_get_bounds(typcache, mr, mr->rangeCount - 1, &tmp, &upper2);
906 : :
907 [ + + + + ]: 1523 : return (range_cmp_bounds(typcache, &lower1, &lower2) == 0 &&
908 : 54 : range_cmp_bounds(typcache, &upper1, &upper2) == 0);
909 : : }
910 : :
911 : : /*
912 : : * GiST consistent test on an index internal page with range query
913 : : */
914 : : static bool
915 : 3164 : range_gist_consistent_int_range(TypeCacheEntry *typcache,
916 : : StrategyNumber strategy,
917 : : const RangeType *key,
918 : : const RangeType *query)
919 : : {
5158 heikki.linnakangas@i 920 [ + + + + : 3164 : switch (strategy)
+ + + + +
- ]
921 : : {
922 : 341 : case RANGESTRAT_BEFORE:
1814 akorotkov@postgresql 923 [ + + + + ]: 341 : if (RangeIsEmpty(key) || RangeIsEmpty(query))
5158 heikki.linnakangas@i 924 : 112 : return false;
1814 akorotkov@postgresql 925 : 229 : return (!range_overright_internal(typcache, key, query));
5158 heikki.linnakangas@i 926 : 341 : case RANGESTRAT_OVERLEFT:
1814 akorotkov@postgresql 927 [ + + + + ]: 341 : if (RangeIsEmpty(key) || RangeIsEmpty(query))
5158 heikki.linnakangas@i 928 : 112 : return false;
1814 akorotkov@postgresql 929 : 229 : return (!range_after_internal(typcache, key, query));
5140 tgl@sss.pgh.pa.us 930 : 341 : case RANGESTRAT_OVERLAPS:
1814 akorotkov@postgresql 931 : 341 : return range_overlaps_internal(typcache, key, query);
5158 heikki.linnakangas@i 932 : 341 : case RANGESTRAT_OVERRIGHT:
1814 akorotkov@postgresql 933 [ + + + + ]: 341 : if (RangeIsEmpty(key) || RangeIsEmpty(query))
5158 heikki.linnakangas@i 934 : 112 : return false;
1814 akorotkov@postgresql 935 : 229 : return (!range_before_internal(typcache, key, query));
5140 tgl@sss.pgh.pa.us 936 : 341 : case RANGESTRAT_AFTER:
1814 akorotkov@postgresql 937 [ + + + + ]: 341 : if (RangeIsEmpty(key) || RangeIsEmpty(query))
5140 tgl@sss.pgh.pa.us 938 : 112 : return false;
1814 akorotkov@postgresql 939 : 229 : return (!range_overleft_internal(typcache, key, query));
5158 heikki.linnakangas@i 940 : 341 : case RANGESTRAT_ADJACENT:
1814 akorotkov@postgresql 941 [ + + + + ]: 341 : if (RangeIsEmpty(key) || RangeIsEmpty(query))
5158 heikki.linnakangas@i 942 : 112 : return false;
1814 akorotkov@postgresql 943 [ - + ]: 229 : if (range_adjacent_internal(typcache, key, query))
5158 heikki.linnakangas@i 944 :UBC 0 : return true;
1814 akorotkov@postgresql 945 :CBC 229 : return range_overlaps_internal(typcache, key, query);
5140 tgl@sss.pgh.pa.us 946 : 600 : case RANGESTRAT_CONTAINS:
1814 akorotkov@postgresql 947 : 600 : return range_contains_internal(typcache, key, query);
5140 tgl@sss.pgh.pa.us 948 : 341 : case RANGESTRAT_CONTAINED_BY:
949 : :
950 : : /*
951 : : * Empty ranges are contained by anything, so if key is or
952 : : * contains any empty ranges, we must descend into it. Otherwise,
953 : : * descend only if key overlaps the query.
954 : : */
5134 955 [ + + ]: 341 : if (RangeIsOrContainsEmpty(key))
956 : 36 : return true;
1814 akorotkov@postgresql 957 : 305 : return range_overlaps_internal(typcache, key, query);
5140 tgl@sss.pgh.pa.us 958 : 177 : case RANGESTRAT_EQ:
959 : :
960 : : /*
961 : : * If query is empty, descend only if the key is or contains any
962 : : * empty ranges. Otherwise, descend if key contains query.
963 : : */
1814 akorotkov@postgresql 964 [ - + ]: 177 : if (RangeIsEmpty(query))
5134 tgl@sss.pgh.pa.us 965 :UBC 0 : return RangeIsOrContainsEmpty(key);
1814 akorotkov@postgresql 966 :CBC 177 : return range_contains_internal(typcache, key, query);
5147 tgl@sss.pgh.pa.us 967 :UBC 0 : default:
968 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
969 : : return false; /* keep compiler quiet */
970 : : }
971 : : }
972 : :
973 : : /*
974 : : * GiST consistent test on an index internal page with multirange query
975 : : */
976 : : static bool
1814 akorotkov@postgresql 977 :CBC 3233 : range_gist_consistent_int_multirange(TypeCacheEntry *typcache,
978 : : StrategyNumber strategy,
979 : : const RangeType *key,
980 : : const MultirangeType *query)
981 : : {
5158 heikki.linnakangas@i 982 [ + + + + : 3233 : switch (strategy)
+ + + + +
- ]
983 : : {
984 : 341 : case RANGESTRAT_BEFORE:
1814 akorotkov@postgresql 985 [ + + + + ]: 341 : if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
986 : 112 : return false;
987 : 229 : return (!range_overright_multirange_internal(typcache, key, query));
5158 heikki.linnakangas@i 988 : 341 : case RANGESTRAT_OVERLEFT:
1814 akorotkov@postgresql 989 [ + + + + ]: 341 : if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
990 : 112 : return false;
991 : 229 : return (!range_after_multirange_internal(typcache, key, query));
5140 tgl@sss.pgh.pa.us 992 : 341 : case RANGESTRAT_OVERLAPS:
1814 akorotkov@postgresql 993 : 341 : return range_overlaps_multirange_internal(typcache, key, query);
5158 heikki.linnakangas@i 994 : 341 : case RANGESTRAT_OVERRIGHT:
1814 akorotkov@postgresql 995 [ + + + + ]: 341 : if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
996 : 112 : return false;
997 : 229 : return (!range_before_multirange_internal(typcache, key, query));
5140 tgl@sss.pgh.pa.us 998 : 341 : case RANGESTRAT_AFTER:
1814 akorotkov@postgresql 999 [ + + + + ]: 341 : if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
1000 : 112 : return false;
1001 : 229 : return (!range_overleft_multirange_internal(typcache, key, query));
5158 heikki.linnakangas@i 1002 : 341 : case RANGESTRAT_ADJACENT:
1814 akorotkov@postgresql 1003 [ + + + + ]: 341 : if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
1004 : 112 : return false;
1005 [ - + ]: 229 : if (range_adjacent_multirange_internal(typcache, key, query))
1814 akorotkov@postgresql 1006 :UBC 0 : return true;
1814 akorotkov@postgresql 1007 :CBC 229 : return range_overlaps_multirange_internal(typcache, key, query);
5140 tgl@sss.pgh.pa.us 1008 : 682 : case RANGESTRAT_CONTAINS:
1814 akorotkov@postgresql 1009 : 682 : return range_contains_multirange_internal(typcache, key, query);
5140 tgl@sss.pgh.pa.us 1010 : 341 : case RANGESTRAT_CONTAINED_BY:
1011 : :
1012 : : /*
1013 : : * Empty ranges are contained by anything, so if key is or
1014 : : * contains any empty ranges, we must descend into it. Otherwise,
1015 : : * descend only if key overlaps the query.
1016 : : */
1814 akorotkov@postgresql 1017 [ + + ]: 341 : if (RangeIsOrContainsEmpty(key))
1018 : 36 : return true;
1019 : 305 : return range_overlaps_multirange_internal(typcache, key, query);
1020 : 164 : case RANGESTRAT_EQ:
1021 : :
1022 : : /*
1023 : : * If query is empty, descend only if the key is or contains any
1024 : : * empty ranges. Otherwise, descend if key contains query.
1025 : : */
1026 [ + + ]: 164 : if (MultirangeIsEmpty(query))
1027 : 82 : return RangeIsOrContainsEmpty(key);
1028 : 82 : return range_contains_multirange_internal(typcache, key, query);
1814 akorotkov@postgresql 1029 :UBC 0 : default:
1030 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
1031 : : return false; /* keep compiler quiet */
1032 : : }
1033 : : }
1034 : :
1035 : : /*
1036 : : * GiST consistent test on an index internal page with element query
1037 : : */
1038 : : static bool
1814 akorotkov@postgresql 1039 :CBC 259 : range_gist_consistent_int_element(TypeCacheEntry *typcache,
1040 : : StrategyNumber strategy,
1041 : : const RangeType *key,
1042 : : Datum query)
1043 : : {
1044 [ + - ]: 259 : switch (strategy)
1045 : : {
5139 tgl@sss.pgh.pa.us 1046 : 259 : case RANGESTRAT_CONTAINS_ELEM:
4900 heikki.linnakangas@i 1047 : 259 : return range_contains_elem_internal(typcache, key, query);
1814 akorotkov@postgresql 1048 :UBC 0 : default:
1049 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
1050 : : return false; /* keep compiler quiet */
1051 : : }
1052 : : }
1053 : :
1054 : : /*
1055 : : * GiST consistent test on an index leaf page with range query
1056 : : */
1057 : : static bool
1814 akorotkov@postgresql 1058 :CBC 220995 : range_gist_consistent_leaf_range(TypeCacheEntry *typcache,
1059 : : StrategyNumber strategy,
1060 : : const RangeType *key,
1061 : : const RangeType *query)
1062 : : {
1063 [ + + + + : 220995 : switch (strategy)
+ + + + +
- ]
1064 : : {
1065 : 7422 : case RANGESTRAT_BEFORE:
1066 : 7422 : return range_before_internal(typcache, key, query);
1067 : 17979 : case RANGESTRAT_OVERLEFT:
1068 : 17979 : return range_overleft_internal(typcache, key, query);
1069 : 7273 : case RANGESTRAT_OVERLAPS:
1070 : 7273 : return range_overlaps_internal(typcache, key, query);
1071 : 40800 : case RANGESTRAT_OVERRIGHT:
1072 : 40800 : return range_overright_internal(typcache, key, query);
1073 : 38194 : case RANGESTRAT_AFTER:
1074 : 38194 : return range_after_internal(typcache, key, query);
1075 : 17979 : case RANGESTRAT_ADJACENT:
1076 : 17979 : return range_adjacent_internal(typcache, key, query);
1077 : 64280 : case RANGESTRAT_CONTAINS:
1078 : 64280 : return range_contains_internal(typcache, key, query);
1079 : 15481 : case RANGESTRAT_CONTAINED_BY:
1080 : 15481 : return range_contained_by_internal(typcache, key, query);
1081 : 11587 : case RANGESTRAT_EQ:
1082 : 11587 : return range_eq_internal(typcache, key, query);
1814 akorotkov@postgresql 1083 :UBC 0 : default:
1084 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
1085 : : return false; /* keep compiler quiet */
1086 : : }
1087 : : }
1088 : :
1089 : : /*
1090 : : * GiST consistent test on an index leaf page with multirange query
1091 : : */
1092 : : static bool
1814 akorotkov@postgresql 1093 :CBC 225347 : range_gist_consistent_leaf_multirange(TypeCacheEntry *typcache,
1094 : : StrategyNumber strategy,
1095 : : const RangeType *key,
1096 : : const MultirangeType *query)
1097 : : {
1098 [ + + + + : 225347 : switch (strategy)
+ + + + +
- ]
1099 : : {
1100 : 7422 : case RANGESTRAT_BEFORE:
1101 : 7422 : return range_before_multirange_internal(typcache, key, query);
1102 : 17979 : case RANGESTRAT_OVERLEFT:
1103 : 17979 : return range_overleft_multirange_internal(typcache, key, query);
1104 : 8490 : case RANGESTRAT_OVERLAPS:
1105 : 8490 : return range_overlaps_multirange_internal(typcache, key, query);
1106 : 40800 : case RANGESTRAT_OVERRIGHT:
1107 : 40800 : return range_overright_multirange_internal(typcache, key, query);
1108 : 38194 : case RANGESTRAT_AFTER:
1109 : 38194 : return range_after_multirange_internal(typcache, key, query);
1110 : 17979 : case RANGESTRAT_ADJACENT:
1111 : 17979 : return range_adjacent_multirange_internal(typcache, key, query);
1112 : 75380 : case RANGESTRAT_CONTAINS:
1113 : 75380 : return range_contains_multirange_internal(typcache, key, query);
1114 : 16134 : case RANGESTRAT_CONTAINED_BY:
1115 : 16134 : return multirange_contains_range_internal(typcache, query, key);
5140 tgl@sss.pgh.pa.us 1116 : 2969 : case RANGESTRAT_EQ:
1814 akorotkov@postgresql 1117 : 2969 : return multirange_union_range_equal(typcache, key, query);
1814 akorotkov@postgresql 1118 :UBC 0 : default:
1119 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
1120 : : return false; /* keep compiler quiet */
1121 : : }
1122 : : }
1123 : :
1124 : : /*
1125 : : * GiST consistent test on an index leaf page with element query
1126 : : */
1127 : : static bool
1814 akorotkov@postgresql 1128 :CBC 4958 : range_gist_consistent_leaf_element(TypeCacheEntry *typcache,
1129 : : StrategyNumber strategy,
1130 : : const RangeType *key,
1131 : : Datum query)
1132 : : {
1133 [ + - ]: 4958 : switch (strategy)
1134 : : {
1135 : 4958 : case RANGESTRAT_CONTAINS_ELEM:
1136 : 4958 : return range_contains_elem_internal(typcache, key, query);
5147 tgl@sss.pgh.pa.us 1137 :UBC 0 : default:
1138 [ # # ]: 0 : elog(ERROR, "unrecognized range strategy: %d", strategy);
1139 : : return false; /* keep compiler quiet */
1140 : : }
1141 : : }
1142 : :
1143 : : /*
1144 : : * Trivial split: half of entries will be placed on one page
1145 : : * and the other half on the other page.
1146 : : */
1147 : : static void
5036 tgl@sss.pgh.pa.us 1148 :CBC 21 : range_gist_fallback_split(TypeCacheEntry *typcache,
1149 : : GistEntryVector *entryvec,
1150 : : GIST_SPLITVEC *v)
1151 : : {
4938 bruce@momjian.us 1152 : 21 : RangeType *left_range = NULL;
1153 : 21 : RangeType *right_range = NULL;
1154 : : OffsetNumber i,
1155 : : maxoff,
1156 : : split_idx;
1157 : :
5036 tgl@sss.pgh.pa.us 1158 : 21 : maxoff = entryvec->n - 1;
1159 : : /* Split entries before this to left page, after to right: */
1160 : 21 : split_idx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;
1161 : :
1162 : 21 : v->spl_nleft = 0;
1163 : 21 : v->spl_nright = 0;
1164 [ + + ]: 10794 : for (i = FirstOffsetNumber; i <= maxoff; i++)
1165 : : {
3012 1166 : 10773 : RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
1167 : :
5036 1168 [ + + ]: 10773 : if (i < split_idx)
1169 [ + + ]: 5370 : PLACE_LEFT(range, i);
1170 : : else
1171 [ + + ]: 5403 : PLACE_RIGHT(range, i);
1172 : : }
1173 : :
3012 1174 : 21 : v->spl_ldatum = RangeTypePGetDatum(left_range);
1175 : 21 : v->spl_rdatum = RangeTypePGetDatum(right_range);
5036 1176 : 21 : }
1177 : :
1178 : : /*
1179 : : * Split based on classes of ranges.
1180 : : *
1181 : : * See get_gist_range_class for class definitions.
1182 : : * classes_groups is an array of length CLS_COUNT indicating the side of the
1183 : : * split to which each class should go.
1184 : : */
1185 : : static void
1186 : 22 : range_gist_class_split(TypeCacheEntry *typcache,
1187 : : GistEntryVector *entryvec,
1188 : : GIST_SPLITVEC *v,
1189 : : SplitLR *classes_groups)
1190 : : {
4938 bruce@momjian.us 1191 : 22 : RangeType *left_range = NULL;
1192 : 22 : RangeType *right_range = NULL;
1193 : : OffsetNumber i,
1194 : : maxoff;
1195 : :
5036 tgl@sss.pgh.pa.us 1196 : 22 : maxoff = entryvec->n - 1;
1197 : :
1198 : 22 : v->spl_nleft = 0;
1199 : 22 : v->spl_nright = 0;
1200 [ + + ]: 20435 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1201 : : {
3012 1202 : 20413 : RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
1203 : : int class;
1204 : :
1205 : : /* Get class of range */
5036 1206 : 20413 : class = get_gist_range_class(range);
1207 : :
1208 : : /* Place range to appropriate page */
1209 [ + + ]: 20413 : if (classes_groups[class] == SPLIT_LEFT)
1210 [ + + ]: 5228 : PLACE_LEFT(range, i);
1211 : : else
1212 : : {
1213 [ - + ]: 15185 : Assert(classes_groups[class] == SPLIT_RIGHT);
1214 [ + + ]: 15185 : PLACE_RIGHT(range, i);
1215 : : }
1216 : : }
1217 : :
3012 1218 : 22 : v->spl_ldatum = RangeTypePGetDatum(left_range);
1219 : 22 : v->spl_rdatum = RangeTypePGetDatum(right_range);
5036 1220 : 22 : }
1221 : :
1222 : : /*
1223 : : * Sorting based split. First half of entries according to the sort will be
1224 : : * placed to one page, and second half of entries will be placed to other
1225 : : * page. use_upper_bound parameter indicates whether to use upper or lower
1226 : : * bound for sorting.
1227 : : */
1228 : : static void
5036 tgl@sss.pgh.pa.us 1229 :UBC 0 : range_gist_single_sorting_split(TypeCacheEntry *typcache,
1230 : : GistEntryVector *entryvec,
1231 : : GIST_SPLITVEC *v,
1232 : : bool use_upper_bound)
1233 : : {
1234 : : SingleBoundSortItem *sortItems;
4938 bruce@momjian.us 1235 : 0 : RangeType *left_range = NULL;
1236 : 0 : RangeType *right_range = NULL;
1237 : : OffsetNumber i,
1238 : : maxoff,
1239 : : split_idx;
1240 : :
5036 tgl@sss.pgh.pa.us 1241 : 0 : maxoff = entryvec->n - 1;
1242 : :
7 michael@paquier.xyz 1243 :UNC 0 : sortItems = palloc_array(SingleBoundSortItem, maxoff);
1244 : :
1245 : : /*
1246 : : * Prepare auxiliary array and sort the values.
1247 : : */
5036 tgl@sss.pgh.pa.us 1248 [ # # ]:UBC 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1249 : : {
3012 1250 : 0 : RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
1251 : : RangeBound bound2;
1252 : : bool empty;
1253 : :
5036 1254 : 0 : sortItems[i - 1].index = i;
1255 : : /* Put appropriate bound into array */
1256 [ # # ]: 0 : if (use_upper_bound)
1257 : 0 : range_deserialize(typcache, range, &bound2,
1258 : 0 : &sortItems[i - 1].bound, &empty);
1259 : : else
1260 : 0 : range_deserialize(typcache, range, &sortItems[i - 1].bound,
1261 : : &bound2, &empty);
1262 [ # # ]: 0 : Assert(!empty);
1263 : : }
1264 : :
1265 : 0 : qsort_arg(sortItems, maxoff, sizeof(SingleBoundSortItem),
1266 : : single_bound_cmp, typcache);
1267 : :
1268 : 0 : split_idx = maxoff / 2;
1269 : :
1270 : 0 : v->spl_nleft = 0;
1271 : 0 : v->spl_nright = 0;
1272 : :
1273 [ # # ]: 0 : for (i = 0; i < maxoff; i++)
1274 : : {
4938 bruce@momjian.us 1275 : 0 : int idx = sortItems[i].index;
3012 tgl@sss.pgh.pa.us 1276 : 0 : RangeType *range = DatumGetRangeTypeP(entryvec->vector[idx].key);
1277 : :
5036 1278 [ # # ]: 0 : if (i < split_idx)
1279 [ # # ]: 0 : PLACE_LEFT(range, idx);
1280 : : else
1281 [ # # ]: 0 : PLACE_RIGHT(range, idx);
1282 : : }
1283 : :
3012 1284 : 0 : v->spl_ldatum = RangeTypePGetDatum(left_range);
1285 : 0 : v->spl_rdatum = RangeTypePGetDatum(right_range);
5036 1286 : 0 : }
1287 : :
1288 : : /*
1289 : : * Double sorting split algorithm.
1290 : : *
1291 : : * The algorithm considers dividing ranges into two groups. The first (left)
1292 : : * group contains general left bound. The second (right) group contains
1293 : : * general right bound. The challenge is to find upper bound of left group
1294 : : * and lower bound of right group so that overlap of groups is minimal and
1295 : : * ratio of distribution is acceptable. Algorithm finds for each lower bound of
1296 : : * right group minimal upper bound of left group, and for each upper bound of
1297 : : * left group maximal lower bound of right group. For each found pair
1298 : : * range_gist_consider_split considers replacement of currently selected
1299 : : * split with the new one.
1300 : : *
1301 : : * After that, all the entries are divided into three groups:
1302 : : * 1) Entries which should be placed to the left group
1303 : : * 2) Entries which should be placed to the right group
1304 : : * 3) "Common entries" which can be placed to either group without affecting
1305 : : * amount of overlap.
1306 : : *
1307 : : * The common ranges are distributed by difference of distance from lower
1308 : : * bound of common range to lower bound of right group and distance from upper
1309 : : * bound of common range to upper bound of left group.
1310 : : *
1311 : : * For details see:
1312 : : * "A new double sorting-based node splitting algorithm for R-tree",
1313 : : * A. Korotkov
1314 : : * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
1315 : : */
1316 : : static void
5036 tgl@sss.pgh.pa.us 1317 :CBC 192 : range_gist_double_sorting_split(TypeCacheEntry *typcache,
1318 : : GistEntryVector *entryvec,
1319 : : GIST_SPLITVEC *v)
1320 : : {
1321 : : ConsiderSplitContext context;
1322 : : OffsetNumber i,
1323 : : maxoff;
1211 drowley@postgresql.o 1324 : 192 : RangeType *left_range = NULL,
4938 bruce@momjian.us 1325 : 192 : *right_range = NULL;
1326 : : int common_entries_count;
1327 : : NonEmptyRange *by_lower,
1328 : : *by_upper;
1329 : : CommonEntry *common_entries;
1330 : : int nentries,
1331 : : i1,
1332 : : i2;
1333 : : RangeBound *right_lower,
1334 : : *left_upper;
1335 : :
5036 tgl@sss.pgh.pa.us 1336 : 192 : memset(&context, 0, sizeof(ConsiderSplitContext));
1337 : 192 : context.typcache = typcache;
1338 : 192 : context.has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
1339 : :
1340 : 192 : maxoff = entryvec->n - 1;
1341 : 192 : nentries = context.entries_count = maxoff - FirstOffsetNumber + 1;
1342 : 192 : context.first = true;
1343 : :
1344 : : /* Allocate arrays for sorted range bounds */
7 michael@paquier.xyz 1345 :GNC 192 : by_lower = palloc_array(NonEmptyRange, nentries);
1346 : 192 : by_upper = palloc_array(NonEmptyRange, nentries);
1347 : :
1348 : : /* Fill arrays of bounds */
5036 tgl@sss.pgh.pa.us 1349 [ + + ]:CBC 71124 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1350 : : {
3012 1351 : 70932 : RangeType *range = DatumGetRangeTypeP(entryvec->vector[i].key);
1352 : : bool empty;
1353 : :
5036 1354 : 70932 : range_deserialize(typcache, range,
1355 : 70932 : &by_lower[i - FirstOffsetNumber].lower,
1356 : 70932 : &by_lower[i - FirstOffsetNumber].upper,
1357 : : &empty);
1358 [ - + ]: 70932 : Assert(!empty);
1359 : : }
1360 : :
1361 : : /*
1362 : : * Make two arrays of range bounds: one sorted by lower bound and another
1363 : : * sorted by upper bound.
1364 : : */
1365 : 192 : memcpy(by_upper, by_lower, nentries * sizeof(NonEmptyRange));
1366 : 192 : qsort_arg(by_lower, nentries, sizeof(NonEmptyRange),
1367 : : interval_cmp_lower, typcache);
1368 : 192 : qsort_arg(by_upper, nentries, sizeof(NonEmptyRange),
1369 : : interval_cmp_upper, typcache);
1370 : :
1371 : : /*----------
1372 : : * The goal is to form a left and right range, so that every entry
1373 : : * range is contained by either left or right interval (or both).
1374 : : *
1375 : : * For example, with the ranges (0,1), (1,3), (2,3), (2,4):
1376 : : *
1377 : : * 0 1 2 3 4
1378 : : * +-+
1379 : : * +---+
1380 : : * +-+
1381 : : * +---+
1382 : : *
1383 : : * The left and right ranges are of the form (0,a) and (b,4).
1384 : : * We first consider splits where b is the lower bound of an entry.
1385 : : * We iterate through all entries, and for each b, calculate the
1386 : : * smallest possible a. Then we consider splits where a is the
1387 : : * upper bound of an entry, and for each a, calculate the greatest
1388 : : * possible b.
1389 : : *
1390 : : * In the above example, the first loop would consider splits:
1391 : : * b=0: (0,1)-(0,4)
1392 : : * b=1: (0,1)-(1,4)
1393 : : * b=2: (0,3)-(2,4)
1394 : : *
1395 : : * And the second loop:
1396 : : * a=1: (0,1)-(1,4)
1397 : : * a=3: (0,3)-(2,4)
1398 : : * a=4: (0,4)-(2,4)
1399 : : *----------
1400 : : */
1401 : :
1402 : : /*
1403 : : * Iterate over lower bound of right group, finding smallest possible
1404 : : * upper bound of left group.
1405 : : */
1406 : 192 : i1 = 0;
1407 : 192 : i2 = 0;
1408 : 192 : right_lower = &by_lower[i1].lower;
4938 bruce@momjian.us 1409 : 192 : left_upper = &by_upper[i2].lower;
1410 : : while (true)
1411 : : {
1412 : : /*
1413 : : * Find next lower bound of right group.
1414 : : */
5036 tgl@sss.pgh.pa.us 1415 [ + + + + ]: 247766 : while (i1 < nentries &&
1416 : 123787 : range_cmp_bounds(typcache, right_lower,
1417 : 123787 : &by_lower[i1].lower) == 0)
1418 : : {
1419 [ + + ]: 70932 : if (range_cmp_bounds(typcache, &by_lower[i1].upper,
1420 : : left_upper) > 0)
1421 : 46497 : left_upper = &by_lower[i1].upper;
1422 : 70932 : i1++;
1423 : : }
1424 [ + + ]: 53047 : if (i1 >= nentries)
1425 : 192 : break;
1426 : 52855 : right_lower = &by_lower[i1].lower;
1427 : :
1428 : : /*
1429 : : * Find count of ranges which anyway should be placed to the left
1430 : : * group.
1431 : : */
1432 [ + + + + ]: 240772 : while (i2 < nentries &&
1433 : 117102 : range_cmp_bounds(typcache, &by_upper[i2].upper,
1434 : : left_upper) <= 0)
1435 : 70815 : i2++;
1436 : :
1437 : : /*
1438 : : * Consider found split to see if it's better than what we had.
1439 : : */
1440 : 52855 : range_gist_consider_split(&context, right_lower, i1, left_upper, i2);
1441 : : }
1442 : :
1443 : : /*
1444 : : * Iterate over upper bound of left group finding greatest possible lower
1445 : : * bound of right group.
1446 : : */
1447 : 192 : i1 = nentries - 1;
1448 : 192 : i2 = nentries - 1;
1449 : 192 : right_lower = &by_lower[i1].upper;
4938 bruce@momjian.us 1450 : 192 : left_upper = &by_upper[i2].upper;
1451 : : while (true)
1452 : : {
1453 : : /*
1454 : : * Find next upper bound of left group.
1455 : : */
5036 tgl@sss.pgh.pa.us 1456 [ + + + + ]: 259944 : while (i2 >= 0 &&
1457 : 129876 : range_cmp_bounds(typcache, left_upper,
1458 : 129876 : &by_upper[i2].upper) == 0)
1459 : : {
1460 [ + + ]: 70932 : if (range_cmp_bounds(typcache, &by_upper[i2].lower,
1461 : : right_lower) < 0)
1462 : 46479 : right_lower = &by_upper[i2].lower;
1463 : 70932 : i2--;
1464 : : }
1465 [ + + ]: 59136 : if (i2 < 0)
1466 : 192 : break;
1467 : 58944 : left_upper = &by_upper[i2].upper;
1468 : :
1469 : : /*
1470 : : * Find count of intervals which anyway should be placed to the right
1471 : : * group.
1472 : : */
1473 [ + + + + ]: 246861 : while (i1 >= 0 &&
1474 : 117102 : range_cmp_bounds(typcache, &by_lower[i1].lower,
1475 : : right_lower) >= 0)
1476 : 70815 : i1--;
1477 : :
1478 : : /*
1479 : : * Consider found split to see if it's better than what we had.
1480 : : */
1481 : 58944 : range_gist_consider_split(&context, right_lower, i1 + 1,
1482 : : left_upper, i2 + 1);
1483 : : }
1484 : :
1485 : : /*
1486 : : * If we failed to find any acceptable splits, use trivial split.
1487 : : */
1488 [ - + ]: 192 : if (context.first)
1489 : : {
5036 tgl@sss.pgh.pa.us 1490 :UBC 0 : range_gist_fallback_split(typcache, entryvec, v);
1491 : 0 : return;
1492 : : }
1493 : :
1494 : : /*
1495 : : * Ok, we have now selected bounds of the groups. Now we have to
1496 : : * distribute entries themselves. At first we distribute entries which can
1497 : : * be placed unambiguously and collect "common entries" to array.
1498 : : */
1499 : :
1500 : : /* Allocate vectors for results */
7 michael@paquier.xyz 1501 :GNC 192 : v->spl_left = palloc_array(OffsetNumber, nentries);
1502 : 192 : v->spl_right = palloc_array(OffsetNumber, nentries);
5036 tgl@sss.pgh.pa.us 1503 :CBC 192 : v->spl_nleft = 0;
1504 : 192 : v->spl_nright = 0;
1505 : :
1506 : : /*
1507 : : * Allocate an array for "common entries" - entries which can be placed to
1508 : : * either group without affecting overlap along selected axis.
1509 : : */
1510 : 192 : common_entries_count = 0;
7 michael@paquier.xyz 1511 :GNC 192 : common_entries = palloc_array(CommonEntry, nentries);
1512 : :
1513 : : /*
1514 : : * Distribute entries which can be distributed unambiguously, and collect
1515 : : * common entries.
1516 : : */
5036 tgl@sss.pgh.pa.us 1517 [ + + ]:CBC 71124 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1518 : : {
1519 : : RangeType *range;
1520 : : RangeBound lower,
1521 : : upper;
1522 : : bool empty;
1523 : :
1524 : : /*
1525 : : * Get upper and lower bounds along selected axis.
1526 : : */
3012 1527 : 70932 : range = DatumGetRangeTypeP(entryvec->vector[i].key);
1528 : :
5036 1529 : 70932 : range_deserialize(typcache, range, &lower, &upper, &empty);
1530 : :
1531 [ + + ]: 70932 : if (range_cmp_bounds(typcache, &upper, context.left_upper) <= 0)
1532 : : {
1533 : : /* Fits in the left group */
1534 [ + + ]: 30009 : if (range_cmp_bounds(typcache, &lower, context.right_lower) >= 0)
1535 : : {
1536 : : /* Fits also in the right group, so "common entry" */
1537 : 9430 : common_entries[common_entries_count].index = i;
1538 [ + - ]: 9430 : if (context.has_subtype_diff)
1539 : : {
1540 : : /*
1541 : : * delta = (lower - context.right_lower) -
1542 : : * (context.left_upper - upper)
1543 : : */
1544 : 9430 : common_entries[common_entries_count].delta =
1545 : 9430 : call_subtype_diff(typcache,
1546 : : lower.val,
1547 : 18860 : context.right_lower->val) -
1548 : 9430 : call_subtype_diff(typcache,
1549 : 9430 : context.left_upper->val,
1550 : : upper.val);
1551 : : }
1552 : : else
1553 : : {
1554 : : /* Without subtype_diff, take all deltas as zero */
5036 tgl@sss.pgh.pa.us 1555 :UBC 0 : common_entries[common_entries_count].delta = 0;
1556 : : }
5036 tgl@sss.pgh.pa.us 1557 :CBC 9430 : common_entries_count++;
1558 : : }
1559 : : else
1560 : : {
1561 : : /* Doesn't fit to the right group, so join to the left group */
1562 [ + + ]: 20579 : PLACE_LEFT(range, i);
1563 : : }
1564 : : }
1565 : : else
1566 : : {
1567 : : /*
1568 : : * Each entry should fit on either left or right group. Since this
1569 : : * entry didn't fit in the left group, it better fit in the right
1570 : : * group.
1571 : : */
1572 [ - + ]: 40923 : Assert(range_cmp_bounds(typcache, &lower,
1573 : : context.right_lower) >= 0);
1574 [ + + ]: 40923 : PLACE_RIGHT(range, i);
1575 : : }
1576 : : }
1577 : :
1578 : : /*
1579 : : * Distribute "common entries", if any.
1580 : : */
1581 [ + + ]: 192 : if (common_entries_count > 0)
1582 : : {
1583 : : /*
1584 : : * Sort "common entries" by calculated deltas in order to distribute
1585 : : * the most ambiguous entries first.
1586 : : */
1587 : 84 : qsort(common_entries, common_entries_count, sizeof(CommonEntry),
1588 : : common_entry_cmp);
1589 : :
1590 : : /*
1591 : : * Distribute "common entries" between groups according to sorting.
1592 : : */
1593 [ + + ]: 9514 : for (i = 0; i < common_entries_count; i++)
1594 : : {
1595 : : RangeType *range;
4938 bruce@momjian.us 1596 : 9430 : int idx = common_entries[i].index;
1597 : :
3012 tgl@sss.pgh.pa.us 1598 : 9430 : range = DatumGetRangeTypeP(entryvec->vector[idx].key);
1599 : :
1600 : : /*
1601 : : * Check if we have to place this entry in either group to achieve
1602 : : * LIMIT_RATIO.
1603 : : */
5036 1604 [ - + ]: 9430 : if (i < context.common_left)
5036 tgl@sss.pgh.pa.us 1605 [ # # ]:UBC 0 : PLACE_LEFT(range, idx);
1606 : : else
5036 tgl@sss.pgh.pa.us 1607 [ + - ]:CBC 9430 : PLACE_RIGHT(range, idx);
1608 : : }
1609 : : }
1610 : :
1611 : 192 : v->spl_ldatum = PointerGetDatum(left_range);
1612 : 192 : v->spl_rdatum = PointerGetDatum(right_range);
1613 : : }
1614 : :
1615 : : /*
1616 : : * Consider replacement of currently selected split with a better one
1617 : : * during range_gist_double_sorting_split.
1618 : : */
1619 : : static void
1620 : 111799 : range_gist_consider_split(ConsiderSplitContext *context,
1621 : : RangeBound *right_lower, int min_left_count,
1622 : : RangeBound *left_upper, int max_left_count)
1623 : : {
1624 : : int left_count,
1625 : : right_count;
1626 : : float4 ratio,
1627 : : overlap;
1628 : :
1629 : : /*
1630 : : * Calculate entries distribution ratio assuming most uniform distribution
1631 : : * of common entries.
1632 : : */
1633 [ + + ]: 111799 : if (min_left_count >= (context->entries_count + 1) / 2)
1634 : 47907 : left_count = min_left_count;
1635 [ + + ]: 63892 : else if (max_left_count <= context->entries_count / 2)
1636 : 46239 : left_count = max_left_count;
1637 : : else
1638 : 17653 : left_count = context->entries_count / 2;
1639 : 111799 : right_count = context->entries_count - left_count;
1640 : :
1641 : : /*
1642 : : * Ratio of split: quotient between size of smaller group and total
1643 : : * entries count. This is necessarily 0.5 or less; if it's less than
1644 : : * LIMIT_RATIO then we will never accept the new split.
1645 : : */
1646 [ + + ]: 111799 : ratio = ((float4) Min(left_count, right_count)) /
1647 : 111799 : ((float4) context->entries_count);
1648 : :
1649 [ + + ]: 111799 : if (ratio > LIMIT_RATIO)
1650 : : {
1651 : 56752 : bool selectthis = false;
1652 : :
1653 : : /*
1654 : : * The ratio is acceptable, so compare current split with previously
1655 : : * selected one. We search for minimal overlap (allowing negative
1656 : : * values) and minimal ratio secondarily. If subtype_diff is
1657 : : * available, it's used for overlap measure. Without subtype_diff we
1658 : : * use number of "common entries" as an overlap measure.
1659 : : */
1660 [ + - ]: 56752 : if (context->has_subtype_diff)
1661 : 56752 : overlap = call_subtype_diff(context->typcache,
1662 : : left_upper->val,
1663 : : right_lower->val);
1664 : : else
5036 tgl@sss.pgh.pa.us 1665 :UBC 0 : overlap = max_left_count - min_left_count;
1666 : :
1667 : : /* If there is no previous selection, select this split */
5036 tgl@sss.pgh.pa.us 1668 [ + + ]:CBC 56752 : if (context->first)
1669 : 192 : selectthis = true;
1670 : : else
1671 : : {
1672 : : /*
1673 : : * Choose the new split if it has a smaller overlap, or same
1674 : : * overlap but better ratio.
1675 : : */
1676 [ + + ]: 56560 : if (overlap < context->overlap ||
1677 [ + + + + ]: 47977 : (overlap == context->overlap && ratio > context->ratio))
1678 : 16383 : selectthis = true;
1679 : : }
1680 : :
1681 [ + + ]: 56752 : if (selectthis)
1682 : : {
1683 : : /* save information about selected split */
1684 : 16575 : context->first = false;
1685 : 16575 : context->ratio = ratio;
1686 : 16575 : context->overlap = overlap;
1687 : 16575 : context->right_lower = right_lower;
1688 : 16575 : context->left_upper = left_upper;
1689 : 16575 : context->common_left = max_left_count - left_count;
1690 : 16575 : context->common_right = left_count - min_left_count;
1691 : : }
1692 : : }
1693 : 111799 : }
1694 : :
1695 : : /*
1696 : : * Find class number for range.
1697 : : *
1698 : : * The class number is a valid combination of the properties of the
1699 : : * range. Note: the highest possible number is 8, because CLS_EMPTY
1700 : : * can't be combined with anything else.
1701 : : */
1702 : : static int
1703 : 122531 : get_gist_range_class(RangeType *range)
1704 : : {
1705 : : int classNumber;
1706 : : char flags;
1707 : :
1708 : 122531 : flags = range_get_flags(range);
1709 [ + + ]: 122531 : if (flags & RANGE_EMPTY)
1710 : : {
1711 : 25101 : classNumber = CLS_EMPTY;
1712 : : }
1713 : : else
1714 : : {
1715 : 97430 : classNumber = 0;
1716 [ + + ]: 97430 : if (flags & RANGE_LB_INF)
1717 : 1400 : classNumber |= CLS_LOWER_INF;
1718 [ + + ]: 97430 : if (flags & RANGE_UB_INF)
1719 : 728 : classNumber |= CLS_UPPER_INF;
1720 [ - + ]: 97430 : if (flags & RANGE_CONTAIN_EMPTY)
5036 tgl@sss.pgh.pa.us 1721 :UBC 0 : classNumber |= CLS_CONTAIN_EMPTY;
1722 : : }
5036 tgl@sss.pgh.pa.us 1723 :CBC 122531 : return classNumber;
1724 : : }
1725 : :
1726 : : /*
1727 : : * Comparison function for range_gist_single_sorting_split.
1728 : : */
1729 : : static int
5036 tgl@sss.pgh.pa.us 1730 :UBC 0 : single_bound_cmp(const void *a, const void *b, void *arg)
1731 : : {
4938 bruce@momjian.us 1732 : 0 : SingleBoundSortItem *i1 = (SingleBoundSortItem *) a;
1733 : 0 : SingleBoundSortItem *i2 = (SingleBoundSortItem *) b;
5036 tgl@sss.pgh.pa.us 1734 : 0 : TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1735 : :
1736 : 0 : return range_cmp_bounds(typcache, &i1->bound, &i2->bound);
1737 : : }
1738 : :
1739 : : /*
1740 : : * Compare NonEmptyRanges by lower bound.
1741 : : */
1742 : : static int
5036 tgl@sss.pgh.pa.us 1743 :CBC 188023 : interval_cmp_lower(const void *a, const void *b, void *arg)
1744 : : {
1745 : 188023 : NonEmptyRange *i1 = (NonEmptyRange *) a;
1746 : 188023 : NonEmptyRange *i2 = (NonEmptyRange *) b;
1747 : 188023 : TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1748 : :
1749 : 188023 : return range_cmp_bounds(typcache, &i1->lower, &i2->lower);
1750 : : }
1751 : :
1752 : : /*
1753 : : * Compare NonEmptyRanges by upper bound.
1754 : : */
1755 : : static int
1756 : 330459 : interval_cmp_upper(const void *a, const void *b, void *arg)
1757 : : {
1758 : 330459 : NonEmptyRange *i1 = (NonEmptyRange *) a;
1759 : 330459 : NonEmptyRange *i2 = (NonEmptyRange *) b;
1760 : 330459 : TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
1761 : :
1762 : 330459 : return range_cmp_bounds(typcache, &i1->upper, &i2->upper);
1763 : : }
1764 : :
1765 : : /*
1766 : : * Compare CommonEntrys by their deltas.
1767 : : */
1768 : : static int
1769 : 9346 : common_entry_cmp(const void *i1, const void *i2)
1770 : : {
1771 : 9346 : double delta1 = ((CommonEntry *) i1)->delta;
1772 : 9346 : double delta2 = ((CommonEntry *) i2)->delta;
1773 : :
1774 [ + + ]: 9346 : if (delta1 < delta2)
1775 : 6379 : return -1;
1776 [ - + ]: 2967 : else if (delta1 > delta2)
5036 tgl@sss.pgh.pa.us 1777 :UBC 0 : return 1;
1778 : : else
5036 tgl@sss.pgh.pa.us 1779 :CBC 2967 : return 0;
1780 : : }
1781 : :
1782 : : /*
1783 : : * Convenience function to invoke type-specific subtype_diff function.
1784 : : * Caller must have already checked that there is one for the range type.
1785 : : */
1786 : : static float8
1787 : 373704 : call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
1788 : : {
1789 : : float8 value;
1790 : :
1791 : 373704 : value = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
1792 : : typcache->rng_collation,
1793 : : val1, val2));
1794 : : /* Cope with buggy subtype_diff function by returning zero */
1795 [ + - ]: 373704 : if (value >= 0.0)
1796 : 373704 : return value;
5036 tgl@sss.pgh.pa.us 1797 :UBC 0 : return 0.0;
1798 : : }
|
