Pavan Deolasee wrote:
Can we not use bitmaps to track approximate rather than exact free space ? For example, we can have 8 or 16 buckets of free space. A page with 1-32 bytes free, goes into bucket 1, a page with at 33-64 bytes free, goes into bucket 2 and so on. If you want a page with X bytes free, look into the next immediate larger bucket. (the ranges can varry here)
Yep, that's actually what I was planning to do, except I was thinking of using 8 bits per page, or 256 buckets, because that makes the code a little bit simpler. 16 buckets would probably be enough in practice, though.
Also, the free space doesn't necessarily need to be divided linearly into buckets, we could for example use 8 buckets like:
0 32 1 64 2 128 3 256 4 512 5 1024 6 2048 7 4096
This would give us O(1) time for FSM updates. To speed up lookup, we can use hierarchical bitmaps. Lets work through an example for 8 buckets: At the segment level, we have one FSM page. That can summarize FSM info for ~8000 heap page (1 bit per page per bucket). In addition, we can have first level hierarchy in the same page where one bit, say summarizes info for 100 pages. So if there a page with 'bucket' worth of free space in the first 100 pages in the segment, the corresponding bit in the first hierarchy will be set. In this case, the first level hierarchy would need 80 bits per bucket i.e 80 bytes. We can then extend the concept of segments to say, 'extents'. One FSM page per extent summarizes the FSM info for segments in that extent. With the same logic as above, we can have ~8000 segments per extent. And then one FSM page to summarize info for all extents. I guess at that level we would run out of maximum supported file size anyways.
Well, if you add the higher levels, we're no longer talking about O(1), but O(log n) (for a pretty steep logarithm), just like my proposal.
Well, this could be completely orthogonal to suggestions you are seeking, but nevertheless I had this thought for quite some time.
It's actually not that orthogonal. You describe it as a hierarchical bitmap, but it's essentially the same idea as the binary heap/tree, just with way more than 2 children per parent.
-- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
