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