3.6 Prefix, wildcard và substring

Ba nhu cầu trông giống nhau nhưng cần ba cấu trúc dữ liệu khác nhau. Lẫn chúng là nguyên nhân phổ biến nhất của truy vấn tìm kiếm chậm.

Nhu cầu	Ví dụ	Cấu trúc đúng
Prefix — khớp đầu chuỗi	`mật kh*` (gõ dở, typeahead)	trie / FST / sorted dictionary
Suffix — khớp cuối chuỗi	`*khẩu`	index chuỗi đảo ngược
Wildcard giữa	`m*khẩu`	permuterm hoặc k-gram index
Substring bất kỳ	`%at kha%` (`LIKE`)	k-gram (trigram) index

Prefix: dictionary đã sắp thứ tự là đủ

Term dictionary được sắp theo thứ tự từ điển, nên mật kh* = một phép tìm nhị phân tới vị trí đầu, rồi đọc tuần tự đến khi hết tiền tố. Không cần cấu trúc mới. Trie/FST làm việc này nhanh hơn nữa và còn nén được (xem 3.3).

Đây là lý do prefix search rẻ, còn *khẩu (dấu sao đứng trước) đắt: nó buộc quét toàn bộ dictionary. Trong Elasticsearch, wildcard query mở đầu bằng * là một trong những cách chắc chắn nhất để làm sập cluster.

Suffix: chỉ cần đảo chuỗi

Index thêm mỗi term ở dạng đảo ngược:

"khẩu"  ->  "uảhk"
truy vấn "*khẩu"  ->  đảo thành "uảhk*"  ->  thành bài toán prefix

Hai dictionary, hai lần bộ nhớ cho phần dictionary (phần nhỏ), và *khẩu trở nên rẻ như khẩu*.

Permuterm index: xử lý dấu sao ở giữa

Thêm ký tự đánh dấu hết chuỗi $, rồi index mọi phép quay của term:

term "khau$"  ->  khau$ , hau$k , au$kh , u$kha , $khau

Truy vấn k*u → viết lại thành u$k* → lại là bài toán prefix. Mọi wildcard đơn đều quy về prefix bằng một phép quay.

Giá: dictionary phình ~ (độ dài term + 1) lần. Với term trung bình 8 ký tự là ~9× phần dictionary. Chấp nhận được nếu dictionary nhỏ so với postings, thường đúng.

k-gram index: bài toán substring tổng quát

Cắt term thành các đoạn k ký tự và index k-gram → term:

"khau"  (k=3, có đệm)  ->  "  k", " kh", "kha", "hau", "au "

Truy vấn *hau* → tra trigram hau → được danh sách term ứng viên → phải lọc lại (post-filter) vì k-gram chỉ là điều kiện cần:

*ba*na*  ->  trigram "ba" AND "na"  ->  ứng viên gồm cả "banana" và "nabab"
                                        ^ lọc lại bằng khớp chuỗi thật

Bước lọc lại là bắt buộc, không phải tối ưu. Bỏ nó là sinh kết quả sai.

Cấu trúc này còn là nền của fuzzy search bằng n-gram — cùng một index, dùng cho hai việc.

Ánh xạ sang công cụ thật

Nhu cầu	Postgres	Elasticsearch / OpenSearch
Prefix / typeahead	`text_pattern_ops` btree, hoặc `LIKE 'x%'`	`edge_ngram` analyzer (dựng sẵn, nhanh nhất) hoặc `match_phrase_prefix`
Substring `%x%`	GIN + `pg_trgm`	`wildcard` field type
Wildcard giữa	`pg_trgm`	`wildcard` query — chỉ trên field nhỏ
Suffix	index trên `reverse(col)`	`reverse` token filter

Quy tắc: prefix thì miễn phí, substring thì phải trả bằng một index riêng, và * đứng đầu mà không có index riêng là quét toàn bảng.

Phần 3 — Nền tảng kỹ thuật