Что вы не знали об индексах

Практическое руководство по индексам баз данных на примере таблицы с покемонами. Рассматриваются компромиссы, которые обычно опускают в руководствах, и три типа индексов под конкретные задачи.

Базовый компромисс

Чтение ускоряется, запись замедляется.

Каждый INSERT, UPDATE или DELETE вынужден обновлять все индексы таблицы. Таблица с восемью индексами требует поддерживать девять структур данных. Кроме того, чем больше индексов, тем больше вариантов перебирает планировщик запросов - на быстрых точечных выборках время планирования может превысить время выполнения.

Почему индекс не работает

В составных индексах важен порядок колонок

Индекс по (type_1, type_2) создаёт структуру, отсортированную сначала по type_1, а затем внутри каждой группы - по type_2:

Bug      → Flying   → [Butterfree, ...]
         → Poison   → [Venonat, ...]
Electric → Flying   → [Zapdos, ...]
Fire     → Flying   → [Charizard, ...]
Water    → Flying   → [Wingull, ...]

Это помогает в запросах только по type_1 или по type_1 AND type_2 вместе. Но для запроса только по type_2 индекс бесполезен: записи с Flying разбросаны по группам Bug, Electric, Fire, Water, и перейти в одну конкретную точку дерева нельзя.

Если запросы только по type_2 выполняются так же часто, как и по type_1, создайте второй индекс.

Функции ломают использование индекса

SELECT * FROM pokemon WHERE lower(name) = 'pikachu';

Индекс построен по name, а не по lower(name). Для базы данных это разные вещи. Она переключается на полное сканирование таблицы (full table scan), попутно приводя каждое имя к нижнему регистру.

Это касается любых функций, оборачивающих колонку. Неявные приведения типов работают так же: сравнение текста с числом запускает неявное преобразование с тем же результатом.

Не гадайте, измеряйте

EXPLAIN SELECT * FROM pokemon WHERE name = 'Pikachu';

Index Scan означает, что используется индекс. Seq Scan - читается каждая строка. Используйте EXPLAIN ANALYZE, чтобы выполнить запрос и получить реальное время работы, а не только оценки планировщика.

Менее известные типы индексов

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

Индексируют результат выражения вместо самой колонки:

CREATE INDEX ON pokemon (lower(name));

Теперь условие WHERE lower(name) = 'pikachu' задействует индекс. Подходит для любой детерминированной, неизменяемой (immutable) функции.

Оговорка: если вам постоянно приходится индексировать lower(name), стоит задуматься, почему имена сразу не хранятся в нижнем регистре.

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

Индексируют только строки, подходящие под условие:

CREATE INDEX ON pokemon (name) WHERE is_legendary = true;

80 записей вместо 1000. Меньше размер, быстрее поиск, дешевле поддержка. Запросы, не попадающие под условие (WHERE is_legendary = false), переходят на сканирование таблицы, и это нормально - они всё равно выбирают большую часть строк.

Хорошо подходит для паттерна с мягким удалением (soft delete):

CREATE INDEX ON users (email) WHERE deleted_at IS NULL;

Покрывающие индексы

Когда индекс содержит все необходимые запросу колонки, база данных может вернуть ответ прямо из индекса, вообще не обращаясь к таблице. В EXPLAIN это отображается как Index Only Scan.

Используйте INCLUDE, чтобы добавить колонки без их сортировки:

CREATE INDEX ON pokemon (name) INCLUDE (base_attack);

Теперь такой запрос вообще не трогает таблицу:

SELECT name, base_attack FROM pokemon WHERE name = 'Pikachu';

Почему бы просто не включить base_attack в список индексируемых колонок? Потому что базе пришлось бы сортировать по ней при каждой записи - лишняя работа без всякой пользы, если поиск идёт только по имени.

Что почитать

Use The Index, Luke - подробное руководство по индексации в SQL.

database-design-and-implementation - книга Эдварда Скьоре строит описанные здесь механизмы изнутри: B-дерево, буферный пул, менеджер блокировок, планировщик, глава за главой. Лучший способ перестать воспринимать вывод EXPLAIN как магию - самому написать создающий его планировщик.

readings-in-database-systems - Red Book, бесплатно онлайн. Читать, когда практические вопросы исчерпаны и хочется увидеть всю область целиком: сборник статей о хранении, оптимизации запросов и транзакциях с комментариями и спорами редакторов.

См. также inverted-index для полнотекстового поиска и lsm-tree для хранилищ, оптимизированных под запись, где поддержка индексов обходится особенно дорого.