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());
   }