Re: Free-space-map management thoughts

Stephen Marshall <smarshall(at)wsi(dot)com> writes:
> 1. When the FSM is oversubscribed and one is trying to decide which
> pages to keep, remember that page info is stored in groups of
> CHUNK_SIZE pages, where CHUNK_SIZE is current 32.

Right, oversubscription would actually need to be measured in chunks
not single pages.

> 2. The histogram concept is a neat idea, but I think some reorganization
> of the page information might make it unnecessary. Currently the FSM
> pages are sorted by BlockNumber. This was particularly useful for
> adding information about a single page, but since that interface is no
> longer to be supported, perhaps the decision to sort by BlockNumber
> should also be revisited.

I was thinking about that, but we do still need to handle
RecordAndGetFreeSpace --- in fact that should be the most common
operation. The histogram approximation seems an okay price to pay for
not slowing down RecordAndGetFreeSpace. If you wanted to depend on
the ordering-by-free-space property to any large extent,
RecordAndGetFreeSpace would actually have to move the old page down in
the list after adjusting its free space :-(

> If we sort the page info by available space, we could then use binary
> search to find space thresholds when we are handling oversubscription.

The list-of-chunks storage layout provides only limited traction for
searching anyway, and none at all for a binary search AFAICS. I toyed
with smarter data structures such as hashes or btrees, but couldn't
convince myself that the extra space would be justified.

> Am I missing something that requires the FSM to be ordered by block number?

We could doubtless make it work either way, but I think optimizing
VACUUM at the expense of RecordAndGetFreeSpace is probably not the way
to go.

Another factor to consider is that the round-robin algorithm for handing
out pages during GetFreeSpace would behave considerably differently if
the block list is sorted by free space not block number. I'm not sure
offhand that it would be worse, but we'd have to think about the
consequences.

regards, tom lane