Composite Index — Multi-column Index

Multi-column index: leftmost prefix quyết định index có được dùng hay không

Một index trên (a, b, c) không phải là "ba index gộp lại" — nó là một B-tree duy nhất, các entry sắp xếp theo thứ tự từ điển của bộ ba (a, b, c). Hệ quả thẳng tay: index này phục vụ tốt cho predicate có a, hoặc a AND b, hoặc a AND b AND c, nhưng gần như vô dụng khi predicate chỉ có b hoặc chỉ có c. Hiểu sai quy tắc leftmost prefix là lý do phổ biến nhất khiến team đánh xong index rồi EXPLAIN vẫn ra Seq Scan, vẫn nghĩ "chắc do planner sai" thay vì nhận ra mình đặt sai thứ tự cột.

Cơ chế hoạt động

B-tree trong Postgres lưu các entry đã sort. Với index trên (status, created_at), các leaf page chứa key được sort: trước tiên theo status, trong cùng status thì theo created_at. Khi planner thấy predicate WHERE status = 'pending' AND created_at > '2026-01-01', nó đi xuống cây tìm vị trí bắt đầu của ('pending', '2026-01-01') rồi quét ngang dọc theo sibling pointer — cả hai điều kiện đều được áp tại tầng index. Nhưng khi predicate là WHERE created_at > '2026-01-01' (không có status), không có "điểm vào" nào trên cây: các entry cùng created_at nằm rải rác khắp các leaf khác nhau, mỗi nhóm dưới một status riêng. Postgres docs về multicolumn index nói thẳng: index hiệu quả nhất khi predicate có ràng buộc trên leading columns.

CREATE TABLE jobs (
  id          bigserial PRIMARY KEY,
  status      text        NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  worker_id   bigint,
  payload     jsonb
);

CREATE INDEX jobs_status_created_idx
  ON jobs (status, created_at DESC);

Quy tắc đầy đủ với B-tree multicolumn:

• Predicate dùng được leftmost prefix (status) hoặc (status, created_at) → Index Scan hiệu quả.
• Predicate chỉ trên cột sau (created_at) → index có thể vẫn quét được nhưng phải duyệt toàn bộ leaf để filter; với cardinality cao của status, chi phí xấp xỉ seq scan. Postgres docs gọi đây là use-case "much less efficient".
• Cột đầu là equality, cột sau là range: thứ tự tối ưu. Đảo lại ((created_at, status)) phá vỡ ngay cả khi vẫn có cả hai điều kiện, vì range trên cột đầu khiến phần status = ? ở cột sau phải kiểm bằng Filter, không phải Index Cond.
• IN (...) và = ANY(...) ở cột đầu vẫn dùng được index — planner mở rộng thành nhiều index scan.
• ORDER BY khớp với thứ tự + chiều của index → không tốn sort. ORDER BY status, created_at DESC khớp với (status ASC, created_at DESC).

EXPLAIN cho thấy sự khác biệt: phần Index Cond: là những điều kiện được áp ngay trong index (giảm số tuple lấy lên), Filter: là điều kiện áp sau khi đã lấy tuple. Khi điều kiện đáng ra nằm trong Index Cond lại nhảy xuống Filter, đó là tín hiệu cột không khớp leftmost prefix hoặc opclass sai.

Vấn đề gặp trong production

Failure mode 1: đảo thứ tự cột "cho có cảm giác đúng". Đây là lỗi kinh điển. Team có query WHERE tenant_id = ? AND status = 'active' AND created_at > ? và đánh index (created_at, tenant_id, status) vì "created_at là cột bị filter range, nó quan trọng nhất". Kết quả: index gần như không bao giờ được dùng cho predicate này, planner chọn seq scan hoặc một index khác xấu hơn.

-- Sai: range column đứng trước, equality column đứng sau
CREATE INDEX jobs_bad_idx ON jobs (created_at, status, worker_id);
-- Query: WHERE status = 'pending' AND worker_id = 42
--          AND created_at > now() - interval '1 hour'
-- → Index Cond chỉ chứa được khoảng created_at; status/worker_id rơi vào Filter.

-- Đúng: equality trước, range sau cùng
DROP INDEX jobs_bad_idx;
CREATE INDEX jobs_good_idx ON jobs (status, worker_id, created_at DESC);
-- Index Cond chứa cả ba; range trên created_at quét sibling pointer
-- trong nhóm (status='pending', worker_id=42) là một dải liên tiếp.

Quy tắc: equality trước, range sau, và trong nhóm equality thì cột selectivity cao hơn đứng trước để chia nhỏ tập kết quả nhanh hơn.

Failure mode 2: thừa index vì không nhận ra prefix bao trùm. Có index (tenant_id, user_id, created_at) rồi nhưng team đánh thêm (tenant_id) và (tenant_id, user_id) vì "để dành cho query khác". Hai index sau là redundant — index đầu đã phục vụ được mọi truy vấn mà hai index sau phục vụ. Cái giá: write amplification, storage phí, vacuum chậm hơn. Cách phát hiện: nhìn pg_stat_user_indexes, các index có idx_scan cực thấp trong khi index dài hơn ở cùng bảng có idx_scan cao — dấu hiệu nó bị "che" bởi index khác.

Failure mode 3: tin vào skip scan trên Postgres. Một số database (MySQL từ 8.0, Oracle) có index skip scan — planner có thể bỏ qua cột đầu nếu cardinality thấp. Postgres B-tree truyền thống không có skip scan; predicate thiếu cột đầu = không dùng index hiệu quả được. Có người ngạc nhiên khi cùng schema chạy ngon trên MySQL nhưng chậm trên Postgres. Workaround cổ điển: viết lại query với IN (SELECT DISTINCT leading_col FROM ...) để buộc planner mở rộng, hoặc tạo thêm một index không có cột đầu nếu query đó thật sự quan trọng.

Failure mode 4: cột text với collation không khớp. Multicolumn index trên (email, created_at) với database collation en_US.UTF-8 không phục vụ WHERE email LIKE 'foo%' AND created_at > ?. B-tree dùng collation locale để sort, không tương thích với pattern match byte-by-byte. Phải dùng text_pattern_ops ở cột đầu: CREATE INDEX ... (email text_pattern_ops, created_at).

Failure mode 5: INCLUDE bị nhầm thành key column. Cột trong INCLUDE chỉ là payload trong leaf, không tham gia sort, không phục vụ predicate filter. Có người viết CREATE INDEX ... ON jobs (status) INCLUDE (created_at) rồi mong query WHERE status = 'pending' AND created_at > ? dùng created_at để giảm số entry quét — không. created_at ở INCLUDE chỉ giúp khi planner đã chọn được entry rồi và muốn tránh đi heap (index-only scan). Để filter, created_at phải là key column thực sự.

Cách debug và monitor

Triệu chứng cần biết: query mới deploy bỗng chậm gấp nhiều lần, plan đổi từ Index Scan sang Seq Scan hoặc sang một Bitmap Index Scan trên index khác; trong khi đó index "đáng ra phải dùng" có idx_scan không tăng.

Công cụ cốt lõi:

• EXPLAIN (ANALYZE, BUFFERS) — đọc kỹ phần Index Cond: và Filter:. Nếu một cột có trong index nhưng xuất hiện trong Filter: thay vì Index Cond:, prefix bị vỡ. Rows Removed by Filter cao là dấu hiệu phải lấy quá nhiều tuple lên rồi mới lọc — thiết kế index sai. Buffers: shared hit/read cho biết bao nhiêu page phải đọc; với một query có index khớp tốt, con số này nhỏ.
• pg_stat_user_indexes — idx_scan đếm số lần index được dùng. Sau khi tạo index mới, để workload thật chạy vài giờ rồi check; nếu idx_scan = 0 nghĩa là planner không chọn nó (sai thứ tự cột, sai opclass, hoặc query thực tế khác giả định).
• pg_statio_user_indexes — idx_blks_hit vs idx_blks_read cho index hit ratio. Tỉ lệ hit thấp với index nóng nghĩa là index không vừa shared_buffers; cân nhắc tăng shared_buffers hoặc giảm size index (bỏ cột thừa, dùng partial).
• pg_stat_statements — query nào tốn nhiều total_exec_time; chiếu sang plan để biết nó có dùng index hay không. Đây là input để quyết định cần index nào, không phải đoán.
• hypopg extension — tạo hypothetical index ảo, hỏi planner "nếu có index này thì plan đổi không?" mà không trả cost CREATE INDEX thực. Hữu ích khi cân nhắc thêm hoặc đổi thứ tự cột trên bảng nhiều tỉ row.

Rule phòng ngừa:

• Mọi CREATE INDEX đa cột phải có một query mẫu kèm theo trong commit message; reviewer chiếu thứ tự cột với predicate của query đó.
• Sau mỗi đợt thêm index, audit unused index trong pg_stat_user_indexes sau 7–14 ngày workload thật.
• Khi có index dài (3+ cột), check xem các index ngắn hơn có phải là leftmost prefix không — nếu có, drop chúng.

Tradeoff

Multicolumn index đổi storage + write cost + sự lệ thuộc vào thứ tự cột lấy khả năng phục vụ predicate phức hợp trong một lần index lookup duy nhất. Lợi: predicate gồm nhiều equality + một range được phục vụ ngay tại index, không cần Bitmap And của hai index riêng (vốn tốn thêm bitmap construction và lossy heap recheck). Mất: chỉ một thứ tự cột cụ thể được tối ưu; query không khớp prefix không hưởng lợi gì từ cả index. So với chiến lược "một index per cột rồi để planner Bitmap And": multicolumn nhanh hơn cho predicate đã biết trước, nhưng linh hoạt kém — workload thay đổi là phải redesign. Khi predicate là tập hợp các cột thay đổi tự do (ad-hoc analytics), nhiều single-column index + bitmap and đôi khi là lựa chọn đúng dù chậm hơn cho từng query cụ thể. Quy tắc thực tế: equality trước, range sau, selectivity cao trước; mỗi multicolumn index phục vụ một (hoặc một family) query đã biết; không tạo "phòng khi cần"; đo pg_stat_user_indexes để gỡ cái không dùng.

Câu hỏi phỏng vấn

Leftmost prefix là gì, và vì sao index trên (a, b, c) không phục vụ được query WHERE b = ? AND c = ??

Leftmost prefix là quy tắc: một B-tree multicolumn index trên (a, b, c) chỉ phục vụ hiệu quả các predicate có ràng buộc bắt đầu từ cột trái nhất, tức là (a), (a, b), hoặc (a, b, c). Cơ chế: B-tree sắp xếp entry theo thứ tự từ điển của bộ (a, b, c), nên các bản ghi có cùng b nhưng a khác nhau không liền nhau trên leaf — chúng rải rác trong từng nhóm a riêng. Không có cột a trong predicate, planner không có điểm vào cụ thể nào trên cây, và phải quét toàn bộ leaf (gần như seq scan trên index) nếu vẫn cố dùng, hoặc bỏ index để seq scan heap. Postgres B-tree truyền thống không có skip scan như MySQL/Oracle, nên đừng kỳ vọng nó "tự xoay". Hậu quả production: team đánh index (tenant_id, status, created_at) rồi query WHERE status = 'pending' AND created_at > ? chậm như không có index, plan thành Seq Scan hoặc dùng index khác xấu hơn — fix bằng cách đảo thứ tự cột thành (status, tenant_id, created_at) nếu query đó nóng, hoặc thêm tenant_id IN (...) từ business context để có cột đầu. Điểm ăn điểm là nêu được: cơ chế (sort lexicographic + sibling pointer), quy tắc thiết kế (equality trước, range sau, selectivity cao trước), và cách phát hiện (Index Cond: vs Filter: trong EXPLAIN ANALYZE, kết hợp pg_stat_user_indexes.idx_scan).

Hands-on

Mục tiêu: tái hiện trường hợp đảo thứ tự cột làm index không được dùng, sửa, và xác nhận qua EXPLAIN. Dữ liệu: bảng jobs 5 triệu row mô phỏng job queue với status và created_at.

Dựng Postgres và nạp dữ liệu:

docker run -d --name pg-mc -e POSTGRES_PASSWORD=pw -p 5433:5432 postgres:16
sleep 5
docker exec -i pg-mc psql -U postgres <<'SQL'
CREATE TABLE jobs (
  id          bigserial PRIMARY KEY,
  status      text        NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  worker_id   bigint,
  payload     jsonb
);

INSERT INTO jobs (status, created_at, worker_id, payload)
SELECT
  (ARRAY['pending','running','done','failed','cancelled'])[1+floor(random()*5)],
  now() - (random() * interval '90 days'),
  (random()*1000)::bigint,
  jsonb_build_object('attempt', floor(random()*5))
FROM generate_series(1, 5000000);

ANALYZE jobs;
SQL

Đo baseline với query nóng (filter status + range created_at):

docker exec -i pg-mc psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, worker_id FROM jobs
WHERE status = 'pending' AND created_at > now() - interval '7 days'
ORDER BY created_at DESC LIMIT 50;"

Kết quả: Seq Scan trên jobs, đọc rất nhiều page, latency vài trăm ms tới vài giây tuỳ máy.

Tạo index sai thứ tự (range trước, equality sau):

docker exec -i pg-mc psql -U postgres -c "
CREATE INDEX jobs_bad_idx ON jobs (created_at DESC, status);"

docker exec -i pg-mc psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, worker_id FROM jobs
WHERE status = 'pending' AND created_at > now() - interval '7 days'
ORDER BY created_at DESC LIMIT 50;"

Plan có thể dùng Index Scan trên jobs_bad_idx nhưng phần status = 'pending' xuất hiện ở Filter:, không phải Index Cond:. Rows Removed by Filter sẽ rất cao — index quét nhiều entry không cần thiết.

Đổi sang thứ tự đúng (equality trước, range sau):

docker exec -i pg-mc psql -U postgres -c "
DROP INDEX jobs_bad_idx;
CREATE INDEX jobs_status_created_idx ON jobs (status, created_at DESC);"

docker exec -i pg-mc psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, worker_id FROM jobs
WHERE status = 'pending' AND created_at > now() - interval '7 days'
ORDER BY created_at DESC LIMIT 50;"

Bây giờ Index Cond: chứa cả hai điều kiện, Rows Removed by Filter về 0, Buffers: shared hit xuống chỉ vài chục page, latency rơi xuống sub-millisecond.

Test trường hợp predicate không có cột đầu để thấy leftmost prefix:

docker exec -i pg-mc psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status FROM jobs
WHERE created_at > now() - interval '7 days'
ORDER BY created_at DESC LIMIT 50;"

Plan quay về Seq Scan (hoặc một index khác) — index (status, created_at) không phục vụ được vì thiếu cột status ở predicate. Đây là minh chứng cho quy tắc leftmost prefix.

Thêm cột INCLUDE để chạy index-only scan:

docker exec -i pg-mc psql -U postgres -c "
DROP INDEX jobs_status_created_idx;
CREATE INDEX jobs_status_created_idx
  ON jobs (status, created_at DESC) INCLUDE (worker_id);
VACUUM ANALYZE jobs;"

docker exec -i pg-mc psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT worker_id FROM jobs
WHERE status = 'pending' AND created_at > now() - interval '7 days'
ORDER BY created_at DESC LIMIT 50;"

Plan đổi thành Index Only Scan, Heap Fetches: 0 (sau VACUUM set xong visibility map). Buffers xuống thấp hơn nữa vì không đi heap.

Audit index usage:

docker exec -i pg-mc psql -U postgres -c "
SELECT schemaname, relname, indexrelname, idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE relname = 'jobs'
ORDER BY idx_scan DESC;"

Sau khi chạy vài query nóng, jobs_status_created_idx phải có idx_scan tăng. Nếu đánh thêm một index "phòng hờ" như (worker_id) mà không có query thực tế, nó sẽ ở idx_scan = 0 — ứng viên drop.

Đo index hit ratio:

docker exec -i pg-mc psql -U postgres -c "
SELECT
  indexrelname,
  idx_blks_hit,
  idx_blks_read,
  round(100.0 * idx_blks_hit / nullif(idx_blks_hit + idx_blks_read, 0), 2) AS hit_ratio
FROM pg_statio_user_indexes
WHERE relname = 'jobs';"

Một index nóng nên có hit_ratio cao (gần 100%); ratio thấp với index thường xuyên dùng là dấu hiệu shared_buffers không đủ cho working set.

Dọn dẹp:

docker rm -f pg-mc