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