Re: Free-space-map management thoughts

Stephen Marshall <smarshall(at)wsi(dot)com> writes:
> If I understand the concept correctly, the histogram will only be
> calculated when MultiRecordFreeSpace is called AND the FSM is
> oversubscribed. However, when it is called, we will need to calculate a
> histogram for, and potentially trim data from, all relations that have
> entries in the FSM.

Right --- at least for calls where the particular relation's request has
gone up from before. We could skip examining the other rels when the
requested number of pages is the same or less.

> When vacuuming the entire database, we will end up with an N-squared
> loop where we iterate over all the relations in vacuum, and iterate over
> them again in each call to MultiRecordFreeSpace that occurs within each
> vacuum.

Hmm ... good point. I was thinking it was linear, but that's per
MultiRecordFreeSpace call. The total work involved for a whole-database
vacuum does look like O(N^2). Is there a way around that?

It may be that this isn't really a problem; the behavior of the existing
code could be characterized the same way. (In fact I think it could be
worse than O(N^2) depending on how often acquire_free_space ends up
getting called.) But it's something to think about.

> In any event, I don't really think this is a problem, just something to
> pay attention to. It also highlights the need to make the histogram
> calculation and free space adjustment as efficient as possible.

Yeah. We need that anyway since we'll be doing it with the FSM lock
held. (I was trying to think of ways to avoid holding the lock
throughout MultiRecordFreeSpace, but came up dry.)

regards, tom lane