Точный и аппроксимационный поиск ближайших соседей
Задача нахождения 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.
Если у вас возникнут проблемы, пожалуйста, откройте задачу на github.com/clickhouse/clickhouse/issues.
Создание индекса векторного сходства
Индекс векторного сходства можно создать в новой таблице следующим образом:
Или можно добавить индекс векторного сходства в существующую таблицу:
Индексы векторного сходства являются специальным видом индексов пропуска данных (см. здесь и здесь).
Соответственно, приведённое выше выражение ALTER TABLE вызывает построение индекса только для новых данных, вставляемых в таблицу в будущем.
Чтобы построить индекс и для существующих данных, его необходимо материализовать:
Функция <distance_function> должна быть либо
L2Distance, евклидово расстояние, представляющее собой длину линии между двумя точками в евклидовом пространстве, либоcosineDistance, косинусное расстояние, представляющее угол между двумя ненулевыми векторами.
Для нормализованных данных обычно лучше подходит L2Distance, в противном случае рекомендуется использовать cosineDistance для компенсации масштаба.
Параметр 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(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 проверяет, находится ли 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 будет использовать отбор разделов (partition pruning).
Пример, предполагая, что таблица разделена по 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:
Попадания и промахи кэша для запроса с некоторым id запроса можно получить из system.query_log:
Отличия от обычных индексов пропуска
Как и все обычные индексы пропуска, индексы векторного сходства строятся по гранулам и каждый индексированный блок состоит из GRANULARITY = [N]-многих гранул ([N] по умолчанию для обычных индексов пропуска).
Например, если основная гранулярность индекса таблицы составляет 8192 (настройка index_granularity = 8192), а GRANULARITY = 2, то каждый индексированный блок будет содержать 16384 строки.
Однако структуры данных и алгоритмы для аппроксимационного поиска соседей по своей сути ориентированы на строки.
Они хранят компактное представление набора строк и также возвращают строки для запросов векторного поиска.
Это вызывает некоторые довольно неинтуитивные различия в поведении индексов векторного сходства по сравнению с обычными индексами пропуска данных.
Когда пользователь определяет индекс векторного сходства для столбца, ClickHouse внутренне создаёт векторный индекс "суб-индекс" для каждого индексированного блока. Суб-индекс является "локальным" в том смысле, что он знает только о строках своего содержащего индексного блока. В предыдущем примере и при условии, что столбец имеет 65536 строк, мы получаем четыре индексных блока (охватывающих восемь гранул) и векторный суб-индекс для каждого индексного блока. Суб-индекс теоретически способен возвращать строки для N ближайших точек в пределах своего индексного блока напрямую. Однако поскольку ClickHouse загружает данные с диска в память с точностью до гранул, суб-индексы экстраполируют соответствующие строки до уровня гранулярности. Это отличается от обычных индексов пропуска данных, которые пропускают данные с точностью до индексных блоков.
Параметр GRANULARITY определяет, сколько векторных суб-индексов создаётся.
Более высокие значения GRANULARITY означают меньше, но больше векторных суб-индексов, вплоть до точки, где столбец (или часть данных столбца) имеет только один суб-индекс.
В этом случае суб-индекс имеет "глобальный" обзор всех строк столбца и может напрямую возвращать все гранулы столбца (части) с соответствующими строками (таких гранул может быть максимум LIMIT [N]).
Во втором шаге ClickHouse загрузит эти гранулы и определит наилучшие строки, выполняя полное расстояниевычисление для всех строк гранул.
С малыми значениями GRANULARITY каждый из суб-индексов возвращает до LIMIT N гранул.
В результате больше гранул нужно будет загрузить и пост-фильтровать.
Заметьте, что точность поиска в обоих случаях одинакова, только производительность обработки отличается.
Рекомендуется использовать большие значения GRANULARITY для индексов векторного сходства и возвращаться к меньшим значениям GRANULARITY только в случае проблем, таких как чрезмерное потребление памяти векторными структурами.
Если для индексов векторного сходства не был указан параметр GRANULARITY, значение по умолчанию составляет 100 миллионов.
Пример
возвращает
Ссылки
Блоги: