dengfengjiang77 opened a new pull request, #16839: URL: https://github.com/apache/lucene/pull/16839
Relates to #16674, thanks @kaivalnp for this idea. Currently the scalar quantized writer re-read every raw vector to recompute the merged centroid whenever a source segment had deletions, which means a merge reads the raw vectors three times. The proposal is to compute the merged centroid while the raw vectors are copied in step 1 and use it directly for quantization with the step2 skipped(step2: full read and recompute the centroid is there are deletes). Major code changes: - A new `MergedCentroidCollector` wraps the source vector readers passed to the raw merge and adds each vector they return to a per-segment sum, once per ordinal. `verifyAndComputeCentroid` uses the sums only when the added ordinals are exactly the live ones; otherwise it sums the live vectors in a separate pass and logs that through the merge infoStream. Read order does not matter. - Add `TestCentroidMergeWithDeletes`. It checks that the merged centroid equals the mean of the live vectors across deletes, similarities, fp16, HNSW-SQ, index sort and SortingCodecReader, drives the collector with read patterns that must and must not fall back, and counts the fallback message so a merge that silently takes the extra pass fails. Behavior changes: - COSINE: each vector is normalized before it is added, the same as on flush. - Merge without deletes also use the summed centroid instead of weighted average of the stored centroids. PS: I tried substracting the deleted vectors firstly but on real data it was not faster: reading scattered deleted vector might pull most of `.vec` . So this PR goes with the second idea. Benchmark Result ( run in my side using luceneutil `KnnGraphTester` with `-deleteRate` (mikemccand/luceneutil#627), and I introduced WARM mode[`.vec` stays in page cache] and COLD mode[memory capped at 2304MB and page cache dropped before each merge] in the benchmark tests, here are the concise results: | deletes | warm force merge (s) | cold force merge (s) | |---|---|---| | 0% | 45.95 -> 46.05 (+0.2%) | not run | | 1% | 46.46 -> 45.72 (-1.6%) | 109.87 -> 92.08 (-16.2%) | | 10% | 43.02 -> 42.32 (-1.6%) | 105.50 -> 87.69 (-16.9%) | | 50% | too noisy | 111.75 -> 86.96 (-22.2%) | In the cold runs, each force merge reads 3.4-4.0 GB less from disk, about one full pass over the 4 GB .vec, so to answer @msokolov's question on the real data: removing the centroid pass saves about 1.6% of the force merge when` .vec i`s cahed and 16%-22% when it is not. Test for the new code: new TestCentroidMergeWithDeletes checks the merged centroid equals the mean of the live vectors, test different cases in few and many deletes. The `checkIntegrity` read in step 0 that @mikemccand pointed out is not included in this PR, I will open a separate issue and work on it. Questions for current design: I am wrapping the `MergeState` readers passed to the raw merge. No API change, but it relies on the raw merge reading each live vector through them, as `Lucene99FlatVectorsWriter` does today. But if a format reads another way, the merge will fall back to the extra pass(results will be correct and logged). Another plan is we can add an explicited per-vector hook to FlatVectorsWriter,, but it changes the experimental API where we need more changes on it. So currently I choose the minimum change principle. Many thanks for the review and feedback, I will work on it to make it complete. If there are more result data needed, let me know as well. -- 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]
