Trigram Index là gì?

Trigram Index là một loại chỉ mục (index) trong cơ sở dữ liệu được thiết kế chuyên biệt để tăng tốc độ tìm kiếm chuỗi văn bản, đặc biệt là cho các truy vấn so khớp mẫu như LIKE, ILIKE, biểu thức chính quy (Regex) và tìm kiếm chuỗi gần đúng (Fuzzy Search). Kỹ thuật này phổ biến nhất trong hệ quản trị cơ sở dữ liệu PostgreSQL thông qua module mở rộng pg_trgm.

1. Trigram (3-gram) Là Gì?

Trigram là một nhóm bao gồm 3 ký tự liên tiếp được trích xuất ra từ một chuỗi văn bản lớn hơn.

Khi phân tích một từ để đưa vào index, hệ thống thường thêm hai khoảng trắng ở đầu và một khoảng trắng ở cuối từ để giúp nhận diện chính xác phần bắt đầu và kết thúc của từ đó.

Ví dụ: Từ "cat" sẽ được chia thành 4 trigram sau:

• " c" (hai khoảng trắng + c)
• " ca" (một khoảng trắng + ca)
• "cat"
• "at " (at + một khoảng trắng)

2. Cơ Chế Hoạt Động Của Trigram Index

Thay vì lưu trữ toàn bộ giá trị của chuỗi như các chỉ mục thông thường, Trigram Index hoạt động theo các bước sau:

1. Lập chỉ mục (Indexing): Cơ sở dữ liệu chia nhỏ toàn bộ nội dung văn bản trong cột thành một tập hợp các trigram và lưu trữ chúng (thường dưới dạng GIN hoặc GiST index).
2. Xử lý truy vấn (Querying): Khi bạn tìm kiếm với câu lệnh LIKE '%cat%', hệ thống cũng sẽ chia từ khóa "cat" thành các trigram tương ứng.
3. So khớp (Matching): Hệ thống sẽ tìm trong index những hàng (rows) có chứa đầy đủ các trigram của từ khóa tìm kiếm. Nó bỏ qua việc quét toàn bộ bảng dữ liệu (Full Table Scan), giúp tăng tốc độ truy vấn lên hàng chục đến hàng trăm lần.

3. So Sánh Trigram Index Và B-Tree Index

Chỉ mục mặc định B-Tree thường bị vô hiệu hóa khi bạn đặt dấu % ở đầu từ khóa tìm kiếm. Đây là lúc Trigram Index thể hiện sức mạnh:

4. Ưu Điểm Và Hạn Chế

Ưu điểm:

• Tốc độ đột phá cho LIKE: Giải quyết triệt để bài toán thắt cổ chai hiệu suất khi phải tìm kiếm văn bản chứa các ký tự đại diện ở đầu (%word%).
• Tìm kiếm độ tương đồng: Có thể chấm điểm mức độ giống nhau giữa hai chuỗi (Similarity Score), cho phép tìm được kết quả ngay cả khi người dùng gõ sai chính tả.
• Hỗ trợ Regular Expression: Tối ưu hóa mạnh mẽ cho các câu lệnh tìm kiếm bằng biểu thức chính quy (Regex).

Hạn chế:

• Chi phí lưu trữ cao: Vì phải chia nhỏ văn bản, dung lượng bộ nhớ dành cho Trigram Index thường lớn hơn nhiều so với dữ liệu gốc.
• Giảm tốc độ ghi (Write/Update): Quá trình tính toán và lưu trữ trigram khiến việc chèn thêm (INSERT) hoặc cập nhật (UPDATE) dữ liệu vào bảng tốn nhiều thời gian hơn.
• Không hiệu quả với từ quá ngắn: Các từ chỉ có 1 hoặc 2 ký tự không mang lại nhiều ý nghĩa khi tạo trigram.

5. Ứng Dụng Thực Tế

• Thanh tìm kiếm Auto-complete: Tìm kiếm tên người dùng, tên sản phẩm chứa một cụm từ bất kỳ ở giữa.
• Gợi ý "Có phải ý bạn là...": Hệ thống sửa lỗi chính tả dựa trên khoảng cách tương đồng của các từ.
• Tra cứu danh mục lớn: Tìm kiếm các mã SKU, biển số xe, hoặc mã sản phẩm không theo một quy tắc liền mạch.