Перейти к основному содержимому
Перейти к основному содержимому

Точный и аппроксимированный поиск ближайших соседей

Experimental feature. Learn more.
Private preview in ClickHouse Cloud

Проблема нахождения N ближайших точек в многомерном (векторном) пространстве для заданной точки известна как поиск ближайших соседей. Существуют два основных подхода для решения задачи поиска ближайших соседей:

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

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

Точки в векторном пространстве хранятся в колонке vectors типа массива, например, Array(Float64), Array(Float32) или Array(BFloat16). Ссылочный вектор представляет собой постоянный массив и задается как общее табличное выражение. <DistanceFunction> вычисляет расстояние между ссылочной точкой и всеми сохраненными точками. Можно использовать любую из доступных функций расстояния. N указывает, сколько соседей должно быть возвращено.

Точный поиск ближайших соседей можно выполнить, используя вышеуказанный запрос SELECT как есть. Время выполнения таких запросов, как правило, пропорционально количеству сохраненных векторов и их размерности, т.е. количеству элементов массива. Кроме того, поскольку ClickHouse выполняет брутфорс-сканирование всех векторов, время выполнения также зависит от количества потоков, задействованных в запросе (см. настройку max_threads).

Одним из распространенных способов ускорить точный поиск ближайших соседей является использование менее точного типа данных float. Например, если векторы хранятся как Array(BFloat16) вместо Array(Float32), то размер данных сокращается вдвое, и время выполнения запроса, как ожидается, также сократится вдвое. Этот метод известен как квантизация, и он может уменьшить точность результатов, несмотря на исчерпывающее сканирование всех векторов. Приемлема ли потеря точности, зависит от конкретного случая использования и обычно требует экспериментов.

Пример​

возвращает

Аппроксимированный поиск ближайших соседей

ClickHouse предоставляет специальный индекс "векторного сходства" для выполнения аппроксимированного поиска ближайших соседей.

примечание

Индексы векторного сходства в настоящее время являются экспериментальными. Чтобы включить их, сначала выполните SET allow_experimental_vector_similarity_index = 1. Если у вас возникли проблемы, пожалуйста, создайте issue на github.com/clickhouse/clickhouse/issues.

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

Индекс векторного сходства можно создать в новой таблице следующим образом:

В качестве альтернативы, чтобы добавить индекс векторного сходства в существующую таблицу:

Индексы векторного сходства являются специальными видами индексов пропуска (см. здесь и здесь). Соответственно, вышеуказанное выражение ALTER TABLE приводит к созданию индекса только для новых данных, вставленных в таблицу. Чтобы построить индекс для существующих данных, его необходимо материализовать:

Функция <distance_function> должна быть либо

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

<dimensions> ограничивает количество элементов, которые каждый массив в подлежащей колонке должен иметь (значение должно быть > 0). Если ClickHouse находит массив с другим количеством элементов во время создания индекса, индекс отклоняется и возвращается ошибка.

Параметр GRANULARITY <N> относится к размеру гранул индекса (см. здесь). Значение по умолчанию 100 миллионов должно работать вполне разумно для большинства случаев использования, но его также можно настроить. Мы рекомендуем настраивать только продвинутым пользователям, которые понимают последствия своих действий (см. ниже).

Индексы векторного сходства универсальны в том смысле, что они могут использовать различные методы аппроксимированного поиска. Фактически используемый метод задается параметром <type>. На данный момент единственным доступным методом является HNSW (научная статья), популярная и современная техника для аппроксимированного векторного поиска на основе иерархических графов сопоставления. Если HNSW используется в качестве типа, пользователи могут по желанию указать дополнительные параметры HNSW:

Эти специфические для HNSW параметры доступны:

  • quantization контролирует квантизацию векторов в графе сопоставления. Возможные значения: f64, f32, f16, bf16 или i8. Значение по умолчанию — bf16. Обратите внимание, что этот параметр не влияет на представление векторов в подлежащей колонке.
  • hnsw_max_connections_per_layer контролирует количество соседей на узел графа, также известное как параметр HNSW M. Значение по умолчанию — 32. Значение 0 означает использование значения по умолчанию.
  • hnsw_candidate_list_size_for_construction контролирует размер динамического списка кандидатов во время построения графа HNSW, также известное как параметр HNSW ef_construction. Значение по умолчанию — 128. Значение 0 означает использование значения по умолчанию.

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

Существуют также дополнительные ограничения:

  • Индексы векторного сходства можно строить только на колонках типа Array(Float32) или Array(Float64). Массивы nullable и с низкой кардинальностью, такие как Array(Nullable(Float32)) и Array(LowCardinality(Float32)), не допускаются.
  • Индексы векторного сходства должны быть построены на отдельных колонках.
  • Индексы векторного сходства могут быть созданы на вычисленных выражениях (например, INDEX index_name arraySort(vectors) TYPE vector_similarity([...])), но такие индексы не могут быть использованы для аппроксимированного поиска соседей позже.
  • Индексы векторного сходства требуют, чтобы все массивы в подлежащей колонке имели <dimension>-количество элементов. Это проверяется во время создания индекса. Чтобы как можно скорее выявить нарушения этого требования, пользователи могут добавить ограничение для векторной колонки, например, CONSTRAINT same_length CHECK length(vectors) = 256.
  • Аналогично, значения массива в подлежащей колонке не должны быть ([]) или иметь значение по умолчанию (также []).

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

примечание

Чтобы использовать индексы векторного сходства, настройка compatibility должна быть '' (значение по умолчанию), или '25.1' или новее.

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

Оптимизатор запросов ClickHouse пытается сопоставить вышеуказанный шаблон запроса и воспользоваться доступными индексами векторного сходства. Запрос может использовать индекс векторного сходства только в том случае, если функция расстояния в запросе SELECT совпадает с функцией расстояния в определении индекса.

Продвинутые пользователи могут предоставить собственное значение для настройки hnsw_candidate_list_size_for_search (также известной как параметр HNSW ef_search), чтобы настроить размер списка кандидатов во время поиска (например, SELECT [...] SETTINGS hnsw_candidate_list_size_for_search = <value>). Значение по умолчанию этой настройки — 256, что хорошо работает в большинстве случаев использования. Более высокие значения настройки означают лучшую точность за счет более медленной производительности.

Если запрос может использовать индекс векторного сходства, ClickHouse проверяет, что LIMIT <N>, указанный в запросах SELECT, находится в разумных пределах. Более конкретно, возвращается ошибка, если <N> больше значения настройки max_limit_for_ann_queries, значение по умолчанию 100. Слишком большие LIMIT могут замедлить поиски и обычно указывают на ошибку использования.

Чтобы проверить, использует ли запрос SELECT индекс векторного сходства, вы можете предварить запрос EXPLAIN indexes = 1.

Например, запрос

может вернуть

Индексы векторного сходства используются, если вывод содержит Skip и имя и тип векторного индекса (в примере, idx и vector_similarity). В этом случае индекс векторного сходства отфильтровал две из четырех гранул, т.е. 50% данных. Чем больше гранул можно отфильтровать, тем эффективнее использование индекса.

подсказка

Чтобы обеспечить использование индекса, вы можете выполнить запрос SELECT с настройкой force_data_skipping_indexes (предоставьте имя индекса в качестве значения настройки).

** Постфильтрация и Предфильтрация**

Пользователи могут по желанию указать оператор WHERE с дополнительными условиями фильтрации в запросах SELECT. В зависимости от этих условий фильтрации ClickHouse будет использовать постфильтрацию или предфильтрацию. Эти две стратегии определяют порядок, в котором фильтры оцениваются:

  • При постфильтрации индекс векторного сходства оценивается первым, после чего ClickHouse оценивает дополнительные фильтры, указанные в операторе WHERE.
  • При предфильтрации порядок оценки фильтров будет обратным.

У обеих стратегий есть разные компромиссы:

  • Постфильтрация имеет общую проблему в том, что может вернуть меньшее количество строк, чем запрашивается в операторе LIMIT <N>. Это происходит, когда хотя бы одна из строк результата, возвращенных индексом векторного сходства, не удовлетворяет дополнительные фильтры. В ClickHouse такая ситуация, к счастью, маловероятна, потому что индексы векторного сходства не возвращают строки, а блоки с тысячами строк (см. "Отличия от регулярных индексов пропуска" ниже).
  • Предфильтрация является неразрешимой проблемой. Некоторые специализированные векторные базы данных реализуют ее, но большинство баз данных, включая ClickHouse, вернутся к точному поиску ближайших соседей, т.е. к брутфорс-сканированию без индекса.

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

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

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

Пример, предполагая, что таблица партиционирована по диапазону по year:

ClickHouse проигнорирует все партиции, кроме одной для года 2025. Внутри этой партиции будет применена стратегия постфильтрации.

Если дополнительное условие фильтрации является частью первичного ключа, тогда ClickHouse всегда будет применять предфильтрацию.

Администрирование​

Размер на диске индексов векторного сходства можно получить из system.data_skipping_indices:

Пример вывода:

Настройка производительности​

Настройка создания индекса

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

Чтобы ускорить создание индексов, можно использовать следующие техники:

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

Во-вторых, чтобы ускорить INSERT-операции, пользователи могут отключить создание индексов пропуска для вновь вставленных частей, используя настройку сессии materialize_skip_indexes_on_insert. Запросы SELECT на таких частях будут возвращаться к точному поиску. Поскольку вставленные части, как правило, небольшие по сравнению с общим размером таблицы, ожидается, что воздействие на производительность будет незначительным.

В-третьих, чтобы ускорить слияния, пользователи могут отключить создание индексов пропуска для слияния частей, используя настройку сессии materialize_skip_indexes_on_merge. Это вместе с оператором ALTER TABLE [...] MATERIALIZE INDEX [...] предоставляет явный контроль над циклом жизни индексов векторного сходства. Например, создание индекса может быть отложено до момента, когда все данные будут приняты, или до периода низкой нагрузки на систему, такого как выходные.

Настройка использования индекса

Запросы SELECT требуют загрузки индексов векторного сходства в основную память для их использования. Чтобы избежать многократной загрузки одного и того же индекса векторного сходства в основную память, ClickHouse предоставляет специальный кэш в памяти для таких индексов. Чем больше этот кэш, тем меньше лишних загрузок будет происходить. Максимальный размер кэша можно настроить с помощью серверной настройки vector_similarity_index_cache_size. По умолчанию кэш может вырасти до 5 ГБ.

Текущий размер кэша отображается в system.metrics:

Кэш-попадания и промахи для запроса с некоторым идентификатором запроса можно получить из system.query_log:

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

Отличия от регулярных индексов пропуска​

Как и все обычные индексы пропуска, индексы векторного сходства строятся по гранулам, и каждый индексируемый блок состоит из 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 миллионов.

Пример​

возвращает

Ссылки

Блоги: