Nested loop, hash join và merge join trong PostgreSQL Trung cấp

Vấn đề

1.000 khách hàng, 100.000 đơn hàng, join theo customer_id, group theo vùng:

SELECT c.region, sum(o.amount)
FROM customer_demo c JOIN order_demo o ON o.customer_id = c.id
GROUP BY c.region;

PostgreSQL có ba cách vật lý để thực hiện đúng một phép join này. Bài ép PostgreSQL 17 chạy lần lượt cả ba trên cùng dữ liệu bằng enable_hashjoin, enable_mergejoin, enable_nestloop. Đây là công tắc chẩn đoán, không phải hint để dùng ở production.

Ba thuật toán trong một bảng

	Nested Loop	Hash Join	Merge Join
Cách làm	Mỗi dòng outer → tra inner	Băm bên nhỏ, quét bên lớn để tra	Hai dãy đã sắp thứ tự, duyệt song song
Cần	Thường cần index ở inner	Điều kiện =, đủ RAM cho bảng băm	Điều kiện =, hai bên đã có thứ tự (hoặc phải Sort)
Thắng khi	Outer rất nhỏ, inner có index	Hai bên lớn, không có thứ tự sẵn	Input đã sorted sẵn từ index, hoặc cần output có thứ tự
Thua khi	Outer lớn, inner không có index	Bảng băm vượt work_mem × hash_mem_multiplier (spill ra đĩa)	Phải Sort cả hai bên
Join không dùng = (<, BETWEEN)	Làm được	Không	Không

Cách hoạt động

Hash Join: build rồi probe

Hash Join: build bảng băm từ bên nhỏ, probe bằng bên lớn

Phóng to sơ đồ

customer_demo → Bảng bămbăm id

◀ Trước▶ PhátTiếp ▶↺ Từ đầuBước 1/3

Build: đọc bên nhỏ một lần, băm theo join key (id) và nạp vào bảng băm trong bộ nhớ.

Không cần gợi ý gì, planner tự chọn Hash Join cho query này:

HashAggregate  (cost=2333.11..2333.14 rows=2 width=37) (actual time=18.918..18.922 rows=2 loops=1)
  Buffers: local hit=547
  ->  Hash Join  (cost=28.50..1833.11 rows=100000 width=11) (actual time=0.097..11.002 rows=100000 loops=1)
        Hash Cond: (o.customer_id = c.id)
        ->  Seq Scan on order_demo o  (rows=100000)
        ->  Hash  (cost=16.00..16.00 rows=1000 width=9) (actual time=0.088..0.089 rows=1000 loops=1)
              Buckets: 1024  Batches: 1  Memory Usage: 51kB
              ->  Seq Scan on customer_demo c  (rows=1000)
Execution Time: 18.956 ms

• Bảng băm xây từ customer_demo (bên nhỏ): 1.000 dòng, 51 kB.
• Batches: 1 nghĩa là bảng băm nằm gọn trong bộ nhớ.
• Kết quả: 547 buffer hit, 18.956 ms.

Nested Loop: Memoize cứu chuỗi lặp

Nested Loop với Memoize: tra index một lần cho mỗi customer_id

Phóng to sơ đồ

order_demo → Memoizecustomer_id = ?

◀ Trước▶ PhátTiếp ▶↺ Từ đầuBước 1/3

Với mỗi dòng outer, Nested Loop lấy customer_id và hỏi bên inner: "customer này là ai?".

Ép Nested Loop, planner chèn thêm node Memoize (có từ PostgreSQL 14):

Nested Loop  (cost=0.29..4332.71 rows=100000 width=11) (actual time=0.024..19.495 rows=100000 loops=1)
  Buffers: local hit=3541
  ->  Seq Scan on order_demo o  (rows=100000)
  ->  Memoize  (cost=0.29..0.30 rows=1 width=9) (actual time=0.000..0.000 rows=1 loops=100000)
        Cache Key: o.customer_id
        Hits: 99000  Misses: 1000  Evictions: 0
        ->  Index Scan using customer_demo_pkey on customer_demo c  (rows=1) (loops=1000)
Execution Time: 27.886 ms

• customer_id chỉ có 1.000 giá trị khác nhau trong 100.000 dòng, nên inner index scan chỉ chạy 1.000 lần (Misses); 99.000 lần còn lại lấy từ cache (Hits).
• Nhờ vậy Nested Loop chỉ chậm hơn Hash Join khoảng 47% (27.886 ms so với 18.956 ms), không phải hàng trăm lần như trực giác “vòng lặp lồng nhau”.
• Nó vẫn chậm nhất trong ba vì 100.000 dòng đều phải tra cache một lần.

Merge Join: hai con trỏ trên hai dãy đã sắp

Hình dung Merge Join như ghép hai danh sách đã xếp theo customer_id:

customer (sorted)     order (sorted)
  id=1   ◄──────────►  customer_id=1  (ghép)
  id=1   ◄──────────►  customer_id=1  (ghép)  ← con trỏ order tiến, customer đứng yên
  id=2   ◄──────────►  customer_id=2  (ghép)
  id=3   ◄ ─ ─ ─ ─ ─   customer_id=5          ← 3 < 5: tiến con trỏ bên có key nhỏ hơn

Mỗi bên chỉ duyệt một lần, nhưng cả hai phải có thứ tự. Nếu chưa có, planner phải Sort trước, và đó là chi phí chính của Merge Join.

Merge Join  (cost=0.57..5304.90 rows=100000 width=8) (actual time=0.011..15.001 rows=100000 loops=1)
  Merge Cond: (c.id = o.customer_id)
  Buffers: local hit=100014 read=81
  ->  Index Only Scan using customer_demo_pkey on customer_demo c  (rows=1000)
        Heap Fetches: 1000
  ->  Index Scan using order_demo_customer_idx on order_demo o  (rows=100000) (actual time=0.004..9.531)
Execution Time: 16.949 ms

Thời gian (16.949 ms) ngang Hash Join, nhưng Buffers: hit=100014 so với 547 là gấp 182 lần. Cần đọc đúng con số này:

• hit đếm lượt truy cập buffer, không phải số page khác nhau.
• Index scan ghim buffer cho từng tuple lấy ra, nên cùng một page bị đếm lại nhiều lần. Seq Scan bên Hash Join chỉ ghim mỗi page một lần cho cả lô tuple.
• Vì vậy 182 lần phản ánh số lần chạm buffer (CPU), không phải 182 lần I/O đĩa.
• Muốn biết I/O thật: so read (81 ở đây) hoặc chạy lại với cache lạnh.

Khi Nested Loop thắng tuyệt đối

Đổi query sang chỉ lấy đơn hàng của một khách hàng:

Nested Loop  (cost=5.34..269.79 rows=100 width=4) (actual time=0.023..0.060 rows=100 loops=1)
  ->  Index Only Scan using customer_demo_pkey on customer_demo c  (rows=1)
        Index Cond: (id = 42)
  ->  Bitmap Heap Scan on order_demo o  (rows=100)
        Recheck Cond: (customer_id = 42)
Execution Time: 0.077 ms

0.077 ms, nhanh hơn các full join hàng chục đến hàng trăm lần. Hai query này làm khối lượng việc khác nhau (1 khách so với toàn bộ), nên đừng đọc đây là “Nested Loop nhanh hơn Hash Join”; ý nghĩa đúng là: khi outer chỉ có 1 dòng, không cần xây bảng băm hay sort cả bảng chỉ để lấy 1 dòng.

Chọn thuật toán nào?

Planner quyết định bằng cost; đây là cách đọc kết quả của nó:

Đang tải diagram…

Ví dụ thực tế

Cùng hai bảng, hai query, hai plan khác hẳn

Query	Outer đầu vào	Plan planner chọn
API “xem đơn hàng của một khách” (WHERE customer_id = ?)	1 dòng	Nested Loop, ~0.08 ms
Job “doanh thu theo vùng” mỗi đêm	~toàn bộ 2 bảng	Hash Join

Đừng “tối ưu” bằng cách ép cùng một thuật toán cho cả hai. Để planner quyết theo từng query và chỉ can thiệp khi đo được nó chọn sai.

Khi nào dùng, khi nào không

Ưu điểm

• Nested Loop gần như miễn phí khi outer nhỏ và inner có index (0.077 ms trong demo)
• Hash Join không cần index hay thứ tự, ít lượt truy cập buffer nhất khi hai bảng vừa cache (547 trong demo)
• Merge Join tận dụng thứ tự có sẵn từ index, không cần Sort nếu input đã sắp

Nhược điểm

• Nested Loop nhân chi phí theo số dòng outer; Memoize giảm nhẹ chứ không loại bỏ chi phí này
• Hash Join cần xây bảng băm trong RAM; vượt work_mem × hash_mem_multiplier sẽ chia batch và ghi đĩa tạm
• Merge Join thường phải Sort hai bên nếu không có index phù hợp

Checklist khi một join chậm

1. Chạy EXPLAIN (ANALYZE, BUFFERS) và so rows ước lượng với actual rows ở node join. Ước lượng quá thấp thường khiến planner chọn Nested Loop sai (planner statistics).
2. Nested Loop chậm với loops lớn: kiểm tra inner có Seq Scan hay thiếu index trên join key.
3. Hash Join có Batches > 1: bảng băm đã spill ra đĩa. Cân nhắc tăng work_mem cho phiên cụ thể hoặc giảm lượng dữ liệu vào join. hash_mem_multiplier mặc định 2.0 từ PostgreSQL 15.
4. Merge Join kèm Sort lớn: cân nhắc index cho phép đọc sẵn theo thứ tự join key.
5. Nhiều query nhỏ lặp lại từ ORM (N+1) thực chất là Nested Loop chạy ở tầng ứng dụng, không có Memoize. Gộp thành một join hoặc WHERE id = ANY(...).
6. Chỉ dùng enable_* để chẩn đoán trên phiên riêng. Đừng đặt chúng ở production.

Sai lầm thường gặp

Sai lầm thường gặp

So sánh hai plan chỉ bằng Execution Time trên dữ liệu nhỏ đã nằm gọn trong cache. Hash Join và Merge Join gần như bằng thời gian (18.956 ms và 16.949 ms) nhưng số lượt truy cập buffer chênh 182 lần. Khi đánh giá plan cho production, nhìn cả Buffers (nhớ hit là lượt truy cập, không phải I/O) và đo lại với dữ liệu, cache gần với thực tế.

Tóm tắt

Tóm tắt

• Không có thuật toán join tốt nhất tuyệt đối; mỗi cái thắng ở một hình dạng dữ liệu.
• Outer nhỏ + inner có index → Nested Loop. Hai bảng lớn, join bằng =, không có thứ tự sẵn → Hash Join. Đã sorted sẵn → Merge Join.
• Hash Join và Merge Join chỉ dùng được với điều kiện =; join theo <, BETWEEN chỉ có Nested Loop.
• Buffers hit là lượt truy cập, không phải I/O: muốn biết I/O thật hãy so read hoặc đo với cache lạnh.
• Memoize (từ PostgreSQL 14) làm Nested Loop rẻ hơn nhiều khi join key lặp lại, nhưng không biến nó thành lựa chọn tốt nhất cho join lớn.

Tham khảo

• PostgreSQL 17 — Using EXPLAIN
• PostgreSQL 17 — Planner Method Configuration