pgvector вглубь: векторный поиск внутри PostgreSQL

pgvector 0.8.7 в PostgreSQL 17 на 523 тысячах эмбеддингов против истины точного перебора: HNSW и IVFFlat с ручками и размером, нехватка maintenance_work_mem при построении, оператор не того класса — и запрос молча идёт перебором, фильтр WHERE, который тает выдачу до нуля, итеративное сканирование и его потолок, B-tree рядом с HNSW и общий план подготовленного запроса, при котором EXPLAIN показывает одно, а выполняется другое. Плюс halfvec и битовые коды: почему знаковая квантизация e5 теряет треть соседей и как это лечит вычитание среднего вектора.

В предыдущей статье алгоритмы ANN разбирались без СУБД: своя HNSW, IVF и квантизация на том же корпусе, с истиной точного перебора. Теперь те же алгоритмы внутри PostgreSQL. pgvector добавляет тип vector, операторы расстояния и два индекса — HNSW и IVFFlat — и оставляет эмбеддинги в той же базе, что и остальные данные: те же транзакции, тот же бэкап, тот же SQL.

Цена этого — поведение планировщика и исполнителя PostgreSQL, которое у выделенного движка устроено иначе. Ниже — что именно меняется, когда ANN-индекс становится одним из путей доступа в плане запроса, и в каких местах recall падает без единой ошибки в логе.

Стенд: digital-cookbook/vector-databases/pgvector, датасет серии — digital-cookbook/vector-databases/dataset.

Инженерная схема в стиле «Полдень. XXI век»: просторный цех архива с рядами высоких картотечных шкафов. Конвейер выносит из машины слева оранжевые перфокарты; у стрелки со светофором поток делится — одна карта уходит в выдвинутый ящик картотеки, другая поднимается к сети связанных узлов над шкафами, где оранжевый пунктир отмечает её место в графе. Вертикальные штрихи соединяют узлы графа со шкафами внизу. В правом нижнем углу вставка: полосатая лента вектора сжимается в короткий брусок — компактное представление

В статье

Стенд и контроль

PostgreSQL 17 и pgvector 0.8.7 в Docker (образ закреплён по дайджесту), shared_buffers 1 ГБ, max_parallel_maintenance_workers 4. Корпус и истина — те же, что в первой статье: BEIR Quora, 522 931 документ, эмбеддинги multilingual-e5-small (384 измерения, нормированы), 1000 тестовых запросов с точным top-100. Таблица одна:

CREATE TABLE docs (id int PRIMARY KEY, bucket int NOT NULL,
                   embedding vector(384) NOT NULL, embedding_h halfvec(384) NOT NULL);

id — номер документа в корпусе, как в истине. bucket — синтетическая метка от 0 до 999 для опытов с фильтром: (id · 2654435761) mod 1000, равномерно и без связи со смыслом текста, так что bucket < 10 оставляет ровно 1% корпуса.

Замеры делает vbench на Go (pgx 5.11 и pgvector-go 0.4.1): запросы по одному на одном соединении, ANN recall@10 против истины (доля точной десятки, а не релевантность по разметке). Каждая серия запросов сначала проходит один раз без замера: индекс HNSW занимает около гигабайта, больше shared_buffers, и первая серия после построения иначе мерила бы чтение с диска. Это выяснилось в первой сессии — p50 при самом малом ef_search вышел вдвое больше, чем при следующем.

Контроль — точный перебор в SQL с выключенными индексами против истины датасета:

$ python3 scripts/run-exact.py control
{"variant": "control", "outcome": "match", "detail": "выдача совпала с истиной на 200 запросах из 200, ещё 0 — почти равные скоры на границе десятки; 225 мс на запрос"}

Полный перебор 523 тыс. векторов в PostgreSQL — около четверти секунды на запрос (параллельный Seq Scan и сортировка). С этим числом дальше сравнивается всё остальное.

HNSW в pgvector

CREATE INDEX docs_hnsw ON docs USING hnsw (embedding vector_ip_ops)
    WITH (m = 16, ef_construction = 200);
SET hnsw.ef_search = 40;
SELECT id FROM docs ORDER BY embedding <#> $1 LIMIT 10;

Те же ручки, что в первой статье: m и ef_construction при построении, hnsw.ef_search — на запросе, без перестройки индекса.

hnsw.ef_search ANN recall@10 p50, мкс p99, мкс
10 0,942 384 773
20 0,971 549 2837
40 0,983 729 1194
80 0,988 1171 1906
160 0,994 2200 3815
400 0,997 4220 6492

Своя HNSW из первой статьи с теми же m и ef_construction давала при ef = 40 recall 0,972; pgvector — 0,983. Граф pgvector не хуже, и в нём те же решения, что у Faiss: новому узлу на нижнем слое — до 2·m соседей.

Размер. Индекс занимает 1020 МБ при 766 МБ самих векторов. HNSW в pgvector хранит в страницах индекса копию каждого вектора рядом со списками соседей — поиск не ходит в таблицу за векторами, пока обходит граф. Значит, чтобы поиск не читал диск, в памяти должны жить не векторы таблицы, а индекс: для 523 тыс. векторов размерности 384 — около гигабайта.

maintenance_work_mem. Построение HNSW держит граф в памяти обслуживания. Если граф перестаёт помещаться, pgvector предупреждает и продолжает строить медленнее — индекс получается тот же:

$ python3 scripts/run-hnsw.py mwm64mb
{"variant": "mwm64mb", "outcome": "match", "detail": "построение 384 с; hnsw graph no longer fits into maintenance_work_mem after 28362 tuples; recall@10 0.985 при ef_search 40"}
$ python3 scripts/run-hnsw.py compare
{"variant": "compare", "outcome": "match", "detail": "построение 384 с против 123 с (в 3.1 раза дольше), recall@10 при ef_search 40: 0.985 против 0.983"}

С 64 МБ граф перестал помещаться уже после 28 362 строк из 522 931, и построение заняло 384 с вместо 123 с. Recall при том же ef_search не изменился — платится только время построения. Предупреждение приходит как NOTICE: в логе сервера его нет на уровне по умолчанию, увидеть его можно только в клиенте, который выполнял CREATE INDEX.

IVFFlat

CREATE INDEX docs_ivf ON docs USING ivfflat (embedding vector_ip_ops) WITH (lists = 723);
SET ivfflat.probes = 8;
ivfflat.probes ANN recall@10 p50, мс p99, мс
1 0,500 0,3 0,8
2 0,639 0,5 0,9
4 0,734 0,9 1,6
8 0,806 1,7 2,5
16 0,865 3,1 4,5
32 0,909 5,9 8,0
64 0,947 12,4 15,1
128 0,974 26,4 31,6

Кривая почти та же, что у своей IVF-Flat из первой статьи (0,520 / 0,808 / 0,947 при 1 / 8 / 64 ячейках): k-means в pgvector обучается на своей выборке строк таблицы, поэтому ячейки чуть другие. Построение — 15 с против 123 с у HNSW, но recall 0,97 стоит 128 ячеек и 26 мс на запрос — у HNSW такой recall уже при ef_search = 20, меньше чем за миллисекунду. IVFFlat обучает центроиды по строкам, которые есть в таблице на момент CREATE INDEX: построенный на пустой или нерепрезентативной таблице, он даёт перекос списков, разобранный в первой статье.

Оператор и класс индекса

У индекса есть класс операторов: vector_ip_ops обслуживает только <#> (отрицательное скалярное произведение), vector_cosine_ops — <=>, vector_l2_ops — <->. Запрос с другим оператором ошибки не даёт — он просто не может использовать индекс:

оператор метрика план ANN recall@10 p50, мс
<#> скалярное произведение Limit → Index Scan using docs_hnsw on docs 0,994 0,7
<=> косинусное расстояние Limit → Gather Merge → Sort → Parallel Seq Scan on docs 1,000 240,4
<-> L2 Limit → Gather Merge → Sort → Parallel Seq Scan on docs 0,999 239,2

Здесь 100 запросов, а не 1000, поэтому recall у <#> чуть другой, чем в таблице HNSW выше. На нормированных векторах все три оператора дают один и тот же порядок (это проверено в первой статье), поэтому recall у запросов мимо индекса — около единицы, с расхождениями только на почти равных скорах: это точный перебор, в сотни раз медленнее. Отличить такой запрос можно только по плану: Parallel Seq Scan вместо Index Scan using docs_hnsw. Если векторы нормированы, vector_ip_ops и <#> — самая дешёвая пара; главное — чтобы оператор в запросе и класс индекса совпадали.

Фильтр WHERE и ANN

SELECT id FROM docs WHERE bucket < $2 ORDER BY embedding <#> $1 LIMIT 10;

Индекс HNSW ничего не знает о bucket. Исполнитель берёт из индекса ef_search ближайших кандидатов, и фильтр отбрасывает те, что не подходят. При ef_search = 40 и фильтре на 10% корпуса до LIMIT доходит в среднем четыре строки — ровно то, о чём предупреждает README pgvector. С версии 0.8 есть итеративное сканирование: если после фильтра строк не хватило, обход графа продолжается.

проходит фильтр строк в срезе итеративное сканирование строк на запрос ANN recall@10 p50, мс
50% 261 464 выключено 10,00 0,980 0,5
50% 261 464 relaxed_order 10,00 0,980 0,5
50% 261 464 strict_order 10,00 0,980 0,5
10% 52 294 выключено 3,84 0,384 0,5
10% 52 294 relaxed_order 10,00 0,971 1,6
10% 52 294 strict_order 10,00 0,946 2,0
1% 5230 выключено 0,36 0,035 0,5
1% 5230 relaxed_order 10,00 0,961 12,9
1% 5230 strict_order 10,00 0,916 13,4
0,1% 523 выключено 0,01 0,001 0,5
0,1% 523 relaxed_order 10,00 0,670 30,4
0,1% 523 strict_order 10,00 0,663 30,2

Три режима, четыре доли корпуса, проходящие фильтр, — от половины до 0,1%:

  • Без итеративного сканирования выдача тает вместе с долей: 3,84 строки при 10%, 0,36 при 1%, почти ноль при 0,1%. Ошибки нет: запрос честно вернул то, что прошло фильтр из 40 кандидатов.
  • relaxed_order добирает 10 строк при любой доле, но цена растёт: при 1% — 13 мс на запрос и recall 0,961.
  • strict_order обещает строгий порядок по расстоянию и за это отбрасывает часть найденного: recall ниже, чем у relaxed, на каждой доле от 10% и уже (0,916 против 0,961 при 1%). Если нужен строгий порядок, документация pgvector советует relaxed плюс пересортировку во внешнем запросе.
  • При 0,1% (523 строки на корпус) оба итеративных режима возвращают 10 строк, но recall — две трети: обход останавливается на пределе hnsw.max_scan_tuples (20 000 просмотренных узлов по умолчанию), так и не дойдя до настоящих соседей внутри среза. Строк ровно столько, сколько просили, — и треть из них не те.

Для узкого фильтра граф — неподходящий путь: в срезе из 523 строк точный перебор занимает доли миллисекунды. Это следующий опыт.

B-tree рядом с HNSW и общий план

Добавим обычный индекс по метке:

CREATE INDEX docs_bucket ON docs (bucket);

Теперь у планировщика два пути: HNSW с фильтром после обхода или B-tree по bucket, точный перебор найденных строк и сортировка. При 0,1% EXPLAIN выбирает второй путь — и показывает именно его. А выдача та же, что без B-tree:

индексы plan_cache_mode EXPLAIN с b = 1 (0,1%) общий план строк на запрос ANN recall@10
HNSW auto Limit → Index Scan using docs_hnsw on docs Limit → Index Scan using docs_hnsw on docs 0,01 0,001
HNSW и B-tree auto Limit → Sort → Bitmap Heap Scan on docs → Bitmap Index Scan on docs_bucket Limit → Index Scan using docs_hnsw on docs 0,01 0,001
HNSW и B-tree force_custom_plan Limit → Sort → Bitmap Heap Scan on docs → Bitmap Index Scan on docs_bucket Limit → Index Scan using docs_hnsw on docs 10,00 1,000

Причина — подготовленные запросы. vbench, как большинство драйверов (pgx, JDBC и другие), выполняет запрос через Parse/Bind: текст с $1 и $2 готовится один раз. Первые пять выполнений PostgreSQL планирует под конкретные значения параметров (частный план) — B-tree при 0,1%. Затем, если общий план (generic plan) по оценке не дороже среднего частного, запрос переходит на него. В общем плане значение $2 неизвестно, и планировщик закладывает типичную селективность — HNSW. EXPLAIN с подставленными значениями показывает частный план, а выполняется общий. Отсюда 0,01 строки на запрос в среднем — как без B-tree: пять выполнений с частным планом пришлись на прогревочный проход серии, и все замеренные запросы шли уже по общему. В первой сессии, до прогрева, эти пять запросов попадали в замер и давали по 10 строк.

EXPLAIN (GENERIC_PLAN) (PostgreSQL 16+) показывает общий план без значений — стенд записывает и его. Лечение — любой способ получить частный план на каждое выполнение:

  • SET plan_cache_mode = force_custom_plan для сессии или роли — в стенде это 10 строк, recall 1 и меньше миллисекунды при 0,1%;
  • литерал вместо параметра для селективного условия;
  • отдельный запрос (или частичный индекс WHERE bucket < 10) для заведомо узких срезов.

Ловушка не специфична для pgvector, но с ANN-индексом она особенно тихая: и EXPLAIN, и запрос выглядят правильно, а recall — около нуля.

halfvec и битовые коды

Индекс HNSW — около гигабайта на 523 тыс. векторов, и почти всё в нём — копии векторов. pgvector умеет хранить в индексе меньше:

  • halfvec — 2 байта на координату вместо 4. Колонка embedding_h halfvec(384) и индекс halfvec_ip_ops.
  • битовые коды — индекс по выражению binary_quantize(embedding)::bit(384): бит на координату (знак), расстояние Хэмминга <~>. Кандидаты по коду, затем пересчёт по исходным векторам:
SELECT id FROM (SELECT id, embedding FROM docs
                ORDER BY binary_quantize(embedding)::bit(384) <~> binary_quantize($1::vector)
                LIMIT 1000) t
ORDER BY embedding <#> $1 LIMIT 10;
индекс размер, МБ построение, с точка ANN recall@10 p50, мс
HNSW по vector(384) 1020 123 ef_search 40 0,983 0,7
HNSW по vector(384) 1020 123 ef_search 160 0,994 2,2
HNSW по halfvec(384) 583 98 ef_search 40 0,983 0,6
HNSW по halfvec(384) 583 98 ef_search 160 0,993 1,5
HNSW по знаковому коду bit(384) 174 61 пересчёт 10 0,119 0,3
HNSW по знаковому коду bit(384) 174 61 пересчёт 100 0,396 1,4
HNSW по знаковому коду bit(384) 174 61 пересчёт 1000 0,619 12,0
HNSW по коду после центрирования 174 50 пересчёт 10 0,597 0,4
HNSW по коду после центрирования 174 50 пересчёт 100 0,946 1,4
HNSW по коду после центрирования 174 50 пересчёт 1000 0,993 11,6

halfvec — почти бесплатная экономия: индекс меньше в 1,75 раза при том же recall. Битовые коды без подготовки разочаровывают: индекс меньше почти в шесть раз, но даже пересчёт 1000 кандидатов возвращает только 0,619.

Почему знаковый код теряет соседей. Точный перебор по Хэммингу без всякого индекса отделяет потерю самого кода от потери графа:

код координат с одним знаком у 90% документов и больше пересчёт 10 пересчёт 100 пересчёт 1000
знак координаты 279 0,250 0,481 0,696
знак после вычитания среднего 0 0,652 0,962 0,993

У 279 из 384 координат e5-small знак одинаков у 90% документов и больше. Такой бит почти ничего не различает: у всех документов он один и тот же. Код из 384 бит работает как код из сотни с небольшим. Модели эмбеддингов, которые обучали под бинарную квантизацию, центрируют выход сами; e5 — нет.

Лечение — вычесть средний вектор корпуса перед взятием знака. В pgvector это индекс по выражению с константой:

CREATE INDEX docs_bin ON docs USING hnsw
    ((binary_quantize(embedding - '[…средний вектор…]'::vector)::bit(384)) bit_hamming_ops);

Запрос обязан содержать то же выражение дословно — иначе PostgreSQL не узнает его и пойдёт мимо индекса. После центрирования ни у одной координаты нет перекоса, индекс того же размера, а пересчёт 1000 кандидатов даёт 0,993. Средний вектор считается один раз по корпусу; если распределение данных со временем сдвигается, его пересчитывают вместе с перестройкой индекса.

Та же выдача из Java

Те же 200 запросов при hnsw.ef_search = 40 через JDBC (pgJDBC 42.7.14 и pgvector-java 0.1.6):

$ python3 scripts/run-java.py jdbc
{"variant": "jdbc", "outcome": "match", "detail": "выдача совпала id в id на 200 запросах из 200"}

Поиск по одному и тому же индексу с одними параметрами детерминирован: выдача не зависит от драйвера и языка, recall, измеренный на одном клиенте, переносится на другой.

Где pgvector упирается

По числам стенда:

  • Память. Индекс HNSW хранит копию векторов: 1020 МБ на 766 МБ векторов. Чтобы поиск держал доли миллисекунды, индекс должен помещаться в кеш вместе с рабочим набором остальной базы. halfvec сокращает это в 1,75 раза почти без потерь, центрированные битовые коды — почти в 6 раз с пересчётом.
  • Построение. 123 с на 523 тыс. векторов при достаточной maintenance_work_mem и втрое дольше без неё; построение конкурирует с рабочей нагрузкой за ЦП и память.
  • Фильтры. Узкие срезы — слабое место графа: без итеративного сканирования выдача тает, с ним — дорожает и упирается в hnsw.max_scan_tuples. B-tree рядом с HNSW помогает только при частных планах.
  • Один узел. Масштабирование — вертикальное и через реплики чтения; шардинг векторного индекса pgvector не делает.

Как то же самое выглядит в движках, которые построены вокруг векторного поиска, — в статье Qdrant, Milvus, Weaviateготовится, с 24 ноября; фильтрация и консистентность при обновлениях — в фильтрации и метаданныхготовится, с 10 декабря.

Как повторить

cd vector-databases/dataset && python3 scripts/make-dataset.py
cd ../pgvector && bash scripts/run-all.sh

Датасет собирается один раз для всей серии. Полный прогон стенда — около 40 минут. Одна ось — python3 scripts/run-filter.py. Гипотезы записаны в expected.json до прогона; две из них не устояли, и это там же: B-tree «сам спасает» узкий фильтр только при частных планах, а знаковые коды без центрирования теряют треть соседей даже с пересчётом.

Итог

  • HNSW в pgvector по recall не уступает эталонным реализациям, но его индекс хранит копию векторов — в памяти должен жить именно он.
  • Оператор запроса и класс индекса обязаны совпадать: иначе тот же запрос идёт полным перебором, без ошибки.
  • WHERE применяется после обхода графа: без итеративного сканирования выдача тает, с ним — дорожает, а на совсем узких срезах упирается в предел просмотренных узлов.
  • Подготовленный запрос может выполняться не по тому плану, что показывает EXPLAIN: для селективных условий нужен частный план.
  • halfvec — почти бесплатное сжатие индекса; битовые коды — только после центрирования векторов.

Документация и первоисточники

Обсуждение в Telegram

Присоединиться →