В новой версии YDB теперь доступны две версии векторного поиска — точный и приближённый. Приближённый поиск может работать с миллиардами векторов, если использовать векторный индекс. Такая технология есть у небольшого количества технологических компаний в мире.

Новый релиз СУБД Яндекса делает векторный поиск доступным для всех. Статья под катом написана по мотивам моего доклада на конференции HighLoad++, с которым я выступил 23 июня в Питере. В ней я расскажу про векторный поиск, индекс, RAG и о том, как эти технологии применяются в Алисе.

Как работает Retrieval-Augmented Generation (RAG)

Если большая языковая модель не была чему‑то обучена, то недостающая информация ищется в интернете или базе данных и добавляется в запрос пользователя. Так, отвечая на запросы вроде «Расскажи мне о расписании кино на завтра», модель способна обращаться к фактам о пользователе, которые она сохранила, и пользоваться информацией из внутренних баз знаний.

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

Векторы и векторные базы данных

С помощью обученной языковой модели любой текст можно превратить в массив чисел, который ML‑инженеры называют вектором. У таких векторов есть свойство, которое лежит в основе механизма RAG и векторного поиска: если модель хорошо обучена, а тексты имеют похожий смысл, то их векторы будут располагаться близко друг к другу в многомерном пространстве.

В своём докладе на HighLoad я показываю такое свойство на примере. Обычно используются векторы большой размерности, например из 1024 чисел. Но если взять очень короткие векторы всего из трёх чисел и представить эти числа как координаты в трёхмерном пространстве, то, как хорошо видно на иллюстрации, похожие смыслы (помечены разными цветами) будут группироваться рядом в трёхмерном пространстве:

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

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

Точный векторный поиск в YDB

Самая простая версия векторного поиска реализована у нас с помощью функции YQL для расчёта расстояния между двумя векторами (в примере использовано косинусное расстояние, но можно применять и другие). Эта функция получает на вход два вектора и возвращает косинусное расстояние между ними — число, которое определяет, насколько близко друг к другу расположены векторы в многомерном пространстве.

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

CREATE TABLE facts (
  id Uint64,
  text String,
  user_id Uint64,
  vector Bytes,
  PRIMARY KEY (id)
)

SELECT id, text FROM facts
WHERE user_id = 1
ORDER BY Knn::CosineDistance(vector, $TargetVector)
LIMIT 10

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

Тем не менее у точного поиска есть свои преимущества:

• штатная поддержка строгой согласованности транзакций;

• мгновенная вставка/удаление;

• поддержка максимально широкого множества реляционных операций.

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

Но с увеличением количества векторов для перебора линейно растёт время поиска. Допустим, общий объём базы по всем пользователям — 300 миллионов векторов. Мы провели тесты для YDB: если на одного пользователя приходится 1000 векторов, то поиск займёт всего 5 миллисекунд. А вот при 100 000 векторов на одного пользователя время поиска увеличится уже до 300 миллисекунд.

Приближённый векторный поиск без индекса

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

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

$BitIds = SELECT id
FROM bit_table
ORDER BY Knn::ManhattanDistance(bitEmbedding, $TargetBitEmbedding)
LIMIT 100

SELECT id, text, embedding
FROM float_table
WHERE id IN $BitIds
ORDER BY Knn::CosineDistance(floatEmbedding, $TargetFloatEmbedding)
LIMIT 10

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

Векторный индекс для приближённого поиска

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

Поэтому для YDB решили разработать алгоритм, больше всего похожий на алгоритмы FAISS IVF и ScaNN. При использовании этого алгоритма векторный индекс можно эластично располагать на множестве шардов. Всё это в масштабах Яндекса: миллиарды строк, десятки миллисекунд на поиск внутри дата‑центра. Время создания индекса и занимаемое им место должны линейно зависеть от размера таблицы.

С помощью метода K‑средних всё векторное пространство разбивается на множество кластеров, после чего для каждого такого кластера сохраняется его центроид и список всех векторов. Задача поиска в таком индексе сводится к тому, чтобы по входящему вектору найти нужный кластер и затем быстро перебрать небольшое количество векторов в нём:

Но если векторов миллиарды, то количество кластеров будет большим — и быстро найти нужный кластер не получится. Поэтому для сокращения пространства поиска мы используем алгоритм, похожий на R‑дерево: сначала для входного вектора выбирается наиболее подходящий кластер верхнего уровня, затем наиболее подходящий кластер второго уровня — и так до тех пор, пока поиск не дойдёт до кластера с небольшим количеством векторов, например 100. А их уже можно просто перебрать. Классические R‑деревья хранят в каждом узле ограничивающий прямоугольник и поэтому плохо работают с пространствами большой размерности. Наше дерево в каждом узле хранит список дочерних вершин и не имеет этих проблем:

Весь индекс реализован как две скрытые таблицы YDB. В первой из них, Level Table, хранится иерархия центроидов для быстрого поиска по кластерам. Данные в этой таблице организованы в древовидную структуру, и YDB может быстро найти идентификатор кластера нижнего уровня для вектора, по которому происходит поиск.

Вторая таблица, Posting Table, хранит информацию о векторах в каждом кластере нижнего уровня из первой таблицы. По индексу кластера в ней можно получить индексы всех векторов, которые входят в этот кластер. А сами векторы хранятся в основной таблице, Main Table, которая не является частью индекса:

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

Предварительные замеры производительности показывают, что поиск по сотням миллионов векторов выполняется за десятки миллисекунд, если серверы кластера находятся в одном дата‑центре.

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

ALTER TABLE facts
  ADD INDEX idx_vector
  GLOBAL USING vector_kmeans_tree
  ON (vector)
  WITH (
    distance=cosine,
    vector_type="float",
    vector_dimension=512,
    levels=2,
    clusters=128)

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

SELECT * FROM facts 
VIEW idx_vector
ORDER BY Knn::CosineDistance(embedding, $Target)
LIMIT $k

Фильтруемый векторный индекс

Часто поиск производится не по всем элементам, а только по тем, которые удовлетворяют дополнительному условию. Например, только по истории сообщений для конкретного пользователя. Если фильтровать до векторного поиска, то не получится воспользоваться индексом, так как его дерево построено для всех элементов. А если сначала провести векторный поиск, получить какое‑то количество элементов и отфильтровать их по пользователю, может оказаться, что элементов недостаточно, и придётся повторять векторный поиск. Поэтому нужно фильтровать внутри векторного индекса. Вот так выглядит запрос, который одновременно использует векторный индекс и фильтр по пользователям:

SELECT * FROM facts VIEW idx_vector
  WHERE user_id = $TargetUserId
  ORDER BY Knn::CosineDistance(embedding, $TargetEmbedding)
  LIMIT $k

Для таких сценариев необходимо создавать специализированный индекс со встроенной поддержкой фильтрации. Оптимальным решением стало построение отдельного векторного индекса для каждого ключа в листьях классического индекса. В результате получится столько векторных индексов, сколько User ID в таблице:

В случае YDB это третья таблица векторного индекса с именем Prefix Table. При использовании вторичного индекса YDB находит в Prefix Table все деревья из Level Table, в которых содержатся данные с указанным значением. А затем использует алгоритм, описанный выше, чтобы найти ближайшие к указанному векторы и быстро их перебрать.

Сейчас наша команда работает над добавлением векторов в векторный индекс: добавляемый вектор спускается по дереву кластеров, смещая их центроиды, после чего записывается в Posting Table. Это позволит автоматически пересчитывать индекс за константное время при добавлении и удалении элементов.

Как векторный поиск YDB используется в Алисе

Для команды AI‑ассистента Алисы важны гарантии ACID при записи в несколько таблиц, возможность выполнять JOIN и эластичное масштабирование, поэтому выбор пал на YDB. Текущая реализация использует точный векторный поиск: пока в базе данных по несколько тысяч векторов для каждого пользователя, время поиска составляет десятки миллисекунд. При этом «из коробки» поддерживается строгая согласованность транзакций, мгновенная вставка/удаление, максимально широкое множество реляционных операций. Но объёмы данных линейно растут, поэтому команда готовится перейти на векторный индекс, который позволит среди сотен тысяч фактов находить нужные за миллисекунды.

Если включена опция «Персонализированное общение», то бэкенд Алисы считает векторы для фраз с учётом контекста: от текущей фразы и предыдущего диалога. Когда пользователь делает запрос, бэкенд находит несколько наиболее подходящих по смыслу сессий с пользователем. Сессии передаются фактовому суммаризатору — отдельной модели, которая обучена суммаризировать и формулировать ключевые факты на основе фраз (сессий):

Факты от суммаризатора добавляются в запрос пользователя и передаются в итоговый суммаризатор — основную нейросеть Алисы, возвращающую ответ. Ответ передаётся пользователю как поток токенов, а когда ответ полностью сформирован, помещается в базу данных персонализации, где в будущем Алиса сможет найти его текст с помощью векторного поиска и использовать для формирования следующих ответов.

Также векторный поиск используется для «открывашек». Когда разговор заходит в тупик, Алиса находит в истории одну из интересных пользователю тем из заранее известного списка (домашние животные, хобби и т. д.). Благодаря этому диалог с голосовым помощником похож на разговор с друзьями, когда есть общий контекст общения.

Какой векторный поиск выбрать для вашего проекта

YDB предлагает на выбор три механизма векторного поиска: точный поиск, приближённый поиск без индекса и приближённый поиск с использованием векторного индекса.

• Если поиск ограничен десятками тысяч элементов, то прекрасно справится точный векторный поиск. Достаточно добавить в таблицу колонку для хранения векторов и воспользоваться функцией расстояния для сравнения элементов. Это уже доступно во всех кластерах YDB и работает в продакшн‑окружении.

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

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

База данных YDB доступна как опенсорс‑проект и как коммерческая сборка с открытым ядром. Вы можете запустить её на своих серверах или воспользоваться нашим managed‑решением в Yandex Cloud.

Мы общаемся с нашими пользователями в Telegram и на Хабре. Пишите комментарии к этой статье: мне, как разработчику базы данных, будет интересно поговорить с теми, кто базами данных пользуется!

А ещё мы проводим вебинары для разработчиков, где рассказываем про возможности YDB и отвечаем на вопросы. Ближайший вебинар — как раз по векторному поиску — пройдёт 14 августа 2025 года, записаться на него можно здесь.