Index Scan — Access Method

Index Scan không tự nhiên nhanh: heap fetch và random IO mới quyết định

Index Scan chỉ là tầng đầu tiên của việc đọc dữ liệu — nó trả về TID (block + offset) trỏ vào heap, chứ chưa có row. Để có row thật, Postgres phải đi heap đọc tuple đó và kiểm visibility theo MVCC. Đây là heap fetch, và nó là nguồn của hầu hết các pha "có index mà vẫn chậm": một query đụng index nhưng kéo theo hàng vạn lần random read 8KB page. Hiểu rõ Index Scan, Bitmap Index Scan, Index Only Scan khác nhau ở đâu — và khi nào planner đổi giữa chúng — quyết định việc một query chạy vài ms hay vài giây.

Cơ chế hoạt động

Postgres có bốn access method chính cho việc đọc bảng có index:

• Seq Scan: quét toàn bộ heap theo thứ tự vật lý, áp Filter trên từng row. Sequential IO, không random.
• Index Scan: đi xuống B-Tree, mỗi entry leaf cho một TID, theo TID ra heap đọc tuple, kiểm visibility, trả về. Order theo index. Mỗi TID có thể là một random page read.
• Bitmap Index Scan + Bitmap Heap Scan: quét index để dựng bitmap các block cần đọc, sort theo block, rồi quét heap theo thứ tự block. Mất order của index, đổi lấy IO gần như sequential. Khi cần kết hợp nhiều index (BitmapAnd/BitmapOr), đây là cách duy nhất.
• Index Only Scan: nếu mọi cột query cần đã có trong index (key hoặc INCLUDE) và heap page tương ứng được đánh dấu all-visible trong visibility map, Postgres bỏ qua heap hoàn toàn. Nếu page không all-visible, vẫn phải đi heap để check MVCC — đó là Heap Fetches trong EXPLAIN.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total_cents FROM orders
WHERE customer_id = 42 AND created_at > now() - interval '30 days';

-- Index Scan using orders_customer_created_idx on orders
--   Index Cond: (customer_id = 42 AND created_at > ...)
--   Buffers: shared hit=18 read=120
-- Planning Time: 0.2 ms
-- Execution Time: 4.7 ms

Index Cond là điều kiện áp ngay trong B-Tree để bỏ entry không khớp trước khi đi heap. Buffers: shared hit=18 read=120 cho biết 18 page lấy từ cache, 120 page phải đọc từ đĩa — phần lớn trong số 120 này là heap fetch ngẫu nhiên theo từng TID. Một query "có index" nhưng read cao bất thường nghĩa là index đúng nhưng heap fetch đắt.

Khi query là Index Only Scan, output thêm dòng Heap Fetches: N. N càng cao tức là visibility map càng "lạnh" — autovacuum chưa kịp đánh dấu all-visible cho page vừa update, nên Postgres vẫn phải đi heap kiểm.

Vấn đề gặp trong production

Failure mode 1: Index Scan chậm hơn Seq Scan vì heap fetch quá nhiều. Lệ thường tin "có index = nhanh", nhưng khi predicate selectivity thấp (match nhiều row, ví dụ status = 'active' chiếm 30–40% bảng), Index Scan có thể đọc gần hết heap mà còn đọc theo thứ tự ngẫu nhiên. Mỗi heap fetch một page 8KB, không tận dụng được readahead, mỗi page chỉ lấy ra một row có ích. Cùng dữ liệu mà Seq Scan đọc sequential thường nhanh hơn nhiều lần.

-- Sai: index trên cột low-selectivity, planner bị buộc chọn index do hint hoặc stats lệch
CREATE INDEX orders_status_idx ON orders (status);
-- Query: SELECT * FROM orders WHERE status = 'active';  -- match ~40% bảng
-- Plan: Index Scan → mỗi TID một heap fetch ngẫu nhiên, slower than Seq Scan.

Cách xử lý: chạy ANALYZE để stats đúng (planner sẽ tự chuyển sang Seq Scan hoặc Bitmap Heap Scan); với cột low-cardinality dùng partial index chỉ index phần selective (WHERE status = 'pending' chiếm 1% bảng); hoặc bỏ index nếu nó không phục vụ query selective nào cả.

-- Đúng: partial index chỉ index nhóm thật sự selective
DROP INDEX orders_status_idx;
CREATE INDEX orders_pending_idx ON orders (created_at)
  WHERE status = 'pending';

Failure mode 2: Index Only Scan suy biến vì visibility map cũ. Một dashboard chạy ngon với Index Only Scan, latency vài ms. Sau một batch UPDATE lớn, latency nhảy lên hàng chục ms dù plan không đổi. EXPLAIN cho thấy Heap Fetches: cao bất thường — Postgres vẫn dùng index nhưng phải đi heap kiểm visibility cho gần hết row vì các page mới update không còn all-visible. Autovacuum chưa kịp chạy lại để cập nhật visibility map.

-- Triệu chứng: cùng plan, throughput giảm mạnh sau batch update
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, total_cents FROM orders
WHERE customer_id = 42;
-- Index Only Scan using orders_customer_total_idx
--   Heap Fetches: 18743   ← cao bất thường

Sửa bằng cách VACUUM (không cần FULL) trên bảng để rebuild visibility map, và chỉnh autovacuum_vacuum_scale_factor/autovacuum_vacuum_insert_scale_factor thấp xuống cho bảng update nóng.

Failure mode 3: correlation thấp khiến Index Scan random hết IO. pg_stats.correlation đo mức độ trùng giữa thứ tự logic của một cột và thứ tự vật lý trên đĩa. Cột như created_at của bảng append-only có correlation gần 1 (row mới luôn ở cuối) — Index Scan theo created_at đọc heap gần như sequential. Cột như customer_id rải đều khắp bảng có correlation gần 0 — mỗi TID ở một page khác nhau, mọi heap fetch là random IO. Cùng selectivity, query thứ hai chậm hơn query thứ nhất nhiều lần. Cách giảm: CLUSTER bảng theo index hot (one-shot, không tự duy trì), hoặc dùng BRIN thay B-Tree khi cột correlation cao và workload là range scan thô.

Failure mode 4: SELECT * phá Index Only Scan. Index có (customer_id, created_at) INCLUDE (total_cents) phục vụ tốt query SELECT customer_id, created_at, total_cents. Đổi sang SELECT * và mọi cột không có trong index buộc phải đi heap — Index Only Scan rớt về Index Scan, heap fetch xuất hiện cho mọi row. Đây là lý do trong production tránh SELECT * ở hot path; chỉ select cột thực sự dùng.

Failure mode 5: TOAST làm "một row" thực ra là nhiều page. Cột text/jsonb lớn được lưu out-of-line trong TOAST table. Một Index Scan đọc đúng 1 row vẫn có thể kéo theo nhiều TOAST page reads cho cột đó. Buffers: shared read đột biến lên khi query chạm cột rộng là dấu hiệu. Cách xử lý: không SELECT cột TOAST khi chỉ cần metadata; cân nhắc tách cột rộng sang bảng riêng.

Cách debug và monitor

Triệu chứng cần đọc:

• Plan là Index Scan nhưng Buffers: shared read lớn → heap fetch nhiều, kiểm correlation.
• Plan là Index Only Scan nhưng Heap Fetches: N lớn → visibility map cũ, cần vacuum.
• Plan đổi từ Index Scan sang Bitmap Heap Scan rồi sang Seq Scan theo thời gian → stats lệch, selectivity ước lượng sai.

Công cụ:

• EXPLAIN (ANALYZE, BUFFERS) — luôn bật BUFFERS. shared hit là page cache hit trong shared_buffers; shared read là page phải đọc từ OS cache hoặc đĩa. So sánh giữa plan có index và không có index để thấy access method nào ít page hơn cho cùng kết quả.
• EXPLAIN (ANALYZE, BUFFERS, VERBOSE) — VERBOSE in thêm output column, hữu ích khi check Index Only Scan có thật sự không đi heap.
• track_io_timing = on — EXPLAIN ANALYZE sẽ in I/O Timings: read=... cho biết thời gian thực sự nằm ở IO chứ không phải CPU. Quan trọng để phân biệt "chậm do random IO" và "chậm do filter trên CPU".
• pg_stat_user_indexes — idx_scan (số lần index được chọn), idx_tup_read (số entry quét trong index), idx_tup_fetch (số heap tuple được kéo lên qua index). Tỉ lệ idx_tup_fetch / idx_scan cao = mỗi scan kéo lên nhiều row, kiểm selectivity và heap fetch cost.
• pg_statio_user_tables — heap_blks_hit vs heap_blks_read cho biết hit ratio của heap; nếu thấp khi index nóng, bảng không nằm trong cache, mọi heap fetch là disk read.
• pg_stats.correlation — SELECT attname, correlation FROM pg_stats WHERE tablename = '...'; Cột correlation gần 0 là báo trước Index Scan trên cột đó sẽ random IO.
• pg_visibility extension — pg_visibility_map_summary('orders') đếm trang all_visible/all_frozen. Tỉ lệ thấp = Index Only Scan sẽ kéo heap fetch.

Rule phòng ngừa:

• ANALYZE ngay sau bulk load lớn; bật autovacuum cho bảng UPDATE nóng với scale factor thấp.
• Với hot read query: dùng INCLUDE để biến Index Scan thành Index Only Scan, kèm VACUUM đủ thường để giữ visibility map nóng.
• Khi cột bị query có correlation thấp và selectivity thấp, đừng cố index — Seq Scan hoặc bảng denormalize/aggregate có thể tốt hơn.
• Đọc plan với BUFFERS, không chỉ dựa vào tên access method và thời gian.

Tradeoff

Index Scan đổi page reads nhiều và random IO lấy trả kết quả theo thứ tự index và bỏ qua phần lớn bảng khi selective. Nó thắng tuyệt đối khi predicate chọn ra một phần nhỏ rows (kinh nghiệm: dưới ~5% bảng) và cột có correlation đủ cao để heap fetch không thuần random. Seq Scan thắng khi predicate kéo lên ~10–20% bảng trở lên, vì sequential IO + readahead bù được việc đọc dư. Bitmap Heap Scan là vùng giữa: vẫn dùng index để bỏ qua phần không khớp, nhưng đọc heap theo thứ tự block để cứu IO pattern — mất order, không phục vụ được ORDER BY ... LIMIT mà không kèm sort. Index Only Scan là biến thể tốt nhất khi khả thi, nhưng chỉ duy trì được nếu workload vacuum kịp; với bảng update nóng, nó suy biến về Index Scan + Heap Fetches mà plan vẫn không đổi tên. Quy tắc thực tế: với query hot, chọn cột index theo equality-trước-range, đẩy cột projection vào INCLUDE để mở đường cho Index Only Scan, đo bằng EXPLAIN (ANALYZE, BUFFERS) chứ không tin theo tên plan, và để planner chọn giữa Index/Bitmap/Seq tự do — đừng SET enable_seqscan = off ở production.

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

Index Scan hoạt động thế nào, và vì sao một query có index rồi mà vẫn chậm?

Index Scan đi B-Tree từ root xuống leaf để tìm các entry khớp predicate; mỗi entry leaf chứa TID (block, offset) trỏ vào heap. Postgres cầm TID ra heap đọc tuple đó, kiểm MVCC visibility (xem tuple này có visible với snapshot hiện tại không), rồi trả về cột đã chọn. Vậy mỗi row trong kết quả là một heap fetch — tiềm năng một random 8KB page read nếu page không nằm trong shared_buffers. Có index mà chậm thường do ba lý do production: (1) selectivity thấp, query lấy lên hàng vạn row, mỗi row một heap fetch ngẫu nhiên, tổng IO tệ hơn Seq Scan; (2) correlation thấp giữa thứ tự index và thứ tự vật lý, ngay cả khi selectivity tốt thì heap fetch cũng random; (3) Index Only Scan suy biến do visibility map cũ, Heap Fetches: N cao sau batch update mà autovacuum chưa kịp. Cách xử lý: EXPLAIN (ANALYZE, BUFFERS) để đo page reads thật, dùng INCLUDE đẩy projection vào index để chạy Index Only Scan, VACUUM để rebuild visibility map, dùng partial index cho predicate selective, để planner đổi sang Bitmap Heap Scan khi cần đọc nhiều page (nó sort TID theo block và đọc gần như sequential). Điểm ăn điểm là phân biệt được bốn access method (Seq / Index / Bitmap / Index Only) và nói được khi nào planner chuyển giữa chúng, kèm cách đọc Buffers: và Heap Fetches: để xác nhận giả thuyết — không dừng ở "có index thì phải nhanh".

Hands-on

Mục tiêu: so sánh Seq Scan, Index Scan, Bitmap Heap Scan, Index Only Scan trên cùng dữ liệu; ép heap fetch tăng để thấy Index Only Scan suy biến; sửa bằng VACUUM.

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

docker run -d --name pg-am -e POSTGRES_PASSWORD=pw -p 5433:5432 postgres:16
sleep 5
docker exec -i pg-am psql -U postgres <<'SQL'
ALTER SYSTEM SET track_io_timing = on;
SELECT pg_reload_conf();

CREATE TABLE orders (
  id          bigserial PRIMARY KEY,
  customer_id bigint    NOT NULL,
  status      text      NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  total_cents bigint    NOT NULL
);
INSERT INTO orders (customer_id, status, total_cents, created_at)
SELECT (random()*100000)::bigint,
       (ARRAY['pending','paid','shipped','cancelled'])[1+floor(random()*4)],
       (random()*1000000)::bigint,
       now() - (random() * interval '365 days')
FROM generate_series(1, 5000000);
VACUUM ANALYZE orders;
SQL

Đo Seq Scan (chưa có index):

docker exec -i pg-am psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, total_cents FROM orders WHERE customer_id = 42;"

Sẽ thấy Seq Scan và Buffers: shared read=... lớn (toàn bảng). Tạo index thường rồi đo lại để thấy Index Scan:

docker exec -i pg-am psql -U postgres -c "
CREATE INDEX orders_customer_idx ON orders (customer_id);
VACUUM ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, total_cents FROM orders WHERE customer_id = 42;"

Plan đổi sang Index Scan; Buffers giảm mạnh nhưng vẫn có shared read cho heap fetch. Thêm INCLUDE (total_cents) để mở đường cho Index Only Scan:

docker exec -i pg-am psql -U postgres -c "
DROP INDEX orders_customer_idx;
CREATE INDEX orders_customer_total_idx ON orders (customer_id) INCLUDE (total_cents);
VACUUM ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, total_cents FROM orders WHERE customer_id = 42;"

Plan thành Index Only Scan, dòng Heap Fetches: 0 (visibility map nóng sau VACUUM). Buffers tụt thêm một bậc.

Ép Index Only Scan suy biến bằng cách update để làm bẩn visibility map, rồi đo lại không vacuum:

docker exec -i pg-am psql -U postgres -c "
UPDATE orders SET total_cents = total_cents + 1 WHERE id % 100 = 0;
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, total_cents FROM orders WHERE customer_id = 42;"

Plan vẫn là Index Only Scan nhưng Heap Fetches: N sẽ > 0 và execution time tăng lên. Chạy VACUUM để rebuild visibility map:

docker exec -i pg-am psql -U postgres -c "
VACUUM orders;
EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, total_cents FROM orders WHERE customer_id = 42;"

Heap Fetches về 0, latency hồi lại.

So sánh Bitmap Heap Scan cho query selectivity vừa phải:

docker exec -i pg-am psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM orders
WHERE customer_id BETWEEN 100 AND 5000;"

Với range rộng, planner thường chuyển sang Bitmap Index Scan + Bitmap Heap Scan. Buffers đọc heap theo block, gần sequential.

Đo correlation và quan sát ảnh hưởng tới heap fetch:

docker exec -i pg-am psql -U postgres -c "
SELECT attname, correlation
FROM pg_stats WHERE tablename = 'orders'
ORDER BY abs(correlation) DESC;"

created_at có correlation gần 1 (bảng được nạp theo thời gian), customer_id gần 0. Chạy hai query có cùng selectivity nhưng khác correlation:

docker exec -i pg-am psql -U postgres <<'SQL'
CREATE INDEX orders_created_idx ON orders (created_at);
VACUUM ANALYZE orders;

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM orders
WHERE created_at BETWEEN now() - interval '7 days' AND now() - interval '6 days';

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM orders
WHERE customer_id BETWEEN 100 AND 200;
SQL

Query đầu (correlation cao) sẽ thấy Buffers: shared read rất thấp dù số row tương đương; query sau cao hơn nhiều. Đây là chi phí random IO mà tên plan không nói ra.

Audit usage để thấy idx_tup_fetch vs idx_tup_read:

docker exec -i pg-am psql -U postgres -c "
SELECT indexrelname, idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes WHERE schemaname = 'public';"

Dọn dẹp:

docker rm -f pg-am