← Back to branch summary

~ubuntu-branches/debian/sid/postgresql-9.3/sid

« back to all changes in this revision

Viewing changes to src/backend/utils/adt/rangetypes_typanalyze.c

  • Committer: Package Import Robot
  • Author(s): Martin Pitt
  • Date: 2013-05-08 05:39:52 UTC
  • Revision ID: package-import@ubuntu.com-20130508053952-1j7uilp7mjtrvq8q
Tags: upstream-9.3~beta1
Import upstream version 9.3~beta1

Show diffs side-by-side

added added

removed removed

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