Multi-dimensional PointInSetQuery skips segments that contain matching points

PointInSetQuery finds documents whose single or multi-dimensional point is in a set, and is meant for subclasses. Its constructor requires the packed points in sorted order, which it enforces with BytesRef.compareTo: an unsigned lexicographic order over the whole packed value, in which dimension 0 decides first. Since 10.3.0 (GITHUB#14268, an optimization) the constructor keeps the first and the last point of that order as lowerPoint and upperPoint (PointInSetQuery.java:110-114, :129-134), and scorerSupplier returns null for a segment as soon as, in any dimension, lowerPoint is above the segment's maximum or upperPoint below its minimum (:187-201). Those two points bound only dimension 0. For the set {(0,1), (1,0)} lowerPoint is (0,1); a segment whose only document is at (1,0) has maximum 0 in dimension 1, and 1 > 0, so the whole segment is skipped and count() is 0 instead of 1. Only application-written subclasses with two or more dimensions are hit; every production in-tree factory is 1-D. Used as a MUST_NOT clause or in IndexWriter#deleteDocuments(Query), the skipped segment fails open. Affects 10.3.0 through 10.6.0 (10.6.0 by reading) and main.

• Point field: a field indexed with IntPoint, LongPoint and so on; a point has one value per dimension, for example new IntPoint("p", 1, 0) is the 2-D point (1,0). Each segment records, per dimension, the smallest and largest value of the field (PointValues#getMinPackedValue/getMaxPackedValue: "minimum value for each dimension, packed", PointValues.java:473-481).
• PointInSetQuery: "Abstract query class to find all documents whose single or multi-dimensional point values ... is contained in the specified set"; "This is for subclasses" (PointInSetQuery.java:43-48). The set arrives as a stream of packed points that "must be in sorted order" (:74).
• Lexicographic order: points compared byte by byte over the whole packed value, so dimension 0 decides first and dimension 1 only breaks ties. (0,1) sorts before (1,0) because 0 < 1 in dimension 0.

1. The constructor copies the first point into lowerPoint (PointInSetQuery.java:110-114), checks every further point with BytesRef.compareTo against the previous one (equal: skipped; smaller: "values are out of order", :116-121) and copies the last point into upperPoint (:129-134).
2. scorerSupplier, after the dimension and byte-width checks (:168-185): if the segment has documents, then for every dimension i it returns null when lowerPoint[i] > max[i] or upperPoint[i] < min[i] (:187-201).
3. In lexicographic order the first point has the set's smallest dimension-0 value and the last point the largest, so dimension 0 is checked correctly. In a later dimension the first point's value can be above the set's minimum and the last point's value below its maximum. The check then rejects a segment that holds a set point.
4. A null ScorerSupplier means "nothing matches in this segment": count() and search() get no hits from it; BooleanWeight drops a null clause that is not required (BooleanWeight.java:299-306), so a MUST_NOT clause excludes nothing there; delete-by-query runs only when the weight returns a scorer (FrozenBufferedUpdates.java:400-402), so deleteDocuments(Query) deletes nothing there.
5. The same per-dimension loop in PointRangeQuery (PointRangeQuery.java:263-275), which #14268 followed, is correct: a range's lowerPoint and upperPoint are real per-dimension bounds.

One segment, one document at (1,0); segment minimum = maximum = (1,0).

Shadow builds of main that remove the early exit, or keep it for dimension 0 only, make every test pass, which isolates the cause.

• Who is exposed. Applications that subclass PointInSetQuery through its protected constructor with numDims >= 2, the extension point the javadoc names ("This is for subclasses"), for example a lookup of a set of (entity, day), (x, y) cell or (category, label) pairs on a multi-dimensional IntPoint or LongPoint field.
• Not exposed. Every production in-tree factory passes numDims = 1: IntPoint, LongPoint, FloatPoint, DoublePoint, BinaryPoint and InetAddressPoint.newSetQuery, JoinUtil, and the sandbox BigIntegerPoint and HalfFloatPoint. The only in-tree multi-dimensional factory is the private test helper TestPointQueries#newMultiDimIntSetQuery. A read-only code search of the default branches of Elasticsearch, OpenSearch and Solr found no multi-dimensional subclass (only that summary was kept, not the search output); plugins and private code were not checked.
• Default or opt-in. Default IndexWriterConfig, codec and searcher; one document is enough. The opt-in is the application-written subclass of a @lucene.experimental class.
• When it fires. On a segment, when the set's lexicographically first point has a value in some dimension k >= 1 above the segment's maximum in k, or its last point a value below the segment's minimum in k, while the segment holds a set point. That needs segments that are narrow in a later dimension: small segments (near-real-time readers, frequent flushes), ingestion or index sorting by a later dimension (time series), or merges after deletes.
• How often (measured on small synthetic indexes, not in the field). 2,000 (entity, day) documents indexed in day order and committed every 200: 43 of 200 random sets of 1-8 indexed points return wrong counts. The same with uniform random (x, y): 0 of 200. Deliberately tiny segments: 109 of 300 random 2-D and 150 of 300 random 3-D set queries wrong with one seed (109-154 and 125-159 of 300 over the five seeds run). For a given index and set it is deterministic (20 of 20 iterations).
• What you see. No error. Whole segments contribute no hits, and adding a point to a set can remove hits that the smaller set returned. Positive use only loses hits; negated use fails open (Downstream note). No hang, resource growth, crash or index damage was observed, and the early-return path suggests none.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: hits for the set {(0,1), (1,0)} expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.search.TestPointInSetQueryMultiDim.testSetContainingIndexedPoint(TestPointInSetQueryMultiDim.java:42)

• Contract. Class javadoc: "Abstract query class to find all documents whose single or multi-dimensional point values, previously indexed with e.g. {@link IntPoint}, is contained in the specified set." and "This is for subclasses and works on the underlying binary encoding" (PointInSetQuery.java:43-48). Besides the field shape (bytesPerDim, numDims and each packed point's length, checked at :76-108), the only precondition is the one the constructor javadoc states, "The {@code packedPoints} iterator must be in sorted order" (:74); it is enforced (:116-121) and met by the repro.
• An optimization. "GITHUB#14268: PointInSetQuery early exit on non-matching segments. (hanbj)" is listed under 10.3.0 "Optimizations" (lucene/CHANGES.txt:1597, :1605); an optimization must not change results.
• Upstream tests. TestPointQueries asserts exact multi-dimensional set results (testBasicMultiDimPointInSetQuery, testBasicMultiValueMultiDimPointInSetQuery, testManyEqualValuesMultiDimPointInSetQuery, :1560, :1582, :1610). The first two use multi-point sets, such as {(-7,-7), (17,42)}, which are ordered alike in every dimension, where the first and last points happen to be per-dimension bounds; the third uses one-point sets only. #14268's own test testPointInSetQuerySkipsNonMatchingSegments (:2566) uses 2-D sets of one point only. With the fix every test in lucene/core passes, so no test pins the current behaviour.
• History. #14268's description gives the premise: "the data in the packedPoints parameter is returned in order, so the maximum and minimum values can be determined". That holds for dimension 0 only. Its review covered tests, asserts, the docCount == 0 check and the CHANGES entry, not sets of several multi-dimensional points. It followed the PointRangeQuery early exit (#13033), where the bounds are real per-dimension bounds. 10.2.2 and older, without the early exit, return the right count.

The strongest case for "works as designed or misuse" (built by the devil's advocate and checked by the adjudication): the class is @lucene.experimental; every in-tree factory is 1-D; the test helper's comment calls it a "test-only query factory" that could be "graduated" "if there is demand for real usage" (TestPointQueries.java:1491-1493); and "sorted order" could be read as sorted in every dimension.

Why it fails: @lucene.experimental covers API stability, not correctness, and nothing documents approximate results. The class javadoc promises multi-dimensional membership and invites subclasses, the scorer has its own numDims > 1 branch, and upstream tests assert exact multi-dimensional results; the comment calls the factory test-only, not multi-dimensional support. The constructor enforces whole-value lexicographic order and accepts {(0,1), (1,0)}, which no order sorts in both dimensions at once, so a per-dimension reading would make ordinary sets illegal, which the constructor does not do. A reviewer from another model family (OpenAI GPT-5.6, reading only) called the intended-behaviour case weak. What remains is a reach argument (few users), not a correctness one.

Option A was validated in a scratch worktree at ea57360912ed (removed afterwards). B and C were run only as shadow classes against the reproducers' tests; D was not built.

While the constructor streams the sorted points, update lowerPoint and upperPoint for every dimension >= 1 with the unsigned minimum and maximum over all set points (Arrays.compareUnsigned, already imported); dimension 0 keeps the first and the last sorted point. scorerSupplier is unchanged. The patch is the finder's, with relative paths; fix-with-test.diff adds the TestPointQueries method. Add a CHANGES entry under Bug Fixes.

diff --git a/lucene/core/src/java/org/apache/lucene/search/PointInSetQuery.java b/lucene/core/src/java/org/apache/lucene/search/PointInSetQuery.java
index 6efe5a9f5d0..90b1b979044 100644
--- a/lucene/core/src/java/org/apache/lucene/search/PointInSetQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/PointInSetQuery.java
@@ -110,8 +110,10 @@ public abstract class PointInSetQuery extends Query implements Accountable {
       if (previous == null) {
         previous = new BytesRefBuilder();
         lowerPoint = new byte[bytesPerDim * numDims];
+        upperPoint = new byte[bytesPerDim * numDims];
         assert lowerPoint.length == current.length;
         System.arraycopy(current.bytes, current.offset, lowerPoint, 0, current.length);
+        System.arraycopy(current.bytes, current.offset, upperPoint, 0, current.length);
       } else {
         int cmp = previous.get().compareTo(current);
         if (cmp == 0) {
@@ -123,14 +125,38 @@ public abstract class PointInSetQuery extends Query implements Accountable {
       }
       builder.add(field, current);
       previous.copyBytes(current);
+      // track the per-dimension bounding box: the sorted order only bounds the first dimension
+      for (int dim = 1; dim < numDims; dim++) {
+        int offset = dim * bytesPerDim;
+        if (Arrays.compareUnsigned(
+                current.bytes,
+                current.offset + offset,
+                current.offset + offset + bytesPerDim,
+                lowerPoint,
+                offset,
+                offset + bytesPerDim)
+            < 0) {
+          System.arraycopy(current.bytes, current.offset + offset, lowerPoint, offset, bytesPerDim);
+        }
+        if (Arrays.compareUnsigned(
+                current.bytes,
+                current.offset + offset,
+                current.offset + offset + bytesPerDim,
+                upperPoint,
+                offset,
+                offset + bytesPerDim)
+            > 0) {
+          System.arraycopy(current.bytes, current.offset + offset, upperPoint, offset, bytesPerDim);
+        }
+      }
     }
     sortedPackedPoints = builder.finish();
     sortedPackedPointsHashCode = sortedPackedPoints.hashCode();
     if (previous != null) {
+      // the first dimension's maximum is the last point in sorted order
       BytesRef max = previous.get();
-      upperPoint = new byte[bytesPerDim * numDims];
       assert upperPoint.length == max.length;
-      System.arraycopy(max.bytes, max.offset, upperPoint, 0, max.length);
+      System.arraycopy(max.bytes, max.offset, upperPoint, 0, bytesPerDim);
     }
     ramBytesUsed =
         BASE_RAM_BYTES

Trade-offs

Sound for every set the constructor accepts (sorted, with any duplicates and any BytesRef offset): a segment is skipped only when the set's bounding box misses the segment's box, and a set point inside the segment lies in both. Keeps the early exit in every dimension. Cost, once at construction: per distinct set point 2 x (numDims - 1) unsigned comparisons of bytesPerDim-byte values and at most as many bytesPerDim-byte copies (the loop does not run for 1-D queries), plus one copy of the first point into upperPoint, also for 1-D; nothing per segment. Memory unchanged (the same two arrays). The two arrays become box corners instead of set points; only the constructor, ramBytesUsed, scorerSupplier and a ramBytesUsed test read them, and that test passes. No benchmark was run.

What the checks validated

• Through gradle at ea57360912ed (main only; the patch was not built against the release branches): the repro fails on stock with assertions on and off and passes with the fix with both.
• With the fix: TestPointQueries 56 tests, 0 failures (2 skipped), assertions on and off; 57 with the new method, which fails on stock; 46 point-related test classes, 344 tests, 0 failures; the whole lucene/core suite, 748 classes, 8,866 tests with assertions on and 8,867 (with the new method) with assertions off, 0 failures (the class counts come from the JUnit XML of the fact check's re-run of the same patch; the gradle logs print totals only); :lucene:core:check -x test (google-java-format, ecj, forbidden APIs) successful.
• Earlier steps: the finder's, the independent reproducer's (6 of 6), the refute reviewer's witness and the security probe's (5 of 5) tests pass with the same patch; the bounded-exhaustive harness finds 0 mismatches in 1,282,176 cases (11,160 on stock).

Limit the loop in scorerSupplier to dimension 0 (i < numDims becomes i < 1).

Trade-offs

Tiny and sound by the same argument as option A's dimension 0 (the first and last sorted points do bound dimension 0), but it drops the pruning on later dimensions that option A keeps, and only the independent reproducer's 6 tests were run with it.

What the checks validated

As a shadow class on main: the independent reproducer's 6 tests pass. The module suite was not run.

Revert the bounds check of #14268.

Trade-offs

Also removes the optimization for 1-D queries, where it is correct. Not recommended.

What the checks validated

As a shadow class on main: the independent reproducer's 6 tests and the finder's test pass.

Skip a segment only if no set point lies inside the segment's per-dimension box.

Trade-offs

Prunes more than a bounding box, but costs up to one box test per set point per segment. Not built or run.

A subclass cannot override createWeight, which builds the check and is final, so the check runs whenever the query itself is executed; a subclass could override rewrite(IndexSearcher), which is not final and which PointInSetQuery does not override, to return the query below instead (not run). For small sets, use a BooleanQuery of SHOULD clauses IntPoint.newRangeQuery(field, p, p), one exact box per point, within the clause limit; or ship a patched copy of the class.

Trade-offs

Slower than a set query for large sets and bounded by the clause limit. Not run as a workaround; the independent reproducer used exactly this OR of exact boxes only as a cross-check of its brute-force counts on main, where it agreed with them.

Method: bounded-exhaustive translation validation, a hunt unit (bulk-overload precondition matrix), 2026-10-26 (the hunt's "semi-formal" tier).

• The harness built every 2-D index of 1-4 documents over {0,1}^2 and every 3-D index of 1-3 documents over {0,1}^3, with maxPointsInLeafNode 1-3 and 4 layouts (11,088 indexes, 1,282,176 query cases), on the stock main jars, and compared each result with a brute-force reference over the stored values. The unit's own bulk-versus-per-document oracle found nothing; the brute-force reference flagged 11,160 mismatches, all multi-dimensional PointInSetQuery set queries. With the fix: 0.
• A z3 model of the check: for (dimensions, set points) = (2,2), (2,3), (3,2) and (3,4), with one-byte dimensions, the shipped check can skip a segment whose box holds a set point (satisfiable, witnesses logged), a per-dimension min/max check cannot (unsatisfiable); a vacuity control is satisfiable and a 1-D control (3 set points) unsatisfiable. Other sizes were not run.
• Then a public-API JUnit, a review by an independent reviewer from another model family (OpenAI GPT-5.6, reading only: real, high), an independent reproducer, a refute-lens review by the same model family (reading only; its "not real, low" was procedural because it could not run code), a devil's advocate, an adjudication, a history sweep, a prior-report search, a security assessment, a registry re-run and an audit. Neither reviewer from the other model family wrote or ran a test of its own; the refute review's wrapper did run the finder's test, which failed.