Prefetch unvisited neighbors during HNSW search - #1020
Manuelreyesbravo wants to merge 1 commit into
Conversation
HnswLoadUnvisitedFromDisk fills the unvisited array with the tid of every neighbor the search is about to consider, so their block numbers are all known before the first one is read. The loop that follows reads them one at a time, waiting on each. Issuing those reads up front lets them overlap. Measured on 38,352 vector(768) rows with a 145 MB HNSW index. Each run is 300 searches with a different query vector every time (pgbench), so the working set is the whole index rather than one repeated path. Two prebuilt binaries are swapped between runs, A/B order alternated between rounds, page cache dropped identically before each run, and PostgreSQL is confined to a memory cgroup so that reads actually reach the disk (~56 us each) instead of the host page cache (~3 us): memory available without with 200 MB 14.9 ms 8.0 ms 1.9x 350 MB 5.03 ms 4.96 ms no difference fully resident 0.756 ms 0.737 ms no difference It helps when I/O dominates, and stays out of the way when it does not. Skipped on the in-memory path, where there are no buffers to fetch. This is a hint and not a read: no pin, no lock, nothing to release, so it cannot change what the scan visits. Buffer reads and hits are identical with and without it, and the 50 nearest neighbors come back identical, in the same order. Worth noting where this does NOT pay off: the same change in a quantized graph index (pgvectorscale's DiskANN, ~0.7 KB per vector) measured as noise, because many neighbors share one 8 KB page and there is little left to overlap. HNSW stores the full vector, so each element takes close to a page of its own and a neighborhood is that many independent reads. make installcheck: 14/14.
|
I should have read your branches before opening this. You already wrote this Setup: 38,352 One correction was needed first:
That gap is mostly not about read streams. It is the ramp-up. A stream starts at
(absolute numbers in that pair are inflated — something else was using the disk. So with a one-line change your branch lands within 14% of this patch, and at I also re-ran the head-to-head under All versions read the identical set of pages — 585 hits, 278 reads, to the block — One thing I got wrong along the way, in case it saves you time: I assumed the Correction to an earlier version of this comment: I first described Caveats: one machine, one dataset, one index size, one |
|
Hi @Manuelreyesbravo, thanks for sharing. Will try out |
|
Here's what I'm seeing on Postgres 19 with 1M 1536-dimension vectors, 100 queries, and a cold page cache:
|
|
Thanks for taking the time to test this. First, a correction to my earlier comment: I said I checked it with a build that logs the distance: on one query (49 hops) the distance grew to 32-90 within each hop, and That is one of two limits behind the gap:
Fixing either one alone barely helps; fixing both closes most of the gap: PG 19beta4 (-O2), 500k random vectors of 1536 dimensions, default HNSW parameters, 100 queries after a cold start, io_uring, median of 9-14 runs (master 5; runs disturbed by other load on the machine dropped). First column on a local NVMe, second with 1 ms added to every read (dm-delay):
On the fast disk the fix closes less of the gap, since the per-I/O cost of the stream matters more there. With Separately, I tried also prefetching the unvisited neighbors of the next two candidates while the current hop's reads are in flight, so hops overlap: 1.06 s / 5.5 s, for 9% more reads, and the same on PG 18. It works with either approach, so I've kept it out of this PR; happy to open it separately if it seems worth it. Caveats: random vectors, one machine, default |
|
Thanks @Manuelreyesbravo, seeing slightly better performance with If going the prefetch route, I think we'll need to limit by |
|
Thanks, you're right that the limit matters, and it changes the picture. I added it the way the hnsw-prefetch comment suggests: at most Same setup as before (500k x 1536, io_uring), a new run pinned to one CCX, so the numbers differ slightly from my previous table; local NVMe / +1 ms per read, median of 10-14 runs:
So at the default eic, the PR's advantage came from ignoring effective_io_concurrency; with the limit it is about even with the read stream + pause. At eic 64 the limit makes no difference, as you said. On the remaining gap at eic 64: the backend uses about twice the system time with the read stream, and that part is io_uring handing reads to its worker threads. One thing that does help the read stream: while the current hop's reads are in flight, prefetching the unvisited neighbors of the next two candidates, using only what is left of the eic budget after the hop's own reads. In a separate run at eic 64 and +1 ms (so slightly different numbers from the table), that took Given that the two are about even at the default setting, and the read stream gets AIO and I/O accounting from core, I think the read stream with |
|
Thanks for the additional numbers. fwiw, I'm not seeing a difference between Re "prefetching the unvisited neighbors of the next two candidates": the next two candidates may not be visited, which would cause unnecessary prefetches. |
|
Thanks, that fits: with the pause fix the distance is kept between hops, so without FULL it only has to ramp up once per layer. And yes, some look-ahead prefetches are wasted. The search reads the same blocks either way, so every extra read is one: in that run 5.2k extra over 67k (8%). It only spends what's left of the eic budget, but if the waste isn't worth it, I'd leave it out. |
2 participants
HnswLoadUnvisitedFromDiskfills theunvisitedarray with the tid of every neighbor the search is about to consider, so their block numbers are all known before the first one is read. The loop right after reads them one at a time, waiting on each. This asks for them up front so the reads can overlap.The whole change is one loop, guarded to the on-disk path:
When it helps, and when it does not
38,352
vector(768)rows, 145 MB HNSW index, PostgreSQL 19beta2. Each run is 300 searches with a different query vector every time (pgbench), so the working set is the whole index rather than one repeated path.It helps when I/O dominates and stays out of the way when it does not. I could not measure a cost in the resident case; HNSW visits few enough nodes that the extra calls disappear into the noise.
Method
Getting this to measure anything real took three attempts, so the details matter:
git stashsilently stashes nothing and you end up timing one binary against itself.An earlier version of this measurement dropped the page cache before every query and reported 3.5x. That simulates "every search is the first one after a reboot" and overstates the effect by about two times. The 1.9x above is the number that survives a realistic workload.
Correctness
make installcheck: 14/14, includinghnsw_vector,hnsw_halfvec,hnsw_bit,hnsw_sparsevec.diffbetween the two builds.PrefetchBufferis a hint and not a read: no pin, no lock, nothing to release, so it cannot change what the scan visits.Where this does not pay off
I tried the same change in a quantized graph index (pgvectorscale's DiskANN, ~0.7 KB per vector) and it measured as noise. With quantization many neighbors share one 8 KB page, so asking for sixteen of them is three or four reads, not sixteen. HNSW stores the full vector, each element takes close to a page of its own, and a neighborhood really is that many independent reads. That seems to be the condition for this to be worth anything.
Caveats
One machine, one dataset, one index size.
ivfscan.chas the same shape and is untouched here. Happy to run whatever else would make this easier to evaluate — different dimensions,m,ef_search, or a larger corpus.