mufassall

Шпаргалка · Данные и хранение

Полнотекстовый поиск

14 мин · Средний · mufassall.dtwin.uz/ru/l/full-text-search/

← Открыть урок

Проблема

Маркетплейс ищет по каталогу через `LIKE '%слово%'`. При 4 миллионах товаров каждый поиск читает каждую строку и всё равно не находит товары, записанные с другим апострофом, кириллицей или с узбекским аффиксом. Строим настоящий полнотекстовый поиск: инвертированный индекс по разобранным токенам, ранжирование BM25, индекс, который следует за журналом изменений базы, шарды со scatter-gather и устойчивость к опечаткам.

Чему вы научитесь

  • Почему LIKE '%x%' не может использовать индекс и читает всю таблицу
  • Анализ текста: нижний регистр, кириллица в латиницу, узбекские апострофы и аффиксы, один анализатор при индексации и при запросе
  • Инвертированный индекс с postings и ранжирование BM25 на конкретных числах
  • Свежесть индекса через журнал изменений, шардирование по документам, scatter-gather и устойчивость к опечаткам
Итоговая сцена
30%40%

Диаграмма как код

Итоговая схема урока в виде текста: вставьте её в Jira, GitLab, GitHub, Notion или документацию, там Mermaid рисуется сам. Есть варианты для D2 и PlantUML (Confluence, IntelliJ).

Mermaid: схема

flowchart LR
  n_user(["Приложение магазина"])
  n_api["Search API"]
  n_db[("БД товаров")]
  n_catalog["Сервис каталога"]
  n_indexer("Индексатор")
  n_log[["Журнал изменений"]]
  n_shard1[("Шард индекса 1")]
  n_shard2[("Шард индекса 2")]
  n_user -->|"вызов"| n_api
  n_catalog --> n_db
  n_db -->|"асинхронно"| n_log
  n_indexer --> n_log
  n_api --> n_shard1
  n_api --> n_shard2
  n_indexer --> n_shard1
  n_indexer --> n_shard2

Mermaid: последовательность запросов

sequenceDiagram
  participant n_api as Search API
  participant n_db as БД товаров
  participant n_index as Поисковый индекс
  participant n_user as Приложение магазина
  participant n_indexer as Индексатор
  participant n_log as Журнал изменений
  participant n_shard2 as Шард индекса 2
  Note over n_api,n_db: Поиск через LIKE, пока каталог маленький
  n_api->>n_db: SELECT id, title, price_minor FROM products
  Note over n_api,n_db: 4 миллиона товаров: каждый поиск читает таблицу
  n_api->>n_db: EXPLAIN ANALYZE SELECT ... WHERE lower(title #124;#124; ' ' #124;#124; description) LIKE '%choynak%'#59;
  n_db-->>n_api: Seq Scan on products (rows removed by filter: 3 998 160)
  Note over n_api,n_index: Перевернуть: от слова к товарам
  n_api->>n_index: term df postings (doc id: positions)
  Note over n_user,n_api: Одно слово, написанное четырьмя способами
  n_user->>n_api: sellers wrote #34;g'ilof#34; (phone case) in 4 ways, 2 170 products
  Note over n_indexer,n_index: Решить, что такое слово, один раз и для обеих сторон
  n_indexer->>n_index: analyze(#34;Telefon GʻILOFLARI, qora#34;)
  Note over n_api,n_index: Ранжировать по релевантности, а не по продажам
  n_api->>n_index: query #34;elektr choynak#34; N = 4 000 000 avgdl = 12
  Note over n_indexer,n_db: Новый товар не виден до завтра
  n_indexer->>n_db: 10:12 seller adds #34;Elektr choynak 2 l#34; id 4120551 -#62; Products DB ok
  Note over n_indexer,n_log: Питать индекс из журнала изменений базы
  n_indexer->>n_log: cdc products op=u id=4120551 lsn 0/7A3F10
  Note over n_api,n_shard2: Делить по документам, спрашивать каждый шард
  n_api->>n_shard2: search q=#34;elektr choynak#34; size=10 -#62; both shards
  Note over n_user,n_api: Найти #34;choynak#34;, когда покупатель набрал #34;choyank#34;
  n_user->>n_api: POST /v1/search HTTP/1.1
  n_api-->>n_user: HTTP/1.1 200 OK

D2

direction: right

n_user: "Приложение магазина" {
  shape: rectangle
}
n_api: "Search API" {
  shape: rectangle
}
n_db: "БД товаров" {
  shape: cylinder
}
n_catalog: "Сервис каталога" {
  shape: rectangle
}
n_indexer: "Индексатор" {
  shape: rectangle
  style.multiple: true
}
n_log: "Журнал изменений" {
  shape: queue
}
n_shard1: "Шард индекса 1" {
  shape: cylinder
}
n_shard2: "Шард индекса 2" {
  shape: cylinder
}

n_user -> n_api: "вызов"
n_catalog -> n_db
n_db -> n_log: "асинхронно"
n_indexer -> n_log
n_api -> n_shard1
n_api -> n_shard2
n_indexer -> n_shard1
n_indexer -> n_shard2

PlantUML: последовательность запросов

@startuml
participant "Search API" as n_api
database "БД товаров" as n_db
database "Поисковый индекс" as n_index
participant "Приложение магазина" as n_user
participant "Индексатор" as n_indexer
queue "Журнал изменений" as n_log
database "Шард индекса 2" as n_shard2
note over n_api, n_db : Поиск через LIKE, пока каталог маленький
n_api -> n_db : SELECT id, title, price_minor FROM products
note over n_api, n_db : 4 миллиона товаров: каждый поиск читает таблицу
n_api -> n_db : EXPLAIN ANALYZE SELECT ... WHERE lower(title || ' ' || description) LIKE '%choynak%';
n_db --> n_api : Seq Scan on products (rows removed by filter: 3 998 160)
note over n_api, n_index : Перевернуть: от слова к товарам
n_api -> n_index : term df postings (doc id: positions)
note over n_user, n_api : Одно слово, написанное четырьмя способами
n_user -> n_api : sellers wrote "g'ilof" (phone case) in 4 ways, 2 170 products
note over n_indexer, n_index : Решить, что такое слово, один раз и для обеих сторон
n_indexer -> n_index : analyze("Telefon GʻILOFLARI, qora")
note over n_api, n_index : Ранжировать по релевантности, а не по продажам
n_api -> n_index : query "elektr choynak" N = 4 000 000 avgdl = 12
note over n_indexer, n_db : Новый товар не виден до завтра
n_indexer -> n_db : 10:12 seller adds "Elektr choynak 2 l" id 4120551 -> Products DB ok
note over n_indexer, n_log : Питать индекс из журнала изменений базы
n_indexer -> n_log : cdc products op=u id=4120551 lsn 0/7A3F10
note over n_api, n_shard2 : Делить по документам, спрашивать каждый шард
n_api -> n_shard2 : search q="elektr choynak" size=10 -> both shards
note over n_user, n_api : Найти "choynak", когда покупатель набрал "choyank"
n_user -> n_api : POST /v1/search HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
@enduml

PlantUML: компоненты

@startuml
left to right direction
agent "Приложение магазина" as n_user
component "Search API" as n_api
database "БД товаров" as n_db
component "Сервис каталога" as n_catalog
collections "Индексатор" as n_indexer
queue "Журнал изменений" as n_log
database "Шард индекса 1" as n_shard1
database "Шард индекса 2" as n_shard2
n_user --> n_api : вызов
n_catalog --> n_db
n_db --> n_log : асинхронно
n_indexer --> n_log
n_api --> n_shard1
n_api --> n_shard2
n_indexer --> n_shard1
n_indexer --> n_shard2
@enduml

Итог

Шесть правил полнотекстового поиска.

1) LIKE '%x%' читает каждую строку; дальше маленькой таблицы он не растёт. 2) Решите, что такое слово, одним анализатором для товаров и запросов: нижний регистр, один алфавит, без вариантов апострофа, осторожный стеммер. 3) Инвертированный индекс связывает слова с отсортированными postings; поиск читает только эти списки. 4) Ранжируйте BM25: редкость учитывается, повторы насыщаются, длинные тексты штрафуются. 5) Питайте индекс из журнала изменений базы и примите near-real-time; цены и остатки перечитываются из базы. 6) Шардируйте по документам со scatter-gather и прощайте опечатки в жёстких пределах.

Показатели: в начале и в конце

ПоказательВ началеВ конце
p95 поиска45 мс24 мс
Строк прочитано за поиск50 00021 000
Не найдено нужных товаров37%6%
Поисков без результатов3%2%
От записи до поиска0 с2 с

Шаги

  1. Кейс Поиск через LIKE, пока каталог маленький

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

  2. Проблема 4 миллиона товаров: каждый поиск читает таблицу

    Через три года в каталоге 4 миллиона товаров и 1.2 ГБ текста.

  3. Решение Перевернуть: от слова к товарам

    Инвертированный индекс хранит для каждого слова список товаров, где оно встречается, — его postings.

  4. Проблема Одно слово, написанное четырьмя способами

    Быстро, но треть нужных товаров всё ещё не находится.

  5. Решение Решить, что такое слово, один раз и для обеих сторон

    Прежде чем слово попадёт в индекс, анализатор нормализует его: нижний регистр, кириллица в латиницу ("чойнак" → "choynak"), все варианты апострофа удаляются, текст режется на токены, отсекается короткий список аффиксов.

  6. Решение Ранжировать по релевантности, а не по продажам

    Теперь "elektr choynak" находит 1 840 товаров, и порядок важен.

  7. Проблема Новый товар не виден до завтра

    Индекс перестраивается каждую ночь.

  8. Решение Питать индекс из журнала изменений базы

    Каждое закоммиченное изменение в таблице товаров попадает в журнал изменений через CDC или outbox.

  9. Решение Делить по документам, спрашивать каждый шард

    С описаниями и позициями индекс дорастает до 38 ГБ и больше не помещается в памяти одного узла: в пик p95 ползёт вверх.

  10. Решение Найти "choynak", когда покупатель набрал "choyank"

    2% поисков всё ещё ничего не находят, в основном из-за опечаток.

  11. Итоги Итог

    Шесть правил полнотекстового поиска.

Термины

Инвертированный индекс
Индекс, который хранит для каждого слова отсортированный список документов, где оно встречается (postings). Поиск читает не документы, а только списки слов из запроса и пересекает их.
Анализатор текста
Цепочка шагов, превращающая текст в токены индекса: нижний регистр, один алфавит, удаление вариантов апострофа, разбиение на токены, стемминг. Тот же анализатор обязан применяться и к запросу.
BM25
Стандартная формула ранжирования полнотекстового поиска. Редкие слова весят больше (idf), повторы помогают, но насыщаются (k1), длинные тексты штрафуются (b).
Индекс near-real-time
Индекс, в котором новые записи становятся видимыми не сразу, а при следующем refresh, обычно раз в секунду. Чем чаще refresh, тем больше мелких сегментов на слияние.
Scatter-gather
Запрос рассылается во все шарды, каждый возвращает свой топ-k, а координатор сливает их в один список. Ответ длится столько, сколько самый медленный шард.