PostgreSQL — GIN / GiST / BRIN

B-tree là index mặc định cho equality và range trên scalar values. Ba loại dưới đây phục vụ các bài toán B-tree không làm được.

1. GIN — Generalized Inverted Index

Dùng khi nào

jsonb — tìm theo key/value bên trong document
array — tìm theo phần tử trong mảng
Full-text search
pg_trgm — LIKE/ILIKE, similarity search

Cách hoạt động

GIN là inverted index — thay vì map row → values, nó map value → danh sách rows chứa value đó.

jsonb column "payload":
  row 1: {"type": "click", "page": "home"}
  row 2: {"type": "view",  "page": "home"}
  row 3: {"type": "click", "page": "cart"}

GIN index:
  "click" → [row1, row3]
  "view"  → [row2]
  "home"  → [row1, row2]
  "cart"  → [row3]

Khi query WHERE payload @> '{"type": "click"}' → lookup "click" trong GIN → trả về [row1, row3] ngay, không scan toàn bảng.

GIN cũng dùng cấu trúc B-tree bên dưới — nhưng khác B-tree thông thường ở chỗ:

B-tree thông thường: index nguyên giá trị column
  tier = 'gold' → ctid(0,1)

GIN: decompose giá trị thành từng phần tử → index từng phần tử
  tags = ["sale", "new"]
  → "sale" → [ctid(0,1), ctid(2,3)]
  → "new"  → [ctid(0,1), ctid(1,2)]
  → 1 row có thể xuất hiện trong nhiều posting list

Trade-off

Build chậm — phải index từng element bên trong document/array
Lookup nhanh — đã có sẵn inverted map
Update chậm — mỗi UPDATE phải cập nhật nhiều entries trong index

GIN Pending List (fastupdate)

fastupdate = on (default): GIN không update tree ngay khi INSERT — ghi vào pending list trước:

INSERT row mới
→ KHÔNG update GIN tree ngay
→ ghi vào pending list (RAM/disk) trước
→ transaction xong ngay, không chờ

Autovacuum chạy định kỳ:
→ merge pending list vào GIN tree
→ xóa pending list

Query trong lúc chưa merge:
→ scan GIN tree (đã merge)
→ scan thêm pending list (chưa merge)
→ gộp kết quả → vẫn đúng

So sánh với B-tree thông thường:

B-tree: INSERT → update tree ngay trên RAM → async flush xuống disk
GIN:    INSERT → ghi pending list RAM → autovacuum merge vào tree → async flush xuống disk

B-tree: 1 bước delay (RAM → disk)
GIN:    2 bước delay (pending list → tree → disk)

sql

-- jsonb: tìm document chứa key-value
CREATE INDEX idx_payload_gin ON events USING GIN (payload);
SELECT * FROM events WHERE payload @> '{"type": "click"}';

-- jsonb: tìm theo key bất kỳ (jsonb_path_ops nhỏ hơn, chỉ hỗ trợ @>)
CREATE INDEX idx_payload_gin ON events USING GIN (payload jsonb_path_ops);

-- array: tìm phần tử trong mảng
CREATE INDEX idx_tags_gin ON products USING GIN (tags);
SELECT * FROM products WHERE tags @> ARRAY['bestseller'];

-- trgm: LIKE/ILIKE với index
CREATE EXTENSION pg_trgm;
CREATE INDEX idx_name_trgm ON products USING GIN (name gin_trgm_ops);
SELECT * FROM products WHERE name ILIKE '%điện thoại%';

ILIKE và index

WHERE name ILIKE 'iPad%'   → % ở cuối → B-tree được ✅
WHERE name ILIKE '%iPad%'  → % ở đầu  → mất B-tree index ❌ → Seq Scan

Fix: dùng pg_trgm + GIN
→ GIN index hỗ trợ ILIKE '%...%' hiệu quả
→ không bị vấn đề % ở đầu

Full-text search

Full-text search = tìm kiếm theo nội dung văn bản, không phải exact match:

sql

-- Tokenize text thành tsvector
SELECT to_tsvector('english', 'Product 123 Description 123');
-- output: '123':2,4 'descript':3 'product':1
-- → stemming: "description" → "descript"
-- → "phones" → "phone" (tìm "phone" ra cả "phones")

Với tiếng Việt dùng simple thay vì english:

sql

-- 'english' → stemming, bỏ qua tiếng Việt
SELECT to_tsvector('english', 'Mô tả sản phẩm iPad Air Black');
-- output: 'air' 'black' 'ipad' ← bỏ qua toàn bộ tiếng Việt!

-- 'simple' → giữ nguyên tất cả từ, phù hợp tiếng Việt
SELECT to_tsvector('simple', 'Mô tả sản phẩm iPad Air Black');
-- output: 'air' 'black' 'ipad' 'mô' 'phẩm' 'sản' 'tả'

Tạo GIN index cho full-text search:

sql

-- Expression index — index trên biểu thức, không phải column thẳng
-- Gộp name + description để tìm kiếm trên cả 2 field
CREATE INDEX idx_products_fts
ON products
USING GIN (to_tsvector('simple', name || ' ' || description));

-- Query phải khớp với expression trong index
SELECT * FROM products
WHERE to_tsvector('simple', name || ' ' || description)
   @@ to_tsquery('simple', 'iPad & Air');  -- tìm có cả "iPad" và "Air"

SELECT * FROM products
WHERE to_tsvector('simple', name || ' ' || description)
   @@ to_tsquery('simple', 'MacBook | Dell');  -- tìm có "MacBook" hoặc "Dell"

So sánh ILIKE vs Full-text search:

ILIKE '%iPad%':
→ không dùng được B-tree index
→ Seq Scan toàn bộ table

Full-text search + GIN:
→ GIN decompose text thành từng từ
→ tìm từ "iPad" → lookup trong GIN → nhanh
→ không bị vấn đề % ở đầu
→ thêm stemming, hỗ trợ tìm kiếm tự nhiên hơn

2. GiST — Generalized Search Tree

Dùng khi nào

Geo / PostGIS — tìm điểm trong vùng, khoảng cách
Range types — daterange, tsrange, overlap queries
Nearest-neighbor search (ORDER BY ... <->)
pg_trgm với ORDER BY similarity (thay GIN khi cần sort theo khoảng cách)

Cách hoạt động

GiST là lossy index — không lưu chính xác value, mà lưu bounding box (xấp xỉ) cho mỗi node. Khi tìm kiếm:

Query: điểm P có nằm trong vùng V không?

GiST tìm:
1. Có bounding box nào overlap với V?  ← nhanh, dùng index
2. Với các candidate đó, check lại chính xác  ← recheck, đọc heap

Bước recheck là đặc trưng của GiST — index có thể trả về false positives, phải verify lại. Không ảnh hưởng correctness, nhưng thêm một lượt đọc heap.

sql

-- Range overlap — [generic pattern, schema này không có range-type column]
-- Thay bookings/during bằng bảng và column range-type tương ứng trong project của bạn
CREATE INDEX idx_booking_range ON bookings USING GIST (during);  -- [generic pattern]
SELECT * FROM bookings WHERE during && '[2024-01-10, 2024-01-15)';  -- [generic pattern]

-- Nearest-neighbor: tìm 5 sản phẩm tên gần giống nhất
CREATE INDEX idx_name_gist ON products USING GIST (name gist_trgm_ops);
SELECT name, name <-> 'iphone' AS dist
FROM products
ORDER BY dist
LIMIT 5;

GIN vs GiST với pg_trgm

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

→ Dùng GIN cho LIKE/ILIKE, dùng GiST khi cần ORDER BY theo similarity score.

3. BRIN — Block Range Index

Dùng khi nào

Time-series data insert theo thứ tự thời gian
Log tables, event tables với created_at tăng dần
Bảng rất lớn mà B-tree index quá tốn disk

Cách hoạt động

BRIN không index từng row — nó chia bảng thành các block range (mặc định 128 pages), lưu min và max của column trong mỗi range:

Bảng metrics (insert theo recorded_at):

Block range 1 (page 1-128):   min=2024-01-01, max=2024-01-15
Block range 2 (page 129-256): min=2024-01-15, max=2024-02-01
Block range 3 (page 257-384): min=2024-02-01, max=2024-02-20

Query: WHERE recorded_at >= '2024-02-01'
→ BRIN biết chỉ cần scan từ block range 3 trở đi
→ skip toàn bộ range 1 và 2

Cực nhỏ — index chỉ lưu min/max per range, không phải per row. Bảng 100 triệu row: B-tree ~5GB, BRIN ~100KB.

Điều kiện để BRIN hiệu quả

Data phải insert theo thứ tự vật lý — nếu rows được insert ngẫu nhiên, min/max của mỗi range sẽ overlap nhau → BRIN không filter được gì.

Insert theo thứ tự (tốt):
Range 1: min=Jan, max=Jan15  ─┐
Range 2: min=Jan15, max=Feb  ─┤ không overlap
Range 3: min=Feb, max=Feb20  ─┘

Insert ngẫu nhiên (xấu):
Range 1: min=Jan, max=Dec  ─┐
Range 2: min=Jan, max=Dec  ─┤ overlap toàn bộ → không filter được
Range 3: min=Jan, max=Dec  ─┘

metrics là bảng flat (không partitioned), data insert theo thứ tự thời gian — đây là điều kiện lý tưởng để BRIN hoạt động hiệu quả nhất.

sql

CREATE INDEX idx_metrics_brin ON metrics USING BRIN (recorded_at)
WITH (pages_per_range = 128);  -- default, tăng lên nếu muốn index nhỏ hơn nữa

-- Xem query có dùng BRIN không
EXPLAIN SELECT * FROM metrics WHERE recorded_at >= '2024-02-01';

-- Xem summary của BRIN index (cần extension pgstattuple)
SELECT * FROM brin_page_items(get_raw_page('idx_metrics_brin', 2), 'idx_metrics_brin');

4. Hash

Chỉ hỗ trợ equality (=). Không hỗ trợ range, sort, hay NULL.

Hash function:
"gold"   → bucket 3
"silver" → bucket 7
"gold"   → bucket 3  ← cùng giá trị → cùng bucket → O(1)

B-tree: O(log n) — log(1,000,000) ≈ 20 bước
Hash:   O(1)     — nhanh hơn nhưng không đáng kể

Tại sao ít dùng:

B-tree hỗ trợ:          Hash chỉ hỗ trợ:
equality    ✅           equality    ✅
range       ✅           range       ❌
sort        ✅           sort        ❌
LIKE prefix ✅           LIKE        ❌

→ B-tree làm được mọi thứ Hash làm được
→ O(1) vs O(log n) không đáng kể trong thực tế
→ không đáng đánh đổi tính năng để lấy mức chênh lệch tốc độ nhỏ

Trước PG 10 không WAL-safe → crash có thể corrupt index. PG 10+ đã fix, nhưng B-tree vẫn được ưa dùng hơn vì hỗ trợ nhiều hơn với kích thước tương đương.

5. Chọn loại index

Bài toán	Index
Equality / range trên scalar (id, date, number)	B-tree (default)
`jsonb` tìm theo key/value	GIN
Array tìm theo phần tử	GIN
LIKE / ILIKE / fuzzy search	GIN + pg_trgm
Full-text search tiếng Anh	GIN + tsvector('english')
Full-text search tiếng Việt	GIN + tsvector('simple')
Nearest-neighbor, similarity sort	GiST + pg_trgm
Geo / PostGIS	GiST
Range overlap (daterange, tsrange)	GiST
Time-series insert theo thứ tự, bảng rất lớn	BRIN
Equality only, cần O(1)	Hash (hiếm dùng)

PostgreSQL — GIN / GiST / BRIN ​

1. GIN — Generalized Inverted Index ​

Dùng khi nào ​

Cách hoạt động ​

Trade-off ​

GIN Pending List (fastupdate) ​

ILIKE và index ​

Full-text search ​

2. GiST — Generalized Search Tree ​

Dùng khi nào ​

Cách hoạt động ​

GIN vs GiST với pg_trgm ​

3. BRIN — Block Range Index ​

Dùng khi nào ​

Cách hoạt động ​

Điều kiện để BRIN hiệu quả ​

4. Hash ​

5. Chọn loại index ​

PostgreSQL — GIN / GiST / BRIN

1. GIN — Generalized Inverted Index

Dùng khi nào

Cách hoạt động

Trade-off

GIN Pending List (fastupdate)

ILIKE và index

Full-text search

2. GiST — Generalized Search Tree

Dùng khi nào

Cách hoạt động

GIN vs GiST với pg_trgm

3. BRIN — Block Range Index

Dùng khi nào

Cách hoạt động

Điều kiện để BRIN hiệu quả

4. Hash

5. Chọn loại index