Skip to content

Commit 4f17dee

Browse files
ilariapetcpoerschke
ilariapet
and
cpoerschke
authored
SOLR-17813: Add support for SeededKnnVectorQuery in vector search (#3705)
* support Lucene's (proposed) HNSW search seeding feature Co-authored-by: Christine Poerschke <cpoerschke@apache.org>
1 parent 18778f5 commit 4f17dee

5 files changed

Lines changed: 229 additions & 43 deletions

File tree

‎solr/CHANGES.txt‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,8 @@ New Features
8181

8282
* SOLR-17948: Support indexing primitive float[] values for DenseVectorField via JavaBin (Puneet Ahuja, Noble Paul)
8383

84+
* SOLR-17813: Add support for SeededKnnVectorQuery (Ilaria Petreti via Alessandro Benedetti)
85+
8486
Improvements
8587
---------------------
8688

‎solr/core/src/java/org/apache/solr/schema/DenseVectorField.java‎

Lines changed: 62 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@
4141
import org.apache.lucene.search.KnnFloatVectorQuery;
4242
import org.apache.lucene.search.PatienceKnnVectorQuery;
4343
import org.apache.lucene.search.Query;
44+
import org.apache.lucene.search.SeededKnnVectorQuery;
4445
import org.apache.lucene.search.SortField;
4546
import org.apache.lucene.util.BytesRef;
4647
import org.apache.lucene.util.hnsw.HnswGraph;
@@ -377,43 +378,35 @@ public Query getKnnVectorQuery(
377378
String vectorToSearch,
378379
int topK,
379380
Query filterQuery,
381+
Query seedQuery,
380382
EarlyTerminationParams earlyTermination) {
381383

382384
DenseVectorParser vectorBuilder =
383385
getVectorBuilder(vectorToSearch, DenseVectorParser.BuilderPhase.QUERY);
384386

385-
switch (vectorEncoding) {
386-
case FLOAT32:
387-
KnnFloatVectorQuery knnFloatVectorQuery =
388-
new KnnFloatVectorQuery(fieldName, vectorBuilder.getFloatVector(), topK, filterQuery);
389-
if (earlyTermination.isEnabled()) {
390-
return (earlyTermination.getSaturationThreshold() != null
391-
&& earlyTermination.getPatience() != null)
392-
? PatienceKnnVectorQuery.fromFloatQuery(
393-
knnFloatVectorQuery,
394-
earlyTermination.getSaturationThreshold(),
395-
earlyTermination.getPatience())
396-
: PatienceKnnVectorQuery.fromFloatQuery(knnFloatVectorQuery);
397-
}
398-
return knnFloatVectorQuery;
399-
case BYTE:
400-
KnnByteVectorQuery knnByteVectorQuery =
401-
new KnnByteVectorQuery(fieldName, vectorBuilder.getByteVector(), topK, filterQuery);
402-
if (earlyTermination.isEnabled()) {
403-
return (earlyTermination.getSaturationThreshold() != null
404-
&& earlyTermination.getPatience() != null)
405-
? PatienceKnnVectorQuery.fromByteQuery(
406-
knnByteVectorQuery,
407-
earlyTermination.getSaturationThreshold(),
408-
earlyTermination.getPatience())
409-
: PatienceKnnVectorQuery.fromByteQuery(knnByteVectorQuery);
410-
}
411-
return knnByteVectorQuery;
412-
default:
413-
throw new SolrException(
414-
SolrException.ErrorCode.SERVER_ERROR,
415-
"Unexpected state. Vector Encoding: " + vectorEncoding);
416-
}
387+
final Query knnQuery =
388+
switch (vectorEncoding) {
389+
case FLOAT32 -> new KnnFloatVectorQuery(
390+
fieldName, vectorBuilder.getFloatVector(), topK, filterQuery);
391+
case BYTE -> new KnnByteVectorQuery(
392+
fieldName, vectorBuilder.getByteVector(), topK, filterQuery);
393+
};
394+
395+
final boolean seedEnabled = (seedQuery != null);
396+
final boolean earlyTerminationEnabled =
397+
(earlyTermination != null && earlyTermination.isEnabled());
398+
399+
int caseNumber = (seedEnabled ? 1 : 0) + (earlyTerminationEnabled ? 2 : 0);
400+
return switch (caseNumber) {
401+
// 0: no seed, no early termination -> knnQuery
402+
default -> knnQuery;
403+
// 1: only seed -> Seeded(knnQuery)
404+
case 1 -> getSeededQuery(knnQuery, seedQuery);
405+
// 2: only early termination -> Patience(knnQuery)
406+
case 2 -> getEarlyTerminationQuery(knnQuery, earlyTermination);
407+
// 3: seed + early termination -> Patience(Seeded(knnQuery))
408+
case 3 -> getEarlyTerminationQuery(getSeededQuery(knnQuery, seedQuery), earlyTermination);
409+
};
417410
}
418411

419412
/**
@@ -446,4 +439,41 @@ public SortField getSortField(SchemaField field, boolean top) {
446439
throw new SolrException(
447440
SolrException.ErrorCode.BAD_REQUEST, "Cannot sort on a Dense Vector field");
448441
}
442+
443+
private Query getSeededQuery(Query knnQuery, Query seed) {
444+
return switch (knnQuery) {
445+
case KnnFloatVectorQuery knnFloatQuery -> SeededKnnVectorQuery.fromFloatQuery(
446+
knnFloatQuery, seed);
447+
case KnnByteVectorQuery knnByteQuery -> SeededKnnVectorQuery.fromByteQuery(
448+
knnByteQuery, seed);
449+
default -> throw new SolrException(
450+
SolrException.ErrorCode.SERVER_ERROR, "Invalid type of knn query");
451+
};
452+
}
453+
454+
private Query getEarlyTerminationQuery(Query knnQuery, EarlyTerminationParams earlyTermination) {
455+
final boolean useExplicitParams =
456+
(earlyTermination.getSaturationThreshold() != null
457+
&& earlyTermination.getPatience() != null);
458+
return switch (knnQuery) {
459+
case KnnFloatVectorQuery knnFloatQuery -> useExplicitParams
460+
? PatienceKnnVectorQuery.fromFloatQuery(
461+
knnFloatQuery,
462+
earlyTermination.getSaturationThreshold(),
463+
earlyTermination.getPatience())
464+
: PatienceKnnVectorQuery.fromFloatQuery(knnFloatQuery);
465+
case KnnByteVectorQuery knnByteQuery -> useExplicitParams
466+
? PatienceKnnVectorQuery.fromByteQuery(
467+
knnByteQuery,
468+
earlyTermination.getSaturationThreshold(),
469+
earlyTermination.getPatience())
470+
: PatienceKnnVectorQuery.fromByteQuery(knnByteQuery);
471+
case SeededKnnVectorQuery seedQuery -> useExplicitParams
472+
? PatienceKnnVectorQuery.fromSeededQuery(
473+
seedQuery, earlyTermination.getSaturationThreshold(), earlyTermination.getPatience())
474+
: PatienceKnnVectorQuery.fromSeededQuery(seedQuery);
475+
default -> throw new SolrException(
476+
SolrException.ErrorCode.SERVER_ERROR, "Invalid type of knn query");
477+
};
478+
}
449479
}

‎solr/core/src/java/org/apache/solr/search/neural/KnnQParser.java‎

Lines changed: 21 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -23,17 +23,18 @@
2323
import org.apache.solr.request.SolrQueryRequest;
2424
import org.apache.solr.schema.DenseVectorField;
2525
import org.apache.solr.schema.SchemaField;
26+
import org.apache.solr.search.QParser;
2627
import org.apache.solr.search.SyntaxError;
2728

2829
public class KnnQParser extends AbstractVectorQParserBase {
2930

3031
// retrieve the top K results based on the distance similarity function
3132
protected static final String TOP_K = "topK";
3233
protected static final int DEFAULT_TOP_K = 10;
34+
protected static final String SEED_QUERY = "seedQuery";
3335

3436
// parameters for PatienceKnnVectorQuery, a version of knn vector query that exits early when HNSW
35-
// queue
36-
// saturates over a {@code #saturationThreshold} for more than {@code #patience} times.
37+
// queue saturates over a {@code #saturationThreshold} for more than {@code #patience} times.
3738
protected static final String EARLY_TERMINATION = "earlyTermination";
3839
protected static final boolean DEFAULT_EARLY_TERMINATION = false;
3940
protected static final String SATURATION_THRESHOLD = "saturationThreshold";
@@ -88,6 +89,18 @@ public EarlyTerminationParams getEarlyTerminationParams() {
8889
return new EarlyTerminationParams(enabled, saturationThreshold, patience);
8990
}
9091

92+
protected Query getSeedQuery() throws SolrException, SyntaxError {
93+
String seed = localParams.get(SEED_QUERY);
94+
if (seed == null) return null;
95+
if (seed.isBlank()) {
96+
throw new SolrException(
97+
SolrException.ErrorCode.BAD_REQUEST,
98+
"'seedQuery' parameter is present but is blank: please provide a valid query");
99+
}
100+
final QParser seedParser = subQuery(seed, null);
101+
return seedParser.getQuery();
102+
}
103+
91104
@Override
92105
public Query parse() throws SyntaxError {
93106
final SchemaField schemaField = req.getCore().getLatestSchema().getField(getFieldName());
@@ -96,6 +109,11 @@ public Query parse() throws SyntaxError {
96109
final int topK = localParams.getInt(TOP_K, DEFAULT_TOP_K);
97110

98111
return denseVectorType.getKnnVectorQuery(
99-
schemaField.getName(), vectorToSearch, topK, getFilterQuery(), getEarlyTerminationParams());
112+
schemaField.getName(),
113+
vectorToSearch,
114+
topK,
115+
getFilterQuery(),
116+
getSeedQuery(),
117+
getEarlyTerminationParams());
100118
}
101119
}

‎solr/core/src/test/org/apache/solr/search/neural/KnnQParserTest.java‎

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1198,4 +1198,120 @@ public void onlyOneInputParam_shouldThrowException() {
11981198
vectorToSearch)),
11991199
SolrException.ErrorCode.BAD_REQUEST);
12001200
}
1201+
1202+
@Test
1203+
public void knnQueryWithSeedQuery_shouldPerformSeededKnnVectorQuery() {
1204+
// Test to verify that when the seedQuery parameter is provided, the SeededKnnVectorQuery is
1205+
// executed (float).
1206+
String vectorToSearch = "[1.0, 2.0, 3.0, 4.0]";
1207+
1208+
assertQ(
1209+
req(
1210+
CommonParams.Q,
1211+
"{!knn f=vector topK=4 seedQuery='id:(1 4 7 8 9)'}" + vectorToSearch,
1212+
"fl",
1213+
"id",
1214+
"debugQuery",
1215+
"true"),
1216+
"//result[@numFound='4']",
1217+
"//str[@name='parsedquery'][.='SeededKnnVectorQuery(SeededKnnVectorQuery{seed=id:1 id:4 id:7 id:8 id:9, seedWeight=null, delegate=KnnFloatVectorQuery:vector[1.0,...][4]})']");
1218+
}
1219+
1220+
@Test
1221+
public void byteKnnQueryWithSeedQuery_shouldPerformSeededKnnVectorQuery() {
1222+
// Test to verify that when the seedQuery parameter is provided, the SeededKnnVectorQuery is
1223+
// executed (byte).
1224+
1225+
String vectorToSearch = "[2, 2, 1, 3]";
1226+
1227+
// BooleanQuery
1228+
assertQ(
1229+
req(
1230+
CommonParams.Q,
1231+
"{!knn f=vector_byte_encoding topK=4 seedQuery='id:(1 4 7 8 9)'}" + vectorToSearch,
1232+
"fl",
1233+
"id",
1234+
"debugQuery",
1235+
"true"),
1236+
"//result[@numFound='4']",
1237+
"//str[@name='parsedquery'][.='SeededKnnVectorQuery(SeededKnnVectorQuery{seed=id:1 id:4 id:7 id:8 id:9, seedWeight=null, delegate=KnnByteVectorQuery:vector_byte_encoding[2,...][4]})']");
1238+
}
1239+
1240+
@Test
1241+
public void knnQueryWithBlankSeed_shouldThrowException() {
1242+
// Test to verify that when the seedQuery parameter is provided but blank, Solr throws a
1243+
// BAD_REQUEST exception.
1244+
String vectorToSearch = "[1.0, 2.0, 3.0, 4.0]";
1245+
1246+
assertQEx(
1247+
"Blank seed query should throw Exception",
1248+
"'seedQuery' parameter is present but is blank: please provide a valid query",
1249+
req(CommonParams.Q, "{!knn f=vector topK=4 seedQuery=''}" + vectorToSearch),
1250+
SolrException.ErrorCode.BAD_REQUEST);
1251+
}
1252+
1253+
@Test
1254+
public void knnQueryWithInvalidSeedQuery_shouldThrowException() {
1255+
// Test to verify that when the seedQuery parameter is provided with an invalid value, Solr
1256+
// throws a BAD_REQUEST exception.
1257+
String vectorToSearch = "[1.0, 2.0, 3.0, 4.0]";
1258+
1259+
assertQEx(
1260+
"Invalid seed query should throw Exception",
1261+
"Cannot parse 'id:'",
1262+
req(CommonParams.Q, "{!knn f=vector topK=4 seedQuery='id:'}" + vectorToSearch),
1263+
SolrException.ErrorCode.BAD_REQUEST);
1264+
}
1265+
1266+
@Test
1267+
public void knnQueryWithKnnSeedQuery_shouldPerformSeededKnnVectorQuery() {
1268+
// Test to verify that when the seedQuery parameter itself is a knn query, it is correctly
1269+
// parsed and applied as the seed for the main knn query.
1270+
String mainVectorToSearch = "[1.0, 2.0, 3.0, 4.0]";
1271+
String seedVectorToSearch = "[0.1, 0.2, 0.3, 0.4]";
1272+
1273+
assertQ(
1274+
req(
1275+
CommonParams.Q,
1276+
"{!knn f=vector topK=4 seedQuery=$seedQuery}" + mainVectorToSearch,
1277+
"seedQuery",
1278+
"{!knn f=vector topK=4}" + seedVectorToSearch,
1279+
"fl",
1280+
"id",
1281+
"debugQuery",
1282+
"true"),
1283+
"//result[@numFound='4']",
1284+
"//str[@name='parsedquery'][.='SeededKnnVectorQuery(SeededKnnVectorQuery{seed=KnnFloatVectorQuery:vector[0.1,...][4], seedWeight=null, delegate=KnnFloatVectorQuery:vector[1.0,...][4]})']");
1285+
}
1286+
1287+
@Test
1288+
public void
1289+
knnQueryWithBothSeedAndEarlyTermination_shouldPerformPatienceKnnVectorQueryFromSeeded() {
1290+
// Test to verify that when both the seed and the early termination parameters are provided, the
1291+
// PatienceKnnVectorQuery is executed using the SeededKnnVectorQuery.
1292+
String vectorToSearch = "[1.0, 2.0, 3.0, 4.0]";
1293+
1294+
assertQ(
1295+
req(
1296+
CommonParams.Q,
1297+
"{!knn f=vector topK=4 seedQuery='id:(1 4 7 8 9)' earlyTermination=true}"
1298+
+ vectorToSearch,
1299+
"fl",
1300+
"id",
1301+
"debugQuery",
1302+
"true"),
1303+
// Verify that 4 documents are returned
1304+
"//result[@numFound='4']",
1305+
// Verify that the parsed query is a nested PatienceKnnVectorQuery wrapping a
1306+
// SeededKnnVectorQuery
1307+
"//str[@name='parsedquery'][contains(.,'PatienceKnnVectorQuery(PatienceKnnVectorQuery{saturationThreshold=0.995, patience=7, delegate=SeededKnnVectorQuery{')]",
1308+
// Verify that the seed query contains the expected document IDs
1309+
"//str[@name='parsedquery'][contains(.,'seed=id:1 id:4 id:7 id:8 id:9')]",
1310+
// Verify that a seedWeight field is present — its value (BooleanWeight@<hash>) includes a
1311+
// hash code that changes on each run, so it cannot be asserted explicitly
1312+
"//str[@name='parsedquery'][contains(.,'seedWeight=')]",
1313+
// Verify that the final delegate is a KnnFloatVectorQuery with the expected vector and topK
1314+
// value
1315+
"//str[@name='parsedquery'][contains(.,'delegate=KnnFloatVectorQuery:vector[1.0,...][4]')]");
1316+
}
12011317
}

‎solr/solr-ref-guide/modules/query-guide/pages/dense-vector-search.adoc‎

Lines changed: 28 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,7 @@ The strategy implemented in Apache Lucene and used by Apache Solr is based on Na
4747

4848
It provides efficient approximate nearest neighbor search for high dimensional vectors.
4949

50-
See https://doi.org/10.1016/j.is.2013.10.006[Approximate nearest neighbor algorithm based on navigable small world graphs [2014]] and https://arxiv.org/abs/1603.09320[Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs [2018]] for details.
50+
See https://doi.org/10.1016/j.is.2013.10.006[Approximate nearest neighbor algorithm based on navigable small world graphs (2014)] and https://arxiv.org/abs/1603.09320[Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (2018)] for details.
5151

5252

5353
== Index Time
@@ -416,7 +416,7 @@ The search results retrieved are the k=10 nearest documents to the vector in inp
416416
|Optional |Default: `false`
417417
|===
418418
+
419-
Early termination is an HNSW optimization. Solr relies on the Lucene’s implementation of early termination for kNN queries, based on https://cs.uwaterloo.ca/~jimmylin/publications/Teofili_Lin_ECIR2025.pdf[Patience in Proximity: A Simple Early Termination Strategy for HNSW Graph Traversal in Approximate k-Nearest Neighbor Search].
419+
Early termination is an HNSW optimization. Solr relies on the Lucene’s implementation of early termination for kNN queries, based on https://cs.uwaterloo.ca/~jimmylin/publications/Teofili_Lin_ECIR2025.pdf[Patience in Proximity: A Simple Early Termination Strategy for HNSW Graph Traversal in Approximate k-Nearest Neighbor Search (2025)].
420420
+
421421
When enabled (true), the search may exit early when the HNSW candidate queue remains saturated over a threshold (saturationThreshold) for more than a given number of iterations (patience). Refer to the two parameters below for more details.
422422
+
@@ -457,6 +457,26 @@ Here's an example of a `knn` search using the early termination with input param
457457
[source,text]
458458
?q={!knn f=vector topK=10 earlyTermination=true saturationThreshold=0.989 patience=10}[1.0, 2.0, 3.0, 4.0]
459459

460+
`seedQuery`::
461+
+
462+
[%autowidth,frame=none]
463+
|===
464+
|Optional |Default: none
465+
|===
466+
+
467+
A query seed to initiate the vector search, i.e. entry points in the HNSW graph exploration. Solr relies on Lucene’s implementation of {lucene-javadocs}/core/org/apache/lucene/search/SeededKnnVectorQuery.html[SeededKnnVectorQuery] based on https://arxiv.org/pdf/2307.16779[Lexically-Accelerated Dense Retrieval (2023)].
468+
+
469+
The seedQuery is primarily intended to be a lexical query, guiding the vector search in a hybrid-like way through traditional query logic. Although a knn query can also be used as a seed — which might make sense in specific scenarios and has been verified by a dedicated test — this approach is not considered a best practice.
470+
+
471+
The seedQuery can also be used in combination with earlyTermination.
472+
473+
Here is an example of a `knn` search using a `seedQuery`:
474+
475+
[source,text]
476+
?q={!knn f=vector topK=10 seedQuery='id:(1 4 10)'}[1.0, 2.0, 3.0, 4.0]
477+
478+
The search results retrieved are the k=10 nearest documents to the vector in input `[1.0, 2.0, 3.0, 4.0]`. Documents matching the query `id:(1 4 10)` are used as entry points for the ANN search. If no documents match the seed, Solr falls back to a regular knn search without seeding, starting instead from random entry points.
479+
460480
=== knn_text_to_vector Query Parser
461481

462482
The `knn_text_to_vector` query parser encode a textual query to a vector using a dedicated Large Language Model(fine tuned for the task of encoding text to vector for sentence similarity) and matches k-nearest neighbours documents to such query vector.
@@ -824,7 +844,7 @@ cat > cuvs_configset/conf/solrconfig.xml << 'EOF'
824844
<luceneMatchVersion>10.0.0</luceneMatchVersion>
825845
<dataDir>${solr.data.dir:}</dataDir>
826846
<directoryFactory name="DirectoryFactory" class="${solr.directoryFactory:solr.NRTCachingDirectoryFactory}"/>
827-
847+
828848
<updateHandler class="solr.DirectUpdateHandler2">
829849
<updateLog>
830850
<str name="dir">${solr.ulog.dir:}</str>
@@ -853,7 +873,7 @@ cat > cuvs_configset/conf/solrconfig.xml << 'EOF'
853873
<int name="rows">10</int>
854874
</lst>
855875
</requestHandler>
856-
876+
857877
<requestHandler name="/update" class="solr.UpdateRequestHandler" />
858878
</config>
859879
EOF
@@ -865,16 +885,16 @@ cat > cuvs_configset/conf/managed-schema << 'EOF'
865885
<?xml version="1.0" ?>
866886
<schema name="schema-densevector" version="1.7">
867887
<fieldType name="string" class="solr.StrField" multiValued="true"/>
868-
<fieldType name="knn_vector" class="solr.DenseVectorField"
869-
vectorDimension="8"
870-
knnAlgorithm="cagra_hnsw"
888+
<fieldType name="knn_vector" class="solr.DenseVectorField"
889+
vectorDimension="8"
890+
knnAlgorithm="cagra_hnsw"
871891
similarityFunction="cosine" />
872892
<fieldType name="plong" class="solr.LongPointField" useDocValuesAsStored="false"/>
873893
874894
<field name="id" type="string" indexed="true" stored="true" multiValued="false" required="false"/>
875895
<field name="article_vector" type="knn_vector" indexed="true" stored="true"/>
876896
<field name="_version_" type="plong" indexed="true" stored="true" multiValued="false" />
877-
897+
878898
<uniqueKey>id</uniqueKey>
879899
</schema>
880900
EOF

0 commit comments

Comments
 (0)