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