Re: Free Space Map rewrite

Here's an updated version of the FSM rewrite. Major changes since last 
snapshot:
- WAL-logging
- Locking of operations involving multiple pages has been fixed
- contrib/pg_freespacemap has been rewritten to be useful with the new 
FSM implementation

The interesting part of this patch is the FSM implementation, 
freespace.c; I'm now working on the relation fork and xlogutils.c 
rewrite stuff as separate patches.

I've been trying to do some basic performance testing of this, but since 
FSM overhead is so small both in the old and new implementation, I 
haven't been able to tease apart any meaningful difference yet. Perhaps 
that just means that it's not something to worry about, though we have 
to watch out for degenerate worst-case scenarios.

One behavioral difference between the old and the new FSM is that in the 
old implementation, GetPageWithFreeSpace immediately subtracts the 
amount that was asked for from the FSM, but not in the new one. Updating 
the new FSM is significantly more expensive, because updates are 
WAL-logged, so I don't think it's worthwhile to do that anymore. Mind 
you that we only did that for the first insert to a page anyway; 
subsequent inserts to the target page didn't update the FSM in the old 
scheme either. Can anyone think of a use case where that would make a 
difference?

Does anyone want to suggest performance test cases for FSM?

There's one noteworthy detail in the current implementation: the FSM 
always takes at least 3 pages. That seems wasteful for small tables that 
only need 1-2 pages for the data itself. I have a solution sketched up: 
for small tables that fit on a single FSM (smaller than ~4000 pages, or 
~32 MB), use just the one FSM page, and when the table grows, switch to 
the full-blown multi-page implementation. That's pretty straightforward 
in principle, but does add a fair amount of code to cope with both 
formats, and to handle the switchover. Does anyone care? I'm thinking of 
not implementing this in the first phase, but adding it later after the 
code is committed, if there's demand.

Another related detail is that currently all searches have to traverse 
three pages, starting from the root, even if the table is small so that 
the root page contains just one child. This has already been solved in 
our b-tree implementation, with the "fast root" system, and I'm planning 
to do the same for the FSM. But again, unless we can actually come up 
with a test case that shows the overhead, do we care? In any case, this 
is again something I'd like to implement as an add-on patch after the 
first version is committed.

Heikki Linnakangas wrote:
> Hi,
> 
> Here's a new snapshot of the FSM rewrite I've been working on. The "map 
> fork" stuff hasn't been changed since last patch (I have some work to do 
> there based on Tom's recent comments), but the FSM implementation itself 
> is now starting to get in shape. So the thing to look at in this patch 
> is freespace.c. It's unreadable in diff format because the whole file 
> has basically been rewritten, you'll have to apply the patch. I've also 
> attached a README, which is also part of the patch.
> 
> Still a lot of work to be done, like ironing out race conditions between 
> updates and searches, the approach I'm planning to take there is 
> explained in the README, and WAL-logging, but I'm fairly happy with 
> what's there now.
> 


-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com


-- 
Sent via pgsql-patches mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-patches