Re: New FSM allocation policy

Tom Lane wrote:
> Gregory Stark <stark(at)enterprisedb(dot)com> writes:
>> One idea, we could scan the rest of the current page and use the first match.
>
>> Another, given the way your tree structure works you can also descend the tree
>> with a "target" page. You can find the first page with enough free space after
>> the target page if there are any. (Take left branch if it's > target and has
>> enough free space else take right branch if there's enough free space else
>> take left branch).
>
> I think the trick here is how to also preserve the property that
> different backends tend to be inserting into different pages.

Yep. If we just always look at the next page, there's the danger of
having multiple backends compete for the same pages again.

> There may
> be no very good way to do that without maintaining some shared state,
> ie the last page handed out.
>
> However, it would probably be sufficient to do that for some pretty
> small number of tables, allowing a fixed-size shared memory area to be
> sufficient.

.. similar to how we handle synchronized seqscans. Yep, that's one
option. I wish we could get rid of the shared memory area and lock
altogether, though.

We could put an extra field on the FSM root page. Hmm, it doesn't
actually need to be a single global field, so we could have a field like
that on every FSM page, for better concurrency. So the algorithm for the
set+search operation becomes:

1. Lock FSM page for the old heap page X
2. Set the value for X
3. See if the page pointed to by (fsmpage->nextPtr++) has enough free
space. If it does, return that.
4. Otherwise, start searching from root, with random traversal.

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