← Back to branch summary

~ubuntu-branches/debian/experimental/postgresql-11/experimental

« back to all changes in this revision

Viewing changes to contrib/tsm_system_time/tsm_system_time.c

  • Committer: Package Import Robot
  • Author(s): Christoph Berg
  • Date: 2018-05-22 14:19:08 UTC
  • Revision ID: package-import@ubuntu.com-20180522141908-0oy9ujs1b5vrda74
Tags: upstream-11~beta1
Import upstream version 11~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/tsm_system_time/tsm_system_time.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * tsm_system_time.c
 
4
 *        support routines for SYSTEM_TIME tablesample method
 
5
 *
 
6
 * The desire here is to produce a random sample with as many rows as possible
 
7
 * in no more than the specified amount of time.  We use a block-sampling
 
8
 * approach.  To ensure that the whole relation will be visited if necessary,
 
9
 * we start at a randomly chosen block and then advance with a stride that
 
10
 * is randomly chosen but is relatively prime to the relation's nblocks.
 
11
 *
 
12
 * Because of the time dependence, this method is necessarily unrepeatable.
 
13
 * However, we do what we can to reduce surprising behavior by selecting
 
14
 * the sampling pattern just once per query, much as in tsm_system_rows.
 
15
 *
 
16
 * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
 
17
 * Portions Copyright (c) 1994, Regents of the University of California
 
18
 *
 
19
 * IDENTIFICATION
 
20
 *        contrib/tsm_system_time/tsm_system_time.c
 
21
 *
 
22
 *-------------------------------------------------------------------------
 
23
 */
 
24
 
 
25
#include "postgres.h"
 
26
 
 
27
#ifdef _MSC_VER
 
28
#include <float.h>                              /* for _isnan */
 
29
#endif
 
30
#include <math.h>
 
31
 
 
32
#include "access/relscan.h"
 
33
#include "access/tsmapi.h"
 
34
#include "catalog/pg_type.h"
 
35
#include "miscadmin.h"
 
36
#include "optimizer/clauses.h"
 
37
#include "optimizer/cost.h"
 
38
#include "utils/sampling.h"
 
39
#include "utils/spccache.h"
 
40
 
 
41
PG_MODULE_MAGIC;
 
42
 
 
43
PG_FUNCTION_INFO_V1(tsm_system_time_handler);
 
44
 
 
45
 
 
46
/* Private state */
 
47
typedef struct
 
48
{
 
49
        uint32          seed;                   /* random seed */
 
50
        double          millis;                 /* time limit for sampling */
 
51
        instr_time      start_time;             /* scan start time */
 
52
        OffsetNumber lt;                        /* last tuple returned from current block */
 
53
        BlockNumber doneblocks;         /* number of already-scanned blocks */
 
54
        BlockNumber lb;                         /* last block visited */
 
55
        /* these three values are not changed during a rescan: */
 
56
        BlockNumber nblocks;            /* number of blocks in relation */
 
57
        BlockNumber firstblock;         /* first block to sample from */
 
58
        BlockNumber step;                       /* step size, or 0 if not set yet */
 
59
} SystemTimeSamplerData;
 
60
 
 
61
static void system_time_samplescangetsamplesize(PlannerInfo *root,
 
62
                                                                        RelOptInfo *baserel,
 
63
                                                                        List *paramexprs,
 
64
                                                                        BlockNumber *pages,
 
65
                                                                        double *tuples);
 
66
static void system_time_initsamplescan(SampleScanState *node,
 
67
                                                   int eflags);
 
68
static void system_time_beginsamplescan(SampleScanState *node,
 
69
                                                        Datum *params,
 
70
                                                        int nparams,
 
71
                                                        uint32 seed);
 
72
static BlockNumber system_time_nextsampleblock(SampleScanState *node);
 
73
static OffsetNumber system_time_nextsampletuple(SampleScanState *node,
 
74
                                                        BlockNumber blockno,
 
75
                                                        OffsetNumber maxoffset);
 
76
static uint32 random_relative_prime(uint32 n, SamplerRandomState randstate);
 
77
 
 
78
 
 
79
/*
 
80
 * Create a TsmRoutine descriptor for the SYSTEM_TIME method.
 
81
 */
 
82
Datum
 
83
tsm_system_time_handler(PG_FUNCTION_ARGS)
 
84
{
 
85
        TsmRoutine *tsm = makeNode(TsmRoutine);
 
86
 
 
87
        tsm->parameterTypes = list_make1_oid(FLOAT8OID);
 
88
 
 
89
        /* See notes at head of file */
 
90
        tsm->repeatable_across_queries = false;
 
91
        tsm->repeatable_across_scans = false;
 
92
 
 
93
        tsm->SampleScanGetSampleSize = system_time_samplescangetsamplesize;
 
94
        tsm->InitSampleScan = system_time_initsamplescan;
 
95
        tsm->BeginSampleScan = system_time_beginsamplescan;
 
96
        tsm->NextSampleBlock = system_time_nextsampleblock;
 
97
        tsm->NextSampleTuple = system_time_nextsampletuple;
 
98
        tsm->EndSampleScan = NULL;
 
99
 
 
100
        PG_RETURN_POINTER(tsm);
 
101
}
 
102
 
 
103
/*
 
104
 * Sample size estimation.
 
105
 */
 
106
static void
 
107
system_time_samplescangetsamplesize(PlannerInfo *root,
 
108
                                                                        RelOptInfo *baserel,
 
109
                                                                        List *paramexprs,
 
110
                                                                        BlockNumber *pages,
 
111
                                                                        double *tuples)
 
112
{
 
113
        Node       *limitnode;
 
114
        double          millis;
 
115
        double          spc_random_page_cost;
 
116
        double          npages;
 
117
        double          ntuples;
 
118
 
 
119
        /* Try to extract an estimate for the limit time spec */
 
120
        limitnode = (Node *) linitial(paramexprs);
 
121
        limitnode = estimate_expression_value(root, limitnode);
 
122
 
 
123
        if (IsA(limitnode, Const) &&
 
124
                !((Const *) limitnode)->constisnull)
 
125
        {
 
126
                millis = DatumGetFloat8(((Const *) limitnode)->constvalue);
 
127
                if (millis < 0 || isnan(millis))
 
128
                {
 
129
                        /* Default millis if the value is bogus */
 
130
                        millis = 1000;
 
131
                }
 
132
        }
 
133
        else
 
134
        {
 
135
                /* Default millis if we didn't obtain a non-null Const */
 
136
                millis = 1000;
 
137
        }
 
138
 
 
139
        /* Get the planner's idea of cost per page read */
 
140
        get_tablespace_page_costs(baserel->reltablespace,
 
141
                                                          &spc_random_page_cost,
 
142
                                                          NULL);
 
143
 
 
144
        /*
 
145
         * Estimate the number of pages we can read by assuming that the cost
 
146
         * figure is expressed in milliseconds.  This is completely, unmistakably
 
147
         * bogus, but we have to do something to produce an estimate and there's
 
148
         * no better answer.
 
149
         */
 
150
        if (spc_random_page_cost > 0)
 
151
                npages = millis / spc_random_page_cost;
 
152
        else
 
153
                npages = millis;                /* even more bogus, but whatcha gonna do? */
 
154
 
 
155
        /* Clamp to sane value */
 
156
        npages = clamp_row_est(Min((double) baserel->pages, npages));
 
157
 
 
158
        if (baserel->tuples > 0 && baserel->pages > 0)
 
159
        {
 
160
                /* Estimate number of tuples returned based on tuple density */
 
161
                double          density = baserel->tuples / (double) baserel->pages;
 
162
 
 
163
                ntuples = npages * density;
 
164
        }
 
165
        else
 
166
        {
 
167
                /* For lack of data, assume one tuple per page */
 
168
                ntuples = npages;
 
169
        }
 
170
 
 
171
        /* Clamp to the estimated relation size */
 
172
        ntuples = clamp_row_est(Min(baserel->tuples, ntuples));
 
173
 
 
174
        *pages = npages;
 
175
        *tuples = ntuples;
 
176
}
 
177
 
 
178
/*
 
179
 * Initialize during executor setup.
 
180
 */
 
181
static void
 
182
system_time_initsamplescan(SampleScanState *node, int eflags)
 
183
{
 
184
        node->tsm_state = palloc0(sizeof(SystemTimeSamplerData));
 
185
        /* Note the above leaves tsm_state->step equal to zero */
 
186
}
 
187
 
 
188
/*
 
189
 * Examine parameters and prepare for a sample scan.
 
190
 */
 
191
static void
 
192
system_time_beginsamplescan(SampleScanState *node,
 
193
                                                        Datum *params,
 
194
                                                        int nparams,
 
195
                                                        uint32 seed)
 
196
{
 
197
        SystemTimeSamplerData *sampler = (SystemTimeSamplerData *) node->tsm_state;
 
198
        double          millis = DatumGetFloat8(params[0]);
 
199
 
 
200
        if (millis < 0 || isnan(millis))
 
201
                ereport(ERROR,
 
202
                                (errcode(ERRCODE_INVALID_TABLESAMPLE_ARGUMENT),
 
203
                                 errmsg("sample collection time must not be negative")));
 
204
 
 
205
        sampler->seed = seed;
 
206
        sampler->millis = millis;
 
207
        sampler->lt = InvalidOffsetNumber;
 
208
        sampler->doneblocks = 0;
 
209
        /* start_time, lb will be initialized during first NextSampleBlock call */
 
210
        /* we intentionally do not change nblocks/firstblock/step here */
 
211
}
 
212
 
 
213
/*
 
214
 * Select next block to sample.
 
215
 *
 
216
 * Uses linear probing algorithm for picking next block.
 
217
 */
 
218
static BlockNumber
 
219
system_time_nextsampleblock(SampleScanState *node)
 
220
{
 
221
        SystemTimeSamplerData *sampler = (SystemTimeSamplerData *) node->tsm_state;
 
222
        HeapScanDesc scan = node->ss.ss_currentScanDesc;
 
223
        instr_time      cur_time;
 
224
 
 
225
        /* First call within scan? */
 
226
        if (sampler->doneblocks == 0)
 
227
        {
 
228
                /* First scan within query? */
 
229
                if (sampler->step == 0)
 
230
                {
 
231
                        /* Initialize now that we have scan descriptor */
 
232
                        SamplerRandomState randstate;
 
233
 
 
234
                        /* If relation is empty, there's nothing to scan */
 
235
                        if (scan->rs_nblocks == 0)
 
236
                                return InvalidBlockNumber;
 
237
 
 
238
                        /* We only need an RNG during this setup step */
 
239
                        sampler_random_init_state(sampler->seed, randstate);
 
240
 
 
241
                        /* Compute nblocks/firstblock/step only once per query */
 
242
                        sampler->nblocks = scan->rs_nblocks;
 
243
 
 
244
                        /* Choose random starting block within the relation */
 
245
                        /* (Actually this is the predecessor of the first block visited) */
 
246
                        sampler->firstblock = sampler_random_fract(randstate) *
 
247
                                sampler->nblocks;
 
248
 
 
249
                        /* Find relative prime as step size for linear probing */
 
250
                        sampler->step = random_relative_prime(sampler->nblocks, randstate);
 
251
                }
 
252
 
 
253
                /* Reinitialize lb and start_time */
 
254
                sampler->lb = sampler->firstblock;
 
255
                INSTR_TIME_SET_CURRENT(sampler->start_time);
 
256
        }
 
257
 
 
258
        /* If we've read all blocks in relation, we're done */
 
259
        if (++sampler->doneblocks > sampler->nblocks)
 
260
                return InvalidBlockNumber;
 
261
 
 
262
        /* If we've used up all the allotted time, we're done */
 
263
        INSTR_TIME_SET_CURRENT(cur_time);
 
264
        INSTR_TIME_SUBTRACT(cur_time, sampler->start_time);
 
265
        if (INSTR_TIME_GET_MILLISEC(cur_time) >= sampler->millis)
 
266
                return InvalidBlockNumber;
 
267
 
 
268
        /*
 
269
         * It's probably impossible for scan->rs_nblocks to decrease between scans
 
270
         * within a query; but just in case, loop until we select a block number
 
271
         * less than scan->rs_nblocks.  We don't care if scan->rs_nblocks has
 
272
         * increased since the first scan.
 
273
         */
 
274
        do
 
275
        {
 
276
                /* Advance lb, using uint64 arithmetic to forestall overflow */
 
277
                sampler->lb = ((uint64) sampler->lb + sampler->step) % sampler->nblocks;
 
278
        } while (sampler->lb >= scan->rs_nblocks);
 
279
 
 
280
        return sampler->lb;
 
281
}
 
282
 
 
283
/*
 
284
 * Select next sampled tuple in current block.
 
285
 *
 
286
 * In block sampling, we just want to sample all the tuples in each selected
 
287
 * block.
 
288
 *
 
289
 * When we reach end of the block, return InvalidOffsetNumber which tells
 
290
 * SampleScan to go to next block.
 
291
 */
 
292
static OffsetNumber
 
293
system_time_nextsampletuple(SampleScanState *node,
 
294
                                                        BlockNumber blockno,
 
295
                                                        OffsetNumber maxoffset)
 
296
{
 
297
        SystemTimeSamplerData *sampler = (SystemTimeSamplerData *) node->tsm_state;
 
298
        OffsetNumber tupoffset = sampler->lt;
 
299
 
 
300
        /* Advance to next possible offset on page */
 
301
        if (tupoffset == InvalidOffsetNumber)
 
302
                tupoffset = FirstOffsetNumber;
 
303
        else
 
304
                tupoffset++;
 
305
 
 
306
        /* Done? */
 
307
        if (tupoffset > maxoffset)
 
308
                tupoffset = InvalidOffsetNumber;
 
309
 
 
310
        sampler->lt = tupoffset;
 
311
 
 
312
        return tupoffset;
 
313
}
 
314
 
 
315
/*
 
316
 * Compute greatest common divisor of two uint32's.
 
317
 */
 
318
static uint32
 
319
gcd(uint32 a, uint32 b)
 
320
{
 
321
        uint32          c;
 
322
 
 
323
        while (a != 0)
 
324
        {
 
325
                c = a;
 
326
                a = b % a;
 
327
                b = c;
 
328
        }
 
329
 
 
330
        return b;
 
331
}
 
332
 
 
333
/*
 
334
 * Pick a random value less than and relatively prime to n, if possible
 
335
 * (else return 1).
 
336
 */
 
337
static uint32
 
338
random_relative_prime(uint32 n, SamplerRandomState randstate)
 
339
{
 
340
        uint32          r;
 
341
 
 
342
        /* Safety check to avoid infinite loop or zero result for small n. */
 
343
        if (n <= 1)
 
344
                return 1;
 
345
 
 
346
        /*
 
347
         * This should only take 2 or 3 iterations as the probability of 2 numbers
 
348
         * being relatively prime is ~61%; but just in case, we'll include a
 
349
         * CHECK_FOR_INTERRUPTS in the loop.
 
350
         */
 
351
        do
 
352
        {
 
353
                CHECK_FOR_INTERRUPTS();
 
354
                r = (uint32) (sampler_random_fract(randstate) * n);
 
355
        } while (r == 0 || gcd(r, n) > 1);
 
356
 
 
357
        return r;
 
358
}