Monitor reports a query with one required clause and minimumNumberShouldMatch=1 that matches nothing

The Monitor (lucene-monitor) matches documents against stored queries. To select candidate queries quickly, its default QueryDecomposer splits a registered query into parts, stores each part under the query's id and later runs the parts instead of the query. For a BooleanQuery it keeps the query whole only when minimumNumberShouldMatch is above 1, when it has more than one distinct required clause, or when one required clause comes with a SHOULD clause that decomposes to something. Otherwise it decomposes its lone MUST or FILTER clause instead (plus the MUST_NOT exclusions), which is not valid in general when minimumNumberShouldMatch is above 0. A query with one required clause, minimumNumberShouldMatch=1 and no SHOULD clause that decomposes to a part, such as "alpha AND at least one of []" = (+text:alpha)~1, matches nothing in core (it rewrites to MatchNoDocsQuery, and core's testNoOptionalButMin2 asserts 0 hits), but the Monitor reports it for every document that contains alpha. Only extra matches occur, in every release with the module (8.2.0 to 10.6.0, 10.6.0 by reading) and on main. Keeping such a query whole (one condition) fixes it, and the whole monitor module passes with that change.

• Monitor (lucene-monitor, org.apache.lucene.monitor): stores queries and reports which of them an incoming document matches. A presearcher first selects candidate queries by their terms; the selected queries are then run against the document.
• QueryDecomposer: splits a registered query into parts that are indexed and run separately ("Split a disjunction query into its constituent parts"). Each part keeps the registered query's id, and a match of any part reports that id.
• minimumNumberShouldMatch (shown as ~1): how many SHOULD clauses must match. "If this method is used, then the specified number of clauses is required." With 1 and no SHOULD clause, nothing can match.

1. QueryDecomposer.decomposeBoolean returns the query whole if minimumNumberShouldMatch > 1 (QueryDecomposer.java:78).
2. It sorts the clauses into required (MUST or FILTER, a HashSet), exclusions (MUST_NOT) and the decompositions of the SHOULD clauses (:80-91). It returns the query whole if there are two or more distinct required clauses, or one plus a non-empty SHOULD decomposition (:93-95).
3. Otherwise, with one required clause, it decomposes that clause instead, "If we only have a single MUST clause and no SHOULD clauses" (:97-101), and adds the exclusions back to every part (:103-116). The rewrite is not valid in general when minimumNumberShouldMatch is above 0: with 1, the "at least one" condition is gone.
4. QueryCacheEntry.decompose stores each part under the parent's id (QueryCacheEntry.java:51-60), and Monitor.StandardQueryCollector runs the part as the final matcher (Monitor.java:293-299). So the wrong part is a wrong final answer, not just an extra candidate.

The trigger is exactly: minimumNumberShouldMatch 1, one distinct MUST/FILTER clause, and no SHOULD clause that decomposes to a query (none, an empty BooleanQuery, or a pure-negative one), with any MUST_NOT clauses. Such a query also leaks from inside a SHOULD disjunction, a DisjunctionMaxQuery or a BoostQuery of any boost, because those are decomposed into their children. The BooleanQuery with this shape matches nothing, but a registered query that contains it need not: text:zzz ((+text:alpha)~1) correctly matches documents with zzz, and the Monitor also reports it for "alpha beta".

Document {text: "alpha beta"}, StandardAnalyzer, IndexSearcher on a one-document index vs Monitor.match with QueryMatch.SIMPLE_MATCHER:

In the finder's bounded comparison (46,233 queries with up to three leaves, 40 tiny documents), 56,903 of the 1,849,320 (query, document) checks were false positives in each of 202 runs (200 presearcher configurations, two of them repeated end to end), and 0 were misses; with the fix, the three end-to-end re-runs had 0 and 0.

• Who. lucene-monitor users with the default QueryDecomposer (MonitorConfiguration.java:38) who register such a query: built with BooleanQuery.Builder (one SHOULD clause per list element and setMinimumNumberShouldMatch(1)), or from an XML query parser template, which takes a minimumNumberShouldMatch attribute. The list is empty, for example a subscriber with no groups or a filter with no selected values.
• Default vs opt-in. Default Monitor configuration and decomposer; lucene-monitor is an optional module. The checks ran the simple matcher only; by reading, all built-in matchers are affected, because each is handed the stored part to run. Read-only Monitors decompose the stored query again at match time with the same decomposer.
• Parsers. The classic, multi-field and simple query parsers cannot express minimumNumberShouldMatch (0 false positives in 1,500 random strings each). The flexible StandardQueryParser can, with @N, which it documents for pure disjunction groups only; (+alpha -omega)@1 still reaches the bug.
• Scale. None needed: one query and one document, deterministic, with assertions on and off.
• Effect. Silent extra matches, caused by a BooleanQuery that matches nothing in core (a registered query that contains one can still match other documents correctly); nothing fails or is corrupted, and IndexSearcher is unaffected.
• How likely. Rare: it needs exactly minimumNumberShouldMatch 1 with one required clause and an optional part that decomposes to nothing (typically an empty list). The two public Monitor users found parse queries with the classic parser, and no report was found in the public sources searched.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<0> but was:<1>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.monitor.TestMonitorMinShouldMatchSingleRequiredClause.testRequiredClauseWithMinShouldMatchAndNoShouldClause(TestMonitorMinShouldMatchSingleRequiredClause.java:43)

• BooleanQuery contract. BooleanQuery.java:50-62: "Specifies a minimum number of the optional BooleanClauses which must be satisfied ... If this method is used, then the specified number of clauses is required." rewrite returns MatchNoDocsQuery("SHOULD clause count less than minimumNumberShouldMatch") (:570-576); its one-clause shortcut fires only for 0, or for 1 with a SHOULD clause (:278-297).
• Core tests. TestBooleanMinShouldMatch.testNoOptionalButMin2 builds exactly one MUST clause with minimum 1 and asserts 0 hits; testNoOptionalButMin does the same with two MUST clauses.
• Monitor contract. The package javadoc: the simple matcher "just returns the set of query ids that a Document has matched"; candidates "are then run against the document", so the Monitor "can avoid running queries that have no chance of matching". QueryDecomposer: parts "can be indexed and run separately", which needs the parts together to match what the query matches.
• The code already cares. The guard at QueryDecomposer.java:78 keeps minimum > 1 whole; the comment at :97-98 ("a single MUST clause and no SHOULD clauses") states a rewrite that is not valid in general for a minimum above 0. No monitor test covers minimum 1 with a required clause.
• Precedent. LUCENE-1134 (2008): core BooleanQuery.rewrite reduced a single-clause query to its clause while ignoring the minimum; fixed as a bug (CHANGES 2.4.0: "only optimize a single clause query if minNumShouldMatch<=0"), adding testNoOptionalButMin2.
• History. In the predecessor library (Luwak), the decomposer first kept any query with a MUST clause whole, where the minimum > 1 guard was enough; a 2014 commit ("Allow single-valued conjunctions to be decomposed") added the single-MUST branch without revisiting the guard. Luwak treated a lost minimum elsewhere as a bug (#122 / #123). No by-design discussion was found.

The strongest works-as-designed case (the devil's advocate, the cross-model reviewer and the adjudication): the triggering BooleanQuery matches nothing, so it is degenerate input and arguably a caller mistake; the decomposer is a documented, pluggable heuristic; the comment shows the single-MUST split was deliberate; and the classic parser cannot build the shape, while the flexible parser documents @N for pure disjunctions only.

Why it fails: nothing documents that decomposition may change which queries match or that registered queries must be pre-rewritten, and the default Monitor contradicts IndexSearcher on the same query and document. The registered query need not be degenerate: nested in a disjunction, a parent that can match gains extra matches. The shape is legal and tested in core and comes naturally from code that adds one SHOULD clause per list element; in LUCENE-10618 @jpountz noted that such queries "can also happen to non-degenerate queries if some SHOULD clauses rewrite to a MatchNoDocsQuery" (about core's rewrite; the Monitor decomposes the query before any rewrite). The split's premise is false whenever the minimum is above 0, and core fixed the identical reduction as a bug. A pluggable decomposer is a workaround, not a contract. Verdict: not intended; a defect since the import. Expect pushback on severity, not on correctness; maintainers may also prefer another fix, such as rejecting such queries at registration.

One fix was built and run in a scratch worktree at a9779ef3c193; a no-change workaround was run on stock main. The alternatives were not run.

The finder's one-condition fix with reworded comments, plus testSingleRequiredClauseWithMinShouldMatchIsNotDecomposed in TestQueryDecomposer (MUST; FILTER with an exclusion; nested in a disjunction, which is still split). +8/-4 lines in QueryDecomposer.java (comments included), +29 in the test.

// More than one MUST clause, or a single MUST clause with disjunctions, or a single MUST
// clause with minimumNumberShouldMatch > 0: then the SHOULD clauses are required, and with no
// SHOULD clause that can match, the query matches nothing
if (mandatory.size() > 1
    || (mandatory.size() == 1
        && (subqueries.size() > 0 || q.getMinimumNumberShouldMatch() > 0)))
  return Collections.singleton(q);

Trade-offs

• Only the decomposition of a BooleanQuery that matches nothing changes (and so the parts of a registered query that contains one); minimum 0 and the shapes already kept whole are untouched. Cost: expected to be small for this rare shape (when selected, the whole query is rewritten and run instead of the bare required clause); not benchmarked.
• Upgrade note (read, not run): the stored parts, and so the cache ids, of an affected query change. A writable Monitor re-decomposes stored queries when it opens a persisted index and skips index entries with unknown cache ids; a read-only Monitor over an index written before the fix looks the old cache id up in a fresh decomposition and throws "Cached queries not found" if it is gone. That needs an affected query whose required clause split into two or more parts, such as (+(a b))~1; re-registering such queries clears it, but only through a writable Monitor over the same index (a read-only Monitor cannot commit). Until then a writable Monitor keeps the old index rows, looked up by their old cache ids, so if the part count of such a query changed, the other parts of a parent query can be missed.

What the checks validated

Gradle in a scratch worktree of a9779ef3c193 (as its script states; the repro runner records that commit for the same primary-test result), seed DEADBEEF: the whole :lucene:monitor:test with the 5 repro classes added, 37 classes, 193 tests, 0 failures, 1 skipped (a @Nightly test), with assertions on and off; all 10 repro tests that fail on stock pass. :lucene:monitor:check -x test with the fix and the primary test (google-java-format, ecj lint, forbidden APIs): BUILD SUCCESSFUL. Earlier, the finder's bounded comparison with the fix: 0 false positives and 0 misses.

if (msm > 1 || (msm > 0 && <any MUST or FILTER clause>)) return Collections.singleton(q);

Trade-offs

Same results by reading. It scans the clauses once more but returns such a query before decomposing its SHOULD clauses, so its cost compared with the recommended fix is not established. Not run.

Return an empty decomposition when the minimum cannot be met.

Trade-offs

Cheaper, but it must re-implement core's rules for which SHOULD clauses can match (empty and pure-negative nested queries) and changes what getDisjunctCount() reports. A query with no part also disappears from getQueryIds() and getQueryCount(), and updating an existing id to no part leaves its old index rows in place (WritableQueryIndex.java:107-127, 185-203). Keeping the query whole lets core decide. Not run.

register throws for a BooleanQuery that cannot match.

Trade-offs

An API decision for the maintainers. It has to find such a node anywhere in the query, and it would also refuse a parent such as text:zzz ((+text:alpha)~1), which can match. Not run.

A QueryDecomposer subclass whose decomposeBoolean returns the query whole when getMinimumNumberShouldMatch() > 0 and it has a MUST or FILTER clause, else calls super, set with new MonitorConfiguration().setQueryDecomposer(...). No Lucene change.

Trade-offs

The primary test's six checks pass with it on stock main. Every application has to know about it; not registering "X AND at least one of []" at all also avoids the bug (not run).

Method: bounded-exhaustive translation validation against a reference semantics (the hunt's "semi-formal" tier).

• The finder's harness enumerated every distinct query of a grammar with at most three leaves (BooleanQuery with MUST, SHOULD, FILTER and MUST_NOT clauses and minimumNumberShouldMatch 0 to 2, DisjunctionMaxQuery, ConstantScoreQuery, BoostQuery, nested): 46,233 queries, on 40 documents (token sequences over three terms, length 0 to 3).
• For each of 200 presearcher configurations it registered the queries in a Monitor, recorded which parts Monitor.match selects and runs (a recording matcher), evaluated each such part with IndexSearcher on the document, and compared the result with the exact answer from IndexSearcher for the whole query: 1,849,320 checks per run. Two of the configurations were also run end to end through Monitor.match with the simple matcher, asserting that both ways agree (202 runs in all).
• Result: 56,903 false positives in every run and 0 misses. Two deliberately broken variants (a presearcher that drops terms, a decomposer that drops exclusions) were caught, which shows the comparison is not vacuous.
• With the one-condition decomposer fix, the end-to-end re-runs (two presearcher configurations and a control) had 0 false positives and 0 misses. (The stock summary also lists a prototype control decomposer with 1,464 false positives: an earlier version of that prototype, whose witness, a pure-negative SHOULD clause, the current version keeps whole; on the stock jar the current version gives 0.)
• The finder then wrote the public-API JUnit test, and independent checkers reproduced it.