HNSW: insertPage rewinds to unfittable deleted slots after VACUUM, causing near-full index scan per insert with variable-size types (sparsevec) — reproduction for #975 #1025

Summary

With variable-size vector types (sparsevec), VACUUM can rewind the HNSW metapage insertPage to a page whose freed slot is too small to ever hold the element being inserted. Because insertPage is chosen before the size check, every subsequent insert of a larger element restarts its page walk from that page and scans the index to the end — turning each insert into a near-full index scan, permanently.

We hit this in production as a 38x regression in per-row insert cost (1,107 → 42,403 buffers/row) starting ~29 hours after the first autovacuum that ever touched a sparsevec HNSW index.

I have a self-contained synthetic reproduction (below, runnable on pgvector/pgvector:pg16) that shows buffers per insert growing 1:1 with index page count, a fixed-size vector negative control that shows no regression, and a verified one-line fix (regression suite passes, 2.2x faster mixed-size insert workload, identical final index size).

This is the same mechanism reported in #975, which was closed for lack of reproducible information. This issue is an attempt to supply exactly that.

Environment

• PostgreSQL 16.13 (AWS Aurora, I/O-Optimized with the tiered read cache enabled — relevant because index misses surface as CPU rather than as BufferIO waits)

• pgvector 0.8.1 in production

• Verified still present on 0.8.5 (pgvector/pgvector:pg16, PostgreSQL 16.14) — src/hnswinsert.c allocation logic is byte-identical between v0.8.1 and v0.8.5:

  $ diff <(curl -sL .../v0.8.1/src/hnswinsert.c) <(curl -sL .../v0.8.5/src/hnswinsert.c)
  # only: #include changes, an unrelated UpdateGraphOnDisk() signature change
  # (efConstruction param removed), and one cast. HnswFreeOffset() and
  # AddElementOnDisk() page-allocation logic: unchanged.
  

Production table (~39M rows) has both a fixed-size vector(1024) column and a sparsevec column, each with its own HNSW index:

The workload is effectively write-only — the sparse index has accumulated 102 idx_scan total.

Symptom

Timeline (relative days):

Per-row insert cost went 1,107 → 42,403 buffers/row (38.3x). Characteristics that ruled out the obvious explanations:

• Uncorrelated with concurrency and with throughput (r ≈ 0 for both).
• Strongly correlated with wall-clock time (r = +0.887) — i.e. it tracks index growth, not load.
• Changing the client batch size (50 → 10 rows per statement) did not change per-row cost.
• Wait-event sampling attributed 99.0% of all CPU wait to this single INSERT statement.

All of that is consistent with "each insert walks a linearly growing number of index pages", and inconsistent with lock contention, plan change, or client-side regression.

Root cause

src/hnswinsert.c, HnswFreeOffset() (v0.8.5 lines 68-69; v0.8.1 lines 62-63):

if (etup->deleted)
{
    BlockNumber elementPage = BufferGetBlockNumber(buf);
    ...
    if (!BlockNumberIsValid(*newInsertPage))
        *newInsertPage = elementPage;      /* <-- claimed BEFORE any size check */
    ...
    pageFree  = ItemIdGetLength(eitemid) + PageGetExactFreeSpace(page);
    npageFree = ItemIdGetLength(nitemid);
    ...
    /* Check for space */
    if (pageFree >= etupSize && npageFree >= ntupSize)   /* <-- v0.8.5 line 103 */
    {
        *freeOffno = offno;
        ...
        return true;
    }

The first deleted element encountered claims *newInsertPage, unconditionally. The size check that decides whether that slot is actually usable happens ~35 lines later. If it fails, the walk continues to the next slot / next page — but newInsertPage is already latched (it is guarded by !BlockNumberIsValid, so it is never revised).

AddElementOnDisk() then writes it back (v0.8.5 lines 345-346, 681-682; v0.8.1 lines 339-340, 675-676):

if (BlockNumberIsValid(newInsertPage) && newInsertPage != insertPage)
    *updatedInsertPage = newInsertPage;
...
if (BlockNumberIsValid(newInsertPage))
    HnswUpdateMetaPage(index, 0, NULL, newInsertPage, MAIN_FORKNUM, building);

Why fixed-size types are immune. For vector(1024), every element tuple is exactly 4,104 B, so any deleted slot always fits. HnswFreeOffset() returns true on the first deleted element it sees and the walk stops immediately. The bug is invisible.

Why sparsevec is not. SPARSEVEC_SIZE(nnz) = 16 + nnz * 8 — element size varies with the number of non-zeros. A slot freed by a small vector cannot hold a large one, so:

1. VACUUM leaves scattered deleted small elements on early pages.
2. An insert of a large element starts at insertPage, hits one of those pages, latches newInsertPage to it, fails the size check, and then walks nextblkno all the way to the end of the index (AddElementOnDisk()'s for (;;) loop) to find room.
3. It writes insertPage back to that early page.
4. Every subsequent large insert repeats the full walk.

Worse: when the rewound insertPage itself contains a deleted element, newInsertPage == insertPage, the newInsertPage != insertPage guard suppresses the metapage write, and the rewind becomes permanent — there is no mechanism that ever advances it again. This matches what the synthetic reproduction below shows (L1 ≈ L2 ≈ L3, sustained).

pgvector never uses the free space map — GetFreeIndexPage / RecordFreeIndexPage / FreeSpaceMap appear 0 times in src/ — so this linear walk is the only page-allocation strategy available.

Related, secondary. AddElementOnDisk() has a second newInsertPage assignment (v0.8.5 lines 199-200):

/* Keep track of first page where element at level 0 can fit */
if (!BlockNumberIsValid(newInsertPage) && PageGetFreeSpace(page) >= minCombinedSize)
    newInsertPage = currentPage;

minCombinedSize is derived from the current element's etupSize, which makes the shared insertPage size-specific: a small insert can legitimately park insertPage on a page that only fits small elements, and the next large insert pays for it. This is a milder version of the same problem and is not addressed by the fix below.

Reproduction

A. Production EXPLAIN, same row content, only nnz varies

Identical dense vector, identical content, only the sparsevec non-zero count differs (44 vs 150). Fresh ids (pure INSERT, no upsert). Each statement run as BEGIN → EXPLAIN (ANALYZE, BUFFERS) → ROLLBACK, in this order:

• 3.3x more non-zeros → 7.6x more pages scanned. The bigger the element, the further it has to walk to find a slot that fits.
• S2 touched ~6 GB of index, entirely buffer hits, zero reads — pure CPU, not I/O. This is the tiered-cache effect that made the incident look like a CPU problem.
• ROLLBACK does not undo the metapage update (index page writes are not transactional here), which is why the ordering of S1–S4 is meaningful and why S3/S4 are cheap.
• In production many backends insert concurrently and each reads and writes insertPage (last-writer-wins), so an individual statement's cost fluctuates depending on where insertPage happens to point at that moment. In the isolated synthetic repro below, the cost is instead sustained.

B. Production element size distribution

pg_column_size() over 18,970 sampled rows of the sparsevec column:

A 2.3x spread between p10 and p90 is enough. Nothing exotic is required — ordinary variance in non-zero count is sufficient to make most deleted slots unusable for most inserts.

C. Self-contained synthetic reproduction

Runs on stock pgvector/pgvector:pg16 with no special setup:

docker run -d --name pgv-repro -e POSTGRES_PASSWORD=pw -e POSTGRES_DB=repro \
  --shm-size=1g pgvector/pgvector:pg16 \
  -c shared_buffers=1GB -c maintenance_work_mem=1GB -c max_parallel_maintenance_workers=4
docker exec -i pgv-repro psql -U postgres -d repro -v nrows=200000 < repro.sql

-- repro.sql
\set ON_ERROR_STOP on
CREATE EXTENSION IF NOT EXISTS vector;
DROP TABLE IF EXISTS items;

-- sparsevec with exactly `nnz` non-zeros, evenly strided so indices are distinct/ascending
CREATE OR REPLACE FUNCTION make_sv(nnz int, dim int, seed bigint)
RETURNS sparsevec LANGUAGE sql IMMUTABLE AS $$
  SELECT ('{' || string_agg(
            ((g - 1) * (dim / nnz) + 1 + (seed % (dim / nnz)))::text || ':' ||
            round((0.1 + ((seed * g) % 991)::numeric / 991.0), 4)::text,
            ',' ORDER BY g)
          || '}/' || dim)::sparsevec
  FROM generate_series(1, nnz) g;
$$;

CREATE TABLE items (
    id        bigserial PRIMARY KEY,
    embedding sparsevec(10000)
) WITH (autovacuum_enabled = off);

-- every row has a SMALL number of non-zeros
INSERT INTO items (embedding)
SELECT make_sv(50, 10000, i) FROM generate_series(1, :nrows) i;

CREATE INDEX items_sparse_hnsw ON items
    USING hnsw (embedding sparsevec_l2_ops) WITH (m = 16, ef_construction = 64);

\echo '### index pages BEFORE vacuum'
SELECT pg_relation_size('items_sparse_hnsw') / 8192 AS index_pages;

\echo '### C0 large insert (nnz=500) BEFORE delete/vacuum'
BEGIN;
EXPLAIN (ANALYZE, BUFFERS, COSTS off, TIMING off)
INSERT INTO items (embedding) VALUES (make_sv(500, 10000, 900001));
ROLLBACK;

-- SCATTERED deletes: every 20th row (5%). This matters -- deleting a contiguous
-- prefix instead frees whole pages, which do fit a large element, and the effect
-- largely disappears. Production deleted 906,375 tuples scattered across 39M rows.
DELETE FROM items WHERE id % 20 = 0;
VACUUM items;

\echo '### index pages AFTER vacuum'
SELECT pg_relation_size('items_sparse_hnsw') / 8192 AS index_pages;

\echo '### L1 large insert (nnz=500), first after vacuum'
BEGIN;
EXPLAIN (ANALYZE, BUFFERS, COSTS off, TIMING off)
INSERT INTO items (embedding) VALUES (make_sv(500, 10000, 900002));
ROLLBACK;

\echo '### L2 large insert (nnz=500), repeat'
BEGIN;
EXPLAIN (ANALYZE, BUFFERS, COSTS off, TIMING off)
INSERT INTO items (embedding) VALUES (make_sv(500, 10000, 900003));
ROLLBACK;

\echo '### S1 small insert (nnz=50)'
BEGIN;
EXPLAIN (ANALYZE, BUFFERS, COSTS off, TIMING off)
INSERT INTO items (embedding) VALUES (make_sv(50, 10000, 900004));
ROLLBACK;

\echo '### L3 large insert (nnz=500), after a small insert'
BEGIN;
EXPLAIN (ANALYZE, BUFFERS, COSTS off, TIMING off)
INSERT INTO items (embedding) VALUES (make_sv(500, 10000, 900005));
ROLLBACK;

Results on stock pgvector 0.8.5 / PostgreSQL 16.14, run at two scales:

The last two rows are the point: buffers − baseline equals the index page count. Every large insert reads the entire index. Doubling the index doubles the per-insert cost (6.5x → 11.4x over baseline), and it stays that way — L2 and L3 are not cheaper than L1.

D. Negative control — fixed-size vector, same procedure

vector(512), 100k rows, HNSW m=16 / ef_construction=64, same scattered 5% delete + VACUUM:

No regression at all, on a larger index. This confirms the problem is specific to variable-size element tuples.

Why this didn't show up earlier

The sparse index was created after the last autovacuum of that table. For the next ~20 days there were plenty of inserts but zero deleted elements in that index, so HnswFreeOffset() never found anything to latch onto and insertPage only ever moved forward. CPU was flat at 1–5%.

The first autovacuum that included the sparse index removed 906,375 tuples and, from that point on, insertPage had somewhere to rewind to. The regression starts ~29 hours later, not immediately, because the walk length grows as insertPage gets pinned progressively further behind the growing tail of the index.

So the trigger is not "many deletes" — it is the first VACUUM after a variable-size HNSW index has grown large. Any deployment that builds a sparsevec HNSW index on a big table and then runs long enough for autovacuum to reach it will eventually hit this.

Relation to #975

#975 describes the same mechanism from the other side: "VACUUM identifies old reusable holes and effectively rewinds insertion toward old pages / subsequent inserts start probing from those old reusable pages." That is exactly what HnswFreeOffset() lines 68-69 do.

It was closed as not actionable for lack of a reproducer. The difference in how it presents is probably why it was hard to pin down:

• In HNSW inserts can spend a long time on BufferIO after VACUUM due to insertPage rewinding to old reusable pages #975 the rewound pages were cold, so the cost appeared as BufferIO waits.
• In our case a tiered read cache keeps them warm, so the identical page walk appears as 100% CPU with zero reads (see S2 above: hit=765,135 read=0).

Same defect, two different-looking symptoms. I'm filing this as a new issue rather than commenting on the closed one, with the reproducer that was missing.

Proposed fix

Latch newInsertPage only for a slot that actually fits. Against v0.8.5:

--- a/src/hnswinsert.c
+++ b/src/hnswinsert.c
@@ -64,9 +64,6 @@ HnswFreeOffset(Relation index, Buffer buf, Page page, HnswElement element, Size
 			ItemId		nitemid;
 			Size		pageFree;
 			Size		npageFree;
-
-			if (!BlockNumberIsValid(*newInsertPage))
-				*newInsertPage = elementPage;
 
 			if (neighborPage == elementPage)
 			{
@@ -102,6 +99,9 @@ HnswFreeOffset(Relation index, Buffer buf, Page page, HnswElement element, Size
 			/* Check for space */
 			if (pageFree >= etupSize && npageFree >= ntupSize)
 			{
+				if (!BlockNumberIsValid(*newInsertPage))
+					*newInsertPage = elementPage;
+
 				*freeOffno = offno;
 				*freeNeighborOffno = neighborOffno;
 				*tupleVersion = etup->version;

When no slot fits, newInsertPage then falls through to the existing size-aware assignment in AddElementOnDisk() (PageGetFreeSpace(page) >= minCombinedSize), which is the intended behavior.

Verification of the fix

Built v0.8.5 unpatched and patched in the same container (postgres:16, OPTFLAGS='') and ran the identical script:

The patch converts a per-insert full index scan into a one-time one. After L1 pays to find room, insertPage points at a page that can actually hold such an element, and subsequent large inserts return to baseline cost.

Regression suite — make installcheck on the patched build: all 14 tests pass, including hnsw_sparsevec, hnsw_vector, hnsw_halfvec, hnsw_bit.

Trade-off measured. The concern with this change is that small deleted slots behind insertPage stop being offered for reuse and are only reclaimed by REINDEX. I tried to measure that cost: 100k rows, 5% scattered delete, VACUUM, then 5,000 inserts alternating nnz=50 / nnz=500:

Identical final index size, 2.2x faster. In this workload the space-reuse regression did not materialize at all — the slots that stop being scanned are the ones that were never usable anyway. That may not hold for every size distribution, so it is worth a second opinion.

A more complete fix would track deleted slots by size class (or use the FSM, which HNSW currently does not touch at all), but that is a larger design change; the one-liner above removes the pathological case.

Happy to supply more data, run variations of the reproduction, or test an alternative patch.