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 2017/12/26 16:39:55 UTC
[1/2] lucene-solr:master: LUCENE-8105: ReqOptSumScorer to implement
setMinCompetitiveScore.
Repository: lucene-solr
Updated Branches:
refs/heads/master e82e02940 -> e3f90385b
LUCENE-8105: ReqOptSumScorer to implement setMinCompetitiveScore.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/01023a95
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/01023a95
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/01023a95
Branch: refs/heads/master
Commit: 01023a95c8a05ebd9667457db72fa12031e06086
Parents: e82e029
Author: Adrien Grand <jp...@gmail.com>
Authored: Tue Dec 26 14:14:56 2017 +0100
Committer: Adrien Grand <jp...@gmail.com>
Committed: Tue Dec 26 14:14:56 2017 +0100
----------------------------------------------------------------------
.../apache/lucene/search/ReqOptSumScorer.java | 159 ++++++++++++++--
.../lucene/search/TestReqOptSumScorer.java | 190 +++++++++++++++++++
2 files changed, 333 insertions(+), 16 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/01023a95/lucene/core/src/java/org/apache/lucene/search/ReqOptSumScorer.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/ReqOptSumScorer.java b/lucene/core/src/java/org/apache/lucene/search/ReqOptSumScorer.java
index 35de51a..6b2ace8 100644
--- a/lucene/core/src/java/org/apache/lucene/search/ReqOptSumScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/ReqOptSumScorer.java
@@ -27,9 +27,14 @@ class ReqOptSumScorer extends Scorer {
/** The scorers passed from the constructor.
* These are set to null as soon as their next() or skipTo() returns false.
*/
- protected final Scorer reqScorer;
- protected final Scorer optScorer;
- protected final DocIdSetIterator optIterator;
+ private final Scorer reqScorer;
+ private final Scorer optScorer;
+ private final float reqMaxScore;
+ private final DocIdSetIterator optApproximation;
+ private final TwoPhaseIterator optTwoPhase;
+ private boolean optIsRequired;
+ private final DocIdSetIterator approximation;
+ private final TwoPhaseIterator twoPhase;
/** Construct a <code>ReqOptScorer</code>.
* @param reqScorer The required scorer. This must match.
@@ -44,17 +49,136 @@ class ReqOptSumScorer extends Scorer {
assert optScorer != null;
this.reqScorer = reqScorer;
this.optScorer = optScorer;
- this.optIterator = optScorer.iterator();
+
+ this.reqMaxScore = reqScorer.maxScore();
+
+ final TwoPhaseIterator reqTwoPhase = reqScorer.twoPhaseIterator();
+ this.optTwoPhase = optScorer.twoPhaseIterator();
+ final DocIdSetIterator reqApproximation;
+ if (reqTwoPhase == null) {
+ reqApproximation = reqScorer.iterator();
+ } else {
+ reqApproximation= reqTwoPhase.approximation();
+ }
+ if (optTwoPhase == null) {
+ optApproximation = optScorer.iterator();
+ } else {
+ optApproximation= optTwoPhase.approximation();
+ }
+
+ approximation = new DocIdSetIterator() {
+
+ private int nextCommonDoc(int reqDoc) throws IOException {
+ int optDoc = optApproximation.docID();
+ if (optDoc > reqDoc) {
+ reqDoc = reqApproximation.advance(optDoc);
+ }
+
+ while (true) { // invariant: reqDoc >= optDoc
+ if (reqDoc == optDoc) {
+ return reqDoc;
+ }
+
+ optDoc = optApproximation.advance(reqDoc);
+ if (optDoc == reqDoc) {
+ return reqDoc;
+ }
+ reqDoc = reqApproximation.advance(optDoc);
+ }
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ int doc = reqApproximation.nextDoc();
+ if (optIsRequired) {
+ doc = nextCommonDoc(doc);
+ }
+ return doc;
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ int doc = reqApproximation.advance(target);
+ if (optIsRequired) {
+ doc = nextCommonDoc(doc);
+ }
+ return doc;
+ }
+
+ @Override
+ public int docID() {
+ return reqApproximation.docID();
+ }
+
+ @Override
+ public long cost() {
+ return reqApproximation.cost();
+ }
+
+ };
+
+ if (reqTwoPhase == null && optTwoPhase == null) {
+ this.twoPhase = null;
+ } else {
+ this.twoPhase = new TwoPhaseIterator(approximation) {
+
+ @Override
+ public boolean matches() throws IOException {
+ if (reqTwoPhase != null && reqTwoPhase.matches() == false) {
+ return false;
+ }
+ if (optTwoPhase != null) {
+ if (optIsRequired) {
+ // The below condition is rare and can only happen if we transitioned to optIsRequired=true
+ // after the opt approximation was advanced and before it was confirmed.
+ if (reqScorer.docID() != optApproximation.docID()) {
+ if (optApproximation.docID() < reqScorer.docID()) {
+ optApproximation.advance(reqScorer.docID());
+ }
+ if (reqScorer.docID() != optApproximation.docID()) {
+ return false;
+ }
+ }
+ if (optTwoPhase.matches() == false) {
+ // Advance the iterator to make it clear it doesn't match the current doc id
+ optApproximation.nextDoc();
+ return false;
+ }
+ } else if (optApproximation.docID() == reqScorer.docID() && optTwoPhase.matches() == false) {
+ // Advance the iterator to make it clear it doesn't match the current doc id
+ optApproximation.nextDoc();
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public float matchCost() {
+ float matchCost = 1;
+ if (reqTwoPhase != null) {
+ matchCost += reqTwoPhase.matchCost();
+ }
+ if (optTwoPhase != null) {
+ matchCost += optTwoPhase.matchCost();
+ }
+ return matchCost;
+ }
+ };
+ }
}
@Override
public TwoPhaseIterator twoPhaseIterator() {
- return reqScorer.twoPhaseIterator();
+ return twoPhase;
}
@Override
public DocIdSetIterator iterator() {
- return reqScorer.iterator();
+ if (twoPhase == null) {
+ return approximation;
+ } else {
+ return TwoPhaseIterator.asDocIdSetIterator(twoPhase);
+ }
}
@Override
@@ -62,26 +186,23 @@ class ReqOptSumScorer extends Scorer {
return reqScorer.docID();
}
- /** Returns the score of the current document matching the query.
- * Initially invalid, until the {@link #iterator()} is advanced the first time.
- * @return The score of the required scorer, eventually increased by the score
- * of the optional scorer when it also matches the current document.
- */
@Override
public float score() throws IOException {
// TODO: sum into a double and cast to float if we ever send required clauses to BS1
int curDoc = reqScorer.docID();
float score = reqScorer.score();
- int optScorerDoc = optIterator.docID();
+ int optScorerDoc = optApproximation.docID();
if (optScorerDoc < curDoc) {
- optScorerDoc = optIterator.advance(curDoc);
+ optScorerDoc = optApproximation.advance(curDoc);
+ if (optTwoPhase != null && optScorerDoc == curDoc && optTwoPhase.matches() == false) {
+ optScorerDoc = optApproximation.nextDoc();
+ }
}
-
if (optScorerDoc == curDoc) {
score += optScorer.score();
}
-
+
return score;
}
@@ -91,6 +212,13 @@ class ReqOptSumScorer extends Scorer {
}
@Override
+ public void setMinCompetitiveScore(float minScore) {
+ if (optIsRequired == false && minScore > reqMaxScore) {
+ optIsRequired = true;
+ }
+ }
+
+ @Override
public Collection<ChildScorer> getChildren() {
ArrayList<ChildScorer> children = new ArrayList<>(2);
children.add(new ChildScorer(reqScorer, "MUST"));
@@ -99,4 +227,3 @@ class ReqOptSumScorer extends Scorer {
}
}
-
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/01023a95/lucene/core/src/test/org/apache/lucene/search/TestReqOptSumScorer.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestReqOptSumScorer.java b/lucene/core/src/test/org/apache/lucene/search/TestReqOptSumScorer.java
new file mode 100644
index 0000000..d241e72
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/search/TestReqOptSumScorer.java
@@ -0,0 +1,190 @@
+/*
+ * 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 org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field.Store;
+import org.apache.lucene.document.StringField;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.RandomIndexWriter;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.BooleanClause.Occur;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestReqOptSumScorer extends LuceneTestCase {
+
+ public void testBasics() throws IOException {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir, newIndexWriterConfig().setMergePolicy(
+ // retain doc id order
+ newLogMergePolicy(random().nextBoolean())));
+ Document doc = new Document();
+ doc.add(new StringField("f", "foo", Store.NO));
+ w.addDocument(doc);
+ doc = new Document();
+ doc.add(new StringField("f", "foo", Store.NO));
+ doc.add(new StringField("f", "bar", Store.NO));
+ w.addDocument(doc);
+ doc = new Document();
+ doc.add(new StringField("f", "foo", Store.NO));
+ w.addDocument(doc);
+ doc = new Document();
+ doc.add(new StringField("f", "bar", Store.NO));
+ w.addDocument(doc);
+ doc = new Document();
+ doc.add(new StringField("f", "foo", Store.NO));
+ doc.add(new StringField("f", "bar", Store.NO));
+ w.addDocument(doc);
+ w.forceMerge(1);
+
+ IndexReader reader = w.getReader();
+ w.close();
+ IndexSearcher searcher = newSearcher(reader);
+ Query query = new BooleanQuery.Builder()
+ .add(new ConstantScoreQuery(new TermQuery(new Term("f", "foo"))), Occur.MUST)
+ .add(new ConstantScoreQuery(new TermQuery(new Term("f", "bar"))), Occur.SHOULD)
+ .build();
+ Weight weight = searcher.createNormalizedWeight(query, ScoreMode.TOP_SCORES);
+ LeafReaderContext context = searcher.getIndexReader().leaves().get(0);
+
+ Scorer scorer = weight.scorer(context);
+ assertEquals(0, scorer.iterator().nextDoc());
+ assertEquals(1, scorer.iterator().nextDoc());
+ assertEquals(2, scorer.iterator().nextDoc());
+ assertEquals(4, scorer.iterator().nextDoc());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, scorer.iterator().nextDoc());
+
+ scorer = weight.scorer(context);
+ scorer.setMinCompetitiveScore(Math.nextDown(1f));
+ assertEquals(0, scorer.iterator().nextDoc());
+ assertEquals(1, scorer.iterator().nextDoc());
+ assertEquals(2, scorer.iterator().nextDoc());
+ assertEquals(4, scorer.iterator().nextDoc());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, scorer.iterator().nextDoc());
+
+ scorer = weight.scorer(context);
+ scorer.setMinCompetitiveScore(Math.nextUp(1f));
+ assertEquals(1, scorer.iterator().nextDoc());
+ assertEquals(4, scorer.iterator().nextDoc());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, scorer.iterator().nextDoc());
+
+ scorer = weight.scorer(context);
+ assertEquals(0, scorer.iterator().nextDoc());
+ scorer.setMinCompetitiveScore(Math.nextUp(1f));
+ assertEquals(1, scorer.iterator().nextDoc());
+ assertEquals(4, scorer.iterator().nextDoc());
+ assertEquals(DocIdSetIterator.NO_MORE_DOCS, scorer.iterator().nextDoc());
+
+ reader.close();
+ dir.close();
+ }
+
+ public void testRandomFrequentOpt() throws IOException {
+ doTestRandom(0.5);
+ }
+
+ public void testRandomRareOpt() throws IOException {
+ doTestRandom(0.05);
+ }
+
+ private void doTestRandom(double optFreq) throws IOException {
+ Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir, newIndexWriterConfig());
+ int numDocs = atLeast(1000);
+ for (int i = 0; i < numDocs; ++i) {
+ int numAs = random().nextBoolean() ? 0 : 1 + random().nextInt(5);
+ int numBs = random().nextDouble() < optFreq ? 0 : 1 + random().nextInt(5);
+ Document doc = new Document();
+ for (int j = 0; j < numAs; ++j) {
+ doc.add(new StringField("f", "A", Store.NO));
+ }
+ for (int j = 0; j < numBs; ++j) {
+ doc.add(new StringField("f", "B", Store.NO));
+ }
+ if (random().nextBoolean()) {
+ doc.add(new StringField("f", "C", Store.NO));
+ }
+ w.addDocument(doc);
+ }
+ IndexReader r = w.getReader();
+ w.close();
+ IndexSearcher searcher = newSearcher(r);
+
+ Query mustTerm = new TermQuery(new Term("f", "A"));
+ Query shouldTerm = new TermQuery(new Term("f", "B"));
+ Query query = new BooleanQuery.Builder()
+ .add(mustTerm, Occur.MUST)
+ .add(shouldTerm, Occur.SHOULD)
+ .build();
+
+ TopScoreDocCollector coll = TopScoreDocCollector.create(10, null, true);
+ searcher.search(query, coll);
+ ScoreDoc[] expected = coll.topDocs().scoreDocs;
+
+ // Also test a filtered query, since it does not compute the score on all
+ // matches.
+ query = new BooleanQuery.Builder()
+ .add(query, Occur.MUST)
+ .add(new TermQuery(new Term("f", "C")), Occur.FILTER)
+ .build();
+
+ coll = TopScoreDocCollector.create(10, null, true);
+ searcher.search(query, coll);
+ ScoreDoc[] expectedFiltered = coll.topDocs().scoreDocs;
+
+ for (int i = 0; i < 4; ++i) {
+ Query must = mustTerm;
+ if (i % 2 == 1) {
+ must = new RandomApproximationQuery(must, random());
+ }
+ Query should = shouldTerm;
+ if (i >= 2) {
+ should = new RandomApproximationQuery(should, random());
+ }
+
+ query = new BooleanQuery.Builder()
+ .add(must, Occur.MUST)
+ .add(should, Occur.SHOULD)
+ .build();
+
+ coll = TopScoreDocCollector.create(10, null, false);
+ searcher.search(query, coll);
+ ScoreDoc[] actual = coll.topDocs().scoreDocs;
+
+ CheckHits.checkEqual(query, expected, actual);
+
+ query = new BooleanQuery.Builder()
+ .add(query, Occur.MUST)
+ .add(new RandomApproximationQuery(new TermQuery(new Term("f", "C")), random()), Occur.FILTER)
+ .build();
+
+ coll = TopScoreDocCollector.create(10, null, false);
+ searcher.search(query, coll);
+ ScoreDoc[] actualFiltered = coll.topDocs().scoreDocs;
+
+ CheckHits.checkEqual(query, expectedFiltered, actualFiltered);
+ }
+
+ r.close();
+ dir.close();
+ }
+
+}
[2/2] lucene-solr:master: LUCENE-8097: Implement maxScore() on
disjunctions.
Posted by jp...@apache.org.
LUCENE-8097: Implement maxScore() on disjunctions.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/e3f90385
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/e3f90385
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/e3f90385
Branch: refs/heads/master
Commit: e3f90385b4928e3639ee09a907df323e452c74de
Parents: 01023a9
Author: Adrien Grand <jp...@gmail.com>
Authored: Tue Dec 26 14:19:26 2017 +0100
Committer: Adrien Grand <jp...@gmail.com>
Committed: Tue Dec 26 14:19:26 2017 +0100
----------------------------------------------------------------------
.../lucene/search/DisjunctionMaxQuery.java | 18 +++++---
.../lucene/search/DisjunctionMaxScorer.java | 46 ++++++++++++++++----
.../lucene/search/DisjunctionSumScorer.java | 20 +++++++--
.../org/apache/lucene/search/WANDScorer.java | 14 +++++-
.../java/org/apache/lucene/util/MathUtil.java | 15 +++++++
.../queryparser/xml/DisjunctionMaxQuery.xml | 4 +-
.../lucene/queryparser/xml/TestCoreParser.java | 2 +-
7 files changed, 98 insertions(+), 21 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxQuery.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxQuery.java b/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxQuery.java
index 97c02a6..3285baf 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxQuery.java
@@ -62,6 +62,9 @@ public final class DisjunctionMaxQuery extends Query implements Iterable<Query>
*/
public DisjunctionMaxQuery(Collection<Query> disjuncts, float tieBreakerMultiplier) {
Objects.requireNonNull(disjuncts, "Collection of Querys must not be null");
+ if (tieBreakerMultiplier < 0 || tieBreakerMultiplier > 1) {
+ throw new IllegalArgumentException("tieBreakerMultiplier must be in [0, 1]");
+ }
this.tieBreakerMultiplier = tieBreakerMultiplier;
this.disjuncts = disjuncts.toArray(new Query[disjuncts.size()]);
}
@@ -156,20 +159,25 @@ public final class DisjunctionMaxQuery extends Query implements Iterable<Query>
@Override
public Explanation explain(LeafReaderContext context, int doc) throws IOException {
boolean match = false;
- float max = Float.NEGATIVE_INFINITY;
- double sum = 0;
+ float max = 0;
+ double otherSum = 0;
List<Explanation> subs = new ArrayList<>();
for (Weight wt : weights) {
Explanation e = wt.explain(context, doc);
if (e.isMatch()) {
match = true;
subs.add(e);
- sum += e.getValue();
- max = Math.max(max, e.getValue());
+ float score = e.getValue();
+ if (score >= max) {
+ otherSum += max;
+ max = score;
+ } else {
+ otherSum += score;
+ }
}
}
if (match) {
- final float score = (float) (max + (sum - max) * tieBreakerMultiplier);
+ final float score = (float) (max + otherSum * tieBreakerMultiplier);
final String desc = tieBreakerMultiplier == 0.0f ? "max of:" : "max plus " + tieBreakerMultiplier + " times others of:";
return Explanation.match(score, desc, subs);
} else {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxScorer.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxScorer.java b/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxScorer.java
index 084de66..c5c3640 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxScorer.java
@@ -19,6 +19,8 @@ package org.apache.lucene.search;
import java.io.IOException;
import java.util.List;
+import org.apache.lucene.util.MathUtil;
+
/**
* The Scorer for DisjunctionMaxQuery. The union of all documents generated by the the subquery scorers
* is generated in document number order. The score for each document is the maximum of the scores computed
@@ -28,6 +30,7 @@ import java.util.List;
final class DisjunctionMaxScorer extends DisjunctionScorer {
/* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
private final float tieBreakerMultiplier;
+ private final float maxScore;
/**
* Creates a new instance of DisjunctionMaxScorer
@@ -43,25 +46,52 @@ final class DisjunctionMaxScorer extends DisjunctionScorer {
DisjunctionMaxScorer(Weight weight, float tieBreakerMultiplier, List<Scorer> subScorers, boolean needsScores) {
super(weight, subScorers, needsScores);
this.tieBreakerMultiplier = tieBreakerMultiplier;
+ if (tieBreakerMultiplier < 0 || tieBreakerMultiplier > 1) {
+ throw new IllegalArgumentException("tieBreakerMultiplier must be in [0, 1]");
+ }
+
+ float scoreMax = 0;
+ double otherScoreSum = 0;
+ for (Scorer scorer : subScorers) {
+ float subScore = scorer.maxScore();
+ if (subScore >= scoreMax) {
+ otherScoreSum += scoreMax;
+ scoreMax = subScore;
+ } else {
+ otherScoreSum += subScore;
+ }
+ }
+
+ if (tieBreakerMultiplier == 0) {
+ this.maxScore = scoreMax;
+ } else {
+ // The error of sums depends on the order in which values are summed up. In
+ // order to avoid this issue, we compute an upper bound of the value that
+ // the sum may take. If the max relative error is b, then it means that two
+ // sums are always within 2*b of each other.
+ otherScoreSum *= (1 + 2 * MathUtil.sumRelativeErrorBound(subScorers.size() - 1));
+ this.maxScore = (float) (scoreMax + otherScoreSum * tieBreakerMultiplier);
+ }
}
@Override
protected float score(DisiWrapper topList) throws IOException {
- double scoreSum = 0;
- float scoreMax = Float.NEGATIVE_INFINITY;
+ float scoreMax = 0;
+ double otherScoreSum = 0;
for (DisiWrapper w = topList; w != null; w = w.next) {
- final float subScore = w.scorer.score();
- scoreSum += subScore;
- if (subScore > scoreMax) {
+ float subScore = w.scorer.score();
+ if (subScore >= scoreMax) {
+ otherScoreSum += scoreMax;
scoreMax = subScore;
+ } else {
+ otherScoreSum += subScore;
}
}
- return (float) (scoreMax + (scoreSum - scoreMax) * tieBreakerMultiplier);
+ return (float) (scoreMax + otherScoreSum * tieBreakerMultiplier);
}
@Override
public float maxScore() {
- // TODO: implement but be careful about floating-point errors.
- return Float.POSITIVE_INFINITY;
+ return maxScore;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java b/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java
index 729a298..7e22991 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java
@@ -20,21 +20,36 @@ package org.apache.lucene.search;
import java.io.IOException;
import java.util.List;
+import org.apache.lucene.util.MathUtil;
+
/** A Scorer for OR like queries, counterpart of <code>ConjunctionScorer</code>.
*/
final class DisjunctionSumScorer extends DisjunctionScorer {
-
+
+ private final float maxScore;
+
/** Construct a <code>DisjunctionScorer</code>.
* @param weight The weight to be used.
* @param subScorers Array of at least two subscorers.
*/
DisjunctionSumScorer(Weight weight, List<Scorer> subScorers, boolean needsScores) {
super(weight, subScorers, needsScores);
+ double maxScore = 0;
+ for (Scorer scorer : subScorers) {
+ maxScore += scorer.maxScore();
+ }
+ // The error of sums depends on the order in which values are summed up. In
+ // order to avoid this issue, we compute an upper bound of the value that
+ // the sum may take. If the max relative error is b, then it means that two
+ // sums are always within 2*b of each other.
+ double maxScoreRelativeErrorBound = MathUtil.sumRelativeErrorBound(subScorers.size());
+ this.maxScore = (float) ((1.0 + 2 * maxScoreRelativeErrorBound) * maxScore);
}
@Override
protected float score(DisiWrapper topList) throws IOException {
double score = 0;
+
for (DisiWrapper w = topList; w != null; w = w.next) {
score += w.scorer.score();
}
@@ -43,8 +58,7 @@ final class DisjunctionSumScorer extends DisjunctionScorer {
@Override
public float maxScore() {
- // TODO: implement it but be careful with floating-point errors
- return Float.POSITIVE_INFINITY;
+ return maxScore;
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
----------------------------------------------------------------------
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 2f3b600..f5f647e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/WANDScorer.java
@@ -26,6 +26,8 @@ import java.util.Collection;
import java.util.List;
import java.util.OptionalInt;
+import org.apache.lucene.util.MathUtil;
+
/**
* This implements the WAND (Weak AND) algorithm for dynamic pruning
* described in "Efficient Query Evaluation using a Two-Level Retrieval
@@ -120,6 +122,7 @@ final class WANDScorer extends Scorer {
int tailSize;
final long cost;
+ final float maxScore;
WANDScorer(Weight weight, Collection<Scorer> scorers) {
super(weight);
@@ -142,10 +145,12 @@ final class WANDScorer extends Scorer {
// Use a scaling factor of 0 if all max scores are either 0 or +Infty
this.scalingFactor = scalingFactor.orElse(0);
+ double maxScoreSum = 0;
for (Scorer scorer : scorers) {
DisiWrapper w = new DisiWrapper(scorer);
float maxScore = scorer.maxScore();
w.maxScore = scaleMaxScore(maxScore, this.scalingFactor);
+ maxScoreSum += maxScore;
addLead(w);
}
@@ -154,6 +159,12 @@ final class WANDScorer extends Scorer {
cost += w.cost;
}
this.cost = cost;
+ // The error of sums depends on the order in which values are summed up. In
+ // order to avoid this issue, we compute an upper bound of the value that
+ // the sum may take. If the max relative error is b, then it means that two
+ // sums are always within 2*b of each other.
+ double maxScoreRelativeErrorBound = MathUtil.sumRelativeErrorBound(scorers.size());
+ this.maxScore = (float) ((1.0 + 2 * maxScoreRelativeErrorBound) * maxScoreSum);
}
// returns a boolean so that it can be called from assert
@@ -375,8 +386,7 @@ final class WANDScorer extends Scorer {
@Override
public float maxScore() {
- // TODO: implement but be careful about floating-point errors.
- return Float.POSITIVE_INFINITY;
+ return maxScore;
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/MathUtil.java b/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
index 09437fe..7430c5d 100644
--- a/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
@@ -149,5 +149,20 @@ public final class MathUtil {
return mult * Math.log((1.0d + a) / (1.0d - a));
}
+ /**
+ * Return a relative error bound for a sum of {@code numValues} positive doubles,
+ * computed using recursive summation, ie. sum = x1 + ... + xn.
+ * NOTE: This only works if all values are POSITIVE so that Σ |xi| == |Σ xi|.
+ * This uses formula 3.5 from Higham, Nicholas J. (1993),
+ * "The accuracy of floating point summation", SIAM Journal on Scientific Computing.
+ */
+ public static double sumRelativeErrorBound(int numValues) {
+ if (numValues <= 1) {
+ return 0;
+ }
+ // u = unit roundoff in the paper, also called machine precision or machine epsilon
+ double u = Math.scalb(1.0, -52);
+ return (numValues - 1) * u;
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/DisjunctionMaxQuery.xml
----------------------------------------------------------------------
diff --git a/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/DisjunctionMaxQuery.xml b/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/DisjunctionMaxQuery.xml
index ebf1400..0c94b00 100644
--- a/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/DisjunctionMaxQuery.xml
+++ b/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/DisjunctionMaxQuery.xml
@@ -18,7 +18,7 @@
<DisjunctionMaxQuery>
<TermQuery fieldName="a">merger</TermQuery>
- <DisjunctionMaxQuery tieBreaker="1.2">
+ <DisjunctionMaxQuery tieBreaker="0.3">
<TermQuery fieldName="b">verger</TermQuery>
</DisjunctionMaxQuery>
-</DisjunctionMaxQuery>
\ No newline at end of file
+</DisjunctionMaxQuery>
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e3f90385/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/TestCoreParser.java
----------------------------------------------------------------------
diff --git a/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/TestCoreParser.java b/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/TestCoreParser.java
index d97e2f6..b9e44c1 100644
--- a/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/TestCoreParser.java
+++ b/lucene/queryparser/src/test/org/apache/lucene/queryparser/xml/TestCoreParser.java
@@ -102,7 +102,7 @@ public class TestCoreParser extends LuceneTestCase {
assertEquals(0.0f, d.getTieBreakerMultiplier(), 0.0001f);
assertEquals(2, d.getDisjuncts().size());
DisjunctionMaxQuery ndq = (DisjunctionMaxQuery) d.getDisjuncts().get(1);
- assertEquals(1.2f, ndq.getTieBreakerMultiplier(), 0.0001f);
+ assertEquals(0.3f, ndq.getTieBreakerMultiplier(), 0.0001f);
assertEquals(1, ndq.getDisjuncts().size());
}