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

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

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

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

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

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

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

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.