Bạn cần đối chiếu hai chồng hồ sơ dày để tìm những cái khớp mã. Cách chậm: cầm từng tờ chồng A, lật cả chồng B tìm mã trùng — triệu tờ A nhân triệu tờ B là ác mộng. Cách nhanh: bày chồng nhỏ hơn ra thành một bảng tra trên mặt bàn theo mã (mỗi mã một ô), rồi lướt chồng còn lại, mỗi tờ chỉ liếc bảng một cái là biết khớp hay không. Nhưng cách nhanh có một điều kiện ngầm: mặt bàn phải đủ rộng để bày hết bảng tra. Nếu bàn chật, bạn phải bày một phần, cất phần còn lại vào tủ, làm nhiều lượt — chậm hẳn. Hash join của cơ sở dữ liệu là đúng cái bàn tra này, và bài này là lần tôi khen nó nhanh mà quên hỏi mặt bàn có đủ rộng không.
Bài trước kết ở chỗ planner bỏ nested loop khi bảng ngoài lớn và chọn hash join thay. Bài này mổ chính cách join đó: nó nhanh cho những phép nối bảng-lớn-với-bảng-lớn mà nested loop bó tay, nhưng đổi lại cần bộ nhớ — và tôi vấp đúng cái điều kiện bộ nhớ ấy khi đo, ra một con số khiến "hash join nhanh" thành nửa đúng.
Hash join: băm một bên, dò bên kia
Khi phải join hai bảng lớn mà không lọc nhỏ được bên nào, nested loop thất bại: nó cần một vòng lặp cho mỗi hàng bảng ngoài, mà bảng ngoài có hàng triệu hàng thì là hàng triệu lần tra. Hash join giải quyết bằng một chiến lược khác hẳn, hai bước:
- Dựng bảng băm (hash table): lấy bảng nhỏ hơn trong hai bảng, băm giá trị cột join của từng hàng, và giữ bảng băm đó trong RAM — chính là bày chồng nhỏ ra bàn tra.
- Dò: quét bảng còn lại, băm cột join của mỗi hàng, và dò thẳng vào bảng băm — tìm khớp trong thời gian gần như hằng số.
Kết quả là chi phí O(N + M) (quét mỗi bảng đúng một lần) thay vì O(N × M) của nested loop không index. Với hai bảng lớn, đây là khác biệt sống còn: một triệu nhân năm trăm nghìn là con số thiên văn, còn một triệu cộng năm trăm nghìn thì máy làm trong tích tắc. Đổi lại, hash join có một yêu cầu mà nested loop không có: bảng băm phải vừa bộ nhớ — và đó là chỗ tôi vấp.
Đo: hash nhanh, nhưng cần RAM
Tôi tạo khach_hang 500.000 hàng và don_hang một triệu hàng, rồi join toàn bộ (đếm số cặp khớp). Đo qua các cấu hình:
| Cách / cấu hình | Kế hoạch | Thời gian |
|---|---|---|
| Mặc định | Hash Join | 78 ms (Batches=1) |
Ép enable_hashjoin=off |
Nested Loop | 223 ms |
work_mem = 1MB |
Hash, Batches=16 | 223 ms |
work_mem = 256MB |
Hash, Batches=1 | 189 ms |
Dòng đầu: hash join mặc định (có chạy song song) làm xong trong 78 ms, với Batches: 1 và Memory Usage: 23MB — nghĩa là bảng băm 23MB nằm gọn trong RAM, dựng một lần và dò một lượt. Ép planner dùng nested loop trên cùng truy vấn (dòng hai) mất 223 ms — nó phải làm một triệu lần tra chỉ mục, chậm gần 3 lần. Đúng như dự đoán: với bảng lớn không lọc, hash join thắng. Điểm khác biệt cốt lõi so với nested loop nằm ở cấu trúc: nested loop lặp một bên và tra bên kia (mỗi hàng ngoài một lần tra), còn hash join quét mỗi bảng đúng một lần rồi để bảng băm làm việc khớp — nên số hàng bảng ngoài không còn nhân lên thành số lần tra nữa.
Nhưng dòng ba là chỗ tôi đo hụt.
Hash join tràn ra đĩa
Thấy hash join 78 ms, tôi định chốt gọn: "hash join lo được join bảng lớn, xong". Nhưng theo thói quen của sê-ri, tôi thử đổi một biến để xem nó có ổn định không — hạ work_mem xuống 1MB (nhỏ) rồi đo lại cùng truy vấn. Kết quả: vẫn Hash Join, nhưng Batches: 16, và thời gian nhảy lên 223 ms.
Con số chậm hẳn cho cùng một kế hoạch buộc tôi tìm biến ẩn — và nó nằm ngay trong EXPLAIN: Batches. Bảng băm 23MB không vừa work_mem 1MB, nên PostgreSQL không thể giữ cả bảng băm trong RAM. Nó chia bảng băm thành 16 phần (batch), giữ một phần trong RAM và tràn 15 phần còn lại ra đĩa, rồi xử lý từng phần một — ghi và đọc lại dữ liệu băm nhiều lần. Đúng cái bàn chật phải bày một phần, cất phần kia vào tủ, làm nhiều lượt. Batches: 16 chính là con số tố cáo: hash join đang tràn đĩa. Tăng work_mem lên 256MB (dòng bốn), bảng băm vừa RAM, Batches: 1, và thời gian về 189 ms (không song song nên chậm hơn dòng một, nhưng nhanh hơn bản 16-batch).
Cái tôi trật là tưởng "hash join nhanh" là vô điều kiện — trong khi tốc độ của nó phụ thuộc bảng băm có vừa work_mem hay không. Khi vừa (Batches: 1), nó bay; khi không vừa (Batches > 1), nó tràn đĩa và chậm đi. Ở đây chỉ chậm ~18% vì đĩa của container là đĩa ảo nhanh — đúng biến ẩn "tốc độ đĩa" từ bài WAL; trên một ổ cứng thật, tràn 16 batch ra đĩa sẽ là một vực sâu về hiệu năng, không phải 18%. Một con số nhanh ("78 ms") chỉ đúng cho điều kiện nó được đo (bảng băm vừa RAM), và con số Batches trong EXPLAIN là thứ cho biết điều kiện đó có thỏa không. Đọc mỗi thời gian tổng mà bỏ qua Batches là bỏ qua lý do vì sao một hash join lúc nhanh lúc chậm.
Về đến code hằng ngày
Điều đầu tiên: hash join là lựa chọn đúng cho join bảng lớn, nhưng work_mem là nút chỉnh quyết định nó nhanh hay tràn đĩa. Nếu một truy vấn phân tích (join, GROUP BY, sắp xếp trên nhiều bảng lớn) chạy chậm bất ngờ, kiểm EXPLAIN (ANALYZE) xem có Batches > 1 (hash) hay Sort Method: external merge (sắp xếp tràn đĩa) không — đó là dấu hiệu work_mem quá nhỏ cho khối lượng đó. Tăng work_mem (cho phiên hoặc cho truy vấn cụ thể, không nhất thiết toàn cục vì mỗi thao tác dùng riêng một work_mem) thường biến truy vấn tràn đĩa thành truy vấn trong RAM, nhanh gấp bội.
Điều thứ hai: hash join không giữ thứ tự. Bảng băm phá vỡ mọi thứ tự — kết quả hash join ra theo thứ tự "tình cờ" của việc dò băm. Nếu bạn cần kết quả đã sắp, hoặc bạn muốn tránh một bước Sort sau join, một cách join khác (merge join, bài sau) có thể phù hợp hơn dù chậm hơn ở bước join thuần. Đây là lý do cùng một truy vấn, thêm ORDER BY có thể làm planner đổi cả kiểu join.
Và cái mẫu hình đằng sau hash join — đánh đổi bộ nhớ lấy tốc độ bằng một bảng tra, với điều kiện ngầm là bảng tra phải vừa RAM — chính là một trong những kỹ thuật nền tảng bạn dùng hằng ngày ở tầng code, cùng cái bẫy y hệt. Muốn tìm phần tử chung của hai danh sách trong Java, bạn bỏ một danh sách vào HashSet rồi dò danh sách kia (O(n+m)) thay vì hai vòng lặp lồng (O(n×m)) — đó đúng là hash join viết tay. Nhưng nếu cái HashSet đó lớn tới mức không vừa heap, JVM bắt đầu GC liên miên hoặc OutOfMemoryError — chính là "tràn batch" phiên bản ứng dụng. Mọi cache trong bộ nhớ, mọi Map để khử-trùng hay tra nhanh đều mang cùng đánh đổi: nhanh khi vừa RAM, sụp khi không. Mẫu số chung đáng mang theo: "dùng một bảng băm/tập hợp trong bộ nhớ để biến O(n×m) thành O(n+m)" là cú lật ngoạn mục nhất trong tối ưu — nhưng luôn kèm điều kiện ngầm 'cấu trúc đó vừa bộ nhớ'; trước khi tin nó nhanh, hãy hỏi nó có vừa RAM ở quy mô thật không, vì lúc tràn ra đĩa/GC thì lợi thế bốc hơi. Gói lại bằng số: hash join dựng bảng băm từ bảng nhỏ hơn rồi dò bảng kia — O(N+M), nhanh cho bảng lớn (78ms so với 223ms của nested loop); nhưng chỉ nhanh khi bảng băm vừa work_mem (Batches=1), còn không thì tràn ra đĩa nhiều batch (Batches=16) và chậm đi.
Muốn tự thấy thì tìm một truy vấn join hai bảng lớn (hoặc GROUP BY trên bảng lớn) và chạy EXPLAIN (ANALYZE). Trong node Hash, tìm dòng Buckets: ... Batches: ... Memory Usage: .... Nếu Batches là 1, bảng băm vừa RAM — tốt. Nếu Batches lớn hơn 1, hash join đang tràn ra đĩa vì work_mem không đủ. Thử SET work_mem = '256MB'; (chỉ cho phiên hiện tại) rồi chạy lại — nếu Batches về 1 và thời gian giảm, bạn vừa tìm ra và sửa một nút thắt bộ nhớ. Và nhớ: SHOW work_mem; cho biết mặc định của bạn (thường chỉ 4MB), thường quá nhỏ cho truy vấn phân tích nặng.
