Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
Hi guys, let's get started.
Chào các bạn, chúng ta bắt đầu nhé.
For you in the class, a lot to cover, a lot to go over. Again, on the docket for you, hopefully everyone's well rested after getting project two completed last night.
Hôm nay lớp mình có rất nhiều nội dung cần đi qua. Trước hết, có một số thông báo cho các bạn, hy vọng mọi người đã nghỉ ngơi đầy đủ sau khi hoàn thành project hai tối qua.
Midterm exam, again, is still available, my office hours on Wednesdays, come take a look. If you want things regraded, take a photo and send it to me.
Bài thi giữa kỳ vẫn còn có thể xem lại, giờ tiếp sinh viên của tôi vào các thứ Tư, hãy đến xem nhé. Nếu muốn chấm lại, các bạn hãy chụp ảnh và gửi cho tôi.
Homework four will be due this Sunday coming up, on November 2nd. And then project three that came out last week, that'll be due on November 16th.
Bài tập về nhà bốn sẽ đến hạn vào Chủ nhật này, ngày 2 tháng 11. Còn project ba ra tuần trước thì hạn nộp là ngày 16 tháng 11.
And the recitation for that will be tomorrow night at 8 p.m. on Zoom. And it's been posted on Piazza for this. Any questions about homework four or project three?
Buổi thảo luận cho phần đó sẽ diễn ra tối mai lúc 8 giờ tối trên Zoom. Thông tin này đã được đăng trên Piazza. Có câu hỏi nào về bài tập bốn hay project ba không?
Yes, the question is what column is the leaderboard graded by? It should be the one on the far right. The last one, yeah.
Vâng, câu hỏi là bảng xếp hạng được chấm theo cột nào? Đó là cột ở ngoài cùng bên phải. Cột cuối cùng, đúng vậy.
It doesn't rank that by default, you click it like twice and it'll rank it. Other questions?
Mặc định nó không xếp hạng, bạn bấm vào khoảng hai lần là nó sẽ xếp hạng. Còn câu hỏi nào khác không?
All right, and again, if you can't get up the databases, today after class we'll have another seminar speaker. This will be the same guy that came, gave a talk in class about SingleStore.
Được rồi, và nhắc lại, nếu các bạn không thể khởi chạy được các cơ sở dữ liệu, thì hôm nay sau giờ học sẽ có thêm một diễn giả của buổi seminar. Đây là người đã đến nói chuyện trong lớp về SingleStore.
I think that day SingleStore got acquired by the private equity. So this is post private equity acquisition for those guys. So he's giving a talk to us at 4:30 after this class.
Tôi nhớ hôm đó SingleStore bị một quỹ đầu tư tư nhân mua lại. Vậy nên đây là thời điểm sau khi họ bị quỹ đầu tư tư nhân mua lại. Anh ấy sẽ nói chuyện với chúng ta lúc 4:30 sau giờ học này.
And a week from now, we'll have a senior alumni, distinguished alumni, Ryan Johnson, who did his PhD here before I came to CMU, did his PhD in databases.
Và một tuần nữa, chúng ta sẽ có một cựu sinh viên lâu năm, một cựu sinh viên xuất sắc, Ryan Johnson, người đã học tiến sĩ ở đây về cơ sở dữ liệu trước khi tôi đến CMU.
And now he's at Databricks working on Delta Lake. So he'll come talk about what Delta Lake does.
Và hiện anh ấy làm ở Databricks, phụ trách Delta Lake. Anh ấy sẽ đến nói về những gì Delta Lake làm.
It's in the same sort of family as the Iceberg, Hudi stuff that we've talked about so far in Delta Lake.
Nó thuộc cùng họ với Iceberg, Hudi mà chúng ta đã nói đến từ đầu đến giờ trong phần Delta Lake.
And then next week on Tuesday at the regular DataScript meeting at noon, we have somebody from Uber calling in to give a talk about how Uber uses Apache Pinot.
Và tuần sau, vào thứ Ba, trong buổi họp DataScript thường lệ lúc 12 giờ trưa, sẽ có một người từ Uber kết nối từ xa để nói về việc Uber sử dụng Apache Pinot như thế nào.
All right, so last class, all of last week, we were talking about how we are going to build the data system's runtime component, the query engine, the execution engine, to execute queries.
Được rồi, vậy buổi trước, cũng như cả tuần trước, chúng ta đã nói về cách xây dựng thành phần thời gian chạy của hệ quản trị dữ liệu, tức là query engine, execution engine, để thực thi các truy vấn.
And last class, in particular, we talked about how we want to design the system to support parallel queries.
Và đặc biệt ở buổi trước, chúng ta đã nói về cách thiết kế hệ thống để hỗ trợ các truy vấn song song.
We talked about these exchange operators, essentially these ways to coalesce results from multiple workers running at the same time that are working on different parts of a data set or different parts of a query plan at the same time.
Chúng ta đã nói về các toán tử exchange, về cơ bản là những cách để gộp kết quả từ nhiều worker chạy cùng một lúc, đang xử lý các phần khác nhau của một tập dữ liệu hoặc các phần khác nhau của một kế hoạch truy vấn cùng lúc.
And we put them all together and produce a final result. And so the key thing that we were talking about during this process was that there is this query plan that was being generated.
Rồi ta ghép tất cả lại và tạo ra kết quả cuối cùng. Và điểm mấu chốt mà chúng ta đã nói trong quá trình này là có một kế hoạch truy vấn đang được sinh ra.
We didn't say how, but there's this query plan that had these physical operators that were defining how we run access tables, how we're going to compute joins, and do any other algorithms we talked about so far.
Chúng ta chưa nói là bằng cách nào, nhưng có một kế hoạch truy vấn gồm các toán tử vật lý xác định cách chúng ta truy cập các bảng, cách chúng ta tính các phép nối, và thực hiện mọi thuật toán khác mà chúng ta đã nói đến từ đầu đến giờ.
And so we've been very hand-wavy throughout the entire semester about, OK, how do we get one of these query plans? And so that's what today is all about for this week.
Và vì vậy, suốt cả học kỳ chúng ta đã nói khá chung chung về việc, Vậy làm thế nào để có được một query plan như thế này? Và đó chính là nội dung của buổi hôm nay trong tuần này.
How do we take a SQL query from an application or from somebody who wants to run a query, and how do we produce that into a query plan that we can then execute using all the components in our system that we've designed so far?
Làm thế nào để lấy một truy vấn SQL từ một ứng dụng hoặc từ một người nào đó muốn chạy truy vấn, rồi biến nó thành một query plan mà chúng ta có thể thực thi bằng tất cả các thành phần của hệ thống mà chúng ta đã thiết kế cho đến giờ?
And obviously, I'm going to focus on SQL because that's the default language or de facto standard for querying tables in a relational model.
Và dĩ nhiên, tôi sẽ tập trung vào SQL vì đó là ngôn ngữ mặc định hay chuẩn de facto để truy vấn các bảng trong mô hình quan hệ.
The same concepts and techniques that we'll be talking about today are applicable for whatever other query language you may want to use.
Những khái niệm và kỹ thuật tương tự mà chúng ta sẽ nói đến hôm nay đều áp dụng được cho bất kỳ ngôn ngữ truy vấn nào khác mà các bạn muốn dùng.
So again, the high-level path of what we're going through now is that we have our application that is written in PHP, Java, Rust, whatever. It doesn't matter.
Vậy nhắc lại, đường đi ở mức tổng quan của những gì chúng ta đang xem xét là: ta có một ứng dụng được viết bằng PHP, Java, Rust, gì cũng được. Điều đó không quan trọng.
And they're going to connect to our database system, and they're going to send us a SQL query. And the first step along this process is that we have to parse the SQL query, right?
Ứng dụng sẽ kết nối đến hệ quản trị cơ sở dữ liệu của chúng ta, và gửi cho chúng ta một truy vấn SQL. Và bước đầu tiên trong quá trình này là chúng ta phải phân tích cú pháp (parse) truy vấn SQL, đúng không?
You know, classic compiler class, you know, pick your favorite parsing library or tokenizer, whatever.
Bạn biết đấy, giống môn trình biên dịch kinh điển, cứ chọn thư viện phân tích cú pháp hay tokenizer mà bạn thích.
Like, we'll parse the tokens, and we'll generate what's called an abstract syntax tree, which is just a tree structure that's going to say things like, there is a scan on some table that has a name, right?
Chúng ta sẽ phân tích các token, và tạo ra cái gọi là cây cú pháp trừu tượng (abstract syntax tree), đó chỉ là một cấu trúc cây cho biết những điều như: có một thao tác quét trên một bảng nào đó có tên như thế, đúng không?
There's a bunch of strings, because that's defined what's in the SQL query.
Ở đây có một loạt chuỗi, vì đó là những gì được xác định trong truy vấn SQL.
So then this abstract syntax tree is passed into a binder, and that's responsible for now resolving all those string identifiers that are in our SQL query, like table names, column names, things like that, or function names, of course, right?
Sau đó cây cú pháp trừu tượng này được chuyển vào binder, và binder chịu trách nhiệm phân giải tất cả các định danh dạng chuỗi có trong truy vấn SQL của chúng ta, như tên bảng, tên cột và những thứ tương tự, hoặc tất nhiên là cả tên hàm nữa.
And it's going to consult the catalog that's going to have all this information about what these different database objects we have in our system.
Và nó sẽ tra cứu catalog, nơi chứa toàn bộ thông tin về các đối tượng cơ sở dữ liệu khác nhau có trong hệ thống của chúng ta.
And it's basically going to do this mapping from a name to an internal ID, like an object ID. In Postgres, they're called OIDs, right?
Về cơ bản nó sẽ ánh xạ từ một cái tên sang một ID nội bộ, tức là một object ID. Trong Postgres, chúng được gọi là OID, đúng không?
And we have to do this, because if someone says select star from table blah, and we don't have a table blah, we want to throw an error, right?
Và chúng ta phải làm vậy, vì nếu ai đó viết select star from table blah, mà chúng ta không có bảng blah nào, thì ta muốn báo lỗi, đúng không?
And so that's what the binder's responsible for doing. Binders are super complicated, because it's easy if it's like select star from table foo, right? That's easy.
Và đó là việc mà binder chịu trách nhiệm. Binder cực kỳ phức tạp, vì nếu chỉ là select star from table foo thì rất dễ, đúng không? Cái đó dễ.
It's when you start having nested queries and duplicate names or joins on the same table with itself. That's when the binder gets kind of nasty.
Khó là khi bắt đầu có các truy vấn lồng nhau và tên trùng lặp hoặc phép nối một bảng với chính nó. Đó là lúc binder trở nên khá rắc rối.
You know, we could spend a whole semester on this or not.
Chúng ta có thể dành cả một học kỳ cho phần này, hoặc không.
But assume that something knows how to take string tokens for table name objects or column names and map it to an internal ID.
Nhưng hãy giả định rằng có một thành phần biết cách lấy các token chuỗi là tên đối tượng bảng hoặc tên cột và ánh xạ chúng sang một ID nội bộ.
And then at that point, we know like the type or the schema or whatever the thing that they're accessing.
Và đến lúc đó, chúng ta biết kiểu dữ liệu hay lược đồ, hay bất cứ thứ gì của đối tượng mà họ đang truy cập.
And then once we do this binding, Now we have what is called a logical plan.
Và khi đã thực hiện xong bước binding này, ta có cái gọi là kế hoạch logic (logical plan).
So now we have something that says, I want to access table foo, and I want to do an aggregation on it. I want to do a sorting on this column, right?
Lúc này ta có một thứ nói rằng: tôi muốn truy cập bảng foo, và tôi muốn thực hiện một phép tổng hợp trên đó. Tôi muốn sắp xếp theo cột này, đúng không?
It's a high level definition of what the query wants to do without defining exactly how to do it or how to actually execute it.
Đó là định nghĩa ở mức cao về việc truy vấn muốn làm gì, mà không xác định chính xác làm như thế nào hay thực thi thực sự ra sao.
And then we take that logical plan, pass it into our optimizer, and this is now responsible for looking at the schema to figure out what are the objects that this thing's trying to access.
Sau đó ta lấy kế hoạch logic này và chuyển vào bộ tối ưu hóa (optimizer), và bộ này có nhiệm vụ xem xét schema để xác định những đối tượng mà truy vấn này đang cố truy cập là gì.
Consulting a cost model says, all right, for these different options that I have to execute this query, which one's actually better?
Nó tham khảo một mô hình chi phí (cost model) và nói: được rồi, trong các lựa chọn khác nhau để thực thi truy vấn này, lựa chọn nào thực sự tốt hơn?
And this cost model could be fed using statistics that are collected in the catalog.
Mô hình chi phí này có thể được cung cấp dữ liệu bằng các thống kê được thu thập trong catalog.
Could have its own magic constants in them to define whether a scan is faster, or a sequential scan is faster than the index scan or whatever, right?
Nó cũng có thể có các hằng số "ma thuật" riêng để xác định liệu một lần quét nhanh hơn, hay quét tuần tự nhanh hơn quét chỉ mục (index scan), hay điều gì đó tương tự, đúng không?
There's some, the cost model is allowed to judge whether one plan is going to be better than another, given a bunch of alternatives.
Mô hình chi phí được phép đánh giá xem kế hoạch nào tốt hơn kế hoạch nào, khi có nhiều phương án thay thế.
And then voila, the optimizer says, OK, well, I crunched on this. Here's the best physical plan that I could find for this query.
Và rồi, bộ tối ưu hóa nói: được rồi, tôi đã tính toán xong. Đây là kế hoạch vật lý (physical plan) tốt nhất mà tôi tìm được cho truy vấn này.
And then we can then pass that off now to the query engine we just discussed last class to go ahead and schedule this for execution.
Sau đó ta chuyển nó cho query engine mà ta vừa thảo luận ở buổi trước để lên lịch thực thi.
So today's class, we're going to focus on the optimizer box here. Next class, we'll focus on the cost model box up above. And obviously, it's symbiotic.
Vậy buổi hôm nay ta sẽ tập trung vào khối optimizer này. Buổi sau, ta sẽ tập trung vào khối cost model ở phía trên. Và rõ ràng là chúng cộng sinh với nhau.
You need one, you know, the optimizer doesn't always need a cost model, but a lot of the methods we'll talk about today do. But you need some way to say this is actually better.
Bạn cần một cái, bộ tối ưu hóa không phải lúc nào cũng cần mô hình chi phí, nhưng nhiều phương pháp ta nói hôm nay thì cần. Nhưng bạn cần một cách nào đó để nói rằng cái này thực sự tốt hơn.
Ideally, you want to be able to say this alternative plan is better than another plan, right?
Lý tưởng nhất là bạn có thể nói rằng phương án này tốt hơn một kế hoạch khác, đúng không?
So this is the path we're going on, and we're focusing on the optimizer piece and the cost model. Like I said, the binder and parser, It's just a bunch of engineering.
Đây là con đường ta đang đi, và ta tập trung vào phần optimizer và cost model. Như tôi đã nói, binder và parser chỉ là một đống công việc kỹ thuật.
It's painful, especially the binder. But we can use stuff off the shelf if necessary.
Nó rất vất vả, nhất là binder. Nhưng nếu cần ta có thể dùng đồ có sẵn.
All right, so let's look at an example of what we're trying to, you know, look at actually a query and see how we're going to do this.
Được rồi, hãy xem một ví dụ về điều ta đang cố làm, xem một truy vấn thực tế và xem ta sẽ làm việc này như thế nào.
So say we have now a simple query like this. We're doing a join against the employee table with the department table.
Giả sử ta có một truy vấn đơn giản như thế này. Ta đang thực hiện phép join bảng employee với bảng department.
We're going to find everyone who's in the toy department, and we want to get all the unique names, right?
Ta sẽ tìm tất cả những người thuộc phòng đồ chơi (toy), và ta muốn lấy tất cả các tên duy nhất, đúng không?
And say that in our data system, we always have this catalog that keeps track of all the different tables that I have. What are the primary keys? What indexes do I have?
Và giả sử trong hệ quản trị dữ liệu của ta luôn có catalog này theo dõi tất cả các bảng mà ta có. Khóa chính là gì? Ta có những chỉ mục nào?
And whether they're clustered or unclustered on those keys.
Và chúng là clustered hay unclustered trên các khóa đó.
And then I'll have some basic information that says I have, in the case of the employee table, I have 10,000 tuples or 10,000 records split across 1,000 pages.
Rồi ta sẽ có một số thông tin cơ bản cho biết ta có, trong trường hợp bảng employee, 10.000 tuple hay 10.000 bản ghi được chia trên 1.000 trang.
And for department, there's 500 records split across 50 pages, right? This is like kind of the bare minimum. Well, the bare minimum is you have nothing, right?
Còn với department, có 500 bản ghi chia trên 50 trang, đúng không? Đây chỉ là mức tối thiểu. Thật ra thì mức tối thiểu là bạn không có gì cả, đúng không?
But that's more the lake house data lake stuff. We can ignore that.
Nhưng đó là chuyện của lake house, data lake hơn. Ta có thể bỏ qua.
But if there's the bare minimum you need, you obviously need to know the schema because you need to know what, you know, if the query says I want to read table employee, that's what the schema actually is.
Nhưng nếu nói về mức tối thiểu bạn cần, thì rõ ràng bạn cần biết schema, vì bạn cần biết nếu truy vấn nói tôi muốn đọc bảng employee, thì schema thực sự của nó là gì.
Not always, but for our class here, we assume that's the case. And then we need to know, obviously, what indexes we have available to us.
Không phải lúc nào cũng vậy, nhưng trong lớp này ta giả định là như thế. Và rõ ràng ta cũng cần biết mình có những chỉ mục (index) nào để dùng.
So if you just sort of take almost a little transcription or mapping of the SQL query and convert it to relational algebra, you end up with something like this, right?
Vậy nếu bạn lấy gần như một bản chuyển đổi trực tiếp hay ánh xạ của truy vấn SQL sang đại số quan hệ, bạn sẽ có một thứ như thế này, đúng không?
You have scans on employee and department. Now I'm going to do a cross join. And then everything that I have in either my where clause, my on clause, right, those are just filters.
Bạn có các phép quét trên employee và department. Giờ tôi sẽ thực hiện một cross join. Và mọi thứ có trong mệnh đề where hoặc mệnh đề on của tôi, đúng không, đó chỉ là các bộ lọc.
And then I have the projection at the top, Right? So let's say we build a sort of a naive implementation of a database system.
Và rồi ở trên cùng tôi có phép chiếu, đúng không? Giả sử ta xây dựng một bản cài đặt ngây thơ (naive) của một hệ cơ sở dữ liệu.
And at the leaf nodes of this query plan, we're going to read the employee table, all 5,000 records.
Và ở các nút lá của kế hoạch truy vấn này, ta sẽ đọc bảng employee, toàn bộ 5.000 bản ghi.
And then we're going to read the rights table, all 500 records.
Rồi ta đọc bảng rights, toàn bộ 500 bản ghi.
And then what we're going to do is, when we do the, we're just going to scan them in and write them out to like a temp file, like something really, really basic.
Rồi điều ta sẽ làm là, khi ta thực hiện, ta chỉ quét chúng vào rồi ghi ra một tệp tạm, một thứ thật sự rất cơ bản.
And then now once we have all that data prepared, we can then do the join. I'm sorry, after we do the Cartesian join, the Cartesian product, then we now start doing the filtering.
Và khi đã chuẩn bị xong toàn bộ dữ liệu đó, ta có thể thực hiện phép join. Xin lỗi, sau khi ta thực hiện phép join Descartes, tức tích Descartes, thì bây giờ ta bắt đầu lọc.
So again, this is just bottom here, we're just matching up all the tuples of employees, all the tuples of the department.
Vậy một lần nữa, ở dưới cùng này, ta chỉ ghép tất cả các tuple của employee với tất cả các tuple của department.
Then we now do the filter to start throwing away tuples that aren't, where there isn't a match on the department ID and the employee department ID.
Rồi ta thực hiện bộ lọc để bắt đầu loại bỏ các tuple mà không có sự khớp giữa ID của department và ID department của employee.
And same thing, now we're going to suck in all the tuples we wrote out in temp table, temp file one, read those back in, and then produce a new temp file two, T2, that has the result of this join.
Và tương tự, bây giờ ta sẽ nạp vào tất cả các tuple mà ta đã ghi ra bảng tạm, tệp tạm một, đọc chúng lại, rồi tạo ra một tệp tạm mới là hai, T2, chứa kết quả của phép join này.
We then pass this up to the next filter operator, read all the data in, do the filter, write it all out. And then we end up with our final projection at the top.
Sau đó ta chuyển nó lên toán tử lọc tiếp theo, đọc toàn bộ dữ liệu vào, lọc, rồi ghi hết ra. Và cuối cùng ta có phép chiếu ở trên cùng.
We do four reads in, one write out to produce the final result. So for this naive plan, because you never want to do a cross join, right?
Ta thực hiện bốn lần đọc vào, một lần ghi ra để tạo kết quả cuối cùng. Vậy với kế hoạch ngây thơ này, vì bạn không bao giờ muốn dùng cross join, đúng không?
If we just executed almost, again, a literal translation of what the SQL query defines for us, right? Map it to relational algebra, we're doing 2 million IOs.
Nếu ta chỉ thực thi gần như là, một bản dịch theo nghĩa đen những gì truy vấn SQL định nghĩa cho ta, đúng không? Ánh xạ nó sang đại số quan hệ, ta phải thực hiện 2 triệu lần IO.
We can start doing all the tricks we talked about throughout the entire semester to reduce this, reduce the amount of IO we're doing, but just being more intelligent and more efficient in the operators we're going to choose when we execute this query.
Ta có thể bắt đầu áp dụng mọi mẹo mà ta đã nói đến trong suốt học kỳ để giảm con số này, giảm lượng IO mà ta thực hiện, chỉ bằng cách thông minh hơn và hiệu quả hơn trong việc chọn các toán tử mà ta sẽ dùng khi thực thi truy vấn này.
So for example, if I get rid of that cross join and now I do an inner join, so as I'm scanning the table, I can just do the join rather than having to materialize everything out in the cross join, right?
Ví dụ, nếu tôi bỏ cross join đó đi và bây giờ dùng inner join, nên khi đang quét bảng, tôi có thể thực hiện phép join ngay, thay vì phải materialize toàn bộ kết quả của cross join, đúng không?
And now I've got to start making a decision of what my join algorithm should be.
Và bây giờ tôi phải bắt đầu đưa ra quyết định về việc thuật toán join của mình nên là gì.
So if I just do a block nested loop join or page nested loop join, I'm still going to write things out to a temp file.
Nếu tôi chỉ dùng block nested loop join hoặc page nested loop join, thì tôi vẫn sẽ ghi dữ liệu ra một tệp tạm.
But now I'm not writing out the cross product of all combinations of all tuples from the left and the right side. I'm actually doing the matching as I'm going along.
Nhưng giờ tôi không ghi ra tích Descartes của mọi tổ hợp của tất cả các tuple từ phía trái và phía phải. Tôi thực sự thực hiện việc so khớp ngay trong lúc duyệt.
And then now in the next phase, when I do this additional filter here to throw out anybody that's not in the toy department, I'm reading less data in.
Và sau đó, ở giai đoạn tiếp theo, khi tôi thực hiện bộ lọc bổ sung này để loại bỏ những ai không thuộc phòng ban đồ chơi, thì tôi đọc vào ít dữ liệu hơn.
And now, again, writing the same amount of data out. And so the end projection is still the same.
Và một lần nữa, lượng dữ liệu ghi ra vẫn như cũ. Vì vậy phép chiếu cuối cùng vẫn giữ nguyên.
So now we got it down to 54,000 IOs from 2 million by choosing a better plan. Can we do better? Of course, right?
Như vậy, nhờ chọn một kế hoạch tốt hơn, ta đã giảm từ 2 triệu xuống còn 54,000 IO. Ta có thể làm tốt hơn không? Tất nhiên rồi, đúng không?
It's all the tricks that we learned throughout the entire semester, right? So if I just take this and I replace the nested loop join with a sort-merge join, right?
Đó là tất cả các mẹo mà ta đã học trong suốt cả học kỳ, đúng không? Nếu tôi lấy cái này và thay nested loop join bằng sort-merge join, đúng không?
Assuming I have 50 buffers, I can now write out less data for this phase. And I can reduce the total amount of IOs even further. Now we get it down to 7,000.
Giả sử tôi có 50 buffer, thì tôi có thể ghi ra ít dữ liệu hơn ở giai đoạn này. Và tôi có thể giảm tổng số IO xuống nữa. Bây giờ ta giảm xuống còn 7,000.
But again, in this example here, because I'm taking all the results of the scan from this and this and the join and then writing it out, all the tuples out to a file.
Nhưng một lần nữa, trong ví dụ này, vì tôi lấy toàn bộ kết quả của phép quét từ bảng này và bảng này cùng với phép join rồi ghi ra, ghi tất cả các tuple ra một tệp.
And then once that file is written, then start the next operator to read it all back in. That's the materialization model that we talked about last class, which we said is very inefficient.
Và sau khi tệp đó được ghi xong, thì mới bắt đầu toán tử tiếp theo để đọc lại toàn bộ. Đó là mô hình materialization mà ta đã nói ở buổi trước, và ta đã nói rằng nó rất kém hiệu quả.
If you're reading a lot of data or passing a lot of data from one operator to the next, Because there's no pipelining of this.
Nếu bạn đọc nhiều dữ liệu hoặc chuyển nhiều dữ liệu từ toán tử này sang toán tử kế tiếp. Vì ở đây không có pipelining.
So if we switch to the vectorization model, we can get rid of all of these additional writes and reads back in for these temp files and just pipeline all the tuples up.
Vì vậy nếu ta chuyển sang mô hình vectorization, ta có thể loại bỏ tất cả các lần ghi bổ sung và đọc lại các tệp tạm này, và chỉ cần đẩy các tuple lên theo đường ống.
And now we get it down to 3,000 IOs. Can we do even better than this?
Và bây giờ ta giảm xuống còn 3,000 IO. Ta có thể làm tốt hơn nữa không?
Yeah, push down filter. There's one more optimization we can do. Remember the joins, we said it matters whether the largest table is on the right-hand side or the left-hand side.
Đúng, đẩy bộ lọc xuống. Còn một tối ưu hóa nữa ta có thể làm. Hãy nhớ về các phép join, ta đã nói rằng việc bảng lớn nhất nằm ở phía phải hay phía trái là quan trọng.
So in this case here, we can do what he proposed: push down the filter and now swap the order of the employees table and department table, and push down the filter below the join like this.
Vậy trong trường hợp này, ta có thể làm như bạn ấy đề xuất: đẩy bộ lọc xuống và đổi thứ tự của bảng employees và bảng department, rồi đẩy bộ lọc xuống dưới phép join như thế này.
And now the query is going to be more efficient. Now we can get it down to just three reads and one write, because we knew an index lookup on the name.
Và bây giờ truy vấn sẽ hiệu quả hơn. Bây giờ ta có thể giảm xuống chỉ còn ba lần đọc và một lần ghi, vì ta biết có thể tra cứu chỉ mục theo name.
Then we knew index nested loop join instead of the sort-merge join. And now we're only reading 37 IOs. We're doing 37 IOs for this one query.
Khi đó ta dùng index nested loop join thay vì sort-merge join. Và bây giờ chúng ta chỉ đọc 37 IO. Chúng ta tốn 37 IO cho truy vấn này.
The question is, how do I decide which one to be in the left or the right? In this example here, because I had the index on the department name, there's only 500 records.
Câu hỏi là, làm sao tôi quyết định bảng nào nằm bên trái hay bên phải? Trong ví dụ này, vì tôi có chỉ mục trên tên phòng ban, nên chỉ có 500 bản ghi.
I mean, hand-waving how we determine the selectivity of this predicate here, that's next class. But you would look and say, all right, well, I only have 500 records and there's 100 departments.
Ý tôi là, tạm bỏ qua việc chúng ta xác định độ chọn lọc của vị từ này như thế nào, việc đó để buổi sau. Nhưng bạn sẽ nhìn vào và nói, được rồi, tôi chỉ có 500 bản ghi và có 100 phòng ban.
So therefore, I'm going to have some distribution information to say, it's not one department has everybody.
Vì vậy, tôi sẽ có một số thông tin về phân phối để cho biết rằng không phải một phòng ban nào đó chứa tất cả mọi người.
And I know I would want to choose this index, because now I can just go get the small number of tuples that are coming out of this.
Và tôi biết mình sẽ muốn chọn chỉ mục này, vì bây giờ tôi chỉ cần đi lấy một số ít tuple được trả ra từ đó.
And then now when I do my join, it's way more efficient, because now I'm just probing on the other side.
Rồi khi thực hiện phép join, nó hiệu quả hơn nhiều, vì lúc này tôi chỉ việc dò tìm ở phía bên kia.
What's that? It's a question: do I need additional IO to go fetch the statistics? Yes, I'm ignoring that.
Gì vậy? Câu hỏi là: có cần thêm IO để lấy các thống kê không? Có, tôi đang bỏ qua điều đó.
Right, it'd be, typically that would stay in memory, because it's much smaller than the actual data. The way you actually implement the statistics is just another table.
Thông thường những thống kê đó sẽ nằm trong bộ nhớ, vì chúng nhỏ hơn nhiều so với dữ liệu thực. Cách bạn cài đặt thống kê thực ra chỉ là một bảng khác.
So yeah, there is IO. There's locking stuff, which I haven't talked about. That's next week. There is additional overhead of going and getting those statistics. But for our purposes here, we're ignoring all that.
Vậy nên đúng, có IO. Còn có chuyện khóa nữa, mà tôi chưa nói tới. Cái đó để tuần sau. Có thêm chi phí phụ để đi lấy những thống kê đó. Nhưng với mục đích của chúng ta ở đây, ta bỏ qua tất cả những điều đó.
All right, so we can kind of see we did a couple of things here. We did a bunch of optimizations where we moved things down. We changed the physical ordering of different operations.
Được rồi, vậy ta có thể thấy ta đã làm vài việc ở đây. Ta đã thực hiện một loạt tối ưu hóa, đẩy các thao tác xuống thấp hơn. Ta đã thay đổi thứ tự vật lý của các phép toán khác nhau.
We changed the order of whether a department employee is on the right or left-hand side of the join. So there's a bunch of these tricks here.
Ta đã thay đổi việc department hay employee nằm ở bên phải hay bên trái của phép join. Vậy có cả một loạt mánh như thế ở đây.
And this is what the optimizer is going to do.
Và đây chính là việc mà bộ tối ưu hóa sẽ làm.
So anytime you open up SQLite, or DuckDB, or Postgres from your terminal, and you write a SQL query in it, it's going to run some variation of these algorithms we'll talk about today to produce a physical plan that it actually can execute.
Vì vậy, bất cứ khi nào bạn mở SQLite, DuckDB hay Postgres từ terminal, và viết một truy vấn SQL trong đó, nó sẽ chạy một biến thể nào đó của các thuật toán mà chúng ta sẽ nói đến hôm nay để tạo ra một kế hoạch vật lý mà nó thực sự có thể thực thi.
Then it runs your query. It's doing this in real time as you hit Enter and run a query. In the case of homework one, the query is going to run, say, for 10 milliseconds.
Sau đó nó mới chạy truy vấn của bạn. Nó làm việc này theo thời gian thực ngay khi bạn nhấn Enter để chạy truy vấn. Trong bài tập về nhà 1, truy vấn sẽ chạy chẳng hạn 10 mili giây.
It'll spend maybe a millisecond, for simple queries, to run all this optimization stuff, then produce a result. And as a human, it appears almost instantaneous. For more complex queries, it's not instantaneous.
Với các truy vấn đơn giản, nó có thể mất khoảng một mili giây để chạy toàn bộ phần tối ưu hóa này, rồi mới tạo ra kết quả. Và với con người, nó gần như tức thì. Với các truy vấn phức tạp hơn, nó không tức thì.
We'll talk about how we decide when to terminate. But this is all going to happen when you hit Enter or when you set up a query.
Chúng ta sẽ nói về cách quyết định khi nào dừng. Nhưng tất cả điều này sẽ xảy ra khi bạn nhấn Enter hoặc khi bạn thiết lập một truy vấn.
The DBMS is going to do all this and then run the query, which, to me, I find fascinating. All right.
DBMS sẽ làm tất cả những việc này rồi mới chạy truy vấn, điều mà theo tôi thì rất thú vị. Được rồi.
So today we're going to talk about the background of query optimization in a little bit more detail than what we've talked about so far.
Vậy hôm nay chúng ta sẽ nói về nền tảng của tối ưu hóa truy vấn chi tiết hơn một chút so với những gì đã nói đến giờ.
Then we'll spend time talking about how we're going to do transformations or enumerations of different possible query alternatives, or query plan alternatives, we have for a given query.
Sau đó chúng ta sẽ dành thời gian nói về cách thực hiện các phép biến đổi hay các phương án liệt kê khác nhau có thể có của truy vấn, hay các phương án kế hoạch truy vấn mà ta có cho một truy vấn cho trước.
Then we'll talk about the two basic high-level categories for query optimization. There's heuristics and rule-based, where you're applying the transformation rules without a cost model.
Sau đó chúng ta sẽ nói về hai loại tối ưu hóa truy vấn cơ bản ở mức cao. Có heuristic và dựa trên luật (rule-based), trong đó bạn áp dụng các luật biến đổi mà không có mô hình chi phí.
And then there'll be the cost-based search, and there'll be two variations of that. So most new database systems, when they first come online, they'll build a heuristic-based, rule-based optimizer.
Và sau đó là tìm kiếm dựa trên chi phí, và sẽ có hai biến thể của nó. Hầu hết các hệ cơ sở dữ liệu mới, khi mới ra đời, sẽ xây dựng một bộ tối ưu hóa dựa trên heuristic, dựa trên luật.
And then later on, they'll get more sophisticated as the project grows and becomes more popular. Then they'll switch over to a cost-based one.
Và về sau, chúng sẽ trở nên tinh vi hơn khi dự án lớn lên và phổ biến hơn. Khi đó chúng sẽ chuyển sang bộ tối ưu hóa dựa trên chi phí.
You need the rules first to do the cost-based. We'll see why as we go along. All right. So what are we doing here at high level?
Bạn cần có các luật trước để làm dựa trên chi phí. Chúng ta sẽ thấy lý do dần dần. Được rồi. Vậy ở mức cao, ở đây chúng ta đang làm gì?
So again, given a query's logical plan that we get from the binder, because it's mapped the names of tables and columns to actual object identifiers in the catalog, the optimizer is responsible for generating a bunch of different alternative plans to execute.
Một lần nữa, cho trước kế hoạch logic của một truy vấn mà ta nhận được từ binder, vì nó đã ánh xạ tên các bảng và cột sang các định danh đối tượng thực trong catalog, bộ tối ưu hóa chịu trách nhiệm sinh ra một loạt các kế hoạch thực thi thay thế khác nhau.
And those alternatives could be, at least initially, other logical plans. But in the end, we've got to produce a physical execution plan that our engine can actually run.
Và những phương án đó, ít nhất ban đầu, có thể là các kế hoạch logic khác. Nhưng cuối cùng, ta phải tạo ra một kế hoạch thực thi vật lý mà engine của chúng ta thực sự chạy được.
So it's not enough to say, I want to join table A and table B.
Vì vậy, chỉ nói "tôi muốn nối bảng A và bảng B" là chưa đủ.
I have to know, I'm going to do a hash join on table A and B, or I'm going to do a sort-merge join on table A and B.
Tôi phải biết là mình sẽ dùng hash join cho bảng A và B, hay sẽ dùng sort-merge join cho bảng A và B.
That's the physical plan. I need to know what that is in order to actually execute anything.
Đó là kế hoạch vật lý. Tôi cần biết điều đó thì mới thực thi được bất cứ thứ gì.
And the key thing is that whenever we generate these alternative plans, it's absolutely critical that whatever plan we generate is equivalent to whatever the original query was, or whatever the original logical plan that we were given.
Và điều mấu chốt là mỗi khi sinh ra các kế hoạch thay thế này, điều tối quan trọng là bất kỳ kế hoạch nào ta sinh ra cũng phải tương đương với truy vấn ban đầu, hoặc với kế hoạch logic ban đầu mà ta được cung cấp.
It doesn't matter that we produce a really fast plan if it produces incorrect results, because what's the whole point of doing any of this optimization?
Việc ta tạo ra một kế hoạch rất nhanh là vô nghĩa nếu nó cho kết quả sai, vì mục đích của toàn bộ việc tối ưu hóa này là gì chứ?
It might as well just return 1 or null, right? And no one's going to care. So we'll see as we go along.
Khi đó cứ trả về 1 hoặc null cũng được, đúng không? Và sẽ chẳng ai quan tâm. Chúng ta sẽ thấy dần dần.
These transformation rules that we'll talk about, they're going to be set up so that when I permute the plan and start making changes to things, I have to be guaranteed that the output of that transformation process is a plan that's still correct.
Các luật biến đổi mà chúng ta sẽ nói tới được thiết lập sao cho khi tôi hoán vị kế hoạch và bắt đầu thay đổi các thành phần, tôi phải được đảm bảo rằng kết quả đầu ra của quá trình biến đổi đó là một kế hoạch vẫn đúng.
So this will be very complicated to do. Just picking the right join order, the joins for a query plan, is shown to be NP-hard.
Vì vậy việc này sẽ rất phức tạp. Chỉ riêng việc chọn đúng thứ tự nối, các phép nối của một kế hoạch truy vấn, đã được chứng minh là NP-hard.
So the search space for the possible queries that we may have to deal with is quite large. Now, most queries aren't joining a lot of tables. Most are joining one table.
Vì vậy không gian tìm kiếm các truy vấn khả dĩ mà ta có thể phải xử lý là khá lớn. Tuy nhiên, hầu hết các truy vấn không nối nhiều bảng. Hầu hết chỉ dùng một bảng.
Sorry, most queries don't have joins. And then the second most common query is having two joins.
Xin lỗi, hầu hết các truy vấn không có phép nối. Và loại truy vấn phổ biến thứ hai là có hai phép nối.
But it's a long tail where people do a lot of weird stuff, and we have to be able to handle that. The largest number of joins I've come across in a database is 1,500.
Nhưng đây là một đuôi dài, nơi người ta làm rất nhiều thứ kỳ quặc, và chúng ta phải có khả năng xử lý những trường hợp đó. Số phép join lớn nhất mà tôi từng gặp trong một cơ sở dữ liệu là 1.500.
And this is obviously not a query written by humans. This is something from a dashboard. Someone clicking a bunch of buttons to do a bunch of things.
Và rõ ràng đây không phải là truy vấn do con người viết. Nó đến từ một dashboard. Có người bấm một loạt nút để làm một loạt việc.
But you have to do a join on 1,500 tables, and our solution space is exponential. We have to start making a bunch of decisions, how to prune this down.
Nhưng bạn phải join 1.500 bảng, và không gian lời giải của chúng ta tăng theo hàm mũ. Chúng ta phải bắt đầu đưa ra hàng loạt quyết định về cách cắt tỉa không gian này.
How to figure out whether one plan is better than another? As we look at these alternatives, that'll be the cost model, and that we'll cover next week, right?
Làm sao biết một kế hoạch tốt hơn kế hoạch khác? Khi xem xét các phương án này, đó sẽ là mô hình chi phí, và chúng ta sẽ học vào tuần sau, nhé?
And then an ideal scenario is that no matter how bizarre someone writes a SQL query, and this matters now with LLMs, because LLMs are spitting out stuff all the time, right?
Và kịch bản lý tưởng là dù người ta viết một truy vấn SQL kỳ quặc đến đâu, và điều này quan trọng hiện nay với các LLM, vì LLM lúc nào cũng sinh ra đủ thứ, đúng không?
No matter how bizarre it actually is, no matter what weird things they're doing, ideally, the optimizer should be able to produce a good plan, an optimal plan.
Dù nó kỳ quặc đến mức nào, dù họ làm những điều lạ lùng gì, lý tưởng nhất là bộ tối ưu hóa phải tạo ra được một kế hoạch tốt, một kế hoạch tối ưu.
We'll see some cases where that's not always true. When we open up Postgres and other systems for things as humans, you think that should be obvious. In other cases, it's not always.
Chúng ta sẽ thấy một số trường hợp điều đó không phải lúc nào cũng đúng. Khi mở Postgres và các hệ thống khác, xét theo góc nhìn của con người, bạn sẽ nghĩ điều đó là hiển nhiên. Trong những trường hợp khác thì không phải lúc nào cũng vậy.
All right, so I think we've already covered this, but logical and physical plan. Logical plan, again, is just describing at a high level what I want my operator to be in a query plan.
Được rồi, tôi nghĩ chúng ta đã nói về phần này, đó là kế hoạch logic và kế hoạch vật lý. Kế hoạch logic, nhắc lại, chỉ mô tả ở mức cao toán tử nào tôi muốn có trong kế hoạch truy vấn.
I want to join table A and B. I'm not saying how to join it. I'm just saying I want to join them.
Tôi muốn join bảng A và B. Tôi không nói join bằng cách nào. Tôi chỉ nói rằng tôi muốn join chúng.
And then the physical operators will be the actual implementation details of how to actually execute that equivalent logical operator.
Còn các toán tử vật lý là chi tiết triển khai thực tế về cách thực thi toán tử logic tương đương đó.
I want to do a hash join on table A and B. I want to do a sort-merge on A and B.
Tôi muốn thực hiện hash join trên bảng A và B. Tôi muốn thực hiện sort-merge trên A và B.
And as I'm doing my transformations to convert logical operators to physical operators, it isn't always going to be a one-to-one mapping, meaning a logical join operator might not always produce, when I do my transformation, a single equivalent physical join operator.
Và khi tôi thực hiện các phép biến đổi để chuyển toán tử logic thành toán tử vật lý, không phải lúc nào cũng là ánh xạ một-một, nghĩa là một toán tử join logic không phải lúc nào cũng tạo ra, khi tôi biến đổi, đúng một toán tử join vật lý tương đương.
In some cases, I'll break it up. In other cases, I can retract them. And the data system is free to move things around.
Có trường hợp tôi tách nó ra. Có trường hợp tôi có thể gộp chúng lại. Và hệ thống dữ liệu được tự do sắp xếp lại mọi thứ.
The optimizer is free to move things around if it thinks it's going to make a difference about producing a better query plan.
Bộ tối ưu hóa được tự do sắp xếp lại mọi thứ nếu nó cho rằng điều đó sẽ tạo ra khác biệt để có kế hoạch truy vấn tốt hơn.
There's other things we'll care about in a second or maybe at the end of this lecture.
Còn những điều khác mà chúng ta sẽ quan tâm ngay sau đây hoặc có thể là ở cuối bài giảng này.
I also need to keep track of, for each operator, what does the data look like that they're producing? The most obvious thing is the sort order.
Tôi cũng cần theo dõi, với mỗi toán tử, dữ liệu mà chúng tạo ra trông như thế nào. Điều hiển nhiên nhất là thứ tự sắp xếp.
So if I know I need my output to be sorted, I want to keep track of what operator is going to produce the data in that sorted order.
Vậy nếu tôi biết mình cần đầu ra được sắp xếp, tôi muốn theo dõi xem toán tử nào sẽ tạo ra dữ liệu theo thứ tự đã sắp xếp đó.
Because it might be the sort-merge join operator. It might be the order by operator. But the data might already be sorted or coming from an index.
Vì đó có thể là toán tử sort-merge join. Cũng có thể là toán tử order by. Nhưng dữ liệu cũng có thể đã được sắp xếp sẵn hoặc đến từ một chỉ mục.
So you keep track of some of these physical properties in your query optimizer so that when you're doing these transformations, You know the data is coming out in the right form that you would need, or that one operator may need.
Vì vậy, bạn theo dõi một số thuộc tính vật lý này trong bộ tối ưu hóa truy vấn để khi thực hiện các phép biến đổi, bạn biết dữ liệu đầu ra có đúng dạng mà bạn cần, hoặc mà một toán tử nào đó có thể cần.
It's also worth mentioning, too, that we're only going to focus on doing query optimization at one query at a time.
Cũng đáng nhắc rằng chúng ta chỉ tập trung tối ưu hóa truy vấn cho từng truy vấn một.
So we're going to treat every query as if it's on an island by itself. We're not worried about other queries running at the same time.
Tức là ta coi mỗi truy vấn như đang ở một hòn đảo riêng. Ta không bận tâm đến các truy vấn khác đang chạy cùng lúc.
We'll get a little bit... we can talk a little bit about that in the cost model. That's mostly determining, is one query going to interfere with another?
Ta sẽ nói đôi chút về điều đó ở phần mô hình chi phí. Phần đó chủ yếu xác định xem một truy vấn có gây nhiễu cho truy vấn khác hay không?
And that changes the expected cost of certain operators. But nearly all systems, I can't think of anybody outside of research that does this.
Và điều đó làm thay đổi chi phí kỳ vọng của một số toán tử. Nhưng gần như mọi hệ thống, tôi không nghĩ ra hệ thống nào ngoài giới nghiên cứu làm điều này.
Yeah, pretty much every system you can think of takes one SQL query and produces one query plan for it. It's not going to take...
Vâng, hầu như mọi hệ thống bạn nghĩ tới đều nhận một truy vấn SQL và tạo ra một kế hoạch truy vấn cho nó. Nó sẽ không nhận...
you could also take multiple queries in and either figure out how to overlap them so you can run them at the same time, or be aware that one query could be producing results that another query could read.
bạn cũng có thể nhận nhiều truy vấn cùng lúc, rồi tìm cách cho chúng chồng lấn để chạy đồng thời, hoặc nhận biết rằng một truy vấn có thể tạo ra kết quả mà truy vấn khác có thể đọc.
Similar to the scan sharing, that stuff that we talked about before.
Tương tự như chia sẻ quét (scan sharing) mà ta đã nói trước đó.
But no system actually does this, because most people don't write programs that way, where you say, here's all the queries I'm going to execute ahead of time and in this order.
Nhưng thực tế không hệ thống nào làm vậy, vì hầu hết mọi người không viết chương trình theo cách đó, tức là nói rằng, đây là tất cả các truy vấn tôi sẽ thực thi, được biết trước và theo thứ tự này.
DBT does that, which we talked about at the beginning of the semester, where you have sort of a DAG of queries. And then you can do this multi-query optimization.
DBT làm vậy, mà ta đã nói ở đầu học kỳ, khi bạn có một dạng DAG của các truy vấn. Và khi đó bạn có thể thực hiện tối ưu hóa đa truy vấn.
But to keep our lives simple today, and in most systems that are out there, at least all the ones people are actually using in production, they're all going to do single query optimization.
Nhưng để cho đơn giản hôm nay, và với hầu hết các hệ thống hiện có, ít nhất là tất cả những hệ thống người ta thực sự dùng trong môi trường production, chúng đều thực hiện tối ưu hóa đơn truy vấn.
All right.
Được rồi.
So now that we have sort of a high-level understanding of what a query optimizer is doing in the first 20 minutes of class, we will now go into more details and start to talk about how we're actually going to implement this in our database system.
Vậy giờ ta đã có hiểu biết ở mức tổng quan về việc bộ tối ưu hóa truy vấn làm gì trong 20 phút đầu của buổi học, ta sẽ đi vào chi tiết hơn và bắt đầu nói về việc thực sự cài đặt điều này trong hệ cơ sở dữ liệu của chúng ta như thế nào.
And an optimizer is really comprised of three components, three concepts or design decisions.
Một bộ tối ưu hóa thực sự gồm ba thành phần, ba khái niệm hay quyết định thiết kế.
The first is how we're going to do transformations, converting logical operators into other logical operators or logical operators into physical operators.
Thứ nhất là cách ta thực hiện các phép biến đổi, chuyển toán tử logic thành các toán tử logic khác hoặc chuyển toán tử logic thành toán tử vật lý.
This allows us to enumerate over a bunch of different possibilities of a query plan. And then we can have a way to determine whether one plan is going to be better than another.
Điều này cho phép ta liệt kê một loạt khả năng khác nhau của một kế hoạch truy vấn. Và sau đó ta cần có cách xác định liệu kế hoạch này có tốt hơn kế hoạch kia hay không.
The next piece is going to be the search algorithm of how we're going to look at our possible enumerations and evaluate them and make decisions of what's the next transformation we should apply, or what's the next part of the solution space we should examine, and how that process runs and how we get feedback and try to refine our decision making.
Phần tiếp theo là thuật toán tìm kiếm, tức là cách ta xem xét các phương án đã liệt kê và đánh giá chúng và quyết định xem phép biến đổi tiếp theo nên áp dụng là gì, hay phần tiếp theo của không gian lời giải mà ta nên xem xét là gì, cũng như quá trình đó chạy ra sao và ta nhận phản hồi như thế nào để cố gắng tinh chỉnh việc ra quyết định của mình.
And then the last piece, again, is the cost model, is how we're going to determine whether one query plan is better than another. What's the correct cost of a query plan?
Và phần cuối cùng, một lần nữa, là mô hình chi phí, tức là cách ta xác định liệu một kế hoạch truy vấn có tốt hơn kế hoạch khác hay không. Chi phí đúng của một kế hoạch truy vấn là bao nhiêu?
If I want to know how long it's going to take, what's the easiest, or not the easiest, what's the most accurate way to determine how long a query is going to take?
Nếu tôi muốn biết nó sẽ mất bao lâu, cách dễ nhất à không phải dễ nhất, mà là cách chính xác nhất để xác định một truy vấn sẽ chạy mất bao lâu là gì?
Run it, right?
Là chạy nó, đúng không?
But if I just said my solution space is exponential and I have, for one query, a billion different choices of queries, query plans I could use, I can't possibly actually run them.
Nhưng nếu tôi vừa nói không gian lời giải của tôi tăng theo hàm mũ và với một truy vấn, tôi có một tỉ lựa chọn khác nhau, tức một tỉ kế hoạch truy vấn có thể dùng, thì tôi không thể chạy hết chúng được.
Because if I ran them, I would get the result and I could just return that back to the user.
Bởi vì nếu đã chạy chúng thì tôi đã có kết quả và có thể trả luôn kết quả đó lại cho người dùng.
So the cost model is a way for us to approximate, to guess whether one query plan is going to be better than another. And again, we'll focus on how we do that next class.
Vì vậy mô hình chi phí là cách để ta xấp xỉ, để ước đoán xem một kế hoạch truy vấn có tốt hơn kế hoạch khác hay không. Và một lần nữa, ta sẽ tập trung vào cách làm điều đó ở buổi học sau.
MongoDB actually does what I just said before. They just run the queries. See what everyone comes back first, and that's the one that you keep reusing.
MongoDB thực ra làm đúng như điều tôi vừa nói. Họ cứ chạy các truy vấn. Xem cái nào trả về trước, và đó là cái mà bạn sẽ tiếp tục dùng lại.
It's simple. It's brain dead. It sort of works. For more complex things, it falls apart. But as I said in the last class, everyone's query optimizer is really bad.
Nó đơn giản. Nó ngô nghê. Nó cũng tạm chạy được. Với những trường hợp phức tạp hơn thì nó đổ vỡ. Nhưng như tôi đã nói ở buổi trước, trình tối ưu hóa truy vấn của ai cũng rất tệ.
It's determining how bad you are relative to other ones. All right. So today's class, we're talking about the first two: how we do transformations, enumeration, and then what the search algorithms actually look like.
Vấn đề là xác định xem bạn tệ đến mức nào so với những cái khác. Được rồi. Vậy buổi học hôm nay, ta sẽ nói về hai phần đầu: cách ta thực hiện các phép biến đổi, liệt kê, và sau đó các thuật toán tìm kiếm thực sự trông như thế nào.
So a transformation rule allows us, again, to convert the query operator, query plans, the operators within them, either logical, sorry, they're always going to be logical, and then we go to physical.
Vậy một quy tắc biến đổi cho phép ta, một lần nữa, chuyển đổi các toán tử truy vấn, các kế hoạch truy vấn, và các toán tử bên trong chúng, hoặc là logic, xin lỗi, chúng luôn là logic, rồi sau đó ta chuyển sang vật lý.
Usually don't do transformation from physical to physical. That complicates things.
Thường ta không biến đổi từ vật lý sang vật lý. Điều đó làm mọi thứ phức tạp hơn.
But the idea is that it allows us to take a current state of our query plan, and it could be a mixture of logical operators and physical operators, all logical operators, and then generate alternatives for that query plan that we think will lead us to a better result.
Nhưng ý tưởng là nó cho phép ta lấy trạng thái hiện tại của kế hoạch truy vấn, có thể là hỗn hợp các toán tử logic và toán tử vật lý, hoặc toàn bộ là toán tử logic, rồi sinh ra các phương án thay thế cho kế hoạch truy vấn đó mà ta nghĩ sẽ dẫn đến kết quả tốt hơn.
Or we think that we'll have promising solutions for our search process.
Hoặc ta nghĩ rằng sẽ có những lời giải triển vọng cho quá trình tìm kiếm của mình.
What's that? The statement is, it's like rewrite rules. Yes, but rewrite rules at the plan level.
Gì vậy? Ý bạn là nó giống như các quy tắc viết lại. Đúng, nhưng là quy tắc viết lại ở cấp độ kế hoạch.
But for the DAG, yes. For the tree structure of the query plan, yes. The reason why I was being hesitant is that there are rewrite rules for SQL.
Với DAG thì đúng. Với cấu trúc cây của kế hoạch truy vấn thì đúng. Lý do tôi còn do dự là vì có những quy tắc viết lại cho SQL.
Like at the SQL level, like the strings, if I pattern match on like select star from a view, they can then rewrite that into something else.
Tức là ở cấp độ SQL, như các chuỗi ký tự, nếu tôi so khớp mẫu kiểu select star from một view, thì họ có thể viết lại nó thành thứ khác.
That would be, in my example before, that would be potentially before the binder or after the binder.
Điều đó sẽ là, trong ví dụ trước của tôi, thì có thể là trước binder hoặc sau binder.
String matching. It's error prone, but you can do it. Some people do that. I'm not saying it's a good idea. You could, right? All right.
So khớp chuỗi. Cách này dễ lỗi, nhưng làm được. Có người vẫn làm như vậy. Tôi không nói đó là ý hay. Nhưng em có thể làm được, đúng không? Được rồi.
So again, these transformation rules allow us to identify different promising plans. And then either the output is always going to be an alternative plan.
Vậy nên, các quy tắc biến đổi này cho phép chúng ta xác định các kế hoạch tiềm năng khác nhau. Và kết quả đầu ra luôn là một kế hoạch thay thế.
And ideally, that plan will have a lower cost or expected cost than the one we started off with. Or alternatively, it may actually be worse.
Lý tưởng nhất, kế hoạch đó sẽ có chi phí thấp hơn hoặc chi phí kỳ vọng thấp hơn kế hoạch ban đầu. Hoặc ngược lại, nó có thể thực sự tệ hơn.
But because we do a certain transformation, it then leads us or unlocks a bunch of other transformations we could do. That those will then have a lower cost, right?
Nhưng vì ta thực hiện một phép biến đổi nhất định, nó dẫn tới hoặc mở ra hàng loạt phép biến đổi khác mà ta có thể làm. Và những kế hoạch đó sẽ có chi phí thấp hơn, đúng không?
And the key tenet we're going to use to make this all work is rely on relational algebra equivalencies, where we can be assured that if we convert a certain set of operators in our query plan to another set of operators, because of the rules of relational algebra, we know that the plans will be equivalent and correct.
Và nguyên lý chính mà ta sẽ dùng để làm cho tất cả điều này hoạt động là dựa vào các phép tương đương của đại số quan hệ, trong đó ta có thể chắc chắn rằng nếu ta chuyển đổi một tập toán tử trong kế hoạch truy vấn sang một tập toán tử khác, thì nhờ các quy tắc của đại số quan hệ, ta biết rằng các kế hoạch đó tương đương và đúng đắn.
And this is repeating what I said.
Và đây là nhắc lại điều tôi vừa nói.
So again, we can rely on the fact that because relational algebra is well-defined, more so than SQL, relational algebra is well-defined, we would know the rules in which we can change things and permute those relational algebra operators to produce other operators that we know are equivalent to each other, right?
Vậy nên một lần nữa, ta có thể dựa vào việc đại số quan hệ được định nghĩa chặt chẽ, chặt chẽ hơn SQL, đại số quan hệ được định nghĩa rõ ràng, nên ta biết những quy tắc cho phép thay đổi mọi thứ và hoán vị các toán tử đại số quan hệ đó để tạo ra các toán tử khác mà ta biết là tương đương với nhau, đúng không?
So if you go look at examples like selections, right?
Vậy hãy xem các ví dụ như phép chọn, được chứ?
So I know that if I have a select operator with a predicate p1, p2, p3, up to pn, that in this case here, it's conjunction.
Tôi biết rằng nếu tôi có một toán tử select với vị từ p1, p2, p3, cho đến pn, ở đây là phép hội.
I know I can decompose or break up that conjunctive clauses into separate predicates and have now separate select operators or filter operators for each of those individually.
Tôi biết mình có thể phân rã hay tách các mệnh đề hội đó thành các vị từ riêng rẽ và giờ có các toán tử select riêng hay toán tử lọc cho từng vị từ một.
So instead of scanning relation R and applying p1 and p2 and p3 and p4 all at the same time, I can break it up into different filter operators.
Thay vì quét quan hệ R và áp dụng p1 và p2 và p3 và p4 cùng một lúc, tôi có thể tách thành các toán tử lọc khác nhau.
And then now I can move them around independently from each other. And I know I'm still going to produce the same correct result.
Và giờ tôi có thể di chuyển chúng độc lập với nhau. Và tôi biết mình vẫn tạo ra cùng một kết quả đúng.
Or I may want to do p2 first, apply p2 first before p1, because p2 is cheaper to run and it's more selective.
Hoặc tôi có thể muốn làm p2 trước, áp dụng p2 trước p1, vì p2 chạy rẻ hơn và có tính chọn lọc cao hơn.
And again, because of the relational algebra rules, I can move those things around and I still produce the same semantically logical result.
Và một lần nữa, nhờ các quy tắc của đại số quan hệ, tôi có thể di chuyển các thứ này mà vẫn tạo ra cùng một kết quả hợp lý về mặt ngữ nghĩa.
What's that? The question is, would you ever want to combine them again? Sure, why not? Yes.
Gì vậy? Câu hỏi là, liệu có bao giờ muốn gộp chúng lại không? Được chứ, sao không? Có.
The question is, is the select operator commutative with all other operators? Everything but outer joins. We're not going to cover outer joins.
Câu hỏi là, toán tử select có giao hoán với mọi toán tử khác không? Trừ phép nối ngoài. Chúng ta sẽ không bàn về phép nối ngoài.
Outer joins are tricky because of the null semantics. But for this lecture, yes. And the question, again, the question is, is the select operator commutative?
Phép nối ngoài phức tạp vì ngữ nghĩa của null. Nhưng với bài giảng này thì có. Và câu hỏi, một lần nữa, là toán tử select có giao hoán không?
And my answer is, yes, except for outer joins because of the nulls. If there's no match on one side versus another, what produces the null? But let's ignore that. That's what I'm saying.
Và câu trả lời là có, ngoại trừ phép nối ngoài vì các giá trị null. Nếu một bên không khớp với bên kia thì cái gì tạo ra null? Nhưng hãy bỏ qua chuyện đó. Ý tôi là vậy.
Like, there's no outer join in relational algebra. There is in SQL. So that's why the semantics are trickier. Relational algebra has been extended for that.
Kiểu như, trong đại số quan hệ không có outer join. Còn trong SQL thì có. Đó là lý do ngữ nghĩa phức tạp hơn. Đại số quan hệ đã được mở rộng để xử lý trường hợp đó.
All right, so there are other optimizations we can do. Similar to what we talked about, I think, two classes ago. Like, hey, here's this expression tree.
Được rồi, vậy là còn những tối ưu hóa khác mà chúng ta có thể làm. Tương tự những gì chúng ta đã nói, tôi nghĩ là cách đây hai buổi. Kiểu như, đây là cây biểu thức này.
We can apply sort of compiler tricks to try to optimize things further. So here I have x equals 3 and y equals x.
Chúng ta có thể áp dụng các mẹo kiểu trình biên dịch để tối ưu thêm. Ở đây tôi có x bằng 3 và y bằng x.
Well, I know because of commutativity that I can take the x equals 3 and replace the y equals x to be y equals 3.
Thì, nhờ tính giao hoán, tôi biết là tôi có thể lấy x bằng 3 và thay y bằng x thành y bằng 3.
Because I know x equals 3 when I was doing the comparison. And it seems like a trivial thing.
Vì tôi biết x bằng 3 khi thực hiện phép so sánh. Nghe có vẻ là chuyện tầm thường.
But that's actually going to be way faster now to do my evaluation when I'm actually running through real data.
Nhưng thực ra việc đánh giá bây giờ sẽ nhanh hơn nhiều khi tôi chạy trên dữ liệu thực.
Because now I'm just comparing with a value that can sit in a register rather than a reference to another variable.
Vì bây giờ tôi chỉ so sánh với một giá trị có thể nằm trong một thanh ghi, thay vì một tham chiếu đến biến khác.
You can do other optimizations ahead of time, too. Like x equals 1 plus 1. The optimizer can say, well, I know 1 plus 1 is going to produce a constant.
Bạn cũng có thể tối ưu trước những thứ khác. Như x bằng 1 cộng 1. Trình tối ưu có thể nói, tôi biết 1 cộng 1 sẽ cho ra một hằng số.
So let me just evaluate that now and produce 2 and then substitute that. So I'm not doing 1 plus 1 over and over again. And this last one is a bit more nuanced.
Vậy hãy tính nó ngay bây giờ, ra 2, rồi thay vào. Để tôi không phải tính 1 cộng 1 lặp đi lặp lại. Và cái cuối cùng này tinh tế hơn một chút.
But it basically says it's similar to the constant propagation stuff we covered last time, where instead of me running this year function to get the year out for every single tuple I may be looking at, if I have a billion tuples, then I'm better off just applying the function once and then reusing the result over and over again.
Nhưng về cơ bản nó tương tự với phần constant propagation chúng ta đã học lần trước, trong đó thay vì chạy hàm year này để lấy ra năm cho từng tuple mà tôi có thể xét, nếu có một tỉ tuple thì tốt hơn là chỉ áp dụng hàm một lần rồi dùng lại kết quả đó nhiều lần.
For joins, again, ignoring outer joins. But in the case of inner joins, equijoins, they are commutative, so I can swap the order. Like R join S, that's equivalent to S join R.
Với các phép join, một lần nữa, bỏ qua outer join. Nhưng với inner join, equijoin, chúng có tính giao hoán, nên tôi có thể đổi thứ tự. Như R join S thì tương đương với S join R.
Likewise, if I have R join S followed by join T, I can move all those things around, and I still produce the same result.
Tương tự, nếu tôi có R join S rồi join T, tôi có thể sắp xếp lại tất cả những thứ đó, và vẫn cho ra cùng một kết quả.
And when we talked about joins, we said that depending on the join algorithm implementation, so the physical operator we're going to use in our query plan to do the join, I may want to have the larger table be the outer table versus the inner table.
Và khi nói về các phép join, chúng ta đã nói rằng tùy vào cách cài đặt thuật toán join, tức là toán tử vật lý mà chúng ta dùng trong kế hoạch truy vấn để thực hiện join, tôi có thể muốn bảng lớn hơn làm bảng ngoài hay làm bảng trong.
So that's why, if I have statistics to determine which one is actually the larger one, I can look at the, I can move things around, and I know I'm guaranteed to still produce the same result, because of those commutativity and associativity rules.
Vì vậy, nếu tôi có thống kê để xác định bảng nào thực sự lớn hơn, tôi có thể xem, tôi có thể sắp xếp lại các thứ, và tôi biết chắc chắn vẫn cho ra cùng một kết quả, nhờ các quy tắc giao hoán và kết hợp đó.
Cartesian product, same thing, yes. In general, you never want to do a cross product, though, unless the query says do a cross join. You never do it. But that's an easy one.
Tích Descartes cũng vậy, đúng thế. Nói chung, bạn không bao giờ muốn làm tích chéo, trừ khi truy vấn yêu cầu làm cross join. Không bao giờ làm. Nhưng đó là trường hợp dễ.
So again, just to show you how challenging this is, the number of join orders you have in an n-way binary join, again, binary means I can only join two tables at a time, it's going to be this massive number here.
Vậy, một lần nữa, để cho bạn thấy việc này khó đến mức nào, số thứ tự join bạn có trong một phép join nhị phân n chiều, một lần nữa, binary nghĩa là mình chỉ có thể join hai bảng tại một thời điểm, thì con số này sẽ cực kỳ lớn.
Just showing you there's so many different choices we have to consider.
Chỉ để cho các em thấy là có rất nhiều lựa chọn mà chúng ta phải cân nhắc.
And if we just try to blindly look at everything, all possible combinations, as we sort of permute the search tree, exhaustive iteration would just be way too slow.
Và nếu chúng ta cứ mù quáng xem xét mọi thứ, tất cả các tổ hợp có thể, khi hoán vị cây tìm kiếm, thì việc duyệt vét cạn sẽ chậm không thể chấp nhận được.
So a bunch of these transformation rules are going to allow us to throw things away that we don't want to consider, like a cross join, for example, and I don't have to bother even considering them.
Vì vậy, một loạt quy tắc biến đổi này sẽ cho phép chúng ta loại bỏ những thứ mà chúng ta không muốn xét đến, chẳng hạn như cross join, và mình thậm chí không cần bận tâm xem xét chúng.
And when we talk about IBM System R, they're going to throw away two different types of join tree structures, Because then that cuts down the search space, even though that may actually be the true optimal plan, just in the sake of actually producing a result they would need to actually run in reasonable time.
Và khi nói về IBM System R, họ sẽ loại bỏ hai kiểu cấu trúc cây join khác nhau, vì như vậy sẽ thu hẹp không gian tìm kiếm, dù đó có thể thực sự là kế hoạch tối ưu thật sự, chỉ nhằm tạo ra được một kết quả mà họ cần chạy trong thời gian hợp lý.
They don't even bother considering them.
Họ thậm chí không buồn xem xét chúng.
All right, so what are the kind of transformations we could do? Well, a bunch of these we've already talked about, and I'll just go through an example one by one.
Được rồi, vậy chúng ta có thể thực hiện những phép biến đổi nào? Chà, nhiều phép trong số này chúng ta đã nói tới rồi, và tôi sẽ đi qua từng ví dụ một.
And all of these here, we can do this at the logical level, because we don't have to define exactly what join algorithm we're going to use.
Và tất cả những phép này, chúng ta có thể làm ở mức logic, vì chúng ta không cần xác định chính xác sẽ dùng thuật toán join nào.
We just know that these rules should get applied, because we, as database people that built the system, we know that these are things you're always going to do.
Chúng ta chỉ biết rằng các quy tắc này nên được áp dụng, vì chúng ta, là những người làm cơ sở dữ liệu đã xây dựng hệ thống, biết rằng đây là những việc lúc nào cũng nên làm.
So we don't have to ask a cost model, "Hey, is this going to make me better or not?" These are things you always want to apply.
Nên chúng ta không cần hỏi cost model: "Này, cái này có giúp mình tốt hơn hay không?" Đây là những thứ lúc nào cũng nên áp dụng.
So the first one was the example that we saw at the beginning. I want to split my conjunctive clauses.
Vậy cái đầu tiên là ví dụ mà chúng ta thấy lúc đầu. Tôi muốn tách các mệnh đề hội (conjunctive clause).
So again, if I take a literal translation of the SQL query, trying to find all the people that are, all the artists appear on the tribute album for DJ Mushu, then I would have these bunch of cross joins, because that's a naive implementation that comes out of the binder.
Vậy nên, nếu tôi dịch nguyên văn câu truy vấn SQL, để tìm tất cả những người, tất cả nghệ sĩ xuất hiện trong album tribute cho DJ Mushu, thì tôi sẽ có một loạt cross join này, vì đó là cách triển khai ngây thơ mà binder tạo ra.
And then I have my single filter clause, filter operator that has all the conjunctive clauses inside of them.
Và rồi tôi có một mệnh đề filter duy nhất, toán tử filter chứa tất cả các mệnh đề hội bên trong.
So I just take this guy here, just split it up on the ends, which is easy to do, because I'm traversing the tree structure.
Vậy tôi chỉ cần lấy cái này, tách nó ra tại các phép AND, việc này dễ làm, vì tôi đang duyệt cấu trúc cây.
Then I'm going to produce a bunch of different, or now a sequence of three filter operators that each are going to do one of those predicates by themselves.
Sau đó tôi sẽ tạo ra một loạt các hay giờ là một chuỗi ba toán tử filter mà mỗi toán tử sẽ xử lý riêng một predicate.
Now I can do the predicate pushdown trick we saw before. And see, this is why you want to break this up, because now they're independent of each other.
Bây giờ tôi có thể dùng mẹo predicate pushdown mà chúng ta đã thấy trước đó. Và thấy chưa, đây là lý do bạn muốn tách chúng ra, vì giờ chúng độc lập với nhau.
I can move them individually based on what I see below me in the query plan.
Tôi có thể di chuyển từng cái dựa trên những gì tôi thấy bên dưới trong kế hoạch truy vấn.
So this top predicate here, artist ID equals appears.artist ID, I can put that right above the cross product join between artists and appears.
Vậy predicate trên cùng này, artist ID bằng appears.artist ID, tôi có thể đặt ngay phía trên phép join tích Descartes giữa artists và appears.
And likewise, the album name equals Mushu tribute, I put that right above the scan on album. And I get a query plan that looks like this.
Và tương tự, album name bằng Mushu tribute, tôi đặt ngay phía trên phép scan trên album. Và tôi có được một kế hoạch truy vấn trông như thế này.
Then the obvious thing I want to do is apply a transformation rule that says, well, if I see a Cartesian product with a predicate right above it that has the join clause, I can convert that into an inner join.
Vậy thì điều hiển nhiên tôi muốn làm là áp dụng một quy tắc biến đổi nói rằng, nếu tôi thấy một tích Descartes có một vị từ nằm ngay phía trên nó chứa điều kiện join, thì tôi có thể chuyển nó thành một inner join.
And I just traverse down the tree and apply those changes.
Và tôi chỉ việc duyệt xuống cây và áp dụng những thay đổi đó.
This one depends on what the execution environment is, depends on what the query processing model you're using, depends on what the data actually looks like. You can also do a projection pushdown.
Việc này phụ thuộc vào môi trường thực thi là gì, phụ thuộc vào mô hình xử lý truy vấn mà bạn đang dùng, phụ thuộc vào dữ liệu thực tế trông như thế nào. Bạn cũng có thể thực hiện projection pushdown.
So I can have a projection at the top, artist.name, that's the only thing I need in my output.
Tôi có thể có một phép chiếu ở trên cùng, artist.name, đó là thứ duy nhất tôi cần trong kết quả đầu ra.
But depending on how big, wide these tables are, I may want to push down projections before I even do the join, because I can throw away a bunch of columns that I don't need and don't need to propagate up into the query plan.
Nhưng tùy vào các bảng này lớn, rộng đến mức nào, tôi có thể muốn đẩy các phép chiếu xuống trước cả khi thực hiện join, vì tôi có thể loại bỏ một loạt cột mà tôi không cần và không cần truyền lên phía trên trong kế hoạch truy vấn.
So you get something like this. So all these transformations, again, just to reiterate, all these transformations I just did here are doing logical to logical transformations.
Như vậy bạn sẽ có một thứ như thế này. Vậy tất cả những phép biến đổi này, xin nhắc lại, tất cả những phép biến đổi tôi vừa làm ở đây đều là biến đổi từ logic sang logic.
And I don't need a cost model to determine whether it's the right thing to do.
Và tôi không cần mô hình chi phí để quyết định đó có phải việc nên làm hay không.
We, as database people, people that understand how the system is actually going to be implemented, can define rules to say, this is something I always want to do.
Chúng ta, những người làm cơ sở dữ liệu, những người hiểu hệ thống thực sự sẽ được cài đặt như thế nào, có thể định nghĩa các quy tắc để nói rằng, đây là việc tôi luôn muốn làm.
Again, if you don't remember anything else in this course, other than you never use mmap in your database, you should never do a cross join unless somebody asks you to do it.
Một lần nữa, nếu các bạn không nhớ gì khác trong môn học này, ngoài việc không bao giờ dùng mmap trong cơ sở dữ liệu của mình, thì cũng đừng bao giờ dùng cross join trừ khi có người yêu cầu.
So an easy logical transformation rule is, say, replace any cross joins or cross products with an inner join, if you can.
Vậy một quy tắc biến đổi logic đơn giản là, thay mọi cross join hay tích Descartes bằng inner join, nếu có thể.
So The number of these transformation rules your system will have will depend on the sophistication of the system itself and the optimizer.
Vậy, số lượng các quy tắc biến đổi mà hệ thống của bạn có sẽ phụ thuộc vào độ tinh vi của chính hệ thống và của bộ tối ưu hóa.
I think Microsoft probably talks about, I think they have about 480, 500 different transformation rules.
Tôi nghĩ Microsoft có nói là họ có khoảng 480, 500 quy tắc biến đổi khác nhau.
And they probably have one of the world's best query optimizers. So that's probably the upper limit of how many would actually exist.
Và họ có lẽ có một trong những bộ tối ưu hóa truy vấn tốt nhất thế giới. Nên đó có lẽ là giới hạn trên của số quy tắc có thể tồn tại.
Although I will say they are discovering new ones that didn't exist before using AI. So that's kind of cool. And that paper is coming out. It's been announced.
Tuy nhiên tôi phải nói là họ đang khám phá ra những quy tắc mới mà trước đây chưa tồn tại, bằng cách dùng AI. Nên điều đó khá hay. Và bài báo đó sắp ra rồi. Nó đã được công bố.
I think it's the one I talked about when I came back from Microsoft, I was really excited about. That one should be coming out pretty soon.
Tôi nghĩ đó là cái mà tôi đã nói đến khi tôi trở về từ Microsoft, cái mà tôi rất háo hức. Bài đó chắc sẽ ra khá sớm.
But they're using LLMs to find query transformation rules they didn't think about before. It turns out a lot of them, they are actually correct.
Nhưng họ dùng các LLM để tìm ra những quy tắc biến đổi truy vấn mà trước đây họ chưa nghĩ tới. Hóa ra rất nhiều trong số đó thực sự là đúng.
So I would say also, too, in my example here, all the transformation rules are doing one-to-one mapping. Like I'm doing, like I went from, well, in this case here, it's less than one.
Tôi cũng muốn nói thêm, trong ví dụ này của tôi, tất cả các quy tắc biến đổi đều là ánh xạ một-một. Như tôi vừa làm, tôi đi từ, à, trong trường hợp này thì là ít hơn một.
I took a filter operator and a cross join. And then I converted that to a single join operator. So I went from two logical operators to one logical operator.
Tôi lấy một toán tử filter và một cross join. Rồi tôi chuyển chúng thành một toán tử join duy nhất. Vậy là tôi đi từ hai toán tử logic xuống một toán tử logic.
In other cases, it may go in the other direction. In this case here, I had one projection operator. Then it then converted it to a bunch more projection operators.
Trong những trường hợp khác, nó có thể đi theo chiều ngược lại. Ở trường hợp này, tôi có một toán tử projection. Sau đó nó được chuyển thành nhiều toán tử projection hơn.
And in this example here, I'm kind of going a one-way street, my transformations. Like I'm saying, going back here, I'm saying, I know I want to get rid of this cross join.
Và trong ví dụ này, các phép biến đổi của tôi đang đi theo kiểu đường một chiều. Như tôi đang nói, quay lại đây, tôi biết mình muốn loại bỏ cross join này.
So let me go and generate an alternative that uses the inner join. And then you don't actually care about where you came from.
Vậy hãy tạo ra một phương án thay thế dùng inner join. Và khi đó bạn thực sự không quan tâm mình đến từ đâu.
So I don't need to keep track of the history of what was the query plan before I did that transformation rule.
Nên tôi không cần theo dõi lịch sử về việc kế hoạch truy vấn trước khi áp dụng quy tắc biến đổi đó là gì.
In other transformation rules, You do actually want to keep around the old ones. And we'll see how we handle that in a second.
Với các quy tắc biến đổi khác, bạn thực sự muốn giữ lại các kế hoạch cũ. Và lát nữa chúng ta sẽ xem cách xử lý việc đó.
Because you may decide you're going down a path in your search tree that doesn't actually help you, and you want to backtrack and go back. Yes?
Bởi vì bạn có thể nhận ra mình đang đi theo một hướng trong cây tìm kiếm mà thực ra không giúp ích gì, và bạn muốn quay lui trở lại. Bạn có câu hỏi?
The statement is, in this example here, I'm joining artists and appears first. Is that just incidental? In the PowerPoint demonstration, yes. You would need a cost model to determine whether one's bigger than another.
Câu hỏi là: trong ví dụ này, tôi join artists và appears trước. Đó chỉ là ngẫu nhiên phải không? Trong bản trình chiếu PowerPoint này thì đúng vậy. Bạn sẽ cần một mô hình chi phí để xác định bảng nào lớn hơn bảng nào.
Which one do you want to join first? We'll talk about that in a sec.
Bạn muốn join bảng nào trước? Lát nữa chúng ta sẽ nói về việc đó.
So in some database systems, like Oracle famously in the 80s, however you defined it in your FROM clause, if you look at it, it says FROM artists, appears, album.
Vậy ở một số hệ quản trị cơ sở dữ liệu, như Oracle nổi tiếng hồi thập niên 80, bạn định nghĩa thế nào trong mệnh đề FROM, nếu nhìn vào thì thấy là FROM artists, appears, album.
And at the bottom, I have artists, appears, and album. I'm joining in that order. That's how they would decide join ordering.
Và ở dưới cùng, tôi có artists, appears, rồi album. Tôi join theo thứ tự đó. Đó là cách họ quyết định thứ tự join.
And they called this a semantic optimizer, because you, as the human, wrote your query this way. Therefore, you knew the order you wanted to join things. It's all s**t.
Và họ gọi đây là bộ tối ưu hóa ngữ nghĩa, vì bạn, là con người, đã viết truy vấn theo cách này. Do đó, bạn biết thứ tự mình muốn join. Toàn là nhảm nhí.
It's not real. People don't know what the hell they're doing.
Không có thật đâu. Người ta chẳng biết mình đang làm cái quái gì.
But that's what Larry Essel would say how great his optimizer was, because it allowed him to maintain the semantic meaning of what you wrote in your application.
Nhưng đó là điều Larry Ellison nói để khoe bộ tối ưu hóa của ông ta tuyệt vời thế nào, vì nó cho phép ông ta duy trì ngữ nghĩa của những gì bạn viết trong ứng dụng của mình.
It's all s**t. It's all s**t. I'll show a quote in a second. All right. So, yes. I'm just curious, because in the data system, is there a way to hint?
Toàn là nhảm nhí. Lát nữa tôi sẽ cho xem một câu trích dẫn. Được rồi. Vâng. Tôi chỉ tò mò, vì trong hệ quản trị dữ liệu, có cách nào để đưa gợi ý không?
The question is, is there a way to hint? To give hints to the query, to the data system, the query optimizer, and say, I do want things to be ordered this way.
Câu hỏi là có cách nào để đưa gợi ý không? Để đưa gợi ý cho truy vấn, cho hệ quản trị dữ liệu, cho bộ tối ưu hóa truy vấn, và nói rằng tôi muốn mọi thứ được sắp xếp theo thứ tự này.
Yes. So not all data systems support hints. Like Postgres, by default, does not.
Có. Không phải hệ quản trị dữ liệu nào cũng hỗ trợ gợi ý. Chẳng hạn Postgres theo mặc định thì không.
There's an extension called PgHintPlan or PlanHint, one of the two, where you basically put comments in the front of the SQL query and say, Join A then followed by B, or B to A.
Có một extension tên là PgHintPlan hoặc PlanHint, một trong hai, trong đó về cơ bản bạn đặt các chú thích ở đầu truy vấn SQL và nói, Join A rồi đến B, hoặc B đến A.
And you can actually do things like, I want to do a hash join. I want to make sure you use this index. MySQL can do this and some things.
Và bạn thực sự có thể làm những việc như, tôi muốn dùng hash join. Tôi muốn đảm bảo bạn dùng chỉ mục này. MySQL làm được việc này và một số thứ khác.
Oracle can do this. SQL Server, I think you have to dump the whole query out and put it back and put hints in.
Oracle cũng làm được. Còn SQL Server, tôi nghĩ bạn phải xuất toàn bộ truy vấn ra rồi đưa lại vào và thêm các gợi ý.
But yeah, you can override the optimizer's decision where you find it just making stupid choices. And you say, you're dumb. Do it this way. But you have to know what you're doing.
Nhưng đúng, bạn có thể ghi đè quyết định của bộ tối ưu hóa khi thấy nó đưa ra những lựa chọn ngu ngốc. Và bạn nói: bạn ngốc quá, hãy làm theo cách này. Nhưng bạn phải biết mình đang làm gì.
The question is, do I think there's value in hinting? Yes. Because I'd be naive just saying, well, like, so the Postgres engineering philosophy is that you should not have hints.
Câu hỏi là: tôi có nghĩ hint có giá trị không? Có. Vì sẽ là ngây thơ nếu tôi chỉ nói rằng, ừ thì, triết lý kỹ thuật của Postgres là bạn không nên dùng hint.
The optimizer should be improved to make sure you don't ever have to write hints. We can look at some examples in a second where they just get it wrong.
Bộ tối ưu hóa nên được cải thiện để bạn không bao giờ phải viết hint. Lát nữa chúng ta sẽ xem vài ví dụ mà bộ tối ưu hóa làm sai hoàn toàn.
And you do want hints. The challenge of hints, though, it kind of goes back to, I think, maybe the first or second lecture, when I talked about, like, this CODASYL out there.
Và lúc đó bạn thực sự muốn có hint. Tuy nhiên, thách thức của hint thì phần nào quay lại với có lẽ là bài giảng đầu tiên hoặc thứ hai, khi tôi nói về CODASYL ngày xưa.
Where if you didn't write your queries in a declarative language, you would say, I want to do the join order this way. And I want to make sure I use this algorithm.
Ở đó, nếu bạn không viết truy vấn bằng ngôn ngữ khai báo, bạn sẽ nói: tôi muốn thực hiện thứ tự join theo cách này. Và tôi muốn đảm bảo dùng thuật toán này.
You're sort of hand coding what the join algorithm is going to be. And you're essentially locking in the query plan based on what you see the data at that time.
Bạn đang tự viết tay thuật toán join sẽ là gì. Và về cơ bản bạn đang cố định kế hoạch truy vấn dựa trên dữ liệu mà bạn thấy tại thời điểm đó.
So now if the data distribution changes, and now you want to flip the join order, or flip an algorithm you're using, you've got to go back and rewrite your application.
Vậy nếu phân phối dữ liệu thay đổi, và giờ bạn muốn đổi thứ tự join, hoặc đổi thuật toán đang dùng, bạn phải quay lại và viết lại ứng dụng của mình.
So hints kind of give you that problem as well. Basically locking in what exactly you want the query plan to be. And maybe that's OK.
Vậy hint cũng gây ra vấn đề đó. Về cơ bản là cố định chính xác kế hoạch truy vấn mà bạn muốn. Và có thể điều đó vẫn ổn.
But if the assumptions you make when you define those query plans change, the data evolves in some way, or the guy that wrote the hints quits, And then you're now responsible for maintaining this code base from 10 years ago.
Nhưng nếu các giả định bạn đưa ra khi định nghĩa các kế hoạch truy vấn ấy thay đổi, dữ liệu thay đổi theo cách nào đó, hoặc người viết hint nghỉ việc, thì giờ bạn phải chịu trách nhiệm bảo trì cơ sở mã từ 10 năm trước.
And you're like, what the f*** are all these hints? And the assumptions are all wrong. It's going to produce bad query plans.
Và bạn kiểu: mấy cái hint này là cái quái gì vậy? Và các giả định đều sai hết. Nó sẽ tạo ra các kế hoạch truy vấn tệ.
So, like, a double-edged sword. Like, yes, in some cases, they're a good idea. In other cases, you know, maybe not. All right.
Nên nó như con dao hai lưỡi. Có, trong một số trường hợp chúng là ý hay. Trong các trường hợp khác thì có lẽ không. Được rồi.
So again, the search engine in our query optimizer is responsible for applying these transformation rules, generating different alternatives, either logical alternatives or physical alternatives, and then using a cost model to determine whether one plan is better than another.
Vậy một lần nữa, công cụ tìm kiếm trong bộ tối ưu hóa truy vấn của chúng ta chịu trách nhiệm áp dụng các quy tắc biến đổi, sinh ra các phương án khác nhau, có thể là phương án logic hoặc phương án vật lý, rồi dùng mô hình chi phí để xác định kế hoạch nào tốt hơn kế hoạch nào.
But it may not be the case that you always apply a cost model. It may just be the search engine says, I'm out of rules for me to run, or run out of time.
Nhưng không phải lúc nào cũng áp dụng mô hình chi phí. Có thể công cụ tìm kiếm chỉ nói rằng, tôi hết quy tắc để chạy, hoặc hết thời gian.
Then it just stops, right? The challenge is going to be that we may not always have all the information we need to produce the best optimal plan.
Thì nó chỉ dừng lại, đúng không? Thách thức là không phải lúc nào chúng ta cũng có đủ thông tin cần thiết để tạo ra kế hoạch tối ưu nhất.
So remember, we talked about prepared statements, where you basically say, here's a SQL query I want to run in the future. Give it a name, like a macro.
Hãy nhớ chúng ta đã nói về prepared statement, nơi bạn nói: đây là một truy vấn SQL tôi muốn chạy trong tương lai. Đặt tên cho nó, như một macro.
And then now I can execute it by passing in input parameters, like an RPC or a function call.
Và rồi tôi có thể thực thi nó bằng cách truyền vào các tham số đầu vào, giống như một RPC hoặc một lời gọi hàm.
When you call prepare, most databases will generate a physical plan for you so that when you then invoke that query, it doesn't have to run through the optimizer.
Khi bạn gọi prepare, hầu hết cơ sở dữ liệu sẽ tạo một kế hoạch vật lý cho bạn để khi sau đó bạn gọi truy vấn đó, nó không phải chạy qua bộ tối ưu hóa nữa.
It has a query plan ready to go.
Nó đã có sẵn một kế hoạch truy vấn.
Of course, the challenge is if I have input parameters that I don't know at the time I'm doing planning, how do I pick the best optimal plan?
Tất nhiên, thách thức là nếu tôi có các tham số đầu vào mà tôi không biết vào lúc đang lập kế hoạch, thì làm sao chọn được kế hoạch tối ưu nhất?
And so the easiest thing is to take an average. Well, then, as soon as you have statistics, or if you take a good average. So we may be dealing with incomplete information.
Và cách dễ nhất là lấy giá trị trung bình. Vâng, khi đó, ngay khi bạn có thống kê, hoặc nếu bạn lấy được một giá trị trung bình tốt. Vì vậy, chúng ta có thể phải xử lý thông tin không đầy đủ.
Especially with statistics, we may not have anything. But we'll see how we can handle that next class.
Đặc biệt với thống kê, có thể chúng ta chẳng có gì cả. Nhưng chúng ta sẽ xem cách xử lý chuyện đó ở buổi học sau.
All right, so as I said, there's basically two approaches to this.
Được rồi, như tôi đã nói, về cơ bản có hai cách tiếp cận.
There's just applying all the rules that we talked about so far, and you keep applying them until you realize you're stuck in an infinite loop, or you run out of whatever your budget is for running, or there's no more transformations actually to apply.
Một là áp dụng tất cả các quy tắc mà chúng ta đã nói đến cho tới giờ, và bạn cứ áp dụng cho đến khi nhận ra mình bị kẹt trong một vòng lặp vô hạn, hoặc hết ngân sách dành cho việc chạy, hoặc không còn phép biến đổi nào để áp dụng nữa.
And as I said, this is what most people build when they build a data system that will support SQL. This is the very first thing that they're going to end up implementing.
Và như tôi đã nói, đây là thứ mà hầu hết mọi người xây dựng khi họ xây dựng một hệ thống dữ liệu hỗ trợ SQL. Đây là thứ đầu tiên mà họ sẽ triển khai.
And then a more sophisticated approach is to use cost-based search. I'm saying sophisticated. This is actually what IBM built back in the 70s.
Và một cách tiếp cận tinh vi hơn là dùng tìm kiếm dựa trên chi phí. Tôi nói là tinh vi, nhưng thực ra đây là thứ IBM đã xây dựng từ những năm 70.
So the very first relational data system came with its own cost-based query optimizer. But still, people implement the first one because it's just easier to do.
Tức là hệ thống dữ liệu quan hệ đầu tiên đã đi kèm với bộ tối ưu hóa truy vấn dựa trên chi phí của riêng nó. Nhưng người ta vẫn triển khai cách thứ nhất vì nó dễ làm hơn.
So we'll first talk about this one, understand what it is, and then we'll see how we can do it.
Vì vậy, trước hết chúng ta sẽ nói về cách này, hiểu nó là gì, rồi sau đó sẽ xem cách làm.
You still need to do the heuristics in some cases to help us guide in our cost-based search.
Trong một số trường hợp, bạn vẫn cần dùng heuristic để giúp định hướng cho tìm kiếm dựa trên chi phí.
All right, so a heuristic-based query optimizer, it's defining static rules that transform logical operators and physical operators, again, without a cost model.
Được rồi, một bộ tối ưu hóa truy vấn dựa trên heuristic định nghĩa các quy tắc tĩnh để biến đổi các toán tử logic và toán tử vật lý, một lần nữa, mà không có mô hình chi phí.
And these decisions can be based on things like, oh, you're doing a where clause with an equality predicate on a primary key. Well, I know that I have a primary key index.
Và những quyết định này có thể dựa trên những điều như, ồ, bạn đang dùng mệnh đề where với một vị từ so sánh bằng trên khóa chính. Vậy thì tôi biết là mình có một chỉ mục khóa chính.
Therefore, the access method should, the physical operator for your scan for reading that table should just be looking up on that primary key index.
Do đó, phương thức truy cập nên là, toán tử vật lý để quét, để đọc bảng đó, chỉ nên là tra cứu trên chỉ mục khóa chính đó.
It could be simple things like that, where all that projection, predicate pushdown we talked about before, limit pushdown if you can, and then some really basic, simple rules for determining what should be the join order.
Có thể là những thứ đơn giản như vậy, cùng với toàn bộ phép đẩy xuống của phép chiếu và vị từ mà chúng ta đã nói trước đây, đẩy xuống limit nếu có thể, và một vài quy tắc thực sự cơ bản, đơn giản để xác định thứ tự join nên là gì.
It could be the naive thing, like to assume whatever the SQL query gives you, that's the join order people wanted.
Có thể là cách ngây thơ, như giả định rằng truy vấn SQL đưa cho bạn thứ tự nào, thì đó là thứ tự join mà người dùng muốn.
Or, again, whether or not this is the cost model, it's semantics to say, "All right, I'll just go look to see how many tuples I expect to be in this table, and then that'll determine the join order."
Hoặc, dù đây có phải là mô hình chi phí hay không, thì cũng chỉ là cách gọi, họ nói: "Được rồi, tôi sẽ xem thử bảng này dự kiến có bao nhiêu tuple, và điều đó sẽ quyết định thứ tự join."
So this is what Ingres built in the 1970s, their first query optimizer. Ingres, again, was the precursor to Postgres. Oracle had this also in the 1970s, up until the early 90s.
Đây là thứ Ingres đã xây dựng vào những năm 1970, bộ tối ưu hóa truy vấn đầu tiên của họ. Ingres, một lần nữa, là tiền thân của Postgres. Oracle cũng có cách này vào những năm 1970, cho đến đầu những năm 90.
They went pretty far with this. This is what MongoDB essentially does now.
Họ đã đi khá xa với cách này. Về cơ bản đây là thứ MongoDB đang làm hiện nay.
And again, every new data system written in the last 10 years, when they first started off, unless they're using bits and pieces of Postgres or a query optimizer package called Calcite, this is what everyone else does.
Và một lần nữa, mọi hệ quản trị dữ liệu mới được viết trong 10 năm qua, khi mới bắt đầu, trừ khi họ dùng các mảnh ghép của Postgres hoặc một gói bộ tối ưu hóa truy vấn tên là Calcite, thì đây là những gì mọi người khác làm.
And the reason is because it's pretty simple to implement.
Và lý do là vì nó khá đơn giản để triển khai.
It's really easy to debug, because you just take the SQL query and trace through the debugger and see all the rules that get applied and see what comes along.
Nó thực sự rất dễ gỡ lỗi, vì bạn chỉ cần lấy câu truy vấn SQL và chạy từng bước trong trình gỡ lỗi, xem tất cả các quy tắc được áp dụng và xem kết quả ra sao.
The problem is going to be, though, it's going to rely on magic constants or hard-coded intuition about whether one decision is better than another. And for simple things like predicate pushdown, that's OK.
Tuy nhiên, vấn đề là nó sẽ dựa vào các hằng số "ma thuật" hoặc trực giác được mã hóa cứng về việc quyết định này có tốt hơn quyết định kia hay không. Và với những việc đơn giản như predicate pushdown thì không sao.
For more complex queries, this becomes problematic.
Với các truy vấn phức tạp hơn, điều này trở nên có vấn đề.
And if I have to do a lot of joins, you're never going to get an optimal plan, just because you can't reason about all the different independencies and what the data looks like and understand how things get propagated up in query plans.
Và nếu tôi phải thực hiện nhiều phép join, bạn sẽ không bao giờ có được kế hoạch tối ưu, đơn giản vì bạn không thể suy luận về tất cả các phụ thuộc khác nhau và dữ liệu trông như thế nào, cũng như hiểu cách mọi thứ được lan truyền lên trong các kế hoạch truy vấn.
So there is a big optimization to get you for simple things, like simple applications where there are no joins.
Vì vậy nó là một bước tối ưu hóa lớn cho những việc đơn giản, như các ứng dụng đơn giản không có phép join.
But once you start doing more than two tables in a query, sorry, joining more than two tables in a query, this falls apart.
Nhưng một khi bạn bắt đầu dùng nhiều hơn hai bảng trong một truy vấn, xin lỗi, join nhiều hơn hai bảng trong một truy vấn, thì cách này sụp đổ.
Yes? So the question is, what do we mean by magic constant? So do I have slides on this? Let me see. No, it's not here.
Vâng? Câu hỏi là: hằng số ma thuật nghĩa là gì? Tôi có slide về điều này không nhỉ? Để xem. Không, không có ở đây.
So a magic constant would be, how do I determine whether an index scan is better than a sequential scan?
Vậy một hằng số ma thuật sẽ là, làm sao tôi xác định index scan tốt hơn sequential scan?
So if it's simple things like WHERE id = 1, 2, 3 and id is the primary key, then, yeah, index scans would make sense.
Nếu là những việc đơn giản như WHERE id = 1, 2, 3 và id là khóa chính, thì đúng, index scan là hợp lý.
But now if I start doing range predicates, scans, and I chose to either do a sequential scan or an index scan, I kind of need to know what the distribution of the data looks like, what's the cost of accessing the index versus scanning the table, right?
Nhưng giờ nếu tôi bắt đầu dùng các vị từ khoảng, quét, và tôi phải chọn giữa sequential scan hoặc index scan, thì tôi cần biết phân bố của dữ liệu trông như thế nào, chi phí truy cập chỉ mục so với quét bảng là bao nhiêu, đúng không?
Now you're basically starting to build a cost model. So a lot of times in systems, they'll say, well, a sequential scan is some multiple faster than a random IO.
Lúc này về cơ bản bạn đang bắt đầu xây dựng một mô hình chi phí. Nên nhiều khi trong các hệ thống, người ta sẽ nói rằng sequential scan nhanh hơn random IO một số lần nào đó.
So now how do you set those knobs correctly? Depends on the hardware, depends on what the data is. Now, the cost model stuff next class will have the same problem too.
Vậy làm sao đặt đúng các tham số đó? Tùy thuộc vào phần cứng, tùy thuộc vào dữ liệu là gì. Phần mô hình chi phí ở buổi sau cũng sẽ có cùng vấn đề này.
But this is even more problematic in just pure heuristics.
Nhưng điều này còn có vấn đề hơn trong các heuristic thuần túy.
Ideally, also, too, you want to define your transformation rules in, not necessarily a DSL, but in a structured manner so that you can compose them together real quickly.
Lý tưởng nhất, bạn cũng muốn định nghĩa các quy tắc biến đổi bằng, không nhất thiết là một DSL, mà theo cách có cấu trúc để có thể kết hợp chúng với nhau thật nhanh.
In Postgres, it's supposed to if-then-else statements. That's the rules.
Trong Postgres, đó là các câu lệnh if-then-else. Đó là các quy tắc.
The question is, why don't they write a DSL for that? It's hard. I mean, let me tell you, right? They know their optimizer sucks. But it's hard. Yeah, in the back.
Câu hỏi là: tại sao họ không viết một DSL cho việc đó? Vì khó. Ý tôi là, để tôi nói cho bạn nghe nhé? Họ biết bộ tối ưu hóa của họ tệ. Nhưng nó khó. Vâng, ở phía sau.
The question is, is there only one parameter we want to optimize as a cost model? We'll cover that next class. No. But IO usually is the big one.
Câu hỏi là, liệu chỉ có một tham số mà ta muốn tối ưu trong mô hình chi phí không? Chúng ta sẽ nói buổi sau. Không. Nhưng IO thường là yếu tố lớn.
But IO could be network IO, disk IO, right? And disk and network is getting really fast. CPU is probably the bottleneck. So that matters too now.
Nhưng IO có thể là IO mạng, IO đĩa, đúng không? Và đĩa và mạng đang trở nên rất nhanh. CPU có lẽ là nút thắt cổ chai. Nên điều đó giờ cũng quan trọng.
The question is, how, when I say we're trying to produce a good plan, what do I mean by good? Depends. Most instances we'll optimize for performance, right?
Câu hỏi là, làm thế nào, khi tôi nói rằng chúng ta đang cố tạo ra một kế hoạch tốt, thì "tốt" nghĩa là gì? Tùy trường hợp. Hầu hết các trường hợp chúng ta sẽ tối ưu cho hiệu năng, đúng không?
And how do you, as a human, perceive performance? It's wall clock time.
Và với tư cách con người, bạn cảm nhận hiệu năng như thế nào? Đó là thời gian thực (wall clock time).
But it's very hard to come up with a cost model that says, These amount of IOs are going to take this many milliseconds. And therefore, I have to have this many.
Nhưng rất khó xây dựng một mô hình chi phí nói rằng, Lượng IO này sẽ mất chừng này mili giây. Và do đó, tôi cần có chừng này.
And that's going to calculate the wall clock time. So instead, they use synthetic values. Again, we'll cover that more in the next class.
Và từ đó sẽ tính ra thời gian thực. Vì vậy, thay vào đó, người ta dùng các giá trị tổng hợp. Một lần nữa, chúng ta sẽ nói kỹ hơn về điều đó ở buổi học sau.
But most systems are going to say, I care about the performance of the query. Other systems may care about the cost of actually running the query in the cloud environment.
Nhưng hầu hết các hệ thống sẽ nói rằng: tôi quan tâm đến hiệu năng của truy vấn. Một số hệ thống khác có thể quan tâm đến chi phí thực sự của việc chạy truy vấn trong môi trường đám mây.
But that's not that common. But you could do it, just because it's another objective. You just optimize for them. All right, so this is the snippet from the unofficial Larry Ellison autobiography.
Nhưng điều đó không phổ biến lắm. Nhưng bạn vẫn có thể làm, vì đó cũng chỉ là một mục tiêu khác. Bạn chỉ cần tối ưu cho chúng. Được rồi, đây là một đoạn trích từ cuốn tự truyện không chính thức của Larry Ellison.
And in one of these pages here, it's Stonebreaker, the guy that invented Postgres and Ingress. They interview him. And he starts talking about how, again, Oracle's query optimizer in the 80s was total crap.
Và ở một trong những trang này, là Stonebraker, người đã phát minh ra Postgres và Ingres. Họ phỏng vấn ông ấy. Và ông ấy bắt đầu kể rằng, bộ tối ưu hóa truy vấn của Oracle hồi thập niên 80 thật sự rất tệ.
But then he called them, instead of making his weakness be the thing that the marketing people and his competitors could take advantage of, he would then claim that they had this beautiful semantic optimizer that just generated the join order based on the order in which the tables appeared in the query.
Nhưng sau đó ông ta, thay vì để điểm yếu của mình trở thành thứ mà bộ phận marketing và các đối thủ có thể lợi dụng, đã tuyên bố rằng họ có một bộ tối ưu hóa ngữ nghĩa tuyệt đẹp chỉ đơn giản là tạo ra thứ tự join dựa trên thứ tự các bảng xuất hiện trong truy vấn.
And as I said, it's a stupid thing. You wouldn't actually want to build an optimizer this way. But they were able to sell that to people because it was the 80s, right?
Và như tôi đã nói, đó là một điều ngớ ngẩn. Bạn sẽ không thực sự muốn xây dựng một bộ tối ưu hóa theo cách này. Nhưng họ vẫn bán được nó cho mọi người vì đó là thập niên 80, đúng không?
All right, so that's heuristic and rules. Again, I would say also these are not mutually exclusive.
Được rồi, vậy đó là heuristic và các luật. Một lần nữa, tôi cũng muốn nói rằng chúng không loại trừ lẫn nhau.
So you could build a cost-based search that still applies all the transformation rules that we talked about so far.
Vì vậy, bạn có thể xây dựng một tìm kiếm dựa trên chi phí mà vẫn áp dụng tất cả các luật biến đổi mà chúng ta đã nói đến từ đầu.
And you could do a first pass of doing that logical transformation stuff that I talked about in the beginning. And then you hand off the final remaining decisions to a cost-based optimizer.
Và bạn có thể thực hiện lượt đầu tiên để làm phần biến đổi logic mà tôi đã nói ở phần đầu. Rồi bạn giao các quyết định còn lại cuối cùng cho một bộ tối ưu hóa dựa trên chi phí.
But it depends on how you implement stuff.
Nhưng điều đó còn tùy vào cách bạn triển khai.
All right, so again, with the cost-based search, we're going to apply the transformation rules that we've defined before, going to enumerate a bunch of different choices we would have.
Được rồi, một lần nữa, với tìm kiếm dựa trên chi phí, chúng ta sẽ áp dụng các luật biến đổi đã định nghĩa trước đó, và liệt kê hàng loạt lựa chọn khác nhau mà chúng ta có.
And at every step of the way, at least when we're doing the cost-based search, we would consult the cost model and say, is this new plan we're generating after you apply this rule, is this better than the best I've seen so far?
Và ở mỗi bước, ít nhất là khi chúng ta thực hiện tìm kiếm dựa trên chi phí, chúng ta sẽ tham khảo mô hình chi phí và hỏi, kế hoạch mới mà chúng ta tạo ra sau khi áp dụng luật này, có tốt hơn kế hoạch tốt nhất tôi đã thấy cho đến giờ không?
If no, then based on how I'm searching things, I may actually want to stop searching that branch in my solution space. Or I may be allowed to override that initial increase in the cost.
Nếu không, thì tùy cách tôi tìm kiếm, tôi có thể muốn dừng tìm kiếm nhánh đó trong không gian lời giải. Hoặc tôi có thể được phép bỏ qua mức tăng chi phí ban đầu đó.
Think of it like a gradient descent search.
Hãy hình dung nó giống như một cuộc tìm kiếm bằng gradient descent.
I'm allowed to ignore that I'm bumping back up, because I know once I get on the other side of that hill, then I'll get down to something that looks like the local true optimal.
Tôi được phép bỏ qua việc chi phí đang tăng trở lại, vì tôi biết một khi vượt qua được ngọn đồi đó, tôi sẽ đi xuống tới một điểm trông giống như tối ưu cục bộ thực sự.
So you would typically do this in a bunch of phases, depending on what your query looks like.
Vì vậy, thông thường bạn sẽ làm việc này theo nhiều giai đoạn, tùy vào truy vấn của bạn trông như thế nào.
You could handle all the subplans that are tackling one table at a time, one relation at a time. Then you expand out and say, I want to handle all the joins.
Bạn có thể xử lý tất cả các subplan chỉ làm việc với một bảng, tức một quan hệ, tại một thời điểm. Sau đó bạn mở rộng ra và nói: tôi muốn xử lý tất cả các phép join.
Then you expand out even further and say, I want to handle all the nested queries. Some systems do this in stages. Other systems do this in an all-at-once, holistic tuning approach, or optimization approach.
Rồi bạn mở rộng thêm nữa và nói: tôi muốn xử lý tất cả các truy vấn lồng nhau. Một số hệ thống làm việc này theo từng giai đoạn. Những hệ thống khác làm tất cả cùng một lúc, theo cách tinh chỉnh toàn diện, hay cách tối ưu hóa toàn diện.
We'll see the two examples of this. So when do we decide to stop?
Chúng ta sẽ xem hai ví dụ về việc này. Vậy khi nào thì quyết định dừng?
The obvious thing is you just set a timer and say, well, when my query optimizer is run for, I don't know, 500 milliseconds, or whatever you want to set the threshold to be.
Cách hiển nhiên là đặt một bộ đếm thời gian và nói rằng, khi bộ tối ưu hóa truy vấn của tôi đã chạy, ví dụ, 500 mili giây, hoặc bất kỳ ngưỡng nào bạn muốn đặt.
Once I run to that time, then I stop, and I produce whatever the best query plan I've seen so far. That's what I'm going to execute with.
Khi chạy hết thời gian đó thì tôi dừng, và đưa ra kế hoạch truy vấn tốt nhất mà tôi đã thấy cho đến lúc đó. Đó là kế hoạch tôi sẽ dùng để thực thi.
Another could be if you have a way to define the threshold and say, don't give me back any query. Don't stop searching until you find a query plan that has this lower cost.
Một cách khác là nếu bạn có cách xác định một ngưỡng và nói rằng, đừng trả về bất kỳ kế hoạch truy vấn nào. Đừng dừng tìm kiếm cho đến khi tìm được một kế hoạch truy vấn có chi phí thấp hơn mức này.
So it could be like, I'm replanning the query that I've seen before. I don't want to let it go until I see, Stop once I see a query that's 10 better.
Chẳng hạn, tôi đang lập lại kế hoạch cho một truy vấn mà tôi đã thấy trước đây. Tôi không muốn dừng cho đến khi thấy một truy vấn tốt hơn 10.
And a query plan that's 10 better than I've seen before.
Tức là một kế hoạch truy vấn tốt hơn 10 so với những gì tôi đã thấy trước đó.
Or at some point, if you sort of plateau, you're not seeing any better plan over a period of time, then you can drop out as well.
Hoặc đến một lúc nào đó, nếu kết quả đi ngang, tức là không thấy kế hoạch nào tốt hơn trong một khoảng thời gian, thì bạn cũng có thể dừng lại.
If the query is simple, and your system is really fast, and you don't have a lot of rules to apply, you may end up just exhausting all the possible combinations.
Nếu truy vấn đơn giản, hệ thống của bạn rất nhanh, và bạn không có nhiều quy tắc để áp dụng, thì có thể bạn sẽ duyệt hết mọi tổ hợp có thể.
And then you don't have to wait for the timeout or the cost threshold. You just come back and say, "I know this is the optimal plan." Like SELECT * FROM foo, that's pretty instantaneous.
Và khi đó bạn không phải chờ hết thời gian hay đạt ngưỡng chi phí. Bạn chỉ cần quay lại và nói: "Tôi biết đây là kế hoạch tối ưu." Như SELECT * FROM foo, truy vấn đó gần như tức thì.
You don't have to do a lot of rules to figure out what. You don't have to look at a bunch of alternatives. You can spit out something very quickly.
Bạn không cần áp dụng nhiều quy tắc để xác định. Bạn không cần xem xét hàng loạt phương án thay thế. Bạn có thể đưa ra kết quả rất nhanh.
The way to actually really do this is actually not on wall clock time or all these other things. It's actually going to be, number three is obvious. You always want to do number three.
Cách thực sự để làm việc này thật ra không phải dựa trên thời gian thực hay những thứ khác. Thật ra thì, cách số ba là hiển nhiên. Bạn luôn muốn làm cách số ba.
But for this last one here, instead of trying to count how long I've run, in SQL Server, what they do is they count how many transformation rules they've applied.
Nhưng với cách cuối cùng này, thay vì cố đếm xem tôi đã chạy bao lâu, trong SQL Server, họ đếm số quy tắc biến đổi đã được áp dụng.
And then when you exhaust the number of transformation rules, then it kicks out and terminates the search. I'm going to take a guess why they do this. Instead of wall clock time.
Và khi đã dùng hết số lượng quy tắc biến đổi cho phép, thì nó thoát ra và kết thúc việc tìm kiếm. Tôi thử đoán xem vì sao họ làm vậy, thay vì dùng thời gian thực.
The statement is you're guaranteed to get at least what?
Điều được khẳng định là bạn được đảm bảo ít nhất sẽ nhận được gì?
The statement is you're guaranteed at least to get one transformation considered. Yeah, but you would set the transformation count for like, I don't know, hundreds of thousands.
Điều được khẳng định là bạn được đảm bảo ít nhất cũng được xem xét một phép biến đổi. Đúng, nhưng bạn sẽ đặt số lượng phép biến đổi là, kiểu như, tôi không biết nữa, hàng trăm nghìn.
Yes, bingo. They said that different hardware may have different wall clock time. Or actually, same hardware, but now the system's being overloaded because a lot of queries are running.
Đúng rồi, chính xác. Họ nói rằng phần cứng khác nhau có thể cho thời gian đồng hồ thực khác nhau. Hoặc thực ra, cùng một phần cứng, nhưng lúc này hệ thống bị quá tải vì có rất nhiều truy vấn đang chạy.
And if I set it to the wall clock time and my CPU is taxed out, If one second where my CPU is overutilized, I may not apply as many rules versus one second when it's underutilized and I can use the core to its fullest capabilities.
Và nếu tôi đặt theo thời gian đồng hồ thực mà CPU của tôi đã kiệt sức, nếu trong một giây mà CPU bị sử dụng quá mức, tôi có thể áp dụng được ít quy tắc hơn so với một giây khi nó nhàn rỗi và tôi có thể khai thác lõi hết công suất.
So this guarantees that no matter how stressed out the system actually is, you're always guaranteed to produce the same plan for the same query, given the same input constraints.
Vì vậy cách này đảm bảo rằng dù hệ thống thực tế đang chịu tải nặng đến đâu, bạn luôn được đảm bảo tạo ra cùng một kế hoạch cho cùng một truy vấn, với cùng các ràng buộc đầu vào.
So MySQL and SQL Server, they do the first one. Because in case of, or sorry, Postgres and MySQL do the first one.
Vậy MySQL và SQL Server, họ dùng cách thứ nhất. Vì trong trường hợp, à xin lỗi, Postgres và MySQL dùng cách thứ nhất.
In case of Postgres, there is no concept of transformation rules that applies and you can start counting them. It just has a bunch of if-then-else statements that it always runs through.
Trong trường hợp của Postgres, không có khái niệm quy tắc biến đổi được áp dụng để bạn có thể bắt đầu đếm chúng. Nó chỉ có một loạt câu lệnh if-then-else mà lúc nào nó cũng chạy qua.
And the way SQL Server does it, and that'll be the top-down search we'll see in a second, they know all the, as they go along, they're sort of incrementally applying rules and you just keep count of how many they've applied.
Còn cách SQL Server làm, và đó sẽ là tìm kiếm từ trên xuống mà chúng ta sắp thấy, họ biết tất cả, khi đi dần, họ áp dụng các quy tắc theo kiểu tăng dần và bạn chỉ cần đếm xem họ đã áp dụng bao nhiêu.
If they exhaust it, you at least need to get to the bottom of the search tree so you have at least one query plan that you can actually then run.
Nếu họ dùng hết số lượng đó, thì ít nhất bạn cũng cần đi tới đáy của cây tìm kiếm để có ít nhất một kế hoạch truy vấn mà bạn thực sự có thể chạy.
But at least no matter whether you're running on a machine that's fully utilized or underutilized, you'll always produce the same query plan.
Nhưng ít nhất, dù bạn đang chạy trên một máy được sử dụng hết công suất hay nhàn rỗi, bạn sẽ luôn tạo ra cùng một kế hoạch truy vấn.
All right, so the first thing we want to do is figure out, one of the things we have to do is apply transformation rules to figure out how we're actually going to access the data on our underlying tables.
Được rồi, việc đầu tiên chúng ta muốn làm là tìm ra, một trong những việc phải làm là áp dụng các quy tắc biến đổi để xác định chúng ta sẽ thực sự truy cập dữ liệu trên các bảng bên dưới như thế nào.
And this could be through a combination of things that we'll see in the next class. But we want to look at all the different choices that we have for accessing our table.
Và điều này có thể thực hiện bằng một tổ hợp các thứ mà chúng ta sẽ thấy ở buổi học tới. Nhưng chúng ta muốn xem xét tất cả các lựa chọn khác nhau mà chúng ta có để truy cập bảng.
And a transformation rule could convert things like get table foo, or scan table foo, however you want to define it, and it can convert that into a physical operator that either does a sequential scan, or an index scan, or a multi-index scan that we talked about last time.
Và một quy tắc biến đổi có thể chuyển những thứ như get table foo, hay scan table foo, tùy bạn định nghĩa, thành một toán tử vật lý thực hiện quét tuần tự, hoặc quét chỉ mục, hoặc quét đa chỉ mục mà chúng ta đã nói lần trước.
So it'd look at the catalog, look at the statistical information, and it could say, "Here's all the choices I have for accessing this data."
Nên nó sẽ xem danh mục, xem thông tin thống kê, và có thể nói: "Đây là tất cả các lựa chọn tôi có để truy cập dữ liệu này."
And then it applies transformation rules to convert that logical scan operator into the different physical operators. And this is just repeating what I've already said.
Rồi nó áp dụng các quy tắc biến đổi để chuyển toán tử quét logic đó thành các toán tử vật lý khác nhau. Và đây chỉ là lặp lại những gì tôi đã nói.
But again, we look at all the things we have, the way to access data, and we just try out different combinations of them based on what our rules are allowed to do.
Nhưng một lần nữa, chúng ta xem tất cả những gì mình có, các cách truy cập dữ liệu, và thử các tổ hợp khác nhau của chúng dựa trên những gì các quy tắc của mình cho phép.
At the end of the day, if we have no index we could use, because the predicates don't match on it, or it's a hash index and we want to do a less than or greater than, at the end of the day, no matter what, we can always convert a logical scan operator on a table into a physical sequential scan.
Rốt cuộc, nếu chúng ta không có chỉ mục nào để dùng, vì các vị từ không khớp với nó, hoặc đó là hash index và ta muốn so sánh nhỏ hơn hoặc lớn hơn, thì cuối cùng, dù thế nào đi nữa, ta luôn có thể chuyển một toán tử scan logic trên một bảng thành một sequential scan vật lý.
Like, that's the fallback choice. And it could be the slowest, but it's something we can always rely on. For simple queries, they're what is known as, called, Sargable.
Tức là, đó là lựa chọn dự phòng. Nó có thể chậm nhất, nhưng là thứ ta luôn có thể dựa vào. Với các truy vấn đơn giản, chúng được gọi là Sargable.
This is a database term. It just means search argument able. It comes from the 80s.
Đây là một thuật ngữ cơ sở dữ liệu. Nó chỉ có nghĩa là search argument able. Nó có từ những năm 80.
It basically just says, it's like, I can have a transformation rule that looks at my scan operator, looks at my predicate, and then looks in the catalog and says, "Here's an index that I could use for this predicate here," and I can just convert the logical scan operator into a physical operator on that index.
Về cơ bản nó nói rằng, tôi có thể có một quy tắc biến đổi xem xét toán tử scan của mình, xem vị từ của mình, rồi tra trong catalog và nói rằng, "Đây là một index mà tôi có thể dùng cho vị từ này," và tôi có thể chuyển toán tử scan logic thành một toán tử vật lý trên index đó.
And it seems kind of obvious that you can always just do this. You can always just look.
Nghe có vẻ hiển nhiên là lúc nào cũng làm được như vậy. Lúc nào cũng chỉ cần tra là được.
It's like, "Oh, I definitely need to access this data, and I need to, or I want to be sorted on whatever this column is."
Kiểu như, "Chắc chắn tôi cần truy cập dữ liệu này, và tôi cần, hoặc tôi muốn nó được sắp xếp theo cột này."
But a lot of these systems choke up on this, or I may decide, even though I have the index in a call space transformation, that I don't actually even want to apply it, because it's just better to do a sequential scan.
Nhưng nhiều hệ thống bị vấp ở chỗ này, hoặc tôi có thể quyết định, dù có index trong một phép biến đổi dựa trên chi phí, là tôi thực ra không muốn áp dụng nó, vì làm sequential scan lại tốt hơn.
So let's do a quick demo of that. All right, let me log in.
Ta làm một demo nhanh về việc đó. Được rồi, để tôi đăng nhập.
So I pre-populated some data in Postgres. I think it's 10 million rows, which is a bunch of random information.
Tôi đã nạp sẵn một ít dữ liệu vào Postgres. Tôi nghĩ là 10 triệu dòng, toàn thông tin ngẫu nhiên.
Right, there's a primary key called id, and then a value, just a random integer. And I think I have, I populated 10 million.
Có một khóa chính tên là id, và một cột value, là một số nguyên ngẫu nhiên. Và tôi nghĩ là tôi có, tôi đã nạp 10 triệu.
Yeah, OK. So I've created an index on the value column, right? So in the bottom here, I created a B+tree index.
Vâng, được rồi. Tôi đã tạo một index trên cột value, đúng không? Ở phía dưới này, tôi đã tạo một B+tree index.
You always have one on the primary key, and I also created a B+tree index on the value column.
Lúc nào cũng có một index trên khóa chính, và tôi cũng tạo một B+tree index trên cột value.
So without running the queries, again, we can put the explain keyword in front of our query, and this will give us the query plan here, right?
Vậy nên, không cần chạy các truy vấn, một lần nữa, ta có thể đặt từ khóa explain trước truy vấn, và nó sẽ cho ta kế hoạch truy vấn ở đây, đúng không?
So here I'm doing a select star, select id from the xxx table, where value is greater than or equal to 1, 2, 3, and value is less than 4, 5, 6.
Ở đây tôi đang chạy select star, select id từ bảng xxx, với value lớn hơn hoặc bằng 1, 2, 3, và value nhỏ hơn 4, 5, 6.
And in this case here, Postgres decides that, yes, I want to use the index on the value column, and instead of doing a sequential scan.
Và trong trường hợp này, Postgres quyết định rằng, vâng, tôi muốn dùng index trên cột value, thay vì làm một sequential scan.
Likewise, if I do a lookup like this, I want to do a select star from the table, order by the value column, and give me the top 20 values, right?
Tương tự, nếu tôi tra cứu thế này, tôi muốn select star từ bảng, order by cột value, và cho tôi 20 giá trị đầu, đúng không?
In this case here, Postgres recognizes, again, I have an index on the value column, and the data is going to be sorted the way I want.
Trong trường hợp này, Postgres nhận ra, một lần nữa, là tôi có index trên cột value, và dữ liệu sẽ được sắp xếp đúng như tôi muốn.
So it's allowed to go ahead and use that. Let's see if it finds me. No, it didn't find me. OK, but Postgres' optimizer is dumb.
Nên nó được phép dùng index đó. Xem nó có tìm thấy tôi không. Không, nó không tìm thấy tôi. Được rồi, nhưng trình tối ưu hóa của Postgres thì ngốc.
Let's look at this query. What am I doing? Same query as above. Give me the top 20 values. But in my order by clause, I put value plus 0. Value is an integer column.
Hãy xem truy vấn này. Tôi đang làm gì đây? Cùng truy vấn như ở trên. Lấy cho tôi 20 giá trị đầu. Nhưng trong mệnh đề order by, tôi viết value cộng 0. Value là một cột số nguyên.
That means if you add 0 to it, it's the same value, right?
Nghĩa là nếu cộng thêm 0 thì vẫn ra cùng giá trị, đúng không?
Well, I've already told you what it's going to have. I'm going to say, let's vote, see whether Postgres picks the index or not. But I already told you it's stupid, and it doesn't, Right?
Thì tôi đã nói cho bạn biết nó sẽ có gì rồi. Giờ ta cùng bỏ phiếu xem Postgres có chọn index hay không. Nhưng tôi đã nói là nó ngốc rồi, và nó không chọn, đúng không?
So this seems, as humans, you look at this and say, well, clearly, plus 0, I can just drop that, because I know it's an integer, right?
Là con người, nhìn cái này bạn sẽ nói, rõ ràng là cộng 0 thì bỏ đi được, vì tôi biết nó là số nguyên, đúng không?
I think, and if I go back correctly, I made the column.
Tôi nghĩ, nếu tôi nhớ đúng thì lúc tạo cột đó, tôi đã không khai báo not null. Có lẽ vì thế, đúng không?
I didn't make it not null. Maybe that's why, right? But it could look at its statistics and recognize that I don't have any null values, right, in its cost model.
Nhưng nó có thể xem thống kê của mình và nhận ra là không có giá trị null nào cả, trong mô hình chi phí của nó.
But it can't do that, right? So if I, let's see, I doubt it'll even do that. So if I drop the table, this should go fast.
Nhưng nó không làm được như vậy, đúng không? Để xem, tôi nghi là nó cũng không làm thế đâu. Nếu tôi xóa bảng, việc này sẽ chạy nhanh.
I add it back. And here, now, I'm going to say the value is not null.
Tôi tạo lại nó. Và lần này tôi khai báo value là not null.
And let me go generate some, this query here is the insert into that just generates, generates series, makes a bunch of values. And I'm going to insert that into the table.
Rồi tôi sẽ tạo một ít dữ liệu, truy vấn này là câu insert into chỉ để sinh ra, dùng generate series, tạo ra một loạt giá trị. Và tôi sẽ chèn chúng vào bảng.
It only takes a few seconds, in theory. There it goes here.
Về lý thuyết chỉ mất vài giây. Xong rồi đây.
All right, so now, and let me add now the index on that column. Should take a few seconds.
Được rồi, bây giờ tôi thêm index trên cột đó. Sẽ mất vài giây.
And now, I go, there's the first query without the plus zero. And it's able to figure out that I choose the index.
Và bây giờ, đây là truy vấn đầu tiên, không có cộng không. Và nó nhận ra được là tôi chọn index.
And this is here, even though it's not null, it can't use the index. Now, we'll talk about analyze next class. But that's basically a way for it to collect statistics about the table.
Còn ở đây, dù cột là not null, nó vẫn không dùng được index. Buổi sau chúng ta sẽ nói về analyze. Về cơ bản đó là cách để nó thu thập thống kê về bảng.
In this case here, it has all the statistics it needs. And it still can't pick the index. Yes.
Trong trường hợp này, nó có đủ mọi thống kê cần thiết. Vậy mà nó vẫn không chọn index. Vâng, mời bạn.
The question is, why does it think the Scratch plan has a lower cost than what? Let's see. So here's the first one. And here's the second one.
Câu hỏi là, tại sao nó nghĩ kế hoạch Scratch có chi phí thấp hơn kế hoạch kia? Để xem. Đây là cái đầu tiên. Và đây là cái thứ hai.
Right, so you're saying for which one? So which one, for which operator? Each operator has its own cost, right?
Vậy bạn đang nói về cái nào? Toán tử nào? Mỗi toán tử có chi phí riêng, đúng không?
Why is one of the top smaller than this one? Because this is reading all the data. Yeah, so what I'm saying, the query is order by value plus zero.
Tại sao một cái ở trên lại nhỏ hơn cái này? Vì cái này đọc toàn bộ dữ liệu. Vâng, ý tôi là truy vấn có order by value cộng không.
As a human, you know any integer plus zero is the same value. So that plus zero means nothing. Postgres sees that and says, "Oh, I can't do this because it can't match."
Là con người, bạn biết số nguyên nào cộng không cũng ra cùng giá trị. Nên cộng không chẳng có nghĩa gì. Postgres thấy vậy và nói: "Ồ, tôi không làm được vì không khớp được."
It's trying to do a string match on the name of the column. And if it sees any expression with a plus zero, it doesn't pick the index.
Nó đang cố so khớp chuỗi với tên của cột. Và nếu thấy biểu thức nào có cộng không, nó không chọn index.
The statement is, no matter how many, no matter what, like plus zero times one, right, like plus 1,000, it should just always use the index?
Ý của bạn là, dù thế nào đi nữa, như cộng không nhân một, hay cộng 1.000, thì nó cũng nên luôn dùng index?
It doesn't.
Nó không làm vậy.
The statement is, if I need to, if I want to do an expression in my, yes. Yes, do it in a printable way. Yes, they're not.
Câu hỏi là, nếu tôi cần, nếu tôi muốn dùng một biểu thức trong truy vấn của mình, vâng. Vâng, làm theo cách có thể in ra được. Vâng, chúng không phải vậy.
Because the operator says, "Oh, I can't, it's not an exact match. I can't do it." The statement is, partial evaluation is hard. Why? Not many what?
Vì toán tử nói: "Ồ, tôi không thể, đây không phải khớp chính xác. Tôi không làm được." Vấn đề là, đánh giá một phần rất khó. Tại sao? Không nhiều cái gì cơ?
Data as compilers or compiler to compiler? Data as could do it. I don't have a SQL Server running, but SQL Server handles this, no problem.
Data as là trình biên dịch hay từ trình biên dịch sang trình biên dịch? Data as có thể làm được. Tôi không có SQL Server đang chạy, nhưng SQL Server xử lý chuyện này rất ổn.
But that's like, SQL Server's fit. I wish I could get it working. I don't have it working. Yeah, I was rushing this. I didn't get it to work.
Nhưng đó là chuyện của SQL Server thôi. Ước gì tôi cho nó chạy được. Tôi chưa cho nó chạy được. Vâng, tôi làm vội quá nên không chạy được.
But let me try, let's try DuckDB.
Nhưng để tôi thử, ta thử DuckDB.
Statement is, plus one might overflow, yes.
Câu hỏi là, cộng một có thể gây tràn số, vâng.
But if you have statistical information about your queries, or so your data, you could say no value is greater than whatever the upper limit or even close to it.
Nhưng nếu bạn có thông tin thống kê về các truy vấn của mình, hoặc về dữ liệu của bạn, bạn có thể nói không giá trị nào lớn hơn giới hạn trên, thậm chí không gần tới giới hạn đó.
So therefore, it's safe for me to do it. Now, your statistics might be wrong, and therefore, you're very conservative about it, yes.
Vì vậy, tôi làm điều đó là an toàn. Tuy nhiên, thống kê của bạn có thể sai, nên bạn phải rất thận trọng về chuyện này, vâng.
But you don't need that for, like, you could still do the order by. And again, because you know, like, if it's just like plus something, right?
Nhưng bạn không cần điều đó, bạn vẫn có thể thực hiện order by. Và một lần nữa, vì bạn biết, nếu chỉ là cộng thêm một giá trị nào đó, đúng không?
Like the, how does this?
Như là, chuyện này hoạt động thế nào?
Actually, I don't know what they would do if for the, I don't know, I actually don't know how they would handle the overflow if you do the projection after the fact.
Thật ra, tôi không biết họ sẽ làm gì nếu, tôi không rõ, tôi thật sự không biết họ sẽ xử lý tràn số thế nào nếu bạn thực hiện phép chiếu sau đó.
Because it's still technically the largest. But it's still, you might throw an error. I don't know. All right, now you get into, like, semantics of SQL. Like, does it round or not round, right?
Vì về mặt kỹ thuật nó vẫn là giá trị lớn nhất. Nhưng bạn vẫn có thể gặp lỗi. Tôi không biết. Được rồi, giờ ta đi vào ngữ nghĩa của SQL. Ví dụ, nó làm tròn hay không làm tròn, đúng không?
And that's, rounding gets weird.
Và đó là, làm tròn khá kỳ quặc.
Now we're getting into a rabbit hole. Hold on. So I have, like, say, I have 4.5, say 4.2, right? If I cast that to an int, what number should I get?
Giờ ta sa vào một cái hố sâu rồi. Khoan đã. Giả sử tôi có 4.5, à giả sử 4.2, đúng không? Nếu tôi ép kiểu nó sang int, bạn sẽ nhận được số nào?
Who says, raise your hand if you say 4. Raise your hand if you say 5. Raise your hand if you say throw an error. There's an error, right?
Ai nghĩ là 4 thì giơ tay. Ai nghĩ là 5 thì giơ tay. Ai nghĩ là báo lỗi thì giơ tay. Có lỗi, đúng không?
So what if I do that? Doesn't like that. What about this? Takes 4. All right, let's try DuckDB.
Vậy nếu tôi làm thế này thì sao? Nó không chịu. Còn cái này? Ra 4. Được rồi, ta thử DuckDB.
So select 4.2, cast it as an int. All right, raise your hand if you say an error. Raise your hand if you say 4. Raise your hand if you say 5. 4.
Vậy select 4.2, ép kiểu thành int. Được rồi, ai nghĩ là lỗi thì giơ tay. Ai nghĩ là 4 thì giơ tay. Ai nghĩ là 5 thì giơ tay. Ra 4.
All right, let's try 4.8. Raise your hand if it's not an error. Say, raise your hand if you say 4. Raise your hand if you say 5.
Được rồi, thử 4.8. Ai nghĩ là không báo lỗi thì giơ tay. Ai nghĩ là 4 thì giơ tay. Ai nghĩ là 5 thì giơ tay.
5, right? But we did this in Postgres and showed an error, right? Firebolt might work, too, because I think it uses the Postgres parser.
Ra 5, đúng không? Nhưng ta làm việc này trong Postgres thì báo lỗi, đúng không? Firebolt có thể cũng chạy được, vì tôi nghĩ nó dùng trình phân tích cú pháp của Postgres.
I don't know if this is going to work. 4.2. No, it doesn't like that.
Tôi không biết cái này có chạy không. 4.2. Không, nó không chịu.
That colon, colon, colon, and then what the type is, that's a Postgres idiom that DuckDB picked up in Postgres.
Dấu hai chấm, hai chấm, hai chấm, rồi đến tên kiểu dữ liệu, đó là một cách viết quen thuộc của Postgres mà DuckDB đã tiếp nhận từ Postgres.
So select 4.2, cast 4.2 as integer.
Vậy select 4.2, cast 4.2 as integer.
What am I doing wrong?
Mình đang làm sai chỗ nào vậy?
No, no, like that. So can't cast, and I forget, is this the one that's signed?
Không, không, như thế này cơ. Vậy là không cast được, mà mình quên rồi, cái này là kiểu có dấu phải không?
It might be MySQL. Ah, it restarted, sorry. All right, I forgot the point of this.
Có thể là MySQL. À, nó khởi động lại rồi, xin lỗi. Được rồi, mình quên mất mục đích của việc này là gì.
Actually, I want to show something to DuckDB real quick. So DuckDB, I've created the same table, and I can run the same queries as before, right?
Thực ra, mình muốn cho các bạn xem nhanh một thứ trên DuckDB. Đây là DuckDB, mình đã tạo cùng một bảng, và mình có thể chạy các truy vấn giống như trước, đúng không?
And even though I had an index on this table, It decides to still do a sequential scan, right?
Và dù mình có một chỉ mục trên bảng này, nó vẫn quyết định làm sequential scan, đúng không?
Now if I do this, the one query we had before, again, give me the top 20 values after ordering by. Who says it's going to use the index? Raise your hand. Very few.
Giờ nếu mình chạy cái này, truy vấn mà ta đã có trước đó, một lần nữa, lấy cho tôi 20 giá trị đầu sau khi sắp xếp. Ai nghĩ nó sẽ dùng chỉ mục? Giơ tay lên. Rất ít người.
Who says it's going to do a sequential scan? I tricked you. You're all wrong. It's going to do two sequential scans.
Ai nghĩ nó sẽ làm sequential scan? Mình lừa các bạn rồi. Tất cả đều sai. Nó sẽ làm hai lần sequential scan.
All right, that's kind of hard to see, but I'll just scroll up. So what is it doing?
Được rồi, hơi khó nhìn, nhưng mình sẽ cuộn lên. Vậy nó đang làm gì?
It's doing a sequential scan once on the side here, so on the one side, and it's going to get the top N values of that, and then it builds a hash join, and then scans the table again, and joins it with itself, and finds all the matches.
Nó quét tuần tự một lần ở phía này, tức là ở một bên, và lấy ra top N giá trị của phần đó, rồi xây dựng một hash join, và quét bảng lần nữa, join nó với chính nó, và tìm tất cả các kết quả khớp.
And again, according to DuckDB's cost model, this says it's just faster to do that. So no matter what I put here, I put a plus zero, right?
Và một lần nữa, theo mô hình chi phí của DuckDB, làm như vậy đơn giản là nhanh hơn. Nên dù mình đặt gì ở đây, kể cả cộng thêm không, đúng không?
It's still going to pick the same thing. And if I actually run it, as we saw before, although this is running parallel queries, like, it can rip through this in, what is that?
Nó vẫn sẽ chọn cùng một kế hoạch. Và nếu mình chạy thật, như đã thấy trước đó, dù nó đang chạy các truy vấn song song, nó có thể xử lý xong trong, đó là bao nhiêu nhỉ?
0.01, 10 milliseconds, whereas Postgres will take, you know, almost a second.
0,01, 10 mili giây, trong khi Postgres sẽ mất, bạn biết đấy, gần một giây.
All right, this is a sequential scan. If I give it this, it's still slow.
Được rồi, đây là một sequential scan. Nếu mình cho nó cái này, nó vẫn chậm.
Yeah, saving is, I'm comparing between ColumnStore and RowStore. Yeah, I didn't say it was a fair comparison. I'm just saying that, like, saving is, what if I forced DuckDB to use it?
Vâng, ý bạn là mình đang so sánh giữa ColumnStore và RowStore. Vâng, mình đâu có nói đó là một so sánh công bằng. Mình chỉ muốn nói là, nếu mình ép DuckDB dùng chỉ mục thì sao?
I don't know if they queried by nits, I forget. I think it might, I don't know. I know I did it in Postgres and other things.
Mình không biết nó có truy vấn theo nits không, mình quên rồi. Có thể là có, mình không biết. Mình biết là mình đã làm điều đó trong Postgres và các hệ khác.
All right, sorry, that was, I love demos, I love SQL. All right, let's see if we get this to work again, or not.
Được rồi, xin lỗi, mình thích demo, mình thích SQL. Được rồi, xem thử lần nữa có chạy được không nhé.
Whatever, if it finds me, it finds me. Whatever, all right, cool.
Sao cũng được, nếu nó chạy thì chạy. Thôi, được rồi, tuyệt.
All right, the thing I want to get into, again, that's important, is understand, is there's, for a cost-based search, there's, let's Do that one at the end.
Được rồi, điều mình muốn đi vào, một lần nữa, rất quan trọng, là hiểu rằng có, đối với tìm kiếm dựa trên chi phí, có, để mình để cái đó lại đến cuối.
Question is, which one's the least, worst one? The Germans have the best one, Umbra. DuckDB copied what Umbra did, but actually, they didn't copy from Umbra. They copied from the first German system, Hyper.
Câu hỏi là, cái nào ít tệ nhất? Người Đức có cái tốt nhất, Umbra. DuckDB sao chép những gì Umbra làm, nhưng thực ra họ không sao chép từ Umbra. Họ sao chép từ hệ thống đầu tiên của Đức, Hyper.
The Umbra one has a bunch of other stuff, and they write about it in papers, that blows DuckDB out of the water. But that one's not open source, and it's commercialized as CedarDB.
Bản của Umbra còn có một loạt thứ khác, và họ viết về nó trong các bài báo, nó vượt xa DuckDB. Nhưng hệ thống đó không phải mã nguồn mở, và nó được thương mại hóa thành CedarDB.
Umbra has the best bottom-up one. SQL Server has the best top-down one.
Umbra có bộ tối ưu bottom-up tốt nhất. SQL Server có bộ tối ưu top-down tốt nhất.
The theory, I think, shows the bottom one is actually better than top-down. Top-down has other advantages that we'll cover later.
Theo tôi, lý thuyết cho thấy bottom-up thực ra tốt hơn top-down. Top-down có những ưu điểm khác mà chúng ta sẽ nói sau.
All right, so there's two ways to implement your query optimizer, when you do the search, and when you start looking at multiple relations. Again, bottom-up or top-down.
Được rồi, vậy có hai cách để hiện thực bộ tối ưu truy vấn của bạn, khi bạn thực hiện tìm kiếm, và khi bạn bắt đầu xét nhiều quan hệ. Một lần nữa, bottom-up hoặc top-down.
So in bottom-up, the idea is that you start with nothing. You have nothing in your query plan. You just have what the leaves of the query plan are.
Với bottom-up, ý tưởng là bạn bắt đầu từ con số không. Trong kế hoạch truy vấn của bạn chưa có gì cả. Bạn chỉ có các nút lá của kế hoạch truy vấn.
And then you build it up incrementally to get to the final outcome that you want. In a top-down optimizer, you start with the final result that you want.
Rồi bạn xây dựng dần từng bước để đến kết quả cuối cùng mà bạn muốn. Với bộ tối ưu top-down, bạn bắt đầu từ kết quả cuối cùng mà bạn muốn.
Like, I want to produce the join of this, this, and this, whatever sort of, I, whatever is in my query plan, in my query.
Kiểu như, tôi muốn tạo ra phép join của cái này, cái này và cái này, bất kể là gì, bất kể có gì trong kế hoạch truy vấn, trong truy vấn của tôi.
And then I traverse down, search down the query plan, adding the operators I need to get me to that result until I reach the leaf nodes.
Rồi tôi đi xuống, tìm kiếm xuống dưới kế hoạch truy vấn, thêm các toán tử cần thiết để đạt được kết quả đó cho đến khi chạm tới các nút lá.
Again, me sitting with my hands making little finger gestures doesn't mean anything. So let's look at examples, see what I'm talking about.
Một lần nữa, việc tôi ngồi đây vung tay làm các cử chỉ ngón tay nhỏ cũng chẳng có ý nghĩa gì. Vậy hãy xem các ví dụ để thấy tôi đang nói về điều gì.
For now, for all these examples, we're going to have two distinctions between our operators and our query plan.
Hiện tại, trong tất cả các ví dụ này, chúng ta sẽ phân biệt hai loại giữa các toán tử và kế hoạch truy vấn.
We'll have the light gray one be logical operators, and then the darker ones be the physical operators. All right, so bottom-up. We start with the bottom of this, leaf nodes.
Màu xám nhạt là các toán tử logic, còn màu đậm hơn là các toán tử vật lý. Được rồi, bottom-up. Ta bắt đầu từ đáy, các nút lá.
I want to scan artist, I want to scan appears, and then eventually I want to get into the artist-appears join output.
Tôi muốn quét artist, tôi muốn quét appears, và cuối cùng tôi muốn có kết quả đầu ra của phép join artist-appears.
So what I would do is I start from the bottom, and I look at, apply my transformation rules and say, here's all the choices I would have as I go up the query plan until I reach my final destination.
Vậy tôi sẽ bắt đầu từ dưới lên, áp dụng các quy tắc biến đổi và nói rằng, đây là tất cả các lựa chọn tôi có khi đi lên trong kế hoạch truy vấn cho đến khi tới đích cuối cùng.
And whatever path to that final destination at the top has the lowest cost, that's my optimal plan, and I choose that.
Và đường đi nào đến đích ở trên cùng có chi phí thấp nhất, đó là kế hoạch tối ưu của tôi, và tôi chọn nó.
In top-down or backward chaining, you start at the very top here, and you say, well, what do I need to do to get down to the leaf nodes?
Với top-down hay suy diễn lùi, bạn bắt đầu từ trên cùng ở đây, và tự hỏi, tôi cần làm gì để đi xuống các nút lá?
So first thing, I have my artist appears, I apply this first choice, and because now I need to at least get to the leaf nodes once so I can at least have some query plan, I would do basically a depth-first search, going down one side of the query plan, get down to this leaf node, look at all my possible choices, get down, and then come back up and look down this path and look at all my possible choices.
Đầu tiên, tôi có artist appears, tôi áp dụng lựa chọn đầu tiên này, và vì giờ tôi cần ít nhất chạm tới các nút lá một lần để ít nhất có một kế hoạch truy vấn nào đó, về cơ bản tôi sẽ thực hiện tìm kiếm theo chiều sâu, đi xuống một phía của kế hoạch truy vấn, xuống đến nút lá này, xem tất cả các lựa chọn có thể, đi xuống, rồi quay lên và xem xuống nhánh này, xem tất cả các lựa chọn có thể.
And then I end up with the final result for my query. Again, let me go through more details of these.
Và cuối cùng tôi có kết quả cuối cùng cho truy vấn của mình. Một lần nữa, để tôi đi qua chi tiết hơn về những cách này.
This is the high level, the two distinctions that we're going to have in our implementations. And if you're coming from the sort of a classical optimization world, it's backward chaining versus forward chaining.
Đây là mức tổng quan, hai cách phân biệt mà chúng ta sẽ có trong các hiện thực của mình. Và nếu bạn đến từ thế giới tối ưu hóa cổ điển, thì đó là suy diễn lùi so với suy diễn tiến.
All right, let me skip this. This is basically saying that if there's patterns you can recognize in your query where you know that it's a query of a certain category.
Được rồi, để tôi bỏ qua cái này. Về cơ bản, điều này nói rằng nếu có những mẫu mà bạn nhận ra được trong truy vấn của mình mà bạn biết đó là một truy vấn thuộc một loại nhất định.
Like when we talk about Snowflake schemas and star schemas, if you know it's going to be like, I have a single fact table and a bunch of dimension tables, then you don't even bother doing a full search.
Ví dụ khi nói về Snowflake schema và star schema, nếu bạn biết nó sẽ giống như, tôi có một bảng fact duy nhất và một loạt bảng dimension, thì bạn thậm chí không cần bận tâm đến việc tìm kiếm toàn bộ.
You just sort of bootstrap it with a planned structure they think is close to the optimal, and you start to search from there, again, rather than starting from scratch.
Bạn chỉ cần khởi tạo nó bằng một cấu trúc kế hoạch mà bạn cho là gần với tối ưu, và bắt đầu tìm kiếm từ đó, một lần nữa, thay vì bắt đầu từ con số không.
All right, so bottom-up optimization.
Được rồi, vậy là tối ưu hóa từ dưới lên.
We're going to do a bunch of static rules that we had at the beginning to do this initial optimization, and then we're going to use dynamic programming, which I realize I shouldn't rush through in the last six minutes, but let me get through the bottom-up, and we'll come back to top-down next class.
Chúng ta sẽ áp dụng một loạt quy tắc tĩnh mà ta có ở đầu buổi để thực hiện bước tối ưu hóa ban đầu này, rồi sau đó sẽ dùng quy hoạch động, mà tôi nhận ra là không nên vội vàng lướt qua trong sáu phút cuối, nhưng cứ để tôi đi hết phần từ dưới lên, còn phần từ trên xuống sẽ quay lại ở buổi sau.
All right, so you're going to do dynamic programming, which is divide and conquer.
Được rồi, bạn sẽ dùng quy hoạch động, tức là chia để trị.
Start looking at the different choices you have going up the query plan, and you work your way up to the top.
Bắt đầu xem xét các lựa chọn khác nhau khi đi lên trong kế hoạch truy vấn, và bạn đi dần lên đến đỉnh.
The very first bottom-up query optimizer, the first cost-based query optimizer ever, was IBM's System R.
Bộ tối ưu hóa truy vấn từ dưới lên đầu tiên, cũng là bộ tối ưu hóa truy vấn dựa trên chi phí đầu tiên từ trước đến nay, là System R của IBM.
And basically what they do is they break up the query plan into these blocks, like sort of subplans, and they would optimize them, and they would sort of stitch the blocks back together to produce the final result that they would want.
Về cơ bản, họ chia kế hoạch truy vấn thành các khối, kiểu như các kế hoạch con, rồi tối ưu hóa từng khối, và sau đó ghép các khối lại với nhau để tạo ra kết quả cuối cùng mà họ muốn.
Because it was the 1970s, computer hardware was very limited, not a lot of memory, and single core, very weak CPUs.
Vì đó là những năm 1970, phần cứng máy tính rất hạn chế, không có nhiều bộ nhớ, chỉ một lõi, CPU rất yếu.
They had to do a bunch of simple optimizations and throw away results to reduce the search space to make the problem more tractable.
Họ phải thực hiện một loạt tối ưu hóa đơn giản và loại bỏ bớt kết quả để thu hẹp không gian tìm kiếm, làm cho bài toán dễ giải quyết hơn.
So one of the design decisions they made is that they would only consider left-deep trees, and they would never look at right-deep trees or bushy trees.
Vì vậy, một trong những quyết định thiết kế của họ là chỉ xét các cây left-deep, và không bao giờ xét cây right-deep hay cây bushy.
So a left-deep tree basically says, I'm going to join two tables A and B, and whatever the output of that is, I'm going to join with the next table.
Cây left-deep về cơ bản nghĩa là: tôi kết hai bảng A và B, và kết quả đầu ra của phép đó, tôi sẽ kết với bảng tiếp theo.
And whatever the output of that, I'm going to join with the next table. It's left-deep because it's going up on one side of the query plan.
Và đầu ra của phép đó, tôi lại kết với bảng tiếp theo. Gọi là left-deep vì nó phát triển lên về một phía của kế hoạch truy vấn.
Rather than have this example we had before, I could join A and B, and then join C and D, and then take the output of those two joins, and then join them together.
Thay vì như ví dụ trước đây, tôi có thể kết A với B, rồi kết C với D, sau đó lấy đầu ra của hai phép kết đó rồi kết chúng với nhau.
So System R is not going to do any of that.
System R sẽ không làm bất kỳ điều nào như vậy.
Some systems, I think Postgres still does this today, like they won't support bushy joins in their optimizer, again, just to reduce the search space.
Một số hệ thống, tôi nghĩ Postgres ngày nay vẫn vậy, không hỗ trợ phép kết bushy trong bộ tối ưu hóa của chúng, một lần nữa, chỉ để thu hẹp không gian tìm kiếm.
All right.
Được rồi.
So the way it would work is you first look at all your leaf nodes in your query plan, all your access methods, and you apply simple heuristics to say, which of the best choices based on what I have in my catalog?
Cách nó hoạt động là trước tiên bạn xem xét tất cả các nút lá trong kế hoạch truy vấn, tất cả các phương thức truy cập, và áp dụng các heuristic đơn giản để xác định lựa chọn nào tốt nhất dựa trên những gì tôi có trong catalog?
Then you're going to apply transformation rules to enumerate all possible join orderings you would have for your table, and then you figure out which one is going to have the lowest cost.
Sau đó bạn áp dụng các quy tắc biến đổi để liệt kê tất cả các thứ tự kết có thể có cho các bảng của bạn, rồi bạn xác định xem phương án nào có chi phí thấp nhất.
This diagram doesn't mean anything, so let's look at the tree structure. So again, I start at the beginning.
Sơ đồ này chẳng có ý nghĩa gì, nên hãy xem cấu trúc cây. Vậy là, một lần nữa, tôi bắt đầu từ đầu.
I would figure out all the different ways I could access these three tables, artist, album, and appears.
Tôi sẽ xác định tất cả các cách khác nhau để truy cập ba bảng này, artist, album và appears.
And then once I have that, now I'm going to figure out what's the join order I want to use, what path I want to get up to my final outcome where I join artist, appears, and album.
Và khi đã có điều đó, bây giờ tôi sẽ xác định thứ tự join mà tôi muốn dùng, con đường nào để đi tới kết quả cuối cùng, nơi tôi join artist, appears, và album.
So in the first level of the tree search, I would look at all possible combinations of joining these three different tables here. Now I'm looking at the physical operator.
Vậy ở tầng đầu tiên của việc tìm kiếm trên cây, tôi sẽ xem xét mọi tổ hợp có thể khi join ba bảng khác nhau này. Bây giờ tôi đang xét các toán tử vật lý.
So I'm going to join hash, hash join on artist and appears, sort-merge join on artist and appears, and so forth.
Vậy tôi sẽ có hash join giữa artist và appears, sort-merge join giữa artist và appears, và cứ thế.
And obviously, this doesn't fit in PowerPoint, so imagine it's all possible combinations going here on the other side.
Rõ ràng là cái này không vừa trong PowerPoint, nên hãy tưởng tượng tất cả các tổ hợp có thể nằm ở phía bên kia.
Then I invoke the cost model and say, OK, all these different physical operators that I have, which path going up to the next logical operators in the tree, which one of each of those have the lowest cost?
Sau đó tôi gọi mô hình chi phí và nói, được rồi, trong tất cả các toán tử vật lý khác nhau mà tôi có, đường đi lên các toán tử logic tiếp theo trong cây, đường nào trong số đó có chi phí thấp nhất?
And I'm going to throw away the ones that don't have the highest cost. All right, best cost and lowest cost, depending on what you're trying to minimize or maximize for.
Và tôi sẽ loại bỏ những đường không có chi phí tốt nhất. Được rồi, chi phí tốt nhất hay chi phí thấp nhất, tùy vào việc bạn đang cố cực tiểu hóa hay cực đại hóa điều gì.
And then I do the same thing again. I look at all possible join orders for the next two tables in the query plan.
Rồi tôi lại làm điều tương tự. Tôi xem xét mọi thứ tự join có thể cho hai bảng tiếp theo trong kế hoạch truy vấn.
So taking the output of artist and appears, and I want to join it with album. So I look at the hash join, look at the merge join.
Lấy đầu ra của artist và appears, và tôi muốn join nó với album. Tôi xem hash join, xem merge join.
I could look at nested loop join if I wanted. I have more space in PowerPoint. I look at all those possible combinations.
Tôi cũng có thể xem nested loop join nếu muốn. Tôi còn chỗ trong PowerPoint. Tôi xem xét tất cả các tổ hợp có thể đó.
And then same thing, I pick for each path, which one everyone has the lowest cost.
Rồi tương tự, với mỗi đường đi, tôi chọn cái nào có chi phí thấp nhất.
Then I look now for all the paths from the bottom, the starting point, to the top, which path has the global lowest cost.
Sau đó tôi xét tất cả các đường đi từ dưới cùng, điểm xuất phát, lên đến đỉnh, đường nào có chi phí thấp nhất toàn cục.
And that's the one I want to end up with at the end. It's just dynamic programming.
Và đó là cái tôi muốn có ở cuối cùng. Đó chỉ là quy hoạch động.
It means you're dividing up by looking at one bubble at a time rather than looking at all possible join orderings at the same time.
Nghĩa là bạn chia nhỏ bài toán bằng cách xét từng bong bóng một thay vì xét tất cả các thứ tự join có thể cùng một lúc.
Of course, the challenge in this implementation is that they had no notion of the physical properties of the data. So they had no notion of a sort order.
Tất nhiên, thách thức trong cách cài đặt này là họ không có khái niệm về các thuộc tính vật lý của dữ liệu. Nên họ không có khái niệm về thứ tự sắp xếp.
So if my query had an order by clause, in this case here, they couldn't account for that in their implementation. And hash joins make all the data random anyway.
Vậy nếu truy vấn của tôi có mệnh đề order by, như trong trường hợp này, họ không thể tính đến nó trong cách cài đặt của họ. Và hash join dù sao cũng làm dữ liệu thành ngẫu nhiên.
So the way they make this work is they would embed in the cost model itself.
Cách họ làm cho nó hoạt động là nhúng nó vào chính mô hình chi phí.
They would say, oh, well, after I figure out the path I want to go through, I would give a penalty to any query plan that doesn't have the data sorted in the way that I wanted versus the ones that do have sort of the data that I wanted.
Họ nói rằng, sau khi tôi xác định được đường đi mình muốn, tôi sẽ phạt bất kỳ kế hoạch truy vấn nào không có dữ liệu được sắp xếp theo cách mà tôi muốn, so với những kế hoạch có dữ liệu như tôi muốn.
OK? Yes.
Được chứ? Vâng, mời bạn.
This question, is this guaranteed to be optimal? No, of course, no. Yeah. Yeah. Yes.
Câu hỏi là liệu cách này có đảm bảo tối ưu không? Không, tất nhiên là không. Vâng. Vâng, mời em.
The question is, the statement is, and they're correct, this is quadratic cost if you only consider left-deep trees. Yes. And so if you throw away bushy plans and right-deep trees, it reduces quite significantly.
Câu hỏi là, nhận định là và em nói đúng, chi phí này là bậc hai nếu chỉ xét các cây left-deep. Vâng. Và nếu loại bỏ các kế hoạch bushy và các cây right-deep, thì không gian tìm kiếm giảm đi khá đáng kể.
But it's still quadratic.
Nhưng nó vẫn là bậc hai.
And it's that large number that you can't align number. Yes, I'm talking about board. Yes, and that's massive. All right. Let's stop here. Again, this was rushed, so I apologize.
Và đó là con số lớn đến mức em không thể căn chỉnh được. Vâng, tôi đang nói về cái bảng. Đúng, và nó rất lớn. Được rồi. Chúng ta dừng ở đây. Một lần nữa, phần này hơi vội, nên tôi xin lỗi.
We'll pick up on this on Wednesday. We'll go over this and the top optimization, and then we'll spend the rest of the class talking about cost models. OK? All right. Hit it.
Chúng ta sẽ tiếp tục phần này vào thứ Tư. Chúng ta sẽ xem lại phần này và phần tối ưu hóa phía trên, rồi dành phần còn lại của buổi học để nói về các mô hình chi phí. Được chứ? Được rồi. Bắt đầu thôi.
Motherfuckers can't maintain whatever strength flow in the drain.
Lũ khốn này không thể duy trì được dòng chảy sức mạnh nào trong cống.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.