Join algorithms — Nested Loop, Hash Join, Merge Join

JOIN 2 bảng — nghe đơn giản. Nhưng bên trong PostgreSQL có 3 cách thực thi hoàn toàn khác nhau, mỗi cách có profile về complexity, memory, và tốc độ riêng biệt. Planner chọn một trong ba dựa trên data profile — nếu chọn sai, query có thể chậm 100x.

Query SELECT u.name, count(t.id) FROM users u JOIN tasks t ON t.assignee_id = u.id GROUP BY u.id trên dataset 1 triệu task: Hash Join chạy 450 ms, Nested Loop chạy 24 giây nếu không có index. Cùng một query, cùng một data — chỉ khác algorithm. Hiểu khi nào planner chọn gì, và khi nào planner chọn sai, là 80% kỹ năng query tuning trong thực tế.

1. Analogy — Tìm tên trong 2 danh sách

Bạn có danh sách A gồm 10.000 tên nhân viên và danh sách B gồm 1 triệu bản ghi task. Cần ghép nhân viên với task của họ theo employee_id. Ba người thư ký có ba cách làm:

2. Vì sao 3 algorithm — data profile quyết định tất cả

Ba algorithm giải quyết ba tình huống khác nhau về kích thước data, sự tồn tại của index, và thứ tự sắp xếp:

Nested Loop sinh ra để khai thác index. Nếu bảng ngoài (outer) nhỏ và bảng trong (inner) có B-tree index trên join column, mỗi row outer chỉ tốn O(log B) để probe inner — tổng cộng O(A × log B). Khi A = 100 và B có index, đây là nhanh nhất. Khi A = 1,000,000 và không có index — là thảm họa.

Hash Join không cần index và không cần data đã sorted. Nó xây hash table từ bảng nhỏ hơn, rồi quét bảng lớn hơn tra hash table theo equality. Complexity O(A + B) — linear với tổng kích thước. Bottleneck duy nhất là hash table phải fit vào work_mem. Nếu spill to disk → performance rớt nghiêm trọng.

Merge Join tận dụng khi data đã được sort sẵn — thường từ B-tree index range scan. Hai sorted stream được merge theo kiểu khoá kéo — đi tuyến tính O(A + B) sau khi có thứ tự. Nếu phải sort trước: O(A log A + B log B). Best cho equi-join khi cả hai bảng đều có B-tree index trên join column.

3. Nested Loop — streaming-friendly, index-dependent

Nested Loop là algorithm đơn giản nhất về memory: không build structure, không sort — chỉ với mỗi row outer, probe inner. Ưu điểm lớn: streaming — PostgreSQL trả row đầu tiên ngay khi có, không cần đợi xử lý hết inner. Đây là lý do LIMIT query thường thấy Nested Loop.

EXPLAIN ANALYZE
SELECT u.name, t.title
FROM users u JOIN tasks t ON t.assignee_id = u.id
WHERE u.id < 100;

Nested Loop  (cost=0.42..1500.00 rows=200 width=64)
             (actual time=0.025..2.500 rows=180 loops=1)
  ->  Index Scan using users_pkey on users u  (cost=0.28..8.30 rows=99 width=40)
                                              (actual time=0.010..0.080 rows=99 loops=1)
        Index Cond: (id < 100)
  ->  Index Scan using idx_tasks_assignee on tasks t
                                              (cost=0.42..15.00 rows=2 width=32)
                                              (actual time=0.018..0.024 rows=2 loops=99)
        Index Cond: (assignee_id = u.id)

loops=99 trên node inner: Index Scan vào tasks chạy 99 lần — 1 lần per row từ outer (users). actual time=0.018..0.024 là time của 1 lần chạy duy nhất. Tổng time thực tế của inner node = 99 × 0.024 ms ≈ 2.4 ms — hoàn toàn chấp nhận được.

Vì sao hiệu quả ở đây: outer chỉ có 99 row (u.id < 100), và idx_tasks_assignee cho phép probe inner O(log B) thay vì quét toàn bộ.

Khi nào trở thành thảm họa: nếu outer 1,000,000 row và inner không có index → 1,000,000 Seq Scan → 1,000,000 × 15 ms = 250 giây. Hash Join cùng data đó: 450 ms. Chênh lệch 500x.

Nested Loop cost model (đơn giản hóa):
  outer_rows × cost(inner_scan_per_row)

Với index:    99 × 0.024 ms = 2.4 ms  ← tốt
Không index:  1,000,000 × 15 ms = 250,000 ms  ← thảm họa

4. Hash Join — build hash table, probe bằng larger

Hash Join chia thành 2 phase: build (xây hash table từ bảng nhỏ hơn) và probe (quét bảng lớn hơn, tra hash table theo equality). Không cần index, không cần sorted data — chỉ cần equi-join (=) và đủ work_mem.

EXPLAIN ANALYZE
SELECT u.name, count(t.id)
FROM users u JOIN tasks t ON t.assignee_id = u.id
GROUP BY u.id, u.name;

HashAggregate  (cost=25000.00..25200.00 rows=10000 width=48)
               (actual time=480.000..485.000 rows=10000 loops=1)
  Group Key: u.id, u.name
  Batches: 1  Memory Usage: 1200kB
  ->  Hash Join  (cost=350.00..18000.00 rows=1000000 width=32)
                 (actual time=0.500..450.000 rows=950000 loops=1)
        Hash Cond: (t.assignee_id = u.id)
        ->  Seq Scan on tasks t  (cost=0.00..14000.00 rows=1000000 width=16)
                                 (actual time=0.020..120.000 rows=1000000 loops=1)
        ->  Hash  (cost=225.00..225.00 rows=10000 width=24)
                  (actual time=0.420..0.420 rows=10000 loops=1)
              Buckets: 16384  Batches: 1  Memory Usage: 480kB
              ->  Seq Scan on users u  (cost=0.00..225.00 rows=10000 width=24)
                                       (actual time=0.010..0.180 rows=10000 loops=1)

Build phase: users (10.000 row, 480 kB) được load vào hash table. Probe phase: tasks (1 triệu row) được quét Seq Scan, mỗi row tra hash table bằng assignee_id. Batches: 1 = hash table fit hoàn toàn trong work_mem — mọi probe xảy ra trong RAM, không có disk I/O.

Khi spill to disk — Batches > 1:

-- Giả sử hash table quá lớn cho work_mem mặc định (4MB):
-- Ví dụ với bảng users 5 triệu row:

->  Hash  (cost=62500.00..62500.00 rows=5000000 width=24)
          (actual time=15.000..15.000 rows=5000000 loops=1)
      Buckets: 8192  Batches: 32  Memory Usage: 4096kB
      ->  Seq Scan on users u  (rows=5000000 loops=1)

Batches: 32 = PostgreSQL chia hash table thành 32 lô. Mỗi lô build → probe một phần của tasks. Điều này nghĩa là tasks phải được đọc 32 lần thay vì 1 lần — 32x chậm hơn về I/O. Khi thấy Batches lớn: fix bằng tăng work_mem cho session đó.

Hash Join cost model:
  build cost (quét + hash bảng nhỏ) + probe cost (quét bảng lớn + hash lookup)
  = O(smaller_table) + O(larger_table)
  = O(A + B)  ← linear với tổng data, bất kể index

5. Merge Join — hai sorted stream, linear scan

Merge Join hoạt động giống khoá kéo (zipper): cả hai input phải được sort theo join column. Sau đó, một "con trỏ" đặt ở đầu mỗi stream và tiến song song — khi tìm thấy key bằng nhau, emit cặp đó; khi khác nhau, tiến con trỏ ở bên nhỏ hơn. Không cần hash table, không cần nhớ nhiều dữ liệu — memory footprint cực kỳ thấp (chỉ 1 row mỗi bên).

EXPLAIN ANALYZE
SELECT u.name, p.name AS project_name
FROM users u JOIN projects p ON p.owner_id = u.id;

Merge Join  (cost=2500.00..4800.00 rows=8500 width=48)
            (actual time=0.080..15.000 rows=8500 loops=1)
  Merge Cond: (u.id = p.owner_id)
  ->  Index Scan using users_pkey on users u
                        (cost=0.28..1200.00 rows=10000 width=24)
                        (actual time=0.015..2.500 rows=10000 loops=1)
  ->  Sort  (cost=1200.00..1225.00 rows=10000 width=28)
            (actual time=0.060..0.800 rows=10000 loops=1)
        Sort Key: p.owner_id
        Sort Method: quicksort  Memory: 1200kB
        ->  Seq Scan on projects p  (cost=0.00..300.00 rows=10000 width=28)
                                    (actual time=0.010..0.180 rows=10000 loops=1)

users dùng Index Scan using users_pkey — B-tree primary key trả ra data đã sorted theo u.id, không cần sort thêm. projects chưa có index trên owner_id → phải Sort trước (Sort Method: quicksort Memory: 1200kB). Sau khi cả hai stream đã sorted, merge chạy tuyến tính.

Khi cả hai đã sorted sẵn (best case):

-- Nếu projects có index trên owner_id:
CREATE INDEX idx_projects_owner ON projects(owner_id);

-- Plan mới:
-- Merge Join  (actual time=0.040..8.000 rows=8500 loops=1)
--   ->  Index Scan using users_pkey on users u
--   ->  Index Scan using idx_projects_owner on projects p
--         (không có Sort node)
-- O(A + B) thuần — không có sort cost

Merge Join cost model:
  Nếu cần sort:  O(A log A + B log B) + O(A + B) merge
  Đã sorted:     O(A + B) merge thuần  ← tốt nhất với range output sorted

Merge Join cũng đặc biệt hữu ích khi kết quả cần trả ra đã sorted theo join column — PostgreSQL có thể tận dụng tính chất sorted của Merge Join để bỏ qua Sort node tiếp theo trong plan.

6. Bảng decision tree — chọn algorithm theo tình huống

Rule of thumb quan trọng nhất: Khi thấy Nested Loop với loops lớn (vài chục nghìn) và inner là Seq Scan — đó là dấu hiệu planner đang chọn sai algorithm. Root cause thường là row estimate sai (bài tiếp theo).

7. work_mem — hash table trong RAM vs spill to disk

work_mem là tham số quan trọng nhất ảnh hưởng đến Hash Join và Sort node (dùng trong Merge Join). Mỗi operation (không phải mỗi query, không phải mỗi connection) có thể dùng tới work_mem RAM.

-- Kiểm tra work_mem hiện tại
SHOW work_mem;
-- 4MB  ← mặc định — thấp cho analytics query

-- Set cho session cụ thể (analytics, không ảnh hưởng connection pool)
SET work_mem = '64MB';

-- Hoặc cho transaction cụ thể
SET LOCAL work_mem = '256MB';

Detect spill to disk:

EXPLAIN (ANALYZE, BUFFERS)
SELECT u.name, count(t.id)
FROM users u JOIN tasks t ON t.assignee_id = u.id
GROUP BY u.id, u.name;

Hash Join  (actual time=0.500..450.000 rows=950000 loops=1)
  Buckets: 16384  Batches: 1  Memory Usage: 480kB

Batches: 1 và Memory Usage: 480kB — tốt, fit trong work_mem. Nếu thấy:

Batches: 32  Memory Usage: 4096kB

Hash table đã đầy work_mem → spill. Với Sort node spill, dấu hiệu khác:

Sort Method: external merge  Disk: 12000kB

Trước khi spill thường thấy Sort Method: quicksort Memory: 4096kB. Khi vượt ngưỡng → chuyển sang external merge Disk: X kB. Disk sort chậm hơn in-memory quicksort khoảng 5–20x tùy I/O speed.

Chiến lược work_mem:

OLTP connection pool (nhiều concurrent):
  Giữ 4MB mặc định — N connection × 4MB = tổng RAM có thể dự đoán

Analytics session (ít, query lớn):
  SET work_mem = '256MB';  — set per session/tx, không global
  Analytics query thường dùng nhiều Sort + Hash Join → lợi rõ rệt

KHÔNG nên:
  SET global work_mem = '256MB'  với 200 connection
  → 200 × 256MB × số_operation_parallel = OOM tiềm năng

8. Force algorithm — debug và so sánh

PostgreSQL cho phép tắt từng algorithm để force planner chọn cái còn lại. Đây là công cụ debug — không dùng trong production.

-- Force Nested Loop (tắt Hash Join và Merge Join)
SET enable_hashjoin = off;
SET enable_mergejoin = off;

EXPLAIN ANALYZE
SELECT u.name, count(t.id)
FROM users u JOIN tasks t ON t.assignee_id = u.id
GROUP BY u.id, u.name;
-- Planner buộc phải dùng Nested Loop
-- So sánh actual time với Hash Join ở trên

-- Reset về mặc định
RESET enable_hashjoin;
RESET enable_mergejoin;

-- Force Hash Join (tắt Nested Loop và Merge Join)
SET enable_nestloop = off;
SET enable_mergejoin = off;

EXPLAIN ANALYZE
SELECT u.name, count(t.id)
FROM users u JOIN tasks t ON t.assignee_id = u.id
GROUP BY u.id, u.name;

RESET enable_nestloop;
RESET enable_mergejoin;

Workflow debug điển hình:

1. Chạy query với plan mặc định, ghi actual time.
2. Force từng algorithm, so sánh actual time.
3. Nếu algorithm bị force chạy nhanh hơn — planner đang chọn sai → điều tra root cause (thường là stale statistics, bài tiếp theo).
4. Fix root cause (ANALYZE, VACUUM, extended statistics) — không giữ enable_* = off trong production.

SET enable_* chỉ là gợi ý mạnh — planner vẫn có thể vi phạm trong một số điều kiện cực đoan. Không dùng để force plan trong production code.

9. Pitfall — bad row estimate và work_mem balance

Ví dụ thực tế:
  Planner estimate: outer table = 100 row
  → Chọn Nested Loop (100 × inner_cost = nhỏ, tưởng tốt)

  Thực tế: outer table = 1,000,000 row
  → Nested Loop: 1,000,000 × 25ms = 25,000 giây  ← thảm họa
  → Hash Join cùng data: ~500ms  ← 50,000x nhanh hơn

Root cause: statistics stale (ANALYZE chưa chạy sau bulk insert)
            hoặc cross-column correlation (bài tiếp theo)

Detect: EXPLAIN ANALYZE → so sánh estimated rows vs actual rows ở outer node
Fix:    ANALYZE table;
        CREATE STATISTICS IF NOT EXISTS stats_col1_col2 ON col1, col2 FROM table;

Triệu chứng: Hash Join với Batches: 16+ → chậm bất thường
             Sort Method: external merge Disk: X kB

Work_mem 4MB mặc định → hash spill với table > 50,000-100,000 row
→ Mỗi batch đọc lại probe table → I/O nhân nhiều lần

Fix 1: SET work_mem = '64MB'; cho analytics session
Fix 2: Xác định query pattern → SET LOCAL work_mem trong transaction analytics

Anti-pattern:
  ALTER SYSTEM SET work_mem = '256MB';  -- nâng toàn cục
  → 100 connection × 5 operation × 256MB = 128 GB potential RAM → OOM

Best practice:
  OLTP pool:         work_mem = 4MB (mặc định)
  Analytics session: SET work_mem = '64MB'; hoặc '256MB'; per session

10. Applied — TaskFlow 4-table JOIN analytics

Query thực tế từ TaskFlow analytics dashboard — đếm task per user per project:

SELECT u.name, p.name AS project, count(t.id) AS task_count
FROM users u
JOIN project_members pm ON pm.user_id = u.id
JOIN projects p ON p.id = pm.project_id
LEFT JOIN tasks t ON t.assignee_id = u.id AND t.project_id = p.id
GROUP BY u.id, u.name, p.id, p.name;

EXPLAIN ANALYZE output điển hình (dataset: 10.000 users, 500 projects, 1 triệu tasks):

HashAggregate  (cost=45000.00..47000.00 rows=50000 width=80)
               (actual time=2100.000..2150.000 rows=45000 loops=1)
  Group Key: u.id, u.name, p.id, p.name
  Batches: 4  Memory Usage: 4096kB
  ->  Hash Left Join  (cost=28000.00..42000.00 rows=1000000 width=64)
                      (actual time=850.000..1980.000 rows=980000 loops=1)
        Hash Cond: ((t.assignee_id = u.id) AND (t.project_id = p.id))
        ->  Hash Join  (cost=1200.00..8500.00 rows=50000 width=48)
                       (actual time=15.000..45.000 rows=48000 loops=1)
              Hash Cond: (pm.project_id = p.id)
              ->  Hash Join  (cost=225.00..2400.00 rows=50000 width=32)
                             (actual time=1.500..12.000 rows=48000 loops=1)
                    Hash Cond: (pm.user_id = u.id)
                    ->  Seq Scan on project_members pm
                                (cost=0.00..800.00 rows=50000 width=16)
                                (actual time=0.010..3.500 rows=50000 loops=1)
                    ->  Hash  (cost=225.00..225.00 rows=10000 width=24)
                              (actual time=1.200..1.200 rows=10000 loops=1)
                          Buckets: 16384  Batches: 1  Memory Usage: 480kB
                          ->  Seq Scan on users u  (rows=10000 width=24)
              ->  Hash  (cost=150.00..150.00 rows=500 width=24)
                        (actual time=0.800..0.800 rows=500 loops=1)
                    Buckets: 1024  Batches: 1  Memory Usage: 32kB
                    ->  Seq Scan on projects p  (rows=500 width=24)
        ->  Seq Scan on tasks t  (cost=0.00..14000.00 rows=1000000 width=16)
                                  (actual time=0.020..120.000 rows=1000000 loops=1)
Planning Time: 2.500 ms
Execution Time: 2180.000 ms

Đọc plan bottom-up:

1. Innermost Hash Join (level 3): build hash từ users (10k row, 480 kB), probe bằng project_members → 48.000 (user, membership) pairs.
2. Middle Hash Join (level 2): build hash từ projects (500 row, 32 kB — rất nhỏ), probe bằng kết quả level 3 → 48.000 (user, project) pairs.
3. Hash Left Join (level 1): build hash từ 48.000 pairs, probe bằng tasks (1 triệu row) → 980.000 matches. Đây là node đắt nhất — 1.130 ms.
4. HashAggregate: group by và đếm. Batches: 4 — aggregate spill một phần → dấu hiệu nên tăng work_mem.

Bottleneck và fix:

-- Fix 1: Tăng work_mem cho session analytics
SET work_mem = '64MB';
-- HashAggregate sẽ Batches: 1 → nhanh hơn đáng kể

-- Fix 2: Index trên tasks(assignee_id, project_id) cho Hash Left Join
CREATE INDEX idx_tasks_assignee_project ON tasks(assignee_id, project_id);
-- Planner có thể chuyển Hash Left Join sang Nested Loop nếu outer nhỏ hơn sau filter
-- Hoặc Merge Join nếu cả hai sorted theo (assignee_id, project_id)

-- Sau fix, kiểm tra lại:
EXPLAIN (ANALYZE, BUFFERS)
SELECT u.name, p.name AS project, count(t.id) AS task_count
FROM users u
JOIN project_members pm ON pm.user_id = u.id
JOIN projects p ON p.id = pm.project_id
LEFT JOIN tasks t ON t.assignee_id = u.id AND t.project_id = p.id
GROUP BY u.id, u.name, p.id, p.name;

Pattern cần nhớ khi đọc multi-table JOIN plan: tìm node có actual time lớn nhất (đây thường là Hash Join với bảng lớn nhất), kiểm tra Batches (nếu > 1 → cần thêm work_mem), và xem estimated rows vs actual rows ở mỗi node (sai lệch lớn → stale statistics).

11. Deep Dive

12. Tóm tắt

• PostgreSQL có 3 join algorithm: Nested Loop, Hash Join, Merge Join — planner chọn dựa trên data size, index availability, và sort order.
• Nested Loop: O(A × log B) với index, O(A × B) không index. Memory ~0. Streaming-friendly → tốt cho LIMIT. Best khi outer nhỏ + inner có index.
• Hash Join: O(A + B). Build hash table từ bảng nhỏ hơn, probe bằng bảng lớn hơn. Cần work_mem để giữ hash table. Spill to disk khi Batches > 1 → slow. Best cho equi-join với bảng trung bình-lớn không có index phù hợp.
• Merge Join: O(A log A + B log B) nếu cần sort; O(A + B) nếu đã sorted (B-tree index). Memory thấp (1 row mỗi bên). Best khi cả hai bảng đã sorted theo join column hoặc cần output sorted.
• Batches: 1 trong Hash Join = hash table fit trong work_mem → tốt. Batches: N > 1 → spill to disk → fix bằng SET work_mem = 'XMB' per session analytics.
• Bad row estimate → planner chọn Nested Loop khi nên Hash Join → có thể 1000x chậm hơn. Root cause: stale statistics. Fix: ANALYZE table.
• Force algorithm để debug: SET enable_hashjoin = off — chỉ dùng trong dev/debug, không trong production.
• Multi-table JOIN: đọc plan bottom-up, tìm node actual time lớn nhất, kiểm tra Batches, và so sánh estimated vs actual rows tại mỗi node.

13. Tự kiểm tra

Bài tiếp theo: Statistics & cost model — vì sao planner đoán sai