zacharymorn commented on code in PR #972: URL: https://github.com/apache/lucene/pull/972#discussion_r910552971
########## lucene/core/src/java/org/apache/lucene/search/BlockMaxMaxscoreScorer.java: ########## @@ -0,0 +1,322 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.search; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Comparator; +import java.util.LinkedList; +import java.util.List; + +/** Scorer implementing Block-Max Maxscore algorithm */ +public class BlockMaxMaxscoreScorer extends Scorer { + // current doc ID of the leads + private int doc; + + // doc id boundary that all scorers maxScore are valid + private int upTo = -1; + + // heap of scorers ordered by doc ID + private final DisiPriorityQueue essentialsScorers; + // list of scorers ordered by maxScore + private final LinkedList<DisiWrapper> maxScoreSortedEssentialScorers; + + private final DisiWrapper[] allScorers; + + // sum of max scores of scorers in nonEssentialScorers list + private float nonEssentialMaxScoreSum; + + private long cost; + + private final MaxScoreSumPropagator maxScoreSumPropagator; + + // scaled min competitive score + private float minCompetitiveScore = 0; + + private int cachedScoredDoc = -1; + private float cachedScore = 0; + + /** + * Constructs a Scorer that scores doc based on Block-Max-Maxscore (BMM) algorithm + * http://engineering.nyu.edu/~suel/papers/bmm.pdf . This algorithm has lower overhead compared to + * WANDScorer, and could be used for simple disjunction queries. + * + * @param weight The weight to be used. + * @param scorers The sub scorers this Scorer should iterate on for optional clauses + */ + public BlockMaxMaxscoreScorer(Weight weight, List<Scorer> scorers) throws IOException { + super(weight); + + this.doc = -1; + this.allScorers = new DisiWrapper[scorers.size()]; + this.essentialsScorers = new DisiPriorityQueue(scorers.size()); + this.maxScoreSortedEssentialScorers = new LinkedList<>(); + + long cost = 0; + for (int i = 0; i < scorers.size(); i++) { + DisiWrapper w = new DisiWrapper(scorers.get(i)); + cost += w.cost; + allScorers[i] = w; + } + + this.cost = cost; + maxScoreSumPropagator = new MaxScoreSumPropagator(scorers); + } + + @Override + public DocIdSetIterator iterator() { + // twoPhaseIterator needed to honor scorer.setMinCompetitiveScore guarantee + return TwoPhaseIterator.asDocIdSetIterator(twoPhaseIterator()); + } + + @Override + public TwoPhaseIterator twoPhaseIterator() { + DocIdSetIterator approximation = + new DocIdSetIterator() { + + @Override + public int docID() { + return doc; + } + + @Override + public int nextDoc() throws IOException { + return advance(doc + 1); + } + + @Override + public int advance(int target) throws IOException { + while (true) { + + if (target > upTo) { + updateMaxScoresAndLists(target); + } else { + // minCompetitiveScore might have increased, + // move potentially no-longer-competitive scorers from essential to non-essential + // list + movePotentiallyNonCompetitiveScorers(); + } + + assert target <= upTo; + + DisiWrapper top = essentialsScorers.top(); + + if (top == null) { + // all scorers in non-essential list, skip to next boundary or return no_more_docs + if (upTo == NO_MORE_DOCS) { + return doc = NO_MORE_DOCS; + } else { + target = upTo + 1; + } + } else { + // position all scorers in essential list to on or after target + while (top.doc < target) { + top.doc = top.iterator.advance(target); + top = essentialsScorers.updateTop(); + } + + if (top.doc == NO_MORE_DOCS) { + return doc = NO_MORE_DOCS; + } else if (top.doc > upTo) { + target = upTo + 1; + } else { + double docScoreUpperBound = nonEssentialMaxScoreSum; + + for (DisiWrapper w = essentialsScorers.topList(); w != null; w = w.next) { + docScoreUpperBound += w.scorer.score(); + } Review Comment: I just gave it a try, but it seems caching a partial score from essential list here may require more changes / additional data structure inside `score()`, as this scorer no longer maintains the non-essential list explicitly, but only remembers sum of maxScore from non-essential list, so it will need to differentiate scorers from non-essential list when using the cached essential list score. I think I will prefer to have a follow-up issue on this ? ########## lucene/core/src/java/org/apache/lucene/search/WANDScorer.java: ########## @@ -106,7 +106,7 @@ static long scaleMaxScore(float maxScore, 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. */ - private static long scaleMinScore(float minScore, int scalingFactor) { + static long scaleMinScore(float minScore, int scalingFactor) { Review Comment: Updated. -- 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-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
