PostgreSQL Free Space Map

When examining a PostgreSQL database instance, you will notice files with the _fsm suffix. These are Free Space Map (FSM) files, used to track the free space within a table. Here we analyze why the FSM exists and how it is designed.

Why Do We Need a Free Space Map?

As a table undergoes continuous tuple insertions and deletions, free space inevitably accumulates within tuple blocks. When a new tuple needs to be inserted, a question arises: which page should this tuple be inserted into? If we were to scan the entire table to find the first page with sufficient free space, the efficiency would be very poor. Therefore, PostgreSQL introduced the Free Space Map to quickly locate a page with enough free space to hold a new tuple, or to determine that no such page exists and the relation must be extended by one page. As stated in the PostgreSQL source README: The purpose of the free space map is to quickly locate a page with enough free space to hold a tuple to be stored; or to determine that no such page exists and the relation must be extended by one page.

How Is the FSM Designed?

To speed up lookups, the FSM file should be as small as possible. We know that a page is 8KB in size, meaning the maximum free space will not exceed 8192. Representing 8192 requires 2 bytes. To compress the FSM file size, we use a single byte to represent each page’s free space. A byte has 8 bits, with a maximum value of 255, and 8192/256 = 32. Therefore, the actual value stored in the FSM file must be multiplied by 32 to obtain the real size. A value of 0 indicates no free space.

So how is the FSM file organized? The simplest approach would be a large array.

typedef uint32 BlockNumber;

#define InvalidBlockNumber      ((BlockNumber) 0xFFFFFFFF)

#define MaxBlockNumber          ((BlockNumber) 0xFFFFFFFE)

PostgreSQL can have up to 2^32 - 1 data pages at most. If each page needed 1 byte to represent its free space, that would require 4GB of space. Searching through such a large space to find a block with sufficient free space using an array would be very inefficient — it would require an O(N) linear scan, and in the worst case traversing all the data, which is unacceptable. Therefore, PostgreSQL uses a tree structure to organize the FSM file.

The FSM file consists of 8KB FSM block pages organized in a 3-layer tree structure. Layers 0 and 1 are auxiliary layers, while layer 2 holds the actual free space values for each heap page. Each layer forms a max-heap, and within each FSM block, a local max-heap binary tree is constructed.

For example:

    4
 4     2
3 4   0 2    <- This level represents heap pages

Why a three-layer structure? Each FSM block is 8KB by default. After deducting the necessary file block header, the remaining space in the FSM block is used entirely to store the block’s internal max-heap binary tree, with each leaf node using one byte to represent free space. Based on the properties of a complete binary tree, each FSM block can hold approximately 4000 leaf nodes. With a two-layer structure, you can store 4000 * 4000 < 2^32 leaf nodes — not enough. With three layers, however, 4000 * 4000 * 4000 > 2^32, so a three-layer structure is needed.

Why use 8KB pages to store FSM data? It matches the data page Page size, allowing the buffer management logic to be reused. It is also the result of balancing hardware characteristics and operating system considerations.

The Process of Inserting a Tuple into a Table

Here we only analyze the general flow. Inserting a tuple into a table is actually quite complex, involving many details such as locking, WAL logging, transactions, and more. To insert a tuple into a table, you first need to determine which page to insert into — a page that has more free space than the size of the new tuple. This requires calling GetPageWithFreeSpace(Relation rel, Size spaceNeeded), which returns the block number of a page with the specified amount of free space.

ExecInsert
--> table_tuple_insert
    --> heapam_tuple_insert
        // insert a tuple into a heap table
        --> heap_insert
            --> RelationGetBufferForTuple(relation, heaptup->t_len, ...)
                // get a page that can hold the tuple; the page's free space
                // must be greater than heaptup->t_len
                --> GetPageWithFreeSpace(relation, targetFreeSpace);
                    // get a page with enough free space to store the tuple
                --> page = BufferGetPage(buffer);   // get the page

                --> pageFreeSpace = PageGetHeapFreeSpace(page);
                    // get the page's free space size
                --> RelationSetTargetBlock(relation, targetBlock);
                    // set the target block
            --> RelationPutHeapTuple(relation, buffer, heaptup,
                    (options & HEAP_INSERT_SPECULATIVE) != 0);
                // insert the tuple
            --> MarkBufferDirty(buffer);    // mark the buffer as dirty
            // ... insert WAL log

How to Calculate the Free Space of a Page?

According to the heap page layout, the available free space equals pd_upper - pd_lower - sizeof(ItemIdData).

Size PageGetFreeSpace(Page page)
{
    int         space;
    // calculate the free space size
    space = (int) ((PageHeader) page)->pd_upper -
        (int) ((PageHeader) page)->pd_lower;
    // if the free space is less than the size of ItemIdData, return 0
    if (space < (int) sizeof(ItemIdData))
        return 0;
    space -= sizeof(ItemIdData);
    // subtract the size of ItemIdData, because inserting data
    // actually consumes additional ItemIdData space
    return (Size) space;
}

When Is the FSM Updated?

In PostgreSQL, space reclamation is performed via auto-vacuum or by manually executing VACUUM. Vacuum cleans up pages in the table, recalculates the free space, and updates the FSM file.

vacuum_rel
--> vacuum_open_relation
    // when executing vacuum, the table must be locked;
    // vacuum full requires AccessExclusiveLock,
    // otherwise ShareUpdateExclusiveLock
--> table_relation_vacuum(rel, params, vac_strategy);
    --> heap_vacuum_rel(rel, params, bstrategy)
        --> lazy_scan_heap(vacrel, params, aggressive);
            // performs lazy vacuum, as distinguished from full vacuum
            --> for (blkno = 0; blkno < nblocks; blkno++)
                {
                    // get the buffer corresponding to the block number
                    buf = ReadBufferExtended(vacrel->rel, MAIN_FORKNUM,
                            blkno, RBM_NORMAL, vacrel->bstrategy);

                    page = BufferGetPage(buf);

                    // prune the page
                    lazy_scan_prune(vacrel, buf, blkno, page,
                            vistest, &prunestate);
                    --> heap_page_prune

                    // get the page's free space size
                    Size freespace = PageGetHeapFreeSpace(page);
                    // update the FSM
                    RecordPageWithFreeSpace(vacrel->rel, blkno, freespace);
                    --> fsm_set_and_search(rel, addr, slot, new_cat, 0);
                        --> fsm_readbuf(rel, addr, true);
                        --> fsm_set_avail(page, slot, newValue)
                }