Sorting on a multi-valued SORTED_NUMERIC field returns the wrong top hits after updateSortedNumericDocValue (doc-values overlays)

With doc-values overlays (IndexWriterConfig#setMaxDocValuesOverlays, @lucene.experimental; on by default on main with 8 overlays, opt-in in 10.6.0), a set-only doc-values update is written as a sparse layer and merged with the old column at read time. After IndexWriter#updateSortedNumericDocValue (new in 10.6.0, #16581) on a segment whose SORTED_NUMERIC field is multi-valued in some document, the segment reads the field through OverlaySortedNumericDocValues. Its advanceExact delegates to DocValuesOverlayMerger#advanceExact, which moves only layers whose docID() < target; on advanceExact(docID()) nothing moves, so nextValue() continues on the base column where the previous read stopped instead of restarting the document's values. DocValuesIterator#advanceExact allows target == docID() on purpose (LUCENE-7462: comparators read a value more than once), and TopFieldCollector does exactly that for every competitive hit (compareBottom, then copy). So SortedNumericSortField sorts can return wrong top hits and wrong sort values, silently and the same way every time for the same index and search, until a merge (or a fold to one dense column) rewrites the segment; a MAX sort can instead throw IndexOutOfBoundsException or RuntimeException(EOFException). Three documents and one update suffice: the top hit by minimum is doc 2 instead of doc 1. The documents that go wrong are the ones that were not updated; data on disk is correct. Fields that are single-valued everywhere and NUMERIC/BINARY overlays are not affected. A one-method fix in OverlaySortedNumericDocValues#advanceExact (re-position the winning layer when the target is the current document) passes the test and the doc-values-update, overlay and sort suites.

1. The view. SegmentDocValuesProducer#getSortedNumeric returns the base iterator when a field has one producer, else OverlaySortedNumericDocValues.from(...) (SegmentDocValuesProducer.java:218-224). from takes the singleton OverlayNumericDocValues path only when every layer is single-valued (OverlaySortedNumericDocValues.java:79-89), else builds OverlaySortedNumericDocValues (:91), which "works whether the base column is single- or multi-valued" (:23-28).
2. Delegation. nextValue() and docValueCount() read layers[merger.valueLayer()] (:41-49); advanceExact(target) is merger.advanceExact(target) (:51-54).
3. The merger (DocValuesOverlayMerger.java:72-80):

   while (layers[heap[1]].docID() < target) {
     layers[heap[1]].advance(target);
     siftDown();
   }
   docID = target;
   winner = layers[heap[1]].docID() == target ? heap[1] : -1;

A layer already on target is not touched. The class javadoc says layers "are advanced with advance only (never advanceExact) so iteration and random access can be interleaved" (:28-29); it says nothing about re-reading the current document.

1. The base column's cursor. In the default codec's dense multi-valued iterator, advanceExact sets start/end from the address table and nextValue() is values.get(start++) with no end check (Lucene90DocValuesProducer.java:2061-2072). Not re-positioned, a second read continues with the document's next value, then the next document's values (a neighbour's, or the pre-update values of an updated document), or runs past the end of the column.
2. The consumer. LongLeafComparator#getValueForDoc calls advanceExact(doc) (LongComparator.java:79-85) for compareBottom, compareTop and copy (:93-107), through SortedNumericSelector.MinValue (SortedNumericSelector.java:135-142: one nextValue()) or MaxValue (:169-174, :194-201: docValueCount() values). Once the queue is full, TopFieldCollector calls compareBottom(doc) (TopFieldCollector.java:93) and, for a competitive hit, copy(bottom.slot, doc) (:116). The first n documents only get copy (:122-126), one read.

A traced run of the three documents (main, assertions off): copy(doc 0) reads 50, the bottom is 50. compareBottom(doc 1) reads 10: competitive. copy(doc 1) calls advanceExact(1) again; the base layer stays on doc 1 with its cursor after 10, so nextValue() is 90 and doc 1 is stored with key 90. compareBottom(doc 2) reads 70 from the update layer; 70 < 90, so doc 2 replaces doc 1. Top hit: doc 2, key 70. With setMaxDocValuesOverlays(0): doc 1, key 10.

• Direct re-read: advanceExact(1), nextValue() = 10, advanceExact(1), nextValue() = 90.
• A MAX sort (reverse) on the same three documents returns doc 2 (70) instead of doc 1 (90).
• Two documents {5} (updated to 1) and {10, 90}, MAX descending, top 1: IndexOutOfBoundsException on a ByteBuffersDirectory, RuntimeException(EOFException: read past EOF) on an FSDirectory. Correct with overlays off.
• Wrong sort keys: with doc 0 updated to 70 instead, the MIN top hit is doc 2 with key 40 (its true minimum is 30); with doc 0 updated to 1, a MAX sort returns the right hit, doc 1, but with key 40, doc 2's value.
• searchAfter: page 2 after (doc 1, key 10) returns doc 1 again, already on page 1, with key 30 (doc 2's pre-update value); with overlays off it returns doc 0, key 50.
• Updated documents read correctly: their winning layer is the single-valued update, whose nextValue() returns the same value every time. The wrong keys go to documents that were not updated.
• Not affected: NUMERIC and BINARY overlays (they have no per-document value cursor) and SORTED_NUMERIC fields that are single-valued in every document of the segment (singleton path): 12,846 re-read checks over 200 random indexes, 0 mismatches.

• Who is exposed. Users of the new IndexWriter#updateSortedNumericDocValue (or updateDocValues with a SortedNumericDocValuesField) on a field that is multi-valued in at least one document of the segment; the javadoc and CHANGES both allow a multi-valued field ("The field itself may be single- or multi-valued"). On main this is the default configuration; in 10.6.0 it needs the experimental setMaxDocValuesOverlays(n > 0).
• Effect. Silent wrong top hits and wrong sort values (FieldDoc.fields) for SortedNumericSortField with MIN or MAX. It shows when the collector re-reads a competitive document that was not updated, so that its values come from the multi-valued base column; that needs more matches than the requested top n (or searchAfter); whether the hits or keys then come out wrong depends on the values, and the same index and search give the same wrong result every time. Sometimes loud: with MAX the stale cursor can run past the column and fail the query (IndexOutOfBoundsException or RuntimeException(EOFException)).
• How long. Until the segment is merged, or until a fold rewrites the field as one dense column, for readers opened after that (a reader that is already open keeps its view). A fold happens while writing the next set-only update once the field already has maxDocValuesOverlays delta generations; it is a dense rewrite, one producer that reads correctly, when the prior deltas' summed docs-with-value counts reach half the segment's maxDoc. Otherwise a sparse fold keeps the base plus one folded generation, still read through the overlay view.
• Scale. Three documents and one update suffice. In a random probe with 300 documents of 1 to 3 values each (2 to 11 segments) and 400 single-valued updates (6 seeds, overlay limits 1, 2 and 8), a second read was wrong for 71 to 227 of the 300 documents in each run, while single reads were right in all 73,200 checks and CheckIndex was clean.
• Not affected. Fields that are single-valued in every document of the segment (the motivating case of #16580), NUMERIC and BINARY overlays, overlays off, and persisted data: in the same probe every single read was right, after the updates and after reopening the writer with overlays off. Merges ran in only 3 of its 18 runs, so for merges the evidence is mainly upstream tests such as TestSortedNumericDocValuesUpdates#testUpdateKeepsOtherDocsMultiValuedAcrossMerge, which pass with the fix.
• Also executed. searchAfter paging, which reads each hit with compareTop and then copy (with compareBottom first once its queue is full): page 2 can return a hit from page 1 again. Application code that calls advanceExact twice on a document to read its values again gets the direct re-read above.

The test sits in org.apache.lucene.index like the upstream doc-values update tests but uses only public classes and methods. It pins the default codec (Lucene104, whose doc values use the Lucene90 format; the only codec run); newDirectory() picks the Directory by seed, and every seed tried fails (DEADBEEF through gradle and the standalone runner, assertions on and off; 1, C0FFEE and 5EED42 on the standalone runner, assertions off). With setMaxDocValuesOverlays(0) the same scenario passes.

Suggested regression test: this same test, for example as a method of TestSortedNumericDocValuesUpdates.

On 10.6.0 overlays are off by default (DEFAULT_MAX_DOC_VALUES_OVERLAYS = 0), so the test passes there as written; with .setMaxDocValuesOverlays(8) added to the IndexWriterConfig it fails with the same message. On 10.5.2 it does not compile (updateSortedNumericDocValue does not exist).

TestOverlaySortedNumericSort > testMinSortAfterUpdate FAILED
    java.lang.AssertionError: expected:<1> but was:<2>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:75239423F2B9FA40]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.junit.Assert.assertEquals(Assert.java:633)
        at org.apache.lucene.index.TestOverlaySortedNumericSort.testMinSortAfterUpdate(TestOverlaySortedNumericSort.java:49)
:lucene:core:test (FAILURE): 1 test, 1  failure

# the same with -Ptests.asserts=false, and on the standalone runner with -ea and -da
# 10.6.0 + setMaxDocValuesOverlays(8): the same failure; 10.6.0 default: passes
# with the recommended fix: 1 test, 0 failures

• Contract. DocValuesIterator#advanceExact: "target must be greater than or equal to the current doc ID" (DocValuesIterator.java:24-28). Adrien Grand on LUCENE-7462 (#8514, 2016-10-20): "Initially I wanted to require that the target is strictly greater than the current doc id but this caused issues with comparators that may need to get the value multiple times [...] So the current patch only requires that the target is greater than or equal to the current document."
• The documented way to re-read. In the 2018 java-user thread "Read DocValue twice", the same maintainer answered: "If you want to read the values again, you need to call setDocument (Lucene < 7.0) or advanceExact (Lucene >= 7.0) before calling nextValue()".
• Same defect class, fixed before. LUCENE-7890 (#8941, 2017): "The SortedSetDocValues and SortedNumericDocValues instances returned by the MemoryIndex should support subsequent advanceExact(0) invocations"; its test TestMemoryIndex#testDocValues_resetIterator is still on main and calls advanceExact(0) three times, expecting all five values each time (TestMemoryIndex.java:327-366). LUCENE-8117 (#9165, 2018) fixed advanceExact returning invalid SORTED_NUMERIC values in the Lucene54 producer.
• The other implementations checked restart. The default codec recomputes start on each advanceExact, in the dense (Lucene90DocValuesProducer.java:2061-2067) and the sparse multi-valued iterator (:2184-2198, :2263-2271); MemoryIndex does since LUCENE-7890; AssertingSortedNumericDocValues#advanceExact accepts target >= in.docID() and resets its value budget, valueUpto = 0 (AssertingLeafReader.java:1176-1187). No implementation that continues the cursor was found besides the overlay view (not an exhaustive audit).
• Overlays are a storage choice. setMaxDocValuesOverlays trades read cost for write amplification (IndexWriterConfig.java:335-342); #16581's description says supporting a multi-valued base is intended ("really it's not hard to support multi-valued SortedNumericDocValues"). With overlays off the same data sorts correctly.
• Why tests missed it. TestSortedNumericDocValuesUpdates never calls advanceExact and uses SortedNumericSortField only to check that an index-sort field is rejected; the overlay and update tests read each document once.

Strongest case (the intended-lens reviewers and the adjudication): the merger documents an advance-only design; the SortedNumericDocValues javadoc only says "Do not call this more than docValueCount times for the document" and never says that a repeated advanceExact restarts the values; overlays are @lucene.experimental. So continuing the cursor could be called allowed.

Why it fails: the advance-only rule is about moving layers ("so iteration and random access can be interleaved"), not about re-reading a document; the >= contract exists for comparators that read a value more than once, and core TopFieldCollector is that caller, so the view breaks Lucene's own sorting, not an outside misuse; @lucene.experimental marks API instability, and the feature is on by default on main. A maintainer could also document the restart explicitly, but documentation alone would not repair TopFieldCollector on overlays: a code change is still needed, preferably the overlay-local one.

Two forms of the same restart were built and run in a scratch worktree of 645d4fe14a20: in the view (recommended) and in the shared merger. A value-buffering design and a documentation-only change are listed for completeness.

When the target is the current document and a layer has it, call advanceExact(target) on the winning layer, so its values start over (OverlaySortedNumericDocValues.java, +8/-1). The idea is the first finder's.

  @Override
  public boolean advanceExact(int target) throws IOException {
    final boolean sameDoc = target == merger.docID();
    final boolean found = merger.advanceExact(target);
    if (found && sameDoc) {
      // advanceExact(docID()) must restart the document's values, but the merger does not move a
      // layer that already sits on target: re-position the winning layer (target == its docID()).
      layers[merger.valueLayer()].advanceExact(target);
    }
    return found;
  }

Trade-offs

• Safe by construction: the winning layer sits on target with a value, so advanceExact(target) is legal, returns true and leaves it there; the merger's heap and its advance-only rule for moving layers are unchanged. NUMERIC and BINARY overlays are untouched.
• Cost: one extra advanceExact on one layer, only when the same document is positioned again. No benchmark was run.

What the checks validated

• Stock + test: fails through gradle with assertions on and off (expected:<1> but was:<2>); + fix: passes.
• + fix: 10 suites (the test, TestSortedNumericDocValuesUpdates, TestIncrementalDocValuesUpdates, TestMixedDocValuesUpdates, TestNumericDocValuesUpdates, TestBinaryDocValuesUpdates, TestOverlayNumericDocValues, TestOverlayBinaryDocValues, TestSortedNumericSortField, TestTopFieldCollector): 138 tests, 2 skipped, 0 failures, with assertions on and off; :lucene:core:check -x test passes.
• In the hunt: the bounded-exhaustive check finds 0 counterexamples with this fix, and the independent verifiers' and reviewers' own tests pass with it.
• The independent fact check repeated these gradle runs in its own scratch worktree with the same results.
• Not run: the full Lucene test suite, the nightly tests, any benchmark.

When target == docID and a layer wins, call layers[winner].advanceExact(target); reword the class javadoc, which says "never advanceExact" (+10/-2).

Trade-offs

Covers any future multi-valued overlay built on the merger. Adds the extra call to NUMERIC and BINARY re-reads, which do not need it, and changes a class shared by all overlay types; a committer may still prefer it as the single place that owns positioning.

What the checks validated

• + this fix instead: the same 10 suites, 138 tests, 2 skipped, 0 failures, with assertions on (not run with assertions off or through check).

Copy the winning layer's docValueCount() values into an array on every positioning and serve nextValue() from it.

Trade-offs

Independent of how layers behave, but adds a copy for every document positioned, whether it is read once or twice.

Change the javadoc instead of the code.

Trade-offs

Contradicts the LUCENE-7462 contract and leaves TopFieldCollector broken on overlays: documentation alone would not repair the collector, so a code change is still needed.

Method: semi-formal (a code-reading hypothesis witnessed by bounded-exhaustive translation validation), a hunt unit, 2026-10-25. The harness drives the real DocValuesOverlayMerger and OverlaySortedNumericDocValues through every legal move sequence (nextDoc, advance, advanceExact) over up to 3 layers and 5 documents, compares every read with an independently written union reference, and repeats with advanceExact(docID()) allowed and forbidden. Re-run on 645d4fe14a20: 38,874 layer assignments, 386,132 reachable merger states; SORTED_NUMERIC counterexamples only when the repeated advanceExact is allowed, NUMERIC 0 in both modes, 0 everywhere with the fix.

Independently, a hunt unit built an Alloy 6 model of the overlay read protocol, got a 4-step counterexample and confirmed it with a differential test on the real jar. Later units (a hunt unit, a hunt unit with the MAX-sort exception, and round-17 probes) saw it again; the adjudication collapsed all of them into this row and the no-noise gate reduced the repro to one test.