Add IO prefetch to HNSW graph crawl?
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
In the cold case (KNN vectors don't all fit in RAM), it should help to add prefetching to our HNSW graph crawl?
When we pop the best node out of the work queue, we could ask for all of its neighbor node's vectors to be prefetched before we loop through them evaluating their distance and inserting them into the work queue. We could maybe go further and do so for the top N nodes in the queue. Modern SSDs are typically highly concurrent (maybe 1000s of concurrent requests before they saturate?) so we should use that.
Lucene's prefetch API is very similar to async IO, but maybe not quite as efficient (CPU core will sometimes be more idle with prefetch since Lucene isn't executing immediately as each `WILL_NEED` IO request finishes), but it should still be a big win with HNSW versus not prefetching?
Maybe with virtual threads we could eventually build a "real" async IO solution, but that's a bigger thing.
Or maybe we are already prefetching today in our latest `KnnVectorsFormat` Codec default and I missed it?
Contributor guide
Research direction
Start with the HNSW graph crawl and the latest KnnVectorsFormat Codec default, then compare their current behavior with Lucene's prefetch API. Measure the cold case where KNN vectors do not fit in RAM, including queue depth and SSD concurrency. Done would require a decided prefetch design and evidence that it improves crawl performance without regressing other cases.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100