HNSWとApache Dorisでの使用方法
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検索のための多くのアルゴリズムが既に提案されていましたが、それぞれに制限がありました。
Proximate Graph
このアルゴリズムファミリーの基本的なアイデアは、グラフ内のエントリーポイント（ランダムな頂点または何らかのヒューリスティックによって選択された頂点）から開始し、次にグラフを反復的に走査することです。各反復で、アルゴリズムはクエリベクトルと現在のノードの全ての隣接ノード間の距離を計算し、最も近い隣接ノードを次の反復の新しいベースノードとして選択し、現在の最良候補セットを継続的に維持します。特定の停止条件が満たされた場合（最後の反復でより近いノードが見つからなかったなど）、アルゴリズムは終了し、候補セット内の上位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: これらの条件下で十分に「高い」ノードが見つかったら、貪欲探索を実行して最終的な上位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で削除できます。インデックスの削除と再作成は、ハイパーパラメータチューニング時に、希望するrecallを達成するために異なるパラメータの組み合わせをテストする必要がある場合によく行われます。
Querying
ANNインデックスはTop‑N searchとrange searchの両方をサポートします。
ベクトル列が高次元の場合、クエリベクトル自体のリテラル表現が追加の解析オーバーヘッドを発生させる可能性があります。そのため、本番環境では、特に高い同時実行性の下で、完全なクエリベクトルを生のSQLに直接埋め込むことは推奨されません。より良い実践は、SQLの繰り返し解析を避けるprepared statementを使用することです。
prepared statementに基づいてDorisでのベクトル検索に必要な操作をラップし、Dorisクエリ結果をPandas DataFrameにマップするデータ変換ユーティリティを含むdoris-vector-search pythonライブラリの使用を推奨します。これにより、下流の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 |
事前に1つの最適な設定を提供することは困難ですが、ハイパーパラメータ選択のための実用的なワークフローに従うことができます：
- インデックスなしでテーブル
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) |
