PostgreSQL Source Code: src/backend/access/tablesample/bernoulli.c Source File

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-2025, 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 "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 tuples with hash less than this */
40 uint32 seed; /* random seed */
41 OffsetNumber lt; /* last tuple returned from current block */
42} BernoulliSamplerData;
43
44
45static void bernoulli_samplescangetsamplesize(PlannerInfo *root,
46 RelOptInfo *baserel,
47 List *paramexprs,
48 BlockNumber *pages,
49 double *tuples);
50static void bernoulli_initsamplescan(SampleScanState *node,
51 int eflags);
52static void bernoulli_beginsamplescan(SampleScanState *node,
53 Datum *params,
54 int nparams,
55 uint32 seed);
56static OffsetNumber bernoulli_nextsampletuple(SampleScanState *node,
57 BlockNumber blockno,
58 OffsetNumber maxoffset);
59
60
61/*
62 * Create a TsmRoutine descriptor for the BERNOULLI method.
63 */
64Datum
65 tsm_bernoulli_handler(PG_FUNCTION_ARGS)
66{
67 TsmRoutine *tsm = makeNode(TsmRoutine);
68
69 tsm->parameterTypes = list_make1_oid(FLOAT4OID);
70 tsm->repeatable_across_queries = true;
71 tsm->repeatable_across_scans = true;
72 tsm->SampleScanGetSampleSize = bernoulli_samplescangetsamplesize;
73 tsm->InitSampleScan = bernoulli_initsamplescan;
74 tsm->BeginSampleScan = bernoulli_beginsamplescan;
75 tsm->NextSampleBlock = NULL;
76 tsm->NextSampleTuple = bernoulli_nextsampletuple;
77 tsm->EndSampleScan = NULL;
78
79 PG_RETURN_POINTER(tsm);
80}
81
82/*
83 * Sample size estimation.
84 */
85static void
86 bernoulli_samplescangetsamplesize(PlannerInfo *root,
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 */
126static void
127 bernoulli_initsamplescan(SampleScanState *node, int eflags)
128{
129 node->tsm_state = palloc0(sizeof(BernoulliSamplerData));
130}
131
132/*
133 * Examine parameters and prepare for a sample scan.
134 */
135static void
136 bernoulli_beginsamplescan(SampleScanState *node,
137 Datum *params,
138 int nparams,
139 uint32 seed)
140{
141 BernoulliSamplerData *sampler = (BernoulliSamplerData *) node->tsm_state;
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 */
180static OffsetNumber
181 bernoulli_nextsampletuple(SampleScanState *node,
182 BlockNumber blockno,
183 OffsetNumber maxoffset)
184{
185 BernoulliSamplerData *sampler = (BernoulliSamplerData *) node->tsm_state;
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}
static void bernoulli_samplescangetsamplesize(PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
Definition: bernoulli.c:86
static void bernoulli_initsamplescan(SampleScanState *node, int eflags)
Definition: bernoulli.c:127
Datum tsm_bernoulli_handler(PG_FUNCTION_ARGS)
Definition: bernoulli.c:65
static void bernoulli_beginsamplescan(SampleScanState *node, Datum *params, int nparams, uint32 seed)
Definition: bernoulli.c:136
static OffsetNumber bernoulli_nextsampletuple(SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
Definition: bernoulli.c:181
uint32 BlockNumber
Definition: block.h:31
#define PG_UINT32_MAX
Definition: c.h:595
uint64_t uint64
Definition: c.h:539
uint32_t uint32
Definition: c.h:538
float float4
Definition: c.h:634
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2403
double clamp_row_est(double nrows)
Definition: costsize.c:213
int errcode(int sqlerrcode)
Definition: elog.c:854
int errmsg(const char *fmt,...)
Definition: elog.c:1071
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:150
#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
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:81
void * palloc0(Size size)
Definition: mcxt.c:1395
#define IsA(nodeptr, _type_)
Definition: nodes.h:164
#define makeNode(_type_)
Definition: nodes.h:161
#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:232
static float4 DatumGetFloat4(Datum X)
Definition: postgres.h:441
uint64_t Datum
Definition: postgres.h:70
tree ctl root
Definition: radixtree.h:1857
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:715
OffsetNumber lt
Definition: bernoulli.c:41
Definition: primnodes.h:324
Definition: pg_list.h:54
Definition: nodes.h:135
Cardinality tuples
Definition: pathnodes.h:981
BlockNumber pages
Definition: pathnodes.h:980
bool use_bulkread
Definition: execnodes.h:1643
void * tsm_state
Definition: execnodes.h:1642
bool use_pagemode
Definition: execnodes.h:1644
Definition: tsmapi.h:57
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

AltStyle によって変換されたページ (->オリジナル) /