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ả.
Alright guys, let's get started. A round of applause for DJ Cash, awesome.
Được rồi các em, chúng ta bắt đầu nhé. Một tràng pháo tay cho DJ Cash nào, tuyệt vời.
Your bank account is taken care of now, or are you just waiting for money to come in? It's getting better, it's getting better. Okay, yeah.
Giờ thì tài khoản ngân hàng của em ổn rồi chứ, hay em vẫn đang đợi tiền chuyển vào? Đang khá hơn rồi, đang khá hơn rồi. Được, vâng.
Again, I gotta say goodbye to DJ, I gotta make sure he's doing okay. Alright guys, a lot to cover, because there's a bunch of stuff we didn't cover last class.
Lại một lần nữa, thầy phải chào tạm biệt DJ, thầy phải chắc là em ấy ổn. Được rồi các em, hôm nay có rất nhiều nội dung cần nói, vì có một loạt thứ chúng ta chưa kịp học ở buổi trước.
At the end, we rushed through, I want to pick up on that.
Cuối buổi, chúng ta đã nói lướt qua, và thầy muốn tiếp tục từ chỗ đó.
So again, midterm exams: if you want to come to my office hours after class today, you can come look at them with the solution.
Trước hết, về bài thi giữa kỳ: nếu các em muốn đến giờ tiếp sinh viên của thầy sau buổi học hôm nay, các em có thể đến xem bài thi cùng với lời giải.
Homework four is due this Sunday, and then project three, I forgot about this. Recitation was last night, I'll post that on Piazza after class with the video and the slides.
Bài tập về nhà 4 hạn nộp vào Chủ nhật này, và còn dự án 3, thầy suýt quên mất. Buổi thảo luận đã diễn ra tối qua, thầy sẽ đăng lên Piazza sau buổi học cùng với video và slide.
Any questions about homework four or project three? Alright, so last class, we were talking about the query optimizer.
Các em có câu hỏi nào về bài tập về nhà 4 hay dự án 3 không? Được rồi, ở buổi trước chúng ta đã nói về bộ tối ưu hóa truy vấn.
We sort of kicked off the discussion talking about how the query optimizer is the component of the system that is responsible for taking a SQL query and then generating a physical plan, an execution plan, that the data system can then actually execute.
Chúng ta mở đầu bằng việc nói về việc bộ tối ưu hóa truy vấn là thành phần của hệ thống chịu trách nhiệm nhận một truy vấn SQL rồi tạo ra một kế hoạch vật lý, một kế hoạch thực thi, mà hệ quản trị dữ liệu thực sự có thể thực thi.
And we talked about how we went from the SQL, we parse it, generate an abstract syntax tree, we run it through the binder, where we resolve names of tables, of column names and functions to actual internal identifiers.
Và chúng ta đã nói về quá trình đi từ câu SQL, chúng ta phân tích cú pháp, tạo ra cây cú pháp trừu tượng, rồi đưa qua bộ liên kết (binder), nơi chúng ta phân giải tên bảng, tên cột và hàm thành các định danh nội bộ thực sự.
And then with that logical plan, we can do some additional transformations without considering a cost model, try to fix things up and make it a little bit better than a literal translation of the SQL query from the abstract syntax tree.
Và với kế hoạch logic đó, chúng ta có thể thực hiện thêm một số phép biến đổi mà không cần mô hình chi phí, để chỉnh sửa và làm cho nó tốt hơn một chút so với bản dịch nguyên văn truy vấn SQL từ cây cú pháp trừu tượng.
And then we talked a little bit at the end, but we ran out of time, and we'll pick up where we left off, talking about the cost-based search, where we try to look for alternative plans, alternative physical plans, and pick the one that we think is going to have the lowest cost.
Sau đó chúng ta có nói một chút ở cuối buổi, nhưng đã hết thời gian, nên chúng ta sẽ tiếp tục từ chỗ đã dừng, nói về tìm kiếm dựa trên chi phí, trong đó chúng ta cố gắng tìm các kế hoạch thay thế, các kế hoạch vật lý thay thế, và chọn kế hoạch mà chúng ta cho là có chi phí thấp nhất.
And again, I'm putting cost here in parentheses because the cost is going to vary per system, per environment, what you're trying to optimize for.
Và một lần nữa, thầy để chữ chi phí trong ngoặc đơn ở đây vì chi phí sẽ khác nhau tùy từng hệ thống, từng môi trường, tùy vào việc em muốn tối ưu điều gì.
But usually, you're going to try to optimize the amount of disk IOs in a very basic cost model, but you can build upon that and do more sophisticated things, like considering how much it takes to compute a function or to process something that's in memory.
Nhưng thông thường, với mô hình chi phí rất cơ bản, em sẽ cố tối ưu số lần IO đĩa, nhưng em có thể xây dựng thêm trên đó và làm những việc phức tạp hơn, như xét đến thời gian cần để tính một hàm hoặc để xử lý thứ gì đó đang nằm trong bộ nhớ.
And then we said the way we determine, or the way we implement, our cost-based query optimizer, the quality of the plans it's going to produce is going to be a combination of these three factors.
Và sau đó chúng ta nói rằng cách chúng ta xác định, hay cách chúng ta xây dựng, bộ tối ưu hóa truy vấn dựa trên chi phí, thì chất lượng của các kế hoạch mà nó tạo ra sẽ là sự kết hợp của ba yếu tố này.
So what kind of transformation rules do we have that will convert the logical plan to another logical plan, or a logical plan to a physical plan?
Vậy chúng ta có những quy tắc biến đổi nào để chuyển một kế hoạch logic thành một kế hoạch logic khác, hoặc một kế hoạch logic thành một kế hoạch vật lý?
And this allows us to enumerate over different permutations of the query plan and try to find one with a better cost. Then there'll be the search algorithm, which we rushed at the end.
Điều này cho phép chúng ta liệt kê các hoán vị khác nhau của kế hoạch truy vấn và cố tìm ra một kế hoạch có chi phí tốt hơn. Tiếp theo là thuật toán tìm kiếm, phần mà ta đã làm vội ở cuối buổi trước.
We'll pick up again now.
Bây giờ ta sẽ tiếp tục.
But this is the method in which we're going to explore the different possibilities of alternative plans we have being generated by the transformation rules of the enumeration process, then search for them and try to find better choices.
Đây là phương pháp để ta khám phá các khả năng khác nhau của những kế hoạch thay thế được sinh ra bởi các quy tắc biến đổi trong quá trình liệt kê, rồi tìm kiếm chúng và cố gắng tìm ra những lựa chọn tốt hơn.
And then the cost model piece that we'll talk about at the end, that's where we try to predict what will be the expected runtime behavior of a query plan, not so much to try to generate an absolute value, like this query is going to take 15 seconds, or you're not trying to pick something that's going to be something you can measure in the real world.
Sau đó là phần mô hình chi phí mà ta sẽ nói đến ở cuối, đó là nơi ta cố gắng dự đoán hành vi thời gian chạy kỳ vọng của một kế hoạch truy vấn, không hẳn để tạo ra một giá trị tuyệt đối, kiểu như truy vấn này sẽ mất 15 giây, hay là ta không cố chọn ra một thứ nào đó mà bạn có thể đo được trong thế giới thực.
What you're really trying to do with this cost model is to identify whether one query plan is better than another.
Điều ta thực sự muốn làm với mô hình chi phí này là xác định xem một kế hoạch truy vấn có tốt hơn kế hoạch khác hay không.
So this cost model will be an internal metric we'll use that the database optimization can only use.
Vì vậy mô hình chi phí này là một thước đo nội bộ mà ta sẽ dùng, và chỉ bộ tối ưu hóa của cơ sở dữ liệu mới dùng được.
So whatever cost model that MySQL is using, they spit out a number, say, "This is the cost of a query plan." That's meaningless in Postgres or Oracle or pick your favorite database system.
Chẳng hạn mô hình chi phí mà MySQL đang dùng, nó đưa ra một con số, rồi nói: "Đây là chi phí của kế hoạch truy vấn." Con số đó vô nghĩa trong Postgres hay Oracle, hay hệ cơ sở dữ liệu nào bạn thích.
So the cost model is the internal mechanism we use to figure this out. So for today's class, we'll come back to the search algorithms, the top of the bottom versus bottom of the top.
Vậy mô hình chi phí là cơ chế nội bộ để ta tìm ra điều này. Trong buổi hôm nay, ta sẽ quay lại các thuật toán tìm kiếm, tức là từ trên xuống dưới so với từ dưới lên trên.
And then we'll talk about the kind of statistics we would collect.
Rồi ta sẽ nói về loại thống kê mà ta thu thập.
And then the cost models we use to estimate the cardinality of the operators, because that's going to be the big thing where we have to determine how much work a query is going to consume or use, because that's going to tell us how much data we're sending between the different operators.
Và sau đó là các mô hình chi phí dùng để ước lượng lực lượng (cardinality) của các toán tử, vì đó sẽ là điều quan trọng nhất, khi ta phải xác định một truy vấn sẽ tiêu tốn hay sử dụng bao nhiêu công việc, bởi nó sẽ cho ta biết lượng dữ liệu mà ta gửi giữa các toán tử khác nhau.
And again, just to preface this, this is super hard. This is the hardest part of database systems. This is the part I know the least about.
Và một lần nữa, nói trước là phần này cực kỳ khó. Đây là phần khó nhất của hệ cơ sở dữ liệu. Đây là phần tôi biết ít nhất.
So don't feel like you're not following along, but it's super challenging. We're barely scratching the surface here. And like long as you understand the high level concepts, that's what really matters.
Nên đừng nghĩ rằng mình không theo kịp, nó thực sự rất thách thức. Ở đây ta mới chỉ chạm vào bề mặt. Và miễn là bạn hiểu các khái niệm ở mức tổng quan, thì đó mới là điều thực sự quan trọng.
And then the details of this maybe only matters if you actually go in and building a query optimizer. All right.
Còn các chi tiết thì có lẽ chỉ quan trọng nếu bạn thực sự xây dựng một bộ tối ưu hóa truy vấn. Được rồi.
So again, the search algorithm is the way we're going to, again, enumerate or look at different alternative plans or choices we have for both logical operators and their corresponding physical operators in our query plan.
Vậy thuật toán tìm kiếm là cách để ta liệt kê hoặc xem xét các kế hoạch thay thế khác nhau hay các lựa chọn mà ta có cho cả các toán tử logic và các toán tử vật lý tương ứng trong kế hoạch truy vấn.
And the two approaches: either start from the bottom and work your way to the top, sometimes called forward chaining.
Có hai cách tiếp cận: hoặc bắt đầu từ dưới và đi dần lên trên, đôi khi gọi là suy diễn tiến (forward chaining).
And then the alternative approach is start from the top and then you work your way to the bottom to the leaf nodes. And again, conceptually, they're sort of the same at a high level.
Cách còn lại là bắt đầu từ trên rồi đi dần xuống dưới tới các nút lá. Và về mặt khái niệm, ở mức tổng quan thì chúng khá giống nhau.
The thing they're trying to produce is the same, trying to generate a physical plan that I can then go execute.
Thứ chúng cố gắng tạo ra là như nhau, tạo ra một kế hoạch vật lý mà sau đó tôi có thể đem đi thực thi.
But there's some nuances to the different approaches in terms of how much backtracking or how much redundant work you could possibly encounter while you're generating these query plans.
Nhưng giữa các cách tiếp cận này có một số điểm khác biệt tinh tế về mức độ quay lui hay lượng công việc dư thừa mà bạn có thể gặp phải trong lúc tạo ra các kế hoạch truy vấn này.
And in particular, the bottom one, they're going to make heavy use of memorization to avoid redundant, superfluous computations. All right.
Và đặc biệt là cách từ dưới lên, nó sẽ dùng nhiều memoization để tránh các phép tính dư thừa, không cần thiết. Được rồi.
So bottom up basically is you start with the leaf nodes in your query plan. You basically start with nothing, like, here's how I'm going to access the individual tables.
Vậy từ dưới lên về cơ bản là bạn bắt đầu từ các nút lá trong kế hoạch truy vấn. Về cơ bản bạn bắt đầu từ con số không, kiểu như: đây là cách tôi sẽ truy cập từng bảng.
And then I'm going to figure out now what order I want to generate the joins and other parts of the query plan, working the way to the top, where you end up with the final result that you want, like, I want to join these tables and produce this output.
Rồi tiếp theo tôi sẽ xác định xem mình muốn tạo các phép join và các phần khác của kế hoạch truy vấn theo thứ tự nào, đi dần lên trên cùng, nơi bạn có được kết quả cuối cùng mà mình muốn, kiểu như: tôi muốn join các bảng này và cho ra kết quả đầu ra này.
Top down is the opposite, where you start with what you want to produce, start with what the outcome you want to be for the query, and then you work the way down and try to figure out what operators I need to introduce to get me back to that location.
Từ trên xuống thì ngược lại, bạn bắt đầu từ thứ mình muốn tạo ra, bắt đầu từ kết quả mà bạn muốn có cho truy vấn, rồi đi dần xuống dưới và cố xác định xem cần đưa vào những toán tử nào để quay về được đúng đích đó.
So the very first query optimizer that IBM built, sorry, the very first cost-based query optimizer that IBM built in the 1970s in System R follows this top approach here.
Trình tối ưu hóa truy vấn đầu tiên mà IBM xây dựng, xin lỗi, trình tối ưu hóa truy vấn dựa trên chi phí đầu tiên mà IBM xây dựng vào thập niên 1970 trong System R đi theo cách tiếp cận từ trên xuống này.
And I'll show you the next slide. Most open source data systems that are out today that you know about are doing something like this.
Tôi sẽ cho các bạn xem ở slide tiếp theo. Hầu hết các hệ thống dữ liệu mã nguồn mở hiện nay mà các bạn biết đều làm theo kiểu như thế này.
Postgres is doing something that sort of looks like this. DB2 is doing this. The Germans do this, but like on steroids.
Postgres làm theo kiểu trông giống thế này. DB2 cũng làm vậy. Người Đức cũng làm vậy, nhưng ở mức cực mạnh.
And then DuckDB follows some of the work that the Germans did at Munich 10 years ago, and it's following this approach as well.
Còn DuckDB theo một số công trình mà người Đức ở Munich đã làm cách đây 10 năm, và cũng đi theo cách tiếp cận này.
So again, the way this is going to work is that we're going to use our transformation rules to do some initial optimizations, to again do predicate pushdown, do the things we know we're always going to want to do to optimize our query without actually consulting a cost model.
Vậy cách nó hoạt động là chúng ta sẽ dùng các quy tắc biến đổi để thực hiện một số tối ưu hóa ban đầu, chẳng hạn đẩy predicate xuống (predicate pushdown), làm những việc mà ta biết lúc nào cũng muốn làm để tối ưu truy vấn mà không cần tham chiếu đến mô hình chi phí.
And then we're going to use this divide-and-conquer algorithm that's going to, again, sort of search at sort of different join levels in the tree, and I'll show this next slide, Like, which can be the optimal join ordering, and what physical algorithm I'm going to want to use to compute the different joins.
Sau đó chúng ta sẽ dùng thuật toán chia để trị này, thuật toán sẽ tìm kiếm ở các mức join khác nhau trong cây, tôi sẽ cho xem ở slide sau, xem thứ tự join tối ưu có thể là gì, và tôi sẽ muốn dùng thuật toán vật lý nào để tính các phép join khác nhau.
So let's say, again, we have a query like this. We're doing a three-way join: Artist, Appears, Album. This is the example I showed at the beginning of the semester.
Giả sử, một lần nữa, ta có một truy vấn như thế này. Ta đang thực hiện phép join ba bảng: Artist, Appears, Album. Đây là ví dụ tôi đã cho xem ở đầu học kỳ.
And so in the System R implementation, the first stage, you basically apply a bunch of transformation rules that try to figure out, for each of the tables I need to access, what's the best access method to use?
Vậy trong cách cài đặt của System R, ở giai đoạn đầu tiên, bạn áp dụng một loạt quy tắc biến đổi để cố xác định, với mỗi bảng cần truy cập, phương thức truy cập tốt nhất để dùng là gì?
And this is going to be simple things like, well, in the case of Artist, I don't have anything I could use as a filter directly on my table, because there's no WHERE artist name equals something.
Và đây sẽ là những việc đơn giản như, trong trường hợp của Artist, tôi không có gì để dùng làm bộ lọc trực tiếp trên bảng của mình, vì không có mệnh đề WHERE artist name bằng một giá trị nào đó.
So therefore, I'm going to want to do a sequential scan. But in the case of the Album table, I have an index on the name attribute, so I can use that in my plan.
Do đó, tôi sẽ muốn dùng sequential scan. Nhưng với bảng Album, tôi có một chỉ mục trên thuộc tính name, nên tôi có thể dùng nó trong kế hoạch của mình.
So then now the next stage, and this is where the divide-and-conquer piece comes in, where we're going to seed out all the different possible join orderings I have for the tables, right?
Rồi đến giai đoạn tiếp theo, và đây là chỗ phần chia để trị xuất hiện, nơi chúng ta sẽ liệt kê ra tất cả các thứ tự join có thể có của các bảng, đúng không?
Do I want to join Artist and Appears first, or Appears and Album first? I just do this for all possible combinations, including introducing Cartesian products, because those are still valid joins.
Tôi muốn join Artist với Appears trước, hay Appears với Album trước? Tôi làm việc này cho mọi tổ hợp có thể, kể cả đưa vào các tích Descartes, vì chúng vẫn là các phép join hợp lệ.
And then now I'm going to run this dynamic programming algorithm, the divide-and-conquer approach, where I'm going to now start examining each of these different combinations I could have to get to my final outcome, because I'm starting at the bottom, and choose the one that's going to have the lowest cost.
Sau đó tôi sẽ chạy thuật toán quy hoạch động này, tức cách tiếp cận chia để trị, trong đó tôi sẽ bắt đầu xem xét từng tổ hợp khác nhau này mà tôi có thể dùng để đi đến kết quả cuối cùng, vì tôi bắt đầu từ dưới cùng, và chọn tổ hợp có chi phí thấp nhất.
Say it again? Correct, yes.
Em nói lại được không? Đúng, vâng.
So his statement is, and he's correct, in the last class I said that the largest query I've seen with joins, in terms of number of tables, was like 1,500, 1,600 or something.
Ý của bạn ấy là, và bạn ấy nói đúng, trong buổi trước tôi đã nói truy vấn lớn nhất có join mà tôi từng thấy, tính theo số bảng, vào khoảng 1.500, 1.600 gì đó.
And then, wouldn't this explode in terms of number of choices you have to consider? Absolutely, yes. Before exploding with what, sorry?
Vậy thì chẳng phải số lựa chọn cần xem xét sẽ bùng nổ sao? Chắc chắn rồi. Xin lỗi, bùng nổ với cái gì cơ?
Yeah, so he's correct.
Vâng, bạn ấy nói đúng.
If I do this, the search base isn't going to be huge, and therefore I'm never going to be able to even try to get to something reasonable.
Nếu làm như vậy, không gian tìm kiếm sẽ cực lớn, và do đó tôi sẽ không bao giờ có thể đi đến được một kết quả hợp lý.
So they'll do a bunch of things like throw away anything that's not a left-deep join tree. So that throws away a bunch of possibilities I could have in terms of these orderings.
Vì vậy họ sẽ làm nhiều việc, chẳng hạn loại bỏ mọi thứ không phải là cây join left-deep. Như vậy sẽ loại bỏ rất nhiều khả năng mà tôi có thể có về các thứ tự này.
I would throw away any Cartesian products right away, that's easy.
Tôi sẽ loại ngay mọi tích Descartes, việc đó dễ.
There's other things you can do, like if I know it's a, a common trick is if I know it's a, there's a certain pattern to the schema that I'm always going to want to do joins a certain way, then I can throw away anything that's not that.
Còn có những việc khác có thể làm, ví dụ nếu tôi biết nó là, một mẹo thường dùng là nếu tôi biết nó là, lược đồ có một mẫu nhất định mà tôi luôn muốn join theo một cách nhất định, thì tôi có thể loại bỏ mọi thứ không phải như vậy.
There's a bunch of heuristics you apply to prune down the search base. We're not covering that here, that's more the advanced class stuff.
Có rất nhiều heuristic để áp dụng nhằm cắt tỉa không gian tìm kiếm. Ở đây chúng ta không đề cập, đó là nội dung của lớp nâng cao.
But there's other, like you can do, you can run like an approximation algorithm to get like a dirty start, and then use that as the, like, you know, dirty heuristic to kind of get some initial setting, and then use that as the starting point rather than starting from scratch.
Nhưng còn những cách khác, ví dụ bạn có thể chạy một thuật toán xấp xỉ để có một điểm khởi đầu sơ sài, rồi dùng nó như là, bạn biết đấy, một heuristic sơ sài để có được một thiết lập ban đầu, rồi dùng nó làm điểm xuất phát thay vì bắt đầu từ đầu.
But we have to understand the basic algorithm before we start doing the advanced stuff. But the answer is right, yes, this gets huge.
Nhưng chúng ta phải hiểu thuật toán cơ bản trước khi bắt đầu làm những thứ nâng cao. Nhưng câu trả lời là đúng, vâng, nó trở nên rất lớn.
Postgres does this, except if you have, by default, if you have 13 or more tables in your query, they don't do this, they fall back to a genetic algorithm, which I'm not going to cover.
Postgres làm như vậy, trừ khi theo mặc định, truy vấn của bạn có từ 13 bảng trở lên, thì họ không làm vậy, mà chuyển sang dùng một thuật toán di truyền, phần này tôi sẽ không đề cập.
If I have time, I can show slides. But like that thing is like super broken, and it doesn't work, right?
Nếu còn thời gian, tôi có thể cho xem slide. Nhưng thứ đó hỏng nặng lắm, và nó không hoạt động tốt, đúng không?
But that's what they do, it's basically an approximation, because you can't do sort of this dynamic programming. What's that? His question is, where does the number 13 come from?
Nhưng họ làm vậy đấy, về cơ bản đó là một phép xấp xỉ, vì bạn không thể áp dụng kiểu quy hoạch động này. Gì cơ? Câu hỏi của bạn ấy là con số 13 từ đâu ra?
Magic constant, right? Like you can, you can change it, by default it's 13. Some people just turn it off entirely, because it doesn't always, it's not guaranteed good results, yes.
Là một hằng số kỳ diệu thôi. Bạn có thể thay đổi nó, mặc định là 13. Có người còn tắt hẳn nó đi, vì không phải lúc nào nó cũng cho kết quả tốt, không được đảm bảo, đúng vậy.
The question is, is there a potential version of the algorithm that works? Yeah, so I'm not going to talk about this.
Câu hỏi là liệu có một phiên bản khả thi của thuật toán hay không? Vâng, nhưng tôi sẽ không nói về chuyện này.
There is a class of optimization algorithms that basically are doing, that are random.
Có một lớp các thuật toán tối ưu hóa về cơ bản là ngẫu nhiên.
Like, you can do simulated annealing, you can do the genetic algorithm from Postgres, that's sort of the same thing, like you're rolling the dice and see what comes up.
Chẳng hạn, bạn có thể dùng simulated annealing, hoặc dùng thuật toán di truyền của Postgres, về cơ bản cũng như nhau, giống như bạn gieo xúc xắc rồi xem ra kết quả gì.
Like, again, you can't guarantee you're going to find the optimal, because it's random, like a random walk through a search space. In the case of the Postgres one, I mean, it's several factors, right?
Một lần nữa, bạn không thể đảm bảo sẽ tìm được phương án tối ưu, vì nó ngẫu nhiên, giống như một bước đi ngẫu nhiên trong không gian tìm kiếm. Với trường hợp của Postgres, có nhiều yếu tố đấy.
Like, is the implementation of the algorithm correct? I think, I think they said there was a bug in it, I forget what it is, like it's not truly random.
Chẳng hạn, việc cài đặt thuật toán có đúng không? Tôi nghĩ họ từng nói là có một lỗi trong đó, tôi quên mất là lỗi gì, kiểu như nó không thực sự ngẫu nhiên.
And then it also depends on your cost model, which we'll get to in a second. If your cost model is crap, then who cares how good the algorithm is?
Và nó còn phụ thuộc vào mô hình chi phí, phần này lát nữa ta sẽ nói tới. Nếu mô hình chi phí của bạn tệ thì thuật toán tốt đến đâu cũng chẳng ai quan tâm.
Like, you just, it's going to make bad predictions. But if you're consistently crappy, then maybe that's okay. Give me, give me half, we'll get to that, yeah.
Vì nó sẽ đưa ra những dự đoán sai. Nhưng nếu bạn tệ một cách nhất quán thì có lẽ cũng chấp nhận được. Cho tôi nửa phút, ta sẽ nói tới phần đó, vâng.
The Postgres one is the only one I know that does the random walk. The Germans do, if it's less than 100 tables, they have an efficient implementation of the algorithm that they can find.
Postgres là hệ duy nhất tôi biết dùng bước đi ngẫu nhiên. Còn nhóm người Đức thì, nếu dưới 100 bảng, họ có một cài đặt thuật toán hiệu quả mà họ có thể tìm ra.
They'll do the exact search, the exhaustive search. Above 100, then they do, they do sort of like the approximation first, and then that seeds an algorithm that does the more exhaustive search.
Họ sẽ thực hiện tìm kiếm chính xác, tìm kiếm vét cạn. Trên 100 thì họ làm một phép xấp xỉ trước, rồi kết quả đó làm đầu vào cho một thuật toán tìm kiếm vét cạn hơn.
But that way you know you're throwing away things that you're never going to consider anyway.
Nhưng như vậy bạn biết là mình loại bỏ những thứ mà dù sao cũng sẽ không bao giờ xét tới.
All right, so the basic, the walkthrough of the algorithm looks like this. So again, at the bottom is my starting point, and I want to get to the top here.
Được rồi, vậy phần minh họa cơ bản của thuật toán trông như thế này. Một lần nữa, ở dưới cùng là điểm xuất phát, và tôi muốn đi lên đến trên cùng.
So I'm going to work my way to the top and say, okay, I have three tables: Artist, Album, and Appears. Assuming I've already picked out what the access method I'm going to use.
Tôi sẽ đi dần lên trên và nói rằng, được rồi, tôi có ba bảng: Artist, Album và Appears. Giả sử tôi đã chọn xong phương thức truy cập sẽ dùng.
So now I've got to figure out in what order I want to join these tables, and what physical operator, what algorithm I'm going to want to use. Hash joins versus sort-merge join.
Giờ tôi phải xác định thứ tự join các bảng này, và toán tử vật lý nào, thuật toán nào tôi muốn dùng. Hash join hay sort-merge join.
You know, you'd also maybe consider nested loop join as well, but for space reasons I'm not showing that. And again, I'm only showing certain, you know, three different combinations.
Bạn cũng có thể xét thêm nested loop join, nhưng vì lý do không gian nên tôi không vẽ ra. Và một lần nữa, tôi chỉ cho thấy ba tổ hợp khác nhau.
This obviously would span out over here, but it wouldn't fit in PowerPoint. So for now, each of these pass up into the next level in the tree.
Rõ ràng nó sẽ mở rộng ra tới đây, nhưng sẽ không vừa trong PowerPoint. Vậy bây giờ, mỗi cái này được chuyển lên tầng tiếp theo trong cây.
I would say, okay, this one over here is joining Artist and Appears, and I haven't joined Album yet. So I can either join, do a hash join to join Artist and Appears.
Tôi sẽ nói, được rồi, cái ở đây là join Artist và Appears, và tôi vẫn chưa join Album. Vậy tôi có thể dùng hash join để join Artist và Appears.
I can do a merge join to do Artist and Appears.
Hoặc tôi có thể dùng merge join cho Artist và Appears.
And for each of those, now I can cost them, use my cost model, and say which of these ones are going to have a lower cost.
Với mỗi cách đó, giờ tôi có thể tính chi phí bằng mô hình chi phí của mình, và xem cách nào có chi phí thấp hơn.
And so for each of these pass up to the next level in the tree, I'll keep the one that has the lowest cost and throw away the others.
Và với mỗi nhánh được đưa lên tầng kế tiếp trong cây, tôi sẽ giữ lại cái có chi phí thấp nhất và bỏ những cái còn lại.
And now at the next level, I do the same thing. So again, I've already joined Artist and Appears.
Rồi ở tầng tiếp theo, tôi làm điều tương tự. Vậy là tôi đã join Artist và Appears rồi.
Now I want to take the output of Artist and Appears join and join it with Album.
Giờ tôi muốn lấy kết quả của phép join Artist và Appears rồi join nó với Album.
So I'm going to do the same thing and look at all the possible combinations I have for different physical operators to do that next level of the join, then go back and cost each of them to figure out which one has the lowest cost, going up to the same level, or coming from the same parent, going up to the next level.
Nên tôi sẽ làm tương tự và xem xét mọi tổ hợp có thể có của các toán tử vật lý để thực hiện tầng join kế tiếp đó, rồi quay lại tính chi phí từng cái để tìm ra cái có chi phí thấp nhất, trong số những cái cùng tầng, hay xuất phát từ cùng một nút cha, đi lên tầng kế tiếp.
Throw away all the other ones.
Bỏ hết những cái còn lại.
And then now for each of these paths up to the root or the top of the query plan, I'm going to pick which one everyone has the lowest level cost across all these different choices.
Và giờ với mỗi đường đi lên đến gốc, tức đỉnh của kế hoạch truy vấn, tôi sẽ chọn cái có chi phí thấp nhất ở cấp đó trong tất cả các lựa chọn này.
And then that's what you're deciding to be the lowest cost. It's divide and conquer. Rather than looking at all possible combinations, I'm just looking at each level. Like, OK, I've just joined two tables.
Và đó là cái bạn quyết định là có chi phí thấp nhất. Đây là chia để trị. Thay vì xem xét tất cả các tổ hợp có thể, tôi chỉ xem từng tầng một. Kiểu như, được rồi, tôi vừa join hai bảng.
What are the different possibilities I have? And now you can kind of see where some of these heuristics could help prune the search space. Because you would say, like, well, I go back here.
Tôi có những khả năng nào? Và giờ bạn có thể thấy phần nào các heuristic này có thể giúp cắt tỉa không gian tìm kiếm. Vì bạn sẽ nói, ví dụ, tôi quay lại đây.
If I know that the tables are so big that I'm never going to do a nested loop join, don't even bother trying to add a nested loop join and considering that.
Nếu tôi biết các bảng lớn đến mức tôi sẽ không bao giờ dùng nested loop join, thì đừng thèm thêm nested loop join vào và cân nhắc nó.
So back to his point, there's more magic constants. You could say, like, if the table is this size, then don't consider a nested loop join.
Quay lại ý của bạn ấy, đúng là có thêm các hằng số "ma thuật". Bạn có thể nói, nếu bảng có kích thước này, thì đừng cân nhắc nested loop join.
So another hack in all this is that the one is that instead of trying to, sorry, instead of, when we keep checking the best plans, we can ignore in what format we need the data to be in.
Một mẹo nữa trong tất cả những điều này là thay vì, xin lỗi, thay vì, khi chúng ta liên tục kiểm tra các kế hoạch tốt nhất, chúng ta có thể bỏ qua việc dữ liệu cần ở định dạng nào.
Meaning, like, what are the physical properties of the data? Like sorting, for example. Sorting is a physical property of data.
Nghĩa là, các thuộc tính vật lý của dữ liệu là gì? Ví dụ như thứ tự sắp xếp. Sắp xếp là một thuộc tính vật lý của dữ liệu.
So in this case here, I can not consider any of that while I'm computing my join order.
Vậy trong trường hợp này, tôi có thể không xét đến bất cứ điều đó khi tính thứ tự join.
And then I can go back and then say, after I've computed the join order, if I recognize that it isn't in the property that I need, like I need the data sorted on the artist ID, if it's not like that, then I can just graft on a sort at the top, up above.
Rồi sau khi đã tính xong thứ tự join, tôi quay lại và nếu nhận ra dữ liệu không có thuộc tính mà tôi cần, chẳng hạn tôi cần dữ liệu được sắp xếp theo artist ID, mà nó lại không như vậy, thì tôi chỉ cần gắn thêm một phép sort lên trên cùng.
Or I can modify my cost model and recognize that, going back here, the sort merge join is going to put the data in the sort order that I need.
Hoặc tôi có thể sửa mô hình chi phí và nhận ra rằng, quay lại chỗ này, sort merge join sẽ đưa dữ liệu vào đúng thứ tự sắp xếp mà tôi cần.
So I'll make sure that has a lower cost than the hash join.
Nên tôi sẽ đảm bảo nó có chi phí thấp hơn hash join.
The System R one is pretty primitive. The later ones, you can consider this directly in it. Yes, question? All right, So this is bottom to the top.
Cách của System R khá sơ khai. Các hệ thống sau này thì xét trực tiếp điều này luôn. Vâng, bạn có câu hỏi? Được rồi, đây là cách đi từ dưới lên trên.
Top down, again, you're starting with the logical plan, which would be the final output.
Với top-down, một lần nữa, bạn bắt đầu từ kế hoạch logic, tức là kết quả đầu ra cuối cùng.
And then now you're basically doing branch and bound search, looking for a path down to all the different leaf nodes so that you can have a complete query plan.
Và sau đó về cơ bản bạn thực hiện tìm kiếm nhánh cận, tìm một đường đi xuống tất cả các nút lá khác nhau để có được một kế hoạch truy vấn hoàn chỉnh.
All right, so the System R bottom to the top approach, that was invented in the 1970s. This approach came about in the late 80s, early 90s.
Được rồi, vậy cách tiếp cận bottom-up của System R, được phát minh vào những năm 1970. Cách tiếp cận này xuất hiện vào cuối thập niên 80, đầu thập niên 90.
The most famous implementation of this is something called Cascades, which is implemented in SQL Server, Greenplum, and CockroachDB.
Cài đặt nổi tiếng nhất của nó là thứ gọi là Cascades, được cài đặt trong SQL Server, Greenplum và CockroachDB.
And I think Databricks might be using this in their Catalyst optimizer as well, at least some form of this.
Và tôi nghĩ Databricks cũng có thể đang dùng nó trong trình tối ưu hóa Catalyst của họ, ít nhất là một dạng nào đó của nó.
And the basic idea is that as you're traversing down and looking at different options in the query plan, you keep track of the best plan you've seen so far.
Ý tưởng cơ bản là khi bạn duyệt xuống và xem xét các lựa chọn khác nhau trong kế hoạch truy vấn, bạn theo dõi kế hoạch tốt nhất mà bạn đã thấy cho đến nay.
And then at some point, if you reach a path in the query plan where the current cost from the root to wherever you're at now, if that's greater than the lowest cost you've seen for a complete query plan, then you know you don't need to keep going down and searching that part of the tree.
Và rồi tại một thời điểm, nếu bạn đến một đường đi trong kế hoạch truy vấn mà chi phí hiện tại từ gốc đến chỗ bạn đang đứng, nếu chi phí đó lớn hơn chi phí thấp nhất bạn từng thấy của một kế hoạch truy vấn hoàn chỉnh, thì bạn biết mình không cần đi xuống và tìm kiếm tiếp phần đó của cây nữa.
You can just sort of cut it off and not have to look at everything.
Bạn có thể cắt bỏ nó và không phải xem xét mọi thứ.
But the way you're sort of potentially revisiting different choices, this can get quite expensive because you could be revisiting things over and over again.
Nhưng cách bạn có thể phải xem lại các lựa chọn khác nhau, việc này có thể trở nên khá tốn kém vì bạn có thể xem lại cùng một thứ nhiều lần.
So all these implementations rely on a memo table or memoization table to keep track of, like, here's things I've cost before. Don't cost them again.
Vì vậy tất cả các cài đặt này đều dựa vào một bảng memo hay bảng ghi nhớ để theo dõi, kiểu như: đây là những thứ tôi đã tính chi phí rồi. Đừng tính chi phí lại nữa.
So for the longest time, there was only a few scattered research papers that described how to do this approach, especially in the context of this thing called Cascades.
Trong suốt một thời gian rất dài, chỉ có vài bài báo nghiên cứu rải rác mô tả cách thực hiện cách tiếp cận này, đặc biệt là trong bối cảnh của thứ gọi là Cascades.
But it was well known that SQL Server had been doing this since the 1990s.
Nhưng ai cũng biết SQL Server đã làm theo cách này từ những năm 1990.
The guy that wrote that B plus tree paper we talked about before, we talked about the parallelization stuff, the Volcano and exchange operators.
Người đã viết bài báo về B+ tree mà chúng ta nói trước đây, chúng ta cũng đã nói về song song hóa, Volcano và các toán tử exchange.
That's this one same guy, got hired by Microsoft in the late 90s. They threw away the old query optimizer they had, and he rewrote it to be the Cascades style.
Chính là người đó, được Microsoft thuê vào cuối những năm 90. Họ vứt bỏ trình tối ưu hóa truy vấn cũ mà họ có, và ông ấy viết lại nó theo kiểu Cascades.
And it probably is, you know, with the exception of maybe the Germans, it is the best query optimizer. It's certainly the best top-down query optimizer. Germans have the best bottom-up.
Và có lẽ, trừ khi tính đến có thể là người Đức, đó là trình tối ưu hóa truy vấn tốt nhất. Chắc chắn nó là trình tối ưu hóa truy vấn top-down tốt nhất. Người Đức có bottom-up tốt nhất.
And so for the longest time, there wasn't a very good description of how to actually implement one of these optimizers. So Microsoft put out a book last year. It's open source.
Và trong suốt một thời gian rất dài, không có một mô tả nào thật tốt về cách thực sự cài đặt một trong những trình tối ưu hóa này. Vì vậy Microsoft đã xuất bản một cuốn sách năm ngoái. Nó là mã nguồn mở.
You can go download it for free and read it. That thing's amazing. It's the best book I've read last year in my life. Like, it describes all the details.
Bạn có thể tải về miễn phí và đọc. Cuốn đó tuyệt vời. Đó là cuốn sách hay nhất tôi đọc năm ngoái, trong đời tôi. Nó mô tả tất cả các chi tiết.
Not all, but many of the details of how SQL Server does implement their query optimizer. But obviously, we can't go into too much detail for this lecture.
Không phải tất cả, nhưng nhiều chi tiết về cách SQL Server cài đặt trình tối ưu hóa truy vấn của họ. Nhưng hiển nhiên, chúng ta không thể đi quá sâu vào chi tiết trong bài giảng này.
But, you know, we take the advanced class, we'll spend more time talking about this. All right, so again, top-down optimization, we're going to start with what we want the final outcome to be.
Nhưng, các bạn biết đấy, nếu học lớp nâng cao thì chúng ta sẽ dành nhiều thời gian hơn để nói về phần này. Được rồi, vậy một lần nữa, với tối ưu hóa từ trên xuống, chúng ta bắt đầu từ kết quả cuối cùng mà mình muốn.
So we want our final outcome in this example here. Now we're going to do the artist, appears, and album. And now we're also going to include the physical property we want as well.
Vậy ta muốn kết quả cuối cùng như trong ví dụ này. Bây giờ ta sẽ làm với artist, appears và album. Và giờ ta cũng sẽ đưa vào cả thuộc tính vật lý mà ta muốn.
We want the data to be sorted by the artist ID.
Ta muốn dữ liệu được sắp xếp theo artist ID.
So now we're going to go through and apply a bunch of these transformation rules to either convert logical plans to other logical plans or logical plans into physical plans.
Vậy bây giờ ta sẽ duyệt qua và áp dụng một loạt quy tắc biến đổi để chuyển kế hoạch logic thành các kế hoạch logic khác hoặc chuyển kế hoạch logic thành kế hoạch vật lý.
We never go back from physical back to logical. So here's sort of, again, similar to what we had before. Here's all the stages of the sort of logical operators we have down below.
Ta không bao giờ đi ngược từ vật lý trở lại logic. Vậy đây là phần tương tự như lúc trước. Đây là tất cả các giai đoạn của các toán tử logic mà ta có ở bên dưới.
And we would run transformation rules to expand all these things out.
Và ta sẽ chạy các quy tắc biến đổi để khai triển tất cả những thứ này ra.
And then now, starting from the root, we're going to go through and look at the different choices we would have to get to this final outcome up here.
Rồi từ nút gốc, ta sẽ đi qua và xem xét các lựa chọn khác nhau mà ta có để đạt được kết quả cuối cùng ở trên này.
So we know that we want to join artist, appears, and album. So we say down below, we can join artist and appears after joining that.
Vậy ta biết là muốn join artist, appears và album. Nên ta nói ở bên dưới, có thể join artist với appears trước.
And then we join with album. And then the rest of them, we use a merge join.
Rồi join với album. Còn các phần còn lại thì ta dùng merge join.
So now, instead of looking at all the possible combinations at the next level, we actually traverse down into this and look at all the ways we would get to that level going up and keep going down here.
Vậy bây giờ, thay vì xem tất cả các tổ hợp có thể ở tầng kế tiếp, ta thực sự đi sâu xuống đây và xem tất cả các cách để đi tới tầng đó từ bên dưới lên, và tiếp tục đi xuống.
So now we say, are we going to join artist and appears? So I can either do a hash join for that. And I keep going down here.
Giờ ta hỏi: ta có join artist và appears không? Tôi có thể dùng hash join cho phần đó. Và tôi tiếp tục đi xuống.
And now we say, how do I actually access these tables? And I would pick my access method for that.
Và giờ ta hỏi: thực sự thì truy cập các bảng này bằng cách nào? Và tôi sẽ chọn phương thức truy cập cho chúng.
But now, once I sort of reach the bottom, I then go back up and start looking down another path because I'm doing depth first search.
Nhưng khi đã xuống tới đáy, tôi quay lên và bắt đầu xem xét một nhánh khác vì tôi đang dùng tìm kiếm theo chiều sâu.
I've got to get to the bottom first before I start looking at other levels. So then I come to artist appears.
Tôi phải xuống tới đáy trước rồi mới xem các tầng khác. Vậy rồi tôi quay lại artist appears.
And I can do possibly a merge join of that, do the same thing, come down and figure out what the access methods are for these other operators.
Và có thể dùng merge join cho phần đó, làm tương tự, đi xuống và xác định các phương thức truy cập cho những toán tử khác này.
And this is where the memoization stuff helps because I'm revisiting, like, how do I want to access artist, albums and appears at the lowest level of the tree as I'm costing it and coming back down over and over again.
Và đây là chỗ memoization phát huy tác dụng vì tôi liên tục xem lại chuyện truy cập artist như thế nào, albums và appears ở tầng thấp nhất của cây khi tôi tính chi phí và đi xuống lặp đi lặp lại.
I don't want to compute that cost every single time I revisit these things. So I just check the memo table to see whether I've visited this node before.
Tôi không muốn tính chi phí đó mỗi lần quay lại những nút này. Nên tôi chỉ kiểm tra memo table xem đã duyệt nút này chưa.
All right? So you basically just do that. Imagine this thing expanding out and getting quite large.
Được chứ? Về cơ bản là cứ làm như vậy. Hãy tưởng tượng cấu trúc này mở rộng ra và trở nên khá lớn.
And then there are, without going into too much detail, priorities you can set for these transformation rules so that maybe you want to look at hash joins before you look at merge joins.
Và, không đi quá chi tiết, bạn có thể đặt mức ưu tiên cho các quy tắc biến đổi này để chẳng hạn bạn muốn xét hash join trước khi xét merge join.
In case you run out of time in your search, You at least have a plan that generates a bunch of hash joins, even though it may not be optimal, but it's good enough.
Phòng khi bạn hết thời gian tìm kiếm, thì ít nhất bạn vẫn có một kế hoạch sinh ra nhiều hash join, dù có thể không tối ưu, nhưng cũng đủ tốt.
The other thing we have to do is keep track of how we're going to make sure that the data has the physical property we want at the top of the plan, or actually really any level of the plan.
Việc khác ta phải làm là theo dõi cách đảm bảo rằng dữ liệu có thuộc tính vật lý mà ta muốn ở đỉnh của kế hoạch, hay thực ra là ở bất kỳ mức nào của kế hoạch.
We have this order by requirement that the data has to be sorted on artist ID.
Ta có yêu cầu order by là dữ liệu phải được sắp xếp theo artist ID.
So now if we go and look at this operator here to do a hash join, we would know that that doesn't guarantee that data is in that property that we want.
Vậy bây giờ nếu ta xem toán tử hash join ở đây, ta sẽ biết rằng nó không đảm bảo dữ liệu có thuộc tính mà ta muốn.
So we know we don't even need to actually go look at it.
Vậy là ta biết thậm chí không cần xem xét nó nữa.
But then if we add a sort operator, it doesn't do the join for us, but it adds the data in the form that we need.
Nhưng nếu ta thêm một toán tử sort, nó không thực hiện phép join cho ta, mà nó đưa dữ liệu về dạng ta cần.
So we're allowed to go visit that, and then again, apply more transformation rules and say, "OK, well, I still need to join this data. How am I getting it up to me?"
Vì vậy ta được phép duyệt nhánh đó, rồi lại áp dụng thêm các luật biến đổi và nói: "Được rồi, mình vẫn cần join dữ liệu này. Làm sao để đưa nó lên chỗ mình?"
So then now if I do a transformation rule and say, now add the hash join, when I cost it, and I would see that, oh, adding the sort plus the hash join, that cost is greater than the merge join path I've seen before, I don't even consider it, again, going down.
Vậy nếu giờ ta áp dụng một luật biến đổi, tức là thêm hash join, khi tính chi phí, ta sẽ thấy rằng thêm sort cộng với hash join thì chi phí lớn hơn đường merge join mà ta đã thấy trước đó, nên ta sẽ không xét nó nữa, không đi sâu xuống tiếp.
So maybe I'll skip this, but I just know that the way they're going to implement the guarantee the data is in the physical property you want, they just add these enforcer nodes.
Có lẽ tôi sẽ bỏ qua phần này, nhưng tôi chỉ cần các bạn biết cách họ cài đặt việc đảm bảo dữ liệu có thuộc tính vật lý mà bạn muốn là họ chỉ thêm các nút enforcer này.
And it's just a way to say, make sure that nothing comes up to me that isn't ordered the way that I need it up above.
Về cơ bản đó là cách để nói rằng, đảm bảo không có gì đi lên chỗ tôi mà không được sắp xếp theo thứ tự tôi cần ở phía trên.
And so I can do a bunch of transformation rules, and I can match them in the rules.
Vậy ta có thể có nhiều luật biến đổi và so khớp chúng trong các luật.
It would say, this data will be in this form that you need, Or this data would not be in the form that you want.
Nó sẽ cho biết dữ liệu này sẽ ở dạng mà bạn cần, hoặc dữ liệu này sẽ không ở dạng mà bạn muốn.
And so I only apply the rules that I know that I want. That avoids, again, having to fan out and look at possibly everything. So in the sake of time, I'll just skip this.
Nhờ đó ta chỉ áp dụng những luật mà ta biết là mình muốn. Như vậy lại tránh được việc phải mở rộng ra và xem xét có thể là mọi thứ. Vì thời gian có hạn, tôi sẽ bỏ qua phần này.
I'm just trying to say that you can add this in as part of this first-class property in the search.
Tôi chỉ muốn nói rằng bạn có thể đưa nó vào như một thuộc tính hạng nhất trong quá trình tìm kiếm.
So that's the search algorithms. Again, we can either just do pure heuristics and just apply them one after another until we put the query in a form that we can actually execute.
Vậy đó là các thuật toán tìm kiếm. Một lần nữa, ta có thể chỉ dùng heuristic thuần túy và áp dụng các luật lần lượt cái này sau cái kia cho đến khi truy vấn ở dạng mà ta thực sự có thể thực thi.
If we're going to do a cost-based search, then we either go top-down versus bottom-up. Both systems do bottom-up. The more sophisticated, newer ones are doing top-down. But it's super hard either way. All right.
Nếu ta làm tìm kiếm dựa trên chi phí, thì ta đi từ trên xuống hoặc từ dưới lên. Cả hai hệ thống đều làm từ dưới lên. Những hệ thống mới và tinh vi hơn thì làm từ trên xuống. Nhưng cách nào cũng cực kỳ khó. Được rồi.
So for all these different operators, when we talked about them before, when we talked about query execution, we talked about different ways or different formulas we would use to compute the amount of work they were going to do.
Với tất cả các toán tử khác nhau này, khi ta nói về chúng trước đây, khi nói về thực thi truy vấn, ta đã nói về các cách khác nhau hay các công thức khác nhau mà ta dùng để tính lượng công việc mà chúng sẽ phải làm.
Like when we talked about the different join algorithms, the sort-merge join, nested loop join, and the hash joins, we talked about them in terms of how much data they were going to have to read in and how much data they're going to have to write out, how many IOs they were doing.
Chẳng hạn khi nói về các thuật toán join khác nhau, sort-merge join, nested loop join và hash join, ta nói về chúng xét theo lượng dữ liệu chúng sẽ phải đọc vào và lượng dữ liệu chúng sẽ phải ghi ra, tức là chúng thực hiện bao nhiêu IO.
But the challenge is going to be, now that we're trying to build a real query plan where we have real data that we're going to be running on, it's no longer these sort of abstract numbers or these formulas.
Nhưng thách thức là, giờ đây khi ta cố xây dựng một kế hoạch truy vấn thực tế với dữ liệu thật mà ta sẽ chạy trên đó, thì nó không còn là những con số trừu tượng hay những công thức như vậy nữa.
We actually have to come up with estimates for what this data is actually going to be.
Chúng ta thực sự phải đưa ra các ước lượng về dữ liệu này thực tế sẽ như thế nào.
So when we talk about those IOs, how are we actually computing them other than just me showing them on PowerPoint?
Vậy khi nói về những IO đó, chúng ta thực sự tính chúng bằng cách nào, ngoài việc em chiếu lên PowerPoint?
And this can be hard to do because, as we'll see, The amount of data you may have to process, if you're a join operator, it's going to depend on how much data is being sent to you below you in the query plan.
Và việc này có thể khó, bởi vì như chúng ta sẽ thấy, lượng dữ liệu mà bạn có thể phải xử lý, nếu bạn là một toán tử join, sẽ phụ thuộc vào lượng dữ liệu được gửi lên cho bạn từ bên dưới trong kế hoạch truy vấn.
And then the problem is going to get compounded because if I have multiple joins in my query plan, I can maybe do OK predicting how much data is coming into me from the scanning tables to my join.
Và vấn đề sẽ còn trở nên trầm trọng hơn vì nếu kế hoạch truy vấn của tôi có nhiều phép join, có lẽ tôi dự đoán khá ổn lượng dữ liệu đi vào phép join từ các bảng được quét.
But now I take the output of that join and feed it to another join.
Nhưng bây giờ tôi lấy kết quả đầu ra của phép join đó và đưa vào một phép join khác.
If my estimate for how much data is coming in my first join is off, then I have no hope picking out a good estimate for how much data is coming out of the second join, and for all these operators.
Nếu ước lượng của tôi về lượng dữ liệu vào phép join đầu tiên bị lệch, thì tôi không còn hy vọng đưa ra được ước lượng tốt về lượng dữ liệu ra khỏi phép join thứ hai, và cho tất cả các toán tử này.
Again, we can't just go execute the queries, because if we could do that, then we could just run the queries instead of trying to figure out, for the thousands or even tens of thousands, millions of possibilities that I have, I can't run those each individually.
Một lần nữa, ta không thể cứ thực thi các truy vấn, vì nếu làm được vậy, thì ta cứ chạy truy vấn luôn thay vì cố tìm ra, trong hàng nghìn hoặc thậm chí hàng chục nghìn, hàng triệu khả năng mà tôi có, tôi không thể chạy từng cái một.
So this is where the database system's cost model is going to come in.
Đây là lúc mô hình chi phí của hệ quản trị cơ sở dữ liệu xuất hiện.
It's a way for us to estimate the amount of work an operator is going to have to do within a query plan, given the current state of the database.
Đó là cách để ta ước lượng khối lượng công việc mà một toán tử phải làm trong kế hoạch truy vấn, dựa trên trạng thái hiện tại của cơ sở dữ liệu.
And what I mean by the current state is what the distribution of values look like in the tables that you're trying to access a query against.
Và trạng thái hiện tại ở đây nghĩa là phân phối các giá trị trong các bảng mà bạn đang cố truy cập bằng truy vấn.
And the challenge of this is that in some database systems or some applications, the data is not static.
Thách thức ở đây là trong một số hệ cơ sở dữ liệu hay ứng dụng, dữ liệu không tĩnh.
Meaning if I'm running a website like Reddit, I'm getting new updates and new inserts all the time. And potentially, the distribution of values could change.
Nghĩa là nếu tôi vận hành một website như Reddit, tôi liên tục nhận được các cập nhật và chèn mới. Và phân phối các giá trị có thể thay đổi.
So my cost estimates from today may look a lot different than what they would look like a month from now. Usually not too drastic, but it can drift over time and cause problems.
Nên các ước lượng chi phí của hôm nay có thể khác khá nhiều so với một tháng sau. Thường không quá mạnh, nhưng nó có thể trôi dần theo thời gian và gây ra vấn đề.
And as I said before, this internal cost that we're generating is not going to be something that's related to the physical world. Usually it's not. Some systems, but it's rare, it is.
Và như tôi đã nói trước đó, chi phí nội bộ mà ta tạo ra này không phải là thứ liên quan đến thế giới vật lý. Thường là không. Một vài hệ thống thì có, nhưng hiếm.
It's going to be this relative number that we just use to say whether one query plan is going to be more efficient or better than another query plan.
Nó chỉ là một con số tương đối để ta cho biết liệu một kế hoạch truy vấn có hiệu quả hơn hay tốt hơn kế hoạch truy vấn khác hay không.
And we can't take what our Postgres estimates are and apply them to MySQL's optimizer. They're completely separate notions.
Và ta không thể lấy các ước lượng của Postgres rồi áp dụng cho bộ tối ưu hóa của MySQL. Chúng là những khái niệm hoàn toàn tách biệt.
So the two types of components we'd have in our cost estimates for an operator are going to be the physical cost and the logical cost.
Vậy hai loại thành phần trong ước lượng chi phí cho một toán tử là chi phí vật lý và chi phí logic.
So physical cost would be the resource consumption of an operator, of a query plan, when the data system runs that query.
Chi phí vật lý là mức tiêu thụ tài nguyên của một toán tử, của một kế hoạch truy vấn, khi hệ thống dữ liệu chạy truy vấn đó.
Basic things we already talked about was like IOs: how many blocks of data or pages of data I'm going to read from disk or write to disk.
Những thứ cơ bản chúng ta đã nói tới là IO: tôi sẽ đọc bao nhiêu block dữ liệu hay page dữ liệu từ đĩa hoặc ghi xuống đĩa.
But you can extend that out for other parts of a computer: how many packets I'm going to send over the network, how much time I'm going to spend in the CPU, how many cycles to do some operation.
Nhưng bạn có thể mở rộng sang các thành phần khác của máy tính: tôi sẽ gửi bao nhiêu gói tin qua mạng, tôi sẽ tốn bao nhiêu thời gian trên CPU, cần bao nhiêu chu kỳ để thực hiện một thao tác.
Cache measures are a little bit more complicated to estimate. But getting more low-level in parts of the hardware, it becomes more problematic.
Các số đo về cache thì khó ước lượng hơn một chút. Nhưng càng đi xuống mức thấp của phần cứng thì càng khó.
And of course, obviously, this is going to depend on what my hardware actually looks like, what my CPUs look like. How much L3 cache do I have?
Và tất nhiên, điều này sẽ phụ thuộc vào phần cứng của tôi thực sự trông như thế nào, các CPU của tôi ra sao. Tôi có bao nhiêu L3 cache?
So typically, most systems are going to do IOs as the dominant factor. You maybe also want to include how much memory I'm going to consume in my operator, because obviously, that's a finite resource.
Nên thông thường, hầu hết các hệ thống coi IO là yếu tố chi phối. Có thể bạn cũng muốn tính thêm toán tử của tôi sẽ tiêu thụ bao nhiêu bộ nhớ, vì rõ ràng đó là một tài nguyên hữu hạn.
For CPU cycles, the high-end systems can be a bit more smart about this.
Với chu kỳ CPU, các hệ thống cao cấp có thể thông minh hơn một chút.
Something like Postgres will just say, if something's in memory, what's the relative cost of accessing something in memory, processing in memory, versus reading something from disk?
Một hệ thống như Postgres sẽ chỉ nói rằng, nếu dữ liệu nằm trong bộ nhớ, thì chi phí tương đối của việc truy cập dữ liệu trong bộ nhớ, xử lý trong bộ nhớ, so với đọc từ đĩa là bao nhiêu?
That's a loose approximation for coming in and out.
Đó là một phép xấp xỉ sơ lược cho việc đưa dữ liệu vào và ra.
Logical costs would be the estimated output size per operator.
Chi phí logic là kích thước đầu ra ước tính của mỗi toán tử.
And what's nice about this, at least logical costs, is that no matter what physical operator I choose, the logical cost has to be the same.
Và điểm hay ở đây, ít nhất với chi phí logic, là dù tôi chọn toán tử vật lý nào, chi phí logic vẫn phải như nhau.
So if I'm joining table A and table B, no matter whether I do a sort-merge join, a nested loop join, or a hash join, it's going to produce X number of tuples.
Nếu tôi join bảng A và bảng B, dù tôi dùng sort-merge join, nested loop join, hay hash join, thì nó vẫn tạo ra X tuple.
So sometimes those logical costs can be used to prune things out before you're actually looking at all the different physical operator choices for a query plan.
Vì vậy đôi khi có thể dùng các chi phí logic đó để loại bớt các lựa chọn trước khi thực sự xem xét tất cả các lựa chọn toán tử vật lý khác nhau cho một kế hoạch truy vấn.
But the problem is, in order for me to predict how much data my operator is going to spit out, I've got to know how much data is coming in.
Nhưng vấn đề là, để dự đoán được lượng dữ liệu mà toán tử của tôi sẽ trả ra, tôi phải biết có bao nhiêu dữ liệu đi vào.
And now you get this sort of recursive problem we'll see later on. So just showing Postgres as an example, again, I would say this is the most basic, simplest cost model you can have.
Và như vậy bạn gặp một vấn đề đệ quy mà chúng ta sẽ thấy sau. Tôi lấy Postgres làm ví dụ, và tôi cho rằng đây là mô hình chi phí cơ bản nhất, đơn giản nhất mà bạn có thể có.
So what they care about is the CPU cost, and then the relative cost for different types of I/O I might perform, like random I/O versus sequential I/O.
Điều họ quan tâm là chi phí CPU, và chi phí tương đối của các loại I/O khác nhau mà tôi có thể thực hiện, như I/O ngẫu nhiên so với I/O tuần tự.
And then you weight them, these different factors, based on some magic constant you can specify in your configuration of the database system.
Rồi bạn gán trọng số cho các yếu tố khác nhau này, dựa trên một hằng số "ma thuật" mà bạn có thể chỉ định trong cấu hình của hệ quản trị cơ sở dữ liệu.
So let's say if something's in memory, that's going to be 400 times faster than reading something from a disk.
Ví dụ, nếu dữ liệu nằm trong bộ nhớ, thì nó nhanh hơn 400 lần so với đọc từ đĩa.
And if you're reading something that's sequential I/O, reading a sequence of pages that are one after another, that's going to be 4x faster than doing random I/O.
Và nếu bạn đọc theo kiểu I/O tuần tự, đọc một chuỗi các page nằm liền nhau, thì nó nhanh hơn 4 lần so với I/O ngẫu nhiên.
So if you go look at the Postgres documentation, you'll see all the definition of these parameters, like sequential scan cost, random page cost. These are numbers you can specify in these weighting factors.
Nếu bạn xem tài liệu của Postgres, bạn sẽ thấy định nghĩa của tất cả các tham số này, như chi phí quét tuần tự (sequential scan cost), chi phí trang ngẫu nhiên (random page cost). Đây là những con số bạn có thể chỉ định, tức là các hệ số trọng số này.
But it has this huge blurb right here that says, basically, warning, saying, hey, look, these are kind of just like, there isn't a good way to exactly determine these values, because it changes for different hardware.
Nhưng ngay chỗ đó có một đoạn giải thích rất dài, nói rằng, về cơ bản là một cảnh báo, kiểu như, này, các giá trị này chỉ là, không có cách nào tốt để xác định chính xác các giá trị này, vì nó thay đổi theo từng phần cứng khác nhau.
And so they're sort of meant to be a good guess estimate of what you should do.
Nên chúng chỉ được coi là một ước lượng đoán hợp lý về những gì bạn nên đặt.
And if you change them too much, they say you have problems because you end up picking bad query plans. So this is like, I would say Postgres cost model is not very sophisticated.
Và nếu bạn thay đổi chúng quá nhiều, họ nói bạn sẽ gặp vấn đề vì cuối cùng chọn ra các kế hoạch truy vấn tồi. Vì vậy tôi cho rằng mô hình chi phí của Postgres không phải là quá tinh vi.
It's the bare minimum you would need to have, say, you have a cost model in your database system.
Nó là mức tối thiểu bạn cần có, giả sử như, bạn muốn có một mô hình chi phí trong hệ quản trị cơ sở dữ liệu của mình.
The high-end systems, like DB2 and Oracle and those guys, they do all sorts of tricks to try to figure out what these actual values are.
Các hệ thống cao cấp, như DB2 và Oracle và những hệ tương tự, họ dùng đủ mọi mẹo để tìm ra các giá trị thực tế này.
Like when you turn on DB2 from IBM, they'll run a bunch of microbenchmarks to figure out, what is the cost of reading something from a disk? What is the cost?
Chẳng hạn khi bạn bật DB2 của IBM lên, nó sẽ chạy một loạt microbenchmark để xác định, chi phí đọc một thứ gì đó từ đĩa là bao nhiêu? Chi phí là bao nhiêu?
What is the actual time it takes to send a packet over the network? How fast is my CPU?
Thời gian thực tế để gửi một gói tin qua mạng là bao lâu? CPU của tôi nhanh đến mức nào?
And they use that in their cost model instead of these magic constants that you set in Postgres. You can still override that, but it's trying to compute things for you on their own.
Và họ dùng những giá trị đó trong mô hình chi phí thay cho các hằng số kỳ diệu mà bạn đặt trong Postgres. Bạn vẫn có thể ghi đè chúng, nhưng hệ thống tự cố gắng tính toán mọi thứ cho bạn.
Because that's trying to reflect the real hardware. So again, if your database moves from one machine to another, they'll automatically update.
Vì nó cố phản ánh phần cứng thực tế. Nên nếu cơ sở dữ liệu của bạn chuyển từ máy này sang máy khác, chúng sẽ tự động cập nhật.
Their question is, why doesn't Postgres do something more sophisticated? It's hard. And also too, the query optimizer, nobody wants to touch it in Postgres because it's very brittle.
Câu hỏi của bạn là tại sao Postgres không làm điều gì tinh vi hơn? Vì nó khó. Và nữa, bộ tối ưu hóa truy vấn, không ai muốn đụng vào nó trong Postgres vì nó rất dễ vỡ.
I would say it would be easier for them to add the DB2 calculations that I mentioned, the microbenchmarks.
Tôi cho rằng việc thêm các phép tính của DB2 mà tôi vừa nói sẽ dễ hơn cho họ, tức là các microbenchmark.
That's an easier thing to do than rewriting the whole engine, the query optimizer itself. That would be a major overhaul. Yes.
Đó là việc dễ làm hơn so với viết lại toàn bộ engine, tức là chính bộ tối ưu hóa truy vấn. Đó sẽ là một cuộc đại tu lớn. Vâng, mời bạn.
If you ever looked in Linux, if you ever looked at slash proc CPU info or do LSCPU, you'll see a thing called bogomips. That's a microbenchmark.
Nếu bạn từng xem trong Linux, xem /proc/cpuinfo hoặc chạy lscpu, bạn sẽ thấy một thứ gọi là bogomips. Đó là một microbenchmark.
When Linux starts up, it uses that as the timing for the scheduler. It's an approximation of how the whole production is.
Khi Linux khởi động, nó dùng giá trị đó làm mốc thời gian cho bộ lập lịch. Đó là một giá trị xấp xỉ cho tốc độ của toàn bộ hệ thống.
I would say also, Postgres, in the high-end systems, DB2, they're distributed parallel systems. So they need to worry about how much time it takes to send data over the network.
Tôi cũng muốn nói thêm, Postgres, còn các hệ thống cao cấp, DB2, là những hệ thống song song phân tán. Nên họ phải lo về thời gian gửi dữ liệu qua mạng.
Because they can also be aware of storage tiering, like fast local storage versus remote storage, they need to know what those times are as well.
Vì họ cũng có thể nhận biết việc phân tầng lưu trữ, như lưu trữ cục bộ nhanh so với lưu trữ từ xa, họ cũng cần biết những thời gian đó.
Postgres has no notion of those things. It just has table spaces.
Postgres không có khái niệm nào về những thứ này. Nó chỉ có table space.
The way we're going to get these estimates of how much work we think our operator is going to do, or how much data we think we're going to process, is going to be through statistics.
Cách chúng ta sẽ có được những ước lượng này về lượng công việc mà ta cho là toán tử của mình sẽ thực hiện, hoặc lượng dữ liệu mà chúng ta nghĩ mình sẽ xử lý, là thông qua thống kê.
When people talk about, in your data system, you're keeping track of statistics, it's basically internal metadata that the data system is going to collect on your data.
Khi người ta nói đến việc, trong hệ thống dữ liệu của bạn, bạn theo dõi các thống kê, thì về cơ bản đó là siêu dữ liệu nội bộ mà hệ thống dữ liệu thu thập về dữ liệu của bạn.
They're then using the query optimizer to try to figure out what is the expected work for either the logical level or the physical level for the different operators.
Sau đó, họ dùng bộ tối ưu hóa truy vấn để cố xác định khối lượng công việc kỳ vọng, ở mức logic hoặc mức vật lý, cho các toán tử khác nhau.
Again, we need to have these summaries because we can't actually just run our queries on the real data, although we can do sampling. We'll see that in a second.
Một lần nữa, chúng ta cần có các bản tóm tắt này vì chúng ta không thể chạy truy vấn trực tiếp trên dữ liệu thật, mặc dù chúng ta có thể lấy mẫu. Lát nữa chúng ta sẽ thấy điều đó.
But you can't run the full query, because by that point, I've already produced the answer that I would want from running the query.
Nhưng bạn không thể chạy toàn bộ truy vấn, vì đến lúc đó, tôi đã tạo ra đúng câu trả lời mà tôi muốn có khi chạy truy vấn rồi.
And getting the wrong join order, sometimes it can be 1,000x worse than picking the optimal plan. So we want to avoid all that.
Và chọn sai thứ tự join, đôi khi có thể tệ hơn kế hoạch tối ưu tới 1.000 lần. Vì vậy chúng ta muốn tránh tất cả những điều đó.
Of course, now the challenge is nothing comes for free, as is often the case in systems and data systems and computer science.
Tất nhiên, thách thức bây giờ là không có gì miễn phí, như thường thấy trong các hệ thống, hệ thống dữ liệu và khoa học máy tính.
So there would be this trade-off of how accurate you want our statistical summaries to be versus how much time you want to spend computing them, how much storage space you want to maintain or use to maintain these things.
Vì vậy sẽ có sự đánh đổi giữa việc bạn muốn các bản tóm tắt thống kê chính xác đến mức nào so với thời gian bạn muốn bỏ ra để tính chúng, và dung lượng lưu trữ bạn muốn dùng để duy trì chúng.
When things get updated in the database, do I stop what I'm doing immediately and go update my statistics? Or am I allowed to get a little bit out of date and suffer those consequences?
Khi dữ liệu trong cơ sở dữ liệu được cập nhật, tôi có dừng ngay việc đang làm để đi cập nhật thống kê không? Hay tôi được phép để chúng hơi lỗi thời và chịu hậu quả đó?
There's no one set of criteria I could say, "This is what you always want to do." It depends on so many different factors.
Không có một bộ tiêu chí nào để tôi nói: "Đây là điều bạn luôn nên làm." Nó phụ thuộc vào rất nhiều yếu tố khác nhau.
But most systems implement one approach to doing statistics. SQL Server and the high-end systems can do more. But in Postgres, they have pretty basic statistics.
Nhưng hầu hết các hệ thống cài đặt một cách tiếp cận để làm thống kê. SQL Server và các hệ thống cao cấp có thể làm nhiều hơn. Nhưng trong Postgres, thống kê khá cơ bản.
And you either run them when you ask it to, or you run it when you do background maintenance things.
Và bạn chạy chúng khi bạn yêu cầu, hoặc chạy khi hệ thống thực hiện các tác vụ bảo trì nền.
The way we're going to store these statistics is that they're just going to be another table in our database. It's a special table, an internal table in the catalog.
Cách chúng ta lưu các thống kê này là chúng chỉ là một bảng khác trong cơ sở dữ liệu của chúng ta. Đó là một bảng đặc biệt, một bảng nội bộ trong catalog.
But we're not going to store this in memory in a heap in a separate space. We'll just store it as a regular tuple.
Nhưng chúng ta sẽ không lưu nó trong bộ nhớ, trong một heap ở một không gian riêng. Chúng ta chỉ lưu nó như một tuple thông thường.
So that way we get all the storage and durability guarantees that we'd have as regular data.
Nhờ vậy chúng ta có mọi đảm bảo về lưu trữ và độ bền như với dữ liệu thông thường.
As I already said before, what triggers the DBMS to go collect the statistics depends on the implementation. It could be things like, in Oracle's case, I think it's like 10 p.m.
Như tôi đã nói trước đó, điều gì kích hoạt DBMS đi thu thập thống kê phụ thuộc vào cách cài đặt.
at night, they just run a job automatically to go collect new statistics for the day, for the next day.
Có thể là những thứ như, với Oracle, tôi nghĩ là 10 giờ tối, họ tự động chạy một tác vụ để thu thập thống kê mới cho ngày hôm đó, cho ngày hôm sau.
In Postgres, if you modify a table so much, by having it like 10 or 20%, then that goes ahead and triggers off the background job to go collect statistics.
Trong Postgres, nếu bạn sửa đổi một bảng nhiều đến mức, khoảng 10 hay 20%, thì nó sẽ kích hoạt tác vụ nền để đi thu thập thống kê.
And again, you can mainly do this using either, in Postgres it's ANALYZE, in other systems it's called UPDATE STATISTICS. So let me go to a quick demo so you can see these things.
Và một lần nữa, về cơ bản bạn có thể làm việc này bằng cách dùng hoặc là, trong Postgres là ANALYZE, còn ở các hệ thống khác thì gọi là UPDATE STATISTICS. Giờ tôi sẽ chạy một demo nhanh để các bạn thấy những thứ này.
Just to prove to you that they're just regular tables. And there's nothing special about them. Let me log in.
Chỉ để chứng minh với các bạn rằng chúng chỉ là những bảng bình thường. Và chẳng có gì đặc biệt về chúng cả. Để tôi đăng nhập.
So... Turn off the lights, although that might kill the camera, but whatever.
Giờ... tắt đèn đi, dù có thể làm camera bị tối, nhưng kệ.
I probably should do that, whatever. So this is Postgres. So Postgres has this table called pg_statistic. Anything with underscore pg is...
Có lẽ tôi nên làm vậy, kệ đi. Đây là Postgres. Postgres có một bảng tên là pg_statistic. Bất cứ thứ gì bắt đầu bằng pg_ thì...
And a name like that, that's an internal catalog for Postgres, right? So I see a bunch of stuff. What does that actually all mean? So let's do it on a per table basis.
Và một cái tên như vậy là catalog nội bộ của Postgres, đúng không? Tôi thấy một loạt thứ. Vậy tất cả những thứ này có nghĩa là gì? Vậy hãy xem theo từng bảng.
So remember before, I had this enroll table in my examples, right?
Nhớ lại trước đây, trong các ví dụ tôi có bảng enroll này, đúng không?
This had five records in it, keeping track of what grades people in the class, right?
Bảng này có năm bản ghi, theo dõi điểm của những người trong lớp, đúng không?
So I can go to pgStatistic and say, give me the statistics for this table, right?
Vậy tôi có thể vào pg_statistic và nói rằng, hãy cho tôi các thống kê của bảng này, đúng không?
So that's kind of hard to read, so let me put it in this sort of extended form, right?
Cái này khá khó đọc, nên tôi sẽ chuyển sang dạng mở rộng này, đúng không?
So when you think of, like, each block here is gonna be a, you know, is one row in the table. So what do we see? We see that we have the table name, enrolled.
Khi các bạn nghĩ về nó, mỗi khối ở đây sẽ là một dòng trong bảng. Vậy ta thấy gì? Ta có tên bảng, enrolled.
We have the attribute name, the column name, SID. Then we have some other stuff about, like, the number of distinct values, most common values, most common frequencies.
Ta có tên thuộc tính, tên cột, SID. Rồi một số thứ khác như số lượng giá trị phân biệt, các giá trị phổ biến nhất, các tần suất phổ biến nhất.
They don't have any histograms here because there's not a lot of data.
Ở đây không có histogram nào vì không có nhiều dữ liệu.
But you can see, like, they're keeping track of a bunch of things, and they're just rows and arrays in the table, right?
Nhưng các bạn thấy là họ theo dõi khá nhiều thứ, và chúng chỉ là các dòng và mảng trong bảng, đúng không?
And so if I go ahead and kill this, let's delete the stats for, you know, for this table. Now I'm gonna go back and try to read it, right? Nothing shows up.
Và nếu tôi xóa cái này đi, hãy xóa các thống kê của bảng này. Giờ tôi quay lại thử đọc, đúng không? Không hiện gì cả.
So if I tell Postgres to run analyze on that table, it takes 23 milliseconds because, you know, it fits on one page.
Nếu tôi bảo Postgres chạy analyze trên bảng đó, nó mất 23 mili giây vì bảng vừa vặn trong một trang.
And then now when I go back, I see again all the same stats as before.
Và giờ khi quay lại, tôi lại thấy tất cả các thống kê như trước.
And this is what we're gonna use in our cost model to figure out how much data actually exists when I do estimations.
Và đây là thứ ta sẽ dùng trong mô hình chi phí để biết thực sự có bao nhiêu dữ liệu khi tôi thực hiện ước lượng.
So just to give you what a real table might look like with real stats. So this is from our encyclopedia db.io. But now you can see, now you have this histogram bounds.
Để cho các bạn thấy một bảng thật với thống kê thật trông như thế nào. Đây là từ bách khoa toàn thư db.io của chúng tôi. Giờ các bạn thấy có histogram bounds này.
You have the histogram bounds. There's no frequent values for any of these.
Có các histogram bounds. Không có giá trị thường gặp nào cho các cột này.
But, like, you basically see, like, in the storing, this one is for is current to false, and you have the frequency of those, Right?
Nhưng về cơ bản các bạn thấy, trong phần lưu trữ, cột này là is current bằng false, và bạn có tần suất của chúng, đúng không?
Most of the data in this is where the is current is set to false. So it's just, there's nothing magic about this. They're just data structures stored in, stored as a regular table.
Phần lớn dữ liệu ở đây có is current được đặt là false. Nên chẳng có gì kỳ diệu cả. Chúng chỉ là các cấu trúc dữ liệu được lưu như một bảng bình thường.
But it's not something you should be maintaining or doing yourself. Like the data structures do this for you. And this is what I've already said before.
Nhưng đây không phải thứ bạn nên tự duy trì hay tự làm. Các cấu trúc dữ liệu sẽ làm việc này cho bạn. Và đây là điều tôi đã nói trước đó.
So for every single column in a table, the data system is gonna go try to collect these statistics and basically maintain some histograms and other things that we'll talk about in a second.
Vậy với mỗi cột trong một bảng, hệ thống dữ liệu sẽ thu thập các thống kê này và về cơ bản là duy trì một số histogram và những thứ khác mà lát nữa chúng ta sẽ nói tới.
So sometimes in some systems, they'll also track the statistics for groups of columns or groups of attributes. These are called correlated statistics.
Vậy nên đôi khi, ở một số hệ thống, họ cũng theo dõi thống kê cho các nhóm cột hoặc nhóm thuộc tính. Chúng được gọi là thống kê tương quan (correlated statistics).
So if I know that, like, if there's a correlation between, like, zip code and city, like every city can only be in one zip code.
Giả sử tôi biết rằng, có một mối tương quan giữa, chẳng hạn, mã bưu chính và thành phố, như kiểu mỗi thành phố chỉ có thể nằm trong một mã bưu chính.
So instead of treating them as independent variables, I know they're correlated and I can compute stats on those combination of those two columns together.
Thay vì coi chúng là các biến độc lập, tôi biết chúng có tương quan và tôi có thể tính thống kê trên tổ hợp của hai cột đó cùng nhau.
So then when I do my estimations, I get better results.
Như vậy khi ước lượng, tôi sẽ có kết quả tốt hơn.
So in SQL, you can say CREATE CORRELATED STATISTICS. You can tell it I wanna create statistics on multiple columns.
Trong SQL, bạn có thể viết CREATE CORRELATED STATISTICS. Bạn có thể cho nó biết là tôi muốn tạo thống kê trên nhiều cột.
In some systems like SQL Server, if you put two columns together in an index, the data system says, oh, they must be important. They must go together.
Ở một số hệ thống như SQL Server, nếu bạn đặt hai cột cùng nhau trong một chỉ mục, hệ thống dữ liệu sẽ nghĩ: ồ, chắc chúng quan trọng. Chắc chúng đi cùng nhau.
So let me compute the correlated statistics for them together, right?
Vậy để tôi tính thống kê tương quan cho cả hai cùng nhau, đúng không?
Otherwise, because it's combinatorial, the number of different choices you have of correlated statistics, you don't wanna generate all these things, that'd be expensive to do.
Nếu không thì, vì đây là bài toán tổ hợp, số lựa chọn thống kê tương quan khác nhau mà bạn có rất lớn, bạn không muốn tạo hết chúng, vì sẽ rất tốn kém.
So they try to use tricks to figure out which ones they actually combine together. All right, so there's gonna be four approaches for how we wanna maintain our statistics.
Nên họ dùng các mẹo để xác định những cột nào thực sự nên kết hợp với nhau. Được rồi, vậy có bốn cách tiếp cận để duy trì thống kê.
All right, four different types of statistical data structures. The first is gonna be histograms. This is the most common thing. This is what we saw in Postgres.
Bốn loại cấu trúc dữ liệu thống kê khác nhau. Đầu tiên là histogram. Đây là thứ phổ biến nhất. Đây là thứ chúng ta đã thấy trong Postgres.
And this is just for each occurrence of a unique value within a column, Count the number of times that it shows up, or you're bucketing them together.
Với mỗi giá trị duy nhất xuất hiện trong một cột, đếm số lần nó xuất hiện, hoặc gom chúng vào các bucket.
And we'll see that in a second. Another one would be sketches. You've already saw a sketch in Project Zero, the count-min sketch.
Lát nữa chúng ta sẽ thấy. Loại khác là sketch. Bạn đã thấy một sketch trong Project Zero, đó là count-min sketch.
And these are statistical approximations or probabilistic data structures that can approximate the different factors or aspects of the data.
Đây là các cấu trúc dữ liệu xấp xỉ thống kê hay xác suất có thể ước lượng các yếu tố hay khía cạnh khác nhau của dữ liệu.
Sampling would be when we maintain a small snapshot or small subset of the original tables and use that to estimate statistics.
Sampling là khi chúng ta duy trì một bản chụp nhỏ hay một tập con nhỏ của các bảng gốc và dùng nó để ước lượng thống kê.
Or in some cases, maybe run mini queries against the real data and then try to extract the statistical properties of the data from that sample.
Hoặc trong một số trường hợp, chạy các truy vấn nhỏ trên dữ liệu thật rồi cố trích xuất các thuộc tính thống kê của dữ liệu từ mẫu đó.
And then the last one would be more modern techniques using machine learning models that try to learn the cardinality, learn the statistical properties of tables.
Và cuối cùng là các kỹ thuật hiện đại hơn dùng mô hình học máy để học cardinality, học các thuộc tính thống kê của bảng.
So in terms of what systems implement what, very top, histograms, the most common one because they're the easiest.
Về việc hệ thống nào triển khai cái gì, trên cùng là histogram, phổ biến nhất vì dễ nhất.
In the modern era, the last 20 years, or yeah, about 15, 20 years, sketches are becoming more common. And you can use these in combination with each other. Sampling is very rare.
Trong kỷ nguyên hiện đại, 20 năm qua, hay đúng hơn khoảng 15, 20 năm, sketch đang trở nên phổ biến hơn. Và bạn có thể dùng chúng kết hợp với nhau. Sampling thì rất hiếm.
I think only the Germans and Umbra and SQL Server use sampling. I'm not aware of any other system that does sampling. And then ML stuff, nobody's putting this in production yet.
Tôi nghĩ chỉ có hệ thống của người Đức, Umbra và SQL Server dùng sampling. Tôi không biết hệ thống nào khác dùng sampling. Còn các kỹ thuật ML thì chưa ai đưa vào môi trường production cả.
The research is very promising, but it's still, it's very early. Yes.
Nghiên cứu rất triển vọng, nhưng vẫn còn rất sớm. Vâng, mời em.
The question is, how do I deal with very high cardinality columns? These slides here, yes, we'll get there, yeah.
Câu hỏi là: xử lý các cột có cardinality rất cao thì sao? Những slide này, vâng, chúng ta sẽ nói tới phần đó.
All right, so again, histograms, just think of like a hash map where you keep track of a hash table, keep track of like for every unique value in my column, I'm gonna maintain the number of times that I've seen it.
Được rồi, vậy histogram, cứ hình dung như một hash map, tức là bạn duy trì một bảng băm, theo dõi từng giá trị duy nhất trong cột của tôi, và tôi sẽ lưu số lần đã gặp giá trị đó.
Right? So say I'm keeping track of people's age or something like this, and it's only people aged from one to 15, right? I just keep track of every single unique value.
Đúng không? Ví dụ tôi đang theo dõi tuổi của mọi người hay đại loại vậy, và chỉ có những người từ một đến 15 tuổi, đúng không? Tôi chỉ việc theo dõi từng giá trị duy nhất.
Here's the number of occurrences that they have.
Đây là số lần xuất hiện của chúng.
So in my toy example here, I have to maintain the original column, the original data in the table itself, but now I gotta maintain this other histogram to keep track of every single unique value I have in that column.
Vậy trong ví dụ đơn giản này, tôi phải giữ cột gốc, tức dữ liệu gốc trong chính bảng, nhưng giờ còn phải duy trì thêm histogram này để theo dõi từng giá trị duy nhất có trong cột đó.
So my example here, it's small. It's only like 60 bytes plus the maybe 32 or 64 bytes for each occurrence. But think in terms of like billions of entries in the column, right?
Ví dụ của tôi ở đây thì nhỏ. Chỉ khoảng 60 byte cộng với có thể 32 hoặc 64 byte cho mỗi số lần xuất hiện. Nhưng hãy nghĩ tới cột có hàng tỉ phần tử, đúng không?
To store 1 billion values with 32-bit numbers, it's gonna be four gigs. Four something, yeah, 4.1 something gigs, right? So that's not the data itself.
Để lưu 1 tỉ giá trị bằng số 32 bit thì cần bốn gigabyte. Bốn phẩy gì đó, vâng, 4,1 gì đó gigabyte. Đó chưa phải là dữ liệu.
That's the histogram about the data for one column.
Đó là histogram về dữ liệu của một cột.
So for every single column, if I'm gonna record all the unique values in the accounts for them, then that's obviously gonna be really, really big, and I don't wanna do that.
Vậy với mỗi cột, nếu tôi ghi lại mọi giá trị duy nhất cùng số lần đếm của chúng, thì rõ ràng nó sẽ rất rất lớn, và tôi không muốn làm vậy.
What's that? The question, the counter's small? But still, like, could be, right? Yeah, in that case, if every value's unique, then the count is one, yes.
Sao cơ? Câu hỏi là bộ đếm nhỏ ư? Nhưng vẫn có thể lớn, đúng không? Vâng, trong trường hợp đó, nếu mọi giá trị đều duy nhất thì số đếm là một, đúng.
Then that's small. You could bit-pack that, yes. But still, it's like it's, that's for one column in one table.
Khi đó nó nhỏ. Có thể bit-pack nó, đúng vậy. Nhưng đó mới chỉ là một cột trong một bảng.
If my table has 100 columns, or hundreds of columns, then it becomes super expensive to do. So we gotta reduce the size, and there's a couple tricks to do this.
Nếu bảng của tôi có 100 cột, hoặc hàng trăm cột, thì chi phí sẽ cực kỳ đắt. Vì vậy ta phải giảm kích thước, và có vài mẹo để làm việc này.
One is to do an equi-width histogram, where instead of storing every unique value with their own separate count, I'm gonna bucket them together, where the size of each bucket will be the same.
Một là dùng histogram equi-width, trong đó thay vì lưu mỗi giá trị duy nhất với số đếm riêng, tôi sẽ gom chúng lại thành các bucket, với kích thước mỗi bucket bằng nhau.
Like, the width of the bucket is gonna be the same, hence the name equi-width.
Tức là độ rộng của bucket đều như nhau, nên mới gọi là equi-width.
So I would convert my original histogram into something like this, where I'm just gonna store now the range of values that I have, and then a separate count for that.
Vậy tôi sẽ chuyển histogram gốc thành dạng như thế này, trong đó giờ tôi chỉ lưu khoảng giá trị, và một số đếm riêng cho khoảng đó.
So, if now I wanna get the estimate, like, say, the something equals something, how many times is that gonna occur?
Giờ nếu tôi muốn ước lượng, ví dụ điều kiện cái gì đó bằng cái gì đó, thì nó sẽ xuất hiện bao nhiêu lần?
I would figure out what bucket it's in, take whatever the count is, and divide it by the number of values in the bucket, like size four. Okay, we'll cover those formulas in a second.
Tôi xác định nó nằm trong bucket nào, lấy số đếm của bucket đó, rồi chia cho số giá trị trong bucket, ở đây là kích thước bốn. Được rồi, các công thức đó lát nữa ta sẽ bàn.
Another approach is to use equi-depth histograms, and these are shown to be better than equi-width because they are, because, again, you're, for the heavy hitters, they're not gonna get sort of lost in the noise with a bunch of low-rank or low-occurrence values.
Một cách khác là dùng histogram equi-depth, và loại này được chứng minh là tốt hơn equi-width vì chúng, bởi vì, một lần nữa, đối với các giá trị xuất hiện rất nhiều, chúng sẽ không bị chìm lẫn trong nhiễu giữa một đống giá trị có thứ hạng thấp hay ít xuất hiện.
So the idea is here now, I don't want the width of the bucket to be the same, I want the height of the bar per bucket to be the same.
Vậy ý tưởng ở đây là, giờ tôi không muốn độ rộng của các bucket bằng nhau, mà tôi muốn chiều cao của cột trên mỗi bucket bằng nhau.
So in this case here, the height of just putting 14 and 15 together, the height combining them will be 12, right?
Như trong trường hợp này, nếu gộp 14 và 15 lại với nhau, thì chiều cao khi gộp sẽ là 12, đúng không?
Versus like bucket three here, I had to put nine, 10, 11, 12, 13, and the height of that's gonna be nine, right?
Còn so với bucket ba ở đây, tôi phải gộp chín, 10, 11, 12, 13, và chiều cao của nó sẽ là chín, đúng không?
So this is a way to sort of handle the outliers because now they're gonna be sort of, you have a more accurate count because there's fewer elements within each bucket, potentially.
Vậy đây là một cách để xử lý các giá trị ngoại lai, bởi vì bây giờ chúng sẽ, bạn có số đếm chính xác hơn vì có ít phần tử hơn trong mỗi bucket, có thể là vậy.
So now related to his problem or his question, their question about like, what about if I have like heavy hitters or values that occur a lot, wouldn't it be nice to have, you know, accurate counts of those things?
Bây giờ liên quan đến vấn đề hay câu hỏi của bạn ấy, về việc, nếu tôi có các giá trị xuất hiện rất nhiều thì chẳng phải sẽ tốt nếu có, bạn biết đấy, số đếm chính xác của chúng sao?
So I can do what's called an N-bias histogram where I'm gonna use N minus one buckets to keep track of an exact count for the most frequent keys that I see.
Vậy tôi có thể dùng cái gọi là histogram N-bias trong đó tôi dùng N trừ một bucket để theo dõi số đếm chính xác của các khóa xuất hiện thường xuyên nhất.
And then for everybody else, they get thrown in this last bucket R that's just trying to say, okay, well, you know, you're probably not gonna need these keys that often, they don't occur that often, so therefore it's okay to have a less accurate count for those guys.
Còn với tất cả những khóa còn lại, chúng bị ném vào bucket cuối cùng R, nó chỉ nhằm nói rằng, được rồi, có lẽ bạn sẽ không cần đến các khóa này thường xuyên đâu, chúng không xuất hiện thường xuyên, nên chấp nhận số đếm kém chính xác hơn cho chúng.
So you just basically look at, what are all my most frequent keys?
Vậy về cơ bản bạn chỉ cần xem, những khóa nào xuất hiện thường xuyên nhất?
And then I store them as, again, exact counts, and then everybody else, I'm sorry, everybody else just ends up with this R1 over here.
Rồi tôi lưu chúng dưới dạng số đếm chính xác, còn tất cả những khóa khác, xin lỗi, tất cả những khóa khác chỉ nằm vào R1 ở đây.
Yes.
Vâng, mời bạn.
Their question is, if the distribution of the, rephrase what you're saying, if the distribution of the values change where now there's a new most frequent key, do I have to rebuild this?
Câu hỏi của bạn ấy là, nếu phân phối của, nói lại ý bạn nhé, nếu phân phối của các giá trị thay đổi và giờ có một khóa mới xuất hiện nhiều nhất, thì tôi có phải xây dựng lại cái này không?
Yes. And that's what the, that ANALYZE command I did basically goes through, wipes away whatever my histograms are and recomputes them.
Có. Và đó là việc mà lệnh ANALYZE tôi chạy về cơ bản sẽ duyệt qua, xóa sạch các histogram hiện có và tính toán lại chúng.
Now Postgres is gonna be a little bit, try to be a little bit more clever and do things like, keep track of, without running ANALYZE, my explicit ANALYZE, but like without, if I'm doing this sort of incrementally, I can keep track of, here's the pages that I haven't modified since the last time I analyzed them, so don't reanalyze them, and then use it incrementally up these things.
Giờ Postgres sẽ cố gắng thông minh hơn một chút và làm những việc như theo dõi, mà không cần chạy ANALYZE tường minh của tôi, nhưng mà không cần, nếu tôi làm kiểu tăng dần, tôi có thể theo dõi rằng, đây là các trang mà tôi chưa sửa đổi kể từ lần phân tích gần nhất, nên đừng phân tích lại chúng, rồi dùng cách đó để cập nhật dần dần.
But again, you can call those errors, and then call those problems, but whatever. It's an approximation anyway, so you're already gonna be error-prone. Yes.
Nhưng một lần nữa, bạn có thể gọi đó là lỗi, rồi gọi đó là vấn đề, nhưng thôi kệ. Dù sao nó cũng chỉ là xấp xỉ, nên vốn dĩ đã dễ sai số rồi. Vâng, mời bạn.
How are the histograms implemented? In the case of Postgres, I showed you, it's just an array of values. Nothing fancy. All right, sketches.
Các histogram được cài đặt như thế nào? Với Postgres, như tôi đã cho bạn xem, nó chỉ là một mảng các giá trị. Không có gì cầu kỳ. Được rồi, sketch.
Again, I think, the count-min sketch we've already covered, but there's basically versions of sketches that provide different, can answer different questions like, what's the most frequent items?
Một lần nữa, tôi nghĩ count-min sketch thì chúng ta đã học rồi, nhưng về cơ bản có nhiều phiên bản sketch khác nhau, có thể trả lời những câu hỏi khác nhau, ví dụ như các phần tử nào xuất hiện thường xuyên nhất?
I use count-min sketch. How do I count the number of distinct items? I use HyperLogLog. And there's a lot of great open-source implementations now. The Apache DataSketches is probably the best one.
Tôi dùng count-min sketch. Vậy làm sao đếm số lượng các phần tử phân biệt? Tôi dùng HyperLogLog. Và hiện nay có rất nhiều bản cài đặt mã nguồn mở rất tốt. Apache DataSketches có lẽ là bản tốt nhất.
It originally started out in Java, but now I think there's implementations in Rust and C++. Those are probably the best ones.
Ban đầu nó được viết bằng Java, nhưng giờ tôi nghĩ đã có các bản cài đặt bằng Rust và C++. Đó có lẽ là những bản tốt nhất.
The Google ZetaSketch, I don't think they're actually maintaining that anymore, but it is an open-source one.
Còn ZetaSketch của Google thì tôi nghĩ họ không còn duy trì nó nữa, nhưng nó là một bản mã nguồn mở.
So you can replace all your histograms, in theory, with sketches, because they'll give you the same, sort of answer the same kind of questions, and in some cases, they're more easily mergeable than histograms, but they have different properties.
Vậy về lý thuyết, bạn có thể thay toàn bộ histogram bằng sketch, vì chúng sẽ trả lời cùng loại câu hỏi như vậy, và trong một số trường hợp, chúng dễ hợp nhất hơn histogram, nhưng chúng có những đặc tính khác nhau.
All right, so I'm going to skip the count-min sketch and the HyperLogLog stuff, because I want to get to the, Let me cover sampling real quickly, because we want to get to the cardinality stuff, because we need that for the next homework.
Được rồi, tôi sẽ bỏ qua phần count-min sketch và HyperLogLog, vì tôi muốn đi tới phần... Để tôi nói nhanh về lấy mẫu, vì chúng ta muốn đến phần cardinality, vì chúng ta cần nó cho bài tập về nhà tiếp theo.
All right, so sampling, again, is just that you have a subset of the data, or you examine a subset of the table, of the data you want to access, and try to predict the properties of it.
Được rồi, lấy mẫu (sampling) đơn giản là bạn có một tập con của dữ liệu, hoặc bạn xem xét một tập con của bảng, của dữ liệu mà bạn muốn truy cập, và cố dự đoán các tính chất của nó.
So you can either maintain a separate read-only copy of your data, like a small portion of it, and you do all your estimates on that thing, on that sample, or you can do a sample against the real data, but you have to be careful not to interfere with queries that are actually running for real, not just sampling information.
Bạn có thể duy trì một bản sao chỉ đọc riêng của dữ liệu, chẳng hạn một phần nhỏ của nó, và thực hiện mọi ước lượng trên đó, trên mẫu đó, hoặc bạn có thể lấy mẫu ngay trên dữ liệu thật, nhưng bạn phải cẩn thận để không gây ảnh hưởng đến các truy vấn đang chạy thật sự, chứ không chỉ là lấy thông tin mẫu.
And so the way SQL Server does it, they do the first one. I don't know of anybody that does the second one.
Cách SQL Server làm là chọn cách đầu tiên. Tôi không biết hệ nào làm theo cách thứ hai.
MySQL kind of does the second one, but they're not really sampling to get stats.
MySQL có phần giống cách thứ hai, nhưng thực ra họ không lấy mẫu để thu thập thống kê.
What MySQL will do in some cases, they will recognize you have a subquery in the middle of the optimizer, stop what they're doing, go run that query for real, and get the result back.
Điều MySQL làm trong một số trường hợp là nhận ra bạn có một truy vấn con ở giữa trình tối ưu hóa, dừng việc đang làm, chạy truy vấn đó thật sự rồi lấy kết quả về.
So it's not exactly sampling, but it is going against the real data.
Vậy nó không hẳn là lấy mẫu, nhưng nó chạy trên dữ liệu thật.
In SQL Server's case, when they start running the optimizer, if they recognize I don't have stats when the query shows up, they'll stop the optimization process, run Analyzer, and go collect a sample, and go collect statistics, and then come back to the optimizer.
Với SQL Server, khi bắt đầu chạy trình tối ưu hóa, nếu nhận ra mình không có thống kê khi truy vấn đến, họ sẽ dừng quá trình tối ưu hóa, chạy Analyzer, đi lấy một mẫu, thu thập thống kê, rồi quay lại trình tối ưu hóa.
Because they don't want to make bad predictions. All right, so the basic idea is like this. You have a table, a bunch of people.
Vì họ không muốn đưa ra những dự đoán tồi. Được rồi, ý tưởng cơ bản như sau. Bạn có một bảng gồm nhiều người.
You want to find people, all the people in your database that are above age 50. So the sample would basically do a random, pick random tuples from this.
Bạn muốn tìm tất cả những người trong cơ sở dữ liệu có tuổi trên 50. Việc lấy mẫu về cơ bản là chọn ngẫu nhiên các tuple từ bảng này.
And there's different ways to do more sophisticated types of sampling. And then I have my little sample here. I have Obama, Tupac, and DJ Cash.
Và có nhiều cách để lấy mẫu phức tạp hơn. Và đây là mẫu nhỏ của tôi. Tôi có Obama, Tupac và DJ Cash.
I have their status, what's going on in their lives. And then now what I want to estimate is what the selectivity is for all the people who are age greater than 50.
Tôi có tình trạng của họ, cuộc sống của họ đang như thế nào. Và điều tôi muốn ước lượng bây giờ là độ chọn lọc (selectivity) của những người có tuổi lớn hơn 50.
In this case here, it's only Obama who is that old, because Tupac's dead, and he's only 21. Are you 21 or 20? How old are you? 23, all right. Well, all by two, sorry.
Trong trường hợp này, chỉ có Obama là già như vậy, vì Tupac đã mất rồi, và anh ấy chỉ mới 21 tuổi. Bạn 21 hay 20 tuổi? Bạn bao nhiêu tuổi? 23, được rồi. Thôi, lệch hết hai tuổi, xin lỗi.
All right, so in that case here, the table, the probability of people above age 50 is one third. And you would say that roughly maps to what it is in the real table, right?
Được rồi, vậy trong trường hợp này, với bảng này, xác suất những người trên 50 tuổi là một phần ba. Và bạn sẽ nói rằng con số đó xấp xỉ với giá trị trong bảng thật, đúng không?
All right, so with either samples, the sketches, or the histograms, we now want to predict the cardinality of the different operators.
Được rồi, vậy với mẫu, sketch hay histogram, giờ chúng ta muốn dự đoán cardinality của các toán tử khác nhau.
Like how much data, or how many tuples, is each operator going to produce?
Ví dụ mỗi toán tử sẽ tạo ra bao nhiêu dữ liệu, hay bao nhiêu tuple?
Because then we can use that as the backbone for other decisions, like, all right, how many tuples am I going to produce?
Bởi vì khi đó ta có thể dùng nó làm nền tảng cho các quyết định khác, chẳng hạn, được rồi, tôi sẽ tạo ra bao nhiêu tuple?
That'll determine how much data I may have to read or write in my other operators in my query plan.
Điều đó sẽ quyết định lượng dữ liệu tôi có thể phải đọc hoặc ghi trong các toán tử khác của kế hoạch truy vấn.
And so the basic things we need to be able to predict are what the selection conditions could be for filters.
Và vì vậy những thứ cơ bản mà ta cần dự đoán được là các điều kiện chọn của bộ lọc có thể là gì.
Like if I have a predicate on a table, how many tuples are going to match that predicate, and therefore how many tuples are going to come as part of the output?
Ví dụ nếu tôi có một vị từ trên một bảng, thì sẽ có bao nhiêu tuple khớp với vị từ đó, và do đó có bao nhiêu tuple sẽ nằm trong kết quả đầu ra?
Or if I do a join, and I join two tables together, how many tuples are going to be produced from doing that join?
Hoặc nếu tôi thực hiện phép join, nối hai bảng với nhau, thì phép join đó sẽ tạo ra bao nhiêu tuple?
And then likewise, if I'm doing a distinct value estimation for a group by clause, how many tuples do I expect to come out of that?
Và tương tự, nếu tôi ước lượng số giá trị phân biệt cho mệnh đề group by, thì tôi kỳ vọng có bao nhiêu tuple đi ra từ đó?
So if you have those three estimations, then that's the building block you need to do more complex things, like multiple joins, and group bys, and other sorting things.
Vậy nếu bạn có ba loại ước lượng này, thì đó là khối xây dựng bạn cần để làm những việc phức tạp hơn, như nhiều phép join, group by, và các thao tác sắp xếp khác.
So the way this is going to work is that we're going to produce what are called derivable statistics that we can extract from the statistical summaries that Jason has collected and built From our tables.
Cách việc này hoạt động là chúng ta sẽ tạo ra cái gọi là các thống kê suy ra được mà ta có thể trích xuất từ các bản tóm tắt thống kê mà Jason đã thu thập và xây dựng từ các bảng của chúng ta.
And so for this, we'll say the n subscript r, which is going to say the number of tuples we have in the relation, and then we'll have this new function v that's going to tell us the number of distinct values we would have for an attribute a.
Và ở đây, ta sẽ có n chỉ số dưới r, cho biết số tuple có trong quan hệ, và sau đó ta có hàm mới v cho ta biết số giá trị phân biệt của thuộc tính a.
So I'm not saying, again, at this point, is it greater than a or less than a?
Một lần nữa, ở đây tôi chưa nói là lớn hơn a hay nhỏ hơn a.
I'm just saying for a given value a, how many occurrences do I have of this in my columns? And then I want to compute what's called a selection cardinality.
Tôi chỉ nói với một giá trị a cho trước, thì có bao nhiêu lần xuất hiện của nó trong các cột của tôi? Và sau đó tôi muốn tính cái gọi là selection cardinality.
It's going to be the average number of tuples that I expect to produce for a given attribute a given the number of tuples that I have in my relation.
Đó là số tuple trung bình mà tôi kỳ vọng sẽ tạo ra cho một thuộc tính a cho trước, dựa trên số tuple có trong quan hệ.
And then from this, that's what we use to basically estimate the selectivity.
Và từ đó, chúng ta dùng nó để ước lượng selectivity.
So depending on what the predicate looks like, there's different formulas we're going to use for the statistics we've collected, and we use histograms as the basic version of this, to say here's the number of tuples I expect to qualify for my predicates or whatever it is the operation I'm doing.
Vậy tùy vào dạng của vị từ, sẽ có các công thức khác nhau cho các thống kê đã thu thập, và chúng ta dùng histogram làm phiên bản cơ bản của việc này, để nói rằng đây là số tuple tôi kỳ vọng thỏa mãn các vị từ của tôi, hay bất kể phép toán nào tôi đang thực hiện.
And therefore, that's the number of tuples I expect to come out of my operator. So let's look at the easiest one.
Và do đó, đó là số tuple tôi kỳ vọng sẽ đi ra từ toán tử của mình. Vậy hãy xem trường hợp dễ nhất.
The easiest one's going to be a predicate where age equals nine, an equality predicate. Something equals something. Right?
Trường hợp dễ nhất sẽ là một vị từ trong đó age bằng 9, một vị từ so sánh bằng. Cái gì đó bằng cái gì đó. Đúng không?
So if I had my histogram I had before, and I had the exact number of occurrences for every unique value, then to compute the selectivity of this predicate, it's just saying the number of occurrences divided by the number of unique values, or unique number of tuples that I have in my table.
Vậy nếu tôi có histogram như lúc trước, và có số lần xuất hiện chính xác cho mọi giá trị duy nhất, thì để tính selectivity của vị từ này, nó chỉ là số lần xuất hiện chia cho số giá trị duy nhất, hay số lượng tuple duy nhất mà tôi có trong bảng.
Right? So now for the selectivity age equals nine, I just go look at my histogram. What's the number of tuples I expect to match? In this case, four.
Đúng không? Vậy bây giờ với độ chọn lọc của age bằng 9, tôi chỉ cần xem histogram của mình. Số tuple tôi kỳ vọng khớp là bao nhiêu? Trong trường hợp này là bốn.
So therefore, the selectivity of this predicate is four divided by 45. And I get 0.088.
Vì vậy, độ chọn lọc của vị từ này là bốn chia 45. Và tôi được 0,088.
So this is saying that for all the tuples that are in my table people, or table R here, when I apply this predicate, 0.08 will match.
Điều này có nghĩa là trong tất cả các tuple thuộc bảng people của tôi, hay bảng R ở đây, khi tôi áp dụng vị từ này, sẽ có 0,08 số tuple khớp.
But again, we said that we don't want to maintain an exact count for the number of values in a histogram. We want to use one of these equi-depth ones, for example.
Nhưng như đã nói, chúng ta không muốn duy trì số đếm chính xác cho số lượng giá trị trong một histogram. Chẳng hạn, chúng ta muốn dùng loại equi-depth.
So now, my approximation is going to be based on whatever bucket I land in. In this case here, age nine lands us on nine to 13 inclusive.
Vậy bây giờ, giá trị xấp xỉ của tôi sẽ dựa trên bucket mà tôi rơi vào. Ở đây, age bằng 9 đưa chúng ta vào khoảng từ 9 đến 13, bao gồm cả hai đầu.
So now my estimation is going to be the count here for this bucket, which is nine, divided by the number of values that are within this range of the bucket, five.
Vậy ước lượng của tôi sẽ là số đếm của bucket này, là chín, chia cho số lượng giá trị nằm trong khoảng của bucket này, là năm.
And then now that gives me my estimate here. What's the problem with this approach? Yes.
Và đó là ước lượng của tôi ở đây. Cách tiếp cận này có vấn đề gì? Vâng, mời bạn.
The statement is, it represents not multiple predicates, but multiple values in the bucket, not just the one I'm looking for. Absolutely, yes. I'm also assuming that it's a continuous range of values.
Ý bạn là, nó đại diện không phải cho nhiều vị từ, mà cho nhiều giá trị trong bucket, chứ không chỉ giá trị tôi đang tìm. Chính xác. Tôi cũng đang giả định đó là một khoảng giá trị liên tục.
In this example here, it's people age nine to 13. Not a big deal, but think of really big tables with really big numbers. They have gaps in that sequence.
Trong ví dụ này, đó là những người có tuổi từ 9 đến 13. Không có gì to tát, nhưng hãy nghĩ đến những bảng rất lớn với những con số rất lớn. Chúng có những khoảng trống trong dãy đó.
So I'm assuming here that for all the values that appear in this bucket, they occur with the same probability as all the other values in the same bucket.
Vậy ở đây tôi giả định rằng tất cả các giá trị xuất hiện trong bucket này đều xuất hiện với xác suất bằng với các giá trị khác trong cùng bucket.
That's why I'm dividing by five.
Đó là lý do tôi chia cho năm.
So the dirty secret in cost models is that there's a bunch of assumptions we have to make because we don't have accurate statistics and a complete view of the data.
Vậy, bí mật không mấy đẹp đẽ của các mô hình chi phí là chúng ta phải đưa ra một loạt giả định vì chúng ta không có thống kê chính xác và cái nhìn đầy đủ về dữ liệu.
Those are assumptions we have to make in our formulas in order to make this thing probably even tractable. Again, I keep bringing up the enterprise systems do this, Oracle does that.
Đó là những giả định chúng ta phải đưa vào các công thức để bài toán này có thể giải quyết được. Tôi cứ nhắc đi nhắc lại rằng các hệ thống doanh nghiệp làm thế này, Oracle làm thế kia.
This is one of the big differences you're going to get when you pay Oracle millions and millions of dollars and SQL Server millions of dollars for their data systems.
Đây là một trong những khác biệt lớn mà bạn sẽ nhận được khi trả cho Oracle hàng triệu đô la và cho SQL Server hàng triệu đô la để dùng hệ thống dữ liệu của họ.
Their cost models will be way more sophisticated. Their formulas will be way more sophisticated than what Postgres has. To their point, can't Postgres just write a better one?
Mô hình chi phí của họ tinh vi hơn nhiều. Các công thức của họ tinh vi hơn nhiều so với của Postgres. Theo ý bạn, Postgres không thể viết một cái tốt hơn sao?
Sure, but you need people that are experts in query optimizers, and they're not cheap. The best ones are at SQL Server or the Germans.
Được chứ, nhưng cần những người là chuyên gia về bộ tối ưu hóa truy vấn, mà họ không rẻ. Những người giỏi nhất ở SQL Server hoặc là người Đức.
So one of the assumptions we're going to make is that we're going to assume that the distribution of data is going to be uniform.
Vậy một trong những giả định chúng ta sẽ đưa ra là chúng ta sẽ giả định rằng phân bố dữ liệu là đồng đều.
That the occurrence of every single value within a column is going to appear with the equal probability of all other columns or other values in that same column.
Tức là mỗi giá trị trong một cột sẽ xuất hiện với xác suất bằng với tất cả các cột khác hay các giá trị khác trong cùng cột đó.
Now, we can mitigate this a little bit by keeping track of the heavy hitters, by keeping track of the most frequent values separately in the equi-width histogram.
Giờ, chúng ta có thể giảm nhẹ vấn đề này phần nào bằng cách theo dõi các heavy hitter, bằng cách theo dõi riêng các giá trị xuất hiện thường xuyên nhất trong histogram equi-width.
But for everything else that isn't a heavy hitter, we have to make the assumption, and it falls apart in some cases. Now, we can also do a range predicate. We'll see this problem again.
Nhưng với mọi giá trị còn lại không phải heavy hitter, chúng ta phải đưa ra giả định đó, và trong một số trường hợp nó không còn đúng. Bây giờ, chúng ta cũng có thể xử lý một vị từ khoảng. Chúng ta sẽ còn gặp lại vấn đề này.
So here I want to say, give me all the people that are age greater than 7, greater than or equal to 7.
Ở đây tôi muốn nói là, hãy cho tôi tất cả những người có tuổi lớn hơn 7, lớn hơn hoặc bằng 7.
Well, I know that I want to include everybody, all the values up above 9 and above, because it's greater than or equal to 7.
Tôi biết rằng mình muốn bao gồm tất cả mọi người, tất cả các giá trị từ 9 trở lên, vì điều kiện là lớn hơn hoặc bằng 7.
So I know that from starting at this bucket range here over there, I want to include all of that in my estimation.
Vậy tôi biết rằng bắt đầu từ khoảng của bucket này trở đi, tôi muốn đưa toàn bộ phần đó vào ước lượng của mình.
So I know that the number of occurrences will be at least 9 plus 12.
Nên tôi biết số lần xuất hiện sẽ ít nhất là 9 cộng 12.
But the challenge is going to be this middle one here, where 7 is in the middle between 6 and 8.
Nhưng thách thức nằm ở bucket ở giữa này, nơi 7 nằm giữa 6 và 8.
So again, if I'm assuming uniform distribution of the possible values, I'm going to say, take the count of 12, divide it by 3, because there's 3 unique values inside this bucket, and I multiply that by 2 because I know it's at least 7 or 8 in this.
Vậy một lần nữa, nếu tôi giả định phân phối đều của các giá trị có thể có, tôi sẽ nói rằng, lấy số đếm 12, chia cho 3, vì có 3 giá trị khác nhau trong bucket này, rồi nhân với 2 vì tôi biết nó là ít nhất 7 hoặc 8 trong đây.
Right? So I get my estimation like this. But again, as I said, not only are we assuming that the values are uniform, we're also assuming the values are continuous.
Đúng không? Vậy là tôi có ước lượng như thế này. Nhưng như tôi đã nói, chúng ta không chỉ giả định các giá trị là đều, mà còn giả định các giá trị là liên tục.
For my small range here, it's not a big deal, but think of really large numbers: you could have gaps, and you may be counting tuples that appear that don't actually exist.
Với khoảng nhỏ ở đây thì không vấn đề gì, nhưng hãy nghĩ đến các số rất lớn: có thể có những khoảng trống, và bạn có thể đang đếm những tuple xuất hiện mà thực ra không tồn tại.
But you don't know, because you're based on approximations. Negation is pretty easy. Right? Not equals, it's just the opposite, the inverse of equals.
Nhưng bạn không biết, vì bạn dựa trên các giá trị xấp xỉ. Phủ định thì khá dễ. Đúng không? Không bằng chỉ là điều ngược lại, là phần nghịch đảo của bằng.
So all we'd have to do is say, for age doesn't equal 2, well, I figure out what is the selectivity of age equals 2, which I would land in this bucket here, do the same formulas that we had before, and then whatever that is, I take 1 minus that, because I know that if it's equal to this, it should be in here.
Vậy chúng ta chỉ cần nói, với age không bằng 2, tôi tính độ chọn lọc của age bằng 2, giá trị đó rơi vào bucket này, dùng các công thức như trước, rồi kết quả là bao nhiêu thì tôi lấy 1 trừ đi nó, vì tôi biết nếu nó bằng giá trị này thì nó nằm trong bucket này.
If it's not equal to that, then it's all these other ones here.
Còn nếu nó không bằng thì nó nằm ở tất cả các bucket còn lại.
So the key observation, and maybe I already slipped up and said this already, is that we are, at the end of the day, the selectivity estimates, they're just probabilities.
Vậy nhận xét then chốt, mà có lẽ tôi đã lỡ nói ra rồi, là rốt cuộc thì các ước lượng độ chọn lọc chỉ là các xác suất.
Right? What's the probability that a tuple will match within whatever data I'm looking at according to my predicate? And based on what my predicate is, I can apply these different formulas.
Đúng không? Xác suất để một tuple khớp trong phần dữ liệu mà tôi đang xét theo vị từ của tôi là bao nhiêu? Và tùy vào vị từ của tôi là gì, tôi có thể áp dụng các công thức khác nhau này.
So, okay, well, this is, if it's a single predicate, like something equals something, something, you know, not equal to something, then that's pretty straightforward.
Vậy, được rồi, nếu là một vị từ đơn, như cái gì đó bằng cái gì đó, hay không bằng cái gì đó, thì khá đơn giản.
But now if I have multiple predicates, then it gets more tricky.
Nhưng nếu có nhiều vị từ thì mọi chuyện trở nên phức tạp hơn.
And now you come back to like stats 101, and you can just make other assumptions to simplify the problem, which get at the cost of accuracy.
Và lúc này bạn quay lại với thống kê cơ bản, và có thể đưa ra thêm các giả định để đơn giản hóa bài toán, đổi lại là phải đánh đổi độ chính xác.
So in this case here, I have two predicates, age equals two, and name like a wild card. And so for each of those separate predicates, I can calculate different selectivities for them.
Trong trường hợp này, tôi có hai vị từ, age bằng 2, và name like với một ký tự đại diện. Và với từng vị từ riêng biệt đó, tôi có thể tính được các độ chọn lọc (selectivity) khác nhau cho chúng.
Right? But now how do I combine them? Right?
Đúng không? Nhưng giờ làm sao kết hợp chúng lại? Đúng không?
If you go back to, like, a simple Venn diagram, you sort of think of, like, this: the first pink circle is the first predicate, and the blue circle is the second predicate.
Nếu quay lại một biểu đồ Venn đơn giản, các bạn có thể hình dung thế này: hình tròn màu hồng đầu tiên là vị từ thứ nhất, và hình tròn màu xanh là vị từ thứ hai.
But what I really want to find is this middle overlapping part here. So how can I do that in statistics?
Nhưng thứ tôi thực sự muốn tìm là phần giao nhau ở giữa này. Vậy làm thế nào để làm điều đó trong thống kê?
If you assume they're independent, the two independent predicates, then you can just multiply them together and produce the output, or get the selectivity that way.
Nếu giả sử chúng độc lập, tức hai vị từ độc lập, thì bạn chỉ cần nhân chúng với nhau để ra kết quả, hay nói cách khác là tính được độ chọn lọc theo cách đó.
So the second big assumption all these cost models are going to make is that your predicates are independent. Right?
Vậy giả định lớn thứ hai mà tất cả các mô hình chi phí này đều đưa ra là các vị từ của bạn độc lập với nhau. Đúng không?
And then assuming it's all conjunction clauses, that you take the first probability, or the first selectivity computed for the first predicate, and you can multiply it by another predicate.
Và nếu giả sử tất cả đều là mệnh đề hội (conjunction), thì bạn lấy xác suất đầu tiên, hay độ chọn lọc đầu tiên tính cho vị từ thứ nhất, rồi nhân nó với vị từ khác.
For, again, for disjunction, it's a bit more complicated, but you basically, you know, the math sort of works out like this. Right?
Còn với phép tuyển (disjunction) thì phức tạp hơn một chút, nhưng về cơ bản phép toán sẽ ra như thế này. Đúng không?
The challenge, of course, is going to be that oftentimes, or in many cases, these aren't independent. Right? And your estimates can get way off.
Tất nhiên, thách thức là thường thì hoặc trong nhiều trường hợp, chúng không độc lập. Đúng không? Và ước lượng của bạn có thể lệch rất xa.
And so there's a bunch of little statistical tricks you can do to try to mitigate this problem, because you're going to end up underestimating what the true cardinality or selectivity is going to be.
Vì vậy có một loạt mẹo thống kê nhỏ mà bạn có thể dùng để giảm bớt vấn đề này, vì bạn sẽ kết thúc bằng việc ước lượng thấp so với lực lượng (cardinality) hay độ chọn lọc thực sự.
We won't talk about this too much, but in the case of SQL Server, what they did, started doing in 2014, in the book they talk about this, is that when I start having a lot of predicates that are all in together in conjunction clauses, I rank them based on their selectivity.
Chúng ta sẽ không nói quá nhiều về điều này, nhưng trong trường hợp của SQL Server, điều họ làm, bắt đầu từ năm 2014, trong sách có nói về chuyện này, là khi tôi có rất nhiều vị từ nằm chung với nhau trong các mệnh đề hội, thì tôi xếp hạng chúng dựa trên độ chọn lọc.
So the ones that are most selective independently are the ones I put in sort of the front of the clause.
Những vị từ có độ chọn lọc riêng cao nhất là những vị từ tôi đặt lên đầu mệnh đề.
But then all subsequent predicates, I'm going to diminish their probability by some weighting factor that exponentially goes down, so that I end up predicting, I end up underpredicting less, because if I multiply them together, then I can get to really small predictions that are way off.
Nhưng với tất cả các vị từ tiếp theo, tôi sẽ giảm xác suất của chúng bằng một hệ số trọng số giảm dần theo hàm mũ, để cuối cùng tôi dự đoán, tôi ít bị ước lượng thấp hơn, bởi vì nếu nhân chúng với nhau, thì tôi có thể ra những dự đoán cực nhỏ và lệch rất xa.
Again, we'll cover that more in the advanced class. Right? So disjunction, again, for ORs, just trying to find this whole thing, and you just assume that they're independent and end up like this.
Một lần nữa, chúng ta sẽ nói kỹ hơn trong lớp nâng cao. Đúng không? Còn phép tuyển, tức là với OR, chỉ là tìm toàn bộ phần này, và bạn chỉ cần giả sử chúng độc lập và kết quả ra như thế này.
All right, so let me show the problem of correlated attributes, and you'll see why the Microsoft trick has sort of worked.
Được rồi, để tôi cho các bạn thấy vấn đề của các thuộc tính tương quan, và các bạn sẽ hiểu vì sao mẹo của Microsoft có hiệu quả.
So this is a really simple example from a famous IBM researcher from a few years ago. Say a simple database that has two tables, makes and models, right, for cars.
Đây là một ví dụ rất đơn giản từ một nhà nghiên cứu nổi tiếng của IBM cách đây vài năm. Giả sử một cơ sở dữ liệu đơn giản có hai bảng, makes và models, đúng không, cho xe hơi.
And then a query shows up where I say, find me all the records where make equals Honda and model equals Accord. Right?
Rồi có một truy vấn xuất hiện, trong đó tôi nói: tìm cho tôi tất cả các bản ghi mà hãng xe bằng Honda và mẫu xe bằng Accord. Đúng không?
So if I apply the two assumptions I've talked about so far, the independence assumption and the uniformity assumption, then if I plug and chug my formulas, I end up with a selectivity like this.
Vậy nếu áp dụng hai giả định mà tôi đã nói đến từ đầu, là giả định độc lập và giả định phân bố đều, rồi cứ thế thay số vào công thức, ta sẽ có một độ chọn lọc như thế này.
So again, I have 10 makes, like Honda, Toyota, and Ford. So if I'm trying to find where make equals one, you know, Honda, one match, so that's going to be one over 10.
Một lần nữa, tôi có 10 hãng xe, như Honda, Toyota và Ford. Nên nếu tôi tìm make bằng, chẳng hạn, Honda, tức là một kết quả khớp, thì sẽ là một phần mười.
So one out of 10 tuples will match. If I'm trying to find Accord, you know, say I have 100 cars and one of them is Accord, then that's going to be one over 100.
Tức là cứ 10 tuple thì có một tuple khớp. Nếu tôi tìm Accord, giả sử tôi có 100 chiếc xe và một trong số đó là Accord, thì sẽ là một phần một trăm.
Now if I assume those two probabilities are independent, I multiply the two together and I get 0.001. But we know that's incorrect as humans because who makes an Accord?
Bây giờ nếu tôi giả định hai xác suất này độc lập, tôi nhân hai số lại với nhau và được 0,001. Nhưng con người chúng ta biết điều đó sai, vì ai sản xuất Accord?
Only Honda, right? So the correct selectivity is really one over 100. Right? We don't need that one over 10 part to multiply that.
Chỉ có Honda, đúng không? Nên độ chọn lọc đúng thực ra là một phần một trăm. Đúng không? Ta không cần nhân thêm phần một phần mười đó.
All right, so you see those small numbers, you know, you say, all right, that's not that far off, who cares? But you're actually an order of magnitude off.
Được rồi, bạn nhìn những con số nhỏ này, và nghĩ: cũng đâu có lệch bao nhiêu, ai quan tâm? Nhưng thực ra bạn đã lệch một bậc độ lớn.
And so again, think of huge tables, right? I went from thinking there's 100 million tuples when it's really a billion tuples. Right? That's huge and that's going to matter.
Và hãy nghĩ đến những bảng khổng lồ nhé. Tôi tưởng có 100 triệu tuple trong khi thực tế là một tỉ tuple. Đúng không? Chênh lệch đó rất lớn và nó sẽ có ảnh hưởng.
So again, this is why the Microsoft trick, what they try to do is They'll say, I'll do the one over 100 first and then I'll still do the one over 10, but I'll put a little weight factor on it so that it's not as pronounced in my final calculation.
Vì vậy, đây là lý do của mẹo của Microsoft, họ sẽ nói: tôi tính một phần một trăm trước rồi vẫn tính một phần mười, nhưng gắn thêm một hệ số trọng số nhỏ để nó không quá nổi bật trong kết quả tính cuối cùng.
So they're never going to be exactly 0.001, but it won't be as bad as being an order of magnitude off. Again, it's a trick that works for them.
Nên chúng sẽ không bao giờ đúng bằng 0,001, nhưng sẽ không tệ như bị lệch một bậc độ lớn. Một lần nữa, đó là mẹo hiệu quả với họ.
I don't think anybody else, anybody else does it. I don't know whether, I don't think there's any statistical guarantees you can extrapolate from it.
Tôi không nghĩ có ai khác làm vậy. Tôi không biết liệu có đảm bảo thống kê nào mà bạn có thể suy rộng từ đó hay không.
All right, the last one I'll talk about is how to do join size estimation. And this is where it can, this is where it all falls apart.
Được rồi, vấn đề cuối cùng tôi sẽ nói là cách ước lượng kích thước của phép join. Và đây là chỗ mọi thứ đổ vỡ.
So the problem I'm trying to solve is I got two relations R and S, and I want to say, what's the range of possible sizes of the number of tuples I expect to come out of doing that join?
Bài toán tôi muốn giải là có hai quan hệ R và S, và tôi muốn biết khoảng kích thước có thể có của số tuple mà tôi kỳ vọng sẽ có sau phép join đó?
Right? So, how many tuples are going to match based on my join predicate?
Đúng không? Vậy có bao nhiêu tuple khớp theo vị từ join của tôi?
So think about all the things I said that are hard to do, just dealing with one table, trying to figure out what, you know, for a predicate on it, how many tuples are going to come out of that?
Hãy nghĩ đến mọi thứ tôi đã nói là khó làm, chỉ với một bảng, là xác định, với một vị từ trên bảng đó, sẽ có bao nhiêu tuple đi ra?
Now I've got to say I've got two tables, and how, what's the likelihood that the values in one table are going to match when I do my join and the values in the other table?
Giờ tôi có hai bảng, và khả năng các giá trị ở bảng này khớp với các giá trị ở bảng kia khi tôi join là bao nhiêu?
And, you know, if it's all primary key lookups, you know, that you can maybe figure it out, would be okay.
Và nếu toàn là tra cứu theo khóa chính thì có lẽ bạn còn tính ra được, vậy cũng ổn.
But if it's like primary key, foreign key, where it's like one tuple in the outer table will match multiple tuples in the inner table, things get really bad, or things get bad, things get really bad when it's like, it's many-to-many or end-to-end.
Nhưng nếu là khóa chính, khóa ngoại, trong đó một tuple ở bảng ngoài khớp với nhiều tuple ở bảng trong, thì mọi thứ trở nên rất tệ, hoặc là tệ, thực sự rất tệ khi nó là quan hệ nhiều-nhiều hay n-n.
Like I have multiple tuples in the outer table matched to multiple tuples in the inner table, You're screwed. It's all over, right?
Tức là tôi có nhiều tuple ở bảng ngoài khớp với nhiều tuple ở bảng trong. Lúc đó coi như hỏng. Hết cứu rồi, đúng không?
So, one of the assumptions that we're going to make this all work is that we'll rely on what's called the containment principle.
Vậy, một trong những giả định để mọi thứ hoạt động được là chúng ta dựa vào cái gọi là nguyên lý bao hàm (containment principle).
And this is just saying that we expect that there will always be a match in the, for the inner table key with the outer table key.
Điều này chỉ có nghĩa là ta kỳ vọng luôn luôn có một kết quả khớp giữa khóa của bảng trong với khóa của bảng ngoài.
If you have to start figuring out that there aren't going to be matches, then it just, estimates get completely screwed up. It's wrong, right?
Nếu bạn phải bắt đầu tính xem có những trường hợp không khớp, thì các ước lượng sẽ bị sai lệch hoàn toàn. Nó sẽ sai, đúng không?
Again, we're just simplifying the problem by sacrificing the accuracy of our estimates in exchange for making it actually more tractable. That we have statistics that can figure this out.
Một lần nữa, ta chỉ đang đơn giản hóa bài toán bằng cách hy sinh độ chính xác của các ước lượng để đổi lấy việc bài toán thực sự dễ xử lý hơn. Và ta có các thống kê để tính được điều này.
So the formula looks like this, right?
Công thức trông như thế này, đúng không?
You basically say, you know, what's the estimated size of the number of tuples I'm going to match from the outer table with the inner table, so R to S, and likewise going the other way, what's the number of tuples I'm going to match from S going into R, right?
Về cơ bản bạn tính kích thước ước lượng, tức số tuple tôi sẽ khớp từ bảng ngoài với bảng trong, tức từ R sang S, và tương tự theo chiều ngược lại, số tuple tôi sẽ khớp từ S sang R là bao nhiêu, đúng không?
So I have basically these two formulas there.
Vậy về cơ bản tôi có hai công thức này.
So the cardinality estimation for the join is going to be the, basically the size of the Cartesian product of the tables and the tuples in R and tuples in S divided by the max selectivity of either of these two choices.
Ước lượng cardinality cho phép join sẽ là về cơ bản kích thước của tích Descartes của các bảng, tức số tuple trong R nhân số tuple trong S, chia cho giá trị lớn nhất của độ chọn lọc trong hai lựa chọn này.
Like, the size of the tuples I'm going to match in R, from R to S, the size of the tuples I'm going to match from S to R.
Tức là, số tuple tôi sẽ khớp trong R, từ R sang S, và số tuple tôi sẽ khớp từ S sang R.
In the back, yes.
Bạn ở phía sau, mời bạn.
Yes, so the statement is, I said that you could have a join that does match M tuples in R to M tuples in S. How does the containment principle handle that? It doesn't.
Vâng, ý bạn là, tôi đã nói rằng có thể có một phép join khớp M tuple trong R với M tuple trong S. Nguyên lý bao hàm xử lý trường hợp đó thế nào? Nó không xử lý được.
So the question is, what do you do if that happens?
Vậy câu hỏi là, bạn làm gì nếu điều đó xảy ra?
The benefit of the containment principle, it allows us to use a simplified formula to estimate the number of tuples I expect to come out of the join. Right?
Lợi ích của nguyên lý bao hàm là nó cho phép ta dùng một công thức đơn giản để ước lượng số tuple dự kiến sẽ ra từ phép join. Đúng không?
Without it, if I have to consider the case, I don't, like, we're not even talking about left outer join, but like, I don't have matches, then like, the formula doesn't work.
Nếu không có nó, mà tôi phải xét cả trường hợp, tức là, ta còn chưa nói đến left outer join, mà chỉ là không có kết quả khớp, thì công thức sẽ không còn đúng.
Again, like, these are all in the textbook. What I'm describing, and this is essentially what Postgres does, there's, again, it's not good, but like, there's nothing else, right?
Một lần nữa, những điều này đều có trong giáo trình. Những gì tôi đang mô tả, và về cơ bản đây là cách Postgres làm, là, một lần nữa, nó không tốt, nhưng không có cách nào khác, đúng không?
Other than, you know, running on samples would solve all this, because you just, you do the join in the sample, right?
Ngoài việc chạy trên mẫu thì sẽ giải quyết được tất cả, vì bạn chỉ cần thực hiện phép join trên mẫu, đúng không?
But if you're based on histograms or even sketches, this is essentially what you have. Right?
Nhưng nếu bạn dựa trên histogram hay thậm chí sketch, thì về cơ bản đây là những gì bạn có. Đúng không?
All right, let's walk through an example, and see, again, I'm not trying to be like, like super depressed or dour about all this, but let me just show you like, why this is super hard, and why everything, why it's, like, why things get really bad.
Được rồi, hãy cùng đi qua một ví dụ, và xem, một lần nữa, tôi không cố tỏ ra là quá chán nản hay ủ dột về chuyện này, nhưng để tôi cho các bạn thấy vì sao việc này cực kỳ khó, và vì sao mọi thứ lại trở nên rất tệ.
We're basically going to show how we're going to get, propagate errors from our bad estimates at the bottom, to our bad estimates in the middle, and then produce bad estimates at the top, just gets multiplicative.
Về cơ bản chúng ta sẽ thấy cách các sai số từ những ước lượng tồi ở dưới cùng lan truyền lên, sang những ước lượng tồi ở giữa, rồi tạo ra những ước lượng tồi ở trên cùng, và sai số cứ nhân lên.
So the very first thing we do, say this is the query plan we want to run, and again, for this one, we don't have to have the physical operators, we can just do this at the logical level, try to predict how many tuples we expect to come out of each different operators.
Đầu tiên, giả sử đây là kế hoạch truy vấn mà ta muốn chạy, và với ví dụ này, ta không cần các toán tử vật lý, ta chỉ cần làm ở mức logic, cố dự đoán xem mỗi toán tử sẽ cho ra khoảng bao nhiêu tuple.
So for A and C, there's no filter on it, but in the case of B, we have this B is greater than 100, which actually I'm missing, I cheated in naming the space, I didn't show a filter operator, but assume that the B greater than, B ID greater than 100 at the bottom.
Với A và C thì không có bộ lọc nào, còn với B thì ta có điều kiện B lớn hơn 100, mà thật ra tôi đang thiếu nó, tôi đã làm tắt khi đặt tên cho vùng trống, không vẽ toán tử lọc, nhưng hãy giả sử có điều kiện B ID lớn hơn 100 ở dưới cùng.
All right, so for each of these, I can compute the selectivity of them, and for B ID greater than 100, assume that I have, again, some histogram that allows me to do that approximation.
Rồi, với mỗi cái này, tôi có thể tính độ chọn lọc (selectivity) của chúng, và với B ID lớn hơn 100, giả sử tôi lại có một histogram nào đó cho phép xấp xỉ như vậy.
And then now I want to go at the next level, the query plan. It's like, all right, what's the cardinality of the join operator, right?
Và giờ tôi muốn lên mức tiếp theo của kế hoạch truy vấn. Câu hỏi là: lực lượng (cardinality) của toán tử join là bao nhiêu?
The first one here. So for this, I use that same formula from the last slide.
Cái đầu tiên ở đây. Với nó, tôi dùng cùng công thức ở slide trước.
I say, okay, I have this number of tuples coming up from A and B, and then what's the selectivity I expect for matching AID to BID, or the selectivity of matching BID greater than 100, and then take the max of that, and that's telling me it's going to be sort of the upper bound of the number of tuples I expect to potentially come out of this, you know, this join operator.
Tôi nói: được, tôi có từng này tuple đến từ A và B, rồi độ chọn lọc tôi kỳ vọng khi ghép A ID với B ID là bao nhiêu, hoặc độ chọn lọc của điều kiện B ID lớn hơn 100, rồi lấy max của chúng, và đó cho tôi biết đại khái cận trên của số tuple mà tôi kỳ vọng có thể xuất ra từ toán tử join này.
And this, again, why we're doing the containment principle is that if I have to consider that I'm not going to have a match, you know, or doing a left-hand join where I produce more tuples than I expect because I don't have a match, then this doesn't work.
Và đây lại là lý do ta dùng nguyên lý containment: nếu tôi phải xét trường hợp không có phần tử khớp, hoặc dùng left join, khi đó tôi tạo ra nhiều tuple hơn dự kiến vì không có phần tử khớp, thì cách này không còn đúng.
But if we simplify it, it does work, reasonably.
Nhưng nếu đơn giản hóa thì nó vẫn khá hiệu quả.
But then say now, then I take, I got to take the output of that first join, and now that's going to be fed as input to the next join, right, on the left-hand side, because I need to know how many tuples I expect to come in, plus now the scan I'm doing on C.
Nhưng giờ tôi phải lấy đầu ra của phép join đầu tiên đó, và nó sẽ được đưa làm đầu vào cho phép join tiếp theo, ở phía bên trái, vì tôi cần biết có khoảng bao nhiêu tuple đi vào, cộng với phép quét trên C.
So now what we see is that we're starting with sort of basic estimations for the least of the query plan, right?
Vậy giờ ta thấy là ta bắt đầu với các ước lượng cơ bản ở tầng thấp nhất của kế hoạch truy vấn, đúng không?
That one we might be okay with, but then when we start doing the join, we're taking the output of that join, feeding that as the input to the next join.
Cái đó có thể ta chấp nhận được, nhưng khi bắt đầu join, ta lấy đầu ra của phép join đó, đưa làm đầu vào cho phép join kế tiếp.
And so if our formulas and our estimates and our histograms are all off for the lower parts, then that just makes this even worse coming up. Right?
Và nếu các công thức, các ước lượng và các histogram của ta đều sai ở các phần phía dưới, thì càng lên cao mọi thứ càng tệ hơn. Đúng không?
And so basically we're, we have bad, bad estimates here, and then bad estimates here.
Và vậy là ở đây chúng ta có những ước lượng rất tồi, và rồi ở đây cũng ước lượng sai.
And, and for three tables, not a big deal, but think of like the 1500 table join at Metro 4, it's, it's all house of cards going, going to the top.
Và với ba bảng thì không phải vấn đề lớn, nhưng hãy nghĩ đến phép join 1500 bảng ở Metro 4, tất cả chỉ như lâu đài trên cát, cứ chồng lên cho đến tận trên cùng.
And the research literature shows that the, all the data systems, because of these different assumptions I'm talking about, they end up underestimating the number of tuples they expect at different operators.
Và các tài liệu nghiên cứu cho thấy rằng tất cả các hệ thống dữ liệu, do những giả định khác nhau mà tôi đang nói đến, đều có xu hướng ước lượng thấp số tuple mà chúng kỳ vọng ở các toán tử khác nhau.
And you add more joins, the underestimations get higher and higher. And so, okay, so what's the problem with that?
Và bạn càng thêm nhiều join thì mức ước lượng thấp càng lớn. Vậy thì, được rồi, điều đó gây ra vấn đề gì?
Well, now I think I, the size of the data I'm coming up to me at some higher point in the tree is low.
Chà, lúc này tôi nghĩ rằng, kích thước dữ liệu đi lên đến tôi ở một điểm cao hơn trong cây là nhỏ.
So therefore I don't want to do a hash join because I'm only expecting 10 tuples. And so I choose a nested loop join because that's really efficient if everything fits in memory.
Vì vậy tôi không muốn dùng hash join vì tôi chỉ kỳ vọng có 10 tuple. Và thế là tôi chọn nested loop join vì nó thực sự hiệu quả nếu mọi thứ vừa trong bộ nhớ.
But then if I'm underestimating, I may be getting, you know, a million tuples and I really wanted a hash join. And now I'm doing the, you know, the slow nested loop join.
Nhưng nếu tôi ước lượng thấp, tôi có thể nhận được, bạn biết đấy, một triệu tuple và lẽ ra tôi thực sự cần một hash join. Và giờ tôi đang chạy nested loop join chậm chạp đó.
The question is why can't you switch on the spot? Advanced class. So his question, so what he's asking is, it's called adaptive join, sorry, adaptive query processing, AQP.
Câu hỏi là tại sao không chuyển đổi ngay tại chỗ? Đây là chủ đề nâng cao. Vậy câu hỏi của bạn ấy là, cái này gọi là adaptive join, xin lỗi, adaptive query processing, AQP.
And basically what that is, you put little hooks in the query plan to say, when I generated, when I, when the optimizer generated this plan, I expect the data to look like this.
Về cơ bản, bạn đặt các hook nhỏ vào kế hoạch truy vấn để nói rằng, khi tôi tạo ra, khi trình tối ưu hóa tạo ra kế hoạch này, tôi kỳ vọng dữ liệu trông như thế này.
I expect to get 10 tuples coming up. And therefore I want to do a nested loop join.
Tôi kỳ vọng nhận được 10 tuple đi lên. Và do đó tôi muốn dùng nested loop join.
If I see, if I see more than 10 or more than some threshold, stop what I'm doing, throw away the work and switch now to a hash join, right?
Nếu tôi thấy nhiều hơn 10 hoặc nhiều hơn một ngưỡng nào đó, hãy dừng việc đang làm, bỏ phần việc đã làm và chuyển ngay sang hash join, đúng không?
So, SQL Server can do something like this.
SQL Server có thể làm điều gì đó như vậy.
Snowflake can do something like this as well, but they, for group eyes and things like that, right? That's hard to do. Only the high end systems do it. And it's very rare.
Snowflake cũng có thể làm điều tương tự, nhưng họ làm cho group by và những thứ như vậy, đúng không? Điều đó khó làm. Chỉ các hệ thống cao cấp mới làm. Và nó rất hiếm.
Another easier way to do this would be, if I, I had these little hooks and say, "Okay, my estimates are just way off."
Một cách dễ hơn để làm là, nếu tôi có các hook nhỏ này và nói: "Được rồi, ước lượng của tôi lệch quá xa."
Rather than trying to be more fine-grained in the adaptation that you're talking about, like change the hash, they change the join algorithm. You say, "Well, this is all crap.
Thay vì cố gắng điều chỉnh chi tiết hơn như kiểu điều chỉnh mà bạn đang nói đến, như thay đổi hash, họ đổi thuật toán join. Bạn nói: "Chà, tất cả cái này vô dụng.
Give up, stop the query, throw away all the results, go back to the optimizer and say, 'Hey, look, you're way off. Here's what I'm really seeing.'"
Bỏ cuộc, dừng truy vấn, bỏ hết mọi kết quả, quay lại trình tối ưu hóa và nói: 'Này, nhìn xem, ông ước lượng lệch quá xa rồi. Đây là những gì tôi thực sự thấy.'"
And then let the optimizer run again and join a new query plan. And the thought process there is like, all right, well, my query plan is so terrible.
Rồi để trình tối ưu hóa chạy lại và đưa ra một kế hoạch truy vấn mới. Và cách nghĩ ở đây là, được rồi, kế hoạch truy vấn của tôi quá tệ.
It's going to take an hour to run this.
Chạy cái này sẽ mất một tiếng.
So it's worth me to go back to the optimizer, spend another, I don't know, a couple, you know, 20 seconds or something, get a better query plan.
Nên quay lại trình tối ưu hóa là đáng, tốn thêm, tôi không biết, khoảng 20 giây gì đó, để có kế hoạch truy vấn tốt hơn.
Cause I may cut down the competition time in half. And of course, you obviously don't want to throw away what you've done.
Vì tôi có thể giảm một nửa thời gian tính toán. Và tất nhiên, rõ ràng bạn không muốn bỏ đi những gì đã làm.
If you're like, "Oh, it's near the end," like, that's hard to do. No, nobody does that one. I don't think it's in. Yeah. So that's called adaptive query optimization.
Nếu bạn thấy kiểu "Ồ, gần xong rồi", thì điều đó khó làm. Không, không ai làm cách đó. Tôi không nghĩ là có. Vâng. Cái đó được gọi là adaptive query optimization.
That's the advanced class on this one. That's basically, you can sort of figure out like the pain tolerance for how off you're allowed to be in your estimates.
Đó là nội dung của lớp nâng cao về vấn đề này. Về cơ bản, bạn có thể xác định được mức chịu đựng cho việc ước lượng của mình được phép sai lệch bao nhiêu.
And you annotate the query plan so that if you see it, you're way off, you basically abort it and go back. But you want to do this at the bottom, not the top.
Và bạn chú thích kế hoạch truy vấn để nếu thấy ước lượng sai quá xa, thì về cơ bản bạn hủy nó và quay lại. Nhưng bạn muốn làm điều này ở phía dưới, không phải ở phía trên.
If you've been running for, the query is going to take an hour. You've been running for 59 minutes. You don't want to give up and go back.
Giả sử truy vấn này sẽ mất một giờ. Bạn đã chạy được 59 phút. Bạn không muốn bỏ cuộc và quay lại.
To that point. Yes. The threshold I'm talking about should be dynamic based on where you are.
Đúng ý đó. Vâng. Ngưỡng mà tôi nói đến nên thay đổi động tùy theo vị trí bạn đang ở.
Like based on the height of you are in the query plan, what the operator is, what the data might look like.
Chẳng hạn dựa trên độ cao của bạn trong kế hoạch truy vấn, toán tử là gì, dữ liệu có thể trông như thế nào.
How many, like how many, the size of the data, at least I expect to see versus what I'm seeing. Right. If it's, you know, you're reading a hundred megabyte table, who cares?
Bao nhiêu, kiểu như bao nhiêu, kích thước dữ liệu, ít nhất là tôi mong đợi thấy so với những gì tôi đang thấy. Đúng không. Nếu bạn đọc một bảng 100 megabyte thì ai quan tâm?
But like, you know, you're in the petabyte range. And yeah, I think that matters. Yes. Wait, sorry, say it again, say it again, sorry.
Nhưng nếu bạn ở mức petabyte thì tôi nghĩ điều đó quan trọng. Vâng. Khoan, xin lỗi, bạn nói lại đi, nói lại giúp tôi.
Yes.
Vâng.
The question is, I mentioned that, I don't, I don't think I have slides here. I mentioned that most data systems underestimate and joins. What happens when you underestimate, when you overestimate?
Câu hỏi là, tôi đã nói rằng, tôi không nghĩ là mình có slide ở đây. Tôi đã nói rằng hầu hết các hệ thống dữ liệu đều ước lượng thấp các phép join. Vậy chuyện gì xảy ra khi ước lượng thấp, hay khi ước lượng cao?
So you may end up choosing a hash join when a nested loop join would have been faster.
Bạn có thể kết thúc bằng việc chọn hash join trong khi nested loop join lẽ ra nhanh hơn.
You may end up allocating your hash table size, if you're doing a hash join, to be larger than it actually needs to be.
Bạn có thể cấp phát kích thước bảng băm nếu đang làm hash join, lớn hơn mức thực sự cần thiết.
Of course, the opposite, if you underestimate the size and you end up getting too big, you got to stop what you're doing, a copy of the hash table.
Dĩ nhiên, ngược lại, nếu bạn ước lượng thấp kích thước và cuối cùng nó quá lớn, bạn phải dừng việc đang làm và sao chép bảng băm.
That's what Postgres has, has that problem. So like you end up maybe allocating more things than you actually need and you still could produce a bad query plan.
Postgres gặp vấn đề đó. Nên có thể bạn cấp phát nhiều hơn mức thực sự cần và vẫn có thể tạo ra một kế hoạch truy vấn tệ.
All right. We have a few minutes left. So actually, let me see if I have the slide here I can share.
Được rồi. Chúng ta còn vài phút. Để tôi xem có slide nào ở đây để chia sẻ không.
Oh, I might. Yes.
Ồ, có thể có. Vâng.
Yes. Perfect. So this is a paper. There's a, there's a newer version of this paper.
Vâng. Tuyệt. Đây là một bài báo. Có một phiên bản mới hơn của bài báo này.
It came out this year because I think it won, it won best or test of time award.
Nó ra mắt năm nay vì tôi nghĩ nó đã giành giải xuất sắc nhất hoặc giải test of time.
So this is from the, the advanced topics class I taught last semester, but then I almost died. I couldn't teach the rest, but it was on query optimization, right?
Đây là từ lớp chủ đề nâng cao mà tôi dạy học kỳ trước, nhưng rồi tôi suýt chết. Tôi không thể dạy phần còn lại, nhưng nó nói về tối ưu hóa truy vấn.
So this is a paper from the Germans from 2015 that basically trying to measure how good the data system, different data systems are for doing cost model estimations.
Đây là bài báo của các tác giả người Đức từ năm 2015, về cơ bản cố gắng đo xem các hệ thống dữ liệu khác nhau làm ước lượng mô hình chi phí tốt đến đâu.
Um, And so for this one, the basic is they use the, it's called the Join Order Benchmark. It's the IMDB database.
Ừm, ở bài này, về cơ bản họ dùng cái gọi là Join Order Benchmark. Đó là cơ sở dữ liệu IMDB.
It's not that big, but they have a bunch of queries that do a ton of joins on them.
Nó không quá lớn, nhưng có hàng loạt truy vấn thực hiện rất nhiều phép join trên đó.
And they try to estimate how good the query model estimations are for the, or the cost model estimations are for the cardinality of the joins.
Và họ thử ước lượng xem các ước lượng của mô hình truy vấn tốt đến đâu, hay các ước lượng của mô hình chi phí, về lực lượng của các phép join.
I mean, every tuple I expect to come out of these joins as you add more joins in your query, right? So, uh, this graph is from the paper, from the Germans.
Ý tôi là, mỗi tuple mà tôi mong đợi sẽ ra từ các phép join này như là khi bạn thêm nhiều phép join hơn vào truy vấn, đúng không? Đồ thị này lấy từ bài báo của nhóm người Đức.
And so there's, each of these runs going to be, there's five different systems here, right? And a way to, I got pulling one quarter kills the camera too.
Và ở đây, mỗi lần chạy sẽ là, có năm hệ thống khác nhau ở đây, đúng không? Và cách để, ôi, kéo một phần tư cũng làm hỏng camera.
Oh, it didn't like me. All right. Uh, all right. So again, there's five different systems here. Along the X axis here is the number of joins they have, right?
Ồ, nó không ưa mình rồi. Được rồi. Ừm, được rồi. Vậy nhắc lại, có năm hệ thống khác nhau ở đây. Dọc theo trục X là số phép join, đúng không?
So the zero means it's a table, a single scan on a table by itself, right? Uh, and then you add more and more joins.
Số 0 nghĩa là một lần quét đơn trên một bảng, đứng riêng một mình, đúng không? Rồi sau đó bạn thêm ngày càng nhiều phép join.
And so what you see here are the error bounds, right? The line going across the middle, that's the exact estimate, or sorry, the exact measurement of cardinality of the join operators.
Và những gì bạn thấy ở đây là các giới hạn sai số, đúng không? Đường chạy ngang ở giữa là giá trị ước lượng chính xác, à xin lỗi, là số đo chính xác của cardinality của các toán tử join.
So if you're above the red bar, then you're overestimating. If you're below it, then you're underestimating. And you can see the error bounds for this, right?
Nên nếu bạn ở trên vạch đỏ thì bạn đang ước lượng quá cao. Nếu ở dưới nó thì bạn đang ước lượng quá thấp. Và bạn có thể thấy các giới hạn sai số cho điều này, đúng không?
And so of course, all of them, what you see is that they're all underestimating as you add more joins, because of all those assumptions that I talked about before, where they're saying, I expect to get fewer tuples out of my join operator than I actually will.
Và dĩ nhiên, tất cả chúng, điều bạn thấy là tất cả đều ước lượng thấp khi bạn thêm nhiều join hơn, vì tất cả những giả định mà tôi đã nói trước đó, khi chúng cho rằng, tôi kỳ vọng nhận được ít tuple hơn từ toán tử join so với thực tế.
And then now you're taking that underestimation, feeding that into another join operator, that then underestimates even further, right? And the problem gets compounded for this, right? What's that?
Và rồi bạn lấy kết quả ước lượng thấp đó, đưa vào một toán tử join khác, toán tử đó lại ước lượng thấp thêm nữa, đúng không? Và vấn đề cứ chồng chất lên, đúng không? Gì vậy?
Uh, this, this one here? Yeah, like, the question is which one this is, but this one's overestimating. Actually, I, I've seen the slides, I know when it's coming up.
Ừm, cái này à? Ừ, câu hỏi là cái này là hệ nào, nhưng cái này đang ước lượng quá cao. Thật ra tôi đã xem các slide rồi, tôi biết khi nào nó xuất hiện.
Um, and then there's this one here that's like way, way off. So, let's play a game. Who, let's take a guess what the systems are.
Và rồi có cái này ở đây lệch rất, rất xa. Vậy chúng ta chơi một trò nhé. Ai, hãy đoán xem các hệ thống đó là gì.
All right, I'll tell you, the choices are, uh, Postgres, SQL Server, uh, the German system, the first German system, and Oracle.
Được rồi, tôi sẽ nói các lựa chọn là Postgres, SQL Server, hệ thống của người Đức, hệ thống Đức đầu tiên, và Oracle.
Uh, what did I say? SQL Server, Oracle, Postgres, uh, the German system, and maybe MySQL might be one of them as well.
Ừm, tôi vừa nói gì nhỉ? SQL Server, Oracle, Postgres, hệ thống của người Đức, và có thể MySQL cũng là một trong số đó.
All right. So, this one clearly is the, is the worst. What do we think this is?
Được rồi. Cái này rõ ràng là tệ nhất. Các bạn nghĩ nó là gì?
Wait, I hear, raise your hand and say Postgres, raise your hand and say Oracle, MySQL, the Germans, SQL Server.
Khoan, giơ tay và nói Postgres, giơ tay và nói Oracle, MySQL, người Đức, SQL Server.
Okay. The first one is Postgres, the last one is Hyper, ah, DB2 was the other one. The worst one here is Oracle. All right.
Được. Cái đầu tiên là Postgres, cái cuối là Hyper, à, DB2 là cái còn lại. Cái tệ nhất ở đây là Oracle. Được rồi.
You know, I made a big deal about how bad Postgres is compared to Oracle one. Like, I mean, this was over 10 years ago, so I, I think they fixed it since then.
Tôi từng nhấn mạnh Postgres tệ thế nào so với Oracle. Nhưng đây là chuyện hơn 10 năm trước, nên tôi nghĩ họ đã sửa kể từ đó.
Uh, but, in this case here, SQL Server is the only one doing sampling. Right? And that's why their estimates are, are better than the, than the other ones.
Nhưng trong trường hợp này, SQL Server là hệ duy nhất dùng lấy mẫu. Đúng không? Và đó là lý do ước lượng của họ tốt hơn các hệ khác.
All right. At least, that attributes to that. Um, in the case of the Germans, after this paper came out, I think in their new system, they then added sampling.
Ít nhất là có thể quy cho điều đó. Còn với người Đức, sau khi bài báo này ra đời, tôi nghĩ trong hệ thống mới của họ, họ đã thêm lấy mẫu.
And it helps a little bit, but it's not that great. But again, like, you know, DB2 and Oracle, these are systems that people have been working on for decades.
Và nó có cải thiện một chút, nhưng không tốt lắm. Nhưng một lần nữa, DB2 và Oracle, đây là những hệ thống mà người ta đã làm việc suốt nhiều thập kỷ.
And spent, you know, millions of dollars of people, you know, time trying to optimize these things. And they still get a way off. This is 2015.
Và đã bỏ ra hàng triệu đô la cho nhân lực, thời gian cố gắng tối ưu những thứ này. Vậy mà họ vẫn sai lệch rất xa. Đây là năm 2015.
There's a newer one that came out, I think this year. And I, I think the Germans win again. Um, okay.
Có một bài mới hơn ra mắt, tôi nghĩ là trong năm nay. Và tôi nghĩ người Đức lại thắng nữa. Ừm, được rồi.
I, you actually don't know, because it's closed source. You don't know. They might have fixed it. Hmm?
Thực ra bạn không biết được, vì nó là mã nguồn đóng. Bạn không biết. Có thể họ đã sửa rồi. Hmm?
I mean, the question is, like, what are they, what are they tested against? Uh, I mean, they, the Germans designed this benchmark for just this paper.
Ý tôi là, câu hỏi là họ được kiểm thử dựa trên cái gì? Ừm, những người Đức đã thiết kế benchmark này chỉ riêng cho bài báo này.
So it's not like, they may have gone back now since then, and improved it further. Right?
Nên không phải là, có thể từ đó đến giờ họ đã quay lại và cải tiến nó thêm. Đúng không?
No, there's, well, there's a new German system and a new German paper, um, that follows up on it. Okay. So, this is just repeating what I've already said.
Không, à, có một hệ thống mới của người Đức và một bài báo mới của người Đức, ừm, tiếp nối bài đó. Được rồi. Vậy là, đây chỉ là lặp lại những gì tôi đã nói.
So, right, yeah, so, just to finish up.
Vậy, đúng rồi, để kết thúc phần này.
The, hopefully the main takeaway of this is that, again, we're making a bunch of assumptions of what the data looks like, and what the formulas are, just to make this thing actually work.
Hy vọng điều rút ra chính từ phần này là một lần nữa, chúng ta đưa ra hàng loạt giả định về dữ liệu trông như thế nào, và các công thức ra sao, chỉ để làm cho thứ này thực sự chạy được.
But, in practice, again, for real data, especially data with a lot of churn, a lot of, when it's changing all the time, it, um, it can get real bad real quickly.
Nhưng trong thực tế, với dữ liệu thật, đặc biệt là dữ liệu có nhiều biến động, rất nhiều, khi nó thay đổi liên tục, ừm, nó có thể trở nên rất tệ rất nhanh.
Right?
Đúng không?
And at the end of the day, what the cost model is trying to do is estimate the number of tuples we expect an operator to spit out, and we use that to then calculate how much work I'll have to do, or how much IO I'll have to do, reading the data or writing the data.
Và cuối cùng thì, mô hình chi phí đang cố làm là ước lượng số tuple mà chúng ta kỳ vọng một toán tử sẽ trả ra, rồi dùng nó để tính xem tôi sẽ phải làm bao nhiêu việc, hoặc bao nhiêu IO tôi sẽ phải thực hiện khi đọc hoặc ghi dữ liệu.
As I said, this is all problematic. There's a lot of problems.
Như tôi đã nói, tất cả những điều này đều có vấn đề. Có rất nhiều vấn đề.
I was trying to teach, as I said, a, a, a, a, a, a, a, a, a, a, a, a, a, a,
Như tôi đã nói, tôi đang cố dạy, một, một, một, một, một, một, một, một, một, một, một, một, một, một,
a, a, a, a, a, a, a, a, a, a, a, a, a, when we start doing parallel things, that maybe what you're used to, like, to not memory barriers in the same way in like a system class, now it's gonna have different notions of correctness, and that don't seem to, you know, that all aren't always gonna be intuitive right away.
một, một, một, một, một, một, một, một, một, một, một, một, một, khi chúng ta bắt đầu làm các việc song song, thì có thể điều bạn quen thuộc, chẳng hạn, không phải các rào cản bộ nhớ theo cách tương tự như trong một lớp về hệ thống, giờ nó sẽ có những khái niệm khác về tính đúng đắn, và những thứ đó dường như không, bạn biết đấy, lúc nào cũng sẽ không trực quan ngay lập tức.
Okay, all right, hit it.
Được rồi, nào, bắt đầu thôi.
Oh
Ồ
Đă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.