With index sorting and a parent field, deleting only a block's parent makes every later merge fail

With an index sort and IndexWriterConfig#setParentField, a merge compares each document by the sort value of the next parent at or after it (parents.nextSetBit(docID)). If an application deletes only the parent of a block, with deleteDocuments or with updateDocuments by a term that only the parent carries, the next merge sorts the live child by its deleted parent's value and drops the parent. When that value sorts last, the merged segment ends with a child that has no parent after it. From then on every later sorted merge that includes the segment gets NO_MORE_DOCS from nextSetBit, uses it as a doc id and reads past the end of the sort field's doc values; IndexWriter treats the exception as tragic, closes and loses uncommitted documents. A new writer with the same index sort fails the same way, natural merges fail too, SortingCodecReader.wrap hits the same lookup, and CheckIndex reports the index clean. Every release from 9.10.0 (#12829) to 10.5.2, 10.6.0 (by reading) and main; four documents suffice.

• Document block: documents added together with IndexWriter.addDocuments (or updateDocuments), parent last.
• Parent field (IndexWriterConfig#setParentField, 9.10+; required for an index created with 10.0 or later that uses index sorting with blocks, DocumentsWriterPerThread.java:272-280): IndexWriter marks the last document of each block, and every single document, as a parent, "In order to maintain the API guarantee that the document order of a block is not altered by the IndexWriter" (IndexWriterConfig.java:579-590).
• Sorted merge: a merge of index-sorted segments is a k-way merge (MultiSorter.sort). With blocks, each document is compared by the sort value of its block's parent, found with parents.nextSetBit(docID).

1. MultiSorter.sort builds the parent bitset from the parent doc values over all documents, live or deleted (MultiSorter.java:52-64), and visits every document in the initial pass (:109) and the merge loop (:131); only the final doc maps drop deleted documents (:141-153).
2. Merge 1 creates the orphan. c1 is compared by nextSetBit(0) = 1, its deleted parent p1 (value 10), so x (5) goes first and p1 is dropped: the merged segment is [x(P), c1]. It keeps hasBlocks=true (IndexWriter.java:5313-5319).
3. Merge 2 uses the sentinel as a doc id. final int effectiveDocID = parents == null ? docID : parents.nextSetBit(docID); (MultiSorter.java:166) is passed to setTopValue (:168). For c1 there is no set bit at or after it, so nextSetBit returns NO_MORE_DOCS = 2147483647, as its javadoc says (BitSet.java:89-93).
4. The LONG sorter calls values.advanceExact(docID) and values.longValue() (IndexSorter.java:296-298), although advanceExact needs "a valid doc ID, ie. >= 0 and < maxDoc" (DocValuesIterator.java:25-28). The 1-bit-per-value reader reads byte 2147483647 >>> 3 = 268435455: EOFException: read past EOF (pos=268435455), wrapped in a RuntimeException.
5. handleMergeException ignores only an internal MergePolicy.MergeAbortedException (IndexWriter.java:5043-5053) and rethrows the rest; this RuntimeException reaches tragicEvent(t, "merge") (:5109-5113), which rolls back and closes the writer (:6098-6104): uncommitted changes are gone.
6. The committed segment still ends with c1, so every later sorted merge that includes it, in this writer or a new one with the same index sort, repeats steps 3-5. Exceptions: a segment whose sort field is stored as a constant (a one-document orphan segment) merges fine, and a writer without the index sort merges the index but gives up the index sort for good (see Recovery under Who is affected).

Sorter.sort(LeafReader), used by SortingCodecReader.wrap, has the same lookup (Sorter.java:191-199): ArrayIndexOutOfBoundsException: Index 2147483647 out of bounds for length 2.

The diagram probe runs this sequence with the repro's configuration and prints every committed segment; the JUnit asserts only the outcome and stops at the throw. The probe's committed index after the failure holds x, c1 and y (numDocs=3), and the study matrix logs the uncommitted document as lost.

The exception type depends on the setup: RuntimeException(EOFException) with the default codec on a file-system directory, IndexOutOfBoundsException on ByteBuffersDirectory, EOFException for a BinarySortField, AssertionError with the test framework's Asserting codec. LONG, INT, DOUBLE, STRING and binary sort fields all fail.

When the orphan does not end the merged segment, nothing throws: it silently joins the following block ([y(P) c1 x(P)]). That is the search-semantics hazard already discussed upstream, not this crash.

• Who is exposed. Applications that use index sorting, a parent field and document blocks, and delete or update a block by a term or query that matches the parent but not every child, for example an id stored only on the parent. The parent field is optional in 9.10-9.12 and required for an index created with 10.0 or later that uses index sorting with blocks (the check is indexMajorVersionCreated >= 10), so every such index has it; an index created before 10.0 may keep sorting blocks without one, and then MultiSorter does not reach this lookup. softUpdateDocument on the parent triggers it too.
• Downstream (read, not run). Elasticsearch (#105738, implemented by #110251, 2024) and OpenSearch (#18536, 2025) set the Lucene parent field for index sorting with nested fields. Whether their own delete and update paths can produce a parent-only delete was not checked; neither tracker has a report of this crash.
• Default or opt-in. Index sorting, the parent field and blocks are opt-in; the codec and the directory are the defaults. The repro also sets LogDocMergePolicy (merge factor 1000) and SerialMergeScheduler, so it merges only on forceMerge and in the test thread, and the natural-merge test uses LogDocMergePolicy(mergeFactor=2). With the default TieredMergePolicy and ConcurrentMergeScheduler the same steps fail the same way and the writer closes from the merge thread, so isOpen() can stay true for a moment after forceMerge throws.
• Scale. None: four documents (c1, p1, x, y). Deterministic.
• What it takes. The merge must place the orphan (or orphans) at the end of the merged segment's live documents, with no parent after them. With one ascending sort field, as here, the deleted parent's value sorts after every other live document's key; in general it depends on the whole sort (fields, direction, missing values, ties, the merge's tie-breaks) and on which documents are deleted. Otherwise the orphan is silently re-parented and nothing throws. A segment holding a single orphan and nothing else does not crash, by luck: its sort field is stored as a constant.
• What you see. Loud: an unchecked exception from a merge, a closed writer, uncommitted documents lost; with ConcurrentMergeScheduler the background merge fails and the next addDocument throws AlreadyClosedException. Then the same in every new writer with the same index sort. addIndexes(CodecReader) of the index into another sorted writer fails too. Reads keep working and CheckIndex (default codec) reports no problem, which makes it hard to diagnose.
• Recovery. The study found one: delete every remaining document of the affected segment, so it is dropped without a merge. A writer opened with the same parent field but no index sort also merges the index, but the merged segment has no index sort, and from then on a writer with the index sort cannot open the index (cannot change previous indexSort=null).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected the second forceMerge(1) to succeed, got java.lang.IndexOutOfBoundsException
       org.apache.lucene.index.TestIndexSortDeletedParentMerge.testMergeAfterDeletingBlockParent(TestIndexSortDeletedParentMerge.java:59)
     Caused by: java.lang.IndexOutOfBoundsException
       java.base/java.nio.Buffer$1.apply(Buffer.java:756)
       java.base/java.nio.Buffer$1.apply(Buffer.java:753)
       java.base/jdk.internal.util.Preconditions$4.apply(Preconditions.java:213)
       java.base/jdk.internal.util.Preconditions$4.apply(Preconditions.java:210)
       java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:98)
       [...]

• The contracts. IndexWriterConfig#setParentField: the parent marker exists "to maintain the API guarantee that the document order of a block is not altered by the IndexWriter" (IndexWriterConfig.java:579-590). MIGRATE.md:875-880 and CHANGES for #12829 (CHANGES.txt:2945-2949): "Document blocks are maintained alongside their parent documents during sort and merge."
• The warning is about search. IndexWriter#addDocuments (IndexWriter.java:1499-1504): "Today this is fine, because merging will preserve a block. The order of documents within a segment will be preserved, even when child documents within a block are deleted. Most search features (like result grouping and block joining) require you to mark documents; when these documents are deleted these search features will not work as expected." Nothing says IndexWriter's own merges can fail.
• The API accepts the trigger. deleteDocuments(Term...) (IndexWriter.java:1855-1864) and updateDocuments(Term, Iterable) (:1593-1605) accept any term; nothing rejects or cascades a parent-only delete.
• Internal contracts. nextSetBit documents NO_MORE_DOCS (BitSet.java:89-93); advanceExact requires a doc id below maxDoc (DocValuesIterator.java:25-28). MultiSorter passes one to the other unchecked.
• forceMerge (IndexWriter.java:2213-2214): "If an Exception is hit, for example due to disk full, the index will not be corrupted and no documents will be lost." Disk full is only an example; the promise is general. Here the failed merge closes the writer and loses the uncommitted documents, and it fails again on every retry.
• Tests. No upstream test deletes only a parent under index sort: TestIndexSorting.testIndexSortWithBlocks (:3287) deletes nothing, and testMixRandomDocumentsWithBlocks (:3370) deletes by an id (:3383) that every document of the block carries, so it always deletes whole blocks.
• Controls. The same delete without an index sort merges fine (the orphan joins the next block), and the same scenario on 9.9.2, before the parent field, passes.
• History. In #12711 s1monw asked "would we also delete all children?"; in the #12829 review they noted that a parent-only delete makes adjacent blocks "merge ... magically or erroneous together" and floated cascading deletes. No follow-up, and neither thread mentions a merge exception or a closed writer.

The strongest case for "intended": deletes that break a block are caller misuse. mikemccand in LUCENE-4068 (2012): "you cannot delete the parent w/o deleting all of its children"; jpountz in #14067 (2024): "Block-joins require deletes to be consistent across parent and child documents. So I wouldn't call it a bug"; rmuir in LUCENE-6512: "this is a solr bug". addDocuments and updateDocuments are @lucene.experimental, and MultiSorter assumes every child has a parent after it. An independent reviewer from another model family (OpenAI GPT-5.6, reading only) rated this argument "moderate".

Why it fails: those statements are about block semantics and block-join search. mikemccand's LUCENE-4068 remark was made while wording the addDocuments javadoc, and the javadoc that came out of it names only search-time consequences ("these search features will not work as expected"). Here IndexWriter itself breaks: it accepts the delete, its own merge puts the orphan last and drops the parent, and from then on it cannot merge a segment it wrote. The result is an unchecked read past the end of doc values, a tragic close that drops unrelated uncommitted documents, and the same on every restart, while CheckIndex calls the index clean. Without an index sort the same delete merges fine. Even under the misuse reading the outcome should be a rejected delete or a clean error, not a writer that can never merge again. "Index files are trusted" (SECURITY.md lines 30-34) does not apply: Lucene wrote this index through public API calls. SortingCodecReader is the weaker case: it is @lucene.experimental, the caller wraps a reader explicitly, here one whose block layout is already broken, and its exception closes no writer and loses no documents. Verdict: not intended, a defect.

One fix was built and validated in a throwaway clone at ea57360912ed, at the merge and SortingCodecReader lookups (parent-or-self.diff). The other options come from the study and the review and were not run.

A package-private helper in Sorter replaces the unchecked lookups: MultiSorter.setComparableValues (merge, MultiSorter.java:166) and the comparator wrapper of Sorter.sort(LeafReader) (SortingCodecReader, Sorter.java:198). +12/-1 lines in Sorter.java, +1/-1 in MultiSorter.java.

// Sorter.java
static int parentOrSelf(BitSet parents, int docID) {
  final int parent = parents.nextSetBit(docID);
  return parent == DocIdSetIterator.NO_MORE_DOCS ? docID : parent;
}
    in.compare(parentOrSelf(parents, docID1), parentOrSelf(parents, docID2));

// MultiSorter.java:166
final int effectiveDocID = parents == null ? docID : Sorter.parentOrSelf(parents, docID);

Trade-offs

• A crash stop, not a semantics fix. The orphan sorts by its own value. A probe with the fix and one more document, big (99), gives [x(P) y(P) c1 big(P)] after the second merge: c1 now belongs to big's block, the hazard upstream already knew; slow CheckIndex is clean.
• Several trailing orphans each sort by their own value, so a later merge can place other documents between them. A variant could key every trailing orphan by the segment's last document to keep them together (not run).
• Both sites. With only the MultiSorter guard, the SortingCodecReader test still fails.
• Cost. One comparison per document visit in a sorted merge; no benchmark was run.

What the checks validated

• Stock: this test 3 of 4 and the candidate test 4 of 5 fail through gradle, assertions on and off.
• Fix: both pass (9 of 9). With TestIndexSorting (62), TestSortingCodecReader (3) and TestBinarySortField (25): 99 tests, 0 failures, assertions off (the flag is in the run command; a passing gradle log does not print it). With every test matching org.apache.lucene.index.*Sort*, TestAddIndexes and TestIndexWriterMerging: 26 classes, 200 tests, 0 failures, 2 skipped (the Test2B* monster tests), assertions on.
• :lucene:core:tidy leaves the fix and the test unchanged; :lucene:core:check -x test passes (google-java-format, ecjLint, forbiddenApis).
• Standalone harness with the fix shadowed in: 4 of 4 pass, assertions on and off. On 9.10.0 a one-line guard of the same kind turns the candidate test from 4 of 5 failing to 5 of 5 passing.

When a parent field is configured, a delete that matches a parent also deletes the documents of its block, as s1monw floated in the #12829 review. Not built.

Trade-offs

Fixes the crash and the re-parenting, but changes what deleteDocuments and updateDocuments delete, which needs agreement upstream; the delete path must find each deleted parent's children.

A merge treats a live child whose parent is deleted as deleted. Not built.

Trade-offs

No orphans, no crash, but it silently removes documents the application did not delete.

CheckIndex could report a segment with blocks and a parent field whose last document is not a parent (the study's suggestion). Not built.

Trade-offs

Reports the damage instead of preventing it; today CheckIndex calls such an index clean.

Method: model-based random testing (the 2026-10-22 study's non-formal baseline), not a formal-methods find.

• The harness drove IndexWriter and NRT readers with random operation sequences (adds, blocks, deletes, updates, commits, merges, reopens, optional index sort), compared every reader against an executable reference model, treated any unexpected exception as a failure, and shrank failing sequences automatically.
• This root cause first appeared 15.8 s into the first smoke run (17.8 s and 3.1 s into the two seeded base runs).
• A separate verifier read only the operation sequence, wrote its own minimal test and a 14-test matrix with different values, ran them with 5 seeds, assertions on and off, and on the 9.12.3, 10.1.0, 10.3.1 and 10.5.2 jars, and classed it as a new bug. More verifiers whose P, Dafny and OpenJML models were extended toward this scenario (hinted, not blind) agreed. TLA+ and Alloy models of the study could not express it.
• 2026-10-26: re-verified on main ea57360912ed, a release sweep of every 9.x and 10.x release, a cross-model refute review (an independent reviewer from another model family, OpenAI GPT-5.6, reading only: real, high), a prior-report search, and this doc's test and gradle-validated fix.