Những ý tưởng cốt lõi của Jeffrey Ullman thúc đẩy cơ sở dữ liệu hiện đại: đại số quan hệ, quy tắc tối ưu, join, và lập kế hoạch kiểu compiler giúp hệ thống mở rộng.
Hầu hết những người viết SQL, xây dashboard, hoặc tinh chỉnh một truy vấn chậm đều hưởng lợi từ công trình của Jeffrey Ullman—dù họ chưa từng nghe tên ông. Ullman là một nhà khoa học máy tính và giảng viên, những nghiên cứu và giáo trình của ông giúp định nghĩa cách cơ sở dữ liệu mô tả dữ liệu, suy luận về truy vấn, và thực thi chúng một cách hiệu quả.
Khi một engine cơ sở dữ liệu biến SQL của bạn thành thứ nó có thể chạy nhanh, nó dựa vào những ý tưởng vừa chính xác vừa linh hoạt. Ullman giúp chính thức hóa ý nghĩa của truy vấn (để hệ thống có thể viết lại an toàn), và ông kết nối suy nghĩ về cơ sở dữ liệu với suy nghĩ về compiler (để truy vấn có thể được phân tích cú pháp, tối ưu và dịch thành các bước thực thi).
Ảnh hưởng đó thầm lặng vì nó không hiện ra thành một nút bấm trong công cụ BI của bạn hay một tính năng hiển thị trong console cloud. Nó thể hiện qua:
JOINBài viết này dùng các ý tưởng cốt lõi của Ullman làm chuyến tham quan có hướng về nội bộ cơ sở dữ liệu quan trọng nhất trong thực tế: cách đại số quan hệ nằm dưới SQL, cách viết lại truy vấn bảo toàn ý nghĩa, tại sao bộ tối ưu dựa trên chi phí đưa ra lựa chọn như vậy, và cách các thuật toán join thường quyết định một công việc kết thúc trong vài giây hay vài giờ.
Chúng ta cũng sẽ lồng một vài khái niệm giống compiler—phân tích cú pháp, viết lại, và lập kế hoạch—bởi vì engine cơ sở dữ liệu hành xử giống những compiler tinh vi hơn nhiều người tưởng.
Lời hứa nhanh: chúng ta sẽ giữ thảo luận chính xác, nhưng tránh các chứng minh nặng toán. Mục tiêu là cung cấp mô hình tư duy bạn có thể áp dụng ở nơi làm việc lần tới khi vấn đề hiệu năng, scale, hoặc hành vi truy vấn khó hiểu xuất hiện.
Nếu bạn từng viết một truy vấn SQL và mong nó “chỉ có một nghĩa duy nhất,” bạn đang dựa vào những ý tưởng mà Jeffrey Ullman đã giúp phổ biến và chính thức hóa: một mô hình rõ ràng cho dữ liệu, cộng với các cách chính xác để mô tả thứ một truy vấn yêu cầu.
Ở lõi, mô hình quan hệ xử lý dữ liệu như bảng (relation). Mỗi bảng có hàng (tuple) và cột (attribute). Nghe có vẻ hiển nhiên bây giờ, nhưng phần quan trọng là kỷ luật nó tạo ra:
Cách nhìn này giúp suy nghĩ về tính đúng đắn và hiệu năng mà không phải nói chung chung. Khi bạn biết một bảng đại diện cho gì và hàng được xác định thế nào, bạn có thể dự đoán join sẽ làm gì, bản sao có ý nghĩa ra sao, và tại sao một vài bộ lọc thay đổi kết quả.
Trong các bài giảng của mình, Ullman thường dùng đại số quan hệ như một kiểu máy tính truy vấn: một tập nhỏ các toán tử (select, project, join, union, difference) mà bạn có thể kết hợp để diễn đạt điều mình muốn.
Tại sao điều này quan trọng khi làm việc với SQL: các cơ sở dữ liệu dịch SQL thành dạng đại số rồi viết lại nó thành một dạng tương đương khác. Hai truy vấn trông khác nhau có thể đại số là giống nhau—đó là cách các bộ tối ưu có thể thay đổi thứ tự join, đẩy filter xuống, hoặc loại bỏ công việc thừa trong khi vẫn giữ nguyên ý nghĩa.
SQL phần lớn là “muốn gì,” nhưng engine thường tối ưu bằng cách dùng đại số “làm như thế nào.”
Các dialect SQL khác nhau (Postgres vs. Snowflake vs. MySQL), nhưng nền tảng thì không đổi. Hiểu khóa, quan hệ, và tương đương đại số giúp bạn nhận ra khi truy vấn về mặt logic sai, khi nó chỉ chậm, và thay đổi nào giữ nguyên ý nghĩa qua nền tảng.
Đại số quan hệ là “toán học phía dưới” SQL: một tập nhỏ các toán tử mô tả kết quả bạn muốn. Công trình của Jeffrey Ullman giúp làm rõ cách nhìn này—và nó vẫn là mô hình tư duy mà hầu hết bộ tối ưu sử dụng.
Một truy vấn cơ sở dữ liệu có thể biểu diễn như một pipeline từ vài khối xây dựng:
WHERE trong SQL)SELECT col1, col2)JOIN ... ON ...)UNION)EXCEPT trong nhiều dialect)Vì tập này nhỏ, việc suy luận về tính đúng đắn trở nên dễ hơn: nếu hai biểu thức đại số tương đương, chúng trả cùng một bảng cho mọi trạng thái cơ sở dữ liệu hợp lệ.
Lấy một truy vấn quen thuộc:
SELECT c.name
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.total > 100;
Về mặt khái niệm, đây là:
bắt đầu với một join giữa customers và orders: customers ⋈ orders
select chỉ các orders trên 100: σ(o.total > 100)(...)
project cột bạn muốn: π(c.name)(...)
Đó không phải ký hiệu nội bộ chính xác của mọi engine, nhưng là ý tưởng đúng: SQL trở thành một cây toán tử.
Nhiều cây khác nhau có thể cho cùng kết quả. Ví dụ, các filter thường có thể được đẩy sớm hơn (áp dụng σ trước một join lớn), và các projection có thể loại bỏ cột không dùng sớm hơn (áp dụng π sớm hơn).
Những quy tắc tương đương đó cho phép cơ sở dữ liệu viết lại truy vấn thành một kế hoạch rẻ hơn mà không đổi ý nghĩa. Khi bạn nhìn truy vấn như đại số, “tối ưu hóa” không còn là phép màu mà trở thành biến dạng có quy tắc và an toàn.
Khi bạn viết SQL, cơ sở dữ liệu không chạy nó “như viết.” Nó dịch câu lệnh của bạn thành một kế hoạch truy vấn: biểu diễn có cấu trúc về công việc cần làm.
Mô hình tư duy tốt là cây các toán tử. Lá đọc bảng hoặc index; các node trong cây biến đổi và kết hợp hàng. Các toán tử phổ biến gồm scan, filter (selection), project, join, group/aggregate, và sort.
Các cơ sở dữ liệu thường tách lập kế hoạch thành hai lớp:
Ảnh hưởng của Ullman xuất hiện ở việc nhấn mạnh những biến đổi bảo toàn ý nghĩa: tái sắp xếp kế hoạch logic theo nhiều cách mà không đổi câu trả lời, rồi chọn chiến lược vật lý hiệu quả.
Trước khi chọn cách thực thi cuối cùng, bộ tối ưu áp dụng các quy tắc “dọn dẹp” đại số. Những rewrite này không đổi kết quả; chúng giảm công việc không cần thiết.
Ví dụ phổ biến:
Giả sử bạn muốn các orders của người dùng ở một quốc gia:
SELECT o.order_id, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'CA';
Một cách diễn giải ngây thơ có thể join tất cả users với tất cả orders rồi mới lọc Canada. Một rewrite bảo toàn ý nghĩa sẽ đẩy filter xuống để join chạm ít hàng hơn:
country = 'CA'order_id và totalVề mặt kế hoạch, bộ tối ưu cố gắng biến:
Join(Users, Orders) → Filter(country='CA') → Project(order_id,total)
thành gần giống:
Filter(country='CA') on Users → Join(with Orders) → Project(order_id,total)
Kết quả giống nhau. Công việc ít hơn.
Những rewrite này dễ bị bỏ qua vì bạn không gõ chúng—nhưng chúng là lý do lớn khiến cùng một SQL có thể chạy nhanh ở cơ sở dữ liệu này nhưng chậm ở cơ sở dữ liệu khác.
Khi bạn chạy một truy vấn SQL, cơ sở dữ liệu xem xét nhiều cách hợp lệ để lấy cùng một kết quả, rồi chọn cách mà nó ước tính là rẻ nhất. Quá trình quyết định này gọi là tối ưu hóa dựa trên chi phí—và đây là nơi lý thuyết kiểu Ullman xuất hiện rất thực tế trong hiệu năng hàng ngày.
Mô hình chi phí là hệ thống chấm điểm mà bộ tối ưu dùng để so sánh các kế hoạch thay thế. Hầu hết engine ước tính chi phí dựa trên vài nguồn lực chính:
Mô hình không cần hoàn hảo; nó cần đúng theo hướng đủ thường xuyên để chọn kế hoạch tốt.
Trước khi chấm điểm kế hoạch, bộ tối ưu hỏi ở mỗi bước: bước này sẽ cho ra bao nhiêu hàng? Đó là cardinality estimation.
Nếu bạn lọc WHERE country = 'CA', engine ước tính tỉ lệ hàng khớp. Nếu bạn join customers với orders, nó ước tính bao nhiêu cặp sẽ khớp trên khoá join. Những dự đoán số hàng này quyết định engine thích index scan hay full scan, hash join hay nested loop, hay sort sẽ nhỏ hay rất lớn.
Những ước tính của bộ tối ưu dựa trên thống kê: đếm, phân bố giá trị, tỉ lệ null, và đôi khi tương quan giữa các cột.
Khi stats lỗi thời hoặc thiếu, engine có thể đoán sai số hàng rất nhiều lần. Một kế hoạch trông rẻ trên giấy có thể trở nên đắt đỏ trong thực tế—triệu chứng kinh điển bao gồm chậm đột ngột sau khi dữ liệu tăng, thay đổi kế hoạch “ngẫu nhiên”, hoặc join bất ngờ phải spill ra đĩa.
Ước lượng tốt hơn thường đòi hỏi nhiều công sức hơn: thống kê chi tiết hơn, lấy mẫu, hoặc khám phá nhiều kế hoạch ứng viên. Nhưng việc lập kế hoạch cũng tốn thời gian, nhất là với truy vấn phức tạp.
Vì vậy bộ tối ưu cân bằng hai mục tiêu:
Hiểu đánh đổi này giúp bạn đọc EXPLAIN: bộ tối ưu không cố gắng “tỏ ra thông minh”—nó cố gắng đúng theo cách dự đoán được với thông tin hạn chế.
Công trình của Ullman giúp phổ biến một ý tưởng đơn giản nhưng mạnh: SQL không thật sự "chạy" mà được dịch thành một kế hoạch thực thi. Không đâu rõ điều đó hơn là ở join. Hai truy vấn trả cùng hàng có thể khác nhau rất nhiều về thời gian chạy tùy vào thuật toán join engine chọn—và thứ tự join.
Nested loop join đơn giản: với mỗi hàng bên trái, tìm hàng tương ứng bên phải. Nó nhanh khi bên trái nhỏ và bên phải có index hữu ích.
Hash join xây một bảng băm từ một input (thường là input nhỏ hơn) và dò bằng input kia. Nó mạnh cho các input lớn, không có thứ tự, với điều kiện đẳng thức (ví dụ A.id = B.id), nhưng cần bộ nhớ; spill-to-disk có thể xóa mất lợi thế.
Merge join duyệt hai input theo thứ tự đã sắp xếp. Nó phù hợp khi cả hai phía đã được sắp thứ tự (hoặc dễ sắp), như khi index trả hàng theo thứ tự khóa join.
Với ba bảng trở lên, số thứ tự join có thể nở ra rất nhiều. Nối hai bảng lớn trước có thể tạo ra một kết quả trung gian khổng lồ làm chậm mọi thứ. Thứ tự tốt thường bắt đầu với filter có tính chọn lọc cao (ít hàng nhất) và nối ra ngoài, giữ intermediates nhỏ.
Index không chỉ tăng tốc lookup—chúng làm cho một số chiến lược join khả thi. Một index trên khóa join có thể biến nested loop tốn kém thành pattern “seek cho mỗi hàng” nhanh. Ngược lại, thiếu hoặc index không dùng được có thể đẩy engine về hash joins hoặc sort lớn cho merge joins.
Cơ sở dữ liệu không chỉ “chạy SQL.” Chúng biên dịch nó. Ảnh hưởng của Ullman trải dài cả lý thuyết cơ sở dữ liệu và suy nghĩ về compiler, và kết nối đó giải thích tại sao engine truy vấn giống chuỗi công cụ ngôn ngữ lập trình: chúng dịch, viết lại, và tối ưu trước khi thực hiện bất kỳ công việc nào.
Khi bạn gửi một truy vấn, bước đầu giống front end của compiler. Engine tách token từ từ khóa và định danh, kiểm tra ngữ pháp, và xây một parse tree (thường được đơn giản thành abstract syntax tree). Đây là nơi lỗi cơ bản bị bắt: thiếu dấu phẩy, tên cột mơ hồ, quy tắc grouping không hợp lệ.
Một mô hình tư duy hữu ích: SQL là một ngôn ngữ lập trình mà “chương trình” mô tả quan hệ dữ liệu thay vì vòng lặp.
Compiler chuyển cú pháp thành một IR; cơ sở dữ liệu làm tương tự: dịch cú pháp SQL thành toán tử logic như:
GROUP BY)Dạng logic này gần với đại số quan hệ hơn là văn bản SQL, nên dễ suy nghĩ về ý nghĩa và tương đương.
Các tối ưu compiler giữ kết quả chương trình giống mà làm cho thực thi rẻ hơn. Bộ tối ưu cơ sở dữ liệu làm điều tương tự, dùng các hệ quy tắc như:
Đây là phiên bản cơ sở dữ liệu của “loại bỏ mã chết”: không phải kỹ thuật giống hệt, nhưng cùng triết lý—bảo toàn ngữ nghĩa, giảm chi phí.
Nếu truy vấn của bạn chậm, đừng chỉ nhìn SQL. Hãy xem kế hoạch truy vấn như bạn sẽ kiểm tra mã máy biên dịch. Kế hoạch cho bạn biết engine đã chọn gì: thứ tự join, dùng index, và nơi thời gian được tiêu tốn.
Bài học thực tế: học đọc EXPLAIN như một bản liệt kê assembly cho hiệu năng. Nó biến tinh chỉnh từ phỏng đoán thành debug dựa trên bằng chứng. For more on turning that into a habit, see /blog/practical-query-optimization-habits.
Hiệu năng truy vấn tốt thường bắt đầu trước khi bạn viết SQL. Lý thuyết thiết kế schema của Ullman (đặc biệt là chuẩn hóa) giúp cấu trúc dữ liệu để cơ sở dữ liệu giữ tính đúng đắn, dự đoán được, và hiệu quả khi nó lớn lên.
Chuẩn hóa nhằm:
Những lợi ích về đúng đắn đó dịch thành lợi ích hiệu năng sau này: ít trường trùng lặp, index nhỏ hơn, và ít cập nhật tốn kém.
Bạn không cần ghi nhớ các chứng minh để dùng ý tưởng:
Denormalize có thể là lựa chọn thông minh khi:
Chìa khóa là denormalize có chủ đích, với quy trình để giữ trùng lặp đồng bộ.
Thiết kế schema hình thành những gì bộ tối ưu có thể làm. Khóa và foreign key rõ ràng cho phép chiến lược join tốt hơn, rewrite an toàn hơn, và ước lượng số hàng chính xác hơn. Trong khi đó, trùng lặp quá mức có thể phình index và làm chậm ghi, và cột nhiều giá trị chặn các predicate hiệu quả. Khi dữ lượng tăng, quyết định mô hình hóa ban đầu thường quan trọng hơn việc tối ưu từng truy vấn nhỏ lẻ.
Khi một hệ thống “scale,” hiếm khi chỉ là thêm máy to hơn. Thường khó là cùng một ý nghĩa truy vấn phải được giữ nguyên trong khi engine chọn một chiến lược vật lý rất khác để giữ thời gian chạy dự đoán được. Sự nhấn mạnh của Ullman về các tương đương chính thức chính là điều cho phép những thay đổi chiến lược đó mà không đổi kết quả.
Ở kích thước nhỏ, nhiều kế hoạch “ổn.” Ở quy mô lớn, khác biệt giữa quét một bảng, dùng index, hoặc dùng kết quả đã tính trước có thể là khác biệt giữa vài giây và vài giờ. Phần lý thuyết quan trọng vì bộ tối ưu cần một tập quy tắc rewrite an toàn (ví dụ: đẩy filter sớm, sắp xếp lại join) mà không thay đổi đáp án—dù chúng thay đổi lớn công việc thực hiện.
Partitioning (theo ngày, khách hàng, vùng, v.v.) biến một bảng logic thành nhiều mảnh vật lý. Điều đó ảnh hưởng đến lập kế hoạch:
Văn bản SQL có thể không đổi, nhưng kế hoạch tốt nhất phụ thuộc vào nơi hàng nằm.
Materialized views về cơ bản là “biểu thức con đã lưu.” Nếu engine có thể chứng minh truy vấn của bạn khớp (hoặc viết lại để khớp) với một kết quả đã lưu, nó có thể thay thế công việc tốn kém—như join và aggregation lặp—bằng một lookup nhanh. Đây là tư duy đại số quan hệ trong thực tế: nhận diện tương đương rồi tái sử dụng.
Caching có thể tăng tốc đọc lặp, nhưng nó không cứu được truy vấn phải quét quá nhiều dữ liệu, shuffle intermediates khổng lồ, hoặc tính một join quá lớn. Khi vấn đề scale xuất hiện, lời giải thường là: giảm lượng dữ liệu cần chạm tới (bố cục/partitioning), giảm tính toán lặp (materialized views), hoặc thay đổi kế hoạch—chứ không chỉ “thêm cache.”
Ảnh hưởng của Ullman thể hiện qua một tâm thế đơn giản: coi một truy vấn chậm như một phát biểu ý định mà cơ sở dữ liệu có thể viết lại, rồi xác minh xem nó thực sự đã quyết định gì. Bạn không cần trở thành nhà lý thuyết để hưởng lợi—bạn chỉ cần một quy trình lặp lại.
Bắt đầu với những phần thường chiếm đa số thời gian chạy:
Nếu bạn chỉ làm một việc, xác định toán tử đầu tiên nơi số hàng bùng nổ. Đó thường là nguyên nhân gốc.
Những lỗi này dễ viết nhưng rất tốn kém:
WHERE LOWER(email) = ... có thể ngăn index dùng (dùng cột chuẩn hóa hoặc functional index nếu DB hỗ trợ).Đại số quan hệ khuyến khích hai bước thực tế:
WHERE trước join khi có thể để thu nhỏ input.Một giả thuyết tốt có thể là: “Join này đắt vì chúng tôi đang join quá nhiều hàng; nếu filter orders xuống 30 ngày gần nhất trước, input join giảm.”
Dùng quy tắc quyết định đơn giản:
EXPLAIN cho thấy công việc có thể tránh được (join thừa, lọc muộn, predicate không sargable).Mục tiêu không phải “SQL khôn ngoan.” Mà là kết quả trung gian dự đoán được nhỏ hơn—chính xác là dạng cải thiện bảo toàn tương đương mà ý tưởng Ullman giúp bạn nhận ra.
Những khái niệm này không chỉ dành cho DBA. Nếu bạn giao hàng một ứng dụng, bạn đang thực hiện quyết định về cơ sở dữ liệu và lập kế hoạch truy vấn dù không nhận ra: hình dạng schema, lựa chọn khóa, pattern truy vấn, và lớp truy cập dữ liệu đều ảnh hưởng tới những gì bộ tối ưu có thể làm.
Nếu bạn dùng workflow tạo nhanh (ví dụ sinh một app React + Go + PostgreSQL từ giao diện chat trong Koder.ai), các mô hình tư duy kiểu Ullman là mạng an toàn thực tế: bạn có thể xem lại schema được sinh để đảm bảo khóa và quan hệ rõ, kiểm tra các truy vấn app dựa vào, và kiểm chứng hiệu năng với EXPLAIN trước khi vấn đề xuất hiện ở production. Càng nhanh bạn lặp qua “ý định truy vấn → kế hoạch → sửa”, bạn càng thu được nhiều giá trị từ phát triển tăng tốc.
Bạn không cần "học lý thuyết" như một thú vui riêng. Cách nhanh nhất để hưởng lợi từ nền tảng kiểu Ullman là học vừa đủ để đọc kế hoạch truy vấn tự tin—rồi luyện tập trên chính cơ sở dữ liệu của bạn.
Tìm các sách và bài giảng này (không có liên kết—chỉ là điểm bắt đầu được trích dẫn rộng rãi):
Bắt đầu nhỏ và liên kết mỗi bước với thứ bạn quan sát được:
Chọn 2–3 truy vấn thực và lặp:
IN sang EXISTS, đẩy predicate trước, loại cột không cần, so sánh kết quả.Dùng ngôn ngữ rõ ràng, dựa trên kế hoạch:
Đó là lợi ích thực tế của nền tảng Ullman: bạn có một từ vựng chung để giải thích hiệu năng—không cần phỏng đoán.
Jeffrey Ullman đã giúp hình thành cách cơ sở dữ liệu biểu diễn ý nghĩa truy vấn và cách hệ thống có thể an toàn biến đổi truy vấn thành những dạng tương đương nhanh hơn. Nền tảng đó xuất hiện bất cứ khi nào engine viết lại truy vấn, sắp xếp lại các join, hoặc chọn một kế hoạch thực thi khác trong khi vẫn đảm bảo tập kết quả giống nhau.
Đại số quan hệ là một tập các toán tử nhỏ (select, project, join, union, difference) miêu tả chính xác kết quả truy vấn. Các engine thường chuyển SQL thành một cây toán tử giống đại số để áp dụng quy tắc tương đương (ví dụ: đẩy filter xuống trước) trước khi chọn chiến lược thực thi.
Bởi vì tối ưu hóa phụ thuộc vào việc chứng minh rằng truy vấn được viết lại vẫn trả về cùng kết quả. Các quy tắc tương đương cho phép bộ tối ưu làm những việc như:
WHERE trước joinNhững thay đổi này có thể giảm đáng kể khối lượng công việc mà không thay đổi ý nghĩa.
Kế hoạch logic mô tả cần tính toán gì (filter, join, aggregate) độc lập với chi tiết lưu trữ. Kế hoạch vật lý chọn cách chạy các phép đó (index scan vs full scan, hash join vs nested loop, phân luồng…). Hầu hết khác biệt hiệu năng đến từ lựa chọn vật lý, được hỗ trợ bởi những rewrite logic.
Tối ưu hóa theo chi phí đánh giá nhiều kế hoạch hợp lệ và chọn cái có chi phí ước tính thấp nhất. Chi phí thường do các yếu tố thực tế như số hàng xử lý, I/O, CPU và bộ nhớ (kể cả việc hash/sort bị tràn ra đĩa) quyết định.
Ước lượng lượng tử (cardinality estimation) là giả thiết của bộ tối ưu về “sẽ có bao nhiêu hàng ra khỏi bước này?” Những ước tính này quyết định thứ tự join, loại join, và liệu index scan có hợp lý hay không. Khi ước tính sai (thường do thống kê cũ/thiếu), bạn có thể gặp chậm đột ngột, spill lớn, hoặc thay đổi kế hoạch bất ngờ.
Tập trung vào một vài dấu hiệu quan trọng:
Hãy coi kế hoạch như mã máy đã biên dịch: nó cho biết engine thực sự đã quyết định làm gì.
Chuẩn hóa giảm trùng lặp dữ liệu và các bất thường khi cập nhật, dẫn đến bảng và index nhỏ hơn và join đáng tin cậy hơn. Denormalization có thể hợp lý cho analytics hoặc trường hợp đọc nhiều, nhưng phải có quy trình đồng bộ rõ ràng (refresh, chấp nhận trùng lặp có kiểm soát).
Khi scale, thường cần thay đổi chiến lược vật lý trong khi vẫn giữ ý nghĩa truy vấn. Các công cụ phổ biến:
Caching giúp đọc lặp nhưng không cứu nổi truy vấn cần quét quá nhiều dữ liệu hoặc sinh intermediates khổng lồ.