On Thu, Sep 8, 2016 at 11:54 AM, Pavan Deolasee <pavan.deolasee@gmail.com> wrote: > For example, for a table with 60 bytes wide tuple (including 24 byte > header), each page can approximately have 8192/60 = 136 tuples. Say we > provision for 136*2 = 272 bits per page i.e. 34 bytes per page for the > bitmap. First 272 offsets in every page are represented in the bitmap and > anything greater than are in overflow region. On the other hand, the current > representation will need about 16 bytes per page assuming 2% dead tuples, 40 > bytes per page assuming 5% dead tuples and 80 bytes assuming 10% dead > tuples. So bitmap will take more space for small tuples or when vacuum is > run very aggressively, both seems unlikely for very large tables. Of course > the calculation does not take into account the space needed by the overflow > area, but I expect that too be small.
I thought about something like this, but it could be extremely inefficient for mostly frozen tables, since the bitmap cannot account for frozen pages without losing the O(1) lookup characteristic
Well, that's correct. But I thought the whole point is when there are large number of dead tuples which requires large memory. If my math was correct as explained above, then even at 5% dead tuples, bitmap representation will consume approximate same memory but provide O(1) search time.
