Hannu Krosing <hannu@tm.ee> writes:
> Another idea would be using bitmaps where we have just one bit per
> database page and do a seq scan but just over marked pages.
That seems a bit too lossy for me, but I really like your later idea
about folding. Generalizing that a little, we can choose any fold point
we like. We could allocate, say, one 32-bit word per page and set the
(i mod 32) bit when item i is fingered by the index. After retrieving
the heap page, we'd need to test all the valid rows that have item
numbers matching a set bit mod 32. On typical tables (with circa 100
items per page) this would require testing only about 3 rows per page.
ORing and ANDing of such bitmaps still works, with the understanding
that it's lossy and you have to double check each retrieved tuple.
If the fold point is above about 100, your idea of keeping track of
whether we actually set any wrapped-around bits would become useful,
but below that I think we'd just be wasting a bit.
regards, tom lane