FrequentTermsSpanBooleanQueryRewrite sizes its queue from maxSize before collecting any term, so Integer.MAX_VALUE fails every search and large caps cost heap on every rewrite

SpanMultiTermQueryWrapper.FrequentTermsSpanBooleanQueryRewrite, added for 10.6.0 by #16484, turns a span-wrapped multi-term query into a SpanOrQuery of the maxSize matching terms with the highest document frequency. It is built on ScoringRewrite, which collects every matching term first, but its builder is a PriorityQueue of capacity maxSize, and ScoringRewrite.rewrite creates the builder before it collects any term (ScoringRewrite.java:107 vs :109 on main 645d4fe14a20; the queue at SpanMultiTermQueryWrapper.java:313). Lucene's internal PriorityQueue allocates maxSize + 1 slots up front and rejects maxSize >= 2,147,483,631 (PriorityQueue.java:121-134). So Integer.MAX_VALUE, which the constructor accepts and the sibling TopTermsSpanBooleanQueryRewrite handles, makes every search throw IllegalArgumentException, with 3 matching terms or none, and a large legal cap such as 2^26 allocates about 268 MB on every rewrite. 10.6.0 (released 2026-10-29) and main are affected; no earlier release has the class. Sizing the queue by the terms actually collected fixes both and, in every case tested, leaves the kept terms unchanged.

1. The constructors store maxSize unchecked (SpanMultiTermQueryWrapper.java:301-308) and delegate to an anonymous ScoringRewrite<PriorityQueue<ScoreTerm>> whose builder is

   @Override
   protected PriorityQueue<ScoreTerm> getTopLevelBuilder() {
     return PriorityQueue.usingComparator(maxSize, order);
   }

(:311-314). addClause calls insertWithOverflow for each term (:331-339), build pops the queue into a SpanOrQuery (:316-324), and checkMaxClauseCount is a no-op because "the priority queue already bounds the number of retained terms" (:326-329).

1. ScoringRewrite.rewrite calls getTopLevelBuilder() (ScoringRewrite.java:107) before collectTerms (:109). The number of matching terms is known only afterwards, col.terms.size() (:111).
2. PriorityQueue.usingComparator builds new PriorityQueue<>(maxSize, lessThan) (PriorityQueue.java:61-64). The constructor throws IllegalArgumentException for maxSize < 0 or maxSize >= ArrayUtil.MAX_ARRAY_LENGTH (:121-125; Integer.MAX_VALUE - NUM_BYTES_ARRAY_HEADER, 2,147,483,631 on the test JVM), else allocates new Object[maxSize + 1] (:129, :134). The class is @lucene.internal and documents the pre-allocation only there (:34-39).

So the queue is sized by the cap, not by the terms found: at maxSize >= 2,147,483,631 every rewrite throws, and below that every rewrite with a positive maxSize allocates maxSize + 1 references (2 for maxSize 0) (4 bytes each with compressed references), for any number of matching terms.

TopTermsRewrite.rewrite takes Math.min(size, getMaxSize()) and collects into a growing java.util.PriorityQueue (TopTermsRewrite.java:64-65). TopTermsSpanBooleanQueryRewrite uses it with getMaxSize() = Integer.MAX_VALUE (SpanMultiTermQueryWrapper.java:205-216), so it accepts Integer.MAX_VALUE and allocates the same small amount at every size tried.

The same exception with IndexSearcher.setMaxClauseCount(Integer.MAX_VALUE) and for a prefix that matches no term. Byte counts depend on the JVM; the edge 2,147,483,631 depends on its array header size.

• Opt-in. The wrapper's default rewrite is SCORING_SPAN_QUERY_REWRITE, or TopTermsSpanBooleanQueryRewrite for a top-terms query such as FuzzyQuery (SpanMultiTermQueryWrapper.java:65-77); an application must call setRewriteMethod(new FrequentTermsSpanBooleanQueryRewrite(n)). No Lucene code outside the class and its test builds it. Within that usage the default writer, codec and searcher suffice, and 3 documents are enough.
• Loud, not silent. A huge cap fails on the first query with a clean IllegalArgumentException (the constructor accepted it). A cap in the millions costs maxSize + 1 slots of heap on every rewrite, up to OutOfMemoryError on a small heap. No wrong results, no index effect.
• The clause limit. Under the default IndexSearcher clause limit (1024), keeping more than 1,025 terms already fails with TooManyNestedClauses (related bug LFV-733): the clause check tests numClauses > maxClauseCount before it counts the clause, so it lets 1,025 clauses through and throws on the 1,026th (IndexSearcher.java:907-921; the off-by-one is tracked upstream as #10339). So caps far above 1024 matter once the limit is raised. The Integer.MAX_VALUE failure does not depend on the clause limit.
• Releases. The class first shipped in 10.6.0 (released 2026-10-29), which is affected; it can be fixed in 10.6.1.
• Likelihood: rare. The class exists to bound expansion, so most callers pass small caps; a GitHub code search on 2026-10-28 found no downstream user.

The test uses ByteBuffersDirectory and the default IndexWriterConfig, so the seed randomizes only test-framework settings (locale, time zone, default codec, similarity and the like), and the failure does not depend on them: it is the same with two seeds and with assertions on and off. The recorded gradle runs used this command in a scratch worktree with the test copied in, plus --no-daemon --max-workers=4 -Ptests.jvms=4. The catch only turns the exception into an expected-vs-actual message.

It asserts the headline (the exception) only. The per-rewrite allocation is a JVM-dependent consequence of the same line; the finder's allocation test measured it (about 268 MB at maxSize 2^26, OutOfMemoryError with -Xmx256m) and passes with the fix, but it is evidence, not a proposed regression test.

cp $REPRO/TestFrequentTermsSpanRewriteMaxSize.java $LUCENE/lucene/queries/src/test/org/apache/lucene/queries/spans/
cd $LUCENE && ./gradlew :lucene:queries:test --tests TestFrequentTermsSpanRewriteMaxSize -Ptests.seed=DEADBEEF -Ptests.asserts=true
# also with -Ptests.asserts=false

TestFrequentTermsSpanRewriteMaxSize > testMaxSizeIntegerMaxValue FAILED
    java.lang.AssertionError: expected count 3, but the rewrite threw java.lang.IllegalArgumentException: maxSize must be >= 0 and < 2147483631; got: 2147483647
        at org.apache.lucene.queries.spans.TestFrequentTermsSpanRewriteMaxSize.testMaxSizeIntegerMaxValue(TestFrequentTermsSpanRewriteMaxSize.java:50)

        Caused by:
        java.lang.IllegalArgumentException: maxSize must be >= 0 and < 2147483631; got: 2147483647
            at org.apache.lucene.util.PriorityQueue.<init>(PriorityQueue.java:123)
            at org.apache.lucene.util.PriorityQueue.<init>(PriorityQueue.java:80)
            at org.apache.lucene.util.PriorityQueue.usingComparator(PriorityQueue.java:63)
            at org.apache.lucene.queries.spans.SpanMultiTermQueryWrapper$FrequentTermsSpanBooleanQueryRewrite$1.getTopLevelBuilder(SpanMultiTermQueryWrapper.java:313)
            at org.apache.lucene.queries.spans.SpanMultiTermQueryWrapper$FrequentTermsSpanBooleanQueryRewrite$1.getTopLevelBuilder(SpanMultiTermQueryWrapper.java:310)
            at org.apache.lucene.search.ScoringRewrite.rewrite(ScoringRewrite.java:107)
            at org.apache.lucene.queries.spans.SpanMultiTermQueryWrapper$FrequentTermsSpanBooleanQueryRewrite.rewrite(SpanMultiTermQueryWrapper.java:350)
            at org.apache.lucene.queries.spans.SpanMultiTermQueryWrapper.rewrite(SpanMultiTermQueryWrapper.java:121)
            at org.apache.lucene.search.ConstantScoreQuery.rewrite(ConstantScoreQuery.java:44)
            at org.apache.lucene.search.IndexSearcher.rewrite(IndexSearcher.java:873)
            at org.apache.lucene.search.IndexSearcher.count(IndexSearcher.java:497)
            at org.apache.lucene.queries.spans.TestFrequentTermsSpanRewriteMaxSize.testMaxSizeIntegerMaxValue(TestFrequentTermsSpanRewriteMaxSize.java:47)
:lucene:queries:test (FAILURE): 1 test, 1  failure

# the same with -Ptests.asserts=false; with the fix: :lucene:queries:test (SUCCESS): 1 test

• Contract. "Create a rewrite that keeps at most maxSize terms" (SpanMultiTermQueryWrapper.java:300, :305). The class javadoc defines the class by its ranking difference to TopTermsSpanBooleanQueryRewrite (:261-263). The bound and the pre-allocation are documented only on the @lucene.internal PriorityQueue (PriorityQueue.java:34-39, :121-125).
• The class's design. "ScoringRewrite first collects every matching term ... and this rewrite then retains the maxSize most frequent" (:268-274): the size of the set is known before the queue is needed.
• The sibling. TopTermsSpanBooleanQueryRewrite(Integer.MAX_VALUE) keeps the 3 terms with the default and with a raised clause limit.
• Precedent. LUCENE-504 (#1581), fixed by Uwe Schindler in 15743fc1793 (2009-11-06), changed FuzzyQuery to use java.util.PriorityQueue, "which grows dynamically to support BooleanQuery.maxClauseCount(Integer.MAX_VALUE) without exhausting all memory" (the commit subject itself spells the class java.utilPriorityQueue). TopTermsRewrite keeps that design today. IndexSearcher.searchAfter likewise caps numHits at Math.max(1, reader.maxDoc()) before sizing its collector (IndexSearcher.java:587-599).
• Why tests missed it. The class's only upstream test uses size 8; #16484's review did not discuss sizes.

Strongest case: pre-allocating a queue sized by the caller's N is a deliberate Lucene pattern (TopScoreDocCollectorManager and TopFieldCollectorManager document "pre-allocate a full array of length numHits"), and the PriorityQueue exception is a deliberate guard against a confusing OutOfMemoryError (4c646dab3fb, 2018). The class exists to bound expansion, so "no limit" goes against its purpose; SCORING_SPAN_QUERY_REWRITE already keeps every term; and under the default clause limit (1024) more than 1,025 terms fail anyway (the clause check throws on the 1,026th clause).

Why it fails: those collectors document the pre-allocation on their public API; this class does not, and fails late, at search time, from an internal class, after its public constructor accepted the value. The sibling it is defined against accepts Integer.MAX_VALUE; with a raised clause limit, keeping every matching term is a legal result; and LUCENE-504 already settled the question for multi-term rewrites. Even if huge caps were unsupported, the constructor should reject them. The intended-behaviour check: real, high confidence for the exception, medium for the allocation on its own, so the allocation is filed as a consequence, not as a second bug.

Three fixes were built and run in a scratch worktree of 645d4fe14a20; capping or rejecting the size alone is not recommended.

A private builder TopFrequentTerms replaces the queue as the ScoringRewrite builder. It keeps terms in a pending list while fewer than maxSize have arrived; on the first term beyond maxSize it allocates a queue of maxSize slots, moves the pending terms in and continues with insertWithOverflow; if that never happens, build() allocates a queue of exactly the collected count. Terms are offered in the same order as before. The constructor also rejects a negative maxSize (optional hardening; today a negative size fails at search time with the same exception).

void add(ScoreTerm st) {            // once per matching term
  if (queue == null) {
    if (pending.size() < maxSize) {
      pending.add(st);
      return;
    }
    queue = newQueue(maxSize);       // more than maxSize terms: allocate now
  }
  queue.insertWithOverflow(st);
}
// build(): finish() makes newQueue(pending.size()) if the queue was never needed

Trade-offs

About 50 lines and a new private class. When more than maxSize terms match, the peak at the switch is the pending list (maxSize terms, plus the ArrayList's spare capacity) plus the new queue (maxSize + 1 slots); the list is dropped right after the move. The branch_10_6 line reads new PriorityQueue<>(maxSize) { lessThan }, so a backport needs the 10.x queue API.

What the checks validated

• Stock + test: fails with assertions on and off; + fix: passes with assertions on and off (gradle).
• + fix: the whole lucene/queries module, 513 tests with the new test, 0 failures, assertions on and off; :lucene:queries:check -x test (format, ecjLint, forbiddenApis) passes.
• + fix: the finder's 3 tests pass, including the 2^26 allocation test, also with -Xmx256m (stock: OutOfMemoryError).
• The finder's exhaustive harness (0-4 matching terms): 60,960 cases, 0 mismatches with the fix and results identical to stock for every size stock accepts; a Z3 model: the fix cannot throw for maxSize >= 0 and its queue array never has more than max(n + 1, 2) slots (the model does not cover the pending list).
• Not run: the full Lucene test suite, nightly tests, branch_10_6.

The builder becomes a List<ScoreTerm>; build() creates PriorityQueue.usingComparator(Math.min(maxSize, builder.size()), order), offers every collected term with insertWithOverflow in the same order, then pops as before (+14/-12).

Trade-offs

Smallest and easiest to review, but it keeps a ScoreTerm and its Term for every matching term until build(), where today the queue drops the overflow at once. ScoringRewrite already holds every matching term's bytes and TermStates for the whole rewrite, so memory stays linear in the matching terms, with a larger constant when far more terms match than maxSize.

What the checks validated

The test passes; the whole lucene/queries module passes (513 tests); check -x test passes after a formatting fix; the finder's 3 tests and the -Xmx256m test pass.

Option A with builder capacity Math.min(maxSize, IndexSearcher.getMaxClauseCount()), as the core top-terms rewrites cap their size (+59/-8). Related bug LFV-733 changes the same line for the clause limit.

Trade-offs

It also changes LFV-733's case: an explicit maxSize above the clause limit then keeps at most the limit instead of failing with TooManyNestedClauses; argue that in LFV-733's issue.

What the checks validated

The whole lucene/queries module passes (513 tests); check -x test passes; the finder's 3 tests pass, including the raised-clause-limit case.

Capping the eager queue at IndexSearcher.getMaxClauseCount() hides the bug only at the default limit: with setMaxClauseCount(Integer.MAX_VALUE) the exception is back, and the allocation becomes min(maxSize, limit) + 1 slots (executed by the finder and the independent reproduction). Rejecting large sizes in the constructor and documenting the pre-allocation fails fast, but keeps the per-rewrite allocation for every cap below the edge and diverges from the sibling, which accepts Integer.MAX_VALUE.

Method: differential testing, then bounded-exhaustive translation validation and a Z3 model (semi-formal).

• A planning probe on main a9779ef3c193 (2026-10-28) ran FrequentTermsSpanBooleanQueryRewrite and TopTermsSpanBooleanQueryRewrite at the same sizes: only the new rewrite threw, at 2,147,483,631 and Integer.MAX_VALUE, and it took 154 ms at 2^26 against 1 ms.
• The finder reduced it to a public-API JUnit (6 documents, 3 terms) and found the cause by reading ScoringRewrite.rewrite while modelling it.
• A harness compared the rewrite with a reference written from its javadoc on every small case: 60,960 cases, 0-4 matching terms, 1 or 2 segments, sizes -1, 0..n+1, 4096, 2,147,483,631 and Integer.MAX_VALUE, both built-in orders. The only mismatches were the 12,440 exception cases at the two edge sizes; a deliberately wrong reference is caught.
• A Z3 bit-vector model of the queue sizing confirmed that the stock code can throw or allocate over 10^6 slots for at most 3 terms, and that the lazy fix cannot (6 of 6 queries as expected).
• This doc's one-method test is a reduction of the finder's test.