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 : }
|
