Lucene - Core
  1. Lucene - Core
  2. LUCENE-1974

BooleanQuery can not find all matches in special condition

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 2.9
    • Fix Version/s: 2.9.1, 3.0
    • Component/s: core/query/scoring
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      query: (name:tang*)
      doc=5137 score=1.0 doc:Document<stored,indexed<name:tangfulin>>
      doc=11377 score=1.0 doc:Document<stored,indexed<name:tangfulin>>
      query: name:tang* name:notexistnames
      doc=5137 score=0.048133932 doc:Document<stored,indexed<name:tangfulin>>

      It is two queries on the same index, one is just a prefix query in a
      boolean query, and the other is a prefix query plus a term query in a
      boolean query, all with Occur.SHOULD .

      what I wonder is why the later query can not find the doc=11377 doc ?

      the problem can be repreduced by the code in the attachment .

      1. LUCENE-1974.test.patch
        5 kB
        Hoss Man
      2. LUCENE-1974.test.patch
        5 kB
        Hoss Man
      3. LUCENE-1974.patch
        7 kB
        Michael McCandless
      4. BooleanQueryTest.java
        3 kB
        tangfulin

        Activity

        Hide
        Hoss Man added a comment -

        this is the same as the previously attached test but i've simplified it (to me) and revamped it to be a patch that can be applied to 2.9.0.

        I can confirm that it fails for me (against 2.9.0) and seems to suggest a weird hit collection bug somwhere in the BooleanScorer or Prefix scoring code

        (a prefix query works, a boolean query containing term queries work, but a boolean query containing a prefix query fails to find all the expected matches)

        Unless i'm missing something really silly, this suggests a pretty heinious bug somewhere in the core scoring code.

        Show
        Hoss Man added a comment - this is the same as the previously attached test but i've simplified it (to me) and revamped it to be a patch that can be applied to 2.9.0. I can confirm that it fails for me (against 2.9.0) and seems to suggest a weird hit collection bug somwhere in the BooleanScorer or Prefix scoring code (a prefix query works, a boolean query containing term queries work, but a boolean query containing a prefix query fails to find all the expected matches) Unless i'm missing something really silly, this suggests a pretty heinious bug somewhere in the core scoring code.
        Hide
        Hoss Man added a comment -

        tweaked test so that it can be applied to 2.4.1 (by removing readOnly param from IndexSearcher constructor)

        verified this test passes against 2.4.1 ... it's a new bug in 2.9.0

        Show
        Hoss Man added a comment - tweaked test so that it can be applied to 2.4.1 (by removing readOnly param from IndexSearcher constructor) verified this test passes against 2.4.1 ... it's a new bug in 2.9.0
        Hide
        Michael McCandless added a comment -

        Hmm... seems to be a bug in BooleanScorer... if you call static BooleanQuery.setAllowDocsOutOfOrder(false) the test passes (so that's a viable workaround it seems).

        Show
        Michael McCandless added a comment - Hmm... seems to be a bug in BooleanScorer... if you call static BooleanQuery.setAllowDocsOutOfOrder(false) the test passes (so that's a viable workaround it seems).
        Hide
        Robert Muir added a comment -

        Hoss man, i played with this a little, maybe this is all obvious tho

        • test passes if you set BooleanQuery.setAllowDocsOutOfOrder(false) [its booleanscorer, not booleanscorer2]
        • to simplify things, you can use ConstantScoreQuery of a single term instead of PrefixQuery to trigger it

        agree with the comment in the original test, if you trace the execution, the problem is it doesnt actually refill the queue with his second doc (which is docid 11,000 or something). this is because .score() is being called on the subscorer with an end limit of 8192 or so.

        // refill the queue
              more = false;
        ...
                if (subScorerDocID != NO_MORE_DOCS) {
                  more |= sub.scorer.score(sub.collector, end, subScorerDocID);
         ...   
            } while (current != null || more);
        
        Show
        Robert Muir added a comment - Hoss man, i played with this a little, maybe this is all obvious tho test passes if you set BooleanQuery.setAllowDocsOutOfOrder(false) [its booleanscorer, not booleanscorer2] to simplify things, you can use ConstantScoreQuery of a single term instead of PrefixQuery to trigger it agree with the comment in the original test, if you trace the execution, the problem is it doesnt actually refill the queue with his second doc (which is docid 11,000 or something). this is because .score() is being called on the subscorer with an end limit of 8192 or so. // refill the queue more = false ; ... if (subScorerDocID != NO_MORE_DOCS) { more |= sub.scorer.score(sub.collector, end, subScorerDocID); ... } while (current != null || more);
        Hide
        Michael McCandless added a comment -

        Ugh, this is the bug:

        Index: src/java/org/apache/lucene/search/Scorer.java
        ===================================================================
        --- src/java/org/apache/lucene/search/Scorer.java	(revision 824846)
        +++ src/java/org/apache/lucene/search/Scorer.java	(working copy)
        @@ -87,7 +87,7 @@
               collector.collect(doc);
               doc = nextDoc();
             }
        -    return doc == NO_MORE_DOCS;
        +    return doc != NO_MORE_DOCS;
           }
           
           /** Returns the score of the current document matching the query.
        
        

        I'll commit shortly, to trunk & 2.9 branch.

        Show
        Michael McCandless added a comment - Ugh, this is the bug: Index: src/java/org/apache/lucene/search/Scorer.java =================================================================== --- src/java/org/apache/lucene/search/Scorer.java (revision 824846) +++ src/java/org/apache/lucene/search/Scorer.java (working copy) @@ -87,7 +87,7 @@ collector.collect(doc); doc = nextDoc(); } - return doc == NO_MORE_DOCS; + return doc != NO_MORE_DOCS; } /** Returns the score of the current document matching the query. I'll commit shortly, to trunk & 2.9 branch.
        Hide
        Michael Busch added a comment -

        It's also concerning that no unit test catches this...

        Show
        Michael Busch added a comment - It's also concerning that no unit test catches this...
        Hide
        Michael McCandless added a comment -

        It's also concerning that no unit test catches this...

        I agree.... I'll commit tangfulin & Hoss's test case.

        I think the other tests do not catch it because the error only happens if the docID is over 8192 (the chunk size that BooleanScorer uses). Most of our tests work on smaller sets of docs.

        Show
        Michael McCandless added a comment - It's also concerning that no unit test catches this... I agree.... I'll commit tangfulin & Hoss's test case. I think the other tests do not catch it because the error only happens if the docID is over 8192 (the chunk size that BooleanScorer uses). Most of our tests work on smaller sets of docs.
        Hide
        Michael McCandless added a comment -

        Thanks tangfulin and Hoss! I think we need to spin 2.9.1 for this.

        Show
        Michael McCandless added a comment - Thanks tangfulin and Hoss! I think we need to spin 2.9.1 for this.
        Hide
        Yonik Seeley added a comment -

        It's also concerning that no unit test catches this...

        I've said it before, I'll say it again... anything of sufficient complexity really benefits from random tests to hit boundary cases that one would not have thought to code for. We have quite a few in Solr, but not enough. We obviously don't have enough in Lucene either.

        One other simple tactic I've used in Solr to increase the chance of hitting boundary conditions is to make sure many segments are created by default (bad for performance, good for testing), and that cache sizes, window sizes, etc are small so that they are crossed more often by more tests.

        Show
        Yonik Seeley added a comment - It's also concerning that no unit test catches this... I've said it before, I'll say it again... anything of sufficient complexity really benefits from random tests to hit boundary cases that one would not have thought to code for. We have quite a few in Solr, but not enough. We obviously don't have enough in Lucene either. One other simple tactic I've used in Solr to increase the chance of hitting boundary conditions is to make sure many segments are created by default (bad for performance, good for testing), and that cache sizes, window sizes, etc are small so that they are crossed more often by more tests.
        Hide
        Michael McCandless added a comment -

        +1... we need many more tests that do this in Lucene.

        Show
        Michael McCandless added a comment - +1... we need many more tests that do this in Lucene.
        Hide
        Michael Busch added a comment -

        I think we need to spin 2.9.1 for this.

        +1

        +1... we need many more tests that do this in Lucene.

        +1

        Show
        Michael Busch added a comment - I think we need to spin 2.9.1 for this. +1 +1... we need many more tests that do this in Lucene. +1
        Hide
        tangfulin added a comment -

        Good job, Thanks you all for this!

        Though we have spent about a day to change our project back to Lucene 2.4 to avoid the bug, now I think it is time to change it back

        Show
        tangfulin added a comment - Good job, Thanks you all for this! Though we have spent about a day to change our project back to Lucene 2.4 to avoid the bug, now I think it is time to change it back
        Hide
        Michael McCandless added a comment -

        As a test, to tease out more corner cases, I temporarily dropped BooleanScorer's chunk size from 2048 to 16, and ran all tests. Everything passed.

        Show
        Michael McCandless added a comment - As a test, to tease out more corner cases, I temporarily dropped BooleanScorer's chunk size from 2048 to 16, and ran all tests. Everything passed.
        Hide
        Michael McCandless added a comment -

        Though we have spent about a day to change our project back to Lucene 2.4 to avoid the bug, now I think it is time to change it back

        Thank you for finding the bug, narrowing down, and opening issue!! Sorry for all the hassle

        Show
        Michael McCandless added a comment - Though we have spent about a day to change our project back to Lucene 2.4 to avoid the bug, now I think it is time to change it back Thank you for finding the bug, narrowing down, and opening issue!! Sorry for all the hassle
        Hide
        Michael McCandless added a comment -

        I've modified TestBoolean2 to show the bug (attached patch), by
        building up a larger index from the small test index it normally uses.
        I'll commit shortly.

        Here are the conditions that tickle the bug:

        • Must be a BooleanQuery, that contains only SHOULD and up to 32
          MUST_NOT clauses (so that BooleanScorer not BooleanScorer2 is
          used).
        • At least one of the clauses must not be a TermQuery.
        • Must be a segment with more than 4096 docs, and, the clause(s)
          that are not TermQuery must all have no matches in a 2048 chunk
          (and must have valid matches after that chunk). When such a chunk
          is hit, then BooleanScorer stops prematurely.
        Show
        Michael McCandless added a comment - I've modified TestBoolean2 to show the bug (attached patch), by building up a larger index from the small test index it normally uses. I'll commit shortly. Here are the conditions that tickle the bug: Must be a BooleanQuery, that contains only SHOULD and up to 32 MUST_NOT clauses (so that BooleanScorer not BooleanScorer2 is used). At least one of the clauses must not be a TermQuery. Must be a segment with more than 4096 docs, and, the clause(s) that are not TermQuery must all have no matches in a 2048 chunk (and must have valid matches after that chunk). When such a chunk is hit, then BooleanScorer stops prematurely.
        Hide
        Michael McCandless added a comment -

        Bulk close all 2.9.1 issues.

        Show
        Michael McCandless added a comment - Bulk close all 2.9.1 issues.

          People

          • Assignee:
            Michael McCandless
            Reporter:
            tangfulin
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development