Поиск — это сложно. Важная часть многих приложений, которую нелегко реализовать правильно. Особенно в случае с RAG-пайплайнами, где на качество поиска завязан весь процесс.

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

Эрик Закариассон, разработчик и автор блога Anyblockers, рассмотрел в своей статье, как использовать Postgres для создания надёжной поисковой системы. В рамках задачи автор объединил три техники:

Полнотекстовый поиск с tsvector
Семантический поиск с pgvector
Нечёткое сопоставление с pg_trgm
Бонус: BM25

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

Не стану лишний раз рассказывать о том, почему вы должны использовать Postgres™️ для всего, но если хотите почитать об этом, вот несколько хороших ресурсов:

Стол с четырьмя ножками

Именно с этим столом мы будем работать в качестве примера.

create table documents (
    id bigint primary key generated always as identity,
    title text,
    fts_title tsvector generated always as (to_tsvector('english', title)) stored,
    embedding vector(1536)
);

В дальнейшем мы будем развивать эту таблицу. Поскольку в Supabase есть отличная статья о реализации гибридного поиска, воспользуемся ею в качестве отправной точки.

Следуйте руководству по реализации FTS с GIN-индексами и семантического поиска с pgvector (также известного как bi-encoder dense retrieval).
Исходя из личного опыта я бы выбрал вкрапления размерностью 1536, так как они дают гораздо лучшие результаты. Источник: поверьте мне.
Я заменил функцию Supabase только CTE и запросом, а также снабдил параметры префиксом $. Вот как это выглядит:

with full_text as (
    select
        id,
        -- Note: ts_rank_cd is not indexable but will only rank matches of the where clause
        -- which shouldn't be too big
        row_number() over(order by ts_rank_cd(fts_title, websearch_to_tsquery($query_text)) desc) as rank_ix
    from
        documents
    where
        fts_title @@ websearch_to_tsquery($query_text)
    order by rank_ix
    limit least($match_count, 30)
),
semantic as (
    select
        id,
        row_number() over (order by embedding <#> $query_embedding) as rank_ix
    from
        documents
    order by rank_ix
    limit least($match_count, 30)
)
select
    documents.*
from
    full_text
    full outer join semantic
        on full_text.id = semantic.id
    join documents
        on coalesce(full_text.id, semantic.id) = documents.id
order by
    coalesce(1.0 / ($rrf_k + full_text.rank_ix), 0.0) * $full_text_weight +
    coalesce(1.0 / ($rrf_k + semantic.rank_ix), 0.0) * $semantic_weight
    desc
limit
    least($match_count, 30);

Примечание: Мы используем coalesceв нескольких местах по важным причинам:

В пункте join

join documents
    on coalesce(full_text.id, semantic.id) = documents.id

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

2. В пункте order by

coalesce(1.0 / ($rrf_k + full_text.rank_ix), 0.0) * $full_text_weight +
coalesce(1.0 / ($rrf_k + semantic.rank_ix), 0.0) * $semantic_weight

Позволяет справиться со случаями, когда документ может присутствовать в одном результате поиска, но не в другом. Если документа нет в полнотекстовых результатах, его full_text.rank_ixбудет NULL, поэтому мы используем coalesce, чтобы рассматривать его как 0.0 в расчёте ранжирования. То же самое относится и к результатам семантического поиска.

Для объединения результатов мы используем Reciprocal Ranked Fusion (RRF).

Этот метод гарантирует, что элементы, занявшие высокие позиции в нескольких списках, получают высокий ранг в окончательном списке. Он также гарантирует, что элементы, занявшие высокие позиции только в нескольких списках, но низкие в других, не получают высокий ранг в окончательном списке. Размещение ранга в знаменателе при расчёте балла помогает "штрафовать" записи с низким рангом.

Также стоит отметить:

$rrf_k: Чтобы предотвратить чрезвычайно высокие оценки для элементов, занявших первое место (поскольку мы делим на ранг), в знаменатель часто добавляют константу k, чтобы сгладить оценку.
$ _weight: Мы можем присвоить вес каждому методу. Это очень полезно при настройке результатов.

Реализация нечёткого поиска

Итак, все вышеописанное позволяет нам продвинуться довольно далеко, но непосредственной проблемой являются опечатки в именованных сущностях. Хотя семантический поиск устраняет некоторые из этих проблем, захватывая сходства, он с трудом справляется с именами, аббревиатурами и другим текстом, который не является семантически схожим. Чтобы сгладить эту проблему, мы вводим расширение pg_trgm, позволяющее осуществлять нечёткий поиск.

create extension if not exists pg_trgm;

Оно работает с триграммами. Вот как это выглядит:

Триграммы полезны для нечёткого поиска, поскольку разбивают слова на последовательности из трёх символов. Это позволяет находить похожие слова, даже если в них есть опечатки или небольшие вариации. Например, слова «hello» и «helo» имеют много общих триграмм, что облегчает их сопоставление при нечётком поиске.

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

create index idx_documents_title_trgm on documents using gin (title gin_trgm_ops);

После этого — добавить его в полный поисковый запрос. Расширение использует оператор % для фильтрации текста, сходство которого больше порога pg_trgm.similarity_threshold (по умолчанию 0,3). Есть также несколько других полезных операторов. Все хорошо документировано здесь: pg_trgm - поддержка сходства текста с использованием триграммного соответствия.

Вот новый запрос с реализованным нечётким поиском:

with fuzzy as ( 
    select id,
           similarity(title, $query_text) as sim_score,
           row_number() over (order by similarity(title, $query_text) desc) as rank_ix
    from documents
    where title % $query_text
    order by rank_ix
    limit least($match_count, 30)
),
full_text as (
    select id,
           ts_rank_cd(to_tsvector('english', title), websearch_to_tsquery($query_text)) as rank_score,
           row_number() over (order by ts_rank_cd(to_tsvector('english', title), websearch_to_tsquery($query_text)) desc) as rank_ix
    from documents
    where to_tsvector('english', title) @@ websearch_to_tsquery($query_text)
    order by rank_ix
    limit least($match_count, 30)
),
semantic as (
    select id,
           row_number() over (order by embedding <#> $query_embedding) as rank_ix
    from documents
    order by rank_ix
    limit least($match_count, 30)
)
select documents.*
from fuzzy
full outer join full_text on fuzzy.id = full_text.id
full outer join semantic on coalesce(fuzzy.id, full_text.id) = semantic.id
join documents on coalesce(fuzzy.id, full_text.id, semantic.id) = documents.id
order by
    coalesce(1.0 / ($rrf_k + fuzzy.rank_ix), 0.0) * $fuzzy_weight +
    coalesce(1.0 / ($rrf_k + full_text.rank_ix), 0.0) * $full_text_weight +
    coalesce(1.0 / ($rrf_k + semantic.rank_ix), 0.0) * $semantic_weight
desc
limit least($match_count, 30);

Отладка ранжирования

Получив результаты, очень полезно понять, почему что-то совпало, а что-то нет. Для начала нам нужно убедиться, что мы возвращаем все оценки из различных CTE.

semantic as (
  select id,
  1 - (embedding <=> $query_embedding) as cosine_similarity, 
)

Далее нам нужно включить их в окончательный ответ. Я обнаружил, что полезно хранить их в виде объекта JSON, который можно передавать как угодно.

select
  ...
  json_build_object(
      'fuzzy', json_build_object('rank_ix', fuzzy.rank_ix, 'sim_score', fuzzy.sim_score),
      'full_text', json_build_object('rank_ix', full_text.rank_ix, 'rank_score', full_text.rank_score),
      'semantic', json_build_object('rank_ix', semantic.rank_ix, 'cosine_similarity', semantic.cosine_similarity)
  ) as rankings
...

Вот как это выглядит:

{
  "rankings": {
    "fuzzy": {
      "rank_ix": 5,
      "sim_score": 0.6
    },
    "full_text": {
      "rank_ix": 4,
      "rank_score": 0.756
    },
    "semantic": {
      "rank_ix": 1,
      "cosine_similarity": 0.912
    }
  }
}

Настройка полнотекстового поиска

Взвешивание tsvectors

Теперь в ваших документах может быть не только заголовок, но и содержимое. Давайте добавим столбец body.

create table documents (
    id bigint primary key generated always as identity,
    title text,
    body text, 
    fts_title tsvector generated always as (to_tsvector('english', title)) stored, 
    fts_body tsvector generated always as (to_tsvector('english', body)) stored, 
    embedding vector(1536)
);

Мы сохраняем только один столбец встраивания, несмотря на то, что у нас несколько полей. Лично я не обнаружил значительной производительности в сохранении нескольких встраиваний, но вместо этого сохранил и title, и bodyв одном. В конце концов titleдолжен быть кратким представление body. Здесь я рекомендую вам поэкспериментировать в зависимости от ваших потребностей.

Теперь посмотрим на столбцыfts_. Мы ожидаем, что заголовок будет коротким и насыщенным ключевыми словами, а тело будет длиннее и содержать больше деталей. Таким образом, нам нужно скорректировать соотношение столбцов полнотекстового поиска между собой. Для лучшего понимания советую документацию: 12.3.3. Ранжирование результатов поиска favicon.

Вот вкратце:

Веса позволяют определять приоритеты слов в зависимости от их местоположения или важности в документе.
A-weight: наиболее важные (например, заголовок, хедеры). По умолчанию 1.0
B-weight: важные (например, начало документа, аннотация). По умолчанию 0,4
C-weight: стандартная важность (например, основной текст). По умолчанию 0,2
D-вес: наименее важные (например, сноски, примечания). По умолчанию0,1
Настройте весовые коэффициенты для точной регулировки значимости в зависимости от структуры документа и потребностей приложения.

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

С этой информацией мы можем приступить к обновлению индексов:

create table documents (
    id bigint primary key generated always as identity,
    title text,
    body text,
    fts_title tsvector generated always as (setweight(to_tsvector('english', coalesce(title, '')), 'A')) stored, 
    fts_body tsvector generated always as (setweight(to_tsvector('english', coalesce(body, '')), 'C')) stored, 
    embedding vector(1536)
);

В результате titleбудет иметь вес 1,0, а body — 0,2.

Как и раньше, мы добавим новыйfts_bodyв финальный запрос. Я также переименовал предыдущий full_textв fts_title.

...
fts_body as (
    select id,
           ts_rank_cd(fts_body, websearch_to_tsquery($query_text)) as rank_score,
           row_number() over (order by ts_rank_cd(fts_body, websearch_to_tsquery($query_text)) desc) as rank_ix
    from documents
    where fts_body @@ websearch_to_tsquery($query_text)
    order by rank_ix
    limit least($match_count, 30)
),
...

И комбинированный запрос:

select
    documents.*,
    coalesce(1.0 / ($rrf_k + fuzzy.rank_ix), 0.0) * $fuzzy_weight +
    coalesce(1.0 / ($rrf_k + fts_title.rank_ix), 0.0) * $fts_title_weight +
    coalesce(1.0 / ($rrf_k + fts_body.rank_ix), 0.0) * $fts_body_weight +
    coalesce(1.0 / ($rrf_k + semantic.rank_ix), 0.0) * $semantic_weight as combined_rank,
    json_build_object(
        'fuzzy', json_build_object('rank_ix', fuzzy.rank_ix, 'sim_score', fuzzy.sim_score),
        'fts_title', json_build_object('rank_ix', fts_title.rank_ix, 'rank_score', fts_title.rank_score),
        'fts_body', json_build_object('rank_ix', fts_body.rank_ix, 'rank_score', fts_body.rank_score), 
        'semantic', json_build_object('rank_ix', semantic.rank_ix, 'cosine_similarity', semantic.cosine_similarity)
    ) as debug_rankings
from fuzzy
full outer join fts_title on fuzzy.id = fts_title.id
full outer join fts_body on coalesce(fuzzy.id, fts_title.id) = fts_body.id
full outer join semantic on coalesce(fuzzy.id, fts_title.id, fts_body.id) = semantic.id
join documents on coalesce(fuzzy.id, fts_title.id, fts_body.id, semantic.id) = documents.id
order by combined_rank desc
limit least($match_count, 30);

Корректировка длины

Если вы читали документацию к ts_rank_cd, то видели, что там есть параметр нормализации. Вот он:

Обе функции ранжирования принимают опцию целочисленной normalization , которая определяет, должна ли длина документа влиять на его ранг и как именно. Опция целочисленной нормализации управляет несколькими поведениями, поэтому она представляет собой маску: вы можете указать одно или несколько поведений с помощью | (например, 2|4).

Мы можем использовать эти опции, чтобы:

Корректировать смещение длины документа
Сбалансировать релевантность различных наборов документов
Масштабировать результаты ранжирования для последовательного представления

Значение опции	Когда использовать	Пример применения
Без нормализации (`0`)	Когда вам нужны необработанные показатели ранжирования без корректировок	Сравнение документов одинаковой длины и структуры
Логарифм нормализации длины (`1`)	Если вы хотите слегка уменьшить влияние длины документа	Документы смешанной длины, в которых не должны преобладать более длинные документы
Нормализация длины (`2`)	Когда требуется сильная нормализация по длине документа	Различные длины документов, где плотность содержания имеет большее значение, чем общее количество совпадений
Среднее гармоническое расстояние (только ts_rank_cd) (`4`)	Когда вы хотите учитывать близость терминов при ранжировании	Фразы или тесно связанные термины важны для поиска
Нормализация уникального слова (`8`)	Когда вы хотите отдать предпочтение документам с более разнообразным словарным запасом	Вознаграждение за богатство содержания, а не за повторение
Логарифм нормализации уникального слова (`16`)	Когда вы хотите слегка уменьшить влияние словарного разнообразия	Баланс между богатством словарного запаса и частотой употребления терминов
Масштабирование в диапазоне 0-1 (`32`)	Когда вам нужен единый диапазон оценок для всех запросов	Отображение оценок в виде процентов или прогресс-баров

Комбинируйте варианты с помощью побитового OR (|) для более тонкой нормализации. Например:

Используйте 2|4 для нормализации по длине и близости терминов. Используйте 1|8 для сбалансированного подхода, учитывающего как длину документа, так и разнообразие словарного запаса.

Я достиг хороших результатов, установив 0 (без нормализации) для заголовка и 1(логарифмическая длина документа) для тела. Опять же, рекомендую вам поэкспериментировать с различными вариантами, чтобы найти наилучший для вашего случая использования.

Реранжирование с помощью кросс-кодера

Многие поисковые системы основаны на двухступенчатом подходе. Это означает, что вы используете двунаправленный кодировщик для получения первых N результатов, а затем кросс-кодировщик для их ранжирования по поисковому запросу.

Двунаправленный кодировщик работает быстро, поэтому он отлично подходит для поиска по множеству документов. Кросс-кодер работает медленнее, но более производителен, что делает его отличным средством для повторного ранжирования полученных результатов.

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

Существует множество различных инструментов для этого. Один из лучших — Rerankfavicon от Cohere. Другой способ — создать свой собственный с помощью GPT от OpenAIfavicon.

Бустинг результатов для улучшения пользовательского опыта

Чтобы обеспечить еще лучший пользовательский опыт, вы можете бустить определённые столбцы в зависимости от сценария использования. Например, при поиске по базе знаний вы можете забустить результаты поиска, с которыми пользователь взаимодействовал. Также можно бустить результаты, которые были недавно изменены.

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

Предполагая, что у нас есть столбцы updated_at и updated_by в таблице документов, мы можем реализовать это следующим образом:

select
    ...
    -- Recency boost
    (1 + $recency_boost * (1 - extract(epoch from (now() - documents.updated_at)) / extract(epoch from (now() - '2020-01-01'::timestamp)))) *
    -- User boost
    case when documents.updated_by = $current_user_id then (1 + $user_boost) else 1 end
    as combined_rank,
    json_build_object(
        ...
        'recency_boost', (1 - extract(epoch from (now() - documents.updated_at)) / extract(epoch from (now() - '2020-01-01'::timestamp))),
        'user_boost', case when documents.updated_by = $current_user_id then $user_boost else 0 end
    ) as debug_rankings

Когда следует искать альтернативные решения?

Хотя Postgres — надёжный выбор для многих сценариев поиска, он не лишён ограничений. Отсутствие продвинутых алгоритмов, таких как BM25, ощущается при работе с документами различной длины. Полагаясь на TF-IDF для полнотекстового поиска, Postgres может плохо справляться с очень длинными документами и редкими терминами в больших коллекциях.

Edit: На самом деле Postgres не использует TF-IDF для полнотекстового поиска. Его встроенные функции ранжирования (ts_rank и ts_rank_cd) в первую очередь учитывают частоту терминов в отдельных документах и близость терминов, но не принимают во внимание статистику по всему корпусу. Такой подход может не справиться с очень длинными документами и не учитывает редкость терминов во всей коллекции.

Прежде чем искать альтернативные решения, обязательно проведите измерения. Есть вероятность, что оно того не стоит.

Бонус: добавление BM25

В отличие от FTS в Postgres, BM25 учитывает статистику по всему корпусу и нормализацию длины документа. Вот некоторые причины, по которым вы можете захотеть его использовать:

Лучшая обработка вариаций длины документа
Улучшение релевантности для редких терминов
Учет убывающей отдачи от частоты терминов
Отраслевой стандарт в области информационного поиска

А вот пара расширений, которые вы можете установить для работы с BM25:

Заключение

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

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

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

Дайте мне знать, если я что-то упустил! :)

Канал Sravni Tech в TG

Frontender`s Spectre

Postgres как поисковый движок