Lucene - Core
  1. Lucene - Core
  2. LUCENE-4571

speedup disjunction with minShouldMatch

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 4.1
    • Fix Version/s: 4.3, Trunk
    • Component/s: core/search
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      even minShouldMatch is supplied to DisjunctionSumScorer it enumerates whole disjunction, and verifies minShouldMatch condition on every doc:

        public int nextDoc() throws IOException {
          assert doc != NO_MORE_DOCS;
          while(true) {
            while (subScorers[0].docID() == doc) {
              if (subScorers[0].nextDoc() != NO_MORE_DOCS) {
                heapAdjust(0);
              } else {
                heapRemoveRoot();
                if (numScorers < minimumNrMatchers) {
                  return doc = NO_MORE_DOCS;
                }
              }
            }
            afterNext();
            if (nrMatchers >= minimumNrMatchers) {
              break;
            }
          }
          
          return doc;
        }
      

      Stefan Pohl proposes (as well as I get it) to pop nrMatchers-1 scorers from the heap first, and then push them back advancing behind that top doc. For me the question no.1 is there a performance test for minShouldMatch constrained disjunction.

      1. LUCENE-4571.patch
        18 kB
        Stefan Pohl
      2. LUCENE-4571.patch
        17 kB
        Stefan Pohl
      3. LUCENE-4571.patch
        18 kB
        Stefan Pohl
      4. LUCENE-4571.patch
        15 kB
        Stefan Pohl
      5. LUCENE-4571.patch
        15 kB
        Robert Muir
      6. LUCENE-4571.patch
        19 kB
        Robert Muir
      7. LUCENE-4571.patch
        12 kB
        Stefan Pohl

        Activity

        Uwe Schindler made changes -
        Status Resolved [ 5 ] Closed [ 6 ]
        Robert Muir made changes -
        Status Open [ 1 ] Resolved [ 5 ]
        Fix Version/s 5.0 [ 12321663 ]
        Fix Version/s 4.3 [ 12324143 ]
        Resolution Fixed [ 1 ]
        Stefan Pohl made changes -
        Attachment LUCENE-4571.patch [ 12575034 ]
        Stefan Pohl made changes -
        Attachment LUCENE-4571.patch [ 12574992 ]
        Stefan Pohl made changes -
        Attachment LUCENE-4571.patch [ 12574639 ]
        Stefan Pohl made changes -
        Attachment LUCENE-4571.patch [ 12574583 ]
        Robert Muir made changes -
        Attachment LUCENE-4571.patch [ 12570309 ]
        Robert Muir made changes -
        Attachment LUCENE-4571.patch [ 12570301 ]
        Stefan Pohl made changes -
        Attachment LUCENE-4571.patch [ 12570152 ]
        Mikhail Khludnev made changes -
        Comment [ Robert,
        I've got your points. I need some time to familiarize with luceneutil. btw, why it's not in the main Lucene codebase (I assume it's a frequent question)?

        About BS1 (despite it's an offtop formally), I'm not really understand how you want to score via [term-at-time|http://nlp.stanford.edu/IR-book/html/htmledition/computing-vector-scores-1.html#fig:cosinealg] for minShouldMatch, will you allocate more than single bit (or even byte) per document in a buffer? ]
        Mikhail Khludnev made changes -
        Field Original Value New Value
        Description even minShouldMatch is supplied for DisjunctionSumScorer it enumerates whole disjunction, and verifies minShouldMatch condition [on every doc|https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java#L70]:

        {code}
          public int nextDoc() throws IOException {
            assert doc != NO_MORE_DOCS;
            while(true) {
              while (subScorers[0].docID() == doc) {
                if (subScorers[0].nextDoc() != NO_MORE_DOCS) {
                  heapAdjust(0);
                } else {
                  heapRemoveRoot();
                  if (numScorers < minimumNrMatchers) {
                    return doc = NO_MORE_DOCS;
                  }
                }
              }
              afterNext();
              if (nrMatchers >= minimumNrMatchers) {
                break;
              }
            }
            
            return doc;
          }
        {code}

        [~spo] proposes (as well as I get it) to pop nrMatchers-1 scorers from the heap first, and then push them back advancing behind that top doc. For me the question no.1 is there a performance test for minShouldMatch constrained disjunction.
        even minShouldMatch is supplied to DisjunctionSumScorer it enumerates whole disjunction, and verifies minShouldMatch condition [on every doc|https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/DisjunctionSumScorer.java#L70]:

        {code}
          public int nextDoc() throws IOException {
            assert doc != NO_MORE_DOCS;
            while(true) {
              while (subScorers[0].docID() == doc) {
                if (subScorers[0].nextDoc() != NO_MORE_DOCS) {
                  heapAdjust(0);
                } else {
                  heapRemoveRoot();
                  if (numScorers < minimumNrMatchers) {
                    return doc = NO_MORE_DOCS;
                  }
                }
              }
              afterNext();
              if (nrMatchers >= minimumNrMatchers) {
                break;
              }
            }
            
            return doc;
          }
        {code}

        [~spo] proposes (as well as I get it) to pop nrMatchers-1 scorers from the heap first, and then push them back advancing behind that top doc. For me the question no.1 is there a performance test for minShouldMatch constrained disjunction.
        Mikhail Khludnev created issue -

          People

          • Assignee:
            Unassigned
            Reporter:
            Mikhail Khludnev
          • Votes:
            1 Vote for this issue
            Watchers:
            11 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development