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-2016, 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
tsm_system_time_handler(PG_FUNCTION_ARGS)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
system_time_samplescangetsamplesize(PlannerInfo * root,RelOptInfo * baserel,List * paramexprs,BlockNumber * pages,double * tuples)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
system_time_initsamplescan(SampleScanState * node,int eflags)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
system_time_beginsamplescan(SampleScanState * node,Datum * params,int nparams,uint32 seed)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
system_time_nextsampleblock(SampleScanState * node)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
system_time_nextsampletuple(SampleScanState * node,BlockNumber blockno,OffsetNumber maxoffset)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
gcd(uint32 a,uint32 b)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
random_relative_prime(uint32 n,SamplerRandomState randstate)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 }
359