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'm going to give you a cap. Almost forgot to record. You doing well? How's your money situation? It's okay?
Tôi sẽ đưa cho bạn một chiếc mũ lưỡi trai. Suýt nữa thì quên ghi hình. Bạn khỏe không? Tình hình tài chính của bạn thế nào? Ổn chứ?
Yeah, it's getting better. Okay, good to hear. Again, he's like, I need you to make money as a DJ.
Vâng, đang khá lên rồi. Được, nghe vậy thì tốt. Lại nữa, anh ấy bảo: tôi cần cậu kiếm tiền bằng nghề DJ.
I'm like, all right, we'll pay you to do this, but anything else you want to do, I can't do that with you.
Tôi bảo: được rồi, chúng tôi sẽ trả tiền để cậu làm việc này, nhưng bất cứ việc gì khác cậu muốn làm thì tôi không thể làm cùng cậu được.
Okay, I got it. Cheers. All right, for you guys, a lot to cover today. So again, reminder for a bunch of things coming up for you guys in the class.
Được rồi, tôi hiểu. Cạn ly. Nào, với các bạn, hôm nay có rất nhiều nội dung cần đề cập. Trước hết, nhắc lại một loạt việc sắp tới của các bạn trong lớp này.
In homework three, we do this Sunday. Again, the idea is that you submit it on Sunday and then we will give you back the solutions on Monday.
Bài tập về nhà 3 thì hạn nộp là Chủ nhật này. Ý tưởng là các bạn nộp bài vào Chủ nhật và thứ Hai chúng tôi sẽ trả lại lời giải cho các bạn.
Because one week from now, in this room at the same time, we will have the midterm exam. I won't be here. My number one PhD students will be here to practice the exam.
Vì một tuần nữa kể từ bây giờ, tại phòng này, vào cùng giờ, chúng ta sẽ có bài thi giữa kỳ. Tôi sẽ không có mặt. Nghiên cứu sinh tiến sĩ số một của tôi sẽ có mặt để cùng các bạn luyện đề.
The main thing to know is that there's a study guide available online with a practice exam that's posted on Piazza.
Điều chính cần biết là có một bản hướng dẫn ôn tập trực tuyến cùng với một đề thi thử được đăng trên Piazza.
Make sure if you show up here, bring your senior ID so we keep track of who is who when you turn in your exam.
Nếu các bạn đến đây thì nhớ mang theo thẻ sinh viên năm cuối để chúng tôi biết ai là ai khi các bạn nộp bài thi.
And then for the notes, it's a single sheet of paper, double-sided, eight and a half by 11. It won't then be handwritten.
Còn về phần ghi chú, được dùng một tờ giấy, hai mặt, cỡ 8,5 x 11 inch. Và nó phải được viết tay.
So you're just not like taking slides and shrinking them down to fit on a single paper. And if you want to write on your tablet and print it out, that's fine too.
Nghĩa là các bạn không được lấy các slide rồi thu nhỏ lại cho vừa một tờ giấy. Còn nếu bạn muốn viết trên máy tính bảng rồi in ra thì cũng được.
Okay, any questions about the exam?
Được rồi, có câu hỏi nào về bài thi không?
Again, if things are unclear, please post on Piazza. And then project two went out on Monday this week, and that'll be due after we come back from fall break.
Nếu có điều gì chưa rõ, hãy đăng lên Piazza. Và dự án 2 đã được công bố vào thứ Hai tuần này, hạn nộp sẽ sau khi chúng ta quay lại từ kỳ nghỉ thu.
Okay? All right, there was actually one big announcement three hours ago in the world of databases. There was an acquisition. Anybody hear what it is, know what it is?
Được chứ? Nào, thực ra có một thông báo lớn cách đây ba giờ trong thế giới cơ sở dữ liệu. Có một thương vụ mua lại. Có ai nghe là gì không, có biết không?
Databricks bought another company. So they bought Mooncake. They're actually going to give a talk with us in, like, I don't know, three or four weeks after fall break.
Databricks đã mua một công ty khác. Họ mua Mooncake. Thực ra họ sắp có một buổi nói chuyện với chúng ta, khoảng tôi không rõ, ba hay bốn tuần sau kỳ nghỉ thu.
So they were Postgres with DuckDB inside of it. So you run your queries, and you have an analytical query. It can then call down to DuckDB and then read and write to Iceberg.
Họ là Postgres có DuckDB bên trong. Bạn chạy các truy vấn của mình, và bạn có một truy vấn phân tích. Nó có thể gọi xuống DuckDB rồi đọc và ghi vào Iceberg.
Again, we had them give a talk, whatever, last week. Kept saying how important Iceberg was. Again, Databricks bought the Iceberg people for $2 billion, and now they bought Mooncake for, there we go.
Chúng ta cũng đã mời họ nói chuyện, tuần trước thì phải. Họ cứ nói Iceberg quan trọng đến mức nào. Databricks đã mua những người làm Iceberg với giá 2 tỷ đô la, và giờ họ mua Mooncake với giá, đây rồi.
And then there's texting, whatever. That's a weird flex. All right. Yeah, so they have a ton of money. Everyone's waiting for them to go to IPO, and they're hiring a ton.
Còn có tin nhắn gì đó nữa, kệ đi. Khoe khoang kỳ quặc thật. Được rồi. Vâng, họ có cả đống tiền. Ai cũng đang chờ họ IPO, và họ đang tuyển dụng rất nhiều.
All right, so where we're at now in the course is, again, from this diagram I showed earlier in the semester, where we said we could sort of start at the bottom of the disk layer and work our way up.
Nào, vậy hiện giờ chúng ta đang ở đâu trong khóa học, lại là từ sơ đồ tôi đã cho xem hồi đầu học kỳ, nơi chúng ta nói rằng có thể bắt đầu từ dưới cùng, tầng đĩa, rồi đi dần lên trên.
Now we're up here at the operator execution. So we know how to build a disk manager, a buffer pool manager to read and write pages from disk into memory.
Giờ chúng ta đang ở trên này, phần thực thi toán tử. Vậy là chúng ta đã biết cách xây dựng một disk manager, một buffer pool manager để đọc và ghi các trang từ đĩa vào bộ nhớ.
We know now how to build indexes and other data structures on top of our buffer pool to allow us to access the data.
Giờ chúng ta cũng biết cách xây dựng các chỉ mục và những cấu trúc dữ liệu khác trên nền buffer pool để truy cập dữ liệu.
So now it's time to start talking about, okay, let's run some queries.
Vì vậy đã đến lúc bắt đầu nói về việc, được rồi, hãy chạy một số truy vấn.
So for the next four lectures of this class, which will be covered on the midterm, and then next class, which is not covered in the midterm, and then a week after the fall break, we'll start talking about how you're actually going to take queries and execute them and produce results, as you would see when you run DuckDB, SQLite, MySQL, whatever you want in your local terminal.
Trong bốn bài giảng tiếp theo của lớp này, những bài sẽ nằm trong bài thi giữa kỳ, rồi đến buổi học sau đó, buổi không nằm trong bài thi giữa kỳ, và một tuần sau kỳ nghỉ thu, chúng ta sẽ bắt đầu nói về việc thực sự lấy các truy vấn như thế nào rồi thực thi chúng và tạo ra kết quả, như bạn thấy khi chạy DuckDB, SQLite, MySQL, tùy bạn chọn, trong terminal trên máy của bạn.
How do you get back to those results that people are asking for? So today's class, we're going to be focusing on sorting algorithms.
Làm thế nào để có được những kết quả mà người ta yêu cầu? Buổi hôm nay, chúng ta sẽ tập trung vào các thuật toán sắp xếp.
Next class will be about joins, Sort of the two, again, two sort of fundamental things you need to have in your database system.
Buổi sau sẽ nói về phép nối (join). Đây, một lần nữa, là hai thứ cơ bản mà hệ cơ sở dữ liệu nào cũng cần có.
And then afterwards, we'll talk about how do you actually then build the database system to take these different algorithms that we can support and read on the data we stored on disk or bring to the buffer pool and produce results.
Sau đó, chúng ta sẽ nói về việc làm thế nào xây dựng hệ cơ sở dữ liệu để dùng các thuật toán khác nhau này, những thuật toán mà ta có thể hỗ trợ và đọc dữ liệu đã lưu trên đĩa hoặc đưa vào buffer pool rồi tạo ra kết quả.
Okay? So the first thing to understand about where we're going forward next is what these query plans are actually going to look like.
Được chứ? Điều đầu tiên cần hiểu về hướng đi tiếp theo của chúng ta là các kế hoạch truy vấn (query plan) thực sự trông như thế nào.
So now we're going to start bringing back some of the relational algebra stuff we talked about in the beginning, but the high-level idea of a query plan is that it's just going to be this directed data structure, usually a tree.
Giờ chúng ta sẽ bắt đầu nhắc lại một số nội dung về đại số quan hệ mà ta đã nói ở phần đầu, nhưng ý tưởng tổng quát về một kế hoạch truy vấn là nó chỉ là một cấu trúc dữ liệu có hướng, thường là một cây.
It's better off to be a DAG, but not all systems do that. We'll cover why that matters later on.
Tốt hơn là dùng DAG, nhưng không phải hệ thống nào cũng làm vậy. Chúng ta sẽ nói về lý do điều đó quan trọng sau.
But it's basically some tree-like data structure here where you have, on the leaf nodes, all the tables I want to access, right?
Nhưng về cơ bản đó là một cấu trúc dữ liệu dạng cây mà ở các nút lá, có tất cả các bảng tôi muốn truy cập, đúng không?
Or the data that we're storing in some materialized form as part of a table or a file, whatever. That's all at the bottom.
Hoặc dữ liệu mà chúng ta lưu ở dạng vật chất hóa như một phần của bảng hay một tệp, gì cũng được. Tất cả đều nằm ở dưới cùng.
And then essentially, they're going to be feeding data up into these operators, like a filter or a join or a projection or whatever.
Sau đó, về cơ bản, chúng sẽ đưa dữ liệu lên các toán tử này, như bộ lọc, phép nối, phép chiếu hay gì đó.
And each operator is going to do some computation on it based on what the operator is defined to do.
Và mỗi toán tử sẽ thực hiện một phép tính trên dữ liệu đó, dựa theo việc toán tử được định nghĩa để làm gì.
And then at the end, we produce a final result that we then send back to the client. And that's the result of your query.
Rồi cuối cùng, chúng ta tạo ra kết quả cuối cùng và gửi lại cho client. Và đó là kết quả truy vấn của bạn.
So this is obviously PowerPoint, and there's a bunch of boxes going up on the lines, so it doesn't really mean anything.
Đây rõ ràng là PowerPoint, với một loạt hộp và đường nối đi lên, nên thực ra nó chẳng có ý nghĩa gì cả.
But there's a bunch of low-level details or design decisions we can have in our system for what these boxes actually represent. Are we sending single tuples? Are we sending columns?
Nhưng có rất nhiều chi tiết cấp thấp hay các quyết định thiết kế mà chúng ta có thể đưa ra trong hệ thống về việc những chiếc hộp này thực sự biểu diễn cái gì. Chúng ta gửi từng tuple hay gửi từng cột?
Are we sending the entire result? Are we pushing the data from the bottom to the top? Are we pulling it from the top to the bottom?
Chúng ta có gửi toàn bộ kết quả không? Chúng ta đẩy dữ liệu từ dưới lên trên? Hay kéo nó từ trên xuống dưới?
There's a bunch of those things we'll cover after fall break, right?
Có rất nhiều vấn đề như vậy mà chúng ta sẽ học sau kỳ nghỉ thu, được chứ?
But the high-level idea, what you need to understand, is that there's these sort of fundamental steps in our query plan that are going to be represented by these relational operators that are going to produce some portion of the final result that we need for our query.
Nhưng ý tưởng ở mức cao mà các em cần hiểu là có những bước cơ bản như thế này trong kế hoạch truy vấn được biểu diễn bằng các toán tử quan hệ này, và chúng sẽ tạo ra một phần của kết quả cuối cùng mà truy vấn của chúng ta cần.
And then once we reach the root node, that's what gets sent back to the client. Okay?
Rồi khi đến nút gốc, đó là thứ được gửi về cho client. Được chứ?
So now, also hearkening back to the beginning of the semester, when we start talking about the algorithms we're going to implement to execute these queries, we have to remind ourselves that we're focusing on what are called disk-oriented database systems, where the system has to assume that the table you're trying to access, or trying to query against in these query plans,
Bây giờ, cũng nhắc lại từ đầu học kỳ, khi chúng ta bắt đầu nói về các thuật toán mà chúng ta sẽ cài đặt để thực thi các truy vấn này, chúng ta phải nhớ rằng mình đang tập trung vào cái gọi là hệ quản trị cơ sở dữ liệu hướng đĩa, trong đó hệ thống phải giả định rằng bảng mà em đang cố truy cập, hoặc đang truy vấn trong các kế hoạch truy vấn này,
may not fit entirely in main memory. And furthermore, the thing to be aware about is that the intermediate results in between these operators in our query plan, that may not fit in memory either.
có thể không vừa hoàn toàn trong bộ nhớ chính. Hơn nữa, điều cần lưu ý là các kết quả trung gian giữa các toán tử trong kế hoạch truy vấn của chúng ta cũng có thể không vừa trong bộ nhớ.
So we may have to write those things out the disk in order to give the illusion that we can fit everything in memory.
Vì vậy chúng ta có thể phải ghi chúng ra đĩa để tạo ảo giác rằng mọi thứ đều vừa trong bộ nhớ.
And so this means that if there are times where we think we're going to have to write them out the disk, we're actually going to choose algorithms that may not be asymptotically as efficient as other algorithms, but they're going to maximize the amount of sequential I/O that we have to do.
Điều này có nghĩa là nếu có lúc nào đó chúng ta nghĩ mình sẽ phải ghi chúng ra đĩa, thì chúng ta sẽ chọn những thuật toán có thể không hiệu quả tiệm cận bằng các thuật toán khác, nhưng tối đa hóa lượng I/O tuần tự mà chúng ta phải thực hiện.
And therefore, that's how we're going to get better performance. And in particular, when we talk about sorting today, the fastest algorithms are going to be like QuickSort or PowerSort, whatever your favorite one is.
Và do đó, đó là cách chúng ta đạt hiệu năng tốt hơn. Cụ thể, khi nói về sắp xếp hôm nay, các thuật toán nhanh nhất sẽ là QuickSort hoặc PowerSort, tùy em thích thuật toán nào nhất.
But those are great when everything's in memory.
Chúng rất tuyệt khi mọi thứ nằm trong bộ nhớ.
But if you have to go read and write data from disk, because you're running out of memory in your buffer pool and you've got to spill the disk, then those algorithms are actually going to be not great.
Nhưng nếu em phải đọc và ghi dữ liệu từ đĩa, vì bộ nhớ trong buffer pool của em sắp hết và em phải ghi tràn ra đĩa, thì những thuật toán đó thực ra sẽ không tốt.
And there'll be better ones that we'll talk about today. Okay?
Và sẽ có những thuật toán tốt hơn mà hôm nay chúng ta sẽ nói đến. Được chứ?
Again, it's another example why we don't want to rely on the operating system to manage memory for us, because we can make all these decisions about what we actually want to stage, keep in memory and write out, if we want to prefetch things.
Một lần nữa, đây là một ví dụ cho thấy vì sao chúng ta không muốn dựa vào hệ điều hành để quản lý bộ nhớ thay mình, vì chúng ta có thể tự quyết định cái gì cần đưa vào, giữ lại trong bộ nhớ và ghi ra, hay có muốn tải trước thứ gì không.
The OS doesn't know anything about what this query plan is actually doing. So it's not going to make good decisions.
Hệ điều hành không biết gì về việc kế hoạch truy vấn này thực sự đang làm gì. Nên nó sẽ không đưa ra quyết định tốt.
Whereas we know exactly what this query plan is because we have to execute it.
Còn chúng ta biết chính xác kế hoạch truy vấn này là gì vì chúng ta phải thực thi nó.
So we know that if we're running down here, what the other stages are going to be, and we can make decisions about where we're going to put data and when we're going to read and write to disk.
Nên chúng ta biết rằng nếu mình đang chạy ở dưới này, các giai đoạn khác sẽ là gì, và chúng ta có thể quyết định sẽ đặt dữ liệu ở đâu và khi nào sẽ đọc và ghi xuống đĩa.
Okay?
Được chứ?
So it should be kind of obvious why we want sorting in our database system, right? But it's good to understand some key goals we'll have, why we're going to want to do this.
Vậy nên khá rõ vì sao chúng ta cần sắp xếp trong hệ quản trị cơ sở dữ liệu, đúng không? Nhưng cũng nên hiểu một số mục tiêu chính, tức là vì sao chúng ta lại muốn làm điều này.
Obviously, one big obvious thing is that the relational model is unsorted. Right? We said that it was based on set algebra. In the case of SQL, it's based on bag algebra.
Một điều hiển nhiên là mô hình quan hệ không có thứ tự. Đúng không? Chúng ta đã nói nó dựa trên đại số tập hợp. Với SQL, nó dựa trên đại số túi (bag algebra).
There could be duplicates, but everything's unsorted. And so many times in applications, people are going to want data sorted.
Có thể có các bản ghi trùng lặp, nhưng mọi thứ đều không có thứ tự. Và nhiều khi trong các ứng dụng, người ta sẽ muốn dữ liệu được sắp xếp.
And the way you can ask for this in SQL is through an ORDER BY clause. Right? So they can say, hey, I want this data in this table.
Cách để yêu cầu điều này trong SQL là dùng mệnh đề ORDER BY. Đúng không?
Sort it based on some arbitrary keys, either ascending or descending order, other characteristics, other parameters we could pass in. And so therefore, we need to support that.
Họ có thể nói: tôi muốn dữ liệu trong bảng này, sắp xếp theo một số khóa tùy ý, theo thứ tự tăng dần hoặc giảm dần, cùng các đặc tính khác, các tham số khác mà ta có thể truyền vào. Do đó, chúng ta cần hỗ trợ điều đó.
But one of the things we'll see in today's class as well is that, even if the query is not asking for the data to be sorted in a certain way, we may end up still actually wanting to sort it because, therefore, we can choose different algorithms in our query plan that will be more efficient because we know the data is sorted versus being unsorted.
Nhưng một điều nữa chúng ta sẽ thấy trong buổi học hôm nay là, ngay cả khi truy vấn không yêu cầu dữ liệu phải được sắp xếp theo một cách nào đó, chúng ta vẫn có thể muốn sắp xếp nó, bởi vì khi đó chúng ta có thể chọn các thuật toán khác nhau trong kế hoạch truy vấn hiệu quả hơn, vì chúng ta biết rằng dữ liệu đã được sắp xếp so với khi chưa sắp xếp.
Right?
Đúng không?
The most obvious thing will be, and we'll see this later on when we talk about aggregations, if I sort my data, then it's really easy for me to then figure out to remove duplicates when I want to have a distinct clause, because I just sort of scan through this sort of data.
Ví dụ rõ nhất sẽ là, và chúng ta sẽ thấy sau này khi nói về phép gộp (aggregation), nếu tôi sắp xếp dữ liệu, thì tôi rất dễ loại bỏ các bản ghi trùng lặp khi cần dùng mệnh đề DISTINCT, vì tôi chỉ cần quét qua dữ liệu đã sắp xếp đó.
And if I see that a key is the same as the last one I just looked at, then I can just throw it away.
Và nếu tôi thấy một khóa giống với khóa vừa xem ngay trước đó, thì tôi chỉ cần bỏ nó đi.
In other cases, if you're doing a join, there's join algorithms we'll see next class where you actually sort the data first, and then you merge it together.
Trong những trường hợp khác, nếu bạn thực hiện phép nối (join), có những thuật toán nối mà chúng ta sẽ thấy ở buổi sau, trong đó bạn sắp xếp dữ liệu trước, rồi sau đó trộn chúng lại với nhau.
And that's really efficient to do as well.
Và cách đó cũng rất hiệu quả.
In some systems, like in SQL Server, they will recognize that, hey, it'd be really nice if I had a B+tree on this table that you don't have.
Trong một số hệ thống, như SQL Server, chúng nhận ra rằng, sẽ rất tốt nếu có một B+tree trên bảng này mà bạn chưa có.
So they'll sort the data first, then build a B+tree on top of that sort of data, do whatever it is they need to do in the query, and then immediately throw it away once the query is done.
Vì vậy, chúng sắp xếp dữ liệu trước, rồi xây dựng một B+tree trên dữ liệu đã sắp xếp đó, làm bất cứ điều gì cần làm trong truy vấn, rồi bỏ nó đi ngay khi truy vấn kết thúc.
They call it a spooling index.
Họ gọi đó là spooling index.
So again, in that example, it's much more efficient to build a B+tree if you sort the data first, because then you just go along the leaf nodes and build a scaffolding up above rather than doing things piecemeal or incrementally.
Vậy trong ví dụ đó, xây dựng B+tree hiệu quả hơn nhiều nếu bạn sắp xếp dữ liệu trước, vì khi đó bạn chỉ cần đi dọc theo các nút lá và dựng khung các tầng bên trên, thay vì làm từng phần hoặc chèn dần từng bước.
Again, so in general, sorting is going to be really helpful for a bunch of different things, and obviously we want this to be as efficient as possible.
Vậy nói chung, sắp xếp sẽ rất hữu ích cho nhiều việc khác nhau, và rõ ràng là ta muốn việc này hiệu quả nhất có thể.
So if the data, either the tables at rest or our intermediate results, if that can fit entirely in main memory, then we don't need anything we're going to talk about in this class today, because then you just pick whatever your favorite sorting algorithm is you learned in CS101.
Vì vậy, nếu dữ liệu, dù là các bảng lưu trữ tĩnh hay các kết quả trung gian, có thể nằm gọn hoàn toàn trong bộ nhớ chính, thì ta không cần bất cứ thứ gì sẽ nói trong buổi học hôm nay, vì khi đó bạn chỉ cần chọn thuật toán sắp xếp yêu thích mà bạn đã học trong CS101.
Kids usually say QuickSort, and there's TimSort, PowerSort. Go read the Wikipedia page. There's a ton of different sorting algorithms. PickleSort, CycleSort, GnomeSort, CocktailShakerSort. There's a ton of these. They all have different properties.
Các bạn sinh viên thường nói QuickSort, ngoài ra còn có TimSort, PowerSort. Hãy đọc trang Wikipedia. Có vô số thuật toán sắp xếp khác nhau. PickleSort, CycleSort, GnomeSort, CocktailShakerSort. Có rất nhiều loại. Chúng đều có những tính chất khác nhau.
If everything's in memory, then just pick one of those, and you'll be fine. There is one optimization you can do.
Nếu mọi thứ đều nằm trong bộ nhớ, thì cứ chọn một cái, và sẽ ổn thôi. Có một tối ưu hóa mà bạn có thể làm.
If you know the data is mostly sorted, then there's algorithms that can take advantage of that and not do the full QuickSort setup. There's something called VergeSort that came out a few years ago.
Nếu bạn biết dữ liệu đã gần như được sắp xếp, thì có những thuật toán tận dụng được điều đó và không phải chạy đầy đủ QuickSort. Có một thuật toán tên là VergeSort ra đời cách đây vài năm.
There's a bunch of algorithms that have the ability to recognize whether the data is already sorted. If not, they bail out and fall back to QuickSort.
Có một số thuật toán có khả năng nhận biết dữ liệu đã được sắp xếp hay chưa. Nếu chưa, chúng thoát ra và quay về dùng QuickSort.
Otherwise, they then plow through and they can run things more efficiently, almost like an insert sort.
Nếu rồi, chúng chạy thẳng một mạch và xử lý hiệu quả hơn, gần giống như insert sort.
And there's a bunch of these visualization tools people like to make to show you how data moves around when you run one of these sort of algorithms.
Và có nhiều công cụ trực quan hóa mà mọi người hay làm để cho bạn thấy dữ liệu di chuyển thế nào khi chạy một trong các thuật toán sắp xếp này.
Again, if everything's in memory, no big deal. Pick your favorite one. TimSort is what Python uses. Actually, they got rid of TimSort recently, but now it's like PowerSort.
Một lần nữa, nếu mọi thứ nằm trong bộ nhớ thì không có gì to tát. Chọn cái bạn thích. Python dùng TimSort. Thực ra gần đây họ đã bỏ TimSort, giờ là PowerSort.
Postgres uses QuickSort. All these ones are pretty common. But again, it's when we can't fit everything in memory.
Postgres dùng QuickSort. Những thuật toán này đều khá phổ biến. Nhưng vấn đề là khi ta không thể chứa hết mọi thứ trong bộ nhớ.
And we would know this because we know how much memory we have in our buffer pool manager. Or typically, a query is allocated a certain amount of memory used for sorting or working memory.
Và ta sẽ biết điều này vì ta biết mình có bao nhiêu bộ nhớ trong buffer pool manager. Hoặc thông thường, một truy vấn được cấp một lượng bộ nhớ nhất định dùng cho sắp xếp hay làm bộ nhớ làm việc.
So we'd know that, hey, we have to sort one gigabyte of data, but we only have 800 megabytes of RAM or buffer space to use.
Vì vậy ta sẽ biết rằng, này, ta phải sắp xếp một gigabyte dữ liệu, nhưng chỉ có 800 megabyte RAM hay không gian buffer để dùng.
Then we got to fall back and use something else.
Khi đó ta phải chuyển sang dùng cách khác.
So the thing to understand what we're now going to be sorting is what are called runs. And so the input to these sorting algorithms would be these unsorted runs or semi-sorted runs.
Vậy điều cần hiểu về thứ ta sắp sửa sắp xếp là cái gọi là các run. Và đầu vào của các thuật toán sắp xếp này sẽ là các run chưa sắp xếp hoặc sắp xếp một phần.
And then you run your sorting algorithm. And then if it's in memory, you just run QuickSort on that. Then we'll see how to do this in multiple stages with external merge sort.
Sau đó bạn chạy thuật toán sắp xếp. Và nếu nằm trong bộ nhớ, bạn chỉ cần chạy QuickSort trên đó. Sau đó ta sẽ xem cách làm việc này qua nhiều giai đoạn với external merge sort.
But you end up producing an output. The output is just that input run sorted based on whatever the key you want to sort on.
Nhưng cuối cùng bạn tạo ra một đầu ra. Đầu ra chính là run đầu vào đó được sắp xếp theo khóa nào mà bạn muốn sắp xếp.
And so it isn't just going to be like in your algorithms class, where we have a list of numbers and you want to sort those.
Và nó sẽ không chỉ giống như trong môn thuật toán của bạn, nơi ta có một danh sách các số và muốn sắp xếp chúng.
Remember that we're talking about tuples in a database or in tables.
Hãy nhớ rằng ta đang nói về các tuple trong cơ sở dữ liệu hay trong các bảng.
So it's actually going to be a key-value pair, where the key is going to be whatever it is that I want to sort on, and the value is going to be either the actual tuple that the key belongs to, or a pointer to it, or a record ID to it.
Vì vậy nó thực ra sẽ là một cặp khóa-giá trị, trong đó khóa là thuộc tính mà tôi muốn sắp xếp theo, còn giá trị sẽ là chính tuple mà khóa đó thuộc về, hoặc là một con trỏ tới nó, hoặc một record ID của nó.
And we won't talk about this too much in this class. We'll see this more when we talk about joins and query processing later.
Chúng ta sẽ không nói quá nhiều về điều này trong lớp. Chúng ta sẽ thấy rõ hơn khi nói về join và xử lý truy vấn ở phần sau.
But the two choices of what the value is going to be can depend on what kind of system you're building.
Nhưng hai lựa chọn về việc giá trị sẽ là gì có thể phụ thuộc vào loại hệ thống mà bạn đang xây dựng.
Now you see why understanding what these different layers are is going to matter, because one is actually going to be better than another in different scenarios.
Bây giờ các bạn thấy vì sao việc hiểu các tầng khác nhau này lại quan trọng, vì trong các tình huống khác nhau, cách này sẽ tốt hơn cách kia.
So if I'm building a row store system, then I want to use typically what's called early materialization. Meaning the sorted runs are going to contain the key followed by the entire tuple.
Vậy nếu tôi xây dựng một hệ thống row store, thì thường tôi sẽ dùng cái gọi là early materialization. Nghĩa là các sorted run sẽ chứa khóa theo sau là toàn bộ tuple.
This is all the bytes for the tuple that I fetch from a page.
Đó là tất cả các byte của tuple mà tôi lấy từ một page.
And the reason why this makes sense in a row store is because when I go fetch the page for a tuple, I'm getting all the data that I need at the moment I go fetch that page.
Lý do cách này hợp lý trong row store là vì khi tôi đi lấy page chứa một tuple, tôi có được toàn bộ dữ liệu cần thiết ngay lúc lấy page đó.
So I don't want to have to go back and fetch more data later on. And I don't need to, if everything's all there.
Nên tôi không muốn phải quay lại lấy thêm dữ liệu về sau. Và tôi cũng không cần, nếu mọi thứ đã có đủ ở đó.
If you're building a column store, they often use what is called late materialization.
Nếu bạn xây dựng một column store, họ thường dùng cái gọi là late materialization.
Meaning instead of storing the actual tuple data, since I only have to bring in the pages I need if it's a column store, and not maybe the entire thing, Then I just keep track of the record ID, or the offset in the columns for the tuple, whatever it is that I'm sorting on.
Nghĩa là thay vì lưu dữ liệu thực của tuple, vì với column store tôi chỉ cần đưa vào những page cần thiết, chứ có thể không phải toàn bộ, nên tôi chỉ theo dõi record ID, hoặc offset trong các cột của tuple, tức là thứ mà tôi đang sắp xếp theo.
And then at some later point, if I need to go get the rest of the data, I just follow that record ID to get the thing that I need.
Rồi đến một lúc nào đó sau này, nếu cần lấy phần dữ liệu còn lại, tôi chỉ việc lần theo record ID đó để lấy thứ mình cần.
And the idea here is you don't want to pass around a bunch of data that you don't need if you're going to end up throwing away a bunch of columns in your query.
Ý tưởng ở đây là bạn không muốn truyền đi một đống dữ liệu mà bạn không cần, nếu cuối cùng bạn sẽ bỏ đi nhiều cột trong truy vấn của mình.
So I'm going to bring this up to say I'm not going to show you the value portion of all the data we're going to be sorting in this class.
Tôi nhắc đến điều này để nói rằng tôi sẽ không trình bày phần giá trị của toàn bộ dữ liệu mà chúng ta sắp xếp trong lớp này.
We'll see this later again when we talk about joins. But just understand it isn't just the keys. I also got to pass along extra data to know what the key belongs to.
Chúng ta sẽ gặp lại điều này khi nói về join. Nhưng hãy hiểu rằng không chỉ có các khóa. Tôi còn phải truyền kèm dữ liệu bổ sung để biết khóa đó thuộc về cái gì.
What is the question? What's the value of K? It's a key, an attribute.
Câu hỏi là gì? K có giá trị là gì? Nó là một khóa, một thuộc tính.
It's some subset of columns of a table that I'm sorting on. You would call it the sort. It's the same key you would build the index on columns, right?
Đó là một tập con các cột của bảng mà tôi sắp xếp theo. Bạn có thể gọi nó là khóa sắp xếp. Nó cũng là khóa mà bạn sẽ dùng để xây dựng chỉ mục trên các cột, đúng không?
It's the same thing.
Hoàn toàn giống nhau.
So it is a bit of a debate in data systems when you build OLAP systems, which one you want to actually use.
Trong các hệ thống dữ liệu, khi xây dựng hệ thống OLAP thì có một cuộc tranh luận, là nên thực sự dùng cách nào.
For row store, you almost always use early materialization because, again, you're already fetching the page. You get all the data. You might as well just copy it along.
Với row store, bạn hầu như luôn dùng early materialization vì, một lần nữa, bạn vốn đã lấy page rồi. Bạn có toàn bộ dữ liệu. Cứ sao chép theo luôn cho xong.
Whether or not to use late materialization depends on who you ask.
Có dùng late materialization hay không thì tùy bạn hỏi ai.
One of the early data systems that was a column store that did late materialization was Vertica.
Một trong những hệ thống dữ liệu đầu tiên là column store và dùng late materialization là Vertica.
But then they said that was a mistake and they got rid of it when you start reading from S3.
Nhưng sau đó họ nói rằng đó là một sai lầm và họ đã bỏ nó đi khi bắt đầu đọc dữ liệu từ S3.
ClickHouse put a blog article out three or four months ago where they said they added late materialization. So, again, we'll talk about this more later.
ClickHouse đã đăng một bài blog cách đây khoảng ba hoặc bốn tháng, trong đó họ nói rằng họ đã thêm late materialization. Vậy nên, một lần nữa, chúng ta sẽ nói kỹ hơn về điều này sau.
But this is very important when we talk about how we actually do query processing on column store systems.
Nhưng điều này rất quan trọng khi chúng ta nói về cách thực sự xử lý truy vấn trên các hệ thống column store.
All right, so today's class, we're going to talk about sort of the two main sorting algorithms you would see in a data system: top-N heap sort and external merge sort.
Được rồi, vậy buổi học hôm nay, chúng ta sẽ nói về hai thuật toán sắp xếp chính mà bạn sẽ gặp trong một hệ quản trị dữ liệu: top-N heap sort và external merge sort.
Then we'll talk about how we do aggregations with sorting.
Sau đó chúng ta sẽ nói về cách thực hiện phép tổng hợp bằng sắp xếp.
And then also give a preview of how to do aggregations using hash tables or hashing, because then that'll segue us into next class when we talk about joins, because the big debate can be whether I want to do a sort-merge join or a hash join.
Rồi cũng xem trước cách thực hiện phép tổng hợp bằng bảng băm, tức là hashing, vì điều đó sẽ dẫn chúng ta sang buổi sau khi nói về phép nối (join), bởi cuộc tranh luận lớn có thể là tôi muốn dùng sort-merge join hay hash join.
And then today we have a flash talk from the MotherDuck guys, which is one of the commercial incarnations of DuckDB.
Và hôm nay chúng ta có một bài nói chớp nhoáng từ các bạn ở MotherDuck, một trong những phiên bản thương mại của DuckDB.
And, again, you may be thinking, like, why do they spend all this time talking about sorting? Isn't that, like, from the 1960s in computer science? Like, Quicksort is, like, the '60s or '70s.
Và, một lần nữa, có thể các bạn đang nghĩ, tại sao họ lại dành nhiều thời gian nói về sắp xếp thế? Chẳng phải nó có từ những năm 1960 trong khoa học máy tính rồi sao? Quicksort là từ khoảng thập niên 60 hay 70.
Like, who cares about this all, like, you know, nowadays anyway? Well, this is still a hot topic in database systems because there's always ways to improve these sorting algorithms.
Vậy ai còn quan tâm đến chuyện này ngày nay chứ? Thực ra đây vẫn là một chủ đề nóng trong các hệ quản trị cơ sở dữ liệu vì luôn có cách để cải thiện các thuật toán sắp xếp này.
DuckDB people put out a blog article last week where they went back and rewrote their entire sort algorithm to improve performance based on a bunch of the techniques and things that we'll talk about today.
Nhóm DuckDB đã đăng một bài blog tuần trước, trong đó họ quay lại và viết lại toàn bộ thuật toán sắp xếp của mình để cải thiện hiệu năng dựa trên một loạt kỹ thuật mà hôm nay chúng ta sẽ nói đến.
Some of this is, like, low-level C++ stuff that's not really domain to the high-level topics.
Một phần trong đó là những chi tiết C++ cấp thấp, không thực sự thuộc các chủ đề cấp cao.
But, again, so I'm going to show you that, like, sorting isn't a solved problem in databases even though the topic is really, really old. Same thing when we talk about transactions.
Nhưng, một lần nữa, tôi sẽ cho các bạn thấy rằng sắp xếp không phải là bài toán đã được giải xong trong cơ sở dữ liệu, dù chủ đề này rất, rất cũ. Tương tự khi chúng ta nói về giao dịch.
Transactions go back to the 1970s, but it's an unsolved problem.
Giao dịch có từ thập niên 1970, nhưng đó vẫn là một bài toán chưa được giải quyết.
All right, so the first sorting algorithm we're talking about is top-N heap sort.
Được rồi, thuật toán sắp xếp đầu tiên chúng ta nói đến là top-N heap sort.
And this is a special case sorting algorithm where if you recognize that the data has to be sorted and you have a limit clause or you have a restriction on the number of tuples you want as part of the output, Then a shortcut is just to scan the data once and find the top-N entries that you need as part of your output and spit that out.
Đây là một thuật toán sắp xếp cho trường hợp đặc biệt, trong đó nếu bạn nhận ra dữ liệu cần được sắp xếp và bạn có mệnh đề limit hoặc có giới hạn về số tuple bạn muốn trong kết quả đầu ra, thì một lối tắt là chỉ cần quét dữ liệu một lần và tìm N mục đầu tiên cần cho kết quả đầu ra rồi trả chúng ra.
Right? So say I have a query like this. So let's start from the enroll table, order by the student ID ascending.
Đúng không? Giả sử tôi có một truy vấn như thế này. Vậy hãy bắt đầu từ bảng enroll, order by student ID theo thứ tự tăng dần.
And then now I have this extra parameter that I can put at the end where I say, I want the first four rows.
Và bây giờ tôi có thêm một tham số có thể đặt ở cuối, trong đó tôi nói rằng tôi muốn bốn dòng đầu tiên.
This is like a limit clause, but this is the SQL standard. It says go like this. But then I also can specify whether I want ties in my output result or not.
Nó giống mệnh đề limit, nhưng đây là chuẩn SQL. Nó viết như thế này. Nhưng tôi cũng có thể chỉ định liệu tôi có muốn các giá trị bằng nhau (ties) trong kết quả đầu ra hay không.
So this is saying with ties.
Ở đây là with ties.
So I have, even though I want the top four results, if there are tuples of the same key that are in the top four, I would have more than four as my output.
Vậy nên, dù tôi muốn bốn kết quả đầu tiên, nếu có các tuple cùng khóa nằm trong bốn kết quả đầu tiên, thì kết quả đầu ra của tôi sẽ có nhiều hơn bốn dòng.
So the way to implement this is pretty basic.
Cách cài đặt việc này khá đơn giản.
You just have some kind of sort of heap data structure, like a priority queue, and you just scan through your data in sequential order once, and you just keep updating things in the sort of heap.
Bạn chỉ cần một cấu trúc dữ liệu dạng heap sắp xếp nào đó, như hàng đợi ưu tiên, và quét dữ liệu theo thứ tự tuần tự đúng một lần, rồi liên tục cập nhật heap sắp xếp đó.
So in this case here, my sort of heap is empty. I see that I have, the first thing I'm pointing out is key three.
Trong trường hợp này, heap sắp xếp của tôi đang rỗng. Điều đầu tiên tôi thấy là khóa ba.
Well, since it's empty, I know that this is going to be the smallest value. So I just go ahead and add that. Scan along. Now I see four.
Vì heap đang rỗng, tôi biết đây sẽ là giá trị nhỏ nhất. Nên tôi cứ thêm vào. Quét tiếp. Giờ tôi thấy bốn.
Four is greater than three, so it goes after three in the sort of heap. Same as six. Six goes up to four. And then in this case here, two now is less than three.
Bốn lớn hơn ba, nên nó nằm sau ba trong heap sắp xếp. Sáu cũng vậy. Sáu nằm sau bốn. Rồi đến đây, hai bây giờ nhỏ hơn ba.
It's the smallest value I've seen. So I just slide everybody over and I put two in the front. And now in this case here, I see a nine.
Đó là giá trị nhỏ nhất tôi đã thấy. Nên tôi dịch mọi phần tử sang bên và đặt hai lên đầu. Và đến đây, tôi thấy một số chín.
Nine is larger than the smallest, larger than the largest value I have in my sort of heap, because I can keep track of the min and max pretty easily.
Chín lớn hơn giá trị nhỏ nhất, lớn hơn giá trị lớn nhất mà tôi có trong heap sắp xếp, vì tôi có thể theo dõi min và max khá dễ dàng.
So in this case here, I don't even bother processing nine.
Nên ở đây tôi thậm chí không cần xử lý số chín.
I just skip it and move on to the next one, because I know it'll never fit in my top four results that I want. Now here I see one.
Tôi bỏ qua và chuyển sang phần tử tiếp theo, vì tôi biết nó sẽ không bao giờ lọt vào bốn kết quả đầu mà tôi muốn. Giờ tôi thấy một.
One is less than two, and therefore it's going to slide in the front. Six gets pushed out. I come along here. Now I see four again.
Một nhỏ hơn hai, nên nó sẽ chen lên đầu. Sáu bị đẩy ra. Tôi đi tiếp. Giờ tôi lại thấy bốn.
And because my query asked that I want to keep ties, keys that have the same value, then now I just need to extend my sort of heap to add more space, more buffer space, to put in the ties, and then keep going the next four until I get the end.
Và vì truy vấn của tôi yêu cầu giữ các giá trị đồng hạng, tức các khóa có cùng giá trị, nên giờ tôi chỉ cần mở rộng heap sắp xếp để thêm chỗ, thêm không gian bộ đệm, để chứa các giá trị đồng hạng, rồi tiếp tục với bốn phần tử kế tiếp cho đến khi hết dữ liệu.
In this case here, eight is greater than the largest value I have in my sort of heap, greater than four. So I go ahead and skip that.
Ở đây, tám lớn hơn giá trị lớn nhất tôi có trong heap sắp xếp, lớn hơn bốn. Nên tôi bỏ qua nó.
So I can run this algorithm in log n, or sorry, not log n, in n, because I have to scan all the keys once, and I populate my sort of heap.
Vậy tôi có thể chạy thuật toán này trong log n, à xin lỗi, không phải log n mà là n, vì tôi phải quét tất cả các khóa một lần và điền vào heap sắp xếp.
That's obviously not done in n time, but it's pretty easy to do. And this would be pretty efficient. In the back, yes.
Rõ ràng việc đó không chạy trong thời gian n, nhưng làm khá dễ. Và cách này khá hiệu quả. Bạn ở phía sau, mời hỏi.
So I think your question is, how do I know whether or not the data I want to scan or the output result is going to fit in memory?
Tôi nghĩ câu hỏi của bạn là, làm sao tôi biết liệu dữ liệu mình muốn quét hay kết quả đầu ra có vừa trong bộ nhớ hay không?
And especially if I have multiple queries running at the same time, and how to balance that.
Nhất là khi có nhiều truy vấn chạy cùng lúc, và làm sao để cân bằng việc đó.
So we're not going to talk about resource allocation and scheduling, but the simplest way to think about this is, like in Postgres, you say every query is allowed x amount of memory.
Chúng ta sẽ không nói về phân bổ tài nguyên và lập lịch, nhưng cách nghĩ đơn giản nhất là, như trong Postgres, bạn quy định mỗi truy vấn được dùng x lượng bộ nhớ.
And then you specify a parameter of how many concurrent queries are allowed to run at the same time. And so you just say, all right, well, I have a gig.
Rồi bạn chỉ định một tham số cho biết có bao nhiêu truy vấn đồng thời được phép chạy cùng lúc. Và bạn nói, được rồi, tôi có một gig.
I'll give each, each query is allowed to use up to 100 gigs or 100 megabytes of memory.
Tôi sẽ cho mỗi, mỗi truy vấn được dùng tối đa 100 gig hoặc 100 megabyte bộ nhớ.
And then if I, the data I'm going to scan, in this case here, the original data, the original data doesn't have to fit in memory, but I obviously want my sort of heap in memory.
Và nếu dữ liệu tôi sắp quét, trong trường hợp này là dữ liệu gốc, dữ liệu gốc không cần phải vừa trong bộ nhớ, nhưng rõ ràng là tôi muốn cái heap dùng để sắp xếp của mình nằm trong bộ nhớ.
So I would just do a sequential scan along the original data. I rely on my buffer pool to decide how to evict things.
Vì vậy tôi chỉ cần quét tuần tự trên dữ liệu gốc. Tôi dựa vào buffer pool để quyết định cách loại bỏ các trang.
We talk about ARC and MRU and other things. That's why this all matters. So I scan all my data once, and then I just populate this thing.
Chúng ta đã nói về ARC, MRU và những thứ khác. Đó là lý do tất cả những điều này quan trọng. Vậy là tôi quét toàn bộ dữ liệu một lần, rồi chỉ việc điền vào cấu trúc này.
The sort of heap will typically fit in memory. This is not that big. If I'm asking for the, fetch the first billion rows, then yeah, that's going to be a problem.
Cái heap dùng để sắp xếp thường sẽ vừa trong bộ nhớ. Nó không lớn lắm. Nếu tôi yêu cầu lấy một tỉ hàng đầu tiên, thì đúng, đó sẽ là một vấn đề.
But again, I would know that ahead of time because SQL is declarative. I know how much, I know how many results you're asking.
Nhưng một lần nữa, tôi sẽ biết điều đó trước vì SQL là khai báo. Tôi biết bạn yêu cầu bao nhiêu kết quả.
And therefore I can roughly, I can calculate how big do I think this data structure is going to be, and I can decide whether it's going to fit in memory or not.
Và do đó tôi có thể ước chừng, tôi có thể tính xem cấu trúc dữ liệu này sẽ lớn cỡ nào, và tôi có thể quyết định nó có vừa trong bộ nhớ hay không.
The enterprise systems do a much better job at slicing, dicing resources where you can allow, like, hey, this query, everybody's allowed to use 100 megabytes, but if I'm not using 100 megabytes, I can borrow some from another system, sorry, from another query, and they can be a bit more flexible.
Các hệ thống doanh nghiệp làm tốt hơn nhiều việc chia nhỏ và phân bổ tài nguyên, chẳng hạn cho phép kiểu như, truy vấn này, mỗi người được dùng 100 megabyte, nhưng nếu tôi không dùng hết 100 megabyte, tôi có thể mượn bớt từ một hệ thống khác, xin lỗi, từ một truy vấn khác, và chúng linh hoạt hơn một chút.
I think Postgres is a bit more rigid in the parameters you specify. So this is one example where the enterprise systems are much better at scheduling resources.
Tôi nghĩ Postgres cứng nhắc hơn một chút ở các tham số bạn chỉ định. Vậy đây là một ví dụ cho thấy các hệ thống doanh nghiệp điều phối tài nguyên tốt hơn nhiều.
Yes. Correct. So the question is, if there's a lot of ties, how do I estimate the size of this heap? So we're not going to talk about cost estimates just yet.
Vâng. Đúng vậy. Câu hỏi là, nếu có rất nhiều giá trị bằng nhau, thì làm sao ước lượng kích thước của heap này? Chúng ta chưa nói về ước lượng chi phí vội.
That'll come after the midterm. But you have some basic histograms on the data. So you can figure out, like, how many distinct values would be in a column, right?
Việc đó sẽ đến sau kỳ thi giữa kỳ. Nhưng bạn có một số histogram cơ bản về dữ liệu. Nên bạn có thể tính ra, có bao nhiêu giá trị phân biệt trong một cột, đúng không?
There's a little, the math is a bit fudgy. And because also too, it's a summarization. It's not the real, you don't have the real data.
Phép tính này hơi chắp vá một chút. Và cũng vì đó chỉ là bản tóm tắt. Đó không phải dữ liệu thật, bạn không có dữ liệu thật.
So you basically use some simple cost formulas to decide how big you think this is going to be. And in general, you overestimate because you don't want to be like really wrong.
Nên về cơ bản bạn dùng một số công thức chi phí đơn giản để quyết định bạn nghĩ nó sẽ lớn cỡ nào. Và nói chung, bạn ước lượng dư vì không muốn sai quá nhiều.
Yes. The question is, do you always overestimate for memory? Typically yes.
Vâng. Câu hỏi là có phải lúc nào cũng ước lượng dư cho bộ nhớ không? Thường là có.
Because again, you don't know what, you don't know how much data you're going to, how much, you don't know the size of the intermediate result until you actually produce, run it.
Vì một lần nữa, bạn không biết mình sẽ có bao nhiêu dữ liệu, bạn không biết kích thước của kết quả trung gian cho đến khi thực sự chạy và tạo ra nó.
So this is like your hash table.
Điều này giống như hash table của bạn.
When you want to size that thing, so you don't have to like dump it out and resize it when you run the queries, like, they'll try to do an estimate and then they have a fudge factor.
Khi bạn muốn định cỡ nó, để không phải đổ ra rồi đổi kích thước lại khi chạy truy vấn, họ sẽ cố ước lượng rồi thêm một hệ số dự phòng.
Say, oh, I think I have 100 records, but I'll make, oh, I might see 150, so I'll just allocate it for that. That's pretty much every system does that.
Kiểu như, tôi nghĩ mình có 100 bản ghi, nhưng, ồ, có thể tôi thấy 150, nên tôi sẽ cấp phát cho chừng đó. Gần như hệ thống nào cũng làm vậy.
Because again, you don't know what you're going to see until you actually see it. We'll spend two lectures on query cost models and cost estimations and all these things.
Vì một lần nữa, bạn không biết mình sẽ thấy gì cho đến khi thực sự thấy nó. Chúng ta sẽ dành hai bài giảng cho mô hình chi phí truy vấn, ước lượng chi phí và những thứ như vậy.
This is the black magic of database systems and everybody's terrible at it and it's like really, really hard, but we'll cover that later.
Đây là phép thuật đen của các hệ thống cơ sở dữ liệu và ai cũng làm rất tệ việc này, nó thực sự rất, rất khó, nhưng chúng ta sẽ nói về nó sau.
All right, so again, this is a special case.
Được rồi, như vậy đây là một trường hợp đặc biệt.
If you know your query asks for an order by and it's asking for the top N entries, then you can do this and you don't have to do one scan of the data once.
Nếu bạn biết truy vấn yêu cầu order by và chỉ lấy N bản ghi đầu, thì bạn có thể làm cách này và không cần quét dữ liệu một lần.
If it's a general sort request or order by request, and I can estimate that it's not going to fit in memory, I want to use what's called external merge sort.
Nếu là yêu cầu sắp xếp hay order by thông thường, và tôi ước lượng rằng dữ liệu sẽ không vừa trong bộ nhớ, thì tôi muốn dùng thứ gọi là external merge sort.
So in this case here, you would know how much, you would have a rough idea how much data you're going to scan.
Vậy trong trường hợp này, bạn sẽ biết được bạn sẽ có ý niệm đại khái về lượng dữ liệu mà mình sẽ quét.
It's not always true either, because you could do sorting after joins, and join estimates get way off. But just think of the simplest thing.
Điều này cũng không phải lúc nào cũng đúng, vì bạn có thể sắp xếp sau các phép join, và các ước lượng về join thường lệch rất xa. Nhưng hãy nghĩ đến trường hợp đơn giản nhất.
If I'm going to scan a table and run an ORDER BY on it without a filter, if I know that the table has a billion tuples, I'm going to have to sort a billion tuples, and therefore I can make my cost estimations based on that and decide to fall back to this.
Nếu tôi quét một bảng và chạy ORDER BY trên đó mà không có bộ lọc, nếu tôi biết bảng có một tỉ tuple, thì tôi sẽ phải sắp xếp một tỉ tuple, và do đó tôi có thể đưa ra các ước lượng chi phí dựa trên điều đó và quyết định chuyển sang dùng cách này.
There are some systems that can be a bit more adaptive, where they say, okay, I think the data will fit in memory, so start running quick sort.
Có một số hệ thống có thể thích ứng tốt hơn một chút, tức là họ nói: được rồi, tôi nghĩ dữ liệu sẽ vừa trong bộ nhớ, nên cứ chạy quick sort.
If I get it wrong and I realize I'm spilling to disk, then I just stop what I'm doing, throw away the results, and then fall back to one of these algorithms.
Nếu tôi đoán sai và nhận ra mình đang tràn ra đĩa, thì tôi chỉ việc dừng lại, bỏ kết quả đang có, rồi chuyển sang một trong các thuật toán này.
But not every system can do that.
Nhưng không phải hệ thống nào cũng làm được vậy.
All right, so external merge sort is a divide and conquer algorithm where we're going to split the data that we want to sort up into separate runs, sort them, and then start merging them together into successively larger sorted runs.
Được rồi, external merge sort là một thuật toán chia để trị, trong đó ta sẽ chia dữ liệu cần sắp xếp thành các run riêng biệt, sắp xếp từng run, rồi bắt đầu trộn chúng lại thành các run đã sắp xếp lớn dần.
So there'd be essentially two phases for every sort pass.
Vậy về cơ bản mỗi lượt sắp xếp có hai giai đoạn.
With the first phase, we do the sorting, so we just bring in chunks that we can fit into memory, sort them with your favorite in-memory sorting algorithm, a quick sort or whatever, and then we would, if necessary, write them back out to pages on disk.
Ở giai đoạn đầu, ta thực hiện việc sắp xếp, tức là chỉ đưa vào những khối mà ta có thể chứa vừa trong bộ nhớ, sắp xếp chúng bằng thuật toán sắp xếp trong bộ nhớ mà bạn thích, quick sort hay gì đó, rồi nếu cần thì ghi chúng ra các trang trên đĩa.
And then if we bring them back in, we'll merge them together with sorted runs of the same size and produce larger runs.
Sau đó, khi ta đưa chúng trở lại vào bộ nhớ, ta sẽ trộn chúng với các run đã sắp xếp có cùng kích thước để tạo ra các run lớn hơn.
And we keep doing this over and over again until we end up with all the data completely sorted. I'll show a visualization of this.
Và ta cứ lặp đi lặp lại như vậy cho đến khi toàn bộ dữ liệu được sắp xếp hoàn chỉnh. Tôi sẽ cho xem một hình minh họa.
So the general algorithm is called a K-way external merge sort, but I'll start with a simple one, which is 2-way merge sort, external merge sort, And then 2 is going to be the number of runs we're going to merge for every pass that we do.
Thuật toán tổng quát được gọi là K-way external merge sort, nhưng tôi sẽ bắt đầu với bản đơn giản là 2-way external merge sort. Và 2 là số run mà ta sẽ trộn trong mỗi lượt thực hiện.
So we're going to take two runs, merge them together to produce a new sort of run that's twice as large because it's a combination of the two of them.
Vậy ta sẽ lấy hai run, trộn chúng lại để tạo ra một run mới lớn gấp đôi vì nó là sự kết hợp của cả hai.
And the K-way, you can say, I'm going to bring in K pages or K sorted runs and then just merge them all together and produce one that's K size and write that out.
Còn với K-way, bạn có thể nói: tôi sẽ đưa vào K trang hoặc K run đã sắp xếp rồi trộn tất cả chúng lại với nhau và tạo ra một run có kích thước K rồi ghi nó ra.
We're going to keep it simple with 2. So for this, we're going to assume that the data will be broken up into big N pages.
Chúng ta sẽ làm đơn giản với 2. Với phần này, chúng ta sẽ giả định rằng dữ liệu được chia thành N trang.
And then we'll say that the amount of memory that we're allowed to use in our buffer pool manager will be B pages.
Và lượng bộ nhớ mà chúng ta được phép dùng trong buffer pool manager sẽ là B trang.
And we're going to need that for both the input of the pages that we're bringing in for our input runs, and then we need at least one page to write out, right?
Chúng ta cần bộ nhớ này cho cả đầu vào, tức các trang mà ta đưa vào cho các input run, và ta cũng cần ít nhất một trang để ghi ra, đúng không?
We have one page that we'd write out to disk. So in pass 0, all the data is unsorted on disk.
Ta có một trang sẽ được ghi xuống đĩa. Vậy ở pass 0, toàn bộ dữ liệu trên đĩa chưa được sắp xếp.
So we're going to bring the pages one at a time into memory, sort them in place within, well, actually not in place, make a copy into another buffer pool page, sort that page, and then we'd write it back out to disk.
Nên ta sẽ lần lượt đưa từng trang vào bộ nhớ, sắp xếp ngay tại chỗ, à, thực ra không phải tại chỗ, mà tạo một bản sao sang một trang khác của buffer pool, sắp xếp trang đó, rồi ghi ngược lại xuống đĩa.
We do this until we have all the pages in the input table with input data sorted. And then we then have the successive passes.
Ta làm vậy cho đến khi tất cả các trang của bảng đầu vào đều đã được sắp xếp. Sau đó là các pass kế tiếp.
We'll recursively merge the pairs of sorted runs into larger and larger and larger runs. And then keep doing this until, again, we have a complete output.
Ta sẽ đệ quy trộn từng cặp sorted run thành các run ngày càng lớn hơn. Và tiếp tục như vậy cho đến khi ta có được kết quả đầu ra hoàn chỉnh.
So for this example here, for 2-way merge sort, we need at least three buffer pool pages. We need two for the input and then one for writing out the output.
Vậy với ví dụ này, của 2-way merge sort, ta cần ít nhất ba trang buffer pool. Cần hai trang cho đầu vào và một trang để ghi đầu ra.
So again, in the first pass, we're just going to read all the pages we have on disk and just sort them. So in pass 0, here's all the pages on disk.
Vậy ở pass đầu tiên, ta chỉ đọc tất cả các trang có trên đĩa và sắp xếp chúng. Ở pass 0, đây là toàn bộ các trang trên đĩa.
Again, it's a 2-way external merge sort, and we're just assuming that there's two keys per page. So in the first pass, pass 0, we're going to produce sorted runs of size one page.
Một lần nữa, đây là 2-way external merge sort, và ta giả định mỗi trang có hai khóa. Ở pass đầu tiên, pass 0, ta sẽ tạo ra các sorted run có kích thước một trang.
So for every single page at the top, bring it in, sort its contents, the two keys, and then just write that out back to disk.
Với mỗi trang ở trên cùng, đưa nó vào, sắp xếp nội dung, tức hai khóa, rồi ghi ngược lại xuống đĩa.
Again, this is all sequential IOs, so we can scan the table sequentially, and then when we sort it and write it out, that's all going to be done sequentially as well.
Một lần nữa, tất cả đều là IO tuần tự, nên ta có thể quét bảng một cách tuần tự, và khi sắp xếp rồi ghi ra, việc đó cũng đều được thực hiện tuần tự.
And now in the next pass, we want to generate runs of size two pages, because we're doubling the size of the runs as we go down.
Còn ở pass kế tiếp, ta muốn tạo các run có kích thước hai trang, vì kích thước của các run được nhân đôi khi ta đi xuống.
So in this case here, we're going to bring in these two pages that I have here, 3, 4 and 2, 6, and then we have an output page where we're going to take whatever the result of the sorted run is, and we stage that sorted output there.
Vậy trong trường hợp này, ta sẽ đưa vào hai trang này, 3, 4 và 2, 6, và ta có một trang đầu ra, nơi ta sẽ lấy kết quả của sorted run, và lưu tạm kết quả đã sắp xếp ở đó.
And obviously we know it's going to be two-page runs, so we only have one page to write the first output, and when this gets written out to disk, because it's full, we'll reuse the page and write something else.
Và rõ ràng ta biết đó sẽ là các run hai trang, nên ta chỉ có một trang để ghi đầu ra đầu tiên, và khi trang này được ghi xuống đĩa, vì đã đầy, ta sẽ tái sử dụng trang đó và ghi dữ liệu khác.
So basically in this sort of merge pass, you have two iterators, one that's pointing at both of the runs I'm trying to merge together, and all you're doing is just comparison of the keys.
Về cơ bản, trong merge pass này, bạn có hai iterator, mỗi iterator trỏ vào một trong hai run mà tôi đang muốn trộn với nhau, và việc bạn làm chỉ là so sánh các khóa.
So the beginning here, the first iterator points to 3, the second iterator points to 2.
Vậy ban đầu, iterator thứ nhất trỏ tới 3, iterator thứ hai trỏ tới 2.
2 is less than 3 because we're going in ascending order, so I'll write out 2 and then move the iterator on the second page over by 1.
2 nhỏ hơn 3 vì ta đang đi theo thứ tự tăng dần, nên tôi sẽ ghi 2 ra, rồi dịch iterator ở trang thứ hai đi 1 vị trí.
Now I do the same comparison, compare 3 in the first page, the 6 in the second page.
Giờ tôi so sánh tương tự: so 3 ở trang đầu với 6 ở trang thứ hai.
3 is less than 6, so I write 3, And then now my page is full, so I'm going to go ahead and write that out to disk, but then complete the merging of the other pages.
3 nhỏ hơn 6, nên tôi ghi 3. Và bây giờ trang của tôi đã đầy, nên tôi sẽ ghi trang đó ra đĩa, rồi tiếp tục hoàn tất việc trộn các trang còn lại.
Question: are the offsets disk offsets? Offsets of what? Sorry.
Câu hỏi: các offset này là offset trên đĩa phải không? Offset của cái gì vậy? Xin lỗi.
Like 3, 4, 2, 6? These are the keys.
Như 3, 4, 2, 6 à? Đó là các khóa.
Question is, have I brought the entire page in memory? Yes. You have to, because the keys are in there.
Câu hỏi là tôi có đưa toàn bộ trang vào bộ nhớ không? Có. Bắt buộc phải vậy, vì các khóa nằm trong đó.
My example, it's 2 keys per page, but again, think of like, if I have larger keys, I can't just have offsets when I start the comparisons, because I have to go check to see if the values, where they're real.
Trong ví dụ của tôi, mỗi trang có 2 khóa, nhưng hãy nghĩ thử, nếu tôi có các khóa lớn hơn, tôi không thể chỉ dùng offset khi bắt đầu so sánh, vì tôi phải đi kiểm tra xem các giá trị thật sự nằm ở đâu.
So I bring the pages in, scan through them, and then do that merge comparison.
Vậy nên tôi đưa các trang vào, quét qua chúng, rồi thực hiện so sánh để trộn.
All right, so I'll do this all for the other pages at this pass.
Được rồi, tôi sẽ làm vậy cho tất cả các trang còn lại ở lượt này.
So I end up with 2, 3 runs of size 2 pages, and the last one here, it's less than 1, or it's less than 2, but that's okay, and I have a little end of file marker to say that there's nothing else beyond this.
Cuối cùng tôi có 2, 3 run kích thước 2 trang, và run cuối cùng ở đây nhỏ hơn 1, à, nhỏ hơn 2 trang, nhưng không sao, và tôi có một dấu hiệu kết thúc tệp nhỏ để báo rằng phía sau không còn gì nữa.
So then now the next pass, again, I'm going to generate sorted runs of size, double the size of the last pass.
Rồi đến lượt tiếp theo, tôi lại tạo các sorted run có kích thước gấp đôi lượt trước.
So now I'm going to generate runs of size 4. Do the same thing. Iterate through the two input pages, my sorted runs, and I'm merging.
Giờ tôi sẽ tạo các run kích thước 4. Làm tương tự. Duyệt qua hai trang đầu vào, tức các sorted run của tôi, và trộn chúng.
Do key comparisons to see which one is less than the other, and write them out in successive order, and then when I'm done with generating this run, I then switch over and do the next one.
So sánh khóa để xem cái nào nhỏ hơn cái nào, và ghi chúng ra theo thứ tự liên tiếp, rồi khi tạo xong run này, tôi chuyển sang run tiếp theo.
Do this again, and then you end up with a pass of now 8-page runs, and that's the entire data set. Yes? First what? First pass? So pass 0? Okay.
Làm lại lần nữa, và cuối cùng bạn có một lượt với các run 8 trang, và đó là toàn bộ tập dữ liệu. Vâng? Đầu tiên là gì? Lượt đầu tiên? Tức pass 0? Được.
Pass 1 or pass 0? Okay. Correct. In this example here, I'm assuming I have 3 pages. 3. You only need 3.
Pass 1 hay pass 0? Được. Đúng rồi. Trong ví dụ này, tôi giả sử có 3 trang. 3. Bạn chỉ cần 3.
So say I'm here. So for this first guy here, like 2, 3, 4, 6. That's on this sort of run on this side. I can't use the red.
Giả sử tôi đang ở đây. Với phần đầu tiên này, như 2, 3, 4, 6. Đó là run ở phía bên này. Tôi không dùng được màu đỏ.
And then there's 4, 7, 8, 9. So I only bring this first page here, and this first page here from that run. Then I do my comparison.
Và còn có 4, 7, 8, 9. Vậy tôi chỉ đưa trang đầu tiên ở đây, và trang đầu tiên ở đây từ run đó vào. Rồi tôi thực hiện so sánh.
Because within the run they're sorted, I know that there isn't going to be a key on these lower pages here that could be less than over here if I've already successfully moved down on it.
Vì trong một run các khóa đã được sắp xếp, tôi biết sẽ không có khóa nào ở các trang thấp hơn này có thể nhỏ hơn khóa bên này nếu tôi đã di chuyển qua nó thành công.
So I never need to go back and look at the inputs of the sorted runs again. And therefore, I only need to bring in one page at a time for the two sorted runs.
Nên tôi không bao giờ cần quay lại xem đầu vào của các sorted run đó nữa. Do đó, tôi chỉ cần đưa vào từng trang một cho hai sorted run.
So in this example here, we only need 3. Yes?
Vậy trong ví dụ này, chúng ta chỉ cần 3. Vâng?
The question is, are these mergers consolidating the results of the sorting into separate pages?
Câu hỏi là các bước trộn này có gộp kết quả sắp xếp vào các trang riêng biệt không?
No. So like, go back here. So in pass 1, the size of the sorted run I'm going to generate will be 2 pages.
Không. Hãy quay lại đây. Ở pass 1, kích thước của sorted run tôi sẽ tạo là 2 trang.
So the first page I'm going to generate has 2 and 3 in it. I write that out the disk. Then the next page is going to have 4 and 6 through it.
Trang đầu tiên tôi tạo có 2 và 3 trong đó. Tôi ghi nó ra đĩa. Rồi trang tiếp theo sẽ có 4 và 6.
That's a new page and I write that out the disk. They're separate pages from the original pages that I started with up here.
Đó là một trang mới và tôi ghi nó ra đĩa. Đó là những trang riêng biệt so với các trang gốc mà tôi bắt đầu ở phía trên này.
Yes?
Bạn hỏi à?
The question is, as soon as we finish generating a new output page, we write that out the disk and then we, what, bring another one in?
Câu hỏi là ngay khi chúng ta tạo xong một trang đầu ra mới, chúng ta ghi nó xuống đĩa và sau đó, gì nhỉ, nạp một trang khác vào?
It's already, like, we're going back here. So I wrote out 2 and then I'm going to write out 3. That point, that thing is full. I'm going to write that out the disk.
Thực ra nó đã có sẵn rồi, chúng ta quay lại chỗ này. Vậy tôi ghi ra số 2 và sau đó sẽ ghi ra số 3. Đến lúc đó, trang ấy đã đầy. Tôi sẽ ghi nó xuống đĩa.
But I already have this page and this page in memory. Just keep scanning on them, right?
Nhưng tôi đã có sẵn trang này và trang này trong bộ nhớ. Cứ tiếp tục quét trên chúng, đúng không?
And at some point, the iterator will get to the end and say, oh, I've seen everything I can see for this.
Và đến một lúc nào đó, iterator sẽ đi đến cuối và nói, ồ, mình đã thấy hết mọi thứ có thể thấy ở đây rồi.
If one iterator finishes before the other one, you say, "All right, well, I know there isn't anything on this side that's going to be less than this side."
Nếu một iterator kết thúc trước iterator kia, bạn sẽ nói: "Được rồi, tôi biết là không có gì ở phía này nhỏ hơn phía kia nữa."
So therefore, just write out all the, from the first iterator, write out to disk. And it's sorted because I sorted it before I got to doing that pass anyway. Yes.
Vậy nên cứ ghi toàn bộ phần còn lại từ iterator đầu tiên xuống đĩa. Và nó đã được sắp xếp vì dù sao tôi cũng đã sắp xếp nó trước khi thực hiện lượt đó. Vâng, mời bạn.
The question is, why didn't it traverse the index? It's already sorted. What index?
Câu hỏi là, tại sao không duyệt qua chỉ mục? Nó đã được sắp xếp rồi. Chỉ mục nào?
The statement is, why didn't it do a, why didn't it, like, why not use the index that the key is ordered by? There may not be an index. What if there's no index? Yeah.
Ý bạn là, tại sao nó không, tại sao không dùng chỉ mục được sắp theo khóa đó? Có thể không có chỉ mục nào. Nếu không có chỉ mục thì sao? Vâng.
This is like, for any arbitrary key, I can sort. If I have an index, then, yeah, I could just scan along leaf nodes and I would use that.
Ở đây là với một khóa bất kỳ, tôi đều có thể sắp xếp. Nếu tôi có chỉ mục, thì đúng, tôi chỉ cần quét dọc các nút lá và sẽ dùng cách đó.
But I can't. Yes.
Nhưng tôi không có. Vâng, mời bạn.
His question is, and he's right, and we'll fix this in a second, am I worried about IO stalls when I write to disk? Absolutely. We'll do double buffering. That'll make that go away. Yes.
Câu hỏi của bạn ấy là, và bạn ấy nói đúng, lát nữa chúng ta sẽ khắc phục điều này, liệu tôi có lo về các IO stall khi ghi xuống đĩa không? Chắc chắn rồi. Chúng ta sẽ dùng double buffering. Cách đó sẽ loại bỏ vấn đề này. Vâng.
This is the basic algorithm, though. Just like, I got three pages. I can bring two in and write one out. All right.
Tuy nhiên, đây là thuật toán cơ bản. Giống như, tôi có ba trang. Tôi có thể nạp hai trang vào và ghi một trang ra. Được rồi.
So the number of passes we're going to have to do is 1 plus log 2N. Again, it's, the 1 is for the pass 0 because I have to pass through the data once.
Vậy số lượt chúng ta phải thực hiện là 1 cộng log 2N. Một lần nữa, số 1 là cho lượt 0 vì tôi phải duyệt qua dữ liệu một lần.
And the log 2 is because I'm generating passes that are double the size of the previous one, and N is the total number of pages.
Còn log 2 là vì tôi tạo ra các lượt có kích thước gấp đôi lượt trước, và N là tổng số trang.
Therefore, the total number of IO calls will be 2N because, again, for the, for the plus 1, that's pass 0, I got to read it once and write it out once, hence 2N.
Do đó, tổng số lệnh gọi IO sẽ là 2N vì, một lần nữa, đối với phần cộng 1, tức lượt 0, tôi phải đọc một lần và ghi ra một lần, do đó là 2N.
And then the number of passes up above.
Và sau đó là số lượt ở phía trên.
So, again, in this simple example here, we just assume that we only have three bufferable pages, two for the input, one for the output.
Vậy, một lần nữa, trong ví dụ đơn giản này, chúng ta chỉ giả sử có ba trang có thể đệm, hai cho đầu vào, một cho đầu ra.
The challenge is going to be, though, if we, even if we give, we give more bufferable space to our system, you know, where now we can take, generate larger sorted runs, right, that'll shrink the height of the, of the sort of, the number of passes we have to do, but it's still going to be slow, as he pointed out, because we are essentially just blocking every time we have to write stuff out,
Tuy nhiên, thách thức sẽ là, nếu chúng ta, ngay cả khi chúng ta cấp thêm không gian đệm cho hệ thống, tức là bây giờ chúng ta có thể tạo ra các sorted run lớn hơn, thì điều đó sẽ giảm chiều cao của số lượt mà chúng ta phải thực hiện, nhưng nó vẫn sẽ chậm, như bạn ấy đã chỉ ra, vì về cơ bản chúng ta bị chặn mỗi khi phải ghi dữ liệu ra,
blocking any time we have to read something. Right? So, again, we'll, we'll fix that in a second.
và bị chặn bất cứ khi nào phải đọc thứ gì đó. Đúng không? Vậy nên, chúng ta sẽ khắc phục chuyện đó ngay sau đây.
But in general, the algorithm for this, for a general external merge sort, assuming you have B bufferable pages, you're going to produce, to this, the ceiling of N divided by B sorted runs, since it's a size B, in pass 0, because, again, you'd read everything once and write it out once of that size there.
Nhưng nói chung, thuật toán cho việc này, tức external merge sort tổng quát, giả sử bạn có B trang bộ đệm, thì bạn sẽ tạo ra số lượt chạy đã sắp xếp bằng trần của N chia B, vì mỗi lượt có kích thước B, ở lượt 0, bởi vì, một lần nữa, bạn đọc toàn bộ dữ liệu một lần và ghi ra một lần với kích thước đó.
And then in the subsequent passes, I can generate runs that are size B minus 1, because I need always at least one buffer page for my output.
Và ở các lượt tiếp theo, tôi có thể tạo ra các run có kích thước B trừ 1, vì tôi luôn cần ít nhất một trang bộ đệm cho đầu ra.
Right? And that's the same formula that we showed before. So, let's run through a quick example, again, without doing any double buffering or any optimizations.
Đúng không? Và đó cũng là công thức mà chúng ta đã trình bày trước đó. Giờ hãy chạy qua một ví dụ nhanh, một lần nữa, mà không dùng double buffering hay bất kỳ tối ưu hóa nào.
Assume we want to, we want to sort a data set that has 108 pages and I'm allowed to use five bufferable pages. Right? So, big N equals 108 and B equals 5 here.
Giả sử chúng ta muốn sắp xếp một tập dữ liệu có 108 trang và tôi được phép dùng năm trang bộ đệm. Đúng không? Vậy N bằng 108 và B bằng 5 ở đây.
So, in pass 0, again, I've got to read everything once and write it out once in the sorted runs. So, this will generate 22 sorted runs for me of size five pages each.
Vậy ở lượt 0, tôi phải đọc toàn bộ một lần và ghi ra một lần thành các run đã sắp xếp. Như vậy sẽ tạo ra 22 run đã sắp xếp, mỗi run có kích thước năm trang.
The last one is only three pages, because 108 is not easily, not perfectly divisible by five. And so, we take the ceiling there, because then it just rounds up.
Run cuối cùng chỉ có ba trang, vì 108 không chia hết cho năm. Do đó chúng ta lấy trần ở đây, vì nó sẽ làm tròn lên.
And then in pass 1 now, we're reading in the, those 22 sorted runs of size 5 pages, and now we're going to generate sorted runs of size 10, I'm sorry, of size 20 pages.
Rồi ở lượt 1, chúng ta đọc vào 22 run đã sắp xếp có kích thước 5 trang đó, và bây giờ chúng ta sẽ tạo ra các run đã sắp xếp có kích thước 10, xin lỗi, kích thước 20 trang.
And then the last run, again, it's not full size, so it'll only end up being eight pages because you have to round up.
Và run cuối cùng, một lần nữa, không đủ kích thước, nên cuối cùng nó chỉ có tám trang vì phải làm tròn lên.
We keep doing this until we reach the end, where we produce the two sorted runs that we have to read in, and then you write out one sorted run that's a total of 80 pages, that was originally given as our input.
Chúng ta cứ làm vậy cho đến khi tới cuối, nơi chúng ta tạo ra hai run đã sắp xếp cần đọc vào, rồi bạn ghi ra một run đã sắp xếp có tổng cộng 80 trang, vốn là dữ liệu đầu vào ban đầu của chúng ta.
So, 80 plus 28. Right?
Vậy 80 cộng 28. Đúng không?
So, in this case here, just plug and chugging the formula, you end up with four passes because, again, you're progressively having the number of inputs and outputs, sorry, the number of pages you always have to read in and out per pass is the same, but the number of passes I have to do shrinks down once you have more buffer pool space.
Vậy trong trường hợp này, chỉ cần thay số vào công thức, bạn sẽ có bốn lượt vì, một lần nữa, số lượng đầu vào và đầu ra giảm dần, xin lỗi, số trang bạn luôn phải đọc vào và ghi ra mỗi lượt là như nhau, nhưng số lượt tôi phải thực hiện giảm xuống khi bạn có nhiều không gian buffer pool hơn.
So, let's solve the problem that he brought up, where if I naively just block the world in my database system every time I've got to read and write a page, that's going to be slow because, again, disk stalls can be quite expensive.
Giờ hãy giải quyết vấn đề mà bạn ấy nêu ra, đó là nếu tôi chỉ đơn giản chặn toàn bộ hệ thống trong hệ cơ sở dữ liệu mỗi khi phải đọc và ghi một trang, thì sẽ rất chậm vì, một lần nữa, độ trễ của đĩa có thể khá tốn kém.
Right? Slow spinning disk hard drives are going to be in the order of up to 10 to 50 milliseconds. Right? SSDs are a bit faster.
Đúng không? Ổ cứng đĩa quay chậm sẽ có độ trễ cỡ từ 10 đến 50 mili giây. Đúng không? SSD nhanh hơn một chút.
But even SSDs are really fast, but the only way you get that good speed is if you have a lot of things in your IO queue that you want to read and write in parallel.
Nhưng ngay cả SSD cũng rất nhanh, song cách duy nhất để đạt tốc độ tốt đó là bạn có nhiều thao tác trong hàng đợi IO mà bạn muốn đọc và ghi song song.
That's how these sort of modern systems get good performance.
Đó là cách các hệ thống hiện đại đạt được hiệu năng tốt.
So, if I just do the naive thing we did before, where, like, I'm going to sort this data, I'm going to go fetch all my pages in my buffer pool, then I go ahead and do the merge, the sort and the merge, produce an output buffer and write that out.
Vậy nếu tôi chỉ làm theo cách ngây thơ như trước, tức là tôi sẽ sắp xếp dữ liệu này, tôi sẽ nạp tất cả các trang vào buffer pool, rồi tiến hành trộn, sắp xếp và trộn, tạo ra một bộ đệm đầu ra và ghi nó xuống.
While I'm doing this write, I'm basically stalling the rest of the system. The CPU's not doing anything because it's waiting for all this data to get written out to disk.
Trong lúc ghi như vậy, về cơ bản tôi đang làm đình trệ phần còn lại của hệ thống. CPU không làm gì cả vì nó phải chờ toàn bộ dữ liệu này được ghi xuống đĩa.
Right?
Đúng không?
So, what I want to do is actually use half the buffers that are available to me for sort of one stage of a pass and then another, I want to say stage, like, sort of, one sort of sliver of the data I need to sort within one pass and then the other buffer will be for another sort of sliver of data within my pass.
Vì vậy, điều tôi muốn làm là dùng một nửa số bộ đệm mà tôi có cho một giai đoạn của một lượt, và nửa còn lại cho giai đoạn khác, ý tôi là giai đoạn, kiểu như, một phần dữ liệu cần sắp xếp trong một lượt và bộ đệm còn lại sẽ dành cho một phần dữ liệu khác trong lượt đó.
So, now what'll happen is I can fetch in data from one part of the file and then while that's doing the merging, which is computationally expensive potentially, and writing it out to disk, I go fetch in now the other pages for the other part of the pass I'm at and then they do their own sorting.
Như vậy, điều xảy ra là tôi có thể nạp dữ liệu từ một phần của tệp, và trong lúc phần đó đang được trộn, việc này có thể tốn nhiều tính toán, và ghi xuống đĩa, tôi nạp tiếp các trang khác cho phần còn lại của lượt hiện tại và chúng tự sắp xếp.
I'm sort of ping-ponging or going back and forth where one portion of my buffer pool is being used for sorting things in memory and writing it out to disk and the other portion of my buffer pool is being used for fetching things from disk and then going ahead and sorting them.
Tôi kiểu như chơi bóng bàn qua lại, trong đó một phần của buffer pool được dùng để sắp xếp dữ liệu trong bộ nhớ và ghi xuống đĩa, còn phần kia của buffer pool được dùng để nạp dữ liệu từ đĩa rồi tiếp tục sắp xếp chúng.
Of course, obviously, it's tricky that you don't, you know, you can't magically write data with the same full speed at the same time, so the timing can be a bit tricky, but modern, again, modern SSDs can sort of handle all that and do the balancing to make sure you don't slow things down.
Tất nhiên, rõ ràng là việc này khá khó, vì bạn không thể ghi dữ liệu một cách thần kỳ với tốc độ tối đa cùng lúc, nên việc canh thời gian có thể hơi phức tạp, nhưng các SSD hiện đại có thể xử lý tất cả những việc đó và cân bằng để bảo đảm không làm chậm hệ thống.
So obviously, again, this reduces the amount of memory buffer pools they have available to do larger sorted runs, but this is going to hide the IO stalls you would have from the workers waiting for things to get written from disk.
Dĩ nhiên, một lần nữa, cách này làm giảm lượng bộ nhớ của buffer pool có sẵn để tạo các run đã sắp xếp lớn hơn, nhưng nó sẽ che giấu các đình trệ IO mà bạn sẽ gặp khi các worker phải chờ dữ liệu được ghi xuống đĩa.
All right, there's some additional optimizations we can do in our actual implementation.
Được rồi, có thêm một số tối ưu hóa mà ta có thể làm trong cài đặt thực tế.
Some of these are low-level things where you're kind of trying to shave off, again, cycles in your CPU, but some of these are actually necessary to actually get that thing to actually work well.
Một số là những thứ ở mức thấp, nơi bạn cố gắng tiết kiệm từng chu kỳ trên CPU, nhưng một số thực sự cần thiết để hệ thống chạy tốt.
So, The comparison operation, again, in an algorithms class, they're very hand-wavy about that because it's always like, oh, comparing this integer with that integer and you sort that.
Thao tác so sánh, trong một lớp về thuật toán, người ta nói rất qua loa về nó vì lúc nào cũng kiểu, so sánh số nguyên này với số nguyên kia rồi sắp xếp.
In actuality, oftentimes data is usually going to look like strings or be a combination of multiple keys, and that comparison call to see whether one key is less than another key, that can start to add up and be expensive, especially if you're trying to sort a billion things.
Trên thực tế, dữ liệu thường là chuỗi hoặc là tổ hợp của nhiều khóa, và lời gọi so sánh để xem khóa này có nhỏ hơn khóa kia không có thể cộng dồn lại và trở nên tốn kém, đặc biệt nếu bạn sắp xếp cả tỉ phần tử.
So, a bunch of techniques you could do are, one is called code specialization.
Vì vậy, có một số kỹ thuật bạn có thể dùng, đầu tiên là code specialization.
The idea here is that instead of having, like, in C++, when you have these sort of built-in sort runners, you pass in a function to your comparison, you pass a pointer to your comparison function, and any time the sort algorithm says, I got to compare two keys, it makes a call to that function.
Ý tưởng ở đây là thay vì, ví dụ trong C++, khi bạn có những hàm sắp xếp dựng sẵn như thế này, bạn truyền vào một hàm để so sánh, bạn truyền một con trỏ tới hàm so sánh của mình, và mỗi khi thuật toán sắp xếp nói rằng, tôi cần so sánh hai khóa, nó sẽ gọi hàm đó.
Well, that can be expensive, especially if you're trying to interpret what the bytes are in your keys.
Điều đó có thể tốn kém, đặc biệt nếu bạn phải diễn giải xem các byte trong khóa của mình là gì.
We have to go look in the catalog and say, oh, am I sorting integers, am I sorting strings, and so forth, right?
Chúng ta phải tra trong catalog và xem, à, mình đang sắp xếp số nguyên, hay đang sắp xếp chuỗi, và vân vân, đúng không?
So, a better approach is that if you can pre-generate a bunch of hard-coded versions of your comparison function that sorts keys on a certain type, then you can now inline that in your sorting algorithm, and then it's much faster because now you're not doing the jump call in your CPU to jump to some other location in your address space and call your sorting function.
Vì vậy, một cách tốt hơn là nếu bạn có thể tạo sẵn một loạt phiên bản được viết cứng của hàm so sánh để sắp xếp các khóa theo một kiểu nhất định, thì bạn có thể inline nó vào thuật toán sắp xếp, và khi đó nó nhanh hơn nhiều vì CPU không còn phải thực hiện lệnh nhảy tới một vị trí khác trong không gian địa chỉ để gọi hàm sắp xếp của bạn nữa.
And then you don't have to worry also, too, like, how to figure out what the bytes are. You just call, you know, reinterpret cast because you know exactly what the data should look like.
Và bạn cũng không phải bận tâm nữa về việc làm sao xác định các byte là gì. Bạn chỉ cần gọi, bạn biết đấy, reinterpret cast vì bạn biết chính xác dữ liệu trông như thế nào.
So, there's a bunch of different ways to do this. One is you can do code generation or just-in-time compilation on the fly.
Có nhiều cách khác nhau để làm điều này. Một cách là sinh mã hoặc biên dịch just-in-time ngay khi chạy.
So, some systems, like SingleStore from a few weeks ago, they will, When your query shows up and you want to sort it on some keys, they will then code gen the comparison function in, like, LLVM and compile that to machine code, and then now you're making a function call into machine code that's sort of hard-coded for exactly comparison to keys.
Một số hệ thống, như SingleStore mà chúng ta học vài tuần trước, sẽ như sau, khi truy vấn của bạn đến và bạn muốn sắp xếp theo một số khóa, họ sẽ sinh mã cho hàm so sánh bằng, chẳng hạn, LLVM và biên dịch nó ra mã máy, và khi đó bạn gọi hàm vào đoạn mã máy được viết cứng đúng cho việc so sánh các khóa đó.
Postgres kind of does this, too. It's a bit of a hack, but, like, it's written in C, so you have to deal with this.
Postgres cũng làm điều này phần nào. Nó hơi là một mẹo, nhưng nó được viết bằng C, nên bạn phải xử lý như vậy.
So, in Postgres, if you compile it by hand, instead of downloading the binaries, compile the binary by source, compile it from the source, there's a Perl script that runs before you compile it that takes their comparison function and then makes a bunch of copies of it that have different versions for different data types.
Trong Postgres, nếu bạn tự biên dịch thay vì tải các bản nhị phân về, biên dịch bản nhị phân từ mã nguồn, có một script Perl chạy trước khi bạn biên dịch, nó lấy hàm so sánh của họ rồi tạo ra nhiều bản sao của hàm đó với các phiên bản khác nhau cho các kiểu dữ liệu khác nhau.
So, they'll have a comparison function for integers, a comparison function for floats, and it basically is duplicating the code and then compiling it into the binary, and then at runtime it knows which sort of specialized version of the sorting algorithm they should use.
Họ sẽ có một hàm so sánh cho số nguyên, một hàm so sánh cho số thực, về cơ bản là nhân đôi mã rồi biên dịch vào bản nhị phân, và khi chạy, hệ thống biết nên dùng phiên bản chuyên biệt nào của thuật toán sắp xếp.
It's basically templating, but it's because they're in C and not C++, they have to sort of do this little Perl script hack. Another trick you can do is called suffix truncation.
Về cơ bản đó là templating, nhưng vì họ dùng C chứ không phải C++, nên họ phải dùng cái mẹo script Perl nhỏ này. Một thủ thuật khác là cắt bớt hậu tố (suffix truncation).
I think we talked about this when we talked about varchars before, but basically instead of doing the sort of the full key comparison of two strings, you're basically iterating over every byte and doing one-by-one comparisons, you can pre-compute a prefix of the varchar as the key, like think of a 32-bit integer,
Tôi nghĩ chúng ta đã nói về điều này khi nói về varchar trước đây, nhưng về cơ bản, thay vì so sánh toàn bộ khóa của hai chuỗi, bạn phải duyệt qua từng byte và so sánh từng byte một, bạn có thể tính trước một tiền tố của varchar để làm khóa, chẳng hạn như một số nguyên 32 bit,
and then now I can do fast comparisons to see whether those two prefixes are the same.
và khi đó tôi có thể so sánh nhanh để xem hai tiền tố đó có giống nhau hay không.
If no, then I know how to do easy comparisons to see whether one value is less than another, and that's way faster than having to look at the full key.
Nếu không, thì tôi biết cách so sánh đơn giản để xem giá trị này có nhỏ hơn giá trị kia hay không, và cách đó nhanh hơn rất nhiều so với việc phải xét toàn bộ khóa.
If the two prefixes are the same, then I fall back to doing the slower comparison. And this one is a bit more nuanced. It's an old technique from the 70s.
Nếu hai tiền tố giống nhau, thì tôi quay lại dùng phép so sánh chậm hơn. Còn kỹ thuật này thì phức tạp hơn một chút. Đây là một kỹ thuật cũ từ những năm 70.
It's actually in the DuckDB article that came out last week, but basically, if you have varchars, you don't want to have these arbitrary length size keys, because I'm trying to keep everything nice, tightly packed and always be fixed length.
Thực ra nó có trong bài viết của DuckDB mới ra tuần trước, nhưng về cơ bản, nếu bạn có các varchar, bạn không muốn có những khóa với độ dài tùy ý như vậy, vì tôi đang cố giữ mọi thứ thật gọn gàng, được đóng gói chặt và luôn có độ dài cố định.
So if I can keep everything as dictionary codes, great, but not always.
Nên nếu tôi giữ được mọi thứ ở dạng mã từ điển thì tốt, nhưng không phải lúc nào cũng vậy.
I can't always do that, especially if the same column comes from different files that may have different dictionary codes with the same values.
Tôi không thể luôn làm vậy, nhất là khi cùng một cột đến từ các tệp khác nhau mà có thể có các mã từ điển khác nhau cho cùng những giá trị.
So they have a way to normalize all this by transforming any arbitrary length key into a sort of binary representation.
Vì vậy họ có cách chuẩn hóa tất cả bằng việc biến đổi khóa có độ dài tùy ý thành một dạng biểu diễn nhị phân.
You do a little padding to make sure everything's always fixed length, and then I can do fast comparisons on that.
Bạn thêm một chút phần đệm để đảm bảo mọi thứ luôn có độ dài cố định, và sau đó tôi có thể so sánh nhanh trên dạng đó.
Again, just to point out here, we'll cover more of this in the advanced class, but just checking to see whether one value is less than another value, that actually is expensive at scale, and especially if you're doing it a lot.
Một lần nữa, xin lưu ý ở đây, chúng ta sẽ nói kỹ hơn trong lớp nâng cao, nhưng chỉ việc kiểm tra xem một giá trị có nhỏ hơn giá trị khác hay không thực ra là tốn kém ở quy mô lớn, nhất là khi bạn làm điều đó rất nhiều.
Whereas something like your algorithms, intro to algorithms class, they'll be very hand-wavy over this because they're not worried about actually working on real data.
Trong khi đó, như trong lớp thuật toán, nhập môn thuật toán của các bạn, họ sẽ nói rất qua loa về chuyện này vì họ không bận tâm đến việc làm việc trên dữ liệu thực tế.
All right, so sort of what they were asking about, like, can I just use the index?
Được rồi, vậy điều mà họ đã hỏi, đó là, tôi có thể chỉ dùng chỉ mục không?
Again, external merge sort or the in-memory sorting algorithms, we need to do this if there isn't a data structure we can use, our B+tree.
Một lần nữa, external merge sort hay các thuật toán sắp xếp trong bộ nhớ, chúng ta cần làm vậy nếu không có cấu trúc dữ liệu nào để dùng, tức là B+tree của chúng ta.
We can't use a hash table, because a hash table's unsorted, but if we do have a sorted data structure, then we can take advantage of that in some cases by just scanning along the leaf nodes for the data, assuming that it's sorted on that key, and then we can get the data that we want.
Chúng ta không thể dùng bảng băm, vì bảng băm không có thứ tự, nhưng nếu chúng ta có một cấu trúc dữ liệu đã được sắp xếp, thì trong một số trường hợp ta có thể tận dụng nó bằng cách chỉ quét dọc theo các nút lá để lấy dữ liệu, giả sử nó được sắp xếp theo khóa đó, và rồi ta lấy được dữ liệu mình muốn.
Now the challenge is going to be, since the keys in the B+tree may not actually be the full tuple, And if we need the full tuple as part of the output of the query, we've got to go then get that data.
Thách thức ở đây sẽ là, vì các khóa trong B+tree có thể không phải là toàn bộ tuple, và nếu chúng ta cần toàn bộ tuple làm một phần kết quả đầu ra của truy vấn, thì chúng ta phải đi lấy dữ liệu đó.
And the challenge is going to be, in that case, that the data might be stored in our table pages in a manner that's different than what's defined in the index.
Và thách thức trong trường hợp đó là dữ liệu có thể được lưu trong các trang bảng của chúng ta theo cách khác với thứ tự được định nghĩa trong chỉ mục.
So the index could help us for maybe finding a subset of the data more quickly, but if we've got to go fetch the data, we're going to have to put it back in the correct sorted order anyway, and that could be a bunch of random IO, which could kill us.
Vì vậy chỉ mục có thể giúp ta tìm một tập con dữ liệu nhanh hơn, nhưng nếu phải đi lấy dữ liệu, thì dù sao ta cũng phải sắp xếp lại đúng thứ tự, và đó có thể là cả loạt IO ngẫu nhiên, điều có thể làm chúng ta chậm đi rất nhiều.
So if we have a clustered B+tree, again where the tuple pages, the tuples themselves, are in the same sort order as defined on your B+tree, fantastic.
Còn nếu chúng ta có một B+tree phân cụm, tức là các trang tuple, chính các tuple, có cùng thứ tự sắp xếp như được định nghĩa trên B+tree của bạn, thì tuyệt vời.
Then we don't want to use external merge sort or any sort of algorithm, because we just rip along the leaf nodes. That's sequential access, and everything's sorted already in the way that we want.
Thì chúng ta không muốn dùng external merge sort hay bất kỳ thuật toán sắp xếp nào, vì chúng ta chỉ cần duyệt thẳng dọc các nút lá. Đó là truy cập tuần tự, và mọi thứ đã được sắp xếp sẵn theo đúng thứ tự mình muốn.
That's fine.
Như vậy là ổn.
If it's unclustered, then having to chase pointers to go get the tuples as defined in the ordering of the keys in the leaf pages, and then putting that back into the order that we want as part of our output, that's actually going to be terrible in the general case, because again, it's a bunch of random IOs in different pages.
Còn nếu là unclustered, thì việc phải lần theo các con trỏ để lấy các tuple theo thứ tự của các khóa trong các trang lá, rồi sắp xếp lại chúng theo thứ tự mà ta muốn cho kết quả đầu ra, thì trong trường hợp tổng quát sẽ rất tệ, vì lại là hàng loạt IO ngẫu nhiên trên các trang khác nhau.
And I can't do that trick we talked about before, where I can sort the pages that I want to access so that I'm only fetching one page at a time, because it has to be in the order that's defined by the ORDER BY clause or whatever the ordering requires.
Và tôi không thể dùng mẹo mà chúng ta đã nói trước đó, là sắp xếp các trang mà tôi cần truy cập để mỗi lần chỉ lấy một trang, vì thứ tự phải theo đúng mệnh đề ORDER BY quy định hoặc bất kỳ yêu cầu sắp xếp nào khác.
Then this is going to be random IO, and it's going to be terrible for us, and we just want to fall back to doing the external merge sort.
Khi đó đây sẽ là IO ngẫu nhiên, và nó sẽ rất tệ cho chúng ta, nên ta chỉ cần quay về dùng external merge sort.
If you're doing top N, where I know I only need N number of queries, or sorry, N number of tuples in my query, then this might be okay because I might be getting like 10 pages at most.
Nếu bạn làm top N, tức là tôi biết mình chỉ cần N truy vấn, à xin lỗi, N tuple trong truy vấn của mình, thì cách này có thể chấp nhận được vì tôi có thể chỉ lấy tối đa khoảng 10 trang.
That's not so bad, but anything else, this is not going to be great. Okay?
Như vậy không tệ lắm, nhưng với mọi trường hợp khác thì không ổn. Được chứ?
So again, if it's in memory, use your favorite sorting algorithm. If it's a limit, if it's an order by clause with a limit, then use the top N heap sort.
Vậy nhắc lại, nếu dữ liệu nằm trong bộ nhớ, hãy dùng thuật toán sắp xếp bạn thích nhất. Nếu là mệnh đề ORDER BY có kèm limit, thì dùng top N heap sort.
If anything else, if it's too large, then I want to fall back to external merge sort.
Còn mọi trường hợp khác, nếu dữ liệu quá lớn, thì tôi muốn quay về dùng external merge sort.
All right, so let's finish up talking about aggregations. Yeah, go ahead, yes.
Được rồi, giờ ta kết thúc phần nói về aggregation. Vâng, bạn hỏi đi.
The question is, B+trees are stored in disk? For this class, yes.
Câu hỏi là, B+tree có được lưu trên đĩa không? Với môn này thì có.
Some systems don't, but this class, yes. Postgres, yes. Most systems, yes.
Một số hệ thống thì không, nhưng với môn này thì có. Postgres thì có. Hầu hết các hệ thống đều có.
No, so the statement is, the question is, are we assuming that the B+tree cannot be stored in disk, not entirely in main memory? No. It could, right, if the buffer pool has enough space.
Không, ý bạn là, câu hỏi là, chúng ta có giả định rằng B+tree không thể lưu trên đĩa, tức là không nằm hoàn toàn trong bộ nhớ chính không? Không. Nó có thể nằm hết trong bộ nhớ, nếu buffer pool có đủ chỗ.
And then there's a whole bunch of, like, policies you could set. Do I want to make sure that my buffer, my B+trees always fit memory and prioritize them over the tuple pages?
Và có cả một loạt chính sách mà bạn có thể thiết lập. Tôi có muốn đảm bảo các B+tree của mình luôn nằm vừa trong bộ nhớ và ưu tiên chúng hơn các trang tuple không?
Some systems let you do that. Right? Depends. I know, again, I keep saying it's a cop-out. It depends on, like, what your workload is, what your hardware is.
Một số hệ thống cho phép làm vậy. Đúng không? Tùy trường hợp. Tôi biết, tôi cứ nói đi nói lại đó là câu trả lời né tránh. Nó phụ thuộc vào khối lượng công việc của bạn là gì, phần cứng của bạn ra sao.
All right, so aggregations, again, this goes back, again, to the earlier in the semester where the idea is that we want to scan some data and produce scalar results for some kind of computation based on, you know, across multiple tuples that we see.
Được rồi, vậy aggregation, điều này lại quay về phần đầu học kỳ, khi ý tưởng là ta muốn quét một số dữ liệu và tạo ra các kết quả vô hướng cho một phép tính nào đó dựa trên nhiều tuple mà ta thấy.
Right?
Đúng không?
So the challenge is that in order to do some of these aggregations, I want to quickly find tuples that match on, you know, like a group by clause or some other aspect of the aggregation I'm trying to compute.
Thách thức là để thực hiện một số aggregation này, tôi muốn nhanh chóng tìm các tuple khớp nhau theo mệnh đề group by chẳng hạn, hoặc một khía cạnh nào đó khác của phép aggregation mà tôi đang cố tính.
So to do this, As I said in the beginning, there's basically two approaches. There's sort of two classes of algorithms we can use to do aggregations and joins for the next class.
Để làm điều này, như tôi đã nói ở đầu, về cơ bản có hai cách tiếp cận. Có hai lớp thuật toán chúng ta có thể dùng để thực hiện phép tổng hợp và phép nối trong buổi học tiếp theo.
It's sorting and hashing. And this is like the age-old debate that goes back to the 1970s in database systems: which of these two approaches is better?
Đó là sắp xếp và băm. Và đây là cuộc tranh luận từ xa xưa có từ những năm 1970 trong lĩnh vực hệ cơ sở dữ liệu: cách tiếp cận nào trong hai cách này tốt hơn?
And it goes back and forth. Originally, sorting was faster in the 70s. Then hardware got better and hashing got faster. And then the sorting algorithms got better, and then sorting got better.
Và nó cứ thay đổi qua lại. Ban đầu, vào thập niên 70, sắp xếp nhanh hơn. Sau đó phần cứng tốt hơn và băm trở nên nhanh hơn. Rồi các thuật toán sắp xếp được cải tiến, và sắp xếp lại tốt hơn.
Sorting was considered the preferred choice. But now, in general, with today's hardware and today's landscape, hashing almost always is going to be the better approach.
Sắp xếp từng được coi là lựa chọn ưu tiên. Nhưng bây giờ, nói chung, với phần cứng và bối cảnh ngày nay, băm hầu như luôn là cách tiếp cận tốt hơn.
In some cases, except when, as we'll see in a second, the data needs to be sorted because there's an ORDER BY clause, then I can just piggyback off of that sorting in some cases and do my aggregation.
Trừ một số trường hợp, như chúng ta sẽ thấy ngay sau đây, khi dữ liệu cần được sắp xếp vì có mệnh đề ORDER BY, thì trong một số trường hợp tôi có thể tận dụng luôn việc sắp xếp đó để thực hiện phép tổng hợp.
But in general, hashing is always going to be better if your disk is slow. So let's say I have a query like this.
Nhưng nói chung, băm luôn tốt hơn nếu đĩa của bạn chậm. Giả sử tôi có một truy vấn như thế này.
SELECT with a DISTINCT clause from the enroll table, where I want to get all the records where the grades are either B and C, and I want to order by the course ID.
SELECT với mệnh đề DISTINCT từ bảng enroll, trong đó tôi muốn lấy tất cả các bản ghi mà điểm là B hoặc C, và tôi muốn sắp xếp theo mã môn học.
So again, think of this as that tree data structure we saw before, but I'm showing this sort of a sequential ordering. But I'm scanning the enroll table. I do a filter.
Một lần nữa, hãy hình dung đây là cấu trúc dữ liệu cây mà chúng ta đã thấy trước đây, nhưng tôi đang biểu diễn nó dưới dạng thứ tự tuần tự. Tôi quét bảng enroll. Tôi áp dụng một bộ lọc.
I throw away the tuples that don't match the grade that I'm looking for. And then I'll do a projection and remove the columns that I don't need in my output.
Tôi loại bỏ các tuple không khớp với điểm mà tôi đang tìm. Sau đó tôi thực hiện phép chiếu và loại bỏ các cột mà tôi không cần trong đầu ra.
So in this case here, I only need the course ID, so I can throw away everything else.
Trong trường hợp này, tôi chỉ cần mã môn học, nên có thể bỏ mọi thứ còn lại.
And now I'm going to sort it based on what's defined in my ORDER BY clause, sorting on the course ID.
Và bây giờ tôi sẽ sắp xếp dựa trên những gì được định nghĩa trong mệnh đề ORDER BY, tức là sắp xếp theo mã môn học.
And then the last step in my query plan is I want to remove the duplicates because I want it DISTINCT.
Và bước cuối cùng trong kế hoạch truy vấn là loại bỏ các bản ghi trùng lặp vì tôi muốn kết quả DISTINCT.
So in this case here, with my sort of output, all I need to do is have a cursor or an iterator to scan through sequentially in this output, and anytime I see a record that is the same as the last one I just looked at, then I know I can ignore it and discard it.
Vậy trong trường hợp này, với đầu ra đã được sắp xếp, tất cả những gì tôi cần là một con trỏ hoặc một iterator để quét tuần tự qua đầu ra này, và bất cứ khi nào tôi thấy một bản ghi giống với bản ghi vừa xem trước đó, thì tôi biết có thể bỏ qua và loại bỏ nó.
Because again, you know, because it's in sorted order, I've got to get to the bottom for 15-826, I'm not going to see 4-45 again, because 8-26 is greater than 4-45 and I've already passed that part here.
Bởi vì, như bạn thấy, do dữ liệu đã được sắp xếp, khi tôi đã đến 15-826 ở phía dưới, tôi sẽ không thấy lại 4-45 nữa, vì 8-26 lớn hơn 4-45 và tôi đã đi qua phần đó rồi.
So for distinct, this is pretty easy. And again, they wanted the data ordered on the course ID anyway, so I just piggyback off of that sorting to do my duplicate elimination.
Vậy với distinct, việc này khá dễ. Và dù sao họ cũng muốn dữ liệu được sắp xếp theo mã môn học, nên tôi tận dụng luôn việc sắp xếp đó để loại bỏ trùng lặp.
I don't have to build a separate hash table to do that. For other things, it can be more tricky.
Tôi không phải xây dựng một bảng băm riêng để làm việc đó. Với những trường hợp khác, nó có thể phức tạp hơn.
But even if you don't want the data sorted, you make still the data system will still could still decide to do sorting-based aggregation. Not always, but some will.
Nhưng ngay cả khi bạn không muốn dữ liệu được sắp xếp, hệ thống cơ sở dữ liệu vẫn có thể quyết định thực hiện phép tổng hợp dựa trên sắp xếp. Không phải lúc nào cũng vậy, nhưng một số hệ thống sẽ làm thế.
So again, so now we have a different query. I want to get the average GPA of all the students enrolled in certain courses.
Vậy bây giờ chúng ta có một truy vấn khác. Tôi muốn lấy điểm GPA trung bình của tất cả sinh viên đăng ký một số môn học nhất định.
So assuming I've already done my join, we'll talk about next class how we actually do that. So I have now a bunch of course IDs and then the student GPAs.
Giả sử tôi đã thực hiện xong phép join, buổi sau chúng ta sẽ nói cách thực hiện việc đó. Vậy giờ tôi có một loạt mã môn học và điểm GPA của sinh viên.
So I'll sort my data based on the course IDs, and then now again I'll just scan through my data and then compute a running total of whatever the aggregation function that it wants.
Tôi sẽ sắp xếp dữ liệu theo mã môn học, rồi lại quét qua dữ liệu và tính một tổng cộng dồn cho hàm tổng hợp mà nó yêu cầu.
So what I'm showing here at the top is the way you basically do this. It's pretty straightforward, right? For min and max, you just keep track of the largest, smallest value I've seen.
Những gì tôi trình bày ở phía trên là cách bạn làm việc này. Khá đơn giản phải không? Với min và max, bạn chỉ cần theo dõi giá trị lớn nhất, nhỏ nhất đã thấy.
So the count is adding one to a counter. Summation is adding things.
Count là cộng thêm một vào bộ đếm. Summation là cộng các giá trị lại.
In the case of average, You just keep a running total of the summation of the column and the number of records you've seen, and then you just divide it at the end and it produces the mean.
Với trường hợp average, bạn chỉ cần giữ tổng cộng dồn của cột và số bản ghi đã thấy, rồi cuối cùng chia ra là được giá trị trung bình.
For arithmetic mean. For geometric mean it's more complicated, but we can control that. So in this case here, my iterator starts.
Đó là trung bình cộng. Với trung bình nhân thì phức tạp hơn, nhưng chúng ta vẫn xử lý được. Trong trường hợp này, iterator của tôi bắt đầu.
I keep track of the last key that I've seen, because I know they're going to be in sorted order, so it's the last course ID I've seen.
Tôi theo dõi khóa cuối cùng đã thấy, vì tôi biết chúng sẽ theo thứ tự đã sắp xếp, tức là mã môn học cuối cùng đã thấy.
At the beginning it's null, and then I have my first record. I have a counter that says that I've seen one tuple so far, and here's the running sum of the GPA.
Ban đầu nó là null, rồi tôi có bản ghi đầu tiên. Tôi có một bộ đếm cho biết đến giờ đã thấy một tuple, và đây là tổng GPA cộng dồn.
Then I set my previous to 15-445. Come down here, I see the same key again, 15-445. So I just update my running total, increment the counter by one, add the GPA to the summation.
Sau đó tôi đặt previous là 15-445. Xuống đây, tôi lại thấy cùng khóa 15-445. Nên tôi chỉ cập nhật tổng cộng dồn, tăng bộ đếm lên một, và cộng GPA vào tổng.
Go down here, now I see a key that doesn't match my previous one that I've seen.
Xuống tiếp, giờ tôi thấy một khóa không khớp với khóa trước đó.
So at this point here I know I'm never going to see 15-445 ever again in my sorted output, so I can take this, whatever I computed here, do the math, divide the summation by the count, and then store the GPA in my computed result here.
Đến đây tôi biết mình sẽ không bao giờ thấy 15-445 nữa trong đầu ra đã sắp xếp, nên tôi có thể lấy những gì đã tính ở đây, tính toán, chia tổng cho số đếm, rồi lưu GPA vào kết quả đã tính ở đây.
Same thing, update the previous key that I've seen. Get down here, it's not matching, 826 doesn't equal 721, so I put 15-721 here.
Tương tự, cập nhật khóa trước đó đã thấy. Xuống đây, không khớp, 826 không bằng 721, nên tôi đặt 15-721 vào đây.
Do the same thing till I reach the bottom and I know I'm done, and then I put my output there. Pretty straightforward.
Làm tương tự cho đến khi tới cuối và biết là đã xong, rồi tôi đặt đầu ra vào đó. Khá đơn giản.
Window functions are a bit more tricky; we can cover that next class if we have time.
Window function phức tạp hơn một chút; nếu còn thời gian, buổi sau chúng ta sẽ nói đến.
So the alternative to sorting is going to be hashing.
Giải pháp thay thế cho sắp xếp là hashing.
So if we don't need the data to be sorted, oftentimes hashing is going to be much better, and the basic idea is that we're going to build hash tables or divide our data into partitions based on hash functions.
Nếu chúng ta không cần dữ liệu được sắp xếp, thì hashing thường sẽ tốt hơn nhiều, và ý tưởng cơ bản là chúng ta sẽ xây dựng các bảng băm hoặc chia dữ liệu thành các phân vùng dựa trên hàm băm.
And again, it's going to be a divide and conquer approach where we can generate smaller subsets of the data that we want so that we can keep things in memory and not have to do as much random IO.
Và đó lại là cách tiếp cận chia để trị nơi chúng ta có thể tạo ra các tập con dữ liệu nhỏ hơn mà chúng ta muốn để có thể giữ dữ liệu trong bộ nhớ và không phải thực hiện quá nhiều IO ngẫu nhiên.
So for hashing aggregation, you basically build a hash table in memory, and as you're scanning through the data, you just update entries in that hash table when you have matches.
Vậy với hashing aggregation, về cơ bản bạn xây dựng một bảng băm trong bộ nhớ, và khi bạn quét qua dữ liệu, bạn chỉ cần cập nhật các mục trong bảng băm đó khi có khớp.
And if the hash table doesn't fit in memory, then we'll have to do sort of recursive partitioning, or do partitioning, and we'll see how to do that in a second.
Và nếu bảng băm không vừa trong bộ nhớ, thì chúng ta sẽ phải chia phân vùng đệ quy, hay nói chung là chia phân vùng, và ta sẽ xem cách làm điều đó ngay sau đây.
Oh shit, sorry. Let me just mute that.
Ôi trời, xin lỗi. Để tôi tắt tiếng cái đó.
Okay, sorry. All right, here we go, sorry. All right. Let me make sure they can hear me.
Được rồi, xin lỗi. Nào, bắt đầu nhé, xin lỗi. Được rồi. Để tôi kiểm tra xem họ có nghe được tôi không.
I don't want to jump this yet, but they want to know when I'm done. I think I'm unmuted, right? I can't see. Am I muted or no? All right, I'm muted.
Tôi chưa muốn chuyển qua phần này, nhưng họ muốn biết khi nào tôi xong. Tôi bật tiếng rồi đúng không? Tôi không nhìn thấy. Tôi đang tắt tiếng hay không? Được rồi, tôi đang tắt tiếng.
All right, sorry. All right. So a hashing aggregate, again, we maintain this hash table. We'll populate it as we go along, and then if everything fits in memory, it's easy.
Được rồi, xin lỗi. Được rồi. Vậy với hashing aggregate, một lần nữa, ta duy trì bảng băm này. Ta sẽ điền dữ liệu vào dần dần, và nếu mọi thứ vừa trong bộ nhớ thì rất dễ.
If not, we have to handle that.
Nếu không, ta phải xử lý trường hợp đó.
If it doesn't fit in memory, then we have to do what's called external hashing aggregation, where we're going to take a pass over the data, use one hash function to split it up into partitions, then bring those partitions one at a time into memory, and then that's going to be sequential IO, and do whatever it is, the aggregation I want to compute, produce some hash table,
Nếu nó không vừa trong bộ nhớ, thì ta phải làm cái gọi là external hashing aggregation, trong đó ta sẽ duyệt qua dữ liệu một lượt, dùng một hàm băm để chia nó thành các phân vùng, rồi đưa từng phân vùng một vào bộ nhớ, và đó sẽ là IO tuần tự, rồi thực hiện phép tổng hợp mà tôi muốn tính, tạo ra một bảng băm nào đó,
and then when I'm done with that partition, swap out to the next partition.
và khi xong với phân vùng đó, ta hoán đổi sang phân vùng tiếp theo.
So this is repeating what I said in the first phase: you partition things up, you can now do a sequential scan on the data, hash it once, figure out what bucket it goes to, or partition of buckets it goes to, then the second pass, I'll bring those partitions in one by one and do whatever the computation I need.
Đây là lặp lại điều tôi đã nói ở pha đầu: bạn chia dữ liệu thành các phân vùng, giờ bạn có thể quét tuần tự dữ liệu, băm một lần, xác định nó thuộc bucket nào, hoặc phân vùng gồm các bucket nào, rồi ở lượt thứ hai, tôi sẽ đưa từng phân vùng vào và thực hiện bất kỳ phép tính nào cần thiết.
So let's look at that example again where I want to run the DISTINCT clause on the roll table. So again, do my filter, that's all fine. Do a projection, that's all fine.
Vậy hãy xem lại ví dụ đó trong đó tôi muốn chạy mệnh đề DISTINCT trên bảng roll. Vậy, vẫn thực hiện lọc, không vấn đề gì. Thực hiện phép chiếu, cũng không vấn đề gì.
But then now I'm going to scan through this intermediate output here, and for every single key, I'm going to hash it, put it into one of these partitions, which can be a series of pages.
Nhưng bây giờ tôi sẽ quét qua kết quả trung gian này, và với từng khóa một, tôi sẽ băm nó, đặt nó vào một trong các phân vùng này, mỗi phân vùng có thể là một chuỗi các trang.
And assuming I have B-1 partitions I could use, I could have that much space, because I could bring in one of these pages at a time over here, but then I'm going to write it out to B-1 pages over here.
Và giả sử tôi có B-1 phân vùng để dùng, tức là có chừng đó không gian, vì tôi có thể đưa từng trang một vào bên này, nhưng rồi tôi sẽ ghi nó ra B-1 trang ở bên này.
So this is the opposite of what we saw with the sorted runs, where my input is larger and my output is one.
Vậy đây là ngược lại với những gì ta thấy ở các sorted run, nơi đầu vào lớn hơn và đầu ra chỉ có một.
In this case here, I want my output to be larger, because I'm trying to split these things up into individual buckets.
Trong trường hợp này, tôi muốn đầu ra lớn hơn, vì tôi đang cố chia những thứ này thành từng bucket riêng.
So in this case here, if this page gets full, then I'm going to just go ahead and write out the disk and just make a new page for it and keep filling that up.
Vậy trong trường hợp này, nếu trang này đầy, thì tôi cứ ghi nó ra đĩa rồi tạo một trang mới cho nó và tiếp tục lấp đầy.
So now in the second phase, I'm going to bring all those pages in from partition one at a time.
Giờ ở pha thứ hai, tôi sẽ đưa tất cả các trang của từng phân vùng một vào.
I can do that in Scrunch.io and then now generate some kind of hash table that's going to build the running total, the aggregation I'm trying to compute, and then when I'm done with that partition, I take whatever the results in that hash table and I put it to some kind of final result buffer.
Tôi có thể làm điều đó trong Scrunch.io và sau đó tạo ra một bảng băm nào đó để xây dựng tổng cộng dồn, tức là phép tổng hợp mà tôi đang muốn tính, và khi xong với partition đó, tôi lấy bất kỳ kết quả nào có trong hash table đó và đưa nó vào một bộ đệm kết quả cuối cùng nào đó.
So going back here. So these are the buckets I generated before. So in partition zero, I had two pages. Partition one had one page and so forth like that.
Quay lại đây. Đây là các bucket mà tôi đã tạo ra lúc trước. Ở partition 0, tôi có hai trang. Partition 1 có một trang, và cứ thế tiếp tục.
So I started the first partition. I'm just going to scan through sequentially. In this case here, I'm computing DISTINCT, so it's pretty obvious.
Vậy tôi bắt đầu với partition đầu tiên. Tôi sẽ quét tuần tự qua nó. Ở đây tôi đang tính DISTINCT nên khá là rõ ràng.
Like I do a hash, I land in my hash table, and if there's no entry there for my key, I put it there. Otherwise, I just ignore it. Then I do the same thing.
Tôi băm, rồi rơi vào một vị trí trong hash table, và nếu chưa có mục nào cho khóa của tôi ở đó thì tôi đặt nó vào. Nếu không thì tôi bỏ qua. Sau đó tôi làm tương tự.
I scan through all these entries doing the same thing, hashing over and over again. I keep seeing the same key so that there's nothing else to add.
Tôi quét qua tất cả các mục này, làm đi làm lại cùng một việc là băm. Tôi cứ gặp lại cùng một khóa nên không có gì để thêm nữa.
And then now when I'm finished with that partition, if I assume that my data is going to be really big, I could take whatever is in this hash table, write it out to a result buffer and then clear this hash table for the next partition.
Và khi tôi đã xong với partition đó, nếu giả sử dữ liệu của tôi rất lớn, tôi có thể lấy mọi thứ trong hash table này, ghi ra một bộ đệm kết quả rồi xóa hash table này để dùng cho partition tiếp theo.
Because again, I've already divided the data up so that when I'm at partition level one, I'm never going to see 15,445 again because there's no way it could have gotten to that level when I hashed it, because again, the same key will always have the same hash value so they end up at the same partition level.
Bởi vì, một lần nữa, tôi đã chia dữ liệu ra sao cho khi ở partition mức một, tôi sẽ không bao giờ gặp lại 15,445 vì khi băm thì không thể nào nó lại rơi vào mức đó, vì cùng một khóa luôn có cùng một giá trị băm nên chúng sẽ nằm ở cùng một partition.
So I'll never see 15,445 ever again once I finish that. What's that?
Vậy nên khi xong thì tôi sẽ không bao giờ thấy lại 15,445. Gì vậy?
Can I guarantee that the hash table here is going to fit in memory? Does it fit in a single page?
Liệu tôi có thể đảm bảo hash table ở đây vừa trong bộ nhớ không? Nó có vừa trong một trang không?
No, you can't guarantee that, but you would say you would have some kind of approximation of how big it should actually be.
Không, bạn không thể đảm bảo được, nhưng bạn sẽ có một ước lượng nào đó về kích thước thực sự của nó.
If I have a billion keys and it takes petabytes, then that's a problem. But any algorithm is going to break down if you do that.
Nếu tôi có một tỉ khóa và nó tốn hàng petabyte thì đó là vấn đề. Nhưng thuật toán nào cũng sẽ hỏng nếu bạn làm vậy.
So at this point here, then I take the next key, I'm going to hash it again.
Đến đây, tôi lấy khóa tiếp theo và băm nó lại.
The hash function we're using here at this second pass has to be different than the other one because we want to spread things around. Because you can...
Hàm băm mà ta dùng ở lượt thứ hai này phải khác với hàm kia vì ta muốn phân tán dữ liệu ra. Bởi vì bạn có thể...
In this case here, it's simplified where there's only one key per level but you could have multiple keys end up at the same level.
Ở đây ví dụ được đơn giản hóa, chỉ có một khóa mỗi mức, nhưng bạn có thể có nhiều khóa cùng rơi vào một mức.
And so the first hash function put it into the same partition.
Và hàm băm đầu tiên đã đưa chúng vào cùng một partition.
So I want to use a different hash function when I build this hash table so that different keys don't then end up hashing to the same thing again.
Nên tôi muốn dùng một hàm băm khác khi xây dựng hash table này để các khóa khác nhau không lại băm ra cùng một giá trị.
Yes? If they collide, then it's okay because I just do linear probing in my hash table. Yeah, assume this is a linear probing hash table. All right, so then same thing.
Vâng? Nếu chúng va chạm thì không sao, vì tôi chỉ cần dò tuyến tính trong hash table. Vâng, giả sử đây là hash table dò tuyến tính. Được rồi, vậy là lại như cũ.
I get to this next partition here. I can write out the contents of this, blow away the contents of my hash table. Again, you don't have to delete the pages and start over.
Tôi đến partition tiếp theo này. Tôi có thể ghi nội dung này ra, rồi xóa sạch nội dung hash table. Một lần nữa, bạn không cần xóa các trang rồi bắt đầu lại.
You just set a flag and say ignore everything you ever see afterwards. Like, basically zero it out. And then do the same thing. Produce this final result.
Bạn chỉ cần đặt một cờ và nói là bỏ qua mọi thứ nhìn thấy sau đó. Về cơ bản là xóa sạch nó về 0. Rồi làm lại y như vậy. Tạo ra kết quả cuối cùng.
Once I'm done scanning all my hash buckets, then I know I've completed my final result and I'm done.
Khi quét xong toàn bộ các hash bucket, thì tôi biết là mình đã hoàn thành kết quả cuối cùng và xong việc.
Again, we can do the same thing as sorting. We can have this rolling tally of the summation or summarization of the data as we go along.
Một lần nữa, ta có thể làm giống như khi sắp xếp. Ta có thể giữ một tổng cộng dồn của phép tính tổng hoặc phần tổng hợp dữ liệu trong khi xử lý.
Basically it works the same way, where I'm just going to scan through the buckets that I produced after the first phase and then just do, again, whatever hash function I have now the second time around, and compute the same kind of running total in my final result.
Về cơ bản nó hoạt động theo cùng một cách, trong đó tôi chỉ quét qua các bucket mà tôi đã tạo ra sau pha đầu tiên rồi cứ thế áp dụng, một lần nữa, bất kỳ hàm băm nào tôi có ở lần thứ hai này, và tính cùng kiểu tổng cộng dồn đó vào kết quả cuối cùng.
And I would know, again, if I'm done at a given level, I can take whatever this is, compute the final result based on what I'm trying to compute, and produce the final output.
Và tôi cũng sẽ biết, nếu đã xong ở một mức nào đó, tôi có thể lấy thứ này, tính kết quả cuối cùng dựa trên thứ tôi đang muốn tính, và tạo ra đầu ra cuối cùng.
Right? Works the same way, except now I'm reading from a hash table instead of reading from a sorted list.
Đúng không? Nó hoạt động theo cùng một cách, chỉ khác là bây giờ tôi đọc từ một hash table thay vì đọc từ một danh sách đã sắp xếp.
All right. So the main takeaway from all this is that if everything's in memory, sorting can be pretty fast.
Được rồi. Vậy điểm chính rút ra từ tất cả những điều này là nếu mọi thứ đều nằm trong bộ nhớ, việc sắp xếp có thể khá nhanh.
If I have to spill to disk, then I want to use external merge sort to be able to sort things.
Nếu tôi phải tràn xuống đĩa, thì tôi muốn dùng external merge sort để sắp xếp dữ liệu.
If I want to do aggregations, hashing is going to be oftentimes the better approach, and most systems will choose that over that.
Nếu tôi muốn thực hiện các phép tổng hợp, thì băm thường là cách tiếp cận tốt hơn, và hầu hết các hệ thống sẽ chọn cách đó thay vì cách kia.
But the main, again, takeaway from all this is that we've seen some of the same techniques In this class that we've seen in other classes and going forward, where we want to try to convert data into sequential blocks so that we can read it out sequentially and write it out sequentially and read it back in sequentially.
Nhưng điểm chính, một lần nữa, rút ra từ tất cả những điều này là ta đã thấy một số kỹ thuật giống nhau trong môn này với những môn khác, và sau này cũng vậy, đó là ta muốn cố gắng chuyển dữ liệu thành các khối liên tiếp để có thể đọc ra tuần tự và ghi ra tuần tự rồi đọc lại vào cũng tuần tự.
That's going to make the system perform much better because, again, sequential I/O is faster than random I/O.
Điều đó sẽ giúp hệ thống chạy tốt hơn nhiều vì, một lần nữa, I/O tuần tự nhanh hơn I/O ngẫu nhiên.
And then we saw how to use double buffering as a way to hide those disk stalls so that the system can still do useful work while other threads are stalled, or workers are stalled, reading and writing from disk.
Và sau đó ta đã thấy cách dùng double buffering như một cách để che giấu các độ trễ do đĩa để hệ thống vẫn làm được việc hữu ích trong khi các thread khác bị chặn, hay các worker bị chặn, khi đọc và ghi từ đĩa.
And this is why we had to do all that concurrency stuff from last class, to make sure all our data structures are thread safe, because now we know we're going to have multiple threads dancing around in our system trying to manipulate things.
Và đây là lý do ta phải học toàn bộ phần đồng thời ở buổi trước, để đảm bảo mọi cấu trúc dữ liệu của ta đều an toàn với thread, vì giờ ta biết sẽ có nhiều thread chạy qua chạy lại trong hệ thống để thao tác với dữ liệu.
All right, before we switch over to the guest speaker, again, next class will be on joins. This lecture is in the homework and will be on the midterm next week.
Được rồi, trước khi chuyển sang khách mời, một lần nữa, buổi sau sẽ nói về join. Bài giảng này có trong bài tập về nhà và sẽ có trong bài thi giữa kỳ tuần sau.
Next class will not be on the midterm. Thank you. So, thanks, Andy. Thanks, everyone. I cannot see. Hopefully you're happy.
Buổi sau sẽ không có trong bài thi giữa kỳ. Cảm ơn. Cảm ơn nhé, Andy. Cảm ơn mọi người. Tôi không nhìn thấy gì cả. Hy vọng mọi người vui.
So I'm here to talk about MotherDuck. We have about 14 minutes' worth of talking. I don't know if that leaves time for questions or not. My name is Boaz.
Tôi ở đây để nói về MotherDuck. Chúng ta có khoảng 14 phút để trình bày. Không biết có còn thời gian cho câu hỏi hay không. Tên tôi là Boaz.
I'm an engineering tech lead for MotherDuck. I'm based in Amsterdam, as we just discussed.
Tôi là engineering tech lead của MotherDuck. Tôi sống ở Amsterdam, như chúng ta vừa trao đổi.
And what I chose to talk about, with the lens of MotherDuck, is what does it mean, a little bit, of building a cloud data warehouse based on an in-process OLAP database, that I understand you guys are familiar with, DuckDB, but we'll get there.
Và điều tôi chọn để nói hôm nay, qua lăng kính của MotherDuck, là việc này có ý nghĩa gì, đại khái, khi xây dựng một kho dữ liệu đám mây dựa trên một cơ sở dữ liệu OLAP chạy trong tiến trình, mà tôi hiểu là các bạn đã quen thuộc, tức DuckDB, nhưng chúng ta sẽ nói tới sau.
Of course, it's just 14 minutes, so we'll try to a little bit motivate why, because I think that's maybe the most interesting. Why would you even do this?
Tất nhiên chỉ có 14 phút, nên chúng tôi sẽ cố giải thích phần nào lý do, vì tôi nghĩ đó có lẽ là phần thú vị nhất. Tại sao lại làm như vậy?
And give you some insight into how it's done and what is interesting on those various pieces. So let's go.
Và cho các bạn một chút hiểu biết về cách nó được thực hiện và điều gì thú vị ở các phần khác nhau đó. Nào, bắt đầu thôi.
Andy, I don't know how the question and answer is going on, but if someone wants to raise a question and you want to interrupt me, that's fine with me.
Andy, tôi không biết phần hỏi đáp đang diễn ra thế nào, nhưng nếu ai muốn đặt câu hỏi và anh muốn ngắt lời tôi, thì tôi không sao cả.
We'll do it at the end. Okay, perfect.
Chúng ta sẽ làm vào cuối buổi. Được, tuyệt.
All right, so before we go and say why would you use a single load database, I think it's good to take a moment and reflect a little bit on what people do with the cloud data warehouse.
Được rồi, trước khi nói tại sao lại dùng một cơ sở dữ liệu chạy trên một máy đơn, tôi nghĩ nên dành một chút thời gian để nhìn lại xem người ta thực sự làm gì với kho dữ liệu đám mây.
And I think it's Jordan Tigani, which kind of had the idea to start something like MotherDuck in the beginning, and other people that followed, analyzed query patterns, and specifically how much data people actually look at when running the query.
Và tôi nghĩ chính Jordan Tigani là người có ý tưởng ban đầu để bắt đầu một thứ như MotherDuck, cùng những người khác sau đó, đã phân tích các mẫu truy vấn, và cụ thể là người ta thực sự xem bao nhiêu dữ liệu khi chạy một truy vấn.
All right, so people have lots and lots of data sitting in their blob stores or in their S3s. But then the question is, how much do they actually look at actively?
Người ta có rất, rất nhiều dữ liệu nằm trong blob store hay trong S3 của họ. Nhưng câu hỏi là họ thực sự truy cập tích cực bao nhiêu?
And here's a tweet by George Fraser, CEO of Fivetran, looking at two famous datasets, the queries from Snowflake and Redshift.
Và đây là một tweet của George Fraser, CEO của Fivetran, xem xét hai tập dữ liệu nổi tiếng, các truy vấn từ Snowflake và Redshift.
And you can, as you clearly see, the vast, vast, vast majority only look at a terabyte or less worth of data.
Và như các bạn thấy rõ, phần rất, rất, rất lớn chỉ xem một terabyte dữ liệu hoặc ít hơn.
So they may have a petabyte sitting there, they may have 500 terabytes sitting there, but they actually typically care about the terabyte or less.
Họ có thể có một petabyte nằm đó, có thể có 500 terabyte nằm đó, nhưng thực tế họ thường chỉ quan tâm đến một terabyte hoặc ít hơn.
And intuitively you can say, well, typically you would look at the most recent data, like say two weeks, one month, or something like that. And that is fairly reflected. So that's one observation.
Và theo trực giác bạn có thể nói rằng, thường thì bạn sẽ xem dữ liệu gần đây nhất, chẳng hạn hai tuần, một tháng, hoặc đại loại như vậy. Và điều đó phản ánh khá đúng. Đó là quan sát thứ nhất.
Second observation is that the building blocks that we use to build a cloud data warehouse, the machines that are available, also have materially changed in the last 20 years.
Quan sát thứ hai là các khối xây dựng mà chúng ta dùng để xây một kho dữ liệu đám mây, tức là các máy có sẵn, cũng đã thay đổi đáng kể trong 20 năm qua.
So if you look into 2006, very early cloud providers, you can get a commodity, say one core and two gigabytes of RAM, which is pretty much nothing in terms of your basic compute unit.
Nếu nhìn lại năm 2006, những nhà cung cấp đám mây đầu tiên, bạn có thể có một máy phổ thông, chẳng hạn một lõi và hai gigabyte RAM, gần như chẳng là gì so với một đơn vị tính toán cơ bản.
And then you aggregate hundreds of those to do something meaningful.
Rồi bạn gộp hàng trăm máy như thế lại để làm được việc gì đó có ý nghĩa.
But if you look today at what you can do, you can get pretty much an insane machine with 400 cores plus 24 terabytes of RAM.
Nhưng nếu nhìn vào hiện nay, bạn có thể làm gì, bạn có thể có một cỗ máy khủng khiếp với 400 lõi cộng 24 terabyte RAM.
If you kind of manage to get your handle on all of this, that's hard.
Nếu bạn xoay xở khai thác được hết, thì điều đó khó đấy.
But if you look at the commodity, like something that I just went to EC2 today, and I click like, yes, I want it, you can get an off-the-shelf 192-core machine with one and a half terabytes worth of RAM, which is insane.
Nhưng nếu nhìn vào loại máy phổ thông, như thứ mà hôm nay tôi vào EC2 và bấm, ừ, tôi muốn cái này, bạn có thể có một máy dựng sẵn 192 lõi với một và một rưỡi terabyte RAM, thật điên rồ.
So what can we do with these two things? We can look at the systems that we've built so far.
Vậy chúng ta có thể làm gì với hai thứ này? Chúng ta có thể nhìn lại các hệ thống đã xây dựng cho đến nay.
And those systems are pretty much geared toward taking many, many, many machines and combining them together to be able to process lots and lots and lots of data.
Những hệ thống đó gần như được thiết kế để lấy rất, rất nhiều máy và kết hợp chúng lại để xử lý một lượng dữ liệu rất, rất lớn.
And the reason you need to do it is because the machines were not that powerful. So you would need to combine them, and people were aiming for having lots of data.
Và lý do cần làm vậy là vì các máy khi đó không mạnh đến thế. Nên bạn phải kết hợp chúng lại, và người ta thì nhắm tới việc có thật nhiều dữ liệu.
But as we've just seen, neither of these is necessarily true today. So the machines are actually quite powerful, and maybe we don't need to analyze so much data.
Nhưng như chúng ta vừa thấy, cả hai điều này không còn nhất thiết đúng ngày nay. Các máy thực ra khá mạnh, và có thể chúng ta không cần phân tích nhiều dữ liệu đến vậy.
So why are we investing in all of that machinery, which means both money and CPU time? Can we be more efficient?
Vậy tại sao chúng ta lại đầu tư vào toàn bộ hệ thống máy móc đó, tức là tốn cả tiền lẫn thời gian CPU? Liệu chúng ta có thể hiệu quả hơn không?
And that is basically the foundational belief behind MotherDuck: if you use single nodes, and you use them to the maximum, it will be simpler because we will not have a distributed system.
Và đó về cơ bản là niềm tin nền tảng đằng sau MotherDuck: nếu bạn dùng các nút đơn lẻ, và tận dụng chúng tối đa, thì mọi thứ sẽ đơn giản hơn vì chúng ta không có hệ thống phân tán.
It will be efficient because you will not pay the overhead of networks, CPU allocation, this type of thing. And if you believe it's efficient, then this actually works wonderfully.
Nó sẽ hiệu quả vì bạn không phải trả chi phí phụ trội cho mạng, việc phân bổ CPU, những thứ kiểu như vậy. Và nếu bạn tin rằng nó hiệu quả, thì cách này hoạt động rất tuyệt.
So that is kind of MotherDuck. So in MotherDuck, we have built a cloud data warehouse based on a single-node, in-process database system that you guys know, namely DuckDB.
Đó chính là MotherDuck. Ở MotherDuck, chúng tôi đã xây dựng một kho dữ liệu đám mây dựa trên hệ thống cơ sở dữ liệu đơn nút, chạy trong tiến trình mà các bạn đã biết, đó là DuckDB.
Now, DuckDB is wonderful, and it's wonderful not only in the sense that it is a very recently developed database with all the latest and greatest research.
DuckDB rất tuyệt, và nó tuyệt không chỉ vì đây là một cơ sở dữ liệu được phát triển rất gần đây với tất cả nghiên cứu mới nhất và tốt nhất.
It's also extremely focused on user friendliness, and it can do a lot of things for you, be it being a classical database, which is store data, read it out in the SQL, or repackage file on S3, or pass your CSV file, or pass your JSON, and so forth, and so forth.
Nó cũng cực kỳ chú trọng đến sự thân thiện với người dùng, và làm được rất nhiều việc cho bạn, từ vai trò một cơ sở dữ liệu cổ điển, tức là lưu dữ liệu, đọc ra bằng SQL, hoặc đóng gói lại tệp trên S3, hoặc phân tích tệp CSV, hoặc JSON của bạn, và v.v., và v.v.
And also had a very rich extension ecosystem to make it even more powerful. So on its own, it's very useful. And it also has another upside. It's very lightweight, right?
Nó cũng có một hệ sinh thái tiện ích mở rộng rất phong phú để làm nó mạnh hơn nữa. Vì vậy riêng nó đã rất hữu ích. Và nó còn một ưu điểm khác. Nó rất nhẹ, đúng không?
It's built to be embeddable in many, many environments.
Nó được xây dựng để nhúng được vào rất nhiều môi trường.
And in extreme case, you can think you have DuckDB available in your browser if you go to that URL over there, and you can process data, read data from S3, do whatever you want to do in full SQL language.
Và trong trường hợp cực đoan, bạn có thể có DuckDB sẵn dùng ngay trong trình duyệt nếu vào URL ở đằng kia, và bạn có thể xử lý dữ liệu, đọc dữ liệu từ S3, làm bất cứ điều gì bạn muốn bằng ngôn ngữ SQL đầy đủ.
So it's fairly powerful, and it's very versatile and very lightweight. So if you put these two things together, right, you're going to get MotherDuck.
Nên nó khá mạnh, rất linh hoạt và rất nhẹ. Vậy nếu kết hợp hai thứ này lại, bạn sẽ có MotherDuck.
MotherDuck takes your standard DuckDB as a client and then connects it with another DuckDB instance that runs all the way in the cloud in those as big as you need the machine, and then together runs a query in what we call dual execution, which means take your query, look at what it does, and figure out which pieces of it need to run in the cloud
MotherDuck lấy DuckDB tiêu chuẩn của bạn làm máy khách rồi kết nối nó với một phiên bản DuckDB khác chạy trên đám mây, trên những máy lớn đến mức bạn cần, và cùng nhau chạy truy vấn theo cách chúng tôi gọi là thực thi kép, nghĩa là lấy truy vấn của bạn, xem nó làm gì, và xác định phần nào của nó cần chạy trên đám mây
and the compute machines that are available there and which pieces can run locally, which means that you have no network overhead. It's very close to you.
và trên các máy tính toán có sẵn ở đó và những phần nào có thể chạy cục bộ, nghĩa là bạn không tốn chi phí mạng. Nó ở rất gần bạn.
And putting these things together means you can do quite funky stuff.
Và kết hợp những thứ này lại thì bạn có thể làm được những việc khá thú vị.
So, for example, here's a visualization built also in CMU by the Dominic Moritz library, where it's taking two charts and interestingly updating the two together as you move, right?
Ví dụ, đây là một bản trực quan hóa được xây dựng cũng tại CMU, bằng thư viện của Dominic Moritz, trong đó lấy hai biểu đồ và cập nhật cả hai cùng lúc một cách thú vị khi bạn di chuyển, đúng không?
And as you can see, you move one and add one. This is real time. Immediately it updates.
Và như bạn thấy, bạn di chuyển một cái và thêm một cái. Đây là thời gian thực. Nó cập nhật ngay lập tức.
And the only reason you can do so is because you have a full database that's running in the browser and there is no network overhead. So every update only needs to compute locally.
Và lý do duy nhất bạn làm được vậy là vì bạn có một cơ sở dữ liệu đầy đủ chạy ngay trong trình duyệt và không có chi phí mạng. Nên mỗi lần cập nhật chỉ cần tính toán cục bộ.
And not have to go all the way to the browser. We can also use it to increase, build a much nicer IDE.
Và không phải đi đường vòng tới tận trình duyệt. Chúng ta cũng có thể dùng nó để xây dựng một IDE tốt hơn nhiều.
So here's a film of the MotherDuck UI, where we have a sample of your dataset cached locally, and that means that we can run your SQL locally and give you instant preview of what you're typing and whether the columns that you added are correct, if your modifications are correct.
Đây là một đoạn phim về giao diện MotherDuck, nơi chúng tôi lưu đệm cục bộ một mẫu của tập dữ liệu của bạn, nghĩa là chúng tôi có thể chạy SQL của bạn ngay tại máy và cho bạn xem trước tức thì những gì bạn đang gõ cũng như các cột bạn thêm vào có đúng không, các chỉnh sửa của bạn có đúng không.
Again, this is a real time movie recorded by the senior AI engineer for me this afternoon. It is very, very snappy.
Một lần nữa, đây là đoạn phim thời gian thực được quay bởi kỹ sư AI cấp cao cho tôi chiều nay. Nó rất, rất nhanh nhạy.
And the only reason that is the case is because we do not need to go to the cell.
Và lý do duy nhất là vì chúng ta không cần phải truy cập lên đám mây.
Okay, so that's a little bit of the motivation and what you can do when you have it.
Được rồi, đó là một chút về động lực và những gì bạn có thể làm khi có nó.
But I want to address the one concern of that chart: it didn't say all queries go below one terabyte or less. It said that by far the majority of them.
Nhưng tôi muốn giải quyết một mối lo về biểu đồ đó: nó không nói rằng mọi truy vấn đều dưới một terabyte hoặc ít hơn. Nó nói rằng phần lớn áp đảo là như vậy.
But what happens if you need to go higher? And I want to go a little bit to how we think about that.
Nhưng điều gì xảy ra nếu bạn cần vượt mức đó? Và tôi muốn nói một chút về cách chúng tôi nghĩ về vấn đề này.
So to do that, let's divide the world a little bit into a system, right?
Để làm vậy, hãy chia thế giới này thành một hệ thống, được chứ?
And that system looks at two axes: the amount of data that you need to analyze and the amount of compute you're going to spend doing so, or you can spend doing so, right?
Và hệ thống đó xét hai trục: lượng dữ liệu bạn cần phân tích và lượng tính toán bạn sẽ dùng để làm việc đó, hay có thể dùng để làm việc đó, đúng không?
And you go on both axes. So let's start on the easy side, which is small data, small compute, right?
Và bạn đi theo cả hai trục. Hãy bắt đầu từ phía dễ, tức là dữ liệu nhỏ, tính toán nhỏ, đúng không?
Just reasonable amount of data, can be sitting on your laptop, and you just want to get some insight about it. And this board is basically where DuckDB was born.
Chỉ là một lượng dữ liệu vừa phải, có thể nằm ngay trên laptop của bạn, và bạn chỉ muốn rút ra vài hiểu biết từ nó. Và vùng này về cơ bản là nơi DuckDB ra đời.
Like that was meant to do, it's a tool. You can use it in your Python. That's why it's embedded. You can use it in your program, wherever you want, and it will work fantastically.
Đó là mục đích của nó, một công cụ. Bạn có thể dùng nó trong Python. Đó là lý do nó là dạng nhúng. Bạn có thể dùng nó trong chương trình của mình, ở bất cứ đâu, và nó sẽ chạy tuyệt vời.
But even here, if you connect it with some cloud-based offering, you get some benefits. Like, if you would think, you have Git.
Nhưng ngay cả ở đây, nếu bạn kết nối nó với một dịch vụ trên đám mây, bạn sẽ có thêm một số lợi ích. Chẳng hạn, hãy nghĩ đến Git.
Git works greatly on your laptop, and then you have GitHub, which typically will help you back up your code base and how to collaborate on it, supply some authorization and control systems, and so forth and so forth.
Git hoạt động rất tốt trên laptop của bạn, và rồi bạn có GitHub, thường giúp bạn sao lưu mã nguồn và cộng tác trên đó, cung cấp một số hệ thống phân quyền và kiểm soát, và còn nhiều thứ khác nữa.
So that's the easy one, right?
Đó là trường hợp dễ nhất, đúng không?
And now let's go one up and say, okay, but I have lots of data and I want to use it with, but I don't have a lot of compute needs.
Giờ hãy nâng lên một mức và giả sử, tôi có rất nhiều dữ liệu và muốn dùng nó với, nhưng tôi không cần nhiều tài nguyên tính toán.
Maybe I'm doing something super small, like even a simple query, like how many records do I have that matches certain criteria?
Có thể tôi chỉ làm một việc rất nhỏ, như một truy vấn đơn giản, ví dụ có bao nhiêu bản ghi thỏa mãn một số tiêu chí nhất định?
And it turns out that DuckDB is also pretty good there too. As it is, right? It can, as I said, scan a Parquet file and a string, give you a great answer.
Và hóa ra DuckDB cũng làm khá tốt trong trường hợp này. Đúng vậy, phải không? Như tôi đã nói, nó có thể quét một tệp Parquet và một chuỗi, rồi cho bạn kết quả rất tốt.
But even in those cases, if you want it on your laptop, then you need to reach out over network into the AWS systems or wherever you are and read the data.
Nhưng ngay cả trong những trường hợp đó, nếu bạn muốn chạy trên laptop, thì bạn phải truy cập qua mạng vào các hệ thống AWS hoặc bất cứ nơi nào bạn lưu dữ liệu để đọc nó.
But if you connect it with DuckDB in the cloud, that means that aggregation or that scan can be done much more quickly and very close to the data, and you only need to download the summary.
Nhưng nếu bạn kết nối với DuckDB trên đám mây, thì phép tổng hợp hay lần quét đó có thể được thực hiện nhanh hơn nhiều và ngay sát dữ liệu, và bạn chỉ cần tải về phần tóm tắt.
So that is something that MotherDuck will automatically do for you if you use MotherDuck-enabled DuckDB, which we'll get to how in a second.
Đó là điều MotherDuck sẽ tự động làm cho bạn nếu bạn dùng DuckDB có hỗ trợ MotherDuck, mà chúng ta sẽ xem cách làm ngay sau đây.
So, going to the next one, what happens if you have not a lot of data, but you do need to do quite a huge computation for some, whatever reason, right?
Tiếp theo, điều gì xảy ra nếu bạn không có nhiều dữ liệu, nhưng lại cần một khối lượng tính toán rất lớn vì một lý do nào đó, bất kể là lý do gì, đúng không?
Maybe it is a very heavy recursive CTE that needs to kind of crunch and crunch and crunch and resolve itself to something, or very, very large join, or maybe you just need to do it as quickly as you can because your latency requirements are very low.
Có thể đó là một CTE đệ quy rất nặng cần phải tính đi tính lại mãi rồi mới ra kết quả, hoặc một phép join rất rất lớn, hoặc có thể bạn chỉ cần làm nó nhanh nhất có thể vì yêu cầu về độ trễ của bạn rất thấp.
So you need to get a very quick answer and you want all the data to be in memory. At that point, yeah, you can use one of those beefy machines.
Tức là bạn cần có câu trả lời rất nhanh và muốn toàn bộ dữ liệu nằm trong bộ nhớ. Lúc đó, vâng, bạn có thể dùng một trong những máy cấu hình mạnh ấy.
And then again, it's no secret that the cloud allows you to spin it up, use it and remove it when you don't need it anymore, and it becomes much more cost effective.
Và một lần nữa, ai cũng biết đám mây cho phép bạn khởi tạo nó, dùng và gỡ bỏ khi không cần nữa, và như vậy tiết kiệm chi phí hơn nhiều.
Again, we will do it for you.
Một lần nữa, chúng tôi sẽ làm việc đó cho bạn.
And I think there is another reason why you would like big compute, and that's not necessarily because your actual compute is big, but you just want to do it many, many times concurrently, right?
Và tôi nghĩ còn một lý do khác khiến bạn cần tính toán lớn, không nhất thiết vì phép tính của bạn lớn, mà vì bạn muốn chạy nó rất nhiều lần đồng thời, đúng không?
Or say you have a whole bunch, or if you all will look at certain data sets and we'll try to do something concurrently, then whatever the computation is, it needs to be done now.
Hoặc giả sử bạn có cả một loạt, hoặc tất cả các bạn cùng xem một số tập dữ liệu và cùng thử làm gì đó đồng thời, thì dù phép tính là gì, nó cũng cần được thực hiện ngay lập tức.
I don't know how many people are in the room, but let's say a hundred times. So because of that reason, you will have quite high compute needs.
Tôi không biết trong phòng có bao nhiêu người, nhưng giả sử là một trăm lần. Vì lý do đó, bạn sẽ có nhu cầu tính toán khá cao.
And the nice thing about using DuckDB, which is a very lightweight operation, is we can actually now give each specific end user its own DuckDB in the cloud, which we call Duckling.
Và điều tuyệt vời khi dùng DuckDB, một hệ thống rất nhẹ, là giờ đây chúng tôi có thể cấp cho mỗi người dùng cuối một DuckDB riêng trên đám mây, mà chúng tôi gọi là Duckling.
And so our lightweight extension is able to spin up on demand a backend for each of you guys. And as soon as you stop using it, it will go away and everything is fine.
Và phần mở rộng nhẹ của chúng tôi có thể khởi tạo theo yêu cầu một backend cho từng bạn. Và ngay khi bạn ngừng dùng, nó sẽ biến mất và mọi thứ vẫn ổn.
So that's how we deal with kind of the scale through a website access or multiple users using things concurrently.
Đó là cách chúng tôi xử lý quy mô thông qua truy cập bằng trang web hoặc nhiều người dùng cùng sử dụng đồng thời.
And finally, the biggest area: with lots of data, you need lots of compute to process it. And I think the question here is also a little bit exactly what you're trying to do.
Và cuối cùng, mảng lớn nhất: với lượng dữ liệu khổng lồ, bạn cần rất nhiều năng lực tính toán để xử lý nó. Và tôi nghĩ câu hỏi ở đây cũng phụ thuộc một chút vào chính xác là bạn đang muốn làm gì.
As we said before, these huge machines can do quite a lot, right? It's also much more efficient to run on them. So that might give you the gains that you need, you run closer.
Như chúng ta đã nói trước đó, những cỗ máy khổng lồ này làm được khá nhiều việc, đúng không? Chạy trên chúng cũng hiệu quả hơn nhiều. Vì vậy điều đó có thể mang lại mức cải thiện bạn cần, khi bạn chạy gần dữ liệu hơn.
And the nice thing about the DuckDB ecosystem is that I now have a new data lake format and architecture called DuckLake. I'm not going to go in there.
Và điều tuyệt vời về hệ sinh thái DuckDB là giờ đây tôi có một định dạng và kiến trúc data lake mới gọi là DuckLake. Tôi sẽ không đi sâu vào phần đó.
Just want to shout out that next Monday our CEO is also giving a talk about that. So if you want to go learn more... But then MotherDuck offers that type of integration as well.
Chỉ muốn nhắc là thứ Hai tuần sau CEO của chúng tôi cũng sẽ có một buổi nói chuyện về chủ đề này. Nên nếu bạn muốn tìm hiểu thêm... Và MotherDuck cũng cung cấp kiểu tích hợp đó.
So we also have a solution for that much bigger scale, if you happen to need it. So with that in mind, let's go a little bit about the lower level and the architecture.
Vì vậy chúng tôi cũng có giải pháp cho quy mô lớn hơn nhiều, nếu bạn cần. Với những điều đó trong đầu, chúng ta hãy đi vào mức thấp hơn một chút và phần kiến trúc.
This is actually a screenshot from my internal Mirror board that says how things are. This is a screenshot of a data region.
Đây thực ra là ảnh chụp màn hình từ bảng Miro nội bộ của tôi mô tả mọi thứ đang vận hành như thế nào. Đây là ảnh chụp màn hình của một vùng dữ liệu.
I'm not going to go into all of those boxes, but just to give you a little bit of a taste.
Tôi sẽ không đi vào tất cả những ô này, mà chỉ để các bạn thấy sơ qua một chút.
First, again, I don't know how much time was spent going into how DuckDB works, but we integrate into its extension mechanism.
Trước hết, tôi không biết các bạn đã dành bao nhiêu thời gian tìm hiểu cách DuckDB hoạt động, nhưng chúng tôi tích hợp vào cơ chế mở rộng của nó.
At the top line, you can see how a normal DuckDB query lifecycle goes. It will parse it. It will bind it. That means figuring out which tables, what fields and so forth.
Ở dòng trên cùng, bạn có thể thấy vòng đời của một truy vấn DuckDB thông thường. Nó sẽ phân tích cú pháp. Nó sẽ thực hiện binding. Nghĩa là xác định những bảng nào, những trường nào, v.v.
Then we'll figure out how to run the query and optimize it. And finally, we'll go on it. We extend each one of those phases with new functionality.
Sau đó chúng ta sẽ tìm cách chạy truy vấn và tối ưu hóa nó. Và cuối cùng, chúng ta sẽ thực thi. Chúng tôi mở rộng từng giai đoạn đó với các chức năng mới.
So the binding needs to know about the cloud tables. The optimizer needs to decide basically what runs well.
Vì vậy bước binding cần biết về các bảng trên đám mây. Bộ tối ưu hóa cần quyết định về cơ bản thứ gì chạy tốt.
So we have the native DuckDB optimization that decides how to run effectively the query if you're close to the data, but we can split the query and decide, okay, this part of the filtering we're going to push up to the cloud, do the aggregation, download it, and then do the join with some local dataset, for example.
Chúng tôi có phần tối ưu hóa gốc của DuckDB quyết định cách chạy truy vấn hiệu quả nếu bạn ở gần dữ liệu, nhưng chúng tôi có thể tách truy vấn ra và quyết định, được rồi, phần lọc này chúng ta sẽ đẩy lên đám mây, thực hiện phép tổng hợp, tải kết quả về, rồi thực hiện phép join với một tập dữ liệu cục bộ chẳng hạn.
And then, of course, the actual execution, which needs to run in this dual mode, part in the cloud, part locally. Again, I think we can go...
Và tất nhiên là phần thực thi thực sự, phải chạy ở chế độ kép này, một phần trên đám mây, một phần cục bộ. Một lần nữa, tôi nghĩ chúng ta có thể...
We can spend a whole talk there, but just realize that we hook into all these phases. And then finally, going a level up to what does it mean to have a cloud system.
dành cả một buổi nói chuyện cho phần đó, nhưng hãy nhận ra rằng chúng tôi móc vào tất cả các giai đoạn này. Và cuối cùng, nâng lên một tầng nữa: có một hệ thống đám mây nghĩa là gì.
So typically clouds separate into a compute layer and a storage layer. I'll touch both of these.
Thông thường các đám mây tách thành tầng tính toán và tầng lưu trữ. Tôi sẽ nói qua cả hai.
So for the lightweight compute we have, first of all, we enjoy the fact that we're a single node and DuckDB is so fast to start up, right?
Với phần tính toán nhẹ mà chúng tôi có, trước hết, chúng tôi hưởng lợi từ việc là một nút đơn và DuckDB khởi động rất nhanh, đúng không?
So our goal for time to an answer for a query is 100 milliseconds. And if that query is very light, it will also return around that time, cold start.
Vì vậy mục tiêu của chúng tôi về thời gian có câu trả lời cho một truy vấn là 100 mili giây. Và nếu truy vấn đó rất nhẹ, thì nó cũng sẽ trả kết quả trong khoảng thời gian đó, tính cả khởi động nguội.
Later will be less, right? Depends on what the query execution time is. While it's up, as we said, we enjoy the efficiency of DuckDB itself and being a single node.
Những lần sau sẽ ít hơn, đúng không? Tùy thuộc vào thời gian thực thi truy vấn. Trong lúc nó đang chạy, như đã nói, chúng ta tận dụng được hiệu quả của chính DuckDB và việc chỉ dùng một nút duy nhất.
And also because it's so light to start up, that also means that we can shut it down very aggressively. So that makes it cost effective.
Và cũng vì khởi động rất nhẹ, nên điều đó cũng có nghĩa là chúng ta có thể tắt nó rất mạnh tay. Nhờ vậy mà tiết kiệm chi phí.
And the last, later point is, this is again a quite big topic, but in distributed system, one of the challenges you have is to figure out how much resources to give each user and to make sure that no user dominates the whole system.
Và điểm cuối cùng, một điểm sau này, đây lại là một chủ đề khá lớn, nhưng trong hệ thống phân tán, một trong những thách thức bạn gặp phải là xác định cấp bao nhiêu tài nguyên cho mỗi người dùng và đảm bảo không người dùng nào chiếm hết cả hệ thống.
Because we are using a single node, we completely outsource this to the container orchestration system. So every database is completely contained and we don't have to worry about it.
Vì chúng tôi dùng một nút duy nhất, nên chúng tôi giao hoàn toàn việc này cho hệ thống điều phối container. Vì vậy mỗi cơ sở dữ liệu hoàn toàn được cô lập và chúng tôi không phải lo về chuyện đó.
But we're out of time. Sorry, the students in the room, next class. We have time for one question. Yes, one question. Any question?
Nhưng chúng ta hết giờ rồi. Xin lỗi các bạn sinh viên trong lớp, để buổi sau nhé. Chúng ta còn thời gian cho một câu hỏi. Vâng, một câu thôi. Có ai hỏi không?
How much is MotherDuck contributing back to DuckDB? Yeah, so we have engineers that write code for DuckDB.
MotherDuck đóng góp lại cho DuckDB nhiều đến mức nào? Vâng, chúng tôi có các kỹ sư viết mã cho DuckDB.
Most of the contribution that we do is through subscription to their work and guiding them together.
Phần lớn đóng góp của chúng tôi là thông qua việc đăng ký dịch vụ cho công việc của họ và cùng nhau định hướng.
So our engineers typically open PRs when something's small, but if it's a bigger item, we will work together with the DuckDB Labs folks to develop it. Okay, awesome. Give her an applause.
Các kỹ sư của chúng tôi thường mở PR khi việc đó nhỏ, còn nếu là hạng mục lớn hơn, chúng tôi sẽ cùng làm việc với những người ở DuckDB Labs để phát triển nó. Được rồi, tuyệt vời. Hãy vỗ tay cho cô ấy nào.
Again, reminder, homework three is due on Sunday. Please do the practice exam. And then, as you said, the MotherDuck talk on DuckLake will be on Monday after class next week, okay?
Nhắc lại, bài tập về nhà ba đến hạn vào Chủ nhật. Hãy làm đề thi thử. Và sau đó, như bạn đã nói, buổi nói chuyện của MotherDuck về DuckLake sẽ diễn ra vào thứ Hai sau giờ học tuần sau, nhé?
All right, guys, have a good weekend. Hit it.
Được rồi các bạn, chúc cuối tuần vui vẻ. Bắt đầu nhạc nào.
Đă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.