HNSW
HNSW (Malkov & Yashunin, 2016) は、高いリコール率と低レイテンシを比較的少ないリソース消費で実現する能力により、高性能なオンラインベクター検索の事実上の標準となっています。Apache Doris 4.x以降、HNSWベースのANNインデックスがサポートされています。本ドキュメントでは、HNSWアルゴリズム、主要なパラメータ、エンジニアリング手法について説明し、本番環境のDorisクラスターでHNSWベースのANNインデックスを構築・調整する方法を解説します。
HNSW以前
HNSW (Hierarchical Navigable Small World) アルゴリズムは、論文 Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs で提案されました。HNSW以前にも、近似k‑NN検索のために多くのアルゴリズムがすでに提案されていましたが、それぞれに制限がありました。
近接グラフ
このアルゴリズム系列の基本的なアイデアは、グラフ内のエントリポイント（ランダムな頂点または何らかのヒューリスティックによって選択された頂点）から開始し、グラフを反復的に探索することです。各反復において、アルゴリズムはクエリベクターと現在のノードのすべての隣接ノード間の距離を計算し、最も近い隣接ノードを次の反復の新しいベースノードとして選択し、現在の最良候補セットを継続的に維持します。最後の反復でより近いノードが見つからないなど、特定の停止条件が満たされた場合、アルゴリズムは終了し、候補セット内の上位K個の最近傍ノードが最終結果として返されます。
これらの近接グラフアルゴリズムは、Delaunayグラフの近似と見なすことができます。なぜなら、Delaunayグラフには重要な性質があり、貪欲探索は常に最近傍を見つけるからです。
しかし、このアルゴリズム系列には2つの主な問題があります：
- データセットが大きくなると、ルーティングフェーズでの反復回数がべき乗則にほぼ従って増加する。
- 高品質な近接グラフを構築することが困難で、局所的なクラスターや乏しい大域的接続性が非常に一般的である。
上図は問題のある近接グラフの形状を直感的に示しています。暗い点は接続性の乏しいノードを表しており、一部のノードは隣接ノードをほとんど持たないため、検索中にそれらに到達することが非常に困難になります。
Navigable Small World
上記の問題に対処するため、2つの主なアイデアがあります：
- ハイブリッドアプローチ：まず粗粒度の検索を実行してより良いエントリポイントを見つけ、次に近接グラフで貪欲探索を実行する。
- 各ノードの最大次数を制限して検索の複雑さを制御しながら、良好な接続性を維持するnavigable small‑world構造を使用する。
NSW (Navigable Small World) は2番目のアイデアを採用しています。
NSWモデルは、社会における人々のつながり方を研究する社会実験の一部として、最初に J. Kleinberg によって提案されました。スモールワールド実験 / 6次の隔たり について聞いたことがあるかもしれません。
k‑NNグラフアルゴリズムについて、対数または多重対数の検索複雑度を達成する任意のスモールワールドネットワークは、しばしばNavigable Small World Networkと呼ばれます。多くの具体的な実装がありますが、ここでは詳細を述べません。
一部のデータセットにおいて、NSWは当時の最先端の検索性能を示していました。しかし、NSWは厳密に対数複雑度を持たないため、特に低次元ベクター空間において、特定のベンチマークでその性能が最適以下になることがありました。
Hierarchical Navigable Small World
NSW検索プロセスは、ズームアウトとズームインの2つのフェーズから構成されると見なすことができます。
zoom-out：ランダムに選択された低次数頂点から開始し、より高い次数を持つノードを優先しながら検索し、隣接ノードまでの平均距離が現在のノードからクエリまでの距離を超えるまで続ける。zoom-in：これらの条件下で十分に「高い」ノードが見つかると、貪欲探索を実行して最終的なTop‑N隣接ノードを取得する。
NSWが多重対数複雑度を達成する理由は、距離評価の総数が検索中に実行されるジャンプ数と訪問されるノードの平均次数の積にほぼ比例するためです。ジャンプ数と平均次数の両方がデータサイズに対してほぼ対数的に増加するため、全体的な多重対数複雑度につながります。
HNSWは、ズームアウトフェーズを高速化することでクエリ時間複雑度を対数に削減します。
より具体的には、HNSWの「階層」構造は、ノードの特性半径（典型的なエッジ長）に基づいてNSWグラフを複数のレイヤーに分割することで得られます。
検索中、HNSWはトップレイヤーノードをエントリポイントとして選択し、レイヤーごとに貪欲探索を実行します。現在のレイヤーで最近傍ノードが見つかると、検索は次のレイヤーに降り、最下位レイヤーに到達するまでプロセスを繰り返します。各レイヤーのノードの最大次数は制限されており、これにより全体的な時間複雑度を対数に保つのに役立ちます。
この階層構造を構築するため、HNSWは幾何分布に従って各ノードにレベルlを割り当て、構造が高くなりすぎないようにします。HNSWはインデックス作成前にデータをシャッフルする必要もありません（NSWは必要で、そうでないとグラフ品質が劣化します）。ランダムレベル割り当て自体が十分なランダム性を提供するためです。この設計により、HNSWでは効率的な増分更新が可能になります。
Apache DorisにおけるHNSW
Apache Dorisはバージョン4.0からHNSWベースのANNインデックス構築をサポートしています。
インデックス構築
ここで使用するインデックスタイプはANNです。ANNインデックスを作成するには2つの方法があります：テーブル作成時に定義するか、CREATE/BUILD INDEX構文を使用するかです。この2つのアプローチは、インデックスが構築される方法とタイミングが異なるため、異なるシナリオに適しています。
アプローチ1：テーブル作成時にベクターカラムにANNインデックスを定義する。データがロードされると、セグメントが作成されるたびにANNインデックスが構築されます。利点は、データロードが完了すると、インデックスがすでに構築されており、クエリが即座にそれを高速化に使用できることです。欠点は、同期的なインデックス構築がデータ取り込みを遅くし、コンパクション中に追加のインデックス再構築が発生してリソースの無駄につながる可能性があることです。
CREATE TABLE sift_1M (
id int NOT NULL,
embedding array<float> NOT NULL COMMENT "",
INDEX ann_index (embedding) USING ANN PROPERTIES(
"index_type"="hnsw",
"metric_type"="l2_distance",
"dim"="128"
)
) ENGINE=OLAP
DUPLICATE KEY(id) COMMENT "OLAP"
DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES (
"replication_num" = "1"
);
INSERT INTO sift_1M
SELECT *
FROM S3(
"uri" = "https://selectdb-customers-tools-bj.oss-cn-beijing.aliyuncs.com/sift_database.tsv",
"format" = "csv");
CREATE/BUILD INDEX
アプローチ2: CREATE/BUILD INDEX。
CREATE TABLE sift_1M (
id int NOT NULL,
embedding array<float> NOT NULL COMMENT ""
) ENGINE=OLAP
DUPLICATE KEY(id) COMMENT "OLAP"
DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES (
"replication_num" = "1"
);
INSERT INTO sift_1M
SELECT *
FROM S3(
"uri" = "https://selectdb-customers-tools-bj.oss-cn-beijing.aliyuncs.com/sift_database.tsv",
"format" = "csv");
データがロードされた後、CREATE INDEXを実行できます。この時点でインデックスはテーブルに定義されていますが、既存のデータに対してはまだインデックスが構築されていません。
CREATE INDEX idx_test_ann ON sift_1M (`embedding`) USING ANN PROPERTIES (
"index_type"="hnsw",
"metric_type"="l2_distance",
"dim"="128"
);
SHOW DATA ALL FROM sift_1M
+-----------+-----------+--------------+----------+----------------+---------------+----------------+-----------------+----------------+-----------------+
| TableName | IndexName | ReplicaCount | RowCount | LocalTotalSize | LocalDataSize | LocalIndexSize | RemoteTotalSize | RemoteDataSize | RemoteIndexSize |
+-----------+-----------+--------------+----------+----------------+---------------+----------------+-----------------+----------------+-----------------+
| sift_1M | sift_1M | 1 | 1000000 | 170.001 MB | 170.001 MB | 0.000 | 0.000 | 0.000 | 0.000 |
| | Total | 1 | | 170.001 MB | 170.001 MB | 0.000 | 0.000 | 0.000 | 0.000 |
+-----------+-----------+--------------+----------+----------------+---------------+----------------+-----------------+----------------+-----------------+
2 rows in set (0.01 sec)
その後、BUILD INDEX文を使用してインデックスを構築できます：
BUILD INDEX idx_test_ann ON sift_1M;
BUILD INDEXは非同期で実行されます。SHOW BUILD INDEX（一部のバージョンではSHOW ALTER）を使用してジョブのステータスを確認できます。
SHOW BUILD INDEX WHERE TableName = "sift_1M";
+---------------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
| JobId | TableName | PartitionName | AlterInvertedIndexes | CreateTime | FinishTime | TransactionId | State | Msg | Progress |
+---------------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
| 1763603913428 | sift_1M | sift_1M | [ADD INDEX idx_test_ann (`embedding`) USING ANN PROPERTIES("dim" = "128", "index_type" = "hnsw", "metric_type" = "l2_distance")], | 2025-11-20 11:14:55.253 | 2025-11-20 11:15:10.622 | 126128 | FINISHED | | NULL |
+---------------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
DROP INDEX
不適切なANNインデックスはALTER TABLE sift_1M DROP INDEX idx_test_annでドロップできます。インデックスのドロップと再作成は、ハイパーパラメータチューニング時に、望ましいリコールを達成するために異なるパラメータの組み合わせをテストする必要がある場合によく行われます。
クエリ実行
ANNインデックスはTop‑N検索と範囲検索の両方をサポートしています。
ベクトル列の次元数が高い場合、クエリベクトル自体のリテラル表現が追加の解析オーバーヘッドを発生させる可能性があります。そのため、完全なクエリベクトルを生のSQLに直接埋め込むことは、特に高い同時実行性の下では本番環境では推奨されません。より良いプラクティスはprepared statementsを使用することで、これにより反復的なSQL解析を回避できます。
doris-vector-searchの使用を推奨します。これはprepared statementsに基づいてDorisでのベクトル検索に必要な操作をラップし、Dorisクエリ結果をPandas DataFrameにマップするデータ変換ユーティリティを含んでおり、下流のAIアプリケーション開発を便利にします。
from doris_vector_search import DorisVectorClient, AuthOptions
auth = AuthOptions(
host="localhost",
query_port=9030,
user="root",
password="",
)
client = DorisVectorClient(database="demo", auth_options=auth)
tbl = client.open_table("sift_1M")
query = [0.1] * 128 # Example 128-dimensional vector
# SELECT id FROM sift_1M ORDER BY l2_distance_approximate(embedding, query) LIMIT 10;
result = tbl.search(query, metric_type="l2_distance").limit(10).select(["id"]).to_pandas()
print(result)
サンプル出力:
id
0 123911
1 11743
2 108584
3 123739
4 73311
5 124746
6 620941
7 124493
8 177392
9 153178
Recall最適化
ベクター検索においてrecallが最も重要な指標です。パフォーマンス数値は所定のrecallレベル下でのみ意味を持ちます。recallに影響を与える主な要因は以下の通りです：
- HNSWのインデックス時パラメーター（
max_degree、ef_construction）とクエリ時パラメーター（ef_search）。 - ベクター量子化。
- セグメントサイズとセグメント数。
この記事では（1）と（3）のrecallに対する影響に焦点を当てます。ベクター量子化については別の文書で扱われます。
インデックスハイパーパラメーター
HNSWインデックスはベクターを多層グラフに整理します。インデックス構築中、ベクターは1つずつ挿入され、層をまたがって隣接ノードと接続されます。このプロセスは概ね以下の通りです：
- 層の割り当て：各ベクターは幾何分布に従ってランダムにレベルが割り当てられます。上位レベルのノードはよりまばらで、ナビゲーションのショートカットとして機能します。
ef_constructionを使用した候補隣接ノードの検索： 各レベルで、HNSWは最大サイズef_constructionの候補キューを使用してローカル検索を実行します。 より大きなef_construction値は一般的により良い隣接ノードとより高品質なグラフ（そしてより高いrecall）をもたらしますが、インデックス構築時間が長くなります。max_degreeを使用した接続の制限： 各ノードの隣接ノード数はmax_degreeによって制限され、グラフが密になりすぎることを防ぎます。
クエリ時：
- 上位層での貪欲検索（粗検索）： 最上位層のエントリーノードから開始し、HNSWは上位層で貪欲検索を実行してクエリの近傍に素早く移動します。
ef_searchを使用した最下位層での幅優先的検索（精密検索）： レイヤー0で、HNSWは最大サイズef_searchの候補キューを使用して隣接ノードをより徹底的に展開します。
まとめると：
max_degreeはノードあたりの最大（双方向）エッジ数を定義します。recall、メモリ使用量、クエリパフォーマンスに影響します。より大きなmax_degreeは通常より高いrecallをもたらしますが、クエリが遅くなります。ef_constructionはインデックス構築中の候補キューの最大長を定義します。より大きな値はグラフ品質とrecallを向上させますが、インデックス構築時間が増加します。ef_searchはクエリ中の候補キューの最大長を定義します。より大きな値はrecallを向上させますが、距離計算数が増加し、クエリレイテンシとCPU使用量が上昇します。
デフォルトで、Dorisはmax_degree = 32、ef_construction = 40、ef_search = 32を使用します。
上記はこれら3つのハイパーパラメーターの定性的分析です。以下の表はSIFT_1Mデータセットでの実証結果を示しています：
| max_degree | ef_construction | ef_search | recall_at_1 | recall_at_100 |
|---|---|---|---|---|
| 32 | 80 | 32 | 0.955 | 0.75335 |
| 32 | 80 | 64 | 0.98 | 0.88015 |
| 32 | 80 | 96 | 0.995 | 0.9328 |
| 32 | 120 | 32 | 0.96 | 0.7736 |
| 32 | 120 | 64 | 0.975 | 0.89865 |
| 32 | 120 | 96 | 0.99 | 0.94575 |
| 32 | 160 | 32 | 0.955 | 0.78745 |
| 32 | 160 | 64 | 0.98 | 0.9097 |
| 32 | 160 | 96 | 0.995 | 0.95485 |
| 48 | 80 | 32 | 0.985 | 0.85895 |
| 48 | 80 | 64 | 0.99 | 0.9453 |
| 48 | 80 | 96 | 1 | 0.97325 |
| 48 | 120 | 32 | 0.97 | 0.78335 |
| 48 | 120 | 64 | 1 | 0.9089 |
| 48 | 120 | 96 | 1 | 0.95325 |
| 48 | 160 | 32 | 0.975 | 0.79745 |
| 48 | 160 | 64 | 0.995 | 0.9192 |
| 48 | 160 | 96 | 0.995 | 0.9601 |
| 64 | 80 | 32 | 1 | 0.9026 |
| 64 | 80 | 64 | 1 | 0.97025 |
| 64 | 80 | 96 | 1 | 0.9862 |
| 64 | 120 | 32 | 0.985 | 0.8548 |
| 64 | 120 | 64 | 0.99 | 0.94755 |
| 64 | 120 | 96 | 0.995 | 0.97645 |
| 64 | 160 | 32 | 0.97 | 0.80585 |
| 64 | 160 | 64 | 0.99 | 0.91925 |
| 64 | 160 | 96 | 0.995 | 0.96165 |
結果は、複数のハイパーパラメーター組み合わせが同様のrecallレベルに到達できることを示しています。たとえば、recall@100 > 0.95を求めるとします。以下の組み合わせはすべて要件を満たします：
| max_degree | ef_construction | ef_search | recall_at_1 | recall_at_100 |
|---|---|---|---|---|
| 32 | 160 | 96 | 0.995 | 0.95485 |
| 48 | 80 | 96 | 1 | 0.97325 |
| 48 | 120 | 96 | 1 | 0.95325 |
| 48 | 160 | 96 | 0.995 | 0.9601 |
| 64 | 80 | 64 | 1 | 0.97025 |
| 64 | 80 | 96 | 1 | 0.9862 |
| 64 | 120 | 96 | 0.995 | 0.97645 |
| 64 | 160 | 96 | 0.995 | 0.96165 |
事前に単一の最適設定を提供するのは困難ですが、ハイパーパラメーター選択のための実用的なワークフローに従うことができます：
- インデックスなしでテーブル
table_multi_indexを作成します。2または3のベクターカラムを含むことができます。 - Stream Loadまたは他の取り込み方法を使用して
table_multi_indexにデータをロードします。 CREATE INDEXとBUILD INDEXを使用してすべてのベクターカラムにANNインデックスを構築します。- 異なるカラムで異なるインデックスパラメーター構成を使用します。インデックス構築が完了した後、各カラムでrecallを計算し、最適なパラメーター組み合わせを選択します。
インデックスあたりのカバー行数
内部的に、Dorisは複数の層でデータを整理します。
- 最上位はテーブルで、分散キーを使用してN個のタブレットに分割されます。タブレットはデータのシャーディング、再配置、リバランスの単位として機能します。
- 各データ取り込みまたはコンパクションは、タブレット下に新しいrowsetを生成します。rowsetはバージョン管理されたデータのコレクションです。
- rowset内のデータは実際にはセグメントファイルに保存されます。
転置インデックスと同様に、ベクターインデックスはセグメントレベルで構築されます。セグメントサイズは、write_buffer_sizeやvertical_compaction_max_segment_sizeなどのBE構成オプションによって決定されます。取り込みとコンパクション中、インメモリmemtableが一定のサイズに達すると、セグメントファイルとしてディスクにフラッシュされ、そのセグメントに対してベクターインデックス（または複数のベクターカラムに対する複数のインデックス）が構築されます。インデックスはそのセグメント内の行のみをカバーします。
HNSWパラメーターの固定セットが与えられると、インデックスが高いrecallを維持できるベクター数には常に制限があります。セグメント内のベクター数がその制限を超えると、recallが劣化し始めます。
以下は、特定のハイパーパラメーター下で良好なrecallを維持しながらセグメントが保持できる行数の実証値です：
| max_degree | ef_construction | ef_search | num_segment | recall_at_100 |
|---|---|---|---|---|
| 32 | 160 | 96 | 1M | 0.95485 |
| 48 | 80 | 96 | 1M | 0.97325 |
| 32 | 160 | 32 | 3M | 0.66983 |
| 128 | 512 | 128 | 3M | 0.9931 |
SHOW TABLETS FROM tableを使用してテーブルのコンパクション状況を調べることができます。対応するURLをたどることで、セグメント数を確認できます。
コンパクションのRecallに対する影響
コンパクションは、元のハイパーパラメーターが示す「カバー容量」を超える可能性のあるより大きなセグメントを作成する場合があるため、recallに影響を与える可能性があります。その結果、コンパクション前に達成されたrecallレベルは、コンパクション後には維持されない場合があります。
BUILD INDEXを実行する前に完全コンパクションをトリガーすることを推奨します。完全にコンパクションされたセグメントでインデックスを構築することで、recallが安定し、インデックス再構築によって引き起こされる書き込み増幅も削減されます。
クエリパフォーマンス
インデックスファイルのコールドローディング
DorisのHNSW ANNインデックスは、MetaのオープンソースライブラリFaissを使用して実装されています。HNSWインデックスは、セグメントの完全なグラフ構造がメモリにロードされた後にのみ有効になります。そのため、高同時実行ワークロードを実行する前に、関連するすべてのセグメントインデックスがメモリにロードされるように、いくつかのウォームアップクエリを実行することを推奨します。そうでなければ、ディスクI/Oオーバーヘッドがクエリパフォーマンスを大幅に損なう可能性があります。
メモリフットプリント vs. パフォーマンス
量子化や圧縮なしで、HNSWインデックスのメモリフットプリントは、インデックス対象のすべてのベクターのメモリフットプリントの約1.2～1.3倍です。
例えば、100万個の128次元ベクターの場合、HNSW-FLATインデックスは約以下を必要とします：
128 * 4 * 1,000,000 * 1.3 ≈ 650 MB。
参考値：
| dim | rows | estimated memory |
|---|---|---|
| 128 | 1M | 650 MB |
| 768 | 10M | 48 GB |
| 768 | 100M | 110 GB |
安定したパフォーマンスを維持するには、各BEが十分なメモリを持つことを確認してください。そうでなければ、頻繁なスワップとインデックスファイルでのI/Oがクエリレイテンシを著しく劣化させます。
ベンチマーク
16コア、64GBマシンでDoris HNSWインデックスのクエリパフォーマンスをベンチマークしました。典型的な本番デプロイメントでは、FEとBEは別々のマシンにあるため、そのようなマシンが2台必要です。典型的な（FE/BE分離）デプロイメントと単一マシンでの混合FE/BEデプロイメントの両方の結果を提供します。
ベンチマークフレームワークはVectorDBBenchです。
ロードジェネレーターは別の16コアマシンで実行されます。
Performance768D1M
ベンチマークコマンド：
NUM_PER_BATCH=1000000 python3.11 -m vectordbbench doris --host 127.0.0.1 --port 9030 --case-type Performance768D1M --db-name Performance768D1M --search-concurrent --search-serial --num-concurrency 10,40,80 --stream-load-rows-per-batch 500000 --index-prop max_degree=128,ef_construction=512 --session-var hnsw_ef_search=128
| Doris (FE/BE分離) | Doris (FE/BE混在) | |
|---|---|---|
| Indexプロパティ | max_degree=128, ef_construction=512, hnsw_ef_search=128 | max_degree=128, ef_construction=512, hnsw_ef_search=156 |
| Recall@100 | 0.9931 | 0.9929 |
| 並行性 (Client) | 10, 40, 80 | 10, 40, 80 |
| 結果QPS | 163.1567 (10) 606.6832 (40) 859.3842 (80) | 162.3002 (10) 542.3488 (40) 607.7951 (80) |
| 平均レイテンシ (s) | 0.06123 (10) 0.06579 (40) 0.09281 (80) | 0.06154 (10) 0.07351 (40) 0.13093 (80) |
| P95レイテンシ (s) | 0.06560 (10) 0.07747 (40) 0.12967 (80) | 0.06726 (10) 0.08789 (40) 0.18719 (80) |
| P99レイテンシ (s) | 0.06889 (10) 0.08618 (40) 0.14605 (80) | 0.06154 (10) 0.07351 (40) 0.13093 (80) |