HNSWベクトル索引のオプティマイザ計画
Hierarchical Navigable Small World (HNSW)グラフは、インメモリー近傍グラフ・ベクトル索引の形式です。ベクトル近似類似検索には非常に効率的なインデックスです。
最も単純なケースでは、問合せには単一の表があり、リレーショナル・フィルタ述語や副問合せは含まれていません。次の問合せ例は、この状況を示しています。
SELECT chunk_id, chunk_data
FROM doc_chunks
ORDER BY VECTOR_DISTANCE( chunk_embedding, :query_vector, COSINE )
FETCH APPROX FIRST 4 ROWS ONLY WITH TARGET ACCURACY 80;オプティマイザで索引を使用することが決定された場合、対応する実行計画は次のようになります(操作ID 5から開始されます)。
上位k件の類似ベクトルは、最初にHNSWベクトル索引を使用して識別されます。それぞれについて、対応する行が元表で識別され、必要な選択された列が抽出されます。
---------------------------------------------------------
| Id | Operation | Name |
---------------------------------------------------------
| 0 | SELECT STATEMENT | |
|* 1 | COUNT STOPKEY | |
| 2 | VIEW | |
|* 3 | SORT ORDER BY STOPKEY | |
| 4 | TABLE ACCESS BY INDEX ROWID| DOC_CHUNKS |
| 5 | VECTOR INDEX HNSW SCAN | DOCS_HNSW_IDX5 |
---------------------------------------------------------
ノート:
Hierarchical Navigable Small World (HNSW)ベクトル索引の構造には、索引内の各ベクトルの対応する元表の行のrowidsが含まれています。
ただし、次の例に示すように、問合せには従来のリレーショナル・データ・フィルタが含まれている場合があります。
SELECT chunk_id, chunk_data
FROM doc_chunks
WHERE doc_id=1
ORDER BY VECTOR_DISTANCE( chunk_embedding, :query_vector, COSINE )
FETCH APPROX FIRST 4 ROWS ONLY WITH TARGET ACCURACY 80;その場合、オプティマイザでHNSWベクトル索引を使用する実行計画が生成される主な代替の操作は基本的に2つです。これらの2つの代替の操作は、プレフィルタリングおよびインフィルタリングと呼ばれます。
プレフィルタリングとインフィルタリングの主な違いは次のとおりです。
- プレフィルタリングは、最初に元表に対してフィルタリング評価を実行し、対応するベクトルのHNSWベクトル索引のみをトラバースします。これは、フィルタ述語が選択的である(つまり、ほとんどの行がフィルタで除外される)場合、非常に高速です。
- 一方、インフィルタリングでは、最初にHNSWベクトル索引をトラバースし、各ベクトル一致候補に対してのみフィルタリングが実行されます。これは、多くの行がフィルタ述語を通過する場合のプレフィルタリングよりも優れています。この場合、考慮するベクトル候補の数は、HNSWベクトル索引のトラバース中に、フィルタを通過する行の数よりはるかに少ない可能性があります。
インフィルタリングとプレフィルタリングの両方で、オプティマイザでは、類似検索操作の前または後に、選択リストから推定される列を処理することが選択される場合があります。後に実行した場合、これは後戻り結合操作と呼ばれます。前に実行した場合は、後戻り結合なし操作と呼ばれます。この2つの間のトレードオフは、類似検索によって返される行数によって異なります。
これら4つの可能性を説明するために、一般的な実行計画を次に示します:
ノート:
使用しているバージョンに応じて、これらの計画のバリエーションを見つけることができます。ただし、アイデアは同じであるため、次の計画は説明のみを目的としています。後戻り結合ありのプレフィルタ(操作ID 9から開始)
フィルタ処理されたrowidsは、HNSWベクトル索引で関連するベクトルが識別される前に、元表で最初に識別され、補助マッピング表に結合されます。関連する元表の行が識別され、必要な選択された列が抽出されます。
--------------------------------------------------------------------------------------------------------
| Id | Operation | Name |
--------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | |
|* 1 | COUNT STOPKEY | |
| 2 | VIEW | |
|* 3 | SORT ORDER BY STOPKEY | |
|* 4 | TABLE ACCESS BY INDEX ROWID | DOC_CHUNKS |
| 5 | VECTOR INDEX HNSW SCAN PRE-FILTER| DOCS_HNSW_IDX3 |
| 6 | VIEW | VW_HPJ_56DFF779 |
|* 7 | HASH JOIN RIGHT OUTER | |
| 8 | TABLE ACCESS FULL | VECTOR$DOCS_HNSW_IDX3$81357_82726_0$HNSW_ROWID_VID_MAP |
|* 9 | TABLE ACCESS FULL | DOC_CHUNKS |
--------------------------------------------------------------------------------------------------------ノート:
- HNSW索引では、補助表および関連する索引を使用して、ベクトルの
idsとrowidsの間のマッピングなどの索引情報を格納します。主にVECTOR$<index name>$HNSW_ROWID_VID_MAP。 - 結合の場合は、次のような計画も確認できます:
NESTED LOOPS OUTER TABLE ACCESS FULL DOC_CHUNKS TABLE ACCESS BY INDEX ROWID VECTOR$DOCS_HNSW_IDX3$81357_82726_0$HNSW_ROWID_VID_MAP INDEX UNIQUE SCAN SYS_C008586
後戻り結合なしのプレフィルタ(操作ID 8から開始)
関連する列を含むフィルタ処理されたrowidsは、まず実表で識別され、バッファされます。結果は、HNSWベクトル索引が最上位K件のベクトルを識別する前に、補助マッピング表に結合されます。識別されたベクトルについては、関連付けられた元表の列が表示されます。
-------------------------------------------------------------------------------------------------------
| Id | Operation | Name |
-------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | |
|* 1 | COUNT STOPKEY | |
| 2 | VIEW | |
|* 3 | SORT ORDER BY STOPKEY | |
| 4 | VECTOR INDEX HNSW SCAN PRE-FILTER| DOCS_HNSW_IDX3 |
| 5 | VIEW | VW_HPF_B919B0A0 |
|* 6 | HASH JOIN RIGHT OUTER | |
| 7 | TABLE ACCESS FULL | VECTOR$DOCS_HNSW_IDX3$81357_82726_0$HNSW_ROWID_VID_MAP |
|* 8 | TABLE ACCESS FULL | DOC_CHUNKS |
-------------------------------------------------------------------------------------------------------後戻り結合ありのインフィルタ(操作ID 5から開始)
HNSWベクトル索引が最初にトラバースされ、識別されたベクトルごとに、元表に対応するrowidのフィルタが適用されます。フィルタを通過する上位K件のrowidsが識別されると、元表の列が抽出されます。
----------------------------------------------------------------
| Id | Operation | Name |
----------------------------------------------------------------
| 0 | SELECT STATEMENT | |
|* 1 | COUNT STOPKEY | |
| 2 | VIEW | |
|* 3 | SORT ORDER BY STOPKEY | |
|* 4 | TABLE ACCESS BY INDEX ROWID | DOC_CHUNKS |
| 5 | VECTOR INDEX HNSW SCAN IN-FILTER| DOCS_HNSW_IDX3 |
| 6 | VIEW | VW_HIJ_B919B0A0 |
|* 7 | TABLE ACCESS BY USER ROWID | DOC_CHUNKS |
----------------------------------------------------------------後戻り結合なしのインフィルタ(操作ID 4から開始)
HNSWベクトル索引が最初にトラバースされ、識別されたベクトルごとに、元表に対応するrowidのフィルタが適用され、関連する列が抽出されます。上位K件のベクトルが識別されると、対応する実表の列が表示されます。
---------------------------------------------------------------
| Id | Operation | Name |
---------------------------------------------------------------
| 0 | SELECT STATEMENT | |
|* 1 | COUNT STOPKEY | |
| 2 | VIEW | |
|* 3 | SORT ORDER BY STOPKEY | |
| 4 | VECTOR INDEX HNSW SCAN IN-FILTER| DOCS_HNSW_IDX3 |
| 5 | VIEW | VW_HIF_B919B0A0 |
|* 6 | TABLE ACCESS BY USER ROWID | DOC_CHUNKS |
---------------------------------------------------------------オプティマイザ計画のHNSW索引
HNSW索引計画では、内部表および関連する索引を使用して、ベクトルidsとrowids間のマッピングなどの索引情報を格納できます。主にVECTOR$<index name>$HNSW_ROWID_VID_MAP。
表8-1 HNSWオプション
| 操作 | オプション | Object_name |
|---|---|---|
| TABLE ACCESS | FULL | VECTOR$<vector-index-name>$<id>$HNSW_ROW_VID_MAP |
| TABLE ACCESS | STORAGE FULL | VECTOR$<vector-index-name>$<id>$HNSW_ROW_VID_MAP |
| TABLE ACCESS | INMEMORY FULL | VECTOR$<vector-index-name>$<id>$HNSW_ROW_VID_MAP |
インメモリー・オブジェクトであるHNSW索引自体の場合、計画はVECTOR INDEX操作を使用します。オブジェクト名GALAXIES_HNSW_INXは、ユーザー指定のHNSW索引名の例として示されています:
| 操作 | オプション | Object_name |
|---|---|---|
| VECTOR INDEX | HNSW SCAN | GALAXIES_HNSW_INX |
| VECTOR INDEX | HNSW SCAN PRE-FILTER | GALAXIES_HNSW_INX |
| VECTOR INDEX | HNSW SCAN IN-FILTER | GALAXIES_HNSW_INX |
親トピック: ベクトル索引のオプティマイザ計画