Индекс (базы данных)

Индекс в базе данных — вспомогательная структура, которая позволяет находить нужные строки таблицы, не просматривая её целиком. Аналогия — предметный указатель в конце книги: чтобы найти упоминания термина, не нужно перелистывать все страницы. Индекс хранит значения выбранных столбцов в упорядоченном (или иначе организованном) виде вместе со ссылками на строки таблицы.

Индексы — главный инструмент ускорения запросов в реляционных базах. Хорошо подобранный индекс превращает запрос, читающий миллионы строк, в запрос, читающий несколько страниц. Но за это приходится платить местом и скоростью записи.

Зачем нужен

Без индекса единственный способ выполнить WHERE email = 'a@b.c' — последовательное сканирование (sequential scan, full table scan): прочитать все строки и проверить условие. Время растёт линейно с размером таблицы. Индекс на основе B-дерева находит значение за логарифмическое число шагов: для таблицы в сто миллионов строк это три–четыре уровня дерева.

Индекс помогает не только фильтрации:

• сортировке — ORDER BY по индексированному столбцу не требует отдельной сортировки;
• соединениям — поиск пары по внешнему ключу в другой таблице;
• уникальности — ограничения PRIMARY KEY и UNIQUE реализуются уникальными индексами;
• агрегатам — min/max по индексу читаются с краёв дерева.

Виды индексов

Список выше соответствует методам доступа PostgreSQL;^[2] в других СУБД набор отличается, но B-дерево (точнее, его вариант B+-дерево) есть везде. Саму структуру описали Рудольф Байер и Эдвард Маккрейт в 1970–1972 годах.^[5] Векторные индексы добавляет расширение pgvector.

Составные, частичные и покрывающие индексы

Составной индекс строится по нескольким столбцам, и порядок столбцов важен. Индекс по (customer_id, created_at) ускоряет запросы по customer_id и по паре customer_id + диапазон дат, но почти не помогает запросу только по created_at — так же, как телефонный справочник, отсортированный по фамилии и имени, бесполезен для поиска по одному имени.^[3]

Частичный индекс включает только строки, удовлетворяющие условию, — например, только неоплаченные заказы. Индекс по выражению строится по результату функции, например lower(email). Покрывающий индекс содержит все столбцы, нужные запросу, и тогда СУБД отвечает, не заходя в таблицу (index-only scan).^[4]

-- составной индекс под частый запрос «последние заказы покупателя»
CREATE INDEX orders_customer_created_idx ON orders (customer_id, created_at DESC);

-- частичный индекс
CREATE INDEX orders_unpaid_idx ON orders (created_at) WHERE paid = false;

-- индекс по выражению для поиска без учёта регистра
CREATE UNIQUE INDEX users_email_lower_idx ON users (lower(email));

-- в PostgreSQL: построить без блокировки записи в таблицу
CREATE INDEX CONCURRENTLY orders_total_idx ON orders (total);

Цена индексов

• Запись медленнее. Каждый INSERT, UPDATE или DELETE обязан обновить все индексы таблицы.
• Место. Индексы занимают диск и память; на нагруженных таблицах их суммарный объём нередко превышает объём данных.
• Не всегда используются. Если условие отбирает значительную часть таблицы, последовательное чтение быстрее тысяч случайных переходов по индексу, и оптимизатор это учитывает.

Почему индекс не используется

Типичные причины: функция над столбцом в условии (WHERE lower(email) = ... при индексе по email), неявное приведение типов, LIKE '%abc' с подстановочным знаком в начале, неверный порядок столбцов в составном индексе, устаревшая статистика. Проверять нужно не догадками, а планом выполнения через EXPLAIN: в нём видно, выбран ли Index Scan или Seq Scan. Подробный разбор типичных ошибок — в книге Маркуса Винанда «Use The Index, Luke».^[6]

Практические правила

1. Индексируйте столбцы из WHERE, JOIN и ORDER BY самых частых и самых медленных запросов, а не «все подряд».
2. Внешние ключи почти всегда стоит индексировать: иначе удаление родительской строки сканирует дочернюю таблицу.
3. Периодически ищите неиспользуемые индексы (в PostgreSQL — представление pg_stat_user_indexes) и удаляйте их.
4. На больших таблицах создавайте индексы без блокировки записи и оформляйте их миграциями.^[1]

См. также

• B-дерево
• EXPLAIN и план запроса
• PostgreSQL
• Векторный поиск
• Хеш-таблица

Источники

1. PostgreSQL Documentation — Indexes
2. PostgreSQL Documentation — Index Types
3. PostgreSQL Documentation — Multicolumn Indexes
4. PostgreSQL Documentation — Index-Only Scans and Covering Indexes
5. R. Bayer, E. McCreight — Organization and Maintenance of Large Ordered Indexes (1972)
6. Markus Winand — Use The Index, Luke