HNSW

HNSW — это алгоритм приблизительного поиска, основанный на слоистой графовой структуре данных, называемой иерархическим маленьким миром (hierarchical navigable small world).

HNSW обеспечивает алгоритмическую сложность log(n) как при вставках, так и при поиске. HNSW может быть параметризован, позволяя достичь компромисса между временем модификации, точностью поиска и объёмом потребляемой памяти.

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

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

Поиск работает схожим образом, но всегда начинается с точки входа в самом высоком слое, поиск продолжается по слоям, пока не дойдёт до базового слоя, где находятся ближайшие соседи. Иллюстрация процесса и подробное описание приведены в статье Understanding Recall in HNSW Search.

Реализован на основе HNSW-индекса из библиотеки hnswlib.

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

Для HNSW-индексов опционально можно задавать начальный размер start_size, который помогает избежать переаллокаций. Оптимальное значение равно размеру полностью заполненного индекса. Значение может быть настолько большим, насколько хватит ресурсов памяти. При установке ожидаемого размера индекс будет работать эффективнее, чем со значением по умолчанию. Слишком большой размер приведет к перерасходу памяти, слишком маленький размер приведет к замедлению вставок. Минимальное значение и значение по умолчанию равны 1000.

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

Имя параметра Описание Допустимые значения Значение по умолчанию Обязательность
m Количество двунаправленных связей, создаваемых для каждого нового элемента во время построения. Рекомендуемый диапазон для m — от 2 до 100. Более высокие значения m работают лучше на наборах данных с высокой внутренней размерностью и/или высоким уровнем полноты (recall), в то время как низкие значения m лучше подходят для наборов данных с низкой внутренней размерностью и/или низким уровнем полноты. Этот параметр также определяет объем потребляемой памяти алгоритма, который примерно равен 8…10 m байт на каждый сохраненный элемент. Например, для случайных векторов с размерностью dim = 4 оптимальное значение m для поиска составляет примерно 6, тогда как для высокоразмерных наборов данных (таких как векторные представления слов или качественные дескрипторы лиц) требуется более высокое значение m (примерно в диапазоне от 48 до 64) для достижения оптимальной производительности при высоком уровне полноты (recall). Диапазон значений m от 12 до 48 подходит для большинства случаев использования. При изменении значения m необходимо обновлять и другие параметры. Параметры ef и ef_construction можно приблизительно оценить, предполагая, что произведение m * ef_construction остается постоянным. [2, 128] 16 Обязательный
ef_construction Этот параметр имеет то же значение, что и ef, но используется во время вставок. Он контролирует соотношение время построения индекса/точность индекса. Увеличение ef_construction приводит к более длительному времени построения, но улучшает качество индекса. Однако в какой-то момент увеличение ef_construction перестает улучшать качество индекса. Один из способов проверить, правильно ли выбрано значение ef_construction, — измерить полноту (recall) для поиска m ближайших соседей, установив ef = ef_construction: если полнота меньше 0.9, есть возможность для улучшения. [4, 1024] 200 Обязательный
multithreading Значение 0 или 1. Если значение 0 — используется однопоточный режим вставок (потребляет меньше памяти и CPU, но вставка в индекс происходит медленнее). Если значение 1 — используется многопоточный режим вставок для транзакций, одиночные вставки всё ещё однопоточные, сам индекс при этом занимает больше памяти, но имеет высокий фактор параллелизма. Количество потоков вставки задаётся через tx_vec_insertion_threads в #config-неймспейсе, по умолчанию 4 потока. 0/1 0 Обязательный
start_size Начальный размер индекса [1000, ∞) 1000 Опциональный
radius Фильтрация векторов по рангам любые float32 Отсутствует Опциональный

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

В этом примере поверх поля VecHnsw создаётся индекс с именем hnsw_idx, типом hnsw, размерностью вектора 1024, метрикой inner_product, начальным размером 1000 и включенными многопоточными транзакциями. Используются параметры ef_construction = 200 и m = 16.

// Для векторных полей тип данных должен быть слайсом (`[]float32`) или массивом(`[N]float32`).
type Item struct {
	Id      int       `reindex:"id,,pk"`
	// Для слайсов требуется явно задать тег `dimension`.
	VecHnsw []float32 `reindex:"hnsw_idx,hnsw,m=16,ef_construction=200,dimension=1024,metric=inner_product,multithreading=1,start_size=1000"`
}

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

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

vecOpts := reindexer.FloatVectorIndexOpts {
	Metric: "l2",
	Dimension: 1024,
	M: 16, 
	EfConstruction: 200,
	MultithreadingMode: 1,
}
indexDef := reindexer.IndexDef {
	Name: "hnsw_idx",
	JSONPaths: []string{"VecHnsw"},
	IndexType: "hnsw",
	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": "hnsw_idx",
  "json_paths": ["VecHnsw"],
  "field_type": "float_vector",
  "index_type": "hnsw",
  "config": {
    "dimension": 1024,
    "metric": "inner_product",
    "start_size": 1000,
    "m": 16,
    "ef_construction": 20,
    "multithreading": 1
  }
}'

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

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

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

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

SELECT * FROM test_ns WHERE KNN(hnsw_idx, [2.4, 3.5, ...], k=100, ef=150)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100)
if err != nil {
	panic(err)
}
hnswSearchParams, err := reindexer.NewIndexHnswSearchParam(150, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").WhereKnn("hnsw_idx", []float32{2.4, 3.5, ...}, hnswSearchParams)

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": [
    {
      "cond": "knn",
      "field": "hnsw_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "ef": 150}
    }
  ],
}'

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

SELECT * FROM test_ns WHERE KNN(hnsw_idx, [2.4, 3.5, ...], ef=150, radius=10.11)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetRadius(10.11)
if err != nil {
	panic(err)
}
hnswSearchParams, err := reindexer.NewIndexHnswSearchParam(150, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").WhereKnn("hnsw_idx", []float32{2.4, 3.5, ...}, hnswSearchParams)

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": [
    {
      "cond": "knn",
      "field": "hnsw_idx",
      "value": [2.4, 3.5, ...],
      "params": {"radius": 10.11, "ef": 150}
    }
  ],
}'

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

SELECT * FROM test_ns WHERE KNN(hnsw_idx, [2.4, 3.5, ...], k=100, ef=150, radius=10.11)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100).SetRadius(10.11)
if err != nil {
	panic(err)
}
hnswSearchParams, err := reindexer.NewIndexHnswSearchParam(150, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").WhereKnn("hnsw_idx", []float32{2.4, 3.5, ...}, hnswSearchParams)

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": [
    {
      "cond": "knn",
      "field": "hnsw_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "radius": 10.11, "ef": 150}
    }
  ],
}'

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

SELECT *, VecHnsw FROM test_ns WHERE id > 5 AND KNN(hnsw_idx, [2.4, 3.5, ...], k=100, ef=200)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(100)
if err != nil {
	panic(err)
}
hnswSearchParams, err := reindexer.NewIndexHnswSearchParam(200, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").
	Select("*", "VecHnsw").
	Where("id", reindexer.GT, 5).
	WhereKnn("hnsw_idx", []float32{2.4, 3.5, ...}, hnswSearchParams)

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": ["*", "VecHnsw"],
  "filters": [
    {
      "op": "and",
      "cond": "gt",
      "field": "id",
      "value": 5
    },
    {
      "op": "and",
      "cond": "knn",
      "field": "hnsw_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 100, "ef": 200}
    }
  ]
}'

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

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

SELECT *, RANK() FROM test_ns WHERE KNN(hnsw_idx, [2.4, 3.5, ...], k=200, ef=300)

knnBaseSearchParams := reindexer.BaseKnnSearchParam{}.SetK(200)
if err != nil {
	panic(err)
}
hnswSearchParams, err := reindexer.NewIndexHnswSearchParam(300, knnBaseSearchParams)
if err != nil {
	panic(err)
}
db.Query("test_ns").WithRank().WhereKnn("hnsw_idx", []float32{2.4, 3.5, ...}, hnswSearchParams)

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_with_rank": true,
  "filters": [
    {
      "op": "and",
      "cond": "knn",
      "field": "hnsw_idx",
      "value": [2.4, 3.5, ...],
      "params": {"k": 200, "ef": 300}
    }
  ],
}'

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

{"id": 0, "rank()": 21.01}
{"id": 7, "rank()": 19.34}
{"id": 2, "rank()": 11.2}