- java.lang.Object
-
- org.apache.lucene.search.Scorable
-
- org.apache.lucene.search.Scorer
-
- org.apache.lucene.search.WANDScorer
-
final class WANDScorer extends Scorer
This implements the WAND (Weak AND) algorithm for dynamic pruning described in "Efficient Query Evaluation using a Two-Level Retrieval Process" by Broder, Carmel, Herscovici, Soffer and Zien. Enhanced with techniques described in "Faster Top-k Document Retrieval Using Block-Max Indexes" by Ding and Suel. For scoreMode ==ScoreMode.TOP_SCORES
, this scorer maintains a feedback loop with the collector in order to know at any time the minimum score that is required in order for a hit to be competitive.The implementation supports both minCompetitiveScore by enforce that
∑ max_score >= minCompetitiveScore
, and minShouldMatch by enforcingfreq >= minShouldMatch
. It keeps sub scorers in 3 different places: - tail: a heap that contains scorers that are behind the desired doc ID. These scorers are ordered by cost so that we can advance the least costly ones first. - lead: a linked list of scorer that are positioned on the desired doc ID - head: a heap that contains scorers which are beyond the desired doc ID, ordered by doc ID in order to move quickly to the next candidate.When scoreMode ==
ScoreMode.TOP_SCORES
, it leverages themax score
from each scorer in order to know when it may callDocIdSetIterator.advance(int)
rather thanDocIdSetIterator.nextDoc()
to move to the next competitive hit. When scoreMode !=ScoreMode.TOP_SCORES
, block-max scoring related logic is skipped. Finding the next match consists of first setting the desired doc ID to the least entry in 'head', and then advance 'tail' until there is a match, by meeting the configuredfreq >= minShouldMatch
and / or∑ max_score >= minCompetitiveScore
requirements.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class org.apache.lucene.search.Scorable
Scorable.ChildScorable
-
-
Field Summary
Fields Modifier and Type Field Description private Scorer[]
allScorers
(package private) long
cost
(package private) int
doc
(package private) static int
FLOAT_MANTISSA_BITS
(package private) int
freq
(package private) DisiPriorityQueue
head
(package private) DisiWrapper
lead
(package private) long
leadMaxScore
private static long
MAX_SCALED_SCORE
private long
minCompetitiveScore
(package private) int
minShouldMatch
private int
scalingFactor
(package private) ScoreMode
scoreMode
(package private) DisiWrapper[]
tail
(package private) long
tailMaxScore
(package private) int
tailSize
(package private) int
upTo
-
Constructor Summary
Constructors Constructor Description WANDScorer(Weight weight, java.util.Collection<Scorer> scorers, int minShouldMatch, ScoreMode scoreMode)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addLead(DisiWrapper lead)
Add a disi to the linked list of leads.private void
addTail(DisiWrapper s)
Add an entry to 'tail'.private void
advanceAllTail()
Advance all entries from the tail to know about all matches on the current doc.private void
advanceHead(int target)
Make sure all disis in 'head' are on or after 'target'.int
advanceShallow(int target)
Advance to the block of documents that containstarget
in order to get scoring information about this block.private void
advanceTail()
Pop the entry from the 'tail' that has the greatest score contribution, advance it to the current doc and then add it to 'lead' or 'head' depending on whether it matches.private void
advanceTail(DisiWrapper disi)
int
docID()
Returns the doc ID that is currently being scored.private int
doNextCompetitiveCandidate()
Move iterators to the tail until there is a potential match.private static void
downHeapMaxScore(DisiWrapper[] heap, int size)
private boolean
ensureConsistent()
java.util.Collection<Scorable.ChildScorable>
getChildren()
Returns child sub-scorers positioned on the current documentfloat
getMaxScore(int upTo)
Return the maximum score that documents between the lasttarget
that this iterator wasshallow-advanced
to included andupTo
included.private static boolean
greaterMaxScore(DisiWrapper w1, DisiWrapper w2)
In the tail, we want to get first entries that produce the maximum scores and in case of ties (eg.private DisiWrapper
insertTailWithOverFlow(DisiWrapper s)
Insert an entry in 'tail' and evict the least-costly scorer if full.DocIdSetIterator
iterator()
Return aDocIdSetIterator
over matching documents.private void
moveToNextCandidate(int target)
Set 'doc' to the next potential match, and move all disis of 'head' that are on this doc into 'lead'.private DisiWrapper
popTail()
Pop the least-costly scorer from 'tail'.private void
pushBackLeads(int target)
Move disis that are in 'lead' back to the tail.(package private) static long
scaleMaxScore(float maxScore, int scalingFactor)
Scale max scores in an unsigned integer to avoid overflows (only the lower 32 bits of the long are used) as well as floating-point arithmetic errors.private static long
scaleMinScore(float minScore, int scalingFactor)
Scale min competitive scores the same way as max scores but this time by rounding down in order to make sure that we do not miss any matches.(package private) static int
scalingFactor(float f)
Return a scaling factor for the given float so thatf x 2^scalingFactor
would be in[2^23, 2^24[
.float
score()
Returns the score of the current document matching the query.void
setMinCompetitiveScore(float minScore)
Optional method: Tell the scorer that its iterator may safely ignore all documents whose score is less than the givenminScore
.TwoPhaseIterator
twoPhaseIterator()
Optional method: Return aTwoPhaseIterator
view of thisScorer
.private void
updateMaxScores(int target)
private void
updateMaxScoresIfNecessary(int target)
UpdateupTo
and maximum scores of sub scorers so thatupTo
is greater than or equal to the next candidate aftertarget
, i.e.private static void
upHeapMaxScore(DisiWrapper[] heap, int i)
Heap helpers-
Methods inherited from class org.apache.lucene.search.Scorable
smoothingScore
-
-
-
-
Field Detail
-
FLOAT_MANTISSA_BITS
static final int FLOAT_MANTISSA_BITS
- See Also:
- Constant Field Values
-
MAX_SCALED_SCORE
private static final long MAX_SCALED_SCORE
- See Also:
- Constant Field Values
-
scalingFactor
private final int scalingFactor
-
minCompetitiveScore
private long minCompetitiveScore
-
allScorers
private final Scorer[] allScorers
-
lead
DisiWrapper lead
-
doc
int doc
-
leadMaxScore
long leadMaxScore
-
head
final DisiPriorityQueue head
-
tail
final DisiWrapper[] tail
-
tailMaxScore
long tailMaxScore
-
tailSize
int tailSize
-
cost
final long cost
-
upTo
int upTo
-
minShouldMatch
final int minShouldMatch
-
freq
int freq
-
scoreMode
final ScoreMode scoreMode
-
-
Method Detail
-
scalingFactor
static int scalingFactor(float f)
Return a scaling factor for the given float so thatf x 2^scalingFactor
would be in[2^23, 2^24[
. Special cases:scalingFactor(0) = scalingFactor(MIN_VALUE) + 1 scalingFactor(+Infty) = scalingFactor(MAX_VALUE) - 1
-
scaleMaxScore
static long scaleMaxScore(float maxScore, int scalingFactor)
Scale max scores in an unsigned integer to avoid overflows (only the lower 32 bits of the long are used) as well as floating-point arithmetic errors. Those are rounded up in order to make sure we do not miss any matches.
-
scaleMinScore
private static long scaleMinScore(float minScore, int scalingFactor)
Scale min competitive scores the same way as max scores but this time by rounding down in order to make sure that we do not miss any matches.
-
ensureConsistent
private boolean ensureConsistent()
-
setMinCompetitiveScore
public void setMinCompetitiveScore(float minScore) throws java.io.IOException
Description copied from class:Scorable
Optional method: Tell the scorer that its iterator may safely ignore all documents whose score is less than the givenminScore
. This is a no-op by default.This method may only be called from collectors that use
ScoreMode.TOP_SCORES
, and successive calls may only set increasing values ofminScore
.- Overrides:
setMinCompetitiveScore
in classScorable
- Throws:
java.io.IOException
-
getChildren
public final java.util.Collection<Scorable.ChildScorable> getChildren() throws java.io.IOException
Description copied from class:Scorable
Returns child sub-scorers positioned on the current document- Overrides:
getChildren
in classScorable
- Throws:
java.io.IOException
-
iterator
public DocIdSetIterator iterator()
Description copied from class:Scorer
Return aDocIdSetIterator
over matching documents.The returned iterator will either be positioned on
-1
if no documents have been scored yet,DocIdSetIterator.NO_MORE_DOCS
if all documents have been scored already, or the last document id that has been scored otherwise.The returned iterator is a view: calling this method several times will return iterators that have the same state.
-
twoPhaseIterator
public TwoPhaseIterator twoPhaseIterator()
Description copied from class:Scorer
Optional method: Return aTwoPhaseIterator
view of thisScorer
. A return value ofnull
indicates that two-phase iteration is not supported.Note that the returned
TwoPhaseIterator
'sapproximation
must advance synchronously with theScorer.iterator()
: advancing the approximation must advance the iterator and vice-versa.Implementing this method is typically useful on
Scorer
s that have a high per-document overhead in order to confirm matches.The default implementation returns
null
.- Overrides:
twoPhaseIterator
in classScorer
-
addLead
private void addLead(DisiWrapper lead)
Add a disi to the linked list of leads.
-
pushBackLeads
private void pushBackLeads(int target) throws java.io.IOException
Move disis that are in 'lead' back to the tail.- Throws:
java.io.IOException
-
advanceHead
private void advanceHead(int target) throws java.io.IOException
Make sure all disis in 'head' are on or after 'target'.- Throws:
java.io.IOException
-
advanceTail
private void advanceTail(DisiWrapper disi) throws java.io.IOException
- Throws:
java.io.IOException
-
advanceTail
private void advanceTail() throws java.io.IOException
Pop the entry from the 'tail' that has the greatest score contribution, advance it to the current doc and then add it to 'lead' or 'head' depending on whether it matches.- Throws:
java.io.IOException
-
updateMaxScores
private void updateMaxScores(int target) throws java.io.IOException
- Throws:
java.io.IOException
-
updateMaxScoresIfNecessary
private void updateMaxScoresIfNecessary(int target) throws java.io.IOException
UpdateupTo
and maximum scores of sub scorers so thatupTo
is greater than or equal to the next candidate aftertarget
, i.e. the top of `head`.- Throws:
java.io.IOException
-
moveToNextCandidate
private void moveToNextCandidate(int target) throws java.io.IOException
Set 'doc' to the next potential match, and move all disis of 'head' that are on this doc into 'lead'.- Throws:
java.io.IOException
-
doNextCompetitiveCandidate
private int doNextCompetitiveCandidate() throws java.io.IOException
Move iterators to the tail until there is a potential match.- Throws:
java.io.IOException
-
advanceAllTail
private void advanceAllTail() throws java.io.IOException
Advance all entries from the tail to know about all matches on the current doc.- Throws:
java.io.IOException
-
score
public float score() throws java.io.IOException
Description copied from class:Scorable
Returns the score of the current document matching the query.
-
advanceShallow
public int advanceShallow(int target) throws java.io.IOException
Description copied from class:Scorer
Advance to the block of documents that containstarget
in order to get scoring information about this block. This method is implicitly called byDocIdSetIterator.advance(int)
andDocIdSetIterator.nextDoc()
on the returned doc ID. Calling this method doesn't modify the currentDocIdSetIterator.docID()
. It returns a number that is greater than or equal to all documents contained in the current block, but less than any doc IDS of the next block.target
must be >=Scorable.docID()
as well as all targets that have been passed toScorer.advanceShallow(int)
so far.- Overrides:
advanceShallow
in classScorer
- Throws:
java.io.IOException
-
getMaxScore
public float getMaxScore(int upTo) throws java.io.IOException
Description copied from class:Scorer
Return the maximum score that documents between the lasttarget
that this iterator wasshallow-advanced
to included andupTo
included.- Specified by:
getMaxScore
in classScorer
- Throws:
java.io.IOException
-
docID
public int docID()
Description copied from class:Scorable
Returns the doc ID that is currently being scored.
-
insertTailWithOverFlow
private DisiWrapper insertTailWithOverFlow(DisiWrapper s)
Insert an entry in 'tail' and evict the least-costly scorer if full.
-
addTail
private void addTail(DisiWrapper s)
Add an entry to 'tail'. Fails if over capacity.
-
popTail
private DisiWrapper popTail()
Pop the least-costly scorer from 'tail'.
-
upHeapMaxScore
private static void upHeapMaxScore(DisiWrapper[] heap, int i)
Heap helpers
-
downHeapMaxScore
private static void downHeapMaxScore(DisiWrapper[] heap, int size)
-
greaterMaxScore
private static boolean greaterMaxScore(DisiWrapper w1, DisiWrapper w2)
In the tail, we want to get first entries that produce the maximum scores and in case of ties (eg. constant-score queries), those that have the least cost so that they are likely to advance further.
-
-