You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "kaivalnp (via GitHub)" <gi...@apache.org> on 2026/09/15 02:44:42 UTC
[I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
kaivalnp opened a new issue, #16674:
URL: https://github.com/apache/lucene/issues/16674
### Description
In the OSQ based vector format, we [recalculate centroids on merge](https://github.com/apache/lucene/blob/bc9adc96cc58d1e20761d961a2ab865eaede3962/lucene/core/src/java/org/apache/lucene/codecs/lucene104/Lucene104ScalarQuantizedVectorsWriter.java#L471) when there are deletes.
If there [aren't any deletes](https://github.com/apache/lucene/blob/bc9adc96cc58d1e20761d961a2ab865eaede3962/lucene/core/src/java/org/apache/lucene/codecs/lucene104/Lucene104ScalarQuantizedVectorsWriter.java#L465), the merged centroid is simply a weighted average of segment-level centroids.
I wonder if we can re-use the information of the previous centroid, even when there are deletes?
i.e. start with `previousCentroid * vectorCount`, and _subtract deleted vectors_ instead?
If the number of deletes is small, perhaps the work is much lesser? The caveat is that vectors may be read at non-contiguous parts of the raw vector file if we just read deleted ones.
This can be especially beneficial for cases where raw vectors go beyond RAM, by avoiding some paging activity?
Going one step further: the access pattern could be improved further if the raw format was more tightly integrated. Currently we perform three passes over the raw vectors:
1. [Merge raw vectors](https://github.com/apache/lucene/blob/bc9adc96cc58d1e20761d961a2ab865eaede3962/lucene/core/src/java/org/apache/lucene/codecs/lucene104/Lucene104ScalarQuantizedVectorsWriter.java#L327)
2. [Compute the centroid](https://github.com/apache/lucene/blob/bc9adc96cc58d1e20761d961a2ab865eaede3962/lucene/core/src/java/org/apache/lucene/codecs/lucene104/Lucene104ScalarQuantizedVectorsWriter.java#L483-L504)
3. [Perform scalar quantization](https://github.com/apache/lucene/blob/bc9adc96cc58d1e20761d961a2ab865eaede3962/lucene/core/src/java/org/apache/lucene/codecs/lucene104/Lucene104ScalarQuantizedVectorsWriter.java#L391-L394)
Can we compute the centroid in (1) and use it directly in (3), skipping (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: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-5733416453
Do we know what the relative cost of centroid computation is compared to other parts of merging vector values? I wonder if we could also have a good saving by computing based on an unbiased sample
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "CH-Abhinav (via GitHub)" <gi...@apache.org>.
CH-Abhinav commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-6000963037
Also can you experiment on unbiased sampling if possible? I think that can improve performance.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "dengfengjiang77 (via GitHub)" <gi...@apache.org>.
dengfengjiang77 commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-6000600328
I checked the proposal from @kaivalnp , it does work well from speed level, and we can calculate the centroid value in different cases( no delete/ delete <= 50% / delete > 50%) which reduce the vector bytes read, the demo test showed that the improvement can be happened, I will open a PR to address the solution.
PS : to answer @msokolov question, the whole force merge will take 10-12s, and this change will increase around 10~20ms, and by bytes read, the vectors reads will reduce from 460MB to 4.6Mb taking 1% deletes for example.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-6018767712
I think there is another full read from `checkIntegrity`? A step 0, run (sequentially?) on all the input segments before they are merged? That is a scan of the whole file and then confirming the checksum? But it's nearly redundant because any of the existing steps 1, 2, 3 could validate the checksum after their full scan? But ... it'd be a change in error detection timing because it would have done some merge work before detecting the bit flips.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "CH-Abhinav (via GitHub)" <gi...@apache.org>.
CH-Abhinav commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-5751560906
do you think doing unbiased samples will always work ? maybe a 1-5% sample would be good enough to calculate centroid for OSQ but that is completely different approach and we don't know if unbiased sampling will work for all vectors we are trading accuracy which is already traded while quantizing.
I would say this approach will be more optimal :-
1. if delete's are N<1% for small segments and N<0.1% for large segments we do what kaivalnp is proposing as it would be optimal to do so
2. if deleted docs are N>1% and N>0.1% for small and large segments respectively we should go with unbiased sampling with K~5%-10% of docs value taken randomly.
my question is can we do this unbiased sampling initially (when first centroid is calculated from graph) and is that accuracy is good enough for lucene? may be we will need to some tests to check accuracy and performance of this method.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "CH-Abhinav (via GitHub)" <gi...@apache.org>.
CH-Abhinav commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-5751613800
@msokolov I think we should go with multiple unbiased samples, calculate their centroids and merge them. this may work if we have large hnsw. smaller once may not have that many documents to even take multiple samples in which case default is best.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] Can we speed up centroid calculation in the OSQ vector format? [lucene]
Posted by "dengfengjiang77 (via GitHub)" <gi...@apache.org>.
dengfengjiang77 commented on issue #16674:
URL: https://github.com/apache/lucene/issues/16674#issuecomment-6020835337
> I think there is another full read from `checkIntegrity`? A step 0, run (sequentially?) on all the input segments before they are merged? That is a scan of the whole file and then confirming the checksum? But it's nearly redundant because any of the existing steps 1, 2, 3 could validate the checksum after their full scan? But ... it'd be a change in error detection timing because it would have done some merge work before detecting the bit flips.
Thanks, Mike, I think replace the full read in step 0 is worth trying, but step1 and step 3 only read live vectors, CRC need every bytes in order. for these files we need be careful:
.vec file - move the check from step 0 to step1, the raw copy can sequentially read , update CRC32
.veq file - we don't read in the merge, it is recomputed by .vec, check it in step 0 only for early detection. Could we drop this check?
.vex file - it will used to initialize the HNSW, suggest we keep the full read check for it
I'm measuring how much of step 0 is .vec vs .veq and will post the numbers later . If this direction looks good to you, I can open a separate issue for it and keep this PR to the centroid change(remove step2 only).
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org