Function RowSampler_Next

src/backend/utils/misc/sampling.c:155–195

}

int64
RowSampler_Next(RowSampler rs)
{
	int64       K = rs->N - rs->t;	/* remaining objects */
	int64		k = rs->n - rs->m;	/* objects still to sample */
	double		p;				    /* probability to skip object */
	double		V;				    /* random */

	Assert(RowSampler_HasMore(rs));	/* hence K > 0 and k > 0 */

	if (k >= K)
	{
		/* need all the rest */
		rs->m++;
		return rs->t++;
	}

    /* 
     * It is not obvious that this code matches Knuth's Algorithm S.
     * Refer to BlockSampler_Next() for detail.
     */
	V = sampler_random_fract(rs->randstate);
    /*
	 * Don't bother overflow of conversion from int64 K (N) as it was
	 * already converted to "double" range value when initialized.
	 */
	p = 1.0 - (double) k / (double) K;
	while (V < p)
	{
		/* skip */
		rs->t++;
		K--; /* keep K == N - t */

		/* adjust p to be new cutoff point in reduced range */
		p *= 1.0 - (double) k / (double) K;
	}

	/* select */
	rs->m++;
	return rs->t++;
}

/*
 * These two routines embody Algorithm Z from "Random sampling with a