Branch data Line data Source code
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-2026, 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 : :
45 : : static void bernoulli_samplescangetsamplesize(PlannerInfo *root,
46 : : RelOptInfo *baserel,
47 : : List *paramexprs,
48 : : BlockNumber *pages,
49 : : double *tuples);
50 : : static void bernoulli_initsamplescan(SampleScanState *node,
51 : : int eflags);
52 : : static void bernoulli_beginsamplescan(SampleScanState *node,
53 : : Datum *params,
54 : : int nparams,
55 : : uint32 seed);
56 : : static OffsetNumber bernoulli_nextsampletuple(SampleScanState *node,
57 : : BlockNumber blockno,
58 : : OffsetNumber maxoffset);
59 : :
60 : :
61 : : /*
62 : : * Create a TsmRoutine descriptor for the BERNOULLI method.
63 : : */
64 : : Datum
65 : 76 : tsm_bernoulli_handler(PG_FUNCTION_ARGS)
66 : : {
67 : 76 : TsmRoutine *tsm = makeNode(TsmRoutine);
68 : :
69 : 76 : tsm->parameterTypes = list_make1_oid(FLOAT4OID);
70 : 76 : tsm->repeatable_across_queries = true;
71 : 76 : tsm->repeatable_across_scans = true;
72 : 76 : tsm->SampleScanGetSampleSize = bernoulli_samplescangetsamplesize;
73 : 76 : tsm->InitSampleScan = bernoulli_initsamplescan;
74 : 76 : tsm->BeginSampleScan = bernoulli_beginsamplescan;
75 : 76 : tsm->NextSampleBlock = NULL;
76 : 76 : tsm->NextSampleTuple = bernoulli_nextsampletuple;
77 : 76 : tsm->EndSampleScan = NULL;
78 : :
79 : 152 : PG_RETURN_POINTER(tsm);
80 : 76 : }
81 : :
82 : : /*
83 : : * Sample size estimation.
84 : : */
85 : : static void
86 : 20 : bernoulli_samplescangetsamplesize(PlannerInfo *root,
87 : : RelOptInfo *baserel,
88 : : List *paramexprs,
89 : : BlockNumber *pages,
90 : : double *tuples)
91 : : {
92 : 20 : Node *pctnode;
93 : 20 : float4 samplefract;
94 : :
95 : : /* Try to extract an estimate for the sample percentage */
96 : 20 : pctnode = (Node *) linitial(paramexprs);
97 : 20 : pctnode = estimate_expression_value(root, pctnode);
98 : :
99 [ + + - + ]: 20 : if (IsA(pctnode, Const) &&
100 : 17 : !((Const *) pctnode)->constisnull)
101 : : {
102 : 17 : samplefract = DatumGetFloat4(((Const *) pctnode)->constvalue);
103 [ + + + + : 17 : if (samplefract >= 0 && samplefract <= 100 && !isnan(samplefract))
+ - - + #
# ]
104 : 15 : samplefract /= 100.0f;
105 : : else
106 : : {
107 : : /* Default samplefract if the value is bogus */
108 : 2 : samplefract = 0.1f;
109 : : }
110 : 17 : }
111 : : else
112 : : {
113 : : /* Default samplefract if we didn't obtain a non-null Const */
114 : 3 : samplefract = 0.1f;
115 : : }
116 : :
117 : : /* We'll visit all pages of the baserel */
118 : 20 : *pages = baserel->pages;
119 : :
120 : 20 : *tuples = clamp_row_est(baserel->tuples * samplefract);
121 : 20 : }
122 : :
123 : : /*
124 : : * Initialize during executor setup.
125 : : */
126 : : static void
127 : 20 : bernoulli_initsamplescan(SampleScanState *node, int eflags)
128 : : {
129 : 20 : node->tsm_state = palloc0(sizeof(BernoulliSamplerData));
130 : 20 : }
131 : :
132 : : /*
133 : : * Examine parameters and prepare for a sample scan.
134 : : */
135 : : static void
136 : 15 : bernoulli_beginsamplescan(SampleScanState *node,
137 : : Datum *params,
138 : : int nparams,
139 : : uint32 seed)
140 : : {
141 : 15 : BernoulliSamplerData *sampler = (BernoulliSamplerData *) node->tsm_state;
142 : 15 : double percent = DatumGetFloat4(params[0]);
143 : 15 : double dcutoff;
144 : :
145 [ + + - + : 15 : if (percent < 0 || percent > 100 || isnan(percent))
+ - ]
146 [ + - + - ]: 2 : 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 : 13 : dcutoff = rint(((double) PG_UINT32_MAX + 1) * percent / 100);
156 : 13 : sampler->cutoff = (uint64) dcutoff;
157 : 13 : sampler->seed = seed;
158 : 13 : 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 : 13 : node->use_bulkread = true;
166 : 13 : node->use_pagemode = (percent >= 25);
167 : 13 : }
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
181 : 21472 : bernoulli_nextsampletuple(SampleScanState *node,
182 : : BlockNumber blockno,
183 : : OffsetNumber maxoffset)
184 : : {
185 : 21472 : BernoulliSamplerData *sampler = (BernoulliSamplerData *) node->tsm_state;
186 : 21472 : OffsetNumber tupoffset = sampler->lt;
187 : 21472 : uint32 hashinput[3];
188 : :
189 : : /* Advance to first/next tuple in block */
190 [ + + ]: 21472 : if (tupoffset == InvalidOffsetNumber)
191 : 1398 : tupoffset = FirstOffsetNumber;
192 : : else
193 : 20074 : 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 : 21472 : hashinput[0] = blockno;
205 : 21472 : hashinput[2] = sampler->seed;
206 : :
207 : : /*
208 : : * Loop over tuple offsets until finding suitable TID or reaching end of
209 : : * block.
210 : : */
211 [ + + ]: 41506 : for (; tupoffset <= maxoffset; tupoffset++)
212 : : {
213 : 40108 : uint32 hash;
214 : :
215 : 40108 : hashinput[1] = tupoffset;
216 : :
217 : 40108 : hash = DatumGetUInt32(hash_any((const unsigned char *) hashinput,
218 : : (int) sizeof(hashinput)));
219 [ + + ]: 40108 : if (hash < sampler->cutoff)
220 : 20074 : break;
221 [ - + + ]: 40108 : }
222 : :
223 [ + + ]: 21472 : if (tupoffset > maxoffset)
224 : 1398 : tupoffset = InvalidOffsetNumber;
225 : :
226 : 21472 : sampler->lt = tupoffset;
227 : :
228 : 42944 : return tupoffset;
229 : 21472 : }
|
