Significant performance impact with new TermOrdValComparator.SkipperBasedCompetitiveState

[benwtrent]

Description

During the 10.4 release process, we noticed a 100-300x slowdown on a benchmark that utilizes doc-skippers.

The query is rather innocuous, its an attempt to sort the result by a SORTED SET field while filtering by a separate sorted set field. The index is sorted by both fields, but also by multiple others.

Before the changes to TermOrdValComparator.SkipperBasedCompetitiveState this query took about 4ms, now its 700+ms.

Here are some interesting flamegraphs (I am attempting to get JFR to pair down the actual times of the queries, but its taking hours as the actual runtime of the benchmark is many hours...)

baseline (note how its 0.06% of samples)

candidate (note how its over 3% of samples)

I am still attempting to fully replicate without an insane benchmark run of multiple hours. The key things seem to be:

• Index sorted by (but not exclusively by) two doc value fields
• Using a skipper with larger windows
• ... and I am not sure what else... need to dig further, this is new territory for me.

Regardless, this competitive iterator is still doing WAY too much work and obviously needs fixing.

One of the key things this shows me is the lack of Lucene Util nightly benchmarks that use the new doc-skipper stuff. I think @romseygeek is working on these to catch stuff like this early.

Related PRs:

• Use SkipBlockRangeIterator in TermOrdValComparator #15696
• Dynamic pruning for SORTED(_SET) fields with doc values skipper #15511

Version and environment details

No response

[benwtrent]

OK, I have a test that repeats the failure, I am not 100% sure if it fully represents our use-case.

Our test uses a compound field as the index sort. This sorting by many various fields might be construed as not really sorting effectively by a single field depending on its cardinality and distribution. Basically, the index could be considered not sorted by the field at all. This is hypothetical. I need @romseygeek to help me here ;).

Here is a test that repeatably fails which the competitive iterator, but passes without it:

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.search;

import java.io.IOException;
import java.util.Arrays;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.SortedDocValuesField;
import org.apache.lucene.document.StringField;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.Term;
import org.apache.lucene.store.Directory;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.BytesRef;

public class TestTermOrdValComparatorSkipperNightly extends LuceneTestCase {

  private static final String SORT_FIELD_SKIP = "meta.file.skip";
  private static final String SORT_FIELD_NO_SKIP = "meta.file.noskip";
  private static final String QUERY_FIELD = "process.name";
  private static final String QUERY_VALUE = "kernel";
  private static final int NUM_DOCS = 200_000;
  private static final int NUM_HITS = 10;
  private static final int TOTAL_HITS_THRESHOLD = 1;
  private static final int WARMUP_ITERS = 2;
  private static final int MEASURE_ITERS = 5;
  private static final double MAX_SLOWDOWN_RATIO = 1.2d;

  @Nightly
  public void testSkipperRegressionOnUncorrelatedDocOrder() throws Exception {
    try (Directory dir = newDirectory()) {
      IndexWriterConfig config = newIndexWriterConfig();

      BytesRef a = new BytesRef("a");
      BytesRef z = new BytesRef("z");
      try (IndexWriter writer = new IndexWriter(dir, config)) {
        for (int i = 0; i < NUM_DOCS; i++) {
          Document doc = new Document();
          doc.add(new StringField(QUERY_FIELD, QUERY_VALUE, Field.Store.NO));
          BytesRef value = (i & 1) == 0 ? a : z;
          doc.add(new SortedDocValuesField(SORT_FIELD_NO_SKIP, value));
          doc.add(SortedDocValuesField.indexedField(SORT_FIELD_SKIP, value));
          writer.addDocument(doc);
        }
        writer.forceMerge(1);
      }

      try (IndexReader reader = DirectoryReader.open(dir)) {
        IndexSearcher searcher = new IndexSearcher(reader);
        Query query = new TermQuery(new Term(QUERY_FIELD, QUERY_VALUE));

        Sort sortWithSkipping = buildSort(SORT_FIELD_SKIP);
        Sort sortWithoutSkipping = buildSort(SORT_FIELD_NO_SKIP);

        warmup(searcher, query, sortWithSkipping);
        warmup(searcher, query, sortWithoutSkipping);

        long withSkipping = measure(searcher, query, sortWithSkipping);
        long withoutSkipping = measure(searcher, query, sortWithoutSkipping);

        double ratio = (double) withSkipping / (double) withoutSkipping;
        assertTrue(
            "skipping-enabled sort should not be much slower; ratio=" + ratio,
            ratio <= MAX_SLOWDOWN_RATIO);
      }
    }
  }

  private static Sort buildSort(String field) {
    SortField sortField = new SortField(field, SortField.Type.STRING);
    return new Sort(sortField, SortField.FIELD_SCORE);
  }

  private static void warmup(IndexSearcher searcher, Query query, Sort sort) throws IOException {
    for (int i = 0; i < WARMUP_ITERS; i++) {
      TopFieldCollectorManager manager =
          new TopFieldCollectorManager(sort, NUM_HITS, null, TOTAL_HITS_THRESHOLD);
      searcher.search(query, manager);
    }
  }

  private static long measure(IndexSearcher searcher, Query query, Sort sort) throws IOException {
    long[] times = new long[MEASURE_ITERS];
    for (int i = 0; i < MEASURE_ITERS; i++) {
      TopFieldCollectorManager manager =
          new TopFieldCollectorManager(sort, NUM_HITS, null, TOTAL_HITS_THRESHOLD);
      long start = System.nanoTime();
      searcher.search(query, manager);
      times[i] = System.nanoTime() - start;
    }
    Arrays.sort(times);
    return times[times.length / 2];
  }
}

Run with:

./gradlew :lucene:core:test --tests "org.apache.lucene.search.TestTermOrdValComparatorSkipperNightly" -Ptests.nightly=true

[romseygeek]

I think the issue here is per-document overhead when the skipper-based competitive iterators can't actually help. We already have some adaptive backoff in NumericComparators for this situation, and I've opened a PR to add something similar to TermOrdValComparator for the skipper case. The test that @benwtrent has added above will pass with my PR, although I opted not to include it directly as wall-clock based timings are too fragile for regular CI tests.