sampling.h File Reference

#include "common/pg_prng.h"
#include "storage/block.h"

Include dependency graph for sampling.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	BlockSamplerData
struct	ReservoirStateData

Typedefs
typedef BlockSamplerData *	BlockSampler
typedef ReservoirStateData *	ReservoirState

Functions
void	sampler_random_init_state (uint32 seed, pg_prng_state *randstate)
double	sampler_random_fract (pg_prng_state *randstate)
BlockNumber	BlockSampler_Init (BlockSampler bs, BlockNumber nblocks, int samplesize, uint32 randseed)
bool	BlockSampler_HasMore (BlockSampler bs)
BlockNumber	BlockSampler_Next (BlockSampler bs)
void	reservoir_init_selection_state (ReservoirState rs, int n)
double	reservoir_get_next_S (ReservoirState rs, double t, int n)
double	anl_random_fract (void)
double	anl_init_selection_state (int n)
double	anl_get_next_S (double t, int n, double *stateptr)

Typedef Documentation

BlockSampler

typedef BlockSamplerData* BlockSampler

Definition at line 37 of file sampling.h.

ReservoirState

typedef ReservoirStateData* ReservoirState

Definition at line 52 of file sampling.h.

Function Documentation

anl_get_next_S()

double anl_get_next_S ( double  t, int  n, double *  stateptr  )

extern

Definition at line 296 of file sampling.c.

{
    double      result;
 
    oldrs.W = *stateptr;
    result = reservoir_get_next_S(&oldrs, t, n);
    *stateptr = oldrs.W;
    return result;
}

References fb(), oldrs, reservoir_get_next_S(), and ReservoirStateData::W.

anl_init_selection_state()

double anl_init_selection_state ( int  n )

extern

Definition at line 281 of file sampling.c.

{
    /* initialize if first time through */
    if (unlikely(!oldrs_initialized))
    {
        sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state),
                                  &oldrs.randstate);
        oldrs_initialized = true;
    }
 
    /* Initial value of W (for use when Algorithm Z is first applied) */
    return exp(-log(sampler_random_fract(&oldrs.randstate)) / n);
}

References fb(), oldrs, oldrs_initialized, pg_global_prng_state, pg_prng_uint32(), ReservoirStateData::randstate, sampler_random_fract(), sampler_random_init_state(), and unlikely.

anl_random_fract()

double anl_random_fract ( void  )

extern

Definition at line 266 of file sampling.c.

{
    /* initialize if first time through */
    if (unlikely(!oldrs_initialized))
    {
        sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state),
                                  &oldrs.randstate);
        oldrs_initialized = true;
    }
 
    /* and compute a random fraction */
    return sampler_random_fract(&oldrs.randstate);
}

References oldrs, oldrs_initialized, pg_global_prng_state, pg_prng_uint32(), ReservoirStateData::randstate, sampler_random_fract(), sampler_random_init_state(), and unlikely.

BlockSampler_HasMore()

bool BlockSampler_HasMore ( BlockSampler  bs )

extern

Definition at line 58 of file sampling.c.

{
    return (bs->t < bs->N) && (bs->m < bs->n);
}

References fb().

Referenced by block_sampling_read_stream_next(), and BlockSampler_Next().

BlockSampler_Init()

BlockNumber BlockSampler_Init ( BlockSampler  bs, BlockNumber  nblocks, int  samplesize, uint32  randseed  )

extern

Definition at line 39 of file sampling.c.

{
    bs->N = nblocks;            /* measured table size */
 
    /*
     * If we decide to reduce samplesize for tables that have less or not much
     * more than samplesize blocks, here is the place to do it.
     */
    bs->n = samplesize;
    bs->t = 0;                  /* blocks scanned so far */
    bs->m = 0;                  /* blocks selected so far */
 
    sampler_random_init_state(randseed, &bs->randstate);
 
    return Min(bs->n, bs->N);
}

References fb(), Min, and sampler_random_init_state().

Referenced by acquire_sample_rows().

BlockSampler_Next()

BlockNumber BlockSampler_Next ( BlockSampler  bs )

extern

Definition at line 64 of file sampling.c.

{
    BlockNumber K = bs->N - bs->t;  /* remaining blocks */
    int         k = bs->n - bs->m;  /* blocks still to sample */
    double      p;              /* probability to skip block */
    double      V;              /* random */
 
    Assert(BlockSampler_HasMore(bs));   /* hence K > 0 and k > 0 */
 
    if ((BlockNumber) k >= K)
    {
        /* need all the rest */
        bs->m++;
        return bs->t++;
    }
 
    /*----------
     * It is not obvious that this code matches Knuth's Algorithm S.
     * Knuth says to skip the current block with probability 1 - k/K.
     * If we are to skip, we should advance t (hence decrease K), and
     * repeat the same probabilistic test for the next block.  The naive
     * implementation thus requires a sampler_random_fract() call for each
     * block number.  But we can reduce this to one sampler_random_fract()
     * call per selected block, by noting that each time the while-test
     * succeeds, we can reinterpret V as a uniform random number in the range
     * 0 to p. Therefore, instead of choosing a new V, we just adjust p to be
     * the appropriate fraction of its former value, and our next loop
     * makes the appropriate probabilistic test.
     *
     * We have initially K > k > 0.  If the loop reduces K to equal k,
     * the next while-test must fail since p will become exactly zero
     * (we assume there will not be roundoff error in the division).
     * (Note: Knuth suggests a "<=" loop condition, but we use "<" just
     * to be doubly sure about roundoff error.)  Therefore K cannot become
     * less than k, which means that we cannot fail to select enough blocks.
     *----------
     */
    V = sampler_random_fract(&bs->randstate);
    p = 1.0 - (double) k / (double) K;
    while (V < p)
    {
        /* skip */
        bs->t++;
        K--;                    /* keep K == N - t */
 
        /* adjust p to be new cutoff point in reduced range */
        p *= 1.0 - (double) k / (double) K;
    }
 
    /* select */
    bs->m++;
    return bs->t++;
}

References Assert, BlockSampler_HasMore(), fb(), K, and sampler_random_fract().

Referenced by block_sampling_read_stream_next().

reservoir_get_next_S()

double reservoir_get_next_S ( ReservoirState  rs, double  t, int  n  )

extern

Definition at line 147 of file sampling.c.

{
    double      S;
 
    /* The magic constant here is T from Vitter's paper */
    if (t <= (22.0 * n))
    {
        /* Process records using Algorithm X until t is large enough */
        double      V,
                    quot;
 
        V = sampler_random_fract(&rs->randstate);   /* Generate V */
        S = 0;
        t += 1;
        /* Note: "num" in Vitter's code is always equal to t - n */
        quot = (t - (double) n) / t;
        /* Find min S satisfying (4.1) */
        while (quot > V)
        {
            S += 1;
            t += 1;
            quot *= (t - (double) n) / t;
        }
    }
    else
    {
        /* Now apply Algorithm Z */
        double      W = rs->W;
        double      term = t - (double) n + 1;
 
        for (;;)
        {
            double      numer,
                        numer_lim,
                        denom;
            double      U,
                        X,
                        lhs,
                        rhs,
                        y,
                        tmp;
 
            /* Generate U and X */
            U = sampler_random_fract(&rs->randstate);
            X = t * (W - 1.0);
            S = floor(X);       /* S is tentatively set to floor(X) */
            /* Test if U <= h(S)/cg(X) in the manner of (6.3) */
            tmp = (t + 1) / term;
            lhs = exp(log(((U * tmp * tmp) * (term + S)) / (t + X)) / n);
            rhs = (((t + X) / (term + S)) * term) / t;
            if (lhs <= rhs)
            {
                W = rhs / lhs;
                break;
            }
            /* Test if U <= f(S)/cg(X) */
            y = (((U * (t + 1)) / term) * (t + S + 1)) / (t + X);
            if ((double) n < S)
            {
                denom = t;
                numer_lim = term + S;
            }
            else
            {
                denom = t - (double) n + S;
                numer_lim = t + 1;
            }
            for (numer = t + S; numer >= numer_lim; numer -= 1)
            {
                y *= numer / denom;
                denom -= 1;
            }
            W = exp(-log(sampler_random_fract(&rs->randstate)) / n);    /* Generate W in advance */
            if (exp(log(y) / n) <= (t + X) / t)
                break;
        }
        rs->W = W;
    }
    return S;
}

References fb(), ReservoirStateData::randstate, S, sampler_random_fract(), W, ReservoirStateData::W, and y.

Referenced by acquire_sample_rows(), analyze_row_processor(), anl_get_next_S(), and file_acquire_sample_rows().

reservoir_init_selection_state()

void reservoir_init_selection_state ( ReservoirState  rs, int  n  )

extern

Definition at line 133 of file sampling.c.

{
    /*
     * Reservoir sampling is not used anywhere where it would need to return
     * repeatable results so we can initialize it randomly.
     */
    sampler_random_init_state(pg_prng_uint32(&pg_global_prng_state),
                              &rs->randstate);
 
    /* Initial value of W (for use when Algorithm Z is first applied) */
    rs->W = exp(-log(sampler_random_fract(&rs->randstate)) / n);
}

References fb(), pg_global_prng_state, pg_prng_uint32(), ReservoirStateData::randstate, sampler_random_fract(), sampler_random_init_state(), and ReservoirStateData::W.

Referenced by acquire_sample_rows(), file_acquire_sample_rows(), and postgresAcquireSampleRowsFunc().

sampler_random_fract()

double sampler_random_fract ( pg_prng_state *  randstate )

extern

Definition at line 241 of file sampling.c.

{
    double      res;
 
    /* pg_prng_double returns a value in [0.0 - 1.0), so we must reject 0.0 */
    do
    {
        res = pg_prng_double(randstate);
    } while (unlikely(res == 0.0));
    return res;
}

References pg_prng_double(), and unlikely.

Referenced by acquire_sample_rows(), analyze_row_processor(), anl_init_selection_state(), anl_random_fract(), BlockSampler_Next(), file_acquire_sample_rows(), random_relative_prime(), random_relative_prime(), reservoir_get_next_S(), reservoir_init_selection_state(), system_rows_nextsampleblock(), and system_time_nextsampleblock().

sampler_random_init_state()

void sampler_random_init_state ( uint32  seed, pg_prng_state *  randstate  )

extern

Definition at line 234 of file sampling.c.

{
    pg_prng_seed(randstate, (uint64) seed);
}

References pg_prng_seed().

Referenced by anl_init_selection_state(), anl_random_fract(), BlockSampler_Init(), reservoir_init_selection_state(), system_rows_nextsampleblock(), and system_time_nextsampleblock().