jeho-rpls opened a new issue, #16400:
URL: https://github.com/apache/lucene/issues/16400
### 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
--
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]
