Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Database & ORMSenior22 phút đọc

JOIN chạy thế nào (nested loop, hash join, merge join) và khi nào partition bảng

Ôn 16 thẻ
Trong bài này

Cụm bài Tối ưu truy vấn: 1. SQL chạy thế nào và đọc execution plan · 2. Lab index PostgreSQL trên dataset hãng bay · 3. Thuật toán JOIN và partition

Bạn viết JOIN, database tự chọn cách ghép hai bảng: cùng câu bookings JOIN tickets, nested loop mất 3,7 giây còn hash join 0,7 giây. Đọc xong, bạn nhận ra ba thuật toán join trong plan, tránh bẫy khi viết join, và biết khi nào nên partition (chia bảng lớn thành nhiều mảnh) thay vì shard.

Nên đọc trước: cú pháp JOIN ở ERD, JOIN, GROUP BY, index ở Index, EXPLAIN, N+1 và phân trang, cách đọc plan ở bài 1. Các plan PostgreSQL 16 và MySQL 8.4 dưới đây là output thật mình chạy trên dataset của bài 2 (2,1 triệu bookings, 3,1 triệu tickets).

1. Nested loop join

Ý chính: với mỗi dòng của bảng ngoài (outer), tìm dòng khớp ở bảng trong (inner). Chi phí ≈ số dòng outer × chi phí một lần tìm ở inner, nên inner phải có index trên cột join.

for each row b in bookings where <điều kiện của b>:          -- outer
    for each row t in tickets where t.book_ref = b.book_ref:  -- inner: tra index nếu có
        emit (b, t)
  • Có index: mỗi lần tìm chỉ vài page. Không có: mỗi dòng outer là một lần quét cả inner.
  • Chạy được với mọi điều kiện join (<, BETWEEN, LIKE).
  • Trả dòng đầu gần như ngay, rất hợp với LIMIT.

Ép PostgreSQL dùng nested loop cho 132.789 booking có total_amount >= 500000:

Nested Loop  (actual time=1.378..428.104 rows=196171 loops=1)
  ->  Seq Scan on bookings b  (actual time=1.360..104.560 rows=132789 loops=1)
        Filter: (total_amount >= '500000'::numeric)
  ->  Index Only Scan using tickets_book_ref_idx on tickets t  (actual time=0.002..0.002 rows=1 loops=132789)
        Index Cond: (book_ref = b.book_ref)

Mỗi lookup chỉ 0,002 ms, nhưng nhân với loops=132789 thành khoảng 270 ms. Biến thể block nested loop của MySQL trước 8.0.20 nay đã được thay bằng hash join (mục 2).

2. Hash join

Ý chính: pha build đọc input nhỏ hơn vào hash table theo khoá join; pha probe đọc input lớn từng dòng và tra bảng. Chi phí ≈ O(n + m), không cần index, nhưng cần bộ nhớ.

flowchart LR
  subgraph Build["1. Build: input nhỏ hơn"]
    C["bookings đã lọc<br/>132.789 dòng"] --> H["Hash table<br/>key = book_ref"]
  end
  subgraph Probe["2. Probe: stream input lớn"]
    T["tickets<br/>3,1 triệu dòng"] --> L{"hash(book_ref)<br/>có trong bảng?"}
  end
  H -.-> L
  L -->|có| O["Trả dòng ghép"]
  L -->|không| X["Bỏ"]

Giới hạn: chỉ dùng cho điều kiện bằng (PostgreSQL), và phải build xong mới trả được dòng đầu.

Hash Join  (actual time=148.566..728.749 rows=196171 loops=1)
  Hash Cond: (t.book_ref = b.book_ref)
  ->  Seq Scan on tickets t  (actual time=0.084..267.757 rows=3100000 loops=1)
  ->  Hash  (actual time=147.911..147.912 rows=132789 loops=1)
        Buckets: 262144  Batches: 1  Memory Usage: 7106kB
        ->  Seq Scan on bookings b  (actual time=4.577..128.159 rows=132789 loops=1)
              Filter: (total_amount >= '500000'::numeric)

Node Hash là pha build: 7 MB, Batches: 1 nghĩa là vừa bộ nhớ. Hạ work_mem (bộ nhớ PostgreSQL cho mỗi bước sort/hash) xuống 1 MB thì thành Batches: 4 Memory Usage: 1772kB kèm temp written=327: đã tràn ra đĩa.

Tràn đĩa (Grace hash join), lọc sớm, block nested loop cũ và benchmark của MySQL

Block nested loop (BNL). Khi inner không có index, MySQL trước 8.0.20 gom các dòng outer vào join buffer (join_buffer_size) rồi quét inner một lần cho mỗi buffer đầy, so sánh trong bộ nhớ. Nếu t1 JOIN t2 ra 10 dòng, nested loop thường quét t3 10 lần; join buffer chứa đủ 10 dòng thì chỉ quét một lần.

Từ MySQL 8.0.20, BNL được thay hoàn toàn bằng hash join. Thấy Using join buffer (Block Nested Loop) nghĩa là MySQL bản cũ.

Tràn ra đĩa (Grace hash join). Khi input build không vừa bộ nhớ, cả hai input được chia thành N phần theo một hàm hash thứ hai trên khoá join, ghi ra file tạm, rồi join từng cặp phần i. Dòng chỉ khớp với dòng cùng phần nên kết quả vẫn đúng, đổi lại phải đọc ghi đĩa thêm một lượt. MySQL làm tương tự bằng “chunk file” khi vượt join_buffer_size (mặc định 256 KB). PostgreSQL 11+ có Parallel Hash: nhiều worker cùng build một hash table chung.

Lọc sớm. Với t1 JOIN t2 ON t1.a = t2.a WHERE t1.b > 3 AND t2.c < 4, EXPLAIN FORMAT=TREE của MySQL 8.4 cho thấy Filter: (t1.b > 3) nằm dưới node Hash và Filter: (t2.c < 4) nằm dưới phía probe: hash join lọc cả hai input trước khi ghép.

Benchmark. Benchmark kiểu TPC-H của đội MySQL khi ra mắt hash join (8.0.18) cho thấy có câu từ hơn 400 giây với BNL xuống khoảng 2,5 giây.

3. Merge join

Ý chính: sắp xếp hai input theo khoá join rồi đi song song bằng hai con trỏ. Nếu hai input đã có thứ tự sẵn từ index thì không cần sort, và PostgreSQL chọn nó khi ORDER BY trùng khoá join.

Hai con trỏ: bên nào khoá nhỏ hơn thì tiến bên đó, bằng nhau thì trả dòng ghép.

SELECT b.book_ref, t.ticket_no
FROM bookings b JOIN tickets t ON t.book_ref = b.book_ref
ORDER BY b.book_ref LIMIT 100000;
Limit  (actual time=0.014..61.773 rows=100000 loops=1)
  ->  Merge Join  (actual time=0.013..58.510 rows=100000 loops=1)
        Merge Cond: (b.book_ref = t.book_ref)
        ->  Index Only Scan using bookings_pkey on bookings b  (actual time=0.003..21.098 rows=67745 loops=1)
        ->  Index Scan using tickets_book_ref_idx on tickets t  (actual time=0.008..20.103 rows=100000 loops=1)

Không Sort, không hash table, dừng sau 100.000 dòng. Bỏ ORDER BY ... LIMIT (đếm toàn bộ) thì planner quay về hash join.

4. So sánh và mô phỏng bằng Java

Ý chính: không thuật toán nào luôn thắng. Join toàn bộ hai bảng lớn thì hash join nhanh hơn hẳn; lọc còn ít dòng thì gần như hoà.

Đo bằng \timing trên PostgreSQL (cache nóng, không song song):

Truy vấn Hash join Nested loop + index
6% booking (total_amount >= 500000), ~196.000 dòng kết quả 300–390 ms ~395 ms
Toàn bộ 2,1 triệu booking × 3,1 triệu vé 685 ms 3.750 ms
Mô phỏng trong bộ nhớ bằng Java 21

Mô phỏng 200.000 person, 2.000 country cho thấy độ phức tạp. Nested loop không index là hai vòng for lồng nhau, O(n × m); index nested loop thay vòng trong bằng TreeMap.get, O(n log m). Merge join là hai con trỏ đi trên hai danh sách đã sắp xếp như mục 3 (bản đầy đủ có xử lý khoá trùng ở cả hai phía). Hash join:

record Country(int id, String name) {}
record Person(int id, int countryId) {}
record Row(Person p, Country c) {}

// Hash join: build trên input nhỏ, probe bằng input lớn -> O(n + m)
static List<Row> hashJoin(List<Country> build, List<Person> probe) {
    var table = new HashMap<Integer, List<Country>>();
    for (var c : build) table.computeIfAbsent(c.id(), k -> new ArrayList<>()).add(c);
    var out = new ArrayList<Row>();
    for (var p : probe)
        for (var c : table.getOrDefault(p.countryId(), List.of())) out.add(new Row(p, c));
    return out;
}
nested loop          808.8 ms  160033 rows
index nested loop     10.3 ms  160033 rows
hash join              3.1 ms  160033 rows
merge join            21.9 ms  160033 rows

Trong database, chênh lệch ít hơn vì chi phí chính là đọc page (xem bảng \timing ở trên).

5. Viết JOIN cho đúng và nhanh

Ý chính: optimizer tự sắp thứ tự bảng, nên việc của bạn là index cột trong ON và đặt điều kiện đúng chỗ (ON hay WHERE) với LEFT JOIN.

ON và WHERE. Với INNER JOIN, hai chỗ cho cùng kết quả. Với LEFT JOIN thì khác hẳn:

-- customers: An, Binh, Chi. orders: An có 1 PAID + 1 CANCELLED, Binh có 1 CANCELLED.
SELECT c.name, o.id FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id AND o.status = 'PAID';
-- An | 10    Binh | NULL    Chi | NULL      → mọi khách, kèm đơn PAID nếu có

SELECT c.name, o.id FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id
WHERE o.status = 'PAID';
-- An | 10                                  → chỉ còn khách có đơn PAID

Dấu hiệu trong plan PostgreSQL: câu thứ hai ra Hash Join thường, không phải Hash Left Join, vì planner thấy WHERE loại mọi dòng NULL nên tự hạ xuống INNER JOIN.

Thứ tự join, hint và cách lọc theo bảng khác

Thứ tự join. PostgreSQL thử mọi thứ tự đến join_collapse_limit = 8 bảng; từ 12 bảng chuyển sang GEQO (thuật toán tìm kiếm gần đúng) và có thể chọn kém. Lời khuyên “bảng lớn join bảng nhỏ” khá mơ hồ: planner tự chọn phía build/outer theo số dòng sau khi lọc. Hint (MySQL /*+ JOIN_ORDER(...) */, PostgreSQL pg_hint_plan) chỉ là phương án cuối.

6. Case study: join decomposition

Ý chính: join decomposition là tách một câu JOIN thành nhiều câu một bảng rồi ghép ở ứng dụng. Đổi một round-trip và snapshot nhất quán lấy cache theo entity và khả năng tách service; chỉ đáng làm khi ranh giới service hoặc cache buộc phải vậy.

Case study tag/post: các câu tách và cái giá so với một câu JOIN

Bối cảnh. Trang “bài viết theo tag” chạy tag JOIN tag_post JOIN post WHERE tag.name = 'mysql'; post sắp có database riêng và được đọc rất nhiều. Phương án tách:

SELECT id FROM tag WHERE name = 'mysql';                    -- 1 dòng, cache được lâu
SELECT post_id FROM tag_post WHERE tag_id = 1234;           -- danh sách id
SELECT * FROM post WHERE id = ANY(:ids);                    -- MySQL: WHERE id IN (...)

7. Partition bảng

Ý chính: partitioning chia dữ liệu một bảng thành nhiều mảnh vật lý nhưng vẫn truy vấn như một bảng. Nó giúp đọc ít hơn và xoá dữ liệu cũ rẻ, nhưng chỉ khi truy vấn lọc theo partition key.

Vertical là tách cột (đưa description dài, ít đọc sang bảng phụ); horizontal là tách dòng theo một partition key, ví dụ bookings theo tháng của book_date. Bài này nói về kiểu thứ hai. Pruning là planner bỏ qua các partition không thể chứa dòng cần tìm.

Partitioning Sharding
Phạm vi Các mảnh trong một server Các mảnh trên nhiều server
Ứng dụng Không cần biết Phải biết (hoặc qua middleware như Vitess, Citus)
Mục đích chính Đọc ít hơn (pruning), xoá dữ liệu cũ rẻ, bảo trì từng mảnh Chia tải ghi và dung lượng vượt một máy
Khi server chết Mất tất cả partition Chỉ mất shard trên server đó

Thử nghiệm trên PostgreSQL với bookings_p partition theo tháng (15 partition):

CREATE TABLE bookings_p (
  book_ref     char(6) NOT NULL,
  book_date    timestamptz NOT NULL,
  total_amount numeric(10,2) NOT NULL,
  PRIMARY KEY (book_ref, book_date)            -- bắt buộc chứa partition key
) PARTITION BY RANGE (book_date);
CREATE TABLE bookings_p_201703 PARTITION OF bookings_p FOR VALUES FROM ('2017-03-01') TO ('2017-04-01');
-- ... một partition mỗi tháng (vòng lặp DO hoặc extension pg_partman), cộng một DEFAULT partition
CREATE INDEX ON bookings_p (book_date);        -- tự tạo trên mọi partition
Thử nghiệm Bảng thường bookings bookings_p
count(*) một tháng Seq Scan cả bảng, 13.376 page, 188 ms Chỉ quét bookings_p_201703, 1.064 page, 11,6 ms
WHERE book_ref = '00A1B2' (không có partition key) 1 Index Scan 15 Index Scan, mỗi partition một
Bỏ dữ liệu tháng 7/2016 (64.981 dòng) DELETE 316 ms, sinh WAL và dead tuple DETACH PARTITION 2 ms

Chọn partition key theo phân bố (partition xấp xỉ đều, không có partition “nóng”) và cách truy cập (truy vấn chính có lọc theo key không):

  • RANGE theo thời gian cho dữ liệu có vòng đời. Cùng ý tưởng ở NoSQL: partition key ghép (channel_id, bucket) với bucket là một cửa sổ thời gian, để partition của kênh bận không phình mãi, xem Thiết kế hệ thống chat kiểu Discord.
  • LIST theo tenant khi truy vấn luôn trong một tenant.
  • HASH để chia đều khi không có range tự nhiên.
Giới hạn của MySQL partitioning, và Redis Cluster như một ví dụ sharding

MySQL partitioning có RANGE, LIST, HASH, KEY và RANGE/LIST COLUMNS. Giới hạn:

  • Tối đa 8.192 partition mỗi bảng từ 5.6.7 (con số 1.024 hay được nhắc là của bản cũ).
  • PK/unique phải chứa mọi cột của biểu thức partition: PRIMARY KEY (id) với PARTITION BY RANGE (YEAR(created_at)) gặp lỗi 1503.
  • Không có foreign key và FULLTEXT.

Vì vậy nhiều đội chỉ dùng nó cho bảng log/event theo thời gian để drop dữ liệu cũ.

Redis Cluster là ví dụ sharding thu nhỏ dễ quan sát: key băm vào 16.384 hash slot chia cho các master, client được chuyển hướng bằng MOVED/ASK, và lệnh nhiều key chỉ chạy khi các key cùng slot (hash tag); xem Redis: persistence, replication, Sentinel và Cluster.

Chọn shard key, bốn case study và resharding không downtime ở Sharding: chọn shard key và resharding; khi nào đổi hẳn sang NoSQL, NewSQL hay columnar ở Chọn database: SQL, NoSQL, NewSQL.

8. Case study: một bảng quá lớn thì làm gì

Ý chính: đo trước, rồi leo từng bậc, chỉ lên bậc tiếp khi bậc hiện tại không đủ. Mỗi bậc đắt và khó quay lại hơn bậc trước.

Bậc Giải quyết Cái giá
1. Viết lại query Không sargable (điều kiện không dùng được index), SELECT *, OFFSET sâu, N+1 Gần như không có
2. Index Thiếu index, sai thứ tự cột, thiếu covering Chậm ghi, tốn dung lượng
3. Archive 90% dữ liệu không ai đọc nhưng làm index to, cache kém Job archive, quy định truy cập dữ liệu cũ
4. Cache Đọc lặp cùng dữ liệu Invalidation, dữ liệu cũ
5. Read replica Tải đọc vượt một node Replication lag, đọc-sau-ghi
6. Partition / shard Vòng đời dữ liệu, pruning / tải ghi vượt một node Ràng buộc unique, truy vấn thiếu key; shard mất join/transaction
7. Database khác Phân tích trên toàn bộ lịch sử Thêm hệ thống, đồng bộ dữ liệu (CDC — đọc thay đổi từ log của DB để đẩy sang hệ khác)

Ví dụ (kịch bản minh hoạ): bookings 800 triệu dòng, 600 GB, p95 API “lịch sử đặt chỗ” từ 50 ms lên 900 ms, báo cáo đêm chạy quá giờ, có người đề xuất shard. Thủ phạm là OFFSET sâu và thiếu index (passenger_id, book_date): bậc 1–2 đưa p95 về 60 ms. 85% dữ liệu cũ hơn 18 tháng chỉ báo cáo đọc: partition theo tháng để detach, báo cáo sang database phân tích. Không cần shard.

Bài tập

Bài 1: Chiến lược archive dữ liệu cũ hiệu quả

Đề (bài về nhà của khoá, diễn đạt lại): thiết kế chiến lược archive dữ liệu cũ của bảng bookings, giữ 18 tháng gần nhất trong bảng chính.

Lời giải Bài 1: partition + detach, xoá theo lô, bảng tổng hợp

Hỏi trước: dữ liệu cũ còn cần truy vấn không, giữ bao lâu theo luật, có phải xoá dữ liệu cá nhân theo yêu cầu không. Ba hướng:

  1. Partition theo tháng + detach/drop: mỗi tháng ALTER TABLE bookings DETACH PARTITION bookings_2024_05 CONCURRENTLY (PostgreSQL 14+, không chặn truy vấn), export bảng đã tách ra Parquet trên object storage, rồi DROP TABLE. Gần như không tốn I/O trên bảng chính; cần partition từ đầu hoặc một migration lớn.
  2. Xoá theo lô khi không partition được: DELETE ... WHERE id IN (SELECT id ... WHERE book_date < ? ORDER BY id LIMIT 5000), commit mỗi lô, nghỉ giữa các lô, theo dõi replication lag, chép sang bảng archive trước khi xoá (MySQL có pt-archiver). Chậm, sinh nhiều WAL/binlog, cần VACUUM sau đó.
  3. Bảng tổng hợp theo ngày/tháng cho báo cáo, chi tiết đi archive.

Xoá theo lô an toàn được bàn kỹ ở Xoá dữ liệu cũ an toàn.

Ghi nhớ

  • Giải thích được vì sao nested loop cần index còn hash join cần bộ nhớ, và đọc được Batches: 4.
  • Biết khi nào PostgreSQL chọn merge join, và vì sao không mang nhận xét đó sang MySQL.
  • Viết đúng LEFT JOIN có điều kiện lọc trên bảng bên phải.
  • Kể được hai cái giá của partition và nó khác shard ở đâu.
  • Trả lời “bảng quá lớn thì làm gì” bằng các bậc, bắt đầu từ việc hỏi số liệu.

Câu hỏi phỏng vấn

Junior

Database có những thuật toán join nào?

Ba thuật toán: nested loop, hash join và merge join.

Nested loop: với mỗi dòng ngoài, tìm dòng khớp ở bảng trong, tốt khi có index trên cột join. Hash join: build hash table từ input nhỏ rồi probe bằng input lớn, tốt cho join lớn với điều kiện bằng. Merge join: sắp xếp hai input rồi đi song song; có ở PostgreSQL, không có ở MySQL.

Đặt điều kiện ở ON hay WHERE có khác nhau không?

Với INNER JOIN thì không; với LEFT JOIN thì có.

Điều kiện trên bảng bên phải đặt ở WHERE loại các dòng NULL và biến nó thành INNER JOIN. Muốn giữ mọi dòng bảng trái thì đặt điều kiện trong ON.

Mid

Khi nào hash join tốt hơn nested loop?

Khi join phần lớn hai bảng lớn với điều kiện bằng, nhất là khi không có index phù hợp trên cột join.

Nested loop tốt hơn khi outer ít dòng và inner có index, hoặc khi cần dòng đầu nhanh với LIMIT. Trong lab: join toàn bộ 2,1 triệu × 3,1 triệu dòng thì hash join 0,7 giây, nested loop 3,7 giây.

Trong plan PostgreSQL, Batches: 4 ở node Hash nghĩa là gì?

Input build không vừa work_mem, nên hash join đã tràn ra đĩa thành 4 phần.

Hai input được chia thành 4 phần theo hash của khoá, các phần chưa xử lý ghi ra file tạm rồi join từng cặp; thấy kèm temp read/written. Xử lý: tăng work_mem cho session đó, giảm số dòng/cột của input build, hoặc chấp nhận nếu không phải truy vấn nóng.

Senior

Bạn partition bảng orders theo created_at. Những gì có thể hỏng?

Unique toàn bảng, foreign key, truy vấn không có created_at, việc tạo partition mới và planning time.

  • PK/unique phải chứa created_at, nên order_id không còn được đảm bảo unique toàn bảng; foreign key trỏ vào bảng phải đổi.
  • Truy vấn theo order_id hay customer_id không có created_at sẽ quét mọi partition.
  • Cần job tạo trước partition cho tháng mới (hoặc default partition) kẻo insert lỗi.
  • Nhiều partition làm tăng planning time.

Đổi lại được pruning theo thời gian và xoá dữ liệu cũ bằng detach.

Bảng chính đạt vài trăm triệu dòng và bắt đầu chậm. Bạn tiếp cận thế nào?

Đo trước, rồi leo từng bậc từ rẻ đến đắt, chỉ lên bậc tiếp khi có số liệu chứng minh bậc trước không đủ.

Đo: kích thước, top query theo tổng thời gian, tỉ lệ đọc/ghi, dữ liệu nóng chiếm bao nhiêu. Các bậc: viết lại query, index, archive, cache, read replica, partition/shard, database khác. Mỗi bậc đắt và khó quay lại hơn bậc trước.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
nested loop join /ˈnestɪd luːp dʒɔɪn/ join bằng vòng lặp lồng “A nested loop is fine here because the outer side has only a few rows.”
hash join /hæʃ dʒɔɪn/ join bằng bảng băm “For a large report the planner switched to a hash join.”
build side /bɪld saɪd/ phía dựng bảng băm “The smaller input should be the build side.”
merge join /mɜːdʒ dʒɔɪn/ join bằng trộn hai dãy đã sắp xếp “Both inputs come sorted from indexes, so a merge join needs no sort.”
partition pruning /pɑːˈtɪʃn ˈpruːnɪŋ/ bỏ qua partition không liên quan “Partition pruning only works if the query filters on the partition key.”
partition key /pɑːˈtɪʃn kiː/ cột dùng để chia partition “Every unique constraint has to include the partition key.”
sharding /ˈʃɑːdɪŋ/ chia dữ liệu qua nhiều server “Sharding spreads write load, but cross-shard joins get expensive.”
join decomposition /dʒɔɪn ˌdiːkɒmpəˈzɪʃn/ tách join thành nhiều câu “Join decomposition makes per-entity caching more effective.”

Ghi chép dựa trên khoá Advanced Backend (Ronin Engineer), viết lại theo cách hiểu của mình.