Kiến thức nền

Liên quan

Kho lưu trữ · 2.408 từ · 10 phút đọc

JOIN: Các mối quan hệ qua giá trị, không phải con trỏ

Diễn đạt các mối quan hệ qua giá trị chia sẻ thay vì tham chiếu vật lý là bước đột phá thực sự của mô hình quan hệ. Năm mươi năm sau, bốn loại join, ba thuật toán join, và một câu hỏi căn bản vẫn chạy hầu hết dữ liệu của thế giới.

Mục lục
  1. TL;DR
  2. Trước JOIN: Điều hướng con trỏ
  3. Lựa chọn quan hệ
  4. Bốn loại Join
    1. INNER JOIN
    2. LEFT OUTER JOIN
    3. RIGHT OUTER JOIN
    4. FULL OUTER JOIN
    5. Join thứ năm không ai yêu cầu: CROSS JOIN
  5. Ba thuật toán Join
    1. Nested Loop Join
    2. Hash Join
    3. Sort-Merge Join
  6. Tại sao thứ tự Join quan trọng
  7. Tại sao không chỉ dùng cơ sở dữ liệu đồ thị?
  8. Phi chuẩn hóa: Khi Join gây tổn thương
  9. Điều JOIN thực sự chứng minh

#TL;DR

Trong cơ sở dữ liệu trước-quan-hệ, các mối quan hệ giữa các bản ghi là con trỏ vật lý — bạn điều hướng từ bản ghi khách hàng đến bản ghi đơn hàng bằng cách theo một địa chỉ bộ nhớ đúng nghĩa mà người viết cơ sở dữ liệu đã quyết định lưu. Trong mô hình quan hệ của Codd, các mối quan hệ là logic: một giá trị chia sẻ trong hai bảng (ID của khách hàng xuất hiện cả trong bảng customers và bảng orders), và phép toán JOIN kết hợp các hàng từ hai bảng theo yêu cầu. Nghe có vẻ là một thay đổi nhỏ nhưng thực ra là sự khác biệt giữa một cơ sở dữ liệu bạn có thể tiến hóa và một cơ sở không thể. Join có bốn loại (INNER, LEFT, RIGHT, FULL OUTER), thực thi với ba thuật toán chính (nested loop, hash, sort-merge), và là nguồn của hầu hết các vấn đề hiệu năng trong khối lượng công việc cơ sở dữ liệu thực tế.

#Trước JOIN: Điều hướng con trỏ

Trong các cơ sở dữ liệu mạng CODASYL và cơ sở dữ liệu phân cấp IMS, các mối quan hệ là rõ ràng. Một bản ghi khách hàng có một con trỏ vật lý đến bản ghi đơn hàng đầu tiên của nó. Mỗi bản ghi đơn hàng có một con trỏ đến bản ghi tiếp theo. Để tìm tất cả đơn hàng của một khách hàng, bạn viết code trông đại khái như thế này:

customer = find_customer(id=101)
order = customer.first_order
while order is not None:
    process(order)
    order = order.next_order

Đây là hiệu quả nếu câu hỏi duy nhất bạn muốn hỏi là “cho tôi các đơn hàng của khách hàng 101.” Đó cũng là câu hỏi duy nhất bạn có thể hỏi rẻ. Để đi từ một đơn hàng về khách hàng, bạn cần một con trỏ ngược — và con trỏ ngược đó phải được thiết lập khi dữ liệu được chèn vào. Để tìm “tất cả đơn hàng đến các địa chỉ London” bạn phải đi qua mọi danh sách đơn hàng của khách hàng và lọc.

Mỗi mẫu truy vấn mới yêu cầu các con trỏ mới. Mỗi con trỏ mới yêu cầu thay đổi schema, di chuyển dữ liệu, và code ứng dụng đã sửa đổi. Truy vấn nhanh khi được dự đoán và không thể khi không.

#Lựa chọn quan hệ

Bài báo năm 1970 của Codd đề xuất điều ngược lại: không có con trỏ gì cả. Một bản ghi khách hàng có ID. Một bản ghi đơn hàng có cột customer_id. Mối quan hệ là sự thật rằng hai cột chứa các giá trị khớp. Dữ liệu không biết điều này về mặt vật lý — đó là một tính chất logic của dữ liệu, tính chất mà cơ sở dữ liệu có thể khám phá và khai thác tại thời điểm truy vấn.

Customers                          Orders
┌────┬──────────────┬──────────┐  ┌────┬─────────┬──────┐
│ id │ name         │ city     │  │ id │ cust_id │  amt │
├────┼──────────────┼──────────┤  ├────┼─────────┼──────┤
│101 │ Ada Lovelace │ London   │  │  1 │     101 │  250 │
│102 │ Alan Turing  │ London   │  │  2 │     102 │   80 │
│103 │ Grace Hopper │ New York │  │  3 │     101 │  430 │
└────┴──────────────┴──────────┘  └────┴─────────┴──────┘

Mối quan hệ ngầm: orders.cust_id khớp customers.id

Không có con trỏ nào trong bảng orders nói “đơn hàng này thuộc bản ghi khách hàng vật lý này.” Cột cust_id chỉ nói “khách hàng cho đơn hàng này có bất kỳ ID nào là 101.” Join các bảng trên orders.cust_id = customers.id tạo ra góc nhìn kết hợp.

Phần thưởng là sự linh hoạt. Cùng dữ liệu có thể được join theo các hướng khác nhau cho các truy vấn khác nhau:

  • “Tìm tất cả đơn hàng của Ada” — join từ customers đến orders.
  • “Tìm khách hàng đã đặt đơn 3” — join từ orders đến customers.
  • “Tìm tất cả khách hàng đã đặt hơn 400$” — join và lọc.
  • “Tìm giá trị đơn hàng trung bình theo thành phố” — join và tổng hợp.

Cơ sở dữ liệu không phải được thiết kế với bất kỳ truy vấn nào trong số này trong đầu. Các mối quan hệ vốn có trong dữ liệu, và ngôn ngữ truy vấn khám phá chúng.

#Bốn loại Join

SQL phơi bày bốn loại join chính, được phân biệt bởi những gì xảy ra với các hàng không có khớp.

#INNER JOIN

Mặc định. Chỉ các hàng có khớp ở cả hai bảng mới xuất hiện trong kết quả.

SELECT c.name, o.amount
FROM customers c
INNER JOIN orders o ON o.cust_id = c.id;

Nếu một khách hàng không có đơn hàng, họ không xuất hiện. Nếu một đơn hàng không có khách hàng khớp (sẽ chỉ ra vi phạm toàn vẹn tham chiếu), nó không xuất hiện.

#LEFT OUTER JOIN

Tất cả hàng từ bảng bên trái, cộng với các khớp từ bên phải. Các hàng bên trái không khớp nhận NULL ở phía bên phải.

SELECT c.name, o.amount
FROM customers c
LEFT JOIN orders o ON o.cust_id = c.id;

Grace Hopper không có đơn hàng. Cô ấy vẫn xuất hiện trong kết quả với NULL ở cột amount. Đây là join bạn sử dụng khi câu hỏi là “liệt kê tất cả khách hàng, và nếu họ có đơn hàng, hiển thị chúng.”

#RIGHT OUTER JOIN

Hình ảnh phản chiếu của LEFT. Tất cả hàng từ bảng bên phải, các hàng bên phải không khớp nhận NULL ở bên trái. Hiếm khi dùng trong thực tế — bạn luôn có thể viết lại một RIGHT JOIN thành LEFT JOIN bằng cách đổi các bảng, và hầu hết tác giả truy vấn thích đọc từ trái sang phải.

#FULL OUTER JOIN

Tất cả hàng từ cả hai bảng. Các hàng không khớp nhận NULL ở bên chúng không khớp. Hữu ích để tìm dữ liệu nên có trong cả hai bảng nhưng không có — báo cáo đối chiếu, ví dụ.

#Join thứ năm không ai yêu cầu: CROSS JOIN

CROSS JOIN là tích Descartes — mỗi hàng của bảng trái được ghép với mỗi hàng của bảng phải, không có điều kiện khớp. Nếu bạn có 1.000 khách hàng và 10.000 đơn hàng, một cross join trả về 10 triệu hàng. Thường là lỗi. Đôi khi cố tình — ví dụ, tạo tất cả tổ hợp giá trị để kiểm thử.

-- NGUY HIỂM: hiếm khi là thứ bạn muốn
SELECT c.name, o.amount
FROM customers c
CROSS JOIN orders o;

Một mệnh đề ON bị thiếu trong SQL thường tạo ra cross join vô tình, đó là lý do một số phương ngữ SQL hiện đại đôi khi từ chối chạy JOIN mà không có điều kiện join rõ ràng.

#Ba thuật toán Join

Viết JOIN trong SQL là khai báo — nó nói cái gì để join, không phải như thế nào. Trình tối ưu truy vấn chọn thuật toán vật lý dựa trên kích thước bảng, index có sẵn, bộ nhớ, và thống kê. Có ba lựa chọn chính.

#Nested Loop Join

for each row r in outer_table:
    for each row s in inner_table:
        if match(r, s):
            emit(r, s)

Độ phức tạp: O(N × M) cho các bảng kích thước N và M. Ngây thơ và chậm cho các bảng lớn — nhưng nếu có một index trên cột join của bảng bên trong, bạn có thể thay vòng lặp bên trong bằng một lookup index, giảm chi phí xuống O(N × log M).

Nested loop thắng khi:

  • Một bảng rất nhỏ (vài hàng).
  • Có một index tốt trên cột join của bảng bên trong.
  • Bộ nhớ chặt — nested loop không cần buffer.

#Hash Join

build: hash_table = {}
       for each row r in smaller_table:
           hash_table[r.join_key].append(r)

probe: for each row s in larger_table:
           for r in hash_table.get(s.join_key, []):
               emit(r, s)

Độ phức tạp: O(N + M) với khoảng O(N) bộ nhớ. Nhanh hơn nhiều so với nested loop cho các bảng lớn, nhưng yêu cầu đủ bộ nhớ để chứa hash của bảng nhỏ hơn. Biến thể: grace hash join phân vùng cả hai bảng xuống đĩa trước, sau đó hash-join từng phân vùng — vẫn hợp lý khi dữ liệu không vừa trong RAM.

Hash join thắng khi:

  • Cả hai bảng đều lớn.
  • Không có index hữu ích trên cột join.
  • Bảng nhỏ hơn vừa trong bộ nhớ.

#Sort-Merge Join

sắp xếp cả hai bảng theo khóa join
đi qua cả hai luồng đã sắp xếp song song, phát các khớp

Độ phức tạp: O(N log N + M log M) do sắp xếp, nhưng nếu dữ liệu đã được sắp xếp (ví dụ, đọc từ một index B-tree trên khóa join), giảm xuống O(N + M).

Sort-merge join thắng khi:

  • Cả hai bảng đã được sắp xếp theo khóa join.
  • Dữ liệu quá lớn cho dấu chân bộ nhớ của hash join.
  • Đầu ra dù sao cũng cần được sắp xếp.

Cơ sở dữ liệu hiện đại cũng có các biến thể: merge join không đẳng thức, broadcast join (cho hệ thống phân tán, nơi một bên đủ nhỏ để sao chép đến mọi nút), join hỗ trợ bloom filter, v.v. Ba cái trên là các trường hợp cốt lõi.

#Tại sao thứ tự Join quan trọng

Một truy vấn join bốn bảng có thể được thực thi theo nhiều thứ tự khác nhau:

SELECT *
FROM customers c
JOIN orders o    ON o.cust_id = c.id
JOIN order_items i ON i.order_id = o.id
JOIN products p  ON p.id = i.product_id;

Có 4! / 2 = 12 cách để sắp xếp các join này (tính cho cây nghiêng trái). Mỗi thứ tự tạo ra cùng kết quả nhưng với hiệu năng có khả năng rất khác nhau:

  • Join orders và order_items trước (cả hai bảng lớn) — bạn nhận được một kết quả trung gian khổng lồ.
  • Lọc customers về London trước, sau đó join với orders — kết quả trung gian nhỏ hơn nhiều.
  • Join products sớm nếu nó nhỏ và có tính chọn lọc cao — trung gian rất nhỏ.

Chọn giữa các lựa chọn này là công việc của trình tối ưu truy vấn, được trình bày trong bài riêng của nó. Lựa chọn phụ thuộc vào kích thước bảng, index có sẵn, và ước lượng cardinality từ thống kê. Làm sai và truy vấn của bạn chạy trong giờ thay vì mili giây.

Hầu hết các vấn đề “truy vấn này chậm” trong cơ sở dữ liệu thực tế là các vấn đề thứ tự join trá hình. EXPLAIN ANALYZE thường tiết lộ rằng trình tối ưu đã chọn thứ tự tồi vì thống kê của nó cũ hoặc vì cấu trúc truy vấn làm bối rối bộ ước lượng.

#Tại sao không chỉ dùng cơ sở dữ liệu đồ thị?

Một phản đối công bằng: nếu thứ chúng ta muốn là các mối quan hệ, tại sao không lưu chúng trực tiếp? Cơ sở dữ liệu đồ thị (Neo4j, JanusGraph, AWS Neptune) lưu các nút và cạnh như các thực thể hạng nhất, được index để duyệt nhanh.

Câu trả lời là hầu hết khối lượng công việc không thực sự là khối lượng công việc đồ thị. Chúng có các mối quan hệ, nhưng những mối quan hệ đó có độ sâu hạn chế và hình dạng có thể dự đoán được. Một truy vấn OLTP điển hình join 2-5 bảng. Một truy vấn phân tích điển hình tổng hợp qua một vài chiều. Đây là những trường hợp nơi:

  • Trừu tượng bảng-và-join của mô hình quan hệ khớp với cấu trúc của dữ liệu.
  • Index trên các cột khóa ngoại làm cho join rẻ.
  • Trình tối ưu truy vấn có thể tìm được kế hoạch tốt.

Cơ sở dữ liệu đồ thị tỏa sáng ở các truy vấn đệ quy sâu: “tìm tất cả người trong sáu mức cách biệt từ người này làm việc trong cùng ngành.” Đó là một traversal đồ thị thực sự mà SQL vật lộn để diễn đạt một cách thanh lịch (mặc dù SQL hiện đại có CTE đệ quy).

Đối với khối lượng công việc doanh nghiệp điển hình — khách hàng, đơn hàng, sản phẩm, danh mục, giao dịch — mô hình quan hệ với join là trừu tượng đúng. Nó đã được tối ưu hóa cạnh tranh trong năm mươi năm. Cơ sở dữ liệu đồ thị có vị trí ngách của nó, nhưng nhỏ hơn những gì tiếp thị của chúng gợi ý.

#Phi chuẩn hóa: Khi Join gây tổn thương

Ở quy mô đủ lớn, join có thể trở thành nút thắt cổ chai. Một truy vấn join một bảng transactions tỷ hàng với một bảng users tỷ hàng và một bảng products triệu hàng có thể chậm bất kể trình tối ưu tốt đến đâu, đơn giản vì khối lượng dữ liệu.

Phản ứng thực dụng là phi chuẩn hóa — lưu trữ dữ liệu dư thừa để tránh join tại thời điểm truy vấn. Thay vì:

SELECT t.amount, u.country
FROM transactions t
JOIN users u ON u.id = t.user_id;

Bạn có thể pre-store country trên chính bảng transactions:

SELECT amount, country
FROM transactions;  -- không cần join

Điều này nhanh hơn nhưng có chi phí. Cập nhật country của người dùng giờ phải lan đến mọi hàng transaction. Lưu trữ lớn hơn. Mô hình dữ liệu ít sạch hơn — bạn đã nhân bản thông tin.

Kho dữ liệu (Snowflake, BigQuery, Redshift) thường xuyên phi chuẩn hóa mạnh mẽ, vì các truy vấn phân tích hưởng lợi từ việc tránh join và tỷ lệ đọc-ghi cao đến mức chi phí cập nhật có thể chấp nhận được. Cơ sở dữ liệu OLTP phi chuẩn hóa thưa thớt, vì khối lượng công việc nặng ghi của chúng sẽ phải cập nhật các bản sao dư thừa liên tục.

Đây là một đánh đổi chủ động, không phải một vấn đề đã giải. Mô hình quan hệ cho bạn thiết kế đã chuẩn hóa như điểm xuất phát; phi chuẩn hóa là một sự khởi hành có chủ ý, có thể đo lường từ đó.

#Điều JOIN thực sự chứng minh

Bài về Mô hình Quan hệ gọi JOIN là “tuệ giác then chốt” của mô hình quan hệ. Khuôn khổ đó chính xác nhưng lạnh lùng. Điều JOIN thực sự chứng minh, trong thực tế:

  • Dữ liệu sống lâu hơn các trường hợp sử dụng ban đầu của nó. Một schema được thiết kế xoay quanh khóa ngoại có thể được truy vấn cho các tổ hợp mà nhà thiết kế ban đầu không lường trước. Schema phân cấp và mạng thì không thể.
  • Các mối quan hệ logic đánh bại các mối quan hệ vật lý. Một con trỏ là một địa chỉ bộ nhớ cụ thể. Một khóa ngoại là một giá trị chia sẻ, ổn định qua các di chuyển, nhân bản, phân mảnh, và khôi phục thảm họa.
  • Engine cơ sở dữ liệu có thể cải thiện. Join có thể được triển khai ngây thơ (nested loop) hoặc tinh vi (hash, sort-merge), và cải thiện triển khai không yêu cầu viết lại bất kỳ code ứng dụng nào. Năm mươi năm kỹ thuật cơ sở dữ liệu đã thêm các thuật toán join thông minh hơn vào cùng bề mặt SQL.

Cơ sở dữ liệu trước-quan-hệ không chậm. Chúng không linh hoạt. JOIN là thứ làm cho mô hình quan hệ linh hoạt: bất kỳ mối quan hệ nào, được khám phá theo yêu cầu, với thuật toán được chọn bởi trình tối ưu tại thời điểm chạy. Dữ liệu không cần biết nó sẽ được truy vấn như thế nào. Đó là thuộc tính làm cho mô hình quan hệ bền vững theo một cách mà không gì trước nó có.