PriorityQueue.downHeap overflows its child index at node 2^30, so on queues of 2^30 or more elements updateTop, pop and insertWithOverflow can crash

PriorityQueue.downHeap computes the child index as int j = i << 1; int k = j + 1;. The constructor accepts any maxSize below ArrayUtil.MAX_ARRAY_LENGTH (2,147,483,631 with compressed references, 2,147,483,623 without), but once a queue holds 2^30 (1,073,741,824) or more elements, a sift-down can reach node 2^30, where i << 1 wraps to Integer.MIN_VALUE. Then k = -2147483647 passes k <= size, heap[k] throws ArrayIndexOutOfBoundsException, and because the children on the path were already moved up and the sifted element is never written back, the queue keeps its size with one element lost and another duplicated.

updateTop and insertWithOverflow can fail from exactly 2^30 elements, pop from 2^30 + 1; 2^30 - 1 always works. A call fails only when its sift-down reaches node 2^30, as it does in the repro. The bug is in every release since 1.3 (2003) and on main, with assertions on or off, and needs no setting. Through the search API it is reachable, by code reading only, from a field-sorted search for 2^30 or more hits (depending on the sort values) or a filtered exact kNN search with k >= 2^30, on an index of more than 2^30 documents; there it fails the request rather than returning wrong hits. Looping only while i <= size >>> 1, like the bound in java.util.PriorityQueue's sift-down, fixes it and passes Lucene's core tests.

protected void downHeap(int i) {                               // PriorityQueue.java:345
  T node = heap[i]; // save top node
  int j = i << 1; // find smaller child                        // :347
  int k = j + 1;                                               // :348
  if (k <= size && lessThan.lessThan(heap[k], heap[j])) {      // :349
    j = k;
  }
  while (j <= size && lessThan.lessThan(heap[j], node)) {      // :352
    heap[i] = heap[j]; // shift up child                       // :353
    i = j;
    j = i << 1;                                                // :355
    k = j + 1;                                                 // :356
    if (k <= size && lessThan.lessThan(heap[k], heap[j])) {    // :357
      j = k;
    }
  }
  heap[i] = node; // install saved node                        // :361
}

1. All children are equal, so lessThan(heap[k], heap[j]) is false and the walk always takes the left child: node 1, 2, 4, 8, ..., 2^29, 2^30. Each step moves a 0 up one level (:353).
2. At i = 2^29: j = 2^30 <= size and 0 < 1, so the 0 at node 2^30 moves up and i = 2^30.
3. j = 2^30 << 1 = 2^31 does not fit in an int: it wraps to Integer.MIN_VALUE (-2,147,483,648), and k = j + 1 = -2,147,483,647 (:355-356).
4. k <= size is true for any negative k (:357), so heap[-2147483647] is read and the JVM's bounds check throws ArrayIndexOutOfBoundsException.
5. heap[i] = node (:361) never runs. The 1 is gone; the 0 of node 2^30 now also sits at node 2^29. The queue still reports 2^30 elements.

• Threshold. The loop moves to i = j only while j <= size, so i reaches 2^30 only when the queue holds 2^30 or more elements. Every smaller queue is unaffected. At or above that size a call fails only if its sift-down actually reaches node 2^30 or deeper, which depends on the values; in the repro (equal elements, a larger new top) it does.
• Always an exception. For every i from 2^30 to 2^31 - 1, i << 1 is negative, so the code never reads or writes a wrong slot: once there, the bounds check always stops it.
• Entry points. updateTop() and updateTop(T) (:286-295), and insertWithOverflow on a full queue (:238; run at 2^30 + 1, at 2^30 it is the same updateTop path), can fail from 2^30 elements. pop() decrements the size before downHeap(1) (:259-260), so it needs 2^30 + 1 elements before the pop. addAll's heapify (:171-173, :203-205) runs the same code (not executed). HitQueue and FieldValueHitQueue inherit downHeap.
• Not affected. add walks up with j >>> 1 (upHeap, :332-343).
• Allowed sizes. The constructor rejects only maxSize < 0 || maxSize >= ArrayUtil.MAX_ARRAY_LENGTH (:121-125), so every size from 2^30 to 2,147,483,630 is accepted (with compressed references; 2,147,483,622 without them).

• Direct users of the public, @lucene.internal PriorityQueue at 2^30 or more elements: executed, fails with assertions on and off.
• Field-sorted search (main and 10.x; by code reading, not executed). IndexSearcher.search(query, n, sort) caps n at maxDoc (IndexSearcher.java:721-733) and each collector gets one FieldValueHitQueue of that size (TopFieldCollectorManager.java:112-114; FieldValueHitQueue extends PriorityQueue). The collector fills it with add (TopFieldCollector.java:438), calls updateTop once it is full (:449), and topDocs() pops every entry (:458-463). Without an executor all segments form one slice (IndexSearcher.java:226-230). So a sorted search for n >= 2^30 hits (for example Integer.MAX_VALUE as "all hits") that collects more than 2^30 hits in one slice of an index with more than 2^30 documents can throw. It does whenever a sift-down reaches node 2^30 or deeper, which depends on the sort values (entries are ordered by value, then by doc, so there is no left edge of equal elements); it becomes likely once the queue holds well over 2^30 entries, and with just over 2^30 the search can complete normally (an independent fact check executed a valid heap of 2^30 + 1 elements whose one risky pop returns normally). Before the queue exists, FieldValueHitQueue.create builds every sort field's comparator with n slots (FieldValueHitQueue.java:139-153), so a search may run out of memory there first.
• Exact kNN search (by code reading), only with a filter: an unfiltered query takes the approximate path (AbstractKnnVectorQuery.java:252-255); exact search runs when the filter matches at most the per-segment k (:282-285) or as a fallback (:301). exactSearch builds a pre-filled HitQueue(min(k, cost)) (:373-374) and calls updateTop for each better hit (:397). With k >= 2^30 and a filter that matches 2^30 or more documents of one segment, the first competitive hit sinks down the left edge of equal sentinels and throws.
• Relevance search used a pre-filled HitQueue on 9.x (by reading); on main it uses a different heap (TernaryLongHeap), which has its own, separately tracked overflow.
• Scale. 2^30 references are 4 GiB with compressed references; in the collectors each slot also holds an entry object and the sort comparators keep their own n-slot arrays, so tens of GB of heap. Lucene allows indexes of up to 2^31 - 129 documents (IndexWriter.MAX_DOCS) and tests such indexes in its monster tests.
• Effect. Through Lucene's collectors the request fails with an exception; the damaged queue belongs to that request and is discarded, so no wrong, extra or missing hits are returned, nothing hangs, nothing is written. A direct caller that catches the exception and keeps using the queue would read the lost and duplicated elements.
• Likelihood: contrived. It needs a billion-entry queue, and the searches of 2026-10-26 found no earlier report.
• Looking ahead. Open draft PR #16277 (a 3-ary queue for FieldValueHitQueue, implementing #16076) computes firstChild(i) = arity * (i - 1) + 2 in int: it keeps the overflow, and for arity 3 it would start at node 715,827,883, so at about 716 million elements (by code reading). Open draft PR #16847 (more than 2^31 documents per index) makes very large indexes a first-class case.

• Smallest input. 2^30 is the smallest failing size; with 2^30 - 1 elements the same call returns 0. Every element is the same cached Integer, so only the reference array is allocated.
• Heap. Lucene's test JVM uses the parallel garbage collector, whose old generation is two thirds of the heap, so at -Ptests.heapsize=5g the 4 GiB array does not fit (OutOfMemoryError: Java heap space in the constructor). With the JVM's default collector a 5 GB heap is enough; the test then takes about 14 s.
• On 9.x and 10.x PriorityQueue is abstract and takes a lessThan override instead of usingComparator; with that one change the test fails on 10.6.0 the same way, at PriorityQueue.java:329.
• As the regression test: this same test, for example as a method of TestPriorityQueue, marked @Monster("needs an 8 GB heap") like TestLongBitSet.testHugeCapacity. It passes with the fix. An 8 GB monster test is heavy; since heap and size are private, a cheap unit test would need a small refactor and would then test the arithmetic, not the real queue.

cp $REPRO/TestPriorityQueueTwoToThe30Elements.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/
cd $LUCENE
./gradlew :lucene:core:test --tests org.apache.lucene.util.TestPriorityQueueTwoToThe30Elements -Ptests.seed=DEADBEEF -Ptests.heapsize=8g
# assertions off: add -Ptests.asserts=false (same result)

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.heapsize=8g, assertions on (the same with -Ptests.asserts=false)
TestPriorityQueueTwoToThe30Elements > testUpdateTop FAILED
    java.lang.ArrayIndexOutOfBoundsException: Index -2147483647 out of bounds for length 1073741825
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:F963D09E6ACA5243]:0)
        at org.apache.lucene.util.PriorityQueue.downHeap(PriorityQueue.java:357)
        at org.apache.lucene.util.PriorityQueue.updateTop(PriorityQueue.java:287)
        at org.apache.lucene.util.PriorityQueue.updateTop(PriorityQueue.java:294)
        at org.apache.lucene.util.TestPriorityQueueTwoToThe30Elements.testUpdateTop(TestPriorityQueueTwoToThe30Elements.java:29)

# 10.6.0 (10.x API form), assertions on and off
java.lang.ArrayIndexOutOfBoundsException: Index -2147483647 out of bounds for length 1073741825
    org.apache.lucene.util.PriorityQueue.downHeap(PriorityQueue.java:329)
    org.apache.lucene.util.PriorityQueue.updateTop(PriorityQueue.java:259)
    org.apache.lucene.util.PriorityQueue.updateTop(PriorityQueue.java:266)

# with the fix: BUILD SUCCESSFUL, 1 test, assertions on and off

• The constructor allows these sizes. It rejects only maxSize < 0 || maxSize >= ArrayUtil.MAX_ARRAY_LENGTH, with the comment "Throw exception to prevent confusing OOME" (PriorityQueue.java:121-125). SOLR-5661 (3ae719d025d, 2014, "catch too-large priority queue") and 4c646dab3fb (2018, "Fix PriorityQueue constructor to throw IllegalArgumentException if you pass Integer.MAX_VALUE as maxSize") tightened it to give clean errors at extreme sizes. Each time the limit was the JVM array limit, never 2^30.
• The contract. "Put()'s and pop()'s require log(size) time" (:31-32); updateTop returns "the new 'top' element" (:284); ArrayIndexOutOfBoundsException is documented only for adding more than maxSize elements (:155-159, :186-190, :210-211). Here size <= maxSize.
• No test or comment sets a 2^30 limit. The only test at an extreme size, TestPriorityQueue.testMaxIntSize, checks the IllegalArgumentException for Integer.MAX_VALUE.
• The JDK bounds it. java.util.PriorityQueue's sift-down (siftDownComparable, siftDownUsingComparator) loops int half = n >>> 1; while (k < half) (JDK 25 source, PriorityQueue.java:686-687, :705-706), the analogous non-leaf guard for its 0-based heap.
• Lucene fixes extreme-scale overflows. LUCENE-6409 (69af3beaed8, 2015) fixed an integer overflow in LongBitSet.ensureCapacity and added a regression test (TestLongBitSet.testHugeCapacity), which was marked @Monster in 2022 for its memory use (#11844).

Strongest case for "not a bug": nobody holds a billion elements in a PriorityQueue; the class is @lucene.internal; it fails loudly with an exception; a 2009 comment says it is "very unlikely in practice" that one will insert this many objects (d2bf223b21c, LUCENE-2119); participants in LUCENE-504 said callers must size queues sensibly; and the only public search trigger needs an index of more than 2^30 documents and a sorted search for more than 2^30 hits on one slice, roughly 50-100 GB of heap.

Why it fails: @lucene.internal renders as "This API is for internal purposes only and might change in incompatible ways in the next release", a compatibility note, not a correctness waiver, and the stable IndexSearcher.search(Query, int, Sort) reaches the class. The 2009 comment was about a different off-by-one (the missing +1 slot at maxSize == Integer.MAX_VALUE), never about downHeap, and explicit validation replaced it in 2014 and 2018. The call does not fail cleanly: it throws halfway and leaves the queue corrupt. And passing Integer.MAX_VALUE for "all hits" is a supported idiom: LUCENE-2119 (ae72952fa41) added the maxDoc cap so it works. "Size queues sensibly" is advice to callers; the constructor's validation defines the accepted sizes, and IndexSearcher itself sizes the queue from the caller's n capped at maxDoc.

What it does establish: the priority is low, and the practical case for "won't fix" is substantial. A maintainer could reasonably call it theoretical, or take only the one-loop fix without an 8 GB test. That does not make the behaviour intended or documented.

Three options; option A was applied in a scratch worktree of main 645d4fe14a20 and run against the minimal test, the closest suites, all core tests and core's static checks.

In downHeap only (+10/-10 lines). Nodes 1 to size/2 are exactly the nodes with a left child, so for them i << 1 <= size and k <= size + 1, and size < ArrayUtil.MAX_ARRAY_LENGTH < Integer.MAX_VALUE: neither can overflow. The loop exits when no child is smaller, as before.

protected void downHeap(int i) {
  T node = heap[i]; // save top node
  // nodes 1..size/2 have a left child; for them i << 1 <= size cannot overflow
  final int lastParent = size >>> 1;
  while (i <= lastParent) {
    int j = i << 1; // find smaller child
    int k = j + 1;
    if (k <= size && lessThan.lessThan(heap[k], heap[j])) {
      j = k;
    }
    if (lessThan.lessThan(heap[j], node) == false) {
      break;
    }
    heap[i] = heap[j]; // shift up child
    i = j;
  }
  heap[i] = node; // install saved node
}

Trade-offs

• Same lessThan calls in the same order, so results, including ties, are unchanged; each level still does one bound check (i <= lastParent instead of j <= size).
• downHeap is a hot path (every competitive hit of a sorted search). No extra work is expected, but performance was not measured; Lucene asks that robustness fixes not slow down hot paths.

What the checks validated

• The minimal test passes with assertions on and off (gradle, scratch worktree of 645d4fe14a20; also standalone).
• Closest suites pass (259 tests): TestPriorityQueue, TestTopFieldCollector*, TestTopDocsMerge, TestTopDocsCollector, TestSort*, TestFieldSortOptimizationSkipping, TestKnn*VectorQuery.
• All of :lucene:core:test passes (8,897 tests, 322 skipped, 0 failures), and so does :lucene:core:check -x test (formatting, ecj lint, forbidden APIs, license checks).
• Earlier, on main ea57360912ed: the finder's test and the version probe pass.

Compute j and k in long, or test Integer.compareUnsigned(k, size) <= 0.

Trade-offs

Smallest diff, but every iteration gains a widening or an unsigned compare in the hot loop, and the code reads worse. Not validated.

Reject maxSize >= 2^30 with IllegalArgumentException.

Trade-offs

Turns the crash into a clean error, but shrinks the documented range; and because IndexSearcher sizes the queue at min(n, maxDoc), a sorted search with n = Integer.MAX_VALUE on an index of more than 2^30 documents would then be refused even when few documents match. Not recommended; not validated.

• The hunt unit covered PriorityQueue and TopDocs.merge. A functional Dafny proof of the heap (39 obligations, 0 errors, 5 of 5 vacuity mutants killed) uses unbounded integers and cannot see overflow.
• So the finder transcribed downHeap's int arithmetic into a separate bounds model with 32-bit wrap-around. Under size < 2^30 every heap[j] and heap[k] read verifies for Java's call sites (downHeap(1) and downHeap(i <= size / 2)); with only the constructor's limit, Dafny reports the reads inside the loop as possibly out of bounds (5 verified, 3 designed errors).
• A public-API JUnit test on the stock main build then failed with Index -2147483647, and a state probe showed the lost element. Independent verifiers reproduced it with their own tests, refined the threshold to exactly 2^30, and searched for any statement that the limit is intended (none found).