Pattern matching — vì sao LIKE '%x' không dùng được index

TL;DR: LIKE 'x%' (prefix) dùng được index có thứ tự vì xác định được một khoảng liên tục để quét; LIKE '%x%' (leading wildcard) thì không, buộc phải quét toàn bộ. Đây là nguyên lý phổ quát cho mọi index dạng cây sắp xếp (B-tree), không riêng engine nào. Case-insensitive viết chuẩn bằng LOWER(col) LIKE LOWER('x%') cần index trên biểu thức. Substring và fuzzy search là bài toán khó cần loại index chuyên dụng (trigram) mà từng RDBMS hỗ trợ khác nhau.

Dashboard quản lý task có ô tìm kiếm theo tiêu đề. Bạn thêm index trên cột title rồi đo:

• WHERE title LIKE 'deploy%' — vài mili-giây, dùng index.
• WHERE title LIKE '%deploy%' — hàng trăm mili-giây, quét toàn bảng.

Cùng một bảng, 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á index? Bài này map 4 cấp pattern matching từ nhẹ đến nặng, giải thích cơ chế prefix scan của index có thứ tự (áp dụng cho mọi RDBMS), 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ế prefix scan — vì sao chỉ prefix mới nhanh

Index dạng B-tree lưu giá trị column đã được sort theo thứ tự từ điển. Khi bạn viết LIKE 'deploy%', hệ quản trị biết rằng kết quả nằm trong khoảng từ '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à đúng với mọi engine dùng index B-tree (PostgreSQL, MySQL/InnoDB, SQL Server, SQLite…).

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 đọc toàn bộ. Cost tăng tuyến tính với số rows.

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

-- FAST: prefix scan, range [deploy, deploz)
SELECT * FROM tasks WHERE title LIKE 'deploy%';   -- dung index, ~5ms

-- SLOW: leading wildcard, khong co prefix
SELECT * FROM tasks WHERE title LIKE '%deploy%';  -- quet toan bang, ~800ms

Cơ chế nội tại của B-tree index (leaf node, range scan, vì sao planner chọn quét index hay quét bảng) được mổ sâu ở Module 6 — Storage & indexing.

3. 4 cấp pattern matching

3.1 LIKE — chuẩn ANSI, case-sensitive

% khớp với chuỗi bất kỳ (kể cả rỗng), _ khớp đúng một ký tự. Đây là chuẩn SQL, có ở mọi RDBMS. Mặc định phân biệt hoa thường (case-sensitive) trên phần lớn engine.

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

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

3.2 Case-insensitive — chuẩn dùng LOWER()

Cách viết portable (chạy ở mọi RDBMS) là hạ cả hai vế về cùng một case:

-- Match deploy, Deploy, DEPLOY, dEpLoY -- chuan ANSI
SELECT * FROM tasks WHERE LOWER(title) LIKE LOWER('Deploy%');

Nhưng index B-tree trên title lưu giá trị gốc, không lưu lowercase, nên query trên LOWER(title) không dùng được index đó. Cần index trên biểu thức:

-- Index tren bieu thuc 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%';

3.3 Regular expression (regex)

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. Hầu hết RDBMS đều hỗ trợ regex nhưng cú pháp toán tử khác nhau: PostgreSQL dùng ~ / ~*, MySQL dùng REGEXP / RLIKE, Oracle dùng REGEXP_LIKE(...), SQLite cần hàm regexp() đăng ký thêm.

-- Y tuong (cu phap minh hoa): bat dau bang deploy hoac release
-- PostgreSQL:  title ~ '^(deploy|release)'
-- MySQL:       title REGEXP '^(deploy|release)'
-- Oracle:      REGEXP_LIKE(title, '^(deploy|release)')

Dù cú pháp nào, regex thường không tận dụng được index có thứ tự — gần như luôn là full scan.

3.4 Full-text search (FTS)

FTS tách văn bản thành token, chuẩn hoá (stemming, bỏ stopword) rồi index riêng. Phù hợp cho tìm theo nghĩa (semantic search) thay vì so khớp chuỗi con. Đây là một hệ thống index tách biệt với B-tree, và mỗi RDBMS hiện thực khác nhau (PostgreSQL tsvector + GIN, MySQL FULLTEXT index, SQL Server Full-Text Search, hoặc engine ngoài như Elasticsearch).

Điểm chung về nguyên lý: FTS đánh đổi độ phức tạp ghi và lưu trữ để lấy khả năng tìm kiếm ngôn ngữ tự nhiên mà LIKE '%x%' không làm được. Chi tiết cơ chế index đặc thù xem Module 6 — Storage & indexing.

4. Decision tree theo use case

flowchart TD
  START["Can tim text trong column"] --> Q1{"Biet prefix co dinh?"}
  Q1 -->|"Co (vd 'deploy...')"| PREFIX["LIKE 'x%' + B-tree index<br/>nhanh nhat"]
  Q1 -->|"Khong"| Q2{"Can tim theo nghia?"}
  Q2 -->|"Co (semantic)"| FTS["Full-text search<br/>tokenize + stem"]
  Q2 -->|"Khong, chi substring"| Q3{"Can chiu loi danh may?"}
  Q3 -->|"Co"| FUZZY["Trigram + similarity"]
  Q3 -->|"Khong"| SUB["LIKE '%x%' + trigram index<br/>(B-tree thuong = full scan)"]

5. Substring và fuzzy — bài toán khó, cần index chuyên dụng

LIKE '%x%' chậm vì không có prefix. Cách giải phổ biến là trigram index: chia văn bản thành các chuỗi 3 ký tự liên tiếp (trigram) rồi index chúng; khi tìm '%deploy%', engine phân tích pattern thành trigram và tra index để lọc candidate, không quét toàn bảng. Trigram cũng cho phép fuzzy search — đo độ tương tự để tìm "deploy" khi người dùng gõ "depoly".

Đây là tính năng đặc thù từng engine: PostgreSQL có extension pg_trgm (index GIN với gin_trgm_ops), MySQL/Oracle/SQL Server có cơ chế khác hoặc dựa vào FTS. Nguyên lý chung quan trọng hơn cú pháp: substring/fuzzy search ở quy mô lớn không thể giải bằng B-tree thường — phải dùng một cấu trúc index khác.

Tradeoff loại index này: ghi chậm hơn B-tree (thường vài lần), lưu trữ lớn hơn. Đáng đầu tư khi bảng 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: full scan (index tren email khong duoc dung)

-- FIX: index tren bieu thuc (ro rang, portable)
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 — ô 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 LOWER(title) LIKE LOWER($1) || '%'
LIMIT 10;
-- Index can: CREATE INDEX ON tasks(LOWER(title));  -> index scan, ~4ms

-- Substring search (user go "dep" -> tim bat ky task chua "dep")
SELECT id, title FROM tasks
WHERE title LIKE '%' || $1 || '%'
LIMIT 50;
-- B-tree thuong: full scan, ~800ms tren 1M tasks
-- Trigram index: ~8ms

-- Fuzzy search chiu loi danh may -- can index/ham similarity cua engine

Prefix 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 chứa chuỗi đó ở bất kỳ vị trí — kết quả nhiều hơn nhưng cần index chuyên dụng. Nhiều app dùng prefix autocomplete khi user đang gõ (low latency) và chuyển sang substring/FTS khi user nhấn Enter.

8. Deep Dive — Pattern matching

9. Liên hệ các bài khác

• Bài 01 — SELECT, projection & alias: nơi WHERE lần đầu xuất hiện; pattern matching là một dạng vị từ WHERE.
• Bài 06 — CASE, COALESCE, NULLIF: kết hợp pattern matching với biểu thức điều kiện để phân loại kết quả.
• Module 6 — Storage & indexing: vì sao prefix dùng được index còn leading wildcard thì không — cơ chế index có thứ tự được mổ sâu ở đó.

10. Tóm tắt

• LIKE 'x%' dùng được index B-tree vì có prefix cố định (range scan); LIKE '%x%' và LIKE '%x' buộc full scan. Nguyên lý này đúng cho mọi RDBMS dùng index có thứ tự.
• Case-insensitive portable: LOWER(col) LIKE LOWER('x%') + index trên biểu thức. ILIKE (PostgreSQL) hay collation (MySQL) là tiện ích dialect.
• Regex mạnh hơn LIKE nhưng cú pháp khác nhau giữa engine và thường không dùng được index.
• Substring/fuzzy ở quy mô lớn cần index chuyên dụng (trigram) — không giải được bằng B-tree thường.
• Function trên indexed column trong WHERE kill index — dùng index biểu thức.

11. Tự kiểm tra

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