Indexes — B-tree, Hash, GIN, Composite

1. Vì sao cần Index?

Bảng users có 10 triệu dòng, cột email không có index. Câu query:

SELECT * FROM users WHERE email = 'alice@example.com';

DB phải Sequential Scan: đọc toàn bộ 10 triệu dòng từ disk, so sánh từng cái — có thể mất nhiều giây đến phút.

Với B-tree index trên email, DB chỉ cần log₂(10⁷) ≈ 23 bước để tìm. Mỗi bước đọc 1 page (~8KB) → ~1ms tổng.

Khác biệt: 30 giây vs 1 mili-giây = 30 000 lần.

1.1. Index không miễn phí

• Tốn dung lượng disk — index thường 10–30% kích thước bảng. 10 index = thêm 1–3× dung lượng.
• Làm chậm INSERT/UPDATE/DELETE — mỗi thao tác phải cập nhật cả index. Bảng càng nhiều index, ghi càng chậm.
• Tốn RAM — index "nóng" được DB cache vào shared_buffers. Quá nhiều → thiếu RAM cho bảng chính.
• Mất thời gian build — CREATE INDEX trên bảng 1 tỉ dòng có thể mất nhiều giờ.

Quy tắc: chỉ tạo index cho cột thực sự được query thường xuyên. Đừng "đánh index phòng xa".

2. B-tree — index mặc định

"B" trong B-tree = "Balanced" (cây cân bằng), không phải "Binary". B-tree là cây nhiều con (mỗi node có nhiều key) và luôn được giữ cân bằng qua mỗi insert/delete.

2.1. Đặc tính

• Tra cứu O(log n) — chỉ cần ~log_fanout(N) bước. Với fanout 200 và 10⁹ dòng: ~5 bước.
• Range scan O(log n + k) — leaves được link doubly để duyệt khoảng (WHERE x BETWEEN A AND B).
• Sorted output — duyệt B-tree → dữ liệu đã sorted theo key. ORDER BY index_col miễn sort.
• Insert balanced — page split khi đầy, propagate lên cha.

2.2. B-tree trong Postgres dùng được cho:

• =, <, <=, >, >=
• BETWEEN
• IN
• IS NULL / IS NOT NULL
• LIKE 'prefix%' (chỉ với prefix — KHÔNG '%suffix')
• ORDER BY col

2.3. Tạo B-tree

-- Mặc định CREATE INDEX là B-tree
CREATE INDEX idx_users_email ON users(email);

-- Tương đương:
CREATE INDEX idx_users_email ON users USING BTREE (email);

-- Multi-column (composite):
CREATE INDEX idx_orders_user_created ON orders(user_id, created_at DESC);

-- DESC, NULLS FIRST/LAST:
CREATE INDEX idx_users_created ON users(created_at DESC NULLS LAST);

-- UNIQUE B-tree:
CREATE UNIQUE INDEX idx_users_email_uniq ON users(LOWER(email));

-- CONCURRENTLY (không lock writes — luôn dùng ở production):
CREATE INDEX CONCURRENTLY idx_orders_status ON orders(status);

3. Hash index

Map key → bucket qua hash function. Tra cứu O(1) trung bình.

3.1. Khi dùng?

• Chỉ cho =, KHÔNG cho range/order.
• Trên Postgres < 10: hash index không WAL, mất khi crash → không khuyến nghị.
• Postgres 10+: hash index đã ổn, nhưng B-tree thường vẫn nhanh ngang và linh hoạt hơn.

CREATE INDEX idx_users_email_hash ON users USING HASH (email);

Thực hành: hầu như không cần. Chỉ dùng khi profiling chỉ ra B-tree không đủ và workload chỉ có equality.

4. GIN / GiST / BRIN — index chuyên biệt

4.1. GIN (Generalized Inverted Index)

"Inverted" — như index ngược trong sách: từ → các trang chứa từ đó. Phù hợp với cột chứa nhiều giá trị nhỏ:

• Full-text search (cột tsvector)
• Array (tags TEXT[])
• JSONB

-- Full-text:
ALTER TABLE posts ADD COLUMN search_vector tsvector
  GENERATED ALWAYS AS (to_tsvector('simple', title || ' ' || body)) STORED;
CREATE INDEX idx_posts_search ON posts USING GIN(search_vector);

SELECT * FROM posts
WHERE search_vector @@ to_tsquery('database & (postgres | mysql)');

-- Array:
CREATE INDEX idx_posts_tags ON posts USING GIN(tags);
SELECT * FROM posts WHERE tags @> ARRAY['sql','tutorial'];

-- JSONB:
CREATE INDEX idx_users_meta ON users USING GIN(meta);
SELECT * FROM users WHERE meta @> '{"role":"admin"}';
SELECT * FROM users WHERE meta -> 'preferences' ->> 'theme' = 'dark';

4.2. GiST (Generalized Search Tree)

Cây tổng quát hỗ trợ các kiểu phức tạp: geometry, range, full-text. Tốt hơn GIN cho:

• Spatial (PostGIS) — &&, ST_Contains
• Range types — tstzrange && (overlap)
• K-nearest neighbor

CREATE INDEX idx_bookings_during ON bookings USING GIST (during);
SELECT * FROM bookings WHERE during && '[2026-05-09,2026-05-10)'::tstzrange;

4.3. BRIN (Block Range Index)

Cực nhỏ, lưu min/max của mỗi block (page) chứ không từng dòng. Phù hợp dữ liệu tự nhiên sorted (ví dụ created_at luôn tăng).

CREATE INDEX idx_logs_created_brin ON logs USING BRIN(created_at);

Index này có thể nhỏ hơn 1000× B-tree, đổi lại scan rộng hơn. Phù hợp khi bảng 1+ tỉ dòng và bạn muốn index "rẻ".

4.4. So sánh nhanh

5. Bitmap Index Scan (planner technique)

Khác với MySQL/Oracle có bitmap index như loại index riêng, Postgres có Bitmap Index Scan — kỹ thuật planner tạo bitmap tạm thời từ B-tree để kết hợp nhiều điều kiện.

SELECT * FROM users
WHERE country = 'VN' AND age > 25;

-- Plan có thể là:
-- BitmapAnd
--   Bitmap Index Scan idx_country (country='VN')   → bitmap A
--   Bitmap Index Scan idx_age (age > 25)            → bitmap B
-- Bitmap Heap Scan: A AND B → đọc dòng thật

Hiệu quả khi 1 index không đủ chọn lọc, 2 index AND lại sẽ chọn lọc cao.

6. Composite Index — index nhiều cột

Một index trên nhiều cột. Thứ tự cột cực kỳ quan trọng.

CREATE INDEX idx_orders_user_created ON orders(user_id, created_at DESC);

Index này phục vụ tốt:

• WHERE user_id = 5
• WHERE user_id = 5 AND created_at > '2026-01-01'
• WHERE user_id = 5 ORDER BY created_at DESC

NHƯNG không tốt cho:

• WHERE created_at > '2026-01-01' (không có user_id, prefix mismatch — DB có thể skip-scan nhưng kém)

6.1. Quy tắc thứ tự cột

Equality trước, range sau.

-- Query: WHERE country = 'VN' AND age > 25
-- ✓ Tốt:  CREATE INDEX ... ON users(country, age);   ← equality first
-- ✗ Tệ:  CREATE INDEX ... ON users(age, country);   ← range first, equality không dùng

Lý do: trong B-tree composite, các dòng được sắp theo cột 1, rồi cột 2. Equality trên cột 1 thu hẹp khoảng → range trên cột 2 trở thành sequential scan trong khoảng nhỏ. Ngược lại, range trên cột 1 → cột 2 không sắp cùng → không scan tuần tự được.

6.2. Số cột trong composite index

Hiếm khi cần > 3 cột. Nhiều cột = index lớn = ghi chậm + ít phù hợp với nhiều query.

7. Covering Index — INCLUDE clause

Index chứa thêm cột non-key để query có thể được trả lời chỉ từ index, không đụng heap. Gọi là "Index-Only Scan".

-- Query phổ biến:
SELECT id, email FROM users WHERE country = 'VN';

-- Index thường: lookup index → đọc heap để lấy email
CREATE INDEX idx_country ON users(country);

-- Covering: include email vào index, không cần đọc heap
CREATE INDEX idx_country_inc ON users(country) INCLUDE (email);

Lợi: 2× nhanh trở lên cho query phù hợp. Hại: index lớn hơn.

Trước Postgres 11 (chưa có INCLUDE), người ta tạo composite index (country, email) để cùng đạt hiệu ứng — nhưng cột email trở thành part of key, ảnh hưởng sort order. INCLUDE rõ ràng hơn.

8. Partial Index — chỉ index một phần dữ liệu

Index có WHERE clause — chỉ index các dòng thỏa.

-- 90% user đã verify; query luôn lọc unverified:
CREATE INDEX idx_users_unverified ON users(email)
  WHERE email_verified = FALSE;

-- Soft delete: chỉ index dòng chưa xóa:
CREATE INDEX idx_orders_active ON orders(created_at)
  WHERE deleted_at IS NULL;

-- Status nóng:
CREATE INDEX idx_orders_pending ON orders(user_id, created_at)
  WHERE status = 'pending';

Lợi: index nhỏ hơn nhiều → tra cứu nhanh hơn, tốn ít disk/RAM. Điều kiện: query phải có cùng predicate trong WHERE để planner dùng được index.

9. Functional / Expression Index

Index trên kết quả 1 hàm/expression.

-- Email case-insensitive:
CREATE UNIQUE INDEX idx_users_email_lower ON users(LOWER(email));
SELECT * FROM users WHERE LOWER(email) = LOWER('ALICE@x.com');

-- JSONB attribute:
CREATE INDEX idx_users_role ON users((meta->>'role'));
SELECT * FROM users WHERE meta->>'role' = 'admin';

-- Date trunc:
CREATE INDEX idx_orders_month ON orders(DATE_TRUNC('month', created_at));
SELECT COUNT(*) FROM orders
WHERE DATE_TRUNC('month', created_at) = '2026-05-01';

Lưu ý: query phải dùng đúng expression như index. WHERE email = ... không match idx ON LOWER(email).

10. Selectivity — chìa khóa quyết định index

Selectivity = số dòng kết quả / tổng số dòng. Càng nhỏ càng tốt cho index.

• Cột email trên 10M user, mỗi email unique → selectivity = 1/10M = cực thấp → index cực hữu ích.
• Cột gender với 2 giá trị → selectivity = 50% → index gần như vô dụng, planner sẽ chọn Seq Scan.
• Cột status với 80% dòng = 'paid', 20% = 'pending' → index trên 'pending' (rare value) hữu ích, trên 'paid' không.

Quy tắc: nếu DB ước tính query sẽ trả > 5–10% bảng, planner sẽ Sequential Scan thay vì dùng index. Random IO của index lookup tốn hơn sequential disk read.

Đó là lý do Partial Index mạnh — bạn ép index chỉ chứa phần selective.

11. Khi nào index KHÔNG được dùng (mặc dù đã tạo)?

11.1. Function trên cột

-- ❌ Index trên `email` không được dùng:
SELECT * FROM users WHERE LOWER(email) = 'a@b.com';

-- ✓ Functional index, hoặc:
SELECT * FROM users WHERE email = 'A@B.com';  -- nhưng case-sensitive!

11.2. Implicit type cast

-- email là VARCHAR, nhưng query dùng số:
SELECT * FROM users WHERE email = 12345;  -- DB cast: ::text
-- Có thể skip index do mismatch.

11.3. OR trên 2 cột khác nhau

SELECT * FROM users WHERE email = 'a@x' OR phone = '0912';
-- Index trên email và phone riêng lẻ — không phải lúc nào planner cũng OR-bitmap-scan.
-- Có thể fallback Seq Scan. Cách thay thế: UNION 2 query.

11.4. Wildcard prefix LIKE

-- ❌ Không dùng B-tree:
SELECT * FROM users WHERE email LIKE '%@gmail.com';
-- Cần GIN trigram (pg_trgm extension) hoặc full-text search.

-- ✓ Dùng B-tree được:
SELECT * FROM users WHERE email LIKE 'alice%';

11.5. Selectivity quá cao

Nếu query trả về > 5–10% bảng, planner thường chọn Seq Scan. Đó là đúng, không phải bug.

11.6. Statistics outdated

Postgres dùng statistics (do ANALYZE thu thập) để estimate. Sau load lớn, chạy:

ANALYZE users;
-- Hoặc chỉ 1 cột:
ANALYZE users (email);

11.7. Composite mismatch order

CREATE INDEX idx ON orders(user_id, created_at);

-- ✓ Dùng:
WHERE user_id = 5;
WHERE user_id = 5 AND created_at > '2026-01-01';

-- ✗ Không dùng tốt:
WHERE created_at > '2026-01-01';  -- prefix là user_id, không có → không tận dụng được

11.8. NULL với constraint

Default Postgres index B-tree có bao gồm NULL. Nhưng WHERE col IS NULL với index không-partial có thể không hiệu quả nếu nhiều NULL.

12. EXPLAIN cơ bản — đo xem index có được dùng

Bạn không "biết" index được dùng — bạn kiểm tra bằng EXPLAIN.

EXPLAIN SELECT * FROM users WHERE email = 'alice@x.com';

-- Output:
-- Index Scan using idx_users_email on users  (cost=0.42..8.44 rows=1 width=85)
--   Index Cond: (email = 'alice@x.com'::text)

Điểm quan trọng:

• Index Scan — index được dùng ✓
• Seq Scan — index KHÔNG được dùng (hoặc không có)
• Bitmap Index Scan — kết hợp nhiều index
• Index Only Scan — covering index, không đụng heap

12.1. EXPLAIN ANALYZE — chạy thật, đo thật

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@x.com';

-- Index Scan using idx_users_email on users
--   (cost=0.42..8.44 rows=1 width=85)
--   (actual time=0.024..0.025 rows=1 loops=1)
--   Index Cond: (email = 'alice@x.com'::text)
-- Planning Time: 0.123 ms
-- Execution Time: 0.045 ms

"actual" vs "estimate": planner đoán dựa trên statistics. Nếu actual lệch estimate quá nhiều (10× trở lên), nghĩa là statistics outdated → chạy ANALYZE.

Sẽ học EXPLAIN sâu hơn ở Ch8.

13. Bài tập

Schema:

CREATE TABLE orders (
  id BIGSERIAL PRIMARY KEY,
  user_id BIGINT, status VARCHAR(20),
  total DECIMAL(10,2),
  created_at TIMESTAMPTZ DEFAULT NOW(),
  deleted_at TIMESTAMPTZ
);
-- 100M dòng, 1M user, status có 5 giá trị (paid 70%, pending 5%, ...)

Đề xuất index cho từng query sau, giải thích lựa chọn:

1. SELECT * FROM orders WHERE user_id = ? ORDER BY created_at DESC LIMIT 20; (timeline user)
2. SELECT * FROM orders WHERE status = 'pending'; (queue xử lý)
3. SELECT * FROM orders WHERE status = 'paid' AND created_at > '2026-05-01'; (báo cáo)
4. SELECT id, total FROM orders WHERE user_id = ?; (lấy nhanh số tiền của user)
5. SELECT * FROM orders WHERE deleted_at IS NULL ORDER BY created_at DESC LIMIT 100; (recent active)

Bài 2. Vì sao composite (status, user_id) phục vụ WHERE status='X' AND user_id=Y tốt nhưng phục vụ WHERE user_id=Y kém? Có nên đổi sang (user_id, status)?

Bài 3. Bạn có 1 index idx_email ON users(email). Query SELECT * FROM users WHERE LOWER(email) = LOWER('A@B.com') chạy chậm. Vì sao? Sửa thế nào?

Bài 4. Cho bảng logs(id, level, message, created_at) với 1 tỉ dòng và created_at tăng dần. Đề xuất loại index phù hợp + lý do.

Bài 5. Khi nào nên dùng INCLUDE thay vì thêm cột vào key của composite index?

14. Quiz