AlloyDB 向け ScaNN: 数百万から数十億のベクトルに対応する、初の PostgreSQL ベクトル検索インデックス
Alan Li
Software Engineer, Databases
Yannis Papakonstantinou
Distinguished Engineer, Databases
※この投稿は米国時間 2025 年 3 月 12 日に、Google Cloud blog に投稿されたものの抄訳です。
エグゼクティブ サマリー - AlloyDB 向け ScaNN は、あらゆるサイズのベクトル インデックスをサポートする、初の Postgres ベースのベクトル検索拡張機能です。高速なインデックス構築、高速なトランザクション更新、小さなメモリ使用量、正確かつ高速な検索を実現します。
多くのお客様が AlloyDB for PostgreSQL を使用して、高度なセマンティック検索や生成 AI のユースケースを実現し、1 億から 10 億以上のベクトルでベクトル検索を実行しています。同時に、運用データベースの残りの部分と連携する大規模なベクトル検索インデックスが必要になり、最初に目を向けるのは Postgres OSS コミュニティの pgvector HNSW グラフ アルゴリズムです。pgvector は PostgreSQL SQL 言語を拡張し、SQL クエリをフィルタおよび結合と組み合わせてベクトル検索をサポートします。これは、最新のアプリケーションにとって非常に価値のある組み合わせです。
Google は 2023 年から、AlloyDB で HNSW が追加された人気の pgvector 拡張機能をサポートしており、今後もサポートを継続していく予定です。時間の経過とともに、複数の代替ベクトル インデックス戦略が登場し、HNSW もそのうちの一つになるでしょう。現在、pgvector HNSW は小規模なデータセットのクエリ パフォーマンスに優れていますが、大規模なデータセットでは、pgvector HNSW グラフ アルゴリズムはそれほど効果的ではありません。ベクトルの数が非常に多いワークロードでは、インデックスの構築にかかる時間と費用、生成されるインデックスのサイズ、インデックスが大きくなりすぎてメインメモリに収まらない場合のパフォーマンス低下という課題が生じる可能性があります。ベクトル インデックスに pgvector が適している状況もありますが、多くの AlloyDB ワークロードでは、代替手段を探す必要がありました。
その一環として、Google は 2024 年 10 月に AlloyDB 向け ScaNN 拡張機能をリリースし、あらゆるユースケースに対応する、市場をリードするベクトル検索ソリューションを提供しました。AlloyDB 向け ScaNN には、Google Research が過去 12 年にわたって開発してきた ScaNN ベクトル検索テクノロジーが組み込まれています。Google は、数百億以上のベクトルを含む Google 検索、YouTube、Google 広告などのアプリケーションで ScaNN を使用しているため、ScaNN が大量のデータセットでうまく機能するのは当然のことと言えます。また、費用対効果が高く柔軟性のあるオプションでもあります。提供するインデックスは pgvector 互換で、あらゆるサイズで機能し、メモリ使用量が 4 分の 1 になり、小さなデータセットでもレイテンシが最大 4 分の 1 になります。
このブログの「ベンチマーク」セクションで、AlloyDB 向け ScaNN が 10 億個のベクトルのインデックスを構築する場合、他の PostgreSQL システムよりも最大 60 分の 1 の費用で済むことを説明しています。また、HNSW はグラフ構造であり、メモリに収まらない場合は費用のかさむランダム アクセス I/O につながるため、インデックス（ScaNN と HNSW）がメインメモリに収まらない場合のレイテンシも最大 10 分の 1 になります。さらに、AlloyDB 向け ScaNN はインデックスの構築時間が短いだけでなく、pgvector HNSW に比べてレイテンシが最大 4 分の 1 になるため、小さなサイズ向けの競争力のあるオプションであることも、同セクションに記載されています。最後に、「アルゴリズム」セクションでは、AlloyDB 向け ScaNN のパフォーマンスの背景にある主な理由を説明しています。詳しくは、記事全文をご覧ください。
ベンチマーク
パフォーマンス テストでは、2 つの一般的なベンチマーク データセット、Glove-100（約 100 万ベクトル、100 次元）と BigANN-1B（10 億ベクトル、128 次元）を使用しました。Glove-100 を使用して、インデックスがメインメモリに収まる場合の pgvector HNSW のパフォーマンスと AlloyDB 向け ScaNN のパフォーマンス、収まらない場合の BigANN-1B のパフォーマンスを示します。まず、検索のパフォーマンスを見てみましょう。
検索のパフォーマンス
OSS Postgres 15 上の AlloyDB 向け ScaNN と pgvector HNSW 0.8.0 をテストしました。どちらも 16 vCPU 128 GB メモリ インスタンスで実行しています。また、2024 年初頭に Cloud ベンダー X がブログで公開した構成と結果に従って、pgvector HNSW 0.7.4 を 16 vCPU 128 GB メモリ インスタンスでテストしました。インデックスは、Glove-100 ベンチマークではメインメモリに収まりますが、BigANN-1B ベンチマークでは収まりません。
当然ながら、メインメモリに収まらない BigANN-1B では、すべてのインデックスのパフォーマンスが大幅に低下します。しかし、pgvector HNSW のレイテンシは 4 秒以上（確かに「秒」です）で、オンライン アプリケーションには許容できません。一方、AlloyDB 向け ScaNN は 10 倍優れたレイテンシ（431 ミリ秒）を実現します。これは、レイテンシが 100 ミリ秒であることが求められるが、費用対効果も求められるユースケースにとって重要です。
一般的に AlloyDB 向け ScaNN のフットプリントははるかに小さいため、AlloyDB 向け ScaNN インデックスはメインメモリに収まるのに対し、pgvector HNSW インデックスは収まらないというユースケースが数多くあります。たとえば、64 vCPU 512 GB メモリ インスタンスで AlloyDB を使用した場合、AlloyDB 向け ScaNN の BigANN-1B は 30 ミリ秒のレイテンシを実現し、pgvector HNSW（レイテンシが 4 秒以上）と比較して約 2 桁の高速化を実現します。
インデックス構築のパフォーマンス
では、インデックスの構築にどれくらい時間がかかったかを見てみましょう。多くのお客様から、pgvector HNSW は、大規模なデータセットのインデックス作成に時間がかかりすぎるというご指摘をいただいています。これは、BigANN-1B の pgvector HNSW インデックスを構築するときに明らかになります。PostgreSQL と Cloud ベンダー X の両方について、16 vCPU 128 GB メモリのマシンではインデックスを構築できなかったことに注目してください。その後、より大きなマシンと構成で、手間のかかる複数の試行を行い、最終的に大規模なインスタンスを使用して、妥当な時間内に pgvector HNSW インデックスを正常に構築しました。しかし、AlloyDB 向け ScaNN では、これらの特大インスタンスの約 10 分の 1 の費用で同じ 16 vCPU 128 GB メモリ インスタンスを使用しました。お客様は、低コストでインデックスを迅速に構築できる利便性を高く評価しています。
アルゴリズム
ベンチマークのセクションで示したように、2 つのベクトル インデックスがメインメモリに収まらない場合、AlloyDB 向け ScaNN と pgvector HNSW のパフォーマンスの差は大きくなります。実際、HNSW アルゴリズムの弱点は、pgvector コミュニティでよく知られています（このチケットなど）。さらに、AlloyDB 向け ScaNN のメモリ使用量は pgvector HNSW の 4 分の 1 に抑えられるため、AlloyDB 向け ScaNN は pgvector HNSW がメモリに収まらない場合でもメモリに収まることを示しました。これらの違いは、2 つのインデックスのデータ構成とアルゴリズムの根本的な違いによって説明されます。理由を理解するために、まずメモリ フットプリントの違いについて説明します。
HNSW はグラフベースのインデックスですが、ScANN は木量子化ベースのインデックスです。一般に、グラフベースのインデックスでは、インデックスはグラフであり、各ベクトルはグラフのノードに対応します。各ノード（各ベクトル）は、選択した隣接ノードに対応するノードに接続されます。通常は、各ノードと他のノードとの接続数を m=20 程度にすることをおすすめします（m はグラフノードあたりの最大隣接ノード数）。さらに、HNSW は、上位レイヤが下位レイヤのエントリ ポイントを提供する、複数の階層レイヤを備えています。
次に、パフォーマンスの違いを見てみましょう。エントリ ポイントから、HNSW は最上位のレイヤで貪欲探索を実行し、検索したベクトルに対する最近傍を検索します。貪欲探索は、挿入されたベクトルに最も近い近傍に反復的に移動し、より近い近傍が見つからなくなるまでこれを続けます。最下層に到達して最も近い近傍が返されるまで、次の下位レイヤに降り、貪欲探索プロセスを繰り返します。
HNSW では、グラフ トラバーサル アクセスはランダムです。したがって、グラフノードがバッファとディスク間でページインとページアウトを行う必要がある 1 億以上のベクトル データセットでは、これらのランダム アクセスによってパフォーマンスが急激に低下します（チケット #700 を参照）。HNSW のランダム アクセスとは異なり、AlloyDB 向け ScaNN のインデックスはキャッシュ フレンドリーであるため、インデックスがセカンダリ ストレージにある場合はブロックベースのアクセス用に最適化され、インデックスがキャッシュされている場合は効率的な SIMD オペレーション用に最適化されます。メモリ不足のデータベース アルゴリズムではよくあることですが、順次アクセスとブロックベース アクセスはランダム アクセスよりも優れています。
次のステップ
Google において ScaNN ベクトル検索は、数十億が利用するユーザー アプリケーションに必要なパフォーマンスを実現するうえで不可欠な存在です。そして今、AlloyDB 向けの ScaNN により、独自のベクトルベースの検索アプリケーションを強化できます。詳細については、AlloyDB 向け ScaNN インデックスの概要をご確認ください。また、AlloyDB 向け ScaNN に関するホワイトペーパーでは、ベクトル検索の概要を紹介し、ScaNN アルゴリズムとその PostgreSQL や AlloyDB への実装方法について詳しく説明しています。
AlloyDB 向け ScaNN が一般提供されています。クイックスタート ガイドに沿って AlloyDB インスタンスを作成し、ドキュメントに沿って高速なベクトルクエリの利用を開始してください。また、AlloyDB を無料で試用できる 30 日間無料トライアルもご利用いただけます。
この投稿は、AlloyDB セマンティック検索チーム（Bohan Liu、Yingjie He、Bin Song、Peiqin Zhao、Jessica Chan）の成果を反映するものです。AlloyDB パフォーマンス エンジニアリング チームと、ベンチマーク結果に貢献した Shrikant Awate、Rajeev Rastogi、Mohit Agarwal、Rishwitha Gunuganti、Hardik Shah、Jahnavi Malhotra、Hari Jeyamani にお礼を申し上げます。また、ScaNN チームの研究に感謝します。
-データベース担当ソフトウェア エンジニア、Alan Li
-データベース担当上級エンジニア、Yannis Papakonstantinou
