Приближенный поиск ближайших соседей с использованием индексов векторного сходства

Experimental feature. Learn more.

Private preview in ClickHouse Cloud

Поиск ближайших соседей — это задача поиска M ближайших векторов к заданному вектору в N-мерном векторном пространстве. Наиболее простой подход для решения этой задачи — это исчерпывающий (грубый) поиск, который вычисляет расстояние между опорным вектором и всеми остальными точками в векторном пространстве. Хотя этот метод гарантирует абсолютно точный результат, он обычно слишком медленный для практических приложений. В качестве альтернативы, приближенные алгоритмы используют жадные эвристики для более быстрого нахождения M ближайших векторов. Это позволяет выполнять семантический поиск изображений, песен, текста встраиваний за миллисекунды.

Блоги:

С точки зрения SQL, поиск ближайших соседей может быть выражен следующим образом:

где

DistanceFunction вычисляет расстояние между двумя векторами (например, L2Distance или cosineDistance,
vectors — это колонка типа Array(Float64) или Array(Float32), или Array(BFloat16), обычно хранящая встраивания,
reference_vector — это литерал типа Array(Float64) или Array(Float32), или Array(BFloat16), и
N — это константное целое число, ограничивающее количество возвращаемых результатов.

Запрос возвращает N ближайших точек в vectors к reference_vector.

Исчерпывающий поиск вычисляет расстояние между reference_vector и всеми векторами в vectors. Таким образом, его время выполнения линейно зависит от количества хранимых векторов. Приблизительный поиск полагается на специальные структуры данных (например, графы, случайные леса и т.д.), которые позволяют быстро находить ближайшие векторы к заданному опорному вектору (т.е. за подполевое время). ClickHouse предоставляет такую структуру данных в форме "индексов векторного сходства", типа индекса пропуска.

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

Синтаксис для создания индекса векторного сходства

примечание

Индексы USearch в настоящее время являются экспериментальными, для их использования вам сначала нужно установить SET allow_experimental_vector_similarity_index = 1.

Индекс может быть создан на колонках типа Array(Float64) или Array(Float32).

Параметры индекса:

method: В настоящее время поддерживается только hnsw.
distance_function: либо L2Distance ( Евклидово расстояние: длина линии между двумя точками в евклидова пространстве), либо cosineDistance ( косинусное расстояние: угол между двумя ненулевыми векторами).
quantization: либо f64, f32, f16, bf16, или i8 для хранения векторов с уменьшенной точностью (необязательно, по умолчанию: bf16)
hnsw_max_connections_per_layer: количество соседей на узел графа HNSW, также известное как M в документе HNSW. Необязательно, по умолчанию: 32. Значение 0 означает использование значения по умолчанию.
hnsw_candidate_list_size_for_construction: размер динамического списка кандидатов при построении графа HNSW, также известный как ef_construction в оригинальном документе HNSW. Необязательно, по умолчанию: 128. Значение 0 означает использование значения по умолчанию.

Для нормализованных данных L2Distance обычно является наилучшим выбором, в противном случае рекомендуется cosineDistance, чтобы компенсировать масштаб.

Пример:

Все массивы должны иметь одинаковую длину. Чтобы избежать ошибок, вы можете использовать CONSTRAINT, например, CONSTRAINT constraint_name_1 CHECK length(vectors) = 256. Пустые Arrays и неопределенные значения Array в операциях INSERT (т.е. значения по умолчанию) также не поддерживаются.

Индексы векторного сходства основаны на библиотеке USearch, которая реализует алгоритм HNSW, т.е. наерархический граф, где каждый узел представляет вектор, а ребра между узлами представляют сходство. Такие иерархические структуры могут быть очень эффективными при работе с большими коллекциями. Они могут извлекать 0.05% или меньше данных из общего набора данных, при этом обеспечивая 99% полноту. Это особенно полезно при работе с высокоразмерными векторами, которые дорого загружать и сравнивать. USearch также использует SIMD для ускорения вычислений расстояний на современных процессорах x86 (AVX2 и AVX-512) и ARM (NEON и SVE).

Индексы векторного сходства строятся во время вставки колонок и слияния. Известно, что алгоритм HNSW обеспечивает медленные вставки. В результате, операции INSERT и OPTIMIZE на таблицах с индексом векторного сходства будут медленнее, чем для обычных таблиц. Индексы векторного сходства предпочтительно использовать только с неизменяемыми или редко изменяемыми данными, когда количество обращений на чтение значительно превышает количество записей. Рекомендуется три дополнительных метода для ускорения создания индекса:

Создание индекса может быть параллелизовано. Максимальное количество потоков можно настроить с помощью серверной настройки max_build_vector_similarity_index_thread_pool_size.
Создание индекса на вновь вставленных частях может быть отключено с помощью установки materialize_skip_indexes_on_insert. Поиск по таким частям будет возвращаться к точному поиску, но поскольку вставленные части, как правило, малы по сравнению с общим размером таблицы, влияние на производительность будет незначительным.
ClickHouse постепенно сливает несколько частей в фоновом режиме в более крупные части. Эти новые части впоследствии могут быть снова объединены в еще более крупные части. Каждое слияние перестраивает индекс векторного сходства выходной части (как и другие индексы пропуска) каждый раз с нуля. Это потенциально приводит к неэффективной работе при создании индексов векторного сходства. Чтобы избежать этого, можно подавить создание индексов векторного сходства во время слияния, используя настройку дерева слияния materialize_skip_indexes_on_merge. Это, в сочетании с командой ALTER TABLE [...] MATERIALIZE INDEX [...], обеспечивает явный контроль над жизненным циклом индексов векторного сходства. Например, создание индекса можно отложить на периоды низкой загрузки (например, на выходные) или после значительного ввода данных.

Индексы векторного сходства поддерживают следующий тип запроса:

Чтобы выполнить поиск с использованием другого значения параметра HNSW hnsw_candidate_list_size_for_search (по умолчанию: 256), также известного как ef_search в оригинальном документе HNSW, выполните запрос SELECT с SETTINGS hnsw_candidate_list_size_for_search = <value>.

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

Ограничения: Алгоритмы приближенного поиска векторов требуют ограничения, следовательно, запросы без клаузы LIMIT не могут использовать индексы векторного сходства. Ограничение также должно быть меньше, чем значение настройки max_limit_for_ann_queries (по умолчанию: 100).

Отличия от обычных индексов пропуска. Подобно обычным индексам пропуска, индексы векторного сходства строятся по гранулам и каждый индексированный блок состоит из GRANULARITY = [N]-числа гранул ([N] = 1 по умолчанию для обычных индексов пропуска). Например, если гранулярность первичного индекса таблицы составляет 8192 (настройка index_granularity = 8192), а GRANULARITY = 2, тогда каждый индексированный блок будет содержать 16384 строки. Однако структуры данных и алгоритмы для приближенного поиска соседей по своей природе ориентированы на строки. Они хранят компактное представление набора строк и также возвращают строки для запросов поиска векторов. Это приводит к некоторым довольно неинтуитивным различиям в поведении индексов векторного сходства по сравнению с обычными индексами пропуска.

Когда пользователь определяет индекс векторного сходства на колонке, ClickHouse внутренне создает "подиндекс" векторного сходства для каждого индексированного блока. Подиндекс является "локальным" в том смысле, что он знает только о строках своего содержащего индексированного блока. В предыдущем примере, если предположить, что колонка содержит 65536 строк, мы получаем четыре индексированных блока (охватывающих восемь гранул) и подиндекс векторного сходства для каждого индексированного блока. Подиндекс теоретически может вернуть строки с N ближайшими точками в пределах своего индексированного блока непосредственно. Однако, поскольку ClickHouse загружает данные с диска в память с гранулярностью гранул, подиндексы экстраполируют соответствующие строки до гранулярности гранул. Это отличается от обычных индексов пропуска, которые пропускают данные с гранулярностью индексированных блоков.

Параметр GRANULARITY определяет, сколько подиндексов векторного сходства будет создано. Более крупные значения GRANULARITY означают меньше, но больше по размеру подиндексов векторного сходства, вплоть до точки, где у колонки (или части данных колонки) остается только один подиндекс. В этом случае подиндекс имеет "глобальный" обзор всех строк колонки и может непосредственно вернуть все гранулы колонки (части) с соответствующими строками (таких гранул не более LIMIT [N]). На втором этапе ClickHouse загрузит эти гранулы и определит фактически лучшие строки, выполняя грубое вычисление расстояния по всем строкам гранул. При малом значении GRANULARITY каждый из подиндексов возвращает до LIMIT N-числа гранул. В результате необходимо загрузить и постфильтровать больше гранул. Обратите внимание, что точность поиска в обоих случаях одинаково хороша, отличается только производительность обработки. Обычно рекомендуется использовать большое значение GRANULARITY для индексов векторного сходства и возвращаться к меньшим значениям GRANULARITY только в случае проблем, таких как чрезмерное потребление памяти структурами векторного сходства. Если для индексов векторного сходства не было указано значение GRANULARITY, значение по умолчанию составляет 100 миллионов.