Stephen Marshall <[EMAIL PROTECTED]> 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 ---------------------------(end of broadcast)--------------------------- TIP 4: Don't 'kill -9' the postmaster