kNN query rewrite throws instead of matching nothing when a leaf's parent reader has no documents

The finding in 30 seconds

Before searching a leaf, a kNN query sizes that leaf's top-k collector by the leaf's share of its parent reader, leaf.maxDoc() / (float) parent.maxDoc(). An empty leaf under an empty parent gives 0 / 0f = NaN, (int) Math.max(1, NaN) is 0, and a collector of size 0 fails.

Background: how a kNN query splits k across leaves

A reader is a tree: leaves (segments) under composite readers such as MultiReader. A kNN query searches every leaf and merges the per-leaf hits into one global top k.
Since 10.3.0 a leaf does not collect all k hits. It collects its expected share of them plus a margin, and leaves whose hits all made the global top k are searched a second time. The share is the leaf's maxDoc divided by its parent's maxDoc.
IndexWriter does not write 0-document segments, so in practice a leaf with 0 documents comes from a reader composed in memory, for example new ParallelLeafReader() with no sub-readers.

Diagram of the bug: a MultiReader with maxDoc 0 holds one ParallelLeafReader with maxDoc 0. The kNN query (k = 3) computes the leaf's share as 0 / 0f = NaN; Math.max(1, NaN) is NaN and the int cast gives a per-leaf k of 0, so the rewrite throws AssertionError with assertions on, or IllegalArgumentException 'initialCapacity must be > 0 ... got: 0' with them off, instead of returning MatchNoDocsQuery. A leaf holding 1 of 3 documents gets share 1/3 and k 14; an empty leaf beside a leaf with documents gets share 0 and k 1. — An empty leaf under an empty parent: its share of the parent is 0 / 0 = NaN, the floor `Math.max(1, NaN)` stays NaN, and `(int) NaN` = 0 asks for a top-k collector of size 0, which throws. A parent with documents gives share 0 and a per-leaf k of 1. Select the still to open it at full size. Generated with AI, checked against the code.

The finding, step by step

Compose a reader with no documents from public API: new MultiReader(new ParallelLeafReader()). Its one leaf has maxDoc 0, and so does that leaf's parent. Rewrite KnnFloatVectorQuery("v", {1, 0}, 3) with new IndexSearcher(reader, Runnable::run).
You expect MatchNoDocsQuery: the rewrite returns it when nothing is found, and 10.2.2 returns it for this reader.
Since 10.3.0 each leaf collects only its share of k plus a margin. The share is the leaf's maxDoc divided by its parent's: a leaf holding 1 of 3 documents gets share 1/3 and a per-leaf k of (int) max(1, 1 + 16 * sqrt(2/3)) = 14. Here the share is 0 / 0f = NaN.
Math.max(1, NaN) is NaN, so the floor of 1 is lost, and (int) NaN is 0. With assertions on, assert perLeafTopK > 0 fails; with them off, the collector's heap throws IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 0.
KnnByteVectorQuery and a match-all filter fail the same way. A parent with documents is fine (share 0, per-leaf k 1), and IndexWriter does not write 0-document segments.

Who is affected

Applications that compose a reader in memory with an empty leaf under an empty parent, such as new MultiReader(new ParallelLeafReader()), and run a kNN query on it. Plain search there already fails through LFV-202, so today it shows through kNN rewrite, explain and search; after LFV-202's fix, unfiltered and match-all-filtered kNN searches still fail. Never a wrong result.

Mechanism, terms and numbers586 words

Since 10.3.0 a kNN vector query sizes each leaf's top-k collector by the leaf's share of its immediate parent reader, leaf.maxDoc() / (float) parent.maxDoc(). For a 0-document leaf under a 0-document parent that is 0 / 0f = NaN; Math.max(1, NaN) keeps the NaN, the int cast gives 0, and a collector of size 0 fails: AssertionError with assertions on, IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 0 from the heap with them off. So rewriting KnnFloatVectorQuery("v", {1, 0}, 3) over new MultiReader(new ParallelLeafReader()) throws instead of returning MatchNoDocsQuery, which 10.2.2 and 9.12.3 return. It came with #14226 and is in every release from 10.3.0 to 10.6.0. IndexWriter does not write 0-document segments, so in practice only readers composed in memory are affected; the failure is loud, never a wrong result, and ordinary search on such readers already fails through LFV-202.

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java`)

Optimistic collection is the default. rewrite wraps the default TopKnnCollectorManager (:305-307) of every KnnFloatVectorQuery and KnnByteVectorQuery in an OptimisticKnnCollectorManager (:106-110) and runs one task per leaf of reader.leaves() (:112-118).
The share divides by the immediate parent. OptimisticKnnCollectorManager.newCollector (:318-333): when the delegate is optimistic and context.parent != null (:324), leafProportion = context.reader().maxDoc() / (float) context.parent.reader().maxDoc() (:326). An empty leaf under an empty parent gives 0 / 0f, NaN.
The floor does not catch NaN (the fix site). perLeafTopKCalculation returns (int) Math.max(1, k * p + LAMBDA * Math.sqrt(k * p * (1 - p))) with LAMBDA = 16 (:343-347, :57). Math.max(double, double) returns NaN when an argument is NaN, and casting NaN to int gives 0.
Only an assert stands guard. The comment "if we divided by zero above, leafProportion can be NaN and then this would be 0" (:328) is followed by assert perLeafTopK > 0 (:329). With assertions off the 0 reaches TopKnnCollectorManager.newOptimisticCollector -> new TopKnnCollector(0, ...) (TopKnnCollectorManager.java:49-53) -> NeighborQueue -> TernaryLongHeap(0), which rejects any capacity below 1 (TernaryLongHeap.java:56-64).
Before any field check. KnnFloatVectorQuery.approximateSearch creates the collector (KnnFloatVectorQuery.java:107-108) before it checks for a missing field (:110-114) or k() == 0 (:115-117), so a leaf without the vector field still gets there. KnnByteVectorQuery is the same (:106-116).
The filtered path is harmless. With a real filter, getLeafResults computes the same share (:272-276), but there a NaN only makes cost <= perLeafTopK (0 <= 0) pick exact search, which returns no hits (:282-285).

Which readers fail (executed on main, assertions on and off)

reader	kNN rewrite
`new MultiReader(new ParallelLeafReader())`	throws
`MultiReader(MultiReader(new ParallelLeafReader()), 3-doc DirectoryReader)` (top maxDoc 3, the empty leaf's parent maxDoc 0)	throws, also `search(knn, 10)` and `explain(knn, 0)`
`MultiReader(new ParallelLeafReader(), 3-doc leaf)` (the parent has documents)	rewrites normally (share 0, per-leaf k 1)
the first reader, with a `TermQuery` filter	`MatchNoDocsQuery`
`new MultiReader()` (no leaves at all)	`MatchNoDocsQuery`

KnnByteVectorQuery, and a MatchAllDocsQuery filter (which the rewrite drops), fail like the first row. A filter that rewrites to no match returns MatchNoDocsQuery early (:82-93). KnnFloat16VectorQuery (main only) creates its collector the same way (KnnFloat16VectorQuery.java:107-108); not run.

The repro uses IndexSearcher(reader, executor) because the no-executor constructor builds its slices at once (IndexSearcher.java:225-230) and rejects the empty leaf there through LFV-202 ("minDocId is greater than than maxDoc: [0] > [0]"). With an executor, slices are built at the first search, and rewrite needs none.

Exposure and likelihood224 words

Who. Applications that compose a reader in memory in which a 0-document leaf sits under a 0-document parent: new MultiReader(new ParallelLeafReader()), or such an empty composite nested inside a MultiReader that has documents. Standard readers over indexes that IndexWriter created do not reach the trigger: it does not write 0-document segments (IndexWriter.java:5669-5677), and a fully deleted segment still has maxDoc > 0.
What shows today. Every reader that triggers this also has a 0-document leaf, and LFV-202 already makes plain search/count and the no-executor IndexSearcher constructor throw on it. On its own, this bug shows through IndexSearcher.rewrite / Query.rewrite and explain(knn, doc) on an executor-backed searcher, and it decides which exception a full kNN search throws, since the rewrite runs before slicing.
After LFV-202 is fixed. A searcher whose slices leave out the empty leaf (a stand-in for LFV-202 fixed) counts 3 hits for MatchAllDocsQuery on the nested reader, while the kNN search still throws. So this is the next failure on the same readers.
Default vs opt-in. The per-leaf share is the default kNN path since 10.3.0, with no setting involved. The executor constructor is @lucene.experimental.
Effect and scale. One loud exception per query; no wrong or missing hits and no index change. No scale or unusual parameter: k = 3 and a 2-d vector. Likelihood: contrived.

Minimal repro

One JUnit test method: rewrite KnnFloatVectorQuery("v", {1, 0}, 3) over new MultiReader(new ParallelLeafReader()) with a same-thread executor and expect MatchNoDocsQuery. Deterministic and single-threaded, no index on disk; it fails with assertions on and off.

TestKnnRewriteEmptyParent.java (one JUnit test, lucene/core tests)34 lines

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.search;

import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.MultiReader;
import org.apache.lucene.index.ParallelLeafReader;
import org.apache.lucene.tests.util.LuceneTestCase;

public class TestKnnRewriteEmptyParent extends LuceneTestCase {

  // expected MatchNoDocsQuery; actual AssertionError (-ea) or IllegalArgumentException capacity 0 (-da)
  public void testKnnRewriteOnEmptyLeafUnderEmptyParent() throws Exception {
    try (IndexReader reader = new MultiReader(new ParallelLeafReader())) {
      IndexSearcher searcher = new IndexSearcher(reader, Runnable::run);
      Query rewritten = searcher.rewrite(new KnnFloatVectorQuery("v", new float[] {1, 0}, 3));
      assertEquals(MatchNoDocsQuery.class, rewritten.getClass());
    }
  }
}

Command

cp $REPRO/TestKnnRewriteEmptyParent.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestKnnRewriteEmptyParent -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: IllegalArgumentException from the heap instead of AssertionError

Expected: The rewrite returns MatchNoDocsQuery ("No documents matched the nearest-neighbor search").
Observed: AssertionError at AbstractKnnVectorQuery.java:329 with assertions on; with them off, IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 0 at TernaryLongHeap.<init>.

All files of this repro: repro/LFV-1209/

More files, environment, full output168 words

TestKnnRewriteEmptyParent (one method, extends LuceneTestCase, package org.apache.lucene.search of the lucene/core tests). It draws no random values and builds no index. Under a second.

As a regression test the same method fits in TestKnnFloatVectorQuery once the imports it lacks (org.apache.lucene.index.MultiReader, org.apache.lucene.index.ParallelLeafReader) are added; its 104-character comment line is over google-java-format's limit of 100 (1.37.0, the version main uses, re-wraps it).

Environment

lucene	`main 5adff78bb168 (12.0.0-SNAPSHOT): fails; 10.3.0, 10.5.2, 10.6.0: the same or an equivalent test fails; 10.2.2, 9.12.3: pass`
jdk	`OpenJDK 25.0.3 (build 25.0.3+9-LTS)`
os	`Linux aarch64 (nothing platform-specific)`

Observed output

TestKnnRewriteEmptyParent > testKnnRewriteOnEmptyLeafUnderEmptyParent FAILED
    java.lang.AssertionError
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:1F1CA913A941FF1D]:0)
        at org.apache.lucene.search.AbstractKnnVectorQuery$OptimisticKnnCollectorManager.newCollector(AbstractKnnVectorQuery.java:329)
        at org.apache.lucene.search.TimeLimitingKnnCollectorManager.newCollector(TimeLimitingKnnCollectorManager.java:44)
        at org.apache.lucene.search.KnnFloatVectorQuery.approximateSearch(KnnFloatVectorQuery.java:108)
        at org.apache.lucene.search.AbstractKnnVectorQuery.getLeafResults(AbstractKnnVectorQuery.java:254)
        ...
1 test completed, 1 failed

# -Ptests.asserts=false
TestKnnRewriteEmptyParent > testKnnRewriteOnEmptyLeafUnderEmptyParent FAILED
    java.lang.IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 0
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:1F1CA913A941FF1D]:0)
        at org.apache.lucene.util.TernaryLongHeap.<init>(TernaryLongHeap.java:59)
        at org.apache.lucene.util.hnsw.NeighborQueue.<init>(NeighborQueue.java:60)
        at org.apache.lucene.search.TopKnnCollector.<init>(TopKnnCollector.java:45)
        at org.apache.lucene.search.knn.TopKnnCollectorManager.newOptimisticCollector(TopKnnCollectorManager.java:52)
        at org.apache.lucene.search.AbstractKnnVectorQuery$OptimisticKnnCollectorManager.newCollector(AbstractKnnVectorQuery.java:330)
        ...
1 test completed, 1 failed

# on 10.3.x the second message is LongHeap's "maxSize must be > 0 and < 2147483630; got: 0"

Why it looks unintended

The code floors the per-leaf k at 1 (Math.max(1, ...)) and asserts perLeafTopK > 0; NaN slips past the floor, and nothing documents an exclusion.
The rewrite returns MatchNoDocsQuery when nothing matches, as upstream testEmptyIndex asserts; 10.2.2 and 9.12.3 return it here.
new ParallelLeafReader() with no sub-readers is legal public API, and upstream tests build one.

The full argument232 words

The code's own floor. Math.max(1, ...) in perLeafTopKCalculation (AbstractKnnVectorQuery.java:343-347) shows the intended minimum per-leaf k is 1, and assert perLeafTopK > 0 (:329) states it as an invariant. Here the assert is an internal invariant, not a documented public precondition or failure mode.
Contract and tests. The rewrite returns MatchNoDocsQuery when nothing is collected (:153-155), and BaseKnnVectorQueryTestCase.testEmptyIndex asserts that result for an index with no documents (BaseKnnVectorQueryTestCase.java:165-176). The KnnFloatVectorQuery and KnnByteVectorQuery constructors document one error, "if k is less than 1". No javadoc, CHANGES or MIGRATE entry excludes empty leaves or empty parents.
The input is legal. ParallelLeafReader has an explicit branch for zero sub-readers (maxDoc = numDocs = 0, ParallelLeafReader.java:96-98), and upstream TestParallelReaderEmptyIndex builds new ParallelLeafReader() (:50).
History. 10.2.2 and 9.12.3 return MatchNoDocsQuery for the same input. #14226 replaced the size-k collector per leaf with the share-based size and added the comment and the assert in the same commit; none of its 65 review and issue comments mentions NaN, division by zero or empty readers.
Precedents. #15334 (merged 2025-10-14, under Bug Fixes) fixed a null-parent NPE on these same lines (for MemoryIndex) and left the zero divisor alone. LUCENE-10351 (#11387, fixed by #580 in 2022): a kNN heap of capacity 0 on a segment where every document with the kNN field was deleted, fixed to return empty results.

The devil's-advocate check130 words

The strongest case for "intended": the author saw the NaN case (the comment) and accepted it, so a parent with maxDoc 0 is unsupported. Empty leaves are already unsearchable through LFV-202, the executor constructor is experimental and rewrite is expert API.

Why it fails: an assert is not a precondition users can see, nothing documents the exclusion, and with assertions off the result is an internal heap error, not a validation message. LFV-202 has a different fix site, and fixing it leaves this bug in place. The executed cross-model review (OpenAI GPT-5.6) and the devil's-advocate verifier both rated it real. Verdict: not intended, a Low robustness defect. A maintainer may still fold it into LFV-202's fix or call it too minor; that is a fair outcome for a Low bug.

Suggested fix

Recommended Clamp after the cast in perLeafTopKCalculation (A, recommended, validated)

Clamp after the cast in perLeafTopKCalculation: Math.max(1, (int) (k * p + LAMBDA * Math.sqrt(k * p * (1 - p)))), so a NaN share gives 1. Every finite share gives the same value as before. The repro passes with assertions on and off, and 237 tests of the closest kNN suites pass.

  private static int perLeafTopKCalculation(int k, float leafProportion) {
    // Clamp after the cast: a parent with maxDoc 0 makes leafProportion 0 / 0f = NaN, and
    // (int) Math.max(1, NaN) would be 0.
    return Math.max(
        1,
        (int) (k * leafProportion + LAMBDA * Math.sqrt(k * leafProportion * (1 - leafProportion))));
  }

All options and trade-offs3 options · 390 words

Option A was built and checked through gradle on 5adff78bb168; B and C were not run.

Clamp after the cast in perLeafTopKCalculation (A, recommended, validated)

In AbstractKnnVectorQuery.perLeafTopKCalculation (:343-347), apply Math.max(1, ...) to the int result instead of to the double, and drop the comment at :328, which no longer holds. The assert at :329 stays and now always holds.

  private static int perLeafTopKCalculation(int k, float leafProportion) {
    // Clamp after the cast: a parent with maxDoc 0 makes leafProportion 0 / 0f = NaN, and
    // (int) Math.max(1, NaN) would be 0.
    return Math.max(
        1,
        (int) (k * leafProportion + LAMBDA * Math.sqrt(k * leafProportion * (1 - leafProportion))));
  }

Trade-offs

Both call sites use the helper (:276, :327), so the filtered path gets the same value. For every finite share the result is unchanged (for x >= 0, (int) max(1, x) == max(1, (int) x)); only NaN changes, from 0 to 1, and the empty leaf then returns no hits. No hot-path cost. Open PR #16847 rewrites the share lines (and keeps the divisor, the comment and the assert).

What the checks validated

Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on and off) and passes with it (assertions off).
With the fix and assertions on: the repro (1), TestKnnFloatVectorQuery (43), TestKnnByteVectorQuery (40), TestKnnByteVectorQueryMMap (40), TestSeededKnnFloatVectorQuery (39) and TestSeededKnnByteVectorQuery (39) in :lucene:core, and the three TestParentBlockJoin*KnnVectorQuery suites (35) in :lucene:join: 237 tests, 0 failures. checkGoogleJavaFormat passes on the fix.
Earlier the finder and the cross-model reviewer each checked the same clamp by shadowing the class: their tests passed, and TestKnnFloatVectorQuery passed 43 of 43 in the finder's run.

Fall back to a size-k collector when the parent is empty (B, not run)

In OptimisticKnnCollectorManager.newCollector, when context.parent.reader().maxDoc() == 0, return delegate.newCollector(...) instead of the optimistic collector.

Trade-offs

Explicit about the case, but the filtered path (:275) computes the same share and would want the same guard; more lines than A.

Skip leaves with maxDoc 0 in rewrite (C, not run)

Create no search task for a leaf with maxDoc 0.

Trade-offs

Saves work on empty leaves, but the rewrite asserts one result per leaf (:148) and the second pass tracks leaves by ord, so it is more invasive.

Downstream note

Downstream products are affected only if they compose such readers themselves, since end-user queries and documents cannot create an empty leaf; OpenSearch's k-NN plugin carries a word-for-word copy of the share computation, comment and assert.

How it was found

A proof-obligation audit of AbstractKnnVectorQuery's per-leaf top-k: the code asserts perLeafTopK > 0 under a comment that names the NaN case, so the audit asked which public-API readers make a leaf's parent have maxDoc 0. An empty ParallelLeafReader inside a MultiReader does; a one-method JUnit test then witnessed the exception.

The method in full124 words

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

The finder took assert perLeafTopK > 0 (AbstractKnnVectorQuery.java:329) and the NaN comment above it as a proof obligation: for every reader the public API can build, the per-leaf top-k must be at least 1. It traced the divisor to the leaf's immediate parent and found that new ParallelLeafReader() inside a MultiReader makes it 0.
The finder then wrote a public-API JUnit test, a probe of the nested and flat reader shapes, and the clamp that makes the test pass.
An independent reproducer, an executed cross-model review and a devil's-advocate verifier reproduced it with their own tests, and an adjudication re-ran the reproducer's test ("Prior reports, history and checks").

Prior reports, history and checks

Prior reports

No prior report found (searched 2026-11-03: GitHub issues, PRs and commits incl. the JIRA archive, dev@, java-user@ and issues@, downstream trackers, and the comments of the introducing PR). Nearest: #14226, whose code comment names the NaN case, and the precedents #15334 and LUCENE-10351.

Searches3 searches

No report of this defect was found. The introducing PR's comment names the NaN case; that is a design assumption, not a report that public-API readers reach it.

What was searched, when, and what turned up
Where	When	How	Found
GitHub issues and PRs (apache/lucene)	2026-11-03	two scripted prior-report searches (the larger: 45 queries, 151 hits, none of high relevance) and 26 manual searches: leafProportion, perLeafTopK, "divided by zero", "initialCapacity must be", "maxSize must be > 0", ParallelLeafReader knn, empty leaf knn; a re-check	no report of this defect
Related threads and open PRs (read)	2026-11-03	the 65 comments of #14226 and those of ten later PRs and issues on this code; the diffs of open PRs touching the file (#16847, #16866, #16578, #14996, #13594, #13525, #16357)	#14226 (introducing PR, comment names NaN), #15334 (null parent, same lines), #11387 / LUCENE-10351 (capacity-0 heap, 2022); #16847 and #16866 do not change the share
Mailing lists, downstream, web	2026-11-03	ten years of dev@, java-user@ and issues@; Elasticsearch, OpenSearch, k-NN and Solr trackers; web searches	no report; OpenSearch's k-NN plugin has a word-for-word copy of the code, and none of its issues mentions an empty parent

History

Introduced by #14226 (d279af1961f on main, 2025-05-05; 61424c489e6 on branch_10x), first released in 10.3.0. 10.3.0, 10.5.2, 10.6.0 and main fail; 10.2.2 and 9.12.3 pass. Not fixed upstream.

Versions tested6 rows

Introduced by #14226 "OptimisticKnnVectorQuery" (Michael Sokolov), squash-merged to main as d279af1961f (2025-05-05) and to branch_10x as 61424c489e6 (same author date, committed 2025-07-17). Before it, every leaf got a collector of size k. It added the share, the NaN comment and the assert together; git log -S 'we divided by zero' on main finds only d279af1961f (with --all, also its backport 61424c489e6); git blame -w -M -C at 5adff78bb168 attributes the comment, the assert and perLeafTopKCalculation to it, and the share line to #15019, which re-wrapped it. CHANGES.txt lists it under 10.3.0 Improvements.

A commit-level A/B isolates it: the 10.2.2 jars with AbstractKnnVectorQuery and SeededKnnVectorQuery from d279af1961f fail at that commit's assert, and with the two classes from its parent 1e6106ae57b they pass. Later refactors (#15019, #15063) and the null-parent fix #15334 kept the three lines; #15163 (10.4.0) moved NeighborQueue from LongHeap to TernaryLongHeap, which changed the assertions-off message. Upstream main 1c2072f0284 (2026-11-02) is unchanged here.

Versions and branches executed, with results
Version or commit	Verdict	Result
9.12.3, 10.2.2	not affected	pass: MatchNoDocsQuery
10.2.2 with the two classes from the parent 1e6106ae57b	A/B, parent	pass
10.2.2 with the two classes from d279af1961f	A/B, commit	fails at the commit's assert; with assertions off in LongHeap
10.3.0	affected	fails; assertions off: LongHeap "maxSize must be > 0 ... got: 0"
10.5.2, 10.6.0	affected	fails; assertions off: TernaryLongHeap "initialCapacity must be > 0 ... got: 0"
main 5adff78bb168	JUnit, gradle	fails, assertions on and off

Independent checks

A finder, an independent reproducer, an executed cross-model review (OpenAI GPT-5.6, real, medium), a devil's-advocate verifier, an adjudication, an audit and a final repro check reproduced it. This doc's gradle runs reproduced it on main and validated fix A.

Checks and verdicts263 words

The cross-model review ran on the older main ea57360912ed; its test was re-run on 5adff78bb168 and fails the same way. Every other check ran on 5adff78bb168 or release jars.

Each independent check and its verdict
Check	Verdict	What it found
finder	reproduced	Own test fails on main (assertions on and off), 10.6.0 and 10.3.0 and passes on 10.2.2; the probe shows the nested reader fails and the flat one does not; the clamp makes the test pass and 43 upstream tests pass.
independent reproducer	real	Own test fails on main, 10.6.0, 10.5.2 and 10.3.0 (assertions on and off) and passes on 10.2.2 and 9.12.3; its probe adds the byte query, the match-all filter, and search and explain on the nested reader.
cross-model review, refute lens (OpenAI GPT-5.6, executed)	real (medium)	Own check fails on the trigger while two controls give MatchNoDocsQuery; the clamp passes. Strongest counter-point: scope (a synthetic reader, the experimental executor constructor, expert rewrite, masked by LFV-202).
devil's-advocate verifier	real	The intended-behaviour case is weak to moderate; its probe shows the kNN failure stays when slicing leaves out the empty leaf.
adjudication	confirmed, Low, high	Re-ran the reproducer's test on 5adff78bb168 with assertions on and off: fails as stated.
audit and final repro check	confirmed, Low	Re-ran the one-test repro on main: fails in both modes, passes with the fix; real but minor.
this doc's gradle check	reproduced; fix A validated	Repro fails on main with assertions on and off; with fix A it passes, and 237 tests of 8 kNN suites pass.

Diagram file

The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.

PNG 505 KB

Sources and provenance

Finding record, Lucene and upstream sources, repro files and diagram notes1,534 words

Finding record

LFV-1209, snapshot of 2026-11-06

Registry title: kNN vector query rewrite throws (AssertionError with -ea, IllegalArgumentException 'initialCapacity must be > 0' with -da) instead of matching nothing when a leaf's parent reader has maxDoc 0, because the per-leaf share 0/0 is NaN and the per-leaf top-k becomes 0 (regression in 10.3.0)
Area: search / kNN vector queries (AbstractKnnVectorQuery optimistic per-leaf top-k)
Priority: Low, rank 789: A kNN query rewrite through an executor-backed searcher on a hand-assembled reader with an empty leaf under an empty parent throws instead of matching nothing, a regression in 10.3.0 that is in every release since. It is contrived and loud: IndexWriter never writes such a leaf, no wrong result is returned, and on current releases only the rewrite and explain paths show it.
Impact class: minor
Impact note: Hits only applications that assemble a reader in memory with a maxDoc-0 leaf whose immediate parent reader also has maxDoc 0 (for example new MultiReader(new ParallelLeafReader()), or such an empty composite nested inside a MultiReader that has documents) and run a KnnFloatVectorQuery or KnnByteVectorQuery (unfiltered or with a match-all filter) through an executor-backed IndexSearcher: the rewrite fails with a loud exception (AssertionError with -ea, IllegalArgumentException from the heap constructor with -da) instead of returning no hits; IndexWriter never writes such a leaf, no scale or unusual parameter is needed (k = 3, a 2-d vector), and no wrong result is returned; because ordinary search/count over these readers already throws through LFV-202, today it shows on its own through IndexSearcher.rewrite / Query.rewrite and explain on the nested reader, and it becomes the visible kNN failure once LFV-202 is fixed; affected since 10.3.0.
Summary: You build a reader that holds an empty leaf under an empty parent, such as new MultiReader(new ParallelLeafReader()), wrap it in an executor-backed IndexSearcher and rewrite a KnnFloatVectorQuery("v", {1, 0}, 3) on it, expecting MatchNoDocsQuery: that is what the rewrite returns when nothing matches, and what 10.2.2 returns for the same input. Instead the optimistic per-leaf collector computes the leaf's share of its parent as 0 / 0f = NaN; Math.max(1, NaN) stays NaN and the int cast gives a per-leaf top-k of 0, so the rewrite fails at 'assert perLeafTopK > 0' with -ea, and with -da the heap behind the collector throws IllegalArgumentException 'initialCapacity must be > 0 and < 2147483630; got: 0'.
Introduced: d279af1961f40465a3a9e8ab84848afe69fd8424 (main; squash-merge of apache/lucene#14226 'OptimisticKnnVectorQuery' by Michael Sokolov (msokolov), parent 1e6106ae57b5), backported to branch_10x as 61424c489e65b545f62dd138d45efce1bfafedfb: it replaced the k-sized TopKnnCollectorManager with a per-leaf size computed from leafProportion = leaf maxDoc / parent maxDoc, and added the comment 'if we divided by zero above, leafProportion can be NaN and then this would be 0' followed only by 'assert perLeafTopK > 0' [exec: the 10.2.2 jars with AbstractKnnVectorQuery and SeededKnnVectorQuery shadowed from d279af1961f fail at that assert (-ea) and in LongHeap (-da), and pass with the two classes from the parent 1e6106ae57b; read: git log -S 'we divided by zero' over the full history finds only this commit, and git blame on 5adff78bb168 still attributes the size calculation, the comment and the assert to it]. The NaN comment and the assert were in the PR's first commit (939889056a, 2025-02-27, then an opt-in class); PR commit 571359aa15 (2025-04-17) made it the default path of every KnnFloatVectorQuery and KnnByteVectorQuery. (2025-05-05 (author date 2025-05-05T13:59:30-04:00, the merge time on main; branch_10x commit 61424c489e6 has the same author date and was committed 2025-07-17))
First affected version: 10.3.0 [exec] (tag commit e2871287e4a, 2025-09-05; fails with -ea and -da); 10.2.2 does not contain 61424c489e6 and passes [exec]
Affected versions: 10.3.0, 10.3.1, 10.3.2, 10.4.0, 10.5.0, 10.5.1, 10.5.2 and 10.6.0 (4ae946e5a9b), plus unreleased main 5adff78bb168 (12.0.0-SNAPSHOT) and branch_11x [read: git tag --contains 61424c489e6]. [exec] fail with -ea and -da: main 5adff78bb168 (finder, the independent reproduction, a re-run of the GPT reviewer's test, the intended-behaviour check, adjudication, re-run), 10.6.0, 10.5.2 and 10.3.0 (on 10.3.x the -da error comes from LongHeap, 'maxSize must be > 0 and < 2147483630; got: 0', before #15163 switched NeighborQueue to TernaryLongHeap in 10.4.0). [exec] pass (MatchNoDocsQuery): 10.2.2 and 9.12.3. Not fixed upstream: the parent-maxDoc divisor, the comment and the assert are unchanged on upstream main 1c2072f0284 (2026-11-02), branch_11x and branch_10_6, and the newest commit on the file is 4b982fffe24 (#16271, author date 2026-07-09). Not new in 10.6 (10.5.2 and 10.3.0 fail). The regression covers the kNN rewrite path only: ordinary search/count on such readers already fails through LFV-202 since 10.0.0. All runs used JDK 25.0.3 on Linux aarch64.
Status: documented (brief, checks and a per-finding doc exist)
Verification: Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
Found by: semi-formal: proof-obligation audit
Upstream and prior reports: none found (2026-11-03, on top of the finder's, the independent reproduction's, the intended-behaviour check's and the adjudication's searches; rechecked the same day): a scripted prior-report search (16 GitHub issue/PR, 3 commit, 2 downstream, 20 mailing-list queries over dev@, java-user@, issues@ and commits@, and 4 JIRA-archive queries; 151 hits, 0 high) plus the finder's run (45 queries), 26 manual GitHub searches on apache/lucene, Elasticsearch, OpenSearch and Solr (perLeafTopK, leafProportion, 'divided by zero', 'initialCapacity must be', 'maxSize must be > 0', ParallelLeafReader knn and others), the review and issue comments of #14226 and of ten later PRs on the same code grepped for NaN, divide, empty and maxDoc, the diffs of the open PRs that touch AbstractKnnVectorQuery (#16578, #16866, #14996, #13594, #13525, #16357) and of #16847, ten years of the dev@, java-user@ and issues@ archives, and web searches: no issue, PR, commit, JIRA entry, list thread or downstream issue reports a kNN query failing on a leaf whose parent has maxDoc 0. Nearest items, not this bug: #14226 (the introducing PR; its code comment names the NaN case, guarded only by an assert, and no review comment discusses it), #15334 (merged 2025-10-14 under Bug Fixes: a null-parent NPE fix on the same lines for MemoryIndex that left the zero divisor alone), #11387 / LUCENE-10351 (fixed by #580 in 2022: a capacity-0 kNN heap on all-deleted segments, other code; a precedent that such inputs give no hits), and #16866 and #16847 (open; neither changes the share computation). Same-day recheck: GitHub search found nothing new (leafProportion 0 hits; perLeafTopK only #16866, #16586 and #14226; 'initialCapacity must be' 0; knn ParallelLeafReader 0); of the 11 PRs updated since 2026-11-03 only #16866 (head 1d02b56f51f9) touches AbstractKnnVectorQuery.java, and none of its changed lines touches the share computation; the newest upstream main commit on the file is still 4b982fffe24 (#16271, author date 2026-07-09).
Lucene commit tested: main 5adff78bb168 (12.0.0-SNAPSHOT) through gradle on 2026-11-03 in a scratch worktree, seed DEADBEEF: the repro without the fix (assertions on and off: fails) and with the clamp fix (assertions off: passes; assertions on, with the 8 closest kNN suites of :lucene:core and :lucene:join: 237 tests, 0 failures), plus checkGoogleJavaFormat on the fix. The hunt ran the repro or an equivalent test on main (assertions on and off), 10.6.0, 10.5.2 and 10.3.0 (fail) and on 10.2.2 and 9.12.3 (pass), and a commit-level A/B of #14226 on the 10.2.2 jars. Only Linux aarch64 with OpenJDK 25.0.3 was run.

Lucene and upstream sources

Finding record: lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java:153-155 (at 5adff78bb168) (rewrite returns MatchNoDocsQuery('No documents matched the nearest-neighbor search') when no hit is collected), :318-333 (OptimisticKnnCollectorManager.newCollector: :324 context.parent != null guard, :326 leafProportion = context.reader().maxDoc() / (float) context.parent.reader().maxDoc(), :327 perLeafTopKCalculation, :328 comment 'if we divided by zero above, leafProportion can be NaN and then this would be 0', :329 assert perLeafTopK > 0, :330 delegate.newOptimisticCollector), :343-347 (perLeafTopKCalculation: (int) Math.max(1, ...), fix site), :248-255 (getLeafResults without a filter goes straight to approximateSearch), :272-285 (filtered path: the same NaN only routes to exact search)
lucene/core/src/java/org/apache/lucene/search/KnnFloatVectorQuery.java:100-121 (at 5adff78bb168) (approximateSearch creates the collector at :107-108, before the missing-field check :110-114 and the k() == 0 check :115-117)
lucene/core/src/java/org/apache/lucene/search/knn/TopKnnCollectorManager.java:49-53 (at 5adff78bb168) (newOptimisticCollector: new TopKnnCollector(k, ...)) and lucene/core/src/java/org/apache/lucene/util/TernaryLongHeap.java:56-64 (initialCapacity < 1 throws IllegalArgumentException)
lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java:195-203 (at 5adff78bb168) (IndexSearcher(IndexReader, Executor), @lucene.experimental)
lucene/core/src/test/org/apache/lucene/search/BaseKnnVectorQueryTestCase.java:165-173 (at 5adff78bb168) (testEmptyIndex: rewrite of a kNN query on an index with no documents is MatchNoDocsQuery) and lucene/core/src/test/org/apache/lucene/index/TestParallelReaderEmptyIndex.java:50 (upstream builds new ParallelLeafReader())
The finding in 30 seconds: lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java:57, (at 5adff78bb168) :106-118, :153-155, :272-285, :305-307, :318-333, :343-347
lucene/core/src/java/org/apache/lucene/search/KnnFloatVectorQuery.java:107-117; (at 5adff78bb168) lucene/core/src/java/org/apache/lucene/search/KnnByteVectorQuery.java:106-116
lucene/core/src/java/org/apache/lucene/search/knn/TopKnnCollectorManager.java:49-53; (at 5adff78bb168) lucene/core/src/java/org/apache/lucene/util/TernaryLongHeap.java:56-64
lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java:199-201, (at 5adff78bb168) :225-230
lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java:82-93; (at 5adff78bb168) lucene/core/src/java/org/apache/lucene/search/KnnFloat16VectorQuery.java:107-108
Who is affected: lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java:199-201 (at 5adff78bb168) (@lucene.experimental)
lucene/core/src/java/org/apache/lucene/index/IndexWriter.java:5669-5677; (at 5adff78bb168) lucene/CHANGES.txt:13474 (LUCENE-5173)
Why it looks unintended: lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java:153-155, (at 5adff78bb168) :328-329, :343-347
lucene/core/src/test/org/apache/lucene/search/BaseKnnVectorQueryTestCase.java:165-176; (at 5adff78bb168) lucene/core/src/test/org/apache/lucene/index/TestParallelReaderEmptyIndex.java:50
lucene/core/src/java/org/apache/lucene/search/KnnFloatVectorQuery.java:61, (at 5adff78bb168) :75; lucene/core/src/java/org/apache/lucene/search/KnnByteVectorQuery.java:60, :74 ("if k is less than 1")
lucene/core/src/java/org/apache/lucene/index/ParallelLeafReader.java:96-98 (at 5adff78bb168)
Suggested fix: lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java:148, (at 5adff78bb168) :275-276, :326-329, :343-347
History: a Lucene clone: git tag --contains 61424c489e6 (releases/lucene/10.3.0 to 10.6.0)
lucene/CHANGES.txt:1660 (at 5adff78bb168)
Diagrams: lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java:326-330, (at 5adff78bb168) :343-347; lucene/core/src/java/org/apache/lucene/util/TernaryLongHeap.java:56-64

Other statements trace to the hunt's working files (models, logs, reviews and briefs), which are not published.

Repro files

TestKnnRewriteEmptyParent.java (one JUnit test, lucene/core tests): repro/LFV-1209/TestKnnRewriteEmptyParent.java (34 lines)

About the diagrams

The diagram follows the repro and the code at 5adff78bb168 (AbstractKnnVectorQuery.java:326-330, :343-347; TernaryLongHeap.java:56-64).

assets/LFV-1209/bug.png (505 KB)

Built 2026-11-06 from the hunt's record of this finding and its doc file. Lucene main under test in this hunt: ea57360912ed. Every listed finding was re-run on Lucene main e1faeba08bde on 2026-11-02.

The finding in 30 seconds

Background: how a kNN query splits k across leaves

The finding, step by step

Who is affected

The mechanism (main 5adff78bb168, lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java)

Which readers fail (executed on main, assertions on and off)

Minimal repro

Environment

Observed output

Why it looks unintended

Suggested fix

Clamp after the cast in perLeafTopKCalculation (A, recommended, validated)

Fall back to a size-k collector when the parent is empty (B, not run)

Skip leaves with maxDoc 0 in rewrite (C, not run)

Downstream note

How it was found

Prior reports, history and checks

Prior reports

History

Independent checks

Diagram file

Sources and provenance

Finding record

Lucene and upstream sources

Repro files

About the diagrams

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java`)