A segment that ends with child documents and no parent makes each BP reordering merge in which it comes last throw and close the IndexWriter

BPReorderingMergePolicy with BPIndexReorderer (lucene/misc) renumbers merged segments and, since 9.11.0, keeps document blocks together when IndexWriterConfig#setParentField is set. BPIndexReorderer assumes that the merged documents end with a parent and never checks it. A segment can end with documents that have no parent after them through calls IndexWriter accepts: a block rejected at a child as the last block before a flush, in an in-memory segment that also holds accepted blocks (its already-indexed documents stay as deleted documents without a parent marker), or a delete or update term that matches only the parent of the segment's last block (a merge then drops the parent). The next reordering merge in which that segment comes last throws ArrayIndexOutOfBoundsException in shuffle() (with assertions off, once the merged view has at least 64 documents; an AssertionError with assertions on), and the IndexWriter closes with a tragic exception, loses uncommitted changes and fails the same way after every reopen. Committed data stays intact and CheckIndex is clean. Opt-in configuration only; released 9.11.0 through 10.6.0 (10.6.0 by reading) and on main, introduced by #13125 (2024).

• Document block: documents added together with IndexWriter#addDocuments; the last one is the parent, the others are its children. With IndexWriterConfig#setParentField, IndexWriter marks every parent with a doc value in that field (IndexingChain.java:604, :644-650).
• BP reordering: BPReorderingMergePolicy wraps a merge policy and asks BPIndexReorderer (recursive graph bisection) for a new document order for each merged segment. Since 9.11.0 it keeps blocks together when a parent field is set (CHANGES 9.11.0, GITHUB#13125).
• Merged view: for a reordering merge, IndexWriter wraps all merging segments in one reader, deleted documents included, and hands it to the reorderer (IndexWriter.java:5545-5558); the merge drops deleted documents afterwards.

1. BPIndexReorderer.computePermutation builds parents = BitSet.of(<parent-field doc values>, maxDoc) (BPIndexReorderer.java:879-882) and reorders all maxDoc documents (:891-893). Nothing checks that document maxDoc - 1 is a parent.
2. In shuffle(), each block runs from its first document to the next parent: numChildren = parents.nextSetBit(firstChild) - firstChild (:373). For documents after the last parent, nextSetBit returns NO_MORE_DOCS (2147483647), so for the trailing run that starts at doc 100, numChildren is 2147483547.
3. The loop cumulativeBias += biases[i + j] (:376-377) then runs past the end of biases (one entry per document): ArrayIndexOutOfBoundsException: Index 103 out of bounds for length 103. Once shuffle() runs, this loop comes before any gain comparison, so it needs no qualifying term (no term in the repros reaches the default minDocFreq of 4,096). It only runs when the merged view has at least 64 documents (2 x the default minPartitionSize of 32, :243-246). With assertions on, assert i + numChildren < end in assertParentStructure (:329) fails first, for any size.
4. IndexWriter treats a failed merge as tragic: tragicEvent(t, "merge") (IndexWriter.java:5109-5113) closes the writer.

• A block rejected at a child. DocumentsWriterPerThread.updateDocuments gives each document a doc ID before indexing it (DocumentsWriterPerThread.java:291) and, on a non-aborting exception such as a term longer than IndexWriter.MAX_TERM_LENGTH (32,766 bytes), marks the block's documents so far deleted (:302-307). The parent marker is written only for the block's last document, which is never reached. If this block is the last one before a flush, the segment ends with these deleted documents. The segment must also hold accepted documents: a rejected block alone in its in-memory segment is dropped at flush as fully deleted, and the merge works (executed).
• A parent-only delete or update. A delete or updateDocuments term that matches only the parent of the segment's last block. The first merge still sees the deleted parent's doc value (deleted documents are in the merged view), so it works and drops the parent; the new segment ends with live children that have no parent after them.

The segment must come last in the merged view. When another segment follows it, that segment's first parent ends the trailing run and the merge completes (executed for both triggers: 200 and 199 documents, assertions on and off); the trailing documents are then treated as part of that segment's first block, which for live children is the search-results hazard upstream already knows.

• Who. Opt-in only: lucene/misc BPReorderingMergePolicy with BPIndexReorderer, document blocks, IndexWriterConfig#setParentField, and no index sort (an index sort turns merge-time reordering off, IndexWriter.java:5545-5546). BP reordering is not on by default.
• Trigger. A segment that ends with parentless documents must come last in a reordering merge. Executed: a forced merge of that segment alone, forceMergeDeletes, a natural LogDocMergePolicy merge with an older segment (Index 199 of 199, Index 203 of 203), and a TieredMergePolicy forceMerge(1) with a larger older segment (Index 603 of 603). Forced merges always reorder; natural merges reorder by default (minNaturalMergeNumDocs 1), and with the javadoc's suggested 2^18 small natural merges skip reordering (code reading). With assertions off the merged view needs at least 64 documents.
• The rejected-block path needs no delete call. IndexWriter rejects a block with a documented IllegalArgumentException (for example a keyword longer than 32,766 bytes in a child), stays open, and itself marks the block's already-indexed documents deleted. An application that checks term lengths before indexing never gets there; otherwise the timing decides: the block must be the last one before a flush in a segment that also holds accepted blocks. One more block in the same in-memory segment defuses it, and a rejected block alone in its segment is dropped at flush (both executed).
• Effect. Loud: the merge throws, the IndexWriter closes with a tragic exception and changes since the last commit are lost; a reopened writer fails again on its next such merge, so indexing cannot get past that merge until the segment is merged without reordering or not last. Committed documents and deletes stay unchanged, CheckIndex is clean, and the failure is fast (well under a second on about 100,000 documents: 210 ms and 80 ms in two runs).
• How likely. A judgement, not measured: rare. A randomized merge test with soft deletes hit it in 4 of 5,000 cases with assertions on; with assertions off the same test hit 0 of 5,000, because the four failing merges had 20 to 62 documents, under the 64-document threshold. Once a segment is in this state, every reordering merge in which it comes last fails (with assertions off, from 64 documents).

# Lucene main 645d4fe14a20, assertions on (-ea), seed 41700001: 1 test(s) run, 1 failed
    => java.lang.AssertionError: forceMerge(1) after a block rejected at a child threw java.lang.AssertionError
       org.apache.lucene.misc.index.TestBPReorderAfterRejectedChild.testForceMergeAfterBlockRejectedAtChild(TestBPReorderAfterRejectedChild.java:57)
     Caused by: java.lang.AssertionError
       org.apache.lucene.misc.index.BPIndexReorderer$IndexReorderingTask.assertParentStructure(BPIndexReorderer.java:329)
       org.apache.lucene.misc.index.BPIndexReorderer$IndexReorderingTask.call(BPIndexReorderer.java:241)
       org.apache.lucene.misc.index.BPIndexReorderer.computePermutation(BPIndexReorderer.java:893)
       org.apache.lucene.misc.index.BPIndexReorderer.computeDocMap(BPIndexReorderer.java:801)
       org.apache.lucene.misc.index.BPReorderingMergePolicy$1.reorder(BPReorderingMergePolicy.java:138)
       [...]

• Contracts. BPReorderingMergePolicy: "When reordering doesn't have enough RAM, it simply skips reordering in order not to fail the merge" (BPReorderingMergePolicy.java:35-36). CHANGES 9.11.0: BP "is now supported on indexes that have blocks, as long as they configure a parent field via IndexWriterConfig#setParentField". IndexWriter#addDocument: a term longer than MAX_TERM_LENGTH throws IllegalArgumentException (IndexWriter.java:1480-1481), and after an exception "the index will be consistent, but this document may not have been added" (:1465-1466). IndexWriter#addDocuments limits the effect of deleted block documents to search features: "when these documents are deleted these search features will not work as expected" (:1501-1503). Neither the block docs nor the BP policy docs warn that this reachable state can make a merge fail and close the writer (IndexWriter.merge handles any merge failure as tragic, :5109-5113). The low-RAM promise shows a robustness intent; no general contract says reordering never fails a merge.
• Behaviour. IndexWriter accepts the rejected block, the delete and the update; core CheckIndex calls the index clean; the same merge without reordering works; deleting the whole block works.
• Tests. TestBPIndexReorderer.testSingleTermWithBlocks indexes whole blocks and deletes nothing; TestBPReorderingMergePolicy deletes documents but indexes no blocks. No upstream test combines BP reordering, a parent field and deletes or rejected blocks.
• History. The BP block PRs (#13125, #13128) never discuss deleted parents or segments that end in children; #13128 made IndexWriter reorder only "when it has a chance to preserve the block structure".

An independent reviewer from another model family (OpenAI GPT-5.6, reading only, could not run Java) built the strongest case for "not a bug": the input is outside the supported block structure. CheckJoinIndex (lucene/join) says "The last document of a segment must always be a parent"; committers have long said that deleting a parent without its children breaks blocks (LUCENE-4068, LUCENE-6660, LUCENE-7674, the #12829 review), and on #14067: "Block-joins require deletes to be consistent across parent and child documents. So I wouldn't call it a bug"; assertParentStructure states the precondition ("Last doc ID must be a parent doc"); the policy promises to skip only when RAM is short; and IndexWriter#addDocuments is marked @lucene.experimental.

Why it fails: on the rejected-block path the application issues no delete call; IndexWriter itself marks the block's already-indexed documents deleted after a documented, non-aborting rejection and leaves the segment ending in them. The application could avoid that only by checking term lengths before indexing, or by the timing of the flush, which it does not normally control. CheckJoinIndex rejects that segment too (executed: "The last document of a segment must always be a parent"), so its invariant is not one IndexWriter maintains; it also rejects a live parent with a deleted child (executed), which addDocuments explicitly supports ("The order of documents within a segment will be preserved, even when child documents within a block are deleted"). Every upstream statement limits the consequence to block-join search results; none says a merge may throw, and @lucene.experimental marks API stability, not a licence for a merge to throw. Lucene asserts check programming errors, not input, and with assertions off the code reads out of bounds. The adjudication (medium confidence), the independent reproducer and the devil's-advocate verifier (moderate-high) rated it a defect; a second cross-model reviewer rated the intended-behaviour case strong for the parent-only path and moderate for the rejected-block path. Verdict: a defect, strongest on the rejected-block path. The parent-only path is much weaker: maintainers can fairly treat CheckJoinIndex's last-parent invariant and the "delete whole blocks" guidance as a precondition of block-aware tooling.

Two fixes were run through gradle in a scratch worktree at a9779ef3c193 (seed DEADBEEF), a third through the repro harness. To compare them, a probe uses a reorderer that really moves blocks (setMinDocFreq(2), setMinPartitionSize(2), 42 blocks), ends the segment with the 3 parentless children of block 41, runs a BP merge and checks: no failure, every block intact, the parentless documents at the end, the rest still reordered. Stock fails it.

Documents after the last parent belong to no block: leave them at the end in their current order and reorder the blocks before them. Patch: optionC-reorder-up-to-last-parent.diff, +5/-1.

BitSet parents = null;
int numDocsToReorder = maxDoc;
String parentField = reader.getFieldInfos().getParentField();
if (parentField != null) {
  parents = BitSet.of(DocValues.getNumeric(reader, parentField), maxDoc);
  // Documents after the last parent (e.g. children whose parent was deleted) belong to no
  // block: leave them at the end, in their current order, and reorder the blocks before.
  numDocsToReorder = maxDoc == 0 ? 0 : parents.prevSetBit(maxDoc - 1) + 1;
}
...
IntsRef docs = new IntsRef(sortedDocs, 0, numDocsToReorder); // was: sortedDocs.length

Trade-offs

• After a parent-only delete the merged segment still ends with those children (as a plain merge leaves it); it no longer breaks later merges.
• "Every block intact" and "the rest still reordered" are shown by one 42-block probe only; deleted children inside blocks, soft deletes, mixed readers, addIndexes and other parent-field layouts were not tested.
• No change for segments that end with a parent. No compression or query-speed benchmark, CHANGES entry, javadoc build or full check was run.

What the checks validated

• The compact repro passes 3 of 3 with assertions on and off.
• The probe passes: the 3 parentless documents stay last, every block is intact, and the block order changed (25 5 24 4 34 ...).
• TestBPIndexReorderer (8 tests), TestBPReorderingMergePolicy (3, its nightly tests included) and TestBpVectorReorderer (8) pass; run together with the compact repro (3) and the probe (1): 5 classes, 23 tests, 0 failures, 0 skipped. Assertions off (the repro, the probe and TestBPReorderingMergePolicy): 7 tests, 0 failures. :lucene:misc:checkGoogleJavaFormat passes with the patch and the compact test.
• Through the repro harness the finder's, the independent reproducer's, the devil's-advocate verifier's and the seven-test rejected-block repro all pass, with assertions on and off.

After building parents, if the last document is not a parent, delete the temporary files and return the current order. Patch: optionA-skip-reordering-finder.diff, +6.

Trade-offs

• Simplest, but the whole merge loses reordering whenever the last document is not a parent; the identity DocMap still costs the reordering overhead of the merge and marks the segment bp.reordered=true; the postings and forward-index work is done before the check (it could move earlier).

What the checks validated

• The compact repro passes 3 of 3 (assertions on; off through the harness) and the three upstream classes pass; the probe fails only its last check, "the blocks before the orphans should still be reordered" (block order stays 0 1 2 ... 40). Earlier the finder's run passed 11 of 11 upstream BP tests with nightly tests on.

parents.set(maxDoc - 1) when it is not set, so the trailing run is one more block (the independent reproducer's shadow fix).

Trade-offs

• Silently changes block membership, which block-join queries see.

What the checks validated

• The repros pass, but the probe fails: BP moves the pseudo-block into the middle of the segment, and after the merge a parentless child of block 41 sits inside block 3 ("doc 89 is in the block of parent doc 93 expected:<3> but was:<41>").

An idea from the #12829 review: make a parent delete also delete its children.

Trade-offs

• Would prevent new parent-only cases, but not the rejected-block path or segments that already end in parentless documents; not a fix on its own.

Method: randomized merge-level differential testing (the hunt's non-formal tier; the finder tagged it semi-formal), in a hunt unit on misc reordering and index splitting.

• Two IndexWriters received the same random sequence of adds, block adds, deletes and merges; one merged through a no-op reorderer, the other through the real BPIndexReorderer. With soft deletes, 4 of 5,000 cases (assertions on) failed in assertParentStructure after a soft-deleted parent.
• Reading BPIndexReorderer's block handling showed the missing last-document check; a deterministic two-session JUnit reproduced it with assertions on and off, on main and on 9.11.0, 9.12.3 and 10.5.2 (9.10.0 passes).
• An independent reproducer and a devil's-advocate verifier found single-writer variants (forceMergeDeletes after a parent-only delete; updateDocuments by a term only the parent carries). A later reach check, run after the adjudication, found the path with no delete: a block rejected at a child as the last block before a commit.
• Found 2026-10-26 on main ea57360912ed; re-checked on a9779ef3c193.