[GITHUB-11915] [Discussion Only] Make Lucene smarter about long runs of matches via new API on DISI

This PR is currently work in progress and is for discussion only for https://github.com/apache/lucene/issues/11915

There are no tests about correctness of those new BitSet methods for any implementation (Fixed, Sparse,...). Would it be possible to add them?

There are no tests about correctness of those new BitSet methods for any implementation (Fixed, Sparse,...). Would it be possible to add them?

Thanks for the review and comment @uschindler ! This PR is currently in draft state to facilitate discussion to make sure I'm on the right track. Will definitely add dedicated tests before converting it to formal PR.

Thanks @jpountz for the review and comment!

Did you manage to observe some speedups with this change?

So far I have only able to run wikimedium10m and see the implementation has around -10% slow down (listed below) for full text boolean queries OrXXXNotYYYY due to changes in ReqExclScorer and Lucene90PostingsReader (and the facet ones don't seems to exercise the changes and should be just random fluctuation). I'm currently still searching for any existing benchmarking tasks that can measure these targeted use cases:

Is it actually common to have long runs of matches? For full-text indexes, maybe not so much, only stop words may have runs of adjacent matches. For string fields, this may happen if the field has a default value that is the value of most documents in the collection. Also it's possible for users to use index sorting in order to cluster similar documents together, which increases the likelihood to have long runs of adjacent matches.

Do you have any pointer which benchmark task I could potentially use? If there isn't one available, I could try to add some next.
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
     BrowseRandomLabelTaxoFacets       39.06     (49.1%)       33.42     (45.6%)  -14.4% ( -73% -  157%) 0.335
            BrowseDateTaxoFacets       34.22     (29.5%)       30.49     (27.9%)  -10.9% ( -52% -   65%) 0.229
       BrowseDayOfYearTaxoFacets       34.30     (29.4%)       30.57     (27.9%)  -10.9% ( -52% -   65%) 0.230
                   OrNotHighHigh      426.33      (2.7%)      388.27      (1.6%)   -8.9% ( -12% -   -4%) 0.000
                   OrHighNotHigh      621.42      (2.7%)      573.32      (2.0%)   -7.7% ( -12% -   -3%) 0.000
                    OrHighNotMed      616.08      (3.8%)      573.20      (2.7%)   -7.0% ( -13% -    0%) 0.000
                    OrHighNotLow      562.98      (4.0%)      525.80      (3.3%)   -6.6% ( -13% -    0%) 0.000
                    OrNotHighMed      712.40      (2.6%)      672.88      (2.4%)   -5.5% ( -10% -    0%) 0.000
            HighTermTitleBDVSort       19.04      (7.9%)       18.73      (8.3%)   -1.6% ( -16% -   15%) 0.534
            HighIntervalsOrdered        1.89     (12.3%)        1.86     (15.0%)   -1.6% ( -25% -   29%) 0.719
           BrowseMonthTaxoFacets       32.23     (33.9%)       31.77     (33.6%)   -1.4% ( -51% -  100%) 0.895
                    OrNotHighLow     1719.50      (3.8%)     1696.85      (4.6%)   -1.3% (  -9% -    7%) 0.326
               HighTermTitleSort      202.79      (2.9%)      200.20      (2.8%)   -1.3% (  -6% -    4%) 0.155
                     AndHighHigh       51.74      (5.8%)       51.08      (5.4%)   -1.3% ( -11% -   10%) 0.475
                          Fuzzy1       59.04      (2.7%)       58.36      (3.2%)   -1.2% (  -6% -    4%) 0.214
                         MedTerm     1364.68      (4.4%)     1349.31      (3.4%)   -1.1% (  -8% -    6%) 0.362
                        Wildcard      314.79      (2.8%)      311.35      (3.5%)   -1.1% (  -7% -    5%) 0.277
                         LowTerm     2087.86      (3.2%)     2065.24      (3.8%)   -1.1% (  -7% -    6%) 0.334
             MedIntervalsOrdered       22.66      (8.6%)       22.42     (10.4%)   -1.0% ( -18% -   19%) 0.730
                        PKLookup      331.54      (2.9%)      328.12      (2.6%)   -1.0% (  -6% -    4%) 0.242
             LowIntervalsOrdered      161.90      (9.5%)      160.23     (11.6%)   -1.0% ( -20% -   22%) 0.758
                          Fuzzy2      100.43      (1.5%)       99.40      (3.0%)   -1.0% (  -5% -    3%) 0.169
                         Respell       88.01      (2.0%)       87.27      (2.4%)   -0.8% (  -5% -    3%) 0.223
            BrowseDateSSDVFacets        4.89     (21.4%)        4.85     (20.2%)   -0.8% ( -34% -   51%) 0.905
     BrowseRandomLabelSSDVFacets       19.23      (7.1%)       19.09      (6.2%)   -0.7% ( -13% -   13%) 0.728
                      AndHighMed      114.49      (5.6%)      113.77      (5.0%)   -0.6% ( -10% -   10%) 0.708
                         Prefix3      376.91      (1.4%)      374.65      (2.5%)   -0.6% (  -4% -    3%) 0.348
               HighTermMonthSort     4250.83      (4.2%)     4227.31      (3.6%)   -0.6% (  -7% -    7%) 0.653
                       OrHighMed      209.50      (6.2%)      208.61      (3.4%)   -0.4% (  -9% -    9%) 0.787
                       LowPhrase       89.33      (3.0%)       88.96      (2.2%)   -0.4% (  -5% -    4%) 0.623
       BrowseDayOfYearSSDVFacets       24.82     (10.9%)       24.75     (11.2%)   -0.3% ( -20% -   24%) 0.940
         AndHighMedDayTaxoFacets      158.35      (1.6%)      158.08      (1.8%)   -0.2% (  -3% -    3%) 0.756
                        HighTerm     2076.24      (3.7%)     2074.83      (2.9%)   -0.1% (  -6% -    6%) 0.949
        AndHighHighDayTaxoFacets       14.81      (2.4%)       14.81      (2.9%)   -0.0% (  -5% -    5%) 0.992
                    HighSpanNear       11.02      (2.0%)       11.02      (2.4%)    0.0% (  -4% -    4%) 0.951
                     LowSpanNear      178.01      (1.7%)      178.17      (1.8%)    0.1% (  -3% -    3%) 0.864
                       OrHighLow      473.27      (6.2%)      473.94      (3.3%)    0.1% (  -8% -   10%) 0.929
                      TermDTSort      230.93      (4.7%)      231.36      (3.3%)    0.2% (  -7% -    8%) 0.885
                 MedSloppyPhrase       20.69      (3.0%)       20.76      (3.0%)    0.3% (  -5% -    6%) 0.721
                     MedSpanNear       80.38      (2.2%)       80.66      (2.1%)    0.3% (  -3% -    4%) 0.618
                       MedPhrase       53.03      (1.8%)       53.23      (1.8%)    0.4% (  -3% -    3%) 0.520
                      AndHighLow     2127.04      (4.1%)     2136.55      (3.4%)    0.4% (  -6% -    8%) 0.706
           HighTermDayOfYearSort      594.24      (6.9%)      597.03      (6.3%)    0.5% ( -11% -   14%) 0.822
                      OrHighHigh       53.90      (5.7%)       54.21      (4.0%)    0.6% (  -8% -   10%) 0.709
            MedTermDayTaxoFacets       41.47      (1.1%)       41.75      (2.8%)    0.7% (  -3% -    4%) 0.311
                      HighPhrase      119.60      (2.0%)      120.53      (1.8%)    0.8% (  -2% -    4%) 0.195
                 LowSloppyPhrase      166.00      (5.7%)      167.36      (5.5%)    0.8% (  -9% -   12%) 0.644
                HighSloppyPhrase       43.02      (5.5%)       43.40      (5.2%)    0.9% (  -9% -   12%) 0.610
           BrowseMonthSSDVFacets       24.48      (8.6%)       24.85     (11.6%)    1.5% ( -17% -   23%) 0.638
          OrHighMedDayTaxoFacets        7.71      (3.7%)        7.86      (6.0%)    1.9% (  -7% -   12%) 0.218
                          IntNRQ      115.47     (14.3%)      118.04     (13.2%)    2.2% ( -22% -   34%) 0.610

You explored implementing this new API in several different places: BitSetIterator, doc-value iterator, postings, etc. and it's already a bit exhausting to review and will get worse when we add more tests. I think it would be helpful if we focused on a single thing for the initial PR that focuses on proving that this API is a good addition, adds good testing, and then implement the new API on other implementations of DocIdSetIterator in follow-up PRs.

For sure. Once I'm able to benchmark this and observe good speed up & we are good with the API, I will break up this PR into smaller pieces.

Fun! Thanks for picking this up @zacharymorn. What about updating FixedBitSet#or(disi) to use this? That's used when rewriting MultiTermQuery instances, and I would think we'd see a performance improvement to prefix3 and wildcard benchmark tasks. I guess the thinking there would be to "flip" an entire long to -1L at once if a run of 64 docs is included in a dense DISI sent to the or.
This idea will probably have diminishing returns after #12055, since we now prioritize only building the more sparse iterators into the bitset upfront, but it could still help. If you really want to look for impact, try switching RegexpQuery and PrefixQuery to use CONSTANT_SCORE_REWRITE instead of CONSTANT_SCORE_BLENDED_REWRITE (in there constructors). That should highlight an impact in the benchmark.

Oh and to clarify on my above comment, I’m not trying to create “scope creep” here. In fact, +1 to Adrien’s comment on limiting the scope of the initial PR. Just trying to suggest areas that might be good candidates for seeing initial impact.

Thanks @gsmiller for your review and suggestions!

What about updating FixedBitSet#or(disi) to use this? That's used when rewriting MultiTermQuery instances, and I would think we'd see a performance improvement to prefix3 and wildcard benchmark tasks. I guess the thinking there would be to "flip" an entire long to -1L at once if a run of 64 docs is included in a dense DISI sent to the or (and then subsequently advance beyond the "dense run" in the DISI).
This idea will probably have diminishing returns after https://github.com/apache/lucene/pull/12055, since we now prioritize only building the more sparse iterators into the bitset upfront, but it could still help. If you really want to look for impact, try switching RegexpQuery and PrefixQuery to use CONSTANT_SCORE_REWRITE instead of CONSTANT_SCORE_BLENDED_REWRITE (in there constructors). That should highlight an impact in the benchmark.

I think @mdmarshmallow might be working on this as per https://github.com/apache/lucene/issues/11915#issuecomment-1459502217.  As part of this PR, I've also added a new API to BitSet#nextClearBit just like JDK's BitSet API,  which might be useful here as well.

I think @mdmarshmallow might be working on this as per #11915 (comment). As part of this PR, I've also added a new API to BitSet#nextClearBit just like JDK's BitSet API, which might be useful here as well.

Yeah I am working on it! Hopefully should be done by today as it's not that big of a change :)

Woohoo! Thanks @zacharymorn / @mdmarshmallow! I suspect we may not really see any benefit though if the DISI can only expose the next non-matching doc within its current block. I think the real advantage here would come from being able to actually skip blocks in the DISI, which would rely on knowing that there are actually multiple consecutive "dense" blocks in a DISI. But... if our only way to know there are multiple consecutive "dense" blocks involves decoding those blocks anyway, maybe there isn't much gain to be had? Hmm... not sure. Excited to see what we learn though!

Thanks @mdmarshmallow for working on it! Btw, I just pushed a commit (https://github.com/apache/lucene/pull/12194/commits/f78182bae7e92b23136b5975dbb9d3199e5e3065) that fixed some bugs identified by randomized tests,  you may want to pull that for your work especially if you are using BitSet#nextClearBit method.

I suspect we may not really see any benefit though if the DISI can only expose the next non-matching doc within its current block. I think the real advantage here would come from being able to actually skip blocks in the DISI, which would rely on knowing that there are actually multiple consecutive "dense" blocks in a DISI. But... if our only way to know there are multiple consecutive "dense" blocks involves decoding those blocks anyway, maybe there isn't much gain to be had? Hmm... not sure. Excited to see what we learn though!

@gsmiller Yeah I'm guessing that as well especially for posting and sparse / dense block, as it would take at least one pass to identify the next candidate. I have tried to cache the result as well and would like to see if that helps, and how it performs under benchmark.

Yeah I was doing some of my own debugging and saw some of those issues. I think this fixed a decent amount of the issues I was seeing but I'm still seeing problems with some tests. I'm not sure if it's an issue with my code or not though, so I'll need to dig a bit deeper.

Ok so I did some more investigation, I think there might be a bug with Lucene90PostingsReader.BlockDocsEnum#peekNextNonMatchingDocID. I haven't looked super deeply into it yet, but I can post the patch/seed/test if you want to look into it as well @zacharymorn.

Ok so I did some more investigation, I think there might be a bug with Lucene90PostingsReader.BlockDocsEnum#peekNextNonMatchingDocID. I haven't looked super deeply into it yet, but I can post the patch/seed/test if you want to look into it as well @zacharymorn.

Hmm that seems strange, as I would think this API won't have direct impact to FixedBitSet#or. Where do you see the error? But yeah feel free to upload a patch/test, or post a comment in the diff for changes that you suspect might be wrong.

Sorry for the delayed response, so I saw it in my optimized version of BitSet#or that does use the peekNextNonMatchingDocID API. I also found the bug, it turns out we just weren't resetting the lastNonMatchingDoc in the reset() function. I created a pull request with my BitSet#or changes and the (one-liner) bug fix.
I'm also planning on benchmarking this and will post here when I do.

I tested with wikimedium10m. Looks like my change caused the Prefix3 test to slow down.. not sure why.
                           TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      116.79      (1.7%)      101.89      (1.2%)  -12.8% ( -15% -  -10%) 0.000
                    OrNotHighMed      270.50      (3.5%)      254.28      (2.8%)   -6.0% ( -11% -    0%) 0.000
                   OrHighNotHigh      173.22      (3.7%)      162.94      (3.3%)   -5.9% ( -12% -    1%) 0.000
                   OrNotHighHigh      304.62      (4.0%)      287.18      (2.4%)   -5.7% ( -11% -    0%) 0.000
                    OrHighNotMed      269.23      (4.3%)      257.83      (3.6%)   -4.2% ( -11% -    3%) 0.001
                        Wildcard      411.95      (2.3%)      395.75      (1.9%)   -3.9% (  -7% -    0%) 0.000
                    OrHighNotLow      391.63      (4.5%)      378.58      (3.8%)   -3.3% ( -11% -    5%) 0.012
            HighTermTitleBDVSort       14.56      (7.8%)       14.14      (6.1%)   -2.9% ( -15% -   12%) 0.199
                      OrHighHigh       25.14      (3.3%)       24.68      (4.3%)   -1.8% (  -9% -    5%) 0.131
                       OrHighMed      104.03      (2.8%)      102.70      (4.3%)   -1.3% (  -8% -    6%) 0.267
             MedIntervalsOrdered       11.84      (4.4%)       11.72      (3.8%)   -1.0% (  -8% -    7%) 0.417
                       OrHighLow      395.96      (1.9%)      391.83      (2.0%)   -1.0% (  -4% -    2%) 0.097
            HighIntervalsOrdered       19.10      (3.9%)       18.95      (4.1%)   -0.8% (  -8% -    7%) 0.541
         AndHighMedDayTaxoFacets      112.90      (1.8%)      112.13      (2.2%)   -0.7% (  -4% -    3%) 0.275
                     AndHighHigh       62.08      (3.5%)       61.72      (4.8%)   -0.6% (  -8% -    8%) 0.666
                    OrNotHighLow      875.73      (3.2%)      871.01      (3.3%)   -0.5% (  -6% -    6%) 0.599
                 LowSloppyPhrase        5.77      (2.3%)        5.74      (3.0%)   -0.5% (  -5% -    4%) 0.536
             LowIntervalsOrdered       46.88      (2.6%)       46.63      (2.7%)   -0.5% (  -5% -    4%) 0.540
                 MedSloppyPhrase       10.85      (2.1%)       10.80      (2.7%)   -0.5% (  -5% -    4%) 0.514
                     MedSpanNear       13.61      (3.4%)       13.55      (3.5%)   -0.4% (  -7% -    6%) 0.681
                HighSloppyPhrase       22.71      (3.6%)       22.64      (4.4%)   -0.3% (  -8% -    7%) 0.789
                        HighTerm      279.23      (5.2%)      278.37      (3.9%)   -0.3% (  -8% -    9%) 0.832
          OrHighMedDayTaxoFacets        4.67      (3.9%)        4.65      (3.6%)   -0.3% (  -7% -    7%) 0.809
                      AndHighLow      826.71      (2.5%)      824.54      (2.5%)   -0.3% (  -5% -    4%) 0.740
                        PKLookup      143.32      (3.6%)      143.00      (3.2%)   -0.2% (  -6% -    6%) 0.837
                       LowPhrase      138.92      (1.7%)      138.73      (2.2%)   -0.1% (  -4% -    3%) 0.828
                         LowTerm      436.79      (2.7%)      436.39      (3.7%)   -0.1% (  -6% -    6%) 0.929
                      AndHighMed      165.94      (3.4%)      165.82      (4.3%)   -0.1% (  -7% -    7%) 0.953
                      HighPhrase       75.52      (2.1%)       75.47      (2.1%)   -0.1% (  -4% -    4%) 0.921
            MedTermDayTaxoFacets       23.58      (4.0%)       23.57      (3.2%)   -0.0% (  -7% -    7%) 0.979
                    HighSpanNear       23.96      (2.5%)       23.96      (2.8%)    0.0% (  -5% -    5%) 0.998
                          Fuzzy2       38.68      (1.7%)       38.69      (2.5%)    0.0% (  -4% -    4%) 0.992
        AndHighHighDayTaxoFacets       13.62      (1.8%)       13.63      (1.7%)    0.1% (  -3% -    3%) 0.903
           BrowseMonthSSDVFacets       10.96      (1.2%)       10.97      (1.0%)    0.1% (  -2% -    2%) 0.766
                         Respell       49.97      (1.4%)       50.04      (1.6%)    0.1% (  -2% -    3%) 0.769
                         MedTerm      368.29      (4.8%)      369.09      (4.6%)    0.2% (  -8% -   10%) 0.884
                       MedPhrase       54.77      (3.6%)       54.94      (3.5%)    0.3% (  -6% -    7%) 0.778
           HighTermDayOfYearSort      299.85      (2.2%)      300.91      (1.9%)    0.4% (  -3% -    4%) 0.590
     BrowseRandomLabelSSDVFacets        6.81      (5.8%)        6.83      (6.9%)    0.4% ( -11% -   13%) 0.862
                          IntNRQ      357.58      (6.6%)      358.90      (7.3%)    0.4% ( -12% -   15%) 0.867
                     LowSpanNear      191.59      (1.8%)      192.64      (1.9%)    0.5% (  -3% -    4%) 0.347
               HighTermTitleSort       54.66      (2.5%)       55.03      (3.8%)    0.7% (  -5% -    7%) 0.502
       BrowseDayOfYearTaxoFacets       24.24      (3.5%)       24.41      (4.2%)    0.7% (  -6% -    8%) 0.571
            BrowseDateTaxoFacets       22.67      (3.4%)       22.84      (3.9%)    0.7% (  -6% -    8%) 0.528
                          Fuzzy1       81.52      (1.8%)       82.20      (1.9%)    0.8% (  -2% -    4%) 0.155
               HighTermMonthSort     1730.74      (6.0%)     1753.97      (4.6%)    1.3% (  -8% -   12%) 0.424
            BrowseDateSSDVFacets        2.96      (3.6%)        3.02      (7.2%)    1.8% (  -8% -   12%) 0.323
                      TermDTSort       81.57      (5.2%)       83.17      (4.8%)    2.0% (  -7% -   12%) 0.214
       BrowseDayOfYearSSDVFacets       10.82     (13.3%)       11.09     (16.3%)    2.5% ( -23% -   37%) 0.590
     BrowseRandomLabelTaxoFacets       14.93      (3.9%)       15.37      (5.4%)    2.9% (  -6% -   12%) 0.049
           BrowseMonthTaxoFacets       22.11      (7.3%)       22.99      (7.3%)    3.9% (  -9% -   19%) 0.087

Do you have any pointer which benchmark task I could potentially use? If there isn't one available, I could try to add some next.

Maybe we could try to leverage the geonames dataset (there's a few benchmarks for it in lucene-util), which has a few low-cardinality fields like the time zone or country. Then enable index sorting on these fields. And make sure we're getting performance when using the time zone in required or excluded clauses?

Sorry for the delayed response, so I saw it in my optimized version of BitSet#or that does use the peekNextNonMatchingDocID API. I also found the bug, it turns out we just weren't resetting the lastNonMatchingDoc in the reset() function. I created a pull request with my BitSet#or changes and the (one-liner) bug fix.
I'm also planning on benchmarking this and will post here when I do.

Thanks @mdmarshmallow for the PR and benchmark result. I have left a few comments there. I feel the reasons you are not seeing much change from benchmark could be that the implementation in BitSet#or might got overridden by subclasses, and/or the implementations in subclasses did not utilize their specialized data structures?

Maybe we could try to leverage the geonames dataset (there's a few benchmarks for it in lucene-util), which has a few low-cardinality fields like the time zone or country. Then enable index sorting on these fields. And make sure we're getting performance when using the time zone in required or excluded clauses?

Thanks @jpountz for the suggestion! I actually did something similar by modifying the benchmarking code to support sorting index by month field, which is a KeywordField, and creating corresponding query with the following syntax to exercise the ReqExclScorer - Posting - DocValue path that I have changed:
ReqExclWithDocValues: newbenchmarktest//names docvalues:-month:[Jan TO Aug]
However, while I was able to run this query, the test actually failed when verifying top matches & scores between baseline and modified code. Upon further digging, I realized a potential issue to this API idea. As Lucene does a lot of two phase iterations, and two phase iterator's approximation may provide a superset of the actual matches. If we were to use this API to find and ignore / skip over a bunch of doc ids from approximation, wouldn't the result be inaccurate?
For example, in the below skippingReqApproximation disi I put inside ReqExclScorer, exclApproximation.peekNextNonMatchingDocID() may provide an inaccurate, longer run of matches as approximation provides superset matches. If we were to further confirm the boundary by actually checking matches on its iterator, then we basically resort to linear scan on the iterator, which defeats the purpose of this new API?
final DocIdSetIterator skippingReqApproximation =
        new DocIdSetIterator() {
          @Override
          public int docID() {}

          @Override
          public int nextDoc() throws IOException {}

          @Override
          public int advance(int target) throws IOException {
            // this exclNonMatchingDoc could be inaccruate, as exclApproximation provides a superset of matches than its underlying iterator
            int exclNonMatchingDoc = exclApproximation.peekNextNonMatchingDocID();

            if (exclApproximation.docID() < target
                && target < exclNonMatchingDoc) {
              return reqApproximation.advance(exclNonMatchingDoc);
            } else {
              return reqApproximation.advance(target);
            }
          }

          @Override
          public long cost() {}
        };

Please let me know if you have any suggestion on this.

Hi @jpountz,  I was able to create a sorted index with new low-cardinality field quarter, run some new benchmark tasks like below, and see substantial improvement for the new tasks (with around -7% impacts to not-long-running terms):
AndHighNotQuarter: +last -quarter:q1 #  freq=830278
AndHighNotQuarter: +united -quarter:q2 #  freq=1185528
AndHighNotQuarter: +year -quarter:q3 #  freq=1098425
AndHighNotQuarter: +its -quarter:q4 #  freq=1160703
AndHighNotQuarter: +but -quarter:q1 #  freq=1484398
AndMedNotQuarter: +mostly -quarter:q2 #  freq=89401
AndMedNotQuarter: +interview -quarter:q3 #  freq=94736
AndMedNotQuarter: +9 -quarter:q4 #  freq=541405
AndMedNotQuarter: +hard -quarter:q1 #  freq=92045
AndMedNotQuarter: +bay -quarter:q2 #  freq=117167

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                   OrNotHighHigh      574.77      (3.1%)      535.14      (3.2%)   -6.9% ( -12% -    0%) 0.000
                   OrHighNotHigh      423.02      (3.6%)      396.20      (3.6%)   -6.3% ( -13% -    0%) 0.000
                    OrHighNotMed      746.53      (3.7%)      702.90      (4.5%)   -5.8% ( -13% -    2%) 0.000
                    OrHighNotLow      750.04      (4.4%)      712.78      (4.5%)   -5.0% ( -13% -    4%) 0.000
                    OrNotHighMed      653.88      (3.0%)      624.44      (3.9%)   -4.5% ( -11% -    2%) 0.000
                    OrNotHighLow     1205.35      (5.4%)     1185.91      (5.8%)   -1.6% ( -12% -   10%) 0.363
                        PKLookup      269.07      (2.4%)      266.45      (3.0%)   -1.0% (  -6% -    4%) 0.259
                      AndHighMed      146.24      (6.4%)      144.93      (6.1%)   -0.9% ( -12% -   12%) 0.649
                        Wildcard      220.71      (3.3%)      218.75      (2.7%)   -0.9% (  -6% -    5%) 0.352
               HighTermTitleSort      148.58      (3.3%)      147.26      (2.7%)   -0.9% (  -6% -    5%) 0.347
            HighTermTitleBDVSort       35.47      (2.5%)       35.18      (2.0%)   -0.8% (  -5% -    3%) 0.247
           BrowseMonthTaxoFacets       35.20     (35.1%)       34.93     (38.6%)   -0.8% ( -55% -  112%) 0.948
                        HighTerm      714.46      (4.1%)      710.25      (3.5%)   -0.6% (  -7% -    7%) 0.626
                         MedTerm     1063.86      (4.3%)     1058.95      (3.4%)   -0.5% (  -7% -    7%) 0.707
                       OrHighMed      192.38      (3.0%)      191.49      (2.6%)   -0.5% (  -5% -    5%) 0.602
                         Prefix3      259.99      (5.9%)      258.85      (6.3%)   -0.4% ( -11% -   12%) 0.821
                      OrHighHigh       39.21      (2.9%)       39.06      (2.2%)   -0.4% (  -5% -    4%) 0.639
                       LowPhrase       65.71      (2.5%)       65.53      (2.6%)   -0.3% (  -5% -    4%) 0.723
                         Respell      105.97      (2.6%)      105.72      (1.7%)   -0.2% (  -4% -    4%) 0.740
            MedTermDayTaxoFacets       38.03      (2.7%)       37.98      (2.2%)   -0.1% (  -4% -    4%) 0.869
                    HighSpanNear       10.67      (2.5%)       10.66      (2.3%)   -0.1% (  -4% -    4%) 0.865
                       MedPhrase       97.20      (3.3%)       97.11      (2.8%)   -0.1% (  -6% -    6%) 0.931
                      AndHighLow     1597.01      (5.2%)     1596.89      (4.1%)   -0.0% (  -8% -    9%) 0.996
                     AndHighHigh       64.16      (4.5%)       64.17      (4.0%)    0.0% (  -8% -    8%) 0.995
         AndHighMedDayTaxoFacets       91.65      (1.6%)       91.73      (2.4%)    0.1% (  -3% -    4%) 0.894
                          Fuzzy2      101.73      (2.5%)      101.84      (2.5%)    0.1% (  -4% -    5%) 0.889
        AndHighHighDayTaxoFacets        6.90      (3.0%)        6.91      (2.3%)    0.1% (  -4% -    5%) 0.890
                HighSloppyPhrase       39.46      (3.9%)       39.54      (3.2%)    0.2% (  -6% -    7%) 0.870
          OrHighMedDayTaxoFacets       22.70      (4.9%)       22.74      (5.7%)    0.2% (  -9% -   11%) 0.899
                     MedSpanNear      117.54      (2.8%)      117.84      (1.9%)    0.3% (  -4% -    5%) 0.735
                          Fuzzy1      189.31      (2.7%)      189.83      (2.8%)    0.3% (  -5% -    5%) 0.753
                      HighPhrase       92.14      (2.9%)       92.41      (2.5%)    0.3% (  -4% -    5%) 0.731
                     LowSpanNear      111.85      (2.1%)      112.29      (2.6%)    0.4% (  -4% -    5%) 0.594
                       OrHighLow      175.33      (4.6%)      176.33      (4.0%)    0.6% (  -7% -    9%) 0.675
                 LowSloppyPhrase       60.26      (3.4%)       60.65      (3.0%)    0.7% (  -5% -    7%) 0.522
                 MedSloppyPhrase      102.93      (3.3%)      103.90      (3.2%)    0.9% (  -5% -    7%) 0.362
             MedIntervalsOrdered       18.60      (5.5%)       18.82      (6.5%)    1.2% ( -10% -   13%) 0.542
            HighIntervalsOrdered        5.94      (8.4%)        6.01      (8.9%)    1.2% ( -14% -   20%) 0.671
                          IntNRQ      183.09      (7.7%)      185.85      (5.7%)    1.5% ( -11% -   16%) 0.482
               HighTermMonthSort     3709.41      (5.6%)     3771.76      (6.9%)    1.7% ( -10% -   15%) 0.400
           HighTermDayOfYearSort      492.50      (5.3%)      501.64      (3.4%)    1.9% (  -6% -   11%) 0.185
             LowIntervalsOrdered      252.81      (8.1%)      258.30      (9.8%)    2.2% ( -14% -   21%) 0.446
                         LowTerm     1057.85      (6.4%)     1081.16      (8.1%)    2.2% ( -11% -   17%) 0.342
                      TermDTSort      253.74      (5.9%)      259.66      (4.5%)    2.3% (  -7% -   13%) 0.161
            BrowseDateSSDVFacets        5.08     (21.2%)        5.28     (24.8%)    3.9% ( -34% -   63%) 0.589
       BrowseDayOfYearSSDVFacets       26.14     (25.7%)       27.21     (34.3%)    4.1% ( -44% -   86%) 0.670
           BrowseMonthSSDVFacets       26.25     (23.4%)       27.98     (30.7%)    6.6% ( -38% -   79%) 0.446
       BrowseDayOfYearTaxoFacets       39.48     (35.1%)       42.26     (34.3%)    7.0% ( -46% -  117%) 0.522
            BrowseDateTaxoFacets       39.49     (35.1%)       42.32     (34.3%)    7.2% ( -46% -  117%) 0.513
               AndHighNotQuarter      147.80      (1.7%)      389.73      (9.5%)  163.7% ( 150% -  177%) 0.000
                AndMedNotQuarter      112.31      (1.1%)      430.97     (13.3%)  283.7% ( 266% -  301%) 0.000

I feel the result so far looks promising. With regard to the question I raised earlier:

As Lucene does a lot of two phase iterations, and two phase iterator's approximation may provide a superset of the actual matches. If we were to use this API to find and ignore / skip over a bunch of doc ids from approximation, wouldn't the result be inaccurate?

maybe one "solution" could be to mark this API as expert only, and warn that any concrete implementation should provide an exact range rather than approximated range?

As Lucene does a lot of two phase iterations, and two phase iterator's approximation may provide a superset of the actual matches. If we were to use this API to find and ignore / skip over a bunch of doc ids from approximation, wouldn't the result be inaccurate?

Indeed we need to be careful wrt how this new API is used with two-phase iterators. The code path that you shared should only be enabled when there is no two-phase confirmation? It will force linear evaluation of matches with two-phase iterators, but I think it's fine, these tend to be slow anyway.

I feel the result so far looks promising.

Very cool indeed!

I have some suggestions for moving this PR forward:

Enhance CheckIndex to check that peekNextNonMatcthingDocID is correct.
Enhance AssertingScorer to check that peekNextNonMatchingDocID is only called when the iterator is positioned. Also check return values.
Revert changes to bitsets and doc-value iterators, let's only focus on postings and negations to keep this initial PR simple? We'll add support for bitsets and doc-value iterators in follow-ups? Maybe we could consider conjunctions too for this initial PR, which are far more common than negations in my experience.
See if we can leverage skip data to skip over longer ranges of doc IDs with postings.
See if we can reduce the slowdown on OrNotHighHigh and other negations when the optimization does not kick in.
A quarter field is a bit extreme, see if we can also observe good speedups with something less extreme like the month field?

I have some suggestions for moving this PR forward:

Enhance CheckIndex to check that peekNextNonMatcthingDocID is correct.
Enhance AssertingScorer to check that peekNextNonMatchingDocID is only called when the iterator is positioned. Also check return values.
Revert changes to bitsets and doc-value iterators, let's only focus on postings and negations to keep this initial PR simple? We'll add support for bitsets and doc-value iterators in follow-ups? Maybe we could consider conjunctions too for this initial PR, which are far more common than negations in my experience.
See if we can leverage skip data to skip over longer ranges of doc IDs with postings.
See if we can reduce the slowdown on OrNotHighHigh and other negations when the optimization does not kick in.
A quarter field is a bit extreme, see if we can also observe good speedups with something less extreme like the month field?

Thanks @jpountz for the suggestions! The plan makes sense to me. I have pushed a commit https://github.com/apache/lucene/pull/12194/commits/b2184995df34cb1e42ff987c37c7c81ecb55aca6 to revert changes to bitset, doc values and ReqExclScorer (since it leveraged approximation and also negatively impacted OrNotXY queries), as well as benchmark the implementation via month. The latest benchmark results look something like these:
Tasks: (had to use monthPostings here since month was already taken as doc value field`
AndHighNotMonth: +last -monthPostings:jan #  freq=830278
AndHighNotMonth: +united -monthPostings:feb #  freq=1185528
AndHighNotMonth: +year -monthPostings:mar #  freq=1098425
AndHighNotMonth: +its -monthPostings:apr #  freq=1160703
AndHighNotMonth: +but -monthPostings:may #  freq=1484398
AndMedNotMonth: +mostly -monthPostings:jun #  freq=89401
AndMedNotMonth: +interview -monthPostings:jul #  freq=94736
AndMedNotMonth: +9 -monthPostings:aug #  freq=541405
AndMedNotMonth: +hard -monthPostings:sep #  freq=92045
AndMedNotMonth: +bay -monthPostings:oct #  freq=117167

Results:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
          OrHighMedDayTaxoFacets       18.68      (5.2%)       18.11      (5.5%)   -3.1% ( -13% -    8%) 0.069
             LowIntervalsOrdered      216.28      (8.6%)      211.46      (9.9%)   -2.2% ( -19% -   17%) 0.447
             MedIntervalsOrdered       84.99     (11.5%)       83.27     (12.6%)   -2.0% ( -23% -   25%) 0.597
            HighIntervalsOrdered       27.27      (8.5%)       26.73      (9.0%)   -2.0% ( -17% -   16%) 0.468
           HighTermDayOfYearSort      464.57      (3.5%)      455.78      (6.3%)   -1.9% ( -11% -    8%) 0.237
            BrowseDateTaxoFacets       18.29      (3.0%)       18.11      (3.1%)   -1.0% (  -6% -    5%) 0.304
               HighTermTitleSort      203.48      (2.1%)      201.63      (2.1%)   -0.9% (  -5% -    3%) 0.174
       BrowseDayOfYearSSDVFacets       14.53      (7.4%)       14.40      (6.0%)   -0.9% ( -13% -   13%) 0.674
                         LowTerm     1262.59      (5.6%)     1253.06      (6.1%)   -0.8% ( -11% -   11%) 0.684
            MedTermDayTaxoFacets       29.75      (2.3%)       29.56      (1.4%)   -0.7% (  -4% -    3%) 0.283
                      AndHighMed      366.10      (4.4%)      363.76      (5.3%)   -0.6% (  -9% -    9%) 0.676
                      HighPhrase      228.16      (2.5%)      227.25      (2.8%)   -0.4% (  -5% -    4%) 0.633
                        PKLookup      314.34      (3.1%)      313.17      (3.7%)   -0.4% (  -6% -    6%) 0.730
         AndHighMedDayTaxoFacets       57.70      (2.9%)       57.52      (2.4%)   -0.3% (  -5% -    5%) 0.714
                      TermDTSort      211.54      (3.5%)      211.05      (5.1%)   -0.2% (  -8% -    8%) 0.869
        AndHighHighDayTaxoFacets       26.74      (1.7%)       26.71      (1.5%)   -0.1% (  -3% -    3%) 0.877
                       LowPhrase       20.75      (2.6%)       20.74      (2.7%)   -0.0% (  -5% -    5%) 0.958
                       MedPhrase      117.30      (2.4%)      117.36      (1.9%)    0.0% (  -4% -    4%) 0.946
                       OrHighMed      202.92      (5.4%)      203.12      (4.6%)    0.1% (  -9% -   10%) 0.950
                     AndHighHigh       74.03      (3.9%)       74.10      (4.6%)    0.1% (  -8% -    8%) 0.940
                     LowSpanNear       45.31      (1.3%)       45.45      (0.8%)    0.3% (  -1% -    2%) 0.371
                        Wildcard      190.90      (3.1%)      191.52      (3.3%)    0.3% (  -5% -    6%) 0.748
       BrowseDayOfYearTaxoFacets       14.14      (2.4%)       14.20      (3.6%)    0.4% (  -5% -    6%) 0.687
            BrowseDateSSDVFacets        4.98     (17.3%)        5.00     (17.5%)    0.5% ( -29% -   42%) 0.927
                         Respell       89.97      (2.0%)       90.42      (1.9%)    0.5% (  -3% -    4%) 0.424
                          IntNRQ       85.40     (19.5%)       85.93     (18.0%)    0.6% ( -30% -   47%) 0.916
                      OrHighHigh       45.64      (5.8%)       45.93      (3.7%)    0.6% (  -8% -   10%) 0.679
            HighTermTitleBDVSort       37.81      (1.0%)       38.09      (2.0%)    0.7% (  -2% -    3%) 0.131
                 MedSloppyPhrase       19.19      (3.2%)       19.34      (3.9%)    0.8% (  -6% -    8%) 0.485
                    HighSpanNear       10.28      (1.6%)       10.37      (1.2%)    0.8% (  -1% -    3%) 0.069
                       OrHighLow      914.57      (4.8%)      922.44      (4.1%)    0.9% (  -7% -   10%) 0.543
                HighSloppyPhrase        8.44      (3.5%)        8.52      (4.1%)    0.9% (  -6% -    8%) 0.452
                    OrNotHighLow     1686.77      (3.6%)     1702.27      (3.7%)    0.9% (  -6% -    8%) 0.425
                 LowSloppyPhrase      240.50      (2.0%)      242.74      (2.9%)    0.9% (  -3% -    5%) 0.239
                          Fuzzy2       24.44      (1.7%)       24.68      (1.1%)    1.0% (  -1% -    3%) 0.030
               HighTermMonthSort     3940.53      (4.8%)     3979.49      (4.7%)    1.0% (  -8% -   10%) 0.507
                   OrHighNotHigh      510.95      (4.1%)      516.14      (3.5%)    1.0% (  -6% -    8%) 0.398
                          Fuzzy1      127.91      (1.6%)      129.29      (1.3%)    1.1% (  -1% -    4%) 0.022
                    OrNotHighMed      781.43      (3.5%)      790.15      (3.7%)    1.1% (  -5% -    8%) 0.324
                   OrNotHighHigh      525.59      (3.3%)      532.45      (3.1%)    1.3% (  -4% -    8%) 0.200
                         MedTerm     1202.24      (3.7%)     1220.51      (4.8%)    1.5% (  -6% -   10%) 0.263
                    OrHighNotMed      569.55      (4.2%)      578.34      (3.7%)    1.5% (  -6% -    9%) 0.216
                     MedSpanNear      136.46      (2.2%)      138.57      (1.9%)    1.5% (  -2% -    5%) 0.019
                    OrHighNotLow      676.93      (4.2%)      687.46      (4.0%)    1.6% (  -6% -   10%) 0.233
                        HighTerm      946.83      (4.1%)      961.82      (4.9%)    1.6% (  -7% -   10%) 0.266
           BrowseMonthSSDVFacets       20.58     (12.2%)       20.94     (21.8%)    1.7% ( -28% -   40%) 0.756
                      AndHighLow     1538.93      (5.6%)     1569.90      (5.7%)    2.0% (  -8% -   14%) 0.263
           BrowseMonthTaxoFacets       16.67      (3.9%)       17.04      (4.1%)    2.2% (  -5% -   10%) 0.079
                         Prefix3     1668.64      (3.7%)     1709.38      (4.6%)    2.4% (  -5% -   11%) 0.064
                  AndMedNotMonth      879.42      (4.1%)     1142.62      (5.9%)   29.9% (  19% -   41%) 0.000
                 AndHighNotMonth      373.72      (4.9%)      600.07      (7.2%)   60.6% (  46% -   76%) 0.000

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
           BrowseMonthSSDVFacets       22.81     (23.8%)       21.14     (15.0%)   -7.3% ( -37% -   41%) 0.244
           BrowseMonthTaxoFacets       17.09      (3.4%)       16.89      (4.2%)   -1.2% (  -8% -    6%) 0.332
           HighTermDayOfYearSort      532.86      (5.1%)      528.05      (6.2%)   -0.9% ( -11% -   10%) 0.614
       BrowseDayOfYearSSDVFacets       14.73      (3.9%)       14.64      (7.2%)   -0.6% ( -11% -   10%) 0.732
                      TermDTSort      226.03      (4.8%)      225.35      (4.8%)   -0.3% (  -9% -    9%) 0.842
                        PKLookup      312.28      (3.6%)      311.52      (2.5%)   -0.2% (  -6% -    6%) 0.805
                    OrHighNotMed      557.57      (5.3%)      556.42      (3.9%)   -0.2% (  -8% -    9%) 0.888
                   OrHighNotHigh      443.79      (4.5%)      443.12      (3.8%)   -0.2% (  -8% -    8%) 0.910
                          IntNRQ      119.18      (2.9%)      119.05      (3.4%)   -0.1% (  -6% -    6%) 0.910
         AndHighMedDayTaxoFacets      154.34      (3.0%)      154.17      (4.1%)   -0.1% (  -6% -    7%) 0.921
                        HighTerm      642.18      (4.7%)      641.61      (3.0%)   -0.1% (  -7% -    8%) 0.944
        AndHighHighDayTaxoFacets        9.79      (3.5%)        9.79      (3.6%)   -0.0% (  -6% -    7%) 0.970
                         MedTerm      927.37      (3.9%)      927.88      (3.5%)    0.1% (  -7% -    7%) 0.963
                          Fuzzy2      135.91      (2.6%)      136.03      (2.7%)    0.1% (  -5% -    5%) 0.911
                       MedPhrase      191.19      (2.5%)      191.39      (2.7%)    0.1% (  -4% -    5%) 0.900
                         Respell       97.25      (2.1%)       97.38      (1.4%)    0.1% (  -3% -    3%) 0.820
                    OrHighNotLow      683.76      (4.4%)      684.68      (4.2%)    0.1% (  -8% -    9%) 0.921
                          Fuzzy1      132.14      (2.6%)      132.37      (2.7%)    0.2% (  -4% -    5%) 0.835
                    OrNotHighMed      634.06      (3.8%)      635.26      (4.9%)    0.2% (  -8% -    9%) 0.892
                        Wildcard      247.85      (3.8%)      248.34      (2.1%)    0.2% (  -5% -    6%) 0.837
       BrowseDayOfYearTaxoFacets       13.96      (1.8%)       13.99      (1.5%)    0.2% (  -3% -    3%) 0.688
                      HighPhrase      203.79      (2.1%)      204.33      (2.5%)    0.3% (  -4% -    4%) 0.713
                       LowPhrase      153.51      (1.9%)      154.15      (2.6%)    0.4% (  -4% -    5%) 0.563
             LowIntervalsOrdered      146.20      (3.2%)      146.81      (3.4%)    0.4% (  -5% -    7%) 0.688
            HighTermTitleBDVSort       32.43      (1.8%)       32.57      (3.1%)    0.4% (  -4% -    5%) 0.587
            MedTermDayTaxoFacets       73.26      (1.3%)       73.62      (1.7%)    0.5% (  -2% -    3%) 0.307
                     MedSpanNear       99.50      (1.8%)      100.01      (1.8%)    0.5% (  -2% -    4%) 0.365
                         LowTerm     1091.52      (5.3%)     1097.52      (4.9%)    0.6% (  -9% -   11%) 0.733
                     LowSpanNear      278.50      (2.0%)      280.09      (2.0%)    0.6% (  -3% -    4%) 0.369
            HighIntervalsOrdered       36.70      (5.9%)       36.92      (6.5%)    0.6% ( -11% -   13%) 0.758
          OrHighMedDayTaxoFacets        6.96      (3.4%)        7.00      (2.9%)    0.6% (  -5% -    7%) 0.518
                 LowSloppyPhrase       29.02      (3.8%)       29.23      (3.8%)    0.7% (  -6% -    8%) 0.543
                       OrHighLow      601.05      (4.1%)      605.60      (5.1%)    0.8% (  -8% -   10%) 0.605
                   OrNotHighHigh      530.94      (4.3%)      535.17      (3.4%)    0.8% (  -6% -    8%) 0.515
                         Prefix3      302.43      (4.2%)      304.98      (5.8%)    0.8% (  -8% -   11%) 0.599
                HighSloppyPhrase       56.77      (3.1%)       57.25      (3.6%)    0.8% (  -5% -    7%) 0.429
                    HighSpanNear       20.22      (1.2%)       20.39      (1.7%)    0.9% (  -2% -    3%) 0.070
             MedIntervalsOrdered      103.06      (4.5%)      104.16      (5.0%)    1.1% (  -7% -   10%) 0.473
                       OrHighMed      276.47      (2.9%)      279.58      (4.4%)    1.1% (  -5% -    8%) 0.338
                      OrHighHigh       51.21      (3.4%)       51.80      (4.2%)    1.1% (  -6% -    9%) 0.341
                      AndHighMed      230.11      (3.5%)      232.91      (4.9%)    1.2% (  -6% -    9%) 0.365
                      AndHighLow     2054.63      (4.8%)     2080.21      (4.8%)    1.2% (  -7% -   11%) 0.413
                 MedSloppyPhrase       89.55      (4.0%)       90.71      (5.1%)    1.3% (  -7% -   10%) 0.373
               HighTermTitleSort      193.20      (3.1%)      195.79      (4.2%)    1.3% (  -5% -    8%) 0.256
                     AndHighHigh       67.40      (3.4%)       68.31      (4.4%)    1.3% (  -6% -    9%) 0.276
            BrowseDateTaxoFacets       18.16      (3.0%)       18.42      (3.1%)    1.5% (  -4% -    7%) 0.125
               HighTermMonthSort     3913.52      (4.4%)     3974.57      (6.4%)    1.6% (  -8% -   12%) 0.369
                    OrNotHighLow     1855.59      (5.1%)     1899.00      (5.3%)    2.3% (  -7% -   13%) 0.155
            BrowseDateSSDVFacets        4.61     (19.0%)        5.32     (25.4%)   15.5% ( -24% -   73%) 0.029
                  AndMedNotMonth      865.67      (2.8%)     1088.95      (4.8%)   25.8% (  17% -   34%) 0.000
                 AndHighNotMonth       75.79      (0.6%)      275.41     (14.5%)  263.4% ( 246% -  280%) 0.000

I'll work on the rest in the next few days.

Hi @jpountz , I have been able to add some more changes for all the areas you mentioned, and here are the are the latest benchmark results (with benchmark code changes in https://github.com/mikemccand/luceneutil/pull/213):
Index sorted by month
Result 1 (one task has close to 800% improvement!):
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      416.18      (1.7%)      380.25      (2.1%)   -8.6% ( -12% -   -4%) 0.000
               HighTermTitleSort       71.98      (7.2%)       68.87      (2.3%)   -4.3% ( -12% -    5%) 0.011
           BrowseMonthSSDVFacets       22.25     (20.2%)       21.42     (16.9%)   -3.8% ( -34% -   41%) 0.522
        AndHighHighDayTaxoFacets       31.20      (2.5%)       30.03      (2.1%)   -3.7% (  -8% -    0%) 0.000
                        Wildcard      198.43      (2.8%)      191.62      (3.3%)   -3.4% (  -9% -    2%) 0.000
         AndHighMedDayTaxoFacets       79.19      (2.4%)       76.51      (1.9%)   -3.4% (  -7% -    0%) 0.000
            MedTermDayTaxoFacets       29.12      (2.7%)       28.20      (2.7%)   -3.2% (  -8% -    2%) 0.000
          OrHighMedDayTaxoFacets        3.12      (7.8%)        3.03      (7.1%)   -2.8% ( -16% -   13%) 0.244
             MedIntervalsOrdered       92.67      (6.9%)       90.84      (7.2%)   -2.0% ( -15% -   13%) 0.376
                      AndHighMed      293.88      (6.0%)      289.04      (5.9%)   -1.7% ( -12% -   10%) 0.381
               HighTermMonthSort     3424.90      (3.9%)     3371.57      (4.1%)   -1.6% (  -9% -    6%) 0.217
                          IntNRQ      109.72      (4.2%)      108.07      (4.4%)   -1.5% (  -9% -    7%) 0.274
                        PKLookup      288.62      (3.9%)      284.30      (2.8%)   -1.5% (  -7% -    5%) 0.161
                      TermDTSort      208.11      (7.2%)      205.01      (3.2%)   -1.5% ( -11% -    9%) 0.396
                     AndHighHigh       85.20      (5.1%)       84.04      (6.2%)   -1.4% ( -11% -   10%) 0.446
           HighTermDayOfYearSort      402.61      (7.1%)      397.22      (6.0%)   -1.3% ( -13% -   12%) 0.519
                    HighSpanNear       54.21      (1.8%)       53.56      (2.0%)   -1.2% (  -4% -    2%) 0.045
                      AndHighLow     1349.28      (5.6%)     1334.43      (5.2%)   -1.1% ( -11% -   10%) 0.522
            HighIntervalsOrdered        5.47      (9.4%)        5.41      (9.3%)   -1.1% ( -18% -   19%) 0.714
                     LowSpanNear       16.30      (1.0%)       16.12      (0.9%)   -1.1% (  -2% -    0%) 0.000
            HighTermTitleBDVSort       36.06      (2.5%)       35.78      (3.4%)   -0.8% (  -6% -    5%) 0.409
                       OrHighMed      120.91      (4.0%)      120.00      (3.9%)   -0.7% (  -8% -    7%) 0.546
                    OrNotHighMed      550.15      (3.2%)      546.31      (3.1%)   -0.7% (  -6% -    5%) 0.488
                       OrHighLow      704.06      (2.6%)      699.32      (3.5%)   -0.7% (  -6% -    5%) 0.486
             LowIntervalsOrdered      135.87      (6.3%)      135.14      (6.6%)   -0.5% ( -12% -   13%) 0.793
       BrowseDayOfYearSSDVFacets       14.38      (4.4%)       14.31      (4.3%)   -0.5% (  -8% -    8%) 0.725
                      OrHighHigh       33.97      (5.2%)       33.82      (4.7%)   -0.5% (  -9% -    9%) 0.769
                   OrNotHighHigh      247.33      (5.9%)      246.43      (3.4%)   -0.4% (  -9% -    9%) 0.811
                    OrNotHighLow     1212.86      (4.0%)     1209.13      (2.9%)   -0.3% (  -6% -    6%) 0.782
                         LowTerm     1160.44      (3.9%)     1157.61      (3.3%)   -0.2% (  -7% -    7%) 0.829
                     MedSpanNear       90.90      (1.9%)       90.83      (2.9%)   -0.1% (  -4% -    4%) 0.927
                         Respell      117.51      (2.2%)      117.57      (2.1%)    0.1% (  -4% -    4%) 0.934
                       LowPhrase       83.46      (3.2%)       83.54      (2.9%)    0.1% (  -5% -    6%) 0.925
                       MedPhrase      136.08      (2.3%)      136.43      (2.5%)    0.3% (  -4% -    5%) 0.734
                   OrHighNotHigh      667.08      (5.9%)      669.58      (4.0%)    0.4% (  -8% -   10%) 0.813
                    OrHighNotLow      527.38      (8.5%)      530.21      (5.4%)    0.5% ( -12% -   15%) 0.812
                          Fuzzy1      121.61      (3.0%)      122.46      (2.5%)    0.7% (  -4% -    6%) 0.424
                          Fuzzy2      108.09      (2.6%)      108.88      (2.4%)    0.7% (  -4% -    5%) 0.353
                      HighPhrase      166.93      (3.4%)      168.28      (2.9%)    0.8% (  -5% -    7%) 0.416
       BrowseDayOfYearTaxoFacets       13.50      (4.9%)       13.63      (0.7%)    1.0% (  -4% -    6%) 0.372
            BrowseDateTaxoFacets       17.77      (3.0%)       17.96      (2.4%)    1.1% (  -4% -    6%) 0.217
                    OrHighNotMed      631.08      (7.1%)      638.31      (4.8%)    1.1% ( -10% -   14%) 0.553
                 LowSloppyPhrase       34.90      (3.9%)       35.34      (3.6%)    1.3% (  -5% -    9%) 0.281
                        HighTerm      755.56      (8.4%)      765.95      (4.1%)    1.4% ( -10% -   15%) 0.513
                HighSloppyPhrase       26.10      (3.2%)       26.55      (2.8%)    1.7% (  -4% -    7%) 0.074
           BrowseMonthTaxoFacets       16.34      (4.1%)       16.62      (3.9%)    1.7% (  -6% -   10%) 0.175
                         MedTerm      977.69      (7.7%)     1002.63      (4.0%)    2.6% (  -8% -   15%) 0.191
                 MedSloppyPhrase      224.51      (7.6%)      230.55      (7.9%)    2.7% ( -11% -   19%) 0.271
            BrowseDateSSDVFacets        4.75     (22.8%)        5.13     (21.1%)    8.0% ( -29% -   67%) 0.249
                  AndMedNotMonth      873.50      (3.6%)      961.61      (4.4%)   10.1% (   2% -   18%) 0.000
               AndMedFilterMonth     2529.28      (4.2%)     2820.90      (6.4%)   11.5% (   0% -   23%) 0.000
              AndHighFilterMonth      477.77      (5.5%)      690.79      (7.9%)   44.6% (  29% -   61%) 0.000
                 AndHighNotMonth       73.70      (0.9%)      647.24     (32.8%)  778.2% ( 738% -  818%) 0.000

Result 2:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
            BrowseDateSSDVFacets        4.93     (20.2%)        4.53     (22.6%)   -8.1% ( -42% -   43%) 0.230
               HighTermTitleSort      160.08      (3.2%)      151.96      (2.8%)   -5.1% ( -10% -    0%) 0.000
                         Prefix3      832.94      (6.2%)      793.74      (5.7%)   -4.7% ( -15% -    7%) 0.012
         AndHighMedDayTaxoFacets       75.93      (2.7%)       72.41      (3.4%)   -4.6% ( -10% -    1%) 0.000
           HighTermDayOfYearSort      351.89      (7.7%)      337.84      (6.6%)   -4.0% ( -16% -   11%) 0.078
            HighTermTitleBDVSort       20.31      (3.3%)       19.52      (2.2%)   -3.9% (  -9% -    1%) 0.000
        AndHighHighDayTaxoFacets       26.47      (1.6%)       25.47      (3.3%)   -3.8% (  -8% -    1%) 0.000
               HighTermMonthSort     3233.06      (8.5%)     3134.43      (6.8%)   -3.1% ( -16% -   13%) 0.209
          OrHighMedDayTaxoFacets       14.30      (5.7%)       13.87      (5.6%)   -3.0% ( -13% -    8%) 0.097
            MedTermDayTaxoFacets       42.77      (2.0%)       41.58      (4.0%)   -2.8% (  -8% -    3%) 0.005
                      TermDTSort      199.07      (5.9%)      194.84      (4.0%)   -2.1% ( -11% -    8%) 0.183
                 LowSloppyPhrase       12.93      (5.2%)       12.68      (4.3%)   -1.9% ( -10% -    8%) 0.215
       BrowseDayOfYearSSDVFacets       14.26      (4.5%)       14.04      (6.5%)   -1.5% ( -11% -    9%) 0.390
             MedIntervalsOrdered       35.02     (11.7%)       34.51     (12.6%)   -1.4% ( -23% -   25%) 0.708
                        Wildcard      183.38      (4.0%)      180.80      (4.2%)   -1.4% (  -9% -    7%) 0.278
                    OrNotHighMed      480.40      (4.1%)      474.15      (3.4%)   -1.3% (  -8% -    6%) 0.275
             LowIntervalsOrdered       17.32     (11.9%)       17.10     (14.2%)   -1.3% ( -24% -   28%) 0.762
                      AndHighLow     1748.98      (6.0%)     1727.37      (7.3%)   -1.2% ( -13% -   12%) 0.558
                    OrNotHighLow     1197.14      (4.4%)     1183.17      (5.5%)   -1.2% ( -10% -    9%) 0.456
            HighIntervalsOrdered       10.67     (12.3%)       10.57     (13.0%)   -1.0% ( -23% -   27%) 0.800
           BrowseMonthSSDVFacets       20.29     (14.4%)       20.08     (16.5%)   -1.0% ( -27% -   34%) 0.839
                 MedSloppyPhrase       28.42      (3.7%)       28.18      (3.1%)   -0.8% (  -7% -    6%) 0.439
                HighSloppyPhrase       66.77      (4.8%)       66.26      (4.5%)   -0.8% (  -9% -    8%) 0.600
                      OrHighHigh       50.39      (3.7%)       50.01      (3.8%)   -0.8% (  -7% -    6%) 0.519
                         MedTerm      987.42      (3.3%)      983.16      (4.3%)   -0.4% (  -7% -    7%) 0.722
                    HighSpanNear       31.47      (1.9%)       31.34      (3.1%)   -0.4% (  -5% -    4%) 0.600
                         Respell      118.93      (3.3%)      118.52      (2.9%)   -0.3% (  -6% -    6%) 0.729
                          Fuzzy1      128.92      (4.7%)      128.77      (3.0%)   -0.1% (  -7% -    8%) 0.926
                       OrHighLow      574.08      (3.9%)      573.52      (4.2%)   -0.1% (  -7% -    8%) 0.939
                    OrHighNotLow      609.71      (4.0%)      609.36      (4.5%)   -0.1% (  -8% -    8%) 0.967
                     LowSpanNear      269.76      (2.8%)      269.99      (3.2%)    0.1% (  -5% -    6%) 0.931
                   OrNotHighHigh      418.19      (3.3%)      418.89      (2.9%)    0.2% (  -5% -    6%) 0.865
                     MedSpanNear       48.13      (2.1%)       48.22      (3.3%)    0.2% (  -5% -    5%) 0.817
            BrowseDateTaxoFacets       17.38      (3.1%)       17.43      (3.3%)    0.3% (  -5% -    6%) 0.756
       BrowseDayOfYearTaxoFacets       13.63      (3.7%)       13.68      (4.0%)    0.4% (  -7% -    8%) 0.765
                        HighTerm      593.45      (4.1%)      595.60      (5.0%)    0.4% (  -8% -    9%) 0.802
                       LowPhrase       70.31      (2.4%)       70.59      (2.4%)    0.4% (  -4% -    5%) 0.606
                          IntNRQ      148.09      (4.0%)      148.79      (4.5%)    0.5% (  -7% -    9%) 0.726
                          Fuzzy2      112.47      (4.5%)      113.20      (3.0%)    0.6% (  -6% -    8%) 0.591
                     AndHighHigh       95.26      (3.8%)       95.91      (2.5%)    0.7% (  -5% -    7%) 0.497
                       OrHighMed      219.71      (4.1%)      221.31      (3.3%)    0.7% (  -6% -    8%) 0.540
                      AndHighMed      269.52      (5.1%)      271.53      (3.6%)    0.7% (  -7% -    9%) 0.594
                        PKLookup      272.60      (4.2%)      274.73      (4.2%)    0.8% (  -7% -    9%) 0.556
                   OrHighNotHigh      685.86      (3.9%)      692.31      (4.2%)    0.9% (  -6% -    9%) 0.467
                       MedPhrase      464.54      (3.9%)      468.94      (3.8%)    0.9% (  -6% -    8%) 0.435
                    OrHighNotMed      610.92      (4.0%)      616.92      (4.6%)    1.0% (  -7% -    9%) 0.469
                      HighPhrase      278.19      (3.6%)      281.02      (3.2%)    1.0% (  -5% -    8%) 0.345
                         LowTerm     1134.43      (4.2%)     1146.81      (4.9%)    1.1% (  -7% -   10%) 0.448
           BrowseMonthTaxoFacets       16.52      (3.4%)       17.34     (37.3%)    5.0% ( -34% -   47%) 0.554
               AndMedFilterMonth     2365.12      (6.6%)     2583.10      (7.4%)    9.2% (  -4% -   24%) 0.000
                  AndMedNotMonth      786.75      (3.8%)     1041.01      (6.0%)   32.3% (  21% -   43%) 0.000
                 AndHighNotMonth      429.14      (3.2%)      629.74      (6.1%)   46.7% (  36% -   57%) 0.000
              AndHighFilterMonth      683.52      (3.7%)     1013.88      (6.5%)   48.3% (  36% -   60%) 0.000

Index without sorting
Result 1:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
               AndMedFilterMonth      650.40      (2.6%)      543.74      (2.5%)  -16.4% ( -20% -  -11%) 0.000
                         Prefix3      753.62      (3.9%)      705.17      (2.7%)   -6.4% ( -12% -    0%) 0.000
               HighTermTitleSort      233.31      (2.5%)      221.63      (2.4%)   -5.0% (  -9% -    0%) 0.000
            BrowseDateSSDVFacets        5.03     (22.3%)        4.78     (26.3%)   -4.8% ( -43% -   56%) 0.530
        AndHighHighDayTaxoFacets       38.08      (0.9%)       36.68      (1.5%)   -3.7% (  -5% -   -1%) 0.000
                      TermDTSort      227.78      (2.9%)      219.68      (3.2%)   -3.6% (  -9% -    2%) 0.000
           HighTermDayOfYearSort      517.02      (5.4%)      501.67      (4.7%)   -3.0% ( -12% -    7%) 0.064
            MedTermDayTaxoFacets      105.92      (2.6%)      102.95      (2.1%)   -2.8% (  -7% -    1%) 0.000
            HighTermTitleBDVSort       33.21      (2.4%)       32.37      (1.8%)   -2.5% (  -6% -    1%) 0.000
         AndHighMedDayTaxoFacets      196.09      (1.9%)      191.19      (2.1%)   -2.5% (  -6% -    1%) 0.000
              AndHighFilterMonth      454.63      (3.5%)      443.42      (4.2%)   -2.5% (  -9% -    5%) 0.046
                        Wildcard      376.65      (3.6%)      367.46      (2.8%)   -2.4% (  -8% -    4%) 0.016
                    OrNotHighMed      457.26      (3.6%)      448.29      (2.8%)   -2.0% (  -8% -    4%) 0.054
          OrHighMedDayTaxoFacets       21.73      (3.7%)       21.35      (3.3%)   -1.8% (  -8% -    5%) 0.113
                    OrNotHighLow     1906.16      (4.0%)     1878.09      (4.8%)   -1.5% (  -9% -    7%) 0.294
                      AndHighMed      335.83      (4.2%)      331.26      (4.6%)   -1.4% (  -9% -    7%) 0.330
                       LowPhrase      434.55      (2.5%)      429.58      (3.9%)   -1.1% (  -7% -    5%) 0.273
           BrowseMonthTaxoFacets       34.67     (31.2%)       34.29     (30.9%)   -1.1% ( -48% -   88%) 0.910
             LowIntervalsOrdered       35.05     (13.0%)       34.75     (11.9%)   -0.9% ( -22% -   27%) 0.826
                    HighSpanNear       15.36      (2.6%)       15.23      (2.5%)   -0.8% (  -5% -    4%) 0.308
             MedIntervalsOrdered       57.80     (10.9%)       57.41     (11.1%)   -0.7% ( -20% -   23%) 0.847
                       OrHighLow      399.47      (5.1%)      396.98      (4.0%)   -0.6% (  -9% -    8%) 0.668
                        HighTerm      792.75      (6.0%)      787.98      (4.4%)   -0.6% ( -10% -   10%) 0.719
                   OrHighNotHigh      441.76      (4.5%)      439.34      (3.2%)   -0.5% (  -7% -    7%) 0.658
                    OrHighNotLow      640.95      (5.2%)      637.60      (3.0%)   -0.5% (  -8% -    8%) 0.699
                      AndHighLow     1592.37      (3.1%)     1584.17      (4.6%)   -0.5% (  -7% -    7%) 0.678
                     LowSpanNear       94.76      (1.9%)       94.28      (2.0%)   -0.5% (  -4% -    3%) 0.407
               HighTermMonthSort     3744.06      (6.0%)     3726.43      (7.5%)   -0.5% ( -13% -   13%) 0.827
                         MedTerm      965.45      (5.0%)      961.47      (4.4%)   -0.4% (  -9% -    9%) 0.782
                     MedSpanNear       87.43      (1.5%)       87.16      (1.2%)   -0.3% (  -2% -    2%) 0.463
                      OrHighHigh       35.11      (4.5%)       35.01      (3.5%)   -0.3% (  -7% -    8%) 0.840
                     AndHighHigh       80.03      (3.7%)       79.84      (4.1%)   -0.2% (  -7% -    7%) 0.851
                   OrNotHighHigh      480.48      (3.5%)      479.47      (2.9%)   -0.2% (  -6% -    6%) 0.838
                          Fuzzy1      132.31      (2.4%)      132.20      (2.9%)   -0.1% (  -5% -    5%) 0.928
                  AndMedNotMonth      940.89      (5.5%)      940.75      (3.0%)   -0.0% (  -8% -    9%) 0.992
                      HighPhrase       73.90      (2.0%)       73.90      (1.9%)    0.0% (  -3% -    3%) 0.997
                         LowTerm     1343.57      (3.4%)     1345.22      (2.7%)    0.1% (  -5% -    6%) 0.899
                 AndHighNotMonth      576.74      (5.7%)      578.45      (4.0%)    0.3% (  -8% -   10%) 0.848
                    OrHighNotMed      477.59      (4.9%)      479.23      (2.9%)    0.3% (  -7% -    8%) 0.789
                          Fuzzy2       87.74      (2.2%)       88.12      (3.0%)    0.4% (  -4% -    5%) 0.606
                       MedPhrase      167.17      (3.7%)      168.15      (4.6%)    0.6% (  -7% -    9%) 0.658
                        PKLookup      291.04      (3.5%)      292.81      (2.8%)    0.6% (  -5% -    7%) 0.544
                HighSloppyPhrase       13.38      (3.0%)       13.47      (3.3%)    0.7% (  -5% -    7%) 0.513
                         Respell       92.43      (2.7%)       93.10      (2.4%)    0.7% (  -4% -    5%) 0.375
                 LowSloppyPhrase       51.85      (1.7%)       52.25      (3.1%)    0.8% (  -3% -    5%) 0.320
                       OrHighMed      166.63      (5.3%)      167.95      (3.4%)    0.8% (  -7% -    9%) 0.570
                 MedSloppyPhrase       91.32      (2.0%)       92.72      (4.4%)    1.5% (  -4% -    8%) 0.153
            HighIntervalsOrdered       16.07     (19.5%)       16.35     (21.2%)    1.7% ( -32% -   52%) 0.791
                          IntNRQ      124.65      (8.9%)      127.31      (4.4%)    2.1% ( -10% -   16%) 0.334
           BrowseMonthSSDVFacets       27.30     (24.7%)       27.93     (28.8%)    2.3% ( -41% -   74%) 0.787
       BrowseDayOfYearSSDVFacets       26.96     (25.1%)       27.66     (29.1%)    2.6% ( -41% -   75%) 0.764
       BrowseDayOfYearTaxoFacets       33.10     (31.9%)       38.26     (30.2%)   15.6% ( -35% -  114%) 0.113
            BrowseDateTaxoFacets       33.06     (31.9%)       38.26     (30.2%)   15.7% ( -35% -  114%) 0.110

Result 2:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      706.78      (2.6%)      650.89      (1.9%)   -7.9% ( -12% -   -3%) 0.000
               AndMedFilterMonth      365.32      (3.5%)      337.92      (3.1%)   -7.5% ( -13% -    0%) 0.000
       BrowseDayOfYearSSDVFacets       31.26     (30.8%)       29.25     (30.2%)   -6.4% ( -51% -   78%) 0.504
          OrHighMedDayTaxoFacets       12.28      (3.8%)       11.59      (4.5%)   -5.6% ( -13% -    2%) 0.000
        AndHighHighDayTaxoFacets       23.31      (2.5%)       22.03      (2.4%)   -5.5% ( -10% -    0%) 0.000
               HighTermTitleSort      232.54      (2.6%)      222.78      (2.9%)   -4.2% (  -9% -    1%) 0.000
            MedTermDayTaxoFacets       71.61      (2.4%)       68.71      (1.9%)   -4.0% (  -8% -    0%) 0.000
           HighTermDayOfYearSort      454.92      (3.4%)      437.24      (5.0%)   -3.9% ( -11% -    4%) 0.004
            HighTermTitleBDVSort       30.62      (4.3%)       29.47      (2.0%)   -3.8% (  -9% -    2%) 0.000
         AndHighMedDayTaxoFacets      149.73      (2.1%)      144.30      (2.5%)   -3.6% (  -8% -    0%) 0.000
           BrowseMonthSSDVFacets       30.98     (31.5%)       29.89     (30.1%)   -3.5% ( -49% -   84%) 0.719
                        Wildcard      309.24      (4.1%)      299.69      (3.7%)   -3.1% ( -10% -    4%) 0.011
                      TermDTSort      228.92      (4.0%)      222.90      (4.6%)   -2.6% ( -10% -    6%) 0.053
                    HighSpanNear       15.84      (1.7%)       15.54      (1.5%)   -1.9% (  -5% -    1%) 0.000
                     MedSpanNear      220.35      (1.8%)      216.48      (1.4%)   -1.8% (  -4% -    1%) 0.001
                    OrNotHighLow     1319.50      (3.0%)     1297.41      (4.4%)   -1.7% (  -8% -    5%) 0.160
                     LowSpanNear       25.57      (1.7%)       25.20      (1.5%)   -1.4% (  -4% -    1%) 0.004
              AndHighFilterMonth      300.43      (3.6%)      296.91      (4.1%)   -1.2% (  -8% -    6%) 0.334
             LowIntervalsOrdered       45.17      (6.1%)       44.87      (6.2%)   -0.7% ( -12% -   12%) 0.735
               HighTermMonthSort     3600.26      (4.8%)     3578.07      (5.4%)   -0.6% ( -10% -    9%) 0.701
                        PKLookup      295.58      (3.4%)      294.44      (2.8%)   -0.4% (  -6% -    6%) 0.694
             MedIntervalsOrdered       54.45      (7.3%)       54.35      (7.9%)   -0.2% ( -14% -   16%) 0.937
                       LowPhrase      111.07      (2.6%)      110.86      (2.2%)   -0.2% (  -4% -    4%) 0.803
                      HighPhrase      151.86      (1.7%)      151.59      (1.9%)   -0.2% (  -3% -    3%) 0.762
                      AndHighLow     1408.12      (2.9%)     1406.52      (3.8%)   -0.1% (  -6% -    6%) 0.915
                         Respell      123.73      (1.6%)      124.09      (1.5%)    0.3% (  -2% -    3%) 0.559
                          Fuzzy1      102.89      (1.9%)      103.29      (2.1%)    0.4% (  -3% -    4%) 0.537
            HighIntervalsOrdered       11.77      (9.0%)       11.82      (9.7%)    0.5% ( -16% -   21%) 0.868
                       MedPhrase      275.49      (2.7%)      276.87      (2.7%)    0.5% (  -4% -    5%) 0.551
                 MedSloppyPhrase       67.52      (2.8%)       67.88      (3.0%)    0.5% (  -5% -    6%) 0.558
                HighSloppyPhrase       49.88      (3.3%)       50.16      (2.7%)    0.6% (  -5% -    6%) 0.562
                          Fuzzy2      137.01      (2.1%)      137.83      (2.0%)    0.6% (  -3% -    4%) 0.354
                         LowTerm     1781.78      (2.3%)     1793.54      (3.1%)    0.7% (  -4% -    6%) 0.443
                 LowSloppyPhrase      208.88      (2.6%)      210.36      (1.7%)    0.7% (  -3% -    5%) 0.304
                          IntNRQ       73.24     (15.5%)       73.85     (11.4%)    0.8% ( -22% -   32%) 0.847
                      AndHighMed      228.03      (3.4%)      230.24      (4.5%)    1.0% (  -6% -    9%) 0.440
                      OrHighHigh       46.01      (3.6%)       46.56      (5.6%)    1.2% (  -7% -   10%) 0.423
                  AndMedNotMonth      840.87      (3.2%)      851.68      (3.6%)    1.3% (  -5% -    8%) 0.233
                    OrNotHighMed      495.20      (2.2%)      501.73      (3.2%)    1.3% (  -3% -    6%) 0.126
                   OrHighNotHigh      608.32      (2.6%)      616.71      (3.9%)    1.4% (  -4% -    8%) 0.184
                     AndHighHigh      104.73      (3.5%)      106.18      (4.4%)    1.4% (  -6% -    9%) 0.273
                       OrHighMed      142.04      (3.5%)      144.54      (4.0%)    1.8% (  -5% -    9%) 0.140
                    OrHighNotMed      606.98      (3.7%)      619.25      (4.2%)    2.0% (  -5% -   10%) 0.105
                   OrNotHighHigh      639.50      (2.7%)      652.79      (3.1%)    2.1% (  -3% -    8%) 0.022
                 AndHighNotMonth      582.41      (3.9%)      596.36      (3.8%)    2.4% (  -5% -   10%) 0.048
                    OrHighNotLow      635.27      (2.7%)      651.37      (4.9%)    2.5% (  -4% -   10%) 0.044
                         MedTerm     1357.80      (3.4%)     1393.89      (4.3%)    2.7% (  -4% -   10%) 0.030
                        HighTerm      538.12      (4.0%)      552.87      (5.9%)    2.7% (  -6% -   13%) 0.085
                       OrHighLow      399.22      (3.5%)      411.88      (4.4%)    3.2% (  -4% -   11%) 0.012
            BrowseDateTaxoFacets       27.83     (31.6%)       30.78     (37.6%)   10.6% ( -44% -  116%) 0.334
            BrowseDateSSDVFacets        5.06     (22.6%)        5.60     (20.2%)   10.7% ( -26% -   69%) 0.114
       BrowseDayOfYearTaxoFacets       27.81     (31.5%)       30.78     (37.9%)   10.7% ( -44% -  116%) 0.331
           BrowseMonthTaxoFacets       29.74     (35.5%)       33.31     (36.4%)   12.0% ( -44% -  130%) 0.290

Looks like the optimization does provide good speed up when the index is sorted, but may slow down for conjunction for unsorted index. However, I'm not totally sure about my implementation for conjunction, although it does pass all the test cases. Could you let me know if the new changes are aligned with what you are looking for?

Result 1 (one task has close to 800% improvement!):

Egads!  Why does Result 2 not also show a massive gain on AndHighNotMonth too?  Which wiki corpus are you running?  Are you running the full (default) 20 JVM iterations?

Thanks @mikemccand for the review! Yes I did run the full 20 iterations with enwiki-20130102-lines.txt corpus. I also tried to just run a single AndHighNotMonth task to find out which one was giving 800% improvement, but the highest improvement I saw was around 150% with this single task:
AndHighNotMonth: +its -monthPostings:apr #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup      182.12     (28.8%)       84.26      (8.4%)  -53.7% ( -70% -  -23%) 0.000
                 AndHighNotMonth       64.22      (8.4%)      160.51     (59.1%)  149.9% (  75% -  237%) 0.000

Not sure if that 800% comes from JVM's JIT compilation actually?
For the above task, being able to leverage skip-data helps a lot to skip much more than what a typical block of 128 docs would allow:
First doc in block: 0 | Last doc in block: 127 | Furthest skip entry doc: -1
First doc in block: 128 | Last doc in block: 255 | Furthest skip entry doc: 524287 | Number of continuous matching docs: 524032
First doc in block: 524288 | Last doc in block: 524415 | Furthest skip entry doc: 589823 | Number of continuous matching docs: 65408
First doc in block: 589824 | Last doc in block: 589951 | Furthest skip entry doc: 655359 | Number of continuous matching docs: 65408
First doc in block: 655360 | Last doc in block: 655487 | Furthest skip entry doc: 720895 | Number of continuous matching docs: 65408
First doc in block: 720896 | Last doc in block: 721023 | Furthest skip entry doc: 786431 | Number of continuous matching docs: 65408
First doc in block: 786432 | Last doc in block: 786559 | Furthest skip entry doc: 851967 | Number of continuous matching docs: 65408
First doc in block: 851968 | Last doc in block: 852095 | Furthest skip entry doc: 917503 | Number of continuous matching docs: 65408
First doc in block: 917504 | Last doc in block: 917631 | Furthest skip entry doc: 983039 | Number of continuous matching docs: 65408
First doc in block: 983040 | Last doc in block: 983167 | Furthest skip entry doc: 991231 | Number of continuous matching docs: 8064
First doc in block: 991232 | Last doc in block: 991359 | Furthest skip entry doc: 992255 | Number of continuous matching docs: 896
First doc in block: 992256 | Last doc in block: 992383 | Furthest skip entry doc: 993279 | Number of continuous matching docs: 896
First doc in block: 993280 | Last doc in block: 993407 | Furthest skip entry doc: 994303 | Number of continuous matching docs: 896
First doc in block: 994304 | Last doc in block: 994431 | Furthest skip entry doc: 995327 | Number of continuous matching docs: 896
First doc in block: 995328 | Last doc in block: 995455 | Furthest skip entry doc: 996351 | Number of continuous matching docs: 896
First doc in block: 996352 | Last doc in block: 996479 | Furthest skip entry doc: 997375 | Number of continuous matching docs: 896
First doc in block: 997376 | Last doc in block: 997503 | Furthest skip entry doc: 998399 | Number of continuous matching docs: 896
First doc in block: 998400 | Last doc in block: 998527 | Furthest skip entry doc: -1
First doc in block: 998528 | Last doc in block: 998655 | Furthest skip entry doc: -1
First doc in block: 998656 | Last doc in block: 998783 | Furthest skip entry doc: -1
First doc in block: 998784 | Last doc in block: 998911 | Furthest skip entry doc: -1
First doc in block: 998912 | Last doc in block: 999039 | Furthest skip entry doc: -1

Not sure if that 800% comes from JVM's JIT compilation actually?

Hmm, note that the actual QPS is varying quite a bit every time.  In your luceneutil run, are you fixing the random seed so the same queries are used every time?  It is odd that PKLookup performance drops too.

Hmm, note that the actual QPS is varying quite a bit every time. In your luceneutil run, are you fixing the random seed so the same queries are used every time?

Yeah indeed. I didn't fix the random seed during my luceneutil runs, and thus the results vary a lot as they may depend on the index and queries under test.

It is odd that PKLookup performance drops too.

I did a few more testings for this, and have some interesting findings:
No changes (comparing baseline with baseline) :
Task: AndHighNotMonth: +its -monthPostings:apr #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                 AndHighNotMonth       62.41      (9.4%)       62.45      (7.7%)    0.1% ( -15% -   18%) 0.979
                        PKLookup      176.62     (28.2%)      177.03     (33.2%)    0.2% ( -47% -   85%) 0.981

Task: AndHighNotMonth: +its -monthPostings:apr #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup      175.53     (25.3%)      166.38     (26.2%)   -5.2% ( -45% -   62%) 0.522
                 AndHighNotMonth       60.36     (17.1%)       62.29      (9.0%)    3.2% ( -19% -   35%) 0.459

PKLookup seems varies a lot as well when there are no changes.
With changes (comparing modified with baseline), and also modify task query:
Task: AndHighNotMonth: +its -monthPostings:apr #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup      182.12     (28.8%)       84.26      (8.4%)  -53.7% ( -70% -  -23%) 0.000
                 AndHighNotMonth       64.22      (8.4%)      160.51     (59.1%)  149.9% (  75% -  237%) 0.000

Task: AndHighNotMonth: +its -monthPostings:jan #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup       81.40     (17.4%)       91.44     (45.6%)   12.3% ( -43% -   91%) 0.258
                 AndHighNotMonth      116.74      (9.2%)      160.54     (45.8%)   37.5% ( -15% -  101%) 0.000

Task: AndHighNotMonth: +its -monthPostings:may #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup       80.18      (6.3%)       74.90      (9.4%)   -6.6% ( -20% -    9%) 0.009
                 AndHighNotMonth       92.19     (12.6%)      144.56     (23.6%)   56.8% (  18% -  106%) 0.000

No task, and only PKLookup is run

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup      128.55     (27.2%)      142.59     (36.9%)   10.9% ( -41% -  103%) 0.286

In addition, I noticed adding -Xbatch JVM argument will actually make the -50% slow down go away (and also boost PKLookup's QPS):
localconstants.py
if 'JAVA_EXE' not in globals():
    JAVA_EXE = 'java'
if 'JAVAC_EXE' not in globals():
    JAVAC_EXE = 'javac'
if 'JAVA_COMMAND' not in globals():
    JAVA_COMMAND = '%s -Xbatch' % JAVA_EXE

Task: AndHighNotMonth: +its -monthPostings:apr #  freq=1160703

                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        PKLookup      328.59     (10.2%)      347.16      (7.2%)    5.7% ( -10% -   25%) 0.043
                 AndHighNotMonth       60.21      (5.4%)      160.46     (41.8%)  166.5% ( 113% -  225%) 0.000

I suspect it's indeed JVM compilation that's causing the difference? Below is the full jvm command line from modified localconstants above and printed out by benchmark in case it will be useful:
java -Xbatch -XX:StartFlightRecording=dumponexit=true,maxsize=250M,settings=/Users/xichen/IdeaProjects/benchmarks/util/src/python/profiling.jfc,filename=/Users/xichen/IdeaProjects/benchmarks/logs/bench-search-baseline_vs_patch-my_modified_version-19.jfr -XX:+UnlockDiagnosticVMOptions -XX:+DebugNonSafepoints -classpath /Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/core/build/libs/lucene-core-10.0.0-SNAPSHOT.jar:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/sandbox/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/misc/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/facet/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/analysis/common/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/analysis/icu/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/queryparser/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/grouping/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/suggest/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/highlighter/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/codecs/build/classes/java/main:/Users/xichen/IdeaProjects/benchmarks/lucene_candidate/lucene/queries/build/classes/java/main:/Users/xichen/.gradle/caches/modules-2/files-2.1/com.carrotsearch/hppc/0.9.1/4bf4c51e06aec600894d841c4c004566b20dd357/hppc-0.9.1.jar:/Users/xichen/IdeaProjects/benchmarks/util/lib/HdrHistogram.jar:/Users/xichen/IdeaProjects/benchmarks/util/build perf.SearchPerfTest -dirImpl MMapDirectory -indexPath /Users/xichen/IdeaProjects/benchmarks/indices/wikimedium10m.lucene_baseline.facets.taxonomy:Date.taxonomy:Month.taxonomy:DayOfYear.sortedset:Date.sortedset:Month.sortedset:DayOfYear.Lucene90.Lucene90.dvfields.sort=month:custom.nd10M -facets taxonomy:Date;Date -facets taxonomy:Month;Month -facets taxonomy:DayOfYear;DayOfYear -facets sortedset:Date;Date -facets sortedset:Month;Month -facets sortedset:DayOfYear;DayOfYear -analyzer StandardAnalyzer -taskSource /Users/xichen/IdeaProjects/benchmarks/util/tasks/wikimedium.10M.nostopwords.tasks -searchThreadCount 2 -taskRepeatCount 20 -field body -tasksPerCat 1 -staticSeed -2249101 -seed -4093553 -similarity BM25Similarity -commit multi -hiliteImpl FastVectorHighlighter -log /Users/xichen/IdeaProjects/benchmarks/logs/baseline_vs_patch.my_modified_version.19 -topN 100 -pk

In terms of code, PKLookup will execute this section of modified code when its doing doc enumeration, but reverting changes there didn't solve the issue.

PKLookup seems varies a lot as well when there are no changes.

I wonder if luceneutil maybe has a bug where PKLookup task is not using the specified random seed to derive which IDs it looks up?  Indeed I have seen it be noisy in the past (not just for you)...

In addition, I noticed adding -Xbatch JVM argument will actually make the -50% slow down go away (and also boost PKLookup's QPS):

Thanks for testing this.  We've debated the merits of disabling background compilation (-Xbatch) in the past, but decided it's too risky since nobody actually runs this way in production so the results would not necessarily reflect production impact.  It is indeed an interesting data point and does seem to point to "hotspot compilation noise" as the source of the wide differences.
Though, I would also expect that as you vary the particular query (apr, jan, may on the negated clause) that the gains should be quite different?  It depends heavily on how the postings fall into long runs or not in the index?  Though, the line file docs for luceneutil are randomly sorted, so there should not be a correlation by time with Lucene's docid.

In terms of code, PKLookup will execute this section of modified code when its doing doc enumeration, but reverting changes there didn't solve the issue.

OK thanks for testing.
I think net/net we can conclude that this is all noise and should not block this great change!  The speedups for some cases are astounding!

Thanks @mikemccand for the additional context!

Thanks for testing this. We've debated the merits of disabling background compilation (-Xbatch) in the past, but decided it's too risky since nobody actually runs this way in production so the results would not necessarily reflect production impact.

+1

Though, I would also expect that as you vary the particular query (apr, jan, may on the negated clause) that the gains should be quite different? It depends heavily on how the postings fall into long runs or not in the index? Though, the line file docs for luceneutil are randomly sorted, so there should not be a correlation by time with Lucene's docid.

The benchmark was run with index sorted by month and the performances gain do vary based on queries (149.9% for apr, 56.8% for may and 37.5% for jan), albeit with different degrees.

Hi @jpountz @mikemccand @rmuir @uschindler @gsmiller , I have added some tests in the last few days and believed this PR is ready for review now, could you please take a look and let me know if you have any suggestion? I'm not particularly sure about my approach for conjunction and leveraging skip data by the way, and am open to alternatives!

The logic looks pretty good to me overall. I like that we're seeing good speedups when using FILTER/MUST_NOT clauses on postings that have long runs!
It'd be good to understand if we can reduce the overhead for the case when the optimization doesn't kick in, as I'd expect this case to remain the most common one.
I'm also curious to get other people's take on whether the additional API is worth the performance benefits. I personally like it because it allows having first-class filters (filters on fields that are part of the index sort) that perform much more efficiently than regular filters. This can be especially useful when managing multiple tenants within the same index, e.g. multiple categories of an e-commerce catalog.

I'd rather like to avoid introducing a flag, but your second idea sounds interesting. Maybe one way to implement it would be to introduce a bulk scorer for conjunctions, and split the doc ID space into something like 128 equal windows, and only checking for peexNextNonMatchingDocID when moving to a new window. This would only ignore queries whose runs of matches are less than 1% of the total segment size, which wouldn't be very useful to speed things up anyway?

Thanks @jpountz for the feedback! On the second approach, I was actually thinking something simpler, such as this https://github.com/apache/lucene/pull/12194/commits/219beab1b1baea4950a3e47bc9bd46df32fef055. I ran the benchmark tests after the change, and got the following results:
Index with sorting
Result 1:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
               AndMedFilterMonth     2142.90      (7.1%)     1996.67      (5.0%)   -6.8% ( -17% -    5%) 0.000
        AndHighHighDayTaxoFacets       13.99      (2.3%)       13.08      (2.3%)   -6.5% ( -10% -   -1%) 0.000
               HighTermTitleSort      131.92      (2.5%)      124.03      (2.8%)   -6.0% ( -10% -    0%) 0.000
         AndHighMedDayTaxoFacets       91.57      (2.0%)       86.87      (3.2%)   -5.1% ( -10% -    0%) 0.000
           HighTermDayOfYearSort      235.50      (4.8%)      227.18      (4.1%)   -3.5% ( -11% -    5%) 0.012
            MedTermDayTaxoFacets       72.51      (2.3%)       70.17      (2.5%)   -3.2% (  -7% -    1%) 0.000
               HighTermMonthSort     3126.27      (3.2%)     3032.93      (3.8%)   -3.0% (  -9% -    4%) 0.007
                        Wildcard      280.45      (5.7%)      272.30      (5.7%)   -2.9% ( -13% -    8%) 0.107
          OrHighMedDayTaxoFacets       22.17      (2.5%)       21.55      (2.4%)   -2.8% (  -7% -    2%) 0.000
            HighTermTitleBDVSort       23.23      (2.9%)       22.59      (2.9%)   -2.7% (  -8% -    3%) 0.003
                      TermDTSort      198.40      (9.4%)      194.24      (9.1%)   -2.1% ( -18% -   18%) 0.474
             MedIntervalsOrdered       53.97     (13.6%)       52.88     (12.8%)   -2.0% ( -24% -   28%) 0.629
                     MedSpanNear      172.23      (2.7%)      168.92      (2.4%)   -1.9% (  -6% -    3%) 0.018
           BrowseMonthSSDVFacets       20.44      (5.9%)       20.09      (6.0%)   -1.7% ( -12% -   10%) 0.360
                         Prefix3      879.87      (4.4%)      866.61      (4.5%)   -1.5% (  -9% -    7%) 0.284
                    HighSpanNear       50.36      (2.3%)       49.60      (1.9%)   -1.5% (  -5% -    2%) 0.022
                     LowSpanNear      372.08      (2.3%)      366.84      (1.7%)   -1.4% (  -5% -    2%) 0.030
                      AndHighLow     1852.63      (3.8%)     1829.62      (4.0%)   -1.2% (  -8% -    6%) 0.318
             LowIntervalsOrdered        9.32     (15.4%)        9.21     (15.4%)   -1.2% ( -27% -   35%) 0.811
            HighIntervalsOrdered        1.55     (20.5%)        1.53     (20.6%)   -1.1% ( -35% -   50%) 0.872
       BrowseDayOfYearSSDVFacets       14.47      (4.8%)       14.33      (5.4%)   -1.0% ( -10% -    9%) 0.524
                    OrNotHighLow     1128.41      (4.1%)     1117.38      (3.9%)   -1.0% (  -8% -    7%) 0.438
                   OrHighNotHigh      492.96      (3.9%)      488.47      (4.3%)   -0.9% (  -8% -    7%) 0.486
                       MedPhrase      372.00      (2.7%)      368.75      (3.0%)   -0.9% (  -6% -    4%) 0.325
                    OrNotHighMed      628.90      (2.8%)      623.55      (2.5%)   -0.9% (  -5% -    4%) 0.310
                    OrHighNotLow      791.85      (3.8%)      785.12      (4.5%)   -0.9% (  -8% -    7%) 0.520
                   OrNotHighHigh      447.73      (2.9%)      444.15      (3.1%)   -0.8% (  -6% -    5%) 0.399
                      OrHighHigh       45.13      (4.0%)       44.78      (4.5%)   -0.8% (  -8% -    8%) 0.575
                    OrHighNotMed      543.72      (3.6%)      539.69      (4.2%)   -0.7% (  -8% -    7%) 0.545
                        HighTerm      946.86      (4.2%)      942.67      (3.8%)   -0.4% (  -8% -    7%) 0.727
                         LowTerm     1446.44      (5.6%)     1442.00      (5.9%)   -0.3% ( -11% -   11%) 0.866
                         MedTerm     1064.71      (3.8%)     1061.77      (3.7%)   -0.3% (  -7% -    7%) 0.815
                          Fuzzy1       78.98      (6.5%)       78.77      (6.2%)   -0.3% ( -12% -   13%) 0.896
       BrowseDayOfYearTaxoFacets       14.60      (3.5%)       14.56      (3.0%)   -0.2% (  -6% -    6%) 0.808
                       OrHighLow      383.35      (3.5%)      382.47      (4.1%)   -0.2% (  -7% -    7%) 0.848
                      AndHighMed      419.38      (3.9%)      418.65      (3.4%)   -0.2% (  -7% -    7%) 0.879
                 LowSloppyPhrase       45.89      (1.9%)       45.85      (1.8%)   -0.1% (  -3% -    3%) 0.895
            BrowseDateTaxoFacets       19.56      (2.2%)       19.55      (2.0%)   -0.1% (  -4% -    4%) 0.925
                       OrHighMed       53.51      (4.0%)       53.49      (3.8%)   -0.1% (  -7% -    8%) 0.965
                 MedSloppyPhrase       77.05      (1.8%)       77.03      (2.0%)   -0.0% (  -3% -    3%) 0.962
                     AndHighHigh      119.95      (3.4%)      119.92      (3.2%)   -0.0% (  -6% -    6%) 0.982
           BrowseMonthTaxoFacets       18.33      (2.3%)       18.35      (2.3%)    0.1% (  -4% -    4%) 0.911
                          IntNRQ      119.39     (22.2%)      119.66     (22.4%)    0.2% ( -36% -   57%) 0.974
                       LowPhrase      105.06      (3.4%)      105.34      (4.0%)    0.3% (  -6% -    7%) 0.824
                        PKLookup      282.66      (3.6%)      283.54      (3.4%)    0.3% (  -6% -    7%) 0.782
            BrowseDateSSDVFacets        5.42      (7.9%)        5.45      (7.3%)    0.5% ( -13% -   16%) 0.839
                      HighPhrase       72.39      (2.6%)       72.78      (2.6%)    0.5% (  -4% -    5%) 0.515
                HighSloppyPhrase        1.41      (5.7%)        1.42      (3.5%)    0.9% (  -7% -   10%) 0.567
                         Respell       95.35      (5.5%)       96.22      (5.3%)    0.9% (  -9% -   12%) 0.593
                          Fuzzy2      102.31      (9.0%)      103.34      (9.6%)    1.0% ( -16% -   21%) 0.731
                  AndMedNotMonth      873.00      (3.1%)      984.05      (3.3%)   12.7% (   6% -   19%) 0.000
              AndHighFilterMonth      362.01      (2.8%)      484.47      (6.0%)   33.8% (  24% -   43%) 0.000
                 AndHighNotMonth      253.17      (1.8%)      596.55     (10.5%)  135.6% ( 121% -  150%) 0.000

Result 2:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
         AndHighMedDayTaxoFacets       66.69      (1.9%)       60.98      (4.1%)   -8.6% ( -14% -   -2%) 0.000
                         Prefix3      419.25      (4.7%)      387.06      (4.0%)   -7.7% ( -15% -    1%) 0.000
        AndHighHighDayTaxoFacets       38.85      (1.6%)       36.34      (3.7%)   -6.5% ( -11% -   -1%) 0.000
                    OrNotHighMed      418.16      (2.1%)      395.85      (3.8%)   -5.3% ( -11% -    0%) 0.000
                      TermDTSort      151.83      (3.8%)      143.84      (3.5%)   -5.3% ( -12% -    2%) 0.000
               AndMedFilterMonth     1849.70      (4.7%)     1753.86      (5.3%)   -5.2% ( -14% -    5%) 0.001
               HighTermMonthSort     3079.34      (3.5%)     2932.00      (4.4%)   -4.8% ( -12% -    3%) 0.000
               HighTermTitleSort      161.65     (10.3%)      154.99      (7.7%)   -4.1% ( -20% -   15%) 0.153
          OrHighMedDayTaxoFacets        3.72      (3.8%)        3.59      (2.9%)   -3.5% (  -9% -    3%) 0.001
           HighTermDayOfYearSort      407.83      (3.0%)      394.86      (4.0%)   -3.2% (  -9% -    3%) 0.005
            MedTermDayTaxoFacets       69.43      (2.4%)       67.48      (2.0%)   -2.8% (  -7% -    1%) 0.000
                    OrNotHighLow     1816.25      (3.9%)     1769.50      (3.9%)   -2.6% (  -9% -    5%) 0.037
            HighTermTitleBDVSort       36.84      (2.1%)       36.03      (1.0%)   -2.2% (  -5% -    0%) 0.000
                        Wildcard      162.28      (6.6%)      158.82      (6.4%)   -2.1% ( -14% -   11%) 0.297
                         LowTerm     1036.19      (5.4%)     1019.64      (5.9%)   -1.6% ( -12% -   10%) 0.373
                    HighSpanNear       36.59      (5.4%)       36.09      (5.5%)   -1.4% ( -11% -   10%) 0.428
                     LowSpanNear      103.37      (1.7%)      102.13      (1.9%)   -1.2% (  -4% -    2%) 0.035
                     MedSpanNear       51.35      (1.6%)       50.86      (1.8%)   -0.9% (  -4% -    2%) 0.083
                       OrHighLow      660.72      (3.4%)      656.05      (3.2%)   -0.7% (  -7% -    6%) 0.494
             MedIntervalsOrdered       21.71      (7.6%)       21.57      (7.6%)   -0.6% ( -14% -   15%) 0.794
            HighIntervalsOrdered       12.02      (9.4%)       11.96      (9.2%)   -0.5% ( -17% -   19%) 0.854
             LowIntervalsOrdered       55.04      (7.4%)       54.74      (7.4%)   -0.5% ( -14% -   15%) 0.819
                   OrNotHighHigh      571.44      (2.6%)      568.54      (3.2%)   -0.5% (  -6% -    5%) 0.581
                         MedTerm     1102.15      (4.2%)     1097.46      (4.4%)   -0.4% (  -8% -    8%) 0.755
                      HighPhrase      108.28      (3.3%)      107.92      (2.9%)   -0.3% (  -6% -    6%) 0.736
                          IntNRQ       81.85      (9.6%)       81.66      (9.6%)   -0.2% ( -17% -   21%) 0.941
                   OrHighNotHigh      401.85      (3.9%)      401.24      (4.3%)   -0.2% (  -8% -    8%) 0.907
                HighSloppyPhrase       26.71      (4.1%)       26.67      (3.8%)   -0.1% (  -7% -    8%) 0.908
                         Respell      110.22      (5.5%)      110.08      (5.1%)   -0.1% ( -10% -   11%) 0.939
                    OrHighNotMed      635.92      (3.7%)      635.34      (4.1%)   -0.1% (  -7% -    8%) 0.942
                 LowSloppyPhrase       11.69      (4.1%)       11.68      (3.9%)   -0.1% (  -7% -    8%) 0.951
                          Fuzzy2       35.65      (7.7%)       35.65      (7.3%)   -0.0% ( -13% -   16%) 0.995
                       OrHighMed      225.90      (2.9%)      225.90      (3.1%)    0.0% (  -5% -    6%) 0.998
                        PKLookup      282.08      (3.1%)      282.19      (3.6%)    0.0% (  -6% -    6%) 0.969
            BrowseDateSSDVFacets        5.43      (9.8%)        5.44      (9.7%)    0.1% ( -17% -   21%) 0.981
                      AndHighMed      139.86      (2.5%)      139.97      (2.9%)    0.1% (  -5% -    5%) 0.929
                      OrHighHigh       42.67      (2.4%)       42.71      (2.7%)    0.1% (  -4% -    5%) 0.923
                        HighTerm     1193.77      (4.6%)     1194.76      (4.8%)    0.1% (  -8% -   10%) 0.956
                     AndHighHigh       72.75      (2.0%)       72.84      (3.0%)    0.1% (  -4% -    5%) 0.876
                       MedPhrase       17.85      (2.8%)       17.88      (2.5%)    0.2% (  -5% -    5%) 0.833
            BrowseDateTaxoFacets       19.36      (2.5%)       19.40      (2.2%)    0.2% (  -4% -    5%) 0.794
                      AndHighLow     1612.73      (3.5%)     1616.44      (3.2%)    0.2% (  -6% -    7%) 0.826
                 MedSloppyPhrase       73.06      (2.5%)       73.26      (2.5%)    0.3% (  -4% -    5%) 0.740
       BrowseDayOfYearTaxoFacets       14.68      (4.7%)       14.72      (4.3%)    0.3% (  -8% -    9%) 0.833
       BrowseDayOfYearSSDVFacets       14.23      (7.7%)       14.27      (8.0%)    0.3% ( -14% -   17%) 0.900
           BrowseMonthTaxoFacets       18.14      (2.6%)       18.20      (2.5%)    0.3% (  -4% -    5%) 0.695
                    OrHighNotLow      532.83      (4.4%)      535.13      (5.2%)    0.4% (  -8% -   10%) 0.778
                       LowPhrase       79.15      (2.1%)       79.50      (2.3%)    0.4% (  -3% -    4%) 0.528
                          Fuzzy1      103.09      (7.8%)      104.65      (7.6%)    1.5% ( -12% -   18%) 0.536
           BrowseMonthSSDVFacets       19.62      (7.3%)       19.94     (12.2%)    1.6% ( -16% -   22%) 0.607
                  AndMedNotMonth      891.86      (2.8%)     1048.85      (5.4%)   17.6% (   9% -   26%) 0.000
              AndHighFilterMonth      685.23      (2.7%)      835.74      (6.1%)   22.0% (  12% -   31%) 0.000
                 AndHighNotMonth       76.06      (0.9%)      657.26     (50.3%)  764.1% ( 706% -  822%) 0.000

Index without sorting
Result 1:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      620.25      (3.8%)      572.56      (3.2%)   -7.7% ( -14% -    0%) 0.000
                        Wildcard       94.62      (6.0%)       87.96      (5.2%)   -7.0% ( -17% -    4%) 0.000
               HighTermTitleSort      185.23     (15.8%)      172.39     (15.9%)   -6.9% ( -33% -   29%) 0.167
        AndHighHighDayTaxoFacets       13.33      (3.2%)       12.53      (3.2%)   -6.0% ( -11% -    0%) 0.000
               AndMedFilterMonth      780.10      (3.2%)      750.30      (3.5%)   -3.8% ( -10% -    2%) 0.000
         AndHighMedDayTaxoFacets       78.48      (1.9%)       75.69      (2.5%)   -3.6% (  -7% -    0%) 0.000
          OrHighMedDayTaxoFacets        9.81      (6.9%)        9.48      (4.9%)   -3.4% ( -14% -    9%) 0.077
            MedTermDayTaxoFacets       91.99      (2.5%)       89.02      (2.2%)   -3.2% (  -7% -    1%) 0.000
              AndHighFilterMonth      458.58      (4.4%)      444.81      (4.4%)   -3.0% ( -11% -    6%) 0.032
            HighTermTitleBDVSort       28.60      (2.0%)       27.83      (1.3%)   -2.7% (  -5% -    0%) 0.000
                          IntNRQ       84.30      (9.3%)       82.10     (11.6%)   -2.6% ( -21% -   20%) 0.430
               HighTermMonthSort     2392.61      (7.2%)     2330.41      (5.4%)   -2.6% ( -14% -   10%) 0.198
                    OrNotHighLow     1069.43      (3.6%)     1042.84      (4.4%)   -2.5% ( -10% -    5%) 0.050
             LowIntervalsOrdered      227.98      (2.7%)      222.64      (4.2%)   -2.3% (  -8% -    4%) 0.035
                      TermDTSort      212.12      (3.3%)      207.21      (3.9%)   -2.3% (  -9% -    5%) 0.044
            HighIntervalsOrdered       38.94      (1.8%)       38.11      (3.3%)   -2.1% (  -7% -    3%) 0.011
                    OrNotHighMed      593.33      (3.4%)      581.36      (3.7%)   -2.0% (  -8% -    5%) 0.074
             MedIntervalsOrdered       21.30      (1.3%)       20.88      (2.9%)   -2.0% (  -6% -    2%) 0.005
                     MedSpanNear       25.77      (2.5%)       25.41      (2.4%)   -1.4% (  -6% -    3%) 0.062
                    HighSpanNear       17.69      (2.7%)       17.45      (2.7%)   -1.4% (  -6% -    4%) 0.107
                     LowSpanNear      128.36      (1.4%)      126.90      (1.3%)   -1.1% (  -3% -    1%) 0.008
                   OrNotHighHigh      548.99      (3.4%)      545.38      (2.9%)   -0.7% (  -6% -    5%) 0.508
           HighTermDayOfYearSort      424.25      (5.8%)      421.73      (3.8%)   -0.6% (  -9% -    9%) 0.703
                   OrHighNotHigh      465.31      (3.7%)      462.73      (4.0%)   -0.6% (  -7% -    7%) 0.648
                        PKLookup      292.46      (4.0%)      290.85      (3.8%)   -0.6% (  -7% -    7%) 0.652
                      HighPhrase      170.22      (3.6%)      169.76      (3.5%)   -0.3% (  -7% -    7%) 0.808
           BrowseMonthTaxoFacets       40.22     (23.2%)       40.14     (23.1%)   -0.2% ( -37% -   60%) 0.979
            BrowseDateTaxoFacets       45.02     (10.1%)       44.99     (10.0%)   -0.1% ( -18% -   22%) 0.982
       BrowseDayOfYearTaxoFacets       45.36      (7.5%)       45.33      (7.3%)   -0.1% ( -13% -   15%) 0.978
                 LowSloppyPhrase       17.25      (5.0%)       17.25      (4.9%)   -0.0% (  -9% -   10%) 0.999
                          Fuzzy1       83.95      (4.1%)       84.05      (4.2%)    0.1% (  -7% -    8%) 0.928
       BrowseDayOfYearSSDVFacets       26.61     (26.3%)       26.64     (26.3%)    0.1% ( -41% -   71%) 0.988
                       MedPhrase       47.60      (3.3%)       47.66      (3.3%)    0.1% (  -6% -    7%) 0.900
                 MedSloppyPhrase       25.42      (4.8%)       25.45      (4.8%)    0.1% (  -9% -   10%) 0.930
                    OrHighNotMed      533.40      (3.8%)      534.12      (3.9%)    0.1% (  -7% -    8%) 0.912
                       LowPhrase       72.95      (2.5%)       73.07      (2.5%)    0.2% (  -4% -    5%) 0.836
                      AndHighMed      331.56      (5.4%)      332.11      (5.5%)    0.2% ( -10% -   11%) 0.923
                         LowTerm     1279.72      (7.0%)     1282.14      (5.1%)    0.2% ( -11% -   13%) 0.922
                         Respell       94.36      (6.2%)       94.70      (5.9%)    0.4% ( -11% -   13%) 0.850
           BrowseMonthSSDVFacets       26.44     (25.9%)       26.53     (25.7%)    0.4% ( -40% -   70%) 0.964
                HighSloppyPhrase       38.93      (4.1%)       39.09      (4.0%)    0.4% (  -7% -    8%) 0.750
                  AndMedNotMonth      891.59      (3.9%)      895.75      (2.6%)    0.5% (  -5% -    7%) 0.657
                      AndHighLow     1747.72      (3.8%)     1756.48      (4.2%)    0.5% (  -7% -    8%) 0.693
                     AndHighHigh       77.63      (4.2%)       78.03      (4.1%)    0.5% (  -7% -    9%) 0.697
                    OrHighNotLow      646.76      (4.5%)      650.22      (4.7%)    0.5% (  -8% -   10%) 0.712
                          Fuzzy2       69.85      (7.1%)       70.28      (7.4%)    0.6% ( -12% -   16%) 0.789
                       OrHighMed      251.43      (4.0%)      252.98      (4.3%)    0.6% (  -7% -    9%) 0.637
            BrowseDateSSDVFacets        5.52      (2.8%)        5.56      (4.1%)    0.7% (  -6% -    7%) 0.534
                       OrHighLow      509.73      (5.2%)      516.04      (4.7%)    1.2% (  -8% -   11%) 0.432
                        HighTerm      716.67      (5.0%)      725.95      (4.2%)    1.3% (  -7% -   10%) 0.372
                         MedTerm     1009.75      (4.5%)     1023.79      (4.1%)    1.4% (  -6% -   10%) 0.306
                      OrHighHigh       40.11      (3.8%)       40.67      (3.4%)    1.4% (  -5% -    8%) 0.217
                 AndHighNotMonth      443.44      (4.1%)      467.71      (3.5%)    5.5% (  -2% -   13%) 0.000

Result 2:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      379.27      (4.2%)      350.63      (3.5%)   -7.6% ( -14% -    0%) 0.000
               HighTermMonthSort     2644.50     (10.0%)     2467.84      (7.9%)   -6.7% ( -22% -   12%) 0.020
                        Wildcard      111.47      (5.8%)      105.48      (5.2%)   -5.4% ( -15% -    6%) 0.002
               HighTermTitleSort      163.42      (8.4%)      155.35      (6.4%)   -4.9% ( -18% -   10%) 0.036
         AndHighMedDayTaxoFacets      106.98      (2.2%)      101.81      (3.1%)   -4.8% (  -9% -    0%) 0.000
                      TermDTSort      200.05      (4.0%)      192.23      (6.4%)   -3.9% ( -13% -    6%) 0.021
        AndHighHighDayTaxoFacets       39.09      (1.8%)       37.65      (1.5%)   -3.7% (  -6% -    0%) 0.000
              AndHighFilterMonth      205.53      (2.8%)      198.29      (3.4%)   -3.5% (  -9% -    2%) 0.000
            HighTermTitleBDVSort       10.04      (2.4%)        9.74      (2.1%)   -3.0% (  -7% -    1%) 0.000
            MedTermDayTaxoFacets       89.94      (2.0%)       87.38      (1.8%)   -2.8% (  -6% -    1%) 0.000
           HighTermDayOfYearSort      418.97      (6.0%)      408.95      (6.9%)   -2.4% ( -14% -   11%) 0.241
               AndMedFilterMonth      639.08      (2.2%)      624.53      (2.5%)   -2.3% (  -6% -    2%) 0.002
          OrHighMedDayTaxoFacets        7.17      (4.0%)        7.02      (4.4%)   -2.1% ( -10% -    6%) 0.112
                 AndHighNotMonth      606.76      (4.7%)      597.90      (4.7%)   -1.5% ( -10% -    8%) 0.328
                    OrNotHighMed      624.52      (2.5%)      616.48      (3.1%)   -1.3% (  -6% -    4%) 0.149
                         MedTerm      883.90      (5.7%)      872.74      (4.5%)   -1.3% ( -10% -    9%) 0.436
                  AndMedNotMonth     1015.43      (3.5%)     1003.04      (2.7%)   -1.2% (  -7% -    5%) 0.216
                     MedSpanNear       11.88      (0.9%)       11.75      (0.8%)   -1.1% (  -2% -    0%) 0.000
                      OrHighHigh       42.30      (4.6%)       41.85      (3.4%)   -1.1% (  -8% -    7%) 0.406
                    OrHighNotMed      573.99      (4.2%)      568.16      (4.5%)   -1.0% (  -9% -    8%) 0.463
             MedIntervalsOrdered       38.88      (6.8%)       38.50      (6.9%)   -1.0% ( -13% -   13%) 0.656
                        HighTerm     1015.56      (5.6%)     1005.98      (4.9%)   -0.9% ( -10% -   10%) 0.571
             LowIntervalsOrdered      154.19      (8.0%)      152.80      (8.2%)   -0.9% ( -15% -   16%) 0.724
                    OrHighNotLow      844.90      (4.9%)      837.29      (4.9%)   -0.9% ( -10% -    9%) 0.561
                     LowSpanNear       78.74      (4.1%)       78.11      (4.1%)   -0.8% (  -8% -    7%) 0.541
                       OrHighMed      153.42      (4.0%)      152.21      (3.4%)   -0.8% (  -7% -    6%) 0.504
                    HighSpanNear        2.96      (0.7%)        2.94      (0.7%)   -0.8% (  -2% -    0%) 0.001
                       MedPhrase      376.73      (2.0%)      374.16      (1.9%)   -0.7% (  -4% -    3%) 0.272
            HighIntervalsOrdered       29.22      (7.3%)       29.03      (7.4%)   -0.7% ( -14% -   15%) 0.769
                   OrHighNotHigh      498.90      (4.1%)      496.29      (4.3%)   -0.5% (  -8% -    8%) 0.695
                 LowSloppyPhrase      132.03      (3.4%)      131.46      (3.1%)   -0.4% (  -6% -    6%) 0.674
                        PKLookup      293.57      (3.3%)      292.52      (3.3%)   -0.4% (  -6% -    6%) 0.735
                         LowTerm     1274.81      (7.5%)     1270.44      (6.3%)   -0.3% ( -13% -   14%) 0.876
       BrowseDayOfYearSSDVFacets       25.40     (20.8%)       25.33     (20.8%)   -0.3% ( -34% -   52%) 0.968
                      AndHighMed      185.94      (4.1%)      185.51      (4.1%)   -0.2% (  -8% -    8%) 0.859
                      AndHighLow     1532.23      (4.7%)     1529.57      (4.7%)   -0.2% (  -9% -    9%) 0.908
                   OrNotHighHigh      433.52      (3.2%)      433.05      (3.2%)   -0.1% (  -6% -    6%) 0.914
                    OrNotHighLow     2173.75      (2.4%)     2171.48      (4.1%)   -0.1% (  -6% -    6%) 0.922
                HighSloppyPhrase       60.06      (4.6%)       60.02      (4.1%)   -0.1% (  -8% -    8%) 0.966
                          IntNRQ       96.82      (0.8%)       96.78      (0.8%)   -0.0% (  -1% -    1%) 0.867
            BrowseDateTaxoFacets       43.83     (12.3%)       43.82     (12.3%)   -0.0% ( -21% -   27%) 0.992
           BrowseMonthSSDVFacets       25.69     (20.6%)       25.69     (20.6%)   -0.0% ( -34% -   51%) 0.998
                 MedSloppyPhrase      160.44      (3.8%)      160.44      (3.6%)   -0.0% (  -7% -    7%) 0.998
           BrowseMonthTaxoFacets       35.59     (27.4%)       35.60     (27.3%)    0.0% ( -42% -   75%) 0.996
                          Fuzzy1       86.58      (7.6%)       86.62      (6.8%)    0.1% ( -13% -   15%) 0.981
                       OrHighLow     1145.19      (3.4%)     1146.01      (3.5%)    0.1% (  -6% -    7%) 0.948
            BrowseDateSSDVFacets        5.47      (2.3%)        5.48      (2.3%)    0.1% (  -4% -    4%) 0.917
       BrowseDayOfYearTaxoFacets       44.34     (11.1%)       44.38     (11.3%)    0.1% ( -20% -   25%) 0.976
                         Respell       90.09      (4.5%)       90.25      (4.4%)    0.2% (  -8% -    9%) 0.899
                     AndHighHigh      113.61      (3.3%)      113.84      (3.5%)    0.2% (  -6% -    7%) 0.849
                      HighPhrase      103.91      (4.5%)      104.21      (4.5%)    0.3% (  -8% -    9%) 0.837
                       LowPhrase      103.85      (3.5%)      104.28      (3.2%)    0.4% (  -6% -    7%) 0.697
                          Fuzzy2       92.09      (8.4%)       92.55     (10.2%)    0.5% ( -16% -   20%) 0.865

Overall, it was able to prevent severe performance drop when the index is unsorted, and only had around 5% negative impact to AndMedFilterMonth task.
However, I also noticed that somehow with sorted index, AndMedFilterMonth was also negatively impacted, so I also made some changes to the task definition below to use the same set of months from AndHighFilterMonth, just to see if query / index characteristics might have affected this.
--- a/tasks/wikimedium.10M.nostopwords.tasks
+++ b/tasks/wikimedium.10M.nostopwords.tasks
@@ -17381,8 +17381,8 @@ AndHighFilterMonth: +united +filter=monthPostings:feb #  freq=1185528
 AndHighFilterMonth: +year +filter=monthPostings:mar #  freq=1098425
 AndHighFilterMonth: +its +filter=monthPostings:apr #  freq=1160703
 AndHighFilterMonth: +but +filter=monthPostings:may #  freq=1484398
-AndMedFilterMonth: +mostly +filter=monthPostings:jun #  freq=89401
-AndMedFilterMonth: +interview +filter=monthPostings:jul #  freq=94736
-AndMedFilterMonth: +9 +filter=monthPostings:aug #  freq=541405
-AndMedFilterMonth: +hard +filter=monthPostings:sep #  freq=92045
-AndMedFilterMonth: +bay +filter=monthPostings:oct #  freq=117167
\ No newline at end of file
+AndMedFilterMonth: +mostly +filter=monthPostings:jan #  freq=89401
+AndMedFilterMonth: +interview +filter=monthPostings:feb #  freq=94736
+AndMedFilterMonth: +9 +filter=monthPostings:mar #  freq=541405
+AndMedFilterMonth: +hard +filter=monthPostings:apr #  freq=92045
+AndMedFilterMonth: +bay +filter=monthPostings:may #  freq=117167

and got the following results:
Index with sorting
Result 1:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      283.26      (5.8%)      253.88      (4.9%)  -10.4% ( -19% -    0%) 0.000
        AndHighHighDayTaxoFacets       20.44      (2.7%)       19.15      (2.4%)   -6.3% ( -11% -   -1%) 0.000
               HighTermTitleSort      120.21      (4.1%)      114.08      (3.7%)   -5.1% ( -12% -    2%) 0.000
         AndHighMedDayTaxoFacets      170.82      (3.3%)      162.82      (3.8%)   -4.7% ( -11% -    2%) 0.000
               HighTermMonthSort     3189.35      (3.2%)     3057.15      (3.0%)   -4.1% ( -10% -    2%) 0.000
            MedTermDayTaxoFacets       53.47      (2.7%)       51.33      (2.3%)   -4.0% (  -8% -    1%) 0.000
                      TermDTSort      195.70      (3.6%)      188.61      (3.8%)   -3.6% ( -10% -    4%) 0.002
           HighTermDayOfYearSort      373.45      (2.5%)      360.41      (3.2%)   -3.5% (  -9% -    2%) 0.000
                    OrNotHighLow     1406.59      (3.4%)     1357.71      (3.8%)   -3.5% ( -10% -    3%) 0.002
          OrHighMedDayTaxoFacets       19.41      (5.5%)       18.90      (4.5%)   -2.7% ( -11% -    7%) 0.092
                        Wildcard      147.47      (6.6%)      144.35      (6.7%)   -2.1% ( -14% -   11%) 0.314
                 LowSloppyPhrase      351.23      (4.5%)      344.15      (4.5%)   -2.0% ( -10% -    7%) 0.156
            HighTermTitleBDVSort       30.79      (4.5%)       30.22      (4.2%)   -1.8% ( -10% -    7%) 0.177
            BrowseDateSSDVFacets        5.64      (7.3%)        5.55     (10.2%)   -1.7% ( -17% -   17%) 0.553
                         LowTerm     1412.43      (5.4%)     1393.26      (4.4%)   -1.4% ( -10% -    8%) 0.382
                    HighSpanNear       35.54      (1.5%)       35.08      (1.1%)   -1.3% (  -3% -    1%) 0.003
            HighIntervalsOrdered        6.83     (13.5%)        6.74     (13.5%)   -1.3% ( -24% -   29%) 0.764
                       OrHighLow      715.40      (3.0%)      706.45      (4.5%)   -1.3% (  -8% -    6%) 0.304
                    OrNotHighMed      667.12      (2.4%)      659.49      (2.9%)   -1.1% (  -6% -    4%) 0.173
             LowIntervalsOrdered       16.55      (9.1%)       16.37      (9.1%)   -1.1% ( -17% -   18%) 0.707
                     MedSpanNear      137.56      (2.3%)      136.08      (2.1%)   -1.1% (  -5% -    3%) 0.125
                     LowSpanNear      126.90      (1.7%)      125.66      (1.4%)   -1.0% (  -3% -    2%) 0.046
                       MedPhrase      259.38      (5.0%)      257.29      (5.4%)   -0.8% ( -10% -   10%) 0.625
             MedIntervalsOrdered       94.29     (13.2%)       93.61     (13.3%)   -0.7% ( -24% -   29%) 0.863
                    OrHighNotLow      736.08      (4.6%)      731.29      (4.4%)   -0.7% (  -9% -    8%) 0.645
                        PKLookup      277.80      (4.1%)      276.28      (4.9%)   -0.5% (  -9% -    8%) 0.702
                   OrNotHighHigh      505.64      (3.7%)      503.51      (3.3%)   -0.4% (  -7% -    6%) 0.701
                          Fuzzy2       85.81      (4.3%)       85.49      (7.0%)   -0.4% ( -11% -   11%) 0.837
       BrowseDayOfYearSSDVFacets       14.25      (6.6%)       14.20      (6.0%)   -0.4% ( -12% -   13%) 0.853
                      AndHighMed      123.40      (3.7%)      122.95      (3.0%)   -0.4% (  -6% -    6%) 0.729
                      HighPhrase      105.62      (2.9%)      105.25      (3.0%)   -0.4% (  -6% -    5%) 0.704
                HighSloppyPhrase       25.14      (5.8%)       25.06      (5.8%)   -0.3% ( -11% -   11%) 0.862
                   OrHighNotHigh      488.98      (3.4%)      487.73      (3.4%)   -0.3% (  -6% -    6%) 0.812
                         MedTerm     2015.74      (3.9%)     2010.82      (3.7%)   -0.2% (  -7% -    7%) 0.839
                     AndHighHigh       83.67      (3.7%)       83.48      (3.0%)   -0.2% (  -6% -    6%) 0.831
                          IntNRQ      101.13      (6.3%)      100.91      (6.3%)   -0.2% ( -12% -   13%) 0.914
                       LowPhrase       39.11      (3.0%)       39.03      (3.3%)   -0.2% (  -6% -    6%) 0.845
                 MedSloppyPhrase      106.20      (2.6%)      106.07      (2.4%)   -0.1% (  -5% -    5%) 0.875
                          Fuzzy1       79.48      (7.4%)       79.42      (7.4%)   -0.1% ( -13% -   15%) 0.974
            BrowseDateTaxoFacets       19.43      (2.5%)       19.42      (2.2%)   -0.1% (  -4% -    4%) 0.938
                         Respell       83.42      (7.4%)       83.45      (7.9%)    0.0% ( -14% -   16%) 0.987
                        HighTerm      819.26      (5.4%)      820.06      (4.9%)    0.1% (  -9% -   10%) 0.952
                      OrHighHigh       34.32      (4.6%)       34.36      (3.9%)    0.1% (  -8% -    9%) 0.940
                       OrHighMed       92.58      (3.8%)       92.67      (3.1%)    0.1% (  -6% -    7%) 0.924
                    OrHighNotMed      572.17      (4.5%)      572.87      (4.5%)    0.1% (  -8% -    9%) 0.931
           BrowseMonthTaxoFacets       18.19      (2.6%)       18.24      (2.4%)    0.3% (  -4% -    5%) 0.709
       BrowseDayOfYearTaxoFacets       14.46      (3.5%)       14.55      (3.0%)    0.7% (  -5% -    7%) 0.531
           BrowseMonthSSDVFacets       20.07      (7.4%)       20.23      (9.7%)    0.8% ( -15% -   19%) 0.766
                      AndHighLow     1259.85      (4.0%)     1273.60      (3.8%)    1.1% (  -6% -    9%) 0.373
                  AndMedNotMonth     1075.74      (3.8%)     1172.98      (3.2%)    9.0% (   1% -   16%) 0.000
               AndMedFilterMonth     1140.24      (6.0%)     1289.34      (5.3%)   13.1% (   1% -   25%) 0.000
              AndHighFilterMonth      467.70      (3.7%)      596.35      (4.9%)   27.5% (  18% -   37%) 0.000
                 AndHighNotMonth      364.62      (3.0%)      627.22      (7.8%)   72.0% (  59% -   85%) 0.000

Result 2:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                         Prefix3      378.42      (4.0%)      353.70      (3.3%)   -6.5% ( -13% -    0%) 0.000
         AndHighMedDayTaxoFacets       46.31      (2.7%)       43.95      (3.0%)   -5.1% ( -10% -    0%) 0.000
                      TermDTSort      195.09      (4.0%)      186.41      (4.1%)   -4.5% ( -12% -    3%) 0.001
               HighTermTitleSort      110.04      (3.9%)      105.25      (4.3%)   -4.4% ( -12% -    4%) 0.001
        AndHighHighDayTaxoFacets       28.36      (2.3%)       27.13      (2.2%)   -4.3% (  -8% -    0%) 0.000
                        Wildcard      220.25      (4.3%)      212.79      (3.8%)   -3.4% ( -11% -    4%) 0.008
                       OrHighLow      430.09      (5.2%)      420.41      (6.3%)   -2.3% ( -13% -    9%) 0.218
           HighTermDayOfYearSort      322.71      (3.0%)      315.77      (3.1%)   -2.2% (  -7% -    4%) 0.025
            HighTermTitleBDVSort       31.31      (2.2%)       30.70      (1.6%)   -2.0% (  -5% -    1%) 0.001
            MedTermDayTaxoFacets       91.69      (3.4%)       89.93      (2.8%)   -1.9% (  -7% -    4%) 0.050
                    OrHighNotLow      542.35      (6.1%)      532.91      (4.4%)   -1.7% ( -11% -    9%) 0.301
          OrHighMedDayTaxoFacets        8.60      (4.3%)        8.46      (3.7%)   -1.7% (  -9% -    6%) 0.188
                    HighSpanNear       48.01      (1.6%)       47.32      (1.3%)   -1.4% (  -4% -    1%) 0.002
                    OrHighNotMed      847.43      (4.6%)      835.55      (4.1%)   -1.4% (  -9% -    7%) 0.310
                         MedTerm      962.30      (6.4%)      950.63      (5.4%)   -1.2% ( -12% -   11%) 0.517
                          Fuzzy1       81.00      (6.5%)       80.08      (6.0%)   -1.1% ( -12% -   12%) 0.566
                   OrNotHighHigh      552.98      (3.7%)      546.73      (3.0%)   -1.1% (  -7% -    5%) 0.286
                     MedSpanNear       12.59      (0.8%)       12.45      (0.7%)   -1.1% (  -2% -    0%) 0.000
                         LowTerm     1599.39      (6.3%)     1582.98      (3.8%)   -1.0% ( -10% -    9%) 0.536
                      OrHighHigh       45.70      (4.6%)       45.27      (4.6%)   -1.0% (  -9% -    8%) 0.512
                    OrNotHighLow     1445.93      (3.8%)     1433.84      (3.9%)   -0.8% (  -8% -    7%) 0.494
                   OrHighNotHigh      561.36      (4.2%)      557.15      (3.0%)   -0.7% (  -7% -    6%) 0.514
               HighTermMonthSort     2730.23      (3.9%)     2711.82      (3.6%)   -0.7% (  -7% -    7%) 0.566
             MedIntervalsOrdered       80.30      (5.8%)       79.80      (5.8%)   -0.6% ( -11% -   11%) 0.736
                          Fuzzy2       87.54      (6.0%)       87.09      (5.7%)   -0.5% ( -11% -   11%) 0.780
            HighIntervalsOrdered        6.28      (5.5%)        6.25      (5.5%)   -0.5% ( -10% -   11%) 0.776
                         Respell       71.34      (4.4%)       71.00      (4.3%)   -0.5% (  -8% -    8%) 0.727
                       MedPhrase      214.30      (4.9%)      213.27      (4.7%)   -0.5% (  -9% -    9%) 0.754
             LowIntervalsOrdered       10.88      (5.0%)       10.83      (5.1%)   -0.5% ( -10% -   10%) 0.769
                    OrNotHighMed      503.93      (3.9%)      501.66      (3.0%)   -0.5% (  -7% -    6%) 0.683
                          IntNRQ       53.53      (5.3%)       53.33      (4.6%)   -0.4% (  -9% -   10%) 0.810
                        HighTerm      788.21      (6.7%)      785.26      (5.1%)   -0.4% ( -11% -   12%) 0.843
                       LowPhrase      581.98      (4.8%)      579.89      (5.2%)   -0.4% (  -9% -   10%) 0.822
                       OrHighMed      265.72      (3.6%)      264.97      (3.6%)   -0.3% (  -7% -    7%) 0.803
                        PKLookup      281.97      (2.5%)      281.25      (2.3%)   -0.3% (  -4% -    4%) 0.736
                     LowSpanNear       97.42      (1.4%)       97.18      (1.8%)   -0.2% (  -3% -    2%) 0.620
                 MedSloppyPhrase       57.32      (3.4%)       57.19      (2.9%)   -0.2% (  -6% -    6%) 0.816
                HighSloppyPhrase       30.68      (2.5%)       30.63      (2.6%)   -0.1% (  -5% -    5%) 0.865
                 LowSloppyPhrase       32.06      (2.8%)       32.02      (2.2%)   -0.1% (  -5% -    5%) 0.871
           BrowseMonthSSDVFacets       20.53      (4.6%)       20.52      (4.7%)   -0.1% (  -9% -    9%) 0.956
       BrowseDayOfYearSSDVFacets       14.53      (2.6%)       14.52      (2.5%)   -0.0% (  -5% -    5%) 0.963
       BrowseDayOfYearTaxoFacets       14.63      (2.8%)       14.66      (2.9%)    0.2% (  -5% -    6%) 0.808
            BrowseDateTaxoFacets       19.45      (2.4%)       19.51      (2.2%)    0.3% (  -4% -    5%) 0.671
           BrowseMonthTaxoFacets       18.23      (2.5%)       18.31      (2.5%)    0.4% (  -4% -    5%) 0.611
                      HighPhrase      161.02      (4.2%)      162.00      (3.8%)    0.6% (  -7% -    8%) 0.634
                     AndHighHigh       75.68      (3.6%)       76.22      (3.8%)    0.7% (  -6% -    8%) 0.540
                      AndHighLow     1653.05      (4.5%)     1665.61      (3.5%)    0.8% (  -6% -    9%) 0.550
                      AndHighMed      317.63      (4.7%)      321.08      (3.9%)    1.1% (  -7% -   10%) 0.428
            BrowseDateSSDVFacets        5.47     (12.7%)        5.53     (14.0%)    1.1% ( -22% -   31%) 0.792
                  AndMedNotMonth      907.12      (5.8%)     1006.04      (5.5%)   10.9% (   0% -   23%) 0.000
               AndMedFilterMonth      826.00      (3.8%)     1014.21      (6.3%)   22.8% (  12% -   34%) 0.000
              AndHighFilterMonth      484.41      (3.8%)      618.97      (5.9%)   27.8% (  17% -   39%) 0.000
                 AndHighNotMonth       76.61      (1.0%)      690.62     (48.2%)  801.4% ( 745% -  858%) 0.000

Index without sorting
Result 1:
                            TaskQPS baseline      StdDevQPS my_modified_version      StdDev                Pct diff p-value
                        Wildcard       35.96      (7.1%)       32.01      (4.6%)  -11.0% ( -21% -    0%) 0.000
                         Prefix3      560.43      (3.0%)      526.43      (3.1%)   -6.1% ( -11% -    0%) 0.000
               AndMedFilterMonth      264.61      (2.4%)      249.82      (2.9%)   -5.6% ( -10% -    0%) 0.000
         AndHighMedDayTaxoFacets       61.28      (1.6%)       58.14      (3.0%)   -5.1% (  -9% -    0%) 0.000
        AndHighHighDayTaxoFacets       24.07      (2.2%)       22.87      (2.5%)   -5.0% (  -9% -    0%) 0.000
               HighTermTitleSort      229.96      (3.0%)      220.60      (3.1%)   -4.1% (  -9% -    2%) 0.000
              AndHighFilterMonth      294.96      (3.8%)      283.28      (4.5%)   -4.0% ( -11% -    4%) 0.002
          OrHighMedDayTaxoFacets       11.38      (4.1%)       10.93      (3.8%)   -3.9% ( -11% -    4%) 0.002
           HighTermDayOfYearSort      412.03      (3.4%)      397.78      (2.8%)   -3.5% (  -9% -    2%) 0.000
                      TermDTSort      226.90      (2.8%)      219.54      (2.7%)   -3.2% (  -8% -    2%) 0.000
            MedTermDayTaxoFacets       60.64      (3.1%)       58.70      (2.5%)   -3.2% (  -8% -    2%) 0.000
            HighTermTitleBDVSort       21.84      (4.4%)       21.15      (4.5%)   -3.2% ( -11% -    5%) 0.023
                    OrNotHighLow     1026.62      (3.2%)      994.09      (3.8%)   -3.2% (  -9% -    3%) 0.004
                    OrNotHighMed      545.06      (2.5%)      530.44      (4.1%)   -2.7% (  -8% -    3%) 0.012
            HighIntervalsOrdered       44.88      (6.0%)       44.07      (5.3%)   -1.8% ( -12% -   10%) 0.315
             LowIntervalsOrdered      108.36      (3.1%)      106.48      (3.8%)   -1.7% (  -8% -    5%) 0.110
                     LowSpanNear       49.51      (1.9%)       48.78      (2.0%)   -1.5% (  -5% -    2%) 0.016
               HighTermMonthSort     2328.38      (7.3%)     2294.68      (6.9%)   -1.4% ( -14% -   13%) 0.518
                          Fuzzy1      150.33      (6.2%)      148.18      (6.3%)   -1.4% ( -13% -   11%) 0.467
                    HighSpanNear       29.48      (1.2%)       29.09      (1.1%)   -1.3% (  -3% -    1%) 0.000
             MedIntervalsOrdered      179.17      (5.8%)      176.92      (5.5%)   -1.3% ( -11% -   10%) 0.484
                     MedSpanNear       15.41      (2.1%)       15.24      (2.0%)   -1.1% (  -5% -    3%) 0.086
                   OrHighNotHigh      525.87      (4.7%)      520.47      (3.8%)   -1.0% (  -9% -    7%) 0.449
                       OrHighLow      567.25      (4.0%)      563.56      (4.5%)   -0.7% (  -8% -    8%) 0.627
                 AndHighNotMonth      585.89      (5.8%)      582.21      (5.9%)   -0.6% ( -11% -   11%) 0.736
                         LowTerm     1183.22      (5.6%)     1176.56      (4.9%)   -0.6% ( -10% -   10%) 0.735
                  AndMedNotMonth      860.00      (4.3%)      855.40      (4.2%)   -0.5% (  -8% -    8%) 0.689
                         Respell       73.80      (5.1%)       73.55      (5.1%)   -0.3% ( -10% -   10%) 0.833
                      HighPhrase       80.32      (2.8%)       80.13      (3.1%)   -0.2% (  -5% -    5%) 0.797
                        PKLookup      288.52      (4.4%)      287.84      (4.8%)   -0.2% (  -8% -    9%) 0.869
                   OrNotHighHigh      512.10      (4.5%)      510.97      (3.9%)   -0.2% (  -8% -    8%) 0.868
                        HighTerm      655.55      (7.1%)      654.16      (6.5%)   -0.2% ( -12% -   14%) 0.922
                         MedTerm     1090.42      (6.0%)     1088.33      (5.3%)   -0.2% ( -10% -   11%) 0.915
                HighSloppyPhrase        8.83      (3.0%)        8.81      (3.2%)   -0.1% (  -6% -    6%) 0.884
            BrowseDateSSDVFacets        5.36      (6.7%)        5.36      (6.7%)   -0.1% ( -12% -   14%) 0.956
       BrowseDayOfYearTaxoFacets       45.49      (5.4%)       45.47      (5.3%)   -0.0% ( -10% -   11%) 0.986
                    OrHighNotMed      602.62      (4.7%)      602.56      (4.8%)   -0.0% (  -9% -    9%) 0.995
                 LowSloppyPhrase       13.54      (1.9%)       13.54      (1.9%)    0.0% (  -3% -    3%) 0.989
            BrowseDateTaxoFacets       45.52      (5.4%)       45.53      (5.4%)    0.0% ( -10% -   11%) 0.992
                 MedSloppyPhrase       22.22      (2.2%)       22.23      (2.2%)    0.1% (  -4% -    4%) 0.941
           BrowseMonthTaxoFacets       37.52     (24.4%)       37.56     (24.5%)    0.1% ( -39% -   64%) 0.987
                       LowPhrase       81.07      (1.9%)       81.19      (2.2%)    0.1% (  -3% -    4%) 0.826
       BrowseDayOfYearSSDVFacets       26.54     (27.0%)       26.59     (26.7%)    0.2% ( -42% -   73%) 0.982
           BrowseMonthSSDVFacets       25.92     (26.6%)       25.98     (26.2%)    0.2% ( -41% -   72%) 0.977