Bài 8: Lọc Metadata (Metadata Filtering) & Thuật Toán Single-stage vs Two-stage

Trong các hệ thống ứng dụng thực tiễn, việc chỉ tìm kiếm sự tương đồng ngữ nghĩa bằng vector là không đủ. Ví dụ: Người dùng muốn tìm kiếm các sản phẩm quần áo tương đồng với ảnh chụp, nhưng chỉ lọc các sản phẩm còn hàng (status = "in_stock") và có giá nhỏ hơn 500k (price < 500000).

Để xử lý bài toán so khớp kết hợp này, Vector DB phải hỗ trợ cơ chế Lọc siêu dữ liệu (Metadata Filtering). Bài học này sẽ đưa bạn đi sâu phân tích 3 giải thuật lọc kinh điển: Lọc trước (Pre-filtering), Lọc sau (Post-filtering) và Lọc lai đồng thời (Single-stage Hybrid Filtering) bằng bitset.

8.1 Nhu cầu lọc dữ liệu kết hợp trong thực tế

Trong cơ sở dữ liệu Vector lưu trữ theo mô hình Hybrid, mỗi bản ghi bao gồm 2 thành phần: Véc-tơ biểu diễn ngữ nghĩa và tài liệu JSON đính kèm (Metadata). Câu truy vấn tìm kiếm lúc này không chỉ chứa vector truy vấn $\mathbf{q}$ mà còn chứa thêm một câu điều kiện logic (như WHERE category = 'laptops').

Việc kết hợp hai tiến trình quét này đòi hỏi các giải thuật thiết kế tinh tế để không làm giảm sụt hiệu năng và độ bao phủ tìm kiếm.

8.2 Thuật toán Lọc sau (Post-filtering / Two-stage)

Lọc sau (Post-filtering) là chiến lược đơn giản nhất. Tiến trình tìm kiếm được chia làm 2 giai đoạn độc lập:

1. Giai đoạn 1: Sử dụng chỉ mục vector (như HNSW hoặc IVF) để tìm ra Top $K'$ vector gần nhất (với $K' > K$, ví dụ $K' = 100$).
2. Giai đoạn 2: Quét qua 100 kết quả này và loại bỏ tất cả các bản ghi không thỏa mãn bộ lọc metadata (ví dụ: loại bỏ các sản phẩm hết hàng), chỉ giữ lại Top $K$ bản ghi cuối cùng.

function postFilter(query, limit, filterFn) {
  // 1. Tìm kiếm KNN thô lấy 100 ứng viên gần nhất
  const candidates = vectorIndex.search(query, 100); 
  
  // 2. Lọc lại bằng điều kiện metadata
  const filtered = candidates.filter(c => filterFn(c.metadata));
  
  return filtered.slice(0, limit);
}

8.3 Thuật toán Lọc trước (Pre-filtering / Two-stage)

Để khắc phục lỗi thiếu hụt kết quả của lọc sau, chúng ta có giải thuật ngược lại là Lọc trước (Pre-filtering):

1. Giai đoạn 1: Quét cơ sở dữ liệu metadata bằng các chỉ mục truyền thống (B-Tree hoặc Hash Index) để lọc ra danh sách tất cả các Vector ID thỏa mãn điều kiện logic.
2. Giai đoạn 2: Chạy thuật toán tìm kiếm vector lân cận gần nhất chỉ trên tập hợp ID này.

function preFilter(query, limit, filterFn) {
  // 1. Quét lọc metadata trước để lấy tập hợp ID hợp lệ
  const validIds = metadataDb.query(filterFn); // Trả về tập Set
  
  // 2. Chỉ tính toán khoảng cách vector trên các ID này
  const results = [];
  for (const id of validIds) {
    const vec = getVector(id);
    const dist = calculateDistance(query, vec);
    results.push({ id, dist });
  }
  return results.sort((a, b) => a.dist - b.dist).slice(0, limit);
}

8.4 Lọc đồng thời (Single-stage Hybrid Filtering)

Giải pháp tối ưu và triệt để nhất hiện nay là Lọc đồng thời (Single-stage Hybrid Filtering).

Trong giải thuật này, chúng ta vẫn duyệt qua đồ thị HNSW bình thường để tận dụng cấu trúc liên kết liền mạch của nó. Tuy nhiên, tại mỗi bước duyệt qua các láng giềng của một node:

1. Chúng ta kiểm tra điều kiện bộ lọc metadata ngay lập tức.
2. Nếu node láng giềng thỏa mãn bộ lọc, nó sẽ được đưa vào hàng đợi kết quả so khớp.
3. Nếu không thỏa mãn bộ lọc, nó vẫn đóng vai trò là "node trung chuyển" để thuật toán tiếp tục nhảy qua duyệt các láng giềng tiếp theo (không làm đứt gãy đường đi của đồ thị).

Để tối ưu hóa bước kiểm tra điều kiện này ở tốc độ cấp độ bit, các Vector DB sử dụng cấu trúc mảng bit Bitset (hoặc Roaring Bitmap). Mỗi điều kiện lọc được biểu diễn bằng một dãy bit nhị phân liên tục, cho phép CPU kiểm tra tính hợp lệ của bản ghi bằng phép toán logic bitwise AND siêu nhanh.

// Mô phỏng lọc đồng thời bằng Bitset
class BitsetFilter {
  constructor(size) {
    this.words = new Uint32Array(Math.ceil(size / 32));
  }
  
  set(idx) {
    this.words[idx >> 5] |= (1 << (idx & 31));
  }
  
  get(idx) {
    return (this.words[idx >> 5] & (1 << (idx & 31))) !== 0;
  }
}

// Kiểm tra nhanh điều kiện lọc trong O(1) khi duyệt node
const isAllowed = bitset.get(currentNodeIdx);
if (isAllowed) {
  addToDistanceCalculation(currentNode);
}

Bảng đối chiếu hiệu năng các giải thuật lọc dữ liệu:

8.5 Thực hành: Pre-filtering vs Post-filtering

Demo dưới đây dựng 60 điểm dữ liệu 2D, trong đó Category B chỉ chiếm ~10% (6 điểm) và nằm rải rác khắp không gian — mô phỏng đúng tình huống "bộ lọc hẹp" đã nói ở trên. Với 1 điểm truy vấn cố định, hãy bật bộ lọc "Chỉ lọc Category B" và so sánh 2 chiến lược để thấy tận mắt hiện tượng thiếu hụt kết quả (recall collapse) của Post-filtering so với Pre-filtering:

import { euclideanDistance } from './vdb-engine.js';

// Sinh 60 diem 2D bang PRNG co seed co dinh (tai lap duoc) - Category B
// chi chiem ~10% (6 diem) va nam rai rac, KHONG nam trong top-K gan nhat
// theo khoang cach tho - dung mo phong "bo loc hep" gay recall collapse
function mulberry32(seed) {
  return function () {
    seed |= 0;
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const SEED = 6;
const N = 60;
const B_COUNT = Math.round(N * 0.1); // 6 diem Category B
const rand = mulberry32(SEED);

const points = [];
for (let i = 0; i < N; i++) {
  const x = 30 + rand() * (640 - 60);
  const y = 30 + rand() * (320 - 60);
  points.push({ id: i, vector: [x, y], category: i < B_COUNT ? 'B' : 'A' });
}

const query = [320, 160];
const K = 3; // so ket qua nguoi dung can
const K_PRIME = 5; // Post-filtering: quet rong hon K truoc khi loc

// Sap xep toan bo diem theo khoang cach that (dung euclideanDistance cua VDBJS)
const byDistance = points
  .map((p) => ({ ...p, distance: euclideanDistance(query, p.vector) }))
  .sort((a, b) => a.distance - b.distance);

// Khong loc: don gian lay Top K gan nhat, bat ke category
function noFilter() {
  return { candidates: byDistance.slice(0, K), results: byDistance.slice(0, K) };
}

// Post-filtering: tim Top K' gan nhat THO truoc, roi moi loai bo cac ban ghi
// khong thoa man Category B - neu bo loc hep, top K' co the KHONG chua diem
// B nao => recall collapse (thieu hut ket qua nghiem trong)
function postFilter() {
  const candidates = byDistance.slice(0, K_PRIME);
  const results = candidates.filter((p) => p.category === 'B').slice(0, K);
  return { candidates, results };
}

// Pre-filtering: loc metadata TRUOC de rut gon tap ung vien chi con Category B,
// roi moi xep hang lai theo khoang cach TRONG tap do - luon dung, khong bi
// thieu hut, du diem B that su nam ngoai top-K' tho ban dau
function preFilter() {
  const candidates = byDistance.filter((p) => p.category === 'B');
  const results = candidates.slice(0, K);
  return { candidates, results };
}