PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
bernoulli.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * bernoulli.c
4  * support routines for BERNOULLI 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 TID together with
12  * 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/bernoulli.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/tsmapi.h"
34 #include "catalog/pg_type.h"
35 #include "optimizer/clauses.h"
36 #include "optimizer/cost.h"
37 #include "utils/builtins.h"
38 
39 
40 /* Private state */
41 typedef struct
42 {
43  uint64 cutoff; /* select tuples with hash less than this */
44  uint32 seed; /* random seed */
45  OffsetNumber lt; /* last tuple returned from current block */
47 
48 
50  RelOptInfo *baserel,
51  List *paramexprs,
52  BlockNumber *pages,
53  double *tuples);
55  int eflags);
57  Datum *params,
58  int nparams,
59  uint32 seed);
61  BlockNumber blockno,
62  OffsetNumber maxoffset);
63 
64 
65 /*
66  * Create a TsmRoutine descriptor for the BERNOULLI method.
67  */
68 Datum
70 {
72 
74  tsm->repeatable_across_queries = true;
75  tsm->repeatable_across_scans = true;
79  tsm->NextSampleBlock = NULL;
81  tsm->EndSampleScan = NULL;
82 
83  PG_RETURN_POINTER(tsm);
84 }
85 
86 /*
87  * Sample size estimation.
88  */
89 static void
91  RelOptInfo *baserel,
92  List *paramexprs,
93  BlockNumber *pages,
94  double *tuples)
95 {
96  Node *pctnode;
97  float4 samplefract;
98 
99  /* Try to extract an estimate for the sample percentage */
100  pctnode = (Node *) linitial(paramexprs);
101  pctnode = estimate_expression_value(root, pctnode);
102 
103  if (IsA(pctnode, Const) &&
104  !((Const *) pctnode)->constisnull)
105  {
106  samplefract = DatumGetFloat4(((Const *) pctnode)->constvalue);
107  if (samplefract >= 0 && samplefract <= 100 && !isnan(samplefract))
108  samplefract /= 100.0f;
109  else
110  {
111  /* Default samplefract if the value is bogus */
112  samplefract = 0.1f;
113  }
114  }
115  else
116  {
117  /* Default samplefract if we didn't obtain a non-null Const */
118  samplefract = 0.1f;
119  }
120 
121  /* We'll visit all pages of the baserel */
122  *pages = baserel->pages;
123 
124  *tuples = clamp_row_est(baserel->tuples * samplefract);
125 }
126 
127 /*
128  * Initialize during executor setup.
129  */
130 static void
132 {
133  node->tsm_state = palloc0(sizeof(BernoulliSamplerData));
134 }
135 
136 /*
137  * Examine parameters and prepare for a sample scan.
138  */
139 static void
141  Datum *params,
142  int nparams,
143  uint32 seed)
144 {
146  double percent = DatumGetFloat4(params[0]);
147  double dcutoff;
148 
149  if (percent < 0 || percent > 100 || isnan(percent))
150  ereport(ERROR,
151  (errcode(ERRCODE_INVALID_TABLESAMPLE_ARGUMENT),
152  errmsg("sample percentage must be between 0 and 100")));
153 
154  /*
155  * The cutoff is sample probability times (PG_UINT32_MAX + 1); we have to
156  * store that as a uint64, of course. Note that this gives strictly
157  * correct behavior at the limits of zero or one probability.
158  */
159  dcutoff = rint(((double) PG_UINT32_MAX + 1) * percent / 100);
160  sampler->cutoff = (uint64) dcutoff;
161  sampler->seed = seed;
162  sampler->lt = InvalidOffsetNumber;
163 
164  /*
165  * Use bulkread, since we're scanning all pages. But pagemode visibility
166  * checking is a win only at larger sampling fractions. The 25% cutoff
167  * here is based on very limited experimentation.
168  */
169  node->use_bulkread = true;
170  node->use_pagemode = (percent >= 25);
171 }
172 
173 /*
174  * Select next sampled tuple in current block.
175  *
176  * It is OK here to return an offset without knowing if the tuple is visible
177  * (or even exists). The reason is that we do the coinflip for every tuple
178  * offset in the table. Since all tuples have the same probability of being
179  * returned, it doesn't matter if we do extra coinflips for invisible tuples.
180  *
181  * When we reach end of the block, return InvalidOffsetNumber which tells
182  * SampleScan to go to next block.
183  */
184 static OffsetNumber
186  BlockNumber blockno,
187  OffsetNumber maxoffset)
188 {
190  OffsetNumber tupoffset = sampler->lt;
191  uint32 hashinput[3];
192 
193  /* Advance to first/next tuple in block */
194  if (tupoffset == InvalidOffsetNumber)
195  tupoffset = FirstOffsetNumber;
196  else
197  tupoffset++;
198 
199  /*
200  * We compute the hash by applying hash_any to an array of 3 uint32's
201  * containing the block, offset, and seed. This is efficient to set up,
202  * and with the current implementation of hash_any, it gives
203  * machine-independent results, which is a nice property for regression
204  * testing.
205  *
206  * These words in the hash input are the same throughout the block:
207  */
208  hashinput[0] = blockno;
209  hashinput[2] = sampler->seed;
210 
211  /*
212  * Loop over tuple offsets until finding suitable TID or reaching end of
213  * block.
214  */
215  for (; tupoffset <= maxoffset; tupoffset++)
216  {
217  uint32 hash;
218 
219  hashinput[1] = tupoffset;
220 
221  hash = DatumGetUInt32(hash_any((const unsigned char *) hashinput,
222  (int) sizeof(hashinput)));
223  if (hash < sampler->cutoff)
224  break;
225  }
226 
227  if (tupoffset > maxoffset)
228  tupoffset = InvalidOffsetNumber;
229 
230  sampler->lt = tupoffset;
231 
232  return tupoffset;
233 }
InitSampleScan_function InitSampleScan
Definition: tsmapi.h:70
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
#define DatumGetUInt32(X)
Definition: postgres.h:492
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
bool repeatable_across_queries
Definition: tsmapi.h:63
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2433
static void bernoulli_beginsamplescan(SampleScanState *node, Datum *params, int nparams, uint32 seed)
Definition: bernoulli.c:140
double tuples
Definition: relation.h:565
void * tsm_state
Definition: execnodes.h:1085
Definition: nodes.h:509
int errcode(int sqlerrcode)
Definition: elog.c:575
uint32 BlockNumber
Definition: block.h:31
#define PG_UINT32_MAX
Definition: c.h:341
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
Datum tsm_bernoulli_handler(PG_FUNCTION_ARGS)
Definition: bernoulli.c:69
unsigned int uint32
Definition: c.h:268
NextSampleBlock_function NextSampleBlock
Definition: tsmapi.h:72
double rint(double x)
Definition: rint.c:22
#define ereport(elevel, rest)
Definition: elog.h:122
SampleScanGetSampleSize_function SampleScanGetSampleSize
Definition: tsmapi.h:67
float float4
Definition: c.h:380
#define FLOAT4OID
Definition: pg_type.h:416
void * palloc0(Size size)
Definition: mcxt.c:878
uintptr_t Datum
Definition: postgres.h:372
OffsetNumber lt
Definition: bernoulli.c:45
#define list_make1_oid(x1)
Definition: pg_list.h:151
static void bernoulli_initsamplescan(SampleScanState *node, int eflags)
Definition: bernoulli.c:131
#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
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
#define DatumGetFloat4(X)
Definition: postgres.h:686
static OffsetNumber bernoulli_nextsampletuple(SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
Definition: bernoulli.c:185
BeginSampleScan_function BeginSampleScan
Definition: tsmapi.h:71
bool repeatable_across_scans
Definition: tsmapi.h:64
static void bernoulli_samplescangetsamplesize(PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
Definition: bernoulli.c:90
int errmsg(const char *fmt,...)
Definition: elog.c:797
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
List * parameterTypes
Definition: tsmapi.h:60
EndSampleScan_function EndSampleScan
Definition: tsmapi.h:74
double clamp_row_est(double nrows)
Definition: costsize.c:173
Definition: pg_list.h:45
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541