Шпаргалка · Данные и хранение
Полнотекстовый поиск
Проблема
Маркетплейс ищет по каталогу через `LIKE '%слово%'`. При 4 миллионах товаров каждый поиск читает каждую строку и всё равно не находит товары, записанные с другим апострофом, кириллицей или с узбекским аффиксом. Строим настоящий полнотекстовый поиск: инвертированный индекс по разобранным токенам, ранжирование BM25, индекс, который следует за журналом изменений базы, шарды со scatter-gather и устойчивость к опечаткам.
Чему вы научитесь
- Почему
LIKE '%x%'не может использовать индекс и читает всю таблицу - Анализ текста: нижний регистр, кириллица в латиницу, узбекские апострофы и аффиксы, один анализатор при индексации и при запросе
- Инвертированный индекс с postings и ранжирование BM25 на конкретных числах
- Свежесть индекса через журнал изменений, шардирование по документам, scatter-gather и устойчивость к опечаткам
Диаграмма как код
Итоговая схема урока в виде текста: вставьте её в 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_shard2Mermaid: последовательность запросов
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 OKD2
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_shard2PlantUML: последовательность запросов
@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
@endumlPlantUML: компоненты
@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 000 | 21 000 |
| Не найдено нужных товаров | 37% | 6% |
| Поисков без результатов | 3% | 2% |
| От записи до поиска | 0 с | 2 с |
Шаги
- Кейс Поиск через LIKE, пока каталог маленький
Продавцы добавляют товары через сервис каталога, покупатели вводят слова в строку поиска.
- Проблема 4 миллиона товаров: каждый поиск читает таблицу
Через три года в каталоге 4 миллиона товаров и 1.2 ГБ текста.
- Решение Перевернуть: от слова к товарам
Инвертированный индекс хранит для каждого слова список товаров, где оно встречается, — его postings.
- Проблема Одно слово, написанное четырьмя способами
Быстро, но треть нужных товаров всё ещё не находится.
- Решение Решить, что такое слово, один раз и для обеих сторон
Прежде чем слово попадёт в индекс, анализатор нормализует его: нижний регистр, кириллица в латиницу ("чойнак" → "choynak"), все варианты апострофа удаляются, текст режется на токены, отсекается короткий список аффиксов.
- Решение Ранжировать по релевантности, а не по продажам
Теперь "elektr choynak" находит 1 840 товаров, и порядок важен.
- Проблема Новый товар не виден до завтра
Индекс перестраивается каждую ночь.
- Решение Питать индекс из журнала изменений базы
Каждое закоммиченное изменение в таблице товаров попадает в журнал изменений через CDC или outbox.
- Решение Делить по документам, спрашивать каждый шард
С описаниями и позициями индекс дорастает до 38 ГБ и больше не помещается в памяти одного узла: в пик p95 ползёт вверх.
- Решение Найти "choynak", когда покупатель набрал "choyank"
2% поисков всё ещё ничего не находят, в основном из-за опечаток.
- Итоги Итог
Шесть правил полнотекстового поиска.
Термины
- Инвертированный индекс
- Индекс, который хранит для каждого слова отсортированный список документов, где оно встречается (postings). Поиск читает не документы, а только списки слов из запроса и пересекает их.
- Анализатор текста
- Цепочка шагов, превращающая текст в токены индекса: нижний регистр, один алфавит, удаление вариантов апострофа, разбиение на токены, стемминг. Тот же анализатор обязан применяться и к запросу.
- BM25
- Стандартная формула ранжирования полнотекстового поиска. Редкие слова весят больше (idf), повторы помогают, но насыщаются (k1), длинные тексты штрафуются (b).
- Индекс near-real-time
- Индекс, в котором новые записи становятся видимыми не сразу, а при следующем refresh, обычно раз в секунду. Чем чаще refresh, тем больше мелких сегментов на слияние.
- Scatter-gather
- Запрос рассылается во все шарды, каждый возвращает свой топ-k, а координатор сливает их в один список. Ответ длится столько, сколько самый медленный шард.