PostgreSQL Bài 19: Regular Expressions và Fuzzy Search với extension pg_trgm

Ở Bài 18, chúng ta đã tìm hiểu Full-Text Search với tsvector và tsquery. FTS xử lý hoàn hảo các câu văn ngôn ngữ tự nhiên dựa trên từ điển và gốc từ (stemming). Tuy nhiên, FTS có hai điểm mù lớn trong thực tế:

1. Gõ sai chính tả (Typo / Misspelling): Nếu khách hàng tìm kiếm "iphoen" hoặc "sam sung", FTS chuẩn sẽ không thể tìm ra sản phẩm "iPhone" hay "Samsung".

2. Tìm chuỗi con tùy ý (Substring / Partial matching): FTS tìm theo từ (word), không tìm được chuỗi con nằm lửng lơ bên trong một từ hoặc mã code (ví dụ: tìm "8839" bên trong mã SKU "VN-8839-PRO").

Để giải quyết hai bài toán này mà vẫn giữ được tốc độ truy vấn cao trên hàng triệu bản ghi, PostgreSQL cung cấp một extension mạnh mẽ mang tên pg_trgm (Trigram).

1. Nguyên lý hoạt động của Trigram (3-gram)

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

Trước khi bóc tách các trigram, PostgreSQL thực hiện chuẩn hóa:

• Chuyển toàn bộ chuỗi về chữ thường (lowercase).

• Bổ sung 2 khoảng trắng phía trước và 1 khoảng trắng phía sau chuỗi để đánh dấu điểm bắt đầu và kết thúc của từ.

Ví dụ chuỗi: "hieu"
Sau khi thêm khoảng trắng: "  hieu "

Tách thành các lát cắt 3 ký tự liên tiếp:
1. "  h"
2. " hi"
3. "hie"
4. "ieu"
5. "eu "

Tổng cộng: Từ "hieu" (4 ký tự) sinh ra 5 trigrams riêng biệt.

1.1. Công thức đo độ tương đồng (Similarity)

Độ tương đồng giữa hai chuỗi $A$ và $B$ được tính bằng hệ số Jaccard Similarity trên tập hợp các trigram của chúng:

$$\text{Similarity}(A, B) = \frac{\vert{}Trigrams(A) \cap Trigrams(B)\vert{}}{\vert{}Trigrams(A) \cup Trigrams(B)\vert{}}$$

• Giá trị trả về nằm trong khoảng từ 0.0 (hoàn toàn khác nhau) đến 1.0 (giống hệt nhau).

• Càng nhiều trigram trùng lặp, hai từ càng giống nhau về mặt phát âm và cấu trúc chữ viết, bất chấp lỗi hoán đổi ký tự hay gõ thiếu chữ.

2. Kích hoạt và Trải nghiệm các hàm cốt lõi của pg_trgm

Mở terminal psql và kích hoạt extension:

SQL

CREATE EXTENSION IF NOT EXISTS pg_trgm;

2.1. Phân tích Trigram với hàm show_trgm()

Xem các trigram thực tế mà engine bóc tách:

SQL

SELECT show_trgm('postgres');

Plaintext

                       show_trgm                       
-------------------------------------------------------
 {"  p"," po","es ",gre,ost,res,tgr,tgr}

2.2. Đo độ tương đồng với similarity() và toán tử %

• Hàm similarity(text, text): Trả về điểm số tương đồng thực tế ($0.0 \rightarrow 1.0$).

• Toán tử %: Kiểm tra xem độ tương đồng có vượt qua ngưỡng (threshold) định trước hay không (mặc định là 0.3).

SQL

-- So sánh từ gõ sai "posgresql" với từ đúng "postgresql":
SELECT 
    similarity('posgresql', 'postgresql') AS score,
    'posgresql' % 'postgresql' AS is_similar;

Plaintext

   score   | is_similar 
-----------+------------
 0.7333333 | t

Điểm số đạt tới 0.73, vượt xa ngưỡng mặc định 0.3, do đó toán tử % trả về true!

2.3. Điều chỉnh ngưỡng tương đồng (Threshold Tuning)

Tùy vào nghiệp vụ, bạn có thể siết chặt hoặc nới lỏng độ "khoan dung" với lỗi chính tả:

SQL

-- Xem ngưỡng hiện tại (mặc định là 0.3):
SHOW pg_trgm.similarity_threshold;

-- Tăng độ khắt khe lên 0.5 trong session hiện tại:
SET pg_trgm.similarity_threshold = 0.5;

3. Regular Expressions trong PostgreSQL

Bên cạnh tìm kiếm mờ, PostgreSQL hỗ trợ hệ thống so khớp biểu thức chính quy (Regex) theo chuẩn POSIX trực tiếp trong mệnh đề WHERE:

Toán tử	Ý nghĩa	Ví dụ
~	Khớp regex (có phân biệt hoa thường - Case-sensitive)	'PostgreSQL' ~ '^Post' (True)
~*	Khớp regex (không phân biệt hoa thường - Case-insensitive)	'postgresql' ~* '^POST' (True)
!~	Không khớp regex (Case-sensitive)	'12345' !~ '[a-z]' (True)
!~*	Không khớp regex (Case-insensitive)	'abc' !~* '[0-9]' (True)

Khai thác hàm regexp_matches() và regexp_replace():

SQL

-- 1. Bóc tách số điện thoại từ văn bản thô:
SELECT (regexp_matches('Hotline liên hệ: 0912345678 hoặc 0987654321', '(0[0-9]{9})', 'g'))[1] AS phone;

-- 2. Chuẩn hóa chuỗi (Xóa khoảng trắng thừa liên tiếp):
SELECT regexp_replace('Học   PostgreSQL     rất   thú vị', '\s+', ' ', 'g');
-- Kết quả: "Học PostgreSQL rất thú vị"

4. Đánh Index tăng tốc: Cứu cánh cho LIKE '%...%' và Regex

Đây là tính năng giá trị nhất của pg_trgm trong kiến trúc cơ sở dữ liệu thực tế.

Thông thường, câu lệnh:

SQL

SELECT * FROM users WHERE email LIKE '%gmail%';
SELECT * FROM products WHERE code ~* '.*PRO-[0-9]+.*';

bắt buộc phải chạy Sequential Scan vì B-Tree Index chỉ hỗ trợ tìm kiếm tiền tố (LIKE 'gmail%'), hoàn toàn vô dụng với ký tự % hoặc regex nằm ở đầu chuỗi.

Bằng cách dùng pg_trgm, bạn có thể đánh index cho cả LIKE '%...%' và biểu thức chính quy!

4.1. Lựa chọn: GIN Index vs GiST Index cho Trigram

Tiêu chí so sánh	GIN Trigram (gin_trgm_ops)	GiST Trigram (gist_trgm_ops)
Tốc độ đọc (SELECT)	Rất nhanh (Gấp 2-3 lần GiST)	Chậm hơn một chút
Tốc độ ghi (INSERT/UPDATE)	Chậm hơn (phải cập nhật nhiều posting list)	Nhanh hơn GIN
Dung lượng Index	Lớn hơn	Gọn gàng hơn
Hỗ trợ toán tử sắp xếp k-NN (<->)	Không hỗ trợ	Hỗ trợ cực tốt (Tìm Top N từ giống nhất tức thì)

5. Thực hành: Xây dựng hệ thống Auto-complete và Fuzzy Search

Tạo bảng khách hàng giả lập với 100.000 dòng để quan sát sự khác biệt hiệu năng:

SQL

CREATE SCHEMA IF NOT EXISTS search_lab;

CREATE TABLE search_lab.customers (
    id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    full_name TEXT NOT NULL,
    email TEXT NOT NULL
);

-- Nạp 100.000 dòng dữ liệu mẫu
INSERT INTO search_lab.customers (full_name, email)
SELECT 
    'Customer ' || i || ' ' || (ARRAY['Nguyen', 'Tran', 'Le', 'Pham', 'Hoang'])[1 + (i % 5)],
    'user_' || i || '@domain' || (i % 10) || '.com'
FROM generate_series(1, 100000) AS i;

-- Đánh GIN Trigram Index trên full_name và email
CREATE INDEX idx_customers_name_trgm_gin ON search_lab.customers USING GIN (full_name gin_trgm_ops);
CREATE INDEX idx_customers_email_trgm_gin ON search_lab.customers USING GIN (email gin_trgm_ops);

ANALYZE search_lab.customers;

Kịch bản 1: Tăng tốc truy vấn LIKE '%...%'

Tìm kiếm tất cả khách hàng có chứa chuỗi "Nguyen" ở bất kỳ vị trí nào:

SQL

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM search_lab.customers 
WHERE full_name LIKE '%Nguyen%';

Kế hoạch thực thi (Execution Plan):

Plaintext

Bitmap Heap Scan on customers  (cost=12.25..315.40 rows=20000 width=35) (actual time=0.850..4.120 rows=20000 loops=1)
  Recheck Cond: (full_name ~~ '%Nguyen%'::text)
  Buffers: shared hit=415
  ->  Bitmap Index Scan on idx_customers_name_trgm_gin  (cost=0.00..7.25 rows=20000 width=0) (actual time=0.610..0.610 rows=20000 loops=1)
        Index Cond: (full_name ~~ '%Nguyen%'::text)

Nhận xét: Thay vì quét toàn bộ bảng mất hàng chục mili-giây, engine sử dụng Bitmap Index Scan thông qua idx_customers_name_trgm_gin và trả về kết quả trong dưới 5 mili-giây!

Kịch bản 2: Fuzzy Search xử lý lỗi gõ sai chính tả

Người dùng gõ sai họ "Nguyen" thành "Nguen":

SQL

SELECT 
    full_name, 
    similarity(full_name, 'Nguen') AS match_score
FROM search_lab.customers
WHERE full_name % 'Nguen'
ORDER BY match_score DESC
LIMIT 5;

Kết quả:

Plaintext

          full_name          | match_score 
-----------------------------+-------------
 Customer 5 Nguyen           |   0.4166667
 Customer 10 Nguyen          |   0.4166667
 Customer 15 Nguyen          |   0.4166667
 Customer 20 Nguyen          |   0.4166667
 Customer 25 Nguyen          |   0.4166667

Hệ thống nhận diện được "Nguyen" chính là từ khách hàng muốn tìm và trả về ngay lập tức.

Kịch bản 3: Auto-complete siêu tốc bằng GiST Index và Toán tử <-> (k-NN)

Toán tử <-> trong pg_trgm đo khoảng cách (distance) giữa 2 chuỗi:

$$\text{Distance} = 1.0 - \text{Similarity}$$

Nếu sử dụng GiST Index, PostgreSQL có thể dùng thuật toán k-Nearest Neighbors (k-NN) để tìm ra Top $N$ từ gần giống nhất mà không cần tính toán toàn bộ bảng rồi mới Sort:

SQL

-- Tạo GiST Index trên cột full_name
CREATE INDEX idx_customers_name_trgm_gist ON search_lab.customers USING GIST (full_name gist_trgm_ops);

-- Lấy 3 kết quả gần giống nhất với "Nguyn" (Top-3 nearest):
EXPLAIN (ANALYZE, BUFFERS)
SELECT full_name
FROM search_lab.customers
ORDER BY full_name <-> 'Nguyn'
LIMIT 3;

Kế hoạch thực thi:

Plaintext

Limit  (cost=0.28..1.15 rows=3 width=39) (actual time=0.210..0.218 rows=3 loops=1)
  ->  Index Scan using idx_customers_name_trgm_gist on customers  (cost=0.28..29150.00 rows=100000 width=39)
        Order By: (full_name <-> 'Nguyn'::text)

Nhận xét: Kế hoạch thực thi là một Index Scan thuần túy có Order By trực tiếp trên cây GiST. Thời gian phản hồi chỉ tốn 0.2 mili-giây — cực kỳ lý tưởng cho các tính năng Search Suggestion/Auto-complete gõ tới đâu gợi ý tới đó.

6. So sánh tổng kết: FTS (tsvector) vs Trigram (pg_trgm)

Tiêu chí	Full-Text Search (tsvector)	Trigram Search (pg_trgm)
Đơn vị xử lý	Từ ngữ (Word/Lexeme) dựa trên từ điển	Các lát cắt 3 ký tự (3-grams)
Ngữ pháp & Từ loại	Hiểu gốc từ, số ít/nhiều, stop words	Không hiểu ngữ pháp, chỉ so sánh cấu trúc ký tự
Xử lý gõ sai (Typo)	Không hỗ trợ (phải đúng từ gốc)	Rất mạnh (Fuzzy match)
Tìm chuỗi con (LIKE '%..%')	Không hỗ trợ	Hỗ trợ tối đa với GIN/GiST Index
Phù hợp nhất với	Bài viết dài, mô tả tài liệu, blog, sách	Tìm kiếm Tên người dùng, Tên sản phẩm ngắn, Mã code, Auto-complete

Kỹ thuật kết hợp thực chiến: Trên các website thương mại điện tử lớn, kiến trúc sư thường kết hợp cả hai:

1. Dùng FTS để tìm kiếm trên phần mô tả chi tiết sản phẩm (description).

2. Dùng pg_trgm trên phần tên sản phẩm (product_name) để bắt lỗi gõ phím nhanh của người dùng trên thanh search box.

7. Tóm tắt & Bài tiếp theo

• pg_trgm phân rã văn bản thành các chuỗi 3 ký tự liên tiếp để đo độ tương đồng Jaccard.

• Khắc phục hoàn toàn bài toán tìm kiếm mờ (Fuzzy Search) khi người dùng nhập sai chính tả.

• Sử dụng GIN Trigram Index (gin_trgm_ops) để tối ưu hóa triệt để các câu truy vấn LIKE '%chuỗi_con%' và Regular Expressions.

• Sử dụng GiST Trigram Index (gist_trgm_ops) kết hợp toán tử khoảng cách <-> cho các tính năng Auto-complete / Search Suggestion thời gian thực.

Bài 20 xem tiếp: DDL nâng cao: Recursive CTE và ứng dụng xử lý dữ liệu cây (Tree/Graph structures) — khép lại Phần 3, chúng ta sẽ tìm hiểu kỹ thuật đệ quy trong SQL với WITH RECURSIVE: giải quyết bài toán cây danh mục đa cấp (Category Trees), cơ cấu tổ chức nhân sự (Manager-Employee), và phát hiện vòng lặp vô tận (Cycle Detection).