MultiPassIndexSplitter's round-robin split puts the last few documents of an index at IndexWriter.MAX_DOCS into two parts or into none, for most part counts of 145 or more, because (j + numParts - i) % numParts overflows int

MultiPassIndexSplitter (lucene/misc) splits an index into N parts by reading it once per part. In round-robin mode, the command line's default, pass i keeps document j only when (j + numParts - i) % numParts == 0 (MultiPassIndexSplitter.java:103), the intended j % numParts == i. The sum is an int. For an index of IndexWriter.MAX_DOCS = 2,147,483,519 documents and 145 parts, the sum passes Integer.MAX_VALUE for the last doc ids, wraps negative (the int value is the sum minus 2^32), and because 2^32 mod 145 = 16, pass i also keeps the overflowing documents of part i + 16.

The result is silent: with 145 parts, documents 2,147,483,511 to 2,147,483,518 are each copied into two parts (2,147,483,527 documents in total); with 149 parts, 10 documents are in no part; with 1000 parts, 296 (by exact enumeration). The parts open and read normally. The input must have maxDoc + numParts > 2^31 (deleted documents count), so it takes an index at the document limit and a large part count, which is why the priority is low. The line dates from the class's first commit (LUCENE-1959, 2009) and is in every release from 3.0.0 to 10.6.0; j % numParts != i fixes it.

1. Inputs. split() checks only outputs.length >= 2 and in.numDocs() >= 2 (:71-76); numParts = outputs.length (:77), and maxDoc = input.maxDoc() (:82) counts deleted documents too. The command line parses -num with no upper bound (:138), rejects only values below 2 (:163-165), and is round-robin unless -seq is given (:127, :133).
2. One pass per part. For each part i (:84), undeleteAll() (:85) resets a private live-docs bit set from the source's own live docs (:244-258).
3. The keep test (:100-107), all in int:

   for (int j = 0; j < maxDoc; j++) {
     if ((j + numParts - i) % numParts != 0) {   // :103
       input.deleteDocument(j);
     }
   }

(j + numParts - i) % numParts == 0 is a non-negative way to write j % numParts == i, and it is right only while the sum fits in an int.

1. The wrap. When j + numParts - i >= 2^31, the int value is the sum minus 2^32 (negative, so Java's % gives a negative or zero remainder). The remainder is zero, and j kept, exactly when j - i is congruent to 2^32 modulo numParts. For 145 parts, 2^32 mod 145 = 16, so pass i keeps the overflowing documents of part i + 16.
2. Copy. addIndexes copies the documents left live into part i (:108-114). Each part is a normal index that opens and reads normally (CheckIndex was not run); only which documents it holds is wrong.

• MAX_DOCS = Integer.MAX_VALUE - 128 = 2,147,483,519 (IndexWriter.java:201-208), so doc ids run from 0 to 2,147,483,518.
• 145 parts, j = 2,147,483,511 (j % 145 = 16). Pass 0: j + 145 = 2,147,483,656 wraps to -2,147,483,640 = -145 x 14,810,232, remainder 0, kept. Pass 16: j + 129 = 2,147,483,640 fits, remainder 0, kept. The document is in parts 0 and 16.
• Over all passes: documents 2,147,483,511 to 2,147,483,518 are each in two parts (parts 0 to 7 hold one extra; parts 16 to 23 hold them too), 2,147,483,527 documents in total (+8).
• 149 parts: documents 2,147,483,509 to 2,147,483,518 are in no part (2,147,483,509 in total, -10). 1000 parts: 296 documents in no part (enumeration).
• When it happens. Some pass overflows only if maxDoc + numParts > 2^31; that is necessary, not sufficient. At MAX_DOCS that takes at least 130 parts; 130 to 144 happen to come out right, 145 is the smallest count that fails, and 831 of the 880 counts from 145 to 1024 fail. The other 49 are exact, for example 147, 148, 150, 153 and every power of two (2^32 mod 2^k = 0). The smallest input that fails with 145 parts has 2,147,483,512 documents; with 1000 parts, 2,147,483,001.
• Not affected: sequential mode (-seq, :86-99), whose bounds never exceed maxDoc; an SMT model proved it exact for 2, 3, 7, 64, 129 and 130 parts.

• Who can be hit. Users of the lucene/misc MultiPassIndexSplitter (an opt-in, offline index tool) in round-robin mode, its default, on an input whose maxDoc (deleted documents included) is within about numParts - 129 documents of MAX_DOCS, with a part count that fails, and only if the affected documents near the top are live: a document already deleted in the source stays deleted in every part. An index that has reached the document limit is exactly one someone may want to split, but usually into far fewer parts.
• Silent. The parts open and read normally: the independent reproducer opened every part and read the last documents' doc values. A few documents are missing from the output or appear in two parts, and the only sign is that the parts' document counts do not add up to the input's (CheckIndex was not run on the parts).
• Scale. The input has two billion documents and the tool reads it once per part: the recorded full splits took about 75 to 111 minutes each (the finder's, of empty documents, 75 to 78 minutes; the independent reproducer's and the adjudication's, of documents empty except for doc values on the last 64, 93 to 111 minutes). The minimal test stops after part 0.
• Older releases reach further. Before MAX_DOCS there was no document ceiling below Integer.MAX_VALUE, so small part counts can fail too. Executed on 3.0.0 only: an input of 2,147,483,645 documents (the largest the 3.0.0 runs could split) gives one document too many with 6 parts and 5 too few with 10 parts; 3.1 to 4.9.0 were not executed. Since MAX_DOCS arrived (LUCENE-5843, 4.9.1 and 4.10.0), only part counts of 145 or more can fail.
• Likelihood: contrived. It needs an index at the document limit and a large, unlucky part count; no public report of it was found.

• Input. Exactly MAX_DOCS = 2,147,483,519 = 257 x 8,355,967 empty documents: one force-merged segment of 8,355,967 addDocument calls (no document blocks), added 257 times with addIndexes(CodecReader...), all in ByteBuffersDirectory.
• Why only part 0. outputs[1..144] are one already-closed ByteBuffersDirectory. split() writes and closes part 0, then the IndexWriter for part 1 throws AlreadyClosedException, which the test expects. Part 0 is complete at that point; this saves 144 more passes over two billion documents. The full 145-part split was run separately (sum 2,147,483,527).
• Codec pinned. split() builds its own IndexWriterConfig, so the test sets Codec.setDefault(TestUtil.getDefaultCodec()) (the test framework restores the default after the class). Two seeds give the same failure.
• Cost. A 4 GB heap (a 256 MB live-docs bit set plus merge doc maps). About 1 minute with a plain JUnit runner and about 3 minutes under gradle, whose test JVM runs with C1 only.
• Formatting. ./gradlew tidy (google-java-format) only wraps the long comment above the assertion.
• What it asserts. Only part 0's count: 14,810,232 = the number of ids j with j % 145 == 0 (0, 145, ..., 2,147,483,495). It gets one more, because doc 2,147,483,511 of part 16 is copied there too. split() only clears live-doc bits, so the extra document can only be one that belongs to another part.
• As the regression test: the same test. It fails on stock and passes with the fix. Its scale matches the @Monster tests, like TestIndexWriterMaxDocs (which run only with -Ptests.monster=true), and it needs -Ptests.heapsize=4g.

# gradle, main 645d4fe14a20, seed DEADBEEF (the same with -Ptests.asserts=false)
TestMultiPassIndexSplitterRoundRobinOverflow > testPart0OfMaxDocsIndex FAILED
    java.lang.AssertionError: numDocs of round-robin part 0 of 145 expected:<14810232> but was:<14810233>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:FD70867819D80048]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.failNotEquals(Assert.java:835)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:647)
        at org.apache.lucene.misc.index.TestMultiPassIndexSplitterRoundRobinOverflow.testPart0OfMaxDocsIndex(TestMultiPassIndexSplitterRoundRobinOverflow.java:64)
  2> Writing part 1 ...

# the full 145-part split (the independent reproducer's own test, main ea57360912ed, -da, re-run by the adjudication)
java.lang.AssertionError: round-robin split is not a partition of the input: 8 bad parts,
  sum of parts' numDocs=2147483527 vs input numDocs=2147483519;
  first problems: [part 0: numDocs=14810233 expected=14810232;
  last-64 docs held=[2147483495, 2147483511] expected=[2147483495], part 1: ...

# full splits on the main jars (-da): sums of the parts' numDocs
144 parts: 2,147,483,519 (exact)   145 parts: 2,147,483,527 (+8)   149 parts: 2,147,483,509 (-10)

• The contract. split() javadoc: "If false, source document id-s will be assigned in a deterministic round-robin fashion to one of the output splits." (MultiPassIndexSplitter.java:65-67). Class javadoc: "This tool splits input index into multiple equal parts." (:43). The 3.0.0 CHANGES entry: "MultiPassIndexSplitter can split any index into any number of output parts, at the cost of doing multiple passes over the input index."
• The test. TestMultiPassIndexSplitter.testSplitRR splits an 11-document index (the last one deleted) into 3 parts and asserts, for each part k, that its first document is document k, that it holds at most 4 documents, and that it lacks an id of another part (part 0 lacks 1, part 1 lacks 0, part 2 lacks 0 and 1): spot checks of the j % numParts == i mapping.
• History. The expression came with the class (LUCENE-1959, 2009) and was never changed. In that review, a reviewer reported "If we have 13 docs ... and numParts=3, 12th doc is missing with -seq mode", and the i < numParts - 1 guard (:95) was added before the commit: a lost document was treated as a bug. Overflow and size limits were never discussed.
• Legal input. MAX_DOCS is the "Hard limit on the maximum number of documents that may be added to the index" (IndexWriter.java:201-208); TestIndexWriterMaxDocs.testExactlyAtTrueLimit (@Monster) builds such an index. Neither split() nor -num bounds the part count.
• Precedent. CHANGES records fixes of int overflows at extreme but legal scale, for example LUCENE-10678 (a BKD tree with more than 4 billion points), LUCENE-8221 (MoreLikeThis.setMaxDocFreqPct) and LUCENE-6409 (LongBitSet.ensureCapacity).

The strongest case for "not worth calling a bug" (the intended-behaviour devil's advocate, a cross-model review and the adjudication): the scale is unrealistic, the tool is an expensive misc utility that reads the input once per part, and the class javadoc's NOTE already says it "can easily break up" document blocks added with addDocuments.

Why it fails: scale argues for a low priority, not for intent; the NOTE is about blocks being spread over different parts, which round-robin does by design, not about documents being lost or duplicated, and the repro adds documents one at a time with addDocument; nothing documents a size or part-count limit; and the fix costs nothing. Verdict: not intended, low impact.

One fix was run through gradle in a scratch worktree of 645d4fe14a20 (OpenJDK 25.0.3, seed DEADBEEF); it is the hunt's candidate fix, unchanged. The other options are described, not run.

In the round-robin loop of split() (MultiPassIndexSplitter.java:103). The comment is optional.

         for (int j = 0; j < maxDoc; j++) {
-          if ((j + numParts - i) % numParts != 0) {
+          if (j % numParts != i) { // j + numParts - i overflows int for j near IndexWriter.MAX_DOCS
             input.deleteDocument(j);
           }
         }

Trade-offs

• For 0 <= j and 0 <= i < numParts both tests keep the same documents, and j % numParts stays in [0, numParts), so nothing can overflow.
• Same cost: one remainder per document per pass. No behaviour change below the overflow window.

What the checks validated

• Stock: the repro fails with assertions on and off.
• Fix: the repro passes with assertions on and off.
• Closest suite TestMultiPassIndexSplitter (testSplitRR, testSplitSeq): 2 tests, 0 failures.
• The whole misc test suite with the repro in place: 24 classes, 317 tests, 0 failures, 9 skipped (seed DEADBEEF).
• :lucene:misc:check -x test passes with the fix and the repro tidied by ./gradlew :lucene:misc:tidy, which only wraps the repro's long comment line; the fix needed no reformatting. Untidied, the check fails on that comment line alone.
• Earlier: the independent reproducer's full 145-part split with the fix shadowed is exact, the minimal test passes with the fix shadowed (assertions on and off), and every enumeration finds the fixed test exact for all part counts from 2 to 1024.

if ((j + (long) numParts - i) % numParts != 0).

Trade-offs

Also correct and overflow-free, and keeps the original shape, but it is less obvious than j % numParts != i and hides why the cast is needed.

Throw when maxDoc + numParts > 2^31.

Trade-offs

Refuses valid splits that the one-line fix handles.

Start from an empty bit set and set j = i, i + numParts, ... instead of clearing every other document.

Trade-offs

Faster, but j += numParts can itself overflow near MAX_DOCS unless j is a long, and it must set a bit only where the source document is live, to keep the source's own deletions; a bigger change for a tool whose run time is dominated by addIndexes.

Method: semi-formal (the first counterexample came from an exact enumeration of the transcribed expression, not from the solver). Hunt unit on the misc reorder and split tools, 2026-10-26, main ea57360912ed.

• Model. A Z3 4.12 bit-vector model of both split modes in exact Java int semantics, with a vacuity mutant (the -seq mode without its last-part rule, which the solver must and did catch). It proved "no document lost" and "no document duplicated" for sequential mode at 2, 3, 7, 64, 129 and 130 parts and for round-robin at 2, 3, 7 and 64 parts, and returned unknown for round-robin at 129 and 130 parts (120 s timeouts).
• Enumeration. Over the window where j + numParts - i can overflow, the AI tool evaluated the transcribed test exactly in Java int arithmetic for every part count from 2 to 1024 at maxDoc = MAX_DOCS: 145 is the first failing count, and 831 counts fail. Later checks repeated it independently, in Java and in closed form, with the same result.
• Full scale. A full split of a MAX_DOCS-document index on the stock main jars (on a separate arm64 host): 145 parts +8, 149 parts -10, 144 parts exact.
• Then: an independent reproducer wrote its own JUnit from the claim alone and failed it on main (-ea and -da), 10.5.2 and 9.12.3; an adjudication re-ran it with a new seed; a fourth audit re-ran a full-scale split.