PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
tsm_system_rows.c File Reference
#include "postgres.h"
#include "access/relscan.h"
#include "access/tsmapi.h"
#include "catalog/pg_type.h"
#include "miscadmin.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "utils/sampling.h"
Include dependency graph for tsm_system_rows.c:

Go to the source code of this file.

Data Structures

struct  SystemRowsSamplerData
 

Functions

 PG_FUNCTION_INFO_V1 (tsm_system_rows_handler)
 
static void system_rows_samplescangetsamplesize (PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
 
static void system_rows_initsamplescan (SampleScanState *node, int eflags)
 
static void system_rows_beginsamplescan (SampleScanState *node, Datum *params, int nparams, uint32 seed)
 
static BlockNumber system_rows_nextsampleblock (SampleScanState *node)
 
static OffsetNumber system_rows_nextsampletuple (SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
 
static bool SampleOffsetVisible (OffsetNumber tupoffset, HeapScanDesc scan)
 
static uint32 random_relative_prime (uint32 n, SamplerRandomState randstate)
 
Datum tsm_system_rows_handler (PG_FUNCTION_ARGS)
 
static uint32 gcd (uint32 a, uint32 b)
 

Variables

 PG_MODULE_MAGIC
 

Function Documentation

static uint32 gcd ( uint32  a,
uint32  b 
)
static

Definition at line 355 of file tsm_system_rows.c.

Referenced by random_relative_prime().

356 {
357  uint32 c;
358 
359  while (a != 0)
360  {
361  c = a;
362  a = b % a;
363  b = c;
364  }
365 
366  return b;
367 }
char * c
unsigned int uint32
Definition: c.h:268
PG_FUNCTION_INFO_V1 ( tsm_system_rows_handler  )
static uint32 random_relative_prime ( uint32  n,
SamplerRandomState  randstate 
)
static

Definition at line 374 of file tsm_system_rows.c.

References CHECK_FOR_INTERRUPTS, gcd(), and sampler_random_fract().

Referenced by system_rows_nextsampleblock().

375 {
376  uint32 r;
377 
378  /* Safety check to avoid infinite loop or zero result for small n. */
379  if (n <= 1)
380  return 1;
381 
382  /*
383  * This should only take 2 or 3 iterations as the probability of 2 numbers
384  * being relatively prime is ~61%; but just in case, we'll include a
385  * CHECK_FOR_INTERRUPTS in the loop.
386  */
387  do
388  {
390  r = (uint32) (sampler_random_fract(randstate) * n);
391  } while (r == 0 || gcd(r, n) > 1);
392 
393  return r;
394 }
double sampler_random_fract(SamplerRandomState randstate)
Definition: sampling.c:238
unsigned int uint32
Definition: c.h:268
static uint32 gcd(uint32 a, uint32 b)
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:97
static bool SampleOffsetVisible ( OffsetNumber  tupoffset,
HeapScanDesc  scan 
)
static

Definition at line 330 of file tsm_system_rows.c.

References HeapScanDescData::rs_ntuples, and HeapScanDescData::rs_vistuples.

Referenced by system_rows_nextsampletuple().

331 {
332  int start = 0,
333  end = scan->rs_ntuples - 1;
334 
335  while (start <= end)
336  {
337  int mid = (start + end) / 2;
338  OffsetNumber curoffset = scan->rs_vistuples[mid];
339 
340  if (tupoffset == curoffset)
341  return true;
342  else if (tupoffset < curoffset)
343  end = mid - 1;
344  else
345  start = mid + 1;
346  }
347 
348  return false;
349 }
uint16 OffsetNumber
Definition: off.h:24
OffsetNumber rs_vistuples[MaxHeapTuplesPerPage]
Definition: relscan.h:77
static void system_rows_beginsamplescan ( SampleScanState node,
Datum params,
int  nparams,
uint32  seed 
)
static

Definition at line 175 of file tsm_system_rows.c.

References DatumGetInt64, SystemRowsSamplerData::doneblocks, SystemRowsSamplerData::donetuples, ereport, errcode(), errmsg(), ERROR, InvalidOffsetNumber, SystemRowsSamplerData::lt, SystemRowsSamplerData::ntuples, SystemRowsSamplerData::seed, SampleScanState::tsm_state, and SampleScanState::use_pagemode.

Referenced by tsm_system_rows_handler().

179 {
181  int64 ntuples = DatumGetInt64(params[0]);
182 
183  if (ntuples < 0)
184  ereport(ERROR,
185  (errcode(ERRCODE_INVALID_TABLESAMPLE_ARGUMENT),
186  errmsg("sample size must not be negative")));
187 
188  sampler->seed = seed;
189  sampler->ntuples = ntuples;
190  sampler->donetuples = 0;
191  sampler->lt = InvalidOffsetNumber;
192  sampler->doneblocks = 0;
193  /* lb will be initialized during first NextSampleBlock call */
194  /* we intentionally do not change nblocks/firstblock/step here */
195 
196  /*
197  * We *must* use pagemode visibility checking in this module, so force
198  * that even though it's currently default.
199  */
200  node->use_pagemode = true;
201 }
void * tsm_state
Definition: execnodes.h:1071
int errcode(int sqlerrcode)
Definition: elog.c:575
#define ERROR
Definition: elog.h:43
#define DatumGetInt64(X)
Definition: postgres.h:613
#define ereport(elevel, rest)
Definition: elog.h:122
#define InvalidOffsetNumber
Definition: off.h:26
int errmsg(const char *fmt,...)
Definition: elog.c:797
static void system_rows_initsamplescan ( SampleScanState node,
int  eflags 
)
static

Definition at line 165 of file tsm_system_rows.c.

References palloc0(), and SampleScanState::tsm_state.

Referenced by tsm_system_rows_handler().

166 {
167  node->tsm_state = palloc0(sizeof(SystemRowsSamplerData));
168  /* Note the above leaves tsm_state->step equal to zero */
169 }
void * tsm_state
Definition: execnodes.h:1071
void * palloc0(Size size)
Definition: mcxt.c:878
static BlockNumber system_rows_nextsampleblock ( SampleScanState node)
static

Definition at line 209 of file tsm_system_rows.c.

References SystemRowsSamplerData::doneblocks, SystemRowsSamplerData::donetuples, SystemRowsSamplerData::firstblock, InvalidBlockNumber, SystemRowsSamplerData::lb, SystemRowsSamplerData::nblocks, SystemRowsSamplerData::ntuples, random_relative_prime(), sampler_random_fract(), sampler_random_init_state(), SystemRowsSamplerData::seed, SampleScanState::ss, ScanState::ss_currentScanDesc, SystemRowsSamplerData::step, and SampleScanState::tsm_state.

Referenced by tsm_system_rows_handler().

210 {
212  HeapScanDesc scan = node->ss.ss_currentScanDesc;
213 
214  /* First call within scan? */
215  if (sampler->doneblocks == 0)
216  {
217  /* First scan within query? */
218  if (sampler->step == 0)
219  {
220  /* Initialize now that we have scan descriptor */
221  SamplerRandomState randstate;
222 
223  /* If relation is empty, there's nothing to scan */
224  if (scan->rs_nblocks == 0)
225  return InvalidBlockNumber;
226 
227  /* We only need an RNG during this setup step */
228  sampler_random_init_state(sampler->seed, randstate);
229 
230  /* Compute nblocks/firstblock/step only once per query */
231  sampler->nblocks = scan->rs_nblocks;
232 
233  /* Choose random starting block within the relation */
234  /* (Actually this is the predecessor of the first block visited) */
235  sampler->firstblock = sampler_random_fract(randstate) *
236  sampler->nblocks;
237 
238  /* Find relative prime as step size for linear probing */
239  sampler->step = random_relative_prime(sampler->nblocks, randstate);
240  }
241 
242  /* Reinitialize lb */
243  sampler->lb = sampler->firstblock;
244  }
245 
246  /* If we've read all blocks or returned all needed tuples, we're done */
247  if (++sampler->doneblocks > sampler->nblocks ||
248  sampler->donetuples >= sampler->ntuples)
249  return InvalidBlockNumber;
250 
251  /*
252  * It's probably impossible for scan->rs_nblocks to decrease between scans
253  * within a query; but just in case, loop until we select a block number
254  * less than scan->rs_nblocks. We don't care if scan->rs_nblocks has
255  * increased since the first scan.
256  */
257  do
258  {
259  /* Advance lb, using uint64 arithmetic to forestall overflow */
260  sampler->lb = ((uint64) sampler->lb + sampler->step) % sampler->nblocks;
261  } while (sampler->lb >= scan->rs_nblocks);
262 
263  return sampler->lb;
264 }
void sampler_random_init_state(long seed, SamplerRandomState randstate)
Definition: sampling.c:229
void * tsm_state
Definition: execnodes.h:1071
double sampler_random_fract(SamplerRandomState randstate)
Definition: sampling.c:238
unsigned short SamplerRandomState[3]
Definition: sampling.h:20
#define InvalidBlockNumber
Definition: block.h:33
static uint32 random_relative_prime(uint32 n, SamplerRandomState randstate)
HeapScanDesc ss_currentScanDesc
Definition: execnodes.h:1046
ScanState ss
Definition: execnodes.h:1066
static OffsetNumber system_rows_nextsampletuple ( SampleScanState node,
BlockNumber  blockno,
OffsetNumber  maxoffset 
)
static

Definition at line 276 of file tsm_system_rows.c.

References Assert, SystemRowsSamplerData::donetuples, FirstOffsetNumber, InvalidOffsetNumber, SystemRowsSamplerData::lt, SystemRowsSamplerData::ntuples, SampleOffsetVisible(), SampleScanState::ss, ScanState::ss_currentScanDesc, and SampleScanState::tsm_state.

Referenced by tsm_system_rows_handler().

279 {
281  HeapScanDesc scan = node->ss.ss_currentScanDesc;
282  OffsetNumber tupoffset = sampler->lt;
283 
284  /* Quit if we've returned all needed tuples */
285  if (sampler->donetuples >= sampler->ntuples)
286  return InvalidOffsetNumber;
287 
288  /*
289  * Because we should only count visible tuples as being returned, we need
290  * to search for a visible tuple rather than just let the core code do it.
291  */
292 
293  /* We rely on the data accumulated in pagemode access */
294  Assert(scan->rs_pageatatime);
295  for (;;)
296  {
297  /* Advance to next possible offset on page */
298  if (tupoffset == InvalidOffsetNumber)
299  tupoffset = FirstOffsetNumber;
300  else
301  tupoffset++;
302 
303  /* Done? */
304  if (tupoffset > maxoffset)
305  {
306  tupoffset = InvalidOffsetNumber;
307  break;
308  }
309 
310  /* Found a candidate? */
311  if (SampleOffsetVisible(tupoffset, scan))
312  {
313  sampler->donetuples++;
314  break;
315  }
316  }
317 
318  sampler->lt = tupoffset;
319 
320  return tupoffset;
321 }
void * tsm_state
Definition: execnodes.h:1071
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
#define InvalidOffsetNumber
Definition: off.h:26
static bool SampleOffsetVisible(OffsetNumber tupoffset, HeapScanDesc scan)
#define Assert(condition)
Definition: c.h:675
HeapScanDesc ss_currentScanDesc
Definition: execnodes.h:1046
ScanState ss
Definition: execnodes.h:1066
static void system_rows_samplescangetsamplesize ( PlannerInfo root,
RelOptInfo baserel,
List paramexprs,
BlockNumber pages,
double *  tuples 
)
static

Definition at line 106 of file tsm_system_rows.c.

References clamp_row_est(), DatumGetInt64, estimate_expression_value(), IsA, linitial, Min, RelOptInfo::pages, and RelOptInfo::tuples.

Referenced by tsm_system_rows_handler().

111 {
112  Node *limitnode;
113  int64 ntuples;
114  double npages;
115 
116  /* Try to extract an estimate for the limit rowcount */
117  limitnode = (Node *) linitial(paramexprs);
118  limitnode = estimate_expression_value(root, limitnode);
119 
120  if (IsA(limitnode, Const) &&
121  !((Const *) limitnode)->constisnull)
122  {
123  ntuples = DatumGetInt64(((Const *) limitnode)->constvalue);
124  if (ntuples < 0)
125  {
126  /* Default ntuples if the value is bogus */
127  ntuples = 1000;
128  }
129  }
130  else
131  {
132  /* Default ntuples if we didn't obtain a non-null Const */
133  ntuples = 1000;
134  }
135 
136  /* Clamp to the estimated relation size */
137  if (ntuples > baserel->tuples)
138  ntuples = (int64) baserel->tuples;
139  ntuples = clamp_row_est(ntuples);
140 
141  if (baserel->tuples > 0 && baserel->pages > 0)
142  {
143  /* Estimate number of pages visited based on tuple density */
144  double density = baserel->tuples / (double) baserel->pages;
145 
146  npages = ntuples / density;
147  }
148  else
149  {
150  /* For lack of data, assume one tuple per page */
151  npages = ntuples;
152  }
153 
154  /* Clamp to sane value */
155  npages = clamp_row_est(Min((double) baserel->pages, npages));
156 
157  *pages = npages;
158  *tuples = ntuples;
159 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:557
Node * estimate_expression_value(PlannerInfo *root, Node *node)
Definition: clauses.c:2399
double tuples
Definition: relation.h:534
#define Min(x, y)
Definition: c.h:806
Definition: nodes.h:506
#define linitial(l)
Definition: pg_list.h:110
#define DatumGetInt64(X)
Definition: postgres.h:613
BlockNumber pages
Definition: relation.h:533
double clamp_row_est(double nrows)
Definition: costsize.c:173
Datum tsm_system_rows_handler ( PG_FUNCTION_ARGS  )

Definition at line 82 of file tsm_system_rows.c.

References TsmRoutine::BeginSampleScan, TsmRoutine::EndSampleScan, TsmRoutine::InitSampleScan, INT8OID, list_make1_oid, makeNode, TsmRoutine::NextSampleBlock, TsmRoutine::NextSampleTuple, NULL, TsmRoutine::parameterTypes, PG_RETURN_POINTER, TsmRoutine::repeatable_across_queries, TsmRoutine::repeatable_across_scans, TsmRoutine::SampleScanGetSampleSize, system_rows_beginsamplescan(), system_rows_initsamplescan(), system_rows_nextsampleblock(), system_rows_nextsampletuple(), and system_rows_samplescangetsamplesize().

83 {
85 
87 
88  /* See notes at head of file */
89  tsm->repeatable_across_queries = false;
90  tsm->repeatable_across_scans = true;
91 
97  tsm->EndSampleScan = NULL;
98 
99  PG_RETURN_POINTER(tsm);
100 }
InitSampleScan_function InitSampleScan
Definition: tsmapi.h:70
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
bool repeatable_across_queries
Definition: tsmapi.h:63
NextSampleTuple_function NextSampleTuple
Definition: tsmapi.h:73
static BlockNumber system_rows_nextsampleblock(SampleScanState *node)
static void system_rows_samplescangetsamplesize(PlannerInfo *root, RelOptInfo *baserel, List *paramexprs, BlockNumber *pages, double *tuples)
NextSampleBlock_function NextSampleBlock
Definition: tsmapi.h:72
SampleScanGetSampleSize_function SampleScanGetSampleSize
Definition: tsmapi.h:67
#define list_make1_oid(x1)
Definition: pg_list.h:145
#define INT8OID
Definition: pg_type.h:304
static void system_rows_initsamplescan(SampleScanState *node, int eflags)
#define makeNode(_type_)
Definition: nodes.h:554
#define NULL
Definition: c.h:229
static void system_rows_beginsamplescan(SampleScanState *node, Datum *params, int nparams, uint32 seed)
static OffsetNumber system_rows_nextsampletuple(SampleScanState *node, BlockNumber blockno, OffsetNumber maxoffset)
BeginSampleScan_function BeginSampleScan
Definition: tsmapi.h:71
bool repeatable_across_scans
Definition: tsmapi.h:64
List * parameterTypes
Definition: tsmapi.h:60
EndSampleScan_function EndSampleScan
Definition: tsmapi.h:74

Variable Documentation

PG_MODULE_MAGIC

Definition at line 39 of file tsm_system_rows.c.