Chỉ mục GIN tìm từ hiếm nhanh gấp 754 lần — nhưng tìm từ phổ biến còn chậm hơn cả không có chỉ mục

Hãy nghĩ tới trang mục lục tra cứu ở cuối một cuốn sách dày. Muốn tìm mọi trang nhắc tới "ty thể", bạn lật tới mục lục, đọc dòng liệt kê số trang — xong trong vài giây, khỏi phải lật cả cuốn. Nhưng thử tra từ "của" xem: nó xuất hiện ở gần như mọi trang, nên dòng liệt kê của nó dài hơn cả việc đọc thẳng cuốn sách. Chỉ mục GIN cho tìm kiếm toàn văn chính là cái mục lục ấy, và toàn bộ chuyện hay–dở của nó nằm đúng ở chỗ này. LIKE '%từ khoá%' không dùng được chỉ mục B-tree, nên mọi tìm kiếm văn bản đều thành quét toàn bảng. GIN với tsvector là câu trả lời của PostgreSQL — nhưng nó không phải lúc nào cũng thắng, và với tiếng Việt có thêm vài chuyện phải xử lý.

Bảng thử: 500.000 bài viết tiếng Việt, 279 MB.

GIN thắng khi từ khoá hiếm, thua khi từ khoá phổ biến

Dòng giữa lại là bài học của phần 10 ở một hình dạng khác: khi kết quả chiếm một phần tư bảng, đi qua chỉ mục rồi nhảy về bảng đắt hơn đọc thẳng.

Dòng cuối cho thấy sức mạnh thật của GIN: nó giữ danh sách bài cho từng từ, nên tìm nhiều từ cùng lúc chỉ là giao hai danh sách. Từ hiếm thu hẹp kết quả ngay, và từ phổ biến đi kèm không làm chậm thêm.

Nhân tiện, ILIKE '%từ%' mất 332,53 ms — chậm gấp 4 lần LIKE vì phải đổi hoa thường cho từng dòng, và không chỉ mục B-tree nào giúp được.

PostgreSQL không có cấu hình tiếng Việt

SELECT to_tsvector('simple', 'Cơ sở dữ liệu quan hệ mã nguồn mở');

'cơ':1 'dữ':3 'hệ':6 'liệu':4 'mã':7 'mở':9 'nguồn':8 'quan':5 'sở':2

Chín từ, tách theo khoảng trắng. Trong danh sách 29 cấu hình có sẵn — english, french, russian, vietnamese — không có tiếng Việt. Và to_tsvector('english', ...) cho kết quả y hệt simple, vì thuật toán rút gọn từ của tiếng Anh không nhận ra từ tiếng Việt nào.

Hệ quả thực tế: "cơ sở" là hai từ riêng biệt, không phải một khái niệm. Muốn tìm đúng cụm phải dùng toán tử liền kề:

tv @@ to_tsquery('simple', 'cơ <-> sở')     -- hai tu dung canh nhau
tv @@ to_tsquery('simple', 'cơ & sở')       -- hai tu cung xuat hien trong bai

Với tiếng Việt, simple thật ra là lựa chọn đúng: nó không cắt gọt gì, chỉ chuyển về chữ thường và tách theo khoảng trắng. Đừng dùng english chỉ vì nó nghe "đầy đủ hơn" — nó không làm gì thêm mà còn loại bỏ những từ nằm trong danh sách từ dừng của tiếng Anh.

Tìm không dấu: bài toán riêng của tiếng Việt

Người dùng gõ co so du lieu, dữ liệu là Cơ sở dữ liệu:

tim 'co & so' -> 0 ket qua

Không có gì bất ngờ, nhưng nó là yêu cầu gần như bắt buộc với mọi ứng dụng tiếng Việt.

Extension unaccent giải quyết phần chuyển đổi:

CREATE EXTENSION unaccent;
SELECT unaccent('Cơ sở dữ liệu');   -- Co so du lieu

Nhưng đánh chỉ mục lên nó thì không được:

CREATE INDEX ON bv USING gin (to_tsvector('simple', unaccent(noi_dung)));

ERROR:  functions in index expression must be marked IMMUTABLE

Đúng cái bẫy phần 14 đã đo: unaccent là STABLE, vì nó đọc từ điển chuyển đổi có thể thay đổi. Kiểm tra: provolatile = 's'.

Cách vá chuẩn là bọc nó trong một hàm bạn tự khai là IMMUTABLE, chỉ định rõ từ điển:

CREATE OR REPLACE FUNCTION bo_dau(text) RETURNS text AS
$$ SELECT unaccent('unaccent', $1) $$
LANGUAGE sql IMMUTABLE STRICT PARALLEL SAFE;

CREATE INDEX ix_ua ON bv USING gin (to_tsvector('simple', bo_dau(noi_dung)));

Đo được: chỉ mục 38 MB, dựng mất 13,7 s, và tìm không dấu chỉ còn 0,12 ms.

Lưu ý điều bạn đang hứa khi khai IMMUTABLE: nếu ai đó sửa từ điển unaccent sau này, chỉ mục sẽ sai và PostgreSQL không phát hiện được. Trong thực tế từ điển đó gần như không bao giờ đổi, nên đây là đánh đổi mọi người chấp nhận — nhưng nên biết mình đang chấp nhận cái gì.

GIN so với GiST cho văn bản

Với tsvector, GIN nhỏ hơn và dựng nhanh hơn. GiST lưu dạng có mất mát nên phải kiểm lại kết quả ở bảng, còn GIN lưu chính xác.

Đổi lại GIN cập nhật chậm hơn — mỗi lần sửa văn bản là sửa danh sách của mọi từ trong đó. PostgreSQL có fastupdate để gom các thay đổi lại, bật sẵn theo mặc định.

Quy tắc: tìm kiếm toàn văn thì dùng GIN. GiST hợp với dữ liệu hình học và khoảng — phần 17.

Dựng cột tsvector thế nào

Cách gọn nhất là cột sinh, giống phần 14:

ALTER TABLE bv ADD COLUMN tv tsvector
  GENERATED ALWAYS AS (to_tsvector('simple', tieu_de || ' ' || noi_dung)) STORED;
CREATE INDEX ON bv USING gin (tv);

Trên 500.000 dòng, thêm cột mất 12,6 s và dựng chỉ mục mất 3,2 s.

Muốn tiêu đề có trọng số cao hơn nội dung thì dùng setweight:

setweight(to_tsvector('simple', tieu_de), 'A') ||
setweight(to_tsvector('simple', noi_dung), 'B')

Rồi xếp hạng bằng ts_rank. Với ứng dụng tiếng Việt thật, bạn thường cần hai chỉ mục — một có dấu để tìm chính xác, một không dấu để tìm khoan dung — và truy vấn OR cả hai.

Khi nào đừng dùng tìm kiếm toàn văn

• Từ khoá phổ biến trong dữ liệu nhỏ. Phép đo ở trên cho thấy quét bảng có thể nhanh hơn.
• Tìm theo tiền tố ngắn. LIKE 'tien to%' dùng được B-tree bình thường, rẻ hơn nhiều.
• Cần tìm gần đúng, sai chính tả. Đó là việc của pg_trgm, không phải tsvector.
• Yêu cầu xếp hạng phức tạp, gợi ý, đồng nghĩa. Đến ngưỡng đó thì Elasticsearch hay Meilisearch phù hợp hơn — và với tiếng Việt chúng có bộ tách từ thật, thứ PostgreSQL không có.

Mẫu số chung

Cái mục lục cuối sách ở đầu bài chính là chỉ mục ngược (inverted index): một ánh xạ từ mỗi từ sang danh sách tài liệu chứa nó. Đây là cấu trúc nền của mọi cỗ máy tìm kiếm trên đời, và toàn bộ kinh tế học của nó gói trong một chữ: độ chọn lọc của từ. Từ hiếm có danh sách ngắn nên tra tức thì; từ phổ biến có danh sách gần bằng cả kho, và khi ấy đọc danh sách rồi nhảy về từng tài liệu còn đắt hơn quét thẳng — đúng dòng "GIN chậm hơn LIKE" ở bảng trên.

Chính vì kinh tế học đó mà mọi hệ tìm kiếm hội tụ về cùng ba mẹo:

• Lucene / Elasticsearch lưu đúng các posting list như vậy, và lý do chúng loại bỏ stop-word ("the", "và", "của") không phải vì những từ đó vô nghĩa, mà vì posting list của một từ có mặt ở mọi tài liệu thì vô dụng để lọc. Cùng lý do, chúng cân trọng số bằng idf (BM25, tf-idf) để dìm các từ phổ biến xuống.
• Khi giao nhiều từ, chiến lược kinh điển là bắt đầu từ từ hiếm nhất — danh sách ngắn nhất — rồi mới lọc dần bằng các từ phổ biến. Đó đúng là dòng "hai từ, một hiếm một phổ biến: 0,09 ms".
• Tự dựng bằng tay trong Java thì đây là một Map<String, List<DocId>>, và bạn vấp đúng cùng vấn đề: khoá phổ biến trỏ tới một danh sách khổng lồ.

Nên câu hỏi đúng khi thiết kế tìm kiếm không phải "chỉ mục này nhanh cỡ nào" mà là "từ khoá người dùng gõ có đủ chọn lọc không" — và hệ quả thực dụng là hãy thiết kế giao diện sao cho câu tìm luôn có ít nhất một từ hiếm. Muốn biết từ nào trong dữ liệu của bạn quá phổ biến để lọc, soát nhanh:

SELECT to_tsvector('simple', 'câu văn tiếng Việt của bạn');

SELECT word, ndoc, nentry
FROM ts_stat('SELECT tv FROM bang_cua_ban')
ORDER BY ndoc DESC
LIMIT 20;

Từ nào có ndoc gần bằng tổng số dòng thì GIN sẽ không giúp được gì khi tìm nó một mình — đó chính là các "stop-word" của riêng dữ liệu bạn.

Phần sau đo GiST và BRIN: hai kiểu chỉ mục cho dữ liệu theo khoảng và theo thời gian.