Расширение поиска по векторному сходству

Расширение vss — это экспериментальное расширение для DuckDB, которое добавляет поддержку индексирования для ускорения запросов поиска по векторному сходству с использованием нового типа фиксированного размера ARRAY DuckDB.

См. запись в блоге об анонсе и статью «Что нового в расширении поиска по векторному сходству?».

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

Для создания нового индекса HNSW (Hierarchical Navigable Small Worlds) в таблице со столбцом ARRAY, используйте оператор CREATE INDEX с клаузой USING HNSW. Например:

CREATE TABLE my_vector_table (vec FLOAT[3]);
INSERT INTO my_vector_table SELECT array_value(a, b, c) FROM range(1, 10) ra(a), range(1, 10) rb(b), range(1, 10) rc(c);
CREATE INDEX my_hnsw_index ON my_vector_table USING HNSW (vec);

Затем индекс будет использоваться для ускорения запросов, использующих клаузу ORDER BY, оценивающую одну из поддерживаемых функций метрики расстояния по отношению к индексированным столбцам и константному вектору, за которой следует клауза LIMIT. Например:

SELECT * FROM my_vector_table ORDER BY array_distance(vec, [1, 2, 3]::FLOAT[3]) LIMIT 3;

Кроме того, перегруженный оператор min_by(col, arg, n) также может быть ускорен с помощью индекса HNSW, если аргумент arg — это соответствующая функция метрики расстояния. Это можно использовать для быстрых одноразовых поисков ближайших соседей. Например, чтобы получить 3 строки с ближайшими векторами к [1, 2, 3]:

SELECT min_by(my_vector_table, array_distance(vec, [1, 2, 3]::FLOAT[3]), 3) AS result FROM my_vector_table;
---- [{'vec': [1.0, 2.0, 3.0]}, {'vec': [1.0, 2.0, 4.0]}, {'vec': [2.0, 2.0, 3.0]}]

Обратите внимание, как мы передаем имя таблицы в качестве первого аргумента к min_by для возврата структуры, содержащей всю сопоставленную строку.

Мы можем проверить, что индекс используется, проверив вывод EXPLAIN и поиска узла HNSW_INDEX_SCAN в плане запроса:

EXPLAIN SELECT * FROM my_vector_table ORDER BY array_distance(vec, [1, 2, 3]::FLOAT[3]) LIMIT 3;

┌───────────────────────────┐
│         PROJECTION        │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│             #0            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│            vec            │
│array_distance(vec, [1.0, 2│
│         .0, 3.0])         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│      HNSW_INDEX_SCAN      │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│   t1 (HNSW INDEX SCAN :   │
│           my_idx)         │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│            vec            │
│   ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─   │
│           EC: 3           │
└───────────────────────────┘

По умолчанию индекс HNSW будет создан с использованием метрики евклидова расстояния l2sq (квадрат L2-нормы), соответствующей функции DuckDB array_distance, но другие метрики расстояния могут быть использованы путем указания опции metric при создании индекса. Например:

CREATE INDEX my_hnsw_cosine_index
ON my_vector_table
USING HNSW (vec)
WITH (metric = 'cosine');

В следующей таблице показаны поддерживаемые метрики расстояния и соответствующие функции DuckDB

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

Параметры индекса

Помимо опции metric, оператор создания индекса HNSW также поддерживает следующие параметры для управления гиперпараметрами процесса построения и поиска индекса:

Кроме того, вы можете переопределить параметр ef_search во время построения индекса, задав параметр конфигурации SET hnsw_ef_search = ⟨int⟩ во время выполнения. Это может быть полезно, если вы хотите поменять производительность поиска на точность или наоборот на основе соединения. Вы также можете снять переопределение, вызвав RESET hnsw_ef_search.

Сохранение

Из-за известных проблем с сохранением пользовательских индексов расширений индекс HNSW по умолчанию может быть создан только в таблицах баз данных в оперативной памяти, если параметр конфигурации SET hnsw_enable_experimental_persistence = ⟨bool⟩ не установлен в значение true.

Причина, по которой эта функция ограничена экспериментальной меткой, заключается в том, что восстановление «Журнала транзакций» (WAL) для пользовательских индексов еще не реализовано должным образом. Это означает, что если произойдет сбой или база данных будет неожиданно закрыта, в то время как есть несохраненные изменения в таблице с индексом HNSW, вы можете потерять данные или повредить индекс.

Если вы включите этот параметр и столкнетесь с неожиданной остановкой, вы можете попытаться восстановить индекс, сначала запустив DuckDB отдельно, загрузив расширение vss и затем ATTACH файл базы данных. Это гарантирует, что функциональность индекса HNSW будет доступна во время воспроизведения Журнала транзакций, что позволит процессу восстановления DuckDB пройти без проблем. Но мы по-прежнему рекомендуем не использовать эту функцию в производственной среде.

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

Вставки, обновления, удаления и пересборка

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

• Быстрее создать индекс после того, как таблица будет заполнена данными, так как начальная массовая загрузка может более эффективно использовать параллелизм в больших таблицах.
• Удаления не отражаются немедленно в индексе, а вместо этого «помечаются» как удаленные, что может привести к устареванию индекса со временем и отрицательно повлиять на качество и производительность запросов.

Чтобы исправить последний момент, можно вызвать функцию pragma PRAGMA hnsw_compact_index('⟨index name⟩') для запуска пересборки индекса, удаляя удаленные элементы, или пересоздать индекс после значительного количества обновлений.

Бонус: объединения поиска по векторному сходству

Расширение vss также предоставляет несколько макросов таблиц для упрощения сопоставления нескольких векторов друг с другом, так называемых «размытых объединений». Это:

• vss_join(left_table, right_table, left_col, right_col, k, metric := 'l2sq')
• vss_match(right_table", left_col, right_col, k, metric := 'l2sq')

Эти функции не в настоящее время используют индекс HNSW, но предоставляются в качестве удобных утилит для пользователей, которым достаточно выполнения поиска по векторному сходству с полным перебором без необходимости написания самим логики объединения. В будущем они также могут стать целями оптимизации на основе индекса.

Эти функции можно использовать следующим образом:

CREATE TABLE haystack (id int, vec FLOAT[3]);
CREATE TABLE needle (search_vec FLOAT[3]);

INSERT INTO haystack SELECT row_number() OVER (), array_value(a,b,c)
FROM range(1, 10) ra(a), range(1, 10) rb(b), range(1, 10) rc(c);

INSERT INTO needle VALUES ([5, 5, 5]), ([1, 1, 1]);

SELECT * FROM vss_join(needle, haystack, search_vec, vec, 3) AS res;

┌───────┬─────────────────────────────────┬─────────────────────────────────────┐
│ score │            left_tbl             │              right_tbl              │
│ float │   struct(search_vec float[3])   │  struct(id integer, vec float[3])   │
├───────┼─────────────────────────────────┼─────────────────────────────────────┤
│   0.0 │ {'search_vec': [5.0, 5.0, 5.0]} │ {'id': 365, 'vec': [5.0, 5.0, 5.0]} │
│   1.0 │ {'search_vec': [5.0, 5.0, 5.0]} │ {'id': 364, 'vec': [5.0, 4.0, 5.0]} │
│   1.0 │ {'search_vec': [5.0, 5.0, 5.0]} │ {'id': 356, 'vec': [4.0, 5.0, 5.0]} │
│   0.0 │ {'search_vec': [1.0, 1.0, 1.0]} │ {'id': 1, 'vec': [1.0, 1.0, 1.0]}   │
│   1.0 │ {'search_vec': [1.0, 1.0, 1.0]} │ {'id': 10, 'vec': [2.0, 1.0, 1.0]}  │
│   1.0 │ {'search_vec': [1.0, 1.0, 1.0]} │ {'id': 2, 'vec': [1.0, 2.0, 1.0]}   │
└───────┴─────────────────────────────────┴─────────────────────────────────────┘

-- Alternatively, we can use the vss_match macro as a "lateral join"
-- to get the matches already grouped by the left table.
-- Note that this requires us to specify the left table first, and then
-- the vss_match macro which references the search column from the left
-- table (in this case, `search_vec`).
SELECT * FROM needle, vss_match(haystack, search_vec, vec, 3) AS res;

┌─────────────────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│   search_vec    │                                                                                       matches                                                                                        │
│    float[3]     │                                                            struct(score float, "row" struct(id integer, vec float[3]))[]                                                             │
├─────────────────┼──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ [5.0, 5.0, 5.0] │ [{'score': 0.0, 'row': {'id': 365, 'vec': [5.0, 5.0, 5.0]}}, {'score': 1.0, 'row': {'id': 364, 'vec': [5.0, 4.0, 5.0]}}, {'score': 1.0, 'row': {'id': 356, 'vec': [4.0, 5.0, 5.0]}}] │
│ [1.0, 1.0, 1.0] │ [{'score': 0.0, 'row': {'id': 1, 'vec': [1.0, 1.0, 1.0]}}, {'score': 1.0, 'row': {'id': 10, 'vec': [2.0, 1.0, 1.0]}}, {'score': 1.0, 'row': {'id': 2, 'vec': [1.0, 2.0, 1.0]}}]      │
└─────────────────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

Ограничения

• В настоящее время поддерживаются только векторы, состоящие из FLOAT (32-битные, одинарной точности).
• Сам индекс не управляется буфером и должен помещаться в оперативную память.
• Размер индекса в оперативной памяти не учитывается в параметре конфигурации DuckDB memory_limit.
• Индексы HNSW могут быть созданы только для таблиц в базах данных оперативной памяти, если параметр конфигурации SET hnsw_enable_experimental_persistence = ⟨bool⟩ установлен в значение true, см. Сохранение для получения дополнительной информации.
• Макросы таблиц объединения векторов (vss_join и vss_match) не требуют и не используют индекс HNSW.