Что физически лежит в индексе

В листьях B-tree лежат пары «ключ → ctid», где ctid хранит пару (номер страницы, номер слота внутри страницы), то есть физический адрес версии строки. Внутренние узлы содержат только разделители-ключи и ссылки на дочерние страницы. Вдобавок листья связаны в двусвязный список, поэтому индекс умеет отдавать данные уже отсортированными и обслуживать диапазонные условия BETWEEN, >, < одним проходом вправо по листьям.

Арифметика, которую хотят услышать

Страница 8 КБ, ключ bigint + ctid ≈ 16 байт с накладными расходами, и на страницу влезает порядка 400 записей. Три уровня дают 400³ ≈ 64 млн ключей, четыре - 25 млрд. Значит, чтобы найти конкретное значение в таблице на 100 млн строк, хватит 4 чтений страниц, причём верхние уровни почти всегда уже в shared_buffers, то есть реальных обращений к диску обычно 1–2. Против 20 ГБ последовательного чтения при Seq Scan.

Почему бинарное дерево проигрывает

• Ветвление 2 против ~400, отсюда высота 27 против 4.
• Узлы бинарного дерева разбросаны по произвольным местам, отсюда случайные чтения, самые дорогие для диска.
• B-tree сбалансировано по построению: все листья на одном уровне, худший случай равен среднему. У обычного BST при вставке возрастающих ключей (а это типичный id) дерево вырождается в список.

Что происходит при вставке

Значение попадает в нужный лист; если лист переполнен, случается split: страница делится пополам, разделитель поднимается в родителя, при переполнении родителя split идёт вверх, и в пределе растёт высота дерева. Отсюда и цена записи: вставка в индекс не сводится к «дописать в конец», это поиск + возможная перестройка страниц + запись в WAL.

Разбор по типам

• B-tree берёт всё, что имеет порядок: =, <, >, BETWEEN, IN, IS NULL, префиксный LIKE 'abc%', а также ORDER BY и MIN/MAX без сортировки. Уникальность и первичные ключи умеет только он.
• Hash понимает только =: ни сортировки, ни диапазонов, ни уникальности. С PG 10 он пишется в WAL (до этого не переживал крэш и не реплицировался), но выигрыш перед B-tree мал, и берут его редко - разве что для очень длинных строк, где хеш заметно компактнее.
• GIN нужен, когда в одном значении много элементов: массивы (@>, &&), jsonb (@>, ?), полнотекстовый поиск (tsvector @@ tsquery), подстроки через pg_trgm. Внутри B-tree по элементам, а в листьях сжатые списки ctid. Читается быстро, пишется медленно; это смягчают настройки fastupdate и gin_pending_list_limit.
• GiST - обобщённое дерево поиска для данных, где «ключом» служит область: геометрия PostGIS, диапазоны tsrange/int4range с оператором пересечения &&, ближайшие соседи (ORDER BY point <-> point), а также EXCLUDE-констрейнты (например, «брони не пересекаются»).
• SP-GiST делит пространство (quad-tree, k-d tree, radix): точки, IP-сети inet, префиксный поиск по строкам. Хорош там, где данные неравномерны.
• BRIN хранит min/max по диапазону страниц (по умолчанию 128), и индекс на терабайтную таблицу занимает мегабайты. Работает, только если физический порядок строк коррелирует со значением колонки. Классический случай: created_at в append-only логах и метриках.

Как выбирать на собеседовании

Вопрос закрывает такой ответ: «сначала спрашиваю, какой оператор в WHERE. Оператор определяет класс индекса: под равенство и диапазон B-tree, под «содержит» GIN, под «пересекается» / «ближайший» GiST, под «строки идут по возрастанию и таблица огромная» BRIN». Проверить, что оператор реально поддерживается, можно через pg_amop или просто по EXPLAIN.

Почему не B-tree

Запрос «найди всё в радиусе 2 км» или «какие полигоны пересекают этот прямоугольник» не сводится к сравнению по одной оси. Отсортировать точки по x не помогает: близкие по обеим координатам точки окажутся в разных концах индекса. Нужна структура, которая группирует объекты по пространственной близости.

Как работает GiST на геометрии

В узлах хранятся ограничивающие прямоугольники (MBR, bounding box) дочерних объектов. Поиск спускается только в те ветки, чей прямоугольник пересекается с искомой областью. Получается R-tree, реализованное поверх обобщённого GiST. Результат приблизительный по bbox, поэтому PostGIS делает двухфазный поиск: индекс отдаёт кандидатов по bbox, затем точный предикат (ST_Intersects, ST_DWithin) отсеивает лишнее.

CREATE EXTENSION postgis;
ALTER TABLE places ADD COLUMN geom geography(Point, 4326);
CREATE INDEX places_geom_idx ON places USING GIST (geom);

-- Всё в радиусе 2 км: ST_DWithin умеет пользоваться индексом
SELECT id, name FROM places
WHERE  ST_DWithin(geom, ST_MakePoint($1, $2)::geography, 2000);

-- Ближайшие 10 (KNN, оператор расстояния идёт прямо в индекс)
SELECT id FROM places ORDER BY geom <-> ST_MakePoint($1, $2)::geography LIMIT 10;

Варианты

• SP-GiST (quad-tree) на чистых точках бывает быстрее и компактнее GiST.
• BRIN подойдёт гигантским таблицам, если данные физически сгруппированы по географии (например, загружены по регионам).
• Геохеш / H3 в отдельной колонке + обычный B-tree обходятся без PostGIS: координату кодируют в строку/число так, чтобы у близких точек был общий префикс, и ищут по префиксу. Работает, но на границах ячеек теряет близкие точки, их добирают из соседних ячеек.

Почему это следует из устройства

Ключи в индексе отсортированы сначала по a, внутри одинаковых a - по b, внутри одинаковых b - по c. Как телефонный справочник по «фамилия, имя, отчество»: всех Ивановых найти легко, а всех Петровичей - только полным перебором.

Правило порядка колонок

1. Сначала колонки с равенством (=, IN): они сужают поиск до непрерывного участка индекса.
2. Затем колонка диапазона (>, BETWEEN). Полезной она бывает только одна и только последней среди «поисковых».
3. Затем колонки сортировки, в том же направлении, что в ORDER BY.
4. Селективность внутри группы равенств вторична: она влияет на размер индекса и на то, сколько других запросов он покроет, но не на то, применим ли он вообще.

Почему индексу всё-таки обычно нужна таблица

В индексной записи нет информации о видимости: там нет xmin/xmax. Индекс не знает, видит ли текущая транзакция конкретную версию строки, поэтому обычный Index Scan обязан сходить в heap и проверить заголовок кортежа. Обойти это помогает visibility map - битовая карта, где взведённый бит означает «все версии на этой странице видны всем транзакциям». Если бит взведён, идти в heap не нужно.

Условия index-only scan

• Все колонки из SELECT, WHERE, ORDER BY есть в индексе.
• Свежий VACUUM: visibility map актуальна.
• В плане это видно как Heap Fetches: 0. Большое число здесь означает, что формально index-only scan выбран, а фактически мы всё равно ходим в таблицу.

INCLUDE против добавления колонки в ключ

-- Вариант 1: колонка в ключе участвует в поиске и сортировке, но раздувает внутренние узлы
CREATE INDEX i1 ON orders (customer_id, total);
-- Вариант 2: с INCLUDE total лежит только в листьях
CREATE INDEX i2 ON orders (customer_id) INCLUDE (total);

-- Для уникальных индексов разница такая:
CREATE UNIQUE INDEX u ON users (email) INCLUDE (name);
-- уникальность по email, а name просто «едет» в листе.
-- Если бы написали (email, name), уникальной была бы пара, а это другая семантика.

INCLUDE (с PG 11) выгоден, когда колонка нужна только для чтения: она не увеличивает внутренние узлы дерева, значит высота и ветвление не страдают, а типы могут быть даже такими, для которых нет операторов сравнения B-tree.

Частичный индекс

-- Мягкое удаление: 99 % запросов ходят только за живыми записями
CREATE INDEX users_active_idx ON users (created_at) WHERE deleted_at IS NULL;

-- Очередь: строк в статусе pending всегда мало, а таблица огромная
CREATE INDEX jobs_pending_idx ON jobs (run_at) WHERE status = 'pending';

-- Уникальность только среди живых: UNIQUE-констрейнтом не выразить, частичным индексом - да
CREATE UNIQUE INDEX users_email_uniq ON users (email) WHERE deleted_at IS NULL;

Планировщик использует частичный индекс, только если может доказать, что предикат запроса влечёт предикат индекса. То есть WHERE status = 'pending' попадёт, а WHERE status = $1 с параметром, как правило, нет: на момент планирования значение неизвестно (спасает generic vs custom plan, но полагаться на это нельзя).

Функциональный индекс

CREATE INDEX users_lower_email_idx ON users (lower(email));
SELECT * FROM users WHERE lower(email) = lower($1);   -- попадёт

CREATE INDEX events_day_idx ON events ((created_at::date));
CREATE INDEX orders_meta_client_idx ON orders ((meta->>'client_id'));

Есть ограничение: выражение должно быть IMMUTABLE. Поэтому CREATE INDEX ... (created_at AT TIME ZONE 'UTC') пройдёт, а (now() - created_at) - нет: индекс, который меняется со временем, смысла не имеет.

Что происходит при создании констрейнта

ALTER TABLE users ADD CONSTRAINT users_email_key UNIQUE (email);
-- PostgreSQL молча создаёт индекс users_email_key и привязывает его к констрейнту.
-- DROP INDEX users_email_key;  -- ошибка: индекс принадлежит констрейнту

Приём для прода

-- Добавить уникальность на живую таблицу без длинной блокировки:
CREATE UNIQUE INDEX CONCURRENTLY users_email_uniq ON users (email);
ALTER TABLE users ADD CONSTRAINT users_email_key UNIQUE USING INDEX users_email_uniq;
-- Второй шаг берёт короткую блокировку и просто «усыновляет» готовый индекс.

Условие не подходит структуре

• Функция над колонкой: WHERE lower(email) = 'a@b.c', WHERE date(created_at) = '2024-01-01'. Индекс хранит значения колонки, а не результат функции. Лечится функциональным индексом или переписыванием условия в диапазон.
• Неявный каст: колонка varchar, а параметр приходит числом; или WHERE id::text = $1. Для индекса каст ничем не отличается от функции. Правильно приводить параметр к типу колонки, а не наоборот.
• LIKE '%abc%': B-tree ищет по префиксу, а его тут нет. Нужен pg_trgm + GIN. Даже LIKE 'abc%' в базе не с C-локалью не попадёт в индекс без text_pattern_ops.
• Не левый префикс составного индекса (см. вопрос про составные индексы).
• OR по разным колонкам: одним индексом его не покрыть; иногда выручает BitmapOr по двум индексам, иногда переписывание в UNION ALL.
• ORDER BY a ASC, b DESC при индексе (a, b): направления не совпали.

Индекс подходит, но он не выгоден

Если под условие попадает существенная доля таблицы (эмпирически больше 5–20 %), Index Scan проигрывает: он делает случайные чтения heap-страниц, а Seq Scan читает подряд, что на порядок дешевле, да ещё и пачками. Планировщик тут поступает правильно, и на собеседовании ждут ответа «здесь Seq Scan оптимален», а не «надо заставить индекс». Есть и промежуточный вариант, Bitmap Heap Scan: PostgreSQL собирает ctid в битовую карту, сортирует по номерам страниц и читает heap условно последовательно.

Планировщик ошибается

Оценки берутся из pg_statistic, который наполняет ANALYZE. После массовой загрузки, после создания индекса, после смены распределения данных статистика врёт, и в плане rows= и actual rows= расходятся на порядки. Лечение: ANALYZE table, поднять default_statistics_target (по умолчанию 100) для конкретной колонки, добавить CREATE STATISTICS для коррелированных колонок (город и страна, товар и категория).

Конкретная цена

• INSERT / DELETE трогают все индексы таблицы: поиск места + возможный split страницы + запись в WAL по каждому индексу.
• UPDATE, задевший индексируемую колонку (кроме колонок только под BRIN), ломает HOT: вместо «новая версия в той же странице и индексы не трогаем» получаем записи во все индексы. Один лишний индекс по «горячей» колонке может удвоить стоимость обновления.
• WAL растёт → растёт трафик репликации, дольше идёт восстановление, больше нагрузки на диск.
• Место: индексы часто занимают больше самой таблицы. И они конкурируют с данными за shared_buffers и страничный кэш ОС - то есть вытесняют оттуда полезное.
• VACUUM обходит каждый индекс, чтобы вычистить ссылки на мёртвые версии; чем больше индексов, тем дольше и тяжелее autovacuum.
• Планировщик перебирает больше вариантов, и время планирования растёт (заметно на OLTP с тысячами простых запросов в секунду).

Как это звучит на собесе

«Индексы разменивают скорость записи на скорость чтения. Под каждый индекс должен быть конкретный запрос из прода, а не гипотеза. На горячей пишущей таблице я сначала считаю, сколько мы теряем на записи, и только потом добавляю». И частая ошибка рядом: добавили индекс, но не удалили тот, что стал из-за него избыточным.

-- 1. Ни разу не использованные, отсортированные по занимаемому месту
SELECT s.relname            AS tbl,
       s.indexrelname       AS idx,
       pg_size_pretty(pg_relation_size(s.indexrelid)) AS sz,
       s.idx_scan
FROM   pg_stat_user_indexes s
JOIN   pg_index i ON i.indexrelid = s.indexrelid
WHERE  s.idx_scan = 0
  AND  NOT i.indisunique       -- уникальные держат бизнес-инвариант
  AND  NOT i.indisprimary
ORDER  BY pg_relation_size(s.indexrelid) DESC;

-- 2. Полные дубликаты: одинаковый набор колонок в одном порядке
SELECT indrelid::regclass AS tbl, array_agg(indexrelid::regclass) AS dupes
FROM   pg_index GROUP BY indrelid, indkey, indpred, indexprs HAVING count(*) > 1;

-- 3. Когда сбросили статистику: без этого idx_scan = 0 ничего не значит
SELECT stats_reset FROM pg_stat_database WHERE datname = current_database();

Что обязательно оговорить

• Статистика копится с момента последнего сброса и только на этом узле. На реплике запросы другие: индекс, «неиспользуемый» на мастере, может активно работать на реплике для отчётов. Проверять надо на всех узлах.
• Есть редкие, но критичные запросы: месячная выгрузка, ночной пересчёт, ручной поиск в поддержке. Наблюдать нужно хотя бы полный бизнес-цикл - месяц.
• Уникальные индексы и индексы под внешними ключами не удалять: они держат ограничения целостности, даже если idx_scan = 0. Кстати, колонка FK без индекса сама по себе беда: DELETE в родительской таблице будет делать Seq Scan по дочерней.
• Безопасного приёма вместо DROP в PostgreSQL штатно нет: сделать индекс невидимым для планировщика нельзя (в MySQL для этого есть ALTER TABLE ... ALTER INDEX ... INVISIBLE). Поэтому на практике индекс переименовывают и держат неделю, чтобы быстро вернуть, либо снимают DDL заранее.

Что происходит без CONCURRENTLY

Блокировка SHARE конфликтует с ROW EXCLUSIVE, который берут INSERT/UPDATE/DELETE. На таблице в 500 ГБ индекс строится десятки минут - и всё это время запись в таблицу стоит. Хуже того, ожидающие запросы выстраиваются в очередь за нашей блокировкой и блокируют даже чтения, которые сами по себе конфликта не имели бы.

Как работает CONCURRENTLY

1. Первый проход: строит индекс по снапшоту, параллельно записи продолжаются.
2. Ждёт завершения всех транзакций, начавшихся до первого прохода.
3. Второй проход: добирает строки, изменившиеся за время первого прохода.
4. Ждёт транзакции, которые могли не видеть индекс, и помечает его валидным.

Ограничения, о которых спрашивают

• Нельзя внутри транзакционного блока, так что миграция должна уметь выполнять такой шаг вне транзакции (в goose это -- +goose NO TRANSACTION; golang-migrate сам транзакцию не открывает, но несколько операторов из одного файла PostgreSQL выполнит одной неявной транзакцией, поэтому такой индекс кладут в отдельный файл, включают режим x-multi-statement, где операторы уходят по одному, или запускают руками).
• Идёт в 2–3 раза дольше и сильнее нагружает диск.
• При сбое остаётся невалидный индекс: планировщик его не берёт, но на каждой записи он обновляется, то есть только вредит. Искать так: SELECT indexrelid::regclass FROM pg_index WHERE NOT indisvalid;, лечить DROP INDEX CONCURRENTLY и повторной попыткой.
• Долгая транзакция блокирует завершение: если кто-то держит открытую транзакцию, CONCURRENTLY будет ждать её вечно. Перед запуском стоит проверить pg_stat_activity.
• Уникальный индекс при конфликте данных упадёт на втором проходе, когда всё время уже потрачено.