# Free Space Map (карта свободного места)

_Хранение и формат на диске · PostgreSQL Knowledge Base_

**TL;DR:** Карта свободного места (_fsm) хранит для каждой страницы таблицы, сколько
в ней свободно места, с точностью до 32 байт. По ней вставка быстро находит
страницу с достаточным зазором, не сканируя таблицу. Карту обновляет VACUUM;
у крошечных таблиц её может не быть вовсе.


Когда нужно вставить строку, PostgreSQL должен найти страницу, где она
поместится. Сканировать ради этого всю таблицу было бы дорого. Поэтому у
каждой таблицы есть **карта свободного места** - отдельный форк `_fsm`
(см. [relfilenode-forks](/courses/postgres/kb/relfilenode-forks.md)), который для каждой страницы помнит размер
свободного зазора.

## Грубо, но быстро

Карта хранит свободное место не побайтово, а категориями: диапазон 8 КБ
делится на 256 ступеней по 32 байта, и для страницы пишется одна ступень
(0-255). Точность в 32 байта тут не вредит: вставке не нужно знать
свободное место до байта, ей хватает «влезет / не влезет». Зато вся карта
получается крошечной - один байт на страницу данных.

Внутри `_fsm` ступени уложены деревом, поэтому запрос «дай страницу, где
свободно хотя бы N байт» отвечается за пару обращений, а не перебором.

## Как это выглядит

Расширение `pg_freespacemap` показывает карту в байтах свободного места
на страницу:

```sql
CREATE EXTENSION IF NOT EXISTS pg_freespacemap;
VACUUM bloat_demo;
SELECT blkno, avail FROM pg_freespace('bloat_demo') ORDER BY blkno LIMIT 5;
--  blkno | avail
-- -------+-------
--      0 |  8160
--      1 |  8160
```

`avail` - сколько байт свободно на странице по версии карты. У `bloat_demo`
половина версий мертва после массового UPDATE; вакуум убрал их с первых
страниц, и те освободились почти целиком (8160 - это пустая страница за
вычетом заголовка). Заметь: число округлено до кратного 32.

## Кто и когда обновляет карту

Главный поставщик данных для карты - `VACUUM`. Пройдясь по таблице и убрав
мёртвые версии, он записывает в `_fsm`, сколько места освободилось на
каждой странице. Обычная вставка тоже подправляет карту, когда занимает
место. Карта приблизительная: она может слегка отставать от реальности, и
это нормально - перед вставкой сервер всё равно перепроверяет саму
страницу.

Если карта говорит, что свободной страницы нет, таблица **расширяется** -
в конец дописывается новая пустая страница.

## Почему её иногда нет

Сразу после `CREATE TABLE` форка `_fsm` не существует - он появляется
позже, обычно при первом вакууме. У совсем маленьких таблиц (несколько
страниц) карты может не быть вообще: проверить три страницы напрямую
дешевле, чем заводить и поддерживать карту. Поэтому `pg_relation_size('t',
'fsm')` для свежей маленькой таблицы вернёт 0.


## Команды

```sql
CREATE EXTENSION IF NOT EXISTS pg_freespacemap;
```
Подключить функции чтения карты свободного места

```sql
SELECT blkno, avail FROM pg_freespace('bloat_demo') ORDER BY blkno;
```
Свободные байты на каждой странице по версии карты

```sql
SELECT pg_relation_size('bloat_demo', 'fsm');
```
Размер форка _fsm в байтах (0, если карты ещё нет)


## См. также

- [relfilenode и форки отношения](/courses/postgres/kb/relfilenode-forks.md)
- [Visibility Map (карта видимости)](/courses/postgres/kb/visibility-map.md)
- [Раскладка страницы 8 КБ](/courses/postgres/kb/page-layout.md)