Từ đầu sê-ri ta chỉ đo truy vấn trên một bảng. Nhưng truy vấn thật gần như luôn JOIN nhiều bảng — đơn hàng với khách hàng, bài viết với tác giả. Cơ sở dữ liệu có nhiều cách thực hiện join, và cách đơn giản nhất là nested loop. Bài này đo khi nào nó nhanh như chớp và khi nào nó là thảm họa, và vấp một cái bẫy khi đọc EXPLAIN khiến tôi suýt tưởng join miễn phí.
Nested loop: hai vòng lặp lồng nhau
Nested loop (vòng lặp lồng) là cách join trực tiếp nhất, đúng như cái tên: với mỗi hàng của bảng ngoài, nó tìm các hàng khớp ở bảng trong. Về bản chất là hai vòng lặp lồng nhau — vòng ngoài duyệt bảng ngoài, vòng trong tìm khớp cho từng hàng.
Chi phí vì thế là một phép nhân: (số hàng bảng ngoài) × (chi phí một lần tìm ở bảng trong). Từ công thức đó suy ra ngay khi nào nó rẻ và khi nào đắt. Rẻ khi cả hai thừa số nhỏ: bảng ngoài ít hàng (ít vòng lặp), và bảng trong có index trên cột join (mỗi lần tìm là một index scan chớp nhoáng, không phải quét cả bảng). Đắt khi một trong hai thừa số phình: bảng trong không có index (mỗi vòng phải quét cả bảng trong — thành O(N×M)), hoặc bảng ngoài quá lớn (quá nhiều vòng). Tôi đo cả hai đầu của phổ này.
Đo: 0,027 ms hay 156 ms
Tôi tạo hai bảng: khach_hang (100.000 khách, khóa chính id) và don_hang (500.000 đơn, mỗi đơn trỏ tới một khách). Rồi join chúng qua vài kịch bản, đọc EXPLAIN ANALYZE:
| Tình huống | Kế hoạch | Thời gian |
|---|---|---|
| Ngoài 5 hàng + index trong | Nested Loop | 0,027 ms (loops=5) |
| Ngoài 2000 hàng + index trong | Nested Loop | 1,87 ms (loops=1999) |
| Ngoài 2000 hàng, không index | Nested Loop + Seq | 156 ms |
| Ngoài 200.000 hàng | Hash Join | (planner tự chuyển) |
Dòng đầu là nested loop lý tưởng: lọc don_hang còn 5 đơn, rồi với mỗi đơn tra khach_hang bằng khóa chính — cả truy vấn 0,027 ms. EXPLAIN cho thấy node bảng trong (index scan trên khach_hang) có loops=5: nó chạy đúng 5 lần, mỗi lần một hàng. Với 2000 đơn ngoài, loops=1999, vẫn chỉ 1,87 ms vì mỗi lần tra là index scan.
Dòng ba là bước ngoặt. Cùng 2000 đơn ngoài, nhưng tôi ép bảng trong không dùng index — giờ mỗi vòng lặp phải quét cả khach_hang. Thời gian nhảy lên 156 ms, chậm khoảng 83 lần. Đây là mặt tối của nested loop: không có index, nó thành O(N×M) và bùng nổ. Và dòng bốn cho thấy vì sao planner khôn: khi bảng ngoài lớn (200.000 hàng), nó bỏ hẳn nested loop và chọn hash join — vì 200.000 vòng lặp là quá nhiều dù có index. Đây là chỗ chi phí ước lượng phát huy: planner tính cost của nested loop (tỉ lệ số vòng) so với hash join và chọn cái rẻ hơn, tự động chuyển cách join theo cỡ dữ liệu.
Một lần tôi đo hớ: quên nhân với loops
Cái bẫy đến khi tôi đọc kế hoạch của nested loop nhanh. Thấy tổng 0,027 ms, tôi định ghi "join rẻ mà, chẳng đáng lo". Rồi tôi nhìn kỹ node bảng trong trong EXPLAIN: Index Scan ... (actual time=0.001..0.001 ...). Chỉ 0,001 mili giây! Tôi suýt kết luận: "cái tra bảng trong gần như miễn phí, join này không tốn gì".
Nhưng có một chữ tôi bỏ qua ngay bên cạnh: loops=1999. Con số actual time trong EXPLAIN cho một node là thời gian mỗi vòng lặp, không phải tổng. Node bảng trong chạy 1999 lần (một lần cho mỗi hàng ngoài), nên đóng góp thật của nó là 0,001 × 1999 ≈ 2 ms, không phải 0,001 ms. Với nested loop, bảng trong luôn chạy nhiều vòng, nên quên nhân với loops là đọc hụt chi phí đúng bằng số vòng — ở đây gần 2000 lần. Theo kỷ luật, đây là kiểu "đọc nhầm đại lượng": tôi lấy một con số per-loop và tưởng nó là tổng.
Cái tôi đo hớ có hai lớp. Thứ nhất, về đọc EXPLAIN: với node bên trong một nested loop, thời gian thật = actual time × loops; đừng đọc mỗi actual time. Thứ hai, về bản thân nested loop: 0,027 ms không có nghĩa "join luôn rẻ" — nó rẻ vì bảng ngoài nhỏ và bảng trong có index. Bỏ một trong hai điều kiện đó, cùng một phép join thành 156 ms hoặc tệ hơn. Bài học đo lường: một con số nhanh chỉ đúng cho điều kiện đo được nó; nested loop nhanh là hệ quả của "ngoài nhỏ + trong có index", không phải bản chất "join thì rẻ". Đo ở điều kiện khác (ngoài lớn, trong không index) cho con số hoàn toàn khác.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: nested loop là bạn của truy vấn "lấy vài hàng rồi join" — đúng mẫu phổ biến nhất trong ứng dụng web. Bạn lọc một ít đơn hàng (WHERE user_id = ? AND ...), rồi join sang bảng khách/sản phẩm để lấy chi tiết: bảng ngoài nhỏ, bảng trong tra bằng khóa chính có index — nested loop chạy chớp nhoáng. Điều kiện bắt buộc là bảng trong phải có index trên cột join. Đây là lý do khóa ngoại nên được đánh index: thiếu nó, một join tưởng nhẹ có thể thành O(N×M) khi dữ liệu lớn lên, và truy vấn "bỗng dưng" chậm thảm khi bảng phình.
Hệ quả thứ hai: đọc loops trong EXPLAIN ANALYZE là kỹ năng bắt buộc để chẩn đoán join. Khi một join chậm, mở kế hoạch ra và tìm node có loops lớn — đó là dấu hiệu nested loop đang lặp quá nhiều. loops cao (hàng chục nghìn trở lên) cộng với một Seq Scan bên trong là công thức của thảm họa: mỗi vòng quét cả bảng. Thấy vậy thì hoặc thêm index cho bảng trong, hoặc để planner chuyển sang hash/merge join (bằng cách cập nhật thống kê để nó ước lượng đúng số hàng ngoài).
Hệ quả thứ ba là bài học đo lường. Con số mang theo: nested loop join có chi phí (số hàng ngoài) × (chi phí tra một lần bên trong) — rẻ như 0,027ms khi ngoài nhỏ và trong có index, nhưng thành 156ms (chậm 83 lần) khi bỏ index, và planner tự chuyển sang hash join khi bảng ngoài lớn; đọc EXPLAIN phải nhân thời gian node trong với loops mới ra tổng. "Join rẻ" không phải chân lý mà là hệ quả của điều kiện; và một con số per-loop nhân với số vòng mới là con số thật.
Thử ba mươi giây
Chọn một truy vấn có JOIN trong ứng dụng của bạn và chạy EXPLAIN (ANALYZE). Tìm node Nested Loop, rồi nhìn node con bên trong nó: đọc cả actual time và loops. Nhân hai số đó để ra thời gian thật của bảng trong — bạn có thể ngạc nhiên vì loops lớn hơn tưởng. Nếu node bên trong là Index Scan/Index Only Scan, join của bạn khỏe. Nếu là Seq Scan với loops cao, đó là một join đang quét cả bảng trong mỗi vòng — thường vì thiếu index trên cột join. Thêm index đó rồi chạy lại, và xem Seq Scan biến thành Index Scan cùng thời gian tụt hàng chục lần — đúng khác biệt bài này đo.
