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

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

Данные в таблице 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. В запросах на выборку с использованием векторного индекса, индексные таблицы будут отображены в статистике запросов.

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

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

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

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

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

Глобальный векторный индекс по колонке 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. Для индексов с префиксом укажите префиксные колонки в условии WHERE:

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;

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