Векторные индексы

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

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

Виды векторных индексов

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

Глобальный векторный индекс

Глобальный векторный индекс по колонке embedding позволяет быстро искать приближённых ближайших соседей по всей таблице:

ALTER TABLE my_table
  ADD INDEX my_index
  GLOBAL USING vector_kmeans_tree
  ON (embedding)
  COVER (embedding, data)
  WITH (distance=cosine, vector_type="float", vector_dimension=512, overlap_clusters=3);

Пример запроса поиска к такому индексу:

PRAGMA ydb.KMeansTreeSearchTopSize = "10";

DECLARE $query_vector AS string;

$query_vector = Knn::ToBinaryStringFloat([1.0, 1.2, 0, ...]);

SELECT user, data
FROM my_table VIEW my_index
ORDER BY Knn::CosineSimilarity(embedding, $query_vector) DESC
LIMIT 10;

Обратите внимание, что:

Как векторная колонка embedding, так и параметр $query_vector должны иметь строковый тип и содержать массив чисел в простом бинарном формате.
Передавать параметр из SDK эффективнее в виде строки, сериализуя числа на стороне приложения (примеры). Альтернативно значение можно передавать из SDK как вектор чисел и конвертировать из списка функциями Knn::ToBinaryString*, но это медленнее.
Конструкция COVER (embedding, data) необязательна и предназначена для создания покрывающего индекса. Это помогает дополнительно ускорить поиск.
Поиск по векторному индексу всегда приближённый - его результаты отличаются от поиска полным перебором.
Увеличение параметра PRAGMA KMeansTreeSearchTopSize повышает качество (полноту) поиска, но снижает его скорость. Параметр задаёт число ближайших к запросу сканируемых кластеров индекса. Значение по умолчанию - 1 (минимальное качество, максимальная скорость).
Параметр overlap_clusters=3 сильно повышает качество будущего поиска при индексации, задавая число кластеров, в которые добавляется каждый вектор, но увеличивает размер индекса.
Параметры vector_type и vector_dimension можно не указывать, если таблица не пуста — они будут автоматически определены из содержимого строк.

Векторный индекс с фильтрацией

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

Чтобы создать такой индекс, укажите несколько индексных колонок. Последняя колонка должна быть векторной, остальные (колонки категорий) - любыми:

ALTER TABLE my_table
  ADD INDEX my_index
  GLOBAL USING vector_kmeans_tree
  ON (user, embedding)
  COVER (embedding, data)
  WITH (distance=cosine);

Запросы поиска к такому индексу с фильтрацией должны включать условия по колонке user:

PRAGMA ydb.KMeansTreeSearchTopSize = "10";

DECLARE $query_vector AS string;

$query_vector = Knn::ToBinaryStringFloat([1.0, 1.2, 0, ...]);

SELECT user, data
FROM my_table VIEW my_index
WHERE user = 'john'
ORDER BY Knn::CosineSimilarity(embedding, $query_vector) DESC
LIMIT 10;

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

Покрывающий векторный индекс

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

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

ALTER TABLE my_table
  ADD INDEX my_index
  GLOBAL USING vector_kmeans_tree
  ON (embedding)
  COVER (embedding, data)
  WITH (distance=cosine);

Функции расстояния

Поддерживаются следующие функции схожести или расстояния:

distance=cosine или similarity=cosine - косинусное расстояние, соответствует сортировке ORDER BY Knn::CosineDistance(...) ASC либо ORDER BY Knn::CosineSimilarity(...) DESC.
distance=manhattan - Манхэттенское расстояние (L1-метрика), соответствует ORDER BY Knn::ManhattanDistance(...) ASC.
distance=euclidean - Евклидово расстояние (L2-метрика), соответствует ORDER BY Knn::EuclideanDistance(...) ASC.
similarity=inner_product - скалярное произведение, соответствует ORDER BY Knn::InnerProductSimilarity(...) DESC.

Полный синтаксис векторных индексов

Создание векторного индекса:

При создании таблицы: CREATE TABLE.
Добавление к существующей таблице: ALTER TABLE.

Полный синтаксис запроса к векторному индексу:

VIEW VECTOR INDEX.

Алгоритм поиска

В текущей реализации доступен один тип индекса: vector_kmeans_tree.

Векторный индекс типа `vector_kmeans_tree`

Индекс vector_kmeans_tree реализует иерархическую кластеризацию данных. Структура индекса включает:

Иерархическая кластеризация:
- индекс строит несколько уровней k-means кластеров;
- на каждом уровне векторы распределяются по заданному количеству кластеров в степени уровня;
- первый уровень кластеризует весь набор данных;
- последующие уровни рекурсивно кластеризуют содержимое каждого родительского кластера.
Процесс поиска:
- поиск идет рекурсивно от первого уровня к последующим;
- при выполнении запросов индекс анализирует только наиболее перспективные кластеры;
- такое усечение пространства поиска позволяет избежать полного перебора всех векторов.
Параметры:
- levels: число уровней в дереве, задает глубину поиска (рекомендуется 1-3);
- clusters: количество кластеров в k-means, определяющее ширину поиска (рекомендуется 64-512).
- overlap_clusters: количество кластеров нижнего уровня, в которые добавляется каждый вектор (рекомендуется 3).

Внутри векторный индекс состоит из скрытых индексных таблиц вида indexImpl*Table. В запросах на выборку с использованием векторного индекса эти таблицы отображаются в статистике запросов. Подробнее об устройстве векторного индекса см. в отдельной статье Векторный индекс вида vector_kmeans_tree.

Перекрытие кластеров

Векторный индекс в YDB может добавлять каждый вектор в несколько кластеров с целью улучшения полноты и скорости поиска:

ALTER TABLE my_table
  ADD INDEX my_index
  GLOBAL USING vector_kmeans_tree
  ON (embedding)
  WITH (distance=cosine, overlap_clusters=3);

В данном примере каждый вектор будет добавлен в 3 ближайших кластера вместо 1.

Параметр overlap_clusters рекомендуется использовать практически всегда, особенно, для векторных индексов с levels > 1, так как он позволяет значительно улучшить полноту поиска даже с небольшими значениями PRAGMA KMeansTreeSearchTopSize (например, 3).

Таким образом, можно снизить параметр PRAGMA и значительно ускорить поиск при сохранении той же полноты.

Партиционирование индексных таблиц

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

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

ALTER TABLE `my_table/my_index/indexImplLevelTable`
SET AUTO_PARTITIONING_BY_LOAD ENABLED;

Или по размеру:

ALTER TABLE `my_table/my_index/indexImplLevelTable`
SET AUTO_PARTITIONING_PARTITION_SIZE_MB 100;

Аналогичную настройку можно применять и к другим индексным таблицам (indexImplPostingTable и indexImplPrefixTable), но таблица Level - самая нагруженная и при этом небольшая по размеру, поэтому для неё настройки автопартиционирования наиболее актуальны.

Использование реплик индексных таблиц

Ещё один способ ускорения поиска - использовать реплики таблиц. Для этого нужно:

Создать покрывающий индекс, чтобы в запросе поиска участвовали только индексные таблицы.

Включить реплики на всех индексных таблицах:

ALTER TABLE `my_table/my_index/indexImplLevelTable` SET READ_REPLICAS_SETTINGS 'PER_AZ:3';
ALTER TABLE `my_table/my_index/indexImplPostingTable` SET READ_REPLICAS_SETTINGS 'PER_AZ:3';

И, для индекса с фильтрацией, также:

ALTER TABLE `my_table/my_index/indexImplPrefixTable` SET READ_REPLICAS_SETTINGS 'PER_AZ:3';

Использовать режим запроса Stale Read-Only.

Обновление векторных индексов

Обновление векторных индексов имеет следующие особенности:

Кластеры не пересчитываются при обновлении

При обновлении таблицы с векторным индексом его внутренняя структура — дерево кластеров (групп схожих векторов) — не перестраивается. Новые или изменённые записи лишь распределяются по уже существующим кластерам.

Со временем это может приводить к деградации индекса, которая проявляется двумя способами:

Снижение полноты — индекс может возвращать меньше релевантных результатов, так как кластеры перестают отражать истинную структуру данных;
Снижение производительности — если кластеры становятся несбалансированными (например, один кластер содержит слишком много записей), поиск замедляется.

Степень деградации зависит от характера обновлений:

Если индекс был построен на репрезентативной выборке (например, случайные 50 % данных), а затем добавлены оставшиеся записи, структура остаётся актуальной, и деградация минимальна;
Если же изначально отсутствовали целые группы схожих векторов, кластеры могут разделять пространство некорректно, и качество поиска может существенно упасть.

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

Чтобы избежать деградации:

Не создавайте векторный индекс на пустой таблице;
Если в таблице накопилось много новых данных, постройте новый индекс и атомарно замените старый индекс на вновь построенный.

Неконсистентность при обновлении во время построения

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

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

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

Рецепты работы с векторным индексом

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

Была ли статья полезна?

Вторичные индексы

Векторный индекс вида vector_kmeans_tree