LantaoJin opened a new pull request, #16794: URL: https://github.com/apache/lucene/pull/16794
### Description `ConcurrentHnswMerger` never uses the join-set merge from #14331. It initializes the merged graph from the largest input graph and then inserts every other vector with a full search, even though `IncrementalHnswGraphMerger.addReader` has already collected the other deletion-free graphs in `graphReaders`. Only the serial `MergingHnswGraphBuilder` joins them. `Lucene99HnswVectorsWriter` picks the concurrent merger whenever the format has a merge executor or the intra-merge executor provides more than one worker, and those merges do about 1.5x the vector comparisons of a serial merge of the same segments. This PR makes the concurrent merger join those graphs too: - `ConcurrentHnswMerger.createBuilder` orders the readers and maps ordinals with the same code as the serial path (new `IncrementalHnswGraphMerger.orderGraphReaders()`, existing `getNewOrdMapping`), initializes from the base graph, and passes the other deletion-free graphs to a new `HnswConcurrentMergeBuilder` constructor. Its private copy of the ordinal mapping is removed. - `HnswConcurrentMergeBuilder` computes the join set of every graph up front, one task per graph, then joins the graphs one after the other: all workers insert the join set with a full search, then all workers insert the rest of that graph with a level-0 search that starts from each node's join-set neighbors and their current neighbors. Nodes of graphs with deletions, or of readers without a graph, are added afterwards exactly as before. - Join phases are short, so they use smaller batches (at least 16 per worker); with the default 2048-node batches, workers idled at every phase boundary and most of the gain was lost. Two things worth knowing. First, the order matters: inserting the join sets of all graphs before the other nodes of any graph is simpler, but it built a clearly worse graph (recall@10 0.9658 instead of 0.9852 at ef=100 on the benchmark below), in a serial implementation as well, so graphs are joined one at a time as `MergingHnswGraphBuilder` does. Second, the serial builder also starts from neighbors inserted earlier (`v < u`); that order does not exist when workers insert concurrently, so only join-set neighbors are used. In a serial ablation that cost 0.0014 recall (0.9866 vs 0.9852). **Tests.** New `TestConcurrentHnswMerger`. One test merges three flushed segments with both mergers through a scorer supplier that counts scored vectors, and requires the concurrent merge to score fewer than 1.25x the vectors of the serial one: before this change it fails on every seed at 1.50-1.53x, after it the ratio is 0.995-1.005. The other test checks that the concurrent merge's recall stays within 0.05 of the serial merge's. The HNSW, Lucene99/102/104 and per-field codec tests, `TestHnswMergeAbort`, `TestIndexWriterForceMerge`, `TestKnnGraph` and the KNN search tests pass, as do `./gradlew tidy` and `check` with errorprone. **Benchmark.** Merger level only, not luceneutil: segments are flushed with `Lucene99HnswVectorsFormat(16, 100)`, then `HnswGraphMerger.merge` is timed on them directly with an on-heap `DefaultFlatVectorScorer`, comparing the concurrent merger before and after this change. 200k vectors, dim 64, a Gaussian mixture around 64 centroids, Euclidean; 32-core aarch64, JDK 25 with the vector incubator module. Merge time in seconds, before → after: | segments | serial | 2 workers | 4 workers | 8 workers | 16 workers | |---|---|---|---|---|---| | 8 x 25k | 41.09 | 31.75 → 22.09 (1.44x) | 15.87 → 10.94 (1.45x) | 8.04 → 5.55 (1.45x) | 4.47 → 2.85 (1.57x) | | 32 x 6250 | 42.62 | 32.28 → 22.93 (1.41x) | 16.19 → 11.39 (1.42x) | 8.25 → 5.76 (1.43x) | 4.20 → 2.96 (1.42x) | | 80k, 40k, 2 x 20k, 3 x 10k, 2 x 5k | 32.56 | 25.15 → 17.61 (1.43x) | 12.56 → 8.76 (1.43x) | 6.69 → 4.54 (1.47x) | 3.51 → 2.41 (1.46x) | At a fixed ef, recall now matches the serial merge and is a little below the old concurrent full rebuild (0.1 to 0.9 points at ef=100, depending on the layout; run-to-run noise is about ±0.005). The joined graphs are cheaper to search, though, so at equal visited nodes recall is on par or better, which is the trade-off #14331 made for the serial path. 32 x 6250 segments, 8 workers, recall@10 / visited nodes per query, mean of two runs (serial: one run): | ef | before | after | serial | |---|---|---|---| | 50 | 0.9435 / 1047 | 0.9352 / 991 | 0.9258 / 991 | | 100 | 0.9832 / 1549 | 0.9802 / 1457 | 0.9794 / 1473 | | 200 | 0.9917 / 2111 | 0.9942 / 1995 | 0.9942 / 2018 | At 1457 visited nodes the old graph interpolates to about 0.976 recall, and at 1995 to about 0.990. -- 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]
