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.patchdiff --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