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