You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mk...@apache.org on 2025/03/01 10:07:51 UTC
(lucene) branch branch_10x updated: Optimize single value ranges for multivalue sortedset docvalues ranges. (#14276) (#14317)
This is an automated email from the ASF dual-hosted git repository.
mkhl pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_10x by this push:
new e006c3a9d81 Optimize single value ranges for multivalue sortedset docvalues ranges. (#14276) (#14317)
e006c3a9d81 is described below
commit e006c3a9d81ef640788781f0240a5c0fc630d8d9
Author: Mikhail Khludnev <mk...@users.noreply.github.com>
AuthorDate: Sat Mar 1 13:07:44 2025 +0300
Optimize single value ranges for multivalue sortedset docvalues ranges. (#14276) (#14317)
* Optimize single value ranges for multivalue sortedset docvalues ranges.
(cherry picked from commit ac44476e7bacc38ad38a40ead1682d8671a43020)
---
lucene/CHANGES.txt | 3 +-
.../sandbox/search/DocValuesMultiRangeQuery.java | 10 ++++++
.../search/SortedSetDocValuesMultiRangeQuery.java | 4 ++-
.../search/TestInetAddrSsDvMultiRangeQuery.java | 42 ++++++----------------
.../sandbox/search/TestSsDvMultiRangeQuery.java | 28 +++++++++++----
5 files changed, 48 insertions(+), 39 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index b3a202bed1c..00629515550 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -34,7 +34,8 @@ New Features
These queries allow for the vector search entry points to be initialized via a `seed` query. This follows
the research provided via https://arxiv.org/abs/2307.16779. (Sean MacAvaney, Ben Trent).
-* GITHUB#13974: Introducing DocValuesMultiRangeQuery.SortedSetStabbingBuilder into sandbox. (Mikhail Khludnev)
+* GITHUB#13974,GITHUB#14276: Introducing DocValuesMultiRangeQuery.SortedSetStabbingBuilder into sandbox.
+ (Mikhail Khludnev)
* GITHUB#14204: Added HistogramCollectorManager to efficiently compute a
histogram of the distribution of the values of a field, for documents
diff --git a/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/DocValuesMultiRangeQuery.java b/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/DocValuesMultiRangeQuery.java
index 943a048054b..bc7b47f2b48 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/DocValuesMultiRangeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/DocValuesMultiRangeQuery.java
@@ -43,6 +43,10 @@ public final class DocValuesMultiRangeQuery {
this.upper = BytesRef.deepCopyOf(upperValue);
}
+ public ByteRange(BytesRef singleValue) {
+ this.upper = this.lower = BytesRef.deepCopyOf(singleValue);
+ }
+
@Override
public boolean equals(Object o) {
if (this == o) {
@@ -88,6 +92,12 @@ public final class DocValuesMultiRangeQuery {
return this;
}
+ /** Adds a value when lower and upper values are equal */
+ public SortedSetStabbingBuilder add(BytesRef singleValue) {
+ clauses.add(new ByteRange(singleValue));
+ return this;
+ }
+
public Query build() {
if (clauses.isEmpty()) {
return new MatchNoDocsQuery();
diff --git a/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetDocValuesMultiRangeQuery.java b/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetDocValuesMultiRangeQuery.java
index 34ae3dcee26..aef7034c286 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetDocValuesMultiRangeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetDocValuesMultiRangeQuery.java
@@ -105,7 +105,9 @@ public class SortedSetDocValuesMultiRangeQuery extends Query {
case FOUND, NOT_FOUND:
lowerOrd = termsEnum.ord();
}
- seekStatus = termsEnum.seekCeil(range.upper);
+ if (range.lower != range.upper) { // just a quick reference check, equality is too rare
+ seekStatus = termsEnum.seekCeil(range.upper);
+ }
long upperOrd = -1;
switch (seekStatus) {
case TermsEnum.SeekStatus.END:
diff --git a/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestInetAddrSsDvMultiRangeQuery.java b/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestInetAddrSsDvMultiRangeQuery.java
index 7ab0a6eca73..cf35f1bb5f5 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestInetAddrSsDvMultiRangeQuery.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestInetAddrSsDvMultiRangeQuery.java
@@ -68,28 +68,6 @@ public class TestInetAddrSsDvMultiRangeQuery extends LuceneTestCase {
new byte[] {127, 2, 3, 3}), // bogus range to avoid optimization
InetAddress.getByAddress(new byte[] {127, 2, 3, 5}));
assertEquals(1, searcher.count(q));
- // assertEquals(1, searcher.count(InetAddressPoint.newPrefixQuery("field", address,
- // 24)));
- // assertEquals(
- // 1,
- // searcher.count(
- // InetAddressPoint.newRangeQuery(
- // "field", InetAddress.getByName("1.2.3.3"),
- // InetAddress.getByName("1.2.3.5"))));
- // assertEquals(
- // 1, searcher.count(InetAddressPoint.newSetQuery("field",
- // InetAddress.getByName("1.2.3.4"))));
- // assertEquals(
- // 1,
- // searcher.count(
- // InetAddressPoint.newSetQuery(
- // "field", InetAddress.getByName("1.2.3.4"),
- // InetAddress.getByName("1.2.3.5"))));
- // assertEquals(
- // 0, searcher.count(InetAddressPoint.newSetQuery("field",
- // InetAddress.getByName("1.2.3.3"))));
- // assertEquals(0, searcher.count(InetAddressPoint.newSetQuery("field")));
-
reader.close();
writer.close();
dir.close();
@@ -147,17 +125,19 @@ public class TestInetAddrSsDvMultiRangeQuery extends LuceneTestCase {
for (int q = 0; q < atLeast(10); q++) {
byte[] alfa = random().nextBoolean() ? getRandomIpBytes() : pivotIpsStream.get();
byte[] beta = random().nextBoolean() ? getRandomIpBytes() : pivotIpsStream.get();
- if (comparator.compare(alfa, 0, beta, 0) > 0) {
+ int cmp;
+ if ((cmp = comparator.compare(alfa, 0, beta, 0)) > 0) {
byte[] swap = beta;
beta = alfa;
alfa = swap;
}
- // ranges.add(InetAddress.getByAddress(alfa));
- // ranges.add(InetAddress.getByAddress(beta));
- qbuilder.add(
- new BytesRef(InetAddressPoint.encode(InetAddress.getByAddress(alfa))),
- new BytesRef(InetAddressPoint.encode(InetAddress.getByAddress(beta))));
-
+ if (cmp == 0 && random().nextBoolean()) {
+ qbuilder.add(new BytesRef(InetAddressPoint.encode(InetAddress.getByAddress(alfa))));
+ } else {
+ qbuilder.add(
+ new BytesRef(InetAddressPoint.encode(InetAddress.getByAddress(alfa))),
+ new BytesRef(InetAddressPoint.encode(InetAddress.getByAddress(beta))));
+ }
bq.add(
SortedSetDocValuesField.newSlowRangeQuery(
"field",
@@ -176,13 +156,13 @@ public class TestInetAddrSsDvMultiRangeQuery extends LuceneTestCase {
}
TopDocs boolRes;
// System.out.println(Arrays.toString((
- boolRes = searcher.search(orRanges, 1000); // ).scoreDocs));
+ boolRes = searcher.search(orRanges, reader.maxDoc()); // ).scoreDocs));
Set<Integer> boolDocs =
Stream.of(boolRes.scoreDocs).map((sd) -> sd.doc).collect(Collectors.toSet());
TopDocs mulRes;
// System.out.println(Arrays.toString((
- mulRes = searcher.search(multiRange, 1000); // ).scoreDocs));
+ mulRes = searcher.search(multiRange, reader.maxDoc()); // ).scoreDocs));
Set<Integer> mulDocs =
Stream.of(mulRes.scoreDocs).map((sd) -> sd.doc).collect(Collectors.toSet());
Set<Integer> falsePos = new HashSet<>(mulDocs);
diff --git a/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestSsDvMultiRangeQuery.java b/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestSsDvMultiRangeQuery.java
index 8a20a3aef21..112feec2cc7 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestSsDvMultiRangeQuery.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestSsDvMultiRangeQuery.java
@@ -18,8 +18,11 @@ package org.apache.lucene.sandbox.search;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import java.io.IOException;
+import java.util.Arrays;
import java.util.Collections;
import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.lucene90.Lucene90DocValuesFormat;
import org.apache.lucene.document.Document;
@@ -119,15 +122,19 @@ public class TestSsDvMultiRangeQuery extends LuceneTestCase {
}
builder1.add(lower, upper);
builder2.add(LongPoint.newRangeQuery("point", lower, upper), BooleanClause.Occur.SHOULD);
- builder3.add(LongPoint.pack(lower), LongPoint.pack(upper));
+ if (Arrays.equals(lower, upper) && random().nextBoolean()) {
+ builder3.add(LongPoint.pack(lower));
+ } else {
+ builder3.add(LongPoint.pack(lower), LongPoint.pack(upper));
+ }
}
Query query1 = builder1.build();
Query query2 = builder2.build();
Query query3 = builder3.build();
- TopDocs result1 = searcher.search(query1, maxDocs, Sort.INDEXORDER);
- TopDocs result2 = searcher.search(query2, maxDocs, Sort.INDEXORDER);
- TopDocs result3 = searcher.search(query3, maxDocs, Sort.INDEXORDER);
+ TopDocs result1 = searcher.search(query1, reader.maxDoc(), Sort.INDEXORDER);
+ TopDocs result2 = searcher.search(query2, reader.maxDoc(), Sort.INDEXORDER);
+ TopDocs result3 = searcher.search(query3, reader.maxDoc(), Sort.INDEXORDER);
assertEquals(result2.totalHits, result1.totalHits);
assertEquals(result2.totalHits, result3.totalHits);
assertEquals(result2.scoreDocs.length, result1.scoreDocs.length);
@@ -160,8 +167,17 @@ public class TestSsDvMultiRangeQuery extends LuceneTestCase {
String field, int... ends) {
DocValuesMultiRangeQuery.SortedSetStabbingBuilder b =
new DocValuesMultiRangeQuery.SortedSetStabbingBuilder(field);
- for (int j = 0; j < ends.length; j += 2) {
- b.add(IntPoint.pack(ends[j]), IntPoint.pack(ends[j + 1]));
+ List<Integer> posns =
+ IntStream.range(0, ends.length / 2).map(i -> i * 2).boxed().collect(Collectors.toList());
+ Collections.shuffle(posns, random());
+ for (Integer pos : posns) {
+ int lower = ends[pos];
+ int upper = ends[pos + 1];
+ if (lower == upper && random().nextBoolean()) {
+ b.add(IntPoint.pack(lower));
+ } else {
+ b.add(IntPoint.pack(lower), IntPoint.pack(upper));
+ }
}
return b;
}