Rewriting Free Space Map

I've started working on revamping Free Space Map, using the approach
where we store a map of heap pages on every nth heap page. What we need
now is discussion on the details of how exactly it should work.

Here's my rough plan on the implementation. It's long, sorry. I'm fairly
confident with it, but please let me know if you see any problems or
have any suggestions or better ideas.

Heap FSM
--------

The FSM is stored in the special area of every nth heap page. When
extending the relation, the heapam checks if the block number of the new
page is one that belongs to the FSM. If it is, it let's the FSM to
initialize it by calling InitFSMPage() on it, and extends the relation
again to get another, normal heap page.

I chose the "every nth page is an FSM page" approach, rather than using
a separate relfilenode, which I also considered. The separate
relfilenode approach has some advantages, like being able to scan all
FSM pages in a sequential fashion, but it involves a fair amount of
catalog and buffer manager changes.

It's convenient that the FSM uses up the whole page, leaving no room for
heap tuples. It simplifies the locking, as we don't need to worry with
the possibility in the FSM that the caller is already holding a lock on
the same page.

In an FSM page, there's one byte for each of the next N heap pages,
starting from the FSM page. That one byte stores the amount of free
space on the corresponding heap page, in BLCKSZ/256 byte precision (32
bytes with default block size).

The mapping of free space to these 256 "buckets" wouldn't necessarily
have to be a linear one, we could for example have a single bucket for
pages with more than BLCKSZ/2 bytes of free space and divide the rest
linearly into 16 byte buckets, but let's keep it simple for now. Of
course, we could also just use 2 bytes per page, and store the page size
exactly, but 32 byte precision seems like enough to me.

Index FSM
---------

Indexes use a similar scheme, but since we only need to keep track
whether a page is used or not, we only need one bit per page. If the
amount of free space on pages is interesting for an indexam in the
future, it can use the heap FSM implementation instead. Or no FSM at
all, like the hash indexam.

To use the index FSM, the indexam needs to leave every nth page alone,
like in the heap. The B-tree assumes that the metapage is at block 0,
but that's also where we would like to store the first index FSM page.
To overcome that, we can make the index FSM special area a little bit
smaller, so that the B-tree metadata fits on the same page as the FSM
information. That will be wasted space on other FSM pages than block 0,
but we're only talking about 24 bytes per FSM page, and we only need one
FSM page per ~512 MB of index pages (with default BLCKSZ).

Performance
-----------

The patch I'm working on currently uses a naive way to find a page in
the FSM. To find a page with X bytes of free space, it scans the FSM
pages until one is found. And it always starts the scan from the
beginning, which is far from optimal. And when there's page with enough
free space, it still needs to scan all FSM pages just to find out that
we need to extend the relation.

To speed things up, we're going to need some mechanism to avoid that.
First of all, we need to somehow cache the information that "there's no
page with >= X bytes left", to avoid fruitless scanning. To speed up the
case when there's only a few pages with enough free space, we can keep a
limited size list of such pages in addition to the map.

These information needs to be in shared memory, either on heap pages
like the FSM pages and managed by the buffer manager, or in a separate
shmem block. I would like to go with normal bufmgr managed pages, as
fixed-sized memory blocks have their problems, and the cached
information should be stored to disk as well.

Let's have one special page in the heap file, called the Free Space List
(FSL) page, in addition to the normal FSM pages. It has the following
structure:

struct {
bit anypages[256]

struct {
BlockNumber blockno;
uint8 freespace;
} freespacelist[as large as fits on page]
}

Remember that we track the free space on each page using one byte, IOW,
each page falls into one of 256 buckets of free space. In the anypages
bitmap, we have one bit per bucket indicating "is there any pages with
this much free space". When we look for a page with X bytes, we check
the bits up to the bucket corresponding X bytes, and if there's no set
bits we know not to bother scanning the FSM pages.

To speed up the scan where there is space, we keep a simple list of
pages with free space. This list is actually like the current FSM, but
here we only use it as a small cache of the FSM pages. VACUUM and any
other operations that update the FSM can put pages to the list when
there's free slots.

We can store the FSL page on a magic location, say block #100. For
relations smaller than that, there's no need for the FSL and we might as
well scan the FSM page. I'm not sure if we should have more than one FSL
page for large tables.

I'm not sure yet how the locking of FSL and FSM pages should work. It
shouldn't be too hard, though, as the FSM/FSL information are just hints
anyway. We do need to take care that we don't permanently lose track of
any significant amount of free space, as after we can do partial vacuums
using the visibility map, VACUUM might not visit one part of a table
even if other parts it are frequently updated.

Page allocation algorithm
-------------------------

There's many different ways we can hand out pages from the FSM. Possible
strategies, some of which are at odds with each other, include:

1. Try to spread out inserts of different backends, to avoid contention
2. Prefer low-numbered pages, to increase the chance of being able to
truncate in VACUUM.
3. Reserve pages with lots of free space for big allocations, prefer
almost full pages for small allocations. To use all space more efficiently.
4. If the table is clustered, try to use pages close to those with
similar values.
5. On UPDATE, try to use pages close to the old tuple.
6. Prefer pages that are currently in cache, to avoid I/O.

The current FSM tries to achieve only 1, and there haven't been many
complaints, so I wouldn't worry too much about the other goals. 4 and 6
would need some major changes to the buffer manager and indexam
interfaces, respectively, and 3 could lead to more I/O when you do a lot
of small inserts.

We can spread inserts of different backends in the Free Space List by
moving a page to the end of the list when it's handed out, or removing
it from there altogether. When the FSL is empty, we can vary the place
where we start to scan the FSM.

To prefer low-number pages, to increase the chance of being able to
truncate the relation later, we can favor lower numbered blocks in
VACUUM when we decide which blocks to put into the FSL. And we can also
bias the starting point of where we start to scan the FSM when the FSL
is empty.

Visibility Map
--------------

This far I've only talked about the FSM, but it's important to consider
how the Visibility Map fits into the scheme. My current thinking is that
there will be one bit per heap page in the visibility map. The exact
semantics of that one bit is still not totally clear, but that's not
important right now.

There's a few alternatives:
1. Mix the visibility map with the FSM, stealing one bit of every FSM
byte. There would then be 7 bits for storing how much space there is on
each page, and 1 bit indicating the visibility.

2. Allocate part of the FSM pages for visibility map. For example, First
1/9 of the page for VM, and 8/9 for the FSM. The VM part would be a
straight bitmap with one bit per page, and the FSM part would use one
byte per page.

3. Use different pages for the VM, for example every nth page for VM,
and every (n+1)th page for FSM.

I'm leaning towards 2 at the moment. 3 is intriguing as well, though,
because it would help with potential lock contention on the VM/FSM pages.

Per-chunk relfrozenxid
----------------------
I'm imagining that we would set a bit in VM, if a page has no dead
tuples at all, making it possible to use it for index-only scans. Such a
page is also uninteresting for VACUUM. However, we would still need to
scan the whole table to freeze tuples.

To alleviate that, we could allocate some space in the FSM pages,
indicating a smallest Xid in a range of heap pages. IOW, like
relfrozenxid, but with a granularity of N pages, rather than whole
relation. You would still have to scan that range of pages to update it,
but that's much better than the whole relation.

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