Thuật toán Join và Thứ tự Join

Bộ dữ liệu cho bài này — perf_sales và employee

Khi bạn join hai bảng, cơ sở dữ liệu chọn một thuật toán join bên trong — quy trình nó dùng để khớp các dòng từ hai bảng.

Các phương thức join khác nhau đi kèm chi phí khác nhau.

Bộ dữ liệu là bảng bán hàng perf_sales (50.000 dòng; emp_id trỏ tới nhân viên bán) và bảng nhân viên employee (30 dòng; emp_id thực sự là khóa chính).

Khi bạn join hai bảng trên emp_id, bạn sẽ xem cái nào hiện là vòng lặp ngoài trong kế hoạch và thứ tự join thay đổi thế nào tùy có chỉ mục hay không.

Trước khi đi vào bài tập, kiểm tra định nghĩa cột và một mẫu dữ liệu cho hai bảng bài này dùng — perf_sales và employee. Sinh perf_sales mất một lúc, nên lần chạy đầu có thể dừng vài giây.

① Dùng PRAGMA table_info(perf_sales); và PRAGMA table_info(employee); để xem định nghĩa cột của cả hai bảng.

② Dùng SELECT * FROM perf_sales LIMIT 5; và SELECT * FROM employee LIMIT 5; để xem trước 5 dòng đầu của mỗi cái.

③ Dùng SELECT COUNT(*) FROM perf_sales; và SELECT COUNT(*) FROM employee; để xác nhận khoảng cách số dòng giữa chúng (50.000 so với 30).

Nested loop join và thứ tự join

Một nested loop join đi qua bảng ngoài từng dòng một và, với mỗi dòng, tra cứu các dòng trong bảng trong thỏa mãn điều kiện join — một vòng lặp lồng nhau đôi.

-- So sánh cùng truy vấn join qua ba phương thức join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Dòng chảy nội bộ của nested loop join
-- for each e in employee:        -- vòng lặp ngoài (30 dòng)
--   for each s in perf_sales:    -- trong (không có chỉ mục, quét cả 50.000 dòng)
--     if s.emp_id = e.emp_id then add to the join result

• Vòng lặp ngoài chạy số lần bằng số dòng của bảng, nên đặt bảng nhỏ hơn ở ngoài
• Phía trong được tra cứu lặp lại từ mỗi dòng ngoài, nên lập chỉ mục khóa join để biến thành tra cứu một lần
• Trong kế hoạch, bảng xuất hiện đầu là ngoài, và cái xuất hiện sau là trong
• Bộ tối ưu chọn outer / inner tự động từ thống kê, nên thứ tự bạn viết trong FROM không nhất thiết được giữ

-- Join perf_sales và employee theo emp_id (tổng bán hàng mỗi nhân viên ở dept 1)
-- Không có chỉ mục trên perf_sales.emp_id, kế hoạch có xu hướng quét perf_sales trong toàn bộ
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SCAN perf_sales AS s   (không chỉ mục, nên trong cũng quét toàn bộ)

-- Thêm chỉ mục trên perf_sales.emp_id và trong có thể tra qua chỉ mục
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Xem kế hoạch cho truy vấn join đếm doanh số mỗi nhân viên, và đọc bảng nào ở vòng lặp ngoài. (Chạy đúng sẽ làm xuất hiện phần giải thích.)

① Thêm tiền tố EXPLAIN QUERY PLAN cho truy vấn join employee và perf_sales trên emp_id và đếm dòng mỗi tên nhân viên với GROUP BY, và xem kế hoạch.

② Bảng xuất hiện đầu trong đầu ra là vòng lặp ngoài, và cái sau là trong. Chưa có chỉ mục trên perf_sales.emp_id, đọc cái nào ở ngoài và phía trong được đọc thế nào.

Làm cho bảng trong của join có thể tra cứu qua chỉ mục và xác nhận kế hoạch chuyển từ SCAN sang SEARCH ... USING INDEX. Gói việc tạo chỉ mục và kiểm tra kế hoạch trong một lần thực thi.

① Xóa chỉ mục cùng tên với DROP INDEX IF EXISTS, rồi tạo chỉ mục trên cột emp_id của perf_sales với CREATE INDEX.

② Thêm tiền tố EXPLAIN QUERY PLAN cho truy vấn join employee và perf_sales trên emp_id và đếm dòng mỗi tên nhân viên, và xem kế hoạch. Xác nhận employee (30 dòng) vẫn ở vòng lặp ngoài còn perf_sales trong giờ được tra qua chỉ mục.

Bộ tối ưu chọn thứ tự join tự động từ thống kê

Thứ tự join — bảng nào lên vòng lặp ngoài — về quy tắc được chọn tự động bởi bộ tối ưu dựa trên thống kê.

Nếu bạn đã thu thập thống kê với ANALYZE (đề cập ở bài trước), bộ tối ưu có thể ước lượng chính xác hơn "bảng nào nhỏ hơn" và "liệu phía trong có tra qua chỉ mục được không" và tối ưu việc gán outer / inner.

Thứ tự bạn viết trong FROM có thể bị bộ tối ưu xáo lại.

Mẹo đọc thứ tự join: trong đầu ra EXPLAIN QUERY PLAN, bảng cao hơn gần với vòng lặp ngoài hơn.

Khi bảng sai lên vòng lặp ngoài và mọi thứ chậm lại, điều đầu tiên cần kiểm tra là liệu khóa join trên bảng bạn muốn làm trong có chỉ mục không.

-- Sau ANALYZE, outer / inner được quyết định chính xác hơn từ thống kê
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
ANALYZE;

-- Ngay cả với perf_sales đầu trong FROM, bộ tối ưu có thể đặt employee nhỏ hơn ở ngoài
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM perf_sales s
JOIN employee e ON e.emp_id = s.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Xác nhận bộ tối ưu chọn cùng thứ tự join ngay cả khi bạn đảo thứ tự bảng trong FROM. Gói việc tạo chỉ mục, thu thập thống kê, và kiểm tra kế hoạch trong một lần thực thi.

① Xóa chỉ mục cùng tên với DROP INDEX IF EXISTS, tạo chỉ mục trên emp_id của perf_sales, rồi chạy ANALYZE; để thu thập thống kê.

② Thêm tiền tố EXPLAIN QUERY PLAN cho truy vấn có FROM là FROM perf_sales s JOIN employee e ON ... (bảng lớn hơn viết trước trong FROM) và đếm dòng mỗi tên nhân viên, và xem kế hoạch. Đọc liệu bộ tối ưu vẫn chọn employee 30 dòng cho vòng lặp ngoài ngay cả khi thứ tự FROM bị lật.

Hash join và sort-merge join — phương thức join dùng bởi cơ sở dữ liệu khác

Cơ sở dữ liệu lớn (PostgreSQL / Oracle / SQL Server và các loại) cũng dùng hash join (xây bảng hash từ phía nhỏ hơn và quét cái còn lại vào nó) và sort-merge join (sắp xếp cả hai phía theo khóa join và đi qua đồng bộ) cùng với nested loop join.

Engine vận hành console trình duyệt của khóa học này chỉ dùng nested loop, nên phần này nói về hai phương thức kia ở mức sơ đồ và khái niệm.

Hash join — biến phía nhỏ hơn thành bảng hash và truyền cái còn lại qua

-- Cùng truy vấn, về khái niệm chạy như hash join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Dòng chảy nội bộ của hash join
-- H := { e.emp_id => e | e in employee }    -- (1) Build (biến employee thành bảng hash)
-- for each s in perf_sales:                  -- (2) Probe (truyền perf_sales qua)
--   if H[s.emp_id] exists: add to the join result

• Đặt bảng nhỏ hơn ở phía build giữ bảng hash đủ nhỏ để vừa bộ nhớ, làm mọi thứ nhanh
• Chỉ hoạt động cho join bằng (=); điều kiện phạm vi (< / BETWEEN) không thể join theo cách này
• Có thể join số dòng lớn ở cả hai phía với một lần đi qua mỗi phía ngay cả không có chỉ mục trong, nên thường nhanh hơn nested loop
• Xuất hiện như Hash Join trong EXPLAIN của cơ sở dữ liệu production

Sort-merge join — sắp xếp cả hai phía, rồi đi qua cùng nhau

-- Cùng truy vấn, về khái niệm chạy như sort-merge join
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Dòng chảy nội bộ của sort-merge join
-- E := sort(employee by emp_id)        -- (1) Sort (sắp xếp cả hai theo emp_id)
-- S := sort(perf_sales by emp_id)
-- i, j := 0, 0
-- while i < |E| and j < |S|:            -- (2) Merge
--   if E[i].emp_id = S[j].emp_id: add to the join result, j++
--   else if E[i].emp_id < S[j].emp_id: i++
--   else: j++

• Nếu cả hai phía đã sắp xếp (xếp theo chỉ mục chẳng hạn), chi phí sort về cơ bản bằng không và cực nhanh
• Xử lý cả join phạm vi (điều kiện join bao gồm < hay BETWEEN) — sức mạnh hash join không có
• Kết quả đến đã sắp theo khóa join, tiện cho các tổng hợp và merge sau
• Xuất hiện như Merge Join trong EXPLAIN của cơ sở dữ liệu production

Hash join và sort-merge join là phương thức join của các RDBMS khác

Hash join và sort-merge join là các phương thức join cung cấp bởi cơ sở dữ liệu lớn như PostgreSQL / Oracle / SQL Server.

Engine vận hành console trình duyệt của khóa học này chỉ dùng nested loop làm thuật toán join (nó có thể tạo chỉ mục nội bộ tạm để hỗ trợ join nếu cần), nên hash join và sort-merge join không thể trình diễn trực tiếp trong console này.

Với những cái đó chúng ta hài lòng với các sơ đồ và code chỉ đọc ở trên để nắm ý tưởng.

Trong khi đó, vòng lặp outer / inner của nested loop join, thứ tự join, và sự lật từ SCAN sang SEARCH ở phía trong do chỉ mục dẫn dắt, tất cả đề cập trước trong bài này, là quan sát được thật.

Khả năng đọc cơ sở dữ liệu chọn phương thức join nào dựa trên cùng hiểu biết về nested loop và thứ tự join.

Cơ sở dữ liệu production sẽ hiển thị các thuật ngữ như Hash Join / Merge Join trong EXPLAIN của chúng, nên bắt đầu bằng việc thoải mái đọc kế hoạch nested loop trong khóa học này.

-- Dưới đây là cách EXPLAIN có thể trông như trong PostgreSQL (chỉ đọc; không chạy trong console khóa học này)
-- EXPLAIN SELECT e.name, SUM(s.amount) FROM employee e
--   JOIN perf_sales s ON s.emp_id = e.emp_id GROUP BY e.name;
-- Kế hoạch ví dụ:
--   Hash Join  (xây bảng hash từ employee, rồi truyền perf_sales)
--   hoặc Merge Join (sắp cả hai theo emp_id, rồi khớp lên)
-- PostgreSQL chọn giữa các phương thức này tự động dựa trên thống kê và chi phí

-- Điều console khóa học này có thể thực sự trình diễn là (nested loop):
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee / SEARCH perf_sales USING INDEX ix_sales_emp (emp_id=?)

Như tóm tắt cho bài này, kiểm tra kế hoạch join thêm một lần với chỉ mục đặt và đọc vòng lặp ngoài, truy cập chỉ mục bên trong, và ý nghĩa của kết quả. Gói việc tạo chỉ mục, kiểm tra kế hoạch, và kiểm tra kết quả trong một lần thực thi.

① Xóa chỉ mục cùng tên với DROP INDEX IF EXISTS, rồi tạo chỉ mục trên emp_id của perf_sales.

② Thêm tiền tố EXPLAIN QUERY PLAN cho truy vấn join employee và perf_sales trên emp_id và đếm doanh số mỗi tên nhân viên, và xem kế hoạch.

③ Chạy cùng truy vấn tổng hợp (không có EXPLAIN QUERY PLAN) với ORDER BY cnt DESC LIMIT 5; để lấy top 5 nhân viên theo số đếm. Đọc cả kế hoạch và kết quả thực.