Thuật toán nối cơ sở dữ liệu (Nested Loop · Sort-Merge · Hash Join)

1. Tổng quan

A. Định nghĩa

Thuật toán nối (Join Algorithm) chỉ phương thức xử lý kết hợp vật lý hai hoặc nhiều quan hệ (bảng) theo điều kiện nối để tạo ra tập kết quả trong cơ sở dữ liệu quan hệ. Khi người dùng chỉ khai báo trong SQL 'kết hợp cái gì' như FROM A, B WHERE A.k = B.k, thì dùng thủ tục vật lý nào để tìm cặp của hai tập hợp là do bộ tối ưu hóa quyết định bằng cách chọn một thuật toán nối.

Chìa khóa để hiểu thuật toán nối nằm ở chỗ 'có nhiều cách tạo ra cùng một kết quả nối, và tùy theo quy mô dữ liệu·phân bố·trạng thái sắp xếp·có hay không chỉ mục mà một cách có thể nhanh hơn hàng chục đến hàng nghìn lần'. Trong mô hình quan hệ, nối là phép toán đắt đỏ nhất nhưng cũng thường xuyên nhất. Kết hợp hai bảng về bản chất là bài toán tìm kiếm (matching) tìm, với mỗi hàng của một tập hợp, hàng tương ứng trong tập hợp kia, và cách tổ chức việc tìm kiếm này chính là điểm khác biệt của thuật toán. Nếu so sánh mọi cặp hàng mà không có chiến lược nào thì chi phí tỉ lệ với tích của hai bảng (tích Descartes), nhưng nếu dùng sắp xếp hoặc bảng băm thì có thể hạ chi phí đó xuống gần tuyến tính.

Việc tại sao nối về bản chất là phép toán đắt đỏ cũng rõ ràng theo lý thuyết tập hợp. Nối hai quan hệ về mặt khái niệm tương đương với tạo tích Descartes (mọi tổ hợp hàng) rồi chỉ giữ lại các hàng thỏa điều kiện nối. Nếu A có 1 triệu hàng, B có 1 triệu hàng thì tích Descartes trở thành 1 nghìn tỷ (10^12) tổ hợp, nên dù điều kiện lọc hiệu quả đến đâu, cách ngây thơ 'thực sự tạo tích rồi lọc' vẫn bất khả thi trên thực tế. Cả ba thuật toán nối đều là phương pháp 'tìm trực tiếp chỉ các cặp thỏa điều kiện mà không thực sự tạo tích', và phương tiện của chúng lần lượt là tìm kiếm chỉ mục·thứ tự sắp xếp·định địa chỉ trực tiếp bằng băm. Học thuật toán nối rốt cuộc là hiểu 'ba thủ thuật kỹ thuật thu nhỏ không gian tìm kiếm theo cấp số mũ xuống gần tuyến tính'.

Lý do DBMS quan hệ tự động chọn thuật toán nối là vì SQL là ngôn ngữ khai báo. Người dùng chỉ viết 'ý nghĩa' của việc kết hợp chứ không chỉ định 'thủ tục' của nó, nên mỗi khi lượng và phân bố dữ liệu thay đổi thì thủ tục tối ưu cũng thay đổi. Các thuật toán nối mà DBMS thương mại·mã nguồn mở triển khai chung chia thành ba loại lớn — nối vòng lặp lồng (Nested Loop Join), nối sắp xếp trộn (Sort-Merge Join), nối băm (Hash Join) — và bộ tối ưu hóa dựa trên chi phí (CBO) chọn phương thức rẻ nhất trong số này cho mỗi truy vấn dựa trên thông tin thống kê.

B. Sự cần thiết và vị trí

Việc chọn thuật toán nối là biến quyết định chi phối hiệu năng truy vấn. Ví dụ, trong truy vấn kết hợp bảng đơn hàng (10 triệu hàng) và bảng khách hàng (1 triệu hàng), khi điều kiện chỉ lọc ra một số rất nhỏ thì Nested Loop đi qua chỉ mục kết thúc trong mili giây; nhưng trong truy vấn kiểu batch phải kết hợp phần lớn hai bảng, dùng cùng Nested Loop sẽ phát sinh hàng trăm triệu lần I/O ngẫu nhiên và mất hàng chục phút. Ngược lại, dùng Hash Join cho truy vấn batch này chỉ quét mỗi bảng một lần và kết thúc trong vài giây. Nghĩa là chỉ một lựa chọn thuật toán cũng thay đổi phi tuyến tính khả năng đáp ứng dịch vụ và mức tiêu thụ tài nguyên.

Thuật toán nối là thành phần cốt lõi của kế hoạch thực thi (execution plan) mà bộ tối ưu hóa lập trong đường ống xử lý SQL (phân tích cú pháp → tối ưu hóa → thực thi). Bộ tối ưu hóa kết hợp ba trục — ① đường truy cập (chỉ mục vs quét toàn bộ), ② thứ tự nối (đọc bảng nào trước), ③ phương thức nối (thuật toán) — để tạo các kế hoạch ứng viên và so sánh chi phí. Do đó, hiểu nguyên lý hoạt động·cấu trúc chi phí·điều kiện tiên quyết của từng thuật toán là năng lực cốt lõi làm nền tảng cho tinh chỉnh DB, thiết kế gợi ý, diễn giải kế hoạch thực thi và ước lượng dung lượng.

2. Cấu trúc tổng thể của thuật toán nối

Ba thuật toán giải mục tiêu chung 'làm sao tìm cặp' bằng những chiến lược khác nhau. Sơ đồ cấu trúc tổng thể dưới đây cho thấy yêu cầu nối phân nhánh thành ba thuật toán vật lý qua bộ tối ưu hóa như thế nào.

flowchart TB
  SQL["Truy vấn nối(FROM A JOIN B ON ...)"] --> OPT["Bộ tối ưu hóa(CBO)"]
  STAT["Thống kê(cardinality·phân bố·chỉ mục)"] --> OPT
  OPT --> NL["Nested Loop Join(vòng lặp lồng)"]
  OPT --> SM["Sort-Merge Join(sắp xếp trộn)"]
  OPT --> HJ["Hash Join(băm)"]
  NL --> NLU["Có lợi khi tập nhỏ·có chỉ mục"]
  SM --> SMU["Có lợi khi đã sắp xếp·nối bất đẳng thức"]
  HJ --> HJU["Có lợi khi nối bằng lớn·chưa sắp xếp"]
  style OPT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style STAT fill:#fef3e8,stroke:#ed8f2f,stroke-width:2px

Điều nhất định phải phân biệt ở đây là thứ tự nối (join order) và phương thức nối (join method). Thứ tự nối là vấn đề 'đọc bảng nào trước để giảm kết quả (driving table)', còn phương thức nối là vấn đề 'kết hợp hai tập đã chọn bằng thuật toán nào'. Nếu có từ ba bảng trở lên, bộ tối ưu hóa thực hiện nối từng hai cái theo giai đoạn (cây left-deep hoặc bushy), quyết định thứ tự và phương thức cùng nhau ở mỗi giai đoạn. Vì kích thước tập kết quả trung gian chi phối chi phí của giai đoạn tiếp theo, nên tìm 'thứ tự lọc nhỏ trước' quan trọng ngang với việc chọn phương thức. Số bảng nối càng tăng thì tổ hợp thứ tự khả dĩ càng bùng nổ theo giai thừa, nên bộ tối ưu hóa giới hạn không gian tìm kiếm bằng quy hoạch động·heuristic.

Khác biệt bản chất của ba thuật toán nằm ở 'giảm chi phí tìm cặp ở đâu'. Nested Loop tìm kiếm bảng kia từng hàng một nhưng tăng tốc tìm kiếm bằng chỉ mục — tức dựa vào 'tính cục bộ của tìm kiếm'. Sort-Merge sắp xếp trước cả hai phía và tìm cặp bằng một lần duyệt đồng thời (trộn) — tức dựa vào 'thứ tự mà sắp xếp tạo ra'. Hash Join tạo bảng băm từ một phía và tìm cặp bằng tra cứu thời gian hằng — tức dựa vào 'định địa chỉ trực tiếp mà băm tạo ra'. Vì ba chiến lược này có điều kiện tiên quyết (chỉ mục·sắp xếp·bộ nhớ) khác nhau, nên ưu thế đảo ngược tùy tình huống dữ liệu. Lý do bộ tối ưu hóa không cố định một cái mà chọn lại theo từng truy vấn nằm ở đây.

3. Nested Loop Join (nối vòng lặp lồng)

Nested Loop Join là phương thức trực quan nhất, tìm cặp thỏa điều kiện nối bằng cách tìm kiếm lặp bảng trong (inner) cho mỗi hàng của bảng ngoài (outer, driving). Đúng như tên gọi, nó có cấu trúc vòng lặp kép, trong đó vòng ngoài lấy tập dẫn đầu từng hàng một và vòng trong dò tập đi sau bằng khóa nối của hàng đó.

Trong cấu trúc này bảng ngoài được gọi là 'bảng dẫn đầu (driving)', và vì kích thước tập dẫn đầu quyết định tổng số lần lặp nên thứ tự nối 'đặt tập nhỏ ở ngoài' chi phối nửa hiệu năng. Bộ tối ưu hóa nhìn thống kê và chọn phía tạo ít kết quả hơn làm phía dẫn đầu, nhưng nếu thống kê bị méo, nó có thể chọn nhầm tập lớn làm dẫn đầu, gây sự cố nổ số lần lặp.

Cốt lõi là 'bảng trong có chỉ mục trên khóa nối hay không'. Nếu có chỉ mục, tìm kiếm bên trong đổi từ quét toàn bộ thành tìm kiếm chỉ mục (truy cập ngẫu nhiên), tìm được cặp chỉ với vài lần đọc khối cho mỗi hàng ngoài. Trong trường hợp này tổng chi phí tỉ lệ xấp xỉ với 'số hàng ngoài × (tìm kiếm chỉ mục + truy cập ngẫu nhiên bảng)'. Do đó nó có lợi áp đảo khi tập ngoài nhỏ và bên trong có chỉ mục thích hợp. Chẳng hạn truy vấn gắn lịch sử đơn hàng của từng người (bên trong, có chỉ mục mã khách hàng) cho '50 khách hàng đăng ký hôm nay' (bên ngoài) kết thúc chỉ với 50 lần tìm kiếm chỉ mục.

Ngược lại, tập ngoài lớn thì chí mạng. Nếu bên ngoài là 1 triệu hàng thì tìm kiếm chỉ mục bên trong lặp 1 triệu lần, và I/O ngẫu nhiên này kéo theo di chuyển đầu đọc đĩa (hoặc truy cập ngẫu nhiên trên SSD) nên chậm hơn I/O tuần tự rất nhiều. Ngoài ra nếu bên trong không có chỉ mục thì mỗi hàng ngoài quét toàn bộ bên trong, nên chi phí bùng nổ tỉ lệ với tích số hàng của hai bảng (tích Descartes). Để giảm nhẹ điều này, DBMS hiện đại dùng các biến thể như block Nested Loop (gom nhiều hàng ngoài và xử lý theo đơn vị bộ đệm), cache khối bên trong, truy cập sau khi sắp xếp khóa ngoài (prefetch).

Nested Loop còn có lợi thế thực tiễn là có lợi cho xử lý phạm vi một phần (partial range). Vì nó tạo kết quả từng hàng một từ đầu, nên trong truy vấn OLTP chỉ cần vài kết quả hàng đầu như ROWNUM <= 10 hoặc LIMIT 10, nó có thể lấy vừa đủ cần và dừng mà không xử lý toàn bộ. Vì thế nó được dùng mặc định cho giao dịch OLTP·phân trang màn hình·tra cứu kết quả nhỏ.

Một biến số khác quyết định hiệu năng Nested Loop là hệ số phân cụm (clustering factor), tức độ khớp giữa thứ tự chỉ mục và thứ tự lưu trữ thực tế của bảng. Nếu các hàng tìm được qua chỉ mục bên trong rải rác khắp các khối bảng (hệ số phân cụm xấu), mỗi hàng ngoài phải truy cập ngẫu nhiên một khối khác nhau, nên dù có chỉ mục thì hiệu năng cảm nhận vẫn giảm. Ngược lại, nếu thứ tự khóa nối khớp với thứ tự lưu trữ thì xác suất thăm lại cùng khối tăng, tỉ lệ trúng cache bộ đệm tăng và I/O ngẫu nhiên giảm. Vì thế tinh chỉnh Nested Loop phải nhìn vượt qua 'đã tạo chỉ mục chưa' đến 'các hàng mà chỉ mục trỏ tới có gom cụm vật lý không'. Ở điểm này, việc chọn thuật toán nối cũng tiếp giáp với thiết kế bảng·thứ tự nạp.

flowchart LR
  O["Bảng Outer(nhỏ·dẫn đầu)"] --> R1["Hàng 1 → tìm Inner bằng khóa nối"]
  O --> R2["Hàng 2 → tìm Inner bằng khóa nối"]
  O --> R3["Hàng N → tìm Inner bằng khóa nối"]
  R1 --> IDX["Chỉ mục khóa nối Inner"]
  R2 --> IDX
  R3 --> IDX
  IDX --> RES["Trả về hàng khớp(matched row)"]
  style IDX fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px

4. Sort-Merge Join (nối sắp xếp trộn)

Sort-Merge Join là phương thức sắp xếp mỗi bảng theo khóa nối, rồi duyệt đồng thời hai luồng đã sắp xếp (merge) để khớp cặp. Hãy hình dung đặt hai cuốn danh bạ cạnh nhau rồi đi xuống tìm cùng một tên. Nếu hai tập được sắp xếp theo cùng thứ tự, có thể tìm cặp bằng cách đọc tuần tự mỗi tập đúng một lần trong khi tiến con trỏ.

Căn cứ để Sort-Merge thành lập là tính chất 'để tìm phần tử chung trong hai dãy đã sắp xếp thì chỉ cần duyệt mỗi phía một lần là đủ'. Vì cả hai được sắp xếp theo cùng thứ tự khóa, nếu khóa một phía nhỏ hơn phía kia thì chỉ cần tiến phía nhỏ, không cần quay lại. Tuy nhiên khi khóa nối có trùng lặp (một-nhiều·nhiều-nhiều) thì phải tua lại (rewind) một con trỏ trong đoạn khớp để xuất mọi tổ hợp, nên nếu độ trùng cao thì giai đoạn trộn cũng phát sinh lùi nhẹ.

Thuật toán này chia lớn thành giai đoạn sắp xếp (Sort) và giai đoạn trộn (Merge). Ở giai đoạn sắp xếp, hai tập được sắp xếp theo thứ tự khóa nối, và chi phí này khoảng N log N chi phối tổng chi phí. Giai đoạn trộn là duyệt tuyến tính (O(N + M)) so sánh hai con trỏ, tiến phía nhỏ hơn và xuất ra kết quả khi khóa bằng nhau. Do đó giảm chi phí sắp xếp bao nhiêu là mấu chốt, và nếu đã ở trạng thái sắp xếp (khi thứ tự sắp xếp được bảo đảm bằng quét toàn bộ chỉ mục, hoặc khi đầu ra của phép toán trước đã được sắp xếp) thì có thể bỏ qua giai đoạn sắp xếp, trở nên rất hiệu quả.

Thế mạnh quyết định của Sort-Merge Join là có thể xử lý nối bất đẳng thức (không bằng). Vì Hash Join chỉ phân định sự trùng khớp của giá trị băm nên chỉ hoạt động với điều kiện = (bằng); còn Sort-Merge dùng thứ tự đã sắp xếp nên có thể áp dụng cho cả các điều kiện như >=, BETWEEN, chồng lấn phạm vi. Ví dụ, nối phạm vi 'ánh xạ chính sách giảm giá mà giá sản phẩm thuộc một khoảng nhất định' là lĩnh vực điển hình của Sort-Merge. Ngoài ra, kết quả sắp xếp có thể tái sử dụng trực tiếp cho ORDER BY hoặc GROUP BY, cho lợi ích thêm khi phép toán tiếp theo yêu cầu sắp xếp.

Giới hạn là chi phí sắp xếp. Nếu cả hai tập đều lớn và chưa sắp xếp thì hai lần sắp xếp quy mô lớn (sắp xếp ngoài dùng đĩa khi cần) đi trước, có thể chậm hơn Hash Join. Trước đây, cho đến khi Hash Join được chuẩn hóa, nó là mặc định cho nối lớn, nhưng ngày nay vị trí xử lý nối bằng lớn phần lớn đã thuộc về Hash Join, và Sort-Merge được chọn trong điều kiện 'đã sắp xếp' hoặc 'nối bất đẳng thức'.

Nếu bộ nhớ không đủ ở giai đoạn sắp xếp thì nó chuyển sang sắp xếp ngoài (external sort), ghi kết quả trung gian ra đĩa tạm thành nhiều run và trộn lại. Khi việc ghi·đọc đĩa này được thêm vào thì chi phí sắp xếp càng lớn, nên ngay cả khi dùng Sort-Merge thì kích thước vùng làm việc sắp xếp (ví dụ SORT_AREA/PGA của Oracle) chi phối hiệu năng. Ngược lại, nếu khóa nối đã có chỉ mục B+Tree sao cho thứ tự sắp xếp được bảo đảm chỉ bằng quét toàn bộ chỉ mục, thì có thể bỏ qua hoàn toàn giai đoạn sắp xếp và kết thúc chỉ bằng duyệt trộn. Như vậy 'có thể có sắp xếp miễn phí hay không' trở thành tiêu chí phán đoán thực chất cho việc áp dụng Sort-Merge.

Phân loại	Nested Loop	Sort-Merge	Hash Join
Chiến lược cơ bản	Tìm Inner theo mỗi hàng ngoài	Sắp xếp cả hai rồi duyệt trộn	Xây bảng băm + dò (probe)
Tình huống có lợi	Tập nhỏ·có chỉ mục	Đã sắp xếp·nối bất đẳng thức	Nối bằng lớn·chưa sắp xếp
Điều kiện nối	Cả bằng·bất đẳng thức	Cả bằng·bất đẳng thức	Chỉ bằng (`=`)
Phụ thuộc chỉ mục	Cao (chỉ mục Inner gần như bắt buộc)	Thấp (sắp xếp thay thế)	Không (băm thay thế)
Độ nhạy bộ nhớ	Thấp	Trung bình (vùng sắp xếp)	Cao (vùng băm)
Xử lý phạm vi một phần	Xuất sắc (trả về sớm)	Bất lợi (cần hoàn tất sắp xếp)	Bất lợi (cần hoàn tất build)
Chi phí tiêu biểu	Số hàng ngoài × tìm Inner	N log N + M log M	N + M (khi đủ bộ nhớ)

5. Hash Join (nối băm)

Hash Join là phương thức xây bảng băm của khóa nối trong bộ nhớ từ bảng nhỏ hơn (build input), rồi đọc bảng lớn hơn (probe input) từng hàng một và tra cứu cùng gàu băm để tìm cặp. Cốt lõi là tra cứu bảng băm có thời gian hằng trung bình (O(1)), nhờ đó có thể tìm ngay cặp của mỗi hàng trong khi quét tuần tự bảng lớn đúng một lần. Nếu đủ bộ nhớ, tổng chi phí hội tụ xấp xỉ về O(N + M), đọc hai bảng mỗi bảng một lần.

Làm ví dụ ngành thực tế, có thể nêu batch tổng hợp doanh thu hằng ngày của một sàn thương mại điện tử lớn. Trong truy vấn star-schema điển hình tổng hợp hàng chục triệu bản ghi nhật ký đơn hàng mỗi ngày (fact) kết hợp với các bảng chiều sản phẩm·thành viên·vùng (dimension), vì bảng chiều nhỏ còn fact khổng lồ, nên Hash Join xây bảng băm từ mỗi chiều và quét fact một lần sẽ kết thúc xử lý trong vài chục giây. Làm cùng công việc bằng Nested Loop có thể mất hàng giờ vì lặp tìm kiếm chỉ mục chiều cho hàng chục triệu bản ghi. Đó là lý do nói rằng tổng hợp kho dữ liệu·BI đứng trên Hash Join cũng không ngoa.

Hoạt động chia thành hai giai đoạn Build và Probe. Ở giai đoạn build, bộ tối ưu hóa nhìn thống kê, chọn tập nhỏ hơn, áp dụng hàm băm lên khóa nối của nó và xây bảng băm nạp theo từng gàu. Ở giai đoạn probe, nó áp dụng cùng hàm băm lên mỗi hàng của tập lớn để tìm gàu tương ứng, xác nhận khớp khóa thực tế trong gàu và xuất kết quả. Tập build càng nhỏ thì bảng băm càng vừa trọn trong bộ nhớ và càng nhanh nhất, vì thế lựa chọn 'lấy bảng nhỏ làm build' chi phối hiệu năng.

Thế mạnh quyết định của Hash Join là nhanh ngay cả khi không có chỉ mục trong nối bằng dữ liệu lớn. Khác với Nested Loop lặp I/O ngẫu nhiên bằng số hàng ngoài, Hash Join chỉ quét tuần tự (sequential I/O) cả hai phía nên có lợi áp đảo trong batch dung lượng lớn·tổng hợp DW·ETL. Chẳng hạn truy vấn phân tích kết hợp 100 triệu doanh thu và 100 nghìn sản phẩm theo mã sản phẩm xây bảng băm từ 100 nghìn sản phẩm và quét 100 triệu doanh thu một lần là xong — hoàn toàn không cần chỉ mục.

Điểm yếu là ràng buộc chỉ dành cho bộ nhớ và nối bằng. Nếu tập build lớn hơn bộ nhớ khả dụng (vùng băm) thì bảng băm không vừa hết trong bộ nhớ, nên chuyển sang Grace Hash Join / băm lai, chia dữ liệu thành nhiều phân vùng, ghi ra đĩa rồi đọc lại. Vì lúc này I/O đĩa tăng và hiệu năng giảm, nên việc thiết lập kích thước vùng băm (ví dụ PGA của Oracle, work_mem của PostgreSQL) rất quan trọng. Ngoài ra vì băm chỉ phân định sự trùng giá trị nên chỉ dùng được với điều kiện = và không áp dụng được cho nối bất đẳng thức như >·BETWEEN, trường hợp đó chuyển sang Sort-Merge hoặc Nested Loop. Cũng cần lưu ý điểm là nếu lệch dữ liệu (skew) nghiêm trọng và giá trị dồn vào một gàu cụ thể thì va chạm băm tăng và hiệu năng suy giảm.

Giải thích thêm một chút về hoạt động của Grace Hash Join: nó chia cả hai phía build·probe thành N phân vùng bằng cùng hàm băm, lưu ra đĩa, rồi chỉ đọc lại và nối các cặp phân vùng cùng số. Vì các hàng có thể thành cặp chắc chắn vào cùng phân vùng băm, nên ngay cả dung lượng lớn không thể nạp hết vào bộ nhớ một lúc cũng xử lý được bằng cách lặp 'nối trong bộ nhớ cắt theo đơn vị phân vùng'. Băm lai còn giữ phân vùng đầu tiên trong bộ nhớ mà không ghi ra đĩa, một sự dung hòa giảm số vòng đi-về đĩa trong phạm vi có thể. Nhờ các cơ chế như vậy, Hash Join có khả năng mở rộng ổn định 'rất nhanh khi đủ bộ nhớ, và chậm dần một cách thoai thoải ngay cả khi thiếu' — đây là lý do các DW dung lượng lớn chọn Hash Join làm vũ khí mặc định cho nối.

6. So sánh và tiêu chí lựa chọn: lý do sinh ra khác biệt

Nguyên nhân căn bản khiến ưu thế của ba thuật toán đảo ngược tùy tình huống là 'chi phí chủ đạo của việc tìm cặp là gì' thay đổi theo quy mô dữ liệu·sắp xếp·chỉ mục·bộ nhớ. Trong truy vấn OLTP lấy kết quả nhỏ, 'chạm ít đến đâu' là quan trọng, nên Nested Loop chỉ xử lý tập ngoài nhỏ và trả về sớm thắng. Ngược lại, trong truy vấn OLAP·batch kết hợp toàn bộ ở dung lượng lớn, 'đọc toàn bộ mấy lần' là quan trọng, nên Hash Join quét tuần tự hai bảng mỗi bảng chỉ một lần thắng. Sort-Merge lấp chỗ trống ở giữa của 'đã sắp xếp nên không có chi phí sắp xếp, hoặc bất đẳng thức nên không dùng được băm'.

Nhìn từ quan điểm này, câu hỏi 'thuật toán nào tốt hơn' tự nó không thành lập. Ba thuật toán không ở quan hệ hơn kém mà ở quan hệ bổ trợ có lĩnh vực áp dụng khác nhau, và mỗi cái chỉ tốt nhất trong khoảng mà điều kiện tiên quyết của nó (chỉ mục·sắp xếp·bộ nhớ) được thỏa. Việc bộ tối ưu hóa không chọn vĩnh viễn một cái mà chọn lại theo từng truy vấn·từng thay đổi thống kê, và việc thực thi thích ứng còn chuyển đổi ngay khi chạy, chính là vì tính bổ trợ này. Vai trò của kỹ sư không phải 'chọn thuật toán tốt nhất' mà là 'sắp đặt dữ liệu và thống kê sao cho mỗi truy vấn được đặt vào đúng khoảng thuật toán'.

Hàm ý thực tiễn thì rõ ràng. Thứ nhất, chiến lược chỉ mục và thuật toán nối là một thể. Nếu định dùng Nested Loop thì chỉ mục khóa nối bên trong là bắt buộc; nếu định dùng Hash Join thì hiệu quả quét tuần tự (phân vùng·nén) quan trọng hơn chỉ mục. Thứ hai, độ tươi của thống kê làm thay đổi lựa chọn thuật toán. Nếu thống kê cũ và tập lớn bị phán nhầm là nhỏ thì bộ tối ưu hóa chọn Nested Loop thay vì Hash Join, gây sự cố điển hình truy vấn vài giây thành hàng chục phút — vì thế khi kế hoạch thực thi đột nhiên chậm thì trước hết kiểm tra thống kê và phương thức nối. Thứ ba, gợi ý bộ tối ưu hóa (USE_NL, USE_HASH, USE_MERGE, v.v.) có thể ép thuật toán, nhưng phải nhớ đây chỉ là liều thuốc tạm thời cho tình huống thống kê bị méo, còn giải pháp căn bản là chỉnh sửa thống kê·chỉ mục·cấu trúc truy vấn.

Thêm cảm nhận về con số cụ thể: trong nối bằng 10 triệu ⨝ 1 triệu mà kết quả chiếm phần lớn tổng thể, Hash Join kết thúc với hai lần quét tuần tự (vài giây); nhưng ép cùng truy vấn sang Nested Loop sẽ mất hàng chục phút với 10 triệu lần I/O ngẫu nhiên tìm kiếm chỉ mục. Ngược lại, trong truy vấn tìm 'đơn hàng của 10 khách hàng vừa đăng ký', Nested Loop kết thúc với 10 lần tìm kiếm chỉ mục (mili giây); nhưng ép sang Hash Join lãng phí vài giây quét toàn bộ 10 triệu đơn hàng để xây bảng băm. Cùng hai bảng đó, 'độ chọn lọc (selectivity) của kết quả' đảo ngược hoàn toàn ưu thế của thuật toán.

Tóm tắt hướng dẫn lựa chọn trong một câu như sau. "Nếu độ chọn lọc thấp (kết quả nhỏ) để tập dẫn đầu có thể làm nhỏ và phía đi sau có chỉ mục thì Nested Loop; nếu độ chọn lọc cao (kết quả lớn) đòi hỏi đọc cả hai phía và là nối bằng thì Hash Join; nếu một phía đã sắp xếp hoặc điều kiện nối là bất đẳng thức thì Sort-Merge." Trong tinh chỉnh thực tiễn, hướng dẫn này được dùng ngược lại — tức 'thiết kế chỉ mục·thống kê·cấu trúc truy vấn sao cho thuật toán mong muốn xuất hiện'. Ví dụ nếu truy vấn OLTP kết quả nhỏ lại được giải một cách kỳ lạ bằng Hash Join, thì bổ sung điều kiện thu hẹp tập dẫn đầu và chỉ mục khóa nối phía đi sau để dẫn dắt bộ tối ưu hóa chọn Nested Loop. Ngược lại nếu batch lớn được giải bằng Nested Loop và chậm, thì làm mới thống kê hoặc dẫn dắt Hash Join bằng gợi ý USE_HASH. Như vậy, biết nguyên lý của thuật toán sẽ giúp chẩn đoán 'tại sao chậm' và thiết kế 'dẫn dắt thế nào'.

7. Nâng cao: sự tiến hóa xử lý nối trong DBMS hiện đại và áp dụng thực tiễn

Ba thuật toán nối cơ bản không đổi trong hàng chục năm, nhưng các kỹ thuật tối ưu xếp chồng lên trên chúng đã phát triển đều đặn. Các xu hướng mới nhất gặp trong thực tiễn được sắp xếp thành ba.

Cả ba dòng này đều tấn công những điểm khác nhau dưới mục tiêu chung 'giảm thêm chi phí nối'. Nối thích ứng nhắm vào độ chính xác của lựa chọn, nối song song·phân tán nhắm vào khả năng mở rộng của xử lý, còn loại bỏ nối·tổng hợp trước nhắm vào việc giảm chính khối lượng công việc. Trong cả kỳ thi kỹ sư chuyên nghiệp lẫn thực tiễn, phải có thể đan ba trục này lại với nhau và thiết kế 'tại sao chậm → can thiệp ở mức nào (lựa chọn·mở rộng·loại bỏ)'.

Thứ nhất là nối thích ứng (Adaptive Join). Như Adaptive Plan của Oracle 12c, Adaptive Join của SQL Server, bộ tối ưu hóa không cố định vào một phương thức trước khi thực thi mà chuyển đổi động giữa Nested Loop và Hash Join bằng cách quan sát số hàng xử lý thực tế trong khi chạy. Đây là nỗ lực hiệu chỉnh ngay khi chạy vấn đề 'phân kỳ giữa cardinality ước lượng và thực tế' do sai số thống kê, đóng vai trò cơ chế an toàn ngăn phán đoán sai nghiêm trọng ngay cả khi thống kê hơi thiếu chính xác. Cùng mạch đó, PostgreSQL đã mở rộng hướng cải thiện lần thực thi tiếp theo bằng thống kê thu thập trong khi chạy.

Thứ hai là nối song song và nối phân tán. Trong môi trường phân tích dung lượng lớn (MPP DW, Spark, Presto/Trino, v.v.), nối băm được cắt thành nhiều nút và thực hiện song song. Lúc này lựa chọn giữa nối xáo trộn (shuffle/repartition join) phân phối lại cả hai phía theo khóa nối và nối phát sóng (broadcast join) nhân bản bảng nhỏ ra tất cả các nút để loại bỏ xáo trộn chi phối hiệu năng phân tán. Nếu một phía đủ nhỏ thì broadcast loại bỏ chi phí xáo trộn mạng và nhanh áp đảo, đây là hình thức mở rộng sang môi trường phân tán của nguyên lý 'lấy phía nhỏ làm build' của Hash Join đơn nút. Ở các khóa nối lệch dữ liệu (skew) nghiêm trọng, phát sinh vấn đề 'skew join' nơi công việc dồn vào một nút cụ thể, nên áp dụng tối ưu skew xử lý riêng các khóa nóng.

Thêm nữa, xử lý chuyên dụng theo loại phép nối (semi/anti/outer join) cũng quan trọng. EXISTS·IN là nối nửa (semi join) chỉ cần một cặp là đủ, dừng tìm kiếm ở lần khớp đầu để giảm chi phí. NOT EXISTS là nối đối (anti join) dùng logic ngược lại, và OUTER JOIN phải bảo tồn cả hàng không có cặp bằng cách điền NULL nên cách triển khai thuật toán khác đi đôi chút. Bộ tối ưu hóa biến chúng thành nối thông thường bằng làm phẳng truy vấn con (unnesting) để tái dùng ba thuật toán, nhưng tối ưu thêm bằng cách tận dụng đặc tính 'kết thúc sớm' của semi/anti. Cùng là Hash Join, nếu là nối nửa thì chỉ đánh dấu phía build có khớp hay không rồi dừng.

Thứ ba là loại bỏ nối và tổng hợp trước. Bộ tối ưu hóa loại bỏ hoàn toàn các nối không ảnh hưởng kết quả khi toàn vẹn khóa ngoại-khóa chính được bảo đảm (join elimination), và chiến lược tính trước kết quả nối hay dùng vào khung nhìn thực thể hóa (Materialized View) là chuẩn ở DW. Ngoài ra, kết hợp với lưu trữ cột·engine thực thi vector hóa, các triển khai thân thiện phần cứng xử lý nối băm theo đơn vị SIMD để nâng hiệu quả CPU cũng đã phổ biến. Trong thực tiễn, xác nhận trong kế hoạch thực thi (EXPLAIN, EXPLAIN ANALYZE, DBMS_XPLAN của Oracle) phương thức nối nào đã được chọn và chênh lệch số hàng thực tế so với ước lượng là điểm khởi đầu của tinh chỉnh.

8. Điểm cần cân nhắc và hàm ý

Vì thuật toán nối không phải lý thuyết suông mà là cốt lõi thực tiễn phân chia hiệu năng·tài nguyên·ổn định vận hành, nên từ quan điểm Kỹ sư chuyên nghiệp phải cân nhắc tổng hợp những điều sau. Đặc biệt, ghi nhớ rằng nối là quan hệ mà 'chỉ mục·phân vùng·thống kê quyết định ở thời điểm thiết kế' và 'thuật toán được chọn ở thời điểm thực thi' ràng buộc lẫn nhau, nên việc phản ánh trước chiến lược nối phù hợp với mẫu truy vấn dự kiến ngay từ giai đoạn thiết kế vật lý là điều nên làm.

Chiến lược áp dụng — dẫn dắt thuật toán phù hợp với tính chất truy vấn: Với OLTP (nhỏ·đồng thời cao), tối ưu cho Nested Loop và thiết kế chỉ mục; với OLAP·batch (lớn·tổng hợp), tối ưu cho Hash Join và hiệu quả quét tuần tự (phân vùng·nén·mức song song). Khi dùng một DBMS cho workload trộn lẫn OLTP/OLAP, phải tách đặc tính của từng nhóm truy vấn và áp dụng chiến lược chỉ mục·thống kê·bộ nhớ một cách phân biệt.
Đánh đổi — bộ nhớ vs I/O, khả năng đáp ứng vs thông lượng: Hash Join là sự đánh đổi dùng bộ nhớ để giảm I/O, và nếu vùng băm thiếu thì rơi xuống dựa trên đĩa và lợi ích biến mất. Nested Loop vô cảm với bộ nhớ nhưng I/O ngẫu nhiên bùng nổ ở dung lượng lớn. Ngoài ra, Nested Loop cho kết quả đầu tiên nhanh (khả năng đáp ứng) trong khi Hash/Sort-Merge phải xử lý toàn bộ (thông lượng), nên lựa chọn thay đổi tùy SLA là 'thời gian phản hồi đầu tiên' hay 'thời gian hoàn tất toàn bộ'.
Ổn định vận hành — quản lý thống kê và ổn định hóa kế hoạch: Vì 90% việc phán đoán sai phương thức nối bắt nguồn từ 'thống kê cũ hoặc không chính xác', nên thu thập thống kê định kỳ·tự động và histogram (biểu diễn phân bố lệch) phải đi trước. Với các truy vấn quan trọng, đặt các cơ chế 'ổn định hóa kế hoạch (plan stability)' như SQL Plan Baseline·cố định kế hoạch, gợi ý, cache kết quả để ngăn kế hoạch đột nhiên thay đổi gây sự cố.
Năng lực chẩn đoán — đọc hiểu kế hoạch thực thi: Điểm khởi đầu của ứng phó sự cố là đọc qua EXPLAIN/EXPLAIN ANALYZE 'bộ tối ưu hóa chọn phương thức nối nào, và số hàng ước lượng (estimated rows) với số hàng thực tế (actual rows) chênh lệch bao nhiêu'. Nếu phân kỳ của hai cái lớn thì nghi ngờ sai số thống kê·ước lượng cardinality, và nhận diện giai đoạn chậm là lặp quá mức của Nested Loop, tràn đĩa (spill) của Hash Join, hay sắp xếp ngoài của Sort-Merge để kê đơn theo nguyên nhân.
Triển vọng và công nghệ liên kết: Với sự phổ biến của thực thi thích ứng, vector hóa·tăng tốc GPU và engine truy vấn phân tán, xử lý nối đang chuyển từ 'lựa chọn tĩnh' sang 'thích ứng khi chạy'. Kiến thức thuật toán nối liên kết chặt chẽ với [[db-optimizer]](Bộ tối ưu hóa RBO·CBO), [[btree-bplus-index]](cấu trúc chỉ mục), [[db-tuning]](tinh chỉnh DB), [[materialized-view]](khung nhìn thực thể hóa), [[columnar-storage]](lưu trữ cột), và việc tích hợp chúng thành một hệ thống hiệu năng duy nhất để hiểu·thiết kế là năng lực mà Kỹ sư chuyên nghiệp cần có.

Tài liệu tham khảo

Oracle Database SQL Tuning Guide — Joins, https://docs.oracle.com/en/database/oracle/oracle-database/19/tgsql/joins.html
PostgreSQL Documentation — Planner/Optimizer, https://www.postgresql.org/docs/current/planner-optimizer.html
Microsoft SQL Server — Adaptive Query Processing, https://learn.microsoft.com/en-us/sql/relational-databases/performance/intelligent-query-processing

Tóm tắt một câu: Thuật toán nối là chiến lược vật lý để tìm cặp của hai bảng — Nested Loop cho tập nhỏ·có chỉ mục, Sort-Merge cho đã sắp xếp·bất đẳng thức, Hash Join cho nối bằng lớn — và chất lượng của lựa chọn đó rốt cuộc phụ thuộc vào thống kê chính xác cùng thiết kế chỉ mục·bộ nhớ thích hợp.