LongHeap and TernaryLongHeap overflow int at 715,827,883 elements: push stops growing and IndexSearcher.search(query, n) can throw

LongHeap and TernaryLongHeap document unbounded growth, but both compute array positions with int multiplications by 3 that overflow once the heap holds 715,827,883 values (a 5.73 GB long[]). push then throws instead of growing and leaves size() one too high, and TernaryLongHeap.downHeap reads a negative index. Since 10.4.0 the default top-hits collector keeps its n hits in a TernaryLongHeap, so on a searcher without an executor IndexSearcher.search(query, n) throws ArrayIndexOutOfBoundsException once n and the index both reach 715,827,883 documents and enough hits are collected (executed on main and 10.6.0). In every executed run nothing was written wrongly and no wrong result was returned; it is a loud failure at extreme scale. Introduced in 9.0.0 (LongHeap) and 10.4.0 (TernaryLongHeap); never fixed.

public long push(long element) {
  size++;                                              // size is now 715,827,883
  if (size == heap.length) {                           // heap.length is 715,827,883: full
    heap = ArrayUtil.grow(heap, (size * 3 + 1) / 2);   // int: 2,147,483,650 wraps to -2,147,483,646; /2 = -1,073,741,823
  }
  heap[size] = element;                                // index 715,827,883 in a long[715,827,883]

• ArrayUtil.grow(long[], int) (ArrayUtil.java:409-414) asserts minSize >= 0 with the message "size must be positive (got -1073741823): likely integer overflow?" (:410). Without assertions a negative minSize is never larger than the array, so the same array comes back and the store one line later goes one past its end.
• The exact target is 1,073,741,825, far below ArrayUtil.MAX_ARRAY_LENGTH (2,147,483,631 on a 64-bit JVM with compressed oops, as in every run here).
• size++ runs first, so after the throw size() says 715,827,883 although only 715,827,882 values are stored; a later pop() throws ArrayIndexOutOfBoundsException (shown by the study's test).
• Every array length from 715,827,883 (3 x 715,827,883 = 2^31 + 1) up to MAX_ARRAY_LENGTH - 1 fails. A heap grown only by push gets stuck between about 0.72 and 1.21 billion values, depending on its initial capacity, for example at 718,079,901 values from capacity 64 (computed with the real ArrayUtil.oversize for every capacity from 1 to 2,000,000).

int firstChild = arity * (i - 1) + 2;          // :225  i = 715,827,883: 3 * 715,827,882 + 2 = 2^31, wraps to -2^31
if (firstChild > size) break; // i is a leaf    // :226  a negative firstChild never stops the loop
...
long bestVal = heap[firstChild];               // :232  ArrayIndexOutOfBoundsException: Index -2147483648

Only a heap of at least 715,827,883 values has slot 715,827,883. It is a leaf there, but once the index has wrapped the leaf test cannot see it. updateTop (:151-155) and pop (:119-129) both sink values this way. From node 1,431,655,766 on the product wraps back to a positive index (205,032,703 for node 1,500,000,000), so with n above 1.43 billion the sift could break heap order silently instead of throwing (read, not run). The binary LongHeap.downHeap computes j = i << 1 (LongHeap.java:181, 189), which wraps from slot 2^30 = 1,073,741,824 (read, not run).

IndexSearcher.search(Query, int) (IndexSearcher.java:623-625, javadoc "Finds the top n hits") calls searchAfter, which caps n at maxDoc (:588, :597) and builds a TopScoreDocCollectorManager (:598-599). The manager only rejects numHits <= 0 (TopScoreDocCollectorManager.java:62). TopScoreDocCollector creates new TernaryLongHeap(numHits, LEAST_COMPETITIVE_CODE) (TopScoreDocCollector.java:44), a full heap of placeholders, and calls heap.updateTop(code) for every competitive hit (:130-135). With equal scores, ascending doc ids and one collector each hit sinks into the next free slot in post-order; slot 715,827,883 is the 202,045,716th, exactly where the executed search threw.

• Default collector, no special configuration. The default top-hits collector of IndexSearcher.search(query, n) uses TernaryLongHeap from 10.4.0 on (LongHeap in 10.3.x, HitQueue before). Lucene itself caps n at maxDoc, so Integer.MAX_VALUE reaches the heap as the document count. The caller still has to ask for n of at least 715,827,883.
• Size. At least 715,827,883 documents in the searched view, about a third of IndexWriter.MAX_DOCS (Integer.MAX_VALUE - 128), and enough collected hits for the sift-down to reach slot 715,827,883. From the code: no update can write that slot without throwing, and every competitive hit replaces one placeholder, so in one collector (a searcher without an executor, or a slice that collects that many hits) a query that matches at least n (>= 715,827,883) documents always throws, at the latest at hit n; in the executed equal-score, single-collector run it threw at hit 202,045,716. With an executor each slice gets its own n-slot collector but only that slice's hits (segments above 250,000 documents get their own slice), so the executed 8-segment index, 83.2 to 93.2 million documents per segment, would not throw that way (not run).
• Executed. 715,827,883 empty documents written with IndexWriter (8 segments, about 9.5 MB, 4.4 minutes), then searcher.search(new MatchAllDocsQuery(), Integer.MAX_VALUE) on new IndexSearcher(reader) (no executor) with an 8 GB JVM heap: ArrayIndexOutOfBoundsException: Index -2147483648 out of bounds for length 715827884 after 27.8 s and 202,045,716 collected hits, on main (assertions on and off) and on 10.6.0. With n = 715,827,882 the same collector collected all 715,827,883 hits, and with the fix n = 715,827,883 did too; these two runs used a counting CollectorManager that does not build TopDocs (one ScoreDoc per hit would need far more than 8 GB).
• Other reach (read, not run). NeighborQueue pushes the HNSW search frontier into a TernaryLongHeap; reaching the push limit needs a frontier of more than 715.8 million entries in one segment. LongHeap's only in-tree users (the backward-codecs PForUtil copies) use 8 slots and never grow. External code may use these @lucene.internal heaps directly.
• Cost of getting there. The collector pre-allocates a 5.73 GB long[] per collector (one per slice with an executor), and returning 715 million ScoreDocs needs far more, so few systems run such a query. But in one collector a bigger JVM heap does not help: at this size the collection throws.
• What breaks. The query or the push throws; nothing is written. A heap whose push threw is left counting one value too many, so code that catches the exception and keeps using the heap reads past its end.

TestLongHeapGrowthOverflow uses only the public methods LongHeap(int size, long initialValue), push, size and top of the @lucene.internal class; it sits in org.apache.lucene.util like TestLongHeap but touches no package-private member. The constructor builds the full array in one call, so there are no 715 million pushes. No randomness of its own.

Heap size. Local gradle test JVMs default to -XX:+UseParallelGC, whose old generation is two thirds of the heap, so the 5.73 GB array needs -Ptests.heapsize=10g; with 8 GB (or the default 512 MB) the test stops earlier with OutOfMemoryError in the constructor. A fixed push really allocates the grown 9.66 GB array while the old one is live, so the passing run needs about 24 GB.

As the regression test: this same test, for example as a method in TestLongHeap (perhaps marked @Monster for its memory need). It covers the push line only; a TernaryLongHeap twin differs only in the class name, and it does not cover the downHeap line the public search reaches. The search path needs a 715.8-million-document index (4.4 minutes to build), so it is evidence, not the repro.

cp TestLongHeapGrowthOverflow.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.TestLongHeapGrowthOverflow -Ptests.seed=DEADBEEF -Ptests.heapsize=10g
# assertions off (production): add -Ptests.asserts=false (same bug, ArrayIndexOutOfBoundsException)
# with a fix the grown 9.66 GB array must fit next to the 5.73 GB one: use -Ptests.heapsize=24g

TestLongHeapGrowthOverflow > testPushGrowsFullHeap FAILED
    java.lang.AssertionError: size must be positive (got -1073741823): likely integer overflow?
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:CCE56747AD5487C5]:0)
        at org.apache.lucene.util.ArrayUtil.grow(ArrayUtil.java:410)
        at org.apache.lucene.util.LongHeap.push(LongHeap.java:79)
        at org.apache.lucene.util.TestLongHeapGrowthOverflow.testPushGrowsFullHeap(TestLongHeapGrowthOverflow.java:27)

# -Ptests.asserts=false:
TestLongHeapGrowthOverflow > testPushGrowsFullHeap FAILED
    java.lang.ArrayIndexOutOfBoundsException: Index 715827883 out of bounds for length 715827883
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:CCE56747AD5487C5]:0)
        at org.apache.lucene.util.LongHeap.push(LongHeap.java:81)
        at org.apache.lucene.util.TestLongHeapGrowthOverflow.testPushGrowsFullHeap(TestLongHeapGrowthOverflow.java:27)

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.heapsize=10g; 10.6.0 and 10.5.2: the same (ArrayUtil.java:411).

# The public search path (evidence, not the repro): 715,827,883 empty docs, search(new MatchAllDocsQuery(), Integer.MAX_VALUE), 8 GB heap:
maxDoc=715827883 numDocs=715827883 leaves=8
threw after 27825 ms
java.lang.ArrayIndexOutOfBoundsException: Index -2147483648 out of bounds for length 715827884
    at org.apache.lucene.util.TernaryLongHeap.downHeap(TernaryLongHeap.java:232)
    at org.apache.lucene.util.TernaryLongHeap.updateTop(TernaryLongHeap.java:153)
    at org.apache.lucene.search.TopScoreDocCollector$1.collectCompetitiveHit(TopScoreDocCollector.java:132)
    ...
    at org.apache.lucene.search.IndexSearcher.searchAfter(IndexSearcher.java:601)
    at org.apache.lucene.search.IndexSearcher.search(IndexSearcher.java:624)
# main, assertions on and off; 10.6.0 the same. With n = 715,827,882 the collector collects all 715,827,883 hits (counting run, no TopDocs built).

• Contract. Class javadocs LongHeap.java:24-25 and TernaryLongHeap.java:24-25; push javadoc :72 in both. The constructors accept initialCapacity in [1, MAX_ARRAY_LENGTH - 1] and throw early "to prevent confusing OOME" (:57-58). No size limit below MAX_ARRAY_LENGTH is documented anywhere.
• Tests. TestLongHeap.testUnbounded and TestTernaryLongHeap.testUnbounded assert growth past the initial capacity (at small sizes); testInvalid rejects only -1, 0 and MAX_ARRAY_LENGTH.
• Intent on record. In the #15140 review jpountz wrote "I had not realized that LongHeap grows unbounded on-demand. This doesn't feel right when the ctor takes a maxSize parameter"; the author replied that changing it "could break existing code that relies on unbounded growth. For instance, NeighborQueue", and the parameter was renamed initialCapacity. Growth is deliberate.
• Precedent. Upstream fixed the same kind of overflow in other internal utilities: LUCENE-6409 "Fixed integer overflow in LongBitSet.ensureCapacity" (2015) and "Catch offset overflows in byte pool (#9660) (#12392)" (2023).
• Effect. With n one smaller the same collector collects all 715,827,883 hits (the control skipped building the TopDocs), and the exact growth target fits: this is an arithmetic accident, not a capacity limit.

Both heaps are @lucene.internal ("This API is for internal purposes only and might change in incompatible ways in the next release."). A reviewer from another model family (OpenAI GPT-5.6, asked to refute) reproduced the push failure, agreed on the root cause, and still judged it not a bug on that ground and because no public path had been run then. Also, 715 million hits is extreme, SECURITY.md leaves bounding inputs to the application, and the failure is loud.

Why it fails: @lucene.internal withdraws API stability, not correctness, and the precedents above are internal classes fixed as bugs. The decisive path uses only IndexWriter, DirectoryReader and IndexSearcher.search(Query, int) on a legal index with a legal n, executed on main and 10.6.0, with a control at n one smaller whose collection completes. (The one-test repro calls the internal LongHeap directly; the public path reaches the downHeap line, not push.) It is not resource exhaustion a limit would prevent: in one collector a bigger JVM heap does not avoid it, where Lucene's own constructors prefer clear errors over confusing ones.

Option A was validated through gradle in a scratch worktree of 645d4fe14a20 and on the public search path. B and C fix only push, D is a slower form of A, E narrows the contract. A workaround for users today: keep n at most 715,827,882, or page with searchAfter.

push in both classes asks ArrayUtil.grow for (int) Math.min((length * 3L + 1) / 2, ArrayUtil.MAX_ARRAY_LENGTH). TernaryLongHeap.downHeap loops only while i <= (size - 2) / arity + 1, the last parent, so firstChild is at most size and cannot wrap; LongHeap.downHeap does the same with size >>> 1, which also removes its i << 1 wrap from slot 2^30.

--- a/lucene/core/src/java/org/apache/lucene/util/TernaryLongHeap.java
+++ b/lucene/core/src/java/org/apache/lucene/util/TernaryLongHeap.java
   public long push(long element) {
     size++;
     if (size == heap.length) {
-      heap = ArrayUtil.grow(heap, (size * 3 + 1) / 2);
+      heap = ArrayUtil.grow(heap, nextHeapLength(size));
     }
@@
+  static int nextHeapLength(int length) {
+    // computed in long, length * 3 would overflow an int for large heaps
+    return (int) Math.min((length * 3L + 1) / 2, ArrayUtil.MAX_ARRAY_LENGTH);
+  }
@@ static void downHeap(long[] heap, int i, int size, int arity) {
     long value = heap[i]; // save top value
-    for (; ; ) {
+    // nodes after the parent of the last node are leaves; testing this instead of computing the
+    // first child of a leaf, which can overflow an int on large heaps
+    final int lastParent = size < 2 ? 0 : (size - 2) / arity + 1;
+    while (i <= lastParent) {
       // first child formula for 1-based indexing
       int firstChild = arity * (i - 1) + 2;
-      if (firstChild > size) break; // i is a leaf
-
       int lastChild = Math.min(firstChild + arity - 1, size);
# LongHeap: the same push change, and downHeap loops while (i <= size >>> 1)

Trade-offs

• push's growth branch is cold. downHeap is hot (once per competitive hit in the collector, once per candidate pop in HNSW search), and SECURITY.md asks that robustness fixes not slow hot paths. An ABBA JMH run on aarch64 found no regression; the ternary sift-down was the same or slightly faster (ternaryUpdateTop, n = 10,000: 2,009.7 and 2,011.7 us/op before, 1,870.2 and 1,853.0 after). x86 was not measured.
• A heap holding MAX_ARRAY_LENGTH - 1 values still cannot take one more (push then throws ArrayIndexOutOfBoundsException); that is the real array limit, and a clearer exception there is optional.
• size++ still runs before the growth, so an OutOfMemoryError from grow also leaves size() one too high; moving it after the store is optional hardening.
• Open draft PR #16847 puts a new DocScoreHeap into TopScoreDocCollector: its PackedDocScoreHeap still wraps a TernaryLongHeap, and its LongDocScoreHeap repeats int firstChild = ARITY * (i - 1) + 2; the same change would apply there. Open draft PR #12314 also edits LongHeap.push.
• Tests: the one-test repro covers push only, not the TernaryLongHeap.downHeap line that the public search reaches (node 715,827,883 of a full heap). The LongHeap.downHeap change fixes a separate wrap (i << 1 from node 2^30, an 8.6 GB array); a narrower change could touch only both push methods and TernaryLongHeap.downHeap.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, 2026-11-01: without the fix the repro fails with assertions on and off (-Ptests.heapsize=10g); with it, it passes with assertions on and off (-Ptests.heapsize=24g).
• With the fix: TestLongHeap (8 tests), TestTernaryLongHeap (8), TestTopDocsCollector (15), TestSearchAfter (1), TestTopDocsMerge (5) and every class of the org.apache.lucene.util.hnsw test package (10 classes, including TestNeighborQueue and the HNSW graph tests): 0 failures.
• ./gradlew :lucene:core:check -x test with the fix and the repro as a new test file: passes.
• On the 715,827,883-document index with the fix compiled over the stock main jars, the collector that search(query, n) uses (TopScoreDocCollectorManager(715,827,883, 1000)) collects all 715,827,883 hits in 93.6 s (counting run, TopDocs not built).

ArrayUtil.grow(heap, (int) Math.min((size * 3L + 1) / 2, ArrayUtil.MAX_ARRAY_LENGTH)) inline in push.

Trade-offs

Passes the repro, but leaves the downHeap overflow, so the search-path crash stays.

What the checks validated

The repro passes with it with assertions on and off (standalone, main 645d4fe14a20, 18 GB G1 heap).

Let ArrayUtil.oversize choose the growth; it over-allocates by about 1/8 and clamps at MAX_ARRAY_LENGTH, so nothing can wrap.

Trade-offs

Changes the growth factor from about 1.69x to about 1.125x, so heaps grown by push (HNSW frontiers) copy more often; not measured. Still needs the downHeap change.

What the checks validated

Not run.

Compute firstChild (and the child loop) in long and compare against size.

Trade-offs

Correct, but measured 15-16% slower on aarch64 JMH (ternaryUpdateTop, n = 10,000: about 2,000 to about 2,280 us/op; ternaryPushPop: 481 to about 558). Rejected for the hot path.

What the checks validated

JMH only (aarch64).

For example reject n >= 715,827,883 in TopScoreDocCollectorManager and document a heap limit.

Trade-offs

Narrows the documented contract to hide an arithmetic bug. Not recommended.

What the checks validated

Not run.

• Inventory: CodeQL over a traced build of lucene/core: every int * or << with an operand the range analysis cannot bound, in the util, packed, BKD, HNSW and codec packages (603 rows), blamed against history to prioritise.
• Decide: Z3 4.12.2 with Java int as 32-bit bit-vectors that wrap, comparing the computed target with the exact value in a wider bit-vector; the first counterexample took 0.01 s, and a binary search over the solver gave the first failing length, 715,827,883; cvc5 agreed.
• Witness and verification: a JUnit on the stock jar, then the study's independent verifier with its own 6-method test, an exhaustive arithmetic check over every length, and the TernaryLongHeap.downHeap twin. Later: a rerun on main b83101cdd2, a one-test minimal repro (2026-10-29), a re-verification on main, 10.5.2 and 10.6.0, a cross-model review and a second adjudication that executed the public search path (2026-11-01).