WANDScorer should support two-phase iterator [LUCENE-8806]

[asfimport]

Following #9815 the WANDScorer should leverage two-phase iterators in order to be faster when used in conjunctions.

---

Migrated from LUCENE-8806 by Jim Ferenczi (@jimczi), updated Jul 05 2022
Attachments: LUCENE-8806.patch (versions: 2)

[asfimport]

Jim Ferenczi (@jimczi) (migrated from JIRA)

Here is a patch that leverages two-phase iterators. I'll now run luceneutil's benchmarks to check for regressions.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

The change to correct. Regarding tests, could you have a separate testRandomTwoPhase from testRandom so that we get an idea whether a problem is related to two-phase iteration or not when we get a failure? It'd also be nice to have something similar to testBasics, but for two-phase iterators, maybe we can somehow rewrite testBasics with phrase queries?

I'm wondering whether we could make this more efficient (possibly as a follow-up, the way changes to WANDScorer are designed in your patch is already an improvement, and the ideas I am suggesting may be difficult to implement):

• Right now your patch checks all clauses that are positioned on the current doc. Maybe we could improve this logic to exit early if the fact that one clause doesn't match makes leadMaxScore less than the min competitive score.
• As a follow-up of the above point, we could then look into advancing disis from the tail lazily instead of calling advanceAllTail like the current patch does. In some cases, leadMaxScore+tailMaxScore might become less than the min competitive score before all disis from the tail have advanced.
• We could look into making TwoPhaseIterator#matches return true as soon as one clause returns true instead of checking them all? This would help in the case that score() isn't called.

[asfimport]

Jim Ferenczi (@jimczi) (migrated from JIRA)

Thanks Adrien. Here is a new patch that address your comments. The two phase matches now lazily checks if a clause matches and return immediately if it's the case in order to avoid calling score when it's not needed. If the max scoring clause has a two-phase that doesn't match it updates the maximum score and checks if it remains competitive without the clause. 

I also separated the two phase random test and added a basic two phase test.

I ran luceneutil to spot any regression and here are the results:

Report after iter 10:
                    TaskQPS baseline      StdDev   QPS patch      StdDev                Pct diff
               OrHighLow      323.00      (2.1%)      319.87      (2.2%)   -1.0% (  -5% -    3%)
               OrHighMed       41.38      (1.9%)       41.16      (1.7%)   -0.5% (  -4% -    3%)
              OrHighHigh       13.92      (2.2%)       13.91      (2.9%)   -0.0% (  -5% -    5%)
           OrHighNotHigh      978.67      (2.4%)      984.77      (4.2%)    0.6% (  -5% -    7%)
            OrNotHighMed      960.71      (2.1%)      967.07      (3.6%)    0.7% (  -4% -    6%)
            OrHighNotLow     1258.37      (2.9%)     1266.74      (4.9%)    0.7% (  -6% -    8%)
            OrHighNotMed     1235.58      (2.4%)     1245.76      (4.5%)    0.8% (  -5% -    7%)
           OrNotHighHigh      999.01      (2.2%)     1007.49      (4.1%)    0.8% (  -5% -    7%)
            OrNotHighLow      745.64      (2.9%)      752.46      (3.2%)    0.9% (  -5% -    7%)

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

+1

Can you run luceneutil on some disjunctions of phrase queries to double check it helps?

[asfimport]

Jim Ferenczi (@jimczi) (migrated from JIRA)

I ran luceneutil with some disjunctions of phrase and term queries:

                    TaskQPS baseline      StdDev   QPS patch      StdDev                Pct diff
      HighPhraseHighTerm        8.47      (1.6%)        4.78      (2.6%)  -43.6% ( -47% -  -40%)
       MedPhraseHighTerm       15.54      (1.2%)        9.41      (2.5%)  -39.5% ( -42% -  -36%)
    HighPhraseHighPhrase        5.99      (1.4%)        3.65      (3.0%)  -39.0% ( -42% -  -35%)
     HighPhraseLowPhrase       15.57      (1.2%)       14.26      (3.6%)   -8.4% ( -13% -   -3%)
      LowPhraseLowPhrase       27.25      (2.0%)       31.75      (4.5%)   16.5% (   9% -   23%)
       HighPhraseLowTerm       26.31      (0.9%)       31.42      (3.4%)   19.4% (  14% -   24%)
       HighPhraseMedTerm       12.95      (1.0%)       15.74      (3.8%)   21.6% (  16% -   26%)
      MedPhraseMedPhrase        9.21      (2.4%)       11.50      (8.3%)   24.9% (  13% -   36%)
        MedPhraseLowTerm       24.85      (1.6%)       31.52      (5.5%)   26.8% (  19% -   34%)
      MedPhraseLowPhrase       11.64      (2.3%)       15.06      (7.1%)   29.3% (  19% -   39%)
     HighPhraseMedPhrase        8.27      (2.0%)       10.77      (7.2%)   30.2% (  20% -   40%)
        MedPhraseMedTerm       14.53      (1.7%)       19.33      (5.6%)   33.0% (  25% -   40%)

While the change speeds up some cases it also shows a non-negligible regression with high and med frequencies.
Currently the phrase scorer doesn't check impacts to compute the max score per blocks so I tried to hack a simple patch that merges the impacts of the terms that appear in the phrase query. The patch keeps the minimum frequency per norm value in order to compute an upper bound of the score of the phrase query. I ran luceneutil again with the modified patch and results are much better:

                    TaskQPS baseline      StdDev   QPS patch      StdDev                Pct diff
      HighPhraseHighTerm        8.22      (3.3%)        8.83      (1.9%)    7.4% (   2% -   12%)
      LowPhraseLowPhrase       26.57      (0.7%)       28.55      (5.5%)    7.4% (   1% -   13%)
     HighPhraseMedPhrase        7.98      (0.8%)        9.01      (5.0%)   12.9% (   7% -   18%)
      MedPhraseMedPhrase        8.95      (1.4%)       10.11      (6.6%)   12.9% (   4% -   21%)
       MedPhraseHighTerm       15.10      (1.1%)       17.69      (4.6%)   17.2% (  11% -   23%)
      MedPhraseLowPhrase       11.17      (1.1%)       13.11      (4.9%)   17.4% (  11% -   23%)
     HighPhraseLowPhrase       15.09      (1.5%)       18.85      (7.4%)   24.9% (  15% -   34%)
    HighPhraseHighPhrase        5.75      (2.3%)        7.26      (4.5%)   26.2% (  18% -   33%)
       HighPhraseLowTerm       25.68      (0.7%)       34.46      (2.4%)   34.2% (  30% -   37%)
        MedPhraseMedTerm       14.23      (0.1%)       20.71      (2.3%)   45.5% (  43% -   47%)
        MedPhraseLowTerm       24.30      (0.6%)       38.47      (2.4%)   58.3% (  55% -   61%)
       HighPhraseMedTerm       12.77      (0.6%)       22.21      (3.1%)   73.9% (  69% -   77%)

However simple phrase queries (without disjunctions) seem to be slower with the merging of impacts:

                  TaskQPS baseline      StdDev   QPS patch      StdDev                Pct diff
              HighPhrase       10.48      (0.0%)        9.74      (0.0%)   -7.1% (  -7% -   -7%)
               MedPhrase       20.92      (0.0%)       20.25      (0.0%)   -3.2% (  -3% -   -3%)
               LowPhrase       24.07      (0.0%)       23.33      (0.0%)   -3.1% (  -3% -   -3%)

I am not sure that the merging of impacts is correct so far so I'll add some tests. It's also unrelated to this change (even if it helps for performance) so I'll open a separate issue to discuss this merging of impacts for phrase query separately.
Considering the results of this change alone (two-phase iterator for the wand) I will not merge it yet since it doesn't improve queries with lots of matches but we can revisit when/if the merging of impacts for phrase queries is implemented. WDYT ?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

FYI we have an issue for phrases already #9358.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I'm a bit confused as to why HighPhraseHighTerm and some other queries get so much slower. I was thinking this could only get faster than before since we would now leverage two-phase iterators instead of using iterators naively.

[asfimport]

Jim Ferenczi (@jimczi) (migrated from JIRA)

FYI we have an issue for phrases already LUCENE-8311.

I forgot about this one, thanks!

I was thinking this could only get faster than before since we would now leverage two-phase iterators instead of using iterators naively.

That was my assumption too but not checking the two-phase iterator when looking for candidates forces the second clause (the one with the lowest score) to advance even when the first clause is a false positive. So It might be related to the fact that checking for a match on high frequency phrases is faster than advancing the other clause.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Oh, that is interesting. Are you testing on wikibigall or one of the wikimedium datasets that has truncated content?

[asfimport]

Jim Ferenczi (@jimczi) (migrated from JIRA)

I am testing with wikimediumall

[asfimport]

Denilson Amorim (migrated from JIRA)

I was curious on the status of this issue. Are the benchmarks posted above already considering merging of impacts for phrase queries? That is. two phase iteration is still not a gain on WAND at this time?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Sorry Denilson Amorim I'm not getting your question.

[asfimport]

Denilson Amorim (migrated from JIRA)

Before reformulating my question. Let me see if I understood this patch and the discussion correctly:

WANDScorer doesn't support calling children two-phase iterators. Therefore, in an attempt to improve performance, this patch adds calls to these two-phase iterators in WAND. However, it didn't perform well in phrase queries benchmarks because its max score calculation wasn't per-block. @jimczi hacked a solution during the discussion here to have per-block max scores in phrase scorers, showing a positive outcome.

Since the discussion went idle, phrase scorers received support for per-block max scores through #9358. But this patch hasn't moved. So I was wondering whether it makes sense to move this patch forward.

Thanks in advanced.