フィルタリングされたベクトル検索:ACORNが修正するもの、ACORNを修正するもの
Filtered Vector Search: What Acorn Fixes, and What Fixes Acorn (qdrant.tech)
要約
この記事は、Qdrantにおけるフィルタリングされたベクトル検索の課題と、それを解決するACORNアルゴリズムについて解説しています。メタデータフィルタリングによってHNSWグラフが分断される問題を、ACORNが検索時に隣接ノードのさらに隣接ノードを探索することで解決する仕組みを説明しています。また、Qdrantが提供するFilterable HNSWとACORNの組み合わせによる検索戦略についても比較しています。
全文翻訳
Filtered Vector Search: ACORNが解決すること、そしてACORNを解決すること
Dylan Couzon & Meina Ghafouri
·
2026年8月7日
[画像: Filtered Vector Search: What ACORN Fixes, and What Fixes ACORN]
フィルタリングされたベクトル検索は、メタデータフィルタが健全な最近傍グラフを散在する島々に変えてしまうと機能しなくなります。HNSWのmパラメータは、各ポイントが持つリンクの数を制御します。Qdrantのデフォルト値m=16では、この記事でベンチマークされた100万ポイントのコレクションでは、レイヤー0でノードあたり平均約21本のリンクがありました。ポイントの96%をフィルタリングすると、ノードあたり平均で1リンク未満しか残らなくなるため、トラバーサルは真の最近傍マッチに到達する前に立ち往生する可能性があります。
Qdrantは、そのダメージを2つの場所で修復します。Filterable HNSWはインデックス作成時に追加のエッジを設けます。ACORNは検索時に近傍ノードの近傍ノードをステップ実行します。どちらも同じコレクション上で動作します。ACORNは、追加エッジが届かない場所、つまりリンクするには値が共通すぎる、単一フィールドのエッジではカバーできないANDフィルタ、ビルドがサイレントにスキップしたペイロードフィールドなどでそのコストに見合う価値を発揮します。
このベンチマークは、単一のQdrantインスタンスで実行され、4つのビルドにわたるQdrant自身の4つの検索戦略を比較します。
2つのACORN
ACORN論文(Patel et al., SIGMOD 2024)は2つのアルゴリズムを説明しています。その見出しにある「固定されたリコール率で2~1,000倍高いスループット」という主張はACORN-gammaのもので、これはインデックス構築時に近傍リストを8.8倍から33.1倍に拡張し、論文自身の表にあるプレーンHNSWのビルド時間を上回ります。
ACORN-1はより軽量です。標準的なHNSWグラフを構築し、直接の近傍ノードがフィルタに失敗した場合に、検索時に近傍ノードの近傍ノードをチェックします。QdrantはACORN-1をクエリパラメータとして実装しており、リクエストごとにオプトインでき、インデックス時の変更はありません。
Qdrantが代わりに構築するグラフ
共同創設者であるAndrey Vasnetsovが2019年に説明したFilterable HNSWは、修復をインデックスに組み込みます。各ポイントに付随するメタデータであるペイロードフィールドがインデックス化されると、Qdrantはそのフィールドの値を持つポイント間にHNSWエッジを追加するため、フィルタリングされたクエリはトラバースするための接続されたグラフを維持できます。Qdrantはインデックス作成時にこれらのエッジをペイロードフィールドに付与しますが、すべてのフィールドがそれに見合うわけではありません。
それらのエッジはビルド時間にコストがかかります。100万ポイントのコレクションでは、HNSWインデックスはエッジなしで116秒、エッジありで507~652秒かかり、コストは4.4倍から5.6倍でした。この範囲は、同一設定での2回のビルドを含んでおり、ビルド間のばらつきを示しています。どちらの数値もインデックスビルド時間であり、インジェストは除外されています。
Qdrantはこれらのエッジをペイロードフィールドごとに構築し、組み合わせごとではないため、ANDフィルタは単一フィールドのエッジがカバーしない交点に到達します。ACORN-1はそのギャップをカバーし、ビルド時間ではなくクエリ時間でコストを支払います。Qdrantのクエリプランナーは、ACORN、フルスキャン、ペイロードインデックスからの直接取得、およびFilterable HNSWの間で自動的に選択します。
3つの検索を切り替えて、それぞれが同じフィルタをどのように処理するかを確認してください。
[画像: 同じグラフ、2つの方法で修復]
同じグラフ、2つの方法で修復。ACORNは検索時にフィルタリングされた近傍ノードをステップ実行し、Filterable HNSWはインデックス作成時に追加エッジを設けて、フィルタリングされたクエリが直接歩けるようにします。グラフは玩具であり、トラバーサルはそれ上で計算されます。
ベンチマーク
ベンチマークは、ANN-benchmarksスイートからの96次元の画像埋め込みである100万のdeep-image-96ベクトルで実行されます。キーワードフィルタは、ポイントの20%から0.012%までマッチします。Recall@10は、500クエリ/フィルタで正確な総当たり検索に対してスコアリングされ、レイテンシは平均サーバーサイドクエリ時間です。
4つの戦略をテストしました。
- プレーングラフ: 追加エッジなしの標準HNSW。
- プレーングラフ + ACORN: ACORNを強制オンにした同じグラフ。
- Filterable HNSW: 追加エッジを持つデフォルトビルド。
- プランナー + ACORN: Qdrantのデフォルトクエリプランナー。各クエリをACORN、フルスキャン、またはペイロードインデックスにルーティングできます。
すべてのフィルタは、ペイロードフィールド上の1つのキーワード値にマッチします。コレクションは7つのそのようなフィールドを持ち、それぞれ5、10、または100の異なる値を含んでいます。
ほとんどのフィルタはベクトルとは独立しています。Correlated (10%)行は簡単なケースで、フィルタを通過するポイントがベクトル空間でも互いに近くに配置されている場合です。
この記事のすべての数値は、Qdrant v1.18.2で、ラップトップクラスの単一マシン上で、シリアルにクエリして測定されました。絶対ミリ秒ではなく、比率を読んでください。再現キットは、ハードウェアと完全な方法論を文書化しています。
hnsw_ef(この記事ではefと短縮)は、検索が評価する候補の数であるため、これを増やすとリコールが向上し、クエリが遅くなります。選択性は、フィルタを通過するポイントの割合です。
この表は最初の3つの戦略を比較しています。full_scan_thresholdは、フィルタリングされた結果セットが直接スキャンするのに十分小さい場合にQdrantに通知します。値はベクトルデータのキロバイト単位で測定され、マッチしたベクトルがこの値より小さい場合、QdrantはHNSWグラフをスキップします。これらの3つの戦略では、すべてのクエリがグラフ上に留まるように、値を低く設定しました。Planner + ACORNはデフォルトのしきい値で実行されます。各セルは、hnsw_ef=64でのRecall@10と平均サーバーサイドレイテンシを示しています。
| フィルタ (選択性) | プレーングラフ | プレーングラフ + ACORN | Filterable HNSW |
|---|---|---|---|
| One keyword (20%) | 62.9% @ 1.6ms | 98.9% @ 4.4ms | 94.8% @ 1.2ms |
| One keyword (10%) | 20.6% @ 1.7ms | 98.1% @ 4.3ms | 99.0% @ 1.1ms |
| One keyword (1%) | 0.1% @ 1.6ms | 67.7% @ 4.7ms | 99.8% @ 1.0ms |
| Correlated (10%) | 88.4% @ 1.7ms | 98.6% @ 3.5ms | 99.0% @ 1.2ms |
プレーングラフはフィルタが厳しくなるにつれて崩壊し、相関フィルタのみが持ちこたえます。ACORNはプレーングラフの2.1倍から2.9倍のレイテンシでリコールを引き戻しますが、1%フィルタで停滞します。これは、RACORN-1フォローアップ論文がターゲットとする弱点です。ACORNが勝つ唯一のフィルタ(20%)は、追加エッジが設定されなかったペイロードフィールドで実行され、次のセクションでその理由を説明します。
hnsw_ef=64での単一フィールドフィルタ、100万ポイント、フィルタあたり500クエリ、高いほど良いRecall@10 (%)One keyword (20%)One keyword (10%)One keyword (1%)Correlated (10%)0102030405060708090100Plain graphPlain graph + ACORNFilterable HNSW
hnsw_ef=64での4つの単一フィールドフィルタにおけるRecall@10。追加エッジが最高のリコールを維持します。
Qdrantのプランナーはこれらすべての中から選択します。フィルタが通過するポイント数を推定し、クエリごとにパスを選択します:グラフ、グラフ上のACORN、または推定値がfull_scan_thresholdを下回った場合のペイロードインデックス。4番目の戦略であるPlanner + ACORNは、4つのフィルタすべてで99.9%から100%のリコールを維持し、グラフ上では7.2msから10.9ms、1%フィルタでは1.5ms(500クエリすべてがペイロードインデックスから来た場合)でした。
Qdrantは、インデックス化された各ペイロードフィールドの値を確認することで追加エッジを構築します。各値について、それを共有するポイントを見つけてリンクするため、その値にフィルタリングされたクエリはトラバースするためのグラフを維持できます。
サイズキャップよりも多くのポイントを共有する値には追加エッジは設定されません。なぜなら、メイングラフはすでにそれだけのポイントを接続しておくべきだからです。Qdrantは、コレクションのスライスである各セグメントに対してこのキャップを導き出します。このセグメントは独自のインデックスを持っています。式は、ポイント数 ÷ ノードあたりの平均リンク数 × 4です。ここでは1つのセグメントが100万ポイントすべてを保持していたため、100万 ÷ 21リンク/ノード × 4 = 190,476ポイントとなり、コレクションの約19%に相当します。より密なグラフでは、ノードあたり24リンクの場合、キャップは16.7%に低下します。
Qdrantはこれらの決定を報告しないため、再現キットはトレースレベルのビルドログとフィールドサイズからそれらを導き出します。ベンチマークの7つのペイロードフィールドは次のように配置されました。
| フィールド | 異なる値の数 | 値あたりのポイント数 | 追加エッジの構築 |
|---|---|---|---|
| 2つのフィールド | 5 | ~200,000 | いいえ、すべての5つの値がキャップを超過 |
| 2つのフィールド | 10 | ~100,000 | はい、10個中10個の値 |
| 相関フィールド | 10 | ~100,000 | はい、10個中10個の値 |
| 2つのフィールド | 100 | ~10,000 | はい、100個中100個の値 |
5値フィールドはキャップを5%超過しているため、それらの値はすべてスキップされました。このスキップが、ACORNが20%フィルタ、および次のセクションの4%交差でFilterable HNSWを上回る理由です。それ以外の場所では、ギャップはビルド間のばらつきの範囲内に留まります。
スキップは意図的です。追加エッジはビルド時間とメモリを消費するため、キャップが存在します。キャップ以下の値でも、full_scan_thresholdフロアを下回っている場合や、ポイントがどれだけうまく接続されているかのサンプリングチェックに失敗した場合にスキップされる可能性があるため、値の数だけでは結果は決まりません。
ダブルフィルタ:交差のギャップ
hnsw_ef=64での同じベンチマークですが、今回は2つのキーワードフィールドに対するANDフィルタを使用します。
| フィルタ (選択性) | プレーングラフ + ACORN | Filterable HNSW | プランナー + ACORN |
|---|---|---|---|
| Two keywords (4%) | 95.2% @ 7.7ms | 63.7% @ 1.2ms | 99.9% @ 13.9ms |
| Two keywords (1%) | 72.7% @ 6.8ms | 70.8% @ 1.5ms | 100% @ 3.7ms |
| Two keywords (0.012%) | 0.6% @ 2.6ms | 1.8% @ 2.6ms | 100% @ 1.3ms |
2つのキーワードの交差には、両方のペイロードフィールドにエッジがあっても、それ自体の追加エッジはありません。どちらの修復も、このefではギャップを閉じません。1%行では、ACORNのリコールは同じグラフの再構築にわたって70.7%から74.1%の範囲に広がり、表でのリードよりも広いです。
プレーングラフは、この表から削除されましたが、最初の2行でそれぞれ0.1%と0.0%を記録しました。ef=512は、トラバーサルが切断された島を使い果たした後、何も変更しません。
efを増やすと、1%交差でのタイが破れます。ef=512では、Filterable HNSWは4.9msで91.2%のリコールに達しますが、ACORNは20.1msで90.3%に達する必要があります。ここでは、検索時間でのグラフの修復は、リコールがわずかに少ない場合に4倍のレイテンシを要します。4%交差が例外であり、両方のフィールドがキャップを超え、ACORNは99.6%対92.5%でリードしています。
hnsw_ef=64での1%ダブルフィルタにおけるリコール@10、100万ポイント、設定あたり500クエリRecall@10 (%)64128256512020406080100Plain graphPlain graph + ACORNFilterable HNSWPlanner + ACORN
hnsw_ef=64、128、256、512での1%ダブルフィルタにおける4つの戦略のリコール@10。
このチャートは、再現キットのfull1実行データを使用しており、リピート0とdouble_a10b10フィルタです。各バーは500クエリの平均です。
0.012%では、約120ポイントが100万ポイントからマッチし、グラフは適切なツールではなくなります。Planner + ACORNは、ペイロードインデックスを読み取ることでその行で勝利します。選択はクエリごとに行われます:1%交差では、500クエリのうち29クエリをグラフに、471クエリをペイロードインデックスにルーティングしました。4%では、全体を通してグラフ上に留まりました。
通常のコレクションでのACORN
前の表では、3つの固定戦略をグラフ上に留めるためにfull_scan_thresholdを低く設定しました。誰もコレクションをそのように実行しません。これはデフォルトの設定です:追加エッジ、デフォルトのしきい値、およびグラフまたはペイロードインデックスのいずれかを選択できるプランナー。ACORNはデフォルトでオフになっているため、左の列はペイロードインデックスを持つコレクションが現在返すものです。
| フィルタ (選択性) | プランナー、ACORNオフ | プランナー + ACORN |
|---|---|---|
| One keyword (20%) | 90.8% @ 1.1ms | 100% @ 5.7ms |
| One keyword (10%) | 98.6% @ 0.9ms | 99.9% @ 4.4ms |
| One keyword (1%) | 100% @ 1.7ms | 100% @ 1.6ms |
| Correlated (10%) | 98.6% @ 1.0ms | 100% @ 4.2ms |
| Two keywords (4%) | 39.7% @ 1.1ms | 100% @ 7.3ms |
| Two keywords (1%) | 97.2% @ 2.1ms | 100% @ 2.5ms |
| Two keywords (0.012%) | 100% @ 1.4ms | 100% @ 1.2ms |
ほとんどのフィルタは助けを必要としません:プランナーは非常に選択的なフィルタを直接ペイロードインデックスに送信し、追加エッジは広範なフィルタをグラフ上で処理します。ACORNは、ペイロードフィールドに追加エッジがない2つのケースでその価値を発揮します。20%フィルタで9パーセントポイント、4%交差で60パーセントポイントを追加します。
プランナーがグラフ上に留まる場合、ACORNは高価です:20%フィルタで5.4倍、4%交差で6.7倍のレイテンシになります。ほとんどのクエリをペイロードインデックスにルーティングする場合、ACORNはほぼ無料です:1%交差は、500クエリ中471クエリがグラフに到達しないため、レイテンシの1.2倍で2.8パーセントポイント増加します。
追加エッジはACORNをさらに強力にします。4%交差では、プレーングラフで95.2%、エッジ配置済みで99.9%に達しました。ACORNは、得られたグラフをトラバースするため、2つの修復はスタックします。
独自のコレクションで測定すること
提供する各フィルタ形状のリコールを測定してください。最も壊れやすい可能性のあるものから始めてください:コレクションの約5分の1以上をカバーする値、およびそれらのAND組み合わせです。ファセットカウントは、どの値がそれほど広範囲かを hiển thịします。
デフォルト設定では、1つのフィルタはACORNオフで39.7%を返しましたが、他のすべてのフィルタは90%以上に留まりました。単一の集計数値ではそれは隠されてしまいます。それらのフィルタがクリーンに戻ってきたら、次に狭い値をテストしてください。
フィルタリングするすべてのフィールドにペイロードインデックスを作成し、最初はACORNをオフのままにしてください。これがQdrantのデフォルトだからです。次に、各フィルタ形状の実際のクエリを数百件サンプリングしてください。このベンチマークに合わせたい場合は500件です。exact: trueで正確な結果を取得し、ACORNオフとオンの両方でリコールとレイテンシをスコアリングしてください。
レイテンシコストに対するリコールの増加を比較してください。39.7%フィルタのような回復はACORNの目的ですが、レイテンシ倍率が小さい場合にのみ、1~2ポイントの増加を取る価値があります。ACORNをオンにするのは、それがフィルタによって獲得されたクエリパスにacorn.enableを設定してください。
私たちのすべての実行で、オンにしてもリコールが低下することはありませんでした。したがって、不確かな場合は、オンのままにするコストはレイテンシです。Qdrantは、デフォルトで0.4であるmax_selectivityを下回る場合にのみそれを適用するため、コレクションの半分にマッチするフィルタはどちらの場合も変更されません。
追加エッジは、クエリが到着する前にグラフを修復します。ACORNは、残ったギャップを修復します。
さらに読む
- ACORN (Patel et al., SIGMOD 2024): ACORN-gammaとACORN-1の背後にある論文。
- RACORN-1: 低選択性でのACORN-1のリコール崩壊をターゲットにしたフォローアップ。
- PostgreSQL ACORN研究: 検索時間修復のフィルタチェックコストを測定します。
- Filterable HNSW: Qdrantの追加エッジの背後にある2019年の記事。
- 再現キット: この表をQdrantバージョンで再実行するためのスクリプト、ピン留めされたイメージ、およびグランドトゥルース。
フィルタリングされた検索セットアップについて話し合うには、お問い合わせください。