Как ускорить поиск фраз в Manticore Search / Хабр

Кратко

bigram_index можно использовать для разных задач, но в этой статье мы говорим именно о производительности поиска фраз: в приведённом ниже бенчмарке на 1 млн документов bigram_index='all' повысил QPS примерно в 2.9x и сократил среднее время ответа фразовых запросов примерно в 3.2x.

Если ваша основная проблема — сопоставление xt850 с xt 850, а не ускорение поиска фраз, см. Как заставить xt850 совпадать с xt 850 .

Поиск по фразам бывает дорогим. Даже если запрос короткий, движку всё равно нужно проверять порядок слов и стоят ли они рядом, и это особенно заметно, когда:

отдельные слова сами по себе очень частотны
объём данных большой
фразовые запросы часто встречаются в вашей нагрузке

Именно для этого предназначен bigram_index .

Что на самом деле делает индексация биграмм

Обычно фраза вроде "noise cancelling headphones" обрабатывается как набор отдельных токенов, которые при этом должны идти в правильном порядке и стоять рядом друг с другом. Индексация биграмм позволяет Manticore заранее сохранять пары соседних токенов, например:

noise cancelling
cancelling headphones

Это даёт движку более быстрый способ сузить набор документов-кандидатов при поиске по фразе.

Здесь мы говорим именно про ускорение поиска по фразам.

Важное замечание: биграммы работают на уровне токенизации

Этот момент легко упустить, если смотреть только на историю про ускорение в идеальном сценарии.

bigram_index работает только на уровне токенизации. Он не учитывает последующие преобразования, такие как морфология, словоформы или стоп-слова, и из-за этого ожидания от поиска по фразам могут не совпасть с реальным поведением.

Практический вывод простой: биграммы могут отлично ускорять поиск фраз, но если ваш индекс сильно опирается на морфологию, словоформы или стоп-слова, сначала проверьте на своих данных, как у вас реально работает поиск по фразам.

Режим 1: Поведение по умолчанию

Это базовый режим. Явная индексация биграмм не включена, поэтому списки постингов для биграмм не хранятся.

Используйте его, когда:

поиск фраз редок
документы короткие
вам нужна самая быстрая индексация

Пример

DROP TABLE IF EXISTS bi_none_demo;

CREATE TABLE bi_none_demo(title text);

INSERT INTO bi_none_demo VALUES
  (1,'wireless noise cancelling headphones'),
  (2,'noise cancelling microphone'),
  (3,'wireless gaming headset');

SELECT id, title FROM bi_none_demo WHERE MATCH('"noise cancelling"');

Это базовое поведение. Запрос возвращает ожидаемые строки, но у Manticore нет предвычисленных списков постингов биграмм, которые помогали бы обрабатывать фразу эффективнее.

Режим 2: all

bigram_index = all

Это самый сильный режим ускорения поиска по фразам. Каждая пара соседних токенов индексируется как биграмма.

Используйте его, когда:

точный поиск фраз является основной функцией
фразовые запросы часто включают общие слова и дают много кандидатов
вам нужно максимальное ускорение поиска по фразам
вы не хотите настраивать список часто встречающихся слов

Пример

DROP TABLE IF EXISTS bi_all_demo;

CREATE TABLE bi_all_demo(title text)
  bigram_index='all';

INSERT INTO bi_all_demo VALUES
  (1,'lord of the rings trilogy'),
  (2,'house of the dragon season 2'),
  (3,'made for iphone charger');

SELECT id, title FROM bi_all_demo WHERE MATCH('"house of the dragon"');
SELECT id, title FROM bi_all_demo WHERE MATCH('"made for iphone"');

Суть здесь не в том, какие строки совпадут, а в другой стратегии индексации: all сохраняет каждую соседнюю пару, поэтому во время поиска фраз движок получает максимальную помощь от биграмм.

Режим all стоит выбирать, когда поиск по фразам становится тяжелее из-за того, что отдельные слова совпадают во множестве документов и Manticore приходится делать больше позиционных проверок, чтобы подтвердить точную фразу. all помогает раньше сузить круг кандидатов.

Режим 3: first_freq

bigram_index = first_freq
bigram_freq_words = for, of, the, with

В этом режиме пара сохраняется только в том случае, если первый токен входит в ваш список часто встречающихся слов.

Используйте его, когда:

поиск фраз важен
вы хотите более лёгкую альтернативу all
многие фразы в ваших данных содержат слова, которые действительно часто встречаются

С приведённым выше списком:

for iphone подходит
of the подходит
the dragon подходит
made for не подходит
lord of не подходит

Для продакшн-использования не подбирайте bigram_freq_words наугад. Вы можете автоматически получить список из собственных данных. Практический способ — выгрузить статистику словаря с помощью indextool через --dumpdict ... --stats, посмотреть самые частые токены и затем собрать по этим результатам небольшой список bigram_freq_words.

Пример

DROP TABLE IF EXISTS bi_first_freq_demo;

CREATE TABLE bi_first_freq_demo(title text)
  bigram_index='first_freq'
  bigram_freq_words='for,of,the,with';

INSERT INTO bi_first_freq_demo VALUES
  (1,'made for iphone charger'),
  (2,'lord of the rings trilogy'),
  (3,'house of the dragon season 2');

SELECT id, title FROM bi_first_freq_demo WHERE MATCH('"made for iphone"');
SELECT id, title FROM bi_first_freq_demo WHERE MATCH('"lord of the"');

Запросы по-прежнему возвращают ожидаемые строки. Меняется только то, какие пары индексируются:

"made for iphone" ускоряется за счёт for iphone
"lord of the" ускоряется за счёт of the

Это делает first_freq более лёгкой альтернативой all, когда многие полезные фразы включают часто встречающиеся связующие слова.

Режим 4: both_freq

bigram_index = both_freq
bigram_freq_words = for, of, the, with

Это самый точечный режим из тех, что основаны на частоте. Пара сохраняется только тогда, когда оба токена входят в список часто встречающихся слов.

Используйте его, когда:

вам нужен минимальный объём биграмм
вам в основном важны пары из слов, которые часто встречаются в ваших данных
вы работаете с большим корпусом и не хотите индексировать каждую соседнюю пару

С тем же списком:

of the подходит
for iphone не подходит
the dragon не подходит

Пример

DROP TABLE IF EXISTS bi_both_freq_demo;

CREATE TABLE bi_both_freq_demo(title text)
  bigram_index='both_freq'
  bigram_freq_words='for,of,the,with';

INSERT INTO bi_both_freq_demo VALUES
  (1,'lord of the rings trilogy'),
  (2,'house of the dragon season 2'),
  (3,'made for iphone charger');

SELECT id, title FROM bi_both_freq_demo WHERE MATCH('"lord of the"');
SELECT id, title FROM bi_both_freq_demo WHERE MATCH('"made for iphone"');

Запросы по-прежнему совпадают, но внутренняя логика отбора здесь другая:

"lord of the" включает of the, который both_freq готов хранить
"made for iphone" включает for iphone, который покрывается first_freq, но both_freq не хранит

Какой режим выбрать?

Бенчмарк в этой статье показывает, что all может дать заметное ускорение, но это всё равно только один бенчмарк на одном типе нагрузки.

В документации Manticore сказано, что для большинства сценариев лучшим режимом является both_freq. Это разумный выбор по умолчанию, потому что он даёт более сбалансированный компромисс между ускорением фраз и стоимостью индексации.

Используйте режимы так:

both_freq — исходная точка по умолчанию для общих задач поиска по фразам
all — когда поиск фраз особенно важен и вам нужно максимальное ускорение, если более высокая стоимость индексации приемлема
first_freq — когда многие полезные фразы в ваших данных содержат частые служебные слова и вам нужен вариант шире, чем both_freq
поведение по умолчанию — когда ускорение фраз не важно

Бенчмарк: действительно ли индексация биграмм ускоряет поиск фраз?

Да. В простом локальном бенчмарке разница хорошо видна.

Мы использовали manticore-load, чтобы создать две таблицы по 1 млн документов на одном и том же инстансе Manticore:

одна без явной настройки bigram_index
другая с bigram_index='all'

Документы представляли собой случайные тексты длиной 60–80 слов, а тест многократно выполнял случайные фразовые запросы из 2 слов.

Для наглядности и индексация, и поиск запускались с --threads=1. В многопоточных режимах показатели, конечно, будут выше, но однопоточные запуски позволяют проще увидеть, как эта настройка влияет на работу одного ядра процессора.

SELECT COUNT(*) FROM bench_bigram_* WHERE MATCH('"<text/2/2>"')

Настройка теста

Загрузка данных без биграмм:

manticore-load \
  --drop \
  --wait \
  --threads=1 \
  --batch-size=1000 \
  --total=1000000 \
  --init="CREATE TABLE bench_bigram_none_rand(title text)" \
  --load="INSERT INTO bench_bigram_none_rand(id,title) VALUES(<increment>,'<text/60/80>')"

Загрузка данных с bigram_index='all':

manticore-load \
  --drop \
  --wait \
  --threads=1 \
  --batch-size=1000 \
  --total=1000000 \
  --init="CREATE TABLE bench_bigram_all_rand(title text) bigram_index='all'" \
  --load="INSERT INTO bench_bigram_all_rand(id,title) VALUES(<increment>,'<text/60/80>')"

Тест поиска без биграмм:

manticore-load \
  --threads=1 \
  --total=5000 \
  --load="SELECT COUNT(*) FROM bench_bigram_none_rand WHERE MATCH('\\\"<text/2/2>\\\"')"

Тест поиска с bigram_index='all':

manticore-load \
  --threads=1 \
  --total=5000 \
  --load="SELECT COUNT(*) FROM bench_bigram_all_rand WHERE MATCH('\\\"<text/2/2>\\\"')"

Что мы увидели

В этом локальном запуске результаты были такими:

Table	QPS	Avg latency
`bench_bigram_none_rand`	`755`	`1.3 ms`
`bench_bigram_all_rand`	`2175`	`0.4 ms`

Это примерно 2.9x прироста QPS и около 3.2x снижения среднего времени ответа при той же нагрузке в 1 млн документов.

Индексация была медленнее с bigram_index='all', что ожидаемо:

без биграмм: около 45k docs/sec
с all: около 17k docs/sec

Именно этот компромисс объясняет, почему существует несколько режимов.

Итоговый вывод

Если ваша главная проблема — производительность поиска фраз, считайте bigram_index прежде всего функцией ускорения.

Для большинства реальных нагрузок начните с both_freq и измерьте результат. Переходите к all, если нужен более сильный эффект и вы можете позволить себе дополнительные затраты на индексацию. first_freq имеет смысл, если на поиск по фразам у вас сильно влияют частые служебные слова.