PostgreSQL — pg_trgm

Extension giúp LIKE/ILIKE sử dụng được index, đồng thời cho phép fuzzy search và similarity search — những thứ mà B-tree không làm được.

---

1. Trigram là gì?

Trigram = chia chuỗi thành các nhóm 3 ký tự liên tiếp.

"iphone" → "  i", " ip", "iph", "pho", "hon", "one", "ne "
           (thêm 2 space ở đầu và 1 space ở cuối)

Hai chuỗi giống nhau khi có nhiều trigram chung. Đây là nền tảng của toàn bộ pg_trgm.

-- Xem trigram của 1 chuỗi
SELECT show_trgm('iphone');
-- {"  i"," ip","hon","iph","ne ","one","pho"}

SELECT similarity('iphone', 'iPhone 15 Pro');
-- 0.47

SELECT similarity('iphone', 'Samsung Galaxy');
-- 0.05

---

2. Vấn đề với LIKE/ILIKE thông thường

-- B-tree index trên name
CREATE INDEX idx_products_name ON products (name);

WHERE name LIKE 'iPhone%'    -- % ở cuối → B-tree dùng được ✅
WHERE name LIKE '%iphone%'   -- % ở đầu  → Seq Scan ❌
WHERE name ILIKE '%iphone%'  -- ILIKE bất kỳ → Seq Scan ❌

Tại sao % ở đầu vô hiệu hóa B-tree:

B-tree sort theo thứ tự từ điển:
  "AirPods Pro"
  "Dell XPS 15"
  "iPad Air"
  "iPhone 14"
  "iPhone 15 Pro"   ← WHERE name LIKE 'iPhone%' → tìm từ đây đến hết "iPhone..."
  "MacBook Pro"

WHERE name LIKE '%phone%'
→ "phone" có thể xuất hiện bất kỳ đâu
→ không có điểm bắt đầu trong B-tree
→ phải scan toàn bộ

Kết luận: không dùng LIKE %...% thông thường trên production:

❌ WHERE name LIKE '%iPad%'   → mất index → Seq Scan → chậm
❌ WHERE name ILIKE '%iPad%'  → mất index → Seq Scan → chậm

✅ Thay thế bằng:
   pg_trgm + ILIKE      → exact substring CÓ index
   pg_trgm similarity   → fuzzy, chấp nhận sai chính tả
   Full-text search      → tìm theo từ, nội dung dài

---

3. Cài đặt và tạo index

CREATE EXTENSION IF NOT EXISTS pg_trgm;

-- GIN index với trgm operator class
CREATE INDEX idx_products_name_trgm ON products USING GIN (name gin_trgm_ops);

-- Giờ cả 3 query này đều dùng index
WHERE name LIKE 'iPhone%'
WHERE name LIKE '%phone%'
WHERE name ILIKE '%điện thoại%'

Cơ chế hoạt động

GIN lưu inverted map: mỗi trigram → danh sách rows chứa trigram đó.

GIN index (products.name):
  "  i"  → [row1, row5, row8, ...]
  " ip"  → [row1, row5, ...]
  "iph"  → [row1, row5, ...]
  "pho"  → [row1, row5, row12, ...]
  "hon"  → [row1, row5, ...]
  "one"  → [row1, row5, row3, ...]
  ...

Query WHERE name ILIKE '%iphone%':
1. Tách "iphone" → trigrams: ["iph", "pho", "hon", "one", ...]
2. Lookup từng trigram trong GIN → lấy danh sách rows
3. Intersection: chỉ rows xuất hiện trong TẤT CẢ trigram lookups
4. Recheck chính xác trên những rows đó
5. Trả về kết quả

→ Thay vì scan 505,000 rows → chỉ scan vài chục rows candidate

Demo thực tế — trước và sau khi có trgm index:

Trước (Parallel Seq Scan):
→ scan toàn bộ 505,000 rows dùng 3 worker song song
→ Execution Time: 78.525ms

Sau (Bitmap Index Scan):
→ chỉ đọc 67 page (5 page index + 62 page heap)
→ Execution Time: 0.253ms
→ nhanh hơn ~310 lần

---

4. Hai toán tử chính

4.1 % — Similarity filter

Trả về rows có điểm giống nhau vượt threshold:

-- Similarity score từ 0.0 đến 1.0
SELECT name, similarity(name, 'iphone') AS score
FROM products
WHERE name % 'iphone'     -- % = similarity > threshold (mặc định 0.3)
ORDER BY score DESC
LIMIT 10;

name                      score
────────────────────────  ─────
iPhone 14 Black           0.47
iPhone 15 Pro Silver      0.44
iPhone SE 2022            0.38
...

Dùng cho autocomplete, fuzzy search — khi user gõ "iphone" sẽ tìm ra "iPhone 15 Pro".

Điều chỉnh threshold:

SET pg_trgm.similarity_threshold = 0.3;  -- default, nhiều kết quả hơn
SET pg_trgm.similarity_threshold = 0.5;  -- chặt hơn, chỉ rất giống mới trả về

Threshold thấp → nhiều kết quả, chấp nhận typo nhiều hơn. Thường để 0.3–0.4 cho search bar.

4.2 ILIKE '%...%' — Substring match

Tìm chứa chuỗi con, không tính score:

-- Tìm tất cả sản phẩm có chứa "điện thoại" (case-insensitive)
SELECT * FROM products
WHERE name ILIKE '%điện thoại%';

Đây là dùng trgm để cứu ILIKE — từ Seq Scan thành Index Scan. Không liên quan đến fuzzy match.

4.3 <-> — Distance (dùng với GiST)

Tính khoảng cách giữa 2 chuỗi (nghịch đảo similarity): 1 - similarity. Dùng để sort nearest-neighbor:

-- GiST index — cần thiết cho ORDER BY <->
CREATE INDEX idx_products_name_gist ON products USING GIST (name gist_trgm_ops);

-- 5 sản phẩm tên gần giống "iphone" nhất
SELECT name, name <-> 'iphone' AS dist
FROM products
ORDER BY dist
LIMIT 5;

name               dist
─────────────────  ────
iPhone 14 Black    0.53
iPhone 15 Pro      0.56
iPhone SE 2022     0.62
...

---

5. GIN vs GiST với trgm

	GIN	GiST
Build time	Chậm hơn	Nhanh hơn
Lookup ILIKE	Nhanh hơn	Chậm hơn
Lookup % (similarity)	Nhanh hơn	Chậm hơn
ORDER BY <-> (nearest-neighbor)	Không hỗ trợ	Hỗ trợ

Tại sao GIN không hỗ trợ ORDER BY <->:

GIN là inverted index — biết "row nào chứa trigram này" nhưng không có cấu trúc spatial để navigate theo khoảng cách.

GiST có bounding box per node, biết "node nào gần query hơn" → có thể traverse theo thứ tự khoảng cách tăng dần.

---

6. Kết hợp với Full-text search

pg_trgm tìm substring/typo. Full-text search tìm từ (với stemming). Hai cơ chế bổ trợ cho nhau:

-- Full-text: "phones" → "phone" (stemming) → tìm ra "iPhone"
WHERE to_tsvector('simple', name) @@ to_tsquery('simple', 'phone')

-- trgm: tìm substring
WHERE name ILIKE '%phone%'

-- trgm similarity: fuzzy, cho phép typo
WHERE name % 'iphon'    -- gõ thiếu 'e' vẫn ra

Chọn cái nào:

Search box ngắn (tên sản phẩm)   → pg_trgm + ILIKE
Chấp nhận sai chính tả           → pg_trgm similarity
Search nội dung dài (mô tả)      → full-text search
LIKE '%...%' thông thường         → không dùng ❌

Trong thực tế, thường kết hợp cả hai: full-text cho search chính xác, trgm làm fallback khi full-text không ra kết quả.

---

7. Các pattern thực tế

Search bar cơ bản

-- Tạo index 1 lần
CREATE INDEX idx_products_name_trgm ON products USING GIN (name gin_trgm_ops);

-- Query từ backend: user gõ gì → tìm kiếm
SELECT id, name, price
FROM products
WHERE name ILIKE '%' || $1 || '%'   -- $1 = input từ user
  AND is_active = true
ORDER BY similarity(name, $1) DESC  -- sort theo độ liên quan
LIMIT 20;

Autocomplete (fuzzy, cho phép typo)

-- Khi user gõ "iphon" muốn ra "iPhone"
SELECT name, similarity(name, $1) AS score
FROM products
WHERE name % $1                     -- similarity > threshold
  AND is_active = true
ORDER BY score DESC
LIMIT 10;

Nearest-neighbor (cần sort chính xác theo distance)

CREATE INDEX idx_products_name_gist ON products USING GIST (name gist_trgm_ops);

SELECT name, name <-> $1 AS dist
FROM products
WHERE is_active = true
ORDER BY dist                       -- GiST traverse theo khoảng cách
LIMIT 5;

Partial index + trgm (index nhỏ hơn, nhanh hơn)

-- Chỉ index active products
CREATE INDEX idx_active_products_name_trgm ON products
  USING GIN (name gin_trgm_ops)
WHERE is_active = true;

-- Query phải kèm WHERE is_active = true thì planner mới dùng partial index
SELECT * FROM products
WHERE name ILIKE '%iphone%'
  AND is_active = true;

---

8. Giới hạn cần biết

Index không hiệu quả với chuỗi quá ngắn:

Chuỗi < 3 ký tự → không tạo được trigram
WHERE name ILIKE '%ip%'  → Seq Scan, dù có index

Thực tế: search bar thường đặt minimum 3 ký tự trước khi gọi API — phù hợp với giới hạn này.

GIN insert chậm hơn B-tree:

GIN dùng pending list — insert xong chưa được merge vào tree ngay. Autovacuum sẽ merge định kỳ. Điều này không ảnh hưởng đến correctness, nhưng nếu pending list quá lớn thì một số query sẽ phải scan thêm pending list.

Planner bỏ qua index khi quá nhiều row thỏa mãn:

WHERE name ILIKE '%Product%' → 99% table thỏa mãn
→ Seq Scan rẻ hơn index scan
→ planner bỏ qua trgm index

WHERE name ILIKE '%iPad%' → ít row → dùng index ✅

---

9. Khi nào dùng gì?

Bài toán	Giải pháp
ILIKE '%...%' — substring match	GIN + gin_trgm_ops
Autocomplete / fuzzy search	GIN + toán tử %
Nearest-neighbor sort theo distance	GiST + <->
Search bar kết hợp fuzzy + chính xác	GIN trgm + Full-text search
Tìm user, product bị typo tên	GIN + toán tử % + threshold ~0.3
LIKE '%...%' thông thường	❌ Không dùng trên production