メインコンテンツまでスキップ

ベクトル量子化調査・選択ガイド

この文書では、実用的な観点から一般的なベクトル量子化手法を紹介し、Apache Doris ANN ワークロードでの適用方法を説明します。

量子化が必要な理由​

ANN ワークロード、特に HNSW では、インデックスメモリがボトルネックになりがちです。量子化は高精度ベクトル（通常 float32）を低精度コードにマッピングし、少量のリコールと引き換えにメモリ使用量を削減します。

Doris では、量子化は ANN インデックスの quantizer プロパティによって制御されます：

  • flat：量子化なし（最高品質、最高メモリ使用量）
  • sq8：スカラー量子化、8ビット
  • sq4：スカラー量子化、4ビット
  • pq：プロダクト量子化

例（HNSW + quantizer）：

CREATE TABLE vector_tbl (
  id BIGINT,
  embedding ARRAY<FLOAT>,
  INDEX ann_idx (embedding) USING ANN PROPERTIES (
    "index_type" = "hnsw",
    "metric_type" = "l2_distance",
    "dim" = "768",
    "quantizer" = "sq8"
  )
)
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 8
PROPERTIES ("replication_num" = "3");

メソッド概要​

メソッドコアアイデア一般的な利得主なコスト
SQ (Scalar Quantization)各次元を独立して量子化大幅なメモリ削減、シンプルな実装FLATよりもビルドが遅い；より強い圧縮で再現率が低下
PQ (Product Quantization)ベクトルをサブベクトルに分割し、コードブックで各サブベクトルを量子化多くのデータセットで圧縮/レイテンシのバランスが良好訓練/エンコーディングコストが高い；チューニングが必要

Apache Dorisは現在、ANNベクトルインデックス作成と検索のコアエンジンとして最適化されたFaiss実装を使用しています。以下で説明するSQ/PQの動作は、実際のDorisに直接関連しています。

Scalar Quantization (SQ)​

原理​

SQはベクトルの次元を変更せず、次元あたりの精度のみを下げます。

次元ごとの標準的なmin-maxマッピングは以下の通りです：

  • max_code = (1 << b) - 1
  • scale = (max_val - min_val) / max_code
  • code = round((x - min_val) / scale)

Faiss SQには2つのスタイルがあります：

  • Uniform：すべての次元が1つのmin/max範囲を共有
  • Non-uniform：各次元が独自のmin/maxを使用

次元の値の範囲が大きく異なる場合、non-uniform SQは通常より良い再構成品質を提供します。

主な特徴​

  • 強み：
    • 直截的で安定
    • 予測可能な圧縮（sq8はfloat32値の約4倍、sq4は約8倍）
  • 弱み：
    • 分布が固定ステップでバケット化できることを前提
    • 次元が高度に非均一（例：強いロングテール）の場合、量子化エラーが増加する可能性

Faissソースレベルノート (SQ)​

Doris + 最適化されたFaiss実装パスの下で、SQ訓練はまずmin/max統計を計算し、その後追加時の範囲外リスクを減らすために範囲をわずかに拡張します。簡略化された形状は以下の通りです：

void train_Uniform(..., const float* x, std::vector<float>& trained) {
    trained.resize(2);
    float& vmin = trained[0];
    float& vmax = trained[1];
    // scan all values to get min/max
    // then optionally expand range by rs_arg
}

非均一SQでは、Faissは次元ごとの統計（1つのグローバル範囲ではなく）を計算するため、異なる次元が大きく異なる値のスケールを持つ場合に、通常はより良い動作をします。

実用的な観察​

内部の128D/256D HNSWテストにおいて：

  • sq8は一般的にsq4よりもrecallをよく保持しました。
  • SQインデックスのbuild/add時間はFLATよりも大幅に長くなりました。
  • 検索レイテンシの変化はsq8では多くの場合小さく、一方sq4はより大きなrecallの低下を示しました。

以下の棒グラフはベンチマークデータの例に基づいています：

SQ build time vs rows (128D)

SQ memory usage vs rows (128D)

Product Quantization (PQ)​

原理​

PQはD次元ベクトルをM個のサブベクトル（それぞれD/M次元）に分割し、各部分空間にk-meansコードブックを適用します。

主要なパラメータ：

  • pq_m：サブ量子化器（サブベクトル）の数
  • pq_nbits：サブベクトルコードあたりのビット数

より大きなpq_mは通常品質を向上させますが、訓練/エンコーディングコストを増加させます。

PQがクエリ時により高速になり得る理由​

PQはLUT（ルックアップテーブル）距離推定を使用できます：

  • クエリサブベクトルとコードブックセントロイド間の距離を事前計算します。
  • テーブルルックアップ + 累積により完全ベクトル距離を近似します。

これにより完全な再構築を回避し、検索CPU コストを削減できます。

Faissソースレベル注記 (PQ)​

同じ実装パスの下で、Faiss ProductQuantizerは部分空間上でコードブックを訓練し、それらを連続的なセントロイドテーブルに格納します。簡略化された形状は：

void ProductQuantizer::train(size_t n, const float* x) {
    Clustering clus(dsub, ksub, cp);
    IndexFlatL2 index(dsub);
    clus.train(n * M, x, index);
    for (int m = 0; m < M; m++) {
        set_params(clus.centroids.data(), m);
    }
}

セントロイドは (M, ksub, dsub) としてレイアウトされます。ここで：

  • M：サブ量子化器の数
  • ksub：サブスペースあたりのコードブックサイズ（2^pq_nbits）
  • dsub：サブベクトルの次元（D / M）

実用的な観察​

同じ内部テストにおいて：

  • PQは明確な圧縮効果を示しました。
  • PQのエンコーディング/トレーニングのオーバーヘッドは高いものでした。
  • SQと比較して、PQはLUT高速化により検索時の動作が優れることが多くありましたが、再現率/構築のトレードオフはデータとパラメータに依存していました。

以下の棒グラフはベンチマークデータの例に基づいています：

PQ index size on disk vs rows (128D/256D)

PQ build time vs rows (128D/256D)

PQ search time vs rows (128D/256D)

DorisのPractical Selection Guide​

これを出発点として使用してください：

  1. メモリが十分で再現率が最優先の場合：flat
  2. 比較的安定した品質で低リスクの圧縮が必要な場合：sq8
  3. 極端なメモリ圧迫があり、低い再現率を受け入れられる場合：sq4
  4. より強いメモリ・パフォーマンスバランスが必要で、チューニングに時間を費やせる場合：pq

推奨される検証プロセス：

  1. ベースラインとしてflatから開始します。
  2. まずsq8をテストし、再現率とP95/P99レイテンシを比較します。
  3. メモリがまだ高すぎる場合は、pqをテストします（最初の試行としてpq_m = D/2）。
  4. sq4はメモリ削減が再現率より高い優先度を持つ場合にのみ使用します。

ベンチマークに関する注記​

  • 絶対時間はハードウェア/スレッド/データセットに依存します。
  • 同じ条件下でメソッドを比較してください：
    • ベクトル次元
    • インデックスパラメータ
    • セグメントサイズ
    • クエリセットとground truth
  • 品質とコストの両方を評価してください：
    • Recall@K
    • インデックスサイズ
    • 構築時間
    • クエリレイテンシ

関連ドキュメント​