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

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

Experimental feature. Learn more.
Private preview in ClickHouse Cloud

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

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

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

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

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

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

Пример​

возвращает

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

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

примечание

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

Создание индекса векторной близости​

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

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

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

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

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

Параметр 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). Массивы нуллабельных и лоу кардиналити чисел с плавающей запятой, такие как Array(Nullable(Float32)) и Array(LowCardinality(Float32)) не разрешены.
  • Индексы векторной близости должны быть созданы над отдельными столбцами.
  • Индексы векторной близости могут быть созданы над вычислительными выражениями (например, INDEX index_name arraySort(vectors) TYPE vector_similarity([...])), но такие индексы не могут быть использованы для аппроксимационного поиска соседей позднее.
  • Индексы векторной близости требуют, чтобы все массивы в подлежащем столбце содержали одно и то же количество элементов. Это проверяется при создании индекса. Чтобы как можно раньше обнаружить нарушения этого требования, пользователи могут добавить ограничение для векторного столбца, например, 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 проверяет, что предел <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 будет применять обрезку разделов.

Пример, предполагающий, что таблица распределена по диапазону год:

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 миллионов.

Пример​

возвращает

Ссылки

Блоги: