Explore moving HNSW's NeighborQueue to a radix heap [LUCENE-10383]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
Now that @jtibshirani improved merging via #11411, nightly benchmarks report the following two top CPU consumers:
```
18.45% 548638 org.apache.lucene.util.VectorUtil#dotProduct()
at org.apache.lucene.index.VectorSimilarityFunction$2#compare()
at org.apache.lucene.util.hnsw.HnswGraph#search()
at org.apache.lucene.util.hnsw.HnswGraphBuilder#addGraphNode()
13.23% 393609 org.apache.lucene.util.LongHeap#upHeap()
at org.apache.lucene.util.LongHeap#push()
at org.apache.lucene.util.hnsw.NeighborQueue#add()
at org.apache.lucene.util.hnsw.HnswGraph#search()
```
Exploration at #9028 suggested that radix heaps perform better than binary heaps if the heap is large: queries with 16 clauses or more got faster while queries with fewer clauses would get slower. With a default beam width of 100, I'd be interested in seeing how HNSW indexing performs if we replace the current binary LongHeap with a radix heap.
---
Migrated from [LUCENE-10383](https://issues.apache.org/jira/browse/LUCENE-10383) by Adrien Grand (@jpountz), updated Jan 22 2022
Contributor guide
Research direction
Start by reading HnswGraph.search, HnswGraphBuilder.addGraphNode, and NeighborQueue.add to understand the current LongHeap path, then review the radix-heap exploration referenced in #9028. Run the nightly benchmarks for HNSW indexing and compare the default beam width of 100 across query clause counts; done means the performance trade-offs are measured and documented.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend, performance, search
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100