Re: Free Space Map data structure

Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> ... what I really wanted to discuss is the data structure needed
> for the Free Space Map.

> The FSM data structure needs to support two basic operations:
> 1. Fast lookup of page with >= X bytes of free space
> 2. Update of arbitrary, individual pages.
> Our current code doesn't support 2, as we always update the FSM in bulk
> after vacuum, but we will need that capability to be able to do partial
> vacuums in the future.

Note that the lack of such infrastructure is mainly because we didn't
need it, not because it couldn't be done. But in any case the current
implementation is a loser, agreed.

> One brilliant idea I had, is a binary heap/tree kind of structure, where
> each heap page is represented by one leaf node.

I'm worried about a couple of things here:

* Loss of concurrency in access to the FSM itself, due to updates having
to change large amounts of interrelated entries, and due to all
processes always wanting to touch the root first.

* Loss of concurrency in subsequent heap updates. The current FSM gets
one thing right: if different backends ask for space, they will (if at
all possible) be given different heap pages to insert into, and
therefore will not suffer page-level contention while they do their
insertions. I don't see what you'll do to ensure a comparable behavior
with this structure.

> Unfortunately, this data structure isn't easily pageable. It still seems
> like a good and simple structure within a page, but we need a way to
> scale it.

I suggest that you *not* scale it. It seems possibly useful to have
this kind of structure within a single map page, but trying to go above
that will result in too much contention IMHO.

regards, tom lane