An index-sorted segment still reads its points after an earlier segment crossed the hits threshold (main and branch_11x since #16857)

Since #16857 ("Consolidate Sort pruning logic", merged 2026-10-29 to main and branch_11x, in no release), a segment whose index sort starts with the search sort gets its comparator wrapped in the new IndexSortedLeafFieldComparator (FieldValueHitQueue.java:190-191 at e1faeba08bde). When not paging, the wrapper avoids the delegate's skipping work, which its own comment calls "redundant work: it measurably slows down index-sorted searches" (IndexSortedLeafFieldComparator.java:31-33), only by hiding competitiveIterator() and not forwarding setHitsThresholdReached() (:86-97). But NumericComparator keeps hitsThresholdReached and queueFull on the comparator that every leaf shares (comparators/NumericComparator.java:59-60). Once an earlier segment of the same slice that is not terminated early has crossed the threshold, the wrapped segment's points builder passes its gate (:222-228) on the forwarded setScorer and setBottom calls, estimates the competitive range and, when it is selective, intersects the BKD tree (:426-445). The iterator is never used. 10.6.0 called disableSkipping() on such segments, which dropped the builder. Performance only: the hits are correct.

• Hits threshold: IndexSearcher#search(query, n, sort) counts hits exactly up to TOTAL_HITS_THRESHOLD = 1,000 (IndexSearcher.java:100). The 1,001st hit makes countHit() call comparator.setHitsThresholdReached() (TopFieldCollector.java:64-77); a leaf collector created after that is told in its constructor (:56-59).
• Competitive iterator: once the threshold is reached and the queue is full, NumericComparator's PointsCompetitiveDISIBuilder estimates how many points fall in the range that can still enter the top n and, when that is under iteratorCost >>> 3 (8x fewer than the query matches), intersects the BKD tree and hands the collector an iterator over the result (comparators/NumericComparator.java:363-446).
• Index-sort early termination: FieldValueHitQueue.getLeafComparator wraps the comparator of each segment whose index sort starts with the search sort in IndexSortedLeafFieldComparator (FieldValueHitQueue.java:177-194, decided per segment, :202-214). It throws CollectionTerminatedException at the first non-competitive document once the threshold is reached (IndexSortedLeafFieldComparator.java:59-69).

1. When not paging, the wrapper returns null from competitiveIterator() (IndexSortedLeafFieldComparator.java:86-89) and does not forward setHitsThresholdReached() (:91-97). Its comment explains why (:31-33): "Otherwise collection terminates anyway and the delegate's skipping, e.g. building iterators from points, is redundant work: it measurably slows down index-sorted searches." It still forwards setBottom (:53-56) and setScorer (:81-84); it has to, because compareBottom needs the bottom and other comparators of a multi-field sort need the scorer.
2. The points builder's gate reads fields of the top-level comparator, protected boolean hitsThresholdReached; protected boolean queueFull; (NumericComparator.java:59-60), shared by every leaf comparator: if (hitsThresholdReached == false) return; and if (leafTopSet == false && queueFull == false) return; (:222-228).
3. An earlier segment that is not terminated early sets both: countHit() -> NumericLeafComparator.setHitsThresholdReached() (:153-159) and setBottom() (:131-137).
4. In the index-sorted segment, the forwarded setScorer() reaches PointsCompetitiveDISIBuilder.setScorer(), which takes the query's cost and runs the segment's first update, "update an iterator when we have a new segment" (:345-355); each forwarded setBottom() runs another. The gate passes, the estimate walks the tree (:426-429) and, when the range is selective, pointValues.intersect(visitor) builds an iterator (:441-445) that the wrapper never exposes.

Before #16857, 10.6.0's TopFieldCollector said "Early termination handles this segment; skipping work in the comparator is redundant." and called comparator.disableSkipping() on each such segment (TopFieldCollector.java:69-74 at 10.6.0), which set competitiveDISIBuilder = null (comparators/NumericComparator.java:110-114 at 10.6.0). #16857 removed disableSkipping (CHANGES 11.0.0, MIGRATE.md:31-32). queueFull being search-wide is legitimate; the comparator-wide hitsThresholdReached is what defeats the wrapper's only off-switch.

Repro data (2,000 unsorted docs with f = 100 to 2,099, then 4,096 docs index-sorted by f, top 10 by f): when the sorted segment starts, the bottom is f = 109, so the competitive range is f <= 108. Its estimate is under 4,096 / 8 = 512, so it intersects one 512-point BKD leaf. The segment stops after 11 of its 4,096 docs. On main the test counts 2 point-tree opens (the estimate's tree and the one inside intersect), and the earlier counting version of the test counts 512 point doc IDs; 10.6.0 and main before #16857: 0.

• Who. Anyone on main or branch_11x code (so 11.0.0 unless fixed, and downstream projects on Lucene snapshots) who calls IndexSearcher#search(query, n, sort) sorted by the leading field of the index sort, a numeric field indexed with points plus doc values (a timestamp, a price), and whose search reaches such a segment after an earlier segment that the index sort does not terminate early has crossed the threshold. Executed trigger shapes (100,000-doc sorted segment after an earlier top 10 from f = 10,000: 10,752 point doc IDs on main, 0 with the fix, top 10 correct in each):
  • a MultiReader over indexes with different or no index sorts (the GITHUB#14399 use that 10.6.0 added per-segment support for; the repro);
  • one index with a parent field that mixes segments with and without document blocks (block segments are not terminated early since #16947);
  • one index sorted by (k, f) where k is constant in some segments, searched by f (#16857's no-op leading field path, FieldValueHitQueue.java:210-213);
  • a two-field search sort [f, g] over an [f, g] index sort (512 point doc IDs with the repro's data).
• Conditions in the segment. The points builder exists only for the first sort field when that field has points (NumericComparator.java:98-106); the gate also returns when docs without the field make the missing value competitive (:230-233); and an intersection runs only when the competitive range is under 1/8 of the current cost (:426-441), otherwise an update stops after the estimate walk.
• Default vs opt-in. Default codec, IndexSearcher and threshold, assertions on or off; but index sorting is opt-in and the mixed layout is uncommon. Without an executor one collector sees every segment (IndexSearcher.java:226-231); with one, only an earlier segment of the same slice counts (a segment over 250,000 docs gets its own slice, :106); that is a property of the current implementation (each slice's collector creates its own comparators, TopFieldCollectorManager.java:112-114), not an API guarantee. Order matters: a sorted segment before the unsorted one wastes nothing.
• Cost. Each intersection reads about as many point doc IDs as fall in the competitive range (whole BKD leaf blocks of 512) and runs only when the estimate is under 1/8 of the current iterator cost (NumericComparator.java:426-441); each later setBottom-time intersection must cut the cost 8x again. So the total per affected segment is at most about cost / 7 (cost/8 + cost/64 + ..., plus up to a leaf block of slack per intersection), plus one estimate walk per update. How much of that ceiling is used depends on where the earlier segment's bottom falls in the sorted segment (the sorted segment counts 11 docs and the top 10 is correct in every run):

• Rough wall-clock (indicative only: shared aarch64 host, 2 CPUs, JDK 25, medians of 9 x 400 searches, 2 runs): 2,000 unsorted + 1,000,000 sorted docs, top 10. Typical bottom (f from 100): 103.1 / 97.5 us per search on main vs 76.3 / 73.7 us with the fix (about 1.3x). A bottom just under cost/8 (f from 124,700): 203.8 / 185.4 vs 68.4 / 68.0 us (about 2.7-3x).
• Not part of this finding. Wrong results: none seen (top hits and totals identical in every shape; an exhaustive multi-leaf harness found 0 wrong results). The STRING sort (TermOrdValComparator has the same comparator-wide flag; a probe saw 9 postings() opens vs 0 in a 100,000-doc terminated segment, not verified independently) and the doc-values-skipper builder (iterator object only, no skipper reads).

TestIndexSortedSegmentPointsWork (one method, extends LuceneTestCase). Each index is written with the default codec (TestUtil.getDefaultCodec()) in one IndexWriter session, so each is one segment; the searcher is a plain new IndexSearcher(reader) (one slice, no executor). The sorted segment's PointValues are wrapped in the test framework's AssertingPointValues, overriding getPointTree() to count. Same outcome with seed DEADBEEF (-ea and -da) and with seeds C0FFEE and 7A11CE (-ea, in the fact check's runs). The test asserts only the tree opens; the correct top 10 and the 11 docs collected come from the earlier counting test and a separate probe.

It uses the main signatures; for 10.x add throws IOException to the getPointValues override, nothing else (the 10.6.0 runs of this test used such a port; the hunt's separate 10.x port is of the earlier test). The commit bracket and the 10.5.2 and 9.12.3 runs used an earlier, longer version of the test (a counting PointTree wrapper that also checks the top 10), which counts 512 point doc IDs where this one counts 2 tree opens.

As a regression test the same method can go into TestTopFieldCollectorEarlyTermination or stay its own class; fix A also needs the TestNumericComparator adaptation (see the fixes).

cp $REPRO/TestIndexSortedSegmentPointsWork.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestIndexSortedSegmentPointsWork -Ptests.seed=DEADBEEF

# gradle, scratch worktree at main e1faeba08bde, -Ptests.seed=DEADBEEF (asserts on; again with -Ptests.asserts=false)
TestIndexSortedSegmentPointsWork > testEarlyTerminatedSegmentReadsNoPoints FAILED
    java.lang.AssertionError: expected:<0> but was:<2>
        at org.apache.lucene.search.TestIndexSortedSegmentPointsWork.testEarlyTerminatedSegmentReadsNoPoints(TestIndexSortedSegmentPointsWork.java:74)
1 test completed, 1 failed

# same worktree + the per-leaf flag fix and the TestNumericComparator adaptation
TestIndexSortedSegmentPointsWork: 1 test, 0 failures (asserts on and off)

# standalone JUnit runner, seed DEADBEEF, -ea and -da
main e1faeba08bde        1 run, 1 failure    expected:<0> but was:<2>
main 645d4fe14a20        1 run, 0 failures   (predates #16857)
10.6.0 (4ae946e5a9b)     1 run, 0 failures   (10.x signature port)

• The PR's own words. IndexSortedLeafFieldComparator.java:31-33 (#16857, e1faeba08bde): "When paging, docs before the top value never fill the queue, so only the delegate can skip them. Otherwise collection terminates anyway and the delegate's skipping, e.g. building iterators from points, is redundant work: it measurably slows down index-sorted searches."
• The released design. 10.6.0's LeafFieldComparator#disableSkipping javadoc (LeafFieldComparator.java:115-122 at 10.6.0): "Called by TopFieldCollector when the search sort is a prefix of this segment's index sort, so the collector can already terminate early and any extra skipping work in the comparator is redundant. This is a per-segment decision: a MultiReader may combine segments with different index sorts." CHANGES 10.6.0 (GITHUB#14399): "...so document skipping can be disabled per segment."
• Older precedent. LUCENE-9599 (#10639, 2020): "As the early termination in this case is already handled in TopFieldCollector, we need to disable sort optimization in comparators."
• A consolidation, not a policy change. The 11.0.0 CHANGES entry #16857 added (CHANGES.txt:39-47, labelled GITHUB#14399, the same issue number as 10.6.0's disableSkipping entry) says the pruning decisions are "consolidated into FieldValueHitQueue, and early termination through examining index sorts is handled by a new IndexSortedLeafFieldComparator class"; MIGRATE.md:31-32 lists disableSkipping as removed. The PR's review is about document blocks; mixed segments and the shared flag never come up.
• No test covers it. TestTopFieldCollectorEarlyTermination.testMultiReaderWithDifferentIndexSorts (:283) and testQueueFilledInEarlierSegment (:548) check hits only.
• Precedent for the class of bug. #13498, "Avoid performance regression by constructing lazily the PointTree in NumericComparator", is listed under Bug Fixes in 9.11.1 and 10.0.0.

The strongest case for "intended" (built by an intended-behaviour checker): the flags are comparator-wide on purpose (since LUCENE-9449, 2020), and upstream TestNumericComparator sets comparator1.hitsThresholdReached = true before creating a leaf comparator to emulate a later leaf; the wrapper is package-private and its @param paging javadoc only says what is "passed through" when paging; no public javadoc promises "no points work"; the cost is bounded.

Why it fails: the shared flag was harmless while an early-terminated segment had no points builder (10.6.0 dropped it per segment). #16857 replaced that switch with a mechanism, not forwarding one call, that works only if the delegate's state is per segment, and its own comment states the goal it then misses. Bounded cost and the missing javadoc promise lower the priority, not the verdict.

Two designs; the first was built and validated, the second is the released 10.6.0 behaviour. The choice is the maintainers'.

In comparators/NumericComparator.java: NumericLeafComparator records whether it was told itself, and CompetitiveDISIBuilder.updateCompetitiveIterator() tests that instead of the comparator-wide field. Since #16857, TopFieldLeafCollector tells every leaf at construction once the threshold was crossed earlier (TopFieldCollector.java:56-59) and countHit() tells it when it crosses it (:70-75), and MultiLeafFieldComparator forwards the call to the first comparator of a multi-field sort (MultiLeafFieldComparator.java:95-99), so in Lucene's own TopFieldCollector paths every normal leaf keeps its pruning; only a wrapped, non-paging leaf, which the wrapper never tells, stops doing points work. Code that writes the protected field directly is the first trade-off. The same gate also guards the doc-values-skipper builder.

     private final CompetitiveDISIBuilder competitiveDISIBuilder;
+    // Whether this leaf was told that the hits threshold is reached. A leaf that terminates early
+    // by its index sort is not told (IndexSortedLeafFieldComparator), so it does no points work.
+    private boolean leafHitsThresholdReached;
@@ NumericLeafComparator.setHitsThresholdReached()
       hitsThresholdReached = true;
+      leafHitsThresholdReached = true;
@@ CompetitiveDISIBuilder.updateCompetitiveIterator()
-      if (hitsThresholdReached == false) {
+      if (leafComparator.leafHitsThresholdReached == false) {
         return;
       }

Trade-offs

• It changes what the protected comparator-wide field means for the gate. Upstream TestNumericComparator.testEmptyCompetitiveIteratorOptimization sets comparator1.hitsThresholdReached = true directly (TestNumericComparator.java:215 and three siblings) and fails with the fix, expected:<2147483647> but was:<0>; the adaptation makes those four helpers call leafComparator.setHitsThresholdReached() instead, "as TopFieldCollector does for a leaf that starts after the threshold was reached". Subclasses outside Lucene that set the field directly would need the same change.
• It relies on #16857's constructor-time call to tell later normal leaves. LFV-1057's fixes keep that (a cost guard) or move it into setScorer(); both combine with this fix (both repros pass).
• Scope: it covers NumericComparator only. TermOrdValComparator (STRING sort) has its own comparator-wide hitsThresholdReached (comparators/TermOrdValComparator.java:110, set at :318, read at :418), so the STRING analogue (not part of this finding) would remain; it could get the same per-leaf flag.
• Open PR #16163 (search_after with the doc-values skipper) rewrites the same gate line into if (hitsThresholdReached == false && leafTopSet == false) {, so the two conflict as text; they appear to compose as if (leafComparator.leafHitsThresholdReached == false && leafTopSet == false) { (not built or tested: rebase onto its current head and run both changes' tests).

What the checks validated

• Gradle in a scratch worktree at e1faeba08bde, JDK 25, -Ptests.seed=DEADBEEF (2026-11-02): the repro fails without the fix (asserts on and off) and passes with it (asserts on and off). With the fix and the test adaptation, org.apache.lucene.search.* (all subpackages) plus org.apache.lucene.index.TestIndexSorting: 217 classes, 2,413 tests, 0 failures, 49 skipped, among them TestSortOptimization (31), TestTopFieldCollectorEarlyTermination (12), TestTopFieldCollector (13), TestSort (30) and TestNumericComparator (3). The fix alone with the unmodified TestNumericComparator fails 1 of 3 (the trade-off above).
• Hunt (standalone runner): the trigger shapes drop to 0 while the plain control without an index sort keeps its 10,752; the 1,000,000-doc case with a bottom just under cost/8 drops to 0 while its control keeps 125,440; an exhaustive multi-leaf harness (42,520,140 + 113,540,400 searches) finds 0 wrong results, wasted points work in 90,192 / 337,440 wrapped leaf-searches on main vs 0 with the fix, and identical pruning in every non-wrapped leaf of its bounded configurations; in a TLA+ model of the leaf protocol (TLC) the invariant NoETWork is violated on main and holds with the fix.

Give LeafFieldComparator back a hook like 10.6.0's disableSkipping() (default no-op; NumericLeafComparator drops its builder; MultiLeafFieldComparator forwards it) and have IndexSortedLeafFieldComparator call it on its delegate when not paging.

Trade-offs

Keeps the protected field's meaning and needs no test change; it is the 10.6.0 behaviour. But it re-adds a method #16857 removed on purpose (CHANGES 11.0.0, MIGRATE.md:31-32), and since the wrapper and the comparators live in different packages the hook has to be public (perhaps @lucene.internal).

The wrapper could hide the calls that drive the builder.

Trade-offs

compareBottom needs the bottom set by setBottom, and other comparators of a multi-field sort need the scorer, so this breaks sorting.

Method: non-formal (the first signal came from code reading and an executed probe; the formal model came later).

• Lead. A review of newly merged upstream code read the #16857 diff.
• Probe. A differential count through the public FilterLeafReader API with a counting PointValues/PointTree wrapper, on upstream main, on main before #16857 and on 10.6.0, identical top 10 in every run: in the MultiReader and block/non-block shapes 10,752 point doc IDs on main vs 0 before #16857 and on 10.6.0; in the no-op leading-field shape 10,752 on main vs 0 with the fix (before #16857 that segment is not terminated early, so its 10,752 there is real pruning; not run on 10.6.0).
• Reduction. One JUnit test, run on main and the commit bracket with assertions on and off, and on three releases (10.6.0 with assertions on and off, 10.5.2 and 9.12.3 with assertions off); a later review replaced it with the one-method test above.
• Model. A TLA+ model of the per-leaf collector/comparator protocol with leaf kinds and the wrapper (TLC): the invariant NoETWork (no points work in a leaf the index sort terminates, when not paging) is violated by upstream main and holds for the code before #16857 and for every per-leaf-flag variant; the properties that no first update is lost and that paging keeps its updates hold everywhere.
• Exhaustive harness. A bounded-exhaustive multi-leaf harness with a per-leaf points-work counter: 0 wrong results; points work in wrapped, non-paging leaves on main only.