LCOV - code coverage report
Current view: top level - src/backend/utils/adt - rangetypes_gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 481 584 82.4 %
Date: 2021-01-26 03:06:49 Functions: 24 26 92.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * rangetypes_gist.c
       4             :  *    GiST support for range types.
       5             :  *
       6             :  * Portions Copyright (c) 1996-2021, 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
     191      434644 : range_gist_consistent(PG_FUNCTION_ARGS)
     192             : {
     193      434644 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     194      434644 :     Datum       query = PG_GETARG_DATUM(1);
     195      434644 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     196             :     bool        result;
     197      434644 :     Oid         subtype = PG_GETARG_OID(3);
     198      434644 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     199      434644 :     RangeType  *key = DatumGetRangeTypeP(entry->key);
     200             :     TypeCacheEntry *typcache;
     201             : 
     202             :     /* All operators served by this function are exact */
     203      434644 :     *recheck = false;
     204             : 
     205      434644 :     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             :      */
     213      434644 :     if (GIST_LEAF(entry))
     214             :     {
     215      429404 :         if (!OidIsValid(subtype) || subtype == ANYRANGEOID)
     216      213664 :             result = range_gist_consistent_leaf_range(typcache, strategy, key,
     217      213664 :                                                       DatumGetRangeTypeP(query));
     218      215740 :         else if (subtype == ANYMULTIRANGEOID)
     219      209828 :             result = range_gist_consistent_leaf_multirange(typcache, strategy, key,
     220      209828 :                                                            DatumGetMultirangeTypeP(query));
     221             :         else
     222        5912 :             result = range_gist_consistent_leaf_element(typcache, strategy,
     223             :                                                         key, query);
     224             :     }
     225             :     else
     226             :     {
     227        5240 :         if (!OidIsValid(subtype) || subtype == ANYRANGEOID)
     228        2620 :             result = range_gist_consistent_int_range(typcache, strategy, key,
     229        2620 :                                                      DatumGetRangeTypeP(query));
     230        2620 :         else if (subtype == ANYMULTIRANGEOID)
     231        2358 :             result = range_gist_consistent_int_multirange(typcache, strategy, key,
     232        2358 :                                                           DatumGetMultirangeTypeP(query));
     233             :         else
     234         262 :             result = range_gist_consistent_int_element(typcache, strategy,
     235             :                                                        key, query);
     236             :     }
     237      434644 :     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       26288 : multirange_gist_compress(PG_FUNCTION_ARGS)
     246             : {
     247       26288 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     248             : 
     249       26288 :     if (entry->leafkey)
     250             :     {
     251       14800 :         MultirangeType *mr = DatumGetMultirangeTypeP(entry->key);
     252             :         RangeType  *r;
     253             :         TypeCacheEntry *typcache;
     254       14800 :         GISTENTRY  *retval = palloc(sizeof(GISTENTRY));
     255             : 
     256       14800 :         typcache = multirange_get_typcache(fcinfo, MultirangeTypeGetOid(mr));
     257       14800 :         r = multirange_get_union_range(typcache->rngtype, mr);
     258             : 
     259       14800 :         gistentryinit(*retval, RangeTypePGetDatum(r),
     260             :                       entry->rel, entry->page, entry->offset, false);
     261             : 
     262       14800 :         PG_RETURN_POINTER(retval);
     263             :     }
     264             : 
     265       11488 :     PG_RETURN_POINTER(entry);
     266             : }
     267             : 
     268             : /* GiST query consistency check for multiranges */
     269             : Datum
     270      126944 : multirange_gist_consistent(PG_FUNCTION_ARGS)
     271             : {
     272      126944 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     273      126944 :     Datum       query = PG_GETARG_DATUM(1);
     274      126944 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     275             :     bool        result;
     276      126944 :     Oid         subtype = PG_GETARG_OID(3);
     277      126944 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     278      126944 :     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      126944 :     *recheck = true;
     286             : 
     287      126944 :     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      126944 :     if (GIST_LEAF(entry))
     296             :     {
     297      124744 :         if (!OidIsValid(subtype) || subtype == ANYMULTIRANGEOID)
     298       62372 :             result = range_gist_consistent_leaf_multirange(typcache, strategy, key,
     299       62372 :                                                            DatumGetMultirangeTypeP(query));
     300       62372 :         else if (subtype == ANYRANGEOID)
     301       60602 :             result = range_gist_consistent_leaf_range(typcache, strategy, key,
     302       60602 :                                                       DatumGetRangeTypeP(query));
     303             :         else
     304        1770 :             result = range_gist_consistent_leaf_element(typcache, strategy,
     305             :                                                         key, query);
     306             :     }
     307             :     else
     308             :     {
     309        2200 :         if (!OidIsValid(subtype) || subtype == ANYMULTIRANGEOID)
     310        1100 :             result = range_gist_consistent_int_multirange(typcache, strategy, key,
     311        1100 :                                                           DatumGetMultirangeTypeP(query));
     312        1100 :         else if (subtype == ANYRANGEOID)
     313         990 :             result = range_gist_consistent_int_range(typcache, strategy, key,
     314         990 :                                                      DatumGetRangeTypeP(query));
     315             :         else
     316         110 :             result = range_gist_consistent_int_element(typcache, strategy,
     317             :                                                        key, query);
     318             :     }
     319      126944 :     PG_RETURN_BOOL(result);
     320             : }
     321             : 
     322             : /* form union range */
     323             : Datum
     324       61260 : range_gist_union(PG_FUNCTION_ARGS)
     325             : {
     326       61260 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     327       61260 :     GISTENTRY  *ent = entryvec->vector;
     328             :     RangeType  *result_range;
     329             :     TypeCacheEntry *typcache;
     330             :     int         i;
     331             : 
     332       61260 :     result_range = DatumGetRangeTypeP(ent[0].key);
     333             : 
     334       61260 :     typcache = range_get_typcache(fcinfo, RangeTypeGetOid(result_range));
     335             : 
     336      139476 :     for (i = 1; i < entryvec->n; i++)
     337             :     {
     338       78216 :         result_range = range_super_union(typcache, result_range,
     339       78216 :                                          DatumGetRangeTypeP(ent[i].key));
     340             :     }
     341             : 
     342       61260 :     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
     362      840106 : range_gist_penalty(PG_FUNCTION_ARGS)
     363             : {
     364      840106 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
     365      840106 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     366      840106 :     float      *penalty = (float *) PG_GETARG_POINTER(2);
     367      840106 :     RangeType  *orig = DatumGetRangeTypeP(origentry->key);
     368      840106 :     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             : 
     378      840106 :     if (RangeTypeGetOid(orig) != RangeTypeGetOid(new))
     379           0 :         elog(ERROR, "range types do not match");
     380             : 
     381      840106 :     typcache = range_get_typcache(fcinfo, RangeTypeGetOid(orig));
     382             : 
     383      840106 :     has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
     384             : 
     385      840106 :     range_deserialize(typcache, orig, &orig_lower, &orig_upper, &orig_empty);
     386      840106 :     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      840106 :     if (new_empty)
     394             :     {
     395             :         /* Handle insertion of empty range */
     396      169826 :         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       11050 :             *penalty = 0.0;
     404             :         }
     405      158776 :         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        2276 :             *penalty = CONTAIN_EMPTY_PENALTY;
     414             :         }
     415      156500 :         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             :              */
     421           0 :             *penalty = 2 * CONTAIN_EMPTY_PENALTY;
     422             :         }
     423      156500 :         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             :              */
     429           0 :             *penalty = 3 * CONTAIN_EMPTY_PENALTY;
     430             :         }
     431             :         else
     432             :         {
     433             :             /*
     434             :              * The least preferred case is broadening of normal range.
     435             :              */
     436      156500 :             *penalty = 4 * CONTAIN_EMPTY_PENALTY;
     437             :         }
     438             :     }
     439      670280 :     else if (new_lower.infinite && new_upper.infinite)
     440             :     {
     441             :         /* Handle insertion of (-inf, +inf) range */
     442           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             :     }
     475      670280 :     else if (new_lower.infinite)
     476             :     {
     477             :         /* Handle insertion of (-inf, x) range */
     478       27164 :         if (!orig_empty && orig_lower.infinite)
     479             :         {
     480        2376 :             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             :                  */
     489           0 :                 *penalty = 0.0;
     490             :             }
     491             :             else
     492             :             {
     493        1188 :                 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         798 :                     if (has_subtype_diff)
     500         798 :                         *penalty = call_subtype_diff(typcache,
     501             :                                                      new_upper.val,
     502             :                                                      orig_upper.val);
     503             :                     else
     504           0 :                         *penalty = DEFAULT_SUBTYPE_DIFF_PENALTY;
     505             :                 }
     506             :                 else
     507             :                 {
     508             :                     /* No extension of original range */
     509         390 :                     *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       25976 :             *penalty = get_float4_infinity();
     520             :         }
     521             :     }
     522      643116 :     else if (new_upper.infinite)
     523             :     {
     524             :         /* Handle insertion of (x, +inf) range */
     525       19200 :         if (!orig_empty && orig_upper.infinite)
     526             :         {
     527        2376 :             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         198 :                 *penalty = 0.0;
     537             :             }
     538             :             else
     539             :             {
     540         990 :                 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             :                      */
     546           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 */
     556         990 :                     *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       18012 :             *penalty = get_float4_infinity();
     567             :         }
     568             :     }
     569             :     else
     570             :     {
     571             :         /* Handle insertion of normal (non-empty, non-infinite) range */
     572      623916 :         if (orig_empty || orig_lower.infinite || orig_upper.infinite)
     573             :         {
     574             :             /*
     575             :              * Avoid mixing normal ranges with infinite and empty ranges.
     576             :              */
     577       61060 :             *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      562856 :             float8      diff = 0.0;
     586             : 
     587      562856 :             if (range_cmp_bounds(typcache, &new_lower, &orig_lower) < 0)
     588             :             {
     589      188984 :                 if (has_subtype_diff)
     590      188984 :                     diff += call_subtype_diff(typcache,
     591             :                                               orig_lower.val,
     592             :                                               new_lower.val);
     593             :                 else
     594           0 :                     diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
     595             :             }
     596      562856 :             if (range_cmp_bounds(typcache, &new_upper, &orig_upper) > 0)
     597             :             {
     598      463722 :                 if (has_subtype_diff)
     599      463722 :                     diff += call_subtype_diff(typcache,
     600             :                                               new_upper.val,
     601             :                                               orig_upper.val);
     602             :                 else
     603           0 :                     diff += DEFAULT_SUBTYPE_DIFF_PENALTY;
     604             :             }
     605      562856 :             *penalty = diff;
     606             :         }
     607             :     }
     608             : 
     609      840106 :     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         360 : range_gist_picksplit(PG_FUNCTION_ARGS)
     620             : {
     621         360 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     622         360 :     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;
     630         360 :     int         non_empty_classes_count = 0;
     631         360 :     int         biggest_class = -1;
     632         360 :     int         biggest_class_count = 0;
     633             :     int         total_count;
     634             : 
     635             :     /* use first item to look up range type's info */
     636         360 :     pred_left = DatumGetRangeTypeP(entryvec->vector[FirstOffsetNumber].key);
     637         360 :     typcache = range_get_typcache(fcinfo, RangeTypeGetOid(pred_left));
     638             : 
     639         360 :     maxoff = entryvec->n - 1;
     640         360 :     nbytes = (maxoff + 1) * sizeof(OffsetNumber);
     641         360 :     v->spl_left = (OffsetNumber *) palloc(nbytes);
     642         360 :     v->spl_right = (OffsetNumber *) palloc(nbytes);
     643             : 
     644             :     /*
     645             :      * Get count distribution of range classes.
     646             :      */
     647         360 :     memset(count_in_classes, 0, sizeof(count_in_classes));
     648      102008 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     649             :     {
     650      101648 :         RangeType  *range = DatumGetRangeTypeP(entryvec->vector[i].key);
     651             : 
     652      101648 :         count_in_classes[get_gist_range_class(range)]++;
     653             :     }
     654             : 
     655             :     /*
     656             :      * Count non-empty classes and find biggest class.
     657             :      */
     658         360 :     total_count = maxoff;
     659        3600 :     for (j = 0; j < CLS_COUNT; j++)
     660             :     {
     661        3240 :         if (count_in_classes[j] > 0)
     662             :         {
     663         376 :             if (count_in_classes[j] > biggest_class_count)
     664             :             {
     665         372 :                 biggest_class_count = count_in_classes[j];
     666         372 :                 biggest_class = j;
     667             :             }
     668         376 :             non_empty_classes_count++;
     669             :         }
     670             :     }
     671             : 
     672             :     Assert(non_empty_classes_count > 0);
     673             : 
     674         360 :     if (non_empty_classes_count == 1)
     675             :     {
     676             :         /* One non-empty class, so split inside class */
     677         346 :         if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_NORMAL)
     678             :         {
     679             :             /* double sorting split for normal ranges */
     680         318 :             range_gist_double_sorting_split(typcache, entryvec, v);
     681             :         }
     682          28 :         else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_LOWER_INF)
     683             :         {
     684             :             /* upper bound sorting split for (-inf, x) ranges */
     685           0 :             range_gist_single_sorting_split(typcache, entryvec, v, true);
     686             :         }
     687          28 :         else if ((biggest_class & ~CLS_CONTAIN_EMPTY) == CLS_UPPER_INF)
     688             :         {
     689             :             /* lower bound sorting split for (x, +inf) ranges */
     690           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 */
     695          28 :             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          14 :         memset(classes_groups, 0, sizeof(classes_groups));
     709             : 
     710          14 :         if (count_in_classes[CLS_NORMAL] > 0)
     711             :         {
     712             :             /* separate normal ranges if any */
     713          14 :             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           0 :             nonInfCount =
     733           0 :                 count_in_classes[CLS_NORMAL] +
     734           0 :                 count_in_classes[CLS_CONTAIN_EMPTY] +
     735           0 :                 count_in_classes[CLS_EMPTY];
     736           0 :             infCount = total_count - nonInfCount;
     737             : 
     738           0 :             nonEmptyCount =
     739           0 :                 count_in_classes[CLS_NORMAL] +
     740           0 :                 count_in_classes[CLS_LOWER_INF] +
     741           0 :                 count_in_classes[CLS_UPPER_INF] +
     742           0 :                 count_in_classes[CLS_LOWER_INF | CLS_UPPER_INF];
     743           0 :             emptyCount = total_count - nonEmptyCount;
     744             : 
     745           0 :             if (infCount > 0 && nonInfCount > 0 &&
     746           0 :                 (Abs(infCount - nonInfCount) <=
     747           0 :                  Abs(emptyCount - nonEmptyCount)))
     748             :             {
     749           0 :                 classes_groups[CLS_NORMAL] = SPLIT_RIGHT;
     750           0 :                 classes_groups[CLS_CONTAIN_EMPTY] = SPLIT_RIGHT;
     751           0 :                 classes_groups[CLS_EMPTY] = SPLIT_RIGHT;
     752             :             }
     753           0 :             else if (emptyCount > 0 && nonEmptyCount > 0)
     754             :             {
     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;
     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             : 
     770          14 :         range_gist_class_split(typcache, entryvec, v, classes_groups);
     771             :     }
     772             : 
     773         360 :     PG_RETURN_POINTER(v);
     774             : }
     775             : 
     776             : /* equality comparator for GiST */
     777             : Datum
     778       61136 : range_gist_same(PG_FUNCTION_ARGS)
     779             : {
     780       61136 :     RangeType  *r1 = PG_GETARG_RANGE_P(0);
     781       61136 :     RangeType  *r2 = PG_GETARG_RANGE_P(1);
     782       61136 :     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             :      */
     790       61136 :     if (range_get_flags(r1) != range_get_flags(r2))
     791          36 :         *result = false;
     792             :     else
     793             :     {
     794             :         TypeCacheEntry *typcache;
     795             : 
     796       61100 :         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
     797             : 
     798       61100 :         *result = range_eq_internal(typcache, r1, r2);
     799             :     }
     800             : 
     801       61136 :     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 *
     821      179206 : 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             : 
     835      179206 :     range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
     836      179206 :     range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
     837      179206 :     flags1 = range_get_flags(r1);
     838      179206 :     flags2 = range_get_flags(r2);
     839             : 
     840      179206 :     if (empty1)
     841             :     {
     842             :         /* We can return r2 as-is if it already is or contains empty */
     843       20700 :         if (flags2 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
     844       20700 :             return r2;
     845             :         /* Else we'd better copy it (modify-in-place isn't safe) */
     846           0 :         r2 = rangeCopy(r2);
     847           0 :         range_set_contain_empty(r2);
     848           0 :         return r2;
     849             :     }
     850      158506 :     if (empty2)
     851             :     {
     852             :         /* We can return r1 as-is if it already is or contains empty */
     853        2288 :         if (flags1 & (RANGE_EMPTY | RANGE_CONTAIN_EMPTY))
     854        2276 :             return r1;
     855             :         /* Else we'd better copy it (modify-in-place isn't safe) */
     856          12 :         r1 = rangeCopy(r1);
     857          12 :         range_set_contain_empty(r1);
     858          12 :         return r1;
     859             :     }
     860             : 
     861      156218 :     if (range_cmp_bounds(typcache, &lower1, &lower2) <= 0)
     862      156146 :         result_lower = &lower1;
     863             :     else
     864          72 :         result_lower = &lower2;
     865             : 
     866      156218 :     if (range_cmp_bounds(typcache, &upper1, &upper2) >= 0)
     867       29696 :         result_upper = &upper1;
     868             :     else
     869      126522 :         result_upper = &upper2;
     870             : 
     871             :     /* optimization to avoid constructing a new range */
     872      156218 :     if (result_lower == &lower1 && result_upper == &upper1 &&
     873       29684 :         ((flags1 & RANGE_CONTAIN_EMPTY) || !(flags2 & RANGE_CONTAIN_EMPTY)))
     874       29684 :         return r1;
     875      126534 :     if (result_lower == &lower2 && result_upper == &upper2 &&
     876          60 :         ((flags2 & RANGE_CONTAIN_EMPTY) || !(flags1 & RANGE_CONTAIN_EMPTY)))
     877          60 :         return r2;
     878             : 
     879      126474 :     result = make_range(typcache, result_lower, result_upper, false);
     880             : 
     881      126474 :     if ((flags1 & RANGE_CONTAIN_EMPTY) || (flags2 & RANGE_CONTAIN_EMPTY))
     882           0 :         range_set_contain_empty(result);
     883             : 
     884      126474 :     return result;
     885             : }
     886             : 
     887             : static bool
     888        1770 : 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        1770 :     if (RangeIsEmpty(r) || MultirangeIsEmpty(mr))
     900           0 :         return (RangeIsEmpty(r) && MultirangeIsEmpty(mr));
     901             : 
     902        1770 :     range_deserialize(typcache, r, &lower1, &upper1, &empty);
     903             :     Assert(!empty);
     904        1770 :     multirange_get_bounds(typcache, mr, 0, &lower2, &tmp);
     905        1770 :     multirange_get_bounds(typcache, mr, mr->rangeCount - 1, &tmp, &upper2);
     906             : 
     907        1778 :     return (range_cmp_bounds(typcache, &lower1, &lower2) == 0 &&
     908           8 :             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        3610 : range_gist_consistent_int_range(TypeCacheEntry *typcache,
     916             :                                 StrategyNumber strategy,
     917             :                                 const RangeType *key,
     918             :                                 const RangeType *query)
     919             : {
     920        3610 :     switch (strategy)
     921             :     {
     922         372 :         case RANGESTRAT_BEFORE:
     923         372 :             if (RangeIsEmpty(key) || RangeIsEmpty(query))
     924          40 :                 return false;
     925         332 :             return (!range_overright_internal(typcache, key, query));
     926         372 :         case RANGESTRAT_OVERLEFT:
     927         372 :             if (RangeIsEmpty(key) || RangeIsEmpty(query))
     928          40 :                 return false;
     929         332 :             return (!range_after_internal(typcache, key, query));
     930         372 :         case RANGESTRAT_OVERLAPS:
     931         372 :             return range_overlaps_internal(typcache, key, query);
     932         372 :         case RANGESTRAT_OVERRIGHT:
     933         372 :             if (RangeIsEmpty(key) || RangeIsEmpty(query))
     934          40 :                 return false;
     935         332 :             return (!range_before_internal(typcache, key, query));
     936         372 :         case RANGESTRAT_AFTER:
     937         372 :             if (RangeIsEmpty(key) || RangeIsEmpty(query))
     938          40 :                 return false;
     939         332 :             return (!range_overleft_internal(typcache, key, query));
     940         372 :         case RANGESTRAT_ADJACENT:
     941         372 :             if (RangeIsEmpty(key) || RangeIsEmpty(query))
     942          40 :                 return false;
     943         332 :             if (range_adjacent_internal(typcache, key, query))
     944           0 :                 return true;
     945         332 :             return range_overlaps_internal(typcache, key, query);
     946         744 :         case RANGESTRAT_CONTAINS:
     947         744 :             return range_contains_internal(typcache, key, query);
     948         372 :         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             :              */
     955         372 :             if (RangeIsOrContainsEmpty(key))
     956          40 :                 return true;
     957         332 :             return range_overlaps_internal(typcache, key, query);
     958         262 :         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             :              */
     964         262 :             if (RangeIsEmpty(query))
     965           0 :                 return RangeIsOrContainsEmpty(key);
     966         262 :             return range_contains_internal(typcache, key, query);
     967           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
     977        3458 : range_gist_consistent_int_multirange(TypeCacheEntry *typcache,
     978             :                                      StrategyNumber strategy,
     979             :                                      const RangeType *key,
     980             :                                      const MultirangeType *query)
     981             : {
     982        3458 :     switch (strategy)
     983             :     {
     984         372 :         case RANGESTRAT_BEFORE:
     985         372 :             if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
     986          40 :                 return false;
     987         332 :             return (!range_overright_multirange_internal(typcache, key, query));
     988         372 :         case RANGESTRAT_OVERLEFT:
     989         372 :             if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
     990          40 :                 return false;
     991         332 :             return (!range_after_multirange_internal(typcache, key, query));
     992         372 :         case RANGESTRAT_OVERLAPS:
     993         372 :             return range_overlaps_multirange_internal(typcache, key, query);
     994         372 :         case RANGESTRAT_OVERRIGHT:
     995         372 :             if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
     996          40 :                 return false;
     997         332 :             return (!range_before_multirange_internal(typcache, key, query));
     998         372 :         case RANGESTRAT_AFTER:
     999         372 :             if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
    1000          40 :                 return false;
    1001         332 :             return (!range_overleft_multirange_internal(typcache, key, query));
    1002         372 :         case RANGESTRAT_ADJACENT:
    1003         372 :             if (RangeIsEmpty(key) || MultirangeIsEmpty(query))
    1004          40 :                 return false;
    1005         332 :             if (range_adjacent_multirange_internal(typcache, key, query))
    1006           0 :                 return true;
    1007         332 :             return range_overlaps_multirange_internal(typcache, key, query);
    1008         744 :         case RANGESTRAT_CONTAINS:
    1009         744 :             return range_contains_multirange_internal(typcache, key, query);
    1010         372 :         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             :              */
    1017         372 :             if (RangeIsOrContainsEmpty(key))
    1018          40 :                 return true;
    1019         332 :             return range_overlaps_multirange_internal(typcache, key, query);
    1020         110 :         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         110 :             if (MultirangeIsEmpty(query))
    1027           0 :                 return RangeIsOrContainsEmpty(key);
    1028         110 :             return range_contains_multirange_internal(typcache, key, query);
    1029           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
    1039         372 : range_gist_consistent_int_element(TypeCacheEntry *typcache,
    1040             :                                   StrategyNumber strategy,
    1041             :                                   const RangeType *key,
    1042             :                                   Datum query)
    1043             : {
    1044         372 :     switch (strategy)
    1045             :     {
    1046         372 :         case RANGESTRAT_CONTAINS_ELEM:
    1047         372 :             return range_contains_elem_internal(typcache, key, query);
    1048           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
    1058      274266 : range_gist_consistent_leaf_range(TypeCacheEntry *typcache,
    1059             :                                  StrategyNumber strategy,
    1060             :                                  const RangeType *key,
    1061             :                                  const RangeType *query)
    1062             : {
    1063      274266 :     switch (strategy)
    1064             :     {
    1065       12460 :         case RANGESTRAT_BEFORE:
    1066       12460 :             return range_before_internal(typcache, key, query);
    1067       24510 :         case RANGESTRAT_OVERLEFT:
    1068       24510 :             return range_overleft_internal(typcache, key, query);
    1069        9654 :         case RANGESTRAT_OVERLAPS:
    1070        9654 :             return range_overlaps_internal(typcache, key, query);
    1071       54400 :         case RANGESTRAT_OVERRIGHT:
    1072       54400 :             return range_overright_internal(typcache, key, query);
    1073       49654 :         case RANGESTRAT_AFTER:
    1074       49654 :             return range_after_internal(typcache, key, query);
    1075       24510 :         case RANGESTRAT_ADJACENT:
    1076       24510 :             return range_adjacent_internal(typcache, key, query);
    1077       72082 :         case RANGESTRAT_CONTAINS:
    1078       72082 :             return range_contains_internal(typcache, key, query);
    1079       20984 :         case RANGESTRAT_CONTAINED_BY:
    1080       20984 :             return range_contained_by_internal(typcache, key, query);
    1081        6012 :         case RANGESTRAT_EQ:
    1082        6012 :             return range_eq_internal(typcache, key, query);
    1083           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
    1093      272200 : range_gist_consistent_leaf_multirange(TypeCacheEntry *typcache,
    1094             :                                       StrategyNumber strategy,
    1095             :                                       const RangeType *key,
    1096             :                                       const MultirangeType *query)
    1097             : {
    1098      272200 :     switch (strategy)
    1099             :     {
    1100       12460 :         case RANGESTRAT_BEFORE:
    1101       12460 :             return range_before_multirange_internal(typcache, key, query);
    1102       24510 :         case RANGESTRAT_OVERLEFT:
    1103       24510 :             return range_overleft_multirange_internal(typcache, key, query);
    1104       11276 :         case RANGESTRAT_OVERLAPS:
    1105       11276 :             return range_overlaps_multirange_internal(typcache, key, query);
    1106       54400 :         case RANGESTRAT_OVERRIGHT:
    1107       54400 :             return range_overright_multirange_internal(typcache, key, query);
    1108       49654 :         case RANGESTRAT_AFTER:
    1109       49654 :             return range_after_multirange_internal(typcache, key, query);
    1110       24510 :         case RANGESTRAT_ADJACENT:
    1111       24510 :             return range_adjacent_multirange_internal(typcache, key, query);
    1112       72082 :         case RANGESTRAT_CONTAINS:
    1113       72082 :             return range_contains_multirange_internal(typcache, key, query);
    1114       21538 :         case RANGESTRAT_CONTAINED_BY:
    1115       21538 :             return multirange_contains_range_internal(typcache, query, key);
    1116        1770 :         case RANGESTRAT_EQ:
    1117        1770 :             return multirange_union_range_equal(typcache, key, query);
    1118           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
    1128        7682 : range_gist_consistent_leaf_element(TypeCacheEntry *typcache,
    1129             :                                    StrategyNumber strategy,
    1130             :                                    const RangeType *key,
    1131             :                                    Datum query)
    1132             : {
    1133        7682 :     switch (strategy)
    1134             :     {
    1135        7682 :         case RANGESTRAT_CONTAINS_ELEM:
    1136        7682 :             return range_contains_elem_internal(typcache, key, query);
    1137           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
    1148          28 : range_gist_fallback_split(TypeCacheEntry *typcache,
    1149             :                           GistEntryVector *entryvec,
    1150             :                           GIST_SPLITVEC *v)
    1151             : {
    1152          28 :     RangeType  *left_range = NULL;
    1153          28 :     RangeType  *right_range = NULL;
    1154             :     OffsetNumber i,
    1155             :                 maxoff,
    1156             :                 split_idx;
    1157             : 
    1158          28 :     maxoff = entryvec->n - 1;
    1159             :     /* Split entries before this to left page, after to right: */
    1160          28 :     split_idx = (maxoff - FirstOffsetNumber) / 2 + FirstOffsetNumber;
    1161             : 
    1162          28 :     v->spl_nleft = 0;
    1163          28 :     v->spl_nright = 0;
    1164       10796 :     for (i = FirstOffsetNumber; i <= maxoff; i++)
    1165             :     {
    1166       10768 :         RangeType  *range = DatumGetRangeTypeP(entryvec->vector[i].key);
    1167             : 
    1168       10768 :         if (i < split_idx)
    1169        5364 :             PLACE_LEFT(range, i);
    1170             :         else
    1171        5404 :             PLACE_RIGHT(range, i);
    1172             :     }
    1173             : 
    1174          28 :     v->spl_ldatum = RangeTypePGetDatum(left_range);
    1175          28 :     v->spl_rdatum = RangeTypePGetDatum(right_range);
    1176          28 : }
    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          14 : range_gist_class_split(TypeCacheEntry *typcache,
    1187             :                        GistEntryVector *entryvec,
    1188             :                        GIST_SPLITVEC *v,
    1189             :                        SplitLR *classes_groups)
    1190             : {
    1191          14 :     RangeType  *left_range = NULL;
    1192          14 :     RangeType  *right_range = NULL;
    1193             :     OffsetNumber i,
    1194             :                 maxoff;
    1195             : 
    1196          14 :     maxoff = entryvec->n - 1;
    1197             : 
    1198          14 :     v->spl_nleft = 0;
    1199          14 :     v->spl_nright = 0;
    1200        4458 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    1201             :     {
    1202        4444 :         RangeType  *range = DatumGetRangeTypeP(entryvec->vector[i].key);
    1203             :         int         class;
    1204             : 
    1205             :         /* Get class of range */
    1206        4444 :         class = get_gist_range_class(range);
    1207             : 
    1208             :         /* Place range to appropriate page */
    1209        4444 :         if (classes_groups[class] == SPLIT_LEFT)
    1210        2550 :             PLACE_LEFT(range, i);
    1211             :         else
    1212             :         {
    1213             :             Assert(classes_groups[class] == SPLIT_RIGHT);
    1214        1894 :             PLACE_RIGHT(range, i);
    1215             :         }
    1216             :     }
    1217             : 
    1218          14 :     v->spl_ldatum = RangeTypePGetDatum(left_range);
    1219          14 :     v->spl_rdatum = RangeTypePGetDatum(right_range);
    1220          14 : }
    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
    1229           0 : range_gist_single_sorting_split(TypeCacheEntry *typcache,
    1230             :                                 GistEntryVector *entryvec,
    1231             :                                 GIST_SPLITVEC *v,
    1232             :                                 bool use_upper_bound)
    1233             : {
    1234             :     SingleBoundSortItem *sortItems;
    1235           0 :     RangeType  *left_range = NULL;
    1236           0 :     RangeType  *right_range = NULL;
    1237             :     OffsetNumber i,
    1238             :                 maxoff,
    1239             :                 split_idx;
    1240             : 
    1241           0 :     maxoff = entryvec->n - 1;
    1242             : 
    1243             :     sortItems = (SingleBoundSortItem *)
    1244           0 :         palloc(maxoff * sizeof(SingleBoundSortItem));
    1245             : 
    1246             :     /*
    1247             :      * Prepare auxiliary array and sort the values.
    1248             :      */
    1249           0 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    1250             :     {
    1251           0 :         RangeType  *range = DatumGetRangeTypeP(entryvec->vector[i].key);
    1252             :         RangeBound  bound2;
    1253             :         bool        empty;
    1254             : 
    1255           0 :         sortItems[i - 1].index = i;
    1256             :         /* Put appropriate bound into array */
    1257           0 :         if (use_upper_bound)
    1258           0 :             range_deserialize(typcache, range, &bound2,
    1259           0 :                               &sortItems[i - 1].bound, &empty);
    1260             :         else
    1261           0 :             range_deserialize(typcache, range, &sortItems[i - 1].bound,
    1262             :                               &bound2, &empty);
    1263             :         Assert(!empty);
    1264             :     }
    1265             : 
    1266           0 :     qsort_arg(sortItems, maxoff, sizeof(SingleBoundSortItem),
    1267             :               single_bound_cmp, typcache);
    1268             : 
    1269           0 :     split_idx = maxoff / 2;
    1270             : 
    1271           0 :     v->spl_nleft = 0;
    1272           0 :     v->spl_nright = 0;
    1273             : 
    1274           0 :     for (i = 0; i < maxoff; i++)
    1275             :     {
    1276           0 :         int         idx = sortItems[i].index;
    1277           0 :         RangeType  *range = DatumGetRangeTypeP(entryvec->vector[idx].key);
    1278             : 
    1279           0 :         if (i < split_idx)
    1280           0 :             PLACE_LEFT(range, idx);
    1281             :         else
    1282           0 :             PLACE_RIGHT(range, idx);
    1283             :     }
    1284             : 
    1285           0 :     v->spl_ldatum = RangeTypePGetDatum(left_range);
    1286           0 :     v->spl_rdatum = RangeTypePGetDatum(right_range);
    1287           0 : }
    1288             : 
    1289             : /*
    1290             :  * Double sorting split algorithm.
    1291             :  *
    1292             :  * The algorithm considers dividing ranges into two groups. The first (left)
    1293             :  * group contains general left bound. The second (right) group contains
    1294             :  * general right bound. The challenge is to find upper bound of left group
    1295             :  * and lower bound of right group so that overlap of groups is minimal and
    1296             :  * ratio of distribution is acceptable. Algorithm finds for each lower bound of
    1297             :  * right group minimal upper bound of left group, and for each upper bound of
    1298             :  * left group maximal lower bound of right group. For each found pair
    1299             :  * range_gist_consider_split considers replacement of currently selected
    1300             :  * split with the new one.
    1301             :  *
    1302             :  * After that, all the entries are divided into three groups:
    1303             :  * 1) Entries which should be placed to the left group
    1304             :  * 2) Entries which should be placed to the right group
    1305             :  * 3) "Common entries" which can be placed to either group without affecting
    1306             :  *    amount of overlap.
    1307             :  *
    1308             :  * The common ranges are distributed by difference of distance from lower
    1309             :  * bound of common range to lower bound of right group and distance from upper
    1310             :  * bound of common range to upper bound of left group.
    1311             :  *
    1312             :  * For details see:
    1313             :  * "A new double sorting-based node splitting algorithm for R-tree",
    1314             :  * A. Korotkov
    1315             :  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
    1316             :  */
    1317             : static void
    1318         318 : range_gist_double_sorting_split(TypeCacheEntry *typcache,
    1319             :                                 GistEntryVector *entryvec,
    1320             :                                 GIST_SPLITVEC *v)
    1321             : {
    1322             :     ConsiderSplitContext context;
    1323             :     OffsetNumber i,
    1324             :                 maxoff;
    1325             :     RangeType  *range,
    1326         318 :                *left_range = NULL,
    1327         318 :                *right_range = NULL;
    1328             :     int         common_entries_count;
    1329             :     NonEmptyRange *by_lower,
    1330             :                *by_upper;
    1331             :     CommonEntry *common_entries;
    1332             :     int         nentries,
    1333             :                 i1,
    1334             :                 i2;
    1335             :     RangeBound *right_lower,
    1336             :                *left_upper;
    1337             : 
    1338         318 :     memset(&context, 0, sizeof(ConsiderSplitContext));
    1339         318 :     context.typcache = typcache;
    1340         318 :     context.has_subtype_diff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
    1341             : 
    1342         318 :     maxoff = entryvec->n - 1;
    1343         318 :     nentries = context.entries_count = maxoff - FirstOffsetNumber + 1;
    1344         318 :     context.first = true;
    1345             : 
    1346             :     /* Allocate arrays for sorted range bounds */
    1347         318 :     by_lower = (NonEmptyRange *) palloc(nentries * sizeof(NonEmptyRange));
    1348         318 :     by_upper = (NonEmptyRange *) palloc(nentries * sizeof(NonEmptyRange));
    1349             : 
    1350             :     /* Fill arrays of bounds */
    1351       86754 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    1352             :     {
    1353       86436 :         RangeType  *range = DatumGetRangeTypeP(entryvec->vector[i].key);
    1354             :         bool        empty;
    1355             : 
    1356      172872 :         range_deserialize(typcache, range,
    1357       86436 :                           &by_lower[i - FirstOffsetNumber].lower,
    1358       86436 :                           &by_lower[i - FirstOffsetNumber].upper,
    1359             :                           &empty);
    1360             :         Assert(!empty);
    1361             :     }
    1362             : 
    1363             :     /*
    1364             :      * Make two arrays of range bounds: one sorted by lower bound and another
    1365             :      * sorted by upper bound.
    1366             :      */
    1367         318 :     memcpy(by_upper, by_lower, nentries * sizeof(NonEmptyRange));
    1368         318 :     qsort_arg(by_lower, nentries, sizeof(NonEmptyRange),
    1369             :               interval_cmp_lower, typcache);
    1370         318 :     qsort_arg(by_upper, nentries, sizeof(NonEmptyRange),
    1371             :               interval_cmp_upper, typcache);
    1372             : 
    1373             :     /*----------
    1374             :      * The goal is to form a left and right range, so that every entry
    1375             :      * range is contained by either left or right interval (or both).
    1376             :      *
    1377             :      * For example, with the ranges (0,1), (1,3), (2,3), (2,4):
    1378             :      *
    1379             :      * 0 1 2 3 4
    1380             :      * +-+
    1381             :      *   +---+
    1382             :      *     +-+
    1383             :      *     +---+
    1384             :      *
    1385             :      * The left and right ranges are of the form (0,a) and (b,4).
    1386             :      * We first consider splits where b is the lower bound of an entry.
    1387             :      * We iterate through all entries, and for each b, calculate the
    1388             :      * smallest possible a. Then we consider splits where a is the
    1389             :      * upper bound of an entry, and for each a, calculate the greatest
    1390             :      * possible b.
    1391             :      *
    1392             :      * In the above example, the first loop would consider splits:
    1393             :      * b=0: (0,1)-(0,4)
    1394             :      * b=1: (0,1)-(1,4)
    1395             :      * b=2: (0,3)-(2,4)
    1396             :      *
    1397             :      * And the second loop:
    1398             :      * a=1: (0,1)-(1,4)
    1399             :      * a=3: (0,3)-(2,4)
    1400             :      * a=4: (0,4)-(2,4)
    1401             :      *----------
    1402             :      */
    1403             : 
    1404             :     /*
    1405             :      * Iterate over lower bound of right group, finding smallest possible
    1406             :      * upper bound of left group.
    1407             :      */
    1408         318 :     i1 = 0;
    1409         318 :     i2 = 0;
    1410         318 :     right_lower = &by_lower[i1].lower;
    1411         318 :     left_upper = &by_upper[i2].lower;
    1412             :     while (true)
    1413             :     {
    1414             :         /*
    1415             :          * Find next lower bound of right group.
    1416             :          */
    1417      343238 :         while (i1 < nentries &&
    1418      171460 :                range_cmp_bounds(typcache, right_lower,
    1419      171460 :                                 &by_lower[i1].lower) == 0)
    1420             :         {
    1421       86436 :             if (range_cmp_bounds(typcache, &by_lower[i1].upper,
    1422             :                                  left_upper) > 0)
    1423       73366 :                 left_upper = &by_lower[i1].upper;
    1424       86436 :             i1++;
    1425             :         }
    1426       85342 :         if (i1 >= nentries)
    1427         318 :             break;
    1428       85024 :         right_lower = &by_lower[i1].lower;
    1429             : 
    1430             :         /*
    1431             :          * Find count of ranges which anyway should be placed to the left
    1432             :          * group.
    1433             :          */
    1434      330578 :         while (i2 < nentries &&
    1435      159298 :                range_cmp_bounds(typcache, &by_upper[i2].upper,
    1436             :                                 left_upper) <= 0)
    1437       86256 :             i2++;
    1438             : 
    1439             :         /*
    1440             :          * Consider found split to see if it's better than what we had.
    1441             :          */
    1442       85024 :         range_gist_consider_split(&context, right_lower, i1, left_upper, i2);
    1443             :     }
    1444             : 
    1445             :     /*
    1446             :      * Iterate over upper bound of left group finding greatest possible lower
    1447             :      * bound of right group.
    1448             :      */
    1449         318 :     i1 = nentries - 1;
    1450         318 :     i2 = nentries - 1;
    1451         318 :     right_lower = &by_lower[i1].upper;
    1452         318 :     left_upper = &by_upper[i2].upper;
    1453             :     while (true)
    1454             :     {
    1455             :         /*
    1456             :          * Find next upper bound of left group.
    1457             :          */
    1458      345426 :         while (i2 >= 0 &&
    1459      172554 :                range_cmp_bounds(typcache, left_upper,
    1460      172554 :                                 &by_upper[i2].upper) == 0)
    1461             :         {
    1462       86436 :             if (range_cmp_bounds(typcache, &by_upper[i2].lower,
    1463             :                                  right_lower) < 0)
    1464       73360 :                 right_lower = &by_upper[i2].lower;
    1465       86436 :             i2--;
    1466             :         }
    1467       86436 :         if (i2 < 0)
    1468         318 :             break;
    1469       86118 :         left_upper = &by_upper[i2].upper;
    1470             : 
    1471             :         /*
    1472             :          * Find count of intervals which anyway should be placed to the right
    1473             :          * group.
    1474             :          */
    1475      331672 :         while (i1 >= 0 &&
    1476      159298 :                range_cmp_bounds(typcache, &by_lower[i1].lower,
    1477             :                                 right_lower) >= 0)
    1478       86256 :             i1--;
    1479             : 
    1480             :         /*
    1481             :          * Consider found split to see if it's better than what we had.
    1482             :          */
    1483       86118 :         range_gist_consider_split(&context, right_lower, i1 + 1,
    1484             :                                   left_upper, i2 + 1);
    1485             :     }
    1486             : 
    1487             :     /*
    1488             :      * If we failed to find any acceptable splits, use trivial split.
    1489             :      */
    1490         318 :     if (context.first)
    1491             :     {
    1492           0 :         range_gist_fallback_split(typcache, entryvec, v);
    1493           0 :         return;
    1494             :     }
    1495             : 
    1496             :     /*
    1497             :      * Ok, we have now selected bounds of the groups. Now we have to
    1498             :      * distribute entries themselves. At first we distribute entries which can
    1499             :      * be placed unambiguously and collect "common entries" to array.
    1500             :      */
    1501             : 
    1502             :     /* Allocate vectors for results */
    1503         318 :     v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
    1504         318 :     v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
    1505         318 :     v->spl_nleft = 0;
    1506         318 :     v->spl_nright = 0;
    1507             : 
    1508             :     /*
    1509             :      * Allocate an array for "common entries" - entries which can be placed to
    1510             :      * either group without affecting overlap along selected axis.
    1511             :      */
    1512         318 :     common_entries_count = 0;
    1513         318 :     common_entries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
    1514             : 
    1515             :     /*
    1516             :      * Distribute entries which can be distributed unambiguously, and collect
    1517             :      * common entries.
    1518             :      */
    1519       86754 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    1520             :     {
    1521             :         RangeBound  lower,
    1522             :                     upper;
    1523             :         bool        empty;
    1524             : 
    1525             :         /*
    1526             :          * Get upper and lower bounds along selected axis.
    1527             :          */
    1528       86436 :         range = DatumGetRangeTypeP(entryvec->vector[i].key);
    1529             : 
    1530       86436 :         range_deserialize(typcache, range, &lower, &upper, &empty);
    1531             : 
    1532       86436 :         if (range_cmp_bounds(typcache, &upper, context.left_upper) <= 0)
    1533             :         {
    1534             :             /* Fits in the left group */
    1535       39802 :             if (range_cmp_bounds(typcache, &lower, context.right_lower) >= 0)
    1536             :             {
    1537             :                 /* Fits also in the right group, so "common entry" */
    1538        7964 :                 common_entries[common_entries_count].index = i;
    1539        7964 :                 if (context.has_subtype_diff)
    1540             :                 {
    1541             :                     /*
    1542             :                      * delta = (lower - context.right_lower) -
    1543             :                      * (context.left_upper - upper)
    1544             :                      */
    1545       15928 :                     common_entries[common_entries_count].delta =
    1546        7964 :                         call_subtype_diff(typcache,
    1547             :                                           lower.val,
    1548       15928 :                                           context.right_lower->val) -
    1549       15928 :                         call_subtype_diff(typcache,
    1550        7964 :                                           context.left_upper->val,
    1551             :                                           upper.val);
    1552             :                 }
    1553             :                 else
    1554             :                 {
    1555             :                     /* Without subtype_diff, take all deltas as zero */
    1556           0 :                     common_entries[common_entries_count].delta = 0;
    1557             :                 }
    1558        7964 :                 common_entries_count++;
    1559             :             }
    1560             :             else
    1561             :             {
    1562             :                 /* Doesn't fit to the right group, so join to the left group */
    1563       31838 :                 PLACE_LEFT(range, i);
    1564             :             }
    1565             :         }
    1566             :         else
    1567             :         {
    1568             :             /*
    1569             :              * Each entry should fit on either left or right group. Since this
    1570             :              * entry didn't fit in the left group, it better fit in the right
    1571             :              * group.
    1572             :              */
    1573             :             Assert(range_cmp_bounds(typcache, &lower,
    1574             :                                     context.right_lower) >= 0);
    1575       46634 :             PLACE_RIGHT(range, i);
    1576             :         }
    1577             :     }
    1578             : 
    1579             :     /*
    1580             :      * Distribute "common entries", if any.
    1581             :      */
    1582         318 :     if (common_entries_count > 0)
    1583             :     {
    1584             :         /*
    1585             :          * Sort "common entries" by calculated deltas in order to distribute
    1586             :          * the most ambiguous entries first.
    1587             :          */
    1588         138 :         qsort(common_entries, common_entries_count, sizeof(CommonEntry),
    1589             :               common_entry_cmp);
    1590             : 
    1591             :         /*
    1592             :          * Distribute "common entries" between groups according to sorting.
    1593             :          */
    1594        8102 :         for (i = 0; i < common_entries_count; i++)
    1595             :         {
    1596        7964 :             int         idx = common_entries[i].index;
    1597             : 
    1598        7964 :             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             :              */
    1604        7964 :             if (i < context.common_left)
    1605           0 :                 PLACE_LEFT(range, idx);
    1606             :             else
    1607        7964 :                 PLACE_RIGHT(range, idx);
    1608             :         }
    1609             :     }
    1610             : 
    1611         318 :     v->spl_ldatum = PointerGetDatum(left_range);
    1612         318 :     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      171142 : 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      171142 :     if (min_left_count >= (context->entries_count + 1) / 2)
    1634       75482 :         left_count = min_left_count;
    1635       95660 :     else if (max_left_count <= context->entries_count / 2)
    1636       74866 :         left_count = max_left_count;
    1637             :     else
    1638       20794 :         left_count = context->entries_count / 2;
    1639      171142 :     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      171142 :     ratio = ((float4) Min(left_count, right_count)) /
    1647      171142 :         ((float4) context->entries_count);
    1648             : 
    1649      171142 :     if (ratio > LIMIT_RATIO)
    1650             :     {
    1651       83986 :         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       83986 :         if (context->has_subtype_diff)
    1661       83986 :             overlap = call_subtype_diff(context->typcache,
    1662             :                                         left_upper->val,
    1663             :                                         right_lower->val);
    1664             :         else
    1665           0 :             overlap = max_left_count - min_left_count;
    1666             : 
    1667             :         /* If there is no previous selection, select this split */
    1668       83986 :         if (context->first)
    1669         318 :             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       83668 :             if (overlap < context->overlap ||
    1677       74396 :                 (overlap == context->overlap && ratio > context->ratio))
    1678       23188 :                 selectthis = true;
    1679             :         }
    1680             : 
    1681       83986 :         if (selectthis)
    1682             :         {
    1683             :             /* save information about selected split */
    1684       23506 :             context->first = false;
    1685       23506 :             context->ratio = ratio;
    1686       23506 :             context->overlap = overlap;
    1687       23506 :             context->right_lower = right_lower;
    1688       23506 :             context->left_upper = left_upper;
    1689       23506 :             context->common_left = max_left_count - left_count;
    1690       23506 :             context->common_right = left_count - min_left_count;
    1691             :         }
    1692             :     }
    1693      171142 : }
    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      106092 : get_gist_range_class(RangeType *range)
    1704             : {
    1705             :     int         classNumber;
    1706             :     char        flags;
    1707             : 
    1708      106092 :     flags = range_get_flags(range);
    1709      106092 :     if (flags & RANGE_EMPTY)
    1710             :     {
    1711       15344 :         classNumber = CLS_EMPTY;
    1712             :     }
    1713             :     else
    1714             :     {
    1715       90748 :         classNumber = 0;
    1716       90748 :         if (flags & RANGE_LB_INF)
    1717         400 :             classNumber |= CLS_LOWER_INF;
    1718       90748 :         if (flags & RANGE_UB_INF)
    1719         124 :             classNumber |= CLS_UPPER_INF;
    1720       90748 :         if (flags & RANGE_CONTAIN_EMPTY)
    1721           0 :             classNumber |= CLS_CONTAIN_EMPTY;
    1722             :     }
    1723      106092 :     return classNumber;
    1724             : }
    1725             : 
    1726             : /*
    1727             :  * Comparison function for range_gist_single_sorting_split.
    1728             :  */
    1729             : static int
    1730           0 : single_bound_cmp(const void *a, const void *b, void *arg)
    1731             : {
    1732           0 :     SingleBoundSortItem *i1 = (SingleBoundSortItem *) a;
    1733           0 :     SingleBoundSortItem *i2 = (SingleBoundSortItem *) b;
    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
    1743      342722 : interval_cmp_lower(const void *a, const void *b, void *arg)
    1744             : {
    1745      342722 :     NonEmptyRange *i1 = (NonEmptyRange *) a;
    1746      342722 :     NonEmptyRange *i2 = (NonEmptyRange *) b;
    1747      342722 :     TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
    1748             : 
    1749      342722 :     return range_cmp_bounds(typcache, &i1->lower, &i2->lower);
    1750             : }
    1751             : 
    1752             : /*
    1753             :  * Compare NonEmptyRanges by upper bound.
    1754             :  */
    1755             : static int
    1756      325674 : interval_cmp_upper(const void *a, const void *b, void *arg)
    1757             : {
    1758      325674 :     NonEmptyRange *i1 = (NonEmptyRange *) a;
    1759      325674 :     NonEmptyRange *i2 = (NonEmptyRange *) b;
    1760      325674 :     TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
    1761             : 
    1762      325674 :     return range_cmp_bounds(typcache, &i1->upper, &i2->upper);
    1763             : }
    1764             : 
    1765             : /*
    1766             :  * Compare CommonEntrys by their deltas.
    1767             :  */
    1768             : static int
    1769        7826 : common_entry_cmp(const void *i1, const void *i2)
    1770             : {
    1771        7826 :     double      delta1 = ((CommonEntry *) i1)->delta;
    1772        7826 :     double      delta2 = ((CommonEntry *) i2)->delta;
    1773             : 
    1774        7826 :     if (delta1 < delta2)
    1775        7826 :         return -1;
    1776           0 :     else if (delta1 > delta2)
    1777           0 :         return 1;
    1778             :     else
    1779           0 :         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      753418 : call_subtype_diff(TypeCacheEntry *typcache, Datum val1, Datum val2)
    1788             : {
    1789             :     float8      value;
    1790             : 
    1791      753418 :     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      753418 :     if (value >= 0.0)
    1796      753418 :         return value;
    1797           0 :     return 0.0;
    1798             : }

Generated by: LCOV version 1.13