Pattern matching — vì sao LIKE '%x' kill index

Dashboard TaskFlow có ô tìm kiếm task theo tiêu đề. Bạn thêm index B-tree trên cột title rồi chạy thử:

• WHERE title LIKE 'deploy%' — 5ms, plan: Index Scan.
• WHERE title LIKE '%deploy%' — 800ms, plan: Seq Scan.

Cùng một table, cùng một index, chỉ thêm dấu % phía trước — index biến mất hoàn toàn. Vì sao leading wildcard vô hiệu hoá B-tree index? Và làm sao pg_trgm khôi phục tốc độ về 8ms?

Bài này map 4 cấp pattern matching từ nhẹ đến nặng, giải thích cơ chế B-tree prefix scan, và đưa ra decision tree khi nào dùng cái nào.

1. Analogy — Tìm tên trong sổ điện thoại

Sổ điện thoại in theo thứ tự alphabet — tên được sort theo tiền tố. Khi tìm tất cả tên bắt đầu bằng "Nguyen", bạn mở thẳng đến trang N, đọc liên tiếp đến khi hết họ Nguyễn — rất nhanh. Nhưng khi tìm tất cả tên có chứa "nguyen" ở bất kỳ vị trí nào, bạn buộc phải đọc từng trang một từ đầu đến cuối — không có cách nào bỏ qua.

2. Cơ chế B-tree prefix scan

B-tree index lưu giá trị column đã được sort theo thứ tự từ điển. Khi bạn viết LIKE 'deploy%', PostgreSQL biết rằng kết quả nằm trong khoảng từ 'deploy' đến 'deployz' (hay chính xác hơn, 'deploy' đến tiền tố kế tiếp 'deploz'). Đây là một range scan — database seek đến điểm bắt đầu rồi đọc liên tiếp cho đến khi ra khỏi range. Rất nhanh.

Với LIKE '%deploy%', không có tiền tố cố định nào — pattern có thể match "abc_deploy_xyz", "x_deploy", hay "deploy" ngay đầu. Database không thể xác định range bắt đầu trong B-tree, buộc phải scan toàn bộ.

-- Co B-tree index tren title
CREATE INDEX idx_tasks_title ON tasks(title);

-- FAST: prefix scan, range [deploy, deploz)
EXPLAIN ANALYZE SELECT * FROM tasks WHERE title LIKE 'deploy%';
-- Plan: Index Scan using idx_tasks_title
-- actual time: 5ms

-- SLOW: leading wildcard, khong co prefix
EXPLAIN ANALYZE SELECT * FROM tasks WHERE title LIKE '%deploy%';
-- Plan: Seq Scan on tasks
-- actual time: 800ms

Forward link: Module 5 của khoá này sẽ phân tích cấu trúc nội tại của B-tree index — leaf node, page split, và cách planner chọn index scan vs seq scan.

3. 4 cấp pattern matching

3.1 LIKE — basic, case-sensitive

% khớp với chuỗi bất kỳ (kể cả rỗng), _ khớp đúng một ký tự. PostgreSQL mặc định case-sensitive.

SELECT * FROM tasks WHERE title LIKE 'deploy%';    -- prefix - fast, dung index
SELECT * FROM tasks WHERE title LIKE '%deploy';    -- suffix - slow, seq scan
SELECT * FROM tasks WHERE title LIKE '%deploy%';   -- contains - slow, seq scan
SELECT * FROM tasks WHERE title LIKE 'deploy___';  -- prefix 6 ky tu + 3 bat ky

Pattern 'deploy%' dùng được B-tree index. Ba pattern còn lại không có prefix cố định — đều là seq scan.

3.2 ILIKE — case-insensitive, PostgreSQL-specific

-- Match deploy, Deploy, DEPLOY, dEpLoY
SELECT * FROM tasks WHERE title ILIKE 'Deploy%';

Nội bộ PostgreSQL chuyển ILIKE 'Deploy%' thành LOWER(title) LIKE LOWER('Deploy%'). B-tree index trên title không dùng được vì index lưu giá trị gốc, không lưu lowercase. Cần expression index:

-- Expression index tren LOWER(title)
CREATE INDEX idx_tasks_title_lower ON tasks(LOWER(title));

-- Bay gio query nay dung duoc index
SELECT * FROM tasks WHERE LOWER(title) LIKE 'deploy%';
-- Plan: Index Scan using idx_tasks_title_lower

3.3 POSIX regex — ~ và ~*

Mạnh hơn LIKE về biểu đạt nhưng không có tối ưu prefix. Dùng khi LIKE không đủ khả năng diễn đạt pattern.

-- ~ case-sensitive, ~* case-insensitive
SELECT * FROM tasks WHERE title ~ '^(deploy|release)';   -- bat dau bang deploy hoac release
SELECT * FROM tasks WHERE title ~* '^deploy';            -- case-insensitive anchor
SELECT * FROM tasks WHERE title ~ '\d{4}-\d{2}-\d{2}';  -- co dang ngay YYYY-MM-DD

Cả ~ và ~* đều không tận dụng được B-tree index — luôn là seq scan hoặc index scan full range.

3.4 Full-text search — tsvector/tsquery

FTS tokenize và stem văn bản, lưu vào tsvector, index bằng GIN. Phù hợp cho semantic search — tìm theo nghĩa, không phải substring.

SELECT * FROM tasks
WHERE to_tsvector('english', title) @@ to_tsquery('deploy & production');
-- Match: "Deploying to production env", "Production deployment checklist"
-- Khong match: "deploying-to-production" (tuy theo tokenizer)

FTS index bằng GIN, không phải B-tree. Forward link: Module 9 của khoá này đi sâu vào FTS, GIN index internals, và cấu hình tiếng Việt với unaccent.

4. Decision tree theo use case

5. pg_trgm — giải bài toán substring và fuzzy

Extension pg_trgm chia văn bản thành các trigram (chuỗi 3 ký tự liên tiếp) rồi index bằng GIN. Khi bạn tìm '%deploy%', PG phân tích pattern thành trigrams rồi dùng GIN index để tìm candidates — không cần scan toàn table.

-- Bat dau bang enable extension
CREATE EXTENSION IF NOT EXISTS pg_trgm;

-- Tao GIN index tren title voi operator class cua trgm
CREATE INDEX idx_tasks_title_trgm ON tasks USING GIN (title gin_trgm_ops);

-- Bay gio LIKE '%deploy%' dung duoc index
EXPLAIN ANALYZE SELECT * FROM tasks WHERE title LIKE '%deploy%';
-- Plan: Bitmap Heap Scan -> Bitmap Index Scan on idx_tasks_title_trgm
-- actual time: 8ms (truoc khi co index: 800ms)

Bonus: pg_trgm cũng hỗ trợ fuzzy similarity search qua operator % và hàm similarity():

-- Tim task co title gan giong 'depoly' (loi danh may)
SELECT title, similarity(title, 'depoly') AS sim
FROM tasks
WHERE title % 'depoly'   -- % la similarity threshold operator, default >= 0.3
ORDER BY sim DESC
LIMIT 10;
-- Tra ve: "deploy prod", "deploy staging", ...

Tradeoff GIN index: write chậm hơn B-tree khoảng 5-10 lần, storage lớn hơn khoảng 2-3 lần. Đáng đầu tư khi table read-heavy và substring/fuzzy search là tính năng cốt lõi.

6. Pitfall — function trên indexed column

-- WRONG: LOWER(email) khong dung index tren email
SELECT * FROM users WHERE LOWER(email) = '[email protected]';
-- Plan: Seq Scan (index tren email khong duoc dung)

-- Fix 1: ILIKE (PostgreSQL tu xu ly, transparent voi app)
SELECT * FROM users WHERE email ILIKE '[email protected]';

-- Fix 2: expression index (ro rang nhat, portable nhat)
CREATE INDEX idx_users_email_lower ON users(LOWER(email));
SELECT * FROM users WHERE LOWER(email) = '[email protected]';
-- Plan: Index Scan using idx_users_email_lower

7. Applied — TaskFlow search box

Ba scenario tìm kiếm phổ biến, mỗi cái cần SQL và index khác nhau:

-- Autocomplete theo prefix (user go "dep" -> goi y "deploy...", "deployment...")
SELECT id, title
FROM tasks
WHERE title ILIKE $1 || '%'
LIMIT 10;
-- Index can: CREATE INDEX ON tasks(LOWER(title));
-- Voi input 'dep' -> LOWER(title) LIKE 'dep%' -> index scan, ~4ms

-- Substring search (user go "dep" -> tim bat ky task chua "dep")
SELECT id, title
FROM tasks
WHERE title ILIKE '%' || $1 || '%'
LIMIT 50;
-- Khong co pg_trgm: seq scan, ~800ms tren 1M tasks
-- Co pg_trgm GIN: bitmap index scan, ~8ms

-- Fuzzy search chiu loi danh may (user go "depoly" -> tra ve "deploy...")
SELECT id, title, similarity(title, $1) AS sim
FROM tasks
WHERE title % $1
ORDER BY sim DESC
LIMIT 10;
-- Can: CREATE INDEX ON tasks USING GIN (title gin_trgm_ops);

Prefix autocomplete và substring search có UX khác nhau rõ rệt: autocomplete LIKE 'x%' chỉ gợi ý task bắt đầu bằng từ đó (giống Google omnibox); substring LIKE '%x%' trả về mọi task có chứa chuỗi đó ở bất kỳ vị trí nào — kết quả nhiều hơn nhưng index cần pg_trgm.

8. Deep Dive — Pattern matching

9. Tóm tắt

• LIKE 'x%' dùng được B-tree index vì có prefix cố định; LIKE '%x%' và LIKE '%x' buộc planner phải seq scan.
• ILIKE là case-insensitive LIKE của PostgreSQL — cần expression index trên LOWER(column) để tận dụng index.
• POSIX regex ~ / ~* cho pattern phức tạp hơn LIKE nhưng không có prefix optimisation, luôn là full scan.
• pg_trgm GIN giải bài toán substring (LIKE '%x%') và fuzzy (similarity()) — tradeoff write chậm hơn và storage lớn hơn B-tree.
• Function trên indexed column trong WHERE clause kill index — dùng expression index hoặc rewrite query để tránh.
• Forward links: Module 5 của khoá này (B-tree internals, composite index) + Module 9 (FTS deep dive + cấu hình tiếng Việt).

10. Tự kiểm tra

SELECT * FROM users WHERE email ILIKE '[email protected]';

CREATE INDEX idx_users_email_lower ON users(LOWER(email));
SELECT * FROM users WHERE LOWER(email) = '[email protected]';

Bài tiếp theo: CASE + COALESCE + NULLIF — fallback và conditional