aruggero opened a new pull request, #16034:
URL: https://github.com/apache/lucene/pull/16034
## Sibling Expansion for DiversifyingChildrenKnnQuery HNSW Search
### Summary
This contribution introduces sibling expansion as an optimization for KNN
vector search over parent-child document relationships (i.e.,
`DiversifyingChildrenFloatKnnVectorQuery` /
`DiversifyingChildrenByteKnnVectorQuery`).
When the HNSW graph searcher encounters a child node belonging to a newly
discovered parent, all siblings of that parent (other children of the same
parent not yet visited) are immediately scored and collected — without
requiring further graph traversal to reach them. This improves recall for
nested document use cases where multiple child vectors share a parent, as
siblings that are close in the document structure may not be well-connected in
the HNSW graph.
### Changes
**New interfaces (lucene/core)**
- `ChildrenSiblingExpansion` — implemented by `KnnCollector `instances that
support ordinal-level sibling expansion during HNSW search. The searcher calls
`pendingSiblingOrdinals()` before collecting a node to get unvisited siblings
to score immediately.
- `DocSiblingExpansion` — doc-ID-level companion used by
`OrdinalTranslatedKnnCollector` to bridge between HNSW ordinal space and
collector doc-ID space.
**Core HNSW searcher (`AbstractHnswGraphSearcher`)**
- Added sibling scoring logic: if the collector implements
`ChildrenSiblingExpansion`, siblings are bulk-scored and inserted into the
candidate queue before the triggering node is collected.
- Respects the visit budget: only as many siblings are scored as the
remaining `visitLimit` allows.
**Join module (lucene/join)**
- `DiversifyingNearestChildrenKnnCollector` now implements
`DocSiblingExpansion`, returning the sibling doc IDs for a given child.
- `DiversifyingNearestChildrenKnnCollectorManager` builds a docId-to-ordinal
mapping used to translate siblings from doc-ID space back to vector ordinals.
- `OrdinalTranslatedKnnCollector` wires the two interfaces together.
- Minor cleanup: removed a dead while (heap.size() > k()) loop in
`topDocs()`, simplified the heap update path (unnecessary `upHeap` branch
removed), and changed `downHeap` return type from int to void.
**Docid-to-Ordinal Cache**
Sibling expansion requires translating child document IDs to HNSW vector
ordinals at search time. To avoid rebuilding this mapping on every query, a
segment-level docId-to-ordinal cache is introduced in
`DiversifyingNearestChildrenKnnCollectorManager`.
It is populated lazily on the first query against a given segment+field
combination and evicted automatically via addClosedListener when the segment
closes — no manual lifecycle management required.
### Tests
- `TestDiversifyingChildrenKnnSiblingExpansion` — comprehensive test suite
covering correctness, early termination, and recall improvement with sibling
expansion enabled vs. disabled.
- `DiversifyingChildrenKnnCollectorTestCase` — shared test case base class.
### Benchmarks
- `DiversifyingChildrenKnnQueryBenchmark` — JMH benchmark covering multiple
children-per-parent and k configurations, with and without the ordinal cache,
to quantify the performance impact of sibling expansion.
#### Results
Benchmarks were run with JMH (Mode.AverageTime, 3 forks × 5 measurement
iterations × 1 s each, 4 warmup iterations) on a single-segment index of 5,000
parents, 128-dimensional float vectors, DOT_PRODUCT similarity.
Three sibling-correlation scenarios are measured:
- best — siblings nearly identical (noise = 0.05); early HNSW termination
is expected.
- standard — siblings moderately correlated (noise = 0.30); realistic
production case.
- worst — siblings fully random; expansion fires but provides no recall
benefit (pure overhead measurement).
The table below compares main (no sibling expansion) against this branch
(sibling). Lower is better (ms/op).
| children | k | correlation | main (ms/op) | sibling (ms/op) | overhead |
| -------- | --- | --------- | ------------- | --------------- | ---------- |
| 4 | 10 | best | 0.070 ± 0.003 | 0.074 ± 0.003 | +5.7% |
| 4 | 10 | standard | 0.053 ± 0.003 | 0.060 ± 0.004 | +13.2% |
| 4 | 10 | worst | 0.050 ± 0.005 | 0.056 ± 0.003 | +12.0% |
| 4 | 100 | best | 0.400 ± 0.013 | 0.448 ± 0.008 | +12.0% |
| 4 | 100 | standard | 0.251 ± 0.012 | 0.321 ± 0.004 | +27.9% |
| 4 | 100 | worst | 0.270 ± 0.026 | 0.328 ± 0.011 | +21.5% |
| 8 | 10 | best | 0.101 ± 0.005 | 0.106 ± 0.007 | +5.0% |
| 8 | 10 | standard | 0.065 ± 0.003 | 0.084 ± 0.004 | +29.2% |
| 8 | 10 | worst | 0.064 ± 0.003 | 0.086 ± 0.005 | +34.4% |
| 8 | 100 | best | 0.642 ± 0.019 | 0.711 ± 0.041 | +10.7% |
| 8 | 100 | standard | 0.330 ± 0.027 | 0.499 ± 0.030 | +51.2%
| 8 | 100 | worst | 0.307 ± 0.016 | 0.512 ± 0.028 | +66.8% |
| 16 | 10 | best | 0.147 ± 0.004 | 0.165 ± 0.008 | +12.2% |
| 16 | 10 | standard | 0.080 ± 0.004 | 0.128 ± 0.007 | +60.0% |
| 16 | 10 | worst | 0.075 ± 0.005 | 0.125 ± 0.007 | +66.7% |
| 16 | 100 | best | 0.985 ± 0.053 | 1.211 ± 0.047 | +22.9% |
| 16 | 100 | standard | 0.568 ± 0.022 | 0.815 ± 0.032 | +43.5% |
| 16 | 100 | worst | 0.496 ± 0.021 | 0.863 ± 0.046 | +74.0% |
**Key observations:**
- Best-case overhead is low (~5–12%): when siblings are nearly identical,
HNSW early termination kicks in after a parent is discovered, partially
offsetting the cost of scoring extra nodes.
- Overhead grows with children-per-parent: scoring more siblings per
parent naturally increases latency; with 16 children, the overhead reaches
~67–74% in the worst case.
- Overhead grows with k: larger result sets require exploring more of the
graph before early termination can trigger, leaving more room for sibling
scoring to accumulate.
- Worst-case overhead is the upper bound: the worst scenario (fully random
siblings) represents the theoretical ceiling — sibling expansion fires on every
parent discovery but contributes nothing to recall. Real-world data almost
always falls between standard and best.
- This benchmark measures latency only, not recall. The primary motivation
for sibling expansion is improving recall for correlated child vectors, a
trade-off that is not captured here.
## Final Considerations
Sibling expansion is always slower in these results because it always adds
work.
For every candidate child found via HNSW, sibling expansion additionally:
- Reads all sibling vectors from the index
- Computes their dot-product scores
- Tries to insert them into the top-k heap
That's extra distance computations and memory accesses on every candidate,
regardless of whether siblings are useful.
Good siblings help HNSW terminate earlier by quickly raising the competitive
score threshold:
| Scenario | Siblings score | Threshold rises | HNSW early exit |
Net overhead |
| --------- | ------------------- | --------------- | ----------------- |
---------------- |
| best | High (nearly identical) | Fast | Yes |
Small (~5-12%) |
| standard | Moderate | Moderate | Partial |
Medium (~13-60%) |
| worst | Random/low | Barely | No |
Large (~12-74%) |
In the best case, finding one good child means all its siblings score well
too, rapidly raising the threshold and letting HNSW skip exploring many nodes.
The expansion cost is partially offset by shorter traversal.
In the worst case, siblings score poorly, so the threshold rises slowly,
HNSW explores more nodes, and you pay the expansion cost on every candidate —
pure overhead with no benefit.
**The problem without sibling expansion**
HNSW explores the vector graph and finds candidate children. When it finds
child C1 of parent P1, it scores P1 with C1's score. But P1 might have another
child, C2, that scores much higher, and HNSW might never visit C2 because it's
not a graph neighbor of C1.
Without sibling expansion, a parent can be under-scored or entirely missed
because HNSW happened to find its weakest child first. The final ranking of
parents is wrong.
Benefits:
- With sibling expansion, when a parent enters the result set, it's
guaranteed to be scored by its actual best child, giving correct relative
ranking between parents.
- Better parent scores raise the HNSW competitive threshold faster, which is
exactly why the best scenario (identical siblings) shows the smallest overhead
— finding any child immediately gives the true parent score, and HNSW can prune
more aggressively.
"Cons":
If HNSW has already found P1 via C1, sibling expansion just refines P1's
score. It doesn't help discover P2, P3, ... Pk faster. You're spending time on
a parent already in the result set instead of exploring graph edges toward new
undiscovered parents.
Looking at the numbers, sibling expansion is always slower — even in the
best scenario. The early termination benefit never outweighs the
sibling-checking cost.
**The real benefit is recall/precision, not speed.**
--
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]
