B-tree индексы, Seq Scan и covering

Индекс — отдельная структура рядом с таблицей. Он помогает найти нужные строки быстрее, чем читать всё подряд. Цель не «чтобы в плане был Index Scan», а чтобы запрос стоил дешевле.

Seq Scan — прочитать таблицу с начала до конца. Как листать книгу без оглавления. На маленькой книге это нормально. На толстой — уже нет.

B-tree — индекс по умолчанию в PostgreSQL. Точнее, это B+tree: сами ключи лежат в листьях, внутренние узлы только направляют поиск. Лист — страница около 8 КБ. На большой таблице высота дерева обычно 3–4 уровня. Поиск по ключу — несколько чтений страниц, а не проход по всей куче.

Пример. Таблица users на 80 строк. WHERE id = 7. Планировщик почти наверняка выберет Seq Scan: прочитать 80 строк подряд дешевле, чем спускаться по дереву и прыгать в таблицу.

B-tree хорошо закрывает равенство, диапазон, ORDER BY по префиксу ключа и IS NULL. Hash-индекс умеет только равенство и на практике нужен редко. GiST, GIN, BRIN — другие семейства: геометрия, полнотекст, JSONB, широкие append-only таблицы. С B-tree начинают.

Как устроен B-tree

Корень и внутренние страницы говорят, куда идти. В листьях лежат ключи и указатели на строки в куче. Указатель называется ctid: номер страницы и слот. Листья связаны между собой. Поэтому диапазон created_at > $1 после первой позиции читается почти подряд по индексу.

Дальше часто нужен прыжок в кучу за остальными колонками. Эти прыжки — случайный I/O. Если условие слабое и строк много, Index Scan читает почти всю таблицу, но ещё и вразброс. Тогда Seq Scan выигрывает: один последовательный проход.

Пример. Индекс по status, а status = 'active' у 80% строк. Индекс найдёт почти все строки и будет прыгать в кучу. Дешевле прочитать таблицу с начала до конца.

Когда планировщик выбирает Seq Scan

Планировщик считает стоимость. Если Seq Scan дешевле — он его возьмёт. Это не баг и не доказательство, что «индекса нет».

• Таблица крошечная: один проход страниц дешевле, чем спуск по дереву плюс обращения в кучу.
• Предикат слабо селективен: условие отсекает мало строк. Селективность — доля строк, которая подходит под условие. Мало строк — индекс любит. Много — Seq Scan.
• Нет подходящего индекса: функция на колонке, неявный cast типов, LIKE '%foo' с ведущим вайлдкардом.
• Статистика врёт: ANALYZE давно не бегал. Планировщик думает, что вернётся 10 строк, а вернётся миллион.

Оценка селективности живёт в pg_stats: MCV (самые частые значения), гистограммы, n_distinct. Без свежего ANALYZE лучший индекс могут не взять.

Covering и Index Only Scan

Covering-индекс покрывает запрос: все нужные колонки уже есть в индексе. Тогда возможен Index Only Scan — ответ из индекса, без похода в кучу за каждой строкой. Колонки могут быть ключом или лежать в INCLUDE.

Ещё нужна visibility map (карта видимости). Если страница кучи помечена all-visible, Postgres знает: все версии на странице видны всем и в кучу ходить не надо. После свежих UPDATE карта ещё не прогрета. Узел в плане всё равно называется Index Only Scan, но появляются Heap Fetches — прыжки в кучу. Выигрыш тает.

Пример. Запрос SELECT status, total FROM orders WHERE user_id = 42. Индекс (user_id) INCLUDE (status, total) покрывает и фильтр, и колонки SELECT. Обычный индекс только по user_id всё равно потащит status и total из кучи.

INCLUDE кладёт колонки в лист, но не в порядок ключа. Индекс остаётся узким для поиска и при этом покрывает SELECT. Цена как у любого индекса: шире лист — больше места, медленнее INSERT и UPDATE этих колонок.

CREATE INDEX idx_orders_user_created ON orders (user_id, created_at);
CREATE INDEX idx_orders_user_cov ON orders (user_id) INCLUDE (status, total);

-- WHERE lower(email) = 'a@b.c' — обычный btree по email не возьмётся
CREATE INDEX idx_users_email_lower ON users (lower(email));

EXPLAIN (ANALYZE, BUFFERS)
SELECT status, total
FROM orders
WHERE user_id = 42;

Первый индекс закрывает фильтр по пользователю и сортировку по времени. Второй позволяет не таскать status и total из кучи. Третий нужен потому, что выражение в WHERE и выражение в индексе должны совпасть. B-tree по email не знает про lower(email).

Цена индекса на запись

Каждый лишний индекс ускоряет часть SELECT и замедляет INSERT, UPDATE, DELETE и VACUUM: нужно поддерживать дополнительные листья. Случайный UUID как первичный ключ размазывает вставки по всему дереву — page splits и bloat (раздувание файла дырами). Монотонный ключ (bigserial, ULID с временем) пишет в «правый» лист и ведёт себя предсказуемее. Горячая правая страница — отдельный спор про конкуренцию.