HNSW
HNSW（Malkov & Yashunin, 2016）は、比較的少ないリソース消費で高いrecallと低いlatencyを実現する能力により、高性能なオンラインベクトル検索のデファクトスタンダードとなっています。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によって最初に提案されました。small‑world実験／6次の隔たりについて聞いたことがあるかもしれません。
k‑NNグラフアルゴリズムにおいて、対数またはポリ対数検索複雑性を達成するsmall‑worldネットワークは、しばしばNavigable Small World Networkと呼ばれます。多くの具体的な実装がありますが、ここでは詳細には説明しません。
一部のデータセットにおいて、NSWは当時の最先端の検索性能を示していました。しかし、NSWは厳密に対数複雑性を持たないため、特に低次元ベクトル空間において、特定のベンチマークではその性能が最適ではない場合があります。
Hierarchical Navigable Small World
NSW検索プロセスは、zoom‑outとzoom‑inの2つのフェーズから構成されていると見なすことができます。
zoom-out：ランダムに選択された低次数の頂点から開始し、より高い次数のノードを優先しながら検索し、隣接ノードへの平均距離が現在のノードからクエリまでの距離を超えるまで続けます。zoom-in：これらの条件下で十分に「高い」ノードが見つかると、グリーディ検索を実行して最終的なTop‑N隣接ノードを取得します。
NSWがポリ対数複雑性を達成する理由は、総距離評価回数が、検索中に実行されるジャンプ回数と訪問ノードの平均次数の積にほぼ比例するためです。ジャンプ回数と平均次数の両方が、データサイズに対してほぼ対数的に増加するため、全体的にポリ対数複雑性となります。
HNSWは、zoom‑outフェーズを高速化することで、クエリ時間複雑性を対数に削減します。
より具体的には、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
ALTER TABLE sift_1M DROP INDEX idx_test_annで不適切なANNインデックスを削除できます。インデックスの削除と再作成は、ハイパーパラメータチューニング中に異なるパラメータの組み合わせをテストして望ましいrecallを達成する必要がある場合によく行われます。
クエリ実行
ANNインデックスはTop‑N検索と範囲検索の両方をサポートしています。
ベクトル列が高次元の場合、クエリベクトル自体のリテラル表現により追加の解析オーバーヘッドが発生する可能性があります。そのため、完全なクエリベクトルを生のSQLに直接埋め込むことは、特に高い同時実行性の下では本番環境では推奨されません。より良い方法は、繰り返しのSQL解析を回避するprepared statementを使用することです。
prepared statementに基づいてDorisでのベクトル検索に必要な操作をラップし、Dorisクエリ結果をPandas DataFrameにマッピングしてダウンストリームのAIアプリケーション開発を便利にするデータ変換ユーティリティを含むdoris-vector-searchの使用を推奨します。
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インデックスはベクトルを多層グラフに整理します。インデックス構築中、ベクトルは一つずつ挿入され、層をまたがってネイバーと接続されます。プロセスは大まかに以下の通りです：
- レイヤー割り当て：各ベクトルは幾何分布に従ってレベルがランダムに割り当てられます。上位レベルのノードはより疎であり、ナビゲーションのためのショートカットとして機能します。
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 prop | 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) |