PostgreSQL Bài 14: Cơ chế JOIN chuyên sâu: Phân tích Nested Loop, Hash Join và Merge Join

Chào mừng bạn bước sang Phần 3: Kỹ thuật truy vấn từ cơ bản đến nâng cao.

Khi bạn viết một câu truy vấn JOIN, bạn chỉ đang diễn đạt kết quả logic bạn muốn nhận về: Bảng A kết hợp với Bảng B theo điều kiện X. Nhưng ở tầng thực thi vật lý, PostgreSQL engine không chỉ có một cách duy nhất để ghép hai bảng lại với nhau.

Query Optimizer (Planner) của PostgreSQL sẽ phân tích dung lượng bảng, sự phân bố thống kê dữ liệu (pg_statistic), sự hiện diện của Index và thông số bộ nhớ (work_mem) để lựa chọn 1 trong 3 thuật toán JOIN vật lý:

1. Nested Loop Join

2. Hash Join

3. Merge Join

Hiểu rõ bản chất toán học, chi phí tính toán (Time & Space Complexity) và điều kiện kích hoạt của từng thuật toán là chìa khóa để bạn đọc hiểu Execution Plan (EXPLAIN) và giải quyết các câu truy vấn chạy chậm trên hệ thống.

1. Nested Loop Join (Vòng lặp lồng nhau)

Đây là thuật toán trực quan và cổ điển nhất, hoạt động tương tự như hai vòng lặp lồng nhau trong mã nguồn ứng dụng (ví dụ: vòng lặp for lồng for).

VÒNG LẶP NGOÀI (Outer / Leading Table - Bảng nhỏ hơn):
FOR each row R1 in Outer Table:
    VÒNG LẶP TRONG (Inner Table - Bảng lớn hơn):
    FOR each row R2 in Inner Table:
        IF R1.key == R2.key THEN
            Output (R1, R2)

Outer Table (ít dòng)          Inner Table (có Index)
   ┌─────────┐                      ┌─────────┐
   │ Row 1   │ ───────────────────► │ Index   │ ──► [Match!]
   ├─────────┤                      │ Lookup  │
   │ Row 2   │ ───────────────────► │ (B-Tree)│ ──► [Match!]
   └─────────┘                      └─────────┘

1.1. Chi phí và Cơ chế hoạt động

• Không có Index ở Inner Table: Phải quét toàn bộ bảng trong (Seq Scan) cho mỗi dòng của bảng ngoài. Độ phức tạp: $O(N \times M)$ — cực kỳ chậm và tốn tài nguyên I/O.

• Có Index ở Inner Table (Index Nested Loop): Với mỗi dòng từ bảng ngoài, engine chỉ cần thực hiện 1 lần Index Lookup trên cây B-Tree của bảng trong. Độ phức tạp giảm xuống: $O(N \log M)$.

1.2. Kịch bản Planner ưu tiên chọn Nested Loop

• Bảng ngoài (Outer relation) trả về rất ít dòng (do có điều kiện WHERE lọc chặt chẽ, hoặc chỉ truy vấn 1 vài ID).

• Bảng trong (Inner relation) có sẵn Index trên cột tham gia phép JOIN.

• Điều kiện JOIN không phải là dấu bằng =, mà là các toán tử so sánh phạm vi hoặc bất đẳng thức (<, >, <=, >=, &&).

2. Hash Join (Kết hợp bằng Bảng băm)

Hash Join là "xương sống" cho hầu hết các câu truy vấn JOIN dữ liệu lớn trong các hệ thống hiện đại, đặc biệt là khi không có Index sẵn.

Thuật toán Hash Join diễn ra qua 2 giai đoạn riêng biệt: Build Phase và Probe Phase.

GIAI ĐOẠN 1: BUILD PHASE (Xây dựng Hash Table trên RAM)
Outer Table (Bảng nhỏ) ──► Hash Function ──► [ Hash Table trong work_mem ]

GIAI ĐOẠN 2: PROBE PHASE (Dò tìm khớp nối)
Inner Table (Bảng lớn) ──► Quét tuần tự từng dòng
                              │
                              ▼ (Băm key qua cùng Hash Function)
                         Tra cứu trong Hash Table ──► [Khớp ──► Output]

2.1. Chi phí và Các giai đoạn chi tiết

1. Build Phase (Giai đoạn Dựng):

   • Engine quét toàn bộ bảng nhỏ hơn (Build relation).

   • Đưa giá trị join key qua hàm băm và lưu toàn bộ các dòng này vào một bảng băm (Hash Table) nằm trên RAM (trong không gian bộ nhớ work_mem).

2. Probe Phase (Giai đoạn Dò):

   • Engine quét tuần tự bảng lớn hơn (Probe relation).

   • Với mỗi dòng của bảng lớn, băm join key rồi tra cứu trực tiếp vào Hash Table. Nếu tìm thấy bucket tương ứng, so sánh chính xác và trả về kết quả.

• Độ phức tạp thời gian: $O(N + M)$ — tuyến tính và cực kỳ nhanh.

2.2. Điểm yếu cốt tử: Thiếu RAM và tràn ra đĩa (Batched Hash Join)

• Bảng băm được xây dựng hoàn toàn bên trong vùng nhớ work_mem.

• Nếu bảng nhỏ vẫn vượt quá dung lượng work_mem, PostgreSQL không thể giữ toàn bộ bảng băm trên RAM. Lúc này, engine buộc phải kích hoạt thuật toán Multi-batch Hash Join: băm dữ liệu thành nhiều lô (batches) và ghi dữ liệu trung gian tạm thời ra ổ đĩa (Spill to Disk).

• Hậu quả: I/O đĩa tăng đột biến, thời gian chạy query chậm đi đáng kể. Bạn sẽ thấy dòng chữ Batches: 4, 8... trong kết quả EXPLAIN ANALYZE.

2.3. Kịch bản Planner chọn Hash Join

• Phép JOIN sử dụng toán tử bằng (=). Hash Join hoàn toàn vô dụng đối với các phép so sánh bất đẳng thức (<, >, !=).

• Dữ liệu hai bảng có kích thước từ trung bình đến lớn.

• Bảng lớn không có sẵn Index trên cột join.

3. Merge Join (Sắp xếp và Hợp nhất)

Merge Join hoạt động dựa trên nguyên lý của thuật toán Merge Sort: nếu cả hai tập dữ liệu đều đã được sắp xếp sẵn theo thứ tự của join key, việc kết hợp hai bảng có thể diễn ra chỉ trong một lần duyệt tuyến tính.

Tập dữ liệu A (Đã sắp xếp)             Tập dữ liệu B (Đã sắp xếp)
   id = 10  ◄────── Con trỏ A           id = 10  ◄────── Con trỏ B (Khớp! Trả về kết quả)
   id = 15                              id = 12
   id = 20                              id = 15
   id = 25                              id = 20

3.1. Cơ chế hoạt động

Engine duy trì hai con trỏ (pointers) duyệt dọc theo hai tập dữ liệu:

1. So sánh giá trị tại hai con trỏ.

2. Nếu hai giá trị bằng nhau: Trả về dòng kết quả và tịnh tiến con trỏ.

3. Nếu giá trị bên A nhỏ hơn bên B: Tịnh tiến con trỏ A sang dòng tiếp theo (và ngược lại).

4. Xử lý trùng lặp (Duplicates): Nếu một key xuất hiện nhiều lần ở cả hai bên, engine sẽ dùng kỹ thuật đánh dấu mốc (Mark & Restore) để quay lui con trỏ và ghép toàn bộ các cặp tích Đề-các của key đó.

3.2. Chi phí tính toán

• Nếu cả hai bảng đã có thứ tự sẵn (do đọc từ B-Tree Index, hoặc do một bước trước đó đã Sort): Độ phức tạp chỉ là $O(N + M)$.

• Nếu chưa được sắp xếp: Engine phải thực hiện công đoạn Sort trước:

  $$\text{Chi phí} = O(N \log N + M \log M + N + M)$$

  Công đoạn Sort này cũng tiêu tốn bộ nhớ work_mem. Nếu thiếu RAM, Sort sẽ chuyển sang cơ chế External Sort trên đĩa.

3.3. Kịch bản Planner chọn Merge Join

• Phép JOIN sử dụng toán tử bằng (=).

• Cả hai bảng đều có kích thước rất lớn (không thể nhét vừa Hash Table vào RAM).

• Cột JOIN ở cả hai bảng đều đã có B-Tree Index, giúp engine đọc trực tiếp dữ liệu đã sắp xếp sẵn mà không cần tốn chi phí Sort.

• Câu truy vấn vừa có JOIN, vừa có mệnh đề ORDER BY đúng trên chính cột join đó (tận dụng kết quả sắp xếp của Merge Join cho luôn phần ORDER BY).

4. Ma trận so sánh 3 cơ chế JOIN

Tiêu chí	Nested Loop Join	Hash Join	Merge Join
Toán tử hỗ trợ	Tất cả các toán tử (=, <, >, !=, spatial, overlap)	Chỉ hỗ trợ dấu bằng (=)	Chỉ hỗ trợ dấu bằng (=) hoặc bất đẳng thức có thứ tự
Yêu cầu Index	Cần B-Tree Index ở bảng trong (Inner) để đạt hiệu năng	Không cần Index	Tối ưu nhất khi cả hai bên đều có B-Tree Index
Bộ nhớ sử dụng	Tiêu tốn cực ít bộ nhớ RAM ($O(1)$)	Đòi hỏi RAM (work_mem) đủ để lưu bảng băm	Tốn RAM nếu phải chạy thêm bước Sort
Tốc độ trả dòng đầu tiên (First Row Latency)	Tức thì (Lý tưởng cho truy vấn có LIMIT)	Chậm hơn (Phải chờ Build xong Hash Table)	Nhanh nếu dữ liệu đã sắp xếp sẵn
Quy mô dữ liệu phù hợp	Một tập rất nhỏ ghép với một tập lớn	Hai tập dữ liệu lớn không sắp xếp	Hai tập dữ liệu khổng lồ đã sắp xếp sẵn

5. Thực hành: Quan sát Plan thực tế trên Terminal psql

Tạo dữ liệu thử nghiệm để ép PostgreSQL bộc lộ 3 cơ chế:

SQL

CREATE SCHEMA IF NOT EXISTS join_lab;

-- 1. Bảng danh mục (nhỏ, 50 dòng)
CREATE TABLE join_lab.categories (
    id INT PRIMARY KEY,
    name TEXT NOT NULL
);
INSERT INTO join_lab.categories 
SELECT i, 'Category ' || i FROM generate_series(1, 50) AS i;

-- 2. Bảng sản phẩm (lớn, 100.000 dòng)
CREATE TABLE join_lab.products (
    id BIGINT PRIMARY KEY,
    category_id INT NOT NULL,
    title TEXT NOT NULL,
    price NUMERIC(10, 2) NOT NULL
);
INSERT INTO join_lab.products 
SELECT 
    i, 
    (i % 50) + 1, 
    'Product ' || i, 
    (random() * 100)::numeric(10, 2)
FROM generate_series(1, 100000) AS i;

-- Tạo index trên foreign key
CREATE INDEX idx_products_category_id ON join_lab.products(category_id);

-- Cập nhật dữ liệu thống kê cho planner
ANALYZE join_lab.categories;
ANALYZE join_lab.products;

Kịch bản 1: Quan sát Nested Loop (Lọc tập nhỏ)

SQL

EXPLAIN (ANALYZE, BUFFERS)
SELECT * 
FROM join_lab.categories c
JOIN join_lab.products p ON c.id = p.category_id
WHERE c.id = 10;

Kế hoạch thực thi:

Plaintext

Nested Loop  (cost=0.29..45.35 rows=2000 width=45) (actual time=0.035..0.850 rows=2000 loops=1)
  Buffers: shared hit=28
  ->  Index Scan using categories_pkey on categories c  (cost=0.15..8.17 rows=1 width=15)
        Index Cond: (id = 10)
  ->  Bitmap Heap Scan on products p  (cost=0.14..37.18 rows=2000 width=30)
        Recheck Cond: (category_id = 10)
        ->  Bitmap Index Scan on idx_products_category_id  (cost=0.00..0.14 rows=2000 width=0)

Giải thích: Do điều kiện c.id = 10 chỉ trả về đúng 1 dòng ở bảng ngoài, Planner ngay lập tức chọn Nested Loop kết hợp Index Scan trên bảng products. Chỉ tốn 28 shared buffers và chạy trong chưa đầy 1 mili-giây.

Kịch bản 2: Quan sát Hash Join (Quét toàn bộ hai bảng)

SQL

EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, p.title, p.price
FROM join_lab.categories c
JOIN join_lab.products p ON c.id = p.category_id;

Kế hoạch thực thi:

Plaintext

Hash Join  (cost=2.12..2580.45 rows=100000 width=35) (actual time=0.048..18.650 rows=100000 loops=1)
  Hash Cond: (p.category_id = c.id)
  Buffers: shared hit=640
  ->  Seq Scan on products p  (cost=0.00..1845.00 rows=100000 width=26)
  ->  Hash  (cost=1.50..1.50 rows=50 width=17) (actual time=0.018..0.018 rows=50 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 11kB
        ->  Seq Scan on categories c  (cost=0.00..1.50 rows=50 width=17)

Giải thích:

• Bảng categories (50 dòng) được chọn làm Build relation, nạp vào Hash Table chỉ tốn 11kB RAM (Memory Usage: 11kB, Batches: 1).

• Sau đó, bảng products (100.000 dòng) được quét tuần tự (Probe relation) và băm để tra cứu vào Hash Table.

Kịch bản 3: Ép Planner chạy Merge Join

Trong môi trường bình thường, bạn không nên can thiệp vào Planner. Tuy nhiên, khi debug hoặc chứng minh thuật toán trong môi trường lab, bạn có thể tạm thời tắt các cơ chế khác trong phiên làm việc hiện tại:

SQL

SET enable_hashjoin = off;
SET enable_nestloop = off;

EXPLAIN (ANALYZE, BUFFERS)
SELECT c.id, c.name, p.title
FROM join_lab.categories c
JOIN join_lab.products p ON c.id = p.category_id
ORDER BY c.id;

Kế hoạch thực thi:

Plaintext

Merge Join  (cost=4.55..3450.00 rows=100000 width=35) (actual time=0.065..32.400 rows=100000 loops=1)
  Merge Cond: (c.id = p.category_id)
  ->  Index Scan using categories_pkey on categories c  (cost=0.15..12.50 rows=50 width=17)
  ->  Index Scan using idx_products_category_id on products p  (cost=0.29..3200.00 rows=100000 width=26)

Giải thích: Cả hai bảng đều được đọc theo thứ tự tăng dần từ B-Tree Index (categories_pkey và idx_products_category_id). Thuật toán Merge Join chạy song song hai con trỏ mà không tốn thêm bất kỳ một bước Sort trung gian nào.

(Đừng quên reset lại cấu hình sau khi test: RESET enable_hashjoin; RESET enable_nestloop;)

6. Tóm tắt & Bài tiếp theo

• PostgreSQL không thực thi JOIN một cách ngẫu nhiên mà luôn tính toán chi phí (Cost Estimation) giữa 3 thuật toán vật lý.

• Nested Loop thống trị khi kết hợp một tập kết quả rất nhỏ với một bảng lớn có sẵn B-Tree Index.

• Hash Join là giải pháp tối ưu cho việc ghép nối các tập dữ liệu lớn dựa trên toán tử bằng (=), nhưng phụ thuộc vào kích thước vùng nhớ work_mem.

• Merge Join phát huy uy lực tối đa khi dữ liệu ở cả hai bảng đã được sắp xếp sẵn thông qua Index.

Bài 15 xem tiếp: Subqueries và CTEs (WITH query): Phân biệt Materialized vs Non-Materialized CTE — chúng ta sẽ tìm hiểu cách tối ưu các câu truy vấn phức tạp bằng Common Table Expressions (CTE), sự thay đổi mang tính bước ngoặt từ PostgreSQL 12 về cơ chế Inline CTE, và cách dùng từ khóa MATERIALIZED để kiểm soát Query Optimizer.