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

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

Векторные индексы особенно полезны для:

рекомендательных систем (поиск похожих товаров/пользователей;
cемантического поиска (сопоставление текстовых эмбеддингов);
поиска похожих изображений;
обнаружения аномалий (поиск выбросов);
классификационных систем (поиск ближайших размеченных примеров).

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

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

Поддерживается несколько функций расстояния/схожести: "inner_product", "cosine" (схожесть) и "cosine", "euclidean" и "manhattan" (расстояние).

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

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

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

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

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

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

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

ALTER TABLE my_table
  ADD INDEX my_index
  GLOBAL USING vector_kmeans_tree
  ON (embedding)
  WITH (distance=cosine, type="uint8", 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, type="uint8", 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, type="uint8", 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, type="uint8", dimension=512, levels=2, clusters=128);

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

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

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

Подробнее про параметры создания векторного индекса смотри в CREATE TABLE

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

Запросы к векторным индексам выполняются с использованием синтаксиса VIEW в YQL. Для индексов с префиксом укажите префиксные колонки в условии WHERE:

SELECT user, data
FROM my_table VIEW my_index
WHERE user = "..."
ORDER BY Knn::CosineSimilarity(embedding, ...) DESC
LIMIT 10;

Ограничения

В настоящее время не поддерживается:

изменение строк в индексированных таблицах;
тип битовых векторов.