Trigram Index (pg_trgm) - Chỉ PostgreSQL

Giải pháp duy nhất (built-in) cho leading wildcard LIKE '%abc%' - hạn chế cơ bản của B+ tree.

-- Bật extension (có sẵn, chỉ cần kích hoạt)
CREATE EXTENSION IF NOT EXISTS pg_trgm;
 
-- Tạo trigram index
CREATE INDEX trgm_idx ON contacts USING GIN (name gin_trgm_ops);
 
-- Giờ query này dùng được index:
SELECT * FROM contacts WHERE name LIKE '%Nguyễn%';

Cách hoạt động

Text được chia thành mọi chuỗi con 3 ký tự (trigram), mỗi trigram được đánh index riêng (kiểu inverted index như GIN):

'Nguyễn Văn Minh' → trigrams: 'ngu', 'guy', 'uyễ', 'yễn', 'ễn ',
                              'n v', ' vă', 'văn', ..., 'min', 'inh'
 
Khi tìm '%Minh%':
1. Tách chuỗi tìm kiếm thành trigram: 'min', 'inh'
2. Tìm các entry chứa TẤT CẢ trigram này → danh sách ứng viên
3. Kiểm tra lại pattern chính xác trên ứng viên (trigram có thể khớp sai thứ tự)

Ưu / Nhược

• ✅ Hỗ trợ ký tự đại diện ở bất kỳ vị trí nào
• ❌ Index có thể rất lớn (mỗi chuỗi sinh nhiều trigram, tăng nhanh theo độ dài)
• ❌ Chuỗi tìm kiếm phải có ít nhất 3 ký tự liên tục (không tính wildcard) để hoạt động hiệu quả

Lưu ý: Trigram index chỉ có trên PostgreSQL. MySQL, SQL Server không có tính năng tương đương tích hợp sẵn - cần tìm kiếm toàn văn phức tạp thì dùng công cụ chuyên biệt (Elasticsearch, MeiliSearch…).

Liên quan

• LIKE và Wildcard - vấn đề mà trigram giải quyết
• JSON Indexing và GIN Index - GIN index dùng chung cơ chế inverted