PostgreSQL Source Code  git master
tsm_system_time.c
Go to the documentation of this file.
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-2019, 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 
38 
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 */
56 
58  RelOptInfo *baserel,
59  List *paramexprs,
60  BlockNumber *pages,
61  double *tuples);
63  int eflags);
65  Datum *params,
66  int nparams,
67  uint32 seed);
70  BlockNumber blockno,
71  OffsetNumber maxoffset);
73 
74 
75 /*
76  * Create a TsmRoutine descriptor for the SYSTEM_TIME method.
77  */
78 Datum
80 {
82 
83  tsm->parameterTypes = list_make1_oid(FLOAT8OID);
84 
85  /* See notes at head of file */
86  tsm->repeatable_across_queries = false;
87  tsm->repeatable_across_scans = false;
88 
94  tsm->EndSampleScan = NULL;
95 
96  PG_RETURN_POINTER(tsm);
97 }
98 
99 /*
100  * Sample size estimation.
101  */
102 static void
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  limitnode = (Node *) linitial(paramexprs);
117  limitnode = estimate_expression_value(root, limitnode);
118 
119  if (IsA(limitnode, Const) &&
120  !((Const *) limitnode)->constisnull)
121  {
122  millis = DatumGetFloat8(((Const *) limitnode)->constvalue);
123  if (millis < 0 || isnan(millis))
124  {
125  /* Default millis if the value is bogus */
126  millis = 1000;
127  }
128  }
129  else
130  {
131  /* Default millis if we didn't obtain a non-null Const */
132  millis = 1000;
133  }
134 
135  /* Get the planner's idea of cost per page read */
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  if (spc_random_page_cost > 0)
147  npages = millis / spc_random_page_cost;
148  else
149  npages = millis; /* even more bogus, but whatcha gonna do? */
150 
151  /* Clamp to sane value */
152  npages = clamp_row_est(Min((double) baserel->pages, npages));
153 
154  if (baserel->tuples > 0 && baserel->pages > 0)
155  {
156  /* Estimate number of tuples returned based on tuple density */
157  double density = baserel->tuples / (double) baserel->pages;
158 
159  ntuples = npages * density;
160  }
161  else
162  {
163  /* For lack of data, assume one tuple per page */
164  ntuples = npages;
165  }
166 
167  /* Clamp to the estimated relation size */
168  ntuples = clamp_row_est(Min(baserel->tuples, ntuples));
169 
170  *pages = npages;
171  *tuples = ntuples;
172 }
173 
174 /*
175  * Initialize during executor setup.
176  */
177 static void
179 {
180  node->tsm_state = palloc0(sizeof(SystemTimeSamplerData));
181  /* Note the above leaves tsm_state->step equal to zero */
182 }
183 
184 /*
185  * Examine parameters and prepare for a sample scan.
186  */
187 static void
189  Datum *params,
190  int nparams,
191  uint32 seed)
192 {
194  double millis = DatumGetFloat8(params[0]);
195 
196  if (millis < 0 || isnan(millis))
197  ereport(ERROR,
198  (errcode(ERRCODE_INVALID_TABLESAMPLE_ARGUMENT),
199  errmsg("sample collection time must not be negative")));
200 
201  sampler->seed = seed;
202  sampler->millis = millis;
203  sampler->lt = InvalidOffsetNumber;
204  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 }
208 
209 /*
210  * Select next block to sample.
211  *
212  * Uses linear probing algorithm for picking next block.
213  */
214 static BlockNumber
216 {
218  instr_time cur_time;
219 
220  /* First call within scan? */
221  if (sampler->doneblocks == 0)
222  {
223  /* First scan within query? */
224  if (sampler->step == 0)
225  {
226  /* Initialize now that we have scan descriptor */
227  SamplerRandomState randstate;
228 
229  /* If relation is empty, there's nothing to scan */
230  if (nblocks == 0)
231  return InvalidBlockNumber;
232 
233  /* We only need an RNG during this setup step */
234  sampler_random_init_state(sampler->seed, randstate);
235 
236  /* Compute nblocks/firstblock/step only once per query */
237  sampler->nblocks = nblocks;
238 
239  /* Choose random starting block within the relation */
240  /* (Actually this is the predecessor of the first block visited) */
241  sampler->firstblock = sampler_random_fract(randstate) *
242  sampler->nblocks;
243 
244  /* Find relative prime as step size for linear probing */
245  sampler->step = random_relative_prime(sampler->nblocks, randstate);
246  }
247 
248  /* Reinitialize lb and start_time */
249  sampler->lb = sampler->firstblock;
251  }
252 
253  /* If we've read all blocks in relation, we're done */
254  if (++sampler->doneblocks > sampler->nblocks)
255  return InvalidBlockNumber;
256 
257  /* If we've used up all the allotted time, we're done */
258  INSTR_TIME_SET_CURRENT(cur_time);
259  INSTR_TIME_SUBTRACT(cur_time, sampler->start_time);
260  if (INSTR_TIME_GET_MILLISEC(cur_time) >= sampler->millis)
261  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  sampler->lb = ((uint64) sampler->lb + sampler->step) % sampler->nblocks;
273  } while (sampler->lb >= nblocks);
274 
275  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
289  BlockNumber blockno,
290  OffsetNumber maxoffset)
291 {
293  OffsetNumber tupoffset = sampler->lt;
294 
295  /* Advance to next possible offset on page */
296  if (tupoffset == InvalidOffsetNumber)
297  tupoffset = FirstOffsetNumber;
298  else
299  tupoffset++;
300 
301  /* Done? */
302  if (tupoffset > maxoffset)
303  tupoffset = InvalidOffsetNumber;
304 
305  sampler->lt = tupoffset;
306 
307  return tupoffset;
308 }
309 
310 /*
311  * Compute greatest common divisor of two uint32's.
312  */
313 static uint32
315 {
316  uint32 c;
317 
318  while (a != 0)
319  {
320  c = a;
321  a = b % a;
322  b = c;
323  }
324 
325  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
334 {
335  uint32 r;
336 
337  /* Safety check to avoid infinite loop or zero result for small n. */
338  if (n <= 1)
339  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  {
349  r = (uint32) (sampler_random_fract(randstate) * n);
350  } while (r == 0 || gcd(r, n) > 1);
351 
352  return r;
353 }
InitSampleScan_function InitSampleScan
Definition: tsmapi.h:71
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:351
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
static OffsetNumber system_time_nextsampletuple(SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
bool repeatable_across_queries
Definition: tsmapi.h:64
static uint32 random_relative_prime(uint32 n, SamplerRandomState randstate)
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2286
void sampler_random_init_state(long seed, SamplerRandomState randstate)
Definition: sampling.c:229
double tuples
Definition: pathnodes.h:683
Oid reltablespace
Definition: pathnodes.h:672
#define INSTR_TIME_GET_MILLISEC(t)
Definition: instr_time.h:202
struct timeval instr_time
Definition: instr_time.h:150
#define Min(x, y)
Definition: c.h:911
void * tsm_state
Definition: execnodes.h:1353
double sampler_random_fract(SamplerRandomState randstate)
Definition: sampling.c:238
Definition: nodes.h:525
int errcode(int sqlerrcode)
Definition: elog.c:608
uint32 BlockNumber
Definition: block.h:31
Datum tsm_system_time_handler(PG_FUNCTION_ARGS)
static BlockNumber system_time_nextsampleblock(SampleScanState *node, BlockNumber nblocks)
unsigned short SamplerRandomState[3]
Definition: sampling.h:20
uint16 OffsetNumber
Definition: off.h:24
static uint32 gcd(uint32 a, uint32 b)
#define linitial(l)
Definition: pg_list.h:195
NextSampleTuple_function NextSampleTuple
Definition: tsmapi.h:74
PG_FUNCTION_INFO_V1(tsm_system_time_handler)
#define ERROR
Definition: elog.h:43
#define INSTR_TIME_SUBTRACT(x, y)
Definition: instr_time.h:170
char * c
#define FirstOffsetNumber
Definition: off.h:27
PG_MODULE_MAGIC
unsigned int uint32
Definition: c.h:359
NextSampleBlock_function NextSampleBlock
Definition: tsmapi.h:73
#define ereport(elevel, rest)
Definition: elog.h:141
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
SampleScanGetSampleSize_function SampleScanGetSampleSize
Definition: tsmapi.h:68
void * palloc0(Size size)
Definition: mcxt.c:980
#define DatumGetFloat8(X)
Definition: postgres.h:714
uintptr_t Datum
Definition: postgres.h:367
#define list_make1_oid(x1)
Definition: pg_list.h:249
#define InvalidOffsetNumber
Definition: off.h:26
#define makeNode(_type_)
Definition: nodes.h:573
BlockNumber pages
Definition: pathnodes.h:682
#define InvalidBlockNumber
Definition: block.h:33
BeginSampleScan_function BeginSampleScan
Definition: tsmapi.h:72
#define INSTR_TIME_SET_CURRENT(t)
Definition: instr_time.h:156
bool repeatable_across_scans
Definition: tsmapi.h:65
static void system_time_samplescangetsamplesize(PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
int errmsg(const char *fmt,...)
Definition: elog.c:822
#define PG_FUNCTION_ARGS
Definition: fmgr.h:188
List * parameterTypes
Definition: tsmapi.h:61
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
EndSampleScan_function EndSampleScan
Definition: tsmapi.h:75
double clamp_row_est(double nrows)
Definition: costsize.c:187
Definition: pg_list.h:50
static void system_time_initsamplescan(SampleScanState *node, int eflags)
static void system_time_beginsamplescan(SampleScanState *node, Datum *params, int nparams, uint32 seed)