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

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

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

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

Векторные индексы в YDB решают задачу поиска ближайших соседей с использованием функций схожести или расстояния. Поддерживается несколько функций расстояния/схожести: "inner_product", "cosine" (схожесть) и "cosine", "euclidean", "manhattan" (расстояние).

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

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

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

1. Иерархическая кластеризация:

   • индекс строит несколько уровней k-means кластеров;
   • на каждом уровне векторы распределяются по заданному количеству кластеров в степени уровня;
   • первый уровень кластеризует весь набор данных;
   • последующие уровни рекурсивно кластеризуют содержимое каждого родительского кластера.

2. Процесс поиска:

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

3. Параметры:

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

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

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

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

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

Ниже приведены примеры создания векторного индекса различных типов.

Базовый векторный индекс

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

ALTER TABLE my_table
  ADD INDEX my_index
  GLOBAL USING vector_kmeans_tree
  ON (embedding)
  WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128);

Векторный индекс с покрывающими колонками

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

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

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

Векторный индекс с фильтрацией, позволяющий фильтровать по колонке user в момент выполнения векторного поиска:

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

Векторный индекс с фильтрацией и покрывающими колонками

Векторный индекс с фильтрацией и покрывающими колонками:

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

Создание векторных индексов

Векторные индексы можно создавать:

• при создании таблицы с помощью YQL-оператора CREATE TABLE;
• добавлять к существующей таблице с помощью YQL-оператора ALTER TABLE.

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

Запросы к векторным индексам выполняются с использованием синтаксиса VIEW в YQL:

DECLARE $query_vector AS List<Uint8>;

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

Для индексов с фильтрацией укажите соответствующие колонки в условии WHERE:

DECLARE $query_vector AS List<Uint8>;

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

Подробнее о выполнении запросов SELECT с использованием векторных индексов можно прочитать в разделе VIEW VECTOR INDEX.

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

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

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

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

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

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

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

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

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

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

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

• YDB CLI & YQL
• YDB SDK: Python, C++