ベクトル量子化調査および選択ガイド

このドキュメントは、実用的な観点から一般的なベクトル量子化手法を紹介し、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");

Method Overview

Method	Core Idea	Typical Gain	Main Cost
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の低下がありました。

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

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アクセラレーションによりしばしば優れた検索時の動作を示しましたが、再現率/構築のトレードオフはデータとパラメータに依存していました。

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

Dorisの実用的選択ガイド

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

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

推奨検証プロセス：

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

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

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

関連ドキュメント

• Overview
• HNSW
• IVF
• ANN Resource Estimation Guide