On Thu, Sep 8, 2016 at 8:42 PM, Claudio Freire <klaussfre...@gmail.com> wrote:
> On Thu, Sep 8, 2016 at 11:54 AM, Pavan Deolasee > <pavan.deola...@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. Thanks, Pavan -- Pavan Deolasee http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services