Intervals.notContainedBy over an OR keeps matches that lie inside one of the OR's clauses but not another

Intervals.notContainedBy(small, big) returns the intervals of small that do not appear within intervals of big. When big is an Intervals.or(...) that splits into two or more groups (in practice at least two distinct clauses, one of them longer than one position: a phrase, ordered, extend, a multi-word synonym that keeps the original token), the default disjunction rewrite of LUCENE-8477 pulls the OR out of the excluded side and ORs one filter per clause. That computes "not inside B1, or not inside B2" where the operator means "not inside B1 and not inside B2", so an interval inside one clause is still returned by the other clause's filter. "york, but not in new york or york city" returns 3 documents instead of 1, and adding a clause to the exclusion adds hits. Chained filters, or or(false, ...), give the documented answer. It is silent, needs no configuration, is reachable from the flexible query parser and through a multi-word synonym that keeps the original token, with no user-written OR. It is in every release from 8.1.0 to 10.6.0 and on main (8 of them run, the rest by git ancestry, 10.6.0 by reading); 8.0.0 gives the documented answer.

• Interval: the range of positions [start, end] where an IntervalsSource matches in a document. york in "i love new york" is [3,3]; phrase(new, york) is [2,3].
• notContainedBy(small, big): keeps each interval of small that does not lie inside any interval of big. Its javadoc: "Returns intervals from the small IntervalsSource that do not appear within intervals from the big IntervalsSource" (Intervals.java:539-540).
• Disjunction rewrite (LUCENE-8477, on by default): operators that are sensitive to internal gaps pull an OR among their sources to the top, FUNC(a, or(x, y)) => or(FUNC(a, x), FUNC(a, y)) (Disjunctions.java:28-31, class note Intervals.java:47-54), so that a longer clause is not "minimized away". It is exact where OR distributes: containedBy(small, or(B1, B2)) is containedBy(small, B1) or containedBy(small, B2). Intervals.or(false, ...) turns it off.

1. Intervals.notContainedBy calls NotContainedByIntervalsSource.build (Intervals.java:545-547), which returns Intervals.or(Disjunctions.pullUp(subtrahend, s -> new NotContainedByIntervalsSource(minuend, s))) (NotContainedByIntervalsSource.java:27-30).
2. Disjunctions.pullUp (Disjunctions.java:66-73) splits the excluded OR with splitDisjunctions (:79-95): all clauses with minExtent() == 1 go into one group, every other clause (in practice a longer one) into its own group. An OR with a single distinct clause has already been collapsed to it (DisjunctionIntervalsSource.java:45-49). With two or more groups, build makes one filter per group and ORs them.
3. An OR returns an interval when any branch returns it. A branch filters against one group only. When that group does not occur in the document, RelativeIterator.reset marks it absent (RelativeIterator.java:58-61) and the filter returns the small source's intervals unchanged (NotContainedByIntervalsSource.java:73-75); when it has no iterator in the segment at all, DifferenceIntervalsSource.java:44-47 does the same. So doc 0's york, removed by "not inside new york", comes back through "not inside york city".
4. The operator needs the intersection of the filters (for clauses that do not nest, De Morgan: not (inside B1 or inside B2) = not inside B1 and not inside B2); the built query computes their union.
5. The other containment operators pull an OR up only from positive positions, where OR distributes: containedBy and containing from their big side, notContaining from its minuend, the side it keeps (ContainedByIntervalsSource.java:28-30, ContainingIntervalsSource.java:31-33, NotContainingIntervalsSource.java:27-30). notContainedBy alone pulls one out of the side it subtracts.

A york inside both phrases ("new york city") stays excluded. An OR of single terms, or(term(new), term(city)), is built as one filter, NOT_CONTAINED_BY(york,or(city,new)), and is correct. Main with -ea and -da, and 10.5.2.

• The natural use: "term X, but not as part of phrase P1 or P2". A Stack Overflow question asks for exactly this with span queries.
• Executed trigger paths (main, also 10.5.2): a user-written Intervals.or of phrases; the flexible StandardQueryParser strings fn:notContainedBy(b fn:or("a b" "b c")), parsed to or(NOT_CONTAINED_BY(b,BLOCK(a,b)),NOT_CONTAINED_BY(b,BLOCK(b,c))), and fn:notContainedBy(york fn:or("new york" "york city")); with no user-written OR, Intervals.analyzedText("nyc", ...) with a query-time multi-word synonym that keeps the original token (nyc => nyc, new york city), which builds or(BLOCK(new,york,city), nyc); an OR of single terms wrapped in extend(..., 0, 1). A replace-only synonym (nyc => new york city) builds BLOCK(new,york,city) with no OR and is correct.
• Not affected: an OR of single terms only (one group); Intervals.notWithin (by code reading: no pull-up, Intervals.java:491-495); containedBy, containing and notContaining.
• Downstream, read only (nothing run): Elasticsearch and OpenSearch map the intervals query's not_contained_by filter to Intervals.notContainedBy and any_of to the rewriting Intervals.or; the Solr 10.1 reference guide documents an intervals parser with any_of and not_contained_by.
• Default vs opt-in: no configuration needed. The plain-Java diagram probe uses the default codec, IndexWriterConfig and IndexSearcher; the JUnit fails under the test framework's randomized codecs; assertions on or off. The intervals API itself is opt-in and less used than boolean and phrase queries, and its package is marked experimental (package-info.java:21).
• Scale: no minimum; two or three short documents suffice (every run used one segment; multi-segment indexes were not run). A document is wrongly returned when every occurrence of the small term lies inside at least one group and at least one occurrence lies outside at least one group. With two phrases, a document is excluded only where every occurrence lies inside both phrases at once; how much that changes real result sets was not measured.
• Damage: silent over-matching and inflated counts; adding a clause to the exclusion adds hits. Every branch returns only intervals of the small source, so the extra hits stay within the small source's hits. The same source drives matches(), so highlighting sees the same extra intervals (by code reading, not tested). No exception, crash or index damage.
• How likely: plausible (a judgement, not measured): ordinary text triggers it, but notContainedBy over an OR of phrases is a niche query shape.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: hits of or(NOT_CONTAINED_BY(a,BLOCK(c,a)),NOT_CONTAINED_BY(a,b)) 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.apache.lucene.queries.intervals.TestNotContainedByOrRewrite.testTermInsideOneClauseOfOrIsExcluded(TestNotContainedByOrRewrite.java:45)

• Contracts. Intervals.notContainedBy (Intervals.java:539-540); the package doc, "Returns intervals that are not contained by another interval" (package-info.java:60-61); the flexible parser doc, "Matches intervals of the source that are not contained by intervals of the reference" (queryparser/.../nodes/intervalfn/package-info.java:596). None makes an exception for an OR.
• The rewrite is the accuracy mode. "if you care more about speed than about accuracy you can use the or(boolean, IntervalsSource...) factory method to prevent rewriting" (Intervals.java:53-54); or(false, ...) "may run more efficiently, but can miss valid hits due to minimization" (Intervals.java:130-131); CHANGES for LUCENE-8477: "Interval disjunctions could miss valid hits ... This behaviour can be disabled if users are more interested in speed rather than accuracy of matching" (lucene/CHANGES.txt:6486-6490).
• Wrong interval matches are bugs: LUCENE-10140, "Fix cases where minimizing interval iterators could return incorrect matches" (lucene/CHANGES.txt:4974-4975).
• Tests. TestDisjunctionRewrites#testNotContainedBy (TestDisjunctionRewrites.java:201-213) asserts the OR-of-filters structure only, with the comment "the 'big' interval should not be minimized, the 'small' one should be". No upstream test checks the matches of notContainedBy with an OR as the big source (TestIntervalQuery#testNotContainedByQuery uses an unordered big source).
• History. 7.4.0-8.0.0 filtered against the whole OR and give the documented answer. LUCENE-8477 aimed at matches missed through minimization (#9243 asked for "not losing matches by adding disjunctions"); its issue and PR never discuss the negated side. The rewrite's author later said intervals rewrite disjunctions "so that queries behave as your or I would expect them to" (#10244).
• Monotonicity. Adding a clause to an exclusion can only remove hits; here it adds them.

The strongest case for "intended" (rated moderate by the refute review and the "works as designed" review, weak by the devil's-advocate verifier): the pull-up is deliberate LUCENE-8477 code, TestDisjunctionRewrites#testNotContainedBy pins exactly this OR shape, the package is experimental, and users can opt out with or(false, ...).

Why it fails: the test checks structure, not matches, and its stated goal (do not minimize the big side) is also met by chaining the same groups. The "pull up the big side" rule is sound for notContaining, where the big side is the one kept, and wrong for notContainedBy, where it is subtracted. No javadoc, CHANGES, MIGRATE entry or discussion gives notContainedBy over an OR the meaning "outside any one clause". "Experimental" allows API changes, not wrong results. The opt-out is documented as the less accurate mode, and here it is the accurate one. The repro's clauses do not nest, so nothing is minimized away and 8.0.0 gave the expected answer. Verdict: a defect.

One fix was built and validated in a scratch worktree at ea57360912ed; one alternative was run to show why it is not enough. Workaround in every affected release: nest notContainedBy once per clause.

Keeps the pull-up groups, so the big side is still not minimized (the rewrite's stated goal), and requires an interval to pass every group's filter: outside B1 and outside B2. TestDisjunctionRewrites#testNotContainedBy changes to expect notContainedBy(notContainedBy(or(phrase("a", "b"), term("a")), term("d")), phrase("c", "d")). Diffs: chain-filters.diff, structural-test-update.diff, fix-with-test.diff (applies cleanly at ea57360912ed).

static IntervalsSource build(IntervalsSource minuend, IntervalsSource subtrahend) {
  // An interval of the minuend is excluded if it lies inside any disjunct of the subtrahend, so
  // chain one filter per disjunct: OR-ing the filters would keep an interval that lies outside
  // just one of them.
  IntervalsSource result = minuend;
  for (IntervalsSource disjunct : Disjunctions.pullUp(subtrahend, Function.identity())) {
    result = new NotContainedByIntervalsSource(result, disjunct);
  }
  return result;
}

Trade-offs

• The built query's structure, toString and equals change. An OR of filters compared its branches as a set (DisjunctionIntervalsSource.java:108-118); a chain compares in order, and that order comes from a hash set, so two queries that differ only in clause order might not be equal. That matters to anything that relies on equals and hashCode (the query cache, deduplication, structural tests). Not tested.
• Cost: one filter per group as before, but the small source is iterated once through nested filters instead of once per OR branch. No benchmark was run.
• Zero groups (by code reading, not tested): notContainedBy(small, or()) with an empty rewriting OR gives no matches today and would return small unchanged with the fix.
• Every validation run used a single segment.
• Not reviewed by a committer.

What the checks validated

• Stock: the doc's test fails 2 of 2 and the nested-clause probe 1 of 1; with the fix all pass.
• org.apache.lucene.queries.intervals.* (with the updated structural test, the new test and the probe), TestStandardQP, TestStandardQPEnhancements and TestMatchHighlighter: 12 classes, 195 tests, 0 failures, assertions on and off.
• The whole queries module: 53 classes, 515 tests, 0 failures, 5 skipped.
• :lucene:queries:check -x test passes (google-java-format, ecjLint, forbiddenApis).
• Every earlier hunt test with the patched class shadowed, fresh seeds: the finder's 2, the independent reproducer's 3 + 2 (parser string, extend), the devil's advocate's 4 (synonym, parser), the GPT-5.6 review stage's 2 (including the nested case) and the security probe's 4: all pass with -ea, and the security probe also with -da.

return new NotContainedByIntervalsSource(minuend, subtrahend); (option-no-pullup.diff).

Trade-offs

Minimizes the big side again: or("x y z", y) reduces to y, so x inside "x y z" is kept, the gap LUCENE-8477 set out to close. Simpler, but not enough.

What the checks validated

Passes the doc's 2 tests; fails the nested-clause probe: NOT_CONTAINED_BY(x,or(BLOCK(x,y,z),y)) expected:<1> but was:<2>.

Say in the javadoc that notContainedBy over a split OR means "outside at least one clause".

Trade-offs

Contradicts the existing javadoc, the package and parser docs, and makes exclusions non-monotonic. Not recommended.

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier; no model checker, SMT solver or prover).

• In a hunt unit (spans and intervals, 2026-10-26) the finder first suspected the defect by reading the callers of pullUpDisjunctions while writing IvRef, an exact reference semantics for interval operators.
• The harness IvTV runs the real interval sources of the main jars against IvRef over every document of up to 6 positions over {a, b, c} (and up to 4 positions with stacked tokens), for every interval expression of 1-2 operator levels: 1,401,702,324 checks on separate build machines.
• Its rewrite check for a negated filter over an OR (the reference takes the excluded side as the plain union of the clauses) failed 300,120 of 1,436,292 checks on stock main and 0 of 248,076 with the fix shadowed, in a smaller run (287,753,697 checks in all). That count also includes nesting shapes, so it is the signal, not a measure of the regression.
• The finder then wrote a deterministic public-API JUnit; the independent checks, history sweep, prior-report search and security screen followed.