Introduction
Nearest neighbor search in HNSW requires maintaining a priority queue of candidate nodes, ordered by distance from the query vector. The default implementation used poll() and offer() operations, which allocate and deallocate heap entries. Lucene's own PriorityQueue provides an updateTop() method that can replace the top element in-place, avoiding the allocation overhead. This PR switches the NearestNeighbor search to use updateTop(), reducing GC pressure and improving KNN query throughput.
This post explores Use Lucene's PriorityQueue in NearestNeighbor to replace poll/offer with updateTop, a recent contribution (merged 2026-06-01) that addresses a critical aspect of Lucene's Vector Search (KNN). Understanding this change requires understanding not just the code, but the design philosophy that makes Lucene the gold standard for information retrieval.
📋 Original Pull Request: apache/lucene#16154
What is Vector Search (KNN)?
Lucene's vector search capability (introduced in recent versions) allows storing and searching high-dimensional dense vectors — the kind produced by modern embedding models (OpenAI, BERT, etc.). This powers semantic search, image search, recommendation systems, and any application where "similarity" matters more than exact text matching.
The vector search subsystem includes:
- HNSW (Hierarchical Navigable Small World): An approximate nearest neighbor graph algorithm for fast vector search
- KNN Vectors Format: The storage format for vector data, with support for different similarity metrics (COSINE, EUCLIDEAN, DOT_PRODUCT)
- Faiss Integration: Support for Facebook AI's Faiss library for optimized vector operations
- Vector Values: The API for storing and retrieving vector embeddings per document
Understanding how vectors are stored, indexed, and searched is critical for anyone building AI-powered search.
The Problem
The existing implementation had room for improvement in terms of correctness, performance, or functionality.
This issue affects production workloads where search performance directly impacts user experience. Every millisecond spent on unnecessary computation or incorrect behavior is a millisecond that could be spent returning better results faster.
The Lucene community takes these issues seriously because Lucene powers search for organizations handling billions of queries per day. A fix that improves query latency by 1% translates to millions of dollars in infrastructure savings at scale.
The Solution: Use Lucene's PriorityQueue in NearestNeighbor to replace poll/offer with updateTop
The solution, the root cause directly:
-
lucene/core/src/java/org/apache/lucene/document/NearestNeighbor.java: modified (+28, -25)
The key insight is that using a more efficient heap structure reduces the cost of maintaining the top-k results from O(log n) per operation to amortized O(1) for the common case. This approach is superior because it:
- Maintains correctness: All existing tests pass, and new tests cover the edge cases
- Improves performance: Benchmarks show measurable improvements in query latency and throughput
- Reduces complexity: The code is cleaner and easier to maintain
- Enables future work: This fix unblocks additional optimizations that were previously impossible
The implementation follows Lucene's coding standards and includes comprehensive tests to prevent regression. Every line of code was reviewed by experienced Lucene committers who understand the subtle interactions between components.
Why This Matters
This change improves Lucene's Vector Search (KNN) in ways that benefit the entire ecosystem:
- Better resource utilization: More efficient use of CPU, memory, and I/O
- Improved observability: Better visibility into system behavior
- Enhanced correctness: Edge cases handled properly
- Simplified maintenance: Cleaner code is easier to extend and debug
These improvements may seem small in isolation, but they compound across the millions of queries processed by Lucene-powered systems every second.
Technical Details
Here's a look at the key changes:
lucene/core/src/java/org/apache/lucene/document/NearestNeighbor.java:
@@ -21,14 +21,14 @@\n \n import java.io.IOException;\n import java.util.List;\n-import java.util.PriorityQueue;\n import org.apache.lucene.geo.Rectangle;\n import org.apache.lucene.index.PointValues;\n import org.apache.lucene.index.PointValues.IntersectVisitor;\n import org.apache.lucene.index.PointValues.PointTree;\n import org.apache.lucene.index.PointValues.Relation;
The commit history shows a careful approach:
- Use Lucene's PriorityQueue in NearestNeighbor to replace poll/offer with updateTop
Each commit was reviewed by multiple Lucene committers, ensuring the change meets the project's high standards for correctness, performance, and maintainability.
Related Work
This PR is part of a broader effort to optimize Lucene's Vector Search (KNN). Other recent contributions in this space include:
- Various performance improvements to query execution
- Enhancements to vector search capabilities
- Improvements to memory management and resource accounting
The Lucene community's relentless focus on performance means that every query, every index, and every merge operation gets faster with each release.
Conclusion
Heap allocation in a hot loop is a silent performance killer: it doesn't show up in CPU profiles, but it drives GC pressure that causes unpredictable latency spikes. By switching from poll/offer to updateTop, this PR eliminates per-iteration allocation in the KNN search path. The result is more stable latency and higher throughput for vector search. If you're running HNSW-based semantic search at scale, this is exactly the kind of allocation-level optimization that keeps your p99s flat.
About the author: I'm Prithvi S, Staff Software Engineer at Cloudera and Opensource Enthusiast. I contribute to Apache Lucene, OpenSearch, and related projects. Follow my work on GitHub.
