Сканирование таблицы целиком это способ найти запись, известный каждому, кто листал бумажный журнал: смотришь строку за строкой, пока не наткнёшься на нужную. Миллион строк означает миллион просмотров, и на диске это часы ожидания. Индекс превращает задачу в соблюдение порядка: данные организованы так, чтобы отсеивать половину оставшихся вариантов каждым шагом, и миллион строк сжимается до пары десятков сравнений. За этим трюком стоит конкретная математика и конкретная цена, и обе стороны вопроса есть смысл знать.
Логарифм как главный герой истории
Бинарный поиск на отсортированном массиве делит интервал пополам. Тысяча элементов разрешается за десять сравнений, миллион за двадцать, миллиард за тридцать. Зависимость логарифмическая, и именно поэтому рост данных почти не влияет на скорость поиска, пока структура поддерживает порядок. База данных переносит этот приём на диск: страница узла дерева вмещает десятки ключей, поэтому каждый уровень отсекает не половину, а девяносто с лишним процентов оставшегося пространства.
Ветвление в BTree доводит идею до предела. Страница узла с сотней ключей сокращает область поиска в сто раз за одно обращение к диску: три уровня дерева покрывают миллионы строк, четыре миллиарды. Главная стоимость поиска это не сравнения, а число чтений страниц с диска, и дерево минимизирует их до единиц независимо от размера таблицы.
Эта арифметика объясняет, почему добавление индекса даёт такой скачок. Запрос, перебирающий миллион строк, тратит на это сотни мегабайт чтения. Запрос по индексу читает три четыре страницы. Отношение времени исполнения измеряется порядками величины, и в повседневной практике запрос либо мгновенный, либо безнадёжный, середина случается редко.
Особое значение имеет селективность. Индекс по булеву признаку пола почти бесполезен, потому что половина таблицы всё равно выбирается. Индекс по уникальному коду почти идеален. Оценка селективности входит в инструментарий оптимизатора запросов, и понимание этого числа заменяет народные приметы про хорошие и плохие индексы.
Память участвует в этом выигрыше тоже. Верхние уровни индекса держатся в кэше базы, и на практике миллион строк разрешается чаще всего одним физическим чтением листовой страницы. Это и есть тот случай, когда рекламное обещание трёх операций оказывается сдержанным.
Устройство индексной страницы и ключа
Страница индекса это контейнер ключей с указателями. Ключ образуется из колонок индекса в объявленном порядке, и сравнение идёт по правилам сортировки этих типов. Составной индекс по фамилии и имени ищет точно по паре или по левому префиксу, но бессилен для имени без фамилии: это правило левого префикса есть прямое следствие физического порядка ключей, и нарушать его запросами безнадёжно.
Указатели в узлах ведут на дочерние страницы вниз по дереву, а листья связаны горизонтальной цепочкой для диапазонных проходов. В кластеризованных индексах листья содержат сами строки, в некластеризованных ссылки на них, и этот выбор определяет, нужна ли дополнительная прогулка за данными после нахождения ключа.
Полнота ключа влияет на высоту дерева. Длинные строковые ключи сокращают число ключей на страницу и прибавляют дереву уровней. Короткие суррогатные ключи делают дерево ниже и кэшируемее, и с этим связаны поколения споров о натуральных и искусственных ключах.
Заполненность страницы тоже предмет заботы. Дерево старается держать страницы полными на три четверти девяносто процентов, оставляя запас на вставки и сохраняя разумную плотность чтения. Массовые удаления портят плотность со временем, и регулярная реорганизация индекса возвращает структуру в форму, как плановая стрижка возвращает форму живой изгороди.
Отдельных абзацев достойны покрывающие индексы, в которых листья хранят все колонки запроса, устраняя вторичное чтение строки. Запрос, который целиком обслуживается индексом, в документации зовётся index only scan, и умение довести горячие запросы до такой формы это признак мастерства администратора.
Баланс между чтением и ценой поддержания индекса
Каждый индекс бесплатен при чтении и платён при записи. Вставка строки обязана обновить все индексы таблицы: найти позицию ключа, вписать запись, возможно расщепить страницу. Десять индексов это десятикратная цена каждой вставки, и об этом узнают на первом же потоке загрузки большой таблицы.
Обновление тоже небесплатно. Меняется значение в индексированной колонке значит ищется и переставляется запись индекса, а когда колонка в кластерном ключе, двигается сама строка. Таблицы с часто меняющимися индексированными полями страдают от хронической фрагментации и усиления записи.
Массовая загрузка обходится трюком: индексы выключают или строят после загрузки, когда данные уже лежат на диске. Построение индекса сортировкой всего набора обходится в разы дешевле, чем инкрементальная вставка миллионов ключей, и все серьёзные движки имеют специальный быстрый путь bulk load, работающий именно так.
Разумный индексный инвентарь поддерживается наблюдением. Статистика использования индексов показывает, какие из них читаются, а какие только обновляются. Индекс, который никто не читает, это чистый налог на запись, и его удаление это самый дешёвый способ ускорить интенсивно пишущую таблицу.
Дисциплина ревизии индексов выглядит так:
- Собрать статистику чтения и обслуживания каждого индекса за представительный период;
- Устранить дубликаты и содержащиеся друг в друге по префиксу индексы;
- Для каждого оставшегося индекса назвать запросы, которые он обслуживает, и порог, за которым его нельзя потерять;
- Повторять ревизию по расписанию, потому что потребности приложения меняются каждый сезон разработки.
Чтение планов запроса и маркеры эффективности
План запроса это протокол решений, которые принял оптимизатор, и читать его обязателен тот, кто хочет понимать индексы. Узлы Seq Scan сообщают о полном сканировании, Index Scan о поиске по индексу, Index Only Scan о работе без обращения к данным. Стоимостные оценки рядом с узлами показывают, во что оптимизатор оценил альтернативы и почему выбрал именно этот путь.
Верхние строки плана говорят про агрегации и соединения, но знающий глаз идёт снизу вверх и ищет таблицы с широкими сканами. Одна случайная таблица без подходящего индекса в соединении одного к одному это классический разрушитель производительности, и оптимизатор часто оказывается невиновен: он выбирал из того, что есть.
Хинты и принудительные планы иногда оправданы на короткий срок, но злоупотреблять ими дорого: данные меняются, статистика обновляется, и вчерашний принуждённый план завтра станет тупиком. Свежая статистика по таблицам это дешёвое здоровье планировщика, и её обновление входит в обычное регламентное обслуживание.
Практический инструментарий включает замеры реального времени узлов через анализирующие варианты вывода планов. Оценки это гипотезы, время это факт, и расхождение на два порядка в точности этих чисел указывает на устаревшую статистику или неожиданную корреляцию колонок.
Обучение на реальных запросах продакшн качества это лучший способ, потому что учебники показывают только стерильные ситуации без смешения паттернов чтения, конкурентных обновлений и фонового давления.
Индексы особых типов и за пределами дерева
BTree это основа, но не монополия. Хэш индексы дают точечное равенство за одно обращение и ничего не умеют про диапазоны. Индексы по тексту, вроде расширенных триграммных или полнотекстовых обратных списков, решают подстроки и поиск по словам, что дереву не по зубам. Пространственные индексы служат географии, битовые карты фактам с малым числом значений. Современный движок предоставляет зоопарк, и корректное использование правильного вида индекса это вторая грамотность после понимания дерева.
Частичные индексы, отфильтрованные предикатом, строятся на подмножестве строк и уменьшают размер при сохранении выигрыша. Функциональные индексы строятся над выражением и позволяют искать по левой части причёсанного текста без трюков в запросе. Каждый тип это ответ на структурное ограничение основного вида.
Индексирование JSON полей и массивов идёт через обобщённые индексы свёртки, о которых стоит хотя бы знать, прежде чем городить обходы. Невежество здесь приводит к печалям массового сканирования полуструктурированных данных.
Правило применения простое: сначала смотри на паттерн запроса и селективность, затем выбирай тип индекса под него, затем пиши структуру, и только потом измеряй. Обратная последовательность ведёт к коллекции ненужных структур, висящих на таблице утяжеляющим грузом.
Частые искажения при работе с индексами
Первая классическая ошибка это вера в то, что индекс всегда ускоряет. При выборке двадцати процентов таблицы оптимизатор честно предпочтёт последовательное чтение данных, потому что сканирование подряд дешевле десятков тысяч прыжков по случайным страницам, и настаивание на индексе через принуждение делает запрос быстрее лишь в редких конфигурациях.
Вторая ошибка это индексирование всего подряд на старте проекта в надежде на светлое будущее. Лишние структуры не только обременяют запись, они ещё и усложняют выбор планировщика, потому что у него появляются почти одинаковые кандидаты и каждый месяц статистика спотыкается о новую комбинацию. Правильная стратегия это добавление индекса строго по поводу, с конкретным запросом в руках и измерением до и после.
Третья ошибка это забвение сортировок: запросы с ORDER BY по многим полям неожиданно проигрывают, если индекс не соответствует направлению и порядку сортировки. Здесь помогает внимательное чтение документации движка, потому что часть систем умеет обходить дерево в обратном порядке, а часть нет, и тонкий текст запроса вдруг определяет, нужна ли сортировка на диске.
Четвёртая веха это скрытые преобразования типов в предикатах. Сравнение колонки с литералом другого типа заставляет движок приводить значения к общему знаменателю, и индекс от пересчёта каждой строки отказывается работать. Симптом коварный: запрос с виду написан под индекс, план показывает сканирование, и лечится приведением типов в явном виде.
Измерение и культура индексной дисциплины
Индексы это вложения с процентами и налогами одновременно. Метрика их здоровья должна быть комплексной: время горячих запросов, темп записи в таблицы, занимаемый объём, доля использований по статистике. Регулярная проверка этих четырёх рядов предотвращает и болезни избытка, и болезни нехватки.
Платёж надо видеть в рупоре нагрузки. Пишущие сервисы с жёсткими дедлайнами не терпят заводных индексов, и перенос вторичных отчётных нужд на реплики со своим набором индексов это нормальная практика, а не эстетство.
Финальное замечание: бинарный поиск и его потомок в виде дерева не перестали работать за полвека существования технологии. Логарифм миллиарда всё так же равен тридцати, и человек, научившийся видеть эту цифру за строкой запроса, уже не станет жертвой байесовского мрака сканирования диска по кругу.
Полезно держать в голове и экономическое измерение вопроса. Индекс занимает место на диске, входит в бэкапы, реплицируется на стендбаи и участвует в каждой реорганизации. Коллекция из десятка структур на таблице в сотни гигабайт это серьёзная статья расходов инфраструктуры, и её регулярный аудит в терминах денег, а не только миллисекунд, делает индексную политику разговором инженеров и менеджмента на одном языке.
Индексы не прощают ни пренебрежения, ни слепого обожания, и уравновешенный взгляд на них это грамотность номер один в ремесле работы с данными.
Рядом с этой дисциплиной живёт и скромность: индекс добавляется ответственно, после чтения плана, а не от испуга.