pg.ddx.io pgvector/pgvector GitHub issues and pull requests
help / color / mirror / Atom feed[pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+
4+ messages / 2 participants
[nested] [flat]
* [pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+
@ 2026-11-12 11:47 "YidaWeng (@YidaWeng)" <noreply+YidaWeng@github.com>
0 siblings, 0 replies; 4+ messages in thread
From: YidaWeng (@YidaWeng) @ 2026-11-12 11:47 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
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.patch
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 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.c
index 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.h
index 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.c
index 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.pl
new file mode 100644
index 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();
^ permalink raw [nested|flat] 4+ messages in thread
* Re: [pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+
@ 2026-11-12 19:24 ` "ankane (@ankane)" <noreply+ankane@github.com>
2 siblings, 0 replies; 4+ messages in thread
From: ankane (@ankane) @ 2026-11-12 19:24 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @YidaWeng, there's [a branch](https://github.com/pgvector/pgvector/compare/hnsw-tidstore2) for this as well (PRs are not needed for anything in #1042).
^ permalink raw [nested|flat] 4+ messages in thread
* Re: [pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+
@ 2026-11-12 19:24 ` "ankane (@ankane)" <noreply+ankane@github.com>
2 siblings, 0 replies; 4+ messages in thread
From: ankane (@ankane) @ 2026-11-12 19:24 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
@ankane closed this.
^ permalink raw [nested|flat] 4+ messages in thread
* Re: [pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+
@ 2026-11-13 06:46 ` "YidaWeng (@YidaWeng)" <noreply+YidaWeng@github.com>
2 siblings, 0 replies; 4+ messages in thread
From: YidaWeng (@YidaWeng) @ 2026-11-13 06:46 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Thanks, I missed `hnsw-tidstore2` — closing this.
A few things I hit while testing that branch, in case they are useful for it:
1. `TidStoreSetBlockOffsets()` is called even when `ndeletedoffs == 0`, which trips `Assert(num_offsets > 0)` in assert-enabled builds. A `ndeletedoffs > 0` guard fixes it.
2. `TidStoreCreateLocal()` takes bytes, but the branch passes the GUC value in kB, so the limit ends up 1024x too small.
3. Using TidStore unconditionally regresses high-dimensional indexes. With `vector(1536)` a page holds one element, so the per-page bitmap costs more than the hash entries: at 50k rows, 10% deleted went from 88 KB to 248 KB and 50% deleted from 280 KB to 584 KB. I only use TidStore when a page can hold at least 4 element tuples (estimated from the entry point tuple) and keep the hash table otherwise.
With that gate, 1M rows at 50% deleted: 3d 8216 KB -> 1472 KB, 128d 8216 KB -> 3008 KB, and 1536d unchanged. Full VACUUM time and peak RSS were neutral. More numbers are in the PR description if they are helpful.
^ permalink raw [nested|flat] 4+ messages in thread
end of thread, other threads:[~2026-11-13 06:46 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-11-12 11:47 [pgvector/pgvector] PR #1063: Switched to TidStore for HNSW vacuuming for Postgres 17+ "YidaWeng (@YidaWeng)" <noreply+YidaWeng@github.com>
2026-11-12 19:24 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-12 19:24 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-13 06:46 ` "YidaWeng (@YidaWeng)" <noreply+YidaWeng@github.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox