Vector DB 3 — Thuật toán ANN & chỉ mục

Vì sao cần tìm lân cận gần đúng (ANN)?

Ở Vector DB 2 — Embeddings & độ tương đồng ta đã biết: mỗi đoạn tài liệu được biến thành một vector nhiều chiều, và "gần nhau về ý nghĩa" tương đương "gần nhau về khoảng cách". Bài toán truy vấn trở thành: cho một vector câu hỏi q, tìm k vector gần q nhất trong kho — đây là k-Nearest Neighbors (KNN).

Cách làm ngây thơ (exact KNN, còn gọi là brute-force / flat search) là tính khoảng cách từ q tới từng vector trong kho, rồi lấy k cái nhỏ nhất. Với N vector chiều d, mỗi truy vấn tốn O(N·d) phép tính. Con số này chết người ở quy mô thật:

• Kho 1.000 vector: brute-force chạy dưới mili-giây — không cần index.
• Kho 5 triệu chunk tài liệu, d = 1024: mỗi truy vấn phải làm ~5 tỷ phép nhân-cộng. Ngay cả với SIMD, một truy vấn có thể mất hàng trăm mili-giây trên một core, và không scale khi QPS tăng.
• Kho 1 tỷ vector: exact KNN gần như bất khả thi cho hệ thống trực tuyến.

Đây là lý do Approximate Nearest Neighbor (ANN) ra đời. Ý tưởng cốt lõi: chấp nhận không luôn trả về đúng k láng giềng gần nhất tuyệt đối, mà trả về một tập "gần đúng" — đổi lại tốc độ nhanh hơn hàng chục đến hàng nghìn lần. Ta đo mức "gần đúng" bằng recall.

Recall — thước đo độ chính xác của ANN

recall@k = tỉ lệ giữa số láng giềng đúng mà ANN tìm được, trên tổng k láng giềng đúng thật sự (do exact KNN xác định). Ví dụ k = 10, ANN trả về 10 kết quả nhưng chỉ 9 trong đó trùng với top-10 thật → recall@10 = 0.9.

Bản chất của ANN là một đường cong đánh đổi: đẩy recall lên cao thì latency tăng và ngược lại. Không có "đúng hoàn toàn và nhanh vô hạn". Việc của kỹ sư là chọn điểm vận hành phù hợp — với tra cứu tài liệu nội bộ ngân hàng, recall 0.95–0.98 ở latency vài mili-giây thường là điểm hợp lý.

Bức tranh tổng thể: các họ thuật toán ANN

Mọi thuật toán ANN đều xoay quanh một nguyên tắc: đừng so với tất cả — chỉ so với những ứng viên có khả năng. Cách chọn "ứng viên có khả năng" chia ANN thành mấy họ chính.

1. Cây / phân vùng không gian (tree / space-partitioning)

Ý tưởng: chia không gian thành các vùng bằng cây, rồi khi truy vấn chỉ đi xuống nhánh chứa vùng gần q.

• KD-tree: chia không gian bằng các siêu phẳng vuông góc trục toạ độ, mỗi tầng cắt theo một chiều. Rất tốt ở chiều thấp (d < 20), nhưng sụp đổ ở chiều cao vì "lời nguyền chiều" (curse of dimensionality) — ở d = 1024, hầu như phải duyệt gần hết cây, không còn nhanh hơn brute-force.
• Annoy (Approximate Nearest Neighbors Oh Yeah, Spotify): dựng nhiều cây ngẫu nhiên (random projection trees), mỗi cây chia không gian bằng siêu phẳng ngẫu nhiên. Truy vấn đi xuống nhiều cây, gộp các ứng viên, rồi tinh chỉnh. Nhiều cây → recall cao hơn nhưng tốn bộ nhớ. Ưu điểm lớn: index là file mmap read-only, chia sẻ giữa nhiều process rất tốt cho phục vụ tĩnh. Nhược điểm: xây lại toàn bộ khi thêm dữ liệu (không cập nhật tăng dần dễ dàng).

2. Hashing — LSH (Locality Sensitive Hashing)

Ý tưởng ngược với hash thông thường: cố tình để các vector gần nhau va chạm vào cùng một bucket. Ta thiết kế họ hàm băm sao cho xác suất hai vector rơi cùng bucket tỉ lệ thuận với độ gần của chúng (ví dụ dùng random hyperplane cho cosine). Truy vấn: băm q, chỉ xét các vector cùng bucket.

• Ưu: lý thuyết đẹp, đảm bảo xác suất, dễ phân tán.
• Nhược: trong thực tế chiều cao, để đạt recall tốt cần rất nhiều bảng băm → ngốn bộ nhớ, và thường thua HNSW/IVF về đường cong recall–tốc độ. Ngày nay LSH ít được chọn cho tìm kiếm ngữ nghĩa quy mô lớn, nhưng vẫn hữu ích ở một số bài toán khử trùng lặp (near-duplicate detection).

3. Lượng tử hoá — PQ (Product Quantization)

Đây không hẳn là cấu trúc tìm kiếm mà là kỹ thuật nén vector để tiết kiệm bộ nhớ và tăng tốc tính khoảng cách. Ý tưởng:

1. Chia vector d chiều thành m đoạn con (subvector).
2. Với mỗi đoạn, học một codebook gồm 2^b centroid (thường b = 8 → 256 centroid/đoạn) bằng k-means.
3. Thay vì lưu số thực gốc, mỗi đoạn chỉ lưu chỉ số centroid gần nhất (1 byte nếu b = 8). Một vector 1024 chiều float32 (4096 byte) có thể nén xuống chỉ m byte (ví dụ m = 64 → 64 byte, gấp ~64 lần).

Khi truy vấn, khoảng cách giữa q và vector nén được xấp xỉ bằng cách tra bảng khoảng cách đã tính sẵn tới các centroid (Asymmetric Distance Computation) — rất nhanh. Đánh đổi: nén làm mất mát thông tin → recall giảm; bù lại nhét được kho khổng lồ vào RAM.

IVF-PQ kết hợp PQ với IVF (mục 4): vừa thu hẹp không gian tìm, vừa nén vector — công thức "kinh điển" của FAISS cho kho hàng trăm triệu đến hàng tỷ vector.

4. IVF — Inverted File (phân cụm rồi tìm cục bộ)

IVF mượn ý tưởng "inverted index" từ tìm kiếm văn bản. Quy trình:

1. Xây (build): chạy k-means trên toàn kho để tạo nlist cụm (centroid). Mỗi vector được gán về cụm gần nhất → tạo nlist danh sách đảo (mỗi cụm là một "posting list").
2. Truy vấn (query): so q với nlist centroid, chọn nprobe cụm gần nhất, và chỉ quét các vector trong nprobe cụm đó thay vì toàn kho.

Hai tham số then chốt:

• nlist (số cụm): thường đặt cỡ ~sqrt(N) tới 4·sqrt(N). nlist lớn → mỗi cụm nhỏ, quét nhanh, nhưng cần nprobe lớn hơn để không "lọt" láng giềng ở biên cụm.
• nprobe (số cụm xét khi truy vấn): núm chỉnh recall–tốc độ chính. nprobe = 1 nhanh nhất nhưng dễ miss (láng giềng thật có thể nằm ở cụm kế bên); tăng nprobe → recall lên, latency lên. nprobe = nlist tương đương brute-force.

Điểm yếu cố hữu của IVF: hiệu ứng biên cụm — vector nằm sát ranh giới hai cụm có thể bị bỏ sót nếu không probe đủ cụm.

5. Đồ thị HNSW — kẻ thống trị hiện nay

HNSW (Hierarchical Navigable Small World) dựa trên đồ thị "thế giới nhỏ": mỗi vector là một đỉnh, nối với một số đỉnh láng giềng. Tìm kiếm = đi bộ tham lam (greedy walk) trên đồ thị — từ một đỉnh vào, liên tục nhảy sang láng giềng gần q hơn cho tới khi không cải thiện được nữa.

Chữ "Hierarchical" là mấu chốt: đồ thị được xếp thành nhiều tầng như bản đồ zoom.

• Tầng trên cùng: ít đỉnh, các cạnh "dài", dùng để nhảy nhanh trên toàn không gian (đi thô).
• Xuống dần các tầng dưới: nhiều đỉnh hơn, cạnh ngắn hơn, tinh chỉnh dần (đi mịn).
• Tìm kiếm bắt đầu ở tầng trên cùng, "trượt" xuống dần, mỗi tầng đưa ta tới vùng gần q hơn — giống tra từ điển: mở giữa sách trước, rồi thu hẹp dần.

Ba tham số HNSW cần nắm:

• M: số cạnh tối đa mỗi đỉnh (ở các tầng trên). M lớn → đồ thị dày, recall cao, tìm nhanh hơn nhưng tốn bộ nhớ (mỗi cạnh là một con trỏ) và build lâu hơn. Điển hình M = 16–48.
• ef_construction: kích thước "danh sách ứng viên động" khi xây đồ thị. Lớn → đồ thị chất lượng cao hơn (láng giềng được chọn tốt hơn), nhưng build chậm hơn. Điển hình 100–500.
• ef_search (còn gọi ef): kích thước danh sách ứng viên khi truy vấn. Đây là núm chỉnh recall–tốc độ chính của HNSW, tương tự nprobe của IVF. ef_search phải >= k; tăng nó → xét nhiều ứng viên hơn → recall lên, latency lên.

Vì sao HNSW phổ biến và mạnh nhất hiện nay: đường cong recall–QPS của nó thường tốt nhất trong các họ ANN, hỗ trợ thêm dữ liệu tăng dần (không phải rebuild toàn bộ như Annoy/IVF thuần), và có sẵn trong hầu hết engine (pgvector, FAISS, Qdrant, Milvus, Elasticsearch, Weaviate). Cái giá phải trả: ngốn RAM (đồ thị phải nằm trong bộ nhớ để đi nhanh) và build tốn thời gian. Kho rất lớn thường ghép HNSW với PQ (ví dụ Qdrant/Milvus) để giảm RAM.

Bảng đánh đổi giữa các họ

Không có "kẻ thắng tuyệt đối" — chọn theo ràng buộc: nếu RAM dư và cần recall/latency tốt → HNSW; nếu kho quá lớn không nhét đủ RAM → IVF-PQ; nếu chỉ phục vụ tĩnh, chia sẻ nhiều process → Annoy.

Tuning tham số: cân recall và tốc độ

Nguyên tắc chung: build một lần cho tốt, tune truy vấn để đạt điểm vận hành.

• Với HNSW: cố định M và ef_construction ở mức khá cao lúc build (vd M = 32, ef_construction = 200), rồi chỉ chỉnh ef_search lúc chạy. Bắt đầu ef_search = 64, đo recall và latency; tăng dần (100, 200...) tới khi recall đạt SLA mong muốn thì dừng — đừng tăng thừa vì latency lên tuyến tính.
• Với IVF: cố định nlist khi build (~sqrt(N)), chỉ chỉnh nprobe lúc chạy theo cùng logic. nprobe từ 1 tăng dần cho tới khi recall đủ.

Cách làm đúng chuẩn công nghiệp: dựng một tập ground-truth bằng exact KNN trên vài nghìn query mẫu, rồi quét lưới (grid) ef_search/nprobe, vẽ đường cong recall vs QPS (hoặc recall vs latency p95), và chọn điểm trên đường cong thoả SLA. Đây là cách benchmark chuẩn (ann-benchmarks.com dùng đúng phương pháp này).

# Minh hoạ (KHÔNG phải SQL chạy được) — quét ef_search để chọn điểm vận hành
for ef in [32, 64, 100, 200, 400]:
    set_hnsw_ef_search(ef)
    hits, total, latencies = 0, 0, []
    for q, truth_topk in ground_truth_queries:   # truth từ exact KNN
        t0 = now()
        result = ann_search(q, k=10)
        latencies.append(now() - t0)
        hits  += len(set(result) & set(truth_topk))
        total += len(truth_topk)
    print(ef, "recall@10=", hits/total, "p95_ms=", p95(latencies))
# chọn ef nhỏ nhất mà recall@10 >= 0.97

Metadata filtering kết hợp ANN

Trong thực tế hiếm khi tìm "toàn kho" — thường kèm điều kiện lọc: "chỉ tìm trong tài liệu thuộc phòng Tín dụng, phiên bản còn hiệu lực, ngôn ngữ tiếng Việt". Ghép filter với ANN có ba chiến lược, mỗi cái có bẫy riêng:

• Pre-filter (lọc trước): lọc theo metadata trước, rồi ANN trên tập con. Đúng ngữ nghĩa nhất, nhưng khó: index ANN (đồ thị HNSW/cụm IVF) được xây trên toàn bộ vector, không biết trước filter → nếu filter loại phần lớn dữ liệu, đồ thị có thể "đứt đường đi" tới vùng còn lại, recall tụt. Các engine hiện đại (Qdrant, Milvus, pgvector 0.8+) giải bằng filtered search — chèn điều kiện vào lúc duyệt đồ thị.
• Post-filter (lọc sau): ANN lấy top-N rồi mới bỏ những cái không thoả filter. Đơn giản nhưng nguy hiểm: nếu filter khắt khe, top-N có thể không còn đủ k kết quả sau lọc — phải "over-fetch" (lấy dư, vd N = 5·k) và vẫn có rủi ro thiếu.
• In-filter / filtered ANN: kiểm tra điều kiện ngay trong lúc duyệt đồ thị/cụm, chỉ nhận đỉnh thoả. Cân bằng tốt nhất và là hướng các vector DB đang hội tụ về.

Thách thức chung: filter chọn lọc quá cao (highly selective) là kịch bản khó nhất cho ANN — đôi khi lọc bằng chỉ mục B-tree rồi brute-force trên tập nhỏ còn nhanh và chính xác hơn. Nhiều engine tự động chuyển sang chiến lược này khi ước lượng số dòng sau filter đủ nhỏ.

Benchmark: đo cái gì?

Đánh giá một cấu hình ANN không chỉ nhìn tốc độ. Bộ chỉ số tối thiểu:

• recall@k: đo trên tập ground-truth (exact KNN). Không có nó thì "nhanh" vô nghĩa.
• QPS (queries per second) và latency p50/p95/p99: đo ở mức tải thật, có concurrency. p99 quan trọng cho trải nghiệm — một truy vấn chậm lâu lâu vẫn làm hỏng SLA.
• Thời gian build & RAM: chi phí vận hành. HNSW recall cao nhưng nếu vượt RAM thì phải cân nhắc IVF-PQ.
• Luôn báo cáo dưới dạng cặp (recall, QPS) — báo một mình QPS mà giấu recall là báo cáo vô giá trị.

Use case thực tế

Bối cảnh: Team dữ liệu NCB xây trợ lý tra cứu nội bộ trên kho quy trình, thông tư, hướng dẫn nghiệp vụ. Sau chunking có 5,2 triệu chunk, mỗi chunk là vector 1024 chiều (từ mô hình embedding ở Vector DB 2), lưu trong Postgres + pgvector (xem Vector DB 4 — pgvector). Yêu cầu: p95 latency < 20ms, recall@10 ≥ 0.97, kèm filter theo phòng ban và trạng thái hiệu lực.

Bước 1 — Vì sao không exact KNN: 5,2 triệu × 1024 chiều → mỗi query ~5,3 tỷ phép tính, đo được p95 ~180ms trên một core, sập ngay khi 20 người dùng đồng thời. Bắt buộc dùng ANN.

Bước 2 — Chọn HNSW: kho ~20 GB vector, server có 64 GB RAM → đồ thị HNSW nhét đủ. Chọn HNSW vì cần recall cao + latency thấp + thêm tài liệu mới hằng ngày (cập nhật tăng dần, không muốn rebuild).

Bước 3 — Build & tune: build với M = 32, ef_construction = 200 (build ~40 phút). Dựng ground-truth bằng exact KNN trên 3.000 query mẫu, quét ef_search:

→ Chọn ef_search = 80: recall 0,972 (đạt ngưỡng), p95 11ms (dưới SLA 20ms), còn dư ngân sách cho filter.

Bước 4 — Filter theo phòng ban: đa số query lọc theo 1 phòng (mỗi phòng ~5–10% kho — filter vừa phải). Dùng filtered search của pgvector 0.8; với query lọc rất khắt khe (một tài liệu cụ thể, <2.000 chunk), planner tự chuyển sang lọc B-tree rồi brute-force — nhanh hơn và recall = 1,0.

Kết quả: p95 giảm từ 180ms xuống 11ms (~16×), recall@10 = 0,972, phục vụ được 150+ QPS trên một node. Xem thêm vận hành ở Vector DB 8 — Production Ops và kết hợp lexical ở Vector DB 6 — Hybrid Search.

Ghi nhớ

• Exact KNN cho recall 1.0 nhưng O(N·d) — bất khả thi ở triệu–tỷ vector; ANN đổi recall lấy tốc độ.
• recall@k là thước đo bắt buộc; luôn báo cáo cặp (recall, QPS/latency), không bao giờ báo tốc độ một mình.
• Các họ ANN: cây/phân vùng (KD-tree, Annoy), hashing (LSH), lượng tử hoá (PQ/IVF-PQ — nén để tiết kiệm RAM), phân cụm (IVF — chỉnh nprobe), đồ thị (HNSW — chỉnh ef_search).
• HNSW là lựa chọn mặc định hiện nay: recall/latency tốt nhất, hỗ trợ cập nhật tăng dần; cái giá là ngốn RAM và build chậm.
• Tuning: cố định tham số build ở mức tốt (M, ef_construction / nlist), chỉ chỉnh tham số query (ef_search / nprobe) để đạt điểm vận hành theo SLA.
• Kho quá lớn không đủ RAM → dùng IVF-PQ hoặc HNSW+PQ để nén.
• Metadata filtering: pre-filter đúng nghĩa nhưng khó, post-filter đơn giản nhưng dễ thiếu kết quả, filtered ANN (in-filter) là hướng cân bằng nhất; filter cực khắt khe có khi brute-force lại tối ưu.