Tuning Vector Indexes and Queries
On this page
SingleStore supports indexed vector search which can be used to improve the performance of similarity searches over larger vector data sets.
Vector indexes can significantly improve the speed of similarity search.
To obtain the performance improvement from vector indexes, it is important to only use vector indexes in specific cases, pick the right index type, and set the index-building and search parameters to meet your application's needs.
For background on vector indexes, also refer to Vector Indexing, Vector Type, Working with Vector Data, and Hybrid Search - Re-ranking and Blending Searches.
Choose a Vector Index
Vector indexes can significantly improve the speed of query execution over larger vector data sets.
When to Use a Vector Index
SingleStore recommends using vector indexes for searches over very large sets of vectors (e.WHERE
clause (filter) in the query which will eliminate many of the rows in the table, you may have acceptable performance without using an index.
Types of Vector Indexes
SingleStore supports several types of vector indexes, but recommends using IVF_
Example Table
The following example table represents product reviews from a web site.
-
id
: anINT
id -
review
: aTEXT
field which stores the text of the comment -
review_
: aembedding VECTOR
of 1024 dimensions which stores a vector embedding of the review -
category
: aVARCHAR
which stores a category assigned to the review
Below is the SQL that creates the example reviews
table.
CREATE TABLE reviews (id INT OPTION 'Integer',review TEXT OPTION 'SeekableString',review_embedding VECTOR(1024) NOT NULL OPTION 'SeekableString',category VARCHAR(256));
Note that the id
column is qualified OPTION 'Integer'
, and the review and review_
columns are qualified as OPTION 'Seekable String'
.OPTION
clauses specify how SingleStore should encode the data in those columns and will improve query performance.
The reviews
table will be used to demonstrate creating and tuning indexes and to discuss advantages, disadvantages, and tradeoffs during index creation and tuning.
General Advantages and Disadvantages
There are several index types and a variety of configuration parameters.
In general, IVF_
HNSW gives excellent performance (search time) and accuracy (recall); however, the size of an HNSW_
As the size of an IVF_
Where to Start
This section is intended to provide a starting point for adding an index to your vector data.reviews
table has been created and data has been loaded into that table.
Create the Vector Index
SingleStore recommends starting with an IVF_m
to be the number of dimensions of the vector column divided by 4.
The following command creates such an index for the reviews
table, where m
is set to 256 (which is 1024/4) and nlist
is set to 1024 and nprobe
is set to 20.nlist
and nprobe
.metric_
is set to DOT_
, which is also the default.
The parameter m
is an index building parameter that determines the number of subquantizers used in product quantization, a method for compressing vectors.nlist
specifies the number of clusters created during index build.nprobe
specifies the number of probes to be used at query time.
ALTER TABLE reviewsADD VECTOR INDEX ivf_pqfs(review_embedding)INDEX_OPTIONS'{"index_type":"IVF_PQFS","metric_type":"DOT_PRODUCT","m":256,"nlist":1024,"nprobe":20}';
After the index is loaded, run the OPTIMIZE
command for best performance.
OPTIMIZE TABLE reviews FULL;
Perform a Similarity Search Query
This example searches for the top 5 reviews that are most similar to a particular phrase.@query_
, which is a vector that represents the phrase to be searched on.@query_
is created from a JSON string; more commonly the @query_
would be obtained from an API or from querying a different table.
The query below uses an ORDER BY … LIMIT
query to look for the top 5 reviews that are most similar to @query_
.DESC
ordering is used in the ORDER BY
clause as the metric used to create the vector index was DOT_
.
SET @query_vec=('[0.002, 0.01, 0.001, ...]'):>VECTOR(1024);SELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsORDER BY score USE INDEX (ivf_pqfs) SEARCH_OPTIONS '{"k":50}' DESCLIMIT 5;
Key points to note about this query:
-
The
@query_
variable is cast to avec VECTOR
to ensure that@query_
is a validvec VECTOR
and to improve performance. -
The
SEARCH_
clause sets the search parameterOPTIONS k
to 50.A setting of k
equal to the theLIMIT
value * 10 is a good starting point.In this example LIMIT
is 5, sok
is set to 5*10 = 50.
The USE INDEX
clause in the query above specifies that the index named ivf_
should be used in the query.USE INDEX
is included for completeness, but is not necessary in this query.
Verify a Vector Index is Being Used
It is important to verify that your query is using a vector index.
-
The metric in the query (dot product vs.
euclidean distance) matches the metric used to create the index. -
The order in the
ORDER BY
clause (DESC
vs.ASC
) in the search query matches the metric.
You can verify that a vector index is being used in a query with EXPLAIN
as shown below.
SET @query_vec = ('[0.002, 0.01, 0.0001, ...]'):>VECTOR(1024);EXPLAINSELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsORDER BY score USE INDEX (ivf_pqfs) SEARCH_OPTIONS '{"k":50}' DESCLIMIT 5;
+----------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+----------------------------------------------------------------------------------------------------------------------------+
| Project [remote_0.id, remote_0.review, remote_0.score] |
| TopSort limit:5 [remote_0.score DESC] |
| Gather partitions:all alias:remote_0 parallelism_level:segment |
| Project [reviews.id, reviews.review, DOT_PRODUCT(reviews.review_embedding,(@query_vec:>vector(1024, F32) NOT NULL)) AS score] |
| TopSort limit:5 [DOT_PRODUCT(reviews.review_embedding,(@query_vec:>vector(3, F32) NOT NULL)) DESC] |
| ColumnStoreFilter [INTERNAL_VECTOR_SEARCH(0, (@query_vec:>vector(1024, F32) NOT NULL), 5, '{\"k\" : 50 }') index] |
| ColumnStoreScan dbname.reviews, SORT KEY __UNORDERED () table_type:sharded_columnstore |
+----------------------------------------------------------------------------------------------------------------------------+
The ColumnStoreFilter line of the EXPLAIN
output above shows INTERNAL_
which indicates that the vector index is being used.INTERNAL_
is not in the ColumnStoreFilter
line, the vector index is not being used.
Test Index Performance
To understand if an index meets the needs of your application, you will want to test the query accuracy (recall) and search time.
Test Accuracy via Recall
As described previously, recall measures the accuracy of the results returned.
The query below contains an empty USE INDEX clause which will disable the use of the vector index.
SET @query_vec = ('[0.002, 0.01, 0.0001, ...]'):>VECTOR(1024);SELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsORDER BY score USE INDEX() DESCLIMIT 5;
To obtain the recall of the indexed query, perform the following steps:
-
Run the query without the index using the empty
USE INDEX()
clause as shown above and note the results.This will give you the actual top N results to your query. (N=5 in the query above. ) -
Run the query with the index and note the results.
This gives you the top N results as determined by the indexed search. Remember that the indexed search returns approximate results. -
Determine how many of the top N results from the indexed query results are in the actual top N results.
For example, if the query with the index returned 4 of the 5 actual results, the recall is 4 / 5 or 80%. Note that the index query will return 5 results. For determining recall, the question is how many of those 5 results are in the results from the query without the index.
Measure Search Time
When measuring search time, it is important to exclude the run time of the first query and to exclude the round-trip time between the client and server.
Perform the following to measure search time.PROFILE
has limited overhead and is acceptable for initial performance testing.PROFILE
.
SET @query_vec = ('[0.002, 0.01, 0.0001, ...]'):>VECTOR(1024);PROFILESELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsORDER BY score USE INDEX (ivf_pqfs) SEARCH_OPTIONS '{"k":50}' DESCLIMIT 5;
Tune IVF_ PQFS Parameters
This section discusses tuning an IVF_m
, nprobe
, and nlist
and one search parameter k
.m
, move on to k
and nprobe
, finally nlist
.
m
The parameter m
is an index building parameter that determines the number of subquantizers used in product quantization.
The parameter m
effectively trades off index size and accuracy of results.m
gives greater accuracy (recall) but the index size is larger.m
gives a smaller index, but the results will have lower accuracy.m
must be set so that dimensions % m
= 0 and m defaults to 32.
Consider values for m such as: dimensions/2, dimensions/4, dimensions/8.
k
The parameter k
is an index search parameter which can be specified at query time.k
is shown below.
The following query uses the reviews
table defined above.@query_
is a VECTOR
representing a phrase the user is interested in and the query searches for reviews in the reviews
table that are similar to @query_
.@query_
.
SET @query_vec = ('[0.002, 0.01, 0.0001, ...]'):>VECTOR(1024);SELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsORDER BY score USE INDEX (ivf_pqfs) SEARCH_OPTIONS '{"k":50}' DESCLIMIT 5;
In this query, k
determines the number of rows output by the vector index scan, that is k
determines the number of rows that the vector index scan produces before the ORDER BY … LIMIT
clause is applied.k
give more accurate results (better recall), but increase search times.k
must be >= limit, where limit is from ORDER BY … LIMIT
clause and the default for k
is the LIMIT
value.
SingleStore suggests starting with a k
of 10 * LIMIT
and adjusting to get the recall and search time needed for your application.
Note
A common cause of poor recall with IVF_k
.
nprobe
nprobe is a search parameter which specifies the number of probes to be used at query time.nlist
clusters and then the query search is done by searching nprobe
of the nearest clusters.nprobe
to 20; nprobe
cannot be greater than nlist
.
A query using a vector index will search an nprobe
/nlist
fraction of the data.
nlist
nlist
is an index-building parameter which specifies the number of inverted lists created when the index is built.nlist
controls the number of centroids generated by k-means clustering.nlist
= 1024; nlist
is the last of the parameters you should try tuning.
If you fix nprobe
and increase nlist
, you get faster queries with worse accuracy; however, the results depend on data distribution and may not change monotonically.nlist
to be of the same order as the square root of the number of rows in a segment.
The following query finds the segment size in number of rows for the reviews
table.
SELECT database_name, table_name,AVG(rows_count) AS average_segment_size_in_rowsFROM information_schema.columnar_segmentsWHERE database_name = 'dbname' AND table_name = 'reviews'GROUP BY ALL;
Tune HNSW_ FLAT Parameters
HNSW_
HNSW_M
and efConstruction
, and one search parameter, ef
.
For tuning HNSW_ef
, which trades recall for performance.ef
gives better accuracy (higher recall), but slower search.ef
increases exhaustiveness of graph search which gives better accuracy (recall) at the cost of slower search performance.ef
set to 120.ef
.
SingleStore recommends starting with setting M
to 12 and efConstruction
to 120.
Approximate Vector Index Memory Use
Vector indexes are stored in memory in SingleStore and can be large.
To approximate the amount of memory used by a vector index, calculate the amount of Malloc_
used before and after the vector index is loaded into memory.Malloc_
.
Note
An improved method for determining the amount of memory used by a vector index will be provided in an upcoming release.
The following example shows how to perform (calculate) this approximation.reviews
table created above.
Important
To calculate the memory used by a vector index, the following steps must be done in order and the steps must be done on a system with minimal other activity.Malloc_
is used by multiple operators in SingleStore so it is important that the system is dedicated to this memory calculation while it is running to avoid other uses of Malloc_
that could impact this calculation.
1. Add a Vector Index
First, add a vector index on the table.HNSW_
; create the type of index that you want to test.
ALTER TABLE reviews ADD VECTOR INDEX hnsw(review_embedding)INDEX_OPTIONS '{"index_type":"HNSW_FLAT"}';
At this point the vector index has been built on disk, but has not been loaded into memory.
2. Calculate the Initial Value of Malloc_ active_ memory
Use the following query to get the value of Malloc_
before the vector index is loaded into memory.Malloc_
across all nodes in the cluster.
SELECT SUM (variable_value) INTO @m1FROM information_schema.mv_global_statusWHERE variable_name = "Malloc_active_memory";
3. Load the Vector Index into Memory
To force the vector index to be loaded into memory, run a query that uses the vector index.
To do so, run the following two queries which will cause the vector index to be loaded into memory.reviews
table and the second query uses that vector in a nearest neighbor search.
In the first query, it is necessary to select a vector from the reviews
table to use as a query vector in the subsequent query (as opposed to using a random query vector) in order to force the vector index to be loaded into memory.
SET @query_vec =(SELECT review_embeddingFROM reviews LIMIT 1);SELECT @query_vec <*> review_embedding AS sINTO @s2FROM reviewsORDER BY sUSE INDEX (hnsw)DESC LIMIT 1;
4. Find the Approximate Memory Use
Re-run the sum query to get the value of Malloc_
after the vector index has been loaded in memory.@m2
and @m1
to obtain the amount of memory used by the vector index.
SELECT SUM (variable_value) INTO @m2FROM information_schema.mv_global_statusWHERE variable_name = "Malloc_active_memory";SELECT @m2-@m1;
Indexed Vector Search with a Filter
Similarity search using a vector index can be combined with standard SQL filters.k
, so that sufficient results are returned.
A query using filtered ANN search is shown below.@query_
using an ORDER BY … LIMIT
query, and uses the filter WHERE category = "Food"
to limit the results to those reviews in the category "Food.
SELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsWHERE category = "Food"ORDER BY score USE INDEX (hnsw) DESCLIMIT 5;
This query uses the index named hnsw
.hnsw
index is first scanned to find reviews that are similar to @query_
, and then the category = "Food"
filter is applied.
The k
parameter, which controls the number of candidates that the index scan will output, is not set in this query and defaults to the value of LIMIT
, which is 5 in this example.hnsw
index.category = "Food"
) is then applied to these 5 candidates, which may yield less than 5 rows in the query result.
To ensure that there are 5 rows in the query result when the query contains a filter, the value of k
must be increased.k
will increase the number of results returned from the index scan, which is also expected to increase the number of results returned from the query until the limit is reached.
When a filter is used with an ANN search, SingleStore recommends setting k
to: (the value of k
without a filter) / (selectivity of the filter).category = "Food"
has a selectivity of 25%, meaning that 25% of the rows in the reviews table are in the category "Food".k
would be adjusted to: (the initial value of k
) / 25%, which is equal to (5/0.
The adjusted query is shown below, with k
set to 20.
SELECT id, review,review_embedding <*> @query_vec AS scoreFROM reviewsORDER BY score USE INDEX (hnsw) SEARCH_OPTIONS '{"k":20}' DESCWHERE category = "Food"LIMIT 5;
In this query, 20 candidates will be returned from the scan of the hnsw
index, those 20 candidates will be filtered by category = "Food"
, and the top 5 of those candidates will be returned as the query result.
As demonstrated in the example above, increasing the value of k
can lead to better results for ANN search queries with filters.
While this example showed how to adjust the k
parameter for HNSW_k
should be adjusted to: (the value of k
without filter) / (selectivity of the filter).
-
For HNSW_
FLAT indexes, SingleStore recommends letting k be the default when there is no filter. -
For IVF_
PQFS indexes, SingleStore recommends setting k
toLIMIT
*10 when there is no filter.
This is because IVF_k
, one to adjust for the vector compression and one to adjust for selectivity.
Related Topics
Last modified: August 14, 2024