Check 100 candidates, not 10 million documents: Faster kNN filters in Elasticsearch

Elastic · 2026 · 3. Quy mô lớn · Độ khó: Khó — bài gốc

Bài nhà cung cấp về một tính năng của chính họ; benchmark do Elastic tự chạy. Mọi nhận định ghi "theo Elastic".

Bối cảnh

• Elasticsearch có hai cấu trúc ANN cho dense_vector: HNSW (đồ thị lân cận, đi từ hàng xóm sang hàng xóm, giữ beam num_candidates) và IVF (bbq_disk, gom vector quanh centroid, quét posting list gần nhất). Cả hai đều nằm theo từng segment Lucene: mỗi segment một đồ thị/một bộ posting list, query tìm từng segment rồi gộp.
• Filter đặt trong mệnh đề knn là pre-filter: kết quả là k láng giềng gần nhất trong số tài liệu khớp filter. Vì cả HNSW lẫn IVF đều không duyệt theo thứ tự doc ID, filter phải được chạy hết trên cả segment và ghi thành bitset trước khi tìm. Chi phí này tỉ lệ với kích thước segment và độ đắt của filter, không với phần segment được duyệt.
• Phần tìm thêm do filter loại tài liệu thì có trần (HNSW dừng đi đồ thị khi đã thăm bằng số tài liệu khớp, rồi chấm trực tiếp). Trường hợp tệ là filter rộng và đắt: trên segment 1 triệu vector, match_phrase khớp 90% tốn 33,4 ms để dựng bitset trong khi tìm vector chỉ 5,2 ms, số phép tính vector chỉ tăng 13%. Trên segment 10 triệu, query HNSW từ 2,3 ms lên 395 ms. Filter term cùng độ khớp chỉ tốn khoảng 0,3 ms.
• Post-filter thủ công (filter ngoài knn) thì nhanh nhưng có thể trả ít hơn k kết quả; người dùng phải tự đoán hệ số lấy dư.

Thay đổi chính

• Engine tự chọn theo từng query, từng shard, giữ nguyên ngữ nghĩa pre-filter:
  1. Ước tính độ chọn lọc: cộng ScorerSupplier#cost() của filter qua các segment (với term là độ dài posting list, đọc từ metadata, không phải dựng gì) chia cho số vector đã index của trường. Rẻ nhưng thô: là cận trên với phép AND; và là tính chất toàn cục của shard, trong khi điều quan trọng là tỉ lệ qua filter quanh vector query (filter language: en với query tiếng Tây Ban Nha).
  2. Chỉ thử post-filter khi độ chọn lọc ≥ 0,7 (ngưỡng mặc định, chỉnh theo index).
  3. Định cỡ số ứng viên bằng mô hình nhị thức: m = (k + Z·sqrt(k(1−p)/p)) / p với Z = 2,5 (thành công khoảng 99,4%), sàn 1,2×k, trần 10.000. Với k = 10: p = 0,9 cần 15 ứng viên, p = 0,55 cần 32. num_candidates của HNSW giữ nguyên (là độ rộng beam, núm vặn độc lập); của IVF thì nhân theo tỉ lệ để không âm thầm giảm mức thăm.
  4. Tìm không filter, rồi chỉ kiểm filter trên ứng viên (tuần tự theo doc ID), không dựng bitset, nên filter cũng không cần cache để nhanh.
  5. Thiếu thì thử lại đúng một lần: loại mọi tài liệu đã thấy, HNSW bắt đầu từ tối đa 4 ứng viên khớp gần nhất mỗi segment, xin thêm theo phần thiếu. Nếu số qua filter dưới một nửa kỳ vọng thì coi là filter tương quan với vùng query, thoát sớm.
  6. Lưới an toàn: vẫn thiếu thì bỏ kết quả và chạy pre-filter gốc. Ước tính sai chỉ tốn latency, không bao giờ trả thiếu hay sai kết quả. Rescore chính xác của vector lượng tử hoá dời ra sau bước lọc để kết quả post-filter và fallback cùng thang điểm.
• Benchmark (theo Elastic): 5 tập dữ liệu (523K tới 10M vector), HNSW và IVF, một và nhiều segment, 5 loại filter, 7 độ chọn lọc, ép chạy cả hai chiến lược. Trên tập 10M: post-filter nhanh hơn ở 104/120 cặp, 2 hoà; 14 cặp thua đều là filter term/range rẻ trên nhiều segment, chậm nhất 1,33 lần. Recall chênh không quá 0,01 ở mọi cặp. Latency post-filter gần như không đổi theo độ chọn lọc (khoảng 10% so với khoảng 50% của pre-filter).
• Giới hạn họ tự nêu: filter trong benchmark gần như độc lập với vector (chưa đo filter tương quan mạnh); nhiều segment làm lợi thế nhỏ đi. Hướng tiếp: ước tính tốt hơn bằng thống kê trường hoặc lấy mẫu, phát hiện tương quan trước, chọn theo chi phí của loại filter chứ không chỉ độ chọn lọc, quyết định theo từng segment.

Vì sao

• Theo Elastic, sau khi phép so khoảng cách đã được tối ưu (lượng tử hoá, SIMD), nút thắt của query vector có filter chuyển sang việc dựng filter; cải tiến đáng giá là nhận ra filter không cần chạy trên 10 triệu tài liệu để trả lời câu hỏi về 10.

Bài học cho SWE

• Đây là một query planner thu nhỏ: ước tính độ chọn lọc từ thống kê rẻ, chọn kế hoạch, và có đường lùi đúng đắn khi ước tính sai.
• Đặt ngưỡng xác suất (trung bình + Z·độ lệch) thay vì trung bình khi cần "đủ k với xác suất cao".
• Khi tối ưu thứ đắt nhất, nút thắt dời sang chỗ trước đây không ai đo.

Liên quan

• Qdrant 2026 (cùng bài toán, sửa ở đồ thị) · Cockroach Labs 2025 (filter ngoài cột tiền tố chưa dùng được index) · Render 2024
• Vector search và index ANN · Query planner và hiệu năng truy vấn · Hạ tầng tìm kiếm