Copilot commented on code in PR #12528:
URL: https://github.com/apache/lucene/pull/12528#discussion_r3122604113
##########
lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java:
##########
@@ -964,6 +979,53 @@ private void visitCompressedDocValues(
}
}
+ // Early terminate if packed value greater than upper point in sorted
dimension.
+ private void visitCompressedDocValuesEarlyTerminate(
+ int[] commonPrefixLengths,
+ byte[] scratchPackedValue,
+ IndexInput in,
+ BKDReaderDocIDSetIterator scratchIterator,
+ int count,
+ PointValues.IntersectVisitor visitor,
+ int compressedDim)
+ throws IOException {
+ // the byte at `compressedByteOffset` is compressed using run-length
compression,
+ // other suffix bytes are stored verbatim
+ final int compressedByteOffset =
+ compressedDim * config.bytesPerDim() +
commonPrefixLengths[compressedDim];
+ commonPrefixLengths[compressedDim]++;
+ int i;
+ VisitState visitState = null;
+ for (i = 0; i < count; ) {
+ scratchPackedValue[compressedByteOffset] = in.readByte();
+ final int runLen = Byte.toUnsignedInt(in.readByte());
+ for (int j = 0; j < runLen; ++j) {
+ for (int dim = 0; dim < config.numDims(); dim++) {
+ int prefix = commonPrefixLengths[dim];
+ in.readBytes(
+ scratchPackedValue,
+ dim * config.bytesPerDim() + prefix,
+ config.bytesPerDim() - prefix);
+ }
+ int offset = i + j;
+ visitState =
+ visitor.visitWithSortedDim(
+ scratchIterator.docIDs[offset], scratchPackedValue,
compressedDim);
+ if (visitState == VisitState.TERMINATE) {
+ break;
+ } else if (visitState == VisitState.MATCH_REMAINING) {
+ scratchIterator.reset(offset, count - offset);
+ visitor.visit(scratchIterator);
+ break;
+ }
+ }
+ if (visitState == VisitState.TERMINATE || visitState ==
VisitState.MATCH_REMAINING) {
+ break;
+ }
+ i += runLen;
+ }
Review Comment:
`visitCompressedDocValuesEarlyTerminate` no longer verifies that the decoded
run lengths add up to `count`. Consider restoring the `i != count` corruption
check when the method finishes scanning the leaf normally (ie. without
`TERMINATE`/`MATCH_REMAINING`), so we keep the same validation guarantees as
`visitCompressedDocValues`.
##########
lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java:
##########
@@ -1369,6 +1369,7 @@ private void writeLeafBlockPackedValues(
}
if (lowCardinalityCost <= highCardinalityCost) {
out.writeByte((byte) -2);
+ out.writeByte((byte) sortedDim);
Review Comment:
Writing an extra `sortedDim` byte after the `-2` marker changes the on-disk
leaf encoding. Since `BKDWriter.VERSION_CURRENT` is unchanged and `BKDReader`
unconditionally reads this extra byte, older segments (written before this
change) with low-cardinality leaves will be mis-decoded. Please bump the BKD
version and make reader/writer conditional on the version (eg. only write/read
`sortedDim` for versions >= new constant; otherwise fall back to the previous
low-cardinality decoding path without early-termination).
##########
lucene/test-framework/src/java/org/apache/lucene/tests/index/AssertingLeafReader.java:
##########
@@ -1643,6 +1657,118 @@ public void visit(int docID, byte[] packedValue) throws
IOException {
in.visit(docID, packedValue);
}
+ @Override
+ public PointValues.VisitState visitWithSortedDim(int docID, byte[]
packedValue, int sortedDim)
+ throws IOException {
+ assert --docBudget >= 0 : "called add() more times than the last call to
grow() reserved";
+
+ // This method, to filter each doc's value, should only be invoked when
the cell crosses the
+ // query shape:
+ assert lastCompareResult == null
+ || lastCompareResult == PointValues.Relation.CELL_CROSSES_QUERY;
+
+ if (lastCompareResult != null) {
+ // This doc's packed value should be contained in the last cell passed
to compare:
+ for (int dim = 0; dim < numIndexDims; dim++) {
+ assert Arrays.compareUnsigned(
+ lastMinPackedValue,
+ dim * bytesPerDim,
+ dim * bytesPerDim + bytesPerDim,
+ packedValue,
+ dim * bytesPerDim,
+ dim * bytesPerDim + bytesPerDim)
+ <= 0
+ : "dim=" + dim + " of " + numDataDims + " value=" + new
BytesRef(packedValue);
+ assert Arrays.compareUnsigned(
+ lastMaxPackedValue,
+ dim * bytesPerDim,
+ dim * bytesPerDim + bytesPerDim,
+ packedValue,
+ dim * bytesPerDim,
+ dim * bytesPerDim + bytesPerDim)
+ >= 0
+ : "dim=" + dim + " of " + numDataDims + " value=" + new
BytesRef(packedValue);
+ }
+ lastCompareResult = null;
+ }
+
+ // TODO: we should assert that this "matches" whatever relation the last
call to compare had
+ // returned
+ assert packedValue.length == numDataDims * bytesPerDim;
+ if (numDataDims == 1) {
+ int cmp = Arrays.compareUnsigned(lastDocValue, 0, bytesPerDim,
packedValue, 0, bytesPerDim);
+ if (cmp < 0) {
+ // ok
+ } else if (cmp == 0) {
+ assert lastDocID <= docID : "doc ids are out of order when point
values are the same!";
+ } else {
+ // out of order!
+ assert false : "point values are out of order";
+ }
+ System.arraycopy(packedValue, 0, lastDocValue, 0, bytesPerDim);
+ lastDocID = docID;
+ }
+ return in.visitWithSortedDim(docID, packedValue, sortedDim);
+ }
+
+ @Override
+ public PointValues.VisitState visitWithSortedDim(
+ DocIdSetIterator iterator, byte[] packedValue, int sortedDim) throws
IOException {
+ // TODO: docBudget -= iterator.length.
+ // assert --docBudget >= 0 : "called add() more times than the last
call to grow()
+ // reserved";
Review Comment:
`visitWithSortedDim(DocIdSetIterator, ...)` has a TODO for docBudget
handling, but without decrementing by the number of docs in the iterator this
asserting visitor can miss over-visitation bugs in bulk paths. Please account
`docBudget` using the iterator's size (`iterator.cost()` for
`BKDReaderDocIDSetIterator`) before delegating.
##########
lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java:
##########
@@ -181,6 +189,166 @@ public void testBasicLongs() throws Exception {
dir.close();
}
+ public void testSparseValuesWithSoredDimIntersectVisitor() throws Exception {
Review Comment:
There is a spelling mistake in the test name: `SoredDim` should be
`SortedDim` for readability and discoverability (and to match the feature
name). Please rename this method (and the other newly added `*SoredDim*` tests)
accordingly.
##########
lucene/core/src/java/org/apache/lucene/index/PointValues.java:
##########
@@ -229,6 +229,44 @@ public enum Relation {
CELL_CROSSES_QUERY
};
+ /** Visit states for current value. */
+ public enum VisitState {
+ /** value match */
+ CONTINUE,
+ /**
+ * Return this if MatchState is PointValues.MatchState.HIGH_IN_SORTED_DIM
in IntersectVisitor,
+ * so we can terminate visiting.
+ */
+ TERMINATE,
+ /**
+ * Return this if MatchState is PointValues.MatchState.HIGH_IN_SORTED_DIM
in Inverse
+ * IntersectVisitor, so we can terminate visiting and match remaining
values.
+ */
+ MATCH_REMAINING
+ };
+
+ /** Math states for current value. */
Review Comment:
Javadoc says "Math states" but the enum is `MatchState`. Please fix the typo
to avoid confusion in public API docs.
##########
lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java:
##########
@@ -822,6 +822,10 @@ private void visitDocValuesWithCardinality(
readCommonPrefixes(commonPrefixLengths, scratchDataPackedValue, in);
int compressedDim = readCompressedDim(in);
+ int sortedDim = compressedDim;
+ if (sortedDim == -2) {
+ sortedDim = in.readByte();
Review Comment:
`sortedDim` is read as an extra byte when `compressedDim == -2`, but this is
not guarded by the BKD format version and the value is not validated. This will
break reading older segments and may allow corrupt data to pass through. Gate
this read on a new BKD version (and keep the old low-cardinality decoding for
older versions), and validate that `0 <= sortedDim < config.numDims()`
(otherwise throw `CorruptIndexException`).
##########
lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java:
##########
@@ -908,13 +919,17 @@ private void visitSparseRawDocValues(
config.bytesPerDim() - prefix);
}
scratchIterator.reset(i, length);
- visitor.visit(scratchIterator, scratchPackedValue);
+ VisitState visitState =
+ visitor.visitWithSortedDim(scratchIterator, scratchPackedValue,
sortedDim);
+ if (visitState == VisitState.TERMINATE) {
+ break;
+ } else if (visitState == VisitState.MATCH_REMAINING) {
+ scratchIterator.reset(i, count - i);
+ visitor.visit(scratchIterator);
+ break;
+ }
i += length;
}
Review Comment:
`visitSparseRawDocValuesEarlyTerminate` removed the integrity check that
sub-block cardinalities sum to `count` (previously threw
`CorruptIndexException` when `i != count`). Even if early-termination is used,
it would be good to keep this corruption detection when the loop completes
normally (no terminate/match-remaining), otherwise index corruption could go
unnoticed.
##########
lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java:
##########
@@ -181,6 +189,166 @@ public void testBasicLongs() throws Exception {
dir.close();
}
+ public void testSparseValuesWithSoredDimIntersectVisitor() throws Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
+ Document doc = new Document();
+ doc.add(new LongPoint("point", -7));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 4));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 5));
+ w.addDocument(doc);
+
+ DirectoryReader r = DirectoryReader.open(w);
+ IndexSearcher s = new IndexSearcher(r);
+ assertEquals(6, s.search(LongPoint.newRangeQuery("point", 0L, 4L),
10).scoreDocs.length);
+ assertEquals(1, s.search(LongPoint.newRangeQuery("point", -8L, 1L),
10).scoreDocs.length);
+ w.close();
+ r.close();
+ dir.close();
+ }
+
+ public void testSparseValuesWithSoredDimInverseIntersectVisitor() throws
Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
+ Document doc = new Document();
+ doc.add(new LongPoint("point", -7));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 4));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 5));
+ w.addDocument(doc);
+
+ DirectoryReader r = DirectoryReader.open(w);
+ IndexSearcher s = new IndexSearcher(r);
+ assertEquals(5, s.search(LongPoint.newRangeQuery("point", 0L, 4L),
10).scoreDocs.length);
+ assertEquals(1, s.search(LongPoint.newRangeQuery("point", -8L, 1L),
10).scoreDocs.length);
+ w.close();
+ r.close();
+ dir.close();
+ }
+
+ public void testCompressedWithSoredDimIntersectVisitor() throws Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
+ Document doc = new Document();
+ doc.add(new LongPoint("point", -7));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 0));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 1));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 4));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 5));
+ w.addDocument(doc);
+
+ DirectoryReader r = DirectoryReader.open(w);
+ IndexSearcher s = new IndexSearcher(r);
+
+ assertEquals(4, s.search(LongPoint.newRangeQuery("point", 0L, 4L),
10).scoreDocs.length);
+ assertEquals(3, s.search(LongPoint.newRangeQuery("point", -8L, 1L),
10).scoreDocs.length);
+
+ w.close();
+ r.close();
+ dir.close();
+ }
+
+ public void testCompressedWithSoredDimInverseIntersectVisitor() throws
Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
Review Comment:
Spelling mistake in the test name: `SoredDim` should be `SortedDim`.
##########
lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java:
##########
@@ -181,6 +189,166 @@ public void testBasicLongs() throws Exception {
dir.close();
}
+ public void testSparseValuesWithSoredDimIntersectVisitor() throws Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
+ Document doc = new Document();
+ doc.add(new LongPoint("point", -7));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 4));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 5));
+ w.addDocument(doc);
+
+ DirectoryReader r = DirectoryReader.open(w);
+ IndexSearcher s = new IndexSearcher(r);
+ assertEquals(6, s.search(LongPoint.newRangeQuery("point", 0L, 4L),
10).scoreDocs.length);
+ assertEquals(1, s.search(LongPoint.newRangeQuery("point", -8L, 1L),
10).scoreDocs.length);
+ w.close();
+ r.close();
+ dir.close();
+ }
+
+ public void testSparseValuesWithSoredDimInverseIntersectVisitor() throws
Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
+ Document doc = new Document();
+ doc.add(new LongPoint("point", -7));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 4));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 5));
+ w.addDocument(doc);
+
+ DirectoryReader r = DirectoryReader.open(w);
+ IndexSearcher s = new IndexSearcher(r);
+ assertEquals(5, s.search(LongPoint.newRangeQuery("point", 0L, 4L),
10).scoreDocs.length);
+ assertEquals(1, s.search(LongPoint.newRangeQuery("point", -8L, 1L),
10).scoreDocs.length);
+ w.close();
+ r.close();
+ dir.close();
+ }
+
+ public void testCompressedWithSoredDimIntersectVisitor() throws Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
Review Comment:
Spelling mistake in the test name: `SoredDim` should be `SortedDim`.
##########
lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java:
##########
@@ -181,6 +189,166 @@ public void testBasicLongs() throws Exception {
dir.close();
}
+ public void testSparseValuesWithSoredDimIntersectVisitor() throws Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
+
+ Document doc = new Document();
+ doc.add(new LongPoint("point", -7));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 2));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 3));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 4));
+ w.addDocument(doc);
+
+ doc = new Document();
+ doc.add(new LongPoint("point", 5));
+ w.addDocument(doc);
+
+ DirectoryReader r = DirectoryReader.open(w);
+ IndexSearcher s = new IndexSearcher(r);
+ assertEquals(6, s.search(LongPoint.newRangeQuery("point", 0L, 4L),
10).scoreDocs.length);
+ assertEquals(1, s.search(LongPoint.newRangeQuery("point", -8L, 1L),
10).scoreDocs.length);
+ w.close();
+ r.close();
+ dir.close();
+ }
+
+ public void testSparseValuesWithSoredDimInverseIntersectVisitor() throws
Exception {
+ Directory dir = newDirectory();
+ IndexWriter w = new IndexWriter(dir, new IndexWriterConfig(new
MockAnalyzer(random())));
Review Comment:
Spelling mistake in the test name: `SoredDim` should be `SortedDim`.
##########
lucene/test-framework/src/java/org/apache/lucene/tests/index/AssertingLeafReader.java:
##########
@@ -1590,6 +1590,20 @@ public void visit(int docID) throws IOException {
in.visit(docID);
}
+ @Override
+ public void visit(DocIdSetIterator iterator) throws IOException {
+ // If we want to keep doc/iterator matched
PointValues.MatchState.HIGH_IN_SORTED_DIM in
+ // remaining docs, don't docBudget -= iterator.length, since we have
reduced docBudget in
+ // visitWithSortedDim.
+ // assert --docBudget >= 0 : "called add() more times than the last
call to grow()
+ // reserved";
+
+ // This method, not filtering each hit, should only be invoked when the
cell is inside the
+ // query shape:
+ assert lastCompareResult == null || lastCompareResult ==
Relation.CELL_INSIDE_QUERY;
+ in.visit(iterator);
+ }
Review Comment:
This override skips decrementing `docBudget` for bulk
`visit(DocIdSetIterator)`. When `BKDReader` uses `MATCH_REMAINING` and calls
`visitor.visit(iterator)`, the asserting visitor will no longer catch cases
where more docs are visited than were reserved by `grow()`. Consider
decrementing by `Math.toIntExact(iterator.cost())` (or iterating and
decrementing per-doc) before delegating, so assertions remain effective.
##########
lucene/core/src/java/org/apache/lucene/document/LatLonPointDistanceQuery.java:
##########
@@ -172,6 +172,53 @@ public long cost() {
};
}
+ private PointValues.MatchState matchesWithState(byte[] packedValue, int
sortedDim) {
+ if (sortedDim == 0) {
+ int lat = NumericUtils.sortableBytesToInt(packedValue, 0);
+ // bounding box check
+ if (lat > maxLat) {
+ // latitude out of bounding box range
+ return PointValues.MatchState.HIGH_IN_SORTED_DIM;
+ } else if (lat < minLat) {
+ return PointValues.MatchState.LOW;
+ }
+ int lon = NumericUtils.sortableBytesToInt(packedValue,
Integer.BYTES);
+ if ((lon > maxLon || lon < minLon) && lon < minLon2) {
+ // longitude out of bounding box range
+ return PointValues.MatchState.NOT_MATCH;
+ }
+ return distancePredicate.test(lat, lon)
+ ? PointValues.MatchState.MATCH
+ : PointValues.MatchState.NOT_MATCH;
+ } else {
+ int lon = NumericUtils.sortableBytesToInt(packedValue,
Integer.BYTES);
+ // // cross
+ // if (lon > maxLon && lon < minLon2) {}
+ // // disable
+ // if (lon > maxLon || lon < minLon) {}
Review Comment:
There is leftover commented-out code in `matchesWithState` that looks like
an abandoned implementation path. Please remove these commented lines to keep
the query logic clear and maintainable.
##########
lucene/core/src/java/org/apache/lucene/index/PointValues.java:
##########
@@ -319,6 +358,21 @@ default void visit(IntsRef ref) throws IOException {
*/
void visit(int docID, byte[] packedValue) throws IOException;
+ /**
+ * Similar to {@link IntersectVisitor#visit(int, byte[])} but data is
visited in increasing
+ * order on the sortedDim, and in the case of ties, in increasing docID
order. Implementers can
+ * stop processing points on the leaf by returning false when for example
the sorted dimension
+ * value is too high to be matched by the query.
+ *
+ * @return VisitState.CONTINUE if the visitor should continue visiting
points on this leaf,
+ * otherwise false.
+ */
+ default VisitState visitWithSortedDim(int docID, byte[] packedValue, int
sortedDim)
+ throws IOException {
+ visit(docID, packedValue);
+ return VisitState.CONTINUE;
+ }
Review Comment:
The Javadoc for `visitWithSortedDim` still refers to returning `false` (eg.
"stop processing ... by returning false" and "otherwise false"), but the method
returns `VisitState`. Please update the documentation to describe the
`VisitState` contract (CONTINUE / TERMINATE / MATCH_REMAINING) accurately.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
