ベクトル最近傍探索(similarity search)とは、ベクトル空間内での距離に基づき、クエリベクトルに最も近いベクトル群を特定する検索手法です。計算過程では特定の距離測定方法(distance metric)が使用されますが、最終的には距離が小さい順に上位k個の最も近いベクトルが出力されます。
この記事では、OceanBaseの2つのベクトル検索方法を紹介します。ひとつはフルスキャンによる厳密な最近傍探索、もうひとつはベクトルインデックスを使用した近似最近傍探索です。また、具体的な例を通じてその使用方法を説明します。
説明
読みやすさのため、本文ではベクトル最近傍探索を「ベクトル検索」、厳密な最近傍探索を「厳密検索」、近似的な最近傍探索を「近似検索」と略称します。
厳密検索の実行
厳密検索とは、データセット内のすべてのベクトルとクエリベクトルとの距離を計算する、フルスキャン方式の検索です。この手法は、検索結果の正確性が完全に保証される一方で、データ規模が大きくなるにつれて計算量が増大し、検索速度が著しく低下するという点があります。
実際の処理では、システムがクエリベクトルvₑと空間内の全ベクトルとの距離を一つずつ計算・比較します。すべての計算が完了した後、最も距離が近い上位k個のベクトルが検索結果として返されます。
例：ユークリッド距離検索
ユークリッド距離検索(Euclidean Similarity Search)は、ベクトル空間内でクエリベクトルに最も近い上位k個のベクトルを検索する方法で、ユークリッド距離を距離の測定基準として使用します。以下の例は、厳密検索を使用して、テーブルからクエリベクトルに最も近い5個のベクトルを取得する方法を示しています。
-- テスト用テーブルの作成
CREATE TABLE t1 (
id INT PRIMARY KEY,
c1 VECTOR(3)
);
-- データの挿入
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]');
-- 厳密検索の実行
SELECT c1
FROM t1
ORDER BY l2_distance(c1, '[0.1, 0.2, 0.3]') LIMIT 5;
戻り値は以下のようになります：
+---------------+
| 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
実行計画の分析
上記の例の実行計画を取得するには、以下のSQLクエリを実行します：
EXPLAIN SELECT c1
FROM t1
ORDER BY l2_distance(c1, '[0.1, 0.2, 0.3]') LIMIT 5;
戻り値は以下のようになります：
+---------------------------------------------------------------------------------------------+
| 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
分析は以下の通りです。
実行方式：
- フルスキャン方式を採用しており、テーブル内のすべてのデータをトラバースする必要があります。実行計画における
TABLE FULL SCAN操作に該当します。この操作はテーブルt1内のすべてのデータをスキャンします。 - 各レコードのベクトル距離を計算し、その後にソートを行います。実行計画における
TOP-N SORT操作に該当します。l2_distance関数を使ってベクトルの距離を計算し、距離が小さい順に並べ替えます。 - 最後に、距離が最小の上位5つのレコードを返します。実行計画における
topn(5)設定に該当します。ソート後の上位5つのレコードだけが返されます。
- フルスキャン方式を採用しており、テーブル内のすべてのデータをトラバースする必要があります。実行計画における
性能：
- 利点：結果が完全に正確で、返されるのは実際の最近傍です。
- 欠点：テーブル全体をスキャンし、すべてのベクトル距離を計算するため、データ量が増えるとパフォーマンスが著しく低下します。
適用シナリオ：
- データ量が比較的小さい場合。
- 結果の正確性が非常に重要な場合。
- 大規模データセットに対するリアルタイムのクエリには不向きです。
ベクトルインデックスを使用した近似検索の実行
ベクトルインデックス検索では、近似最近傍（Approximate Nearest Neighbor、ANN）戦略を採用し、事前に構築されたインデックス構造によって検索プロセスを高速化します。結果の精度は100%保証されませんが、検索性能を大幅に向上させることができ、実際の応用シーンでは精度と性能の間で良好なバランスを取ることが可能です。
例：HNSWインデックスによる近似検索
-- テーブル作成と同時にHNSWベクトルインデックスを作成
CREATE TABLE t2 (
id INT PRIMARY KEY,
vec VECTOR(3),
VECTOR INDEX idx(vec) WITH (distance=l2, type=hnsw, lib=vsag)
);
-- テストデータの挿入
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]');
-- 近似検索を実行し、最も類似する5件のデータを返す
SELECT id, vec
FROM t2
ORDER BY l2_distance(vec, '[0.1, 0.2, 0.3]')
APPROXIMATE
LIMIT 5;
データ量が少ないため、返される結果は上記の厳密検索の結果と一致します。
+------+---------------+
| 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
実行計画の分析
上記の例の実行計画を取得します：
EXPLAIN SELECT id, vec
FROM t2
ORDER BY l2_distance(vec, '[0.1, 0.2, 0.3]')
APPROXIMATE
LIMIT 5;
戻り値は以下のようになります：
+--------------------------------------------------------------------------------------------------------------------+
| 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
分析は以下の通りです。
実行方式：
- ベクトルインデックススキャン方式を採用し、事前に構築されたHNSWインデックスを通じて類似ベクトルを直接特定します。実行計画における
VECTOR INDEX SCAN操作に該当します。この操作はインデックスt2(idx)を使用して検索を行います。 - インデックスのグラフ構造を利用して近傍点を高速に発見するため、すべてのベクトルとの距離計算は不要です。実行計画における
is_index_back=trueの設定に該当します。インデックスを介してテーブルにアクセスし完全なデータを取得することを示します。 - 最終的に、インデックスが最も類似していると判断した5件のレコードを返します。実行計画における
output([t2.id], [t2.vec])に対応し、idとベクトルデータを返すことを示します。
- ベクトルインデックススキャン方式を採用し、事前に構築されたHNSWインデックスを通じて類似ベクトルを直接特定します。実行計画における
性能：
- 利点：検索性能が高く、データ量の増加に対しても安定しています。
- 欠点：結果にはわずかな誤差が生じる可能性があり、100%の正確性は保証されません。
適用シナリオ：
- 大規模データセットのリアルタイム検索。
- 検索性能が特に重要なシナリオ。
- 結果に多少の誤差が許容されるシナリオ。
まとめ
二つの検索方式の比較概要は以下の通りです。
| 比較項目 | 厳密検索 | 近似検索 |
|---|---|---|
| 実行方式 | フルテーブルスキャン(TABLE FULL SCAN)してからソートする |
ベクトルインデックス(VECTOR INDEX SCAN)による直接検索 |
| 実行計画 | TABLE FULL SCANとTOP-N SORTの2つの操作を含む |
VECTOR INDEX SCANの1つの操作のみを含む |
| 性能 | 全テーブルデータをスキャンしソートする必要があり、データ量の増加に伴い性能が著しく低下する | インデックスにより対象データを直接特定するため、性能が安定している |
| 結果の正確性 | 100%正確であり、真の最近傍を返すことが保証される | 近似的な正確さであり、わずかな誤差が生じる可能性がある |
| 適用シナリオ | データ量が少なく、正確性に対する要求が高いシナリオ | 大規模データセットで、性能に対する要求が高いシナリオ |
関連記事
- その他のSQL関数の使用方法については、SQL関数の使用をご参照ください。
- ベクトルインデックスの詳細な説明と使用例については、ベクトルインデックスの作成をご参照ください。
- 大規模なパフォーマンステストを実施する場合は、VectorDBBenchmarkツールを使用してテストデータセットを生成し、厳密検索と近似検索の性能差をより明確に比較することをお勧めします。