PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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 
42 
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 */
60 
62  RelOptInfo *baserel,
63  List *paramexprs,
64  BlockNumber *pages,
65  double *tuples);
67  int eflags);
69  Datum *params,
70  int nparams,
71  uint32 seed);
74  BlockNumber blockno,
75  OffsetNumber maxoffset);
77 
78 
79 /*
80  * Create a TsmRoutine descriptor for the SYSTEM_TIME method.
81  */
82 Datum
84 {
86 
88 
89  /* See notes at head of file */
90  tsm->repeatable_across_queries = false;
91  tsm->repeatable_across_scans = false;
92 
98  tsm->EndSampleScan = NULL;
99 
100  PG_RETURN_POINTER(tsm);
101 }
102 
103 /*
104  * Sample size estimation.
105  */
106 static void
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 */
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
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
193  Datum *params,
194  int nparams,
195  uint32 seed)
196 {
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
220 {
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;
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
294  BlockNumber blockno,
295  OffsetNumber maxoffset)
296 {
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
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
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  {
354  r = (uint32) (sampler_random_fract(randstate) * n);
355  } while (r == 0 || gcd(r, n) > 1);
356 
357  return r;
358 }
InitSampleScan_function InitSampleScan
Definition: tsmapi.h:70
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
static OffsetNumber system_time_nextsampletuple(SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
bool repeatable_across_queries
Definition: tsmapi.h:63
static uint32 random_relative_prime(uint32 n, SamplerRandomState randstate)
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2433
void sampler_random_init_state(long seed, SamplerRandomState randstate)
Definition: sampling.c:229
double tuples
Definition: relation.h:565
Oid reltablespace
Definition: relation.h:554
#define INSTR_TIME_GET_MILLISEC(t)
Definition: instr_time.h:199
struct timeval instr_time
Definition: instr_time.h:147
#define Min(x, y)
Definition: c.h:806
void * tsm_state
Definition: execnodes.h:1102
double sampler_random_fract(SamplerRandomState randstate)
Definition: sampling.c:238
Definition: nodes.h:509
int errcode(int sqlerrcode)
Definition: elog.c:575
uint32 BlockNumber
Definition: block.h:31
Datum tsm_system_time_handler(PG_FUNCTION_ARGS)
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:111
NextSampleTuple_function NextSampleTuple
Definition: tsmapi.h:73
PG_FUNCTION_INFO_V1(tsm_system_time_handler)
#define ERROR
Definition: elog.h:43
#define INSTR_TIME_SUBTRACT(x, y)
Definition: instr_time.h:167
static BlockNumber system_time_nextsampleblock(SampleScanState *node)
char * c
#define FirstOffsetNumber
Definition: off.h:27
PG_MODULE_MAGIC
unsigned int uint32
Definition: c.h:268
NextSampleBlock_function NextSampleBlock
Definition: tsmapi.h:72
#define ereport(elevel, rest)
Definition: elog.h:122
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:67
void * palloc0(Size size)
Definition: mcxt.c:878
#define DatumGetFloat8(X)
Definition: postgres.h:734
uintptr_t Datum
Definition: postgres.h:372
#define list_make1_oid(x1)
Definition: pg_list.h:151
#define InvalidOffsetNumber
Definition: off.h:26
#define makeNode(_type_)
Definition: nodes.h:557
BlockNumber pages
Definition: relation.h:564
#define NULL
Definition: c.h:229
#define InvalidBlockNumber
Definition: block.h:33
#define FLOAT8OID
Definition: pg_type.h:419
BeginSampleScan_function BeginSampleScan
Definition: tsmapi.h:71
#define INSTR_TIME_SET_CURRENT(t)
Definition: instr_time.h:153
bool repeatable_across_scans
Definition: tsmapi.h:64
static void system_time_samplescangetsamplesize(PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
HeapScanDesc ss_currentScanDesc
Definition: execnodes.h:1077
int errmsg(const char *fmt,...)
Definition: elog.c:797
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
List * parameterTypes
Definition: tsmapi.h:60
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:100
EndSampleScan_function EndSampleScan
Definition: tsmapi.h:74
double clamp_row_est(double nrows)
Definition: costsize.c:173
Definition: pg_list.h:45
static void system_time_initsamplescan(SampleScanState *node, int eflags)
static void system_time_beginsamplescan(SampleScanState *node, Datum *params, int nparams, uint32 seed)
ScanState ss
Definition: execnodes.h:1097