ethbak opened a new issue, #16618: URL: https://github.com/apache/lucene/issues/16618
### Description When `IncrementalHnswGraphMerger` reuses a base graph with deletes, the disconnected node repair logic runs on the calling merge thread, outside the concurrent worker pool. This serializes the merge process that is otherwise parallel, in some cases slowing down merges even when compared to fully rebuilding the graph from scratch. ## Change History Logic to support graph re-use during merges on segments with deletes was introduced in #15003, however, it remained silently disabled until release 10.5.1, where #16403 fixed the bug to re-enable it. This uncovered a dormant bug in the original implementation, which caused a drop in recall due to increasingly sparse graphs over many merges with low delete percents. #16559 fixed the drop in recall but exposed another bug (this one) present in the original reuse-with-deletes implementation, where merges are slower with the optimization than with full rebuild from scratch due to lack of parallelism. Before the last fix, this issue was hidden because merge time was artificially lowered due to the incorrect, overly sparse graphs #15003 created. ## Observed Behavior (luceneutil) Comparing two arms, 1) being the 10.5 build, with re-use on, and 2) being the 10.5 build with re-use entirely disabled (`DELETE_PCT_THRESHOLD = -1`), we can see that when we benchmark to compare merge time in multi-core environments (`Lucene99HnswVectorsFormat(M=32, beamWidth=200, numMergeWorkers=8, exec)`), graph re-use can often exceed the merge time of a full rebuild from scratch. ### Results: cohere-1024, M=32, beamWidth=200, 35% deletes Aged base: 500,000 vectors, dot-product, indexed as 5 × 100k segments, then a one-shot 35% delete, then `forceMerge(1)` with 8 merge workers on a 16-core-pinned JVM. | arm | single-threaded phase (copy + repair) | parallel insert (8 workers) | total merge | vs rebuild | |---|--:|--:|--:|--:| | reuse (repair on) | 97.7 s | 77.0 s | 174.7 s | **1.79× slower** | | rebuild | 3.0 s | 94.7 s | 97.7 s | 1.00× | Here, the single-threaded phase represents the amount of time spent copying and repairing the graph / nodes, and the parallel insert is the phase that adds the remaining new nodes to the graph, spread across the 8 merge workers by `HnswConcurrentMergeBuilder.build()`. We can see that with re-use on, the single threaded phase dominates the overall merge time, while the rest of the process is significantly faster with re-use on, as we would expect. ## The Bug `ConcurrentHnswMerger.createBuilder` chooses the reuse path when a base graph is available. On that path it calls `InitializedHnswGraphBuilder.initGraph`, whose `initializeFromGraph` does the following: 1. `copyGraphStructure`: copy each surviving node's neighbor list, minus deleted neighbors, and flag nodes for repair. 2. `repairDisconnectedNodes` --> `fixDisconnectedNodes`: for each flagged node searches (`HnswGraphSearcher.searchLevel`) to re-select diverse neighbors. 3. `rebalanceGraph` The merger waits until AFTER the above to construct `new HnswConcurrentMergeBuilder(taskExecutor, numWorker, …)`, which is what allocates the remaining merge work across the worker pool. Therefore steps 1–3 never touch the pool and are entirely serial. In practice, this means that **the merge re-use optimization is actually a regression in the merge time it was meant to improve** in multi-core setups. ## The Fix To resolve the regression we simply need to move the node repair logic into the HnswConcurrentMergeBuilder phase so its work is parallelized across the worker pool. This seems to be a moderate restructuring change but is relatively straightforward. ## Related - **#16552** - **#16559** - **#16400** - **#16403** - **#15967** ### Version and environment details - Lucene `branch_10_5` @ `22ee725` - Corretto JDK 25 (runtime); JDK 24 to build the fork jar - aarch64 Graviton, m7g.4xlarge (16 vCPU) - JVM pinned to 8 cores (`numMergeWorkers=8`) -- 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]
