第4章: ベクトル検索の心臓部 — ANNアルゴリズム徹底理解

なぜ厳密最近傍では間に合わないのか

クエリベクトルに対して最も近いK件を返す、これが「ベクトル検索」の中核処理です。 素朴な実装は単純で、全件とクエリの距離を計算して上位K件を取り出す「ブルートフォース」です。 数千件までなら実用的ですが、数百万件を超えると致命的に遅くなります。

ANN（Approximate Nearest Neighbor、近似最近傍）はこの問題を解く技術です。 「正確なTop-K」を諦めて「ほぼ正確なTop-K」を返すことで、計算量を劇的に減らします。 実務ではRecall 95〜99%を保ちつつ、厳密kNNの100〜1000倍の速度を出すのが普通です。

ANNアルゴリズム家系図

ANNには大きく3系統あります。それぞれ異なるアイデアで「近い候補を高速に絞る」を実現します。

graph TB
  ANN[ANNアルゴリズム] --> H[ハッシュ系]
  ANN --> T[ツリー/クラスタ系]
  ANN --> G[グラフ系]
  H --> LSH[LSH\n1998]
  T --> IVF[IVF\nk-means]
  T --> IVFPQ[IVF-PQ\n圧縮追加]
  T --> Annoy[Annoy\nランダム射影木]
  G --> HNSW[HNSW\n2016]
  G --> DiskANN[DiskANN\nSSD最適化]
  G --> ScaNN[ScaNN\nGoogle]

  style HNSW fill:#14b8a6,stroke:#0d9488,color:#fff
  style IVFPQ fill:#f97316,stroke:#ea580c,color:#fff
  style DiskANN fill:#8b5cf6,stroke:#6d28d9,color:#fff

HNSWの直感的理解 — 多層Small Worldグラフ

HNSW（Hierarchical Navigable Small World）は、Malkov & Yashuninが2016年に発表し、 現在のベクトル検索の事実上の標準となったアルゴリズムです。 名前は難しそうですが、中核アイデアは意外とシンプルです。

1. 全ノード（ベクトル）をグラフで接続する — 各ノードは近傍ノードとエッジで繋がる
2. グラフを多層化する — 上位層は疎（ハブ的ノードのみ）、下位層は密。スキップリストのイメージ
3. 検索はgreedyに進む — 上位層で大雑把に近づき、下位層で精緻化する
4. Small World特性 — 少数ホップで任意ノードに到達できる接続構造（6次の隔たり理論に近い）

graph TB
  subgraph Layer2[Layer 2 疎]
    L2A[Node A]
    L2B[Node B]
  end
  subgraph Layer1[Layer 1 中]
    L1A[A]
    L1B[B]
    L1C[C]
    L1D[D]
  end
  subgraph Layer0[Layer 0 密 全ノード]
    L0A[A]
    L0B[B]
    L0C[C]
    L0D[D]
    L0E[E]
    L0F[F]
    L0G[G]
  end
  L2A -.降下.-> L1A
  L2B -.降下.-> L1B
  L1C -.降下.-> L0C
  L1D -.降下.-> L0D
  Q[クエリ] -.エントリ.-> L2A
  L2A --> L2B

  style Q fill:#3b82f6,stroke:#1d4ed8,color:#fff
  style Layer0 fill:#1e293b,color:#fff
  style Layer1 fill:#334155,color:#fff
  style Layer2 fill:#475569,color:#fff

HNSWの3大パラメータ

HNSWは以下の3つのパラメータで精度・速度・メモリのトレードオフを制御します。 実務では必ず自データで計測して決めますが、典型的な設定レンジは次の通りです。

-- pgvector HNSW作成（1M行想定）
SET maintenance_work_mem = '16GB';
SET max_parallel_maintenance_workers = 7;

CREATE INDEX CONCURRENTLY idx_embedding
ON documents USING hnsw (embedding vector_cosine_ops)
WITH (m = 32, ef_construction = 128);

-- クエリ時の動的チューニング
SET LOCAL hnsw.ef_search = 100;

SELECT id, content
FROM documents
ORDER BY embedding <=> $1::vector
LIMIT 10;

IVF / IVF-PQ — クラスタリングによる高速化

IVF（Inverted File Index）は、k-meansでベクトル空間をクラスタ分割し、 クエリ時は近傍クラスタ（nprobe個）だけを精査する手法です。 HNSWよりメモリ効率が良く、大規模データで有利です。

PQ（Product Quantization）はベクトルをサブベクトルに分割して量子化し、メモリを1/10〜1/30に圧縮する技術です。 IVFとPQを組み合わせたIVF-PQは、Facebook Faissで広く使われる十億規模検索の定番です。

IVFFlatでは lists（クラスタ数）と probes（探索クラスタ数）がチューニングの肝です。 経験則は lists = √rows、probes = √lists。 100万行なら lists=1000, probes=32 が目安です。

DiskANN — 数十億規模のコスト最適化

DiskANNはMicrosoft Researchが2019年に発表したアルゴリズムで、 インデックスをSSD上に配置し、圧縮ベクトルだけRAMにキャッシュすることで、数十億規模の検索をコスト効率よく実現します。 TimescaleのpgvectorscaleがこれをPostgreSQL向けに実装しています。

ベンチマーク数値の読み方

公開ベンチマークを見るときは、以下の4軸を必ずチェックしてください。これらがそろっていないと公平な比較になりません。

1. Recall@k: どのKでどれだけのRecallか（95% vs 99%で劇的に変わる）
2. レイテンシ: p50 / p95 / p99 のどれか
3. データ規模と次元数: 100万 × 768次元と1億 × 1536次元では別物
4. ハードウェア: CPU/RAM/ストレージ種別、並列度

代表的な指標として、Qdrantのベンチマークでは768次元×1M件で p50レイテンシ 4ms、p99 25ms を達成。 Alibaba CloudのRDS PostgreSQLベンチマークでは、HNSWがIVFFlatの15.5倍のQPSを出しつつ、構築時間は32倍長い、という結果が出ています。

選定ガイド — どのインデックスを選ぶべきか

次章では、具体的なベクトルDBの比較と、特にpgvectorを本番で運用するためのチューニング実践を掘り下げます。 pgvector 0.8の新機能（iterative scan、halfvec、binary quantization）や、pgvectorscaleの実測値まで詳説します。