You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "RamakrishnaChilaka (via GitHub)" <gi...@apache.org> on 2025/09/06 15:48:53 UTC
[PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
RamakrishnaChilaka opened a new pull request, #15163:
URL: https://github.com/apache/lucene/pull/15163
Follow-up to https://github.com/apache/lucene/pull/15140. For vector search, TopKNNCollector uses NeighborQueue. This PR replaces its underlying heap implementation from the binary LongHeap to the TernaryLongHeap.
### Performance Results
On c8g.8xlarge (Graviton) with topN = 1000:
```
TaskQPS baseline StdDevQPS candidate StdDev Pct diff p-value
PKLookup 456.85 (1.4%) 459.33 (0.9%) 0.5% ( -1% - 2%) 0.139
AndHighHighVector 114.90 (0.9%) 116.25 (0.6%) 1.2% ( 0% - 2%) 0.000
AndHighLowVector 119.86 (0.8%) 121.37 (0.7%) 1.3% ( 0% - 2%) 0.000
AndHighMedVector 112.55 (0.8%) 114.00 (0.7%) 1.3% ( 0% - 2%) 0.000
MedTermVector 130.14 (0.8%) 131.91 (0.7%) 1.4% ( 0% - 2%) 0.000
HighTermVector 138.60 (0.8%) 140.81 (0.6%) 1.6% ( 0% - 3%) 0.000
LowTermVector 138.34 (0.7%) 140.74 (0.5%) 1.7% ( 0% - 2%) 0.000
```
On i3.8xlarge with topN = 1000:
```
TaskQPS baseline StdDevQPS candidate StdDev Pct diff p-value
PKLookup 218.10 (2.3%) 217.52 (2.3%) -0.3% ( -4% - 4%) 0.712
AndHighLowVector 75.39 (0.4%) 76.12 (0.4%) 1.0% ( 0% - 1%) 0.000
AndHighHighVector 74.40 (0.5%) 75.20 (0.4%) 1.1% ( 0% - 1%) 0.000
AndHighMedVector 79.06 (0.3%) 79.92 (0.5%) 1.1% ( 0% - 1%) 0.000
MedTermVector 82.18 (0.4%) 83.17 (0.4%) 1.2% ( 0% - 1%) 0.000
HighTermVector 87.32 (0.4%) 88.37 (0.4%) 1.2% ( 0% - 2%) 0.000
LowTermVector 93.71 (0.4%) 95.05 (0.5%) 1.4% ( 0% - 2%) 0.000
```
TLDR; The ternary heap implementation shows consistent performance improvements of 1.0-1.7% across vector search operations on both ARM (Graviton) and x86 architectures.
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "RamakrishnaChilaka (via GitHub)" <gi...@apache.org>.
RamakrishnaChilaka closed pull request #15163: Use TernaryLongHeap in NeighborQueue for faster vector search performance
URL: https://github.com/apache/lucene/pull/15163
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #15163:
URL: https://github.com/apache/lucene/pull/15163#issuecomment-3269135316
The change looks good to me, but I'd like someone who is more intimate with the Lucene's vector search code to take a look, e.g. @msokolov or @benwtrent.
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #15163:
URL: https://github.com/apache/lucene/pull/15163#issuecomment-3264987403
Sorry, maybe I wasn't clear but I was actually endorsing this change. :) Someone may look at your performance numbers and think that it barely makes any difference. I was trying to point out that it may make a difference in other important scenarios. Let's reopen it?
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15163:
URL: https://github.com/apache/lucene/pull/15163#issuecomment-3262462163
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #15163:
URL: https://github.com/apache/lucene/pull/15163
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #15163:
URL: https://github.com/apache/lucene/pull/15163#issuecomment-3264971344
The speedup is tiny, but as @benwtrent pointed out on another issue, this may be less tiny when vector comparisons dominate runtime less, e.g. because of quantization or a lower number of dimensions.
--
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: [PR] Use TernaryLongHeap in NeighborQueue for faster vector search performance [lucene]
Posted by "RamakrishnaChilaka (via GitHub)" <gi...@apache.org>.
RamakrishnaChilaka commented on PR #15163:
URL: https://github.com/apache/lucene/pull/15163#issuecomment-3264981245
Got it Adrian. Closing the PR.
--
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