Re: Free-space-map management thoughts

I wrote:
> Stephen Marshall <smarshall(at)wsi(dot)com> writes:
>> 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.

Here's a possibly off-the-wall idea: maybe the list-of-chunks
representation is not too simple, but too complex. Suppose we stored
all the FSM page data as one big array (of ItemPointerData elements).
Any given relation would own a section of this array in which its page
data is sorted in page-number order. Then RecordAndGetFreeSpace could
use a binary search to locate the old page it needs to update.

This would be noticeably faster as far as lookup operations go, but the
Achilles' heel would be inserting new data: in general you'd need to
push stuff around in the page array to make room. Given fast memcpy()
this might not be too bad though. Alternatively, the data-copying could
be combined with the scan we'd likely be making to remove undersized
pages.

Anyone like this idea? Or should I leave well enough alone?

regards, tom lane