Exact и Approximate Nearest Neighbor Search
Задача нахождения N ближайших точек в многомерном (векторном) пространстве для данной точки известна как поиск ближайших соседей. Существует два основных подхода для решения задачи поиска ближайших соседей:
- Поиск ближайших соседей с точным результатом вычисляет расстояние между данной точкой и всеми точками в векторном пространстве. Это обеспечивает максимальную точность, т.е. гарантировано, что возвращенные точки являются фактическими ближайшими соседями. Поскольку все векторное пространство исследуется исчерпывающе, точный поиск ближайших соседей может быть слишком медленным для практического использования.
- Поиск ближайших соседей с приближением относится к группе техник (например, специальные структуры данных, такие как графы и случайные леса), которые вычисляют результаты намного быстрее, чем точный поиск ближайших соседей. Точность результатов обычно "достаточная" для практического использования. Многие приближенные методы предоставляют параметры для настройки компромисса между точностью результата и временем поиска.
Поиск ближайших соседей (точный или приближенный) можно записать в SQL следующим образом:
Точки в векторном пространстве хранятся в колонке vectors типа массива, например, Array(Float64), Array(Float32) или Array(BFloat16).
Эталонный вектор является постоянным массивом и указывается в качестве общего табличного выражения.
<DistanceFunction> вычисляет расстояние между эталонной точкой и всеми хранящимися точками.
Можно использовать любую доступную функцию расстояния для этого.
<N> указывает, сколько соседей должно быть возвращено.
Exact Nearest Neighbor Search
Поиск ближайших соседей с точным результатом можно выполнить с помощью указанного выше запроса SELECT. Время выполнения таких запросов, как правило, пропорционально количеству хранящихся векторов и их размерности, т.е. количеству элементов массива. Кроме того, поскольку ClickHouse выполняет полное сканирование всех векторов, время выполнения также зависит от количества потоков, используемых запросом (см. настройку max_threads).
Один из распространенных подходов для ускорения точного поиска ближайших соседей заключается в использовании типа данных с низкой точностью float.
Например, если векторы хранятся как Array(BFloat16) вместо Array(Float32), то размер данных уменьшается вдвое, и время выполнения запросов ожидается также уменьшится вдвое.
Этот метод известен как квантизация, и он может снизить точность результатов, несмотря на полное сканирование всех векторов.
Приемлемость потерь в точности зависит от конкретного случая и обычно требует экспериментирования.
Пример
возвращает
Approximate Nearest Neighbor Search
ClickHouse предоставляет специальный индекс "сходства векторов" для выполнения приближенного поиска ближайших соседей.
Индексы сходства векторов в настоящее время являются экспериментальными.
Чтобы включить их, сначала выполните команду SET allow_experimental_vector_similarity_index = 1.
Если возникнут проблемы, пожалуйста, откройте проблему в репозитории ClickHouse.
Создание индекса сходства векторов
Индекс сходства векторов можно создать в новой таблице следующим образом:
В качестве альтернативы, чтобы добавить индекс сходства векторов к существующей таблице:
Индексы сходства векторов являются особым видом индексов пропуска (см. здесь и здесь).
Таким образом, вышеуказанная команда ALTER TABLE вызывает построение индекса только для будущих новых данных, вставляемых в таблицу.
Чтобы построить индекс и для существующих данных, необходимо его материализовать:
Функция <distance_function> должна быть
L2Distance, евклидово расстояние, представляющее длину линии между двумя точками в евклидовом пространстве, илиcosineDistance, косинусное расстояние, представляющее угол между двумя ненулевыми векторами.
Для нормализованных данных L2Distance обычно является наилучшим выбором, в противном случае рекомендуется cosineDistance для компенсации масштаба.
<dimensions> указывает кардинальность массива (количество элементов) в базовой колонке.
Если ClickHouse находит массив с другой кардинальностью во время создания индекса, индекс отвергается и возвращается ошибка.
Необязательный параметр GRANULARITY <N> относится к размеру гранул индекса (см. здесь).
Значение по умолчанию 100 миллионов должно достаточно хорошо работать для большинства случаев, но его также можно настроить.
Рекомендуется настраивать только опытным пользователям, которые понимают последствия своих действий (см. ниже).
Индексы сходства векторов являются универсальными в том смысле, что они могут использовать различные методы приближенного поиска.
Используемый метод уточняется параметром <type>.
На данный момент единственным доступным методом является HNSW (академическая статья), популярная и современная техника для приближенного векторного поиска на основе иерархических графов близости.
Если HNSW используется в качестве типа, пользователи могут дополнительно указать специальные параметры HNSW:
Доступны следующие специальные параметры HNSW:
<quantization>управляет квантизацией векторов в графе близости. Возможные значения:f64,f32,f16,bf16илиi8. Значение по умолчаниюbf16. Обратите внимание, что этот параметр не влияет на представление векторов в базовой колонке.<hnsw_max_connections_per_layer>управляет количеством соседей для каждой узловой графа, также известным как гиперпараметр HNSWM. Значение по умолчанию32. Значение0обозначает использование значения по умолчанию.<hnsw_candidate_list_size_for_construction>управляет размером динамического списка кандидатов во время построения графа HNSW, также известным как гиперпараметр HNSWef_construction. Значение по умолчанию128. Значение0означает использование значения по умолчанию.
Значения по умолчанию всех специальных параметров HNSW работают достаточно хорошо в большинстве случаев использования. Поэтому мы не рекомендуем настраивать специальные параметры HNSW.
Применяются дополнительные ограничения:
- Индексы сходства векторов могут строиться только на колонках типа Array(Float32), Array(Float64) или Array(BFloat16). Массивы с допускающими нулями и низкой кардинальностью, такие как
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_vector_search_queries со значением по умолчанию 100.
Слишком большие значения LIMIT могут замедлить поиск и обычно указывают на ошибку использования.
Чтобы проверить, использует ли SELECT-запрос индекс сходства векторов, вы можете префиксировать запрос EXPLAIN indexes = 1.
В качестве примера запрос
может вернуть
В этом примере 1 миллион векторов в множестве данных dbpedia, каждый размерностью 1536, хранится в 575 гранулах, т.е. 1.7k строк на гранулу. Запрос запрашивает 10 соседей, и индекс сходства векторов находит этих 10 соседей в 10 отдельных гранулах. Эти 10 гранул будут прочитаны во время выполнения запроса.
Индексы сходства векторов используются, если выходные данные содержат Skip и имя и тип векторного индекса (в примере idx и vector_similarity).
В этом случае индекс сходства векторов исключил две из четырех гранул, т.е. 50% данных.
Чем больше гранул может быть исключено, тем эффективнее использование индекса.
Чтобы обеспечить использование индекса, вы можете выполнить SELECT-запрос с настройкой force_data_skipping_indexes (укажите имя индекса в качестве значения настройки).
Пост-фильтрация и Пред-фильтрация
Пользователи могут дополнительно указать клаузу WHERE с дополнительными фильтрами для SELECT-запроса.
ClickHouse будет оценивать эти условия фильтрации, используя стратегию пост-фильтрации или пред-фильтрации.
Коротко говоря, обе стратегии определяют порядок, в котором фильтры оцениваются:
- Пост-фильтрация означает, что индекс сходства векторов оценивается первым, после чего ClickHouse оценивает дополнительные фильтры, указанные в клаузе
WHERE. - Пред-фильтрация означает, что порядок оценки фильтров противоположен.
Стратегии имеют разные компромиссы:
- Пост-фильтрация имеет общую проблему, заключающуюся в том, что она может вернуть менее количества строк, запрашиваемых в клаузе
LIMIT <N>. Эта ситуация возникает, когда одна или несколько результирующих строк, возвращенных индексом сходства векторов, не удовлетворяют дополнительные фильтры. - Пред-фильтрация является общей неразрешимой проблемой. Некоторые специализированные векторные базы данных предлагают алгоритмы пред-фильтрации, но большинство реляционных баз данных (включая ClickHouse) будут возвращаться к точному поиску соседей, т.е. полному сканированию без индекса.
Какая стратегия используется, зависит от условия фильтрации.
Дополнительные фильтры являются частью ключа партиции
Если дополнительное условие фильтрации является частью ключа партиции, ClickHouse применит отсекание партиции.
В качестве примера, таблица разбиена по диапазону по колонке year, и выполняется следующий запрос:
ClickHouse отсечет все партиции, кроме 2025.
Дополнительные фильтры не могут быть оценены с использованием индексов
Если дополнительные условия фильтрации не могут быть оценены с использованием индексов (индекс первичного ключа, индекс пропуска), ClickHouse применяет пост-фильтрацию.
Дополнительные фильтры могут быть оценены с использованием индекса первичного ключа
Если дополнительные условия фильтрации могут быть оценены с использованием индекса первичного ключа (т.е. они формируют префикс первичного ключа), и
- условие фильтрации исключает хотя бы одну строку в пределах части, ClickHouse вернется к пред-фильтрации для "выживших" диапазонов в пределах части,
- условие фильтрации не исключает строк в пределах части, ClickHouse выполнит пост-фильтрацию для части.
На практике последний случай довольно маловероятен.
Дополнительные фильтры могут быть оценены с использованием индекса пропуска
Если дополнительные условия фильтрации могут быть оценены с использованием индексов пропуска (индекс minmax, индекс set и т.д.), Clickhouse выполняет пост-фильтрацию. В таких случаях сначала оценивается индекс сходства векторов, поскольку ожидается, что он удалит больше всего строк по сравнению с другими индексами пропуска.
Для более тонкого контроля над пост-фильтрацией и пред-фильтрацией могут быть использованы две настройки:
Настройка vector_search_filter_strategy (по умолчанию: auto, которая реализует вышеуказанные эвристики) может быть установлена в prefilter.
Это полезно, чтобы заставить пред-фильтрацию в случаях, когда дополнительные условия фильтрации являются крайне селективными.
В качестве примера, следующий запрос может извлечь выгоду от пред-фильтрации:
Предположим, что лишь небольшое количество книг стоит менее 2 долларов, пост-фильтрация может вернуть ноль строк, потому что 10 лучших соответствий, возвращённых индексом векторов, могут все иметь цену выше 2 долларов.
Принуждая пред-фильтрацию (добавив SETTINGS vector_search_filter_strategy = 'prefilter' к запросу), ClickHouse сначала находит все книги с ценой менее 2 долларов, а затем выполняет полное векторное исследование найденных книг.
В качестве альтернативного подхода для решения вышеуказанной проблемы, настройка vector_search_postfilter_multiplier (по умолчанию: 1.0) может быть настроена на значение больше 1.0 (например, 2.0).
Количество ближайших соседей, извлекаемых из индекса векторов, умножается на значение настройки, а затем дополнительные фильтры применяются к этим строкам, чтобы вернуть количество строк, указанных в LIMIT.
В качестве примера, мы можем снова выполнить запрос, но с множителем 3.0:
ClickHouse извлечет 3.0 x 10 = 30 ближайших соседей из индекса векторов в каждой части, а затем оценит дополнительные фильтры.
Только десять ближайших соседей будут возвращены.
Отметим, что настройка vector_search_postfilter_multiplier может смягчить эту проблему, но в крайних случаях (очень селективное условие WHERE) все еще возможно, что возвращается менее N запрашиваемых строк.
Настройка производительности
Настройка сжатия
Практически во всех случаях использования векторы в базовой колонке являются плотными и плохо сжимаются.
В результате сжатие замедляет вставки и чтения в/из векторной колонки.
Поэтому мы рекомендуем отключить сжатие.
Чтобы сделать это, укажите CODEC(NONE) для векторной колонки следующим образом:
Настройка создания индекса
Жизненный цикл индексов сходства векторов привязан к жизненному циклу частей. Другими словами, каждый раз, когда создается новая часть с определенным индексом сходства векторов, индекс создается также. Это обычно происходит при вставках или во время слияний. К сожалению, 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:
Для производственных случаев мы рекомендуем установить размер кэша достаточным образом, чтобы все индексы векторов оставались в памяти все время.
Администрирование и мониторинг
Размер индекса сходства векторов на диске можно получить из system.data_skipping_indices:
Пример вывода:
Отличия от обычных индексов пропуска
Как и все обычные индексы пропуска, индексы сходства векторов создаются по гранулам, и каждый индексируемый блок состоит из 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 миллионов.
Пример
возвращает
Ссылки
Блоги:
