Anatomy of a (Postgres) search engine

PlanetScale · 2026 · 2. Tăng trưởng · Độ khó: Trung bình — bài gốc

Bài giải thích khái niệm của nhà cung cấp, đi kèm ra mắt extension full-text search TIN cho Postgres (chi tiết TIN ở bài khác). Giá trị ở phần cuối: nhúng inverted index vào một DB giao dịch thì phải giải những gì.

Bối cảnh

• B-tree sắp toàn bộ giá trị cột nên tìm được theo giá trị, khoảng, tiền tố, nhưng vô dụng với chuỗi ở giữa; LIKE '%x%' quét mọi dòng. Công cụ đúng là inverted index.

Thay đổi chính (khái niệm)

• Thành phần: term dictionary (thường là cây sắp theo thứ tự từ, wildcard/fuzzy phải quét một phần) → postings list (danh sách ID tài liệu đã sắp và nén: delta encoding khi dày, bitmap khi khoảng nửa tài liệu chứa từ đó; hợp/giao danh sách đã sắp là một lượt O(n), bitmap thì dùng lệnh vector). Dữ liệu vị trí (cho phrase/span query) để riêng vì ít truy vấn cần; dữ liệu tần suất cho chấm điểm BM25. Kích thước index khoảng 20% corpus nếu không có vị trí/điểm, tới khoảng 300% cho index tìm code.
• Tokenizer, stemming, stop word: stop word làm index nhỏ hơn nhưng mất độ chính xác (bỏ cả "the" lẫn "who" thì không tìm được The Who).
• Top-k: postings chia khối có thống kê; truy vấn lấy k kết quả điểm cao nhất có thể bỏ qua cả khối không thể vượt k kết quả đã có.
• Segment, merge, tombstone: index lớn hơn bộ nhớ được ghi thành nhiều segment bất biến; tài liệu mới vào segment khả biến (kém hiệu quả hơn) rồi được "seal". Quá nhiều segment thì phải merge: một lượt tuyến tính nhưng đọc/ghi hàng chục GB và tạm chiếm thêm chừng đó đĩa. Xoá là tombstone (vẫn trả về rồi lọc), chỉ thật sự mất khi merge; update = xoá + chèn.
• Nhúng vào Postgres phải giải: index là một relation có WAL để replication và backup bao gồm nó; trang giải phóng giữa relation không trả cho OS nên phải tự giữ danh sách trang trống; merge không được chạy trong INSERT/UPDATE/DELETE nên cần hàng đợi việc và worker nền; VACUUM phải xoá entry trỏ tới dòng chết, VACUUM FULL đổi ctid nên index phải cập nhật; chèn/xoá phải gắn transaction để chỉ hiện khi commit, mà top-k vẫn phải trả đủ k dòng thấy được; planner phải biết khi nào dùng full-text index, b-tree, hay giao bitmap của cả hai, và lọc nhiều cột full-text bằng CustomScan.

Vì sao

• Một index tìm kiếm bên trong DB giao dịch gánh mọi đòi hỏi của DB (WAL, MVCC, VACUUM, planner) cộng chi phí bảo trì của segment/merge; đó là cái giá để khỏi phải giữ một hệ search riêng đồng bộ với DB (Hạ tầng tìm kiếm).

Bài học cho SWE

• Đừng dùng LIKE '%…%' trên bảng lớn; cần inverted index.
• Index tìm kiếm có chi phí nền (merge, tombstone) phải lập lịch ngoài đường ghi.
• Hiểu cách index lưu xoá (tombstone) để dự đoán dung lượng khi dữ liệu thay đổi nhiều.

Liên quan

• Upstash 2026 (search nhúng vào Redis bằng Tantivy) · LinkedIn 2014 · GitLab 2019 · Tiger Data 2026
• Hạ tầng tìm kiếm