ParadeDB tăng tốc tìm kiếm văn bản: Cuộc đua với TIN của PlanetScale

Trong lĩnh vực cơ sở dữ liệu quan hệ, việc tìm kiếm toàn văn (full-text search) từ lâu vẫn là một bài toán đau đầu. Hai tuần sau khi PlanetScale ra mắt TIN — một extension tìm kiếm toàn văn cho Postgres — đội ngũ ParadeDB đã công bố loạt cải tiến hiệu năng đáng chú ý. Câu chuyện này không chỉ đơn thuần là cuộc đua tốc độ, mà còn là bài học về cách tối ưu hóa hệ thống tìm kiếm trong môi trường Postgres.


Bối cảnh: TIN nhanh hơn ParadeDB như thế nào?

Theo bài công bố của PlanetScale, TIN đạt hiệu năng nhanh hơn ít nhất 8 lần so với ParadeDB 0.25 trong mọi phép benchmark của họ, đặc biệt ở hai hạng mục: tìm kiếm xếp hạng theo BM25 và đếm tài liệu khớp (document count).

PlanetScale lý giải ưu thế này đến từ một khác biệt kiến trúc cơ bản: TIN dùng trực tiếp trường ctid nội bộ của Postgres làm định danh tài liệu, thay vì dùng DocId tuần tự như Tantivy (thư viện tìm kiếm đứng sau ParadeDB). Điều này giúp loại bỏ bảng ánh xạ DocId ↔ ctid, đồng thời tối ưu các thao tác bitmap và kiểm tra khả kiến (visibility check).

Nghe hợp lý — nhưng ParadeDB không đồng ý rằng đây là toàn bộ câu chuyện.

Hai tối ưu thực sự đóng góp phần lớn tốc độ

Sau khi nhận thấy TIN nhanh đến mức "chỉ còn biết im lặng và đội mũ tối ưu hóa lên", đội ngũ ParadeDB đã dành hai tuần để tìm ra nguyên nhân thực sự. Hóa ra, khoảng cách không nằm ở cách định danh tài liệu, mà ở hai điểm nghẽn khác.

Tối ưu 1: Giải quyết truy cập ngẫu nhiên khi tính điểm BM25

Trên tập dữ liệu Hacker News 28,7 triệu tài liệu, ParadeDB nhận ra 83% lượt truy cập trang Postgres đến từ một cấu trúc dữ liệu nhỏ bé: fieldnorms — mảng lưu độ dài tài liệu được lượng tử hóa thành một byte, dùng để chuẩn hóa điểm BM25.

Vấn đề nằm ở tính cục bộ (locality). Tantivy lưu fieldnorms tách biệt khỏi postings list, dưới dạng mảng đánh chỉ mục theo DocId. Khi đọc postings của một từ khóa thì tuần tự, nhưng khi truy xuất fieldnorm tương ứng thì bộ nhớ nhảy loạn xạ khắp mảng — dẫn đến khoảng 1.500 trang Postgres bị chạm cho một truy vấn đơn giản.

Giải pháp của ParadeDB rất trực diện: lưu mảng fieldnorm song song với từng postings list, theo đúng thứ tự DocId. Kết quả là số lượt truy cập fieldnorm giảm từ 1.500 trang xuống chỉ còn 30 trang — một mức giảm đáng kinh ngạc.

Đánh đổi là dung lượng lưu trữ tăng lên, vì fieldnorm của một tài liệu giờ được lặp lại cho mỗi từ khóa riêng biệt. Tuy nhiên, vì phần lớn từ khóa có postings list ngắn, mức tăng thực tế chỉ khoảng 9% trên chỉ mục HN 28,7 triệu tài liệu.

Tối ưu 2: Chọn đúng thuật toán Blockmax

Với các truy vấn disjunction (OR) chứa nhiều từ khóa, ParadeDB nhận thấy dù lượt đọc buffer giảm 80%, thời gian truy vấn chỉ giảm 5% — dấu hiệu của một nút thắt thuật toán, không phải I/O.

Hóa ra phần lớn thời gian bị tiêu tốn trong vòng lặp Blockmax WAND. Đây là thuật toán chuẩn mà các search engine dùng để bỏ qua (skip) các khối postings không thể lọt vào top K khi thực thi truy vấn OR.

Có hai họ thuật toán Blockmax:

• WAND: bỏ qua nhiều hơn nhưng tiêu tốn nhiều chu kỳ CPU hơn để quyết định skip.
• MAXSCORE: bỏ qua ít hơn nhưng chi phí thấp hơn.

Khi truy vấn chứa càng nhiều từ khóa, chi phí của WAND càng lớn và có thể vượt qua lợi ích mà nó mang lại. Tantivy dùng WAND, trong khi Lucene từ năm 2023 đã chọn động giữa WAND và MAXSCORE tùy hình dạng truy vấn.

ParadeDB đã triển khai một đường MAXSCORE với heuristic đơn giản: dùng MAXSCORE cho disjunction có từ ba từ khóa trở lên với postings đủ dày, và WAND cho các trường hợp còn lại. Với truy vấn 10 từ khóa, độ trễ p50 giảm khoảng 6 lần, p95 giảm 8 lần, và kết quả nhanh hơn TIN 2 lần trên tập HN 28,7 triệu tài liệu.

Hai điểm bất thường trong benchmark gốc

ParadeDB nhấn mạnh rằng họ không phủ nhận TIN nhanh. Tuy nhiên, họ chỉ ra hai điểm trong benchmark của PlanetScale vô tình tạo lợi thế cho TIN.

Thứ nhất, lỗi cú pháp ParadeDB. Các truy vấn ParadeDB trong benchmark dùng parser chuỗi dưới toán tử @@@ nhưng không chỉ định tên trường. Mặc định, ParadeDB sẽ tìm trên mọi trường văn bản được đánh chỉ mục — nghĩa là cả id và body trong tập StackExchange. Trong khi đó, TIN chỉ tìm trên một trường. Đây là sự bất công rõ ràng về khối lượng công việc.

Thứ hai, cách xử lý từ phổ biến. TIN sử dụng kỹ thuật gọi là dense-term elision: bỏ qua việc tính điểm cho bất kỳ từ khóa nào xuất hiện trong hơn 10% corpus (cấu hình qua tham số dense_ratio). Ý tưởng này khá thú vị — các từ phổ biến như "the", "is" có postings list khổng lồ nhưng trọng số BM25 rất thấp.

Tuy nhiên, cái giá phải trả là độ chính xác. Khi bật elision, TIN tính toán một xấp xỉ BM25, có thể trả về thứ tự kết quả khác với BM25 chính xác.

Khi ParadeDB phân tích các truy vấn trong benchmark StackExchange, họ phát hiện nhiều truy vấn chỉ gồm các từ phổ biến như "is it", "to a", "is to" — được sinh ra bằng cách lấy mẫu các đoạn từ liên tiếp trong corpus, không phải truy vấn tìm kiếm thực tế.

Trên những truy vấn này, TIN bỏ qua phần lớn công việc tính điểm trong khi ParadeDB vẫn tính điểm chính xác. Kết quả đo được:

• 47,8% truy vấn trả về ít nhất một kết quả trong Top 10 không nằm trong Top 10 "đúng".
• 6,4% truy vấn trả về kết quả mà không có kết quả nào trong Top 10 đúng — tức là sai hoàn toàn.
• Riêng disjunction: 88,2% truy vấn có ít nhất một kết quả ngoài Top 10 đúng lọt vào Top 10.

Đáng chú ý, khi bật stopwords (danh sách từ dừng), ParadeDB đạt 161,9 QPS — cao hơn cả TIN ở cấu hình dense_ratio=2 (35,5 QPS) và dense_ratio=0.1 (114,4 QPS).

Vậy ctid có thực sự vượt trội?

ParadeDB cho rằng lựa chọn giữa ctid và DocId cũng chỉ là một đánh đổi, không phải chân lý tuyệt đối. Không có gì nén tốt hơn các số nguyên dày, sắp xếp, duy nhất — và đó chính là lý do hầu hết hệ thống tìm kiếm dùng DocId u32.

Việc chuyển sang định danh 48-bit không mặc nhiên hiệu quả hơn, đặc biệt vì 48 bit trong ctid là phép ghép của hai miền số khác nhau: số block (đếm hàng triệu) và offset tuple (tối đa 291).

Hơn nữa, DocId u32 dày còn có một lợi thế quan trọng: dễ kết nối với lưu trữ dạng cột (columnar). Các truy vấn tìm kiếm như top K theo trường, lọc khoảng, faceting đều cần columnar format. Với DocId, tài liệu số 42 trong segment ánh xạ trực tiếp tới hàng 42 trong cột. Với ctid, bạn cần một bảng ánh xạ trước khi tra được giá trị cột.

TIN giỏi BM25 và đếm tài liệu, nhưng đó mới chỉ là phần nổi của tảng băng trong một search engine như Elasticsearch. Phần "còn lại của tìm kiếm" cần columnar representation.

Điều rút ra cho cộng đồng mã nguồn mở

Đội ngũ ParadeDB thừa nhận họ đã chủ quan trong việc tối ưu core engine sau khi đạt ngang bằng hiệu năng với Elasticsearch, và chuyển nguồn lực sang mở rộng tính năng (filter phức tạp, facets, joins). TIN đã giúp họ nhìn lại cơ hội cải thiện nền tảng.

Tất cả cải tiến lần này đều mã nguồn mở và đã được đẩy ngược lên thư viện Tantivy. Bản release candidate 0.26.0-rc.2 đã sẵn sàng, và bản stable 0.26.0 dự kiến ra mắt trong tuần tới. Người dùng hiện tại cần đánh chỉ mục lại (reindex) để hưởng trọn vẹn các tối ưu, dù các thay đổi vẫn tương thích ngược.

Câu chuyện giữa ParadeDB và TIN là một ví dụ đẹp về văn hóa cạnh tranh lành mạnh trong cộng đồng mã nguồn mở — nơi các đối thủ học hỏi lẫn nhau và cùng đẩy giới hạn hiệu năng lên cao hơn. Với người dùng Postgres tại Việt Nam đang cân nhắc giải pháp tìm kiếm toàn văn, đây là thời điểm tốt để theo dõi sát các bản phát hành sắp tới của cả hai dự án.