apache / apache/lucene

Explore moving HNSW's NeighborQueue to a radix heap [LUCENE-10383]

Open
#11,419 8 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor module:core/hnsw type:enhancement type:task
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.