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

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

Данные в таблице 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, levels=2, clusters=128, 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 сильно повышает качество будущего поиска при индексации, задавая число кластеров, в которые добавляется каждый вектор, но увеличивает размер индекса.

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

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

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

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

Запросы поиска к такому индексу с фильтрацией должны включать условия по колонке 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, vector_type="float", vector_dimension=512, levels=2, clusters=128, overlap_clusters=3);

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

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

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, vector_type="float", vector_dimension=512, levels=2, clusters=128, 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