Ở bài hash join và merge join ta đã thấy node Sort xuất hiện và tràn đĩa. Sắp xếp là một trong những thao tác tốn kém nhất của cơ sở dữ liệu — ORDER BY, một số GROUP BY, DISTINCT, và merge join đều cần nó. Bài này đo trực tiếp chi phí sắp xếp, cách work_mem quyết định nó nhanh hay tràn đĩa, và vấp một giả định về ORDER BY ... LIMIT khiến tôi tưởng nó tốn hơn thực tế nhiều.
Ba cách sắp xếp
PostgreSQL không có một cách sắp xếp duy nhất; nó chọn một trong ba tùy tình huống, và EXPLAIN ANALYZE cho biết cách nào qua dòng Sort Method:
- quicksort (trong RAM): nếu tập cần sắp vừa
work_mem, PostgreSQL sắp toàn bộ trong bộ nhớ. Nhanh.EXPLAINhiệnSort Method: quicksort Memory: .... - external merge (tràn đĩa): nếu tập vượt
work_mem, nó không thể sắp hết trong RAM. Nó chia dữ liệu thành từng mảnh vừawork_mem, sắp mỗi mảnh, ghi ra đĩa, rồi trộn các mảnh đã sắp lại. Chậm hơn vì phải ghi và đọc đĩa.EXPLAINhiệnSort Method: external merge Disk: .... - top-N heapsort: khi truy vấn có
LIMIT N, PostgreSQL không sắp cả tập rồi lấy N — nó chỉ giữ một heap N phần tử nhỏ nhất khi quét qua dữ liệu. Rất rẻ về cả thời gian lẫn bộ nhớ. Đây là chỗ tôi đo hớ.
Đo: 208 ms, 162 ms, hay 53 ms
Tôi tạo bảng một triệu hàng với cột v ngẫu nhiên, rồi ORDER BY v qua các cấu hình, đọc Sort Method và thời gian:
| Truy vấn / cấu hình | Sort Method | Thời gian |
|---|---|---|
ORDER BY v, work_mem = 1MB |
external merge (đĩa) | 208 ms |
ORDER BY v, work_mem = 256MB |
quicksort (RAM) | 162 ms |
ORDER BY v LIMIT 10, work_mem = 1MB |
top-N heapsort | 53 ms |
Hai dòng đầu là hiệu ứng work_mem. Với work_mem = 1MB, tập cần sắp (24MB) không vừa, nên PostgreSQL dùng external merge, tràn 11,7MB ra đĩa, mất 208 ms. Tăng work_mem lên 256MB, cả 24MB vừa RAM, dùng quicksort, mất 162 ms — nhanh hơn vì không chạm đĩa. (Chênh chỉ ~28% ở đây vì đĩa container là đĩa ảo nhanh — biến ẩn "tốc độ đĩa" quen thuộc; trên ổ cứng thật, tràn đĩa sẽ chậm hơn nhiều.)
Đáng chú ý: dòng đầu chậm hơn dòng hai dù cùng sắp một triệu hàng, chỉ khác nơi làm việc — RAM hay đĩa. Đúng như hai bài join trước cảnh báo, work_mem là ranh giới giữa "sắp trong bộ nhớ" và "tràn ra đĩa", và ranh giới đó quyết định phần lớn tốc độ của mọi thao tác sắp xếp. Dòng ba là chỗ bất ngờ.
Một lần tôi đo hớ: LIMIT không sắp cả tập
Tôi cần lấy 10 hàng có v nhỏ nhất, nên viết ORDER BY v LIMIT 10. Trong đầu tôi, cơ sở dữ liệu phải sắp cả một triệu hàng trước (như dòng hai: 24MB, 162 ms), rồi mới cắt lấy 10 hàng đầu. Tôi đã định ghi chú "top 10 vẫn tốn như sắp toàn bộ".
Nhưng EXPLAIN cho một dòng khác hẳn: Sort Method: top-N heapsort Memory: 25kB — và thời gian chỉ 53 ms. Hai mươi lăm kilobyte, không phải 24 megabyte; 53 ms, không phải 162 ms. PostgreSQL không sắp cả tập. Với LIMIT N, nó duy trì một heap chỉ chứa N phần tử nhỏ nhất đã thấy tới lúc đó: quét qua từng hàng, nếu hàng mới nhỏ hơn phần tử lớn nhất trong heap thì thay vào, không thì bỏ qua. Cuối lượt quét, heap chính là N hàng nhỏ nhất — đã sắp, mà chưa bao giờ giữ quá 10 phần tử trong bộ nhớ.
Cái tôi đo hớ là cho rằng "ORDER BY ... LIMIT N = sắp hết rồi cắt N" — trong khi planner khôn hơn, chỉ theo dõi N phần tử. Đây là kiểu "đo nhầm cái mình nghĩ": tôi tưởng đang đo chi phí sắp toàn bộ, nhưng câu truy vấn thật ra kích hoạt một thuật toán hoàn toàn khác, rẻ hơn hàng trăm lần về bộ nhớ. Bài học đo lường có hai vế. Vế một, cái đo hớ: đừng giả định thuật toán bên dưới một câu SQL — EXPLAIN cho biết cơ sở dữ liệu thật sự làm gì, và với LIMIT nó dùng top-N heapsort chứ không sắp cả tập. Vế hai, về work_mem: khi phải sắp cả một tập lớn (không có LIMIT), tập đó vượt work_mem sẽ tràn ra đĩa (external merge) và chậm đi; tăng work_mem đưa nó về RAM (quicksort). Con số Sort Method trong EXPLAIN là thứ cho biết bạn đang ở tình huống nào.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: ORDER BY ... LIMIT N rẻ một cách bất ngờ, cứ dùng thoải mái cho "top N". Lấy 10 bài mới nhất, 20 sản phẩm bán chạy nhất — những truy vấn này không sắp cả bảng; top-N heapsort giữ chi phí bộ nhớ ở mức N phần tử. Nhưng có một cải tiến còn tốt hơn: nếu cột ORDER BY có index, PostgreSQL đọc theo thứ tự index (Index Scan) và LIMIT dừng ngay sau N hàng đầu — khỏi sắp gì cả, gần như tức thì. Đây là lý do một cột dùng để sắp và phân trang nên được đánh index — nó biến một thao tác sắp xếp (dù là top-N) thành một phép đọc theo thứ tự có sẵn, rẻ nhất trong mọi lựa chọn. Với phân trang bằng ORDER BY ... LIMIT ... OFFSET, index còn giúp bỏ qua nhanh phần đầu thay vì sắp lại từ đầu mỗi trang.
Hệ quả thứ hai: ORDER BY không LIMIT trên tập lớn là thao tác nặng, và work_mem là nút chỉnh. Nếu một truy vấn báo cáo hay xuất dữ liệu chạy chậm, kiểm EXPLAIN (ANALYZE) xem có Sort Method: external merge Disk: ... không — đó là sắp xếp đang tràn đĩa vì work_mem nhỏ. Tăng work_mem (cho phiên hoặc truy vấn đó) thường biến nó thành quicksort trong RAM, nhanh hơn. Nhớ rằng work_mem áp cho mỗi thao tác sắp/băm, nên một truy vấn phức tạp có thể dùng nhiều lần work_mem cùng lúc — đừng đặt quá cao toàn cục.
Hệ quả thứ ba là bài học đo lường. Con số mang theo: sắp xếp có ba kiểu — quicksort (RAM, khi vừa work_mem), external merge (tràn đĩa, khi vượt: 208ms so với 162ms), và top-N heapsort (khi có LIMIT, chỉ giữ N phần tử: 25kB thay vì 24MB, 53ms) — và ORDER BY ... LIMIT không sắp cả tập như ta tưởng. Đừng đoán thuật toán từ câu SQL; Sort Method trong EXPLAIN cho biết cơ sở dữ liệu thật sự sắp thế nào và có tràn đĩa hay không.
Thử ba mươi giây
Chạy EXPLAIN (ANALYZE) SELECT ... ORDER BY cot trên một bảng lớn (không LIMIT) và nhìn node Sort: nếu thấy Sort Method: external merge Disk: ..., sắp xếp đang tràn đĩa. Thử SET work_mem = '256MB'; rồi chạy lại — nếu chuyển thành quicksort Memory: ... và nhanh hơn, bạn vừa tìm ra một nút thắt bộ nhớ. Rồi thêm LIMIT 10 vào và chạy lại: bạn sẽ thấy Sort Method đổi thành top-N heapsort với Memory tí xíu — bằng chứng rằng LIMIT không sắp cả tập. Và nếu cột đó có index, thử bỏ node Sort hẳn: EXPLAIN một ORDER BY cot_co_index LIMIT 10 thường ra Index Scan không kèm Sort — cách sắp rẻ nhất là không sắp gì cả.
