IVF

В основе IVF-индекса (Inverted File Index) лежит разбиение простантсва векторов на отдельные области с использованием алгоритма кластеризации k-means. Каждый кластер представлен своим центроидом, который служит опорной точкой для векторов внутри него.

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

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

Индекс реализован на основе IVF_FLAT из библиотеки faiss.

Параметры конфигурации

При создании IVF-индекса требуется задать centroids_count — количество опорных векторов (центроидов), которые выбираются для разбиения всего множества векторов на кластеры. Каждый вектор входит в кластер ближайшего к себе центроида. При увеличении centroids_count каждый кластер будет содержать меньшее число векторов, что ускорит поиск, но замедлит построение индекса. Обязательный, диапазон значений: [1, 65536].

Рекомендуется выбирать значения в диапазоне от \(4 \sqrt{\text{N}}\) до \(16 \sqrt{\text{N}}\), где \({\text{N}}\) — количество векторов в индексе.

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

Имя параметра Описание Допустимые значения Значение по умолчанию Обязательность
centroids_count Требуемое количество центроидов [1, 65536] Отсутствует Обязательный
radius Фильтрация векторов по рангам любые float32 Отсутствует Опциональный

Пример создания индекса через GO-теги

В этом примере поверх поля VecIvf создаётся индекс с именем ivf_idx, типом ivf, размерностью вектора 1024, метрикой cosine и количеством опорных векторов 80.

// Для векторных полей тип данных должен быть слайсом (`[]float32`) или массивом(`[N]float32`).
type Item struct {
	Id      int       `reindex:"id,,pk"`
	// Для слайсов требуется явно задать тег `dimension`
	VecIvf  []float32 `reindex:"ivf_idx,ivf,centroids_count=80,metric=cosine,dimension=1024"`
}

Пример добавления индекса в уже существующий неймспейс

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

vecOpts := reindexer.FloatVectorIndexOpts {
  Metric: "cosine",
  Dimension: 1024,
  CentroidsCount: 80,
}
indexDef := reindexer.IndexDef {
  Name: "ivf_idx",
  JSONPaths: []string{"VecIvf"},
  IndexType: "ivf",
  FieldType: "float_vector",
  Config: vecOpts,
}
err := DB.AddIndex("ns_name", indexDef)
if err != nil {
  panic(err)
}

curl --location --request POST http://127.0.0.1:9088/api/v1/db/vectors_db/namespaces/test_ns/indexes' \
--header 'Content-Type: application/json' \
--data-raw '{
  "name": "ivf_idx",
  "json_paths": ["VecIvf"],
  "field_type": "float_vector",
  "index_type": "ivf",
  "config": {
    "dimension": 1024,
    "metric": "cosine",
    "centroids_count": 80
  }
}'

Параметры выборки из индекса

Имя параметра Описание Допустимые значения Значение по умолчанию Обязательность
k Максимальное количество документов, возвращаемых из индекса для последующей фильтрации >= 1 Отсутствует Обязательный при отсутствии radius
radius Фильтрация векторов по рангам (rank() < radius для L2-метрики и rank() > radius для consine- и inner product-метрик) (0,+∞) для L2;
(-∞,+∞) для inner product;
(-1,1) для cosine		 Отсутствует Обязательный при отсутствии k
nprobe Количество кластеров, которые будут просматриваться при поиске. Увеличение этого параметра позволяет получить более качественный результат (recall rate), но в то же время замедляет поиск >= 1 1 Опциональный

Примеры KNN-запросов к IVF-индексу

Получение 100 ближайших соседей (используется nprobe = 16):

SELECT * FROM test_ns WHERE KNN(ivf_idx, [2.4, 3.5, ...], k=100, nprobe=16)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100)
if err != nil {
	panic(err)
}
ivfSearchParams, err := reindexer.NewIndexIvfSearchParam(16, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").
	WithRank().
	WhereKnn("ivf_idx", []float32{2.4, 3.5, ...}, ivfSearchParams)

curl --location --request POST 'http://127.0.0.1:9088/api/v1/db/vectors_db/query' \
--header 'Content-Type: application/json' \
--data-raw '{
  "namespace": "test_ns",
  "type": "select",
  "filters": [
    {
      "op": "and",
      "cond": "knn",
      "field": "ivf_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "nprobe": 16}
    }
  ],
}'

Получение ближайших соседей в некотором радиусе (используется nprobe = 16):

SELECT * FROM test_ns WHERE KNN(ivf_idx, [2.4, 3.5, ...], nprobe=16, radius=10.11)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetRadius(10.11)
if err != nil {
	panic(err)
}
ivfSearchParams, err := reindexer.NewIndexIvfSearchParam(16, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").
	WithRank().
	WhereKnn("ivf_idx", []float32{2.4, 3.5, ...}, ivfSearchParams)

curl --location --request POST 'http://127.0.0.1:9088/api/v1/db/vectors_db/query' \
--header 'Content-Type: application/json' \
--data-raw '{
  "namespace": "test_ns",
  "type": "select",
  "filters": [
    {
      "op": "and",
      "cond": "knn",
      "field": "ivf_idx",
      "value": [2.4, 3.5, ...],
      "params": {"radius": 10.11, "nprobe": 16}
    }
  ],
}'

Получение 100 ближайших соседей в некотором радиусе (используется nprobe = 16):

SELECT * FROM test_ns WHERE KNN(ivf_idx, [2.4, 3.5, ...], k=100, nprobe=16, radius=10.11)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100).SetRadius(10.11)
if err != nil {
	panic(err)
}
ivfSearchParams, err := reindexer.NewIndexIvfSearchParam(16, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").
	WithRank().
	WhereKnn("ivf_idx", []float32{2.4, 3.5, ...}, ivfSearchParams)

curl --location --request POST 'http://127.0.0.1:9088/api/v1/db/vectors_db/query' \
--header 'Content-Type: application/json' \
--data-raw '{
  "namespace": "test_ns",
  "type": "select",
  "filters": [
    {
      "op": "and",
      "cond": "knn",
      "field": "ivf_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "radius": 10.11, "nprobe": 16}
    }
  ],
}'

Получение 100 ближайших соседей и их последующая фильтрация по условию id > 5 (также явно запрошен возврат значения поля VecIvf в выдаче и используется nprobe = 10):

SELECT *, VecIvf FROM test_ns WHERE id > 5 AND KNN(ivf_idx, [2.4, 3.5, ...], k=100, nprobe=10)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100)
if err != nil {
	panic(err)
}
ivfSearchParams, err := reindexer.NewIndexIvfSearchParam(10, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").
	Select("*", "VecIvf").
	Where("id", reindexer.GT, 5).
	WhereKnn("ivf_idx", []float32{2.4, 3.5, ...}, ivfSearchParams)

curl --location --request POST 'http://127.0.0.1:9088/api/v1/db/vectors_db/query' \
--header 'Content-Type: application/json' \
--data-raw '{
  "namespace": "test_ns",
  "type": "select",
  "select_filter": ["*", "VecIvf"],
  "filters": [
    {
      "op": "and",
      "cond": "gt",
      "field": "id",
      "value": 5
    },
    {
      "op": "and",
      "cond": "knn",
      "field": "ivf_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "nprobe": 16}
    }
  ]
}'

Получение ранга в выдаче

Пример KNN-запроса по IVF-индексу с получением 100 ближайших соседей и соответствующих им рангов/расстояний:

SELECT *, RANK() FROM test_ns WHERE KNN(vec_ivf, [2.4, 3.5, ...], k=100, nprobe=12)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100)
if err != nil {
	panic(err)
}
ivfSearchParams, err := reindexer.NewIndexIvfSearchParam(12, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").WithRank().WhereKnn("vec_ivf", []float32{2.4, 3.5, ...}, ivfSearchParams)

curl --location --request POST 'http://172.0.0.1:9088/api/v1/db/frontapi/query' \
--header 'Content-Type: application/json' \
--data-raw '{
  "namespace": "test_ns",
  "type": "select",
  "select_with_rank": true,
  "filters": [
    {
      "cond": "knn",
      "field": "vec_ivf",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "nprobe": 12}
    }
  ],
}'

Пример результирующей выдачи:

{"id": 0, "rank()": 1.0}
{"id": 7, "rank()": 0.97}
{"id": 2, "rank()": 0.8432}
{"id": 10, "rank()": 0.54}

Дополнительные action-команды

Эти команды могут быть использованы при помощи их вставки через upsert в #config-неймспейс.

Перестроение кластеров для IVF-индекса

Формат команды в JSON:

{
    "type":"action",
    "action":{
        "command":"rebuild_ivf_index",
        "namespace":"*",
        "index":"*",
        "data_part": 0.5
    }
}

Пример использования через reindexer_tool:

reindexer_tool \
--dsn cproto://127.0.0.1:6534/vectors_db \
-c '\upsert #config {"type":"action","action":{"command":"rebuild_ivf_index", "namespace":"*", "index":"*", "data_part": 0.5}}'

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

  • namespace - определяет целевой неймспейс (* - применяет команду ко всем неймспейсам);
  • index - определяет целевой индекс (* - применяет команду ко всем подходящим индексам в неймспейсе);
  • data_part - определяет долю от общего количества данных в индексе, которая будет использована для построения новых кластеров (диапазон [0.0, 1.0]). Чем больше используется данных, тем более точными получатся результирующие кластеры, однако время вычисления центроидов тоже будет больше.

Переменные среды, влияющие на работу векторных индексов

Часть дополнительных глобальных настроек IVF-индексов может быть задана через переменные среды.

Имя переменной Описание
RX_IVF_MT Ожидает числовое значение 0 или 1. Если задан 1, то для IVF-индексов используется многопоточный режим поиска. По умолчанию 0.
RX_IVF_OMP_THREADS Количество потоков OpenMP, используемое при построении кластеров для IVF-индексов. По умолчанию 8.
RX_CUSTOM_BLAS_LIB_NAME Позволяет задать пользовательское имя для библиотеки BLAS, используемой в IVF-индексах (для случаев, когда reindexer не может найти её самостоятельно).
RX_CUSTOM_LAPACK_LIB_NAME Позволяет задать пользовательское имя для библиотеки LAPACK, используемой в IVF-индексах (для случаев, когда reindexer не может найти её самостоятельно).