Nested Loop Join trong PostgreSQL: nhanh 0,044 ms hay chậm 627 ms, tùy một index

Ba bài trước ta đọc các kiểu quét một bảng. Giờ bước sang chuyện khó hơn: nối hai bảng. PostgreSQL có ba thuật toán join, và bài này mổ xẻ cái đơn giản nhất — Nested Loop Join. Đơn giản không có nghĩa là an toàn: cùng một truy vấn, Nested Loop có thể chạy trong 0,044 ms hoặc 627 ms — chênh nhau 14.000 lần — và ranh giới giữa hai thế giới đó chỉ là một index. Đo thật để thấy vì sao.

Nested Loop hoạt động thế nào

Ý tưởng đúng như tên: hai vòng lặp lồng nhau. Với mỗi dòng của bảng ngoài, quét bảng trong để tìm các dòng thỏa điều kiện join.

for mỗi dòng ngoài:
    for mỗi dòng trong khớp điều kiện: xuất kết quả

Chi phí của nó là một phép nhân: (số dòng bảng ngoài) × (chi phí tìm dòng khớp ở bảng trong mỗi lần). Chính phép nhân này quyết định thiên đường hay địa ngục.

Hình 1: Nested Loop là hai vòng lặp lồng nhau. Thắng khi bảng ngoài nhỏ và bảng trong có index trên cột join; thua nặng khi bảng trong thiếu index, biến thành O(ngoài × trong).

Đo thật: cùng truy vấn, 0,044 ms hay 627 ms

Hai bảng: khach (100.000 dòng) và don (2 triệu dòng, mỗi đơn trỏ tới một khách). Truy vấn nối 5 khách với đơn của họ (WHERE k.id < 6). Ba kịch bản:

Hình 2: Ba kịch bản cùng truy vấn. Nested Loop + inner có index: 0,044 ms. Ép Nested Loop khi inner không index: 626,9 ms (10 triệu phép so sánh). Không index, planner tự chọn Hash Join: 44,9 ms.

Thiên đường — inner có index (planner chọn): bảng ngoài khach chỉ 5 dòng. Với mỗi dòng, PostgreSQL làm một Index Only Scan trên idx_don_khach (loops=5) — mỗi lần là một index lookup tức thì. Tổng 0,044 ms. Đây là điều Nested Loop sinh ra để làm: ngoài nhỏ × tra index nhanh.

Địa ngục — inner không index (ép Nested Loop): bỏ index trên don.khach_id, giờ mỗi dòng ngoài buộc phải quét toàn bộ bảng don để tìm dòng khớp. Kế hoạch cho thấy Seq Scan on don rows=2.000.000, Materialize (5 dòng khach) loops=2.000.000, và Rows Removed by Join Filter: 9.999.733 — gần 10 triệu phép so sánh cho một truy vấn chỉ trả về 89 dòng. Kết quả 626,9 ms, chậm gấp ~14.000 lần chỉ vì mất một index.

Planner biết điều này. Khi không có index, planner không chọn Nested Loop — nó tự chuyển sang Hash Join (44,9 ms). Nested Loop 627 ms chỉ xảy ra khi ta ép planner bằng SET enable_hashjoin = off. Trong thực tế, planner tránh thảm họa này — trừ khi ước lượng số dòng sai khiến nó tưởng bảng ngoài nhỏ hơn thực tế.

Dấu hiệu nhận biết Nested Loop đang giết hiệu năng

Đọc EXPLAIN ANALYZE, ba tín hiệu cảnh báo:

loops lớn ở nhánh trong. loops=5 là lành. loops=2000000 nghĩa là nhánh trong bị chạy lại hai triệu lần — gần như luôn là dấu hiệu Nested Loop sai chỗ.

Rows Removed by Join Filter khổng lồ. Con số này đếm số cặp dòng bị loại sau khi so sánh — 10 triệu ở đây. Nó cho thấy PostgreSQL đang so sánh vét cạn thay vì tra index.

Ước lượng dòng lệch xa thực tế. Nested Loop thảm họa thường bắt nguồn từ planner ước lượng bảng ngoài "vài dòng" nhưng thực tế là hàng nghìn. Nếu EXPLAIN ANALYZE cho thấy rows ước lượng (ví dụ 5) khác xa actual rows (ví dụ 5000), đó là gốc rễ — cần ANALYZE lại để cập nhật thống kê.

Đánh đổi: khi nào Nested Loop là đúng

Nested Loop tối ưu cho join "một-ít". Lấy chi tiết một đơn hàng và các dòng của nó, hồ sơ một người dùng và bài viết của họ — bảng ngoài vài dòng, bảng trong tra bằng index. Không thuật toán nào rẻ hơn.

Đảm bảo cột join của bảng trong có index. Đây là điều kiện sống còn. Khóa ngoại (foreign key) không tự tạo index ở PostgreSQL — bạn phải tự tạo. Rất nhiều truy vấn join chậm bắt nguồn từ một khóa ngoại thiếu index.

Với join "nhiều-nhiều", để planner chọn Hash Join hoặc Merge Join. Khi cả hai phía đều lớn, Nested Loop thua — và đó chính là lúc hai thuật toán join kia tỏa sáng, chủ đề của các bài sau. Đừng ép Nested Loop bằng tay ngoài lúc thử nghiệm.

Ba ý mang về

1. Nested Loop là hai vòng lặp lồng nhau, chi phí bằng (số dòng ngoài) × (chi phí tìm dòng trong) — nên nó chỉ rẻ khi bảng ngoài nhỏ và bảng trong tra được bằng index.
2. Một index quyết định 14.000 lần khác biệt: cùng truy vấn, Nested Loop chạy 0,044 ms khi don.khach_id có index, nhưng 626,9 ms (10 triệu phép so sánh) khi không — luôn đánh index cột join, đặc biệt trên khóa ngoại.
3. Đọc loops và Rows Removed by Join Filter trong EXPLAIN để phát hiện Nested Loop sai chỗ; planner thường tự tránh nó (chọn Hash Join 44,9 ms) trừ khi ước lượng dòng sai — khi đó ANALYZE lại.

Phần sau ta xét thuật toán mà planner đã chọn thay thế: Phần sau mổ xẻ Hash Join — cách nó nối hai bảng lớn bằng một bảng băm trong bộ nhớ, và khi nào nó thắng Nested Loop.