Hai người trực thư viện muốn tìm những cuốn có trong cả hai danh sách của mình. Nếu hai danh sách đã xếp theo mã sách rồi, họ chỉ cần đặt cạnh nhau, dò từ trên xuống một lượt — mã nào khớp thì ghi lại, mã nào lệch thì bên nhỏ hơn lật tiếp. Một vòng là xong, không ai phải lật lại. Nhưng nếu hai danh sách còn lộn xộn, họ phải sắp lại cả hai trước đã — và nếu danh sách dài cả nửa triệu dòng thì riêng khâu sắp đã mệt nhoài. Merge join của cơ sở dữ liệu là đúng hai người trực thư viện này, và bài này là lần tôi chê nó chậm trong khi thật ra tôi bắt nó tự sắp cả đống lộn xộn.
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. Đúng hai người dò hai danh sách đã xếp.
Đ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ụt.
Đ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.
Suýt chê merge vì đo nó ở đ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, đúng như bắt hai người trực thư viện tự sắp lại cả đống lộn xộn trước khi dò.
Ở đ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 trật 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. 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 nhựa.
Về đến code hằng ngày
Điều đầ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ả.
Điều 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ể.
Và cái bẫy sâu nhất ở đây không phải về SQL, mà về cách so sánh hai lựa chọn cho công bằng — thứ lập trình viên làm sai suốt khi benchmark. So hai thuật toán mà một cái được chạy trên dữ liệu đã ở sẵn trong cache còn cái kia phải nạp từ đầu; so hai thư viện mà một cái được "làm nóng" JIT còn cái kia chạy nguội; so cấu trúc dữ liệu này với cấu trúc kia mà quên rằng một cái cũng cung cấp thứ tự (như TreeMap so HashMap — TreeMap chậm hơn khi tra, nhưng cho duyệt-theo-thứ-tự miễn phí, y hệt merge join). Và giống hệt merge join khi cần ORDER BY, một cấu trúc "chậm hơn" ở thao tác chính có thể thắng tổng thể nếu nó đồng thời cho bạn thứ bạn cần ở bước sau. Mẫu số chung đáng mang theo: trước khi kết luận A tốt hơn B, kiểm xem hai bên có làm đúng cùng một việc trong cùng điều kiện không, và có tính cả những thứ một bên "cho kèm" (thứ tự, tính bất biến, cache đã ấm) mà bên kia bắt bạn tự làm về sau không — rất nhiều "X nhanh hơn Y" chỉ đúng ở một điều kiện thiên vị. Gói lại bằng số: 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).
Muốn tự thấy thì 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.
