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ả.
I'd like to cover today, again, a round of applause for Gigi Kast. I should've asked you before, how's your money situation? It's getting better.
Hôm nay tôi muốn nói về, một lần nữa, xin một tràng pháo tay dành cho Gigi Kast. Lẽ ra tôi nên hỏi em trước, tình hình tiền bạc của em thế nào? Đang khá hơn rồi ạ.
Getting better? Okay. I mean, again, we pay you here. I know your radio show doesn't pay you, but you still do gigs for private party stuff.
Khá hơn à? Được rồi. Ý tôi là, ở đây chúng tôi vẫn trả lương cho em mà. Tôi biết chương trình radio của em không trả tiền, nhưng em vẫn đi diễn ở các buổi tiệc riêng.
You're in there. So, why do you want money so bad? Yeah, so, I had some crypto scheme going on.
Em cũng làm việc đó. Vậy sao em lại cần tiền đến thế? Dạ, em có đầu tư vào một kế hoạch tiền mã hóa.
Yeah? You lose all your money on that? Just recouping. All right. Blockchain and crypto is a scam. Blockchain is a terrible implementation of our database.
Vậy à? Mất hết tiền vào đó rồi hả? Em chỉ đang gỡ lại thôi ạ. Được rồi. Blockchain và tiền mã hóa là trò lừa đảo. Blockchain là một bản cài đặt tồi tệ của cơ sở dữ liệu.
We'll see that after the fall break when we talk about transactions.
Chúng ta sẽ thấy điều đó sau kỳ nghỉ thu khi nói về giao dịch.
That's his problem. Whatever. All right. You guys in the class. Again, next class, this room, same time, we're having the midterm exam. Again, the study guide is online. The material is online on Piazza.
Đó là vấn đề của cậu ấy. Kệ đi. Được rồi. Các bạn trong lớp. Buổi sau, tại phòng này, cùng giờ này, chúng ta sẽ có bài thi giữa kỳ. Hướng dẫn ôn tập đã có trực tuyến. Tài liệu có trên Piazza.
Everything, all the notes are posted. Homework 3 solutions went out this morning, so you can check that as well. You need to bring your CMU ID.
Tất cả ghi chú đều đã được đăng. Lời giải Bài tập về nhà 3 đã được đăng sáng nay, nên các bạn cũng có thể xem. Các bạn cần mang theo thẻ CMU ID.
If you want to do logarithms, you can't do it in your head, bring a simple calculator. Your phone is fine. And then a single page, double-sided, handwritten notes.
Nếu cần tính logarit mà không nhẩm được, hãy mang theo một máy tính đơn giản. Điện thoại cũng được. Và một tờ giấy, hai mặt, ghi chú viết tay.
And the idea here is, again, forcing you to look through the material and write down what you think is important, rather than just trying to take every single slide and make it a microfiche and try to shrink it down as small as possible.
Ý tưởng ở đây là buộc các bạn xem lại tài liệu và viết ra những gì các bạn thấy quan trọng, chứ không phải cứ lấy từng slide một rồi thu nhỏ thành vi phim, ép càng nhỏ càng tốt.
Yes, in the back. Yeah, if you use a basic calculator on your phone, that's fine, yes. Because most people don't have a regular calculator these days.
Vâng, bạn ở phía sau. Vâng, nếu dùng máy tính cơ bản trên điện thoại thì được. Vì ngày nay hầu hết mọi người không có máy tính bỏ túi thông thường.
And then because my office hours are after class on Wednesday, plus I got to go travel, I've moved my office hours to be tomorrow in the afternoon at 4:15.
Còn giờ tiếp sinh viên của tôi là sau buổi học thứ Tư, mà tôi lại phải đi công tác, nên tôi đã dời giờ tiếp sinh viên sang chiều mai lúc 4:15.
I'll post those on Piazza as well. So if you want to talk to me, you can talk to me before the midterm. Any questions about the midterm?
Tôi cũng sẽ đăng thông tin đó trên Piazza. Vì vậy nếu muốn trao đổi với tôi, các bạn có thể gặp trước kỳ thi giữa kỳ. Có câu hỏi nào về bài thi giữa kỳ không?
Again, it's chapters, or the lecture is 1 to 11 inclusive, so today's lecture and joins is obviously not going to be on the exam. All right, and then Project 2 is out.
Phạm vi là các chương, hay các bài giảng từ 1 đến 11 tính cả hai đầu, nên bài giảng hôm nay về phép nối (join) hiển nhiên sẽ không có trong đề thi. Được rồi, và Dự án 2 đã được phát hành.
The recitation for that will be also Wednesday after the midterm, because I assume no one is going to look at it until after midterm.
Buổi thảo luận cho dự án đó cũng sẽ diễn ra vào thứ Tư sau kỳ thi giữa kỳ, vì tôi đoán sẽ không ai xem nó cho đến khi thi giữa kỳ xong.
So that will be 8 o'clock this Wednesday on Zoom, and then we'll post the materials afterwards on Piazza. Yes.
Buổi đó sẽ diễn ra lúc 8 giờ thứ Tư này trên Zoom, và sau đó chúng tôi sẽ đăng tài liệu trên Piazza. Vâng.
The question is, is the real exam going to be like the practice exam where the questions are all what, sorry? Yes, roughly multiple choice questions.
Câu hỏi là liệu đề thi thật có giống đề thi thử, với các câu hỏi toàn là gì, xin lỗi? Vâng, đại khái là các câu hỏi trắc nghiệm.
Some of them will be, if the multiple choice question isn't there, you can then fill in something else. It'll look like that. Okay?
Một số câu sẽ như vậy, nếu không có câu hỏi trắc nghiệm ở đó, thì các bạn có thể điền nội dung khác. Nó sẽ trông như vậy. Được chứ?
All right, again, if you can't get enough databases, if you're addicted like I am, we have much more database talks coming up. Today's talk will be at 4:30 p.m. on Zoom.
Được rồi, nếu các bạn vẫn chưa thấy đủ về cơ sở dữ liệu, nếu các bạn cũng nghiện như tôi, chúng ta còn nhiều buổi nói chuyện về cơ sở dữ liệu nữa sắp tới. Buổi nói chuyện hôm nay sẽ diễn ra lúc 4:30 chiều trên Zoom.
That'll be from the co-founder of MotherDuck. Guy also was an engineering director at SingleStore, and prior to that he was also engineering director or lead developer at Google working on BigQuery.
Diễn giả là đồng sáng lập của MotherDuck. Anh ấy cũng từng là giám đốc kỹ thuật tại SingleStore, và trước đó anh ấy cũng là giám đốc kỹ thuật hoặc trưởng nhóm phát triển tại Google, làm việc về BigQuery.
And sort of the story of MotherDuck and DuckDB is, from this guy's perspective, which I agree with in some ways, that instead of building this massively distributed database system, if you make the single node be as efficient as possible, then that can take you pretty far.
Câu chuyện của MotherDuck và DuckDB phần nào là, theo quan điểm của anh này, mà tôi cũng đồng ý ở một số khía cạnh, thay vì xây dựng một hệ cơ sở dữ liệu phân tán quy mô khổng lồ, nếu bạn làm cho một nút đơn hiệu quả nhất có thể, thì điều đó có thể đưa bạn đi khá xa.
So MotherDuck is sort of pushing that story. Then next week we'll have the SpiralDB guys give a talk about Vortex. Vortex is a replacement for Parquet.
Vậy nên MotherDuck đang thúc đẩy câu chuyện đó. Tuần sau, nhóm SpiralDB sẽ có buổi nói chuyện về Vortex. Vortex là giải pháp thay thế cho Parquet.
And then after that will be the guys from Columnar.
Và sau đó sẽ là nhóm từ Columnar.
These are people that used to work on or do work on Apache Arrow, which is something we'll talk about when we talk about distributed systems. But basically it's an in-memory representation of data.
Đây là những người từng làm hoặc đang làm về Apache Arrow, mà chúng ta sẽ nói đến khi bàn về các hệ thống phân tán. Nhưng về cơ bản nó là một biểu diễn dữ liệu trong bộ nhớ.
Sort of like Parquet is for files on disk. Arrow is for in-memory stuff, so you want to pass data between different systems. They speak Arrow. They're compatible.
Giống như Parquet dành cho các tệp trên đĩa. Arrow dành cho dữ liệu trong bộ nhớ, để bạn truyền dữ liệu giữa các hệ thống khác nhau. Chúng nói được Arrow. Chúng tương thích với nhau.
So Columnar is a commercial sort of expansion of the project. All right. So today's lecture is going to be awesome because it's about joins.
Columnar là phần mở rộng mang tính thương mại của dự án. Được rồi. Bài giảng hôm nay sẽ rất tuyệt vì nói về phép nối (join).
And this is going to be for single node systems like DuckDB. This is where most of the time is going to be spent running your queries.
Và phần này dành cho các hệ thống đơn nút như DuckDB. Đây là nơi phần lớn thời gian chạy truy vấn của bạn bị tiêu tốn.
When you go to distributed, it's going to be the shuffle operator, which we'll cover later.
Khi chuyển sang phân tán, đó sẽ là toán tử shuffle, mà chúng ta sẽ học sau.
But on single node systems, joins is the most expensive thing, so we want to see what we can do to speed that up. So last class, we talked about how to handle sorting.
Nhưng trên các hệ thống đơn nút, join là thứ tốn kém nhất, nên chúng ta muốn xem có thể làm gì để tăng tốc nó. Buổi trước, chúng ta đã nói về cách xử lý sắp xếp.
And again, we made this emphasis on that if the database doesn't fit in memory, the data you want to sort doesn't fit in memory, then you would use a technique like external merge sort to allow you to write sequential files out to disk, read sequential files back in, and still perform the sort operation.
Và chúng ta đã nhấn mạnh rằng nếu cơ sở dữ liệu không vừa trong bộ nhớ, dữ liệu bạn muốn sắp xếp không vừa trong bộ nhớ, thì bạn sẽ dùng kỹ thuật như external merge sort để ghi các tệp tuần tự ra đĩa, đọc các tệp tuần tự trở lại, và vẫn thực hiện được phép sắp xếp.
And the high-level design pattern that we took advantage of in sorting, and we'll take advantage of today again in joins, is this divide-and-conquer approach.
Và mẫu thiết kế ở mức cao mà chúng ta tận dụng trong sắp xếp, và hôm nay sẽ lại tận dụng trong join, là cách tiếp cận chia để trị.
By taking a large problem, breaking it up into smaller subproblems, solving those each individually as efficiently as possible, and then putting the result back together. All right.
Lấy một bài toán lớn, chia nó thành các bài toán con nhỏ hơn, giải từng bài một cách hiệu quả nhất có thể, rồi ghép các kết quả lại với nhau. Được rồi.
And the two strategies we're going to use are both sorting and hashing, and aggregations that we saw at the end of the last class as well, is either sorting or hashing.
Hai chiến lược chúng ta sẽ dùng là sắp xếp và băm, và với các phép tổng hợp mà chúng ta thấy ở cuối buổi trước cũng vậy, hoặc là sắp xếp hoặc là băm.
The nested loop join would be the dumbest thing you could do, because it's just for loops, but with sorting and hashing, again, these are a bit more sophisticated, and under the right conditions, can do much better than a bunch of nested for loops.
Nested loop join sẽ là cách ngốc nghếch nhất bạn có thể làm, vì nó chỉ là các vòng lặp for, còn sắp xếp và băm thì phức tạp hơn một chút, và trong những điều kiện phù hợp, có thể tốt hơn nhiều so với một loạt vòng lặp for lồng nhau.
All right. So it sort of goes without saying, because you did homework one, About why we would need a join.
Được rồi. Thực ra không cần nói cũng biết, vì các em đã làm bài tập về nhà số 1, tại sao chúng ta cần phép join.
This will be the one slide, but I pretty much only mention normal forms this entire class, this entire semester.
Đây sẽ là một slide duy nhất, vì gần như tôi chỉ nhắc đến các dạng chuẩn (normal form) đúng một lần trong cả lớp này, trong cả học kỳ này.
We used to teach it in the older versions of this course, the normal forms and Armstrong's axioms and all this stuff, but in the real world, nobody uses them.
Trước đây chúng tôi từng dạy nó trong các phiên bản cũ của môn học này, các dạng chuẩn, các tiên đề Armstrong và đủ thứ như vậy, nhưng trong thực tế, không ai dùng chúng cả.
And if you just use, like, if you write something in Ruby on Rails or Django, or pick your favorite object-relational map, or ORM, you basically end up on third normal form, and that's good enough.
Và nếu em viết một thứ gì đó bằng Ruby on Rails hoặc Django, hoặc chọn bất kỳ ánh xạ đối tượng-quan hệ (ORM) nào em thích, thì về cơ bản em sẽ đạt dạng chuẩn thứ ba, và thế là đủ tốt rồi.
So I just want to mention that these normal form things exist. You don't need to worry about them.
Nên tôi chỉ muốn nói rằng các dạng chuẩn này có tồn tại. Các em không cần lo về chúng.
And then if you only end up building a query optimizer or do other more sophisticated things, you may have to care about them. In the real world, you don't need to know them.
Còn nếu sau này em chỉ đi xây dựng một bộ tối ưu hóa truy vấn hoặc làm những việc phức tạp hơn, thì có thể em sẽ phải quan tâm đến chúng. Trong thực tế, các em không cần biết chúng.
It's basically saying that it's a way to break up your tables into smaller tables, or combine them, based on some properties that you may care about.
Về cơ bản, đó là cách tách các bảng thành những bảng nhỏ hơn, hoặc gộp chúng lại, dựa trên một số tính chất mà em có thể quan tâm.
So first normal form would be, like, if I take my database of all my students enrolled in classes and their grades, I could put that in one giant table with all the columns put together.
Vậy dạng chuẩn thứ nhất sẽ là, chẳng hạn, nếu tôi có cơ sở dữ liệu về tất cả sinh viên đã đăng ký các lớp và điểm của họ, tôi có thể đặt tất cả vào một bảng khổng lồ với mọi cột gộp lại.
That's called first normal form, and obviously that's going to be very inefficient because it's duplicating a lot of data.
Đó gọi là dạng chuẩn thứ nhất, và hiển nhiên cách này sẽ rất kém hiệu quả vì nó lặp lại rất nhiều dữ liệu.
So you start breaking them out to, like, the students table, the enrolled table, and the course table, right?
Vì vậy em bắt đầu tách ra thành bảng sinh viên, bảng đăng ký, và bảng môn học, đúng không?
That ends up being in a higher normal form, and it's a natural way to represent data.
Như vậy sẽ thuộc một dạng chuẩn cao hơn, và đó là cách biểu diễn dữ liệu tự nhiên.
So the reason why we need to do join is that if you start breaking your tables up from the first normal form, with this one giant universal table, into these separate tables, then I want to put them back together to get back the original data.
Vậy lý do chúng ta cần join là nếu em tách các bảng ra từ dạng chuẩn thứ nhất, với một bảng vạn năng khổng lồ, thành các bảng riêng biệt này, thì tôi muốn ghép chúng lại với nhau để lấy lại dữ liệu ban đầu.
That's what the joins are going to do for us.
Đó là việc mà các phép join sẽ làm cho chúng ta.
And so we want to have a join operator in our system that can reconstruct us back to the original data that we want without losing anything.
Và vì thế chúng ta muốn có một toán tử join trong hệ thống có thể tái tạo lại cho chúng ta dữ liệu ban đầu mà chúng ta muốn, không để mất gì.
Seems sort of obvious, but that's what we care about.
Nghe có vẻ hiển nhiên, nhưng đó là điều chúng ta quan tâm.
So the join operators we're going to focus on in this class today, in this semester, are going to be doing what are called equi joins or inner joins, and we're going to do this on doing binary operators, meaning taking two tables and joining them together.
Các toán tử join mà chúng ta sẽ tập trung vào trong lớp hôm nay, trong học kỳ này, sẽ là cái gọi là equi join hay inner join, và chúng ta sẽ thực hiện với các toán tử hai ngôi, nghĩa là lấy hai bảng và join chúng lại với nhau.
This is going to be the most common join operator that will be executed or used in a database system, like taking two tables, just joining them together based on something equals something.
Đây sẽ là toán tử join phổ biến nhất được thực thi hoặc sử dụng trong một hệ quản trị cơ sở dữ liệu, tức là lấy hai bảng, rồi join chúng lại dựa trên điều kiện cái này bằng cái kia.
Something in the first table equals something in the second table. That's the most common thing, and that's what we want to focus on, right?
Một thứ trong bảng thứ nhất bằng một thứ trong bảng thứ hai. Đó là trường hợp phổ biến nhất, và đó là điều chúng ta muốn tập trung vào, đúng không?
And then we can tweak these with the basic algorithms we'll talk about today to handle other things like left outer joins or full outer joins or doing like anti joins, or I want to see something doesn't equal something.
Và sau đó chúng ta có thể điều chỉnh chúng với các thuật toán cơ bản mà hôm nay chúng ta sẽ nói đến để xử lý các trường hợp khác như left outer join hay full outer join hoặc thực hiện anti join, hay khi tôi muốn tìm cái gì đó không bằng cái gì đó.
Something is not in the table. Join those together. So all the algorithms we'll talk about today can be used for handling these other types of joins.
Cái gì đó không nằm trong bảng. Rồi join chúng lại với nhau. Vì vậy, tất cả các thuật toán chúng ta sẽ nói hôm nay đều có thể được dùng để xử lý các kiểu join khác này.
They're called like theta joins, but again, we don't have to worry about that. There are algorithms that do what are called multi-way joins.
Chúng được gọi là theta join, nhưng một lần nữa, chúng ta không cần bận tâm về điều đó. Có những thuật toán thực hiện cái gọi là multi-way join.
So if I have more than two tables in my query that I want to join together, there are some algorithms that can try to join them all at once, but typically this is very hard to do.
Nên nếu truy vấn của tôi có nhiều hơn hai bảng cần join với nhau, có một số thuật toán có thể cố gắng join tất cả chúng cùng một lúc, nhưng thường thì việc này rất khó làm.
Microsoft had this in SQL Server in 1998, but then they took it out three years later in 2001 because the performance was not that great.
Microsoft đã có tính năng này trong SQL Server năm 1998, nhưng rồi họ gỡ nó ra ba năm sau, vào năm 2001, vì hiệu năng không tốt lắm.
Sometimes it'd be really fast, and sometimes it'd be actually worse than doing a simple binary join. So most data systems you know about, Postgres, Oracle, MySQL, pick your favorite.
Có lúc nó rất nhanh, và có lúc nó thực sự còn tệ hơn so với một binary join đơn giản. Vì vậy hầu hết các hệ thống dữ liệu mà các bạn biết, Postgres, Oracle, MySQL, cứ chọn cái nào các bạn thích.
They're going to be doing binary joins, taking two tables and joining them together. There's another class of algorithms that are modern variants of these multi-way joins called worst-case optimal joins.
Chúng sẽ dùng binary join, tức là lấy hai bảng rồi join chúng lại với nhau. Có một lớp thuật toán khác là biến thể hiện đại của các multi-way join này, gọi là worst-case optimal join.
We're not going to cover that this semester.
Chúng ta sẽ không đề cập đến nó trong học kỳ này.
You don't need to know that for this class, but these are algorithms that can do, like, three-way joins very efficiently, and this is useful when you're doing graph traversals in a relational database, because when you join two tables, the size of the output of the joins will be much, much larger than the original inputs, and then you do another join to reduce it down further.
Các bạn không cần biết điều đó cho môn này, nhưng đây là những thuật toán có thể thực hiện, chẳng hạn, join ba bảng rất hiệu quả, và nó hữu ích khi bạn duyệt đồ thị trong một cơ sở dữ liệu quan hệ, bởi vì khi bạn join hai bảng, kích thước đầu ra của phép join sẽ lớn hơn rất, rất nhiều so với các đầu vào ban đầu, rồi bạn làm một phép join khác để thu nhỏ nó lại tiếp.
Think of it like doing a bunch of self-joins. We'll cover worst-case optimal joins in the advanced class. Most systems don't actually support this.
Hãy hình dung như thực hiện một loạt self-join. Chúng ta sẽ học worst-case optimal join trong lớp nâng cao. Hầu hết các hệ thống thực ra không hỗ trợ điều này.
The Relational AI guys that came a few weeks ago, they're one of the systems that support this.
Những người của Relational AI đến cách đây vài tuần là một trong những hệ thống hỗ trợ điều này.
The Germans support this, but pretty much all the commercial systems don't do this, so we don't need to worry about that.
Nhóm người Đức cũng hỗ trợ, nhưng gần như tất cả các hệ thống thương mại đều không làm vậy, nên chúng ta không cần lo về điều đó.
All right, so in general, the rule of thumb we're going to have in all our join algorithms that we talk about today is that we're going to have two tables, right?
Được rồi, nói chung, quy tắc kinh nghiệm cho tất cả các thuật toán join mà chúng ta nói hôm nay là chúng ta sẽ có hai bảng, đúng không?
We'll have the left table and the right table, the inner table and the outer table, and we're always going to want the smaller table of the two tables we want to join, we're going to want to put that as part of the outer table in our query plan, and we're not going to talk about query optimization just yet.
Chúng ta sẽ có bảng bên trái và bảng bên phải, bảng trong và bảng ngoài, và chúng ta luôn muốn lấy bảng nhỏ hơn trong hai bảng cần join, chúng ta muốn đặt nó làm bảng ngoài trong kế hoạch truy vấn của mình, và hiện giờ chúng ta chưa nói về tối ưu hóa truy vấn.
We'll talk about this after the fall break, but it's going to be the database system's query optimizer to figure out which of the two tables are smaller and make sure we put these things in the right order.
Chúng ta sẽ nói về nó sau kỳ nghỉ mùa thu, nhưng chính bộ tối ưu hóa truy vấn của hệ quản trị cơ sở dữ liệu sẽ xác định bảng nào trong hai bảng nhỏ hơn và đảm bảo đặt chúng theo đúng thứ tự.
And again, these algorithms today, again, are binary join algorithms. They're taking two tables and throwing them together.
Và một lần nữa, các thuật toán hôm nay đều là thuật toán binary join. Chúng lấy hai bảng rồi ghép chúng lại với nhau.
If I have more than two tables I want to join in my query plan or my query, then the optimizer also can try to figure out what the order I want to do the join.
Nếu tôi có nhiều hơn hai bảng muốn join trong kế hoạch truy vấn hay trong truy vấn của mình, thì bộ tối ưu hóa cũng có thể cố gắng xác định thứ tự mà tôi nên thực hiện các phép join.
So I join A and B first, followed by C, or B and C first, followed by A, And the way it's going to try to figure this out is based on some statistics that it's going to collect about the database system, about these tables, to try to make educated guesses on the right way to execute things.
Tức là join A và B trước, rồi mới đến C, hoặc join B và C trước, rồi mới đến A. Và cách nó xác định điều này là dựa trên một số thống kê mà nó thu thập về hệ quản trị cơ sở dữ liệu, về các bảng này, để đưa ra những phỏng đoán có cơ sở về cách thực thi đúng đắn.
But again, for this class today, we don't need to worry about it. We're really focused on what's the algorithm we're going to use to join the tables together.
Nhưng một lần nữa, với buổi học hôm nay, chúng ta không cần lo về điều đó. Chúng ta thực sự tập trung vào việc thuật toán nào sẽ được dùng để join các bảng với nhau.
All right, so we saw this query plan last time, right?
Được rồi, vậy là lần trước chúng ta đã thấy kế hoạch truy vấn này, đúng không?
And we said that the representation of a query plan is basically going to be either a tree or a DAG, and a tree is a subset of a DAG.
Và chúng ta đã nói rằng cách biểu diễn một kế hoạch truy vấn về cơ bản sẽ là một cây hoặc một DAG, và cây là một tập con của DAG.
But the idea is that we have data at the bottom from our source data for the tables or files, whatever it is, and we're going to be feeding that up into the query plan for other operators to do whatever it is, the computation they want to do, and then produce a final output that's in the root that we then send out to whoever's requested it, either a client or writing to another table, whatever you want, right?
Nhưng ý tưởng là ở dưới cùng chúng ta có dữ liệu từ nguồn, dữ liệu của các bảng hoặc các tệp, bất kể là gì, và chúng ta sẽ đưa nó lên trong kế hoạch truy vấn cho các toán tử khác thực hiện bất kỳ phép tính nào chúng cần, rồi tạo ra kết quả cuối cùng ở gốc, mà sau đó chúng ta gửi đến bất kỳ ai đã yêu cầu nó, có thể là một client hoặc ghi vào một bảng khác, tùy bạn muốn, đúng không?
And so we'll discuss, after the fall break, we'll discuss what this data is going to look like. Is it going to be a single tuple, a batch of tuples, and so forth?
Và chúng ta sẽ thảo luận, sau kỳ nghỉ thu, xem dữ liệu này sẽ trông như thế nào. Nó sẽ là một tuple đơn lẻ, một lô tuple, v.v.?
And again, we'll worry about that later.
Và một lần nữa, chúng ta sẽ lo chuyện đó sau.
But for today's discussion, we need to talk about what the output of this join operator is going to look like, and then how we're going to determine whether one algorithm is going to be better than another.
Nhưng với phần thảo luận hôm nay, chúng ta cần nói về đầu ra của toán tử join này sẽ trông như thế nào, và sau đó là cách chúng ta xác định xem một thuật toán có tốt hơn thuật toán khác hay không.
How is the data set going to say, I want to use a sort-merge join over a hash join?
Dữ liệu sẽ cho biết thế nào để tôi chọn dùng sort-merge join thay vì hash join?
And again, that's going to then feed into the optimizer when it's trying to then figure out, oh, I want to join table R and S.
Và điều đó sau này sẽ được đưa vào bộ tối ưu hóa khi nó cố gắng xác định, ồ, tôi muốn join bảng R và S.
I want to use this algorithm. I want to use that algorithm. But for us today, we're not worried about that decision yet.
Tôi muốn dùng thuật toán này. Tôi muốn dùng thuật toán kia. Nhưng hôm nay chúng ta chưa lo về quyết định đó.
We just want to know how to determine whether one algorithm is going to be better than another. So for the first one, the output.
Chúng ta chỉ muốn biết cách xác định xem một thuật toán có tốt hơn thuật toán khác hay không. Vậy trước tiên là đầu ra.
Again, when we do a join, the basic idea is taking a tuple from one table and a tuple from the other table that are getting matched on some join key, and I want to then match them together into a single new output tuple, right?
Một lần nữa, khi thực hiện join, ý tưởng cơ bản là lấy một tuple từ một bảng và một tuple từ bảng kia được ghép cặp với nhau dựa trên một khóa join nào đó, rồi tôi muốn ghép chúng lại thành một tuple đầu ra mới duy nhất, đúng không?
And so what this output's going to look like, it's going to depend on a bunch of different factors of how we actually implement our system.
Và đầu ra này sẽ trông như thế nào thì phụ thuộc vào nhiều yếu tố khác nhau về cách chúng ta thực sự cài đặt hệ thống.
But we already saw a little bit of this last class when we talked about the difference between early materialization and late materialization.
Nhưng chúng ta đã thấy một chút về điều này trong buổi trước khi nói về sự khác biệt giữa early materialization và late materialization.
And now, again, when we talk about sorting, but now in the context of joins, this is going to matter because now we're going to assume the data that's coming out of our join operator is going to be used by another operator in our query plan or produces the final output, so we need to decide what this should look like and how do we pass data along, whether to pass data along or not.
Và bây giờ, khi nói về sắp xếp, nhưng trong ngữ cảnh của join, điều này sẽ quan trọng vì giờ đây chúng ta sẽ giả định dữ liệu đi vào từ toán tử join của chúng ta sẽ được một toán tử khác trong kế hoạch truy vấn sử dụng, hoặc tạo ra kết quả cuối cùng, nên ta cần quyết định nó trông như thế nào và truyền dữ liệu đi ra sao, có truyền dữ liệu đi hay không.
So again, early materialization is that the idea is that all the data we're going to need to do the join or anything else in the query plan is going to be given to us or fed up to us from the bottom in the leaf nodes, right?
Vậy nhắc lại, early materialization có ý tưởng là toàn bộ dữ liệu mà ta cần để thực hiện phép join hoặc bất cứ thao tác nào khác trong kế hoạch truy vấn sẽ được đưa cho ta hoặc đẩy lên cho ta từ bên dưới, từ các nút lá, đúng không?
So now if I'm joining tuples from R and S, the output tuple is going to be a concatenation of all the tuples from R, sorry, all the attributes from R, all the attributes from S, and then we'll just mash them together and stitch them together like this, right?
Giờ nếu tôi join các tuple từ R và S, thì tuple đầu ra sẽ là phép nối của tất cả các tuple từ R, xin lỗi, tất cả các thuộc tính từ R, tất cả các thuộc tính từ S, rồi ta chỉ việc ghép chúng lại với nhau như thế này, đúng không?
So that's what will get passed up after we do this join.
Đó là thứ sẽ được truyền lên sau khi ta thực hiện phép join này.
So I'm feeding tuples up from R, feeding tuples up from S, again, I do a filter, but then if I match on the join key where R.ID equals S.ID, The output result is going to be, again, all the columns from R and all the columns from S stitched together.
Vậy tôi đẩy các tuple từ R lên, đẩy các tuple từ S lên, vẫn lọc như trước, nhưng nếu khớp khóa join, tức R.ID bằng S.ID, thì kết quả đầu ra, một lần nữa, sẽ là tất cả các cột từ R và tất cả các cột từ S được ghép lại với nhau.
And so the advantage, again, of early materialization is that we never have to go back to our base tables, R and S, to go get more data, because everything's being passed up to us from the leaves.
Và như vậy, ưu điểm của early materialization là ta không bao giờ phải quay lại các bảng gốc, R và S, để lấy thêm dữ liệu, vì mọi thứ đã được truyền lên cho ta từ các nút lá.
And then recall that late materialization is that instead of passing up data, we're actually just going to pass up the record ID.
Còn late materialization, nhớ lại, là thay vì truyền dữ liệu lên, ta chỉ truyền lên record ID.
And then the bare minimum we need to actually do the join, maybe it's the columns that are being used in the join predicate, the join expression.
Cùng với đó là lượng tối thiểu cần có để thực hiện phép join, có thể là các cột được dùng trong vị từ join, tức biểu thức join.
So in this case here, I have the RID and then the SID, because that's what I'm trying to join on in my ON clause in my query.
Trong trường hợp này, tôi có RID và SID, vì đó là thứ tôi dùng để join trong mệnh đề ON của truy vấn.
And then instead of having all the extra attributes for both these two tuples, or for these two tables, I'm just going to have the record ID.
Và thay vì mang theo tất cả các thuộc tính thừa của hai tuple này, hay của hai bảng này, tôi chỉ giữ record ID.
And then I do my join, match these two guys together, and then that's what gets passed up.
Sau đó tôi thực hiện join, ghép hai tuple này lại với nhau, và đó là thứ được truyền lên.
And now with late materialization, the problem, or the challenge, is going to be that at some later point in my query plan, I need another attribute from table S, and that's not going to be passed along in the tuple that's coming as part of the output of my join.
Với late materialization, vấn đề, hay thách thức, là ở một thời điểm nào đó sau này trong kế hoạch truy vấn, tôi cần thêm một thuộc tính từ bảng S, mà thuộc tính đó sẽ không được truyền theo trong tuple là đầu ra của phép join.
I've got to again go down, make a call down to whatever this base table is, and go get that data. All right?
Tôi lại phải đi xuống, gọi xuống bảng gốc nào đó, và lấy dữ liệu đó. Đúng không?
So the advantage of this, in the context of column stores, where joins are, I'm not saying they're nothing, not that they're more common than in OLAP queries, but, I'm sorry, in OLTP workloads, but in OLAP queries, you usually end up joining more tables than you would in an OLTP system.
Ưu điểm của cách này, trong bối cảnh column store, nơi các phép join, tôi không nói là chúng không đáng kể, không phải là phổ biến hơn so với truy vấn OLAP, mà xin lỗi, so với khối lượng công việc OLTP, còn trong truy vấn OLAP, bạn thường phải join nhiều bảng hơn so với trong hệ thống OLTP.
So again, in the column store system, I didn't have to go read the data from the other columns that I didn't need to do my join.
Vậy nên, trong hệ thống column store, tôi không phải đọc dữ liệu từ các cột khác mà tôi không cần để thực hiện phép join.
And furthermore, if my join is very selective, Meaning I'm throwing away a lot of tuples because they're not matching my join clause, then I'm going to have a win because the number of tuples I'm going to be passing up is quite small.
Hơn nữa, nếu phép join của tôi có tính chọn lọc cao, nghĩa là tôi loại bỏ rất nhiều tuple vì chúng không khớp với mệnh đề join của tôi, thì tôi sẽ có lợi, vì số lượng tuple mà tôi truyền lên phía trên là khá nhỏ.
Then who cares if I have to go then fetch the remaining data that I need from the columns that I didn't pass up, because these guys down here could have been a billion tuples, but I ended up with two after the join.
Vậy thì ai quan tâm nếu sau đó tôi phải lấy nốt phần dữ liệu còn lại mình cần từ những cột mà tôi chưa truyền lên, bởi vì những cột ở dưới đây có thể có tới một tỉ tuple, nhưng sau join tôi chỉ còn hai.
And so therefore, it's not a lot of data I have to go read to go complete the query.
Vì vậy, lượng dữ liệu tôi phải đọc để hoàn thành truy vấn không nhiều.
Again, the main thing that I'm saying from the join algorithm is that we're going to take attributes from one table, attributes from the other table, and they'll get matched together.
Một lần nữa, điều chính tôi muốn nói về thuật toán join là ta sẽ lấy các thuộc tính từ một bảng, các thuộc tính từ bảng kia, và chúng sẽ được ghép với nhau.
And you'll have to pass along the join key in order to compute that join, but whether or not you pass along the other attributes depends on the system and whether we're implementing late materialization or early materialization.
Và bạn sẽ phải truyền khóa join đi để tính phép join đó, còn việc có truyền các thuộc tính khác hay không thì tùy thuộc vào hệ thống và việc ta cài đặt late materialization hay early materialization.
All right. The other thing we need to, again, determine whether one algorithm is going to be better than another is the cost.
Được rồi. Một điều nữa mà ta cần, một lần nữa, để xác định xem thuật toán này có tốt hơn thuật toán kia hay không là chi phí.
So unlike in, I guess, your algorithms class, it's usually, like, you know, complexity defined in terms of, like, the number of times I have to do a certain operation in the actual computation itself.
Không như trong lớp thuật toán của các bạn, thường thì, bạn biết đấy, độ phức tạp được định nghĩa theo, chẳng hạn, số lần tôi phải thực hiện một phép toán nào đó trong chính bản thân quá trình tính toán.
For us, when we do joins in this class, we're going to be focused on the amount of I/O I have to use for both reading and writing data.
Còn với chúng ta, khi làm join trong lớp này, ta sẽ tập trung vào lượng I/O mà tôi phải dùng cho cả việc đọc lẫn ghi dữ liệu.
If I have to spill things at disk and write it back out, I've got to keep track of those costs, and if I've got to read it back in, I've got to keep those costs as well.
Nếu tôi phải đẩy dữ liệu ra đĩa rồi ghi ra, tôi phải tính các chi phí đó, và nếu phải đọc lại vào, tôi cũng phải tính các chi phí đó.
We saw this, again, with the sort-merge algorithm from last class.
Ta đã thấy điều này với thuật toán sort-merge ở buổi trước.
So for today's lecture, we're going to assume that we're going to be joining tables R and S, and we'll say that for table R, it's going to have big M pages in the table and a total of little m tuples in the table, And then we'll have the same thing for S, with big N for the number of pages and little n for the number of tuples, right?
Vậy trong bài giảng hôm nay, ta sẽ giả sử rằng ta sẽ join hai bảng R và S, và ta sẽ nói rằng với bảng R, nó có M trang (M viết hoa) trong bảng và tổng cộng m tuple (m viết thường) trong bảng. Và ta có tương tự cho S, với N viết hoa là số trang và n viết thường là số tuple, đúng không?
For this class here, again, we're only focusing on disk I/O because that's going to be the slowest thing for us. Therefore, we're going to ignore the cost of actually doing the actual join itself.
Trong lớp này, một lần nữa, ta chỉ tập trung vào I/O đĩa vì đó sẽ là thứ chậm nhất đối với ta. Do đó, ta sẽ bỏ qua chi phí của việc thực hiện chính phép join.
Like, if we build a hash table, we're ignoring that cost. If we probe the hash table, we ignore that cost. Last class, we talked about comparing keys in the sort algorithm.
Chẳng hạn, nếu ta xây dựng bảng băm, ta bỏ qua chi phí đó. Nếu ta dò trong bảng băm, ta cũng bỏ qua chi phí đó. Buổi trước, ta đã nói về việc so sánh các khóa trong thuật toán sắp xếp.
We'll ignore that cost as well because the disk I/O is going to be super expensive.
Ta cũng sẽ bỏ qua chi phí đó vì I/O đĩa sẽ cực kỳ tốn kém.
We're also going to assume that everything is going to fit on a single machine, and therefore, we are not worried about sending data over the network.
Ta cũng sẽ giả sử mọi thứ đều vừa trong một máy duy nhất, và do đó, ta không lo về việc gửi dữ liệu qua mạng.
When we talk about distributed databases, then that all comes back. The network costs become a big part of the cost, right?
Khi nói về cơ sở dữ liệu phân tán thì tất cả những điều đó sẽ quay lại. Chi phí mạng trở thành một phần lớn của chi phí, đúng không?
Because now you may be sending things across the world, and that's super expensive. Again, for this class here, we're just going to focus on disk I/O.
Bởi vì lúc đó bạn có thể đang gửi dữ liệu đi khắp thế giới, và điều đó cực kỳ tốn kém. Một lần nữa, trong lớp này, ta chỉ tập trung vào I/O đĩa.
For all these algorithms as well, we're also going to ignore the cost of the output of the operators because they're going to be the same for one algorithm to the next.
Với tất cả các thuật toán này, chúng ta cũng sẽ bỏ qua chi phí xuất kết quả của các toán tử vì chi phí đó sẽ giống nhau giữa thuật toán này và thuật toán khác.
Because I have my hash join algorithm and my nested loop join algorithm. They're all going to produce the same logical result.
Vì tôi có thuật toán hash join và thuật toán nested loop join. Chúng đều sẽ tạo ra cùng một kết quả logic.
It might be sorted in a different order, but again, relational model is unsorted, so that's okay. But the number of tuples that are going to be passing up is going to be the same.
Có thể kết quả được sắp xếp theo thứ tự khác, nhưng như đã nói, mô hình quan hệ là không có thứ tự, nên điều đó không sao. Nhưng số lượng tuple được chuyển lên trên sẽ là như nhau.
So we'll ignore that cost as well. All right. So the... I sort of already said this, but I should say this as well.
Vì vậy chúng ta cũng sẽ bỏ qua chi phí đó. Được rồi. Còn... tôi cũng đã nói điều này rồi, nhưng tôi vẫn nên nói thêm.
Again, the inner join is the most common thing we want to do, common join operator we want to do in our database systems.
Phép inner join là thứ phổ biến nhất mà chúng ta muốn thực hiện, là toán tử join phổ biến mà ta muốn làm trong các hệ quản trị cơ sở dữ liệu.
So we're going to spend a lot of time to make that as efficient as possible, and that's what this class is all about. Sometimes you see some systems also support cross joins.
Vì vậy chúng ta sẽ dành nhiều thời gian để làm cho nó hiệu quả nhất có thể, và đó chính là nội dung của môn học này. Đôi khi bạn thấy một số hệ thống cũng hỗ trợ cross join.
There's not really much you can do to make these things work efficiently because it's just two stupid for loops.
Thật ra không có nhiều việc bạn có thể làm để chúng chạy hiệu quả vì nó chỉ là hai vòng lặp for ngớ ngẩn.
You're just taking all the tuples from one table and mashing it together with all the tuples from the other table.
Bạn chỉ lấy tất cả các tuple từ một bảng rồi ghép chúng với tất cả các tuple của bảng kia.
Building a hash table or sorting things ahead of time doesn't help you in any way.
Xây dựng bảng băm hay sắp xếp trước cũng không giúp ích gì cho bạn.
You obviously can batch things to reduce the number of times you have to go back and fetch data, but at the end of the day, there really isn't anything you can make that work really efficiently.
Dĩ nhiên bạn có thể xử lý theo lô để giảm số lần phải quay lại lấy dữ liệu, nhưng suy cho cùng, thật sự không có gì bạn có thể làm để nó chạy hiệu quả cả.
So again, we're just going to focus on doing the inner joins because that's the most common thing, and there we can do some techniques and some tricks to make things run faster.
Vì vậy, chúng ta sẽ chỉ tập trung vào các inner join vì đó là thứ phổ biến nhất, và ở đó ta có thể dùng một số kỹ thuật và mẹo để chạy nhanh hơn.
All right, so here's the menu for today. We're going to go through the most basic algorithm, the nested loop join.
Được rồi, đây là nội dung của hôm nay. Chúng ta sẽ đi qua thuật toán cơ bản nhất, nested loop join.
This is what most people build first when you build a database system that needs to support joins. We'll talk about three different variants of this.
Đây là thứ mà hầu hết mọi người xây dựng đầu tiên khi xây dựng một hệ quản trị cơ sở dữ liệu cần hỗ trợ join. Chúng ta sẽ nói về ba biến thể khác nhau của nó.
Then we'll spend a little time talking about the sort merge join, but then we'll spend most of our time talking about how to do hash joins, because hash joins are going to be the most important join operator you can have in your system, and this will be what, you know, if you want your joins to run fast, you'd want to build this first before a sort merge join, right?
Sau đó chúng ta sẽ dành một chút thời gian nói về sort merge join, nhưng rồi sẽ dành phần lớn thời gian để nói về cách thực hiện hash join, vì hash join sẽ là toán tử join quan trọng nhất mà bạn có thể có trong hệ thống của mình, và nếu bạn muốn các phép join chạy nhanh, bạn nên xây dựng nó trước sort merge join, đúng không?
All right, so let's look at what I'll call a naive nested loop join, and this is sort of a way of, like, this is a straw man to say why, you know, here's a bad way to do a join, and then we'll see how to build upon this and make this run faster, right?
Được rồi, hãy xem cái mà tôi gọi là naive nested loop join, và đây là một cách để, một ví dụ làm "bung xung" để thấy đây là cách làm join tệ, rồi sau đó ta sẽ xem cách phát triển từ đó để nó chạy nhanh hơn, đúng không?
So we're going to do a join table R and S. It's called nested loop join because the actual implementation of this algorithm is just a bunch of nested for loops, all right?
Chúng ta sẽ thực hiện join bảng R và S. Nó được gọi là nested loop join vì cách cài đặt thực tế của thuật toán này chỉ là một loạt vòng lặp for lồng nhau, được chứ?
So for every single tuple in R, We're going to go get every single tuple in S, check to see whether our join keys match. If yes, then emit it as part of our output.
Với mỗi tuple trong R, chúng ta sẽ lấy từng tuple trong S, kiểm tra xem các khóa join có khớp nhau không. Nếu có, thì xuất nó ra như một phần của kết quả.
So the parlance we'll use, or sorry, the vernacular we'll use for when we talk about joins is the inner table and outer tables, and this comes from these nested for loops, right?
Vậy thuật ngữ mà chúng ta sẽ dùng, à xin lỗi, cách gọi mà chúng ta sẽ dùng khi nói về phép join là bảng trong (inner table) và bảng ngoài (outer table), và cách gọi này xuất phát từ các vòng lặp for lồng nhau, đúng không?
So we'll say the outermost for loop is called the outer table, and the inner one, the one in the middle, is called the inner table.
Vòng lặp for ngoài cùng được gọi là bảng ngoài, còn vòng lặp bên trong, vòng ở giữa, được gọi là bảng trong.
So even though people, even for like a hash join algorithm, sometimes, you know, it's not going to be doing nested for loops, but people still maybe refer to these things as the outer table and the inner table.
Dù là người ta, ngay cả với thuật toán hash join, đôi khi, bạn biết đấy, nó sẽ không chạy các vòng lặp for lồng nhau, nhưng người ta vẫn có thể gọi những thứ này là bảng ngoài và bảng trong.
And in most diagrams of query plans, the outer is on the left, the inner is on the right. Some systems, I think, Snowflake reverses it, right?
Và trong hầu hết các sơ đồ kế hoạch truy vấn, bảng ngoài nằm bên trái, bảng trong nằm bên phải. Một số hệ thống, tôi nghĩ Snowflake thì đảo ngược lại, đúng không?
There's not like a specific term, like a specific way to say, like within a diagram, this is definitely going to be the inner versus the outer.
Không có một thuật ngữ cụ thể nào, một cách nói cụ thể nào để cho biết trong một sơ đồ, chắc chắn đây là bảng trong hay bảng ngoài.
You have different systems, for whatever reason, do different things in their visualizations of query plans. So again, I've already said this just now, like this is bad, don't do this.
Các hệ thống khác nhau, vì lý do nào đó, thể hiện kế hoạch truy vấn theo những cách khác nhau. Vậy nên, như tôi vừa nói, cách này tệ, đừng làm thế.
Why is it bad? Why is it stupid? What's that? It says quadratic, yes. The IO, absolutely yes.
Tại sao nó tệ? Tại sao nó ngốc? Gì vậy? Bạn nói là bậc hai, đúng. Về IO, hoàn toàn đúng.
So this is like stupidly naive, right?
Nên cách này ngây thơ đến ngốc nghếch, đúng không?
This is just saying, for every single tuple in R, scan S in its entirety, go get every single tuple in every single page, read it again, and then get the next tuple in the outer table in R and do the exact same scan all over again, right?
Nó chỉ nói rằng, với mỗi tuple trong R, quét toàn bộ S, lấy từng tuple trong từng trang, đọc lại một lần nữa, rồi lấy tuple tiếp theo trong bảng ngoài R và lại thực hiện đúng lần quét y hệt, đúng không?
It's naively stupid and it's super expensive.
Nó ngây thơ đến ngốc nghếch và cực kỳ tốn kém.
So in this case here, would be the cost of me, big M plus, so the big M is for the scanning all the pages in the outer table.
Vậy trong trường hợp này, chi phí sẽ là M lớn cộng, trong đó M lớn là để quét tất cả các trang của bảng ngoài.
And then for all the tuples in the outer table, I got to scan all the pages of the inner table.
Và rồi với tất cả các tuple trong bảng ngoài, tôi phải quét tất cả các trang của bảng trong.
So little m is all the tuples in the outer table and then big N is all the pages in the inner table, right?
Vậy m nhỏ là số tuple trong bảng ngoài và N lớn là số trang của bảng trong, đúng không?
So if you just put some numbers to this, you'll see how terrible this actually is. Again, this is like the dumbest thing you could ever actually do, right?
Nếu bạn thử đưa số vào, bạn sẽ thấy nó thực sự tệ đến mức nào. Một lần nữa, đây là việc ngốc nhất mà bạn có thể làm, đúng không?
So if our table is kind of small, right? It has a thousand pages in R with 100,000 tuples and 500 pages in S with 40,000 tuples.
Giả sử bảng của ta khá nhỏ, đúng không? R có một nghìn trang với 100.000 tuple và S có 500 trang với 40.000 tuple.
If we just plug and chug our numbers in, we end up with us having to do 50 million IOs.
Nếu ta cứ thế thay số vào, ta sẽ phải thực hiện 50 triệu IO.
And if we actually put a wall clock time, say how much is the cost for one IO, this is running on SSD and on a local box, 100 milliseconds is reasonable.
Và nếu quy ra thời gian thực, giả sử chi phí cho một IO là bao nhiêu, chạy trên SSD và trên máy cục bộ, 100 mili giây là hợp lý.
It's slow, but it's a ballpark number, right?
Chậm, nhưng đó là con số ước chừng, đúng không?
Just joining these two tables, if you just go fetch every single page and ignoring like hardware caching, OS caching, anything, if I had to go pay the cost of going to fetch every single page for the outer table, sorry, the inner table, for every single tuple in the outer table, that'll take 1.3 hours.
Chỉ để join hai bảng này, nếu bạn lấy từng trang một và bỏ qua bộ nhớ đệm phần cứng, bộ nhớ đệm của hệ điều hành, mọi thứ, nếu tôi phải trả chi phí để đi lấy từng trang của bảng ngoài, xin lỗi, bảng trong, cho mỗi tuple trong bảng ngoài, thì sẽ mất 1,3 giờ.
All right? So remember I said before that in general, we always want to put the smaller table as the outer table.
Được chứ? Vậy hãy nhớ tôi đã nói trước đó rằng nhìn chung, ta luôn muốn đặt bảng nhỏ hơn làm bảng ngoài.
So in this case here, the smaller table is S that has fewer pages and fewer tuples.
Vậy trong trường hợp này, bảng nhỏ hơn là S, vì nó có ít trang hơn và ít tuple hơn.
So if I just switch the order of them, right, and now plug and chug, I got the time down to 1.1 hours.
Nên nếu tôi chỉ đổi thứ tự của chúng, đúng không, rồi thay số vào tính, tôi giảm được thời gian xuống còn 1.1 giờ.
So, you know, I saved, what, 20 minutes, but it's still not that great. So in my example here, these two tables are ridiculously small.
Vậy là, bạn biết đấy, tôi tiết kiệm được, khoảng 20 phút, nhưng vẫn chưa tốt lắm. Trong ví dụ này, hai bảng này nhỏ đến mức vô lý.
Assuming I'm doing four kilobyte pages, then the size of this one example here is six megabytes. Like, that'll sit in easily in your L3 cache.
Giả sử tôi dùng các trang 4 kilobyte, thì kích thước của bảng trong ví dụ này là sáu megabyte. Tức là nó nằm gọn trong L3 cache của bạn một cách dễ dàng.
You don't have to go to disk, but you could easily do this joining entirely in CPU cache land. And that's going to be really fast.
Bạn không cần phải truy cập đĩa, mà hoàn toàn có thể thực hiện phép join này ngay trong vùng CPU cache. Và việc đó sẽ rất nhanh.
But if I have to go pay that disk IO cost, if I'm naively going, getting every page of the inner table for every tuple in the outer table, it's going to be horribly, horribly slow.
Nhưng nếu tôi phải trả chi phí IO đĩa, nếu tôi làm một cách ngây thơ, là lấy mọi trang của bảng trong cho mỗi tuple của bảng ngoài, thì nó sẽ chậm khủng khiếp.
So this is like the dumbest thing you can do. Let's see how we can actually make this a little bit better.
Vì vậy đây là việc ngớ ngẩn nhất mà bạn có thể làm. Hãy xem làm thế nào để cải thiện nó một chút.
So one simple thing is to do what's called a block nested loop join.
Một cách đơn giản là dùng cái gọi là block nested loop join.
And this is, again, because we know our tuples are not just sitting by themselves on disk, they're in pages with other tuples that they're friends with, then when we go fetch a page, we want to do as much processing with all the tuples in that page before we move on to the next page.
Và điều này, một lần nữa, là vì chúng ta biết các tuple không nằm riêng lẻ trên đĩa, mà nằm trong các trang cùng với những tuple khác, như những người bạn của chúng, nên khi chúng ta đi lấy một trang, chúng ta muốn xử lý càng nhiều càng tốt với tất cả các tuple trong trang đó trước khi chuyển sang trang tiếp theo.
So we just change now our two nested for loops to be four nested for loops, where for every single block in the outer table, go get a block on the inner table, and then every single tuple in a block on the outer table, do the join against all the tuples in the inner table.
Vậy ta chỉ cần đổi hai vòng lặp for lồng nhau thành bốn vòng lặp for lồng nhau, trong đó với mỗi block của bảng ngoài, ta lấy một block của bảng trong, rồi với mỗi tuple trong một block của bảng ngoài, ta thực hiện join với tất cả các tuple của bảng trong.
Then we can do a little bit better here, right? So now our cost is going to be M plus big M times little n.
Như vậy ta có thể làm tốt hơn một chút, đúng không? Giờ chi phí sẽ là M cộng M lớn nhân n nhỏ.
Again, big M is the cost of scanning all the pages in the outer table, but now for every single page, for every single one of those pages in the outer table, now we're doing a scan of all the pages on the inner table.
Một lần nữa, M lớn là chi phí quét tất cả các trang của bảng ngoài, nhưng giờ với mỗi trang, với mỗi một trang trong số đó của bảng ngoài, ta quét tất cả các trang của bảng trong.
Rather than doing it on a per-tuple basis, now our cost can be reduced quite significantly, right?
Thay vì làm theo từng tuple, giờ chi phí của ta có thể giảm đi khá đáng kể, đúng không?
So again, the question is, for every single big M pages in the outer table, scan all the pages in the inner table.
Vậy một lần nữa, câu hỏi là, với mỗi trang trong M lớn trang của bảng ngoài, quét tất cả các trang của bảng trong.
Yes.
Vâng, mời bạn.
The statement is, and they're correct, that it's not asymptotically better, it's just in practice the constants are better. Yes, I said this earlier. Constants matter in the database world.
Nhận xét là, và bạn nói đúng, nó không tốt hơn về mặt tiệm cận, chỉ là trong thực tế các hằng số tốt hơn. Vâng, tôi đã nói điều này trước đó. Hằng số rất quan trọng trong thế giới cơ sở dữ liệu.
So again, we want the smaller table to always be the outer table, and we would determine which one's smaller than the other not based on the number of tuples, but rather based on the number of pages, because that's the main cost for us of going to disk, is going and fetching pages, not going and fetching individual tuples.
Vậy một lần nữa, ta muốn bảng nhỏ hơn luôn là bảng ngoài, và ta sẽ xác định bảng nào nhỏ hơn bảng nào không dựa trên số tuple, mà dựa trên số trang, vì chi phí chính của việc truy cập đĩa đối với ta là đi lấy các trang, chứ không phải đi lấy từng tuple riêng lẻ.
And obviously, in this scenario here, I'm assuming I have only two buffer pages, bufferable pages, to store data. In a real system, you would have a lot more, right?
Và rõ ràng, trong kịch bản này, tôi giả sử mình chỉ có hai trang buffer, tức hai trang có thể đưa vào buffer, để lưu dữ liệu. Trong một hệ thống thực tế, bạn sẽ có nhiều hơn rất nhiều, đúng không?
So in this case here, you want to try to store, in a sort of, in a block nested loop join where you have multiple pages you can use to store the data as you scan it, you want to put as many buffers of the outer table in memory as possible, and then just leave one page for the input, for the inner table, to bring one page in,
Vậy trong trường hợp này, bạn muốn tìm cách lưu trữ, kiểu như, trong một block nested loop join, nơi bạn có nhiều trang có thể dùng để lưu dữ liệu khi quét nó, bạn muốn đưa càng nhiều buffer của bảng ngoài vào bộ nhớ càng tốt, rồi chỉ để lại một trang cho đầu vào, cho bảng trong, để đưa vào từng trang một,
and then another page to write the output after you do the join. Right? So it basically looks like this now.
và một trang nữa để ghi kết quả đầu ra sau khi thực hiện join. Đúng không? Vậy giờ nó về cơ bản trông như thế này.
For every single, for B minus two pages, B's the total number of bufferable pages I have, scan all the data I can from R, and then go fetch each individual page from S, and then just do that, do that scan of the join of the tuples in the two inner for loops.
Với mỗi lần, cho B trừ hai trang, B là tổng số trang buffer tôi có, quét toàn bộ dữ liệu có thể từ R, rồi đi lấy từng trang riêng lẻ từ S, rồi cứ thế thực hiện việc quét để join các tuple trong hai vòng lặp for bên trong.
Yes?
Có câu hỏi không?
The statement is, I could emit also B minus two pages of data, but like I can only, in this sort of simplistic example, I'm going to fill up one, one page, write that out, then fill the next one up.
Ý bạn là, tôi cũng có thể xuất B trừ hai trang dữ liệu, nhưng tôi chỉ có thể, trong ví dụ khá đơn giản này, tôi sẽ lấp đầy một, một trang, ghi nó ra, rồi lấp đầy trang tiếp theo.
Yeah. Yeah, you need asynchronous I/O, and therefore you need more, yeah, keep it simple. Yes. All right. So we go back now to our formula.
Vâng. Vâng, bạn cần I/O bất đồng bộ, và do đó bạn cần nhiều hơn, vâng, cứ giữ cho đơn giản. Vâng. Được rồi. Giờ ta quay lại công thức của mình.
Assuming you have B minus two pages for scanning the outer table, now our cost is going to be big M, which again, scanning the outer table at least once, and then I get for every single, for every M divided by B minus two, and take the ceiling of that, for all those sort of batches of pages on the outer table,
Giả sử bạn có B trừ hai trang để quét bảng ngoài, thì chi phí của ta bây giờ sẽ là M lớn, tức là quét bảng ngoài ít nhất một lần, rồi với mỗi, mỗi M chia B trừ hai, và lấy trần của nó, tức là với tất cả các lô trang của bảng ngoài,
I got to scan all the pages on the inner table.
tôi phải quét tất cả các trang của bảng trong.
And then plugging, chugging now with our simple formulas we had before, assuming that, you know, we have, you know, if everything can fit in memory, we can get this down now to, to our, the join of R and S from our simple example before, down to 0.15 seconds.
Và giờ cứ thay số vào các công thức đơn giản ta có trước đó, giả sử là, bạn biết đấy, nếu mọi thứ đều vừa trong bộ nhớ, ta có thể giảm nó xuống, phép join của R và S từ ví dụ đơn giản trước đó, xuống còn 0,15 giây.
So 150 milliseconds. So just by bashing things up and taking advantage of the memory that's available to us in the buffer pool, we went from 1.1 hours to less than a second.
Tức là 150 mili giây. Vậy chỉ bằng cách gộp các thứ lại và tận dụng bộ nhớ có sẵn trong buffer pool, ta đã đi từ 1,1 giờ xuống dưới một giây.
Why is it M plus N? Sorry, what?
Tại sao lại là M cộng N? Xin lỗi, gì cơ?
Well, because everything fits in memory, then I read it all once, everything fits in memory, and then I just join it.
Vì mọi thứ đều vừa trong bộ nhớ, nên tôi đọc hết một lần, mọi thứ vừa trong bộ nhớ, rồi chỉ việc join.
Why is it not the constant above?
Tại sao nó không phải là hằng số ở trên?
Because the ceiling M divided by B minus two, that's if, like, I have a batch where I'm reading things in, and then for that batch of the outer table, scan the inner table.
Vì trần của M chia B trừ hai, là khi tôi có một lô mà tôi đọc vào, rồi với lô đó của bảng ngoài, quét bảng trong.
If all the pages in the outer table and the inner table fit in memory, just scan it all, that's the M and the N, add it together, and just do the join on that.
Nếu tất cả các trang của bảng ngoài và bảng trong đều vừa trong bộ nhớ, cứ quét hết, đó là M và N, cộng chúng lại, rồi thực hiện join trên đó.
So what I'm trying to point out here is even though the nested loop join seems kind of brain dead and stupid, if everything fits in memory and maybe everything already is in memory, this is actually pretty fast, Right?
Vậy điều tôi muốn chỉ ra ở đây là dù cho nested loop join trông có vẻ khá ngớ ngẩn và ngu ngốc, nhưng nếu mọi thứ vừa trong bộ nhớ, và có thể mọi thứ vốn đã nằm sẵn trong bộ nhớ, thì thực ra nó khá nhanh, đúng không?
And we'll see when we talk about hash joins, there may be cases where you do some of, some of the join will be done sort of using the hash join with the building hash table, but the other, other, a small portion of it can be done using this sort of in-memory nested loop join, because you can rip through it pretty fast.
Và chúng ta sẽ thấy khi nói về hash join, có những trường hợp một phần của phép join sẽ được thực hiện bằng hash join với việc xây dựng bảng băm, nhưng phần còn lại, một phần nhỏ khác, có thể được thực hiện bằng kiểu nested loop join trong bộ nhớ này, vì bạn có thể chạy qua nó rất nhanh.
So now if I only have B minus, or B equals one or two, then I can get this down to 6,000 IOs, so about 600 milliseconds.
Vậy bây giờ nếu tôi chỉ có B trừ, hay B bằng một hoặc hai, thì tôi có thể giảm xuống còn 6.000 IO, tức khoảng 600 mili giây.
But then if I, again, switch the outer to the inner one, make sure the outer table is, is the smaller one, then I can get it down to 5,500.
Nhưng nếu tôi lại hoán đổi bảng ngoài với bảng trong, đảm bảo bảng ngoài là bảng nhỏ hơn, thì tôi có thể giảm xuống còn 5.500.
Yes.
Vâng.
Then what, sorry?
Sao cơ, xin lỗi?
Yeah, their statement is, and they're correct, that if everything fits in memory, is it just the naive nested loop join? Yes. And if everything's in memory, that's fine.
Vâng, ý của bạn là, và bạn nói đúng, nếu mọi thứ vừa trong bộ nhớ thì cứ dùng naive nested loop join là được, phải không? Đúng. Và nếu mọi thứ nằm trong bộ nhớ thì như vậy là ổn.
And so when we talk about the hash join, the, one of the approaches will be, will be to, one of the approaches is divide and conquer.
Và khi nói về hash join, một trong những cách tiếp cận sẽ là chia để trị.
We'll split things up in such a way that we can maybe try to keep everything in memory, and then the naive nested loop join will, will work the best.
Chúng ta sẽ chia nhỏ dữ liệu sao cho có thể cố giữ mọi thứ trong bộ nhớ, và khi đó naive nested loop join sẽ hoạt động tốt nhất.
If I have to go to disk, it's terrible. If everything's in memory, then I'm great.
Nếu phải xuống đĩa thì rất tệ. Nếu mọi thứ trong bộ nhớ thì tuyệt vời.
All right, so, why is this so bad? Because we already said this.
Được rồi, vậy tại sao nó lại tệ đến thế? Vì chúng ta đã nói điều này rồi.
Again, if I had to go to disk, then I'm basically doing a sequential scan over and over again on the inner table to try to match things from the outer table.
Một lần nữa, nếu phải xuống đĩa, thì về cơ bản tôi cứ quét tuần tự lặp đi lặp lại trên bảng trong để cố khớp các bản ghi từ bảng ngoài.
So you may say, all right, well, sequential scans are not great. We spent a bunch of time learning about indexes.
Bạn có thể nói, được rồi, quét tuần tự thì không hay. Chúng ta đã dành khá nhiều thời gian để học về chỉ mục.
If I have an index, can I take advantage of that to make my, so that inner for loop on the inner table, make that go faster? The answer is yes. We can do this.
Nếu có chỉ mục, liệu tôi có tận dụng nó để làm cho vòng lặp for bên trong trên bảng trong chạy nhanh hơn không? Câu trả lời là có. Chúng ta có thể làm vậy.
Some systems, like SQL Server we talked about before, will, If you're doing a join or any kind of operation on a table, and if the optimizer realizes, "Hey, it'd be really nice if I had an index for this table to make my query go faster," it'll build that index for you, do whatever operation you want to do in your query, and then immediately just throw it away.
Một số hệ thống, như SQL Server mà chúng ta đã nói trước đây, nếu bạn thực hiện join hoặc bất kỳ thao tác nào trên một bảng, và nếu trình tối ưu hóa nhận ra rằng: "Này, sẽ rất tốt nếu có một chỉ mục cho bảng này để truy vấn chạy nhanh hơn", thì nó sẽ xây dựng chỉ mục đó cho bạn, thực hiện thao tác bạn muốn trong truy vấn, rồi ngay lập tức bỏ nó đi.
And then it'll also give you back warnings and say, "Hey, look, I keep building this index for this table for your queries.
Và nó cũng sẽ gửi lại cảnh báo, nói rằng: "Này, tôi cứ phải xây dựng chỉ mục này cho bảng này cho các truy vấn của bạn.
It'd be really nice if you tell me I can have it for good and keep it around." And then a human has to decide whether to do that or not.
Sẽ rất tốt nếu bạn cho tôi biết là có thể giữ nó lại lâu dài." Và sau đó một con người phải quyết định có làm vậy hay không.
All right, so if you have an existing index, then you can modify the nested loop join algorithm to do what's called an index nested loop join algorithm. All right?
Được rồi, nếu bạn đã có sẵn một index, thì bạn có thể sửa đổi nested loop join thành thuật toán gọi là index nested loop join. Được chứ?
And it basically is now the outer table, you're still scanning through all the tuples.
Về cơ bản, bây giờ với bảng ngoài, bạn vẫn quét qua tất cả các tuple.
Then for the inner table, I'm going to take a key that I extract from the outer table tuple and then do a probe into whatever the index is that I have available to me and then see whether I have a match.
Sau đó với bảng trong, tôi sẽ lấy một khóa trích ra từ tuple của bảng ngoài rồi thực hiện một lần probe vào index nào đang có sẵn và xem có khớp hay không.
And that's essentially doing, you know, doing the join for you.
Về bản chất, đó chính là việc thực hiện phép join cho bạn.
So the cost for this is hard to define because it's obviously going to depend on what your index is and what data structure it actually is and the size of it.
Chi phí của cách này khó xác định, vì rõ ràng nó sẽ phụ thuộc vào index của bạn là gì, nó thực sự là cấu trúc dữ liệu nào và kích thước của nó.
So in general, though, we would say the cost now is going to be big M, because, again, we always have to scan all the pages in the outer table.
Tuy nhiên nói chung, ta sẽ nói chi phí bây giờ là M lớn, vì, một lần nữa, ta luôn phải quét tất cả các trang của bảng ngoài.
And then for every single tuple in the inner table, sorry, every single tuple in the outer table, we'll do some kind of probe into this index to, again, find a match.
Và sau đó với mỗi tuple của bảng trong, xin lỗi, mỗi tuple của bảng ngoài, ta sẽ thực hiện một kiểu probe vào index này để tìm ra kết quả khớp.
And, again, we can't define this C easily because, You know, in this class here, because it's going to depend on a bunch of different factors that can vary from one index to the next.
Và ta không thể xác định C này một cách dễ dàng, trong lớp này, vì nó sẽ phụ thuộc vào hàng loạt yếu tố khác nhau mà có thể thay đổi từ index này sang index khác.
Right? Whether it's a B+tree or a skip list or a trie or a hash table. Right? But this is basically what the hash join is going to do. Right?
Đúng không? Dù đó là B+tree, skip list, trie hay hash table. Nhưng về cơ bản đây cũng là điều mà hash join sẽ làm.
So in this case here, assuming I have a B+tree, again, I could probe in that and use that to make a nested loop join, index nested loop join.
Vậy trong trường hợp này, giả sử tôi có một B+tree, tôi có thể probe vào đó và dùng nó để làm nested loop join, tức index nested loop join.
The hash join basically says, I don't have an index, so let me build a hash table now and then do the same kind of probe like this and then throw it away when the query is done, the same way that SQL Server does.
Còn hash join về cơ bản nói rằng: tôi không có index, vậy hãy để tôi xây dựng một hash table ngay bây giờ rồi thực hiện cùng kiểu probe như vậy, sau đó vứt nó đi khi truy vấn kết thúc, giống như cách SQL Server làm.
All right.
Được rồi.
So the main takeaway is for the nested loop join, if everything's in memory, it's going to be super fast and that's going to be actually preferable in many cases.
Vậy điều cần rút ra chính là với nested loop join, nếu mọi thứ đều nằm trong bộ nhớ thì nó sẽ cực kỳ nhanh và thực tế trong nhiều trường hợp đó là lựa chọn tốt hơn.
But in general, if we know we have to go read from disk, then I'm going to want to make sure the smaller table is always going to be the outside.
Nhưng nói chung, nếu ta biết mình phải đọc từ đĩa, thì tôi sẽ muốn bảo đảm bảng nhỏ hơn luôn là bảng ngoài.
Try to batch as much as I can on that outer table as I can in my buffer pool, because that'll make things go up. It'll make things run faster. Okay.
Cố gắng gom thành lô càng nhiều càng tốt của bảng ngoài đó vào buffer pool, vì điều đó sẽ giúp mọi thứ tăng tốc. Nó sẽ làm mọi thứ chạy nhanh hơn. Được rồi.
So the next join algorithm we're going to talk about is, again, sort-merge join. And this is going to be built upon the external merge sort or the sorting stuff we talked about last class.
Vậy thuật toán join tiếp theo mà ta sẽ nói tới, một lần nữa, là sort-merge join. Và nó sẽ được xây dựng dựa trên external merge sort, hay những nội dung về sắp xếp mà ta đã nói ở buổi trước.
And as I said before, since the 1970s, it was this back and forth in the research literature about whether sorting algorithms are better than hash-based algorithms.
Và như tôi đã nói trước đây, từ thập niên 1970, trong các tài liệu nghiên cứu luôn có sự tranh luận qua lại về việc các thuật toán sắp xếp có tốt hơn các thuật toán dựa trên hash hay không.
And then originally sorting was faster because the computers were really slow and hashing was really expensive. And then hashing algorithms got better but then the hardware got better and sorting got better.
Ban đầu sắp xếp nhanh hơn vì máy tính rất chậm và hashing rất tốn kém. Rồi các thuật toán hashing trở nên tốt hơn nhưng rồi phần cứng tốt hơn và việc sắp xếp cũng tốt hơn.
It keeps going back and forth. And in general, the hash join is going to be preferable over the sort-merge join. But you'd want to still have a SortMergeJoin, because if your query is...
Cứ thế qua lại mãi. Và nói chung, hash join sẽ được ưu tiên hơn sort-merge join. Nhưng bạn vẫn muốn có SortMergeJoin, vì nếu truy vấn của bạn...
the data is already sorted on your join key, or there's an ORDER BY clause where you need to sort the data, you can kill two birds with one stone by doing this algorithm and producing results that are sorted for you.
có dữ liệu đã được sắp xếp sẵn theo khóa join, hoặc có mệnh đề ORDER BY khiến bạn cần sắp xếp dữ liệu, thì bạn một mũi tên trúng hai đích bằng cách dùng thuật toán này và tạo ra kết quả đã được sắp xếp sẵn cho bạn.
All right. So SortMergeJoin has two phases.
Được rồi. SortMergeJoin có hai giai đoạn.
And again, the confusing thing about this is that last time we talked about the external merge sort algorithm, and we're going to use the external merge sort in our...
Và một lần nữa, điều gây nhầm lẫn ở đây là lần trước chúng ta đã nói về thuật toán external merge sort, và chúng ta sẽ dùng external merge sort trong...
We can use the external merge sort for our SortMergeJoin algorithm, and we'd use that external merge sort as a sort phase in our join algorithm. And then the merge phase in the sort algorithm...
Chúng ta có thể dùng external merge sort cho thuật toán SortMergeJoin, và dùng external merge sort đó làm giai đoạn sắp xếp trong thuật toán join. Và giai đoạn merge trong thuật toán sắp xếp...
The join algorithm is different than the merge phase in the sort algorithm. Right? I'm not trying to confuse you.
Thuật toán join khác với giai đoạn merge trong thuật toán sắp xếp. Đúng không? Tôi không cố làm các bạn rối đâu.
I'm just trying to say we can still use this external merge sort, which has its own two phases, in our join algorithm, which is going to have its own other two phases.
Tôi chỉ muốn nói là chúng ta vẫn có thể dùng external merge sort này, vốn có hai giai đoạn riêng của nó, trong thuật toán join của chúng ta, vốn có hai giai đoạn riêng khác.
All right? All right. So the basic idea is that we have our two tables that we want to join, and we're going to sort them based on our join keys.
Được chứ? Được rồi. Vậy ý tưởng cơ bản là chúng ta có hai bảng cần join, và sẽ sắp xếp chúng theo khóa join.
And then we're going to have... And that's what you do in the first phase.
Và sau đó chúng ta sẽ... Đó là việc làm ở giai đoạn đầu.
Then the second phase, you have these cursors that are going to walk through your sorted tables and start comparing across to see whether you have a match.
Rồi đến giai đoạn thứ hai, bạn có các con trỏ duyệt qua các bảng đã sắp xếp và bắt đầu so sánh chéo để xem có khớp hay không.
And if you do, then you emit them as part of the join output. And then you just keep moving the cursors forward, marching through, and producing results.
Nếu có, bạn xuất chúng ra như một phần của kết quả join. Rồi cứ tiếp tục dịch các con trỏ về phía trước, duyệt tiếp, và tạo ra kết quả.
And the advantage, because the data is being sorted, at least in the outer table, you know you won't have to... Sorry. Yeah.
Và ưu điểm là, vì dữ liệu đã được sắp xếp, ít nhất ở bảng ngoài, bạn biết là sẽ không phải... Xin lỗi. Vâng.
The outer table, you won't have to backtrack up in the sort of results to look at tuples over and over again. In the inner table, you may still have to do that.
Với bảng ngoài, bạn sẽ không phải quay lui lên trên trong kết quả đã sắp xếp để xét đi xét lại các tuple. Với bảng trong, bạn vẫn có thể phải làm vậy.
But again, it's a simple trick to keep track of these things.
Nhưng đó là một mẹo đơn giản để theo dõi những thứ này.
But the sorting allows us to identify that we know there isn't going to be any match at some prior point in the table once we reach a certain point with our cursor, because the data is sorted.
Nhưng việc sắp xếp cho phép ta biết rằng sẽ không có khớp nào ở một điểm phía trước trong bảng khi con trỏ đã tới một vị trí nhất định, vì dữ liệu đã được sắp xếp.
We can't see, magically, a value that should appear up above down below us. In the back, yes. The question is, can I explain an example with the backtrack?
Không thể có chuyện một giá trị lẽ ra nằm ở phía trên lại xuất hiện phía dưới chúng ta một cách thần kỳ. Ở phía sau, vâng. Câu hỏi là, tôi có thể giải thích một ví dụ về quay lui không?
Yes. Let me give a demonstration. Yes. All right. Let me just skip this. This is the algorithm. Again, I don't like to show code in class.
Được. Để tôi minh họa. Vâng. Được rồi. Tôi bỏ qua phần này. Đây là thuật toán. Một lần nữa, tôi không thích đưa code lên trong lớp.
But basically, there's two cursors. You scan through until you reach the end. And then there's a lot to say whether one increments versus the other and whether you need the backtrack.
Nhưng về cơ bản, có hai con trỏ. Bạn quét cho đến khi tới cuối. Và có nhiều điều để nói về việc tăng con trỏ này so với con trỏ kia và khi nào cần quay lui.
Let's go through an actual example. Here we have our two tables we want to join, the R and S. The first phase of the sort-merge join algorithm is to sort them.
Hãy cùng xem một ví dụ thực tế. Ở đây chúng ta có hai bảng cần join, R và S. Giai đoạn đầu của thuật toán sort-merge join là sắp xếp chúng.
We want to join on the ID column. In both these tables, we're just going to go ahead and sort them.
Chúng ta muốn join trên cột ID. Với cả hai bảng này, ta cứ sắp xếp chúng trước.
Then now, when we enter the second phase to do our merge, we're going to have these two cursors that are going to start at the beginning of their two sorted tables and start comparing with each other on the join key to see whether we have a match.
Rồi bây giờ, khi bước vào giai đoạn thứ hai là merge, ta sẽ có hai con trỏ bắt đầu từ đầu của hai bảng đã được sắp xếp và bắt đầu so sánh với nhau trên khóa join để xem có khớp hay không.
And to handle backtracking, we're also going to keep track of this last value that says, here's the last value I saw as my cursor on the inner table moves down.
Và để xử lý việc quay lui, ta cũng sẽ theo dõi giá trị cuối cùng này, tức là giá trị cuối cùng mà tôi đã thấy khi con trỏ trên bảng trong đi xuống.
So that way, if we then see a join key on the outer table that could have matched something up above in our inner table, we know how to go back and start the scan on that again.
Như vậy, nếu sau đó ta thấy một khóa join trên bảng ngoài có thể khớp với thứ gì đó ở phía trên trong bảng trong, thì ta biết cách quay lại và bắt đầu quét lại từ chỗ đó.
So we start at the very beginning. Both two cursors are pointing to the first tuple. The join key is based on ID.
Vậy ta bắt đầu từ vị trí đầu tiên. Cả hai con trỏ đều trỏ vào tuple đầu tiên. Khóa join dựa trên ID.
So in this case here, 100 equals 100. So this is a match. And we just produce our output like that by just mashing the two tuples, the attributes in the two tuples together.
Trong trường hợp này, 100 bằng 100. Vậy đây là một cặp khớp. Và ta tạo kết quả đầu ra bằng cách ghép hai tuple lại với nhau, tức là ghép các thuộc tính của hai tuple.
Now in this case here, because we have now a match, we're going to just move the inner table's cursor down by one.
Bây giờ, vì ta vừa có một cặp khớp, ta chỉ việc dời con trỏ của bảng trong xuống một dòng.
And we leave the outer table's cursor where it is. Now we do a comparison. 100 equals 100. We have another match. We produce that as an output.
Và giữ nguyên con trỏ của bảng ngoài. Giờ ta so sánh. 100 bằng 100. Lại khớp. Ta xuất kết quả đó ra.
And then now we're going to move down for it again on the inner table. But now at this point here, the value we're looking at is different than the last value we just saw.
Và rồi ta lại dời xuống tiếp trên bảng trong. Nhưng bây giờ, tại điểm này, giá trị ta đang xét khác với giá trị cuối cùng vừa thấy.
So we've got to record that this is the last value that we saw. So we saw 100 before 200. So we keep track that we have 100. All right.
Nên ta phải ghi lại rằng đây là giá trị cuối cùng ta đã thấy. Ta thấy 100 trước 200. Nên ta ghi nhớ là có 100. Được rồi.
So now at this point here, 200 is greater than 100. So we know that we need to move down the outer table's cursor by one.
Vậy bây giờ, 200 lớn hơn 100. Nên ta biết cần dời con trỏ của bảng ngoài xuống một dòng.
Because at this point here, there isn't going to be another value on the inner table that can match with 100 where the outer table is pointing at.
Vì tại điểm này, sẽ không còn giá trị nào khác trên bảng trong có thể khớp với 100 mà bảng ngoài đang trỏ tới.
So we move the outer table's cursor and not the inner table's cursor. So that comes down here. It's 200. Again, 200 equals 200. So we have a match.
Vậy ta dời con trỏ của bảng ngoài chứ không dời con trỏ của bảng trong. Nó xuống đây. Là 200. Lại một lần nữa, 200 bằng 200. Vậy là khớp.
We produce our output. Again, and then now we move the inner table down. Record that the last value that we saw was 200 because now we're seeing 400.
Ta xuất kết quả. Rồi bây giờ ta dời bảng trong xuống. Ghi lại rằng giá trị cuối cùng ta thấy là 200 vì giờ ta đang thấy 400.
And again, 400 is now greater than on the inner table. 400 is greater than 200 on the outer table. So we're going to then move down the outer table's cursor down by one.
Và một lần nữa, 400 trên bảng trong lúc này lớn hơn 200 trên bảng ngoài. Nên ta sẽ dời con trỏ của bảng ngoài xuống một dòng.
Now we see 200 again. And we check our last value. We see that, oh, we just saw 200 before we got to 400.
Giờ ta lại thấy 200. Và ta kiểm tra giá trị cuối cùng. Ta thấy là, à, ta vừa thấy 200 trước khi đến 400.
So now we know we need to backtrack and move the inner table's cursor back up to where 200 was so that we can essentially restart this process of scanning the data in the inner table for the new tuple on the outer table.
Vậy bây giờ ta biết cần quay lui và dời con trỏ của bảng trong ngược lên chỗ có 200 để về cơ bản ta có thể bắt đầu lại quá trình quét dữ liệu trong bảng trong cho tuple mới của bảng ngoài.
So then now again, we have another match on 200. We move the inner table down by one. Now we get 400. This scans down. We get 300.
Vậy bây giờ, ta lại có một cặp khớp nữa trên 200. Ta dời bảng trong xuống một dòng. Giờ ta có 400. Quét xuống. Ta có 300.
300 is less than 400, so we know we want to move down the outer table cursor because there isn't something we can match here on the inner table because we're already at 400.
300 nhỏ hơn 400, nên ta biết cần dời con trỏ bảng ngoài xuống vì không có gì để khớp ở đây trên bảng trong, bởi ta đã ở 400 rồi.
Because things are sorted, we know that we're not magically going to see a 300 later on because it would have appeared before we saw a 400, and we didn't see that.
Vì dữ liệu đã được sắp xếp, ta biết sẽ không thể bỗng dưng thấy một giá trị 300 ở phía sau, vì nó đã phải xuất hiện trước khi ta thấy 400, và chúng ta đã không thấy giá trị đó.
So we move the outer table down by one. Now we have a match on 400. That's good. Inner table moves down by one. Now we have 500. Keep our last value as 400.
Vậy ta di chuyển bảng ngoài xuống một dòng. Giờ ta có một cặp khớp ở 400. Tốt. Bảng trong di chuyển xuống một dòng. Giờ ta có 500. Giữ giá trị cuối cùng là 400.
We're pointing at 500, though 500 is less than, is greater than 400, so the outer table moves down. Now we have 500 again, and that's a match.
Ta đang trỏ vào 500, mà 500 nhỏ hơn, à lớn hơn 400, nên bảng ngoài di chuyển xuống. Giờ ta lại có 500, và đó là một cặp khớp.
And now the inner table's cursor reaches the bottom.
Và giờ con trỏ của bảng trong đã chạm đáy.
We still got to keep track of the last value for ourselves, even though we reached the bottom because we don't know what we're going to see.
Ta vẫn phải tự theo dõi giá trị cuối cùng, dù đã chạm đáy, vì ta không biết sắp thấy giá trị nào.
We might have another match on the outer table again, but now we get 600.
Có thể lại có một cặp khớp khác ở bảng ngoài, nhưng giờ ta gặp 600.
600 is less than, sorry, 600 is greater than 500, so we know at this point we can short circuit because there isn't anything that we'll ever see that will match between these two joins, so we can just scan through and just say we're done.
600 nhỏ hơn, xin lỗi, 600 lớn hơn 500, nên đến đây ta biết có thể dừng sớm, vì sẽ không có gì mà ta sẽ thấy có thể khớp giữa hai bảng của phép nối này nữa, nên ta có thể quét nốt và kết luận là xong.
Let's finish up. Questions? Yes?
Ta kết thúc phần này. Có câu hỏi không? Vâng?
Yes, the statement he made, and he's correct, is that the reason why we keep this last value is because there may be multiple tuples on the inner table matching with a tuple on the outer table.
Vâng, nhận định của bạn ấy, và bạn ấy đúng, là lý do ta giữ giá trị cuối cùng này là vì có thể có nhiều tuple ở bảng trong khớp với một tuple ở bảng ngoài.
Yes.
Vâng.
Now, you can be smart about it and say, oh, if I'm doing a join on columns where they're a unique column or primary key, then I know that I won't have duplicates on the inner table for any match on the outer table.
Bây giờ, bạn có thể khôn ngoan hơn và nói: nếu tôi nối trên các cột là cột duy nhất hoặc khóa chính, thì tôi biết sẽ không có bản sao trùng lặp ở bảng trong cho mỗi lần khớp với bảng ngoài.
So in that case here, you don't need to do any backtracking at all. But in general, you may not be able to know that, therefore you have to maintain this.
Vậy trong trường hợp đó, bạn hoàn toàn không cần quay lui. Nhưng nói chung, bạn có thể không biết được điều đó, nên bạn phải duy trì giá trị này.
What if there was two 100s? So going back up here.
Nếu có hai số 100 thì sao? Quay lại phía trên này.
Oh, so what, like, yeah, so in that case here, you'd have to keep track of, like, well, no, so if you had two 100s, so you see this first one, 100 here.
À, vậy thì, đúng rồi, trong trường hợp đó bạn sẽ phải theo dõi, à không, nếu có hai số 100, thì bạn thấy số 100 đầu tiên ở đây.
So you do this. You would scan through. You match that. That's fine. And then now, the inner table would come down.
Bạn làm thế này. Bạn quét qua. Bạn khớp nó. Ổn. Rồi sau đó, bảng trong sẽ đi xuống.
You would keep track of the last value as 100. The outer table moves down. It would see 200, sorry, it would see 100 again.
Bạn giữ giá trị cuối cùng là 100. Bảng ngoài di chuyển xuống. Nó sẽ thấy 200, xin lỗi, nó sẽ lại thấy 100.
At this point, it says, oh, okay, well, that was my last value, so let me backtrack the inner table. I don't have to backtrack on the outer table ever for this.
Lúc này nó nói: à, được rồi, đó là giá trị cuối cùng của tôi, vậy để tôi quay lui ở bảng trong. Ở đây tôi không bao giờ phải quay lui ở bảng ngoài.
The statement isn't correct. Like, when it backtracks, it backtracks to the first 100, where this was. I'm not recording the pointer, but, like, it would keep track of that.
Nhận định đó không đúng. Khi quay lui, nó quay về số 100 đầu tiên, chỗ ở đây. Tôi không ghi con trỏ ra, nhưng nó sẽ theo dõi điều đó.
And again, if the worst case scenario, if I only have one value in this column when I'm joining, then I'm backtracking at the very beginning.
Và một lần nữa, trong trường hợp xấu nhất, nếu cột tôi đang nối chỉ có một giá trị duy nhất, thì tôi sẽ quay lui ngay từ đầu.
But again, there's no algorithm to make that work great. Yes? Right, I was trying to avoid that.
Nhưng lại nói, không có thuật toán nào làm cho trường hợp đó chạy tốt. Vâng? Đúng, tôi đã cố tránh điều đó.
So the statement is, and he's correct, well, this is an equality predicate, like equi-join. What if it's not that?
Nhận định là thế này, và bạn ấy đúng, đây là vị từ so sánh bằng, tức là equi-join. Nếu không phải vậy thì sao?
Then you have to have additional logic to keep track of, Could I see something based on my join predicate? Is something going to be above or below me?
Thì bạn phải có thêm logic để theo dõi, liệu tôi có thể thấy gì đó dựa trên vị từ nối của mình không? Liệu có thứ gì nằm phía trên hay phía dưới tôi không?
It's more complicated, but yes, you'd have to do that.
Phức tạp hơn, nhưng đúng vậy, em sẽ phải làm như thế.
The statement, the question is, could you figure out something in all cases? What do you mean by figure it out? What do you mean?
Câu hỏi là, liệu em có thể tìm ra cách làm trong mọi trường hợp không? Em muốn nói "tìm ra cách" nghĩa là sao? Ý em là gì?
The question is, could you figure out a way to do a sort merge join for all join conditions? Yeah, no, you can do it for all of them.
Câu hỏi là, liệu em có thể tìm ra cách thực hiện sort merge join cho mọi điều kiện join không? Vâng, được, em có thể làm điều đó cho tất cả.
If I'm saying the logic of backtracking is way more complicated.
Tôi đang nói rằng logic quay lui phức tạp hơn nhiều.
Other questions? That's a nice way to end it. That's nice. Yeah, good. Okay. So, all right, so what is our cost for this?
Còn câu hỏi nào khác không? Đó là một cách kết thúc hay đấy. Tốt. Vâng, hay. Được rồi. Vậy chi phí của phương pháp này là bao nhiêu?
Well, again, we have two phases. We have the sort phase and the merge phase. The sort phase cost is whatever our sort algorithm is going to be for both the two tables.
À, một lần nữa, chúng ta có hai pha: pha sắp xếp và pha trộn. Chi phí pha sắp xếp là chi phí của thuật toán sắp xếp mà chúng ta dùng cho cả hai bảng.
So again, if I'm doing the sort merge join from the last class, then it's the 2M times everything else there because I'm getting B-1 buffer pages.
Vậy nếu tôi dùng sort merge join như ở buổi trước, thì nó là 2M nhân với phần còn lại ở đó vì tôi có B-1 trang bộ đệm.
So I have whatever my cost is for sorting those two, the two input tables.
Vậy tôi có chi phí sắp xếp hai bảng đầu vào đó.
And then now the merge cost, without any backtracking, is just reading all the pages for both the inner table and the outer table once.
Còn chi phí trộn, khi không có quay lui, chỉ là đọc tất cả các trang của cả bảng trong và bảng ngoài đúng một lần.
Backtracking complicates things because then, like, you'd have to know the distribution of the keys and how many duplicates you're going to have per key. So we can't, obviously, put that in our formula here.
Quay lui làm mọi thứ phức tạp hơn vì khi đó, em sẽ phải biết phân bố của các khóa và mỗi khóa sẽ có bao nhiêu bản sao trùng lặp. Vì thế rõ ràng chúng ta không thể đưa điều đó vào công thức ở đây.
And this will be one of the reoccurring themes when we talk about query optimization. They make a bunch of assumptions of what your data looks like because it simplifies these formulas.
Và đây sẽ là một trong những chủ đề lặp lại nhiều lần khi chúng ta nói về tối ưu hóa truy vấn. Họ đưa ra một loạt giả định về việc dữ liệu trông như thế nào vì điều đó làm các công thức này đơn giản hơn.
Because otherwise, how could you know?
Bởi nếu không thì làm sao biết được?
So if I go back to what we wrote in numbers, again, sorting these two tables here, assuming I have 100 buffer pool pages, then the sort cost for table R is 4,000 IOs.
Nếu quay lại những gì chúng ta đã viết bằng số, một lần nữa, sắp xếp hai bảng này, giả sử tôi có 100 trang buffer pool, thì chi phí sắp xếp bảng R là 4.000 IO.
The sort cost for table S is 2,000 IOs, right? But then the merge cost is just, again, scanning of the pages that are sorted once, and that's down to 1,500 IOs.
Chi phí sắp xếp bảng S là 2.000 IO, đúng không? Nhưng chi phí trộn chỉ là, lại là quét các trang đã sắp xếp đúng một lần, và con số đó chỉ còn 1.500 IO.
So the total cost is now 7,500 IOs.
Vậy tổng chi phí bây giờ là 7.500 IO.
So in the case of the everything's in memory, that was 150 milliseconds. Now we're down to 7... We're at 750 milliseconds. And then we can still spill to disk if necessary.
Trong trường hợp mọi thứ nằm trong bộ nhớ, con số đó là 150 mili giây. Giờ chúng ta giảm xuống 7... chúng ta còn 750 mili giây. Và chúng ta vẫn có thể ghi tràn ra đĩa nếu cần.
This is starting to look pretty good.
Trông bắt đầu khá tốt rồi.
I've already mentioned this now, but the worst case scenario for us for pretty much all the join algorithms is that you have the two tables you're trying to join on, they have one value for all the tuples.
Tôi đã nhắc đến điều này rồi, nhưng trường hợp xấu nhất với hầu như mọi thuật toán join là khi hai bảng mà em đang cố join có cùng một giá trị cho tất cả các bộ.
In that case, there's nothing you can do to make that work well. It's like, you know, worst case scenario. But in general, data doesn't usually look like that.
Trong trường hợp đó, em không thể làm gì để nó chạy tốt được. Đó là kịch bản xấu nhất. Nhưng nhìn chung, dữ liệu thường không như vậy.
You wouldn't have a billion tuples that everyone has the same birthday, and you want to join these two tables. That doesn't happen that often.
Em sẽ không có một tỷ bộ mà ai cũng có cùng ngày sinh, rồi lại muốn join hai bảng này. Điều đó không xảy ra thường xuyên.
Or at the scale where this would be a huge issue.
Hoặc ở quy mô mà điều đó sẽ trở thành một vấn đề lớn.
So, as I already said, sort-merge join is going to be good for us when the data is already sorted on the join key that we want, or the output of the query, the final output, there's an ORDER BY clause that's also on our join key.
Như tôi đã nói, sort-merge join sẽ phù hợp với chúng ta khi dữ liệu đã được sắp xếp sẵn theo khóa join mà chúng ta muốn, hoặc khi đầu ra của truy vấn, tức kết quả cuối cùng, có mệnh đề ORDER BY cũng trên khóa join của chúng ta.
Because again, we can just do the sorting for both the join and the final output, and we don't have to do it as a separate step. Right? Yes.
Vì một lần nữa, chúng ta có thể sắp xếp một lần cho cả join lẫn kết quả cuối cùng, mà không cần thực hiện nó như một bước riêng. Đúng không? Vâng, mời bạn.
Yes. The statement is, and they're correct, the merge cost, going back here, of M plus N is the best case scenario. Yes, with no backtracking.
Vâng. Nhận định là, và bạn nói đúng, chi phí merge, quay lại chỗ này, là M cộng N chỉ là trường hợp tốt nhất. Đúng, khi không có backtracking.
All right. So, let's jump into the good one, the hash join.
Được rồi. Vậy chúng ta chuyển sang phần hay nhất, hash join.
So, the basic idea is, again, we have a tuple in R, we have a tuple in S, we want to join them together.
Ý tưởng cơ bản là, một lần nữa, chúng ta có một tuple trong R, một tuple trong S, và muốn join chúng với nhau.
And the idea is that we're going to use the hashing mechanism, the hash function, as a way for us to find the matching tuple from one side versus the other.
Ý tưởng là chúng ta sẽ dùng cơ chế băm, tức hàm băm, như một cách để tìm tuple khớp từ phía này sang phía kia.
And we can base it on this nice property of hash functions: given the same key, it'll produce the same output, the same hash value.
Và chúng ta có thể dựa vào một tính chất hay của hàm băm: với cùng một khóa, nó sẽ cho cùng một đầu ra, cùng một giá trị băm.
So, if my join key is the same as your join key, we want to join together, then we'll end up hashing to the same location in either a hash table or a partition, right?
Vì vậy, nếu khóa join của tôi giống khóa join của bạn, và ta muốn join với nhau, thì chúng sẽ được băm đến cùng một vị trí trong bảng băm hoặc trong một partition, đúng không?
And in the same way, when we talk about hash tables, like a way to get hash, you're sort of randomly jumping into a linear array of slots, where we may have to look around to find the data we want, because we have to sort of scan through to find the slot that has the data we want or an empty slot.
Và tương tự, khi nói về bảng băm, như một cách để lấy giá trị băm, bạn nhảy ngẫu nhiên vào một mảng tuyến tính các slot, nơi chúng ta có thể phải tìm quanh để thấy dữ liệu mình muốn, vì ta phải quét qua để tìm slot chứa dữ liệu mình muốn hoặc một slot trống.
The idea is the same, is that with hashing, we'll land in a location where the data that we could have a match, if it exists, will be nearby, and therefore, we're not having to do a complete linear scan of all the data, or a sequential scan of all the data, as we did in nested loops.
Ý tưởng cũng như vậy, với việc băm, chúng ta sẽ đáp xuống một vị trí mà dữ liệu có thể khớp, nếu tồn tại, sẽ nằm ở gần đó, và do đó ta không phải quét tuyến tính toàn bộ dữ liệu, hay quét tuần tự toàn bộ dữ liệu như trong nested loops.
So, a basic hash join algorithm on a single node has two phases.
Vậy thuật toán hash join cơ bản trên một nút đơn có hai pha.
First phase, we're going to do a sequential scan on the outer table, and then build a hash table using some hash function, and then the second phase, we're going to scan the inner table, use that same hash function, look up in the hash table to see whether we have a match on our join key.
Pha thứ nhất, chúng ta quét tuần tự bảng ngoài, rồi xây dựng một bảng băm bằng một hàm băm nào đó, và pha thứ hai, chúng ta quét bảng trong, dùng cùng hàm băm đó, tra trong bảng băm xem có khớp trên khóa join của mình hay không.
So, we can use whatever our favorite hash table we want that we discussed earlier in the semester.
Chúng ta có thể dùng bất kỳ bảng băm nào mình thích mà ta đã bàn từ đầu học kỳ.
In practice, most systems are going to use linear probe hash table because they're so simple and so fast. Even on a distributed system, it's going to work pretty well.
Trong thực tế, hầu hết các hệ thống sẽ dùng bảng băm linear probe vì chúng rất đơn giản và rất nhanh. Ngay cả trên hệ thống phân tán, nó vẫn hoạt động khá tốt.
And then inside the hash table, we'll have to at least include the join key, because again, we may hash to some location that may have an entry in that slot, But because the hash functions are not guaranteed to be free of collisions, we have to still do a comparison of the join key to see whether we have a match or not.
Và bên trong bảng băm, ít nhất ta phải đưa vào khóa join, vì một lần nữa, ta có thể băm đến một vị trí mà slot đó có thể đã có một mục. Nhưng vì hàm băm không đảm bảo không xảy ra va chạm, nên ta vẫn phải so sánh khóa join để xem có khớp hay không.
So, the basic join algorithm looks like this. We have two for loops still, but they're not nested anymore. They're just separate and executed in serial order.
Vậy thuật toán join cơ bản trông như thế này. Chúng ta vẫn có hai vòng lặp for, nhưng chúng không còn lồng nhau nữa. Chúng tách riêng và được thực thi lần lượt.
So, the first thing I'm going to do is allocate some memory for some kind of hash table, scan through the outer table, or what we call the build side of the join, use a hash function, populate the hash table, then do a sequential scan on the inner table, also called the probe side of the join, scan through, probe inside the hash table, see whether we have a match or not.
Việc đầu tiên tôi sẽ làm là cấp phát một vùng bộ nhớ cho một dạng hash table nào đó, quét qua bảng ngoài, hay còn gọi là phía build của phép join, dùng một hàm băm để điền vào hash table, rồi quét tuần tự bảng trong, còn gọi là phía probe của phép join, quét qua, dò (probe) trong hash table, xem có khớp hay không.
Alright? Pretty basic. But it works really, really well. Because again, it's basically divide and conquer. I'm taking a...
Được chứ? Khá cơ bản. Nhưng nó hoạt động cực kỳ tốt. Vì về cơ bản đây là chia để trị. Tôi lấy...
otherwise it would have been a sequential scan and narrowing down the scope amount of data I have to look at because I'll land on my hash table and find the thing that I want.
nếu không thì nó đã là một lần quét tuần tự và thu hẹp phạm vi lượng dữ liệu tôi phải xem xét vì tôi sẽ nhảy thẳng vào hash table và tìm thấy thứ mình cần.
Now, obviously, I'm going to make sure my hash table is appropriately sized so that I'm not doing the worst case, complete sequential scan of all the keys, if my hash table is too full.
Dĩ nhiên, tôi sẽ đảm bảo hash table có kích thước phù hợp để không rơi vào trường hợp xấu nhất, là quét tuần tự toàn bộ các khóa nếu hash table quá đầy.
But in general, this is going to work really well. Yes.
Nhưng nhìn chung, cách này sẽ hoạt động rất tốt. Vâng, bạn hỏi đi.
The question is, what is the difference between this and index nested loop join? Nothing. At a high level. Index nested loop join has an existing index and I use that.
Câu hỏi là: cái này khác gì index nested loop join? Không khác gì. Ở mức tổng quát. Index nested loop join có sẵn một chỉ mục và tôi dùng nó.
This is, I'm building the hash table just to do the join. Most indexes in real systems aren't going to be hash tables though.
Còn ở đây, tôi xây hash table chỉ để thực hiện phép join. Tuy nhiên, hầu hết các chỉ mục trong hệ thống thực tế không phải là hash table.
If you call create index, by default in most systems, in nearly all systems, you'll get a tree, a B+tree. And so, the B+tree is great. It's probably my... it probably is... not is, probably.
Nếu bạn gọi create index, theo mặc định ở hầu hết các hệ thống, thực tế là gần như mọi hệ thống, bạn sẽ có một cây, tức B+tree. B+tree rất tuyệt. Có lẽ nó là... có lẽ là... không phải là, mà là có lẽ.
It is the most important data structure in the world, but it's not going to be the best thing for joins. For doing a lot of joins.
Nó là cấu trúc dữ liệu quan trọng nhất thế giới, nhưng nó không phải lựa chọn tốt nhất cho phép join. Khi phải thực hiện nhiều phép join.
Because if my hash table is large enough and I don't have a lot of collisions, then I'm doing O(1) lookups. And for a billion tuples, that's a big deal.
Vì nếu hash table đủ lớn và không có nhiều va chạm, thì tôi thực hiện tra cứu O(1). Và với một tỉ tuple, đó là điều rất đáng kể.
That's going to be a huge difference in performance versus the log n traversal in a B+tree.
Hiệu năng sẽ chênh lệch rất lớn so với việc duyệt log n trong B+tree.
So one easy optimization we can do to make our hash joins go faster is to actually build a Bloom filter as we're populating the hash table.
Vậy một tối ưu hóa đơn giản để hash join chạy nhanh hơn là xây dựng một Bloom filter trong lúc điền hash table.
And then now when I want to do my probe, I check the Bloom filter first. If there's a match, then I probe the hash table; otherwise I don't probe the hash table.
Rồi khi cần probe, tôi kiểm tra Bloom filter trước. Nếu có khớp, thì tôi mới probe hash table; nếu không thì không probe hash table.
So this is sometimes called sideways information passing. Some systems will call these Bloom joins. The basic idea is all the same, even though it has different names.
Kỹ thuật này đôi khi được gọi là sideways information passing. Một số hệ thống gọi đây là Bloom join. Ý tưởng cơ bản đều giống nhau dù tên gọi khác nhau.
So say that now I'm going to build my hash table on R. This will be the build side.
Giả sử giờ tôi xây hash table trên R. Đây sẽ là phía build.
So as I'm scanning through R, I'm populating the hash table, but then I'm also going to be building a Bloom filter.
Khi quét qua R, tôi điền vào hash table, nhưng đồng thời tôi cũng xây một Bloom filter.
And then now once the hash table is done and now I want to start scanning S to do the probe into the hash table, I'm basically going to pass along the Bloom filter over to this guy and say, hey, before you check the hash table, go check the Bloom filter.
Rồi khi hash table đã xong và tôi muốn bắt đầu quét S để probe vào hash table, về cơ bản tôi sẽ chuyển Bloom filter sang bên này và nói: này, trước khi kiểm tra hash table, hãy kiểm tra Bloom filter đã.
Because the idea is that I still have to hash anyway to probe into the hash table, but then landing in the hash table and then doing the scan and doing the key comparisons, that could be rather expensive.
Vì ý tưởng là dù sao tôi vẫn phải băm để dò vào bảng băm, nhưng việc đi vào bảng băm rồi quét và so sánh các khóa có thể khá tốn kém.
Whereas just doing the Bloom filter lookup, that's way faster.
Trong khi chỉ tra cứu Bloom filter thì nhanh hơn rất nhiều.
So this is great when my join predicate or my join keys are very selective, meaning most of the tuples I'm examining aren't going to match on the join and I'm throwing most of them away.
Vì vậy cách này rất tốt khi vị từ join hay các khóa join có tính chọn lọc cao, nghĩa là hầu hết các tuple tôi xét sẽ không khớp trong phép join và tôi loại bỏ phần lớn chúng.
Then this would be a huge win for us, because doing a lookup on the Bloom filter is super cheap relative to the hash table.
Khi đó đây sẽ là một lợi ích rất lớn cho chúng ta, vì việc tra cứu trên Bloom filter rẻ hơn rất nhiều so với bảng băm.
So this is a weird thing, for like, kind of violates the notion of, like, in our query plan where we're sending data from one operator to the next, because we're taking information that we collect on R and having this side channel thing we pass over to S.
Đây là một điều hơi lạ, vì nó như là vi phạm quan niệm trong kế hoạch truy vấn, nơi ta gửi dữ liệu từ toán tử này sang toán tử tiếp theo, bởi vì ta lấy thông tin thu thập được trên R và dùng một kênh phụ để truyền sang S.
But again, the win is going to be quite significant. Like, in some, in really selective joins, this can be like a 2x performance improvement, or just building the bloom filter.
Nhưng một lần nữa, lợi ích thu được là khá đáng kể. Chẳng hạn, với các phép join có tính chọn lọc cao, hiệu năng có thể được cải thiện khoảng 2 lần, chỉ nhờ việc xây dựng Bloom filter.
All right.
Được rồi.
So the example I showed before for the simple hash join was kind of like the naive nested loop join, where like you assume everything's in memory and you kind of rip through it.
Ví dụ tôi trình bày trước đó cho simple hash join giống như nested loop join ngây thơ, trong đó bạn giả định mọi thứ đều nằm trong bộ nhớ và cứ thế chạy qua hết.
But if everything's not in memory, then we need to be able to still handle that.
Nhưng nếu không phải mọi thứ đều nằm trong bộ nhớ, ta vẫn cần xử lý được trường hợp đó.
And we don't want to maybe build a giant hash table for our, to do our join, because the hash table is not going to fit in memory, and now we're doing random I/O to different locations or different slots in that hash table, and that's going to be terrible for us for performance.
Và có thể ta không muốn xây dựng một bảng băm khổng lồ để thực hiện join, vì bảng băm sẽ không vừa trong bộ nhớ, và khi đó ta phải thực hiện I/O ngẫu nhiên tới các vị trí khác nhau hay các slot khác nhau trong bảng băm đó, và điều đó sẽ rất tệ cho hiệu năng.
So we're going to rely on, and again, that same divide and conquer approach, where we're going to split the data set we want to join up into smaller subsets and potentially build hash tables for those smaller subsets that do fit in memory, and then rip through that very efficiently.
Vì vậy ta sẽ dựa vào cách tiếp cận chia để trị quen thuộc, trong đó ta chia tập dữ liệu cần join thành các tập con nhỏ hơn và có thể xây dựng bảng băm cho từng tập con nhỏ đó, vừa trong bộ nhớ, rồi chạy qua chúng một cách rất hiệu quả.
So this idea goes back to the 1980s. I think the textbook calls these partition hash joins. Sometimes you'll see in the literature they're called Grace hash joins.
Ý tưởng này có từ những năm 1980. Tôi nghĩ giáo trình gọi đây là partition hash join. Đôi khi trong các tài liệu bạn sẽ thấy nó được gọi là Grace hash join.
And this is named after a seminal work in the 1980s out of Japan building this database machine called Grace.
Cái tên này đến từ một công trình có tính nền tảng ở Nhật Bản vào những năm 1980 xây dựng một máy cơ sở dữ liệu có tên là Grace.
And they had a paper saying, hey look, we have this great database machine called Grace, and here's the hash join we're using.
Họ có một bài báo nói rằng, này, hãy xem, chúng tôi có chiếc máy cơ sở dữ liệu tuyệt vời tên là Grace, và đây là hash join mà chúng tôi đang dùng.
And so the Grace database machine obviously no longer exists, but the legacy is this hash join that pretty much everybody uses today.
Dĩ nhiên máy cơ sở dữ liệu Grace giờ không còn tồn tại nữa, nhưng di sản của nó là hash join mà hầu như ai cũng dùng ngày nay.
So, like the other algorithms we talked about, it's kind of two phases. We have the partition phase.
Giống như các thuật toán khác đã nói, nó gồm hai pha. Pha phân vùng.
We're going to go through both tables, hash the join keys, and then divide it up into partitions and the buckets.
Ta sẽ đi qua cả hai bảng, băm các khóa join, rồi chia chúng thành các phân vùng và các bucket.
And then in the second phase, for each partition level, we're going to again scan through the data and just do the simple hash join that resides in memory that we saw before.
Sau đó ở pha thứ hai, với mỗi phân vùng, ta lại quét qua dữ liệu và thực hiện simple hash join trong bộ nhớ như ta đã thấy trước đó.
Who here has heard of the term database machine before? Probably nobody. All right. It's basically specialized hardware that people built specifically to run database systems.
Ở đây có ai từng nghe đến thuật ngữ database machine (máy cơ sở dữ liệu) chưa? Chắc là không có ai. Được rồi. Về cơ bản đó là phần cứng chuyên dụng mà người ta chế tạo riêng để chạy các hệ quản trị cơ sở dữ liệu.
This is why database systems are the most important piece of software.
Đây là lý do hệ quản trị cơ sở dữ liệu là phần mềm quan trọng nhất.
Think of, like, other than, you know, crypto stuff he was doing, like other than people building specialized hardware for crypto, or maybe, like, you know, graphics and things like that, or machine learning, people have been building specialized hardware for databases for a long time.
Hãy nghĩ xem, ngoài, bạn biết đấy, mấy thứ về tiền mã hóa mà anh ấy từng làm, tức là ngoài việc người ta chế tạo phần cứng chuyên dụng cho tiền mã hóa, hoặc có thể là đồ họa và những thứ tương tự, hay học máy, thì người ta đã chế tạo phần cứng chuyên dụng cho cơ sở dữ liệu từ rất lâu rồi.
So this is one of the earliest ones from one of the early days, called IDM. I just like this picture because the guy's, like, in a suit working on a database.
Đây là một trong những máy đầu tiên, từ những ngày đầu, có tên là IDM. Tôi thích bức ảnh này vì anh chàng mặc vest đang làm việc với một cơ sở dữ liệu.
This is what the future was going to look like. But they were building specialized hardware to do sorting in network as well. And this, again, is from the 1980s.
Tương lai lúc đó được hình dung sẽ trông như thế này. Họ cũng chế tạo phần cứng chuyên dụng để sắp xếp ngay trong mạng. Và điều này, một lần nữa, là từ những năm 1980.
That company's obviously no longer there, but there's a bunch of companies around today that'll sell you database appliances, instead of calling them data machines, called appliances, that, again, are customized hardware or tuned hardware to run database, you know, database workloads.
Công ty đó rõ ràng không còn nữa, nhưng ngày nay có một loạt công ty bán cho bạn các database appliance, thay vì gọi là máy dữ liệu thì gọi là appliance, tức là phần cứng được tùy biến hoặc tinh chỉnh để chạy các khối lượng công việc cơ sở dữ liệu.
Most famous of these is probably going to be Oracle Exadata, and then the Teradata stuff. Right. Think of, like, massive data warehouses.
Nổi tiếng nhất trong số đó có lẽ là Oracle Exadata, và sau đó là các sản phẩm của Teradata. Đúng vậy. Hãy nghĩ đến các kho dữ liệu khổng lồ.
Each of these, each one of these racks is, like, five million dollars. Right. And then maybe double that now, but then you pay a million dollars a year for support for this.
Mỗi tủ rack như vậy có giá khoảng năm triệu đô la. Có thể bây giờ còn gấp đôi, và bạn còn trả một triệu đô la mỗi năm cho hỗ trợ.
Like, this is what you would run for high-end workloads.
Đây là thứ bạn sẽ dùng cho các khối lượng công việc cao cấp.
And inside this, I'm like, you know, Oracle controls all the hardware and the OS, will have, like, I think FPGAs and things like that inside this make it run faster.
Và bên trong đó, bạn biết đấy, Oracle kiểm soát toàn bộ phần cứng và hệ điều hành, tôi nghĩ bên trong có FPGA và những thứ tương tự để chạy nhanh hơn.
Right. One of the companies that will be giving a talk with us in a few weeks is called Yellowbrick.
Đúng vậy. Một trong những công ty sẽ có buổi nói chuyện với chúng ta trong vài tuần nữa là Yellowbrick.
They started off selling a database appliance, again thinking like specialized hardware customized for running a database workload, and this is, you know, they still make a lot of money doing this.
Họ bắt đầu bằng việc bán một database appliance, cũng là phần cứng chuyên dụng được tùy biến để chạy khối lượng công việc cơ sở dữ liệu, và họ vẫn kiếm được rất nhiều tiền từ việc này.
And so, like, just goes to show people are trying to do specialized hardware for data for a long time. Now the current trend is to see how we can leverage GPUs.
Điều đó cho thấy người ta đã cố gắng làm phần cứng chuyên dụng cho dữ liệu từ rất lâu rồi. Xu hướng hiện nay là xem làm thế nào tận dụng được GPU.
There's a bunch of companies that have been doing this for about 10 years now. We had a seminar series in 2018 where a bunch of the GPU database vendors came and gave a talk.
Có một loạt công ty đã làm việc này khoảng 10 năm nay. Chúng tôi từng có một chuỗi hội thảo vào năm 2018 trong đó nhiều nhà cung cấp cơ sở dữ liệu GPU đến nói chuyện.
We have, obviously they're competing against getting GPUs from the ML people, but there's a lot of, like, you know, one generation older GPUs that people don't want to use for training anymore for ML stuff that you can still use in databases and run efficiently.
Rõ ràng họ phải cạnh tranh để có GPU với những người làm ML, nhưng có rất nhiều GPU đời cũ hơn một thế hệ mà người ta không còn muốn dùng để huấn luyện ML nữa nhưng vẫn có thể dùng trong cơ sở dữ liệu và chạy hiệu quả.
We're not going to talk about GPU databases in this class; that'll be in the advanced class.
Chúng ta sẽ không nói về cơ sở dữ liệu chạy trên GPU trong lớp này; phần đó sẽ có trong lớp nâng cao.
Let's just say that it's people have been trying to do this for a while, but it doesn't always pan out.
Cứ nói là người ta đã thử làm điều này được một thời gian rồi, nhưng không phải lúc nào cũng thành công.
Part of the reason why the database machines in the 1980s didn't really pan out either is because in the early days of computing, like, by the time it took you to design specialized hardware, fab it, and then ship it to customers, you know, Intel or Motorola or whoever was putting out new CPUs that were, you know, pretty significant jumps in performance because of Moore's law, and the performance benefit you get from specialized hardware
Một phần lý do khiến các database machine những năm 1980 cũng không thành công thật sự là vì vào những ngày đầu của ngành máy tính, đến lúc bạn thiết kế xong phần cứng chuyên dụng, sản xuất nó, rồi giao cho khách hàng thì Intel hay Motorola hay hãng nào đó đã tung ra những CPU mới với mức tăng hiệu năng khá lớn nhờ định luật Moore, và lợi ích về hiệu năng mà bạn có được từ phần cứng chuyên dụng
just was negated pretty quickly.
bị triệt tiêu khá nhanh.
Nowadays, unless you can get it on Amazon or in the cloud, people don't really care about, you know, running specialized hardware, because it's just, you want everything to be sort of commoditized.
Ngày nay, nếu bạn không thể có nó trên Amazon hay trên đám mây, thì người ta không thực sự quan tâm đến việc chạy phần cứng chuyên dụng, vì người ta muốn mọi thứ đều được hàng hóa hóa.
Anyway, Grace Hash Join was an early days machine and there's a lot of work done in this phase.
Dù sao thì Grace Hash Join là một cỗ máy từ những ngày đầu và đã có rất nhiều công trình được thực hiện ở giai đoạn này.
It's the whole, it's the whole dream of our databases, like if I have specialized hardware to run my database system and run fast with that, would be fantastic.
Đó là toàn bộ giấc mơ của cơ sở dữ liệu, tức là nếu tôi có phần cứng chuyên dụng để chạy hệ cơ sở dữ liệu và chạy nhanh trên đó thì thật tuyệt vời.
No one really has seemed to sort of crack that nut yet.
Dường như chưa ai giải được bài toán hóc búa đó.
Okay, so the way partitioned hash join is going to work is sort of like that partitioning phase we saw when we talked about aggregations last class.
Được rồi, cách partitioned hash join hoạt động khá giống giai đoạn phân vùng mà chúng ta đã thấy khi nói về phép tổng hợp ở buổi trước.
So I'm going to scan through all the table, my outer table, use a hash function, put everything into buckets, right? Scan everything on the inner table, same thing, put everything in buckets.
Tôi sẽ quét toàn bộ bảng, bảng ngoài của tôi, dùng một hàm băm, đưa mọi thứ vào các bucket, đúng không? Quét mọi thứ ở bảng trong, làm tương tự, đưa vào các bucket.
And then now I'm going to be able to spill these out to disk if my buckets get too big.
Và khi đó tôi có thể ghi tràn chúng ra đĩa nếu các bucket quá lớn.
But then now when I want to do the sort of the second phase of, do the join, I only need to examine the data within one bucket and do the comparison across the two tables within one level of a partition, because I know that there isn't going to be a key that got hashed into partition zero at the top for R that's going to get hashed into this bottom bucket down here,
Nhưng khi tôi muốn làm giai đoạn thứ hai, tức là thực hiện phép nối, tôi chỉ cần xem xét dữ liệu trong một bucket và so sánh giữa hai bảng trong cùng một mức của phân vùng, vì tôi biết sẽ không có khóa nào được băm vào phân vùng số không ở trên cùng của R mà lại bị băm vào bucket dưới cùng ở đây,
because the hash function doesn't work that way. Because it's the same hash function, same value, they'll end up in the same level.
vì hàm băm không hoạt động như vậy. Vì là cùng một hàm băm, cùng một giá trị, chúng sẽ rơi vào cùng một mức.
So then now when I want to do my probe to do the join, I'm going to do one level at a time, bring those pages into memory, build a hash table for that, then at the same level read all those buckets from the outer table S and then do a hashing to this hash table, just again,
Vậy khi tôi muốn thực hiện bước dò để nối, tôi sẽ làm từng mức một, đưa các trang đó vào bộ nhớ, xây dựng một bảng băm cho chúng, rồi ở cùng mức đó đọc tất cả các bucket từ bảng ngoài S và băm vào bảng băm này, tương tự như trước,
now everything's in memory, find my match, produce my output.
giờ mọi thứ đều nằm trong bộ nhớ, tìm kết quả khớp, tạo ra kết quả đầu ra.
And then once I'm done probing on the S side, I throw the hash table away because I don't need it anymore, because there's never going to be another match in any other level.
Và khi tôi dò xong ở phía S, tôi vứt bảng băm đi vì không cần nó nữa, vì sẽ không bao giờ có kết quả khớp nào khác ở bất kỳ mức nào khác.
And I Just do the same thing all over again.
Và tôi chỉ lặp lại điều tương tự từ đầu.
Yes, so the question is how do I choose the number of buckets I have, and how do I...
Vâng, câu hỏi là làm sao tôi chọn số lượng bucket, và làm sao tôi...
are they just pages? They're just pages, I'm just appending to them, right?
chúng chỉ là các trang à? Đúng, chúng chỉ là các trang, tôi chỉ nối thêm vào chúng, đúng không?
And then the size is determined by the database system, either through a parameter that you can control as a human, like the operator, the administrator.
Và kích thước này do hệ quản trị cơ sở dữ liệu quyết định, hoặc thông qua một tham số mà con người có thể điều khiển, như người vận hành, người quản trị.
So you can tell, like, Postgres, like, you're allowed to use one megabyte of memory to do hash joins or something like that, right?
Ví dụ bạn có thể nói với Postgres rằng bạn được phép dùng một megabyte bộ nhớ để thực hiện hash join hoặc việc gì đó tương tự, đúng không?
So someone is telling you how many pages you get to do this, right?
Tức là có người cho bạn biết bạn được dùng bao nhiêu trang để làm việc này, đúng không?
And then if the system decides that's not gonna be enough, you do recursive partitioning, we'll see that next, right?
Và nếu hệ thống quyết định như vậy sẽ không đủ, thì bạn phân vùng đệ quy, chúng ta sẽ xem phần đó ngay sau đây, đúng không?
Memory is finite, so I just can't say I'm gonna use all my memory. Something above is determining how much resources you have.
Bộ nhớ là hữu hạn, nên tôi không thể nói là tôi sẽ dùng toàn bộ bộ nhớ. Có thứ gì đó ở tầng trên quyết định bạn có bao nhiêu tài nguyên.
Yes, the question is how is this producing a correct join, not a complete join, correct join, because your statement is, because you could have rows that would,
Vâng, câu hỏi là làm sao điều này tạo ra một phép join đúng, không phải join đầy đủ, mà là join đúng, vì ý của bạn là, có thể có những hàng mà
in one level partition, are you saying match to another level? That can never happen, right?
ở một phân vùng cấp này, lại khớp với một cấp khác, phải không? Điều đó không bao giờ xảy ra, đúng không?
Because if the join key on table R and table S, if the same values, when I hash them, same input to the same hash function, because it's deterministic, will produce the same output.
Vì nếu khóa join trên bảng R và bảng S có cùng giá trị, khi tôi băm chúng, cùng một đầu vào đưa vào cùng một hàm băm, vì nó có tính tất định, sẽ cho ra cùng một đầu ra.
I mod that by the number of, whatever, K, K here, how many levels, my partitions I have, they're gonna end up the same level always.
Tôi lấy phần dư của giá trị đó cho số, gì đó, K, K ở đây, là số cấp, số phân vùng mà tôi có, thì chúng luôn rơi vào cùng một cấp.
If they don't, then something's wrong with the hardware, and the, you know, the data system can't handle that, right?
Nếu không, thì phần cứng có vấn đề, và hệ quản trị dữ liệu không thể xử lý được chuyện đó, đúng không?
But I don't, it's like, it's like the sort-merge sort, like, because I've sorted the data, I can't, I know I can't see something that I should have seen earlier down below because it's been sorted.
Nhưng nó giống như sắp xếp trộn (sort-merge) vậy, vì tôi đã sắp xếp dữ liệu, nên tôi biết mình không thể thấy thứ lẽ ra phải thấy sớm hơn ở phía dưới, vì nó đã được sắp xếp.
If my sort algorithm is wrong, then I have a bunch of other problems, right?
Nếu thuật toán sắp xếp của tôi sai, thì tôi còn cả đống vấn đề khác, đúng không?
So if my hash function is acting all weird, then that's That's, you're in trouble, but in general the algorithm will work. Yes?
Vậy nếu hàm băm của tôi hoạt động kỳ quặc, thì bạn gặp rắc rối rồi, nhưng nói chung thuật toán sẽ hoạt động. Vâng?
So you're asking, what if I have, I think basically, what if all the, what if these buckets get too full? Yes. Next slide.
Vậy bạn đang hỏi, về cơ bản là nếu tất cả, nếu các bucket này bị đầy quá thì sao? Vâng. Slide tiếp theo.
Okay, so if the partitions don't fit in memory, which they were asking about, then I just recursively partition again, and I keep, and again, if everything still doesn't fit in memory, I just partition again.
Được rồi, nếu các phân vùng không vừa trong bộ nhớ, điều mà bạn đó vừa hỏi, thì tôi chỉ việc phân vùng đệ quy lần nữa, và tôi cứ tiếp tục, và nếu mọi thứ vẫn không vừa trong bộ nhớ, tôi lại phân vùng tiếp.
Now again, in the degenerate case, if all the values are the same across all my keys or all my tuples, then recursively partitioning doesn't do anything for us, but again, don't do that.
Dĩ nhiên, trong trường hợp suy biến, nếu tất cả giá trị đều giống nhau trên mọi khóa hay mọi tuple, thì phân vùng đệ quy chẳng giúp được gì, nhưng một lần nữa, đừng làm như vậy.
But at the end of the day, there's nothing you can do. There's no algorithm magic to make that go away.
Nhưng rốt cuộc, bạn không thể làm gì được. Không có phép màu thuật toán nào làm vấn đề đó biến mất.
So eventually I'm just going to keep sub-partitioning my partitions until they fit in memory, and then do my join.
Vì vậy cuối cùng tôi cứ tiếp tục chia nhỏ các phân vùng của mình cho đến khi chúng vừa trong bộ nhớ, rồi thực hiện join.
In practice, you only have to do one extra level of recursive partitioning in real systems.
Trong thực tế, bạn chỉ cần làm một mức phân vùng đệ quy bổ sung trong các hệ thống thực tế.
Again, if it's a degenerate case, there's nothing you can do, but if you identify that you're going to have a lot of keys that are the same, then you just fall back to do the block nested loop join.
Một lần nữa, nếu là trường hợp suy biến thì bạn không thể làm gì được, nhưng nếu bạn nhận ra rằng mình sẽ có rất nhiều khóa giống hệt nhau, thì bạn chỉ cần quay về dùng block nested loop join.
Or if my partitions are actually going to be small enough, I maybe don't want to build the hash table, we'll see in a second.
Hoặc nếu các phân vùng của tôi thực sự đủ nhỏ, thì có thể tôi không cần xây dựng bảng băm, lát nữa chúng ta sẽ thấy.
I'll just do the in-memory nested loop join, because that's going to be really fast to do as well. So let's say this is the table we want to partition, right?
Tôi sẽ chỉ thực hiện nested loop join trong bộ nhớ, vì cách đó cũng sẽ chạy rất nhanh. Giả sử đây là bảng mà chúng ta muốn phân vùng, đúng không?
We have a bunch of buckets, k-1, and then say for whatever reason, a bunch of the keys are hashing to this bucket in level 1.
Chúng ta có một loạt bucket, k-1, và giả sử vì lý do nào đó mà nhiều khóa được băm vào bucket này ở mức 1.
So I'm thinking of this like it's just every single time the page gets full, I write out to disk, I make another page.
Tôi hình dung như thế này: mỗi khi trang bị đầy, tôi ghi nó xuống đĩa rồi tạo một trang khác.
So I'm keeping track of the metadata of how many pages I have at each level. So there's some threshold to say, okay, this thing is getting too full, everything is too skewed.
Vì vậy tôi theo dõi siêu dữ liệu về số trang có ở mỗi mức. Sẽ có một ngưỡng để nói rằng, được rồi, bucket này đang quá đầy, mọi thứ bị lệch quá nhiều.
So then now I'm going to do another round of hashing, pick another hash function, take another seed for the hash function I'm using, and just partition the data at that level all over again into a bunch of more pages, a bunch more buckets.
Khi đó tôi sẽ thực hiện thêm một vòng băm nữa, chọn một hàm băm khác, lấy một seed khác cho hàm băm đang dùng, và phân vùng lại dữ liệu ở mức đó từ đầu thành nhiều trang hơn, nhiều bucket hơn.
And then for the ones that didn't, that weren't too full, I just carry them along at the next phase, because I don't need to repartition them, I don't care about them.
Còn những bucket không bị như vậy, tức là không quá đầy, thì tôi cứ giữ nguyên chuyển sang pha tiếp theo, vì tôi không cần phân vùng lại chúng, tôi không quan tâm đến chúng.
So then now as I do my scan, the same scan on the outer table, sorry, the inner table, if they hash to the two bottom ones, that's fine, I don't think anything special there.
Bây giờ khi tôi quét, cùng một lần quét trên bảng ngoài, xin lỗi, bảng trong, nếu chúng băm vào hai bucket phía dưới, thì không sao, ở đó không có gì đặc biệt.
And then now I just do my in-memory hash join as I did before.
Rồi tôi chỉ việc thực hiện hash join trong bộ nhớ như trước.
But if I recognize that I'm hashing to one of these ones that got overflowed, then I know that I need to call the second hash function to hash them again, and then now they'll land up and align with the keys coming from the outer table.
Nhưng nếu tôi nhận ra mình đang băm vào một trong những bucket bị tràn, thì tôi biết cần gọi hàm băm thứ hai để băm chúng lại, và khi đó chúng sẽ rơi vào đúng vị trí khớp với các khóa đến từ bảng ngoài.
So just like the index probe cost in index nested loop join is hard to quantify, recursive partitioning is also hard to quantify, because it depends on the key distribution, right?
Cũng như chi phí dò chỉ mục trong index nested loop join rất khó định lượng, phân vùng đệ quy cũng khó định lượng, vì nó phụ thuộc vào phân phối của khóa, đúng không?
So in general, we're just going to say to estimate the cost of hash joins is going to be this formula here.
Vì vậy nhìn chung, để ước lượng chi phí của hash join, chúng ta sẽ dùng công thức này.
So 3 times (M plus N), right, because it's one scan in for M plus N, write it out, and then one scan back in to take the partitioned buckets and then do the hash join, and everything's in memory at that point.
Đó là 3 nhân (M cộng N), đúng không, vì có một lần quét đọc vào M cộng N, rồi ghi ra, và một lần quét đọc lại để lấy các bucket đã phân vùng rồi thực hiện hash join, và lúc đó mọi thứ đều nằm trong bộ nhớ.
So using real numbers now, we can get our example table from before down to 450 milliseconds.
Bây giờ dùng số liệu thực tế, chúng ta có thể đưa bảng ví dụ lúc trước xuống còn 450 mili giây.
So sort-merge join was 750 milliseconds, in-memory nested loop join was 150 milliseconds, but if I had to spill to disk, in this case here I can get it down to 450.
Sort-merge join mất 750 mili giây, nested loop join trong bộ nhớ mất 150 mili giây, nhưng nếu phải tràn xuống đĩa, trong trường hợp này tôi có thể giảm xuống 450.
So that's pretty good.
Như vậy là khá tốt.
So one semi-easy, but not always easy to implement and difficult to get right, optimization is what is called a hybrid hash join.
Vậy có một tối ưu hóa khá dễ, nhưng không phải lúc nào cũng dễ triển khai và khó làm cho đúng, gọi là hybrid hash join.
And this is something that was invented in the early 1980s as an extension to the Grace hash join stuff.
Và kỹ thuật này được phát minh vào đầu những năm 1980 như một phần mở rộng của Grace hash join.
And this was invented by the other Davis professor, Janesh Patel's PhD advisor; invented this, I think, with Jim Gray, one of the Turing Award winners in databases back in the day.
Và nó được phát minh bởi một giáo sư khác ở Davis, thầy hướng dẫn tiến sĩ của Janesh Patel; ông ấy phát minh ra nó, tôi nghĩ là cùng với Jim Gray, một trong những người đoạt giải Turing về cơ sở dữ liệu ngày xưa.
And so basically what happens is, if you recognize that a bunch of the data, if your data is skewed and a bunch of the tuples are all going to the same partition, you'll just keep that partition in memory, spill all the other ones out to disk, and then just do an in-memory hash join
Về cơ bản, nếu bạn nhận ra rằng phần lớn dữ liệu, tức là dữ liệu của bạn bị lệch, và rất nhiều tuple đều đi vào cùng một partition, thì bạn cứ giữ partition đó trong bộ nhớ, đẩy tất cả các partition khác ra đĩa, rồi chỉ thực hiện in-memory hash join
or in-memory nested loop join for that hot partition, and then just do the regular Grace hash join algorithm for the other partitions.
hoặc in-memory nested loop join cho partition nóng đó, và với các partition còn lại thì chạy thuật toán Grace hash join thông thường.
So again, assume we have, for whatever reason, all the keys are hashing to this one here, right?
Vậy nên, giả sử vì lý do nào đó, tất cả các khóa đều băm vào partition này đây, đúng không?
So I would recognize, okay, this thing's going to be hot, so I don't want to maybe spill out to disk if it's not that big, and I can keep it in memory.
Tôi sẽ nhận ra, ok, cái này sẽ là partition nóng, nên có thể tôi không muốn đẩy nó ra đĩa nếu nó không quá lớn, và tôi có thể giữ nó trong bộ nhớ.
Let me go ahead and just do that.
Vậy cứ làm như thế đi.
So I would keep this level in memory, take all the other ones, spill those out to disk, and then I just take, now while this is already in memory, build a hash table for this, maybe not even do the bucketing phase, switch it directly to the hash table, and then now populate it as I'm scanning along, and then this guy can then do the join directly against it.
Nên tôi sẽ giữ mức này trong bộ nhớ, lấy tất cả các partition khác và đẩy chúng ra đĩa, rồi vì cái này đã nằm sẵn trong bộ nhớ, tôi xây dựng một bảng băm cho nó, thậm chí có thể không cần giai đoạn chia bucket, chuyển thẳng sang bảng băm, rồi điền dữ liệu vào khi tôi quét qua, và sau đó phần này có thể thực hiện join trực tiếp với nó.
Right, I think it's called hybrid because, again, instead of doing the hash table part at the top level here, you could just do the nested loop, nested loop join, because it's already in memory.
Tôi nghĩ nó được gọi là hybrid vì, một lần nữa, thay vì dùng phần bảng băm ở mức trên cùng này, bạn có thể chỉ cần dùng nested loop join, vì nó đã nằm trong bộ nhớ rồi.
So you're kind of doing both algorithms together. This is challenging to get right because, like, again, how do you know whether something's gonna be the hot partition or not, right?
Tức là bạn đang kết hợp cả hai thuật toán với nhau. Việc này khó làm đúng vì, ví dụ, làm sao bạn biết một partition có phải là partition nóng hay không, đúng không?
Are you, are you just better off using the extra memory to keep these things, keep more of these pages in memory, rather than doing this hash table thing?
Liệu dùng phần bộ nhớ dư để giữ những thứ này có tốt hơn không, giữ nhiều page hơn trong bộ nhớ, thay vì làm cái việc bảng băm này?
So Postgres does this, a bunch of different commercial systems do this.
Postgres làm điều này, nhiều hệ thống thương mại khác nhau cũng làm vậy.
The language is confusing because sometimes they'll call this the hybrid join, so the hybrid hash join, so finding out who actually does this is not, not always clear.
Cách gọi tên khá gây nhầm lẫn vì đôi khi họ gọi nó là hybrid join, tức là hybrid hash join, nên việc tìm ra hệ thống nào thực sự làm điều này không phải lúc nào cũng rõ ràng.
And like I said, sometimes you're just better using the purple pages for the partitions you're building, rather than, you know, specializing one of them to be the hot one.
Và như tôi đã nói, đôi khi bạn dùng các page màu tím sẽ tốt hơn cho các partition bạn đang xây dựng, thay vì chuyên biệt hóa một trong số chúng thành partition nóng.
All right, so to finish up, for our hash joins, the probe table can be sort of really any size, but in general we want it to fit in memory, because again we don't want it to do much random IO on disk, that's gonna be the death to us, right?
Được rồi, để kết thúc, với các hash join, bảng probe có thể có kích thước thực sự bất kỳ, nhưng nói chung ta muốn nó vừa trong bộ nhớ, vì một lần nữa, ta không muốn phải thực hiện nhiều IO ngẫu nhiên trên đĩa, điều đó sẽ là dấu chấm hết cho chúng ta, đúng không?
If everything fits in memory, then the probe can be really fast, you just sort of scan it through once and don't do any partitioning.
Nếu mọi thứ vừa trong bộ nhớ thì probe có thể rất nhanh, bạn chỉ cần quét qua một lần và không cần phân chia partition.
If you don't know what the size of the table could be, then you maybe want to use the extendible hashing, the linear hash table that we talked about a couple classes ago.
Nếu bạn không biết kích thước của bảng có thể là bao nhiêu, thì có lẽ bạn nên dùng extendible hashing, hoặc bảng băm tuyến tính (linear hash table) mà chúng ta đã nói đến cách đây vài buổi.
Most systems don't do that, because again those data structures are less efficient, because there's more machinery to them than, like, a linear probe hash table.
Hầu hết các hệ thống không làm vậy, vì một lần nữa, những cấu trúc dữ liệu đó kém hiệu quả hơn, vì chúng có nhiều cơ chế phức tạp hơn so với bảng băm linear probe.
So when we talk about query optimization, as I said a couple times already, that, like, they're gonna try to estimate how much data or how many tuples you're gonna have to put into your hash table.
Vì vậy, khi nói về tối ưu hóa truy vấn, như tôi đã nói vài lần rồi, hệ thống sẽ cố ước lượng xem có bao nhiêu dữ liệu hay bao nhiêu tuple bạn sẽ phải đưa vào bảng băm.
So that you can sort of size it correctly and not have to, you know, spill or resize it later on. But getting that correct is gonna be super hard to do.
Để có thể định kích thước cho đúng và không phải, bạn biết đấy, tràn ra đĩa hay thay đổi kích thước sau này. Nhưng làm cho đúng điều đó thì cực kỳ khó.
It's hard enough to do it for base tables themselves if I'm reading the tables, but then try to do estimates of the size of data after I do multiple joins, everyone gets that wrong, and horribly wrong.
Ngay cả với bản thân các bảng gốc, khi tôi đọc các bảng đó, cũng đã đủ khó, vậy mà còn phải ước lượng kích thước dữ liệu sau khi thực hiện nhiều phép join, ai cũng ước lượng sai, và sai rất nặng.
So, you know, it's the only way to handle it is to be very, you over-allocate the memory for your hash table to avoid that problem.
Vì thế, cách duy nhất để xử lý là rất, cấp phát dư bộ nhớ cho bảng băm để tránh vấn đề đó.
Of course, that makes you less efficient because now you're using memory, that you're allocating memory you may not actually need for your hash join, could be used for other things.
Tất nhiên, điều đó làm bạn kém hiệu quả hơn vì giờ bạn đang dùng bộ nhớ, bạn cấp phát bộ nhớ mà có thể thực ra không cần cho hash join, mà lẽ ra có thể dùng cho việc khác.
But again, you're just trying to avoid having to spill to disk. Alright, so here's the summary slide of the different algorithms we talked about.
Nhưng một lần nữa, bạn chỉ đang cố tránh phải tràn ra đĩa. Được rồi, đây là slide tóm tắt các thuật toán khác nhau mà chúng ta đã nói.
Again, in general, the hash join is gonna be preferable, right, if you don't already have an index and you don't think the data you're trying to join will fit in disk.
Một lần nữa, nói chung hash join sẽ là lựa chọn tốt hơn, nếu bạn chưa có sẵn chỉ mục và bạn nghĩ dữ liệu cần join sẽ không vừa trong bộ nhớ.
Yes?
Bạn hỏi à?
Yes, yes, so the question is, I mentioned a different,
Vâng, vâng, vậy câu hỏi là, tôi đã nhắc đến nhiều
a bunch of different scenarios where one join algorithm will be better than another, and so the first question is, do database systems implement different join algorithms? Yes.
tình huống khác nhau mà trong đó thuật toán join này tốt hơn thuật toán join khác, và câu hỏi đầu tiên là, các hệ quản trị cơ sở dữ liệu có cài đặt nhiều thuật toán join khác nhau không? Có.
Your database systems then try to figure out which of these join algorithms they should use at run time when your query shows up.
Hệ quản trị cơ sở dữ liệu sau đó sẽ cố xác định nên dùng thuật toán join nào trong số này tại thời điểm chạy, khi truy vấn của bạn đến.
Yes, so that'll be query optimization, that'll be after the fall break, roughly. The formulas they're gonna use to try to figure this out look like this.
Vâng, phần đó thuộc về tối ưu hóa truy vấn, sẽ học sau kỳ nghỉ thu, khoảng vậy. Các công thức mà chúng dùng để xác định điều này trông như thế này.
Right, now the question is, of this menu here, which ones are gonna have, the good ones have all of them.
Được rồi, bây giờ câu hỏi là, trong danh sách này, hệ nào có cái nào, những hệ tốt thì có tất cả.
Postgres has all of these, right? Oracle has all of these, DB2, DuckDB, they have, you have to have all.
Postgres có tất cả những cái này, đúng không? Oracle có tất cả, DB2, DuckDB cũng vậy, bạn phải có đủ.
MySQL didn't have hash joins until like oh 30 25 years later, like, they didn't add it until 2019. I don't think they have the... I don't have merge joins still, right?
MySQL không có hash join cho đến khoảng, ồ, 30 25 năm sau, họ mãi đến năm 2019 mới thêm vào. Tôi nghĩ họ vẫn chưa có... tôi nghĩ vẫn chưa có merge join, đúng không?
But that's okay, because they're focusing on, like, not analytical workloads. It's an OLTP system, right? So I was just trying to say, like, the...
Nhưng không sao, vì họ tập trung vào các tải công việc không phải phân tích. Đó là một hệ thống OLTP mà.
if you're building databases from scratch, when you have to implement your join, the first thing to implement is basically block nested loop join, because it's the easiest thing to do.
Tôi chỉ muốn nói rằng, nếu bạn xây dựng cơ sở dữ liệu từ đầu, khi phải cài đặt phép join, thứ đầu tiên cần cài đặt về cơ bản là block nested loop join, vì đó là cái dễ làm nhất.
And then after that, you're probably gonna want to implement the hash join, because it's gonna be way more efficient.
Và sau đó, có lẽ bạn sẽ muốn cài đặt hash join, vì nó sẽ hiệu quả hơn rất nhiều.
And there's a bunch of different optimizations and tweaks you can do for all these, like, there's a bunch of variations of these things.
Và có rất nhiều cách tối ưu hóa khác nhau và các tinh chỉnh mà bạn có thể áp dụng cho tất cả những thứ này, tức là có rất nhiều biến thể của chúng.
You can have different hash tables, you know, based on the data you're gonna join together. Like, Clickhouse has 20 hash table implementations.
Bạn có thể dùng các bảng băm khác nhau, bạn biết đấy, tùy theo dữ liệu mà bạn sẽ join với nhau. Ví dụ, Clickhouse có tới 20 cách cài đặt bảng băm.
Like, there's, within these general categories of algorithms, there's a bunch of different optimizations you can do, and that's what that's gonna be what distinguishes the enterprise expensive systems from, like, you know, the open source ones.
Tức là, bên trong những nhóm thuật toán tổng quát này, có rất nhiều cách tối ưu hóa khác nhau mà bạn có thể làm, và đó chính là điều sẽ phân biệt các hệ thống doanh nghiệp đắt tiền với các hệ thống mã nguồn mở.
Now with that said, DuckDB and Postgres have a lot of these things that are pretty good. DuckDB is probably pretty state-of-the-art, right?
Tuy nhiên, DuckDB và Postgres có khá nhiều thứ trong số này và chúng khá tốt. DuckDB có lẽ khá là hiện đại nhất, đúng không?
But the challenge is also gonna be in the query optimizer to figure out which of these ones you should use.
Nhưng thách thức còn nằm ở bộ tối ưu hóa truy vấn, để xác định nên dùng cái nào trong số này.
And in practice, again, as I said, the estimations are always gonna be really bad, so the hash join is usually the fallback.
Và trong thực tế, như tôi đã nói, các ước lượng luôn luôn rất tệ, nên hash join thường là phương án dự phòng.
Yes? The question is, what's the C index loop join? That's the constant cost of probing the index. Undefined, because it depends on what the index is and what the data looks like, right?
Vâng? Câu hỏi là C của index loop join là gì? Đó là chi phí hằng số của việc dò tìm trong chỉ mục. Chưa xác định, vì nó phụ thuộc vào chỉ mục là gì và dữ liệu trông như thế nào, đúng không?
It also depends on, like, what the join is. If it's equi-join, you know, in the case of B+tree, it's log n, go to the bottom.
Nó cũng phụ thuộc vào phép join là gì. Nếu là equi-join, trong trường hợp B+tree thì là log n, đi xuống tận đáy.
But if it's, like, they were asking, well, actually, if the key is not unique in that index, I may Traverse the bottom and then scan along leaf nodes.
Nhưng nếu, như bạn ấy hỏi, thực ra, nếu khóa không là duy nhất trong chỉ mục đó, thì tôi có thể duyệt xuống đáy rồi quét dọc theo các nút lá.
How many do I have to scan? Well, it depends on what the data is and what the query is, so that we just say C.
Tôi phải quét bao nhiêu nút? Thì còn tùy vào dữ liệu và truy vấn là gì, nên chúng ta chỉ gọi là C.
But when we talk about query optimization, it'll know, at that point you'll know what the query is, you know what you wanna do, you know what the data roughly looks like, you know what data structure you're hitting up.
Nhưng khi nói về tối ưu hóa truy vấn, nó sẽ biết, lúc đó bạn sẽ biết truy vấn là gì, bạn biết mình muốn làm gì, biết dữ liệu đại khái như thế nào, biết mình đang truy cập cấu trúc dữ liệu nào.
So at query optimization time, we take a SQL query and convert it to the actual plan you execute. That's when you fill in C.
Vì vậy, vào thời điểm tối ưu hóa truy vấn, chúng ta lấy một truy vấn SQL và chuyển nó thành kế hoạch thực thi thực sự. Đó là lúc bạn điền giá trị cho C.
Alright, again, so the main takeaway from right here should be hashing is almost always preferable to sorting, unless the data needs to be sorted as part of the output, then you can just piggyback off that.
Được rồi, một lần nữa, điều cần rút ra chính ở đây là băm hầu như luôn được ưu tiên hơn sắp xếp, trừ khi dữ liệu cần được sắp xếp như một phần của đầu ra, thì khi đó bạn có thể tận dụng luôn.
Even then, in some cases, sorting, doing the hash join then sorting it still might be even better. Again, depends on the hardware, depends on the query, depends on the data.
Ngay cả như vậy, trong một số trường hợp, làm hash join rồi mới sắp xếp có thể vẫn tốt hơn. Một lần nữa, nó phụ thuộc vào phần cứng, truy vấn và dữ liệu.
So, and related to his question, the good systems, good in quotes, will have pretty much all of these techniques and a bunch of other optimizations, but these are the general three algorithms you can do.
Và liên quan đến câu hỏi của bạn ấy, các hệ thống tốt, tốt trong ngoặc kép, sẽ có hầu hết tất cả các kỹ thuật này và nhiều tối ưu hóa khác, nhưng đây là ba thuật toán tổng quát mà bạn có thể dùng.
You can either have nested for loops, hash things or sort things. There isn't anything else. Okay, all right. What's next class?
Bạn có thể dùng các vòng lặp for lồng nhau, băm dữ liệu hoặc sắp xếp dữ liệu. Không còn gì khác nữa. Được rồi. Buổi học tới là gì nhỉ?
Yeah, midterm. Okay, so again, make sure you have your notes, your CMU ID. Don't do any weird things like one year one kid brought his wet laundry. Don't do that.
Đúng rồi, thi giữa kỳ. Vậy nên, một lần nữa, hãy nhớ mang theo ghi chú và thẻ CMU ID của các em. Đừng làm những chuyện kỳ quặc, như có năm nọ một bạn mang cả đồ giặt còn ướt đến. Đừng làm vậy nhé.
Like, I won't be here, but my PhD students will be managing things for us. Okay, all right, then hit it.
Thầy sẽ không có mặt, nhưng các nghiên cứu sinh tiến sĩ của thầy sẽ phụ trách mọi việc cho chúng ta. Được rồi, vậy thì chúc các em làm bài tốt.
Yes, yes, yes, yes, yes, yes, yes, yes, yes, yes, yes, yes, yes,
Vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng,
yes, yes, yes, yes, yes, yes, yes, yes, yes, yes, yes, yes.
vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng, vâng.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.