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

Человек отбрасывает нерелевантные варианты за счёт здравого смысла, компьютер считает расстояния между векторами

Всем привет! Меня зовут Диана Бутько, я студентка 3 курса, изучаю информационные системы и программирование в колледже КМПО РАНХиГС. В InfoWatch я пришла на практику, и одной из моих задач стал сравнительный анализ различных методов поиска похожих векторов. Это один из ключевых аспектов машинного обучения и анализа данных, используемых в рекомендательных системах, кластеризации, семантическом поиске и других областях. Но чем больше объем данных, тем менее эффективными становятся традиционные методы: полный перебор векторов требует больших вычислительных ресурсов, а в других алгоритмах порой необходимо балансировать между точностью и скоростью поиска.

В этой статье я сравниваю пять методов поиска похожих векторов:

• полный перебор по евклидову расстоянию с реализацией в Python;

• FAISS с индексами IndexFlatL2 (полный перебор, евклидово расстояние) и IndexIVFFlat (сегментирование по ячейкам, евклидово расстояние);

• векторный поиск в ClickHouse с индексом HNSW и метриками расстояния L2Distance (евклидово расстояние) и cosineDistance (косинусное сходство).

Методы оценивались по двум ключевым параметрам: время выполнения поиска и потребление памяти на наборе данных из 20 тыс. векторов размерностью 512.

Кому будет полезно?

• Data Scientists и ML‑инженеры, работающие с векторными представлениями (например, эмбеддингами текстов или изображений);

• разработчики аналитических систем, которым важно ускорять поиск по большим массивам векторов;

• архитекторы систем, выбирающие между in‑memory (FAISS) и database‑based (ClickHouse) решениями.

Под катом — разбор методов, сравнительные тесты и рекомендации по выбору оптимального подхода. Все скрипты, которые использовались в исследовании, доступны в репозитории GitHub.

Технический дисклеймер от коллег 

Прежде чем передать слово автору статьи, приведем небольшой комментарий от Зайнуллы Жумаева, коллеги, который выступил в роли технического редактора статьи.

Когда впервые увидел отчёт Дианы по практике, из которого выросла статья на Хабр, моей первой мыслью было: «Это в каких колледжах учатся такие продвинутые студенты‑мутанты?» Мутанты в хорошем смысле. Работу в InfoWatch совмещаю с преподаванием и знаю, что далеко не все студенты могут сделать работу подобного уровня за месяц. При более детальном изучении стало понятно, что это работа всё‑таки уровня студента, пусть и продвинутого. Но нам было важно поделиться результатами исследования, которое сделала Диана, сразу по нескольким причинам. Во‑первых, рассматривается новая функциональность ClickHouse, о которой пока многие не знают. А во‑вторых, хотелось показать, какого уровня исследования проводят наши практиканты «как есть». И от души ими погордиться, конечно:) Решения задач могут быть не безупречны с технической точки зрения, но в данном случае мы считаем, что практика удалась на отлично, а ее результаты будут полезны сообществу.

Если бы исследование проводилось не в рамках ограниченного времени студенческой практики, то его можно было бы провести более строго.

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

Например, важно определиться со следующими вопросами:

• в задаче используются плотные вектора малой размерности (до нескольких сотен, когда FAISS ещё подходит) или разреженные вектора большой размерности (несколько сотен тысяч как вектора TF‑IDF в некоторых задачах лингвистики)?

• каково соотношение между количеством операций обновления векторов и поиском? Если вектора меняются довольно часто, а искать соседей необходимо редко, то методы, требующие предварительной индексации, могут быть не самыми подходящими;

• подойдёт вероятностный поиск или нужна гарантия обнаружения ближайших соседей? Если вероятностный поиск подходит, то какое нижнее ограничение на вероятность обнаружения ближайшего соседа?

Также более правильно было бы варьировать только один из параметров (алгоритм, язык программирования и т. д.) при фиксации всех остальных. Например, для Python также есть библиотека‑обёртка с реализацией HNSW на C++, и можно было бы сравнить разные реализации этого алгоритма индексации. Кроме того, и в самом методе HNSW есть варьируемые параметры, а значит при сравнении реализаций необходимо было бы обеспечить равенство варьируемых параметров.

Самописный метод на Python тоже мог бы работать быстрее. Как минимум, можно было бы не делать сортировку для поиска k ближайших соседей, а найти их за один обход списка векторов, что снизило бы сложность алгоритма.

К измерениям помимо времени выполнения и потребления оперативной памяти можно было бы добавить, например:

• время, затраченное на построение индекса;

• нагрузку на CPU;

• информацию по нагрузке на жёсткий диск;

• измерить не только общее потребление ресурсов, но их распределение между Clickhouse и Python;

Однако, как любят писать в рецензиях на научные статьи «указанные недостатки не снижают практической ценности работы». Итак, передаем слово автору статьи.

---

Подготовка к сравнению методов: что необходимо

Изначально работа начиналась в старой версии ClickHouse (22.1.3.7), но в ходе работы стало понятно, что она не поддерживает необходимый функционал, а именно экспериментальную функцию из новой версии ClickHouse (24.12.3.47). Экспериментальная функция (Approximate Nearest Neighbor Search with Vector Similarity Indexes) позволяет создавать специальные индексы для работы с векторами и для приближенного поиска ближайшего соседа с использованием векторных индексов сходства. Используя следующую команду, можно поднять сервер ClickHouse через Docker:

docker run -d --name some-clickhouse-server --ulimit nofile=262144:262144 clickhouse

После развертывания сервера для удобства взаимодействия с базой данных и выполнения SQL‑запросов можно использовать DBeaver.

Первым шагом стало создание python‑скрипта, автоматизирующего процесс создания базы данных и таблицы в ClickHouse. Этот скрипт был направлен на создание необходимой структуры для хранения векторов и идентификаторов.

SQL‑запрос создания таблицы:

CREATE TABLE IF NOT EXISTS db_master.element (
   doc_id UUID,
   centroid Array(Float64)
) ENGINE = MergeTree()
ORDER BY doc_id

Чтобы задействовать экспериментальные функции индексов, необходимо выполнить в клиенте ClickHouse (clickhouse‑client) команду:

SET allow_experimental_vector_similarity_index = 1 

Это обязательная команда, без нее создать индекс невозможно, поскольку эта настройка позволяет использовать экспериментальные функции, которые еще не являются частью стандартной функциональности базы данных. Для поиска похожих векторов можно добавить индексы в таблицу с помощью следующих SQL‑запросов:

ALTER TABLE db_master.element
   ADD INDEX idx_l2 centroid
   TYPE vector_similarity('hnsw', 'L2Distance')
   GRANULARITY 1;


ALTER TABLE db_master.element
   ADD INDEX idx_cosine centroid
   TYPE vector_similarity('hnsw', 'cosineDistance')
   GRANULARITY 1;

Второй этап включал разработку скрипта для создания тестовых данных и их сохранения в JSON‑файлах. В этом скрипте реализована функция, которая создает заданное количество UUID и случайных векторов с плавающей точкой, каждый из которых размерностью 512. UUID при этом необязательный элемент, можно использовать, например счетчик. Часть python‑кода, отвечающая за генерацию:

existing_uuids = set()
elements = []


for _ in range(self.count):
   while True:
       id_uuid = str(uuid.uuid4())
       if id_uuid not in existing_uuids:
           existing_uuids.add(id_uuid)
           break


   vector = np.random.uniform(
       low=self.low, high=self.high, size=self.size
   ).tolist()


   elements.append({"id": id_uuid, "vector": vector})

Данные сохранялись в JSON — стандартном формате, удобном как для обработки, так и для загрузки в ClickHouse.

Третий скрипт был разработан для загрузки данных из JSON‑файла в базу данных ClickHouse. Данные, сгенерированные вторым скриптом и сохранённые в JSON‑файл, извлекались из него и загружались в таблицу ClickHouse. Ниже представлена часть Python‑кода, отвечающая за извлечение данных и их подготовку к загрузке:

with open(file_input, "r") as file:
   elements = json.load(file)
   for element in elements:
       doc_id = element["id"]
       centroid = element["vector"]
       data_to_load.append((doc_id, centroid))

После загрузки данных в ClickHouse можно переходить к сравнению различных методов для поиска похожих векторов. Дальше подробно опишу каждый из методов, которые мы рассматривали — всего их пять. Для удобства разбила их на два раздела — методы с индексацией и без индексации (с полным перебором).

Сравнение методов поиска

1. Методы с индексацией

Внимательный читатель мог заметить, что дерево на картинке несбалансированное, индекс с таким деревом неоптимален. HNSW не такой, он старается строить сбалансированные деревья

1.1. С метрикой L2 (евклидово расстояние)

Сравниваем животных только по двум признакам, при большем количестве признаков всё то же самое, только N‑мерное пространство нарисовать сложнее

Этот метод выполняет SQL‑запрос в ClickHouse, используя функцию L2Distance. Для этого способа в таблице был реализован индекс «idx_l2», в основе которого лежит функция дистанции, считающая евклидово расстояние (длина прямой между двумя точками в евклидовом пространстве).

Плюсы:

• хорошо масштабируется при увеличении количества данных;

• высокая скорость выполнения.

Минусы:

• функциональность зависит от возможностей ClickHouse и его встроенных функций;

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

Ниже пример SQL‑запроса для поиска похожих векторов с помощью индекса L2Distance. На месте «vector» должны быть значения вектора, на основе которого будет происходить поиск:

WITH { vector } AS reference_vector
SELECT
    doc_id,
    cosineDistance(centroid, reference_vector) AS distance
FROM db_master.element
ORDER BY distance
LIMIT 10

1.1.2. Поиск на основе FAISS с IndexIVFFlat

Этот метод использует индексирование с помощью IndexIVFFlat. Такой подход позволяет разбивать данные на кластеры и производить поиск в этих кластерах. В методе инициализируется индекс, определяется количество кластеров. После находятся ближайшие векторы к заданным входным векторам.

Плюсы:

• гибкость в настройке параметров кластеризации (например, количество кластеров), что позволяет адаптировать метод под конкретные задачи и требования;

• эффективное использование памяти, так как не все векторы загружаются в память одновременно.

Минусы:

• требует предварительного обучения (кластеризации) индекса, что может занять время;

• потенциальная потеря точности поиска из‑за приближенного характера метода.

Ниже часть python‑кода инициализации и настройки индекса IndexIVFFlat для поиска ближайших соседей с использованием библиотеки FAISS:

self.doc_ids = np.array(list(vectors_index.keys()))
self.db_vectors = np.array(list(vectors_index.values()), dtype="float64")
d = self.db_vectors.shape[1]
quantizer = faiss.IndexFlatL2(d)
self.index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
self.index.train(self.db_vectors)
self.index.add(self.db_vectors)

1.2. С метрикой cosine (косинусная близость)

Вообще, косинусное расстояние это , но визуально легче воспринимается угол между векторами

Этот метод выполняет SQL‑запрос в ClickHouse, используя функцию cosineDistance. Для этого способа в таблице был реализован индекс «idx_cosine», в основе которого лежит функция дистанции, считающая косинусное расстояние (угол между двумя ненулевыми векторами).

Плюсы:

• минимальное потребление оперативной памяти;

• хорошо масштабируется при увеличении количества данных.

Минусы:

• функциональность зависит от возможностей ClickHouse и его встроенных функций;

• ограниченная точность, которой может быть недостаточно в некоторых задачах.

Ниже пример SQL‑запроса для поиска похожих векторов с помощью индекса cosineDistance. На месте «vector» должны быть значения вектора, на основе которого будет происходить поиск:

WITH { vector } AS reference_vector
SELECT
    doc_id,
    cosineDistance(centroid, reference_vector) AS distance
FROM db_master.element
ORDER BY distance
LIMIT 10

2. Методы без индексации (полный перебор)

Иголка в стоге сена — это более простая задача, чем knn с полным перебором, т.к. при нахождении иглы мы сразу можем отличить её от соломинки и остановить поиск

2.1. С метрикой L2 (евклидово расстояние)

2.1.1. Поиск на основе полного перебора с метрикой расстояния, реализованной в Python

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

Плюсы:

• простота реализации;

• гибкость в выборе метрики.

Минусы:

• низкая производительность на больших объемах данных;

• высокие затраты по памяти, так как все векторы загружаются в оперативную память

Функция для подсчета евклидова расстояния:

def euclidean_distance(a: np.ndarray, b: np.ndarray) -> float:
   return np.sqrt(np.sum((a - b) ** 2))

2.1.2. Поиск на основе FAISS с IndexFlatL2 (псевдоиндекс - полный перебор)

В этом методе векторы загружаются в память и строится индекс FAISS. Для поиска использовали индекс IndexFlatL2. После настройки индекса находятся ближайшие векторы к заданным входным векторам и возвращает результаты с расстояниями.

Плюсы:

• он проверяет каждый вектор в базе данных, поэтому гарантирует точные результаты;

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

Минусы:

• требует полного перебора векторов, что замедляет поиск на больших данных;

• при очень больших объемах данных потребление памяти может быть высоким, так как FAISS загружает все векторы в оперативную память для построения индекса и поиска.

Ниже часть python‑кода инициализации и настройки индекса IndexFlatL2 для поиска ближайших соседей с использованием библиотеки FAISS:

self.doc_ids = np.array(list(vectors_index.keys()))
self.db_vectors = np.array(list(vectors_index.values()), dtype="float64")
self.index = faiss.IndexFlatL2(self.db_vectors.shape[1])
self.index.add(self.db_vectors)

Тестирование по времени и памяти

Итак, а что же на практике? Тестировали все описанные методы на наборе данных из 20 000 записей, каждая из которых представляла собой вектор размером «float 512» элементов. Поиск происходил по набору данных из 3 записей, тоже представляющих собой вектор размером «float 512». Версии ПО, на котором проводили тестирование: Python 3.12, библиотека Faiss(faiss‑cpu) версии 1.10.0, база данных ClickHouse версии 24.12.3.47. Задача тестирования — сравнить методы по времени выполнения и по использованию памяти, чтобы по результатам определить самый эффективный метод поиска похожих векторов из всех пяти вариантов.

Время выполнения

Среднее время выполнения каждого метода представлено в таблице 1. Метод «Полный перебор», основанный на вычислении евклидова расстояния, показал самое продолжительное время выполнения. Это связано с необходимостью полного перебора всех точек данных. Метод «FAISS IndexFlatL2» продемонстрировал значительное улучшение скорости поиска благодаря оптимизированным алгоритмам. При этом метод «FAISS IndexIVFFlat» оказался менее эффективным, чем предыдущий — из‑за того, что индекс, который используется в методе FAISS IndexIVFFlat»), рассчитан на большие размеры данных. Методы «ClickHouse L2Distance» и «ClickHouse cosineDistance» показали лучшие результаты, особенно при работе с большими объемами данных, благодаря использованию эффективных механизмов индексации. В то же время метод «ClickHouse cosineDistance» оказался самым быстрым из всех рассмотренных способов, что подчеркивает его преимущество в задачах поиска на больших наборах данных.

Таблица 1. Среднее время выполнения методов (секунды)

Метод	Среднее время выполнения (сек)
ClickHouse L2Distance	1.3420
FAISS IndexIVFFlat	2.5666
ClickHouse cosineDistance	1.2525
Полный перебор с метрикой расстояния	2.6867
FAISS IndexFlatL2	2.3519

Использование памяти

Максимальное использование оперативной памяти каждым методом представлено в таблице 2. Метод «Полный перебор», основанный на вычислении евклидова расстояния, показал самую большую пиковую нагрузку на память. Это связано с необходимостью хранения и обработки всех точек данных в оперативной памяти. Методы «FAISS IndexFlatL2» и «FAISS IndexIVFFlat» тоже продемонстрировали высокие значения использования памяти, близкие к методу «Полный перебор», что объясняется схожими требованиями к хранению данных и индексов в памяти. При этом методы «ClickHouse L2Distance» и «ClickHouse cosineDistance» показали значительно более низкую пиковую нагрузку на память. Это связано с использованием оптимизированных механизмов индексации и хранения данных в ClickHouse. Метод «ClickHouse cosineDistance» оказался самым экономичным по использованию памяти.

Таблица 2. Максимальное использование памяти методами (МБ)

Метод	Средняя пиковая нагрузка памяти (MiB)
ClickHouse L2Distance	322.13
FAISS IndexIVFFlat	584.44
ClickHouse cosineDistance	320.33
Полный перебор с метрикой расстояния	585.45
FAISS IndexFlatL2	585.14

Выводы: какой метод эффективнее?

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

Простой перебор с метрикой расстояния на Python работает неплохо только на небольших наборах (до 100 тыс. векторов), тогда как FAISS IndexFlatL2 обеспечивает хороший баланс скорости и точности для средних объемов (100 тыс. — 10 млн). Однако при работе с очень большим количеством данных (10 млн+ векторов) оптимальным выбором становятся рассмотренные специализированные методы ClickHouse — L2Distance и cosineDistance, которые демонстрируют наилучшую производительность при минимальном потреблении памяти.

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

Таким образом, выбор метода определяется соотношением точности, скорости обработки и необходимых ресурсов. Для небольших проектов достаточно простых решений, тогда как для работы с большими объемами данных оптимальным выбором становятся оптимизированные системы вроде ClickHouse. Дальнейшие исследования, на мой взгляд, следует направить на изучение эффективности этих методов при работе с векторами различной размерности и в распределённых системах, что особенно актуально для современных систем обработки векторных представлений.

Диана Бутько

Студентка КМПО РАНХиГС, практикант группы научно‑исследовательской разработки InfoWatch, автор статьи