Re: Free Space Map data structure

On Tue, Apr 8, 2008 at 2:03 PM, Heikki Linnakangas
<heikki(at)enterprisedb(dot)com> wrote:

> Our current code doesn't support 2, as we always update the FSM in bulk
> after vacuum, but we will need that capability to be able to do partial
> vacuums in the future.
>

+1 for that. This will be extremely useful to update FSM after HOT prune/defrag.
Right now, the page free space is only available for subsequent UPDATEs in
the page.

>
> Thoughts? Any other data structures that better fill the bill?
>

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)

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, this could be completely orthogonal to suggestions you are seeking,
but nevertheless I had this thought for quite some time. So just wanted
to speak about it :-)

Thanks,
Pavan

--
Pavan Deolasee
EnterpriseDB http://www.enterprisedb.com