Ta đã đo nested loop (tốt cho ngoài nhỏ) và hash join (tốt cho hai bảng lớn). Cách join thứ ba là merge join, và nó có một tính chất độc đáo mà hai cách kia không có: giữ nguyên thứ tự. Bài này đo khi nào merge join rẻ, khi nào đắt, và vấp một cái bẫy khi so nó với hash join — tôi đo nó ở đúng điều kiện bất lợi cho nó.
Merge join: trộn hai luồng đã sắp
Merge join làm việc như bước "trộn" của merge sort. Nó sắp cả hai bảng theo cột join, rồi cho hai con trỏ chạy song song trên hai luồng đã sắp: khi hai giá trị bằng nhau thì ghép, khi lệch thì đẩy con trỏ nhỏ hơn tiến lên. Vì cả hai luồng đã có thứ tự, mỗi bảng chỉ cần quét một lần — không quay lại, không nhảy nhót.
Điểm quyết định là hai chữ "đã sắp". Nếu hai đầu vào đã có thứ tự sẵn — thường là nhờ đọc theo một index trên cột join — merge join rất rẻ: nó bỏ qua bước sắp xếp, chỉ trộn. Nhưng nếu đầu vào chưa sắp, merge join buộc phải thêm một node Sort trước — và sắp một bảng lớn tốn work_mem, có thể tràn ra đĩa. Đó là chỗ tôi đo hớ.
Đo: 77 ms hay 160 ms, tùy đã sắp chưa
Tôi tạo hai bảng a và b, mỗi bảng 500.000 hàng, cùng có khóa chính id. Rồi ép planner dùng merge join (tắt hash và nested loop) trên các truy vấn khác nhau:
| Tình huống | Kế hoạch | Thời gian |
|---|---|---|
Join theo id (2 đầu đã sắp qua index) |
Merge, không Sort | 77 ms |
Join theo cột chưa sắp (a.val) |
Merge + Sort tràn đĩa | 160 ms |
| Cùng vậy, để hash join | Hash Join | 78 ms |
Dòng đầu là merge join lý tưởng: join theo id, mà cả hai bảng đều có index trên id, nên PostgreSQL đọc chúng theo thứ tự id bằng Index Only Scan — hai luồng đã sắp sẵn. Merge trực tiếp, không có node Sort, xong trong 77 ms — ngang ngửa hash join, mà lại không tốn RAM dựng bảng băm.
Dòng hai là bước ngoặt. Tôi join theo a.val — một cột không có index, chưa sắp. Giờ merge join phải thêm một node Sort để sắp a.val trước, và EXPLAIN cho thấy Sort Method: external merge Disk: 5880kB — nó tràn ra đĩa vì bảng quá lớn so với work_mem. Thời gian nhảy lên 160 ms. Dòng ba cho thấy hash join làm cùng truy vấn đó chỉ trong 78 ms — nhanh gấp đôi, vì nó không cần sắp.
Một lần tôi đo hớ: đo merge ở điều kiện xấu
Nhìn dòng hai và ba cạnh nhau — merge join 160 ms, hash join 78 ms cho cùng truy vấn — phản xạ của tôi là chốt: "merge join dở hơn hash join, cứ dùng hash". Đó là một kết luận nghe hợp lý mà sai bản chất.
Sai ở đâu? Tôi nhìn vào EXPLAIN của bản merge join và thấy thủ phạm: phần lớn 160 ms không phải việc trộn, mà là node Sort phải thêm vào vì a.val chưa sắp. Tôi đang so hash join (không cần sắp) với merge-join-cộng-một-lần-sort — hai thứ khác nhau. Đo merge join trên một cột không có index là đo nó ở đúng điều kiện bất lợi nhất cho nó: buộc nó gánh một bước sắp mà nó vốn sinh ra để tránh.
Ở điều kiện thuận — hai đầu đã sắp qua index (dòng một) — merge join chỉ 77 ms, ngang ngửa hash. Và nó có một lợi thế mà hash join hoàn toàn không có: giữ nguyên thứ tự kết quả. Tôi đo tiếp: join theo id rồi ORDER BY id LIMIT 5. Merge join cho kết quả đã sắp sẵn theo id, nên ORDER BY là miễn phí và LIMIT 5 dừng sớm ngay — cả truy vấn 0,03 ms. Còn hash join phá vỡ thứ tự, nên với cùng truy vấn nó phải thêm một node Sort trên toàn bộ kết quả rồi mới LIMIT — mất 72 ms. Cùng một câu hỏi, merge join nhanh hơn hash hàng nghìn lần, chỉ vì nó giữ thứ tự.
Cái tôi đo hớ là so hai cách join ở một điều kiện thiên vị rồi kết luận cái nào "tốt hơn". Không có cách join nào tốt hơn tuyệt đối; mỗi cách thắng ở điều kiện của nó. Merge join chậm khi phải tự sắp, nhưng rẻ khi đầu vào đã sắp, và vô địch khi bạn cũng cần kết quả sắp. Bài học đo lường: một phép so sánh chỉ công bằng khi hai bên làm cùng một việc trong cùng điều kiện — đo merge join ở chỗ nó phải sắp thêm là không công bằng với nó, y như đo một chiếc xe địa hình trên đường đua.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: merge join tỏa sáng khi dữ liệu đã có thứ tự sẵn — thường nhờ index trên cột join, hoặc khi bạn join trên khóa chính. Với những truy vấn nối các bảng lớn theo khóa đã đánh index, planner có thể chọn merge join và chạy rất gọn. Đây cũng là lý do đánh index đúng cột join không chỉ giúp nested loop (bài phần 17) mà còn mở khóa merge join hiệu quả.
Hệ quả thứ hai, tinh tế hơn: merge join giúp tránh một bước sắp xếp khi bạn cần kết quả đã sắp. Nếu truy vấn của bạn là "join hai bảng rồi ORDER BY theo cột join" (rất phổ biến trong phân trang, báo cáo), merge join cho kết quả sắp sẵn — không cần node Sort riêng, và kết hợp LIMIT thì dừng sớm. Đây là lý do đôi khi thêm ORDER BY vào một truy vấn lại làm planner đổi sang merge join dù nó chậm hơn ở bước join thuần — vì tính cả bước sort tiết kiệm được, merge join rẻ hơn tổng thể.
Hệ quả thứ ba là bài học đo lường. Con số mang theo: merge join trộn hai luồng đã sắp — rẻ (77ms, không sort) khi đầu vào đã có thứ tự qua index, đắt (160ms, Sort tràn đĩa) khi phải tự sắp, và giữ nguyên thứ tự nên tránh được Sort cuối (0,03ms so với 72ms của hash join khi cần ORDER BY). Không cách join nào "tốt nhất"; so sánh chỉ có nghĩa khi hai bên ở cùng điều kiện, và merge join phải được đo ở nơi nó thuộc về: đầu vào đã sắp, hoặc kết quả cần sắp.
Thử ba mươi giây
Tìm một truy vấn join hai bảng theo cột có index (ví dụ khóa ngoại đã đánh index) và thêm ORDER BY theo đúng cột join đó, rồi chạy EXPLAIN (ANALYZE). Nếu bạn thấy Merge Join với hai Index Scan/Index Only Scan bên dưới và không có node Sort ở trên, đó là merge join tận dụng thứ tự index — rất hiệu quả. Thử bỏ ORDER BY hoặc join theo một cột không index, chạy lại, và xem planner có chuyển sang Hash Join không, hoặc merge join có mọc thêm một node Sort (kèm Sort Method: external merge Disk: ... nếu tràn) không. Đó chính là khác biệt "đã sắp hay chưa" mà bài này đo — và là lý do cùng một join có thể chọn ba cách khác nhau tùy dữ liệu và ORDER BY.
