Manfred Koizar <mkoi-pg@aon.at> writes:
> What I have in mind is a kind of "Double Vitter" algorithm. Whatever we
> do to get our sample of rows, in the end the sampled rows come from no
> more than sample_size different blocks. So my idea is to first create a
> random sample of sample_size block numbers, and then to sample the rows
> out of this pool of blocks.
That assumption is faulty, though --- consider wholly-empty pages.
A bigger problem is that this makes the sampling quite nonuniform,
because rows that are on relatively low-density pages would be more
likely to become part of the final sample than rows that are on pages
with lots of tuples. Thus for example your sample would tend to favor
rows with wide values of variable-width columns and exclude narrower
values. (I am not certain that the existing algorithm completely avoids
this trap, but at least it tries.)
regards, tom lane