В поиске по индексируемому текстовому полю условие с известным началом быстро, а поиск по произвольному фрагменту заметно медленнее. Объясните причину.
Обычный B-деревянный индекс эффективно использует упорядоченность ключей для поиска по точному значению или известному начальному префиксу. Условие по произвольному фрагменту, например с шаблоном, начинающимся с любого символа, не задаёт начальную границу диапазона, поэтому оптимизатор обычно не может выполнить эффективный индексный поиск и вынужден проверять много значений.
Индексы появились как способ не просматривать всю таблицу при поиске по упорядочиваемым значениям. B-дерево хранит ключи в отсортированном виде и позволяет быстро найти начало нужного диапазона, после чего последовательно обработать подходящие ключи.
Эта модель хорошо подходит для равенства, диапазона и поиска по префиксу. Она не предназначена для эффективного поиска произвольной последовательности символов внутри каждой строки: такое условие не соответствует естественному порядку ключей.
Пусть в таблице много текстовых значений и есть индекс по этому столбцу. Поиск строк, начинающихся с заданной последовательности, может ограничить чтение узким диапазоном индекса.
Поиск строк, содержащих фрагмент в произвольной позиции, не даёт такой границы. Даже если индекс формально присутствует, чтение большого числа индексных записей с последующей проверкой условия может оказаться почти таким же дорогим, как сканирование таблицы, особенно когда нужно извлекать данные из самой таблицы.
Для B-дерева важен левый префикс ключа. Если известны первые символы значения, оптимизатор может найти позицию, с которой начинаются подходящие ключи, и прочитать ограниченный диапазон. Если шаблон начинается с произвольного символа, положение подходящих строк в отсортированном индексе заранее не локализовано.
Минимальный пример:
Первое условие соответствует диапазону значений, начинающихся с pro. Второе требует искать pro в любой позиции строки, поэтому обычный B-деревянный индекс чаще всего не даёт эффективного поиска по диапазону.
Точное поведение зависит от СУБД, сопоставления строк, типа индекса и настроек оптимизатора. Некоторые системы могут применять специальные классы операторов, индексы для полнотекстового поиска, триграммные или другие специализированные структуры.
Важно отличать индексный поиск от индексного сканирования. Сканирование самого индекса иногда дешевле полного сканирования таблицы, если индекс существенно уже таблицы и содержит все необходимые столбцы, но это всё равно не означает быстрого поиска по произвольному фрагменту.
Исправление не всегда состоит в добавлении ещё одного обычного B-дерева. Для поиска слов нужен полнотекстовый индекс, для поиска подстрок — структура, поддерживающая такие операции, например триграммный индекс в СУБД, где он доступен. Цена решения — дополнительное место, время построения и обслуживания индекса, а также ограничения на поддерживаемые языковые правила и типы запросов.
В каталоге товаров запрос по названию с начальным префиксом выполнялся быстро, но поиск по фрагменту внутри названия стал медленным после роста таблицы до десятков миллионов строк. Обычный индекс по названию уже существовал, однако план показывал чтение большого объёма данных.
Рассматривались три варианта. Полное сканирование не требовало новых объектов, но плохо масштабировалось. Обычный B-деревянный индекс был полезен для префиксного поиска, но не решал поиск произвольной подстроки. Специализированный индекс лучше соответствовал условию, но увеличивал размер базы и стоимость изменений строк.
Выбрали специализированный индекс для отдельного сценария поиска, а запросы по началу строки оставили на обычном B-дереве. Такое разделение было оправдано разными типами поиска: неиспользуемый для других операций тяжёлый индекс не стали добавлять без измерений. После внедрения проверили план выполнения, фактическое число прочитанных строк и нагрузку на операции вставки и обновления.
Нет. Оптимизатор может отказаться от него, если префикс слишком распространён, оценка селективности неблагоприятна, требуется чтение почти всей таблицы или особенности сопоставления строк мешают построить корректный диапазон. Наличие подходящего индекса не гарантирует его выбора: сравниваются ожидаемые стоимости альтернативных планов.
Если условие возвращает много строк, поиск по индексу может породить большое число обращений к таблице за неиндексированными столбцами. Такие разрозненные обращения к страницам иногда дороже последовательного чтения всей таблицы. При высокой доле подходящих строк оптимизатор может выбрать сканирование, а покрывающий индекс способен изменить компромисс, устранив обращения к базовой таблице.
Иногда применяют заранее вычисляемые признаки, например нормализованные токены или отдельные поисковые сущности, но это уже изменение модели данных и поддерживаемых запросов. Простое добавление обычного B-дерева по исходной строке не создаёт эффективного поиска для любого положения подстроки. Такое преобразование оправдано только при чётко ограниченном формате поиска; для общего текстового поиска обычно выбирают специализированный индекс и учитывают его стоимость обслуживания.