ベクトルインデックスのベンチマーク

ベクトルインデックスのベンチマーク

ほぼ全てのデータベースがベクトル検索に対応し、それぞれが大きな数値を謳うブログ記事を公開していますが、その数値の多くは検証不可能です。なぜなら、それらを意味のあるものにする要素が欠けているからです。

推測を止めるために、私たちは vector-bench を構築しました。使用したいエンジンを指定し、固定されたバージョンでビルドし、同じデータ、同じコア、同じコンテナ内にそれぞれ配置し、それら全てに対して同じ測定を実行してレポートを作成します。この記事では、その測定方法について説明します。

データベースに携わっていて、まだベクトルを扱ったことがない方にとって、この記事の前半が最も役立つでしょう。

インデックス化されるもの

埋め込み（embedding）とは、モデルから出力される固定長の浮動小数点数の配列です。その有用な特性は、意味的に類似した入力が、それらの間の距離を測定したときに近くに配置されることです。

ほとんどのケースで、2つの距離尺度で対応できます。L2 は通常の直線距離、ピタゴラスの定理を多次元に拡張したものです。コサイン類似度 は2つのベクトルの間の角度を測定し、その長さを無視します。どちらが適用されるかは、埋め込みを生成したモデルによって決定されます。クエリ時に選択できるものではなく、間違った選択をすると無意味な結果を生む可能性があります。

したがって、欲しいクエリは「このベクトルに最も近いベクトルを持つ10行」となります。

SELECT id FROM documents ORDER BY distance(embedding, ?) LIMIT 10;

この10が k です。

問題はここにあります。これを正確に回答するには、クエリベクトルと全ての行との距離を計算し、ソートする必要があります。Bツリーやハッシュインデックスは役立ちません。なぜなら、それらは1536次元で100万点のデータを近さで並べることができないからです。正確なベクトル検索は、大量の算術処理を追加したフルテーブルスキャンです。

ベクトルインデックスは、正確性を犠牲にしてそれを回避します。それは、全ての行ではなく、有望な数千の候補を調べて、見つかった最良の結果を返します。これが近似最近傍（ANN: Approximate Nearest Neighbor）検索です。通常は正しい結果を返します。

「通常」という言葉には多くの意味が含まれており、それを正確に評価することが、このベンチマークの大部分を占めます。

［画像: ベクトルインデックスの概念図］

それを評価するには、まず正しい答えを知る必要があります。それがグラウンドトゥルースです。これは、インデックスを使用せずに総当たりで一度計算された、全てのクエリに対する真の最近傍です。公開されているANNデータセットは、ベクトルと一緒にグラウンドトゥルースを提供しており、それなしでは近似インデックスを全く評価できません。

これが他の全てを意味のあるものにする数値であり、ほとんどのベクトル検索の主張で省略されているものです。この省略こそが、このプロジェクトが存在する理由です。

ベクトルインデックスの2種類

ベクトル検索を追加したほぼ全てのデータベースは、2つの設計のうちの1つを採用しています。それらは反対の端から同じ問題に取り組み、どちらを持っているかによって調整できることが決まります。

HNSW

HNSW は Hierarchical Navigable Small World の略で、直感的で理解しやすいものです。もしスキップリストを実装したことがあるなら、その構造を想像できるでしょう。

これは、レイヤーで構築されたベクトルのグラフです。各ベクトルはノードであり、その近傍のいくつかのノードにリンクされています。最上位のレイヤーはノード数が少なく、リンクはデータ全体を長く飛び越えます。下の各レイヤーはより多くのノードと短いリンクを持ちます。検索は最上位から開始し、クエリに近い方の隣接ノードにホップし続けます。それ以上近い隣接ノードがなくなると、レイヤーをドロップして続行し、レイヤーがなくなるまで続けます。

［画像: HNSWの構造図］

2つの設定が重要です。

• M: 各ノードが保持するリンクの数です。インデックス構築時に固定されます。Mが高いほど、グラフの接続性が向上し、リコール（再現率）も向上しますが、構築は遅くなり、インデックスサイズも大きくなります。
• ef_search: グラフをたどりながら、検索が追跡する候補ノードの数です。これはセッション変数なので、クエリごとに変更できます。値を上げると、検索はより多くのノードを訪問し、リコールは向上しますが、実行速度は低下します。

ef_construction もあり、これはインデックス構築中に適用される同様の考え方です。全てのエンジンがこれを設定できるわけではなく、公平な比較を試みるときに問題となることが判明しています。

IVF

IVF は Inverted File の略です。これはデータをリンクするのではなく、パーティション化します。テーブルのリストパーティショニングに似ています。

構築時に、ベクトルを nlist 個のクラスタにグループ化し、各クラスタには代表ベクトルがあります。クエリ時には、クエリをこれらの代表ベクトルと比較し、最も近い nprobe 個のクラスタを選択し、それらのクラスタ内のみを検索します。HNSWよりもはるかに速く構築でき、メモリ使用量も少なくなりますが、通常は同じ速度でリコールが悪くなります。これは、真の近傍が検索対象となったクラスタの外側に偶然位置していた場合に、見逃してしまう可能性があります。

［画像: IVFの構造図］

私たちはHNSWを実行しているエンジンのみをテストしています。これはほとんどのデータベースが採用しているものです。IVFエンジンを同じチャートに配置すると、アルゴリズム間のギャップを測定することになり、どちらかの実装の良さを測定することにはならないため、IVFのみのエンジンは独自のバケットに配置されます。

1つの数値では決して十分でない理由

リコールはエンジンのプロパティではありません。それは設定であり、ef_search がその調整ダイヤルです。

これは、1台のマシン上の1つのHNSWインデックス、同じデータ、同じクエリでの例です。唯一の違いは、最初の行では検索がグラフをたどる際に10個の候補ノードを追跡し、2行目では800個を追跡していることです。

800個の候補を10個ではなく保持すると、より良い結果が得られますが、9倍の時間がかかります。両方の行は、同じハードウェア上の同じインデックスの正直な測定値です。

［画像: ef_searchの値とスループット/リコールの関係を示すグラフ］

だからこそ、「当社のデータベースは毎秒3,678件のベクトルクエリを実行します」という言葉は何も教えてくれません。それがどれくらいの頻度で間違った行を返していたのかが分からないからです。それを引用している人も、それを知らないかもしれません。逆もまた同様に空虚です。スループットなしのリコールは無料です。なぜなら、インデックスをオフにしてテーブルをスキャンすれば、リコール1.0は常に利用可能だからです。

ここでの全ての測定はペアです。この記事から1つのことを持ち帰るとすれば、それを選んでください。

ハーネスが各エンジンに課すもの

エンジンごとに1つのテーブル。ID、フィルタリングされたテストでのみ使用される整数タグ列、ベクトル、そして設定されたM値でのHNSWインデックス。

CREATE TABLE t1 (
  id INTEGER PRIMARY KEY,
  tag INTEGER NOT NULL,
  v VECTOR(1536)
);

次に、プレーンなトップkと、行のサブセットに制限された同じ検索の2つのクエリです。

SELECT id FROM t1 ORDER BY distance(v, ?) LIMIT 10;
SELECT id FROM t1 WHERE tag < ? ORDER BY distance(v, ?) LIMIT 10;

tagは0から99までの値を均等に保持しているため、tag < 10 は約10%の行を渡し、tag < 1 は約1%を渡します。これが選択性を制御する方法です。

全てのエンジンがこれを異なって書き込みます。一部は CREATE TABLE 内でインデックスを宣言し、他は別の CREATE INDEX を要求し、距離関数も everywhere で名前が異なります。それらを翻訳するのがドライバーの仕事であり、ドライバーはハーネス全体で唯一エンジン固有のコードです。

また、全てのエンジンには、数値を静かに台無しにする少なくとも1つのセットアップ上の詳細があります。例えばPostgreSQLは、オーバーサイズの値をTOASTと呼ばれる領域にインライン外で格納し、1536次元のベクトルはオーバーサイズと見なされます。列が STORAGE PLAIN に設定されていない限り、全ての距離比較で追加のフェッチが発生します。これはDDLの1行です。これを逃すと、PostgreSQLがベクトル検索とは無関係の理由で遅く見えてしまい、結果からそれを知ることはできません。

測定するもの

リコール対スループット。固定されたインデックスに対して ef_search を反復し、各ポイントでリコールとQPSを記録し、いくつかのM値で繰り返します。k=10で統一します。クエリベクトルは、データセット自体の保持されたクエリセットから取得されます。ロードした行から取得するわけではありません。なぜなら、インデックスに既に存在するベクトルを検索するのははるかに簡単な問題であり、全てのエンジンを等しく良く見せてしまうからです。

2つの設定は完全に異なる動作をし、実行時間の長さに影響します。ef_search はセッション変数なので、それを反復することは既に構築されているインデックスを再利用し、各追加ポイントのコストはほとんどかかりません。Mはインデックスに焼き付けられているため、Mの値ごとにテーブルをドロップしてデータセット全体を再度ロードする必要があります。100万個の1536次元ベクトルでは、値ごとに数時間かかります。そのため、ef_search のポイントは多く、Mの値は非常に少なくなります。

構築コスト。経過時間、毎秒の行数、ディスク上のインデックスサイズ、ピークメモリ使用量。

これはベンチマーク全体で誤解を招く数値を公開しやすい場所です。なぜなら、エンジンはインデックスを同じ方法で構築しないからです。エンジンはインデックスをインクリメンタル、バルク、またはその両方で構築できます。これはどういう意味でしょうか？

インクリメンタル。グラフは各INSERTごとに更新されます。ロードは遅いですが、最後の行がロードされるとインデックスは完成し、テーブルはクエリ可能になります。

バルク。全ての行が最初にロードされ、その後グラフ全体が一括で構築されます。合計ではるかに高速ですが、構築が完了するまでテーブルはベクトルクエリに応答できません。

これらは2つの異なる操作です。私たちのセットの1つのエンジンは両方を行い、そのバルクパスは同じエンジンのインクリメンタルパスよりも毎秒18倍多くの行をロードしました。同じエンジン、同じデータ、同じマシンで、18倍の違いがあります。

したがって、あるエンジンからのバルク数値と別のエンジンからのインクリメンタル数値を並べても、エンジンを比較していることにはなりません。それはインデックスを構築する2つの方法を比較しており、その比率は印象的であるため、人々はそれでも引用します。私たちは、両方のパスを持つエンジンに対して両方のパスを測定し、レポートでどちらがどちらであるかを示します。

ピークメモリはサーバーのコンテナから取得され、データベースのみが実行されています。ハーネスは別のコンテナで実行され、プライベートネットワーク経由でサーバーにアクセスします。

この分離は、聞こえるよりも重要です。クライアントはデータセット全体をメモリに保持しており、数GBのPython配列です。もしクライアントがデータベースと同じコンテナを共有していたら、コンテナのメモリアカウンティングはそれらの配列をデータベースメモリとしてカウントし、公開される全てのメモリ数値は、クライアントが保持していたものによって膨張します。

［画像: メモリ使用量の比較］

同時実行性。1から32のクライアントからのQPSとレイテンシパーセンタイル。エンジンはキャッシュを非常に異なる方法でキャッシュし、クライアントが同じキャッシュを競合し始めるまで、そのどれも表示されません。私たちは、各エンジンが実際に得た理想的な速度向上率を、生のQPSと並べて報告します。なぜなら、クライアントが2つになったときにスループットの向上が止まり、p99が15倍悪化するエンジンは、スケールし続けるエンジンとは全く異なることをしており、スループット列だけではそれを完全に隠してしまうからです。

フィルタリングされた検索。数種類の選択性で、1%の行が通過するまで。
これは、ベクトルを専用ストアではなくデータベース内に保持することを正当化するはずのケースであり、通常よりも多くの注意を払う価値があります。フィルタリングは「正しい」の意味を変えます。tag < 10 の行の中で真のトップ10は、全体での真のトップ10ではありません。そのため、各選択性について、通過する行のみで総当たり計算によりグラウンドトゥルースを再計算します。フィルタリングされた結果を、データセットと共に提供されたフィルタリングされていないグラウンドトゥルースに対してスコアリングすると、全てのエンジンがほぼゼロのリコールになります。私たちはそれを知っています。なぜなら、しばらくの間、まさにそれを実行したからです。

一部のクエリは、10行未満で返されます。ある実行では、200件中81件がそうでした。これはデータが尽きたわけではありません。10%の選択性では約99,000行がフィルタを通過するため、見つけるべき行は常に少なくとも10件あります。原因は操作の順序です。HNSWはまず距離で検索し、次にWHERE句を適用します。数千の候補を集め、フィルタがそれらのほとんどを破棄し、時には10件未満しか残りません。（もしフィルタが実際に10行未満に一致した場合、グラウンドトゥルースも縮小し、エンジンは依然として1.0をスコアリングします。）リコールはこれを既に処理しています。エンジンが返さなかった行はミスとしてカウントされるため、6つの正しい行は0.6をスコアリングします。行数を報告するのは、2つの異なる問題が同じスコアになるためです。「10行のうち4つが間違っている」と「6行すべてが正しい」はどちらも0.6です。前者はより広い検索が必要です。後者は反復スキャンが必要です。行数はどちらのタイプかを示します。また、6行は10行よりも作業量が少ないため、スループットは過大評価されます。

チャーン（Churn）。コーパスの一部を削除して再挿入する前後のリコールとスループット。削除はグラフのエッジを失われた行に向けたままにするためです。インデックスを再構築することで失われたものを回復できるかどうかは、まだ分かりません。これはテストすべき明白な次のステップであり、まだ実行していません。

比較を公平に保つ

全ては2回実行されます。

正規化されたパスは、全てのエンジンに同一のCPU、メモリ、キャッシュ予算を与え、結果の違いは実装によるもので、より多くのRAMが与えられたことによるものではありません。調整済みパスは、各エンジンがそのドキュメントが推奨する設定を使用できるようにします。調整済みはより現実的で、制御は少ないですが、だからこそ最初のパスを置き換えるものではありません。両方のパスを生き残った結果はエンジンに関するものです。それらの間で反転する結果は、全く異なる理由で興味深いものです。

コアは明示的にピン留めされます。物理コアごとに1つの論理CPUを使用します。なぜなら、SMT（Simultaneous Multi-Threading）の兄弟は実行ユニットを共有し、1つのコア上の2つのスレッドは2つのコアのように振る舞わないからです。ハイブリッドチップ上のPコアとEコアの混合も決して行いません。なぜなら、コアタイプ間の移行は、測定しようとしている効果のいくつかよりも多くのばらつきを追加するからです。永続性は、どこでも同じように緩和されます。そうでなければ、デフォルトのfsyncポリシーを比較して、それをベクトル検索と呼ぶことになります。

いくつかの違いは全く均等化できないため、それらを記録します。1つのエンジンだけが公開するノブは、正規化されたパスでは使用されません。なぜなら、それを使用すると、そのエンジンに他の誰も持っていないチューニング軸を与えることになるからです。特定の分離レベルを主張するエンジンは、全員に設定されます。そして、明らかにプレースホルダーであるデフォルト値は、共有予算からサイズ設定されます。あるエンジンのファミリーは依然として16 MiBのグラフキャッシュを出荷していますが、これは何も意味しません。ベンダー自身が変更することを期待している値でエンジンを評価することは、何も測定していません。これら全ては、結果の上にある「既知の非対称性」セクションに配置されます。

人々を困惑させるハードウェアに関する注記が1つあります。これらの実装のいくつかは、距離計算のために手書きのAVX-512コードを出荷しており、1つの命令で16個の浮動小数点数の算術演算を一度に行います。AVX-512を持たないCPU上での同じインデックスは、実質的に異なるベンチマークであり、減速はエンジンごとに同じではないため、数値を補正するためにスケーリングすることさえできません。CPUモデルとその機能フラグは、エンジンバージョンとコミット、イメージID、および実際に解決されたリソース制限と共に、その理由で各実行のマニフェストに含められます。マニフェストなしではレポートはありません。

結果の読み方

単一のチャートを見る前に、妥当性（validity）セクションを読んでください。私たちのレポートは、環境、次に妥当性、次に既知の非対称性、そして結果の順序で意図的に配置されています。失敗したフェーズ、エンジンが短い結果セットを返す、CPUがエンジンの要求する命令セットを欠いているなど、意見を形成する前に、それら全てがあなたの前に表示されます。

注意すべきは、静かなフルスキャンです。

これらのエンジンのいずれも、静かにベクトルインデックスの使用を停止し、代わりにテーブルをスキャンします。スキャンは正確な結果を遅く返します。そのため、出力では高いリコールと低いスループットのように見えます。これは、クエリプランを確認しない限り、保守的に調整されたインデックスと区別がつきません。

これは、全く面白くない理由で発生します。あるエンジンのオプティマイザは、ベクトルインデックスとテーブルスキャンのコストを比較し、LIMITがおおよそテーブルの4分の1を超えるとスキャンを選択します。私たちはまだそれを動かす設定を見つけていません。別のエンジンは、クエリがインデックス構築時に使用されたものとは異なる距離を要求した場合、エラーや警告なしにフォールバックします。インデックスをコサイン用に構築し、クエリをL2演算子で記述すると、シーケンシャルスキャンとソートが得られますが、それを知らせるものは何もありません。

そのため、全てのドライバーは各構成に対して EXPLAIN を実行し、プランにインデックス名が表示されているかを確認します。

WARNING: vector index NOT used (k=10, filtered=True). Plan: …Seq Scan…

スキャンされたものは全て妥当性に入ります。これは、偶然にも印象的なベクトルベンチマーク数値を生成する最も簡単な方法であり、ベンチマークがそれをチェックすることに言及していない場合、その中の何であれ信じる前に、その理由を知りたいと思います。

リコール対スループットの場合、有用な表示は数値ではなく曲線です。ef_search を反復し、リコール対QPSをプロットし、最良のポイントを保持します。各精度のレベルについて、その精度で何らかのエンジンが到達した最高のスループットです。あるエンジンが別のエンジンを上回るのは、同じリコールレベルでその曲線が他方の上にある場合のみです。曲線が交差する場合、答えは実際にどれだけ正確さが必要かによって決まり、それを言うことは回避策ではなく結果です。

曲線は、1つのポイントでの高さではなく形状を比較することを奨励するため、バーチャートもあります。リコールフロアが0.90、0.95、0.99の場合のスループットです。実際に受け入れられる精度を選択し、横に読んでください。

構築中に起こったこと

リストする価値があります。一部は、他のものを信頼する理由であり、一部は、同様のものを構築する人がそれらに遭遇する理由です。

最初の取り込み（ingest）数値はゴミでした。ロードパスは、オートコミットがオンの状態でネットワークラウンドトリップごとに1つのINSERTを実行しており、毎秒88行を測定しました。トランザクションあたり500行をバッチ処理すると、同じエンジンで373行になりました。最初の数値を公開することは、私たち自身のクライアントをベンチマークしてデータベースと呼ぶことになったでしょう。

フィルタリングされた検索とチャーンは、サブセットの行を使用した実行でも、フルコーパスのグラウンドトゥルースに対してスコアリングされていました。全てのエンジンが悪く見え、バグは完全に私たちのものでした。グラウンドトゥルースは現在、データセット、k、行数、選択性でキー付けされています。

両方のリソースパスが1つの結果ディレクトリを共有しており、ANNランナーは既に結果がある構成をスキップします。そのため、調整済みパスは、正規化されたパスが計算したものをすべて静かにスキップし、私たちの調整済み数値は、異なるラベルを付けた正規化された数値のほとんどでした。それに気づくのに、恥ずかしいほど長い時間がかかりました。

レディネスプローブは嘘をつきます。あるエンジンの標準的な「接続を受け入れていますか」チェックは、それが作成しようとしているデータベースが存在する前に成功を返します。プローブはパスし、最初のクエリは失敗し、私たちはしばらくの間、それがエンジンの問題だと確信していました。

最も最近のものは、1536次元のコーパスで発生しました。ANNランナーはデータセット全体をメモリに2回保持します。1つは親プロセスに、もう1つはフォークされたワーカーにあり、コピーは共有されていません。これは、サーバーが使用しているものに加えて、百万の埋め込みに対して約12 GBであり、サーバー専用にサイズ設定したコンテナ内でした。カーネルがワーカーを終了させました。ランナーはワーカーの終了コードをチェックしないため、「Terminating 1 workers」とログに記録し、正常に終了して結果を書き込みませんでした。これは、他に何もすることがない実行と全く同じように見えます。失敗まで3時間かかり、静かに失敗しました。

データベースの追加

これは、私たちが最も正しく行うことを重視した部分です。なぜなら、全体的な目的は、誰かがベクトル検索をリリースするたびに、装置を再構築することを避けることだったからです。各エンジンには以下が必要です。

• 固定されたバージョンからランタイムイメージとテストイメージを生成するDockerfile
• ポート、認証情報、およびどのサーバー設定が正規化されたCPUおよびメモリ予算にマッピングされるかを宣言する設定
• リコールとスループット側のモジュール
• ドライバー：インデックス作成、ロード、クエリ、フィルタリングされたクエリ、インデックスサイズ、およびEXPLAINチェック

次は何

結果は、マニフェストと生の各構成レコードと共に公開されるため、私たちの言葉を鵜呑みにするのではなく、それらを検証できます。全ては https://github.com/Percona-Lab/vector-bench にあります。ハーネス、ドライバー、Dockerfile、ドキュメントです。もし私たちが何かを誤って測定している、またはあなたが私たちよりもよく知っているエンジンに対して不公平であるなら、教えてください。