PostgreSQL Source Code  git master
system.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * system.c
4  * support routines for SYSTEM tablesample method
5  *
6  * To ensure repeatability of samples, it is necessary that selection of a
7  * given tuple be history-independent; otherwise syncscanning would break
8  * repeatability, to say nothing of logically-irrelevant maintenance such
9  * as physical extension or shortening of the relation.
10  *
11  * To achieve that, we proceed by hashing each candidate block number together
12  * with the active seed, and then selecting it if the hash is less than the
13  * cutoff value computed from the selection probability by BeginSampleScan.
14  *
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  * src/backend/access/tablesample/system.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/hash.h"
33 #include "access/relscan.h"
34 #include "access/tsmapi.h"
35 #include "catalog/pg_type.h"
36 #include "optimizer/clauses.h"
37 #include "optimizer/cost.h"
38 #include "utils/builtins.h"
39 
40 
41 /* Private state */
42 typedef struct
43 {
44  uint64 cutoff; /* select blocks with hash less than this */
45  uint32 seed; /* random seed */
46  BlockNumber nextblock; /* next block to consider sampling */
47  OffsetNumber lt; /* last tuple returned from current block */
49 
50 
52  RelOptInfo *baserel,
53  List *paramexprs,
54  BlockNumber *pages,
55  double *tuples);
56 static void system_initsamplescan(SampleScanState *node,
57  int eflags);
58 static void system_beginsamplescan(SampleScanState *node,
59  Datum *params,
60  int nparams,
61  uint32 seed);
64  BlockNumber blockno,
65  OffsetNumber maxoffset);
66 
67 
68 /*
69  * Create a TsmRoutine descriptor for the SYSTEM method.
70  */
71 Datum
73 {
75 
77  tsm->repeatable_across_queries = true;
78  tsm->repeatable_across_scans = true;
84  tsm->EndSampleScan = NULL;
85 
86  PG_RETURN_POINTER(tsm);
87 }
88 
89 /*
90  * Sample size estimation.
91  */
92 static void
94  RelOptInfo *baserel,
95  List *paramexprs,
96  BlockNumber *pages,
97  double *tuples)
98 {
99  Node *pctnode;
100  float4 samplefract;
101 
102  /* Try to extract an estimate for the sample percentage */
103  pctnode = (Node *) linitial(paramexprs);
104  pctnode = estimate_expression_value(root, pctnode);
105 
106  if (IsA(pctnode, Const) &&
107  !((Const *) pctnode)->constisnull)
108  {
109  samplefract = DatumGetFloat4(((Const *) pctnode)->constvalue);
110  if (samplefract >= 0 && samplefract <= 100 && !isnan(samplefract))
111  samplefract /= 100.0f;
112  else
113  {
114  /* Default samplefract if the value is bogus */
115  samplefract = 0.1f;
116  }
117  }
118  else
119  {
120  /* Default samplefract if we didn't obtain a non-null Const */
121  samplefract = 0.1f;
122  }
123 
124  /* We'll visit a sample of the pages ... */
125  *pages = clamp_row_est(baserel->pages * samplefract);
126 
127  /* ... and hopefully get a representative number of tuples from them */
128  *tuples = clamp_row_est(baserel->tuples * samplefract);
129 }
130 
131 /*
132  * Initialize during executor setup.
133  */
134 static void
136 {
137  node->tsm_state = palloc0(sizeof(SystemSamplerData));
138 }
139 
140 /*
141  * Examine parameters and prepare for a sample scan.
142  */
143 static void
145  Datum *params,
146  int nparams,
147  uint32 seed)
148 {
149  SystemSamplerData *sampler = (SystemSamplerData *) node->tsm_state;
150  double percent = DatumGetFloat4(params[0]);
151  double dcutoff;
152 
153  if (percent < 0 || percent > 100 || isnan(percent))
154  ereport(ERROR,
155  (errcode(ERRCODE_INVALID_TABLESAMPLE_ARGUMENT),
156  errmsg("sample percentage must be between 0 and 100")));
157 
158  /*
159  * The cutoff is sample probability times (PG_UINT32_MAX + 1); we have to
160  * store that as a uint64, of course. Note that this gives strictly
161  * correct behavior at the limits of zero or one probability.
162  */
163  dcutoff = rint(((double) PG_UINT32_MAX + 1) * percent / 100);
164  sampler->cutoff = (uint64) dcutoff;
165  sampler->seed = seed;
166  sampler->nextblock = 0;
167  sampler->lt = InvalidOffsetNumber;
168 
169  /*
170  * Bulkread buffer access strategy probably makes sense unless we're
171  * scanning a very small fraction of the table. The 1% cutoff here is a
172  * guess. We should use pagemode visibility checking, since we scan all
173  * tuples on each selected page.
174  */
175  node->use_bulkread = (percent >= 1);
176  node->use_pagemode = true;
177 }
178 
179 /*
180  * Select next block to sample.
181  */
182 static BlockNumber
184 {
185  SystemSamplerData *sampler = (SystemSamplerData *) node->tsm_state;
186  HeapScanDesc scan = node->ss.ss_currentScanDesc;
187  BlockNumber nextblock = sampler->nextblock;
188  uint32 hashinput[2];
189 
190  /*
191  * We compute the hash by applying hash_any to an array of 2 uint32's
192  * containing the block number and seed. This is efficient to set up, and
193  * with the current implementation of hash_any, it gives
194  * machine-independent results, which is a nice property for regression
195  * testing.
196  *
197  * These words in the hash input are the same throughout the block:
198  */
199  hashinput[1] = sampler->seed;
200 
201  /*
202  * Loop over block numbers until finding suitable block or reaching end of
203  * relation.
204  */
205  for (; nextblock < scan->rs_nblocks; nextblock++)
206  {
207  uint32 hash;
208 
209  hashinput[0] = nextblock;
210 
211  hash = DatumGetUInt32(hash_any((const unsigned char *) hashinput,
212  (int) sizeof(hashinput)));
213  if (hash < sampler->cutoff)
214  break;
215  }
216 
217  if (nextblock < scan->rs_nblocks)
218  {
219  /* Found a suitable block; remember where we should start next time */
220  sampler->nextblock = nextblock + 1;
221  return nextblock;
222  }
223 
224  /* Done, but let's reset nextblock to 0 for safety. */
225  sampler->nextblock = 0;
226  return InvalidBlockNumber;
227 }
228 
229 /*
230  * Select next sampled tuple in current block.
231  *
232  * In block sampling, we just want to sample all the tuples in each selected
233  * block.
234  *
235  * It is OK here to return an offset without knowing if the tuple is visible
236  * (or even exists); nodeSamplescan.c will deal with that.
237  *
238  * When we reach end of the block, return InvalidOffsetNumber which tells
239  * SampleScan to go to next block.
240  */
241 static OffsetNumber
243  BlockNumber blockno,
244  OffsetNumber maxoffset)
245 {
246  SystemSamplerData *sampler = (SystemSamplerData *) node->tsm_state;
247  OffsetNumber tupoffset = sampler->lt;
248 
249  /* Advance to next possible offset on page */
250  if (tupoffset == InvalidOffsetNumber)
251  tupoffset = FirstOffsetNumber;
252  else
253  tupoffset++;
254 
255  /* Done? */
256  if (tupoffset > maxoffset)
257  tupoffset = InvalidOffsetNumber;
258 
259  sampler->lt = tupoffset;
260 
261  return tupoffset;
262 }
InitSampleScan_function InitSampleScan
Definition: tsmapi.h:70
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
#define DatumGetUInt32(X)
Definition: postgres.h:492
static OffsetNumber system_nextsampletuple(SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
Definition: system.c:242
#define IsA(nodeptr, _type_)
Definition: nodes.h:561
bool repeatable_across_queries
Definition: tsmapi.h:63
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2492
double tuples
Definition: relation.h:625
void * tsm_state
Definition: execnodes.h:1130
Definition: nodes.h:510
static BlockNumber system_nextsampleblock(SampleScanState *node)
Definition: system.c:183
int errcode(int sqlerrcode)
Definition: elog.c:575
uint32 BlockNumber
Definition: block.h:31
static void system_initsamplescan(SampleScanState *node, int eflags)
Definition: system.c:135
#define PG_UINT32_MAX
Definition: c.h:380
uint16 OffsetNumber
Definition: off.h:24
#define linitial(l)
Definition: pg_list.h:111
NextSampleTuple_function NextSampleTuple
Definition: tsmapi.h:73
#define ERROR
Definition: elog.h:43
#define FirstOffsetNumber
Definition: off.h:27
unsigned int uint32
Definition: c.h:296
NextSampleBlock_function NextSampleBlock
Definition: tsmapi.h:72
double rint(double x)
Definition: rint.c:22
Datum tsm_system_handler(PG_FUNCTION_ARGS)
Definition: system.c:72
#define ereport(elevel, rest)
Definition: elog.h:122
SampleScanGetSampleSize_function SampleScanGetSampleSize
Definition: tsmapi.h:67
float float4
Definition: c.h:428
#define FLOAT4OID
Definition: pg_type.h:416
void * palloc0(Size size)
Definition: mcxt.c:877
OffsetNumber lt
Definition: system.c:47
uintptr_t Datum
Definition: postgres.h:372
#define list_make1_oid(x1)
Definition: pg_list.h:151
uint64 cutoff
Definition: system.c:44
#define InvalidOffsetNumber
Definition: off.h:26
#define makeNode(_type_)
Definition: nodes.h:558
BlockNumber pages
Definition: relation.h:624
uint32 seed
Definition: system.c:45
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:428
#define DatumGetFloat4(X)
Definition: postgres.h:686
#define InvalidBlockNumber
Definition: block.h:33
BlockNumber nextblock
Definition: system.c:46
BeginSampleScan_function BeginSampleScan
Definition: tsmapi.h:71
bool repeatable_across_scans
Definition: tsmapi.h:64
HeapScanDesc ss_currentScanDesc
Definition: execnodes.h:1105
int errmsg(const char *fmt,...)
Definition: elog.c:797
static void system_beginsamplescan(SampleScanState *node, Datum *params, int nparams, uint32 seed)
Definition: system.c:144
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
List * parameterTypes
Definition: tsmapi.h:60
static void system_samplescangetsamplesize(PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
Definition: system.c:93
EndSampleScan_function EndSampleScan
Definition: tsmapi.h:74
double clamp_row_est(double nrows)
Definition: costsize.c:174
Definition: pg_list.h:45
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
ScanState ss
Definition: execnodes.h:1125