Free Space Mapping file in details

1. Overview

Previously, we discussed the MAIN fork file and corresponding extension at Heap file and page in details. This blog will explain a little bit more about the Free Space Mapping file and corresponding extension.

2. What is a Free Space Mapping file

A Free Space Mapping, FSM, file is a file that keeps tracking the availability of free space inside a page. The FSM file is used to quickly locate a page with enough
free space to hold a record to be stored during insertion, and it will be updated during an insertion or a vacuum on the table.

Start from PostgreSQL 8.4 each relation has its own extensible FSM files stored on disk. The FSM file is stored under its relation folder. From previous example,

postgres=# create table orders1 (id int4, test text) using heap;
postgres=# insert into orders1 values(1, 'hello world!');

You will see the heap files under the database folder like below,

$ ls -ltrh /home/user/pgdata/base/12705/16384*
-rw------- 1 user user  24K Oct  8 14:33 /home/user/pgdata/base/12705/16384_fsm
-rw------- 1 user user 8.0K Oct  8 14:34 /home/user/pgdata/base/12705/16384_vm
-rw------- 1 user user 512K Oct  8 14:34 /home/user/pgdata/base/12705/16384

Where 16384 is the table orders1’s oid, and 16384_fsm is the corresponding Free Space Mapping file.

3. How the Free Space Mapping files are managed

Before PostgreSQL 8.4, the FSM is maintained in memory with the limitation of fixed-size. Now, all FSM files are on disk and can be extended in the same way as heap segmentation files. The FSM files will be updated during an insertion and a Vacuum process either periodically or triggered manually. In some conditions, the FSM may need to be rebuilt, for example, if a leaf node’s value is less than the root node or if there is truncate operation.

FSM file is mainly used to quickly locate a page for insert operation and in the meantime it helps to speed up the insertion by trying to inert records in existing pages instead of extend a new page. By doing this, it not only help speed up the insertion but also help improve the selection performance. Moreover, the user to implement various strategies, like preferring pages closer to a given page, or spreading the load across the table.

4. What is inside in an FSM page

Inside the FSM page, there are two binary tree structure are used: low-level binary tree is used to record the amount of free space on each heap page; high-level binary tree is used scale up the low-level data structure. For details, please reference the README.

5. The extension for FSM

The pg_freespacemap extension provides the functions that allow you to inspect the free space in each page for a given relation/table. So far, there is only one function provide in pg_freespacemap, i.e. pg_freespace. This function can be used retrieve the amount of free space on each page by giving different parameters. To use this extension,

postgres=# create extension pg_freespacemap;
CREATE EXTENSION
postgres=# create table orders1 (id int4, test text);
CREATE TABLE
postgres=# insert into orders1 values(generate_series(1,1000), 'hello world!');
INSERT 0 1000

• retrieve free space for all pages

  postgres=# vacuum orders1;
  VACUUM
  postgres=# SELECT * FROM pg_freespace('orders1');
   blkno | avail 
  -------+-------
       0 |     0
       1 |     0
       2 |     0
       3 |     0
       4 |     0
       5 |     0
       6 |  5120
  (7 rows)

  From the above results, it tells that the first 5 pages are all full, only the last page, page6, has some free space are available.

Let’s delete different number of records in each page, and then check free space again to what is happening inside.

postgres=# delete from orders1 where id%2=1 and id < 158;
DELETE 79
postgres=# delete from orders1 where id%4=1 and id >= 158 and id < 315;
DELETE 39
postgres=# delete from orders1 where id%8=1 and id >= 315 and id < 472;
DELETE 19
postgres=# delete from orders1 where id%16=1 and id >= 472 and id < 629;
DELETE 10
postgres=# delete from orders1 where id%32=1 and id >= 629 and id < 786;
DELETE 5
postgres=# delete from orders1 where id%64=1 and id >= 786;
DELETE 3
postgres=# vacuum orders1;
VACUUM
postgres=# SELECT * FROM pg_freespace('orders1');
 blkno | avail 
-------+-------
     0 |  3776
     1 |  1856
     2 |   896
     3 |   480
     4 |   224
     5 |    96
     6 |  5184
(7 rows)

Now, we can see the amount of free space is different and it depends on how many records has been deleted.

• retrieve free space for a specific page
  The pg_freespace also allow you to check the amount of free space available in a specified page, for example,

  postgres=# SELECT * FROM pg_freespace('orders1', 3);
   pg_freespace 
  --------------
            480
  (1 row)

• insert using free space
  From the above delete examples, we know how many records deleted in each page, in other words, the maximum records can fit in for each page. Let’s perform some insertion test.

  postgres=# insert into orders1 values(generate_series(1,65), 'hello world!');
  INSERT 0 65
  postgres=# vacuum orders1;
  VACUUM
  postgres=# SELECT * FROM pg_freespace('orders1');
   blkno | avail 
  -------+-------
       0 |   672
       1 |  1856
       2 |   896
       3 |   480
       4 |   224
       5 |    96
       6 |  5184
  (7 rows)

  From the results above, we can see the records was inserted to the first page, instead of allocating a new page.

6. Summary

We explained why there is a free space mapping file under corresponding relation folder, how the free space mapping files are managed, and demonstrated how to use the extension pg_freespacemap to check what happens when user performed some insert, delete and vacuum. In next blog, I will explain the visibility mapping files.

Ref: PG Database File Layout