13 cách để hiểu phép join trong (RDB)

 (justinjaffray.com)
4 điểm bởi GN⁺ 2023-07-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • inner join trong cơ sở dữ liệu quan hệ không chỉ là cú pháp SQL đơn thuần; cùng một cấu trúc có thể được diễn giải khác nhau qua góc nhìn truy vấn, vòng lặp lồng nhau, mô hình logic, kiểm tra kiểu và đại số
  • Trong các bảng đã chuẩn hóa, join trở thành công cụ thực tế nhất để kết hợp lại thông tin được lưu trữ không trùng lặp bằng cách lần theo các tham chiếu
  • Từ góc độ triển khai, có thể xem đây là việc duyệt qua các cặp hàng rồi chỉ giữ lại những tổ hợp thỏa điều kiện, hoặc chọn các tổ hợp giá trị chỉ tồn tại ở cả hai quan hệ trong miền của các cột
  • Trong mô hình lập trình, có thể giải thích join bằng flatMap, SQL LATERAL, việc giải quyết vấn đề N+1 trong ORM, kiểm tra kiểu dựa trên trait của Rust, và andThen của Set monad
  • Về mặt toán học, đường đi trên đồ thị, mô hình nhỏ nhất, quan hệ khả dĩ lớn nhất, cận trên tối thiểu trong thứ tự bộ phận, và tích vòng của biểu thức quan hệ đều bộc lộ cùng một tính chất của join

Trong dữ liệu đã chuẩn hóa, join trở thành truy vấn tra cứu

  • Về mặt thực tiễn nhất, có thể xem join là thao tác tra cứu một giá trị nào đó, hoặc gắn thêm thông tin dư thừa vào dữ liệu hiện có
  • Ví dụ bắt đầu từ cách lưu user, country, country_code trong cùng một bảng
    • Với mỗi giá trị country giống nhau, country_code bị lặp lại nên phát sinh trùng lặp
    • Nếu dữ liệu thường xuyên thay đổi, phải cập nhật tất cả các vị trí cùng lúc, làm tăng lỗi và giảm hiệu quả
  • Ở dạng chuẩn hóa, quan hệ giữa country và country_code được tách ra thành bảng riêng, còn bảng người dùng chỉ tham chiếu country_id
  • Khi INNER JOIN users và countries theo country_id, ta có thể thu lại dạng ban đầu gồm user, country, country_code
  • Từ đây, phần giải thích tiếp theo giả định rằng việc join được thực hiện ngầm theo các cột cùng tên, nhưng không ràng buộc quá chặt vào chi tiết cú pháp SQL

Góc nhìn triển khai: join duyệt qua hàng và cột

  • Với hai tập R, S và vị từ p, join sẽ duyệt mọi r ∈ R, s ∈ S, sau đó chỉ xuất ra các trường hợp mà p(r, s) là đúng
    • Nếu tích Descartes của hai tập là mọi cách nối hàng có thể có, thì join là tập con trong đó thỏa điều kiện
  • Nhìn theo hướng cột, có thể coi miền của mỗi cột là tập các giá trị khả dĩ, rồi duyệt các tổ hợp giá trị cột
    • Nếu có R(a, b) và S(b, c) thì sẽ duyệt miền của a, b, c
    • Chỉ khi (a, b) thuộc R và (b, c) thuộc S thì mới xuất ra [a, b, c]

Join như những hiện thực thay thế tương thích

  • Ví dụ về John và Sally giải thích join như cách chỉ giữ lại những hiện thực tương thích khi mỗi người chỉ biết một phần thông tin
  • John biết các tổ hợp có thể có giữa pet của mình và con vật stray, Sally cũng biết các tổ hợp có thể có giữa pet của cô ấy và con vật stray
    • Nếu John có dog thì trường hợp stray là dog, và nếu Sally có cat thì trường hợp stray là mouse, không thể đồng thời đúng
    • Bởi vì hai người phải đang quan sát cùng một stray
  • Khi join hai bảng theo stray, chỉ còn lại các tổ hợp pet của John · stray · pet của Sally không mâu thuẫn với nhau

Join trong mô hình lập trình

  • flatMap vốn là hàm tạo một mảng mới cho từng phần tử của mảng gốc rồi nối các kết quả lại, và có thể dùng để triển khai join
    • SELECT * FROM r INNER JOIN s ON p có thể biểu diễn thành r.flatMap(x => s.filter(y => p(x, y)))
    • Cú pháp LATERAL trong một số biến thể SQL biến join thành dạng flatMap
  • Nếu vế phải của LATERAL không tham chiếu tới cột ở vế trái thì nó tương đương với tích Descartes
    • Kỹ thuật decorrelation của truy vấn dựa vào việc loại bỏ các tham chiếu cột ở vế phải bằng một chuỗi phép viết lại liên tiếp
  • Vấn đề N+1 thường gặp trong ORM cũng có thể được giải thích bằng join
    • Nếu chạy thêm truy vấn cho từng hàng trong tập kết quả, thì với các cơ sở dữ liệu dùng connection như Postgres, chi phí cố định của từng truy vấn riêng lẻ là khá lớn
    • Kết quả của việc yêu cầu cơ sở dữ liệu “hãy thực hiện tất cả các tra cứu này” chính là một join như users INNER JOIN countries
    • Với cơ sở dữ liệu in-process như Sqlite, vấn đề này ít nghiêm trọng hơn

Đường đi trên đồ thị và mô hình logic

  • Vì quan hệ là thứ “liên kết” hai tập với nhau nên có thể xem nó như một đồ thị
    • Bảng users nối tập tên người dùng với tập country_id
    • Quan hệ nối country_id với mã quốc gia hai ký tự cũng có thể được biểu diễn thành một đồ thị riêng
  • Nếu tập bên phải của đồ thị thứ nhất và tập bên trái của đồ thị thứ hai cùng chia sẻ một vertex set, ta có thể gộp chúng lại thành một
  • Liệt kê mọi đường đi từ tập bên trái, đi qua vertex ở giữa rồi sang tập bên phải sẽ cho ra join của hai quan hệ
  • Trong logic hình thức, quan hệ được xem là vị từ, còn mô hình là tập các sự kiện làm cho tập mệnh đề trở thành đúng
    • Nếu users(A, B) và countries(B, C, D) là đúng thì có một hàm ý rằng Q(A, B, C, D) là đúng
    • Có thể tồn tại nhiều mô hình thỏa điều kiện này
    • Để có kết quả chuẩn tắc, ta chọn mô hình nhỏ nhất trong các mô hình thỏa điều kiện
    • Mô hình nhỏ nhất này chính là kết quả join của users và country

Join như kiểm tra kiểu

  • Hệ kiểu kiểu ML rất giống Prolog và Datalog, nên có thể biểu diễn theo cách gần với join
  • Trong ví dụ Rust, các quan hệ được định nghĩa bằng trait
    • Users và CountryCode đóng vai trò các quan hệ
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US được định nghĩa như các kiểu cụ thể
  • Các triển khai trait như (Smudge, Canada): Users, (Canada, CA): CountryCode tương ứng với các hàng của quan hệ
  • Để (A, B, C) được nằm trong join thì cần có (A, B): Users và (B, C): CountryCode
  • test::<(Smudge, _, CA)>() sẽ kiểm tra kiểu thành công, nhưng test::<(Smudge, _, US)>() sẽ thất bại vì không có triển khai (Canada, US): CountryCode

Join như phép toán của Set monad

  • Ví dụ Some và None trong JavaScript bắt đầu từ cách gộp các record tùy chọn
    • Nếu hai record có cùng country thì gộp chúng lại và trả về Some
    • Nếu không tương thích hoặc không có giá trị thì trả về None
  • andThen lấy giá trị bên trong optional ra rồi áp dụng hàm gộp
  • Giữ nguyên cùng hàm combine nhưng đổi container thành Rel, ta có thể xử lý tập quan hệ
    • Rel.map áp dụng hàm cho mọi hàng
    • Rel.andThen nối các quan hệ sinh ra từ từng hàng bằng flatMap
  • Khi chạy cùng combine trên quan hệ users và quan hệ countries, ta thu được kết quả join trong đó Smudge, Sissel, Petee được gắn thêm mã quốc gia

Quan hệ khả dĩ lớn nhất và join trong thứ tự bộ phận

  • Một quan hệ thứ ba T có đầy đủ mọi cột của hai quan hệ R, S được gọi là khả dĩ nếu nó không bịa ra thông tin mới
    • Khi giới hạn một hàng của T xuống các cột của R, hàng đó phải thuộc R
    • Tương tự, khi giới hạn xuống các cột của S, hàng đó cũng phải thuộc S
  • Ví dụ, Smudge, Canada, US là không khả dĩ
    • Nếu chỉ nhìn country, country_code thì sẽ thành Canada, US, nhưng đó không phải là hàng tồn tại trong S
  • Quan hệ rỗng cũng là khả dĩ, nhưng quan hệ khả dĩ lớn nhất sẽ chứa Smudge-Canada-CA, Sissel-Canada-CA, Petee-United States-US
  • Quan hệ khả dĩ lớn nhất này chính là join của hai quan hệ
  • Ở góc nhìn thứ tự bộ phận, ta định nghĩa R ≤ Q như sau
    • Q bao gồm mọi cột của R
    • Nếu giới hạn từng hàng của Q xuống các cột của R, ta sẽ thu được một hàng của R
  • Trong thứ tự bộ phận này, tồn tại cận trên tối thiểu R ∨ S của hai quan hệ R, S, và đó chính là join theo nghĩa quan hệ

Join như tích vòng

  • Quan hệ cũng có thể được biểu diễn dưới dạng đại số
    • Một hàng được biểu diễn bằng tích của các cặp cột-giá trị
    • Một quan hệ được biểu diễn bằng tổng của nhiều hàng
  • Ví dụ, hạng tử là tích của user = Smudge và country_id = 1 sẽ tương ứng với một hàng
  • Có thêm các quy tắc để đơn giản hóa biểu thức
    • Idempotence: [x = y][x = y] = [x = y]
    • Contradiction: [x = y][x = z] = 0 if y ≠ z
  • Khi nhân quan hệ người dùng R với quan hệ tra cứu quốc gia S, rồi khai triển bằng luật phân phối và giao hoán, các hạng tử mâu thuẫn sẽ biến mất và chỉ còn lại các hạng tử tương thích
  • Biểu thức còn lại là Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US, và đó chính xác là join của hai quan hệ
  • Cách này cũng có thể được xem là tensor contraction

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-04
Ý kiến trên Hacker News

  • Từ khi bắt đầu hình dung join theo chiều không gian, tôi thấy nó dễ hiểu hơn nhiều
    Nếu đặt mỗi chiều thành một bảng riêng như Dim_X, Dim_Y, Dim_Z rồi gắn chúng bằng cùng EntityId, có thể xem đó là cách cấu thành vị trí 3 chiều của một thực thể
    Để tạo 3 chiều thì cần ít nhất 2 phép inner join, và cũng có thể mở rộng theo cách tương tự cho các chiều phi không gian như thời gian
    Nếu không giới hạn một thời điểm cụ thể, nó sẽ trở thành một báo cáo chứa mọi vị trí mà một thực thể từng có theo thời gian
    Các kiểu join khác cũng dễ hiểu hơn theo biến thể này nếu bạn nắm được khái niệm đủ để có thể “xoay” schema trong đầu

    • Làm tôi nhớ đến HyperDex. Nó dùng cách băm giá trị vào siêu không gian đa chiều dựa trên thuộc tính để làm chỉ mục
      https://dbdb.io/db/hyperdex
    • Cái này có vẻ gần với siêu chuẩn hóa dữ liệu hơn. Thông thường nếu là BCNF thì có lẽ chỉ để thành bảng như EntityPosition(EntityId, X, Y, Z)
      Tuy vậy, ở chỗ phải ghép các mảnh của nhiều chiều và xử lý tổng hợp thì nó gợi nhớ đến phía data warehouse
    • Tôi vẫn luôn thắc mắc tại sao lại dùng cú pháp như JOIN, INNER JOIN. Liệt kê bảng trong FROM rồi viết điều kiện join trong mệnh đề WHERE như một phương trình có vẻ rõ ràng hơn nhiều
      Khi nhiều JOIN trộn lẫn trong một mệnh đề FROM phức tạp thì rất khó đọc, còn đọc các biểu thức điều kiện tương đương trong WHERE lại trực quan hơn
    • Không biết có thể hiểu rằng mọi phép join đều là biến thể của cross join hay không

  • Góc nhìn số 0 là: “join là toán tử của đại số quan hệ”
    https://en.m.wikipedia.org/wiki/Relational_algebra
    Natural join R ⋈ S là tập hợp các tổ hợp tuple có cùng tên thuộc tính chung, và là phép toán quan hệ tương ứng với phép logic AND
    Có thể xem ⋈ là tích Descartes rồi dùng vị từ để lọc ra các hàng không được phép xuất hiện trong kết quả, và khá nhiều phần của SQL sẽ dễ hiểu theo góc nhìn này

    • Trong cách diễn giải hàm của lý thuyết quan hệ, join là hợp thành hàm, nên khá bất ngờ vì góc nhìn đó bị bỏ qua
    • Trong cách giải thích “vòng lặp lồng nhau trên các hàng” đã bao hàm góc nhìn tích Descartes + vị từ

  • Tôi đã tìm tài liệu về triển khai thực thi/lập kế hoạch truy vấn suốt mấy ngày nay, nhưng rất khó tìm được tài liệu đi vào phần hiện thực như vị từ, chỉ mục sẵn có, hay join
    Kết quả Google bị ô nhiễm bởi các tài liệu hướng dẫn cách dùng
    Đến giờ thứ duy nhất tôi tìm được là tài liệu của CMU Database Group, và nó rất xuất sắc

    • Có một cuốn sách miễn phí dài 700 trang về chủ đề này: “Building Query Compilers”
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      Khóa học “Database Systems on Modern CPU Architectures” của TUM cũng có thể hữu ích, và tài liệu năm 2020 có đầy đủ video bài giảng
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • Không chắc có đúng độ sâu bạn muốn hay không, nhưng tài liệu tổng quan tối ưu hóa và query planner của SQLite rất đáng xem
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • Trong tình huống này người ta cũng hay khuyên đọc tài liệu Postgres và mã nguồn. Mã nguồn của nó cũng khá dễ đọc
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • Đây là chủ đề khá chuyên sâu nên khó tìm được giáo trình hay, và còn tùy bạn muốn đi sâu đến mức nào cũng như quan tâm phần nào
      Thực thi truy vấn và lập kế hoạch truy vấn trên thực tế gần như là hai thứ riêng biệt
      Về các bài báo tối ưu hóa join, tôi vẫn cho rằng bài Selinger gốc là tốt nhất
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      Nó không hỗ trợ outer join và sau đó đã có những kỹ thuật hiệu quả hơn, nhưng với ai xem các optimizer kiểu System R thì nó vẫn là tài liệu quen thuộc và dễ đọc
      src/backend/optimizer/README của Postgres cũng có nhiều nội dung khó tìm thấy ở nơi khác
      Các bài giảng của Andy Pavlo ở CMU gần như là tài liệu duy nhất trên mạng giải thích phần này, còn PDF “Building Query Compilers” tuy chưa hoàn chỉnh nhưng có các bài báo cốt lõi của Moerkotte và cộng sự nên vẫn đáng đọc nếu muốn làm hiện thực hiện đại
      Việc tìm các chỉ mục có thể áp dụng thường không quá khó vì chỉ cần xem có sargable predicate hay không, nhưng ước lượng độ chọn lọc thì khó, và ước lượng độ chọn lọc sau join gần như là bài toán khó nhất trong optimizer
      Ví dụ, nếu có A=x AND B=y AND C=z và chỉ có thông tin độ chọn lọc/cardinality của các chỉ mục (A,B), (B,C), thì việc ước lượng độ chọn lọc của toàn bộ ba điều kiện cũng không hề đơn giản
      Thậm chí có bài báo đòi hỏi bộ giải cho “quy hoạch nón bậc hai” để giải chuyện này
    • Tôi thử thêm relational algebra vào trước từ khóa và tìm query planning, thì nhìn qua đã thấy xuất hiện nhiều kết quả thiên về hiện thực hơn

  • Cách thứ 14 là multiway join, còn được gọi là “worst-case optimal join”, nhưng cái tên này không hay lắm
    Nghĩa là thay vì join từng cặp bảng và liên tục tạo kết quả trung gian, ta join từ 3 bảng trở lên cùng lúc mà không cần kết quả trung gian
    Bài blog liên quan và video ngắn có tại https://relational.ai/blog/dovetail-join, còn bài báo gốc ở https://dl.acm.org/doi/pdf/10.1145/3180143
    Tôi đang làm việc tại RelationalAI, và thuật toán join mới này, đã được nghiên cứu trong giới học thuật khoảng 10 năm, đang được chúng tôi cùng một vài công ty cơ sở dữ liệu khởi nghiệp khác đưa ra thị trường

    • Bài giới thiệu về WCOJ của Justin cũng khá hay
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • Nếu phủ định đầu vào, tức đổi sang phần bù của tập hợp, thì AND của join sẽ thành NOR, và Tetris tận dụng điểm này
      Cận worst-case không chặt hơn so với WCOJ không trạng thái/streaming, nhưng dữ liệu thực tế thường có chứng chỉ hộp nhỏ hơn nhiều
      Tôi chưa thấy liệu dovetail join có hỗ trợ truy vấn đệ quy, tức datalog tùy ý nơi chỉ định quan hệ đầu ra còn các quan hệ trung gian để engine tự xử lý, hay không
      Tôi tò mò không biết nó có hỗ trợ các truy vấn như vậy không

  • Cần có nhiều bài như thế này hơn để cho lập trình viên ở tầng ứng dụng thấy được sự tinh tế của mô hình quan hệ
    Phần giải thích và khai phá từ góc nhìn lập trình hàm cũng ngắn gọn và thuyết phục

  • Có vẻ đã bỏ lỡ thêm một cơ hội để dạy về vấn đề N+1
    Join vào chỉ mục không được phân cụm vẫn là N+1, chỉ là N+1 trên đĩa chứ không phải N+1 đi qua lại giữa mạng và đĩa

    • Nghe như kiểu “đáng ra phải bàn về vấn đề X mà tôi quan tâm, và như vậy bài có dài thêm cũng không sao”

  • Inner join là tích Descartes kèm điều kiện

    • Giữa việc tạo ra tích Descartes rồi lọc bằng điều kiện, và việc sinh trực tiếp các điều kiện đó, có khác biệt hiệu năng lớn
      Inner join với điều kiện equi-join thì sinh trực tiếp điều kiện, còn điều kiện non-equi join thì cần đánh giá thực sự

  • Giải thích hay. Câu “cách đúng là chuẩn hóa các bảng” thì đúng với cơ sở dữ liệu giao dịch, nhưng trong kho dữ liệu, một mức độ phi chuẩn hóa nào đó được chấp nhận khá rộng rãi

  • Ví dụ về chuẩn hóa làm tôi nhớ đến thời trước từng thiết kế bảng với suy nghĩ khóa chính số sẽ nhanh hơn chuỗi
    Rồi như vậy sinh ra các id vô nghĩa, và để lấy được giá trị duy nhất thực sự mình muốn thì lại phải join
    Đến một ngày tôi nhận ra rằng nếu dùng cùng một khóa duy nhất ở hai bảng thì có thể giảm số lần join, và dù đơn giản nhưng rất hiệu quả

    • Dù vậy tôi vẫn thích có trường id duy nhất cho mỗi bảng. Nó hữu ích cho việc ghi log và không phải bận tâm đến khóa “thật” gồm nhiều trường
      Thay vào đó, tôi đặt chỉ mục duy nhất trên các giá trị chuỗi, và quan trọng hơn là áp các ràng buộc toàn vẹn lên đó
      Một bảng đầy các chuỗi có ý nghĩa dễ đọc hơn nhiều so với một bảng đầy id số hoặc UUID