B-tree масштабируется логарифмически от числа строк, но линейно по размеру. На таблице в 500 миллионов строк B-tree-индекс по timestamp будет ~10 GiB. И каждый INSERT нужно протащить через log2(500_000_000) ≈ 29 уровней, на самом деле упираясь в WAL и в обновление leaf-страниц.

При этом если данные физически отсортированы (timestamp растёт, ID-серия растёт, audit-логи) — большая часть мощи B-tree не нужна. Нам не нужен точный адрес каждой строки. Нам достаточно знать: «на странице 17392 лежат события от 2024-06-15 10:00 до 10:05» — и при запросе «дай события за 11:00» страницу 17392 не читать вовсе.

Это и есть идея

Структура: min/max на range of pages

BRIN режет таблицу на диапазоны по N страниц подряд (по умолчанию pages_per_range = 128, это 1 MiB) и для каждого диапазона хранит summary — min и max значений индексируемой колонки.

Размер BRIN-индекса смешной: для 1 GiB таблицы при pages_per_range = 128 получаем 1024 summary-записи × ~32 байта ≈ 32 KiB. Даже на 500 GiB таблице BRIN весит мегабайты, а не гигабайты.

Демонстрация на events

Датасет medium+timeseries содержит таблицу events на 100K строк, упорядоченных по occurred_at. Маленькая по меркам BRIN, но идею показывает.

Видно: B-tree на 100K строк — несколько MiB, BRIN — пара KiB. На реальной таблице в сотни миллионов строк разница достигает 10000:1.

Обрати внимание: BRIN — это всегда Bitmap Index Scan + Recheck. Индекс возвращает не точный список tid, а список страниц-кандидатов. Дальше Postgres читает каждую страницу и фильтрует строки по точному условию. То есть на 1 совпавшую строку в range он может прочитать 128 страниц.

pages_per_range: главный tuning-параметр

Дефолт pages_per_range = 128 (1 MiB) — компромисс. Чем меньше — тем точнее min/max, меньше recheck, но больше индекс. Чем больше — наоборот.

Правило: чем больше таблица — тем больший pages_per_range можно себе позволить. Для time-series в 100 GiB значение 256 или даже 512 даёт индекс в считанные мегабайты, чего более чем достаточно.

Что внутри BRIN: revmap и tuples

Структурно BRIN состоит из двух уровней:

1. Meta + revmap (range-map). Это массив указателей: индекс i содержит указатель на BRIN tuple, описывающий range страниц [i*pages_per_range, (i+1)*pages_per_range). Размер revmap — фиксированный, очень маленький.
2. BRIN tuples — собственно записи summary (min/max или bloom). Хранятся в отдельных страницах индексного файла.

Когда вставляется новая строка с большим max, чем уже зафиксирован — нужно обновить tuple. Это single-page update, без перестройки дерева — это и есть причина, по которой BRIN дёшев на write.

Когда BRIN — спасение, а когда — провал

BRIN работает, когда есть корреляция между физическим порядком строк и значением индексируемой колонки. Эта корреляция оценивается в pg_stats как correlation: 1.0 — идеальный порядок, 0.0 — случайный, -1.0 — обратный.

Хорошие кандидаты:

• Time-series: события, логи, метрики — пишутся монотонно по времени.
• Sequential IDs: serial / bigserial — порядок insert совпадает с порядком id.
• Append-only: audit-таблицы, where строки только добавляются и не двигаются.

Плохие кандидаты:

• UPDATE-heavy с MVCC, где строки разлетаются по разным страницам (HOT-чейны эту проблему частично решают).
• Случайные значения (uuid, hash) — корреляция близка к 0, каждый range покрывает весь диапазон, BRIN бесполезен.
• После CLUSTER на другую колонку — порядок ломается.

Если корреляция упала до 0.3, BRIN не возвращает выгоды: Bitmap recheck читает почти все страницы.

bloom-opclass: BRIN для equality

В Postgres 14+ есть BRIN-opclass bloom (не путать с pg_bloom расширением). Вместо min/max он хранит bloom filter по значениям range’а — это позволяет отвечать на WHERE col = X через BRIN. Полезно, когда корреляция плохая, но мощность колонки маленькая (например, country_code — 200 значений на 500M строк): сам диапазон может пересекать всю таблицу по min/max, но bloom скажет «в этом range точно нет ‘JP’» и пропустит его.

Multi-range opclass

С Postgres 14 BRIN также получил multi-range opclass. Вместо одного [min, max] он хранит несколько узких диапазонов на range. Зачем? Представь, что данные почти отсортированы, но иногда «прилетают» сильно более старые события (late-arriving data). При обычном min/max один такой outlier расширяет min до старой даты, и range покрывает огромный интервал — теряется выгода. С multi-range outlier хранится как отдельный мини-диапазон, и большая часть данных в range остаётся узко покрытой.

CREATE INDEX events_at_brin_mr ON events
  USING BRIN (occurred_at timestamptz_minmax_multi_ops);

Размер индекса немного больше, чем у простого minmax, но устойчивость к outliers радикально выше — особенно полезно для логов и event-streams с допуском по времени.

Размер и I/O экономия в цифрах

Сопоставь Heap Blocks: lossy=N с общим числом страниц таблицы (pg_relation_size('events')/8192). Это и есть процент heap, который BRIN сэкономил. На хорошо коррелированных данных это часто 95-99%.

Мониторинг и обслуживание

• pg_stats.correlation для индексируемой колонки — следи, чтобы не падала ниже 0.7.
• pg_stat_user_indexes.idx_scan — если BRIN перестал использоваться оптимизатором, это сигнал, что статистика устарела или корреляция упала.
• VACUUM table обновляет BRIN summary для страниц, добавленных после последнего summarize. Иногда полезно вызвать brin_summarize_new_values('events_at_brin') руками, чтобы догнать.

SELECT brin_summarize_new_values('events_at_brin');

Это особенно важно после массовой вставки и сразу перед запросом — иначе новые страницы ещё не в индексе, и Bitmap Scan будет читать их все целиком.

BRIN + партицирование = золотая комбинация

В реальной timeseries-системе с миллиардами строк часто используют declarative partitioning по неделе/месяцу + BRIN на каждой партиции. Логика:

• Партицирование ограничивает запрос одной (или несколькими) партициями — partition pruning.
• BRIN внутри партиции дополнительно сужает чтение до конкретных страниц.
• DROP старых партиций для архивации — атомарный, без VACUUM.

Это даёт O(1) запрос на «события за последние 5 минут» в таблице на 10 ТБ — без B-tree-индекса, который бы съел сотни гигабайт.

Дополнительный плюс: при rolling-window архивации (новая партиция каждую неделю, старые партиции архивируются через pg_dump --table или TimescaleDB compression), BRIN строится по новой партиции мгновенно (мегабайты при сотнях GB heap), и его не приходится REINDEX.

Если используешь TimescaleDB, обрати внимание: hypertables встроенно используют BRIN-подобные стратегии при chunk-exclusion, а на отдельных колонках уже сверху можно класть свой BRIN. Это часто дёшево и эффективно.

Чек-лист

• BRIN = block range index: min/max (или bloom) на каждый диапазон страниц.
• Размер на порядки меньше B-tree: KiB вместо GiB на больших таблицах.
• Всегда даёт Bitmap Index Scan + Recheck — точность ограничена гранулярностью range.
• Ключевое условие: корреляция физического порядка и значения колонки должна быть высокой (≥ 0.7).
• Параметр pages_per_range — главный tuning: меньше = точнее, но больше; обычно 32-256.
• Use cases: time-series, audit-логи, serial/bigserial ID, append-only таблицы.
• Не использовать для UUID, hash, случайных значений или UPDATE-heavy таблиц с разлетающимися строками.
• Расширения и комбинации: BRIN отлично работает поверх declarative partitioning и в TimescaleDB hypertables.
• Постоянно следи за pg_stats.correlation — если падает, BRIN деградирует молча.

• BRIN на 100 GiB таблице — обычно индекс размером 1-10 MiB; экономия по сравнению с B-tree часто 1000x.