You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2024/11/19 09:13:52 UTC
(lucene) branch branch_10x updated (c96ec0be678 -> a67120e1754)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a change to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
from c96ec0be678 Adding filter to the toString() method of KnnFloatVectorQuery (#13990)
new d6afdc4a257 Only consider clauses whose cost is less than the lead cost to compute block boundaries in WANDScorer. (#14000)
new a67120e1754 Speed up top-k retrieval of filtered disjunctions a bit. (#13996)
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
lucene/CHANGES.txt | 3 +
.../lucene/search/BooleanScorerSupplier.java | 2 +-
.../java/org/apache/lucene/search/WANDScorer.java | 119 +++++++++------------
.../org/apache/lucene/search/TestWANDScorer.java | 6 +-
4 files changed, 62 insertions(+), 68 deletions(-)
(lucene) 01/02: Only consider clauses whose cost is less than the lead cost to compute block boundaries in WANDScorer. (#14000)
Posted by jp...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit d6afdc4a257823970caf07aa05c01c4c58ad2788
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Tue Nov 19 09:27:13 2024 +0100
Only consider clauses whose cost is less than the lead cost to compute block boundaries in WANDScorer. (#14000)
WANDScorer implements block-max WAND and needs to recompute score upper bounds
whenever it moves to a different block. Thus it's important for these blocks to
be large enough to avoid re-computing score upper bounds over and over again.
With this commit, WANDScorer no longer uses clauses whose cost is higher than
the cost of the filter to compute block boundaries. This effectively makes
blocks larger when the filter is more selective.
---
lucene/CHANGES.txt | 3 ++
.../lucene/search/BooleanScorerSupplier.java | 2 +-
.../java/org/apache/lucene/search/WANDScorer.java | 49 ++++++++++++----------
.../org/apache/lucene/search/TestWANDScorer.java | 6 ++-
4 files changed, 37 insertions(+), 23 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 0e697a0dab3..00597be0029 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -70,6 +70,9 @@ Optimizations
* GITHUB#13994: Speed up top-k retrieval of filtered conjunctions.
(Adrien Grand)
+* GITHUB#14000: Speed up top-k retrieval of filtered disjunctions.
+ (Adrien Grand)
+
Bug Fixes
---------------------
* GITHUB#13832: Fixed an issue where the DefaultPassageFormatter.format method did not format passages as intended
diff --git a/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java b/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java
index 7a53bc9a485..515d0a6bba1 100644
--- a/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java
+++ b/lucene/core/src/java/org/apache/lucene/search/BooleanScorerSupplier.java
@@ -478,7 +478,7 @@ final class BooleanScorerSupplier extends ScorerSupplier {
// However, as WANDScorer uses more complex algorithm and data structure, we would like to
// still use DisjunctionSumScorer to handle exhaustive pure disjunctions, which may be faster
if ((scoreMode == ScoreMode.TOP_SCORES && topLevelScoringClause) || minShouldMatch > 1) {
- return new WANDScorer(optionalScorers, minShouldMatch, scoreMode);
+ return new WANDScorer(optionalScorers, minShouldMatch, scoreMode, leadCost);
} else {
return new DisjunctionSumScorer(optionalScorers, scoreMode);
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java b/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
index fe5e8803b4c..1a1ae90203e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
@@ -149,8 +149,9 @@ final class WANDScorer extends Scorer {
int freq;
final ScoreMode scoreMode;
+ final long leadCost;
- WANDScorer(Collection<Scorer> scorers, int minShouldMatch, ScoreMode scoreMode)
+ WANDScorer(Collection<Scorer> scorers, int minShouldMatch, ScoreMode scoreMode, long leadCost)
throws IOException {
if (minShouldMatch >= scorers.size()) {
@@ -202,6 +203,7 @@ final class WANDScorer extends Scorer {
scorers.stream().map(Scorer::iterator).mapToLong(DocIdSetIterator::cost),
scorers.size(),
minShouldMatch);
+ this.leadCost = leadCost;
}
// returns a boolean so that it can be called from assert
@@ -386,26 +388,32 @@ final class WANDScorer extends Scorer {
}
private void updateMaxScores(int target) throws IOException {
- if (head.size() == 0) {
- // If the head is empty we use the greatest score contributor as a lead
- // like for conjunctions.
- upTo = tail[0].scorer.advanceShallow(target);
- } else {
- // If we still have entries in 'head', we treat them all as leads and
- // take the minimum of their next block boundaries as a next boundary.
- // We don't take entries in 'tail' into account on purpose: 'tail' is
- // supposed to contain the least score contributors, and taking them
- // into account might not move the boundary fast enough, so we'll waste
- // CPU re-computing the next boundary all the time.
- int newUpTo = DocIdSetIterator.NO_MORE_DOCS;
- for (DisiWrapper w : head) {
- if (w.doc <= newUpTo) {
- newUpTo = Math.min(w.scorer.advanceShallow(w.doc), newUpTo);
- w.scaledMaxScore = scaleMaxScore(w.scorer.getMaxScore(newUpTo), scalingFactor);
- }
+ int newUpTo = DocIdSetIterator.NO_MORE_DOCS;
+ // If we have entries in 'head', we treat them all as leads and take the minimum of their next
+ // block boundaries as a next boundary.
+ // We don't take entries in 'tail' into account on purpose: 'tail' is supposed to contain the
+ // least score contributors, and taking them into account might not move the boundary fast
+ // enough, so we'll waste CPU re-computing the next boundary all the time.
+ // Likewise, we ignore clauses whose cost is greater than the lead cost to avoid recomputing
+ // per-window max scores over and over again. In the event when this makes us compute upTo as
+ // NO_MORE_DOCS, this scorer will effectively implement WAND rather than block-max WAND.
+ for (DisiWrapper w : head) {
+ if (w.doc <= newUpTo && w.cost <= leadCost) {
+ newUpTo = Math.min(w.scorer.advanceShallow(w.doc), newUpTo);
+ w.scaledMaxScore = scaleMaxScore(w.scorer.getMaxScore(newUpTo), scalingFactor);
+ }
+ }
+ // Only look at the tail if none of the `head` clauses had a block we could reuse and if its
+ // cost is less than or equal to the lead cost.
+ if (newUpTo == DocIdSetIterator.NO_MORE_DOCS && tailSize > 0 && tail[0].cost <= leadCost) {
+ newUpTo = tail[0].scorer.advanceShallow(target);
+ // upTo must be on or after the least `head` doc
+ DisiWrapper headTop = head.top();
+ if (headTop != null) {
+ newUpTo = Math.max(newUpTo, headTop.doc);
}
- upTo = newUpTo;
}
+ upTo = newUpTo;
tailMaxScore = 0;
for (int i = 0; i < tailSize; ++i) {
@@ -451,8 +459,7 @@ final class WANDScorer extends Scorer {
}
}
- assert (head.size() == 0 && upTo == DocIdSetIterator.NO_MORE_DOCS)
- || (head.size() > 0 && head.top().doc <= upTo);
+ assert head.size() == 0 || head.top().doc <= upTo;
assert upTo >= target;
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestWANDScorer.java b/lucene/core/src/test/org/apache/lucene/search/TestWANDScorer.java
index 678a0812ebc..ea914f1acaa 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestWANDScorer.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestWANDScorer.java
@@ -1024,7 +1024,11 @@ public class TestWANDScorer extends LuceneTestCase {
final Scorer scorer;
if (optionalScorers.size() > 0) {
scorer =
- new WANDScorer(optionalScorers, query.getMinimumNumberShouldMatch(), scoreMode);
+ new WANDScorer(
+ optionalScorers,
+ query.getMinimumNumberShouldMatch(),
+ scoreMode,
+ Long.MAX_VALUE);
} else {
scorer = weight.scorer(context);
if (scorer == null) return null;
(lucene) 02/02: Speed up top-k retrieval of filtered disjunctions a bit. (#13996)
Posted by jp...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit a67120e17546e3ec6c837ba958819aef4a2529eb
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Tue Nov 19 09:53:45 2024 +0100
Speed up top-k retrieval of filtered disjunctions a bit. (#13996)
This moves work from `advance(int target)` to `TwoPhaseIterator#matches()` so
that we do less work on hits that do not match the filter.
---
lucene/CHANGES.txt | 2 +-
.../java/org/apache/lucene/search/WANDScorer.java | 70 ++++++++--------------
2 files changed, 26 insertions(+), 46 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 00597be0029..ce9fb078ec3 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -70,7 +70,7 @@ Optimizations
* GITHUB#13994: Speed up top-k retrieval of filtered conjunctions.
(Adrien Grand)
-* GITHUB#14000: Speed up top-k retrieval of filtered disjunctions.
+* GITHUB#13996, GITHUB#14000: Speed up top-k retrieval of filtered disjunctions.
(Adrien Grand)
Bug Fixes
diff --git a/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java b/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
index 1a1ae90203e..730058b33ff 100644
--- a/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
@@ -231,7 +231,11 @@ final class WANDScorer extends Scorer {
}
for (DisiWrapper w : head) {
- assert w.doc > doc;
+ if (lead == null) { // After calling advance() but before matches()
+ assert w.doc >= doc;
+ } else {
+ assert w.doc > doc;
+ }
}
return true;
@@ -286,20 +290,21 @@ final class WANDScorer extends Scorer {
// Move 'lead' iterators back to the tail
pushBackLeads(target);
- // Advance 'head' as well
- advanceHead(target);
-
- // Pop the new 'lead' from 'head'
- moveToNextCandidate(target);
+ // Make sure `head` is also on or beyond `target`
+ DisiWrapper headTop = advanceHead(target);
- if (doc == DocIdSetIterator.NO_MORE_DOCS) {
- return DocIdSetIterator.NO_MORE_DOCS;
+ if (scoreMode == ScoreMode.TOP_SCORES && (headTop == null || headTop.doc > upTo)) {
+ // Update score bounds if necessary
+ moveToNextBlock(target);
+ assert upTo >= target;
+ headTop = head.top();
}
- assert ensureConsistent();
-
- // Advance to the next possible match
- return doNextCompetitiveCandidate();
+ if (headTop == null) {
+ return doc = DocIdSetIterator.NO_MORE_DOCS;
+ } else {
+ return doc = headTop.doc;
+ }
}
@Override
@@ -311,6 +316,9 @@ final class WANDScorer extends Scorer {
@Override
public boolean matches() throws IOException {
+ assert lead == null;
+ moveToNextCandidate();
+
while (leadMaxScore < minCompetitiveScore || freq < minShouldMatch) {
if (leadMaxScore + tailMaxScore < minCompetitiveScore
|| freq + tailSize < minShouldMatch) {
@@ -355,7 +363,7 @@ final class WANDScorer extends Scorer {
}
/** Make sure all disis in 'head' are on or after 'target'. */
- private void advanceHead(int target) throws IOException {
+ private DisiWrapper advanceHead(int target) throws IOException {
DisiWrapper headTop = head.top();
while (headTop != null && headTop.doc < target) {
final DisiWrapper evicted = insertTailWithOverFlow(headTop);
@@ -367,6 +375,7 @@ final class WANDScorer extends Scorer {
headTop = head.top();
}
}
+ return headTop;
}
private void advanceTail(DisiWrapper disi) throws IOException {
@@ -437,7 +446,7 @@ final class WANDScorer extends Scorer {
* Update {@code upTo} and maximum scores of sub scorers so that {@code upTo} is greater than or
* equal to the next candidate after {@code target}, i.e. the top of `head`.
*/
- private void updateMaxScoresIfNecessary(int target) throws IOException {
+ private void moveToNextBlock(int target) throws IOException {
assert lead == null;
while (upTo < DocIdSetIterator.NO_MORE_DOCS) {
@@ -467,48 +476,19 @@ final class WANDScorer extends Scorer {
* Set 'doc' to the next potential match, and move all disis of 'head' that are on this doc into
* 'lead'.
*/
- private void moveToNextCandidate(int target) throws IOException {
- if (scoreMode == ScoreMode.TOP_SCORES) {
- // Update score bounds if necessary so
- updateMaxScoresIfNecessary(target);
- assert upTo >= target;
-
- // updateMaxScores tries to move forward until a block with matches is found
- // so if the head is empty it means there are no matches at all anymore
- if (head.size() == 0) {
- assert upTo == DocIdSetIterator.NO_MORE_DOCS;
- doc = DocIdSetIterator.NO_MORE_DOCS;
- return;
- }
- }
-
+ private void moveToNextCandidate() throws IOException {
// The top of `head` defines the next potential match
// pop all documents which are on this doc
lead = head.pop();
+ assert doc == lead.doc;
lead.next = null;
leadMaxScore = lead.scaledMaxScore;
freq = 1;
- doc = lead.doc;
while (head.size() > 0 && head.top().doc == doc) {
addLead(head.pop());
}
}
- /** Move iterators to the tail until there is a potential match. */
- private int doNextCompetitiveCandidate() throws IOException {
- while (leadMaxScore + tailMaxScore < minCompetitiveScore || freq + tailSize < minShouldMatch) {
- // no match on doc is possible, move to the next potential match
- pushBackLeads(doc + 1);
- moveToNextCandidate(doc + 1);
- assert ensureConsistent();
- if (doc == DocIdSetIterator.NO_MORE_DOCS) {
- break;
- }
- }
-
- return doc;
- }
-
/** Advance all entries from the tail to know about all matches on the current doc. */
private void advanceAllTail() throws IOException {
// we return the next doc when the sum of the scores of the potential