Vector nearest neighbor search (Similarity Search) is a search method based on distance metrics in vector spaces. Its core task is to identify the set of vectors closest to a query vector. Although a specific distance metric (Distance Metric) is used during computation, the final output consists of the Top K nearest vectors sorted by distance from smallest to largest.
This topic describes two vector search methods in OceanBase AI Database: exact nearest neighbor search based on full scanning and approximate nearest neighbor search based on vector indexes. Specific examples are provided to illustrate their usage.
Notice
For ease of reading, vector nearest neighbor search is referred to as vector search, exact nearest neighbor search as exact search, and approximate nearest neighbor search as approximate search in the text.
Perform an exact search
Exact search employs a full scanning strategy, calculating the distance between the query vector and all vectors in the dataset to find the nearest neighbors. This method ensures complete accuracy of the search results. However, due to the need for full-distance computation, search performance degrades significantly with data scale.
During an exact search, the system calculates distances between the query vector (v_e) and every vector in the vector space. After completing the full-distance computation, the system returns the k vectors with the closest distances as the search result.
Example: Euclidean search
Euclidean similarity search is used to find the top-k vectors closest to the query vector in a vector space, using the Euclidean distance as the metric. The following example shows how to use exact search to find the five vectors closest to the query vector from a table:
-- Create a test table
CREATE TABLE t1 (
id INT PRIMARY KEY,
c1 VECTOR(3)
);
-- Insert data
INSERT INTO t1 VALUES
(1, '[0.1, 0.2, 0.3]'),
(2, '[0.2, 0.3, 0.4]'),
(3, '[0.3, 0.4, 0.5]'),
(4, '[0.4, 0.5, 0.6]'),
(5, '[0.5, 0.6, 0.7]'),
(6, '[0.6, 0.7, 0.8]'),
(7, '[0.7, 0.8, 0.9]'),
(8, '[0.8, 0.9, 1.0]'),
(9, '[0.9, 1.0, 0.1]'),
(10, '[1.0, 0.1, 0.2]');
-- Perform an exact search
SELECT c1
FROM t1
ORDER BY l2_distance(c1, '[0.1, 0.2, 0.3]') LIMIT 5;
The return result is as follows:
+---------------+
| c1 |
+---------------+
| [0.1,0.2,0.3] |
| [0.2,0.3,0.4] |
| [0.3,0.4,0.5] |
| [0.4,0.5,0.6] |
| [0.5,0.6,0.7] |
+---------------+
5 rows in set
Execution plan analysis
Obtain the execution plan for the preceding example:
EXPLAIN SELECT c1
FROM t1
ORDER BY l2_distance(c1, '[0.1, 0.2, 0.3]') LIMIT 5;
The return result is as follows:
+---------------------------------------------------------------------------------------------+
| Query Plan |
+---------------------------------------------------------------------------------------------+
| ================================================= |
| |ID|OPERATOR |NAME|EST.ROWS|EST.TIME(us)| |
| ------------------------------------------------- |
| |0 |TOP-N SORT | |5 |3 | |
| |1 |└─TABLE FULL SCAN|t1 |10 |3 | |
| ================================================= |
| Outputs & filters: |
| ------------------------------------- |
| 0 - output([t1.c1]), filter(nil), rowset=16 |
| sort_keys([l2_distance(t1.c1, cast('[0.1, 0.2, 0.3]', ARRAY(18, -1))), ASC]), topn(5) |
| 1 - output([t1.c1]), filter(nil), rowset=16 |
| access([t1.c1]), partitions(p0) |
| is_index_back=false, is_global_index=false, |
| range_key([t1.id]), range(MIN ; MAX)always true |
+---------------------------------------------------------------------------------------------+
14 rows in set
Analysis:
Execution method:
- Uses a full table scan, which requires traversing all data in the table. This corresponds to the
TABLE FULL SCANoperation in the execution plan, which scans all data in tablet1. - Calculates vector distances for each record and then sorts the results. This corresponds to the
TOP-N SORToperation in the execution plan. It uses thel2_distancefunction to calculate vector distances and sorts the results in ascending order of distance. - Finally, returns the five records with the smallest distances. This corresponds to the
topn(5)setting in the execution plan, indicating that only the first five sorted records are returned.
- Uses a full table scan, which requires traversing all data in the table. This corresponds to the
Performance characteristics:
- Advantage: The results are completely accurate, ensuring the returned vectors are truly the nearest neighbors.
- Disadvantage: Requires scanning the entire table and calculating distances for all vectors, leading to significant performance degradation as data volume increases.
Application scenarios:
- Scenarios with a small amount of data.
- Scenarios where the accuracy of search results is extremely important.
- Not suitable for real-time queries on large-scale datasets.
Perform approximate searches by using vector indexes
Vector index search employs an Approximate Nearest Neighbor (ANN) strategy to accelerate the search process through a pre-built index structure. While it cannot guarantee 100% result accuracy, it significantly improves search performance, enabling a good balance between accuracy and performance in practical applications.
Example: Approximate search by using the HNSW index
-- Create an HNSW vector index on a table
CREATE TABLE t2 (
id INT PRIMARY KEY,
vec VECTOR(3),
VECTOR INDEX idx(vec) WITH (distance=l2, type=hnsw, lib=vsag)
);
-- Insert test data
INSERT INTO t2 VALUES
(1, '[0.1, 0.2, 0.3]'),
(2, '[0.2, 0.3, 0.4]'),
(3, '[0.3, 0.4, 0.5]'),
(4, '[0.4, 0.5, 0.6]'),
(5, '[0.5, 0.6, 0.7]'),
(6, '[0.6, 0.7, 0.8]'),
(7, '[0.7, 0.8, 0.9]'),
(8, '[0.8, 0.9, 1.0]'),
(9, '[0.9, 1.0, 0.1]'),
(10, '[1.0, 0.1, 0.2]');
-- Perform an approximate search and return the 5 most similar data records.
SELECT id, vec
FROM t2
ORDER BY l2_distance(vec, '[0.1, 0.2, 0.3]')
APPROXIMATE
LIMIT 5;
The returned results are as follows. Due to the small amount of data, they are consistent with the exact search results mentioned above:
+------+---------------+
| id | vec |
+------+---------------+
| 1 | [0.1,0.2,0.3] |
| 2 | [0.2,0.3,0.4] |
| 3 | [0.3,0.4,0.5] |
| 4 | [0.4,0.5,0.6] |
| 5 | [0.5,0.6,0.7] |
+------+---------------+
5 rows in set
Execution plan analysis
Obtain the execution plan for the example above:
EXPLAIN SELECT id, vec
FROM t2
ORDER BY l2_distance(vec, '[0.1, 0.2, 0.3]')
APPROXIMATE
LIMIT 5;
The returned result is as follows:
+--------------------------------------------------------------------------------------------------------------------+
| Query Plan |
+--------------------------------------------------------------------------------------------------------------------+
| ==================================================== |
| |ID|OPERATOR |NAME |EST.ROWS|EST.TIME(us)| |
| ---------------------------------------------------- |
| |0 |VECTOR INDEX SCAN|t2(idx)|10 |29 | |
| ==================================================== |
| Outputs & filters: |
| ------------------------------------- |
| 0 - output([t2.id], [t2.vec]), filter(nil), rowset=16 |
| access([t2.id], [t2.vec]), partitions(p0) |
| is_index_back=true, is_global_index=false, |
| range_key([t2.__vid_1750162978114053], [t2.__type_17_1750162978114364]), range(MIN,MIN ; MAX,MAX)always true |
+--------------------------------------------------------------------------------------------------------------------+
11 rows in set
Analysis:
Execution method:
- Uses a vector index scan to directly locate similar vectors through the pre-built HNSW index. This corresponds to the
VECTOR INDEX SCANoperation in the execution plan, which searches via the indext2(idx). - Leverages the graph structure of the index to quickly find nearest neighbors without calculating distances for all vectors. This corresponds to the
is_index_back=truesetting in the execution plan, indicating that full data is fetched from the table through the index. - Finally, returns the 5 records deemed most similar by the index. This corresponds to
output([t2.id], [t2.vec])in the execution plan, indicating the return of id and vector data.
- Uses a vector index scan to directly locate similar vectors through the pre-built HNSW index. This corresponds to the
Performance characteristics:
- Advantage: High search performance that remains stable as data volume increases.
- Disadvantage: Results may contain minor errors; 100% accuracy is not guaranteed.
Application scenarios:
- Real-time search on large-scale datasets.
- Scenarios requiring high search performance.
- Scenarios where minor result errors are acceptable.
Comparison summary
A comparison summary of the two search methods is as follows:
Comparison items |
Exact search |
Approximate search |
|---|---|---|
| Execution method | Full table scan (TABLE FULL SCAN) and sort |
Search directly through a vector index (VECTOR INDEX SCAN) |
| Execution plan | Contains two operators: TABLE FULL SCAN and TOP-N SORT |
Contains only one operator: VECTOR INDEX SCAN |
| Performance characteristics | Full table scan and sort are required, and the performance significantly degrades as data volume increases. | The index is used to directly locate the target data, and the performance is stable. |
| Accuracy | 100% accuracy, ensuring the returned neighbor is truly the nearest one. | Approximately accurate, with possible minor errors |
| Application scenarios | Scenarios with small data volumes and high accuracy requirements | Large-scale datasets, high-performance scenarios |
References
- For more information about SQL functions, see Use SQL functions
- For more information about vector indexes and examples, see Overview of dense indexes