shbhar commented on issue #16906: URL: https://github.com/apache/lucene/issues/16906#issuecomment-6611439320
Nice work @Tony-X! I did not know about this paper but had tried a similar approach for both merges and graph creation at flush time but using ordinary NN-descent based on the ideas in [#12440](https://github.com/apache/lucene/issues/12440) (there is a lot of discussion on this topic there including how/if we should use existing segments or graphs for a warm start during merges, etc.) and a comment from @benwtrent in https://github.com/apache/lucene/issues/15773#issuecomment-4045988157 about not using the normal incremental hnsw building approach even outside merges but simply build on flush in batch (which immediately clicked for me - we can exploit Lucene's segment based design for this case!) So in my POC I tried to implement both merges and "batch build on flush" using NN-descent, and it makes sense to me to do both together since they can share the same implementation, in short 1. Batch building at flush (not just merge): FieldWriter.addValue just buffers the vectors and the batch builder makes the graph at flush using NN descent. This is similar to your approach of building layer 0 and then the higher layers just as lucene does 2. Merges: same as your overall approach, but I had a heuristic for skewed merges where if we're merging a small segment into a large one, it is faster/cheaper to still use the existing strategy instead of the batched approach Below diagram (AI generated but looks correct) gives a quick overview of how we can use this batch building approach for speeding up both indexing and merging: <img width="3200" height="2340" alt="Image" src="https://github.com/user-attachments/assets/efc61eb8-b67f-4a17-9a81-2b07a4000274"; /> For KNN - I used a very similar approach to PyNNDescent (RP trees + NN descent) instead of fully random initialization since it cut NN iterations needed while producing a slightly better quality graph (fewer visited at same recall) Rough results with luceneutil on c8id.metal-48xl (Intel) and c8gd.metal-48xl (Graviton4), Cohere v3 1024d, maxConn 16, beamWidth 100. Counting only the total build time meaning indexing + force merge to 1 segment. And for the existing Lucene approach, I had AI tune the RAM buffer, concurrency, etc the best it could on the same dataset and machines for a fair comparison and this is what I got: | | best stock | batch (NN-descent) | E2E speedup (indexing + forceMerge(1))| |---|---|---|---| | 5M, Intel | 319 s | 153 s | 2.09x | | 5M, Graviton4 | 278 s | 180 s | 1.54x | | 1M, Intel | 48 s | 38 s | 1.26x | | 1M, Graviton4 | 44 s | 44 s | tie | And similar to your results, graph quality is same or better at the matched recall with 8-33% fewer visited nodes at 1M and parity at 5M. So IMO indexing or the "batch build on flush" is an equally compelling application for this technique. So we can try solving for both merge + build at flush problems with this approach to reduce the overall indexing wall clock time. Would be interesting to compare head to head on how PiPNN compares with more traditional NN descent regardless. If you want a reference for the POC code for both batch build + merges using ordinary NN descent, I pushed it here: https://github.com/apache/lucene/compare/main...shbhar:lucene:batch-hnsw-nn-descent. FYI it was failing one of the nightly tests for off distribution queries, which I hadnt investigated yet (TestBatchHnswGraphBuilder.testOffDistributionQueryRecall) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
