BRIN — индекс диапазонов блоков

Предпосылки: страницы и кортежи, B-tree.

Таблица логов, миллиард строк:

CREATE TABLE logs (
    id BIGSERIAL,
    created_at TIMESTAMP NOT NULL,
    message TEXT
);

Логи добавляются только в конец таблицы (append-only). Новые записи получают более поздний created_at, и физический порядок строк на диске совпадает с порядком по времени:

Блок 0:    строки с created_at 2024-01-01 00:00 ... 00:05
Блок 1:    строки с created_at 2024-01-01 00:05 ... 00:10
Блок 2:    строки с created_at 2024-01-01 00:10 ... 00:15
...
Блок 1000: строки с created_at 2024-01-01 03:20 ... 03:25

B-tree по created_at индексирует каждую строку: миллиард записей в дереве, 20-30 ГБ на диске. Но данные уже упорядочены физически — зачем хранить точный адрес каждой строки, если достаточно знать: «блоки 200-210 содержат данные за 01:00-01:05»?

BRIN (Block Range Index) — индекс диапазонов блоков — делает именно это. Вместо записи на каждую строку он хранит сводку (min/max) для группы последовательных блоков — одна запись индекса описывает сотни или тысячи строк. Появился в PostgreSQL 9.5 (2016).

Структура

BRIN делит таблицу на диапазоны — группы последовательных блоков фиксированного размера. Для каждого диапазона индекс хранит минимальное и максимальное значение индексируемой колонки:

Таблица (heap):

    Блоки 0-127:     содержат значения от 00:00 до 00:42
    Блоки 128-255:   содержат значения от 00:42 до 01:24
    Блоки 256-383:   содержат значения от 01:24 до 02:06
    ...

BRIN индекс:

    Range 0 (блоки 0-127):     min=00:00, max=00:42
    Range 1 (блоки 128-255):   min=00:42, max=01:24
    Range 2 (блоки 256-383):   min=01:24, max=02:06
    ...

Размер диапазона задаёт параметр pages_per_range — по умолчанию 128 блоков, то есть 1 МБ данных на один элемент индекса:

CREATE INDEX idx_logs_brin ON logs USING brin(created_at);
 
-- Уменьшить диапазон для более точного отсечения:
CREATE INDEX idx_logs_brin ON logs USING brin(created_at)
WITH (pages_per_range = 32);

Поиск

Запрос WHERE created_at BETWEEN '01:00' AND '01:30' проходит два этапа. Сначала PostgreSQL сканирует BRIN индекс — он занимает несколько страниц — и для каждого диапазона проверяет, пересекается ли его [min, max] с условием запроса:

Range 0: [00:00, 00:42] — не пересекается, пропускаем блоки 0-127
Range 1: [00:42, 01:24] — пересекается, читаем блоки 128-255
Range 2: [01:24, 02:06] — пересекается, читаем блоки 256-383
Range 3: [02:06, 02:48] — не пересекается, пропускаем
...

Затем внутри отобранных блоков — sequential scan с проверкой условия для каждой строки. BRIN не даёт точных TID’ов, как B-tree, — он даёт диапазоны блоков, которые могут содержать нужные данные.

Зато размер индекса принципиально другой. Для таблицы в миллиард строк с колонкой TIMESTAMP (8 байт):

B-tree:  каждая строка — запись в индексе    → ~20-30 ГБ
BRIN:    1 млрд строк ≈ 7.5 млн блоков,
         7.5M / 128 ≈ 59,000 range entries   → ~2 МБ

Разница в 10 000 раз. Весь BRIN индекс помещается в оперативную память, не вытесняя из буферного кеша данные таблицы.

Корреляция

Всё описанное выше работает, потому что физический порядок строк в таблице логов совпадает с порядком значений created_at. Но что произойдёт, если проиндексировать колонку, значения которой не связаны с порядком вставки — например, возраст пользователей?

Range 0: min_age=18, max_age=85
Range 1: min_age=19, max_age=82
Range 2: min_age=17, max_age=88

Каждый диапазон охватывает почти весь спектр возрастов. Запрос WHERE age = 25 пройдёт проверку пересечения для всех диапазонов — BRIN не отсечёт ничего, и результат будет не лучше Seq Scan.

Степень соответствия между физическим порядком строк на диске и логическим порядком значений в колонке называется корреляцией. При корреляции близкой к 1.0 или -1.0 значения упорядочены (по возрастанию или убыванию) и BRIN эффективен. При корреляции близкой к 0 значения разбросаны случайно и BRIN бесполезен.

PostgreSQL хранит эту статистику в pg_stats:

SELECT tablename, attname, correlation
FROM pg_stats
WHERE tablename = 'logs';

Высокая корреляция возникает естественно в нескольких случаях. Автоинкрементные id (SERIAL, BIGSERIAL) — новые строки всегда получают большие значения. Временные метки в append-only таблицах (created_at, logged_at) — время движется вперёд, строки ложатся в конец heap. Данные, загруженные из отсортированного источника — COPY из CSV, отсортированного по нужной колонке.

BRIN работает для append-only таблиц: логи, события, метрики, временные ряды — всё, где новые записи добавляются в конец и значение индексируемой колонки монотонно растёт. Таблицы с активными UPDATE, колонки без корреляции с физическим порядком и запросы, требующие точного попадания в единичные строки — не его территория.

DELETE, UPDATE и потеря точности

В production таблица логов живёт не в вакууме. При DELETE строка помечается как dead, но BRIN не обновляется — если удалили строку с максимальным значением, индекс хранит старый max, и диапазон становится шире реальности.

При UPDATE новая версия строки может попасть в другой блок — через FSM PostgreSQL находит свободное место, и оно может оказаться в блоке с данными за другой период (см. VACUUM). Если блок с записями за 00:25-00:30 получит новую версию строки с created_at = 01:02, его диапазон расширится с [00:25, 00:30] до [00:25, 01:02]. Со временем такие расширения накапливаются, и BRIN отсекает всё меньше блоков.

REINDEX пересчитывает min/max по актуальным данным — сужает раздувшиеся диапазоны. Но если данные физически разбросаны (корреляция нарушена), диапазоны всё равно будут широкими. CLUSTER решает корневую проблему — физически переупорядочивает строки по индексу, восстанавливая корреляцию.

Autosummarize

По умолчанию BRIN не создаёт записи для новых блоков автоматически — пока блок не просуммирован, он не участвует в отсечении. Параметр autosummarize меняет это поведение: PostgreSQL периодически сканирует новые блоки и добавляет min/max в индекс:

CREATE INDEX idx_logs_brin ON logs USING brin(created_at)
WITH (pages_per_range = 32, autosummarize = on);

Точность vs размер

pages_per_range — компромисс между размером индекса и точностью отсечения. При значении по умолчанию (128 блоков = 1 МБ данных) индекс минимален, но отсекает крупными кусками — если нужные данные занимают пару блоков, BRIN всё равно отправит на чтение весь диапазон из 128. Уменьшение до 16 блоков (128 КБ) увеличивает индекс в 8 раз, но точность отсечения возрастает пропорционально. Даже при pages_per_range = 1 (одна запись на каждый блок) индекс остаётся на порядки меньше B-tree, потому что хранит только min/max, а не адрес каждой строки.

Корреляция данных и то, как планировщик выбирает между стратегиями сканирования на основе статистики — в планировщике запросов.

Sources

PostgreSQL Documentation (пример: v16): BRIN. https://www.postgresql.org/docs/16/brin.html
PostgreSQL Release Notes: v9.5 (введение BRIN). https://www.postgresql.org/docs/9.5/release-9-5.html

← Hash Index | SP-GiST →

CS Notes

Explorer

brin