LCOV - code coverage report
Current view: top level - src/backend/utils/adt - rangetypes_typanalyze.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 114 123 92.7 %
Date: 2020-06-03 11:07:14 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * rangetypes_typanalyze.c
       4             :  *    Functions for gathering statistics from range columns
       5             :  *
       6             :  * For a range type column, histograms of lower and upper bounds, and
       7             :  * the fraction of NULL and empty ranges are collected.
       8             :  *
       9             :  * Both histograms have the same length, and they are combined into a
      10             :  * single array of ranges. This has the same shape as the histogram that
      11             :  * std_typanalyze would collect, but the values are different. Each range
      12             :  * in the array is a valid range, even though the lower and upper bounds
      13             :  * come from different tuples. In theory, the standard scalar selectivity
      14             :  * functions could be used with the combined histogram.
      15             :  *
      16             :  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
      17             :  * Portions Copyright (c) 1994, Regents of the University of California
      18             :  *
      19             :  *
      20             :  * IDENTIFICATION
      21             :  *    src/backend/utils/adt/rangetypes_typanalyze.c
      22             :  *
      23             :  *-------------------------------------------------------------------------
      24             :  */
      25             : #include "postgres.h"
      26             : 
      27             : #include "catalog/pg_operator.h"
      28             : #include "commands/vacuum.h"
      29             : #include "utils/float.h"
      30             : #include "utils/fmgrprotos.h"
      31             : #include "utils/lsyscache.h"
      32             : #include "utils/rangetypes.h"
      33             : 
      34             : static int  float8_qsort_cmp(const void *a1, const void *a2);
      35             : static int  range_bound_qsort_cmp(const void *a1, const void *a2, void *arg);
      36             : static void compute_range_stats(VacAttrStats *stats,
      37             :                                 AnalyzeAttrFetchFunc fetchfunc, int samplerows, double totalrows);
      38             : 
      39             : /*
      40             :  * range_typanalyze -- typanalyze function for range columns
      41             :  */
      42             : Datum
      43          60 : range_typanalyze(PG_FUNCTION_ARGS)
      44             : {
      45          60 :     VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
      46             :     TypeCacheEntry *typcache;
      47          60 :     Form_pg_attribute attr = stats->attr;
      48             : 
      49             :     /* Get information about range type; note column might be a domain */
      50          60 :     typcache = range_get_typcache(fcinfo, getBaseType(stats->attrtypid));
      51             : 
      52          60 :     if (attr->attstattarget < 0)
      53          60 :         attr->attstattarget = default_statistics_target;
      54             : 
      55          60 :     stats->compute_stats = compute_range_stats;
      56          60 :     stats->extra_data = typcache;
      57             :     /* same as in std_typanalyze */
      58          60 :     stats->minrows = 300 * attr->attstattarget;
      59             : 
      60          60 :     PG_RETURN_BOOL(true);
      61             : }
      62             : 
      63             : /*
      64             :  * Comparison function for sorting float8s, used for range lengths.
      65             :  */
      66             : static int
      67      136414 : float8_qsort_cmp(const void *a1, const void *a2)
      68             : {
      69      136414 :     const float8 *f1 = (const float8 *) a1;
      70      136414 :     const float8 *f2 = (const float8 *) a2;
      71             : 
      72      136414 :     if (*f1 < *f2)
      73          84 :         return -1;
      74      136330 :     else if (*f1 == *f2)
      75      119282 :         return 0;
      76             :     else
      77       17048 :         return 1;
      78             : }
      79             : 
      80             : /*
      81             :  * Comparison function for sorting RangeBounds.
      82             :  */
      83             : static int
      84     1881692 : range_bound_qsort_cmp(const void *a1, const void *a2, void *arg)
      85             : {
      86     1881692 :     RangeBound *b1 = (RangeBound *) a1;
      87     1881692 :     RangeBound *b2 = (RangeBound *) a2;
      88     1881692 :     TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
      89             : 
      90     1881692 :     return range_cmp_bounds(typcache, b1, b2);
      91             : }
      92             : 
      93             : /*
      94             :  * compute_range_stats() -- compute statistics for a range column
      95             :  */
      96             : static void
      97          60 : compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
      98             :                     int samplerows, double totalrows)
      99             : {
     100          60 :     TypeCacheEntry *typcache = (TypeCacheEntry *) stats->extra_data;
     101          60 :     bool        has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
     102          60 :     int         null_cnt = 0;
     103          60 :     int         non_null_cnt = 0;
     104          60 :     int         non_empty_cnt = 0;
     105          60 :     int         empty_cnt = 0;
     106             :     int         range_no;
     107             :     int         slot_idx;
     108          60 :     int         num_bins = stats->attr->attstattarget;
     109             :     int         num_hist;
     110             :     float8     *lengths;
     111             :     RangeBound *lowers,
     112             :                *uppers;
     113          60 :     double      total_width = 0;
     114             : 
     115             :     /* Allocate memory to hold range bounds and lengths of the sample ranges. */
     116          60 :     lowers = (RangeBound *) palloc(sizeof(RangeBound) * samplerows);
     117          60 :     uppers = (RangeBound *) palloc(sizeof(RangeBound) * samplerows);
     118          60 :     lengths = (float8 *) palloc(sizeof(float8) * samplerows);
     119             : 
     120             :     /* Loop over the sample ranges. */
     121       89086 :     for (range_no = 0; range_no < samplerows; range_no++)
     122             :     {
     123             :         Datum       value;
     124             :         bool        isnull,
     125             :                     empty;
     126             :         RangeType  *range;
     127             :         RangeBound  lower,
     128             :                     upper;
     129             :         float8      length;
     130             : 
     131       89026 :         vacuum_delay_point();
     132             : 
     133       89026 :         value = fetchfunc(stats, range_no, &isnull);
     134       89026 :         if (isnull)
     135             :         {
     136             :             /* range is null, just count that */
     137           0 :             null_cnt++;
     138           0 :             continue;
     139             :         }
     140             : 
     141             :         /*
     142             :          * XXX: should we ignore wide values, like std_typanalyze does, to
     143             :          * avoid bloating the statistics table?
     144             :          */
     145       89026 :         total_width += VARSIZE_ANY(DatumGetPointer(value));
     146             : 
     147             :         /* Get range and deserialize it for further analysis. */
     148       89026 :         range = DatumGetRangeTypeP(value);
     149       89026 :         range_deserialize(typcache, range, &lower, &upper, &empty);
     150             : 
     151       89026 :         if (!empty)
     152             :         {
     153             :             /* Remember bounds and length for further usage in histograms */
     154       74130 :             lowers[non_empty_cnt] = lower;
     155       74130 :             uppers[non_empty_cnt] = upper;
     156             : 
     157       74130 :             if (lower.infinite || upper.infinite)
     158             :             {
     159             :                 /* Length of any kind of an infinite range is infinite */
     160        2878 :                 length = get_float8_infinity();
     161             :             }
     162       71252 :             else if (has_subdiff)
     163             :             {
     164             :                 /*
     165             :                  * For an ordinary range, use subdiff function between upper
     166             :                  * and lower bound values.
     167             :                  */
     168       71240 :                 length = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
     169             :                                                           typcache->rng_collation,
     170             :                                                           upper.val, lower.val));
     171             :             }
     172             :             else
     173             :             {
     174             :                 /* Use default value of 1.0 if no subdiff is available. */
     175          12 :                 length = 1.0;
     176             :             }
     177       74130 :             lengths[non_empty_cnt] = length;
     178             : 
     179       74130 :             non_empty_cnt++;
     180             :         }
     181             :         else
     182       14896 :             empty_cnt++;
     183             : 
     184       89026 :         non_null_cnt++;
     185             :     }
     186             : 
     187          60 :     slot_idx = 0;
     188             : 
     189             :     /* We can only compute real stats if we found some non-null values. */
     190          60 :     if (non_null_cnt > 0)
     191             :     {
     192             :         Datum      *bound_hist_values;
     193             :         Datum      *length_hist_values;
     194             :         int         pos,
     195             :                     posfrac,
     196             :                     delta,
     197             :                     deltafrac,
     198             :                     i;
     199             :         MemoryContext old_cxt;
     200             :         float4     *emptyfrac;
     201             : 
     202          60 :         stats->stats_valid = true;
     203             :         /* Do the simple null-frac and width stats */
     204          60 :         stats->stanullfrac = (double) null_cnt / (double) samplerows;
     205          60 :         stats->stawidth = total_width / (double) non_null_cnt;
     206             : 
     207             :         /* Estimate that non-null values are unique */
     208          60 :         stats->stadistinct = -1.0 * (1.0 - stats->stanullfrac);
     209             : 
     210             :         /* Must copy the target values into anl_context */
     211          60 :         old_cxt = MemoryContextSwitchTo(stats->anl_context);
     212             : 
     213             :         /*
     214             :          * Generate a bounds histogram slot entry if there are at least two
     215             :          * values.
     216             :          */
     217          60 :         if (non_empty_cnt >= 2)
     218             :         {
     219             :             /* Sort bound values */
     220          60 :             qsort_arg(lowers, non_empty_cnt, sizeof(RangeBound),
     221             :                       range_bound_qsort_cmp, typcache);
     222          60 :             qsort_arg(uppers, non_empty_cnt, sizeof(RangeBound),
     223             :                       range_bound_qsort_cmp, typcache);
     224             : 
     225          60 :             num_hist = non_empty_cnt;
     226          60 :             if (num_hist > num_bins)
     227          34 :                 num_hist = num_bins + 1;
     228             : 
     229          60 :             bound_hist_values = (Datum *) palloc(num_hist * sizeof(Datum));
     230             : 
     231             :             /*
     232             :              * The object of this loop is to construct ranges from first and
     233             :              * last entries in lowers[] and uppers[] along with evenly-spaced
     234             :              * values in between. So the i'th value is a range of lowers[(i *
     235             :              * (nvals - 1)) / (num_hist - 1)] and uppers[(i * (nvals - 1)) /
     236             :              * (num_hist - 1)]. But computing that subscript directly risks
     237             :              * integer overflow when the stats target is more than a couple
     238             :              * thousand.  Instead we add (nvals - 1) / (num_hist - 1) to pos
     239             :              * at each step, tracking the integral and fractional parts of the
     240             :              * sum separately.
     241             :              */
     242          60 :             delta = (non_empty_cnt - 1) / (num_hist - 1);
     243          60 :             deltafrac = (non_empty_cnt - 1) % (num_hist - 1);
     244          60 :             pos = posfrac = 0;
     245             : 
     246        1776 :             for (i = 0; i < num_hist; i++)
     247             :             {
     248        1716 :                 bound_hist_values[i] = PointerGetDatum(range_serialize(typcache,
     249             :                                                                        &lowers[pos],
     250             :                                                                        &uppers[pos],
     251             :                                                                        false));
     252        1716 :                 pos += delta;
     253        1716 :                 posfrac += deltafrac;
     254        1716 :                 if (posfrac >= (num_hist - 1))
     255             :                 {
     256             :                     /* fractional part exceeds 1, carry to integer part */
     257        1200 :                     pos++;
     258        1200 :                     posfrac -= (num_hist - 1);
     259             :                 }
     260             :             }
     261             : 
     262          60 :             stats->stakind[slot_idx] = STATISTIC_KIND_BOUNDS_HISTOGRAM;
     263          60 :             stats->stavalues[slot_idx] = bound_hist_values;
     264          60 :             stats->numvalues[slot_idx] = num_hist;
     265          60 :             slot_idx++;
     266             :         }
     267             : 
     268             :         /*
     269             :          * Generate a length histogram slot entry if there are at least two
     270             :          * values.
     271             :          */
     272          60 :         if (non_empty_cnt >= 2)
     273             :         {
     274             :             /*
     275             :              * Ascending sort of range lengths for further filling of
     276             :              * histogram
     277             :              */
     278          60 :             qsort(lengths, non_empty_cnt, sizeof(float8), float8_qsort_cmp);
     279             : 
     280          60 :             num_hist = non_empty_cnt;
     281          60 :             if (num_hist > num_bins)
     282          34 :                 num_hist = num_bins + 1;
     283             : 
     284          60 :             length_hist_values = (Datum *) palloc(num_hist * sizeof(Datum));
     285             : 
     286             :             /*
     287             :              * The object of this loop is to copy the first and last lengths[]
     288             :              * entries along with evenly-spaced values in between. So the i'th
     289             :              * value is lengths[(i * (nvals - 1)) / (num_hist - 1)]. But
     290             :              * computing that subscript directly risks integer overflow when
     291             :              * the stats target is more than a couple thousand.  Instead we
     292             :              * add (nvals - 1) / (num_hist - 1) to pos at each step, tracking
     293             :              * the integral and fractional parts of the sum separately.
     294             :              */
     295          60 :             delta = (non_empty_cnt - 1) / (num_hist - 1);
     296          60 :             deltafrac = (non_empty_cnt - 1) % (num_hist - 1);
     297          60 :             pos = posfrac = 0;
     298             : 
     299        1776 :             for (i = 0; i < num_hist; i++)
     300             :             {
     301        1716 :                 length_hist_values[i] = Float8GetDatum(lengths[pos]);
     302        1716 :                 pos += delta;
     303        1716 :                 posfrac += deltafrac;
     304        1716 :                 if (posfrac >= (num_hist - 1))
     305             :                 {
     306             :                     /* fractional part exceeds 1, carry to integer part */
     307        1200 :                     pos++;
     308        1200 :                     posfrac -= (num_hist - 1);
     309             :                 }
     310             :             }
     311             :         }
     312             :         else
     313             :         {
     314             :             /*
     315             :              * Even when we don't create the histogram, store an empty array
     316             :              * to mean "no histogram". We can't just leave stavalues NULL,
     317             :              * because get_attstatsslot() errors if you ask for stavalues, and
     318             :              * it's NULL. We'll still store the empty fraction in stanumbers.
     319             :              */
     320           0 :             length_hist_values = palloc(0);
     321           0 :             num_hist = 0;
     322             :         }
     323          60 :         stats->staop[slot_idx] = Float8LessOperator;
     324          60 :         stats->stacoll[slot_idx] = InvalidOid;
     325          60 :         stats->stavalues[slot_idx] = length_hist_values;
     326          60 :         stats->numvalues[slot_idx] = num_hist;
     327          60 :         stats->statypid[slot_idx] = FLOAT8OID;
     328          60 :         stats->statyplen[slot_idx] = sizeof(float8);
     329          60 :         stats->statypbyval[slot_idx] = FLOAT8PASSBYVAL;
     330          60 :         stats->statypalign[slot_idx] = 'd';
     331             : 
     332             :         /* Store the fraction of empty ranges */
     333          60 :         emptyfrac = (float4 *) palloc(sizeof(float4));
     334          60 :         *emptyfrac = ((double) empty_cnt) / ((double) non_null_cnt);
     335          60 :         stats->stanumbers[slot_idx] = emptyfrac;
     336          60 :         stats->numnumbers[slot_idx] = 1;
     337             : 
     338          60 :         stats->stakind[slot_idx] = STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM;
     339          60 :         slot_idx++;
     340             : 
     341          60 :         MemoryContextSwitchTo(old_cxt);
     342             :     }
     343           0 :     else if (null_cnt > 0)
     344             :     {
     345             :         /* We found only nulls; assume the column is entirely null */
     346           0 :         stats->stats_valid = true;
     347           0 :         stats->stanullfrac = 1.0;
     348           0 :         stats->stawidth = 0; /* "unknown" */
     349           0 :         stats->stadistinct = 0.0;    /* "unknown" */
     350             :     }
     351             : 
     352             :     /*
     353             :      * We don't need to bother cleaning up any of our temporary palloc's. The
     354             :      * hashtable should also go away, as it used a child memory context.
     355             :      */
     356          60 : }

Generated by: LCOV version 1.13