Re: Free Space Map thoughts

Heikki Linnakangas wrote:
> Alvaro Herrera wrote:
>> Simon Riggs wrote:
>>> Presumably we would not store an FSM for small tables? On the basis that
>>> the purpose of the FSM is to save on pointless I/O there must be a size
>>> of table below which an FSM is just overhead.
>> Hmm, do you mean that we would open and verify every page of a small
>> relation until we find one with free space?  That doesn't sound very
>> good.
>
> There is a threshold somewhere. If the heap consists of just one page, 
> clearly the FSM doesn't give any benefit. If it's two pages, it's probably 
> still faster to just check the two pages. Somewhere after that the FSM 
> starts to pay off.

Right.  If you have a 1-page table, and put the first FSM page in page
0, the table is now two pages, so there is a 50% wastage.  But if the
table grows you cannot move all the tuples from page 0 to create the FSM
there.  On the other hand, all tables are 1 page long at a certain
point.

One idea is to have the first FSM page be movable, and create it by
extending the table when as soon as it's first "needed" (this would be
the first vacuum that needs to record free space on the table).  The
page number used is recorded in the relcache entry (and pg_class).
Further FSM pages use a fixed position.  If the table grows beyond the
first fixed position before creating the first FSM page, reserve that
one for the first FSM page and record that.

However I agree this starts to get a little too complex, and the idea of
storing it in a separate file is suddenly attractive.

> Whether the overhead is big enough that we care to optimize by not having 
> the FSM for tiny tables, I don't know. Probably not. If the FSM is stored 
> in the heap file, it's tricky to add the FSM after the fact. If it's a 
> separate file, creating the FSM requires catalog changes.

Creating the FSM is a one-time operation, so I wouldn't be very worried
about performance considerations.

-- 
Alvaro Herrera                                http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support