JOIN: ba thuật toán

PostgreSQL có đúng ba cách nối hai bảng. Bộ tối ưu chọn một trong ba dựa trên chi phí ước lượng, và phần lớn thời gian nó chọn đúng. Phần này ép chạy cả ba trên cùng một truy vấn để xem chúng thật sự chênh nhau bao nhiêu — và tìm ra một dải mà lựa chọn của bộ tối ưu không phải là nhanh nhất.

Bảng đo

500.000 khách hàng nối 2.000.000 đơn hàng, có chỉ mục trên cả hai cột nối:

create table kh(id int primary key, ten text, tinh int);         -- 25 MB
create table dh(id bigserial primary key, kh_id int, ...);        -- 115 MB
create index dh_kh on dh(kh_id);

Truy vấn thay đổi số khách hàng được lọc, để quét qua toàn dải độ chọn lọc:

select count(*) from kh k join dh d on d.kh_id = k.id where k.id <= :n;

Ép từng thuật toán bằng enable_nestloop, enable_hashjoin, enable_mergejoin.

Kết quả

Hai điều đọc ra được.

Nested Loop đúng ở dải hẹp, và đúng một cách áp đảo: 0,18 ms so với 54,42 ms của Hash — nhanh gấp 300 lần. Nó lặp qua từng dòng bên ngoài rồi tra chỉ mục bên trong; với 100 dòng ngoài thì đó là 100 lần tra chỉ mục, mỗi lần vài micro giây.

Merge Join nhanh nhất từ 10.000 trở lên, mà bộ tối ưu không chọn nó lần nào. Ở mức 100.000, Merge mất 25,91 ms còn Hash — cái được chọn — mất 82,85 ms. Chậm gấp 3,2 lần so với lựa chọn tốt nhất.

Vì sao bộ tối ưu chọn sai

Xem chi phí ước lượng của hai kế hoạch ở mức 100.000:

Parallel Hash Join   cost = 2839,68..28066,54
Merge Join           cost = 1,17..37909,03

Bộ tối ưu so 28.066 với 37.909 và chọn Hash. Thực tế thì ngược lại.

Kế hoạch Merge Join cho thấy vì sao nó nhanh:

Merge Join  (actual time=0,218..25,197 rows=133520)
  Merge Cond: (d.kh_id = k.id)
  ->  Parallel Index Only Scan using dh_kh on dh d   (actual time=0,014..7,122)
  ->  Index Only Scan using kh_pkey on kh k          (actual time=0,023..5,638)
        Index Cond: (id <= 100000)

Không có bước Sort nào. Merge Join thường bị coi là đắt vì nó cần dữ liệu đã sắp xếp, nhưng ở đây cả hai bên đều đọc thẳng từ chỉ mục B-tree — mà chỉ mục B-tree vốn đã có thứ tự. Nó chỉ việc đi song song hai danh sách đã sắp và ghép lại.

Ước lượng chi phí cho Parallel Index Only Scan là 30.969, trong khi thực tế nó chỉ mất 7,1 ms. Mô hình chi phí đánh giá việc đọc chỉ mục tuần tự đắt hơn thực tế nhiều — đó là chỗ lệch.

Tôi không coi đây là lỗi cần báo. Mô hình chi phí phải hoạt động trên mọi phần cứng, và giả định của nó thận trọng với đĩa quay. Nhưng nó là lý do cụ thể để biết enable_hashjoin = off tồn tại: khi bạn có một truy vấn báo cáo chạy hàng ngày và đo thấy Merge nhanh hơn, ép nó là hợp lý.

Bỏ chỉ mục thì mọi thứ đảo ngược

Xoá dh_kh rồi đo lại:

Nested Loop từ 0,18 ms lên 260 ms — chậm hơn 1.400 lần. Không còn chỉ mục để tra, mỗi dòng bên ngoài buộc phải quét toàn bộ bảng trong.

Merge Join phải thêm bước Sort cho bên không có chỉ mục, mất luôn lợi thế.

Hash Join thì gần như không đổi (50–85 ms so với 54–82 ms trước đó). Đây chính là đặc điểm của nó: nó không cần chỉ mục và không cần thứ tự. Nó quét một lần bên nhỏ để dựng bảng băm, quét một lần bên lớn để tra. Chi phí phụ thuộc vào kích thước hai bảng chứ không phụ thuộc vào cấu trúc.

Đó là lý do Hash Join là lựa chọn mặc định cho các truy vấn phân tích trên bảng chưa được đánh chỉ mục — nó là thuật toán không đòi hỏi gì cả.

Tôi cũng thử ép Nested Loop trên hai bảng một triệu dòng không có chỉ mục nào. Đó là 10¹² phép so sánh, và tôi phải huỷ truy vấn sau vài phút. Con số ấy đáng nhớ hơn bất kỳ phép đo nào: Nested Loop không có chỉ mục là O(n×m), và nó không "chậm" mà là "không bao giờ xong".

work_mem và số lô băm

Hash Join dựng bảng băm trong work_mem. Không đủ chỗ thì nó chia dữ liệu thành nhiều lô, xử lý từng lô một, và ghi phần chưa tới lượt ra đĩa tạm.

Kết quả không như tôi chờ đợi: 1 MB với 16 lô nhanh hơn 16 MB với 1 lô, và ba lần đo đều thống nhất nên không phải nhiễu.

Lý do là dựng một bảng băm 23 MB tốn thời gian cấp phát và ghi bộ nhớ nhiều hơn phần tiết kiệm được từ việc bỏ 16 lô. Nói cách khác, "chia lô" không đắt như tên gọi của nó gợi ra — dữ liệu vẫn nằm trong bộ nhớ đệm hệ điều hành, không thật sự chạm đĩa (Disk Usage bằng 0 ở mọi mức).

Bài học thực dụng: nâng work_mem để tránh chia lô là lời khuyên hay gặp, nhưng nó chỉ đáng khi bạn thấy Disk Usage khác 0 trong EXPLAIN (ANALYZE, BUFFERS). Nâng mù quáng vừa tốn RAM vừa có thể chậm hơn.

Và nhớ rằng work_mem là cho mỗi nút của mỗi truy vấn, không phải cho cả máy chủ. Một truy vấn có ba phép nối băm chạy song song hai tiến trình phụ có thể dùng tới sáu lần work_mem cùng lúc.

Cái bẫy đã làm hỏng lần đo đầu tiên

Lần chạy đầu, mọi mức độ chọn lọc đều ra Hash Join, kể cả khi chỉ lọc một khách hàng. Kế hoạch cho thấy:

Parallel Seq Scan on kh k  (cost=0.00..5161.00 rows=52933)
  Filter: (id <= 1)
  Rows Removed by Filter: 166666

Ước lượng 52.933 dòng cho điều kiện id <= 1. Con số đó tương ứng với độ chọn lọc 1/3 — giá trị mặc định PostgreSQL dùng khi không có thống kê.

Nguyên nhân:

psql -c "vacuum analyze kh; vacuum analyze dh"
ERROR:  VACUUM cannot run inside a transaction block

psql -c gộp nhiều lệnh trong một chuỗi thành một giao dịch, và VACUUM không chạy được trong giao dịch (phần 22 đã gặp đúng chuyện này ở một ngữ cảnh khác). Cả hai lệnh đều không chạy, và vì tôi đã chuyển đầu ra sang /dev/null nên không thấy thông báo lỗi.

Hậu quả: Hash Join 64,32 ms thay vì Nested Loop 0,08 ms — chậm 800 lần, cho một truy vấn trả về vài dòng.

Điều đáng sợ là truy vấn vẫn chạy đúng. Không có lỗi, không có cảnh báo, chỉ chậm. Trên máy chủ thật, một bảng mới nạp dữ liệu mà chưa kịp ANALYZE cho ra đúng triệu chứng này — và triệu chứng ấy tự biến mất sau khi autovacuum chạy, khiến việc chẩn đoán càng khó.

Cách tách lệnh cho đúng:

psql -c "vacuum analyze kh"
psql -c "vacuum analyze dh"
# hoặc
psql <<'SQL'
vacuum analyze kh;
vacuum analyze dh;
SQL

Dạng heredoc chạy được vì psql gửi từng lệnh riêng khi đọc từ đầu vào chuẩn.

Bảng tóm tắt

Cách nhớ ngắn gọn: Nested Loop là "tra từng cái", Hash Join là "dựng bảng tra", Merge Join là "kéo khoá kéo". Và cả ba đều đúng — chỉ khác nhau ở giả định về dữ liệu.

Thử ba mươi giây

Lấy một truy vấn có JOIN mà bạn thấy chậm:

explain (analyze, buffers) <truy vấn của bạn>;

Ba thứ cần nhìn:

1. Nút nối là gì. Nếu là Nested Loop mà bên trong là Seq Scan thì bạn đang thiếu chỉ mục trên cột nối — đó là ca chậm 1.400 lần ở trên.
2. Ước lượng lệch bao nhiêu. rows= so với actual rows= chênh trên 100 lần nghĩa là bộ tối ưu đang chọn dựa trên thông tin sai (phần 20).
3. Disk Usage có khác 0 không. Nếu có thì work_mem đáng nâng; nếu không thì đừng.

Phần sau đo truy vấn con, CTE, và chỗ CTE chặn tối ưu hoá — kèm so sánh trực tiếp giữa hành vi trước và sau PostgreSQL 12.