Merges through BPReorderingMergePolicy with BpVectorReorderer break document blocks even when a parent field is set

IndexWriter lets a merge renumber documents on an index with document blocks only when a parent field identifies the blocks, because then the reorder can keep each block together; it applies whatever doc map the merge policy returns without checking it. BPReorderingMergePolicy with BpVectorReorderer returns a map that moves every document on its own: the vector bisection never reads the parent field, and documents without a vector are moved after all documents that have one. So a reordered merge silently scrambles the merged segment's blocks: with vectors on the children only or on the parents only, at default settings and at any scale (4 blocks suffice); with vectors on every document, only merges with at least 64 vectors (twice the default minPartitionSize), where the bisection runs, can break them (66 documents: 23 children wrong). Block joins then return another block's parent or none, nested kNN returns fewer hits, and deletes that locate children through a block join miss them; CheckIndex passes, and only reindexing the affected blocks reliably repairs it. The defect came with #14097 (2025-01-07) and exists only on main, so a fix before 11.0.0 keeps it out of every release.

• Document block: documents added together with IndexWriter#addDocuments, children first, parent last. Block joins (ToParentBlockJoinQuery, DiversifyingChildrenFloatKnnVectorQuery, ...) find a child's parent as the first parent document after it, so the order inside a segment is the only link between them.
• Parent field (IndexWriterConfig#setParentField): IndexWriter marks every parent with it. Its javadoc: "In order to maintain the API guarantee that the document order of a block is not altered by the IndexWriter a marker for parent documents is required."
• Merge-time reordering: a merge policy can return a doc map from OneMerge#reorder, and IndexWriter writes the merged segment in that order. BPReorderingMergePolicy does this with an IndexReorderer: BPIndexReorderer (by postings) or BpVectorReorderer (by vector similarity, recursive graph bisection).

1. IndexWriter.mergeMiddle skips the reorder only if an index sort is set, or if some merging segment has blocks while some merging segment (not necessarily the same one) has no parent field (IndexWriter.java:5544-5555, added by #13128 "Make OneMerge#reorder preserve blocks"). Otherwise it calls merge.reorder(...) (:5558) and applies the map with SortingCodecReader.wrap(mergedView, docMap, null) (:5576). Nothing checks the map against the blocks.
2. BPReorderingMergePolicy forwards the call to reorderer.computeDocMap(...) (BPReorderingMergePolicy.java:133-145).
3. BpVectorReorderer.computeDocMap (BpVectorReorderer.java:578-593) permutes the vector ordinals and never reads the parent field; the file contains neither "parent" nor "block". The bisection splits a range only when each half would hold at least minPartitionSize vectors (default 32, :208-211); when it runs it may move any vector document anywhere in the range, so blocks can interleave, depending on the vectors.
4. valueMapToDocMap (:735-789, "sort docs with no value at the end") gives every document without a vector a new ID after all documents with one. When only the children (or only the parents) carry the vector, all parents end up after all children (or before them), whatever the vector values and even when the bisection does not run. When every document has a vector, nothing is moved to the end, and below 64 vectors (default settings) the bisection does not run either: the map is the identity (:737-738) and the blocks survive.
5. The sibling BPIndexReorderer reads the parent field and moves whole blocks (BPIndexReorderer.java:376-382, :450-455, :878-882, #13125). BpVectorReorderer came later (#14097) without that.

4 blocks [bNc0, bNc1, bNp], 2-dimensional vectors, two segments, forceMerge(1), default reorderer settings, vectors on the children or on the parents, main ea57360912ed, assertions on and off:

On the first index, ToParentBlockJoinQuery returns b0p for every child and DiversifyingChildrenFloatKnnVectorQuery with k=3 returns 1 hit (b2c0); with the fix, every child gets its own parent and the kNN query returns 3 hits. CheckIndex passes on the scrambled index.

• 30 blocks of 1-3 children (minPartitionSize 2, three segments): ToParentBlockJoinQuery wrong for 59 of 60 children with child-only vectors and 56 of 60 with vectors on every document.
• 16 blocks, default settings, child-only vectors: 15 of 16 tested children joined to b0p; diversified kNN with k=3 returned 1 hit.
• A variant with minPartitionSize 2 broke 64 of 64 blocks with vectors on children only, on parents only and on every document.
• Vectors on every document, default settings (fact check): 4, 16 and 21 blocks (up to 63 documents) keep every child with its parent; 22 blocks (66 documents) give 23 children the wrong parent, 32 blocks (96 documents) 24.

• Who is exposed. Applications that combine BPReorderingMergePolicy with a BpVectorReorderer (lucene/misc, expert), document blocks with IndexWriterConfig#setParentField, and no index sort (with an index sort IndexWriter never reorders). The natural user is a nested-vector index: parents with child "chunk" documents that carry embeddings, searched with DiversifyingChildrenFloatKnnVectorQuery and ToParentBlockJoinQuery. That is the layout that breaks deterministically; the join module's own test notes "only child documents are allowed to have a vector!" for its nested kNN queries.
• Default or opt-in. Opt-in. Inside that setup, with vectors on the children or on the parents, nothing else is needed: default reorderer settings, no explicit codec (the runs drew randomized test codecs), assertions on or off.
• Scale. With vectors on the children or on the parents: none, 4 blocks (12 documents) in 2 segments, and the result is deterministic. With vectors on every document and default settings, the merge must hold at least 64 vectors (66 documents broke, 63 did not), and where each child lands depends on the vectors (56 of 60 children wrong in a 30-block run with minPartitionSize 2).
• Frequency. Whenever the policy applies a doc map to a segment with blocks. Forced merges were executed; by code reading the policy also reorders natural, full-flush and forced-deletes merges that reach minNaturalMergeNumDocs and the biggest-segment ratio (defaults 1 and 0, so every such merge; the javadoc suggests 262,144 documents for natural merges). No map is applied when the reorderer exceeds its RAM budget, when the merge has no float vector field of that name, or when the IndexWriter gate refuses. addIndexes(CodecReader...) passes the same IndexWriter gate but was not executed.
• What you see. Nothing at write time: no exception, CheckIndex passes (its only parent-aware order check sits in the index-sort test, and reordering never happens with an index sort). At query time block joins return another block's parent or none, nested kNN returns fewer hits, and a delete that finds a root's children through a block join leaves them live. The scramble is persisted; by code reading later merges do not undo it, and reindexing the affected blocks repairs it; documents deleted before the merge stay deleted.
• Versions. Main only, since #14097 (2025-01-07); CHANGES.txt lists it under 11.0.0. Fixing it before 11.0.0 keeps it out of every release.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected blocks [cN, pN] kept together after the merge, got [c0, c1, p0, p1]
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.assertTrue(Assert.java:42)
       org.apache.lucene.misc.index.TestBpVectorMergeKeepsBlocks.testForceMergeKeepsBlocks(TestBpVectorMergeKeepsBlocks.java:63)

• The contracts. IndexWriterConfig#setParentField (IndexWriterConfig.java:580-588): the parent marker is required "to maintain the API guarantee that the document order of a block is not altered by the IndexWriter". IndexWriter#addDocuments (IndexWriter.java:1499-1500): "the index does not currently record which documents were added as a block. Today this is fine, because merging will preserve a block." Here IndexWriter itself runs the reorder, inside a merge it schedules.
• The gate. #13128 ("Make OneMerge#reorder preserve blocks", 2024-03-29) changed IndexWriter "to only call OneMerge#reorder when it has a chance to preserve the block structure, ie. either there are no blocks or blocks are identified by a parent field", and made the test framework's MockRandomMergePolicy reverse whole blocks when a parent field is set (MockRandomMergePolicy.java:268-300).
• The sibling and CHANGES. 9.11.0 CHANGES (lucene/CHANGES.txt:2742-2743): "GITHUB#13125: Recursive graph bisection is now supported on indexes that have blocks, as long as they configure a parent field". BpVectorReorderer's javadoc calls it an "Implementation of recursive graph bisection ... See BPIndexReorderer". TestBPIndexReorderer.testSingleTermWithBlocks asserts complete, parent-last blocks. That entry concerns BPIndexReorderer, the only reorderer at the time, so it shows the design intent rather than a rule for every later reorderer; the setParentField sentence and the #13128 gate are the direct evidence.
• Intent of #14097. Its PR body: "refactored to make BpVectorReorderer compatible with BPIndexReorderer so that either can plug into BPReorderingMergePolicy". None of its 33 texts (body, reviews, comments) mentions parent, child, nested, join, setParentField or hasBlocks; the 3 hits for "block" are "should not block merging". Upstream's TestBPReorderingMergePolicy picks BpVectorReorderer at random but never uses blocks or a parent field.
• History repeats. On 9.10.0 the same policy with the postings reorderer broke blocks the same way ("child b4c1 ended up in the block of parent b10p"); 9.11.0 fixed that with #13125 and #13128 (executed). #14097 let a second reorderer into the gated path without the same handling.

The strongest case for "intended" (an OpenAI GPT-5.6 reviewer with an "intended" lens, and the devil's-advocate verifier): neither the OneMerge#reorder javadoc (@lucene.experimental) nor the IndexReorderer interface (no such tag, like BpVectorReorderer and BPReorderingMergePolicy) says a reorderer must keep blocks; the setParentField javadoc calls the field "optional for all indices that don't use document blocks in combination with index sorting", and MIGRATE says it must be configured "only if index sorting is used together with documents blocks"; addDocuments warns that "in the future Lucene may merge more aggressively re-order documents ... in which case you may need to fully re-index" and that offline re-sorting tools "will likely break them up. Use such tools at your own risk!"; the BPReorderingMergePolicy javadoc still names only BPIndexReorderer; and moving documents without a vector to the end is deliberate and tested (TestBpVectorReorderer.testIndexReorderSparse).

Why it fails: the block duty is stated at the IndexWriter level, and the #13128 gate exists only so that a reorder runs when blocks can be kept; a reorderer that ignores the parent field defeats it. The "future" sentence and the offline-tool NOTE come from LUCENE-3112 (2011, the commit that added addDocuments), long before the parent field (2024). The NOTE is about offline tools; the "future" sentence does foresee merges that reorder documents for compression, which is what this policy does, so the javadoc pulls two ways. What settles it: #13128 later made merge-time reordering conditional on the parent field precisely so that blocks are kept. The "optional ... with index sorting" sentence and the MIGRATE note came with #12829 (2024-01-11), before #13128 (2024-03-29) made the same field the condition for reordering an index with blocks at all. (The NOTE does cover BpVectorReorderer's offline reorderIndexDirectory tool.) The policy javadoc is stale, not a restriction: #14097 plugged the vector reorderer into this policy on purpose. Sparse ordering is fine without blocks; with blocks it is exactly what separates parents from children. @lucene.experimental marks an unstable API, not permission to return wrong block-join results. The "intended" lens rated the case moderate in its record and "weak" in its notes; the refute lens, the independent reproducer, the devil's advocate and the adjudication rejected it.

One fix was built and validated in a scratch worktree at ea57360912ed (removed afterwards); the other options come from the adjudication, the verifiers and this doc and were not run.

In BpVectorReorderer.computeDocMap, return null (no reordering) when reader.getMetaData().hasBlocks(), and say so in the class javadoc. +8 lines in BpVectorReorderer.java, no API change.

if (vectorScore == null) {
  return null;
}
if (reader.getMetaData().hasBlocks()) {
  // This reorderer moves documents one by one, which would break document blocks (children
  // followed by their parent), so leave segments that have blocks in their current order.
  return null;
}

Trade-offs

• Feature loss. Vector reordering is switched off for every segment with blocks, which is the nested-vector layout most likely to want it; those segments keep their merge order, and bp.reordered says false.
• Offline tool. For indexes without a parent field, reorderIndexDirectory then copies segments with blocks unchanged (SortingCodecReader.wrap accepts a null map) instead of scrambling them (executed). On an index with a parent field the tool already fails before reordering, with and without the fix (IllegalArgumentException: its writer has no parent field), and the run left an empty commit: a possible separate defect, not triaged and not part of this report.
• Blind spot it inherits. It relies on LeafMetaData#hasBlocks, which segments written before 9.9 do not record. Those indexes cannot have a parent field; that case is a separate bug in the IndexWriter gate (LFV-429) and is not fixed here.

What the checks validated

• Stock: the test fails 2 of 2 through gradle, assertions on and off.
• With the patch: the test passes 2 of 2, assertions on and off; TestBpVectorReorderer, TestBPReorderingMergePolicy and TestBPIndexReorderer: 19 tests, 0 failures, 2 skipped (@Nightly); the first two with -Ptests.iters=20 (20 draws of the policy test's randomized reorderer choice; the log does not record which reorderer each drew): 220 tests, 0 failures, 40 skipped. The policy test's only reorder-on-merge tests are @Nightly; with -Ptests.nightly=true -Ptests.iters=5 the three suites give 95 tests, 0 skipped, 0 failures (fact check).
• :lucene:misc:test: 24 classes, 317 tests, 0 failures, 9 skipped, with assertions on and off; :lucene:misc:check -x test passes.
• Standalone harness with the patched class: the block-join variant (0 of 8 wrong, 3 kNN hits; with this doc's fix/src in the fact check, and with the finder's code-identical sketch earlier), the devil's advocate's layout variants (4/4) and block-join symptom test (1/1), and the security probe (7/7) pass. The independent reproducer's test fails 2 of 4 only on its own precondition that the merge was reordered (expected:<[tru]e> but was:<[fals]e>), as expected for a fix that skips reordering.
• Not executed with the patch: addIndexes(CodecReader...). By code reading it is covered too: the merged view ORs hasBlocks over its inputs (SlowCompositeCodecReaderWrapper.java:78-94) and addIndexesReaderMerge skips a null map (IndexWriter.java:3561-3565).

Partition whole blocks instead of documents, as BPIndexReorderer does: give all vectors of a block the block's bias (or use one representative per block, such as the centroid of its vectors), sort with blocks as units, and keep documents without a vector inside their block.

Trade-offs

Keeps vector reordering for nested indexes, but it is real work: both the bisection and the "no value at the end" step must change, blocks without any vector need a rule, and ordering quality would need a benchmark.

In IndexWriter.mergeMiddle and addIndexesReaderMerge, when a parent field is set and the merged view has blocks, verify the returned map against the live documents: every live child must keep the same first live parent after it, and the live documents of a block must stay together and in order; otherwise ignore the map or throw. It also needs a rule for trailing children without a parent, which can occur (LFV-417). The simple predicate "for each non-parent document d, oldToNew(d) + 1 == oldToNew(d + 1)" is enough only for complete blocks without deletions: moving a deleted child breaks it without harm, a block whose parent is deleted can pass it and still leave its live children orphaned, and a trailing child has no d + 1.

Trade-offs

Protects every OneMerge#reorder implementation, custom ones too, for O(maxDoc) per reordered merge. Ignoring the map hides a reorderer's bug; throwing fails the merge. A core change, so it needs core review; combine it with A or B rather than replacing them.

State in the BpVectorReorderer and BPReorderingMergePolicy javadoc that indexes with blocks are not supported.

Trade-offs

Leaves IndexWriter breaking its own setParentField guarantee without any error. Either way, the BPReorderingMergePolicy javadoc should stop naming only BPIndexReorderer.

Method: code reading (the hunt's non-formal tier).

• A hunt unit (index sorting, 2026-10-25) was building an Alloy model of the doc maps that index sorting builds with document blocks. Reading every place where IndexWriter applies a doc map, the finder saw that mergeMiddle applies SortingCodecReader.wrap(mergedView, docMap, null) with no block check, and that BpVectorReorderer never reads the parent field. A JUnit on the stock jar confirmed it. The Alloy model has no reorderer and gave no signal for this bug.
• Before the candidate was written, an independent reviewer from another model family (OpenAI GPT-5.6, refute lens) reproduced it with its own 48-block test. Then an independent reproducer, a second GPT-5.6 reviewer with an "intended" lens, a devil's advocate and an adjudication confirmed it, and later stages bisected the introducing commit, searched for prior reports and probed the security angle.