Age Owner Branch data TLA 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-2025, 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/multirangetypes.h"
33 : : #include "utils/rangetypes.h"
34 : : #include "varatt.h"
35 : :
36 : : static int float8_qsort_cmp(const void *a1, const void *a2, void *arg);
37 : : static int range_bound_qsort_cmp(const void *a1, const void *a2, void *arg);
38 : : static void compute_range_stats(VacAttrStats *stats,
39 : : AnalyzeAttrFetchFunc fetchfunc, int samplerows,
40 : : double totalrows);
41 : :
42 : : /*
43 : : * range_typanalyze -- typanalyze function for range columns
44 : : */
45 : : Datum
4758 heikki.linnakangas@i 46 :CBC 15 : range_typanalyze(PG_FUNCTION_ARGS)
47 : : {
48 : 15 : VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
49 : : TypeCacheEntry *typcache;
50 : :
51 : : /* Get information about range type; note column might be a domain */
4275 tgl@sss.pgh.pa.us 52 : 15 : typcache = range_get_typcache(fcinfo, getBaseType(stats->attrtypid));
53 : :
796 peter@eisentraut.org 54 [ + - ]: 15 : if (stats->attstattarget < 0)
55 : 15 : stats->attstattarget = default_statistics_target;
56 : :
4758 heikki.linnakangas@i 57 : 15 : stats->compute_stats = compute_range_stats;
58 : 15 : stats->extra_data = typcache;
59 : : /* same as in std_typanalyze */
796 peter@eisentraut.org 60 : 15 : stats->minrows = 300 * stats->attstattarget;
61 : :
4758 heikki.linnakangas@i 62 : 15 : PG_RETURN_BOOL(true);
63 : : }
64 : :
65 : : /*
66 : : * multirange_typanalyze -- typanalyze function for multirange columns
67 : : *
68 : : * We do the same analysis as for ranges, but on the smallest range that
69 : : * completely includes the multirange.
70 : : */
71 : : Datum
1721 akorotkov@postgresql 72 : 6 : multirange_typanalyze(PG_FUNCTION_ARGS)
73 : : {
74 : 6 : VacAttrStats *stats = (VacAttrStats *) PG_GETARG_POINTER(0);
75 : : TypeCacheEntry *typcache;
76 : :
77 : : /* Get information about multirange type; note column might be a domain */
78 : 6 : typcache = multirange_get_typcache(fcinfo, getBaseType(stats->attrtypid));
79 : :
796 peter@eisentraut.org 80 [ + - ]: 6 : if (stats->attstattarget < 0)
81 : 6 : stats->attstattarget = default_statistics_target;
82 : :
1721 akorotkov@postgresql 83 : 6 : stats->compute_stats = compute_range_stats;
84 : 6 : stats->extra_data = typcache;
85 : : /* same as in std_typanalyze */
796 peter@eisentraut.org 86 : 6 : stats->minrows = 300 * stats->attstattarget;
87 : :
1721 akorotkov@postgresql 88 : 6 : PG_RETURN_BOOL(true);
89 : : }
90 : :
91 : : /*
92 : : * Comparison function for sorting float8s, used for range lengths.
93 : : */
94 : : static int
1152 tgl@sss.pgh.pa.us 95 : 96174 : float8_qsort_cmp(const void *a1, const void *a2, void *arg)
96 : : {
4559 heikki.linnakangas@i 97 : 96174 : const float8 *f1 = (const float8 *) a1;
98 : 96174 : const float8 *f2 = (const float8 *) a2;
99 : :
100 [ + + ]: 96174 : if (*f1 < *f2)
101 : 57 : return -1;
102 [ + + ]: 96117 : else if (*f1 == *f2)
103 : 85254 : return 0;
104 : : else
105 : 10863 : return 1;
106 : : }
107 : :
108 : : /*
109 : : * Comparison function for sorting RangeBounds.
110 : : */
111 : : static int
4758 112 : 1493763 : range_bound_qsort_cmp(const void *a1, const void *a2, void *arg)
113 : : {
4483 bruce@momjian.us 114 : 1493763 : RangeBound *b1 = (RangeBound *) a1;
115 : 1493763 : RangeBound *b2 = (RangeBound *) a2;
116 : 1493763 : TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
117 : :
4758 heikki.linnakangas@i 118 : 1493763 : return range_cmp_bounds(typcache, b1, b2);
119 : : }
120 : :
121 : : /*
122 : : * compute_range_stats() -- compute statistics for a range column
123 : : */
124 : : static void
125 : 21 : compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
126 : : int samplerows, double totalrows)
127 : : {
128 : 21 : TypeCacheEntry *typcache = (TypeCacheEntry *) stats->extra_data;
1721 akorotkov@postgresql 129 : 21 : TypeCacheEntry *mltrng_typcache = NULL;
130 : : bool has_subdiff;
4758 heikki.linnakangas@i 131 : 21 : int null_cnt = 0;
132 : 21 : int non_null_cnt = 0;
133 : 21 : int non_empty_cnt = 0;
134 : 21 : int empty_cnt = 0;
135 : : int range_no;
136 : : int slot_idx;
796 peter@eisentraut.org 137 : 21 : int num_bins = stats->attstattarget;
138 : : int num_hist;
139 : : float8 *lengths;
140 : : RangeBound *lowers,
141 : : *uppers;
4758 heikki.linnakangas@i 142 : 21 : double total_width = 0;
143 : :
1721 akorotkov@postgresql 144 [ + + ]: 21 : if (typcache->typtype == TYPTYPE_MULTIRANGE)
145 : : {
146 : 6 : mltrng_typcache = typcache;
147 : 6 : typcache = typcache->rngtype;
148 : : }
149 : : else
150 [ - + ]: 15 : Assert(typcache->typtype == TYPTYPE_RANGE);
151 : 21 : has_subdiff = OidIsValid(typcache->rng_subdiff_finfo.fn_oid);
152 : :
153 : : /* Allocate memory to hold range bounds and lengths of the sample ranges. */
4758 heikki.linnakangas@i 154 : 21 : lowers = (RangeBound *) palloc(sizeof(RangeBound) * samplerows);
155 : 21 : uppers = (RangeBound *) palloc(sizeof(RangeBound) * samplerows);
4559 156 : 21 : lengths = (float8 *) palloc(sizeof(float8) * samplerows);
157 : :
158 : : /* Loop over the sample ranges. */
4758 159 [ + + ]: 66984 : for (range_no = 0; range_no < samplerows; range_no++)
160 : : {
161 : : Datum value;
162 : : bool isnull,
163 : : empty;
164 : : MultirangeType *multirange;
165 : : RangeType *range;
166 : : RangeBound lower,
167 : : upper;
168 : : float8 length;
169 : :
207 nathan@postgresql.or 170 : 66963 : vacuum_delay_point(true);
171 : :
4758 heikki.linnakangas@i 172 : 66963 : value = fetchfunc(stats, range_no, &isnull);
173 [ - + ]: 66963 : if (isnull)
174 : : {
175 : : /* range is null, just count that */
4758 heikki.linnakangas@i 176 :UBC 0 : null_cnt++;
177 : 0 : continue;
178 : : }
179 : :
180 : : /*
181 : : * XXX: should we ignore wide values, like std_typanalyze does, to
182 : : * avoid bloating the statistics table?
183 : : */
4758 heikki.linnakangas@i 184 [ - + - - :CBC 66963 : total_width += VARSIZE_ANY(DatumGetPointer(value));
- - - - +
- ]
185 : :
186 : : /* Get range and deserialize it for further analysis. */
1721 akorotkov@postgresql 187 [ + + ]: 66963 : if (mltrng_typcache != NULL)
188 : : {
189 : : /* Treat multiranges like a big range without gaps. */
190 : 11133 : multirange = DatumGetMultirangeTypeP(value);
191 [ + + ]: 11133 : if (!MultirangeIsEmpty(multirange))
192 : : {
193 : : RangeBound tmp;
194 : :
195 : 9621 : multirange_get_bounds(typcache, multirange, 0,
196 : : &lower, &tmp);
197 : 9621 : multirange_get_bounds(typcache, multirange,
198 : 9621 : multirange->rangeCount - 1,
199 : : &tmp, &upper);
200 : 9621 : empty = false;
201 : : }
202 : : else
203 : : {
204 : 1512 : empty = true;
205 : : }
206 : : }
207 : : else
208 : : {
209 : 55830 : range = DatumGetRangeTypeP(value);
210 : 55830 : range_deserialize(typcache, range, &lower, &upper, &empty);
211 : : }
212 : :
4758 heikki.linnakangas@i 213 [ + + ]: 66963 : if (!empty)
214 : : {
215 : : /* Remember bounds and length for further usage in histograms */
216 : 56448 : lowers[non_empty_cnt] = lower;
217 : 56448 : uppers[non_empty_cnt] = upper;
218 : :
4559 219 [ + + + + ]: 56448 : if (lower.infinite || upper.infinite)
220 : : {
221 : : /* Length of any kind of an infinite range is infinite */
222 : 2421 : length = get_float8_infinity();
223 : : }
224 [ + - ]: 54027 : else if (has_subdiff)
225 : : {
226 : : /*
227 : : * For an ordinary range, use subdiff function between upper
228 : : * and lower bound values.
229 : : */
2046 alvherre@alvh.no-ip. 230 : 54027 : length = DatumGetFloat8(FunctionCall2Coll(&typcache->rng_subdiff_finfo,
231 : : typcache->rng_collation,
232 : : upper.val, lower.val));
233 : : }
234 : : else
235 : : {
236 : : /* Use default value of 1.0 if no subdiff is available. */
4559 heikki.linnakangas@i 237 :UBC 0 : length = 1.0;
238 : : }
4559 heikki.linnakangas@i 239 :CBC 56448 : lengths[non_empty_cnt] = length;
240 : :
4758 241 : 56448 : non_empty_cnt++;
242 : : }
243 : : else
244 : 10515 : empty_cnt++;
245 : :
246 : 66963 : non_null_cnt++;
247 : : }
248 : :
249 : 21 : slot_idx = 0;
250 : :
251 : : /* We can only compute real stats if we found some non-null values. */
252 [ + - ]: 21 : if (non_null_cnt > 0)
253 : : {
254 : : Datum *bound_hist_values;
255 : : Datum *length_hist_values;
256 : : int pos,
257 : : posfrac,
258 : : delta,
259 : : deltafrac,
260 : : i;
261 : : MemoryContext old_cxt;
262 : : float4 *emptyfrac;
263 : :
264 : 21 : stats->stats_valid = true;
265 : : /* Do the simple null-frac and width stats */
266 : 21 : stats->stanullfrac = (double) null_cnt / (double) samplerows;
267 : 21 : stats->stawidth = total_width / (double) non_null_cnt;
268 : :
269 : : /* Estimate that non-null values are unique */
3317 tgl@sss.pgh.pa.us 270 : 21 : stats->stadistinct = -1.0 * (1.0 - stats->stanullfrac);
271 : :
272 : : /* Must copy the target values into anl_context */
4758 heikki.linnakangas@i 273 : 21 : old_cxt = MemoryContextSwitchTo(stats->anl_context);
274 : :
275 : : /*
276 : : * Generate a bounds histogram slot entry if there are at least two
277 : : * values.
278 : : */
4755 279 [ + - ]: 21 : if (non_empty_cnt >= 2)
280 : : {
281 : : /* Sort bound values */
1152 tgl@sss.pgh.pa.us 282 : 21 : qsort_interruptible(lowers, non_empty_cnt, sizeof(RangeBound),
283 : : range_bound_qsort_cmp, typcache);
284 : 21 : qsort_interruptible(uppers, non_empty_cnt, sizeof(RangeBound),
285 : : range_bound_qsort_cmp, typcache);
286 : :
4758 heikki.linnakangas@i 287 : 21 : num_hist = non_empty_cnt;
288 [ + + ]: 21 : if (num_hist > num_bins)
289 : 12 : num_hist = num_bins + 1;
290 : :
291 : 21 : bound_hist_values = (Datum *) palloc(num_hist * sizeof(Datum));
292 : :
293 : : /*
294 : : * The object of this loop is to construct ranges from first and
295 : : * last entries in lowers[] and uppers[] along with evenly-spaced
296 : : * values in between. So the i'th value is a range of lowers[(i *
297 : : * (nvals - 1)) / (num_hist - 1)] and uppers[(i * (nvals - 1)) /
298 : : * (num_hist - 1)]. But computing that subscript directly risks
299 : : * integer overflow when the stats target is more than a couple
300 : : * thousand. Instead we add (nvals - 1) / (num_hist - 1) to pos
301 : : * at each step, tracking the integral and fractional parts of the
302 : : * sum separately.
303 : : */
304 : 21 : delta = (non_empty_cnt - 1) / (num_hist - 1);
305 : 21 : deltafrac = (non_empty_cnt - 1) % (num_hist - 1);
306 : 21 : pos = posfrac = 0;
307 : :
308 [ + + ]: 1281 : for (i = 0; i < num_hist; i++)
309 : : {
2046 alvherre@alvh.no-ip. 310 : 1260 : bound_hist_values[i] = PointerGetDatum(range_serialize(typcache,
311 : 1260 : &lowers[pos],
312 : 1260 : &uppers[pos],
313 : : false,
314 : : NULL));
4758 heikki.linnakangas@i 315 : 1260 : pos += delta;
316 : 1260 : posfrac += deltafrac;
317 [ + + ]: 1260 : if (posfrac >= (num_hist - 1))
318 : : {
319 : : /* fractional part exceeds 1, carry to integer part */
320 : 1188 : pos++;
321 : 1188 : posfrac -= (num_hist - 1);
322 : : }
323 : : }
324 : :
325 : 21 : stats->stakind[slot_idx] = STATISTIC_KIND_BOUNDS_HISTOGRAM;
326 : 21 : stats->stavalues[slot_idx] = bound_hist_values;
327 : 21 : stats->numvalues[slot_idx] = num_hist;
328 : :
329 : : /* Store ranges even if we're analyzing a multirange column */
1721 akorotkov@postgresql 330 : 21 : stats->statypid[slot_idx] = typcache->type_id;
331 : 21 : stats->statyplen[slot_idx] = typcache->typlen;
332 : 21 : stats->statypbyval[slot_idx] = typcache->typbyval;
1578 tgl@sss.pgh.pa.us 333 : 21 : stats->statypalign[slot_idx] = typcache->typalign;
334 : :
4758 heikki.linnakangas@i 335 : 21 : slot_idx++;
336 : : }
337 : :
338 : : /*
339 : : * Generate a length histogram slot entry if there are at least two
340 : : * values.
341 : : */
4559 342 [ + - ]: 21 : if (non_empty_cnt >= 2)
343 : : {
344 : : /*
345 : : * Ascending sort of range lengths for further filling of
346 : : * histogram
347 : : */
1152 tgl@sss.pgh.pa.us 348 : 21 : qsort_interruptible(lengths, non_empty_cnt, sizeof(float8),
349 : : float8_qsort_cmp, NULL);
350 : :
4559 heikki.linnakangas@i 351 : 21 : num_hist = non_empty_cnt;
352 [ + + ]: 21 : if (num_hist > num_bins)
353 : 12 : num_hist = num_bins + 1;
354 : :
355 : 21 : length_hist_values = (Datum *) palloc(num_hist * sizeof(Datum));
356 : :
357 : : /*
358 : : * The object of this loop is to copy the first and last lengths[]
359 : : * entries along with evenly-spaced values in between. So the i'th
360 : : * value is lengths[(i * (nvals - 1)) / (num_hist - 1)]. But
361 : : * computing that subscript directly risks integer overflow when
362 : : * the stats target is more than a couple thousand. Instead we
363 : : * add (nvals - 1) / (num_hist - 1) to pos at each step, tracking
364 : : * the integral and fractional parts of the sum separately.
365 : : */
366 : 21 : delta = (non_empty_cnt - 1) / (num_hist - 1);
367 : 21 : deltafrac = (non_empty_cnt - 1) % (num_hist - 1);
368 : 21 : pos = posfrac = 0;
369 : :
370 [ + + ]: 1281 : for (i = 0; i < num_hist; i++)
371 : : {
372 : 1260 : length_hist_values[i] = Float8GetDatum(lengths[pos]);
373 : 1260 : pos += delta;
374 : 1260 : posfrac += deltafrac;
375 [ + + ]: 1260 : if (posfrac >= (num_hist - 1))
376 : : {
377 : : /* fractional part exceeds 1, carry to integer part */
378 : 1188 : pos++;
379 : 1188 : posfrac -= (num_hist - 1);
380 : : }
381 : : }
382 : : }
383 : : else
384 : : {
385 : : /*
386 : : * Even when we don't create the histogram, store an empty array
387 : : * to mean "no histogram". We can't just leave stavalues NULL,
388 : : * because get_attstatsslot() errors if you ask for stavalues, and
389 : : * it's NULL. We'll still store the empty fraction in stanumbers.
390 : : */
4559 heikki.linnakangas@i 391 :UBC 0 : length_hist_values = palloc(0);
392 : 0 : num_hist = 0;
393 : : }
4559 heikki.linnakangas@i 394 :CBC 21 : stats->staop[slot_idx] = Float8LessOperator;
2458 tgl@sss.pgh.pa.us 395 : 21 : stats->stacoll[slot_idx] = InvalidOid;
4559 heikki.linnakangas@i 396 : 21 : stats->stavalues[slot_idx] = length_hist_values;
397 : 21 : stats->numvalues[slot_idx] = num_hist;
398 : 21 : stats->statypid[slot_idx] = FLOAT8OID;
399 : 21 : stats->statyplen[slot_idx] = sizeof(float8);
24 tgl@sss.pgh.pa.us 400 :GNC 21 : stats->statypbyval[slot_idx] = true;
4559 heikki.linnakangas@i 401 :CBC 21 : stats->statypalign[slot_idx] = 'd';
402 : :
403 : : /* Store the fraction of empty ranges */
4758 404 : 21 : emptyfrac = (float4 *) palloc(sizeof(float4));
405 : 21 : *emptyfrac = ((double) empty_cnt) / ((double) non_null_cnt);
406 : 21 : stats->stanumbers[slot_idx] = emptyfrac;
407 : 21 : stats->numnumbers[slot_idx] = 1;
408 : :
4559 409 : 21 : stats->stakind[slot_idx] = STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM;
4758 410 : 21 : slot_idx++;
411 : :
412 : 21 : MemoryContextSwitchTo(old_cxt);
413 : : }
4758 heikki.linnakangas@i 414 [ # # ]:UBC 0 : else if (null_cnt > 0)
415 : : {
416 : : /* We found only nulls; assume the column is entirely null */
417 : 0 : stats->stats_valid = true;
418 : 0 : stats->stanullfrac = 1.0;
4483 bruce@momjian.us 419 : 0 : stats->stawidth = 0; /* "unknown" */
2999 tgl@sss.pgh.pa.us 420 : 0 : stats->stadistinct = 0.0; /* "unknown" */
421 : : }
422 : :
423 : : /*
424 : : * We don't need to bother cleaning up any of our temporary palloc's. The
425 : : * hashtable should also go away, as it used a child memory context.
426 : : */
4758 heikki.linnakangas@i 427 :CBC 21 : }
|
