Florian Pflug <fgp@phlo.org> writes:
> This all hinges on the ability to produce a sufficient accurate estimate of the
> TID density p_tup/p_tid, of course.
I think that's the least of its problems. AFAICS this analysis ignores
(1) the problem that the TID space is nonuniform, ie we don't know how
many tuples in each page until we look;
(2) the problem that we don't know the overall number of tuples
beforehand.
I'm not sure that there is any way to deal with (1) fully without
examining every single page, but algorithms that assume that the TIDs
are numbered linearly are broken before they start.
regards, tom lane