Set queries miss matches on points fields with more dimensions than index dimensions

A points field can store more dimensions than it indexes ("selective indexing", Lucene 7.6.0). For such a field with one index dimension, the BKD writer may order a leaf block by a non-indexed dimension, while PointInSetQuery assumes the indexed values arrive in increasing order. The set query then silently skips matches: in a 200,000-document run it missed 91% of the hits, with no error, and CheckIndex stays clean. Every release since 7.6.0 is affected; it needs a custom field type.

• A points field stores one or more fixed-width numbers per document and is indexed in a BKD tree: inner nodes split the values into ranges, and the values end up in leaf blocks of up to 512 points by default (1024 up to 8.5.x).
• Selective indexing (LUCENE-8496, 7.6.0): FieldType.setDimensions(dimensionCount, indexDimensionCount, dimensionNumBytes). Only the first indexDimensionCount dimensions build the tree; the others are only stored next to each value in the leaf blocks. In the code, numDataDims means all dimensions.
• A set query matches documents whose value is any of the given values: IntPoint.newSetQuery("f", 10, 30) and the same method on LongPoint, FloatPoint, DoublePoint, BinaryPoint, InetAddressPoint and the sandbox HalfFloatPoint and BigIntegerPoint all build a one-dimensional PointInSetQuery.

1. The writer. To compress a leaf block, BKDWriter sorts the leaf by one dimension: at the first byte where the values differ, it picks the dimension with the fewest distinct values of that byte, among all dimensions, non-indexed ones included (it must be strictly fewer; a tie keeps dimension 0). So a leaf can be sorted by a non-indexed dimension, and then its indexed values are not in increasing order. This is designed: the feature commit widened these loops to all dimensions, and in review the author replied that leaves "require even the non indexed dimensions be sorted for compression".
2. The query. For any field with one index dimension, PointInSetQuery uses MergePointVisitor. It walks the sorted query values and the indexed values together, like a merge, and its pointer only moves forward: when it sees an indexed value larger than the current query value, it moves past that query value for good. If a smaller indexed value comes later in the same leaf, that document is silently missed (main PointInSetQuery.java:326-340).

Field f = (indexed value, non-indexed value), four documents in one leaf: doc 0 = (30, 5), doc 1 = (10, 5), doc 2 = (20, 5), doc 3 = (40, 9). Each number is 4 bytes and only the last byte differs. On flush the writer counts that byte from the leaf's second point: indexed {0A, 14, 28} = 3 distinct, non-indexed {05, 09} = 2, so the leaf is sorted by the non-indexed dimension. The visit order is 30, 10, 20, 40.

newSetQuery(f, 10, 30) with query values [10, 30]: it sees 30, moves its pointer from 10 to 30 and matches doc 0; it sees 10, but the pointer is at 30, so doc 1 is missed. Result 1 hit, expected 2. newSetQuery(f, 10) returns 0 (expected 1), while newExactQuery(f, 10) returns 1 and newRangeQuery(f, 10, 30) returns 3, both correct. Three documents are enough; two cannot trigger it.

No exception and no assertion fires, with or without -ea. CheckIndex says the index is clean by design: its order check runs only when the total dimension count is 1, and its comment says leaves with more dimensions "are sorted by the dimension with the lowest cardinality to improve block compression".

For a field like setDimensions(3, 2, 4) queried with a multi-dimensional PointInSetQuery (core has no public factory for it), SinglePointVisitor compares the whole stored value (12 bytes) with the 2-index-dimension query point (8 bytes), and these never compare equal. Leaf blocks whose index values all equal the query point are accepted whole without a compare, so it misses the matches in mixed leaf blocks: 2 x (1,2,i) + 2 x (3,4,i) gives 0 instead of 2, and 600 + 600 gives 512 instead of 600. Under -ea, the length assertion in SinglePointVisitor.visit (main :414) fires instead, but only when such a mixed leaf is visited.

• Silently wrong results. Missing hits only, no false positives, and CheckIndex is clean. With one index dimension nothing fails under -ea or -da; the multi-index-dimension case trips an assertion only under -ea. On the same field newSetQuery(f, v) can return 0 while newExactQuery(f, v) returns 1.
• At scale. 200,000 documents, indexed values 0-4999, a 4-valued non-indexed dimension, one segment, 200 random set queries of 1 to 50 values: all 200 wrong, 18,796 of 207,884 expected hits returned, 189,088 (91.0%) missed. A plain one-dimensional copy of the same values is exact. A fully default IndexWriterConfig with FSDirectory and four commits also fails (100 of 100 queries wrong).
• A merge can make correct results wrong. Written as two segments of two documents each, both leaves are sorted by the indexed value (in the first the non-indexed values are equal, so that dimension is not counted; in the second the counts tie 1 to 1) and the query answers 2. After forceMerge(1) the merged leaf counts 4 versus 2, is sorted by the non-indexed value, and answers 1 instead of 2 (on 7.6.0 and on 8.1.0 and later; 7.7.x and 8.0.0 answer 2 here).
• When it triggers. In a 50,000-document sweep: never with unique sequential indexed values; with unique random indexed values and a 2-valued or timestamp-like non-indexed dimension, 97-98% of hits missed; with 1000 distinct indexed values and a 2- or 4-valued or timestamp-like one, 90-92%; with 100 distinct and a 2-valued or timestamp-like one, about 2-2.5%. A 64-valued, random or index-equal non-indexed dimension missed nothing.
• Who is exposed: narrow. It needs a custom field type, setDimensions(n > 1, 1, bytes), through Field(name, byte[], type), BinaryPoint's Expert constructor or a custom field class, plus a set query (the core and sandbox newSetQuery factories, or JoinUtil with ScoreMode.None). No Lucene-provided field has that shape, and a partial code search of Elasticsearch, OpenSearch and Solr found none. The default codec and a default IndexWriterConfig are enough otherwise.
• Old. Every release since 7.6.0 (2018).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<2> 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.search.TestPointInSetQuerySelectiveIndexing.testSetQueryOnOneIndexDimensionOfTwo(TestPointInSetQuerySelectiveIndexing.java:36)

• PointInSetQuery accepts these fields. It checks values.getNumIndexDimensions() != numDims (main :168), so a one-index-dimension field passes. The feature commit changed that check as part of a ~70-file split of getNumDimensions; nothing in the issue or the PR discusses set queries.
• In the same commit the sibling query was given the opposite check. PointInSetIncludingScoreQuery (join), which has its own forward-only merge visitor, throws an IllegalArgumentException for such fields. That points to an oversight, not a design.
• "Wrong factory" does not hold. BinaryPoint's public Expert constructor BinaryPoint(String, byte[], IndexableFieldType) accepts a (2,1,1) type, and BinaryPoint.newSetQuery on it returns 1 instead of 2 (and 0 instead of 1 for one value), while newExactQuery returns 1.
• The configuration is supported and tested. FieldType.setDimensions(int, int, int) is public and not experimental; its validation allows 1 <= indexDimensionCount <= dimensionCount, and TestBKD and BasePointsFormatTestCase randomize the index dimensions in 1..numDims. Set queries on it are not tested.
• Precedent. #8920 (LUCENE-7869, "MemoryIndex should sort 1d points"), an unsorted 1-D source feeding MergePointVisitor, was labelled type:bug and fixed in 6.6.1, 6.7 and 7.0.

The intended-behaviour checker tried to show it is not a bug. What holds: the writer's leaf order is designed and documented; the IntersectVisitor#visit javadoc's "In the 1D case, values are visited in increasing order" was written in 2016, before selective indexing, and Lucene's other code reads "1D" as total dimensions = 1; JoinUtil documents its "to" field as IntPoint, LongPoint, FloatPoint or DoublePoint, so that route is outside its contract. What is weak: PointInSetQuery is @lucene.experimental, which means the API may change, not that wrong results are allowed; and the configuration is tested at the codec level.

Verdict: not intended; a bug. The writer behaves as designed and the query was never adapted to it. The maintainers may still prefer to reject such queries with an IAE (as the sibling query does) rather than make them work; either way the silent wrong answer is a defect. Not a security issue: wrong results on a Lucene-written index, so a public issue is right.

The checks validated the two-part query-side fix and re-ran the writer-side branch; the single-walk visitor and the reject option come from the brief and were not run.

Branch 5b-bkd-selective-indexing-fix (f340c1790e; -fix-106 5622253100 for branch_10_6), patch fix-query-side-main.patch, +9/-5 lines in PointInSetQuery.java: (1) use MergePointVisitor only if numDims == 1 && values.getNumDimensions() == 1, otherwise the existing SinglePointVisitor path; (2) SinglePointVisitor.visit compares only the index-dimension prefix, Arrays.equals(packedValue, 0, pointBytes.length, pointBytes, 0, pointBytes.length), and its assertion becomes >=.

Trade-offs

• Both parts are needed: part 1 alone sends these fields to the unfixed SinglePointVisitor (0 hits under -da, an AssertionError under -ea); part 2 alone fixes only the multi-index-dimension case.
• On these fields set queries then walk the tree once per query value instead of once in total (not measured). Plain one-dimensional fields are unchanged.
• It repairs segments already on disk; no index format change. The full core suite was not run.
• Related, separate root cause: MemoryIndex.getNumIndexDimensions() returns the total dimension count; fix it with or after this fix, because fixing it alone turns an IAE into a silent miss.

What the checks validated

• main: TestPointQueries, org.apache.lucene.util.bkd.*, TestPointValues and TestLucene90PointsFormat, seed DEADBEEF, -ea and -da: 174 tests, 0 failures; branch_10_6: 175 tests, 0 failures; the 3 new tests pass with two seeds.
• More on the main fix: :lucene:join:test 104 tests, :lucene:memory:test 51, sandbox document.* 23, core search.* + document.* 2,829, all passing.
• On an index written and force-merged by the 10.5.2 jar: stock code 77 of 100 queries wrong, with the fix 0 of 100. The demo is correct everywhere, the scale run included.

Branch 5b-bkd-selective-indexing-fix-writer (43d7991778), patch fix-writer-side-main.patch: force sortedDim = 0 when numIndexDims == 1 and dimension 0 is not constant in the leaf, close to what LUCENE-8562 did on the merge path in 7.7/8.0.

Trade-offs

The two one-index-dimension tests pass, but the 3-dimension / 2-index-dimension test still fails; it does not repair existing segments; it may cost some leaf compression (not measured); SimpleText has its own BKD writer and stays wrong under it.

Keep one tree walk: inner nodes are still split on the index dimension, so compare() can keep advancing past query values below the cell; inside a leaf, look each value up among the remaining query values (binary search) instead of consuming them.

Trade-offs

Keeps the single walk and fixes old segments, but still needs part 2 for multi-index-dimension fields. Not built.

Throw an IAE for set queries on fields with non-indexed dimensions, as PointInSetIncludingScoreQuery already does.

Trade-offs

Simpler, but it changes behaviour for queries that sometimes work today.

Method: a Dafny proof whose precondition aimed a bounded-exhaustive check of the real BKD code (the study's "semi-formal" tier). Run 3, experiment "bkd-points-proof" (2026-10-22, main 7cecf79523).

• The task text named the area (points and BKD query evaluation, including PointInSetQuery and BKDWriter) and the techniques (Dafny proofs, and bounded-exhaustive checking of the real BKDWriter/BKDReader with tiny configurations, "numDims 1-2"). It did not mention selective indexing or index versus non-indexed dimensions.
• Dafny, on a hand-written model: MergePointVisitor.dfy proves that the merge visitor plus intersect collect exactly the matching values, given a precondition WF: non-empty nodes, sorted values, values inside the node bounds (17 verified, 0 errors). A mutant that drops "sorted" fails with 4 errors.
• Bounded-exhaustive check of the real code: a Java harness on the real BKDWriter/BKDReader (-ea) checked WF on every tree it built, reading "1D" as numIndexDims == 1, the same reading PointInSetQuery uses. Family 2d1i (2 dimensions / 1 index dimension, 1 byte per dimension, 3 values per dimension, up to 4 points, leaves of 1-3 points; flush, heap and offline paths; format versions 9 and 10; 5 docID layouts): 664,200 trees, 16,106,500 queries, 25.6 s, 19,940 failures, all "1-D values out of order". Every other family, 3d2i included, had 0. The AI tool added the 2d1i and 3d2i families itself.
• What makes it a bug is the wrong hit counts: the proof is about a model, and the check on the real code is exhaustive only within tiny bounds. A separate AI verifier, given the candidate, wrote its own tests with different data and found the SinglePointVisitor and MemoryIndex parts while reading the code; a follow-up folded SinglePointVisitor into this bug.