クラウドネイティブデータウェアハウスByteHouseで高性能なベクトル検索を構築する方法の分析

LLM テクノロジーの適用と実装により、データベースのベクトル分析と AI サポート機能を向上させる必要があります。ベクターデータベースやベクター検索などの機能が登場し、業界から継続的に注目を集めています。簡単に言えば、ベクトル検索テクノロジーとベクトルデータベースは、LLM に外部メモリユニットを提供し、質問や過去の回答に関連するコンテンツを提供することで、LLM がより正確な回答を返すのに役立ちます。

LLM だけでなく、ベクトル検索は OLAP エンジンでも使用され、非構造化データの分析および検索機能が向上しています。 ByteHouse は、Volcano Engine が立ち上げたクラウドネイティブのデータウェアハウスです。最近、高性能なベクトル検索機能を導入しました。この記事では、ByteHouse チームのベクトルデータベース業界とテクノロジーに関する最先端の観察を組み合わせて、OLAP エンジンが高性能なベクトル検索機能を構築する方法について詳しく説明します。最後に、オープンソースソフトウェアの VectorDBBench テストツールを使用すると、Cohere 1M 標準テストデータセットで、リコールが 98 の場合、QPS パフォーマンスは専用のベクターデータベースを上回ることができます。

ベクトル検索の現状分析

ベクトル検索の定義

従来のデータベース方式では、画像、ビデオ、オーディオなどの非構造化データを処理できません。現在、一般的な技術は、一連の埋め込みモデルを通じて非構造化データをベクトル化された表現に変換し、それをデータベースまたは特定の形式で保存することです。検索プロセス中に、クエリ項目は同じモデルを通じて対応するベクトルに変換され、近似一致が実行されて非構造化データがクエリされます。

技術的な原理としては、ベクトル検索には主に K 最近傍 (KNN) 計算が含まれ、その目的は N 次元ベクトルのライブラリ内で最も類似する k 個の結果を見つけることです。

大量のデータを扱うシナリオでは、KNN 計算は通常非常にコストがかかり、短期間で結果を返すことは困難です。さらに、多くのシナリオでは、ユーザーは絶対的に正確な類似性の結果を必要としません。したがって、実際にベクトル検索を使用する場合、通常は KNN の代わりに類似最近傍検索、つまり ANN が使用され、k 個の絶対的に最も近似した結果から K 個の近似最適結果に変更され、それによってある程度の精度が犠牲になり、応答時間が短縮されます。

LLMとベクトル検索

大規模なモデルではトレーニングデータが限られているため、特定の分野の最新ニュースや情報に関するクエリの結果は通常不正確になります。検索の精度を向上させるために、検索する情報に関連する文書に対してテキスト処理を実行し、埋め込みモデルを介してベクトルをベクトルデータベースに書き込み、次に、近接検索のために同じ埋め込みモデルを介して質問をベクトルに変換するという一般的なアプローチがあります。質問の類似知識がプロンプトとして取得され、質問と一緒に処理するために大規模モデルに送信され、最終的により正確な回答が得られます。

ベクトル検索（インデックス作成）のための 4 つのアルゴリズム

ベクトル検索アルゴリズムは、そのストレージ構造に基づいて、大まかに 4 つのタイプに分けられます。

1 つ目は、LSH などの一般的なアルゴリズムを使用したテーブルベースです。
2 番目のタイプはツリーベースで、類似性に基づいてベクトルをツリー構造に構築します。
3 番目のタイプはクラスターベースで、IVF (Inverted File) とも呼ばれます。まずベクトルがクラスター化されます。検索時には、まず最も近い k 個のクラスター中心が計算され、次にこれらのクラスター中心内で最も近い k 個のベクトルが計算されます。このインデックスの利点は、必要なトレーニングプロセスが 1 つだけなので、構築が速いことです。他の一般的に使用されるインデックス（主にグラフベースのインデックス）と比較すると、転置リストとクラスター中心構造のみを追加で保存する必要があるため、追加のメモリ使用量は比較的少なくなります。ただし、それに応じた欠点もあります。クエリを実行するたびにクラスター中心のすべてのベクトルを走査する必要があるため、クエリ速度は次元情報に大きく影響され、高精度のクエリ計算は比較的大きくなり、計算オーバーヘッドが高くなります。このタイプのインデックスは通常、SQ、PQ などのいくつかの定量的アルゴリズムと組み合わせて使用されます。
4 番目のタイプはグラフベースで、類似性に応じてベクトルをグラフ構造に構築し、検索はグラフトラバーサルプロセスになります。一般的に使用されるアルゴリズムは HNSW です。これはリレーショナルクエリに基づいており、インデックスの構築とベクトル間の関係の構築に重点を置いています。主な技術は高速道路と多層最適化手法です。このアルゴリズムの利点は、クエリ速度が速く、同時実行パフォーマンスが優れていることです。一方、欠点としては、構築速度が遅く、メモリ使用量が多いことが挙げられます。

現在の実際のシナリオでは、最も一般的に使用されている方法は、後者の 2 つ、つまりクラスターベースとグラフベースの方法です。

ベクターデータベースの構築方法

まず、ベクターデータベースには、追加、削除、変更、クエリなどのデータメンテナンス機能を含む、ベクター型データとベクターインデックスの保存と管理に関する機能が必要です。さらに、ベクトル検索パフォーマンスに対する要件は通常、比較的高くなります。第二に、ベクトル検索は通常、属性フィルタリングなどの操作と組み合わせる必要があります。最後に、ベクター検索は通常、画像検索などのクエリ用の他の属性と組み合わせられます。最終的に必要なのは、類似した画像パスまたはファイルです。

ベクターデータベースを構築する場合、ベクターを中心にしてボトムアップで専用のベクターデータベースを構築するというアイデアがあります。このアプローチの利点は、ベクトル検索に対して特定の最適化を行い、高いパフォーマンスを確保できることです。欠点は、複雑なデータ管理機能とクエリ機能が欠けており、通常は他のデータベースと組み合わせて使用する必要があることです。

もう 1 つの設計アイデアは、既存のデータベースとデータエンジンに基づいて、ベクトル検索関連の拡張機能を追加することです。利点は、オールインワンのデータ管理とクエリサポートを提供できることです。欠点は、既存のアーキテクチャの制限により、高い検索パフォーマンスを実現することが難しいことです。

ベクターデータベースの最新動向

ベクターデータベースはまだ急速な発展の段階にあります。現在、2つの傾向があります。 1 つは、専用のベクターデータベースを基盤として使用し、ストレージとコンピューティングの分離、一貫性のサポート、リアルタイムインポートなど、より複雑なデータタイプとより多くのデータ管理メカニズムのサポートを継続的に追加することです。さらに、事前フィルタリングや事後フィルタリングなどの複雑なクエリ戦略のサポートも継続的に追加されています。

2 番目の構築アイデアは、データベースにベクトル検索拡張機能を追加して、より多くのベクトル検索アルゴリズムを継続的にサポートし、特別なフィルタリング戦略を継続的に追加し、ベクトル検索のニーズに応じて対応する実行プランを簡素化することです。

上記の 2 つの構築アイデアは、高性能なベクトル検索と完全なデータ管理およびクエリサポートを備えたデータベース形式という統一された目標に向かって収束しています。これは、ByteHouse がベクトル検索関連の機能を設計する際に考慮した主な目標の 1 つでもあります。

ByteHouseの高性能ベクター検索ソリューション

ByteHouse は、Volcano Engine が開発したクラウドネイティブのデータウェアハウス製品です。オープンソースのClickHouseエンジンをベースに技術アーキテクチャを再構築し、クラウドネイティブ環境の展開や運用保守管理、ストレージとコンピューティングの分離、マルチテナント管理などの機能を実現しました。スケーラビリティ、安定性、保守性、パフォーマンス、リソース使用率が大幅に向上しました。

さらに、ByteHouse は、ベクター検索、全文検索、地理空間データ検索などの機能もサポートしています。

高性能ベクターデータベースベースとしての ByteHouse の利点は、比較的完全な SQL 構文サポート、高性能コンピューティングエンジン、比較的完全なデータ管理メカニズム、さまざまなシナリオをサポートできる豊富なデータテーブルエンジンを備えていることです。

より高いベクトル検索パフォーマンスを実現するために、ByteHouse はベクトル中心の設計コンセプトに基づいて効率的なベクトル検索実行パスを構築しました。同時に、さまざまなシナリオのベクトル検索ニーズを満たすために、一般的に使用されるさまざまなベクトル検索アルゴリズムを導入しました。

デザイン

主なデザインアイデア

クエリ実行プロセス中に、ベクトル検索関連のクエリでは、構文解析から実行演算子への短絡変換が実行されます。同時に、コンピューティングの冗長性と IO オーバーヘッドを削減するために、特別な実行演算子が導入されています。
ベクター検索ライブラリ、ベクター検索エグゼキュータ、キャッシュ管理、メタデータ管理などのコンポーネントを含む専用のベクターインデックス管理モジュールが追加されました。
ストレージ層は、ベクターインデックス関連の読み取りおよび書き込みサポートを追加し、各データ部分はベクターインデックス永続ファイルを維持します。

基本的な使い方

実際の使用では、テーブルを作成するときに、インデックス名、ベクター列、インデックスタイプ情報を含むインデックス定義を追加できます。

データのインポートでは、Kafka に基づくリアルタイムインポート、ファイルの挿入、Python SDK など、複数の方法がサポートされています。

基本的なクエリは固定パターンです。必要な列情報を選択し、order by + limit 命令を追加します。クエリは、スカラー情報と組み合わせたハイブリッドクエリと、距離の範囲クエリをサポートします。

課題

高性能なベクトル検索機能を追加する過程で、ByteHouse は主に次の 3 つの困難を克服しました。

増幅問題を読む

根本原因: ByteHouse では、現在の最小の読み取り単位はマークです。 Vector Index クエリで取得した結果に行番号情報が含まれている場合でも、実際に読み取る際には、対応するマーク ID に変換し、下位のストレージ層に渡して読み取る必要があります。

最適化：

1. ベクトル検索の計算は前処理されます。

元の設計では、ベクトル検索計算では、各データ部分で最初にベクトル検索を実行して他の列情報を読み取り、その後に order by + limit を実行して最終結果を取得する必要がありました。このアプローチは、各データ部分の上位 k を取得することと同等であり、読み取られる行数は、部分数に mark_size を乗じて上位 k を乗じた数になります。ここで行われる最適化は、ベクトル検索の計算をデータ部分の読み取りの前に進めることです。まず、すべてのデータ部分のベクトル検索を実行してグローバル topK 結果を取得し、次にそれらを各データ部分に配布して読み取ります。これにより、IO を数百万から数千に削減でき、実際の使用では全体的なパフォーマンスが 2 倍以上になります。

2. ストレージ層でのフィルタリング。

フィルタリングのために、行レベルのクエリ結果をストレージレイヤーの読み取りマークの場所にプッシュダウンし、デシリアライゼーションのオーバーヘッドを削減します。

3. 範囲シナリオでフィルターを最適化します。

日付やラベルによる主キー検索などのシナリオでは、最初と最後のマークのみが読み取られてフィルター処理されるため、フィルターステートメントの実行オーバーヘッドが削減されます。

高いリソース消費

根本原因: MinMax などの他の単純なインデックスと比較すると、ベクトルインデックスの構築には時間がかかり、より多くのリソースを消費します。

最適化：

ビルドスレッドとバックグラウンドマージタスクには同時実行の制限が設定されています。
構築プロセス中に、メモリ使用量が最適化され、完全にメモリ内で実行されていた一部の計算がディスクベースになり、メモリバッファメカニズムが追加されました。この最適化は主に IVF タイプのインデックスに対して実行されます。

コールドリーディングの質問

理由: インデックスを使用するには、インデックス構造をメモリにロードする必要があります。メモリにロードされた後でのみ、検索の高速化を実行できます。

最適化：

キャッシュプリロードのサポートが追加されました。サービスの起動、データの書き込み、バックグラウンドデータのマージのシナリオでは、新しいインデックスを自動的にメモリに読み込むことができます。さらに、自動 GC により、キャッシュ内の期限切れのデータが自動的にリサイクルされます。

最終結果

ByteHouse チームは、業界最新の VectorDBBench テストツールに基づいてテストを実施しました。 Cohere 1M 標準テストデータセットでは、リコールが 98 で、専用のベクトルデータベースと同等のパフォーマンスを達成できました。リコールが 95 を超えると、QPS は 2600 を超え、p99 レイテンシは約 15 ミリ秒となり、業界をリードする利点となります。

パフォーマンス評価

QPS: 同時実行性が継続的に拡大するという前提の下で、どれだけの QPS を達成できるかを評価することを意味します。 HNSW インデックスを同時に使用すると、ByteHouse は Milvus に匹敵するか、それを上回ることさえあります。
再現率: QPSは、精度が同じで再現率が98の場合にのみ意味を持ちます。
ロード時間: データの書き込みやベクトルインデックスの構築にかかる時間を含め、外部からシステムに評価データを追加するのにかかる時間を指します。 ByteHouse のデータ書き込みと全体的な時間を含むプロセス全体は、Milvus よりも優れています。
シリアルレイテンシ P99: 10,000 クエリをシリアルで実行します (レイテンシ P99)。この場合、ByteHouse のパフォーマンスは Milvus よりもわずかに劣ります。主な理由は、ByteHouse IO とクエリ解析にはまだ追加のオーバーヘッドがあり、最適化が必要な領域が多数あることです。小さなクエリの場合、理想的な状態にはまだ達していません。

異なる指標評価

評価対象：IVFPQFS＋Refine(SQ8)とHNSW。

IVFPQFS＋Refine(SQ8)の利点:

リコール要件が高くないという前提の下、メモリ使用量は比較的少なくなります。（HNSWの3分の1）
メモリ使用量をさらに削減するために、refineの精度を下げることができます。
メモリリソースが限られており、書き込みシーンが頻繁に発生する

問題点:

高精度のシナリオではHNSWを置き換えることは困難である

今後の計画

ディスク上のインデックスへのインデックスアクセスや、より優れた圧縮アルゴリズム戦略など、必要なリソースが少なくパフォーマンスが向上するインデックス構造を構築します。
ベクトル取得を他のクエリ結果操作とより適切に統合する方法。たとえば、複雑なフィルタリングステートメント、UDFベースの埋め込み計算の融合、全文検索のサポートなどです。
パフォーマンスの最適化。オプティマイザーと組み合わせてシーンを最適化する方法
使いやすさとエコロジー。現在、langchain などの LLM フレームワークに接続しており、大規模モデルシナリオやその他のベクトル検索シナリオでより優れたユーザビリティを実現する方法をさらに検討していきます。

<<: ガートナー：持続可能性とデジタル主権がパブリッククラウドベースのAIサービスを選択する際の最重要基準となる

>>: CVPR 2024 フルスコアペーパー |変形可能な3Dガウス分布：変形可能な3Dガウス分布に基づく高品質の単眼動画像再構成のための新しい方法