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

Точный и приближенный векторный поиск

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

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

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

WITH [...] AS reference_vector
SELECT [...]
FROM table
WHERE [...] -- a WHERE clause is optional
ORDER BY <DistanceFunction>(vectors, reference_vector)
LIMIT <N>

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

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

Пример​

CREATE TABLE tab(id Int32, vec Array(Float32)) ENGINE = MergeTree ORDER BY id;

INSERT INTO tab VALUES (0, [1.0, 0.0]), (1, [1.1, 0.0]), (2, [1.2, 0.0]), (3, [1.3, 0.0]), (4, [1.4, 0.0]), (5, [1.5, 0.0]), (6, [0.0, 2.0]), (7, [0.0, 2.1]), (8, [0.0, 2.2]), (9, [0.0, 2.3]), (10, [0.0, 2.4]), (11, [0.0, 2.5]);

WITH [0., 2.] AS reference_vec
SELECT id, vec
FROM tab
ORDER BY L2Distance(vec, reference_vec) ASC
LIMIT 3;

возвращает

   ┌─id─┬─vec─────┐
1. │  6 │ [0,2]   │
2. │  7 │ [0,2.1] │
3. │  8 │ [0,2.2] │
   └────┴─────────┘

Индексы сходства векторов​

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

примечание

Индексы сходства векторов доступны в ClickHouse версии 25.8 и выше. Если вы столкнетесь с проблемами, пожалуйста, откройте вопрос в репозитории ClickHouse.

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

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

CREATE TABLE table
(
  [...],
  vectors Array(Float*),
  INDEX <index_name> vectors TYPE vector_similarity(<type>, <distance_function>, <dimensions>) [GRANULARITY <N>]
)
ENGINE = MergeTree
ORDER BY [...]

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

ALTER TABLE table ADD INDEX <index_name> vectors TYPE vector_similarity(<type>, <distance_function>, <dimensions>) [GRANULARITY <N>];

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

ALTER TABLE table MATERIALIZE INDEX <index_name> SETTINGS mutations_sync = 2;

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

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

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

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

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

CREATE TABLE table
(
  [...],
  vectors Array(Float*),
  INDEX index_name vectors TYPE vector_similarity('hnsw', <distance_function>, <dimensions>[, <quantization>, <hnsw_max_connections_per_layer>, <hnsw_candidate_list_size_for_construction>]) [GRANULARITY N]
)
ENGINE = MergeTree
ORDER BY [...]

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

  • <quantization> контролирует квантизацию векторов в графе близости. Возможные значения: f64, f32, f16, bf16, i8 или b1. Значение по умолчанию — bf16. Обратите внимание, что этот параметр не влияет на представление векторов в underlying column.
  • <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(BFloat16). Массивы с nullable и low-cardinality float, такие как Array(Nullable(Float32)) и Array(LowCardinality(Float32)), не допускаются.
  • Индексы сходства векторов должны быть построены на одиночных колонках.
  • Индексы сходства векторов могут быть построены на вычисленных выражениях (например, INDEX index_name arraySort(vectors) TYPE vector_similarity([...])), но такие индексы не могут быть использованы для приближенного поиска соседей позже.
  • Индексы сходства векторов требуют, чтобы все массивы в underlying column имели <dimension>-много элементов — это проверяется во время создания индекса. Чтобы как можно скорее выявить нарушения этого требования, пользователи могут добавить ограничение для векторной колонки, например, CONSTRAINT same_length CHECK length(vectors) = 256.
  • Точно так же значения массива в underlying column не должны быть пустыми ([]) или иметь значение по умолчанию (также []).

Оценка потребления хранилища и памяти

Вектор, созданный для использования с типичной моделью ИИ (например, большая языковая модель, LLMs), состоит из сотен или тысяч значений с плавающей точкой. Таким образом, одно значение вектора может занимать несколько килобайт памяти. Пользователи, которые хотят оценить хранилище, необходимое для underlying vector column в таблице, а также основную память, необходимую для индекса сходства векторов, могут использовать два приведенных ниже формула:

Потребление хранилища векторной колонки в таблице (несжатое):

Storage consumption = Number of vectors * Dimension * Size of column data type

Пример для данных dbpedia:

Storage consumption = 1 million * 1536 * 4 (for Float32) = 6.1 GB

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

Потребление памяти, необходимое для загрузки векторного индекса:

Memory for vectors in the index (mv) = Number of vectors * Dimension * Size of quantized data type
Memory for in-memory graph (mg) = Number of vectors * hnsw_max_connections_per_layer * Bytes_per_node_id (= 4) * Layer_node_repetition_factor (= 2)

Memory consumption: mv + mg

Пример для данных dbpedia:

Memory for vectors in the index (mv) = 1 million * 1536 * 2 (for BFloat16) = 3072 MB
Memory for in-memory graph (mg) = 1 million * 64 * 2 * 4 = 512 MB

Memory consumption = 3072 + 512 = 3584 MB

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

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

примечание

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

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

WITH [...] AS reference_vector
SELECT [...]
FROM table
WHERE [...] -- a WHERE clause is optional
ORDER BY <DistanceFunction>(vectors, reference_vector)
LIMIT <N>

Оптимизатор запросов 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.

В качестве примера, запрос

EXPLAIN indexes = 1
WITH [0.462, 0.084, ..., -0.110] AS reference_vec
SELECT id, vec
FROM tab
ORDER BY L2Distance(vec, reference_vec) ASC
LIMIT 10;

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

    ┌─explain─────────────────────────────────────────────────────────────────────────────────────────┐
 1. │ Expression (Project names)                                                                      │
 2. │   Limit (preliminary LIMIT (without OFFSET))                                                    │
 3. │     Sorting (Sorting for ORDER BY)                                                              │
 4. │       Expression ((Before ORDER BY + (Projection + Change column names to column identifiers))) │
 5. │         ReadFromMergeTree (default.tab)                                                         │
 6. │         Indexes:                                                                                │
 7. │           PrimaryKey                                                                            │
 8. │             Condition: true                                                                     │
 9. │             Parts: 1/1                                                                          │
10. │             Granules: 575/575                                                                   │
11. │           Skip                                                                                  │
12. │             Name: idx                                                                           │
13. │             Description: vector_similarity GRANULARITY 100000000                                │
14. │             Parts: 1/1                                                                          │
15. │             Granules: 10/575                                                                    │
    └─────────────────────────────────────────────────────────────────────────────────────────────────┘

В этом примере 1 миллион векторов в данных dbpedia, каждый с размерностью 1536, хранятся в 575 гранулах, т.е. 1,7 тыс. строк на гранулу. Запрос запрашивает 10 соседей, и индекс сходства векторов находит эти 10 соседей в 10 отдельных гранулах. Эти 10 гранул будут прочитаны во время выполнения запроса.

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

подсказка

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

Постфильтрация и предварительная фильтрация

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

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

Стратегии имеют различные компромиссы:

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

Какая стратегия используется, зависит от условия фильтрации.

Дополнительные фильтры являются частью ключа партиции

Если дополнительное условие фильтрации является частью ключа партиции, то ClickHouse применит обрезку партиции. Например, таблица разбита на диапазоны по колонке year, и выполняется следующий запрос:

WITH [0., 2.] AS reference_vec
SELECT id, vec
FROM tab
WHERE year = 2025
ORDER BY L2Distance(vec, reference_vec) ASC
LIMIT 3;

ClickHouse обрежет все партиции, кроме 2025 года.

Дополнительные фильтры не могут быть оценены с помощью индексов

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

Дополнительные фильтры могут быть оценены с помощью индекса первичного ключа

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

  • условие фильтрации исключает хотя бы одну строку в пределах части, ClickHouse откатится к предварительной фильтрации для "выживших" диапазонов в пределах части,
  • условие фильтрации не исключает никаких строк в пределах части, ClickHouse выполнит постфильтрацию для части.

В практических случаях скорее маловероятно, что сработает последний случай.

Дополнительные фильтры могут быть оценены с помощью индекса пропуска

Если дополнительные условия фильтрации могут быть оценены с помощью индексов пропуска (индекс minmax, индекс множеств и т.д.), ClickHouse выполняет постфильтрацию. В таких случаях сначала оценивается индекс сходства векторов, поскольку ожидается, что он удалит больше строк по сравнению с другими индексами пропуска.

Для более тонкого контроля над постфильтрацией и предварительной фильтрацией могут быть использованы две настройки:

Настройка vector_search_filter_strategy (по умолчанию: auto, которая реализует вышеуказанные эвристики) может быть установлена на prefilter. Это полезно для принудительной предварительной фильтрации в случаях, когда дополнительные условия фильтрации являются исключительно избирательными. Например, следующий запрос может извлечь выгоду от предварительной фильтрации:

SELECT bookid, author, title
FROM books
WHERE price < 2.00
ORDER BY cosineDistance(book_vector, getEmbedding('Books on ancient Asian empires'))
LIMIT 10

Предполагая, что только очень небольшое количество книг стоит меньше 2 долларов, постфильтрация может вернуть ноль строк, потому что 10 лучших совпадений, возвращаемых индексом векторов, могут все стоить больше 2 долларов. Принудив предварительную фильтрацию (добавив SETTINGS vector_search_filter_strategy = 'prefilter' к запросу), ClickHouse сначала находит все книги с ценой менее 2 долларов, а затем выполняет переборный векторный поиск для найденных книг.

В качестве альтернативного подхода к решению вышеуказанной проблемы настройка vector_search_index_fetch_multiplier (по умолчанию: 1.0, максимум: 1000.0) может быть настроена на значение > 1.0 (например, 2.0). Количество ближайших соседей, извлекаемых из индекс векторов, умножается на значение настройки, а затем применяется дополнительный фильтр к этим строкам, чтобы вернуть LIMIT-количество строк. Например, мы можем снова выполнить запрос, но с коэффициентом 3.0:

SELECT bookid, author, title
FROM books
WHERE price < 2.00
ORDER BY cosineDistance(book_vector, getEmbedding('Books on ancient Asian empires'))
LIMIT 10
SETTING vector_search_index_fetch_multiplier = 3.0;

ClickHouse извлечет 3.0 x 10 = 30 ближайших соседей из индекс векторов в каждой части, а затем оценит дополнительные фильтры. Будет возвращено только десять ближайших соседей. Обратите внимание, что настройка vector_search_index_fetch_multiplier может облегчить проблему, но в крайних случаях (когда условие WHERE очень селективно), все равно возможно получить менее N запрашиваемых строк.

Пересчет

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

Поэтому ClickHouse предоставляет оптимизацию, которая отключает пересчет и возвращает наиболее похожие векторы и их расстояния непосредственно из индекса. Оптимизация включена по умолчанию, см. настройку vector_search_with_rescoring. На высоком уровне это работает так, что ClickHouse делает наиболее похожие векторы и их расстояния доступными в виде виртуальной колонки _distances. Чтобы это увидеть, выполните запрос векторного поиска с EXPLAIN header = 1:

EXPLAIN header = 1
WITH [0., 2.] AS reference_vec
SELECT id
FROM tab
ORDER BY L2Distance(vec, reference_vec) ASC
LIMIT 3
SETTINGS vector_search_with_rescoring = 0

Query id: a2a9d0c8-a525-45c1-96ca-c5a11fa66f47

    ┌─explain─────────────────────────────────────────────────────────────────────────────────────────────────┐
 1. │ Expression (Project names)                                                                              │
 2. │ Header: id Int32                                                                                        │
 3. │   Limit (preliminary LIMIT (without OFFSET))                                                            │
 4. │   Header: L2Distance(__table1.vec, _CAST([0., 2.]_Array(Float64), 'Array(Float64)'_String)) Float64     │
 5. │           __table1.id Int32                                                                             │
 6. │     Sorting (Sorting for ORDER BY)                                                                      │
 7. │     Header: L2Distance(__table1.vec, _CAST([0., 2.]_Array(Float64), 'Array(Float64)'_String)) Float64   │
 8. │             __table1.id Int32                                                                           │
 9. │       Expression ((Before ORDER BY + (Projection + Change column names to column identifiers)))         │
10. │       Header: L2Distance(__table1.vec, _CAST([0., 2.]_Array(Float64), 'Array(Float64)'_String)) Float64 │
11. │               __table1.id Int32                                                                         │
12. │         ReadFromMergeTree (default.tab)                                                                 │
13. │         Header: id Int32                                                                                │
14. │                 _distance Float32                                                                       │
    └─────────────────────────────────────────────────────────────────────────────────────────────────────────┘
примечание

Запрос, выполненный без пересчета (vector_search_with_rescoring = 0) и с включенными параллельными репликами, может откатиться к пересчету.

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

Настройка сжатия

Практически во всех случаях использования векторы в underlying column являются плотными и плохо сжимаются. В результате, сжатие замедляет вставки и чтения в/из векторной колонки. Поэтому мы рекомендуем отключить сжатие. Для этого укажите CODEC(NONE) для векторной колонки следующим образом:

CREATE TABLE tab(id Int32, vec Array(Float32) CODEC(NONE), INDEX idx vec TYPE vector_similarity('hnsw', 'L2Distance', 2)) ENGINE = MergeTree ORDER BY id;

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

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

SELECT metric, value
FROM system.metrics
WHERE metric = 'VectorSimilarityIndexCacheBytes'

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

SYSTEM FLUSH LOGS query_log;

SELECT ProfileEvents['VectorSimilarityIndexCacheHits'], ProfileEvents['VectorSimilarityIndexCacheMisses']
FROM system.query_log
WHERE type = 'QueryFinish' AND query_id = '<...>'
ORDER BY event_time_microseconds;

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

Настройка квантизации

Квантизация — это техника для уменьшения объема памяти векторов и вычислительных затрат на создание и обход индексов векторов. Индексы векторов ClickHouse поддерживают следующие варианты квантизации:

КвантизацияНазваниеХранение на размерности
f32Одинарная точность4 байта
f16Полуторная точность2 байта
bf16 (по умолчанию)Полуторная точность (brain float)2 байта
i8Четверная точность1 байт
b1Двоичная1 бит

Квантизация снижает точность векторных поисков по сравнению с поисками по оригинальным значениям с плавающей точкой полного разрешения (f32). Однако на большинстве наборов данных квантизация с полуторной точностью brain float (bf16) приводит к незначительной потере точности, поэтому индексы сходства векторов используют эту технику квантизации по умолчанию. Квантизация с четвертной точностью (i8) и двоичная квантизация (b1) приводит к заметной потере точности в векторных поисках. Мы рекомендуем обе квантизации только в тех случаях, когда размер индекса сходства векторов значительно больше размера доступной оперативной памяти DRAM. В таком случае также рекомендуется включить пересчет (vector_search_index_fetch_multiplier, vector_search_with_rescoring) для повышения точности. Двоичная квантизация рекомендована только для 1) нормализованных встраиваний (т.е. длина вектора = 1, модели OpenAI обычно нормализованы) и 2) если косинусное расстояние используется в качестве функции расстояния. Двоичная квантизация использует расстояние Хэмминга для построения и поиска графа близости. Этап пересчета использует оригинальные векторы с полным разрешением, хранящиеся в таблице, для определения ближайших соседей через косинусное расстояние.

Настройка передачи данных

Ссылающийся вектор в запросе на векторный поиск предоставляется пользователем и, как правило, извлекается, выполняя вызов к большой языковой модели (LLM). Типичный код на Python, который выполняет векторный поиск в ClickHouse, может выглядеть так

search_v = openai_client.embeddings.create(input = "[Good Books]", model='text-embedding-3-large', dimensions=1536).data[0].embedding

params = {'search_v': search_v}
result = chclient.query(
   "SELECT id FROM items
    ORDER BY cosineDistance(vector, %(search_v)s)
    LIMIT 10",
    parameters = params)

Встраиваемые векторы (search_v в приведенном выше фрагменте) могут иметь очень большую размерность. Например, OpenAI предоставляет модели, которые генерируют встраивающие векторы с 1536 или даже 3072 размерностями. В приведенном выше коде драйвер Python для ClickHouse заменяет встраиваемый вектор на строку в человеко-читаемом формате и затем отправляет запрос SELECT полностью как строку. Предполагая, что встраиваемый вектор состоит из 1536 значений с плавающей точкой одинарной точности, отправленная строка достигает длины 20 кБ. Это создает высокую загрузку CPU для токенизации, разбора и выполнения тысяч преобразований строк в числа с плавающей точкой. Также требуется значительное пространство в файле журналов сервера ClickHouse, что приводит к увеличению объема system.query_log.

Обратите внимание, что большинство моделей LLM возвращают встраиваемый вектор в виде списка или массива NumPy из нативных чисел с плавающей точкой. Поэтому мы рекомендуем Python-приложениям передавать параметр ссылочного вектора в бинарной форме, используя следующий стиль:

search_v = openai_client.embeddings.create(input = "[Good Books]", model='text-embedding-3-large', dimensions=1536).data[0].embedding

params = {'$search_v_binary$': np.array(search_v, dtype=np.float32).tobytes()}
result = chclient.query(
   "SELECT id FROM items
    ORDER BY cosineDistance(vector, (SELECT reinterpret($search_v_binary$, 'Array(Float32)')))
    LIMIT 10"
    parameters = params)

В этом примере ссылающийся вектор отправляется как есть в бинарной форме и переинтерпретируется как массив чисел с плавающей точкой на сервере. Это экономит время CPU на стороне сервера и избегает увеличения объема в журналах сервера и system.query_log.

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

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

SELECT database, table, name, formatReadableSize(data_compressed_bytes)
FROM system.data_skipping_indices
WHERE type = 'vector_similarity';

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

┌─database─┬─table─┬─name─┬─formatReadab⋯ssed_bytes)─┐
│ default  │ tab   │ idx  │ 348.00 MB                │
└──────────┴───────┴──────┴──────────────────────────┘

Различия с обычными индексами пропуска​

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

Пример​

CREATE TABLE tab(id Int32, vec Array(Float32), INDEX idx vec TYPE vector_similarity('hnsw', 'L2Distance', 2)) ENGINE = MergeTree ORDER BY id;

INSERT INTO tab VALUES (0, [1.0, 0.0]), (1, [1.1, 0.0]), (2, [1.2, 0.0]), (3, [1.3, 0.0]), (4, [1.4, 0.0]), (5, [1.5, 0.0]), (6, [0.0, 2.0]), (7, [0.0, 2.1]), (8, [0.0, 2.2]), (9, [0.0, 2.3]), (10, [0.0, 2.4]), (11, [0.0, 2.5]);

WITH [0., 2.] AS reference_vec
SELECT id, vec
FROM tab
ORDER BY L2Distance(vec, reference_vec) ASC
LIMIT 3;

возвращает

   ┌─id─┬─vec─────┐
1. │  6 │ [0,2]   │
2. │  7 │ [0,2.1] │
3. │  8 │ [0,2.2] │
   └────┴─────────┘

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

Квантизованный бит (QBit)​

Experimental feature. Learn more.

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

При традиционной квантизации мы теряем точность как во время поиска, так и при хранении данных. В приведенном выше примере мы храним BFloat16 вместо Float32, что означает, что мы никогда не сможем выполнить более точный поиск позже, даже если это будет необходимо. Одним из альтернативных подходов является хранение двух копий данных: квантизированных и с полной точностью. Хотя это работает, это требует избыточного хранения. Рассмотрим сценарий, в котором у нас есть Float64 как исходные данные, и мы хотим выполнять поиск с различной точностью (16-бит, 32-бит или полные 64-бита). Нам нужно будет хранить три отдельные копии данных.

ClickHouse предлагает тип данных Квантизованный бит (QBit), который решает эти ограничения путем:

  1. Хранения оригинальных данных с полной точностью.
  2. Позволяя задавать точность квантизации во время выполнения запроса.

Это достигается путем хранения данных в битовой группировке (что означает, что все i-е биты всех векторов хранятся вместе), что позволяет считывать данные только на запрашиваемом уровне точности. Вы получаете преимущества по скорости за счет уменьшения I/O от квантизации, сохраняя все оригинальные данные доступными, когда это необходимо. Когда выбрана максимальная точность, поиск становится точным.

примечание

Тип данных QBit и связанные с ним функции расстояния в настоящее время являются экспериментальными. Чтобы включить их, выполните SET allow_experimental_qbit_type = 1. Если у вас возникли проблемы, пожалуйста, откройте обращение в репозитории ClickHouse.

Чтобы объявить колонку типа QBit, используйте следующий синтаксис:

column_name QBit(element_type, dimension)

Где:

  • element_type — тип каждого элемента вектора. Поддерживаемые типы: BFloat16, Float32 и Float64
  • dimension — количество элементов в каждом векторе

Создание таблицы QBit и добавление данных​

CREATE TABLE fruit_animal (
    word String,
    vec QBit(Float64, 5)
) ENGINE = MergeTree
ORDER BY word;

INSERT INTO fruit_animal VALUES
    ('apple', [-0.99105519, 1.28887844, -0.43526649, -0.98520696, 0.66154391]),
    ('banana', [-0.69372815, 0.25587061, -0.88226235, -2.54593015, 0.05300475]),
    ('orange', [0.93338752, 2.06571317, -0.54612565, -1.51625717, 0.69775337]),
    ('dog', [0.72138876, 1.55757105, 2.10953259, -0.33961248, -0.62217325]),
    ('cat', [-0.56611276, 0.52267331, 1.27839863, -0.59809804, -1.26721048]),
    ('horse', [-0.61435682, 0.48542571, 1.21091247, -0.62530446, -1.33082533]);

Давайте найдем ближайших соседей к вектору, представляющему слово 'lemon', используя расстояние L2. Третий параметр в функции расстояния указывает точность в битах — более высокие значения обеспечивают большую точность, но требуют больше вычислений.

Вы можете найти все доступные функции расстояния для QBit здесь.

Поиск с полной точностью (64 бита):

SELECT
    word,
    L2DistanceTransposed(vec, [-0.88693672, 1.31532824, -0.51182908, -0.99652702, 0.59907770], 64) AS distance
FROM fruit_animal
ORDER BY distance;

   ┌─word───┬────────────distance─┐
1. │ apple  │ 0.14639757188169716 │
2. │ banana │   1.998961369007679 │
3. │ orange │   2.039041552613732 │
4. │ cat    │   2.752802631487914 │
5. │ horse  │  2.7555776805484813 │
6. │ dog    │   3.382295083120104 │
   └────────┴─────────────────────┘

Поиск с сниженной точностью:

SELECT
    word,
    L2DistanceTransposed(vec, [-0.88693672, 1.31532824, -0.51182908, -0.99652702, 0.59907770], 12) AS distance
FROM fruit_animal
ORDER BY distance;

   ┌─word───┬───────────distance─┐
1. │ apple  │  0.757668703053566 │
2. │ orange │ 1.5499475034938677 │
3. │ banana │ 1.6168396735102937 │
4. │ cat    │  2.429752230904804 │
5. │ horse  │  2.524650475528617 │
6. │ dog    │   3.17766975527459 │
   └────────┴────────────────────┘

Обратите внимание, что с 12-битной квантизацией мы получаем хорошую аппроксимацию расстояний с более быстрой реализацией запроса. Относительный порядок остается в основном неизменным, 'apple' по-прежнему является ближайшим совпадением.

примечание

В текущем состоянии ускорение связано с уменьшением I/O, так как мы читаем меньше данных. Если оригинальные данные были широкими, как Float64, выбор более низкой точности все равно приведет к вычислению расстояний по данным с той же шириной — просто с меньшей точностью.

Соображения по производительности​

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

  • Более высокая точность (ближе к ширине оригинальных данных): более точные результаты, более медленные запросы
  • Низкая точность: более быстрые запросы с приблизительными результатами, уменьшенное использование памяти
примечание

В настоящее время улучшение скорости происходит за счет уменьшения I/O, а не оптимизации вычислений. При использовании более низких значений точности вычисления расстояний все еще выполняются на данных оригинальной ширины.

Ссылки​

Блоги: