向量索引 ANN

對應原題（Common ‧ RAG and Retrieval）

Compare HNSW, IVF-PQ and flat indexes. How do you pick, and what does recall@k cost in latency?

🎯 什麼情境該想到我

當你「要選向量資料庫的索引型別、或發現搜尋結果有時候莫名漏掉正確答案」的時候。
★ 關鍵認知：ANN 的 A 是 Approximate——它「本來就會漏」，這是設計，不是 bug。

⚙️ 怎麼用

問題規模

精確最近鄰要和全部 $N$ 個向量比一次： $O (N \cdot d)$ 。
$N = 1 0^{7}$ 、 $d = 768$ 時每次查詢要 77 億次浮點運算——單機做不到即時。

所以引入近似：用一點 recall 換巨大的速度。

一、Flat（暴力搜尋）

不建索引，全掃。

✅ recall = 100%，零調參，即時增刪，是所有評估的黃金標準
❌ $O (N)$

什麼時候夠用： $N < 100, 000$ 時，現代 SIMD + 多執行緒通常在幾毫秒內掃完。

★ 很多專案在 5 萬筆資料上折騰 HNSW 參數，完全沒必要。先用 Flat，撞到牆再說。

二、IVF（倒排檔案）—— 分群

建索引時：對所有向量跑 k-means，分成 nlist 個 cell（常見 $N$ 到 $4 N$ ）
查詢時：只比對距離最近的 nprobe 個 cell

$掃描量 \approx N \times \frac{nprobe}{nlist}$

nprobe=1 極快但 recall 差；nprobe=nlist 退化成 Flat。nprobe 就是 recall/延遲旋鈕。

⚠️ 邊界效應：真正的最近鄰可能落在隔壁 cell。這是 IVF 漏召回的主要來源，也是它 recall 天花板通常低於 HNSW 的原因。
⚠️ 需要 train（跑 k-means）。資料分布變了要重訓，否則 cell 會失衡。

三、PQ（乘積量化）—— 壓縮

把 $d$ 維向量切成 $m$ 段，每段各自用一個 256 點的碼本量化成 1 byte。

$d \times 4 bytes ⟶ m bytes$

實例：768 維 fp32 = 3,072 bytes → $m = 96$ 的 PQ = 96 bytes，壓縮 32 倍。

距離用查表近似計算（ADC），不需要解壓縮。代價是距離本身變成近似 → recall 再降一階。

IVF-PQ = 分群（少掃） + 量化（省記憶體），是十億級規模的標準做法。

四、HNSW —— 多層近鄰圖

建一個「可導航的小世界圖」，分層：上層稀疏用來長程跳躍，下層稠密用來精修。像跳表，但在向量空間裡。

Layer 2:   ●──────────────●          少數節點，長邊，快速跨越
              ╲         ╱
Layer 1:   ●───●────●───●──●         中等密度
            ╲  │   ╱ ╲  │ ╱
Layer 0:   ●─●─●─●─●─●─●─●─●         全部節點，短邊，精修

查詢從頂層進入，貪婪地往更近的鄰居走，走不動就降一層，直到 Layer 0。

參數	何時作用	影響
`M`	建索引	每個節點的連邊數。大 → recall 高、記憶體大、建圖慢。常見 16–64
`efConstruction`	建索引	建圖時的候選佇列大小。大 → 圖品質好、建得慢。常見 100–500
`efSearch`	查詢	★ 唯一的線上 recall/延遲旋鈕。大 → recall 高、慢

記憶體估算（ $N$ 向量、 $d$ 維、fp32）：
$bytes \approx N \times (向量 4 d + 圖，約 M \times 2 條邊 \times 4 B 8 M)$

實例： $N = 1 0^{6}$ 、 $d = 768$ 、 $M = 16$

向量  : 1M × 3,072 B = 3.07 GB
圖    : 1M ×   128 B = 0.13 GB
合計  ≈ 3.2 GB       ← 全部要常駐記憶體

同樣資料用 IVF-PQ（ $m = 96$ ）只要 ~0.1 GB。這 30 倍就是選型的核心取捨。

★ 五、對照表

	Flat	IVF-PQ	HNSW
recall 天花板	100%	中（~85–95%）	高（~95–99%+）
查詢延遲	高， $O (N)$	低	最低
記憶體	中	最低（壓 10–50×）	最高
建索引時間	0	中（要 train）	慢
需要訓練	❌	✅	❌
即時新增	✅	⚠️ 會逐漸失衡	⚠️ 可以但變慢
刪除	✅	⚠️	❌ 只能墓碑標記，要定期重建
查詢期旋鈕	—	`nprobe`	`efSearch`

★ 六、recall@k 換延遲：報酬遞減曲線（題目的核心）

所有 ANN 索引的本質都一樣：掃描更多候選 → recall 上升、延遲上升。 而這條曲線是強烈的報酬遞減：

recall
100% ┤                              ╭─────  ← 最後幾個百分點極貴
 99% ┤                    ╭────────╯
 95% ┤          ╭────────╯
 90% ┤     ╭───╯
 80% ┤  ╭─╯
     └──┴──────────────────────────────▶ 延遲（≈ efSearch / nprobe）

經驗量級（依資料分布差很多，務必自己量）：

從 → 到	延遲大約
80% → 90%	×1.5
90% → 95%	×2
95% → 99%	×4–10
99% → 99.9%	×10+（常常不如直接用 Flat）

★ 面試的關鍵洞察：RAG 不需要 99.9% 的 recall。
因為後面還有 Reranker 重排序，而且生成端只用 top-5。
95% recall@50 對一個有 reranker 的管線來說綽綽有餘——多花 10 倍延遲去追最後那 4%，是拿使用者體驗換一個量不出差別的指標。

真正該量的不是 recall@k，是端到端的答案正確率。

七、選型決策樹

N < 100k ?                      → Flat（別過度工程）
  │
  ├─ 記憶體裝得下全精度向量？
  │     是 → HNSW（recall 與延遲最好）
  │     否 → IVF-PQ / HNSW+PQ / DiskANN（放 SSD）
  │
  ├─ 需要頻繁刪除？             → 避開純 HNSW，或選有處理墓碑的託管服務
  ├─ 需要極高寫入吞吐？         → IVF 類（HNSW 建圖是瓶頸）
  └─ 大量 metadata 過濾？       → 見下

★ 八、過濾搜尋（最容易踩雷的地方）

實務上幾乎都要「只搜這個使用者能看的／這個版本的／這個語言的」。三種做法：

做法	問題
後過濾（先 ANN 取 top-k，再濾）	⚠️ 過濾掉太多就不夠了 —— top-50 濾完剩 2 個。選擇率越低越糟
前過濾（先篩出子集再搜）	⚠️ 子集可能很大，退化成 Flat
原生 filtered ANN	✅ 在圖／cell 走訪時就套用過濾。各家實作差異大

★ HNSW 在高選擇性過濾下會「圖斷連」：符合條件的節點在圖上彼此不相鄰，貪婪走訪走不過去，recall 暴跌。
這是「加了權限過濾後 RAG 突然變爛」的典型原因，而且在沒有過濾的測試集上完全測不出來。
→ 測試集必須包含真實的過濾條件。見權限感知檢索與引用歸因。

九、產品怎麼選（不是索引型別，是要不要多養一個元件）

（補充自 https://juejin.cn/post/7690026779797733411，查證 2026-09-28）

上面談的是索引型別；實務上更早遇到的問題是要不要為了向量檢索多養一個資料庫：

產品	定位	什麼時候選它
pgvector	Postgres 擴充，支援 HNSW／IVFFlat	Postgres 本來就在、百萬級以下。免費得到與 metadata（`user_id`！）同庫聯查、交易、備份
Qdrant	專用向量庫（Rust），稀疏＋稠密	中等規模、檢索功能要求細
Milvus	分散式，億級	大規模、且有多團隊運維能力
Weaviate	內建 BM25 混合	想開箱就要混合檢索
Chroma	輕量嵌入式	原型／demo

★ 預設選 pgvector。向量檢索不過是一句 ORDER BY embedding <=> :query LIMIT 5，
索引一行 CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops);
（<=> 是 cosine distance＝1 − cosine similarity，pgvector 官方文件查證 2026-09-28）。
為了幾萬筆向量多運維一個資料庫，通常是給自己找事。

⚠️ 常見誤解：「要做稀疏＋稠密混合就得換專用向量庫」——pgvector 自 0.7.0 起就有 sparsevec 型別（上限 1,000 個非零元素）與 sparsevec_*_ops 索引。混合檢索不是換庫的充分理由；資料量級和運維能力才是。

⚠️ 注意 / 什麼時候不適用

一定要有 Flat 當對照。拿一個小樣本跑 Flat 求 ground truth，才能算出你的 ANN 實際 recall 是多少。沒量過就不知道漏了什麼。
距離度量要和 embedding 模型一致（cosine / 內積 / L2）。用內積就要確認向量是否已正規化。
PQ 之後別再期待精確分數。近似距離不能拿來做閾值判斷。
HNSW 的刪除是墓碑。大量刪改後 recall 與延遲都會劣化，要排定期重建。
建索引時間別低估。千萬級的 HNSW 建圖可能要數小時，影響重建索引的營運節奏。
向量維度可以降。Matryoshka 表示法的模型支援截斷維度（768 → 256），記憶體省 3 倍而 recall 掉很少——常比換索引型別划算。
大多數人不該自己調這些。託管向量庫（pgvector、Qdrant、Weaviate、Milvus…）有合理預設。先用預設，量出問題再調。

🧪 我實際套用的紀錄

2026-09-20：從面試題庫展開。待辦：下次建索引前先用 Flat 量一組 ground truth。

🔗 相關

稀疏與密集檢索 —— 它服務的是 dense 那一側
Reranker 重排序 —— 有它就不必追極高 recall
權限感知檢索與引用歸因 —— 過濾搜尋的正確做法
RAG 評估與營運 —— recall@k 怎麼量
量化 Quantization —— PQ 與模型量化是同一個思路的兩個應用
工具-用trigram索引加速模糊查詢 —— PostgreSQL 上的另一種索引取捨

Quartz 5

Explorer