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