I wrote: > Stephen Marshall <[EMAIL PROTECTED]> 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 ---------------------------(end of broadcast)--------------------------- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/users-lounge/docs/faq.html