'Đổi subquery thành JOIN cho nhanh' — tôi làm theo và truy vấn chậm đi 10 lần

Hỏi một người gác cổng "trong tòa nhà này có ai tên Nam không?" thì anh ta chỉ cần tìm thấy một người tên Nam là trả lời "có" ngay, khỏi đếm tiếp. Nhưng nếu bạn hỏi "liệt kê tất cả những lần ai đó tên Nam đi qua cổng, rồi lọc ra danh sách người" thì anh ta phải lật cả cuốn sổ nghìn trang, ghi ra mọi lượt, rồi mới gạch trùng. Hai câu hỏi cho cùng một đáp án — "có những ai" — nhưng khối lượng việc chênh nhau cả chục lần. Trong SQL cũng vậy, và bài này là lần tôi vô tình hỏi câu nặng trong khi câu nhẹ cho đúng kết quả đó.

Có một lời khuyên lưu truyền rất rộng: "subquery chậm, viết lại thành JOIN cho nhanh". Nghe hợp lý — JOIN là công cụ chuyên để nối bảng, còn subquery trông như một truy vấn lồng trong truy vấn, chắc phải tốn hơn. Tôi mang niềm tin đó vào bài này rồi đo, và kết quả lật ngược hẳn: với cùng một câu hỏi, subquery nhanh hơn JOIN mười lần. Hóa ra cái nhãn "subquery" hay "join" gần như không nói gì về tốc độ — thứ quyết định là cái khác.

Cùng câu hỏi, nhiều cách viết

Tôi dựng hai bảng: users (10.000 người) và orders (một triệu đơn, có index trên cột uid), trong đó 8.000 người có ít nhất một đơn. Câu hỏi: liệt kê những người có đơn. Cùng một câu hỏi đó viết được ít nhất ba cách khác nhau:

-- IN subquery
SELECT * FROM users WHERE id IN (SELECT uid FROM orders);
-- EXISTS
SELECT * FROM users u WHERE EXISTS (SELECT 1 FROM orders o WHERE o.uid = u.id);
-- JOIN + DISTINCT
SELECT DISTINCT u.* FROM users u JOIN orders o ON o.uid = u.id;

Ba cách cho cùng 8.000 hàng, và với nhiều người, cả ba trông "tương đương" về mặt logic nên cũng phải tương đương về tốc độ. Nhưng EXPLAIN cho thấy chúng không được chạy như nhau — và chỗ khác biệt không nằm ở nơi tôi tưởng, không phải giữa "subquery" và "join" mà giữa những việc thật sự khác nhau mà mỗi cách bắt CSDL làm.

Đo: IN và EXISTS cho kế hoạch y hệt

Điều đầu tiên đập vào mắt: IN và EXISTS cho ra kế hoạch giống hệt nhau:

IN subquery:  Nested Loop Semi Join   ~5 ms
EXISTS:       Nested Loop Semi Join   ~4,7 ms

Cùng một nút Semi Join, cùng thời gian, gần như không phân biệt nổi hai kế hoạch. Planner nhận ra cả hai đều hỏi "người này có tồn tại một đơn nào không?" và viết lại cả hai về cùng một phép semi join — một kiểu join đặc biệt chỉ kiểm sự tồn tại: với mỗi người, nó tìm đơn khớp và dừng ngay ở đơn đầu tiên, không cần duyệt hết. Đúng anh gác cổng thấy một người tên Nam là trả lời ngay. Cú pháp IN hay EXISTS chỉ là hai cách viết cùng một ý; planner gộp chúng lại. Đây là bằng chứng đầu tiên rằng "subquery" không phải một thứ đồng nhất về hiệu năng.

JOIN chậm hơn subquery mười lần

Giờ tới cách JOIN mà lời khuyên bảo tôi dùng cho nhanh:

JOIN + DISTINCT:  Hash Join + khử trùng   ~50 ms

Chậm hơn IN/EXISTS khoảng mười lần — đúng ngược với kỳ vọng của tôi. Lý do nằm ở việc phải làm, không ở cú pháp. IN/EXISTS thành semi join, chỉ cần biết mỗi người có đơn hay không, nên dừng ở đơn đầu tiên. Còn JOIN nối mọi cặp người–đơn khớp — với một triệu đơn, đó là cả triệu cặp — rồi DISTINCT mới khử trùng để còn lại 8.000 người. Nối một triệu cặp rồi bỏ đi phần lớn là làm rất nhiều việc thừa mà semi join né được hoàn toàn. Đây đúng là anh gác cổng phải chép cả cuốn sổ ra rồi mới gạch trùng.

Cái sai của tôi là gán tốc độ cho nhãn cú pháp ("join nhanh, subquery chậm") thay vì cho việc truy vấn thật sự yêu cầu. Ở đây câu hỏi là "có tồn tại không" — một câu hỏi tồn tại — và semi join là cách đúng để trả lời nó, dù bạn viết bằng IN hay EXISTS. Viết thành JOIN + DISTINCT vô tình bắt CSDL trả lời một câu hỏi nặng hơn (liệt kê mọi cặp) rồi cắt bớt. Lời khuyên "luôn đổi subquery thành join" ở đây làm truy vấn chậm đi mười lần.

Cái thật sự đáng dè chừng: subquery tương quan

Vậy có loại subquery nào thật sự đáng lo không? Có — subquery tương quan (correlated), loại tham chiếu tới hàng của truy vấn ngoài. Tôi đo một ví dụ: đếm số đơn của mỗi người bằng một scalar subquery trong SELECT:

SELECT u.id, (SELECT count(*) FROM orders o WHERE o.uid = u.id) FROM users u;

Subquery này phụ thuộc u.id, nên nó chạy lại một lần cho mỗi người — EXPLAIN ghi rõ SubPlan ... loops=10000. Đây chính là điều khiến correlated subquery mang tiếng chậm: nó là một vòng lặp trá hình. Đây cũng đúng là cơ chế của truy vấn N+1 mà bài trước đo — một truy vấn gốc rồi N truy vấn con, mỗi cái cho một hàng. Khác biệt là ở N+1, vòng lặp nằm trong mã ứng dụng (mỗi vòng một round-trip mạng); ở correlated subquery, vòng lặp nằm gọn trong CSDL, nên rẻ hơn nhiều vì không mất round-trip — nhưng vẫn là một vòng lặp cần để mắt. Nhưng khi đo, kết quả lại tinh tế hơn câu chuyện thường kể:

correlated (loops=10000):  ~27 ms   (mỗi lần dùng index trên uid)
JOIN + GROUP BY:           ~105 ms

Correlated subquery ở đây nhanh hơn cả cách JOIN + GROUP BY. Vì mỗi trong 10.000 lần chạy dùng index để đếm nhanh, còn JOIN + GROUP BY phải quét và gom cả một triệu đơn. Bài học: correlated subquery chạy loops=N lần, và nó chậm chỉ khi N lớn và mỗi lần đắt (không có index). Với index và N vừa phải, nó có thể là cách nhanh nhất. Con số loops trong EXPLAIN — không phải nhãn "subquery" — mới cho bạn biết chi phí thật.

Về đến code hằng ngày

Điều đầu tiên: đừng viết lại theo châm ngôn, hãy đọc kế hoạch. "Subquery chậm, dùng join" là một quy tắc quá thô. IN và EXISTS thường được planner gộp về cùng một semi join; viết cách nào cũng vậy. Và như bài EXPLAIN đã cho thấy, kế hoạch thật kể đúng những gì xảy ra — một Semi Join khác hẳn một Hash Join kèm khử trùng, dù cùng cho một kết quả.

Điều thứ hai: cẩn thận với subquery tương quan, và đo bằng loops. Khi thấy SubPlan với loops=N lớn trong EXPLAIN, đó là dấu hiệu một vòng lặp ẩn — nếu mỗi lần đắt, đây là thủ phạm; nếu có index giữ mỗi lần rẻ, nó vẫn ổn. Gói lại bằng số: cùng một câu hỏi, IN và EXISTS cho kế hoạch y hệt (semi join, ~5ms), và semi join đó nhanh gấp ~10 lần JOIN+DISTINCT (~50ms) vì DISTINCT nối cả triệu cặp rồi khử trùng còn semi join dừng ở cặp đầu; subquery tương quan chạy loops=N, chậm chỉ khi N lớn và mỗi lần đắt (ở đây index giữ rẻ nên 27ms, nhanh hơn JOIN+GROUP BY 105ms) — khác biệt nằm ở việc truy vấn cần và số loops, không ở nhãn subquery hay join.

Và cái bẫy "chọn giải pháp theo nhãn thay vì theo việc thật sự cần làm" này không riêng gì SQL — nó là một trong những sai lầm dai dẳng nhất khi lập trình ở mọi tầng. Trong Java, người ta cãi nhau for truyền thống nhanh hơn hay Stream nhanh hơn, hay ArrayList với LinkedList — nhưng câu trả lời luôn là "còn tùy bạn làm gì với nó", đúng như IN với JOIN ở đây tùy câu hỏi là "tồn tại" hay "liệt kê". Một lệnh gọi ORM findAll().stream().filter(...) trông gọn gàng nhưng lôi cả bảng về bộ nhớ rồi mới lọc — đúng cái tội của JOIN + DISTINCT: bắt máy làm việc nặng rồi vứt phần lớn đi. Mẫu số chung đáng mang theo: tốc độ không dính vào tên của công cụ (subquery, stream, loại collection) mà dính vào lượng việc công cụ đó thật sự bắt máy làm — và cách duy nhất để biết lượng việc đó là đo, không phải nghe châm ngôn.

Muốn tự thấy thì trong psql, với hai bảng cha–con có index trên khóa ngoại, chạy EXPLAIN SELECT * FROM cha WHERE id IN (SELECT cha_id FROM con); rồi EXPLAIN SELECT * FROM cha c WHERE EXISTS (SELECT 1 FROM con WHERE con.cha_id = c.id);. So hai kế hoạch — bạn sẽ thấy chúng gần như y hệt, cùng một Semi Join, chứng tỏ IN và EXISTS là hai cách viết của cùng một phép. Rồi thử EXPLAIN ANALYZE một scalar subquery tương quan (SELECT id, (SELECT count(*) FROM con WHERE con.cha_id = cha.id) FROM cha;) và tìm dòng SubPlan với loops= — con số đó là số lần subquery chạy, và là thứ quyết định nó nhanh hay chậm, chứ không phải việc nó mang tên "subquery". Nửa phút đó chữa được cái phản xạ viết lại truy vấn theo lời đồn.