SloppyPhraseScorer sometimes misses documents that ExactPhraseScorer finds. [LUCENE-3821]

[asfimport]

The general bug is a case where a phrase with no slop is found,
but if you add slop its not.

I committed a test today (TestSloppyPhraseQuery2) that actually triggers this case,
jenkins just hasn't had enough time to chew on it.

ant test -Dtestcase=TestSloppyPhraseQuery2 -Dtests.iter=100 is enough to make it fail on trunk or 3.x

---

Migrated from LUCENE-3821 by Naomi Dushay, updated Mar 13 2012
Attachments: LUCENE-3821_test.patch, LUCENE-3821.patch (versions: 4), LUCENE-3821-SloppyDecays.patch, schema.xml, solrconfig-test.xml

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

Here's Naomi's original description (moved from description section): including the queries, however I can't
reproduce with just that phrase of the document (I tried, it passes).

I think its a more complex bug in SloppyPhraseScorer... and I can reproduce similar behavior with another test.

In upgrading from Solr 1.4 to Solr 3.5, the following phrase searches stopped working in dismax:
"The Beatles as musicians : Revolver through the Anthology"
"Color-blindness [print/digital]; its dangers and its detection"
Both of these queries have a repeated work, and have many terms. It's not the number of terms or the colon surrounded by spaces, because the following phrase search works in Solr 3.5 (and Solr 1.4):
"International encyclopedia of revolution and protest : 1500 to the present"

With Robert Muir's help, we have narrowed the problem down to slop (proximity in lucene QueryParser, query slop in dismax). I have included debugQuery details for the Beatles search; I confirmed the same behavior with the color-blindness search.

Solr 3.5: it fails when (query) slop setting isn't 0.

lucene QueryParser with proximity set to 1 (or anything > 0) : no match
URL: q=all_search:"The Beatles as musicians : Revolver through the Anthology"\~1
final query: all_search:"the beatl as musician revolv through the antholog"\~1

lucene QueryParser with proximity set to 0: result!
URL: q=all_search:"The Beatles as musicians : Revolver through the Anthology"
final query: all_search:"the beatl as musician revolv through the antholog"

6.0562754 = (MATCH) weight(all_search:"the beatl as musician revolv through the antholog" in 1064395), product of:
<snip>
48.450203 = idf(all_search: the=3531140 beatl=398 as=645923 musician=11805 revolv=872 through=81366 the=3531140 antholog=11611)
<snip>

dismax QueryParser with qs=1: no match
ps=0
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=1&ps=0
final query: +(all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01 (all_search:"the beatl as musician revolv through the antholog")\~0.01
ps=1
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=1&ps=1
final query: +(all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01 (all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01

dismax QueryParser with qs=0: result!
ps=0
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=0&ps=0
final query: +(all_search:"the beatl as musician revolv through the antholog")\~0.01 (all_search:"the beatl as musician revolv through the antholog")\~0.01
ps=1
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=0&ps=1
final query: +(all_search:"the beatl as musician revolv through the antholog")\~0.01 (all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01

8.564867 = (MATCH) sum of:
4.2824335 = (MATCH) weight(all_search:"the beatl as musician revolv through the antholog" in 1064395), product of:
<snip>
48.450203 = idf(all_search: the=3531140 beatl=398 as=645923 musician=11805 revolv=872 through=81366 the=3531140 antholog=11611)
<snip>

Solr 1.4: it works regardless of slop settings

lucene QueryParser with any proximity value: result!
\~0
URL: q=all_search:"The Beatles as musicians : Revolver through the Anthology"
final query: all_search:"the beatl as musician revolv through the antholog"
\~1
URL: q=all_search:"The Beatles as musicians : Revolver through the Anthology"\~1
final query: all_search:"the beatl as musician revolv through the antholog"\~1

5.2672544 = fieldWeight(all_search:"the beatl as musician revolv through the antholog" in 3469163), product of:
<snip>
48.157753 = idf(all_search: the=3549637 beatl=392 as=751093 musician=11992 revolv=822 through=88522 the=3549637 antholog=11246)
<snip>

dismax QueryParser with any qs: result!
qs=0, ps=0
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=0&ps=0
final query: +(all_search:"the beatl as musician revolv through the antholog")\~0.01 (all_search:"the beatl as musician revolv through the antholog")\~0.01
qs=0, ps=1
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=0&ps=1
final query: +(all_search:"the beatl as musician revolv through the antholog")\~0.01 (all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01
dismax QueryParser with qs=0: result!
qs=1, ps=0
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=1&ps=0
final query: +(all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01 (all_search:"the beatl as musician revolv through the antholog")\~0.01
qs=1, ps=1
URL: qf=all_search&pf=all_search&q="The Beatles as musicians : Revolver through the Anthology"&qs=1&ps=1
final query: +(all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01 (all_search:"the beatl as musician revolv through the antholog"\~1)\~0.01

7.4490223 = (MATCH) sum of:
3.7245111 = weight(all_search:"the beatl as musician revolv through the antholog"\~1 in 3469163), product of:
<snip>
48.157753 = idf(all_search: the=3549637 beatl=392 as=751093 musician=11992 revolv=822 through=88522 the=3549637 antholog=11246)
<snip>

More information:

schema.xml:
<field name="all_search" type="text" indexed="true" stored="false" />

solr 3.5:
<fieldtype name="text" class="solr.TextField" positionIncrementGap="100" autoGeneratePhraseQueries="true">
<analyzer>
<tokenizer class="solr.WhitespaceTokenizerFactory" />
<filter class="solr.ICUFoldingFilterFactory"/>
<filter class="solr.WordDelimiterFilterFactory"
splitOnCaseChange="1" generateWordParts="1" catenateWords="1"
splitOnNumerics="0" generateNumberParts="1" catenateNumbers="1"
catenateAll="0" preserveOriginal="0" stemEnglishPossessive="1" />
<filter class="solr.EnglishPorterFilterFactory" protected="protwords.txt" />
<filter class="solr.RemoveDuplicatesTokenFilterFactory" />
</analyzer>
</fieldtype>

solr1.4:
<fieldtype name="text" class="solr.TextField" positionIncrementGap="100">
<analyzer>
<tokenizer class="solr.WhitespaceTokenizerFactory" />
<filter class="schema.UnicodeNormalizationFilterFactory" version="icu4j" composed="false" remove_diacritics="true" remove_modifiers="true" fold="true" />
<filter class="solr.WordDelimiterFilterFactory"
splitOnCaseChange="1" generateWordParts="1" catenateWords="1"
splitOnNumerics="0" generateNumberParts="1" catenateNumbers="1"
catenateAll="0" preserveOriginal="0" stemEnglishPossessive="1" />
<filter class="solr.LowerCaseFilterFactory" />
<filter class="solr.EnglishPorterFilterFactory" protected="protwords.txt" />
<filter class="solr.RemoveDuplicatesTokenFilterFactory" />
</analyzer>
</fieldtype>

And the analysis page shows the same results for Solr 3.5 and 1.4

Solr 3.5:

position 1 2 3 4 5 6 7 8
term text the beatl as musician revolv through the antholog
keyword false false false false false false false false
startOffset 0 4 12 15 27 36 44 48
endOffset 3 11 14 24 35 43 47 57
type word word word word word word word word

Solr 1.4:

term position 1 2 3 4 5 6 7 8
term text the beatl as musician revolv through the antholog
term type word word word word word word word word
source start,end 0,3 4,11 12,14 15,24 27,35 36,43 44,47 48,57

For debug purposes, we can consider the Solr document as:

<doc>
<str name="all_search">The Beatles as musicians : Revolver through the Anthology</str>
</doc>

I can't attached the full SolrDoc as all_search is indexed, but not stored, and I use SolrJ to write to the index from java objects ... plus our objects have a zillion fields (I work in a library with very rich metadata and very exacting solr fields). I have attached the Solr 3.5 schema and solrconfig, but they are big and ugly for the same reasons.

For more details, see the erroneously titled email thread "result present in Solr 1.4 but missing in Solr 3.5, dismax only" started on 2012-02-22 on solr-user@lucene.apache.org.

    Naomi

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

Moving to comments...

[asfimport]

Naomi Dushay (migrated from JIRA)

How's this for a document:

<doc>
<str name="id">1</str>
<str name="title_245a_display">The Beatles as musicians</str>
<str name="title_245a_search">The Beatles as musicians :</str>
<str name="title_245c_display">Walter Everett</str>
<str name="title_display">The Beatles as musicians : Revolver through the Anthology</str>
<str name="title_full_display">The Beatles as musicians : Revolver through the Anthology / Walter Everett.</str>
<str name="title_245_search">The Beatles as musicians : Revolver through the Anthology / Walter Everett.</str>
<str name="title_sort">Beatles as musicians Revolver through the Anthology</str>
<str name="all_search">The Beatles as musicians : Revolver through the Anthology</str>
</doc>

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

Here's an improved test that fails every time.

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

I reviewed the random failures: in all cases it fails, repeated terms are in the query.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

I just @Ignore'd this test... it's creating a lot of Jenkins noise... but we should fix this bug!!

[asfimport]

Doron Cohen (migrated from JIRA)

Fails here too like this:

ant test -Dtestcase=TestSloppyPhraseQuery2 -Dtestmethod=testRandomIncreasingSloppiness -Dtests.seed=-171bbb992c697625:203709d611c854a5:1ca48cb6d33b3f74 -Dargs="-Dfile.encoding=UTF-8"

I'll look into it

[asfimport]

Doron Cohen (migrated from JIRA)

I understand the problem.

It all has to do - as Robert mentioned - with the repeating terms in the phrase query. I am working on a patch - it will change the way that repeats are handled.

Repeating PPs require additional computation - and current SloppyPhraseScorer attempts to do that additional work efficiently, but over simplifies in that and fail to cover all cases.

In the core of things, each time a repeating PP is selected (from the queue) and propagated, all its sibling repeaters are propagated as well, to prevent a case that two repeating PPs point to the same document position (which was the bug that originally triggered handling repeats in this code).

But this is wrong, because it propagates all siblings repeaters, and misses some cases.

Also, the code is hard to read, as Mike noted in #3485 (this comment) ).

So this is a chance to also make the code more maintainable.

I have a working version which is not ready to commit yet, and all the tests pass, except for one which I think is a bug in ExactPhraseScorer, but maybe i am missing something.

The case that fails is this:

AssertionError: Missing in super-set: doc 706
q1: field:"(j o s) (i b j) (t d)"
q2: field:"(j o s) (i b j) (t d)"\~1
td1: [doc=706 score=7.7783184 shardIndex=-1, doc=175 score=6.222655 shardIndex=-1]
td2: [doc=523 score=5.5001016 shardIndex=-1, doc=957 score=5.5001016 shardIndex=-1, doc=228 score=4.400081 shardIndex=-1, doc=357 score=4.400081 shardIndex=-1, doc=390 score=4.400081 shardIndex=-1, doc=503 score=4.400081 shardIndex=-1, doc=602 score=4.400081 shardIndex=-1, doc=757 score=4.400081 shardIndex=-1, doc=758 score=4.400081 shardIndex=-1]
doc 706: Document<stored,indexed,tokenized<field:s o b h j t j z o>>

It seems that q1 too should not match this document?

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Doron do you have the seed for that failure? I can dig on the ExactPhraseScorer...

[asfimport]

Doron Cohen (migrated from JIRA)

Patch with fix for this problem. I would expect SloppyPhrase scoring performance to degrade, though I did not measure it.

The single test that still fails (and I think the bug is in ExactPhraseScorer) is testRandomIncreasingSloppiness, and can be recreated like this:

ant test -Dtestcase=TestSloppyPhraseQuery2 -Dtestmethod=testRandomIncreasingSloppiness -Dtests.seed=47267613db69f714:-617bb800c4a3c645:-456a673444fdc184 -Dargs="-Dfile.encoding=UTF-8"

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Hmm patch has this:

import backport.api.edu.emory.mathcs.backport.java.util.Arrays;

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

Thanks for digging into the problem Doron!

I'm going to be ecstatic if that crazy test finds bugs both in exact and sloppy phrase scorers :)

[asfimport]

Doron Cohen (migrated from JIRA)

Hmm patch has this: ... import backport.api...

Oops, here's a fixed patch, also added some comments, and removed the @Ignore from the test

I'm going to be ecstatic if that crazy test finds bugs both in exact and sloppy phrase scorers :)

It is a great test! Interestingly one thing it exposed is the dependency of the SloppyPhraseScorer in the order of PPs in PhraseScorer when phraseFreq() is invoked. The way things work in the super class, that order depends on the content of previously processed documents. This fix removes that wrong dependency, of course. The point is that deliberately devising a test that exposes such a bug seems almost impossible: first you need to think about such a case, and if you did, writing a test that would create this specific scenario is buggy by itself. Praise to random testing, and this random test in particular.

[asfimport]

Doron Cohen (migrated from JIRA)

The remaining failure still happens with the updated patch (same seed), and still seems to me like an ExactPhraseScorer bug.

However, it is probably not a simple one I think, because when adding to TestMultiPhraseQuery, it passes, that is, no documents are matched, as expected, although this supposedly created the exact scenario that failed above.

Perhaps ExactPhraseScorer behavior too is influenced by other docs processed so far.

  public void test_LUCENE_XYZ() throws Exception {
    Directory indexStore = newDirectory();
    RandomIndexWriter writer = new RandomIndexWriter(random, indexStore);
    add("s o b h j t j z o", "LUCENE-XYZ", writer);
    
    IndexReader reader = writer.getReader();
    IndexSearcher searcher = newSearcher(reader);
    
    MultiPhraseQuery q = new MultiPhraseQuery();
    q.add(new Term[] {new Term("body", "j"), new Term("body", "o"), new Term("body", "s")});
    q.add(new Term[] {new Term("body", "i"), new Term("body", "b"), new Term("body", "j")});
    q.add(new Term[] {new Term("body", "t"), new Term("body", "d")});
    assertEquals("Wrong number of hits", 0,
        searcher.search(q, null, 1).totalHits);
    
    // just make sure no exc:
    searcher.explain(q, 0);
    
    writer.close();
    searcher.close();
    reader.close();
    indexStore.close();
  }

[asfimport]

Doron Cohen (migrated from JIRA)

Update: apparently MultiPhraseQuery.toString does not print its "holes".

So the query that failed was not:

field:"(j o s) (i b j) (t d)"

But rather:

"(j o s) ? (i b j) ? ? (t d)"

Which is a different story: this query should match the document

s o b h j t j z o

There is a match for ExactPhraseScorer, but not for Sloppy with slope 1.
So there is still work to do on SloppyPhraseScorer...

(I'll fix MFQ.toString() as well)