(lucene) branch main updated: Order two-phase iterators in DenseConjunctionBulkScorer by matchCost (#16370)

[ro...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

romseygeek pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/main by this push:
     new c4e4e9b1cf8 Order two-phase iterators in DenseConjunctionBulkScorer by matchCost (#16370)
c4e4e9b1cf8 is described below

commit c4e4e9b1cf80ebe4c258aba2b0cce16a1bd2d0e5
Author: Alan Woodward <ro...@apache.org>
AuthorDate: Tue Jul 7 13:39:01 2026 +0100

    Order two-phase iterators in DenseConjunctionBulkScorer by matchCost (#16370)
    
    Currently two-phase iterators are ordered by their approximation
    cost. Many two-phase implementations use maxDoc as their approximation,
    however, meaning that we don't necessarily get a good ordering
    between them and more expensive matches can be called unnecessarily.
    
    This adds an additional comparison layer for two-phase iterators
    that orders by matchCost.
---
 lucene/CHANGES.txt                                 |  3 +
 .../lucene/search/DenseConjunctionBulkScorer.java  |  6 +-
 .../search/TestDenseConjunctionBulkScorer.java     | 85 ++++++++++++++++++++++
 3 files changed, 93 insertions(+), 1 deletion(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 12b928dae11..125fd7cf6d8 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -337,6 +337,9 @@ Optimizations
 * GITHUB#16355: Add ASCII fast-path to CharacterUtils.toLowerCase, avoiding per-char codepoint
   conversion for ASCII-only tokens. 2.16x throughput on English text. (Costin Leau)
 
+* GITHUB#16370: Sort two-phase iterators by matchCost in DenseConjunctionBulkScorer.
+  (Alan Woodward)
+
 Bug Fixes
 ---------------------
 * GITHUB#16350: Disable bulk-scoring in monitor queries. (Alan Woodward)
diff --git a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
index 41f5e71f2d9..9f59eb2c2bb 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
@@ -112,9 +112,13 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
     }
     // Plain approximations before two-phase ones, so matches() only runs on docs that already
     // satisfy every approximation; within each group, cheapest approximation first (lead skipping).
+    // Two-phase clauses that tie on approximation cost are further ordered by matchCost, so a cheap
+    // confirmation (e.g. a doc values range) runs before an expensive one (e.g. a script) even when
+    // both report the same approximation cost.
     this.iterators.sort(
         Comparator.<DisiWrapper>comparingInt(w -> w.twoPhase() == null ? 0 : 1)
-            .thenComparingLong(w -> w.approximation().cost()));
+            .thenComparingLong(w -> w.approximation().cost())
+            .thenComparingDouble(w -> w.twoPhase() == null ? 0 : w.twoPhase().matchCost()));
     this.scorable = new SimpleScorable();
     scorable.score = constantScore;
   }
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java b/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
index c05cb11a543..c23e94d7ab0 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java
@@ -1067,6 +1067,91 @@ public class TestDenseConjunctionBulkScorer extends LuceneTestCase {
     assertEquals(30_000, collector.count);
   }
 
+  /**
+   * When two two-phase clauses tie on approximation cost, the scorer must still confirm the clause
+   * with the cheaper {@link TwoPhaseIterator#matchCost()} first, so that it thins out candidates
+   * before the more expensive confirmation runs. The clauses are passed to the constructor with the
+   * expensive one first, so any observed ordering comes purely from the {@code matchCost}
+   * tie-break.
+   */
+  public void testTwoPhaseIteratorsOrderedByMatchCost() throws IOException {
+    int maxDoc = 100_000;
+
+    // A plain (non-two-phase) leading clause that matches every other doc.
+    FixedBitSet leadMatches = new FixedBitSet(maxDoc);
+    for (int i = 0; i < maxDoc; i += 2) {
+      leadMatches.set(i);
+    }
+    DocIdSetIterator lead = new BitSetIterator(leadMatches, leadMatches.approximateCardinality());
+
+    int[] cheapCalls = {0};
+    int[] expensiveCalls = {0};
+
+    // Cheap to confirm, and selective: only matches 1 in 8 candidates.
+    TwoPhaseIterator cheap =
+        new TwoPhaseIterator(DocIdSetIterator.all(maxDoc)) {
+          @Override
+          public boolean matches() throws IOException {
+            cheapCalls[0]++;
+            return approximation().docID() % 8 == 0;
+          }
+
+          @Override
+          public float matchCost() {
+            return 1f;
+          }
+        };
+    // Expensive to confirm, and matches everything it's asked about.
+    TwoPhaseIterator expensive =
+        new TwoPhaseIterator(DocIdSetIterator.all(maxDoc)) {
+          @Override
+          public boolean matches() throws IOException {
+            expensiveCalls[0]++;
+            return true;
+          }
+
+          @Override
+          public float matchCost() {
+            return 1000f;
+          }
+        };
+
+    BulkScorer scorer =
+        new DenseConjunctionBulkScorer(
+            Collections.singletonList(lead), Arrays.asList(expensive, cheap), maxDoc, 0f);
+    FixedBitSet result = new FixedBitSet(maxDoc);
+    scorer.score(
+        new LeafCollector() {
+          @Override
+          public void setScorer(Scorable scorer) throws IOException {}
+
+          @Override
+          public void collect(int doc) throws IOException {
+            result.set(doc);
+          }
+        },
+        null,
+        0,
+        DocIdSetIterator.NO_MORE_DOCS);
+
+    FixedBitSet expected = new FixedBitSet(maxDoc);
+    for (int i = 0; i < maxDoc; i += 8) {
+      expected.set(i);
+    }
+    assertEquals(expected, result);
+
+    // The cheap clause runs first and thins out the candidate set, so the expensive clause -- even
+    // though it matches every candidate it's asked about -- gets confirmed less often. Without the
+    // matchCost tie-break, both clauses tie on approximation cost and the expensive one would be
+    // confirmed just as often as the cheap one.
+    assertTrue(
+        "expensive matchCost clause should be confirmed less often than the cheap one: cheap="
+            + cheapCalls[0]
+            + " expensive="
+            + expensiveCalls[0],
+        expensiveCalls[0] < cheapCalls[0]);
+  }
+
   public void testMixedTwoPhaseRangeIntersection() throws IOException {
     int maxDoc = 100_000;
     DocIdSetIterator clause1 = DocIdSetIterator.range(10_000, 60_000);