LinkedInは、`pgvector`拡張で使用される一般的なHNSW（Hierarchical Navigable Small World）およびIVFFlatインデックスに対する高性能な代替手段を提供するために設計された、PostgreSQL用のオープンソース拡張機能「pg_vectorsearch」を導入しました。この新しいツールの核心はPRISMインデックスであり、基礎となるアーキテクチャをグラフベースの探索から、セントロイドとパーティションの階層構造へと移行させます。ベクトル空間をクラスターのツリーとして構成することで、このインデックスは、HNSWが必要とする複雑なグラフ構造と比較して、より予測可能なメモリ使用量と高速な構築時間を実現します。
この画像は、pg_vectorsearch拡張機能とそのPRISMインデックスアーキテクチャの公式ブランディングを表しています。
PRISMインデックスは、階層的k-meansクラスタリングを使用してベクトル空間を分割することで動作します。クエリ実行時、システムはレベルごとのビームサーチを実行して関連するパーティションを特定し、その後、それらに関連付けられたポスティングリストをスキャンします。メモリに移動するデータ量を最小限に抑えるため、この拡張機能はRaBitQ（Random Bit Quantization）を採用しており、これはベクトルを1次元あたり約1ビットで表現する手法です。この量子化には数学的な誤差範囲が含まれており、システムは候補のしきい値を設定することが可能です。候補の下限値が現時点での最良の結果を超えている場合、PostgreSQLのヒープからフル精度のベクトルを取得することなく破棄できるため、ランダムI/Oを大幅に削減できます。
PRISMは、HNSWよりも4倍少ないメモリで1億個のベクトルに対して6ミリ秒のクエリレイテンシを達成したと報告されるなど、大幅なパフォーマンス向上を提供しますが、特定の技術的制約も伴います。このインデックスは現在最大1,968次元までサポートしており、高次元のユースケースには適さない可能性があります。さらに、この拡張機能にはPostgreSQLバージョン18以上が必要であり、レガシーな本番環境にとっては移行の障壁となる可能性があります。パーティションの境界付近での精度を維持するために、PRISMは隣接するパーティションにベクトルの重複コピーを保存することができ、これはセントロイドベースのルーティング固有の制限によって近傍が漏れることを防ぐ戦略です。
PRISMはネイティブなPostgreSQLインデックスアクセスメソッドとして実装されているため、データベースの標準的なバッファ管理、Write-Ahead Logging（WAL）、およびMulti-Version Concurrency Control（MVCC）と直接統合されます。この統合により、セントロイドツリーの頻繁にアクセスされる部分は共有バッファキャッシュ内に保持されることが保証され、また「FASTSCAN」ページの使用により、32個のベクトルを同時にSIMDベクトル化してスコアリングすることが可能になります。しかし、新しい挿入によってインデックスが成長するにつれて、ポスティングリストページの物理的な隣接性が時間の経過とともに低下する可能性があり、初期のインデックス構築時と比較してシーケンシャルスキャンの効率に影響を与える可能性があります。