Giao diện
Thuật toán join
Viết JOIN trong SQL chỉ nói muốn kết quả gì; database tự chọn làm thế nào để ghép hai bảng. Có ba cách làm chính: nested loop, hash join và merge join. Cùng một câu query có thể chạy trong 1 mili giây hay 40 giây tuỳ cách database chọn, và tuỳ index ta tạo cho nó.
Biết các thuật toán này giúp đọc được EXPLAIN, đặt index đúng chỗ, và hiểu vì sao một câu join đột nhiên chậm. Phần MySQL cụ thể (thứ tự join, STRAIGHT_JOIN, LEFT JOIN biến thành INNER JOIN) nằm ở MySQL chương 5 và chương 4.
Mọi số liệu trong trang được chạy thật ngày 2026-10-16 trên MySQL 8.0.46 và PostgreSQL 17 (Docker trên laptop). Dữ liệu là bảng customers 100.000 dòng và bảng orders 1.000.000 dòng, mỗi khách khoảng 10 đơn.
Ba thuật toán
Ví dụ dùng câu customers JOIN orders ON orders.customer_id = customers.id. Bảng duyệt trước gọi là bảng ngoài, bảng được tra theo từng dòng của bảng ngoài gọi là bảng trong.
Nested loop
Với mỗi dòng của bảng ngoài, duyệt bảng trong để tìm dòng khớp. Giống hai vòng for lồng nhau (MySQL: Nested-Loop Join Algorithms).
- Không có index trên bảng trong: mỗi dòng ngoài phải quét cả bảng trong. Bảng ngoài N dòng, bảng trong M dòng thì là N × M phép so sánh. Tài liệu PostgreSQL nói thẳng cách này “có thể rất tốn thời gian” (PostgreSQL: Planner/Optimizer).
- Có index trên cột join của bảng trong: mỗi dòng ngoài chỉ cần một lần seek index, đi từ gốc xuống lá B+Tree (vài page). Đây là cách chạy phổ biến nhất trong ứng dụng web: lấy một ít dòng ở bảng ngoài, tra sang bảng trong bằng index.
Hash join
Hai giai đoạn:
- Build: đọc bảng nhỏ hơn, đưa vào một bảng băm trong RAM, với key là cột join.
- Probe: đọc bảng còn lại một lượt; mỗi dòng tra bảng băm để tìm dòng khớp.
Mỗi bảng chỉ đọc một lần, nên tổng công việc khoảng N + M, và không cần index trên cột join. Đổi lại, hash join chỉ dùng được cho phép so sánh bằng (=), và cần bộ nhớ cho bảng băm:
- PostgreSQL: giới hạn bởi
work_mem(mặc định 4 MB) nhânhash_mem_multiplier(mặc định 2). Giới hạn này tính cho từng thao tác, không phải cho cả câu query; một query có nhiều thao tác hash, sort chạy cùng lúc thì mỗi thao tác được dùng ngần ấy (PostgreSQL: Resource Consumption). Không đủ bộ nhớ thì chia thành nhiều đợt (batch) và ghi tạm ra đĩa. - MySQL: giới hạn bởi
join_buffer_size; vượt quá thì dùng file trên đĩa (MySQL: Hash Join Optimization).
Merge join
Sắp hai bảng theo cột join (hoặc đọc theo index đã có thứ tự), rồi đi song song trên hai dãy như khi trộn hai danh sách đã sắp xếp: bên nào nhỏ hơn thì tiến lên một bước, bằng nhau thì ghép. Mỗi bảng chỉ đọc một lần. Nếu phải sort trước thì tốn thêm chi phí sort. PostgreSQL có merge join; MySQL thì không, MySQL chỉ có nested loop và hash join.
Thử: customers JOIN orders ON orders.customer_id = customers.idKhi bảng lớn dần: số phép toán ước lượng
Bước 0/32
customers
| 3 | Chi |
| 1 | An |
| 4 | Dũng |
| 2 | Bình |
orders
| 101 | cid 2 |
| 102 | cid 4 |
| 103 | cid 1 |
| 104 | cid 2 |
| 105 | cid 9 |
| 106 | cid 3 |
| 107 | cid 4 |
| 108 | cid 1 |
Kết quả (0 dòng)
Bấm “Bước tiếp” để bắt đầu.
0phép so sánh / tra cứu đã làm
Thanh dùng thang log: mỗi đoạn dài thêm nghĩa là gấp nhiều lần. Ước lượng thô để so bậc độ lớn, giả định mỗi dòng ngoài khớp ít dòng trong; số đo thật ở bảng bên dưới trang.
Kết quả chạy thật
Mỗi phép thử chạy hai ngày (16/10 và 19/10) trên cùng một laptop. Con số tuyệt đối lệch khá nhiều giữa hai ngày, nhưng thuật toán được chọn và tỉ lệ giữa các cách làm thì giữ nguyên.
PostgreSQL 17
| Câu query | Thuật toán | 16/10 | 19/10 |
|---|---|---|---|
Đơn của một khách (lọc theo email), có index trên orders.customer_id | Nested loop, tra index | 1 ms | 0,12 ms |
| Như trên, nhưng join trên cột không có index | Hash join, quét cả 1 triệu đơn | 41 ms | 35 ms |
| Tổng tiền theo quốc gia, join cả hai bảng | Hash join (song song 3 worker) | 249 ms | 114 ms |
| Như trên, tắt hash join | Merge join qua hai index | 303 ms | 284 ms |
| 2.000 khách × 20.000 đơn, không index | Hash join | 2,9 ms | 2,3 ms |
| Như trên, ép nested loop | Nested loop, loại bỏ 39.999.596 cặp không khớp | 3.396 ms | 2.728 ms |
Hash join với work_mem = 64kB (16 batch), so với đủ bộ nhớ (1 batch) | Hash join | 98 ms so với 73 ms | 83 ms so với 63 ms |
MySQL 8.0
| Câu query | Thuật toán | 16/10 | 19/10 |
|---|---|---|---|
| Đơn của một khách, có index | Tra index | 0,4 ms | 0,05 ms |
| Như trên, join trên cột không có index | Quét cả 1 triệu đơn | 787 ms | 134 ms |
| Tổng tiền theo quốc gia, join cả hai bảng | Nested loop, tra index 100.000 lần | 2,7–3,0 s; 10,7 s lần đầu khi cache lạnh | 1,6–2,8 s |
| Như trên, chặn index bằng hint để MySQL dùng hash join | Hash join | 0,89 s; 2,3 s lần đầu | 0,43–0,44 s |
| 2.000 khách × 20.000 đơn, không index | Hash join | 22 ms | 4,7 ms |
Như trên, ép nested loop (hint NO_BNL) | Nested loop, quét bảng trong 2.000 lần | 40.990 ms | 7.793 ms |
Join cột INT với cột VARCHAR có index | Quét cả index 1 triệu mục | 642 ms (so với 0,02 ms khi cùng kiểu) | 131 ms (so với 0,004 ms) |
Buffer pool MySQL để mặc định 128 MB, nhỏ hơn dữ liệu, nên lần chạy đầu khi cache còn lạnh phải đọc đĩa nhiều.
Năm điều rút ra:
- Lấy ít dòng thì nested loop có index thắng tuyệt đối: nhanh hơn từ 40 tới vài trăm lần so với khi cột join không có index, ở cả hai database. Đây là lý do cột khoá ngoại luôn cần index.
- Nested loop không index là thảm hoạ: cùng hai bảng nhỏ, hash join mất vài mili giây, còn nested loop mất vài giây trên PostgreSQL và từ 8 tới 41 giây trên MySQL, tức là chậm hơn hàng nghìn lần. Số cặp phải so tăng theo tích hai bảng.
- Join cả bảng lớn thì hash join thường nhanh hơn nested loop có index, vì đọc tuần tự một lượt rẻ hơn hàng trăm nghìn lần seek ngẫu nhiên. PostgreSQL tự chọn hash join. MySQL vẫn chọn nested loop dù chậm hơn từ 3 tới 6 lần, vì MySQL chỉ dùng hash join khi không có index nào dùng được cho điều kiện join (MySQL: Hash Join Optimization).
- Thiếu bộ nhớ thì hash join chậm đi, chứ không lỗi: PostgreSQL chia làm 16 batch và chạy chậm hơn khoảng 30%.
- Lệch kiểu dữ liệu làm mất index: MySQL phải đổi từng giá trị
VARCHARsang số để so, nên quét cả index. Đổi cùng kiểu thì lại tra index bình thường.
Optimizer chọn thuật toán thế nào
| PostgreSQL | MySQL | |
|---|---|---|
| Thuật toán có | Nested loop, hash join, merge join | Nested loop, hash join |
| Cách chọn | Sinh mọi kế hoạch cho từng cặp bảng, ước tính chi phí, chọn cái rẻ nhất (Planner/Optimizer) | Có index dùng được cho điều kiện join thì nested loop; không có thì hash join |
| Thứ tự join | Gần như thử hết khi số bảng nhỏ hơn geqo_threshold; nhiều bảng hơn thì dùng thuật toán heuristic (GEQO) | Optimizer tự chọn cho INNER JOIN; ép bằng STRAIGHT_JOIN hoặc hint JOIN_ORDER |
| Điều khiển bằng tay | SET enable_hashjoin = off, enable_mergejoin, enable_nestloop (chỉ để thử nghiệm) | Hint BNL / NO_BNL, NO_INDEX, JOIN_ORDER |
Optimizer dựa vào thống kê (số dòng, phân bố giá trị) để ước tính. Thống kê cũ hoặc sai thì có thể chọn sai thuật toán: tưởng bảng ngoài có 10 dòng nên chọn nested loop, thực tế lại có 1 triệu dòng. Chạy ANALYZE (PostgreSQL) hoặc ANALYZE TABLE (MySQL) sau khi dữ liệu thay đổi nhiều.
Đọc EXPLAIN
| Thấy trong EXPLAIN | Nghĩa |
|---|---|
MySQL Nested loop inner join với dòng con Index lookup on o using customer_id | Nested loop có index. Xem loops=: số lần tra index |
MySQL Inner hash join với khối Hash bên dưới | Hash join; bảng trong khối Hash là bảng dựng bảng băm |
MySQL Filter: (o.customer_code = '42') trên Index scan hoặc Table scan 1 triệu dòng | Không tra được index, phải quét hết rồi lọc |
PostgreSQL Nested Loop + Index Scan hoặc Bitmap Index Scan ở nhánh trong | Nested loop có index |
PostgreSQL Nested Loop + Join Filter + Rows Removed by Join Filter rất lớn | Nested loop không index: dấu hiệu nguy hiểm nhất |
PostgreSQL Hash Join + Hash … Batches: 16 | Hash join không đủ work_mem, phải chia batch ra đĩa |
PostgreSQL Merge Join + Sort | Merge join phải sort trước; có Index Scan thay cho Sort thì không cần sort |
Cách đọc EXPLAIN của MySQL nói chung: MySQL chương 5.
Những lý do hay làm join chậm
| Nguyên nhân | Cách sửa |
|---|---|
| Cột join ở bảng trong không có index | Thêm index trên cột khoá ngoại (MySQL chương 4) |
Hai cột join khác kiểu (INT với VARCHAR) hoặc khác collation | Thống nhất kiểu và collation trong schema |
Bọc cột join trong hàm (ON DATE(o.created_at) = d.day) | Đổi thành điều kiện khoảng, hoặc dùng cột sinh có index |
| Join cả bảng lớn trên MySQL bị nested loop | Hỏi lại có thật cần join cả bảng không: bảng tổng hợp (Bộ đếm & bảng tổng hợp), chạy báo cáo trên hệ OLAP (OLTP vs OLAP); hoặc dùng hint |
| Hash join thiếu bộ nhớ | PostgreSQL: tăng work_mem cho riêng session chạy báo cáo, không tăng cho toàn server; MySQL: join_buffer_size |
| Thống kê cũ làm optimizer chọn sai | ANALYZE / ANALYZE TABLE |
Join nhiều – nhiều làm số dòng nhân lên rồi mới GROUP BY | Gộp từng phía trước rồi mới join (Bẫy của ORM) |
| Dữ liệu nằm ở hai service hoặc hai shard | Không join được trong database; join ở tầng app bằng WHERE id IN (…) theo lô, tránh N+1 query |
Ghi nhớ
- Ba thuật toán: nested loop (có hoặc không index), hash join (build bảng nhỏ, probe bảng lớn, chỉ cho
=), merge join (đi song song trên hai dãy đã sắp; MySQL không có). - Lấy ít dòng: nested loop có index nhanh nhất, nhanh hơn từ 40 tới vài trăm lần so với khi cột join không có index. Không index thì nested loop tăng theo N × M, chậm hơn hash join hàng nghìn lần (vài giây tới vài chục giây so với vài mili giây).
- Join cả bảng lớn: hash join thường thắng. PostgreSQL tự chọn theo chi phí; MySQL chỉ dùng hash join khi không có index nào cho điều kiện join.
- Hash join cần bộ nhớ: PostgreSQL
work_mem×hash_mem_multipliercho mỗi thao tác, MySQLjoin_buffer_size; thiếu thì chia batch ra đĩa. - Đọc EXPLAIN:
loops=,Rows Removed by Join Filter,Batches,FiltertrênTable scanlà các dấu hiệu cần để ý. - Lệch kiểu dữ liệu, bọc hàm, thống kê cũ đều làm mất index hoặc chọn sai thuật toán.
Nguồn tham khảo
Đã chạy thử ngày 2026-10-16 trên MySQL 8.0.46 và PostgreSQL 17 (Docker, cấu hình mặc định, buffer pool MySQL 128 MB). Mọi thời gian là kết quả EXPLAIN ANALYZE. Hint dùng để ép thuật toán: PostgreSQL SET enable_hashjoin/enable_mergejoin = off; MySQL NO_BNL, NO_INDEX. Mô phỏng chạy từng bước là minh hoạ trên bảng nhỏ; phần ước lượng số phép toán là công thức thô, không phải số đo.
Tài liệu chính thức đã đối chiếu (ngày 2026-10-16):
| Nguồn | Dùng cho phần |
|---|---|
| PostgreSQL, Planner/Optimizer | Mô tả nested loop, merge join, hash join; chọn kế hoạch rẻ nhất theo ước tính; tìm thứ tự join gần như đầy đủ dưới geqo_threshold, trên đó dùng heuristic |
| PostgreSQL, Resource Consumption | work_mem mặc định 4 MB, tính cho từng thao tác; hash_mem_multiplier mặc định 2 |
| MySQL 8.4, Hash Join Optimization | Hash join khi mọi join có điều kiện bằng và không có index dùng được cho điều kiện join; join_buffer_size, dùng file trên đĩa khi thiếu; hint BNL / NO_BNL |
| MySQL 8.4, Nested-Loop Join Algorithms | Mô tả nested loop |
Chưa đối chiếu, từ kiến thức chung:
- MySQL không có merge join.
- MySQL có hash join từ 8.0.18 và thay hẳn block nested loop từ 8.0.20 (đã ghi ở MySQL chương 5); trang hash join của tài liệu 8.4 không nhắc phiên bản.
- Giá trị mặc định của
geqo_threshold(PostgreSQL).
Code đã dùng để chạy thử
Script nằm trong thư mục lab/join/ của repo. Tự chạy lại bằng npm run lab:up rồi npm run lab -- join (cách chạy). Hai cột 16/10 và 19/10 trong bảng kết quả là hai lần chạy các script này.
setup-pg.sql, setup-mysql.sql: 100.000 khách, 1.000.000 đơn
sql
-- Dữ liệu cho trang database/join trên PostgreSQL: 100.000 khách, 1.000.000 đơn (mỗi khách khoảng 10 đơn).
-- customer_id có index; customer_id2 cùng giá trị nhưng không có index, để so sánh.
DROP TABLE IF EXISTS orders, customers, c_small, o_small;
CREATE TABLE customers (id INT PRIMARY KEY, email TEXT NOT NULL, country TEXT NOT NULL);
INSERT INTO customers SELECT g, 'c' || g || '@x.vn', (ARRAY['VN','SG','JP','US','DE'])[1 + g % 5] FROM generate_series(1, 100000) g;
CREATE UNIQUE INDEX ON customers (email);
CREATE TABLE orders (id INT PRIMARY KEY, customer_id INT NOT NULL, customer_id2 INT NOT NULL, amount INT NOT NULL);
INSERT INTO orders SELECT g, c, c, (g * 7) % 500 FROM (SELECT g, 1 + (hashint4(g) & 2147483647) % 100000 AS c FROM generate_series(1, 1000000) g) s;
CREATE INDEX ON orders (customer_id);
CREATE TABLE c_small AS SELECT * FROM customers WHERE id <= 2000;
CREATE TABLE o_small AS SELECT * FROM orders WHERE id <= 20000;
ANALYZE;
SELECT (SELECT COUNT(*) FROM customers) AS customers, (SELECT COUNT(*) FROM orders) AS orders;sql
-- Dữ liệu cho trang database/join trên MySQL: 100.000 khách, 1.000.000 đơn.
-- customer_id có index; customer_id2 không có index; customer_code là VARCHAR (để thử join lệch kiểu).
DROP TABLE IF EXISTS orders;
DROP TABLE IF EXISTS customers;
DROP TABLE IF EXISTS c_small;
DROP TABLE IF EXISTS o_small;
SET SESSION cte_max_recursion_depth = 2000000;
CREATE TABLE customers (id INT PRIMARY KEY, email VARCHAR(50) NOT NULL, country CHAR(2) NOT NULL, UNIQUE KEY (email));
INSERT INTO customers WITH RECURSIVE s AS (SELECT 1 AS g UNION ALL SELECT g + 1 FROM s WHERE g < 100000)
SELECT g, CONCAT('c', g, '@x.vn'), ELT(1 + g % 5, 'VN','SG','JP','US','DE') FROM s;
CREATE TABLE orders (id INT PRIMARY KEY, customer_id INT NOT NULL, customer_id2 INT NOT NULL, customer_code VARCHAR(20) NOT NULL, amount INT NOT NULL, KEY (customer_id), KEY (customer_code));
INSERT INTO orders WITH RECURSIVE s AS (SELECT 1 AS g UNION ALL SELECT g + 1 FROM s WHERE g < 1000000)
SELECT g, c, c, CAST(c AS CHAR), (g * 7) % 500 FROM (SELECT g, 1 + (CRC32(g) % 100000) AS c FROM s) x;
CREATE TABLE c_small AS SELECT * FROM customers WHERE id <= 2000;
CREATE TABLE o_small AS SELECT * FROM orders WHERE id <= 20000;
ANALYZE TABLE customers, orders, c_small, o_small;
SELECT (SELECT COUNT(*) FROM customers) AS customers, (SELECT COUNT(*) FROM orders) AS orders;join-pg.sql: các phép thử trên PostgreSQL
sql
-- Các phép thử join trên PostgreSQL. Thời gian lấy từ EXPLAIN ANALYZE (Execution Time).
\echo '=== Join chọn lọc (một khách), có index trên orders.customer_id'
EXPLAIN (ANALYZE, COSTS OFF) SELECT o.id, o.amount FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.email = 'c42@x.vn';
\echo '=== Join gộp cả hai bảng'
EXPLAIN (ANALYZE, COSTS OFF) SELECT c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
\echo '=== Join chọn lọc trên cột không có index (customer_id2)'
EXPLAIN (ANALYZE, COSTS OFF) SELECT o.id, o.amount FROM customers c JOIN orders o ON o.customer_id2 = c.id WHERE c.email = 'c42@x.vn';
\echo '=== 2.000 x 20.000 không index: để tự chọn (hash join), rồi ép nested loop'
EXPLAIN (ANALYZE, COSTS OFF) SELECT COUNT(*) FROM c_small c JOIN o_small o ON o.customer_id2 = c.id;
SET enable_hashjoin = off; SET enable_mergejoin = off;
EXPLAIN (ANALYZE, COSTS OFF) SELECT COUNT(*) FROM c_small c JOIN o_small o ON o.customer_id2 = c.id;
RESET enable_hashjoin; RESET enable_mergejoin;
\echo '=== Ép merge join cho join gộp cả bảng'
SET enable_hashjoin = off;
EXPLAIN (ANALYZE, COSTS OFF) SELECT c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
RESET enable_hashjoin;
\echo '=== Hash join với work_mem = 64kB (chia batch), rồi với work_mem mặc định'
SET work_mem = '64kB';
EXPLAIN (ANALYZE, COSTS OFF) SELECT COUNT(*) FROM orders o JOIN customers c ON c.id = o.customer_id2 WHERE c.country = 'VN';
RESET work_mem;
EXPLAIN (ANALYZE, COSTS OFF) SELECT COUNT(*) FROM orders o JOIN customers c ON c.id = o.customer_id2 WHERE c.country = 'VN';join-mysql.sql: các phép thử trên MySQL
sql
-- Các phép thử join trên MySQL. Thời gian lấy từ EXPLAIN ANALYZE (actual time của node trên cùng).
-- Join gộp cả bảng chạy vài lần vì lần đầu cache còn lạnh (buffer pool mặc định 128 MB).
SELECT '=== Join chọn lọc (một khách), có index' AS step;
EXPLAIN ANALYZE SELECT o.id, o.amount FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.email = 'c42@x.vn';
SELECT '=== Join gộp cả hai bảng (3 lần): MySQL tự chọn nested loop tra index' AS step;
EXPLAIN ANALYZE SELECT c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
EXPLAIN ANALYZE SELECT c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
EXPLAIN ANALYZE SELECT c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
SELECT '=== Chỉ chặn index của orders: MySQL đảo thứ tự, vẫn nested loop (tra khoá chính customers)' AS step;
EXPLAIN ANALYZE SELECT /*+ NO_INDEX(o customer_id) */ c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
SELECT '=== Chặn cả hai index: hash join (2 lần)' AS step;
EXPLAIN ANALYZE SELECT /*+ NO_INDEX(o customer_id) NO_INDEX(c PRIMARY) */ c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
EXPLAIN ANALYZE SELECT /*+ NO_INDEX(o customer_id) NO_INDEX(c PRIMARY) */ c.country, SUM(o.amount) FROM orders o JOIN customers c ON c.id = o.customer_id GROUP BY c.country;
SELECT '=== Join chọn lọc trên cột không có index' AS step;
EXPLAIN ANALYZE SELECT o.id, o.amount FROM customers c JOIN orders o ON o.customer_id2 = c.id WHERE c.email = 'c42@x.vn';
SELECT '=== 2.000 x 20.000 không index: hash join, rồi ép nested loop bằng NO_BNL' AS step;
EXPLAIN ANALYZE SELECT COUNT(*) FROM c_small c JOIN o_small o ON o.customer_id2 = c.id;
EXPLAIN ANALYZE SELECT /*+ NO_BNL(c, o) */ COUNT(*) FROM c_small c JOIN o_small o ON o.customer_id2 = c.id;
SELECT '=== INT join VARCHAR: mất index; ép cùng kiểu thì tra index lại được' AS step;
EXPLAIN ANALYZE SELECT o.id FROM customers c JOIN orders o ON o.customer_code = c.id WHERE c.email = 'c42@x.vn';
EXPLAIN FORMAT=TREE SELECT o.id FROM customers c JOIN orders o ON o.customer_code = CAST(c.id AS CHAR) WHERE c.email = 'c42@x.vn';
EXPLAIN ANALYZE SELECT o.id FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.email = 'c42@x.vn';