A limited ParentsChildrenBlockJoinQuery returns children beyond childLimitPerParent when a filter, a sort or explain() advances it

ParentsChildrenBlockJoinQuery (new in 10.4.0, @lucene.experimental) returns, for each parent that matches parentQuery, its children that match childQuery, at most childLimitPerParent of them. Its iterator's nextDoc() counts a block's matching children from the block's first child, so the hits are the first N matching children of each parent in doc order, as the upstream randomized test defines them. advance(target) instead jumps to the first matching child at or after target and starts counting there, so the matching children of the block before target are never counted and advance() can return a child that nextDoc() never returns, which breaks the DocIdSetIterator#advance contract. A caller whose advance() enters a block past matching children the iterator has not counted can get the extra children, for example a cheaper MUST or FILTER clause that leads a conjunction (+join #id:b returns b in a 5-document repro), a sorted top-N search once competitive skipping starts, and explain(), which tests advance(doc) == doc. Silent, with assertions on or off, default codec and searcher; the default limit (Integer.MAX_VALUE) is not affected. Present since the class was added by #14728, so every release with it (10.4.0 to 10.6.0) and main.

1. nextDoc() (:313-347) advances the child iterator only while childDocCount < childLimitPerParent (:315-317). Once the limit is reached, or the child passed the parent, it resets the count and moves to the next matching parent (:322-330), and alignParentAndChildIterator() moves the child iterator to the first child of that parent's block, parentBits.prevSetBit(parentDoc - 1) + 1 (:386, :390-392). So within each block it returns the first N matching children.
2. advance(target) (:349-382) calls childIt.advance(target) (:355). If the count is used up or the child is past the current parent (:356), it resets childDocCount = 0 (:358) and moves the parent iterator to the child's block, or on to the next parent when the count is used up inside the current block (:359-367); then childDocCount++ (:380). The block's matching children between its first child and target are skipped and never counted. Inside the current block it adds 1 only for the child it returns, so with a limit of 2 or more it undercounts there too.
3. Weight#explain (:170-188) tests scorer.iterator().advance(doc) == doc on a fresh scorer (:173).
4. Who advances the join. Lucene's conjunctions sort their clauses by cost and let the cheapest lead (ConjunctionDISI.java:132, :161; ConjunctionBulkScorer.java:54), using each iterator's cost(); the join iterator's cost is min(childCost, parentCost * childLimitPerParent) (:407-416, formula at :414; the scorer supplier's cost() at :229 is the same formula).

Unsorted search() and count() drive the join with nextDoc() only, so they return the first N matching children of each parent; explain() of a real hit lands on that hit. Only paths that call advance() past uncounted children go wrong.

• Who is hit. Applications using ParentsChildrenBlockJoinQuery (10.4.0 and later) with a finite childLimitPerParent, the parameter the class was added for (#14565). The default Integer.MAX_VALUE is not affected: 0 of 420,758 checks in the bounded-exhaustive model. No use of the class was found in Elasticsearch, OpenSearch or Solr.
• Triggers (public API; default codec, IndexWriterConfig and IndexSearcher; a CheckJoinIndex-valid index):
  • a conjunction where a cheaper MUST or FILTER clause leads, for example a child-attribute filter, the composition the feature request describes (the repro);
  • a plain sorted search search(join, 10, sort) with no other clause, once the sort's competitive iterator starts skipping: 5,000 blocks [c0, c1, parent], limit 1, a long sort field with points and doc values, c1 tiny in five blocks; the top hit is c1-3000, an over-limit child (totalHits = 1002+), on main with assertions on and off and on 10.5.2. With the recommended fix the top 10 are c0-0 to c0-9 and the total stays a lower bound (1001+ of 5,000 matches), consistent with skipping still working (the probe does not instrument skipping);
  • IndexSearcher.explain on a non-hit, which reports a match.
• Same root, notes only. As a MUST_NOT clause the join can exclude documents it does not match (run on 10.5.2 and main only). On 10.5.2 the bounded model finds such cases (up to 6 documents); on main it finds none up to 7 documents, but a separate 15,000-document probe, where the required clause skips past a 4,096-document window into a block, reproduces one (+id:12000 -join returns 0 hits instead of 1). With an explicit LRUQueryCache that caches the join, the conjunction becomes correct (1 hit without the cache, 0 with it), so the answer can also change with caching; not shown with the default caching policy.
• Effect. Silent wrong results: more children per parent than the limit, and an explain() that disagrees with search() for the query alone. Every extra hit still matches childQuery, has a parent that matches parentQuery and satisfies every other required clause.
• Scale. A differential check against a reference join written from the javadoc, over every block layout up to 7 documents and every match pattern: 11,180 mismatches in 1,683,032 checks on main (limit 1: 6,562; limit 2: 3,827; limit 3: 791; MAX: 0). With limit 1, 1,772 of 72,818 single-document FILTER conjunctions and 1,973 of 72,818 explain checks are wrong; 0 mismatches with either fix. The model covers one segment, no deletions, blocks that end in a parent, disjoint parent and child queries and limits 1, 2, 3 and Integer.MAX_VALUE; it says nothing about multi-segment indexes, deletions or other query shapes.
• Not affected: the join alone with unsorted search() and count(), explain() of real hits, the default limit. Intra-segment concurrency is rejected on purpose (ParentsChildrenBlockJoinQuery.java:191-197), so it is not a trigger.
• Likelihood: plausible. A rarely used, experimental class, but deterministic for its users once a filter, a sort or explain() is involved.

The hunt's minimal repro after ./gradlew :lucene:join:applyGoogleJavaFormat, which wraps two long lines and changes nothing else, so it passes the build's format check. The documents and the query are fixed; single thread, one segment. The seed fixes the test framework's randomized environment: locale, time zone, codec, similarity and index settings (the gradle run prints codec=Asserting(Lucene104), sim=Asserting(RandomSimilarity(queryNorm=false)), maxPointsInLeafNode=1990). The failure does not come from that randomization: a plain program without the test framework, using the real default codec and similarity, prints join.count=2 conjunction.count=1 explain(doc 1).isMatch=true on main and on the 10.6.0 release commit, with assertions on and off. The query cache is off because the test framework may install a randomly caching default cache, and caching the join hides the bug.

On stock Lucene the count assertion fails first, so the explain assertion is not reached; an earlier version of the test, which prints the explain result in the count assertion's message, fails with explain(join, doc 1).isMatch()=true expected:<0> but was:<1>.

Regression test: this same test; it passes with either fix.

cp $REPRO/TestParentsChildrenChildLimitAdvance.java $LUCENE/lucene/join/src/test/org/apache/lucene/search/join/
cd $LUCENE && ./gradlew :lucene:join:test --tests TestParentsChildrenChildLimitAdvance -Ptests.seed=5EED1048
# assertions off: add -Ptests.asserts=false (same failure)

# main 645d4fe14a20, gradle, -Ptests.seed=5EED1048 (the same with -Ptests.asserts=false)
TestParentsChildrenChildLimitAdvance > testAdvanceHonoursChildLimitPerParent FAILED
    java.lang.AssertionError: expected:<0> but was:<1>
        ...
        at org.apache.lucene.search.join.TestParentsChildrenChildLimitAdvance.testAdvanceHonoursChildLimitPerParent(TestParentsChildrenChildLimitAdvance.java:68)
:lucene:join:test (FAILURE): 1 test, 1  failure

# line 68: assertEquals(0, searcher.count(joinAndB))
# standalone runner, main -ea / -da and the 10.4.0, 10.5.0, 10.5.1, 10.5.2, 10.6.0 release jars -ea / -da: fail 1/1, same message at line 68
# plain program (no test framework), main and 10.6.0 -ea / -da:
join.count=2 (expected 2) conjunction.count=1 (expected 0) explain(doc 1).isMatch=true (expected false)

# with fix A: the test passes; :lucene:join:test (SUCCESS): 105 tests, 3 skipped (assertions on and off);
# :lucene:join:check (format, ecjLint, forbiddenApis, tests): BUILD SUCCESSFUL
# with fix B: the test passes; :lucene:join:test (SUCCESS): 105 tests, 3 skipped (assertions on)

• The core contract. DocIdSetIterator#advance: "When target > current it behaves as if written: while ((doc = nextDoc()) < target) {} return doc;" (DocIdSetIterator.java:144-152). With limit 1, nextDoc() never returns doc 1, but advance(1) does.
• The query's composition. Occur.MUST: clauses that "must appear in the matching documents"; Occur.FILTER: "Like MUST except that these clauses do not participate in scoring" (BooleanClause.java:27, :35). So +join #id:b is the intersection of {a, c} and {b}: empty.
• Upstream's definition of the hits. testWithRandomizedIndex adds a child to the expected set only while matchingChildrenCount <= childLimitPerParent, walking each block in doc order (TestParentsChildrenBlockJoinQuery.java:119-129).
• The feature request assumes limit-then-intersect. #14565 (Jinny-Wang, the class's author): with a limit of 1, a join over [child1, child2, child3, Parent1] [child4, child5, Parent2] "will return child1 and child4", so combined with title:milk (child3, child5) "the boolean query will return no match"; it proposes putting a childQuery inside the join for that reason.
• The authors guard against counting mid-block. The #14728 commit message: "this query type will not work with intrasegment concurrency, as it may split a block, leading to overcollection of child documents". The query throws for intra-segment partitions (ParentsChildrenBlockJoinQuery.java:191-197), and three places in the test class say "Do not use Concurrency.INTRA_SEGMENT as that would break childLimitPerParent counting" (TestParentsChildrenBlockJoinQuery.java:185 in testAdvance, :246 in the shared helper test(...), :369 in testExplain). advance() into the middle of a block is an unguarded path to the same over-collection.
• No test advances into a block where the limit binds. testAdvance advances only to a block's first child or past the end (TestParentsChildrenBlockJoinQuery.java:212-219); testExplain's explain(query, 4) (:399) advances a fresh scorer to the middle of block [3, 4, 5], past matching child 3, but its limit 2 never binds in that index (:336-386); and the class's tests do not run QueryUtils.check, whose checkFirstSkipTo advances a fresh scorer to every document between hits (QueryUtils.java:408-447).
• Explain disagreeing with search is treated as a bug. On #15041 benwtrent called an explain match for a non-hit in this class's test "troublesome as that indicates we are matching on a filtered out document now, or that explain is broken" (that failure had another cause, merge-ordered doc ids, and was fixed in the test).

The strongest case for "intended" (built by the devil's-advocate verifier and the adjudication): the javadoc promises only a maximum, and each pass of the iterator does return at most N children per parent; it never says which N. #14565 motivates the limit as a diversification budget ("to ensure that docs from more parents are considered"), so "limit after the outer filter" could look useful. The class is @lucene.experimental, and explain() is a development aid that is normally called on hits.

Why it fails: one query on one index gives different answers depending on things that must be transparent: clause costs (one block: 0 hits; two blocks: b), query caching (the join cached: 0 hits) and sort skipping (a plain sorted search puts c1-3000 first). No documentation could describe that. "Limit after the filter" holds only when the filter happens to lead. The advance() contract is not optional, @lucene.experimental is about API stability, and explain() is wrong for the query alone. Verdict: not intended.

Two fixes were built and run; both make advance() return exactly what a nextDoc() loop returns for a finite limit and leave the default limit's code path unchanged.

For a finite limit, advance(target) computes the first document of the target's block, parentBits.prevSetBit(target - 1) + 1. If that lies after the current child, it moves the child iterator there with one advance, aligns the parent, resets the count and counts the child it lands on as the block's first; then it steps with nextDoc() until it reaches target (+38 lines in ParentsChildrenBlockJoinQuery.java).

if (childLimitPerParent != DEFAULT_CHILD_LIMIT_PER_PARENT) {
  int blockStart = target >= parentBits.length() ? target
      : target == 0 ? 0 : parentBits.prevSetBit(target - 1) + 1;
  if (blockStart > childDoc) {
    childDoc = childIt.advance(blockStart);   // skip whole blocks
    childDocCount = 0;
    // ... align parent and child, scores, childDocCount++
    if (childDoc >= target) return childDoc;
  }
  int doc;
  while ((doc = nextDoc()) < target) {}    // count inside the block
  return doc;
}

Trade-offs

• Inside the target's block it steps child by child, at most childLimitPerParent counted children before it moves on to the next parent; blocks before the target's block are still skipped with one advance.
• 38 lines instead of 7. A reviewer may want the original's childDoc <= parentDoc ? parentIt.nextDoc() : parentIt.advance(childDoc) guard (:359-363) mirrored where the fix calls parentIt.advance(childDoc); it only matters if the child query matched a parent document.
• No benchmark was run.

What the checks validated

• Scratch worktrees of 645d4fe14a20, JDK 25: the minimal test fails on stock and passes with the fix (gradle with assertions on, the standalone runner with them off).
• The whole lucene/join module with the fix and the test: 105 tests in 17 suites, 3 skipped, 0 failures, assertions on and off.
• :lucene:join:check (google-java-format, ecjLint, forbiddenApis, tests): BUILD SUCCESSFUL; the formatter leaves the fix unchanged.
• Earlier, by the hunt: 0 mismatches in the bounded-exhaustive model (up to 7 documents); an independent verifier's 4 tests pass; the sorted-search probe returns c0-0 to c0-9, and its 1001+ total is consistent with skipping still active.
• Not run: the full Lucene suite, nightly tests, benchmarks.

For a finite limit, advance(target) runs the DocIdSetIterator#advance reference loop (+7 lines; the sketch of the two hunt units that found the bug).

if (childLimitPerParent != DEFAULT_CHILD_LIMIT_PER_PARENT) {
  // The limit counts the matching children of a block from its first child, so the
  // children between the current doc and the target must be counted, not skipped.
  int doc;
  while ((doc = nextDoc()) < target) {}
  return doc;
}

Trade-offs

Obviously correct, but a finite limit then never skips: a sparse filter leading the conjunction makes the join walk all its matches up to each target (bounded by the join's own cost, matching parents x limit).

What the checks validated

• The minimal test passes with it (gradle and the standalone runner, assertions on); the whole lucene/join module: 105 tests, 3 skipped, 0 failures (assertions on).
• Earlier, by the hunt: 0 mismatches in the bounded-exhaustive model; the 8 upstream tests pass; on the 10.4.0 jars the class with only this change passes.
• Not run: the module with assertions off, :lucene:join:check, benchmarks.

Leave the code and say in the javadoc which N children are returned depends on the caller.

Trade-offs

The answer would depend on clause costs, caching and sort skipping, and explain() would stay wrong for the query alone; no check supports it.

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier), on the stock main jar.

• First signal (2026-10-26). A hunt unit's explain-vs-hit check over block-join indexes (oracle: explain(doc).isMatch() equals "doc is a hit") reported a non-hit child explained as a match; reading advance() found the cause and a probe confirmed the conjunction effect. A second unit found the same root cause the same day, by reading the iterator and with its own advance-vs-nextDoc and FILTER-conjunction checks; its candidate was withdrawn as a duplicate.
• Widened by the adjudication unit (2026-10-29). A differential check against an independent reference join written from the class javadoc: every block layout of up to 7 documents (10,922 indexes), every child/parent match pattern, limits 1, 2, 3 and MAX, with oracles for nextDoc/count, a fresh advance to every target, nextDoc then advance, advance chains, single-document FILTER conjunctions, MUST_NOT and explain. 11,180 mismatches in 1,683,032 checks; 0 for MAX; 0 with either fix.
• Then reduced to one five-document JUnit, reviewed by cross-model reviewers and verifiers (see the checks below).