You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "jpountz (via GitHub)" <gi...@apache.org> on 2025/07/20 21:28:06 UTC
[PR] Further improve filtering by score. [lucene]
jpountz opened a new pull request, #14970:
URL: https://github.com/apache/lucene/pull/14970
PRs #14906 and #14896 improved the efficiency of filtering by score. This PR tries to get some extra speedup by:
- Skipping filtering by score when applying a non-essential clause that doesn't have matches over the range of doc IDs being scored.
- Filtering on float[] scores rather than double[] scores whenever applicable so that vectorization can work on 2x more lanes at once.
- Filtering by score using `VectorUtil#filterByScore` instead of relying on the collector to do it.
Luceneutil on wikibigall reports the following:
```
TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value
OrMany 23.21 (2.1%) 22.81 (2.9%) -1.7% ( -6% - 3%) 0.033
OrHighRare 285.51 (8.2%) 281.68 (6.2%) -1.3% ( -14% - 14%) 0.559
FilteredPrefix3 148.66 (1.6%) 146.92 (2.7%) -1.2% ( -5% - 3%) 0.092
TermTitleSort 82.88 (4.9%) 82.17 (5.0%) -0.9% ( -10% - 9%) 0.585
TermDayOfYearSort 278.76 (1.9%) 276.94 (2.7%) -0.7% ( -5% - 4%) 0.380
FilteredOrMany 16.33 (2.2%) 16.25 (1.7%) -0.5% ( -4% - 3%) 0.405
FilteredOr3Terms 164.07 (1.2%) 163.54 (0.9%) -0.3% ( -2% - 1%) 0.314
FilteredOr2Terms2StopWords 144.33 (0.9%) 144.00 (0.9%) -0.2% ( -2% - 1%) 0.431
FilteredOrStopWords 44.89 (2.2%) 44.86 (1.6%) -0.1% ( -3% - 3%) 0.915
FilteredOrHighMed 150.37 (1.0%) 150.29 (1.0%) -0.1% ( -2% - 1%) 0.858
TermDTSort 376.36 (2.7%) 376.45 (3.6%) 0.0% ( -6% - 6%) 0.982
FilteredTerm 159.30 (3.0%) 159.40 (2.5%) 0.1% ( -5% - 5%) 0.943
FilteredOrHighHigh 66.16 (1.8%) 66.20 (1.6%) 0.1% ( -3% - 3%) 0.903
FilteredAnd2Terms2StopWords 209.89 (1.3%) 210.13 (1.4%) 0.1% ( -2% - 2%) 0.792
FilteredAnd3Terms 186.68 (1.1%) 187.01 (1.0%) 0.2% ( -1% - 2%) 0.602
CountFilteredOrHighMed 146.93 (0.7%) 147.23 (1.0%) 0.2% ( -1% - 1%) 0.464
FilteredAndHighHigh 77.00 (1.4%) 77.18 (3.1%) 0.2% ( -4% - 4%) 0.754
FilteredIntNRQ 286.87 (1.2%) 287.61 (1.4%) 0.3% ( -2% - 2%) 0.539
FilteredAndStopWords 63.47 (1.5%) 63.69 (3.3%) 0.3% ( -4% - 5%) 0.678
FilteredAndHighMed 152.84 (1.4%) 153.41 (1.6%) 0.4% ( -2% - 3%) 0.441
CountAndHighMed 303.73 (1.3%) 305.00 (1.6%) 0.4% ( -2% - 3%) 0.376
CountFilteredOrHighHigh 135.14 (0.9%) 135.71 (1.0%) 0.4% ( -1% - 2%) 0.159
FilteredPhrase 31.18 (1.5%) 31.32 (2.1%) 0.4% ( -3% - 4%) 0.445
CountOrMany 28.24 (2.1%) 28.37 (2.2%) 0.5% ( -3% - 4%) 0.503
CountFilteredPhrase 24.66 (1.7%) 24.79 (2.9%) 0.5% ( -3% - 5%) 0.478
CountAndHighHigh 350.62 (2.1%) 352.70 (2.7%) 0.6% ( -4% - 5%) 0.436
CountOrHighMed 352.79 (1.6%) 355.12 (2.1%) 0.7% ( -3% - 4%) 0.267
CountFilteredOrMany 26.46 (1.8%) 26.64 (1.9%) 0.7% ( -2% - 4%) 0.249
TermMonthSort 3167.86 (2.4%) 3189.35 (2.7%) 0.7% ( -4% - 5%) 0.395
Or2Terms2StopWords 201.14 (1.5%) 202.57 (1.4%) 0.7% ( -2% - 3%) 0.131
CombinedOrHighMed 86.87 (0.8%) 87.50 (2.7%) 0.7% ( -2% - 4%) 0.253
CountTerm 8625.60 (2.6%) 8688.85 (2.8%) 0.7% ( -4% - 6%) 0.392
CombinedOrHighHigh 22.80 (1.0%) 22.99 (3.7%) 0.8% ( -3% - 5%) 0.328
Or3Terms 226.48 (1.6%) 228.60 (1.8%) 0.9% ( -2% - 4%) 0.089
And2Terms2StopWords 200.20 (1.7%) 202.22 (1.3%) 1.0% ( -1% - 4%) 0.036
CountOrHighHigh 333.72 (2.3%) 337.23 (2.4%) 1.1% ( -3% - 5%) 0.156
CombinedAndHighHigh 23.04 (0.8%) 23.30 (1.3%) 1.1% ( -1% - 3%) 0.001
And3Terms 235.22 (1.8%) 237.94 (2.0%) 1.2% ( -2% - 5%) 0.055
CombinedAndHighMed 88.23 (0.7%) 89.37 (1.2%) 1.3% ( 0% - 3%) 0.000
CountPhrase 4.09 (3.0%) 4.15 (1.8%) 1.5% ( -3% - 6%) 0.066
AndMedOrHighHigh 86.57 (1.3%) 87.90 (1.9%) 1.5% ( -1% - 4%) 0.003
AndHighOrMedMed 50.13 (2.0%) 51.26 (2.1%) 2.3% ( -1% - 6%) 0.000
OrStopWords 47.70 (2.6%) 48.98 (2.6%) 2.7% ( -2% - 8%) 0.001
AndStopWords 45.93 (2.9%) 47.37 (2.4%) 3.1% ( -2% - 8%) 0.000
CombinedTerm 38.49 (3.9%) 39.80 (1.2%) 3.4% ( -1% - 8%) 0.000
OrHighMed 251.67 (1.9%) 260.48 (2.3%) 3.5% ( 0% - 7%) 0.000
Term 652.30 (5.9%) 675.34 (5.0%) 3.5% ( -6% - 15%) 0.041
AndHighMed 198.48 (2.1%) 205.50 (2.1%) 3.5% ( 0% - 7%) 0.000
AndHighHigh 67.67 (2.8%) 70.74 (2.6%) 4.5% ( 0% - 10%) 0.000
OrHighHigh 76.43 (2.4%) 80.03 (2.4%) 4.7% ( 0% - 9%) 0.000
```
--
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] Further improve filtering by score. [lucene]
Posted by "HUSTERGS (via GitHub)" <gi...@apache.org>.
HUSTERGS commented on code in PR #14970:
URL: https://github.com/apache/lucene/pull/14970#discussion_r2218149053
##########
lucene/core/src/java/org/apache/lucene/search/BlockMaxConjunctionBulkScorer.java:
##########
@@ -170,11 +170,18 @@ private void scoreWindowScoreFirst(
docAndScoreBuffer.size > 0;
scorers[0].nextDocsAndScores(max, acceptDocs, docAndScoreBuffer)) {
+ if (sumOfOtherClauses[1] != sumOfOtherClauses[0]) {
Review Comment:
Would it be better if we add a boolean member and set the value when `computeMaxScore` and use it here ? Just think out loud
##########
lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java:
##########
@@ -381,9 +423,20 @@ private void scoreNonEssentialClauses(
scorer.doc = scorer.iterator.docID();
}
- for (int i = 0; i < buffer.size; ++i) {
- scorable.score = (float) buffer.scores[i];
- collector.collect(buffer.docs[i]);
+ // The collector already filters hits whose score is less than the min competitive score, but
+ // doing it here is a bit more efficient.
+ int[] docs = buffer.docs;
+ docAndScoreBuffer.growNoCopy(buffer.size);
+ float[] scores = docAndScoreBuffer.features;
+ int size = buffer.size;
Review Comment:
This line can be moved before to the `growNoCopy`?
##########
lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java:
##########
@@ -381,9 +423,20 @@ private void scoreNonEssentialClauses(
scorer.doc = scorer.iterator.docID();
}
- for (int i = 0; i < buffer.size; ++i) {
- scorable.score = (float) buffer.scores[i];
- collector.collect(buffer.docs[i]);
+ // The collector already filters hits whose score is less than the min competitive score, but
+ // doing it here is a bit more efficient.
+ int[] docs = buffer.docs;
+ docAndScoreBuffer.growNoCopy(buffer.size);
+ float[] scores = docAndScoreBuffer.features;
+ int size = buffer.size;
Review Comment:
Also, I'm a little bit curious about the performance impact of the tmp variable `docs` and `score`, does it helps to the 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: [PR] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #14970:
URL: https://github.com/apache/lucene/pull/14970#issuecomment-3118028193
Some queries showed a small speedup, e.g. Fuzzy1: https://benchmarks.mikemccandless.com/Fuzzy1.html. No slowdowns.
--
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] Further improve filtering by score. [lucene]
Posted by "HUSTERGS (via GitHub)" <gi...@apache.org>.
HUSTERGS commented on code in PR #14970:
URL: https://github.com/apache/lucene/pull/14970#discussion_r2227361233
##########
lucene/core/src/test/org/apache/lucene/util/TestVectorUtil.java:
##########
@@ -391,7 +392,46 @@ private static int slowFindNextGEQ(int[] buffer, int length, int target, int fro
return length;
}
- public void testFilterByScore() {
+ public void testFilterByFloatScore() {
+ for (int iter = 0; iter < 1_000; ++iter) {
+ int padding = TestUtil.nextInt(random(), 0, 5);
+ DocAndFloatFeatureBuffer b1 = new DocAndFloatFeatureBuffer();
+ DocAndFloatFeatureBuffer b2 = new DocAndFloatFeatureBuffer();
+ b1.growNoCopy(128 + padding);
+ b2.growNoCopy(128 + padding);
+
+ int doc = 0;
+ for (int i = 0; i < 128 + padding; ++i) {
+ doc += TestUtil.nextInt(random(), 1, 1000);
+ b1.docs[i] = b2.docs[i] = doc;
+ b1.features[i] = b2.features[i] = random().nextFloat();
+ }
+
+ float minScoreInclusive = random().nextFloat();
+ int upTo = TestUtil.nextInt(random(), 0, 127);
+ b1.size = slowFilterByScore(b1.docs, b1.features, minScoreInclusive, upTo);
+ b2.size = VectorUtil.filterByScore(b2.docs, b2.features, minScoreInclusive, upTo);
+ assertEquals(b1.size, b2.size);
+ assertTrue(Arrays.equals(b1.docs, 0, b1.size, b2.docs, 0, b2.size));
+ // two double array should be exactly the same, so just use simple Arrays.equals
Review Comment:
nit: should be float array?
##########
lucene/core/src/java/org/apache/lucene/search/ScorerUtil.java:
##########
@@ -138,6 +138,34 @@ static double minRequiredScore(
return minRequiredScore;
}
+ /**
+ * Filters competitive hits from the provided {@link DocAndFloatFeatureBuffer}.
+ *
+ * <p>This method removes documents from the buffer that cannot possibly have a score competitive
+ * enough to exceed the minimum competitive score, given the maximum remaining score and the
+ * number of scorers.
+ */
+ static void filterCompetitiveHits(
+ DocAndFloatFeatureBuffer buffer,
+ double maxRemainingScore,
+ float minCompetitiveScore,
+ int numScorers) {
+ double minRequiredScoreDouble =
+ minRequiredScore(maxRemainingScore, minCompetitiveScore, numScorers);
+ float minRequiredScore = (float) minRequiredScoreDouble;
Review Comment:
nit: would it be better if we rename the `minRequiredScore` to `minRequiredScoreFloat`?
--
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] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14970:
URL: https://github.com/apache/lucene/pull/14970#discussion_r2219663347
##########
lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java:
##########
@@ -381,9 +423,20 @@ private void scoreNonEssentialClauses(
scorer.doc = scorer.iterator.docID();
}
- for (int i = 0; i < buffer.size; ++i) {
- scorable.score = (float) buffer.scores[i];
- collector.collect(buffer.docs[i]);
+ // The collector already filters hits whose score is less than the min competitive score, but
+ // doing it here is a bit more efficient.
+ int[] docs = buffer.docs;
+ docAndScoreBuffer.growNoCopy(buffer.size);
+ float[] scores = docAndScoreBuffer.features;
+ int size = buffer.size;
Review Comment:
I don't think it does. I wanted to avoid copying doc IDs from `docAndScoreAccBuffer` to `docAndScoreBuffer`, so I directly took doc IDs from `docAndScoreAccBuffer` and only copied scores into the `float[]` of `docAndScoreBuffer`. Since it's using arrays from different `Buffer` objects, I found extracting variables clearer.
--
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] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #14970:
URL: https://github.com/apache/lucene/pull/14970
--
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] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #14970:
URL: https://github.com/apache/lucene/pull/14970#issuecomment-3127202234
I cannot reproduce the slowdown locally, but since this change isn't a net win on nightly benchmarks I'll revert.
--
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] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #14970:
URL: https://github.com/apache/lucene/pull/14970#issuecomment-3118072670
I'll wait for one more data point and revert if this isn't noise.
--
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] Further improve filtering by score. [lucene]
Posted by "HUSTERGS (via GitHub)" <gi...@apache.org>.
HUSTERGS commented on code in PR #14970:
URL: https://github.com/apache/lucene/pull/14970#discussion_r2219688801
##########
lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java:
##########
@@ -381,9 +423,20 @@ private void scoreNonEssentialClauses(
scorer.doc = scorer.iterator.docID();
}
- for (int i = 0; i < buffer.size; ++i) {
- scorable.score = (float) buffer.scores[i];
- collector.collect(buffer.docs[i]);
+ // The collector already filters hits whose score is less than the min competitive score, but
+ // doing it here is a bit more efficient.
+ int[] docs = buffer.docs;
+ docAndScoreBuffer.growNoCopy(buffer.size);
+ float[] scores = docAndScoreBuffer.features;
+ int size = buffer.size;
Review Comment:
Oh, I see. Thanks for your explaination !
--
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] Further improve filtering by score. [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14970:
URL: https://github.com/apache/lucene/pull/14970#issuecomment-3094804765
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] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14970:
URL: https://github.com/apache/lucene/pull/14970#discussion_r2219663347
##########
lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java:
##########
@@ -381,9 +423,20 @@ private void scoreNonEssentialClauses(
scorer.doc = scorer.iterator.docID();
}
- for (int i = 0; i < buffer.size; ++i) {
- scorable.score = (float) buffer.scores[i];
- collector.collect(buffer.docs[i]);
+ // The collector already filters hits whose score is less than the min competitive score, but
+ // doing it here is a bit more efficient.
+ int[] docs = buffer.docs;
+ docAndScoreBuffer.growNoCopy(buffer.size);
+ float[] scores = docAndScoreBuffer.features;
+ int size = buffer.size;
Review Comment:
I don't think it does. In case you missed it, it's using the `int[] docs` from `docAndScore*Acc*Buffer` and the `float[] features` from `docAndScoreBuffer`. So I found extracting variables clearer than picking arrays from different buffer objects directly.
--
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] Further improve filtering by score. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #14970:
URL: https://github.com/apache/lucene/pull/14970#issuecomment-3118065391
Hmm I spoke too quickly, there are some queries that seem to exhibit a slowdown actually. E.g. Or3Terms https://benchmarks.mikemccandless.com/Or3Terms.html
--
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