ストーリー

近似最近傍探索（ANN）

なぜ厳密検索ではダメなのか

graph LR
    subgraph BF["厳密検索（Brute Force）"]
        BF1["全ベクトルとの距離を計算"]
        BF2["正確だが O N×D の計算量"]
        BF3["100万件 × 1536次元
→ 1.5G回の演算"]
        BF4["レイテンシ: 数百ms〜数秒"]
    end

    subgraph ANN["近似最近傍探索（ANN）"]
        AN1["インデックス構造で
高速に候補を絞り込み"]
        AN2["多少の精度ロスと引き換えに
桁違いの高速化"]
        AN3["100万件でも
1-10ms で検索可能"]
        AN4["Recall@10 > 95% を維持可能"]
    end

    style BF fill:#fee2e2,stroke:#dc2626,color:#991b1b
    style ANN fill:#d1fae5,stroke:#059669,color:#065f46
    style BF1,BF2,BF3,BF4 fill:#f3f4f6,stroke:#9ca3af,color:#374151
    style AN1,AN2,AN3,AN4 fill:#f3f4f6,stroke:#9ca3af,color:#374151

主要ANNアルゴリズム

HNSW（Hierarchical Navigable Small World）

アルゴリズムの概要

HNSWは、多層のグラフ構造を使って近似最近傍を高速に探索するアルゴリズムです。

graph TD
    subgraph L2["Layer 2（少数ノード）"]
        L2A["A"] --- L2D["D"]
    end

    subgraph L1["Layer 1（中間ノード）"]
        L1A["A"] --- L1B["B"] --- L1D["D"] --- L1F["F"]
    end

    subgraph L0["Layer 0（全ノード）"]
        L0A["A"] --- L0B["B"] --- L0C["C"] --- L0D["D"] --- L0E["E"] --- L0F["F"] --- L0G["G"] --- L0H["H"] --- L0I["I"] --- L0J["J"]
    end

    L2A --> L1A
    L2D --> L1D
    L1A --> L0A
    L1B --> L0B
    L1D --> L0D
    L1F --> L0F

    S["検索の流れ"]
    S --- S1["1. 最上位レイヤーから
エントリーポイントを選択"]
    S --- S2["2. 現レイヤーで
最近傍ノードに移動"]
    S --- S3["3. 下位レイヤーに降りて
より密なグラフで探索"]
    S --- S4["4. 最下位レイヤーで
最終的な近傍を返す"]

    style L2 fill:#dbeafe,stroke:#2563eb,stroke-width:2px,color:#1e40af
    style L1 fill:#d1fae5,stroke:#059669,color:#065f46
    style L0 fill:#fef3c7,stroke:#d97706,stroke-width:2px,color:#92400e
    style S fill:#1e293b,stroke:#475569,color:#f8fafc
    style S1,S2,S3,S4 fill:#f3f4f6,stroke:#9ca3af,color:#374151

HNSWのパラメータ

interface HNSWConfig {
  // 構築時パラメータ
  m: number;              // 各ノードの接続数。大きいほど精度↑だがメモリ↑
  efConstruction: number; // 構築時の候補リストサイズ。大きいほど精度↑だが構築遅い

  // 検索時パラメータ
  efSearch: number;       // 検索時の候補リストサイズ。大きいほど精度↑だが検索遅い
}

// 推奨値
const defaultConfig: HNSWConfig = {
  m: 16,              // 一般的な推奨値。RAGでは12-24の範囲
  efConstruction: 200, // 構築時は高めに設定して品質確保
  efSearch: 100,       // 検索時はRecall/Latencyのバランスで調整
};

パラメータチューニングの指針

// pgvector での HNSW インデックス作成
async function createHNSWIndex(pool: Pool, config: HNSWConfig): Promise<void> {
  await pool.query(`
    CREATE INDEX CONCURRENTLY IF NOT EXISTS embeddings_hnsw_idx
    ON embeddings USING hnsw (embedding vector_cosine_ops)
    WITH (m = ${config.m}, ef_construction = ${config.efConstruction})
  `);

  // 検索時の ef_search はセッションレベルで設定
  await pool.query(`SET hnsw.ef_search = ${config.efSearch}`);
}

IVF（Inverted File Index）

アルゴリズムの概要

IVFは、ベクトル空間をクラスタに分割し、クエリベクトルに最も近いクラスタのみを探索するアルゴリズムです。

graph TD
    subgraph BUILD["構築フェーズ"]
        B1["1. K-Meansで全ベクトルを
nlistクラスタに分割"]
        B2["2. 各ベクトルが属する
クラスタを記録"]
        B1 --> B2
    end

    subgraph SEARCH["検索フェーズ"]
        S1["1. クエリベクトルに最も近い
nprobeクラスタを選択"]
        S2["2. 選択クラスタ内の
ベクトルのみを厳密検索"]
        S1 --> S2
    end

    subgraph SPACE["ベクトル空間"]
        CL1["クラスタ1
●●●"]
        CL2["クラスタ2
▲▲▲"]
        CL3["クラスタ3
■■■"]
        CL4["クラスタ4
◆◆◆"]
        Q["Q: クエリベクトル"] -.->|最近傍探索| CL4
    end

    BUILD --> SEARCH
    SEARCH --> SPACE

    style BUILD fill:#dbeafe,stroke:#2563eb,stroke-width:2px,color:#1e40af
    style SEARCH fill:#d1fae5,stroke:#059669,color:#065f46
    style SPACE fill:#fef3c7,stroke:#d97706,stroke-width:2px,color:#92400e
    style Q fill:#fee2e2,stroke:#dc2626,color:#991b1b
    style CL1,CL2,CL3,CL4 fill:#f3f4f6,stroke:#9ca3af,color:#374151
    style B1,B2,S1,S2 fill:#f3f4f6,stroke:#9ca3af,color:#374151

IVFのパラメータ

interface IVFConfig {
  nlist: number;    // クラスタ数。sqrt(N) が目安
  nprobe: number;   // 検索時に探索するクラスタ数
}

// データ量に応じた推奨値
function getIVFConfig(vectorCount: number): IVFConfig {
  const nlist = Math.max(
    Math.round(Math.sqrt(vectorCount)),
    100,  // 最低100クラスタ
  );
  const nprobe = Math.max(
    Math.round(nlist * 0.05),  // nlist の5%
    10,    // 最低10クラスタ
  );
  return { nlist, nprobe };
}

// 10万ベクトル → nlist=316, nprobe=16
// 100万ベクトル → nlist=1000, nprobe=50
// 1000万ベクトル → nlist=3162, nprobe=158

PQ（Product Quantization）

ベクトル圧縮

PQは、高次元ベクトルを圧縮してメモリ使用量を劇的に削減する手法です。

graph TD
    PRIN["原理"]
    PRIN --> P1["1. 1536次元のベクトルを
m個のサブベクトルに分割"]
    PRIN --> P2["2. 各サブベクトルを
k個の代表値 codebook で近似"]
    PRIN --> P3["3. 元のfloat32 × 1536次元
→ uint8 × m個に圧縮"]

    MEM["メモリ削減効果"]
    MEM --> M1["元: 1536 × 4 bytes
= 6,144 bytes/vector"]
    MEM --> M2["PQ m=192:
192 bytes/vector"]
    MEM --> M3["圧縮率: 32倍"]

    EX["100万ベクトルの場合"]
    EX --> E1["元: 5.7 GB"]
    EX --> E2["PQ: 183 MB"]

    style PRIN fill:#dbeafe,stroke:#2563eb,stroke-width:2px,color:#1e40af
    style MEM fill:#d1fae5,stroke:#059669,color:#065f46
    style EX fill:#fef3c7,stroke:#d97706,stroke-width:2px,color:#92400e
    style P1,P2,P3 fill:#f3f4f6,stroke:#9ca3af,color:#374151
    style M1 fill:#fee2e2,stroke:#dc2626,color:#991b1b
    style M2 fill:#d1fae5,stroke:#059669,color:#065f46
    style M3,E1,E2 fill:#f3f4f6,stroke:#9ca3af,color:#374151

IVF + PQの組み合わせ

// pgvector での IVFFlat インデックス
async function createIVFFlatIndex(pool: Pool, nlist: number): Promise<void> {
  await pool.query(`
    CREATE INDEX CONCURRENTLY IF NOT EXISTS embeddings_ivfflat_idx
    ON embeddings USING ivfflat (embedding vector_cosine_ops)
    WITH (lists = ${nlist})
  `);
}

// 検索時のパラメータ設定
async function setIVFSearchParams(pool: Pool, nprobe: number): Promise<void> {
  await pool.query(`SET ivfflat.probes = ${nprobe}`);
}

インデックス選択ガイド

データ量に応じた推奨

パフォーマンスベンチマーク

// ベンチマークの実装例
interface BenchmarkResult {
  algorithm: string;
  params: Record<string, number>;
  recall: number;        // Recall@10
  latencyP50: number;    // 50%ile latency (ms)
  latencyP99: number;    // 99%ile latency (ms)
  memoryMB: number;      // メモリ使用量 (MB)
  buildTimeSec: number;  // 構築時間 (秒)
}

async function benchmarkIndex(
  store: VectorStore,
  testQueries: { embedding: number[]; expectedIds: string[] }[],
): Promise<BenchmarkResult> {
  const latencies: number[] = [];
  let totalRecall = 0;

  for (const query of testQueries) {
    const start = performance.now();
    const results = await store.search(query.embedding, 10);
    const latency = performance.now() - start;
    latencies.push(latency);

    const retrievedIds = results.map(r => r.chunk.id);
    const recall = query.expectedIds.filter(id =>
      retrievedIds.includes(id)
    ).length / query.expectedIds.length;
    totalRecall += recall;
  }

  latencies.sort((a, b) => a - b);

  return {
    algorithm: store.constructor.name,
    params: {},
    recall: totalRecall / testQueries.length,
    latencyP50: latencies[Math.floor(latencies.length * 0.5)],
    latencyP99: latencies[Math.floor(latencies.length * 0.99)],
    memoryMB: 0, // 実際にはプロセスメモリを計測
    buildTimeSec: 0,
  };
}

-- shared_buffers: 総メモリの25%
ALTER SYSTEM SET shared_buffers = '4GB';

-- work_mem: インデックス構築時に必要
ALTER SYSTEM SET work_mem = '1GB';

-- maintenance_work_mem: HNSW構築用
ALTER SYSTEM SET maintenance_work_mem = '2GB';

-- effective_cache_size: 総メモリの50-75%
ALTER SYSTEM SET effective_cache_size = '12GB';

-- 1. 並列構築の有効化
SET max_parallel_maintenance_workers = 4;

-- 2. CONCURRENTLY オプションで本番影響を最小化
CREATE INDEX CONCURRENTLY embeddings_hnsw_idx
ON embeddings USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 200);

-- 3. 構築後にANALYZE
ANALYZE embeddings;

まとめ

チェックリスト

• ANN が必要な理由を理解した
• HNSW のアルゴリズムとパラメータ（m, efConstruction, efSearch）を理解した
• IVF のアルゴリズムとパラメータ（nlist, nprobe）を理解した
• PQ によるベクトル圧縮の仕組みを理解した
• データ量に応じたインデックス選択ガイドを把握した

次のステップへ

インデックス戦略を学びました。次のセクションでは、ハイブリッド検索やキャッシュなど、検索の最適化テクニックを学びます。

アルゴリズムの特性を理解した上でパラメータを選ぶ。ブラックボックスで使わないこと。

推定読了時間: 40分