apache / apache/lucene

HNSW graph reuse during merge is silently disabled under per-field codecs since 10.4.0

Open Beginner friendly
#16,400 2 comments 0 reactions 0 assignees View on GitHub
type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

## Summary

`IncrementalHnswGraphMerger` is meant to reuse existing HNSW graphs from input segments during a merge, instead of rebuilding the merged graph from scratch.
Since 10.4.0 this reuse never triggers under a per-field vectors codec, which is how Lucene's default codec wires vector formats and the configuration Elasticsearch runs.
As a result every merge rebuilds the full graph by re-inserting every vector, and the cost that reuse was designed to remove is paid on every merge.

The graph is still correct, so there is no functional symptom. The main effect is that vector merges are much more expensive than they should be, which shows up as longer merges and higher merge CPU.

## The regression

`IncrementalHnswGraphMerger.addReader` unwraps the per-field wrapper into a local variable and then tests the wrong variable.

10.3.0 (working):

```java
KnnVectorsReader currKnnVectorsReader = reader;
if (reader instanceof PerFieldKnnVectorsFormat.FieldsReader candidateReader) {
currKnnVectorsReader = candidateReader.getFieldReader(fieldInfo.name);
}
if (!(currKnnVectorsReader instanceof HnswGraphProvider) || !noDeletes(liveDocs)) {
return this;
}
```

10.4.0 through current branch_10x (broken):

```java
KnnVectorsReader currKnnVectorsReader = reader;
if (reader instanceof PerFieldKnnVectorsFormat.FieldsReader candidateReader) {
currKnnVectorsReader = candidateReader.getFieldReader(fieldInfo.name);
}
if (!(reader instanceof HnswGraphProvider)) {
return this;
}
```

Under a per-field codec, `reader` is a `PerFieldKnnVectorsFormat.FieldsReader`, which does not implement `HnswGraphProvider` on the 10.x branches.
The guard is therefore always true, every candidate segment returns early, no seed graph is ever selected, and the merger falls back to a full rebuild for every merge.

`main` is not affected. On `main`, `FieldsReader` implements `HnswGraphProvider` (added in #14097), so the same guard passes.
The guard on `main` was changed to test `reader` as part of #14097, which bundled the interface implementation that makes it safe.
The change reached the 10.x line separately through the branch_10x cherry-pick of #15003, where the surrounding code did not have that interface implementation, so the guard lost the property it depends on.

## Why it went unnoticed

- There is no functional symptom. Merges complete and produce correct graphs, only slower.
- The nightly Lucene benchmarks track `main`, where reuse works, so no regression signal was produced.
- The two commits that carried reuse improvements into the 10.x line (#14380 and the #15003 cherry-pick) were performance backports.

## Evidence

Source, the guard across release tags:

- 10.3.0: tests `currKnnVectorsReader`, reuse works under per-field.
- 10.4.0, 10.5.0, branch_10x: tests `reader`, reuse dead under per-field.
- `main`: tests `reader` but `FieldsReader implements HnswGraphProvider`, reuse works.

Behavioral, standalone harness against a stock 10.4.0 `lucene-core` jar with the default codec.
Two segments of 60000 and 6000 vectors, 128 dimensions, then a force merge to one segment. The only change on the fixed side is a two line fix in `IncrementalHnswGraphMerger.addReader`, testing and storing the unwrapped `currKnnVectorsReader` instead of the wrapper.

- stock jar: InfoStream logs `addVectors [0 66000)`, a full rebuild, merge takes 5405 ms.
- guard fix only: InfoStream logs `build graph from merging 2 graphs of 66000 vectors, graph sizes:60000 6000`, merge takes 676 ms.

Elasticsearch 9.4.2 (bundles Lucene 10.4.0), in our test environment. About 1M top level documents (2M Lucene docs including nested), with 1.01M 384 dimension float vectors (plain `hnsw`) and 577k 96 dimension vectors (`bbq_hnsw`):

- Reindexing the same source into a fresh index, merge time drops from 2113 s (stock, one run) to 1441 and 1528 s (fixed, two runs), roughly 30 percent less merge work.
- Full day lifecycle merge time under real update churn drops from 16279 s to 14072 s. These are different calendar days, and the fixed day actually processed more merges (3310 vs 2950), so, for a broadly similar merge mix, the per merge cost dropped more than the totals suggest.
- The `bbq_hnsw` field reuses as well. An InfoStream trace during a force merge of a bbq-only index logs `build graph from merging 9 graphs of 200000 vectors`.

A note on recall. Restoring reuse restores the merged graph quality characteristics that `main` users already have, which in our measurements are marginally below a from scratch rebuild.
Over 60 real query vectors, recall@10 at num_candidates 100 measured 1.0000 on rebuild-built graphs and 0.9833 to 0.9950 on reuse-built graphs, with the difference concentrated in one or two queries per build and recoverable by raising num_candidates.
The fix does not introduce a new tradeoff, it re-enables the intended one.

## Scope

The 10.x line is what ships to real deployments. Elasticsearch 9.4 and later bundle the affected releases today.
OpenSearch `main` currently pins 10.5.0 and Solr `main` pins 10.4.0, so upcoming releases of both will carry the affected code unless it is fixed on the 10.x branch.

---

If this looks valid, I would like to work on the fix.

### Version and environment details

Lucene 10.4.0, Elasticsearch 9.4.2

Contributor guide

Open the contributing guide

Research direction

Start in IncrementalHnswGraphMerger.addReader and compare the 10.3.0 guard with the 10.4.0 through branch_10x versions, focusing on the unwrapped per-field reader. Use the standalone merge harness with the default per-field codec and confirm that graph reuse is selected, with InfoStream showing graphs being merged rather than all vectors being rebuilt.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
performance, search
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.