Полнотекстовый поиск: инвертированный индекс, анализ и почему ранжирование важнее совпадения

Поиск товаров выкатили с WHERE title LIKE '%running shoes%'. В демо работает. На 50k строк это full table scan на 400ms, потому что ведущий % убивает любой индекс. Потом покупатель ищет “running shoe” — в единственном числе — и получает ноль результатов, а “Running Shoes” не находит ничего, потому что совпадение чувствительно к регистру. Запрос делает сравнение строк, тогда как задачей был поиск. Две разные проблемы в одном операторе =.

Почему LIKE '%term%' никогда не станет поиском

У LIKE '%running%' два фатальных свойства. Первое: ведущий wildcard означает, что ни один B-tree индекс не поможет — база сканирует каждую строку и прогоняет на каждой поиск подстроки, поэтому стоимость растёт линейно с размером таблицы. На паре тысяч строк никто не замечает; на паре миллионов это таймаут. Второе: он матчит подстроки байтов, а не слова языка. “running” не совпадёт с “run”, “Run”, “ran” или “runs”. Зато радостно найдёт “scunthorpe” внутри длинного слова и промахнётся мимо “shoe”, когда в тексте “shoes”. И главное: у LIKE нет понятия релевантности — строка, где термин встречается один раз в подвале, ранжируется так же, как та, где он трижды в заголовке. Совпадение бинарно; поиск упорядочен.

Полнотекстовый поиск заменяет обе половины. Инвертированный индекс решает нахождение — превращает линейный скан в lookup по хешу. Скоринг релевантности решает упорядочивание — какой из 10 000 матчей человек должен увидеть первым. Нужны оба. Система, которая находит всё, но плохо ранжирует, так же бесполезна, как та, что ранжирует идеально, но слишком медленна.

Инвертированный индекс: термин → posting list

Обычный (прямой) индекс отображает документ на его слова. Инвертированный индекс — наоборот: каждый термин указывает на posting list из id документов, которые его содержат, обычно с позициями и частотами термина. Поиск “running shoes” превращается в: взять posting list для running, взять posting list для shoes, пересечь их. Это два lookup по словарю и merge двух отсортированных списков id — миллисекунды независимо от размера корпуса, потому что ты никогда не трогаешь документы без этих терминов.

Документы:                  Инвертированный индекс:
  doc1: "running shoes"       running -> [doc1, doc3]
  doc2: "blue dress"          shoes   -> [doc1]
  doc3: "trail running gear"  blue    -> [doc2]
                              dress   -> [doc2]
                              trail   -> [doc3]
                              gear    -> [doc3]
Запрос "running shoes" -> пересечение [doc1,doc3] & [doc1] = [doc1]

Это структура данных внутри Postgres tsvector/GIN и внутри Lucene (движок под Elasticsearch и OpenSearch). Трудность не в lookup — в решении, что считается “термином”, а это и есть конвейер анализа.

Анализ: конвейер, который решает, что совпадёт

Сырой текст никогда не попадает в индекс напрямую. Он проходит через анализатор: tokenize → lowercase → удалить стоп-слова → stemming или лемматизация. “The Runners Were Running” становится примерно [run, run] после разбиения по пробелам, понижения регистра, выброса стоп-слов “the”/“were” и стемминга “runners”/“running” до корня “run”. Теперь запрос на “run”, “running” или “runners” попадает в один и тот же индексированный токен. Вот почему полнотекстовый поиск матчит единственное и множественное число там, где LIKE не может — совпадение происходит на нормализованных токенах, а не на сырых строках.

Ловушка сеньора прячется на виду: один и тот же анализатор должен работать на индексировании и на запросе. Если ты стеммишь документы до “run” при индексировании, но забываешь стеммить запрос, то поиск “running” даёт токен “running”, которого нет в индексе, и ты получаешь ноль результатов — молча, без ошибки. Это самый частый инцидент “поиск сломан, и я не знаю почему”. Фикс и диагностика — один и тот же инструмент: API _analyze в Elasticsearch (или to_tsvector в Postgres) показывает точные токены обеих сторон, и ты видишь рассогласование.

Релевантность: TF-IDF, затем BM25

Когда у тебя есть кандидаты, ты их скоришь. Интуиция — TF-IDF: термин важнее в документе, чем чаще он там встречается (term frequency), но менее важен, если он частый по всему корпусу (inverse document frequency) — “the” 50 раз не говорит ни о чём. Современные движки используют BM25 — уточнение, которое чинит главный недостаток TF-IDF: сырая частота термина растёт без предела, поэтому спамный документ, повторяющий “shoes” 200 раз, доминировал бы. BM25 насыщает частоту термина — 10-е вхождение добавляет куда меньше, чем 2-е — и нормализует на длину документа, чтобы длинная статья не получала несправедливый буст просто за длину.

У BM25 две ручки, которые сеньор должен узнавать. k1 (по умолчанию 1.2 в Elasticsearch и Lucene) задаёт, как быстро насыщается частота термина — ниже значит насыщается раньше. b (по умолчанию 0.75) задаёт, насколько сильно нормализуется длина документа: 0 игнорирует длину полностью, 1 нормализует полностью. Дефолты хороши для прозы; ты тюнишь их, когда документы необычно короткие (заголовки товаров) или длинные (мануалы), и тюнишь, измеряя релевантность на размеченных запросах — никогда на глаз, потому что изменение тюнинга, помогающее одному классу запросов, молча регрессирует другой.

Postgres против выделенного движка: реальное решение

Postgres tsvector + GIN — это по-настоящему хороший поиск и правильный дефолт, пока не перестанет быть им. Решение, которое сеньор действительно взвешивает:

Внутри Postgres есть второй выбор: GIN против GiST. GIN ищет примерно в 3 раза быстрее, но строится в ~3 раза дольше, в 2–3 раза больше на диске и медленнее обновляется — а с fastupdate=on он батчит записи в pending list, который раздувает индекс и может застопорить запрос при сбросе. GiST меньше и быстрее обновляется, но lossy, поэтому перепроверяет таблицу на матчах. Правило большого пальца: GIN для read-heavy, в основном статичного текста; GiST когда записи постоянны или размер индекса больно бьёт. Режим отказа на масштабе — bloat GIN под высокой записью: твой “быстрый” поисковый индекс тихо деградирует, пока REINDEX или тюнинг autovacuum не спасут.

Near-real-time и налог на reindex-the-world

Выделенные движки не мгновенно консистентны — они near-real-time. refresh_interval в Elasticsearch по умолчанию 1s, то есть свежеиндексированный документ не ищется до секунды. Это фича: refresh дорогой, поэтому под тяжёлыми bulk-загрузками сеньоры поднимают его до 30s или ставят -1 на время большого импорта и делают refresh один раз в конце — меняя задержку видимости на throughput. Ловушка — предполагать write-then-read консистентность, которой у тебя нет.

Самый большой эксплуатационный налог — миграция reindex-the-world. Lucene не даст сменить тип или анализатор существующего поля — токены уже зафиксированы. Хочешь добавить фильтр синонимов или починить баг стемминга по 200M документам? Ты строишь новый индекс с новым mapping, реиндексируешь всё в него (часы), затем атомарно переключаешь read-алиас со старого на новый, чтобы клиенты не увидели даунтайма. Забыть спроектировать всё за алиасом в первый день — та ошибка, которая превращает однострочный фикс анализатора в многодневную миграцию всем составом.