From: YidaWeng (@YidaWeng) <noreply+YidaWeng@github.com>
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Subject: [pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+
Date: Thu, 12 Nov 2026 11:47:14 +0000
Message-ID: <gh-pgvector-pgvector-1063@github.com> (raw)
Use `TidStore` for the HNSW deletion list on Postgres 17+ (this was listed on the [0.9.0 plan](https://github.com/pgvector/pgvector/issues/1042)).
`TidStore` stores deleted element offsets as a bitmap for each index page instead of a hash entry for each TID. This is a big win when pages hold many elements, since the per-page bitmap replaces many hash entries.
The catch is that the bitmap costs about as much as a few hash entries, so it loses for indexes where pages hold only one or two elements. HNSW pages hold one element for 1536-dimensional vectors, and my first version regressed there:
| dims | deleted | hash table | TidStore (ungated) |
|---:|---:|---:|---:|
| 1536 | 10% | 88 KB | 248 KB |
| 1536 | 50% | 280 KB | 584 KB |
So the patch estimates the number of element tuples per page from the entry point tuple (one buffer read, no extra scan) and only uses `TidStore` when a page can hold at least four elements. Other indexes keep the existing hash table, so there is no change for them.
## Benchmarks
Deletion list memory after pass 1 (1M rows, KB, instrumented builds):
| dims | deleted | hash table | TidStore |
|---:|---:|---:|---:|
| 3 | 1% | 152 | 264 |
| 3 | 10% | 1048 | 456 |
| 3 | 50% | 8216 | 1472 |
| 3 | 100% | 16408 | 1472 |
| 128 | 1% | 152 | 312 |
| 128 | 10% | 1048 | 968 |
| 128 | 50% | 8216 | 3008 |
| 128 | 100% | 16408 | 3008 |
| 1536 | 1% | 24 | 24 |
| 1536 | 10% | 88 | 88 |
| 1536 | 50% | 280 | 280 |
The last three rows use the hash table, so they are unchanged. At very low delete fractions the bitmap uses up to ~2x more memory than the hash table (each touched page gets a bitmap), but the absolute difference is small (under 200 KB per 1M rows at 1%).
Pass 1 time is equal or faster (1M rows, 10% deleted): 659 ms -> 616 ms for 3 dimensions and 1821 ms -> 1361 ms for 128 dimensions.
Full `VACUUM` time and peak RSS are within run-to-run noise (200k rows, 10% deleted, release builds):
| dims | time | peak RSS |
|---:|---:|---:|
| 3 | 35.0 s -> 35.4 s | 99.1 MB -> 99.5 MB |
| 128 | 138.8 s -> 141.2 s | 156.7 MB -> 157.4 MB |
## Testing
- `make installcheck`
- TAP tests: `011_hnsw_vacuum`, `014_hnsw_vector_vacuum_recall`, `022_hnsw_bit_vacuum_recall`, `026_hnsw_halfvec_vacuum_recall`, `030_hnsw_sparsevec_vacuum_recall`, `038_hnsw_sparsevec_vacuum_insert`, `046_hnsw_vacuum_scan`, `047_hnsw_vacuum_insert`, and a new `049_hnsw_vacuum_deletion_list` that vacuums indexes with 3 and 500 dimensions (one for each deletion list implementation)
- also ran the TAP tests with assertions enabled
inline patch 1: CHANGELOG.md, src/hnsw.c, src/hnsw.h and 2 more (+215/-15 lines) download inline-1.patchdiff --git a/CHANGELOG.md b/CHANGELOG.mdindex dfce94f52..5e572b5ed 100644--- a/CHANGELOG.md+++ b/CHANGELOG.md@@ -6,6 +6,7 @@
- Improved performance of HNSW inserts with `sparsevec`
- Improved `amvalidate` for indexes
- Improved property testing for indexes
+- Reduced memory usage for HNSW vacuuming for Postgres 17
- Fixed possible error with iterative index scans during HNSW vacuuming
- Dropped support for Postgres 13 and 14
diff --git a/src/hnsw.c b/src/hnsw.cindex 32f431228..3c79c827c 100644--- a/src/hnsw.c+++ b/src/hnsw.c@@ -490,7 +490,7 @@ hnswhandler(PG_FUNCTION_ARGS)
.amcanparallel = false,
.amcanbuildparallel = true,
.amcaninclude = false,
- .amusemaintenanceworkmem = false,+ .amusemaintenanceworkmem = true,
.amsummarizing = false,
.amparallelvacuumoptions = VACUUM_OPTION_PARALLEL_BULKDEL,
.amkeytype = InvalidOid,
@@ -551,7 +551,11 @@ hnswhandler(PG_FUNCTION_ARGS)
amroutine->amcanbuildparallel = true;
#endif
amroutine->amcaninclude = false;
+#if PG_VERSION_NUM >= 170000+ amroutine->amusemaintenanceworkmem = true; /* for the TidStore deletion list */+#else
amroutine->amusemaintenanceworkmem = false; /* not used during VACUUM */
+#endif
#if PG_VERSION_NUM >= 160000
amroutine->amsummarizing = false;
#endif
diff --git a/src/hnsw.h b/src/hnsw.hindex 9ccb2bbf8..5dc3de173 100644--- a/src/hnsw.h+++ b/src/hnsw.h@@ -32,6 +32,18 @@
#include "storage/shmem.h" /* for add_size()/mul_size() in some versions */
#endif
+#if PG_VERSION_NUM >= 170000+#include "access/tidstore.h"++/*+ * Minimum number of element tuples per page for a TidStore deletion list to+ * use less memory than a hash table. TidStore uses a bitmap for each page+ * with deleted elements, which costs about as much as a few hash entries, so+ * it only pays off when pages hold many elements.+ */+#define HNSW_TIDSTORE_MIN_ELEMS 4+#endif+
#ifdef HNSW_BENCH
#include "portability/instr_time.h"
#endif
@@ -466,6 +478,9 @@ typedef struct HnswVacuumState
/* Variables */
struct tidhash_hash *deleting;
+#if PG_VERSION_NUM >= 170000+ TidStore *tidstore;+#endif
BufferAccessStrategy bas;
HnswNeighborTuple ntup;
HnswElementData highestPoint;
diff --git a/src/hnswvacuum.c b/src/hnswvacuum.cindex 2cf4fb5de..075e68545 100644--- a/src/hnswvacuum.c+++ b/src/hnswvacuum.c@@ -15,6 +15,11 @@
#include "varatt.h"
#endif
+#if PG_VERSION_NUM >= 170000+#include "miscadmin.h"+#include "postmaster/autovacuum.h"+#endif+
#if PG_VERSION_NUM >= 200000
#include "commands/progress.h"
#include "utils/backend_progress.h"
@@ -24,13 +29,58 @@
#define vacuum_delay_point() vacuum_delay_point(false)
#endif
+#if PG_VERSION_NUM >= 170000+/*+ * Determine whether a TidStore deletion list uses less memory than a hash+ * table for this index. TidStore stores a bitmap for each page with deleted+ * elements, so it regresses when pages hold too few elements (e.g.+ * high-dimensional vectors). Estimate the element size from the entry point.+ */+static bool+CanUseTidStore(Relation index, HnswElement entryPoint)+{+ Buffer buf;+ Page page;+ ItemId itemid;+ Size tupleSize;+ bool result = false;++ if (entryPoint == NULL || !BlockNumberIsValid(entryPoint->blkno))+ return false;++ buf = ReadBuffer(index, entryPoint->blkno);+ LockBuffer(buf, BUFFER_LOCK_SHARE);+ page = BufferGetPage(buf);++ if (entryPoint->offno >= FirstOffsetNumber &&+ entryPoint->offno <= PageGetMaxOffsetNumber(page))+ {+ itemid = PageGetItemId(page, entryPoint->offno);++ if (ItemIdIsNormal(itemid))+ {+ tupleSize = MAXALIGN(ItemIdGetLength(itemid) + sizeof(ItemIdData));+ result = tupleSize <= HNSW_MAX_SIZE / HNSW_TIDSTORE_MIN_ELEMS;+ }+ }++ UnlockReleaseBuffer(buf);++ return result;+}+#endif+
/*
* Check if deletion list contains an element
*/
static bool
-DeletingElement(tidhash_hash * deleting, ItemPointer indextid)+DeletingElement(HnswVacuumState * vacuumstate, ItemPointer indextid)
{
- return tidhash_lookup(deleting, *indextid) != NULL;+#if PG_VERSION_NUM >= 170000+ if (vacuumstate->tidstore != NULL)+ return TidStoreIsMember(vacuumstate->tidstore, indextid);+#endif+ return tidhash_lookup(vacuumstate->deleting, *indextid) != NULL;
}
/*
@@ -66,6 +116,8 @@ RemoveHeapTids(HnswVacuumState * vacuumstate)
OffsetNumber offno;
OffsetNumber maxoffno;
bool updated = false;
+ OffsetNumber deletedoffs[MaxOffsetNumber];+ int ndeletedoffs = 0;
vacuum_delay_point();
@@ -127,14 +179,8 @@ RemoveHeapTids(HnswVacuumState * vacuumstate)
if (!ItemPointerIsValid(&etup->heaptids[0]))
{
- ItemPointerData indextid;- bool found;-
/* Add to deletion list */
- ItemPointerSet(&indextid, blkno, offno);-- tidhash_insert(vacuumstate->deleting, indextid, &found);- Assert(!found);+ deletedoffs[ndeletedoffs++] = offno;
}
else if (etup->level > highestLevel)
{
@@ -163,6 +209,29 @@ RemoveHeapTids(HnswVacuumState * vacuumstate)
}
}
+#if PG_VERSION_NUM >= 170000+ if (vacuumstate->tidstore != NULL)+ {+ /* Add to deletion list (offsets are in ascending order) */+ if (ndeletedoffs > 0)+ TidStoreSetBlockOffsets(vacuumstate->tidstore, blkno, deletedoffs, ndeletedoffs);+ }+ else+#endif+ {+ for (int i = 0; i < ndeletedoffs; i++)+ {+ ItemPointerData indextid;+ bool found;++ /* Add to deletion list */+ ItemPointerSet(&indextid, blkno, deletedoffs[i]);++ tidhash_insert(vacuumstate->deleting, indextid, &found);+ Assert(!found);+ }+ }+
blkno = HnswPageGetOpaque(page)->nextblkno;
if (updated)
@@ -175,6 +244,10 @@ RemoveHeapTids(HnswVacuumState * vacuumstate)
#ifdef HNSW_MEMORY
elog(INFO, "memory: %zu KB", MemoryContextMemAllocated(CurrentMemoryContext, true) / 1024);
+#if PG_VERSION_NUM >= 170000+ if (vacuumstate->tidstore != NULL)+ elog(INFO, "deleting memory: %zu KB", TidStoreMemoryUsage(vacuumstate->tidstore) / 1024);+#endif
#endif
}
@@ -207,7 +280,7 @@ NeedsUpdated(HnswVacuumState * vacuumstate, HnswElement element)
continue;
/* Check if in deletion list */
- if (DeletingElement(vacuumstate->deleting, indextid))+ if (DeletingElement(vacuumstate, indextid))
{
needsUpdated = true;
break;
@@ -341,7 +414,7 @@ RepairGraphEntryPoint(HnswVacuumState * vacuumstate)
ItemPointerSet(&epData, entryPoint->blkno, entryPoint->offno);
- if (DeletingElement(vacuumstate->deleting, &epData))+ if (DeletingElement(vacuumstate, &epData))
{
/*
* Replace the entry point with the highest point. If highest
@@ -710,7 +783,7 @@ ConfirmRepaired(HnswVacuumState * vacuumstate)
continue;
/* Check if in deletion list */
- if (DeletingElement(vacuumstate->deleting, indextid))+ if (DeletingElement(vacuumstate, indextid))
elog(ERROR, "hnsw graph not repaired");
}
@@ -876,6 +949,9 @@ static void
InitVacuumState(HnswVacuumState * vacuumstate, IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
{
Relation index = info->index;
+#if PG_VERSION_NUM >= 170000+ HnswElement entryPoint;+#endif
if (stats == NULL)
stats = palloc0_object(IndexBulkDeleteResult);
@@ -894,11 +970,35 @@ InitVacuumState(HnswVacuumState * vacuumstate, IndexVacuumInfo *info, IndexBulkD
HnswInitSupport(&vacuumstate->support, index);
- /* Get m from metapage */+ /* Get m and entry point from metapage */+#if PG_VERSION_NUM >= 170000+ HnswGetMetaPageInfo(index, &vacuumstate->m, NULL, &entryPoint);+#else
HnswGetMetaPageInfo(index, &vacuumstate->m, NULL, NULL);
+#endif++ /* Create deletion list */+#if PG_VERSION_NUM >= 170000+ vacuumstate->deleting = NULL;+ vacuumstate->tidstore = NULL;++ if (CanUseTidStore(index, entryPoint))+ {+ int workMem;- /* Create hash table */+ /* Like other index types, use autovacuum_work_mem if set */+ if (AmAutoVacuumWorkerProcess() && autovacuum_work_mem != -1)+ workMem = autovacuum_work_mem;+ else+ workMem = maintenance_work_mem;++ vacuumstate->tidstore = TidStoreCreateLocal((Size) workMem * 1024, true);+ }+ else+ vacuumstate->deleting = tidhash_create(CurrentMemoryContext, 256, NULL);+#else
vacuumstate->deleting = tidhash_create(CurrentMemoryContext, 256, NULL);
+#endif
}
/*
@@ -907,7 +1007,14 @@ InitVacuumState(HnswVacuumState * vacuumstate, IndexVacuumInfo *info, IndexBulkD
static void
FreeVacuumState(HnswVacuumState * vacuumstate)
{
+#if PG_VERSION_NUM >= 170000+ if (vacuumstate->tidstore != NULL)+ TidStoreDestroy(vacuumstate->tidstore);+ else+ tidhash_destroy(vacuumstate->deleting);+#else
tidhash_destroy(vacuumstate->deleting);
+#endif
pfree(vacuumstate->ntup);
MemoryContextDelete(vacuumstate->tmpCtx);
}
diff --git a/test/t/049_hnsw_vacuum_deletion_list.pl b/test/t/049_hnsw_vacuum_deletion_list.plnew file mode 100644index 000000000..08fc5d8b5--- /dev/null+++ b/test/t/049_hnsw_vacuum_deletion_list.pl@@ -0,0 +1,73 @@+use strict;+use warnings FATAL => 'all';+use PostgreSQL::Test::Cluster;+use PostgreSQL::Test::Utils;+use Test::More;++# Test VACUUM for indexes where pages hold many elements and where they hold+# few elements. This exercises both the TidStore and hash table deletion lists+# on Postgres 17+.++my $node = PostgreSQL::Test::Cluster->new('node');+$node->init;+$node->start;++$node->safe_psql("postgres", "CREATE EXTENSION vector;");++for my $dim (3, 500)+{+ my $table = "tst$dim";+ my $array_sql = join(", ", ('random()') x $dim);++ # Create table and index+ $node->safe_psql("postgres", "CREATE TABLE $table (i int4, v vector($dim));");+ $node->safe_psql("postgres", "ALTER TABLE $table SET (autovacuum_enabled = false);");+ $node->safe_psql("postgres",+ "INSERT INTO $table SELECT i, ARRAY[$array_sql] FROM generate_series(1, 2000) i;"+ );+ $node->safe_psql("postgres", "CREATE INDEX ON $table USING hnsw (v vector_l2_ops);");++ # Delete some elements and update others (the old heap TIDs become dead)+ $node->safe_psql("postgres", "DELETE FROM $table WHERE i % 3 = 0;");+ $node->safe_psql("postgres", "UPDATE $table SET v = v WHERE i % 5 = 0;");++ $node->safe_psql("postgres", "VACUUM $table;");++ # Check that index scans do not return deleted elements+ my $deleted = $node->safe_psql("postgres", qq(+ SET enable_seqscan = off;+ SET hnsw.ef_search = 100;+ SELECT count(*) FROM (+ SELECT i FROM $table ORDER BY v <-> (SELECT v FROM $table WHERE i = 1) LIMIT 10+ ) s WHERE i % 3 = 0;+ ));+ is($deleted, 0, "no deleted elements with $dim dimensions");++ # Check recall of index scans+ my $expected = $node->safe_psql("postgres", qq(+ SET enable_indexscan = off;+ SELECT string_agg(i::text, ',' ORDER BY i) FROM (+ SELECT i FROM $table ORDER BY v <-> (SELECT v FROM $table WHERE i = 1) LIMIT 10+ ) s;+ ));+ my @expected_ids = split(",", $expected);++ my $actual = $node->safe_psql("postgres", qq(+ SET enable_seqscan = off;+ SET hnsw.ef_search = 1000;+ SELECT string_agg(i::text, ',' ORDER BY i) FROM (+ SELECT i FROM $table ORDER BY v <-> (SELECT v FROM $table WHERE i = 1) LIMIT 10+ ) s;+ ));+ my %actual_set = map { $_ => 1 } split(",", $actual);++ my $correct = 0;+ foreach (@expected_ids)+ {+ $correct++ if (exists($actual_set{$_}));+ }++ cmp_ok($correct / scalar(@expected_ids), ">=", 0.9, "recall with $dim dimensions");+}++done_testing();