LCOV - code coverage report
Current view: top level - src/backend/utils/adt - multirangetypes_selfuncs.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 297 360 82.5 %
Date: 2023-12-10 05:11:07 Functions: 13 13 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * multirangetypes_selfuncs.c
       4             :  *    Functions for selectivity estimation of multirange operators
       5             :  *
       6             :  * Estimates are based on histograms of lower and upper bounds, and the
       7             :  * fraction of empty multiranges.
       8             :  *
       9             :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
      10             :  * Portions Copyright (c) 1994, Regents of the University of California
      11             :  *
      12             :  *
      13             :  * IDENTIFICATION
      14             :  *    src/backend/utils/adt/multirangetypes_selfuncs.c
      15             :  *
      16             :  *-------------------------------------------------------------------------
      17             :  */
      18             : #include "postgres.h"
      19             : 
      20             : #include <math.h>
      21             : 
      22             : #include "access/htup_details.h"
      23             : #include "catalog/pg_operator.h"
      24             : #include "catalog/pg_statistic.h"
      25             : #include "catalog/pg_type.h"
      26             : #include "utils/float.h"
      27             : #include "utils/fmgrprotos.h"
      28             : #include "utils/lsyscache.h"
      29             : #include "utils/rangetypes.h"
      30             : #include "utils/multirangetypes.h"
      31             : #include "utils/selfuncs.h"
      32             : #include "utils/typcache.h"
      33             : 
      34             : static double calc_multirangesel(TypeCacheEntry *typcache,
      35             :                                  VariableStatData *vardata,
      36             :                                  const MultirangeType *constval, Oid operator);
      37             : static double default_multirange_selectivity(Oid operator);
      38             : static double calc_hist_selectivity(TypeCacheEntry *typcache,
      39             :                                     VariableStatData *vardata,
      40             :                                     const MultirangeType *constval,
      41             :                                     Oid operator);
      42             : static double calc_hist_selectivity_scalar(TypeCacheEntry *typcache,
      43             :                                            const RangeBound *constbound,
      44             :                                            const RangeBound *hist,
      45             :                                            int hist_nvalues, bool equal);
      46             : static int  rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value,
      47             :                            const RangeBound *hist, int hist_length, bool equal);
      48             : static float8 get_position(TypeCacheEntry *typcache, const RangeBound *value,
      49             :                            const RangeBound *hist1, const RangeBound *hist2);
      50             : static float8 get_len_position(double value, double hist1, double hist2);
      51             : static float8 get_distance(TypeCacheEntry *typcache, const RangeBound *bound1,
      52             :                            const RangeBound *bound2);
      53             : static int  length_hist_bsearch(Datum *length_hist_values,
      54             :                                 int length_hist_nvalues, double value,
      55             :                                 bool equal);
      56             : static double calc_length_hist_frac(Datum *length_hist_values,
      57             :                                     int length_hist_nvalues, double length1,
      58             :                                     double length2, bool equal);
      59             : static double calc_hist_selectivity_contained(TypeCacheEntry *typcache,
      60             :                                               const RangeBound *lower,
      61             :                                               RangeBound *upper,
      62             :                                               const RangeBound *hist_lower,
      63             :                                               int hist_nvalues,
      64             :                                               Datum *length_hist_values,
      65             :                                               int length_hist_nvalues);
      66             : static double calc_hist_selectivity_contains(TypeCacheEntry *typcache,
      67             :                                              const RangeBound *lower,
      68             :                                              const RangeBound *upper,
      69             :                                              const RangeBound *hist_lower,
      70             :                                              int hist_nvalues,
      71             :                                              Datum *length_hist_values,
      72             :                                              int length_hist_nvalues);
      73             : 
      74             : /*
      75             :  * Returns a default selectivity estimate for given operator, when we don't
      76             :  * have statistics or cannot use them for some reason.
      77             :  */
      78             : static double
      79         192 : default_multirange_selectivity(Oid operator)
      80             : {
      81         192 :     switch (operator)
      82             :     {
      83          18 :         case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
      84             :         case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
      85             :         case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
      86          18 :             return 0.01;
      87             : 
      88          54 :         case OID_RANGE_CONTAINS_MULTIRANGE_OP:
      89             :         case OID_RANGE_MULTIRANGE_CONTAINED_OP:
      90             :         case OID_MULTIRANGE_CONTAINS_RANGE_OP:
      91             :         case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
      92             :         case OID_MULTIRANGE_RANGE_CONTAINED_OP:
      93             :         case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
      94          54 :             return 0.005;
      95             : 
      96           0 :         case OID_MULTIRANGE_CONTAINS_ELEM_OP:
      97             :         case OID_MULTIRANGE_ELEM_CONTAINED_OP:
      98             : 
      99             :             /*
     100             :              * "multirange @> elem" is more or less identical to a scalar
     101             :              * inequality "A >= b AND A <= c".
     102             :              */
     103           0 :             return DEFAULT_MULTIRANGE_INEQ_SEL;
     104             : 
     105         120 :         case OID_MULTIRANGE_LESS_OP:
     106             :         case OID_MULTIRANGE_LESS_EQUAL_OP:
     107             :         case OID_MULTIRANGE_GREATER_OP:
     108             :         case OID_MULTIRANGE_GREATER_EQUAL_OP:
     109             :         case OID_MULTIRANGE_LEFT_RANGE_OP:
     110             :         case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
     111             :         case OID_RANGE_LEFT_MULTIRANGE_OP:
     112             :         case OID_MULTIRANGE_RIGHT_RANGE_OP:
     113             :         case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
     114             :         case OID_RANGE_RIGHT_MULTIRANGE_OP:
     115             :         case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
     116             :         case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
     117             :         case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
     118             :         case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
     119             :         case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
     120             :         case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
     121             :             /* these are similar to regular scalar inequalities */
     122         120 :             return DEFAULT_INEQ_SEL;
     123             : 
     124           0 :         default:
     125             : 
     126             :             /*
     127             :              * all multirange operators should be handled above, but just in
     128             :              * case
     129             :              */
     130           0 :             return 0.01;
     131             :     }
     132             : }
     133             : 
     134             : /*
     135             :  * multirangesel -- restriction selectivity for multirange operators
     136             :  */
     137             : Datum
     138         666 : multirangesel(PG_FUNCTION_ARGS)
     139             : {
     140         666 :     PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
     141         666 :     Oid         operator = PG_GETARG_OID(1);
     142         666 :     List       *args = (List *) PG_GETARG_POINTER(2);
     143         666 :     int         varRelid = PG_GETARG_INT32(3);
     144             :     VariableStatData vardata;
     145             :     Node       *other;
     146             :     bool        varonleft;
     147             :     Selectivity selec;
     148         666 :     TypeCacheEntry *typcache = NULL;
     149         666 :     MultirangeType *constmultirange = NULL;
     150         666 :     RangeType  *constrange = NULL;
     151             : 
     152             :     /*
     153             :      * If expression is not (variable op something) or (something op
     154             :      * variable), then punt and return a default estimate.
     155             :      */
     156         666 :     if (!get_restriction_variable(root, args, varRelid,
     157             :                                   &vardata, &other, &varonleft))
     158           0 :         PG_RETURN_FLOAT8(default_multirange_selectivity(operator));
     159             : 
     160             :     /*
     161             :      * Can't do anything useful if the something is not a constant, either.
     162             :      */
     163         666 :     if (!IsA(other, Const))
     164             :     {
     165           0 :         ReleaseVariableStats(vardata);
     166           0 :         PG_RETURN_FLOAT8(default_multirange_selectivity(operator));
     167             :     }
     168             : 
     169             :     /*
     170             :      * All the multirange operators are strict, so we can cope with a NULL
     171             :      * constant right away.
     172             :      */
     173         666 :     if (((Const *) other)->constisnull)
     174             :     {
     175           0 :         ReleaseVariableStats(vardata);
     176           0 :         PG_RETURN_FLOAT8(0.0);
     177             :     }
     178             : 
     179             :     /*
     180             :      * If var is on the right, commute the operator, so that we can assume the
     181             :      * var is on the left in what follows.
     182             :      */
     183         666 :     if (!varonleft)
     184             :     {
     185             :         /* we have other Op var, commute to make var Op other */
     186          24 :         operator = get_commutator(operator);
     187          24 :         if (!operator)
     188             :         {
     189             :             /* Use default selectivity (should we raise an error instead?) */
     190           0 :             ReleaseVariableStats(vardata);
     191           0 :             PG_RETURN_FLOAT8(default_multirange_selectivity(operator));
     192             :         }
     193             :     }
     194             : 
     195             :     /*
     196             :      * OK, there's a Var and a Const we're dealing with here.  We need the
     197             :      * Const to be of same multirange type as the column, else we can't do
     198             :      * anything useful. (Such cases will likely fail at runtime, but here we'd
     199             :      * rather just return a default estimate.)
     200             :      *
     201             :      * If the operator is "multirange @> element", the constant should be of
     202             :      * the element type of the multirange column. Convert it to a multirange
     203             :      * that includes only that single point, so that we don't need special
     204             :      * handling for that in what follows.
     205             :      */
     206         666 :     if (operator == OID_MULTIRANGE_CONTAINS_ELEM_OP)
     207             :     {
     208          30 :         typcache = multirange_get_typcache(fcinfo, vardata.vartype);
     209             : 
     210          30 :         if (((Const *) other)->consttype == typcache->rngtype->rngelemtype->type_id)
     211             :         {
     212             :             RangeBound  lower,
     213             :                         upper;
     214             : 
     215          30 :             lower.inclusive = true;
     216          30 :             lower.val = ((Const *) other)->constvalue;
     217          30 :             lower.infinite = false;
     218          30 :             lower.lower = true;
     219          30 :             upper.inclusive = true;
     220          30 :             upper.val = ((Const *) other)->constvalue;
     221          30 :             upper.infinite = false;
     222          30 :             upper.lower = false;
     223          30 :             constrange = range_serialize(typcache->rngtype, &lower, &upper,
     224             :                                          false, NULL);
     225          30 :             constmultirange = make_multirange(typcache->type_id, typcache->rngtype,
     226             :                                               1, &constrange);
     227             :         }
     228             :     }
     229         636 :     else if (operator == OID_RANGE_MULTIRANGE_CONTAINED_OP ||
     230         570 :              operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
     231         534 :              operator == OID_MULTIRANGE_OVERLAPS_RANGE_OP ||
     232         510 :              operator == OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP ||
     233         486 :              operator == OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP ||
     234         462 :              operator == OID_MULTIRANGE_LEFT_RANGE_OP ||
     235             :              operator == OID_MULTIRANGE_RIGHT_RANGE_OP)
     236             :     {
     237             :         /*
     238             :          * Promote a range in "multirange OP range" just like we do an element
     239             :          * in "multirange OP element".
     240             :          */
     241         198 :         typcache = multirange_get_typcache(fcinfo, vardata.vartype);
     242         198 :         if (((Const *) other)->consttype == typcache->rngtype->type_id)
     243             :         {
     244         198 :             constrange = DatumGetRangeTypeP(((Const *) other)->constvalue);
     245         198 :             constmultirange = make_multirange(typcache->type_id, typcache->rngtype,
     246             :                                               1, &constrange);
     247             :         }
     248             :     }
     249         438 :     else if (operator == OID_RANGE_OVERLAPS_MULTIRANGE_OP ||
     250         402 :              operator == OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP ||
     251         384 :              operator == OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP ||
     252         366 :              operator == OID_RANGE_LEFT_MULTIRANGE_OP ||
     253         348 :              operator == OID_RANGE_RIGHT_MULTIRANGE_OP ||
     254         312 :              operator == OID_RANGE_CONTAINS_MULTIRANGE_OP ||
     255         312 :              operator == OID_MULTIRANGE_ELEM_CONTAINED_OP ||
     256             :              operator == OID_MULTIRANGE_RANGE_CONTAINED_OP)
     257             :     {
     258             :         /*
     259             :          * Here, the Var is the elem/range, not the multirange.  For now we
     260             :          * just punt and return the default estimate.  In future we could
     261             :          * disassemble the multirange constant to do something more
     262             :          * intelligent.
     263             :          */
     264             :     }
     265         294 :     else if (((Const *) other)->consttype == vardata.vartype)
     266             :     {
     267             :         /* Both sides are the same multirange type */
     268         294 :         typcache = multirange_get_typcache(fcinfo, vardata.vartype);
     269             : 
     270         294 :         constmultirange = DatumGetMultirangeTypeP(((Const *) other)->constvalue);
     271             :     }
     272             : 
     273             :     /*
     274             :      * If we got a valid constant on one side of the operator, proceed to
     275             :      * estimate using statistics. Otherwise punt and return a default constant
     276             :      * estimate.  Note that calc_multirangesel need not handle
     277             :      * OID_MULTIRANGE_*_CONTAINED_OP.
     278             :      */
     279         666 :     if (constmultirange)
     280         522 :         selec = calc_multirangesel(typcache, &vardata, constmultirange, operator);
     281             :     else
     282         144 :         selec = default_multirange_selectivity(operator);
     283             : 
     284         666 :     ReleaseVariableStats(vardata);
     285             : 
     286         666 :     CLAMP_PROBABILITY(selec);
     287             : 
     288         666 :     PG_RETURN_FLOAT8((float8) selec);
     289             : }
     290             : 
     291             : static double
     292         522 : calc_multirangesel(TypeCacheEntry *typcache, VariableStatData *vardata,
     293             :                    const MultirangeType *constval, Oid operator)
     294             : {
     295             :     double      hist_selec;
     296             :     double      selec;
     297             :     float4      empty_frac,
     298             :                 null_frac;
     299             : 
     300             :     /*
     301             :      * First look up the fraction of NULLs and empty multiranges from
     302             :      * pg_statistic.
     303             :      */
     304         522 :     if (HeapTupleIsValid(vardata->statsTuple))
     305             :     {
     306             :         Form_pg_statistic stats;
     307             :         AttStatsSlot sslot;
     308             : 
     309         450 :         stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
     310         450 :         null_frac = stats->stanullfrac;
     311             : 
     312             :         /* Try to get fraction of empty multiranges */
     313         450 :         if (get_attstatsslot(&sslot, vardata->statsTuple,
     314             :                              STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
     315             :                              InvalidOid,
     316             :                              ATTSTATSSLOT_NUMBERS))
     317             :         {
     318         450 :             if (sslot.nnumbers != 1)
     319           0 :                 elog(ERROR, "invalid empty fraction statistic");  /* shouldn't happen */
     320         450 :             empty_frac = sslot.numbers[0];
     321         450 :             free_attstatsslot(&sslot);
     322             :         }
     323             :         else
     324             :         {
     325             :             /* No empty fraction statistic. Assume no empty ranges. */
     326           0 :             empty_frac = 0.0;
     327             :         }
     328             :     }
     329             :     else
     330             :     {
     331             :         /*
     332             :          * No stats are available. Follow through the calculations below
     333             :          * anyway, assuming no NULLs and no empty multiranges. This still
     334             :          * allows us to give a better-than-nothing estimate based on whether
     335             :          * the constant is an empty multirange or not.
     336             :          */
     337          72 :         null_frac = 0.0;
     338          72 :         empty_frac = 0.0;
     339             :     }
     340             : 
     341         522 :     if (MultirangeIsEmpty(constval))
     342             :     {
     343             :         /*
     344             :          * An empty multirange matches all multiranges, all empty multiranges,
     345             :          * or nothing, depending on the operator
     346             :          */
     347         222 :         switch (operator)
     348             :         {
     349             :                 /* these return false if either argument is empty */
     350         126 :             case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
     351             :             case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
     352             :             case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
     353             :             case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
     354             :             case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
     355             :             case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
     356             :             case OID_MULTIRANGE_LEFT_RANGE_OP:
     357             :             case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
     358             :             case OID_MULTIRANGE_RIGHT_RANGE_OP:
     359             :             case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
     360             :                 /* nothing is less than an empty multirange */
     361             :             case OID_MULTIRANGE_LESS_OP:
     362         126 :                 selec = 0.0;
     363         126 :                 break;
     364             : 
     365             :                 /*
     366             :                  * only empty multiranges can be contained by an empty
     367             :                  * multirange
     368             :                  */
     369          30 :             case OID_RANGE_MULTIRANGE_CONTAINED_OP:
     370             :             case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
     371             :                 /* only empty ranges are <= an empty multirange */
     372             :             case OID_MULTIRANGE_LESS_EQUAL_OP:
     373          30 :                 selec = empty_frac;
     374          30 :                 break;
     375             : 
     376             :                 /* everything contains an empty multirange */
     377          60 :             case OID_MULTIRANGE_CONTAINS_RANGE_OP:
     378             :             case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
     379             :                 /* everything is >= an empty multirange */
     380             :             case OID_MULTIRANGE_GREATER_EQUAL_OP:
     381          60 :                 selec = 1.0;
     382          60 :                 break;
     383             : 
     384             :                 /* all non-empty multiranges are > an empty multirange */
     385           6 :             case OID_MULTIRANGE_GREATER_OP:
     386           6 :                 selec = 1.0 - empty_frac;
     387           6 :                 break;
     388             : 
     389             :                 /* an element cannot be empty */
     390           0 :             case OID_MULTIRANGE_CONTAINS_ELEM_OP:
     391             : 
     392             :                 /* filtered out by multirangesel() */
     393             :             case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
     394             :             case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
     395             :             case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
     396             :             case OID_RANGE_LEFT_MULTIRANGE_OP:
     397             :             case OID_RANGE_RIGHT_MULTIRANGE_OP:
     398             :             case OID_RANGE_CONTAINS_MULTIRANGE_OP:
     399             :             case OID_MULTIRANGE_ELEM_CONTAINED_OP:
     400             :             case OID_MULTIRANGE_RANGE_CONTAINED_OP:
     401             : 
     402             :             default:
     403           0 :                 elog(ERROR, "unexpected operator %u", operator);
     404             :                 selec = 0.0;    /* keep compiler quiet */
     405             :                 break;
     406             :         }
     407             :     }
     408             :     else
     409             :     {
     410             :         /*
     411             :          * Calculate selectivity using bound histograms. If that fails for
     412             :          * some reason, e.g no histogram in pg_statistic, use the default
     413             :          * constant estimate for the fraction of non-empty values. This is
     414             :          * still somewhat better than just returning the default estimate,
     415             :          * because this still takes into account the fraction of empty and
     416             :          * NULL tuples, if we had statistics for them.
     417             :          */
     418         300 :         hist_selec = calc_hist_selectivity(typcache, vardata, constval,
     419             :                                            operator);
     420         300 :         if (hist_selec < 0.0)
     421          48 :             hist_selec = default_multirange_selectivity(operator);
     422             : 
     423             :         /*
     424             :          * Now merge the results for the empty multiranges and histogram
     425             :          * calculations, realizing that the histogram covers only the
     426             :          * non-null, non-empty values.
     427             :          */
     428         300 :         if (operator == OID_RANGE_MULTIRANGE_CONTAINED_OP ||
     429             :             operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
     430             :         {
     431             :             /* empty is contained by anything non-empty */
     432          24 :             selec = (1.0 - empty_frac) * hist_selec + empty_frac;
     433             :         }
     434             :         else
     435             :         {
     436             :             /* with any other operator, empty Op non-empty matches nothing */
     437         276 :             selec = (1.0 - empty_frac) * hist_selec;
     438             :         }
     439             :     }
     440             : 
     441             :     /* all multirange operators are strict */
     442         522 :     selec *= (1.0 - null_frac);
     443             : 
     444             :     /* result should be in range, but make sure... */
     445         522 :     CLAMP_PROBABILITY(selec);
     446             : 
     447         522 :     return selec;
     448             : }
     449             : 
     450             : /*
     451             :  * Calculate multirange operator selectivity using histograms of multirange bounds.
     452             :  *
     453             :  * This estimate is for the portion of values that are not empty and not
     454             :  * NULL.
     455             :  */
     456             : static double
     457         300 : calc_hist_selectivity(TypeCacheEntry *typcache, VariableStatData *vardata,
     458             :                       const MultirangeType *constval, Oid operator)
     459             : {
     460         300 :     TypeCacheEntry *rng_typcache = typcache->rngtype;
     461             :     AttStatsSlot hslot;
     462             :     AttStatsSlot lslot;
     463             :     int         nhist;
     464             :     RangeBound *hist_lower;
     465             :     RangeBound *hist_upper;
     466             :     int         i;
     467             :     RangeBound  const_lower;
     468             :     RangeBound  const_upper;
     469             :     RangeBound  tmp;
     470             :     double      hist_selec;
     471             : 
     472             :     /* Can't use the histogram with insecure multirange support functions */
     473         300 :     if (!statistic_proc_security_check(vardata,
     474             :                                        rng_typcache->rng_cmp_proc_finfo.fn_oid))
     475           0 :         return -1;
     476         300 :     if (OidIsValid(rng_typcache->rng_subdiff_finfo.fn_oid) &&
     477         300 :         !statistic_proc_security_check(vardata,
     478             :                                        rng_typcache->rng_subdiff_finfo.fn_oid))
     479           0 :         return -1;
     480             : 
     481             :     /* Try to get histogram of ranges */
     482         552 :     if (!(HeapTupleIsValid(vardata->statsTuple) &&
     483         252 :           get_attstatsslot(&hslot, vardata->statsTuple,
     484             :                            STATISTIC_KIND_BOUNDS_HISTOGRAM, InvalidOid,
     485             :                            ATTSTATSSLOT_VALUES)))
     486          48 :         return -1.0;
     487             : 
     488             :     /* check that it's a histogram, not just a dummy entry */
     489         252 :     if (hslot.nvalues < 2)
     490             :     {
     491           0 :         free_attstatsslot(&hslot);
     492           0 :         return -1.0;
     493             :     }
     494             : 
     495             :     /*
     496             :      * Convert histogram of ranges into histograms of its lower and upper
     497             :      * bounds.
     498             :      */
     499         252 :     nhist = hslot.nvalues;
     500         252 :     hist_lower = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
     501         252 :     hist_upper = (RangeBound *) palloc(sizeof(RangeBound) * nhist);
     502       18936 :     for (i = 0; i < nhist; i++)
     503             :     {
     504             :         bool        empty;
     505             : 
     506       18684 :         range_deserialize(rng_typcache, DatumGetRangeTypeP(hslot.values[i]),
     507       18684 :                           &hist_lower[i], &hist_upper[i], &empty);
     508             :         /* The histogram should not contain any empty ranges */
     509       18684 :         if (empty)
     510           0 :             elog(ERROR, "bounds histogram contains an empty range");
     511             :     }
     512             : 
     513             :     /* @> and @< also need a histogram of range lengths */
     514         252 :     if (operator == OID_MULTIRANGE_CONTAINS_RANGE_OP ||
     515         204 :         operator == OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP ||
     516         204 :         operator == OID_MULTIRANGE_RANGE_CONTAINED_OP ||
     517             :         operator == OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP)
     518             :     {
     519         120 :         if (!(HeapTupleIsValid(vardata->statsTuple) &&
     520          60 :               get_attstatsslot(&lslot, vardata->statsTuple,
     521             :                                STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM,
     522             :                                InvalidOid,
     523             :                                ATTSTATSSLOT_VALUES)))
     524             :         {
     525           0 :             free_attstatsslot(&hslot);
     526           0 :             return -1.0;
     527             :         }
     528             : 
     529             :         /* check that it's a histogram, not just a dummy entry */
     530          60 :         if (lslot.nvalues < 2)
     531             :         {
     532           0 :             free_attstatsslot(&lslot);
     533           0 :             free_attstatsslot(&hslot);
     534           0 :             return -1.0;
     535             :         }
     536             :     }
     537             :     else
     538         192 :         memset(&lslot, 0, sizeof(lslot));
     539             : 
     540             :     /* Extract the bounds of the constant value. */
     541             :     Assert(constval->rangeCount > 0);
     542         252 :     multirange_get_bounds(rng_typcache, constval, 0,
     543             :                           &const_lower, &tmp);
     544         252 :     multirange_get_bounds(rng_typcache, constval, constval->rangeCount - 1,
     545             :                           &tmp, &const_upper);
     546             : 
     547             :     /*
     548             :      * Calculate selectivity comparing the lower or upper bound of the
     549             :      * constant with the histogram of lower or upper bounds.
     550             :      */
     551         252 :     switch (operator)
     552             :     {
     553           0 :         case OID_MULTIRANGE_LESS_OP:
     554             : 
     555             :             /*
     556             :              * The regular b-tree comparison operators (<, <=, >, >=) compare
     557             :              * the lower bounds first, and the upper bounds for values with
     558             :              * equal lower bounds. Estimate that by comparing the lower bounds
     559             :              * only. This gives a fairly accurate estimate assuming there
     560             :              * aren't many rows with a lower bound equal to the constant's
     561             :              * lower bound.
     562             :              */
     563             :             hist_selec =
     564           0 :                 calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     565             :                                              hist_lower, nhist, false);
     566           0 :             break;
     567             : 
     568           0 :         case OID_MULTIRANGE_LESS_EQUAL_OP:
     569             :             hist_selec =
     570           0 :                 calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     571             :                                              hist_lower, nhist, true);
     572           0 :             break;
     573             : 
     574           0 :         case OID_MULTIRANGE_GREATER_OP:
     575           0 :             hist_selec =
     576           0 :                 1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     577             :                                                  hist_lower, nhist, false);
     578           0 :             break;
     579             : 
     580           0 :         case OID_MULTIRANGE_GREATER_EQUAL_OP:
     581           0 :             hist_selec =
     582           0 :                 1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     583             :                                                  hist_lower, nhist, true);
     584           0 :             break;
     585             : 
     586          24 :         case OID_MULTIRANGE_LEFT_RANGE_OP:
     587             :         case OID_MULTIRANGE_LEFT_MULTIRANGE_OP:
     588             :             /* var << const when upper(var) < lower(const) */
     589             :             hist_selec =
     590          24 :                 calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     591             :                                              hist_upper, nhist, false);
     592          24 :             break;
     593             : 
     594          24 :         case OID_MULTIRANGE_RIGHT_RANGE_OP:
     595             :         case OID_MULTIRANGE_RIGHT_MULTIRANGE_OP:
     596             :             /* var >> const when lower(var) > upper(const) */
     597          24 :             hist_selec =
     598          24 :                 1 - calc_hist_selectivity_scalar(rng_typcache, &const_upper,
     599             :                                                  hist_lower, nhist, true);
     600          24 :             break;
     601             : 
     602          24 :         case OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP:
     603             :         case OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
     604             :             /* compare lower bounds */
     605          24 :             hist_selec =
     606          24 :                 1 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     607             :                                                  hist_lower, nhist, false);
     608          24 :             break;
     609             : 
     610          24 :         case OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP:
     611             :         case OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
     612             :             /* compare upper bounds */
     613             :             hist_selec =
     614          24 :                 calc_hist_selectivity_scalar(rng_typcache, &const_upper,
     615             :                                              hist_upper, nhist, true);
     616          24 :             break;
     617             : 
     618          84 :         case OID_MULTIRANGE_OVERLAPS_RANGE_OP:
     619             :         case OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP:
     620             :         case OID_MULTIRANGE_CONTAINS_ELEM_OP:
     621             : 
     622             :             /*
     623             :              * A && B <=> NOT (A << B OR A >> B).
     624             :              *
     625             :              * Since A << B and A >> B are mutually exclusive events we can
     626             :              * sum their probabilities to find probability of (A << B OR A >>
     627             :              * B).
     628             :              *
     629             :              * "multirange @> elem" is equivalent to "multirange &&
     630             :              * {[elem,elem]}". The caller already constructed the singular
     631             :              * range from the element constant, so just treat it the same as
     632             :              * &&.
     633             :              */
     634             :             hist_selec =
     635          84 :                 calc_hist_selectivity_scalar(rng_typcache,
     636             :                                              &const_lower, hist_upper,
     637             :                                              nhist, false);
     638          84 :             hist_selec +=
     639          84 :                 (1.0 - calc_hist_selectivity_scalar(rng_typcache,
     640             :                                                     &const_upper, hist_lower,
     641             :                                                     nhist, true));
     642          84 :             hist_selec = 1.0 - hist_selec;
     643          84 :             break;
     644             : 
     645          48 :         case OID_MULTIRANGE_CONTAINS_RANGE_OP:
     646             :         case OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP:
     647             :             hist_selec =
     648          48 :                 calc_hist_selectivity_contains(rng_typcache, &const_lower,
     649             :                                                &const_upper, hist_lower, nhist,
     650             :                                                lslot.values, lslot.nvalues);
     651          48 :             break;
     652             : 
     653          24 :         case OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP:
     654             :         case OID_RANGE_MULTIRANGE_CONTAINED_OP:
     655          24 :             if (const_lower.infinite)
     656             :             {
     657             :                 /*
     658             :                  * Lower bound no longer matters. Just estimate the fraction
     659             :                  * with an upper bound <= const upper bound
     660             :                  */
     661             :                 hist_selec =
     662           0 :                     calc_hist_selectivity_scalar(rng_typcache, &const_upper,
     663             :                                                  hist_upper, nhist, true);
     664             :             }
     665          24 :             else if (const_upper.infinite)
     666             :             {
     667           0 :                 hist_selec =
     668           0 :                     1.0 - calc_hist_selectivity_scalar(rng_typcache, &const_lower,
     669             :                                                        hist_lower, nhist, false);
     670             :             }
     671             :             else
     672             :             {
     673             :                 hist_selec =
     674          24 :                     calc_hist_selectivity_contained(rng_typcache, &const_lower,
     675             :                                                     &const_upper, hist_lower, nhist,
     676             :                                                     lslot.values, lslot.nvalues);
     677             :             }
     678          24 :             break;
     679             : 
     680             :             /* filtered out by multirangesel() */
     681           0 :         case OID_RANGE_OVERLAPS_MULTIRANGE_OP:
     682             :         case OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP:
     683             :         case OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP:
     684             :         case OID_RANGE_LEFT_MULTIRANGE_OP:
     685             :         case OID_RANGE_RIGHT_MULTIRANGE_OP:
     686             :         case OID_RANGE_CONTAINS_MULTIRANGE_OP:
     687             :         case OID_MULTIRANGE_ELEM_CONTAINED_OP:
     688             :         case OID_MULTIRANGE_RANGE_CONTAINED_OP:
     689             : 
     690             :         default:
     691           0 :             elog(ERROR, "unknown multirange operator %u", operator);
     692             :             hist_selec = -1.0;  /* keep compiler quiet */
     693             :             break;
     694             :     }
     695             : 
     696         252 :     free_attstatsslot(&lslot);
     697         252 :     free_attstatsslot(&hslot);
     698             : 
     699         252 :     return hist_selec;
     700             : }
     701             : 
     702             : 
     703             : /*
     704             :  * Look up the fraction of values less than (or equal, if 'equal' argument
     705             :  * is true) a given const in a histogram of range bounds.
     706             :  */
     707             : static double
     708         264 : calc_hist_selectivity_scalar(TypeCacheEntry *typcache, const RangeBound *constbound,
     709             :                              const RangeBound *hist, int hist_nvalues, bool equal)
     710             : {
     711             :     Selectivity selec;
     712             :     int         index;
     713             : 
     714             :     /*
     715             :      * Find the histogram bin the given constant falls into. Estimate
     716             :      * selectivity as the number of preceding whole bins.
     717             :      */
     718         264 :     index = rbound_bsearch(typcache, constbound, hist, hist_nvalues, equal);
     719         264 :     selec = (Selectivity) (Max(index, 0)) / (Selectivity) (hist_nvalues - 1);
     720             : 
     721             :     /* Adjust using linear interpolation within the bin */
     722         264 :     if (index >= 0 && index < hist_nvalues - 1)
     723         360 :         selec += get_position(typcache, constbound, &hist[index],
     724         180 :                               &hist[index + 1]) / (Selectivity) (hist_nvalues - 1);
     725             : 
     726         264 :     return selec;
     727             : }
     728             : 
     729             : /*
     730             :  * Binary search on an array of range bounds. Returns greatest index of range
     731             :  * bound in array which is less(less or equal) than given range bound. If all
     732             :  * range bounds in array are greater or equal(greater) than given range bound,
     733             :  * return -1. When "equal" flag is set conditions in brackets are used.
     734             :  *
     735             :  * This function is used in scalar operator selectivity estimation. Another
     736             :  * goal of this function is to find a histogram bin where to stop
     737             :  * interpolation of portion of bounds which are less than or equal to given bound.
     738             :  */
     739             : static int
     740         336 : rbound_bsearch(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist,
     741             :                int hist_length, bool equal)
     742             : {
     743         336 :     int         lower = -1,
     744         336 :                 upper = hist_length - 1,
     745             :                 cmp,
     746             :                 middle;
     747             : 
     748        2136 :     while (lower < upper)
     749             :     {
     750        1800 :         middle = (lower + upper + 1) / 2;
     751        1800 :         cmp = range_cmp_bounds(typcache, &hist[middle], value);
     752             : 
     753        1800 :         if (cmp < 0 || (equal && cmp == 0))
     754         744 :             lower = middle;
     755             :         else
     756        1056 :             upper = middle - 1;
     757             :     }
     758         336 :     return lower;
     759             : }
     760             : 
     761             : 
     762             : /*
     763             :  * Binary search on length histogram. Returns greatest index of range length in
     764             :  * histogram which is less than (less than or equal) the given length value. If
     765             :  * all lengths in the histogram are greater than (greater than or equal) the
     766             :  * given length, returns -1.
     767             :  */
     768             : static int
     769         360 : length_hist_bsearch(Datum *length_hist_values, int length_hist_nvalues,
     770             :                     double value, bool equal)
     771             : {
     772         360 :     int         lower = -1,
     773         360 :                 upper = length_hist_nvalues - 1,
     774             :                 middle;
     775             : 
     776        1872 :     while (lower < upper)
     777             :     {
     778             :         double      middleval;
     779             : 
     780        1512 :         middle = (lower + upper + 1) / 2;
     781             : 
     782        1512 :         middleval = DatumGetFloat8(length_hist_values[middle]);
     783        1512 :         if (middleval < value || (equal && middleval <= value))
     784         744 :             lower = middle;
     785             :         else
     786         768 :             upper = middle - 1;
     787             :     }
     788         360 :     return lower;
     789             : }
     790             : 
     791             : /*
     792             :  * Get relative position of value in histogram bin in [0,1] range.
     793             :  */
     794             : static float8
     795         276 : get_position(TypeCacheEntry *typcache, const RangeBound *value, const RangeBound *hist1,
     796             :              const RangeBound *hist2)
     797             : {
     798         276 :     bool        has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
     799             :     float8      position;
     800             : 
     801         276 :     if (!hist1->infinite && !hist2->infinite)
     802             :     {
     803             :         float8      bin_width;
     804             : 
     805             :         /*
     806             :          * Both bounds are finite. Assuming the subtype's comparison function
     807             :          * works sanely, the value must be finite, too, because it lies
     808             :          * somewhere between the bounds.  If it doesn't, arbitrarily return
     809             :          * 0.5.
     810             :          */
     811         204 :         if (value->infinite)
     812           0 :             return 0.5;
     813             : 
     814             :         /* Can't interpolate without subdiff function */
     815         204 :         if (!has_subdiff)
     816           0 :             return 0.5;
     817             : 
     818             :         /* Calculate relative position using subdiff function. */
     819         204 :         bin_width = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
     820             :                                                      typcache->rng_collation,
     821             :                                                      hist2->val,
     822             :                                                      hist1->val));
     823         204 :         if (isnan(bin_width) || bin_width <= 0.0)
     824           0 :             return 0.5;         /* punt for NaN or zero-width bin */
     825             : 
     826         204 :         position = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
     827             :                                                     typcache->rng_collation,
     828             :                                                     value->val,
     829             :                                                     hist1->val))
     830             :             / bin_width;
     831             : 
     832         204 :         if (isnan(position))
     833           0 :             return 0.5;         /* punt for NaN from subdiff, Inf/Inf, etc */
     834             : 
     835             :         /* Relative position must be in [0,1] range */
     836         204 :         position = Max(position, 0.0);
     837         204 :         position = Min(position, 1.0);
     838         204 :         return position;
     839             :     }
     840          72 :     else if (hist1->infinite && !hist2->infinite)
     841             :     {
     842             :         /*
     843             :          * Lower bin boundary is -infinite, upper is finite. If the value is
     844             :          * -infinite, return 0.0 to indicate it's equal to the lower bound.
     845             :          * Otherwise return 1.0 to indicate it's infinitely far from the lower
     846             :          * bound.
     847             :          */
     848          60 :         return ((value->infinite && value->lower) ? 0.0 : 1.0);
     849             :     }
     850          12 :     else if (!hist1->infinite && hist2->infinite)
     851             :     {
     852             :         /* same as above, but in reverse */
     853          12 :         return ((value->infinite && !value->lower) ? 1.0 : 0.0);
     854             :     }
     855             :     else
     856             :     {
     857             :         /*
     858             :          * If both bin boundaries are infinite, they should be equal to each
     859             :          * other, and the value should also be infinite and equal to both
     860             :          * bounds. (But don't Assert that, to avoid crashing if a user creates
     861             :          * a datatype with a broken comparison function).
     862             :          *
     863             :          * Assume the value to lie in the middle of the infinite bounds.
     864             :          */
     865           0 :         return 0.5;
     866             :     }
     867             : }
     868             : 
     869             : 
     870             : /*
     871             :  * Get relative position of value in a length histogram bin in [0,1] range.
     872             :  */
     873             : static double
     874         360 : get_len_position(double value, double hist1, double hist2)
     875             : {
     876         360 :     if (!isinf(hist1) && !isinf(hist2))
     877             :     {
     878             :         /*
     879             :          * Both bounds are finite. The value should be finite too, because it
     880             :          * lies somewhere between the bounds. If it doesn't, just return
     881             :          * something.
     882             :          */
     883          60 :         if (isinf(value))
     884           0 :             return 0.5;
     885             : 
     886          60 :         return 1.0 - (hist2 - value) / (hist2 - hist1);
     887             :     }
     888         300 :     else if (isinf(hist1) && !isinf(hist2))
     889             :     {
     890             :         /*
     891             :          * Lower bin boundary is -infinite, upper is finite. Return 1.0 to
     892             :          * indicate the value is infinitely far from the lower bound.
     893             :          */
     894           0 :         return 1.0;
     895             :     }
     896         300 :     else if (isinf(hist1) && isinf(hist2))
     897             :     {
     898             :         /* same as above, but in reverse */
     899           0 :         return 0.0;
     900             :     }
     901             :     else
     902             :     {
     903             :         /*
     904             :          * If both bin boundaries are infinite, they should be equal to each
     905             :          * other, and the value should also be infinite and equal to both
     906             :          * bounds. (But don't Assert that, to avoid crashing unnecessarily if
     907             :          * the caller messes up)
     908             :          *
     909             :          * Assume the value to lie in the middle of the infinite bounds.
     910             :          */
     911         300 :         return 0.5;
     912             :     }
     913             : }
     914             : 
     915             : /*
     916             :  * Measure distance between two range bounds.
     917             :  */
     918             : static float8
     919         408 : get_distance(TypeCacheEntry *typcache, const RangeBound *bound1, const RangeBound *bound2)
     920             : {
     921         408 :     bool        has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
     922             : 
     923         408 :     if (!bound1->infinite && !bound2->infinite)
     924             :     {
     925             :         /*
     926             :          * Neither bound is infinite, use subdiff function or return default
     927             :          * value of 1.0 if no subdiff is available.
     928             :          */
     929         240 :         if (has_subdiff)
     930             :         {
     931             :             float8      res;
     932             : 
     933         240 :             res = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
     934             :                                                    typcache->rng_collation,
     935             :                                                    bound2->val,
     936             :                                                    bound1->val));
     937             :             /* Reject possible NaN result, also negative result */
     938         240 :             if (isnan(res) || res < 0.0)
     939           0 :                 return 1.0;
     940             :             else
     941         240 :                 return res;
     942             :         }
     943             :         else
     944           0 :             return 1.0;
     945             :     }
     946         168 :     else if (bound1->infinite && bound2->infinite)
     947             :     {
     948             :         /* Both bounds are infinite */
     949           0 :         if (bound1->lower == bound2->lower)
     950           0 :             return 0.0;
     951             :         else
     952           0 :             return get_float8_infinity();
     953             :     }
     954             :     else
     955             :     {
     956             :         /* One bound is infinite, the other is not */
     957         168 :         return get_float8_infinity();
     958             :     }
     959             : }
     960             : 
     961             : /*
     962             :  * Calculate the average of function P(x), in the interval [length1, length2],
     963             :  * where P(x) is the fraction of tuples with length < x (or length <= x if
     964             :  * 'equal' is true).
     965             :  */
     966             : static double
     967         360 : calc_length_hist_frac(Datum *length_hist_values, int length_hist_nvalues,
     968             :                       double length1, double length2, bool equal)
     969             : {
     970             :     double      frac;
     971             :     double      A,
     972             :                 B,
     973             :                 PA,
     974             :                 PB;
     975             :     double      pos;
     976             :     int         i;
     977             :     double      area;
     978             : 
     979             :     Assert(length2 >= length1);
     980             : 
     981         360 :     if (length2 < 0.0)
     982           0 :         return 0.0;             /* shouldn't happen, but doesn't hurt to check */
     983             : 
     984             :     /* All lengths in the table are <= infinite. */
     985         360 :     if (isinf(length2) && equal)
     986           0 :         return 1.0;
     987             : 
     988             :     /*----------
     989             :      * The average of a function between A and B can be calculated by the
     990             :      * formula:
     991             :      *
     992             :      *          B
     993             :      *    1     /
     994             :      * -------  | P(x)dx
     995             :      *  B - A   /
     996             :      *          A
     997             :      *
     998             :      * The geometrical interpretation of the integral is the area under the
     999             :      * graph of P(x). P(x) is defined by the length histogram. We calculate
    1000             :      * the area in a piecewise fashion, iterating through the length histogram
    1001             :      * bins. Each bin is a trapezoid:
    1002             :      *
    1003             :      *       P(x2)
    1004             :      *        /|
    1005             :      *       / |
    1006             :      * P(x1)/  |
    1007             :      *     |   |
    1008             :      *     |   |
    1009             :      *  ---+---+--
    1010             :      *     x1  x2
    1011             :      *
    1012             :      * where x1 and x2 are the boundaries of the current histogram, and P(x1)
    1013             :      * and P(x1) are the cumulative fraction of tuples at the boundaries.
    1014             :      *
    1015             :      * The area of each trapezoid is 1/2 * (P(x2) + P(x1)) * (x2 - x1)
    1016             :      *
    1017             :      * The first bin contains the lower bound passed by the caller, so we
    1018             :      * use linear interpolation between the previous and next histogram bin
    1019             :      * boundary to calculate P(x1). Likewise for the last bin: we use linear
    1020             :      * interpolation to calculate P(x2). For the bins in between, x1 and x2
    1021             :      * lie on histogram bin boundaries, so P(x1) and P(x2) are simply:
    1022             :      * P(x1) =    (bin index) / (number of bins)
    1023             :      * P(x2) = (bin index + 1 / (number of bins)
    1024             :      */
    1025             : 
    1026             :     /* First bin, the one that contains lower bound */
    1027         360 :     i = length_hist_bsearch(length_hist_values, length_hist_nvalues, length1, equal);
    1028         360 :     if (i >= length_hist_nvalues - 1)
    1029          48 :         return 1.0;
    1030             : 
    1031         312 :     if (i < 0)
    1032             :     {
    1033          84 :         i = 0;
    1034          84 :         pos = 0.0;
    1035             :     }
    1036             :     else
    1037             :     {
    1038             :         /* interpolate length1's position in the bin */
    1039         228 :         pos = get_len_position(length1,
    1040         228 :                                DatumGetFloat8(length_hist_values[i]),
    1041         228 :                                DatumGetFloat8(length_hist_values[i + 1]));
    1042             :     }
    1043         312 :     PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
    1044         312 :     B = length1;
    1045             : 
    1046             :     /*
    1047             :      * In the degenerate case that length1 == length2, simply return
    1048             :      * P(length1). This is not merely an optimization: if length1 == length2,
    1049             :      * we'd divide by zero later on.
    1050             :      */
    1051         312 :     if (length2 == length1)
    1052         144 :         return PB;
    1053             : 
    1054             :     /*
    1055             :      * Loop through all the bins, until we hit the last bin, the one that
    1056             :      * contains the upper bound. (if lower and upper bounds are in the same
    1057             :      * bin, this falls out immediately)
    1058             :      */
    1059         168 :     area = 0.0;
    1060        3168 :     for (; i < length_hist_nvalues - 1; i++)
    1061             :     {
    1062        3168 :         double      bin_upper = DatumGetFloat8(length_hist_values[i + 1]);
    1063             : 
    1064             :         /* check if we've reached the last bin */
    1065        3168 :         if (!(bin_upper < length2 || (equal && bin_upper <= length2)))
    1066             :             break;
    1067             : 
    1068             :         /* the upper bound of previous bin is the lower bound of this bin */
    1069        3000 :         A = B;
    1070        3000 :         PA = PB;
    1071             : 
    1072        3000 :         B = bin_upper;
    1073        3000 :         PB = (double) i / (double) (length_hist_nvalues - 1);
    1074             : 
    1075             :         /*
    1076             :          * Add the area of this trapezoid to the total. The point of the
    1077             :          * if-check is to avoid NaN, in the corner case that PA == PB == 0,
    1078             :          * and B - A == Inf. The area of a zero-height trapezoid (PA == PB ==
    1079             :          * 0) is zero, regardless of the width (B - A).
    1080             :          */
    1081        3000 :         if (PA > 0 || PB > 0)
    1082        2952 :             area += 0.5 * (PB + PA) * (B - A);
    1083             :     }
    1084             : 
    1085             :     /* Last bin */
    1086         168 :     A = B;
    1087         168 :     PA = PB;
    1088             : 
    1089         168 :     B = length2;                /* last bin ends at the query upper bound */
    1090         168 :     if (i >= length_hist_nvalues - 1)
    1091           0 :         pos = 0.0;
    1092             :     else
    1093             :     {
    1094         168 :         if (DatumGetFloat8(length_hist_values[i]) == DatumGetFloat8(length_hist_values[i + 1]))
    1095          36 :             pos = 0.0;
    1096             :         else
    1097         132 :             pos = get_len_position(length2,
    1098         132 :                                    DatumGetFloat8(length_hist_values[i]),
    1099         132 :                                    DatumGetFloat8(length_hist_values[i + 1]));
    1100             :     }
    1101         168 :     PB = (((double) i) + pos) / (double) (length_hist_nvalues - 1);
    1102             : 
    1103         168 :     if (PA > 0 || PB > 0)
    1104         132 :         area += 0.5 * (PB + PA) * (B - A);
    1105             : 
    1106             :     /*
    1107             :      * Ok, we have calculated the area, ie. the integral. Divide by width to
    1108             :      * get the requested average.
    1109             :      *
    1110             :      * Avoid NaN arising from infinite / infinite. This happens at least if
    1111             :      * length2 is infinite. It's not clear what the correct value would be in
    1112             :      * that case, so 0.5 seems as good as any value.
    1113             :      */
    1114         168 :     if (isinf(area) && isinf(length2))
    1115          48 :         frac = 0.5;
    1116             :     else
    1117         120 :         frac = area / (length2 - length1);
    1118             : 
    1119         168 :     return frac;
    1120             : }
    1121             : 
    1122             : /*
    1123             :  * Calculate selectivity of "var <@ const" operator, ie. estimate the fraction
    1124             :  * of multiranges that fall within the constant lower and upper bounds. This uses
    1125             :  * the histograms of range lower bounds and range lengths, on the assumption
    1126             :  * that the range lengths are independent of the lower bounds.
    1127             :  *
    1128             :  * The caller has already checked that constant lower and upper bounds are
    1129             :  * finite.
    1130             :  */
    1131             : static double
    1132          24 : calc_hist_selectivity_contained(TypeCacheEntry *typcache,
    1133             :                                 const RangeBound *lower, RangeBound *upper,
    1134             :                                 const RangeBound *hist_lower, int hist_nvalues,
    1135             :                                 Datum *length_hist_values, int length_hist_nvalues)
    1136             : {
    1137             :     int         i,
    1138             :                 upper_index;
    1139             :     float8      prev_dist;
    1140             :     double      bin_width;
    1141             :     double      upper_bin_width;
    1142             :     double      sum_frac;
    1143             : 
    1144             :     /*
    1145             :      * Begin by finding the bin containing the upper bound, in the lower bound
    1146             :      * histogram. Any range with a lower bound > constant upper bound can't
    1147             :      * match, ie. there are no matches in bins greater than upper_index.
    1148             :      */
    1149          24 :     upper->inclusive = !upper->inclusive;
    1150          24 :     upper->lower = true;
    1151          24 :     upper_index = rbound_bsearch(typcache, upper, hist_lower, hist_nvalues,
    1152             :                                  false);
    1153             : 
    1154             :     /*
    1155             :      * If the upper bound value is below the histogram's lower limit, there
    1156             :      * are no matches.
    1157             :      */
    1158          24 :     if (upper_index < 0)
    1159           0 :         return 0.0;
    1160             : 
    1161             :     /*
    1162             :      * If the upper bound value is at or beyond the histogram's upper limit,
    1163             :      * start our loop at the last actual bin, as though the upper bound were
    1164             :      * within that bin; get_position will clamp its result to 1.0 anyway.
    1165             :      * (This corresponds to assuming that the data population above the
    1166             :      * histogram's upper limit is empty, exactly like what we just assumed for
    1167             :      * the lower limit.)
    1168             :      */
    1169          24 :     upper_index = Min(upper_index, hist_nvalues - 2);
    1170             : 
    1171             :     /*
    1172             :      * Calculate upper_bin_width, ie. the fraction of the (upper_index,
    1173             :      * upper_index + 1) bin which is greater than upper bound of query range
    1174             :      * using linear interpolation of subdiff function.
    1175             :      */
    1176          24 :     upper_bin_width = get_position(typcache, upper,
    1177          24 :                                    &hist_lower[upper_index],
    1178          24 :                                    &hist_lower[upper_index + 1]);
    1179             : 
    1180             :     /*
    1181             :      * In the loop, dist and prev_dist are the distance of the "current" bin's
    1182             :      * lower and upper bounds from the constant upper bound.
    1183             :      *
    1184             :      * bin_width represents the width of the current bin. Normally it is 1.0,
    1185             :      * meaning a full width bin, but can be less in the corner cases: start
    1186             :      * and end of the loop. We start with bin_width = upper_bin_width, because
    1187             :      * we begin at the bin containing the upper bound.
    1188             :      */
    1189          24 :     prev_dist = 0.0;
    1190          24 :     bin_width = upper_bin_width;
    1191             : 
    1192          24 :     sum_frac = 0.0;
    1193         120 :     for (i = upper_index; i >= 0; i--)
    1194             :     {
    1195             :         double      dist;
    1196             :         double      length_hist_frac;
    1197         120 :         bool        final_bin = false;
    1198             : 
    1199             :         /*
    1200             :          * dist -- distance from upper bound of query range to lower bound of
    1201             :          * the current bin in the lower bound histogram. Or to the lower bound
    1202             :          * of the constant range, if this is the final bin, containing the
    1203             :          * constant lower bound.
    1204             :          */
    1205         120 :         if (range_cmp_bounds(typcache, &hist_lower[i], lower) < 0)
    1206             :         {
    1207          24 :             dist = get_distance(typcache, lower, upper);
    1208             : 
    1209             :             /*
    1210             :              * Subtract from bin_width the portion of this bin that we want to
    1211             :              * ignore.
    1212             :              */
    1213          48 :             bin_width -= get_position(typcache, lower, &hist_lower[i],
    1214          24 :                                       &hist_lower[i + 1]);
    1215          24 :             if (bin_width < 0.0)
    1216           0 :                 bin_width = 0.0;
    1217          24 :             final_bin = true;
    1218             :         }
    1219             :         else
    1220          96 :             dist = get_distance(typcache, &hist_lower[i], upper);
    1221             : 
    1222             :         /*
    1223             :          * Estimate the fraction of tuples in this bin that are narrow enough
    1224             :          * to not exceed the distance to the upper bound of the query range.
    1225             :          */
    1226         120 :         length_hist_frac = calc_length_hist_frac(length_hist_values,
    1227             :                                                  length_hist_nvalues,
    1228             :                                                  prev_dist, dist, true);
    1229             : 
    1230             :         /*
    1231             :          * Add the fraction of tuples in this bin, with a suitable length, to
    1232             :          * the total.
    1233             :          */
    1234         120 :         sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
    1235             : 
    1236         120 :         if (final_bin)
    1237          24 :             break;
    1238             : 
    1239          96 :         bin_width = 1.0;
    1240          96 :         prev_dist = dist;
    1241             :     }
    1242             : 
    1243          24 :     return sum_frac;
    1244             : }
    1245             : 
    1246             : /*
    1247             :  * Calculate selectivity of "var @> const" operator, ie. estimate the fraction
    1248             :  * of multiranges that contain the constant lower and upper bounds. This uses
    1249             :  * the histograms of range lower bounds and range lengths, on the assumption
    1250             :  * that the range lengths are independent of the lower bounds.
    1251             :  */
    1252             : static double
    1253          48 : calc_hist_selectivity_contains(TypeCacheEntry *typcache,
    1254             :                                const RangeBound *lower, const RangeBound *upper,
    1255             :                                const RangeBound *hist_lower, int hist_nvalues,
    1256             :                                Datum *length_hist_values, int length_hist_nvalues)
    1257             : {
    1258             :     int         i,
    1259             :                 lower_index;
    1260             :     double      bin_width,
    1261             :                 lower_bin_width;
    1262             :     double      sum_frac;
    1263             :     float8      prev_dist;
    1264             : 
    1265             :     /* Find the bin containing the lower bound of query range. */
    1266          48 :     lower_index = rbound_bsearch(typcache, lower, hist_lower, hist_nvalues,
    1267             :                                  true);
    1268             : 
    1269             :     /*
    1270             :      * If the lower bound value is below the histogram's lower limit, there
    1271             :      * are no matches.
    1272             :      */
    1273          48 :     if (lower_index < 0)
    1274           0 :         return 0.0;
    1275             : 
    1276             :     /*
    1277             :      * If the lower bound value is at or beyond the histogram's upper limit,
    1278             :      * start our loop at the last actual bin, as though the upper bound were
    1279             :      * within that bin; get_position will clamp its result to 1.0 anyway.
    1280             :      * (This corresponds to assuming that the data population above the
    1281             :      * histogram's upper limit is empty, exactly like what we just assumed for
    1282             :      * the lower limit.)
    1283             :      */
    1284          48 :     lower_index = Min(lower_index, hist_nvalues - 2);
    1285             : 
    1286             :     /*
    1287             :      * Calculate lower_bin_width, ie. the fraction of the of (lower_index,
    1288             :      * lower_index + 1) bin which is greater than lower bound of query range
    1289             :      * using linear interpolation of subdiff function.
    1290             :      */
    1291          48 :     lower_bin_width = get_position(typcache, lower, &hist_lower[lower_index],
    1292          48 :                                    &hist_lower[lower_index + 1]);
    1293             : 
    1294             :     /*
    1295             :      * Loop through all the lower bound bins, smaller than the query lower
    1296             :      * bound. In the loop, dist and prev_dist are the distance of the
    1297             :      * "current" bin's lower and upper bounds from the constant upper bound.
    1298             :      * We begin from query lower bound, and walk backwards, so the first bin's
    1299             :      * upper bound is the query lower bound, and its distance to the query
    1300             :      * upper bound is the length of the query range.
    1301             :      *
    1302             :      * bin_width represents the width of the current bin. Normally it is 1.0,
    1303             :      * meaning a full width bin, except for the first bin, which is only
    1304             :      * counted up to the constant lower bound.
    1305             :      */
    1306          48 :     prev_dist = get_distance(typcache, lower, upper);
    1307          48 :     sum_frac = 0.0;
    1308          48 :     bin_width = lower_bin_width;
    1309         288 :     for (i = lower_index; i >= 0; i--)
    1310             :     {
    1311             :         float8      dist;
    1312             :         double      length_hist_frac;
    1313             : 
    1314             :         /*
    1315             :          * dist -- distance from upper bound of query range to current value
    1316             :          * of lower bound histogram or lower bound of query range (if we've
    1317             :          * reach it).
    1318             :          */
    1319         240 :         dist = get_distance(typcache, &hist_lower[i], upper);
    1320             : 
    1321             :         /*
    1322             :          * Get average fraction of length histogram which covers intervals
    1323             :          * longer than (or equal to) distance to upper bound of query range.
    1324             :          */
    1325         240 :         length_hist_frac =
    1326         240 :             1.0 - calc_length_hist_frac(length_hist_values,
    1327             :                                         length_hist_nvalues,
    1328             :                                         prev_dist, dist, false);
    1329             : 
    1330         240 :         sum_frac += length_hist_frac * bin_width / (double) (hist_nvalues - 1);
    1331             : 
    1332         240 :         bin_width = 1.0;
    1333         240 :         prev_dist = dist;
    1334             :     }
    1335             : 
    1336          48 :     return sum_frac;
    1337             : }

Generated by: LCOV version 1.14