PostgreSQL — B-tree Index

1. Cấu trúc B-tree

Root node (1 page 8KB)
      ↓
Internal nodes (nhiều page 8KB)
      ↓
Leaf nodes (nhiều page 8KB) → chứa key + ctid trỏ đến row thật

Mỗi node = 1 page = 8KB cố định, bất kể chứa bao nhiêu row.

Leaf nodes chứa key + ctid (con trỏ đến row trong heap), không chứa data thật. Khi tìm được key ở leaf → dùng ctid để fetch row từ heap table.

---

2. Page Split

Xảy ra khi insert row mới vào leaf node đã đầy 8KB:

Leaf node đầy:
[10, 15, 20, 25]  ← 8KB, không còn chỗ

Insert key 18:
→ split thành 2 leaf node:
   Leaf A: [10, 15]      ← ~50%
   Leaf B: [18, 20, 25]  ← ~50%
→ key giữa (18) đẩy lên parent node

Cascade split:

Parent còn chỗ → thêm vào parent → xong
Parent cũng đầy → parent split → cascade lên trên
Root đầy → split root → cây tăng thêm 1 tầng

---

3. Index Bloat

Hệ quả của page split và DELETE/UPDATE:

• Nhiều lần split → nhiều page chỉ đầy ~50%
• DELETE/UPDATE → dead entries chiếm chỗ trong page nhưng không được xóa ngay

→ Index phình to hơn cần thiết → range query phải scan nhiều page hơn → chậm → tốn RAM (shared_buffers phải cache nhiều page hơn)

Page = container cố định 8KB — dù trống vẫn chiếm 8KB trên disk:

Page đầy:   [row1, row2, row3, ...]  = 8KB
Page 1 row: [row1, _,    _,    ...]  = 8KB
Page trống: [_,    _,    _,    ...]  = 8KB

Bloat ảnh hưởng query nào nhiều nhất:

WHERE id = 1               → equality → 1 leaf node → ít ảnh hưởng
WHERE id BETWEEN 1 AND 100 → range    → nhiều leaf node → ảnh hưởng rõ rệt

---

4. Xử lý Bloat

Cách	Tác dụng	Lock
VACUUM	Dọn dead entries, tái sử dụng slot	Không
REINDEX CONCURRENTLY	Rebuild index, xóa bloat hoàn toàn	Không
VACUUM FULL	Rebuild table + index, trả disk space	Có
pg_repack	Giống VACUUM FULL nhưng không lock	Không

Tại sao VACUUM không trả disk space:

Page ở giữa file → không thể xóa, phải dịch chuyển toàn bộ data phía sau
Page ở cuối file → VACUUM tự truncate, trả disk space
→ chỉ VACUUM FULL / pg_repack mới rewrite toàn bộ file

Kiểm tra index bloat:

-- Xem kích thước index so với table
SELECT
  indexrelname,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
  pg_size_pretty(pg_relation_size(indrelid))   AS table_size,
  idx_scan
FROM pg_stat_user_indexes
JOIN pg_index USING (indexrelid)
WHERE schemaname = 'public'
ORDER BY pg_relation_size(indexrelid) DESC;

-- Rebuild index không lock
REINDEX INDEX CONCURRENTLY idx_name;

---

5. Deduplication (PG 13+)

Với column có nhiều giá trị trùng nhau (low cardinality), B-tree mặc định tạo 1 entry riêng cho mỗi row — lãng phí space.

PG 13+ gộp các entry trùng key thành 1 entry duy nhất chứa danh sách ctid:

Trước dedup (PG 12):           Sau dedup (PG 13+):
[status='active', ctid=1]      [status='active', ctid=[1,4,7,9,...]]
[status='active', ctid=4]      [status='pending', ctid=[2,5,8,...]]
[status='active', ctid=7]
[status='pending', ctid=2]
...

→ Index nhỏ hơn đáng kể → ít page hơn → ít I/O hơn khi scan.

Dedup bật mặc định. Tắt nếu workload toàn unique values (không có lợi gì):

CREATE INDEX idx_status ON orders (status) WITH (deduplicate_items = off);

---

6. Index-Only Scan

Bình thường index scan gồm 2 bước:

1. Tìm key trong index → lấy ctid
2. Dùng ctid fetch row từ heap table  ← thêm 1 lần I/O

Index-only scan bỏ qua bước 2 — khi tất cả column query cần đều có sẵn trong index:

CREATE INDEX idx_orders ON orders (customer_id, status, total_amount);

-- Index-only scan: tất cả column đều trong index
SELECT customer_id, status, total_amount
FROM orders
WHERE customer_id = 123;

-- Vẫn phải đọc heap: created_at không có trong index
SELECT customer_id, created_at
FROM orders
WHERE customer_id = 123;

Nhưng có điều kiện — Visibility:

Index không chứa thông tin xmin/xmax → không biết row có visible với transaction hiện tại không → cần check thêm.

PostgreSQL dùng Visibility Map để giải quyết:

Visibility Map = file riêng biệt trên disk ({heap_file}_vm)
→ 1 bit cho mỗi page trong heap

bit = 1 (all-visible): toàn bộ row trong page đều live
                       → index-only scan an toàn, bỏ qua heap ✅
bit = 0: page có thể có dead rows hoặc uncommitted rows
                       → phải xuống heap check xmin/xmax ❌

Ví dụ:

Page 0: [row1(live), row2(live), row3(live)] → bit=1 → bỏ qua heap
Page 1: [row4(live), row5(dead), row6(live)] → bit=0 → phải xuống heap
Page 2: [row7(live), row8(live), row9(live)] → bit=1 → bỏ qua heap

Flow index-only scan:

Tìm row → check Visibility Map (bit của page đó)
    ↓
bit = 1                      bit = 0
    ↓                            ↓
Lấy từ index luôn           Xuống heap check xmin/xmax
Không cần đọc heap          Dù chỉ lấy field có trong index!
    ↓                            ↓
Nhanh ✅                    Chậm hơn ❌

Visibility Map được lưu ở đâu:

Disk:
├── heap file    (16384)     ← data thật
├── vm file      (16384_vm)  ← visibility map, rất nhỏ (~1 bit/page)
└── index file   (16385)     ← B-tree

Visibility Map nhỏ đến mức gần như luôn nằm trong shared_buffers
→ check bit gần như free, không tốn I/O

Autovacuum cập nhật Visibility Map:

VACUUM chạy → page nào toàn live rows → đánh dấu bit=1
→ index-only scan bỏ qua heap page đó hoàn toàn

Sau khi VACUUM dọn dead rows trong page 1:
Page 1: [row4(live), _(free), row6(live)] → bit=1
→ lần sau index-only scan bỏ qua heap ✅

Thực tế:

Bảng read-heavy / VACUUM thường xuyên
→ nhiều bit=1 → index-only scan hiệu quả tối đa

Bảng write-heavy (nhiều UPDATE/DELETE)
→ nhiều bit=0 → liên tục phải xuống heap
→ gần như không khác gì index scan thường

Covering index với INCLUDE — đưa thêm column vào index mà không làm key:

-- created_at không phải key (không filter/sort được), chỉ để tránh heap lookup
CREATE INDEX idx_orders_covering ON orders (customer_id)
INCLUDE (status, total_amount, created_at);

---

7. Correlation

Đo mức độ thứ tự vật lý của rows trên disk khớp với thứ tự của index key.

Correlation = 1.0  → rows nằm trên disk đúng thứ tự index
                   → index scan đọc page tuần tự → nhanh

Correlation = 0.0  → rows nằm rải rác
                   → index scan nhảy lung tung giữa các page → chậm (nhiều random I/O)

Correlation = -1.0 → ngược hoàn toàn (cũng là sequential, chỉ ngược chiều)

Planner dùng correlation để tính cost của index scan — correlation thấp → planner có thể bỏ qua index và dùng Seq Scan thay thế (đôi khi đúng đắn).

-- Xem correlation của các column
SELECT tablename, attname, correlation
FROM pg_stats
WHERE tablename = 'orders'
ORDER BY abs(correlation) DESC;

Column id hay created_at (insert theo thứ tự) thường có correlation gần 1.0. Column status, category thường gần 0.

Fix correlation thấp bằng CLUSTER:

CLUSTER users USING users_email_key;
ANALYZE users;  -- bắt buộc chạy sau CLUSTER, PG không tự chạy

Trade-off khi dùng CLUSTER:

→ lock table hoàn toàn (ACCESS EXCLUSIVE)
→ correlation giảm dần sau khi có INSERT/UPDATE mới
→ phải CLUSTER lại định kỳ
→ thực tế ít dùng trên production

---

8. Bitmap Index Scan

Nằm giữa Index Scan và Seq Scan — dùng khi correlation thấp + nhiều rows:

Index Scan thường:
→ tìm từng ctid trong index → nhảy lung tung giữa heap pages
→ correlation thấp → random I/O nhiều → chậm

Bitmap Index Scan:
Bước 1: duyệt index → tạo bitmap (bản đồ page nào cần đọc)
        bitmap: [page3: có, page7: có, page15: có...]
Bước 2: đọc heap theo bitmap, tuần tự từng page
        → Recheck Cond: kiểm tra lại điều kiện trong page

→ tốt hơn Index Scan khi correlation thấp
→ tốt hơn Seq Scan khi chỉ cần 1 phần nhỏ của table

Ví dụ thực tế:

-- full_name correlation = 0.003 → Bitmap Index Scan
EXPLAIN SELECT * FROM users WHERE full_name = 'Nguyen Van A';

Bitmap Heap Scan on users
  Recheck Cond: (full_name = 'Nguyen Van A')
  → Bitmap Index Scan on idx_users_name_trgm

---

9. Khi nào planner bỏ qua index

Planner luôn chọn plan có cost thấp nhất — đôi khi Seq Scan rẻ hơn index scan.

Low selectivity — WHERE condition match quá nhiều row:

-- Bảng 1 triệu row, 800k row có status='active'
-- Index scan: 800k lần random I/O → đắt hơn đọc tuần tự cả bảng
SELECT * FROM orders WHERE status = 'active';           -- → Seq Scan
SELECT * FROM orders WHERE status = 'cancelled' LIMIT 10; -- → Index Scan (ít row)

Small table — bảng nhỏ fit vào vài page, Seq Scan nhanh hơn overhead của index lookup.

Statistics cũ — planner ước lượng sai số rows → cost tính sai → chọn plan sai. Fix bằng ANALYZE.

Function trên column không có expression index:

-- Không dùng index dù idx_email tồn tại
WHERE lower(email) = 'user@example.com'

-- Fix: tạo expression index
CREATE INDEX idx_email_lower ON users (lower(email));

Cost được tính từ:

seq_page_cost    = 1.0  (đọc page tuần tự)
random_page_cost = 4.0  (đọc page ngẫu nhiên, tốn hơn)

Seq Scan:   đọc 1000 page tuần tự  → cost = 1000 * 1.0 = 1000
Index Scan: 577,000 page ngẫu nhiên → cost = 577,000 * 4.0 = 2,308,000
→ Seq Scan rẻ hơn → chọn Seq Scan

Ép planner dùng index để debug (không dùng trên production):

SET enable_seqscan = off;
EXPLAIN SELECT * FROM orders WHERE status = 'active';
SET enable_seqscan = on;