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ả.
Let's get started. A round of applause for DJ Cash, last class. Again, so we missed you on Monday. Tax accountant.
Bắt đầu thôi. Một tràng pháo tay cho DJ Cash, buổi học cuối cùng. Một lần nữa, hôm thứ Hai bọn mình nhớ bạn lắm. Kế toán thuế.
And then what was the dude who showed up at my office? He's just a crazy fan. You said he was like your long-lost brother or something stupid. No, no.
Rồi anh chàng xuất hiện ở văn phòng của thầy là ai vậy? Chỉ là một fan cuồng thôi. Bạn nói anh ta giống như anh em thất lạc từ lâu của bạn hay gì đó ngớ ngẩn. Không, không.
Do you know that guy? No, no. Okay, all right. All right, again, thank you so much for keeping it fresh this semester.
Bạn có biết người đó không? Không, không. Được rồi, được rồi. Được rồi, một lần nữa, cảm ơn bạn rất nhiều vì đã giữ không khí tươi mới trong học kỳ này.
All right, guys, so a lot to cover today, plus we have a guest speaker at the end. So let's jump right into it. Again, Project 4 is due this Sunday.
Được rồi các em, hôm nay có rất nhiều nội dung, và cuối buổi còn có một diễn giả khách mời. Vậy nên vào thẳng vấn đề. Một lần nữa, Project 4 hạn nộp là Chủ nhật này.
On Monday, or sorry, on Saturday, we have the special office hours. Again, 3 o'clock, 3 to 5, in Gates on the fifth floor. Homework 6 is also due this Sunday as well.
Vào thứ Hai, à nhầm, vào thứ Bảy, chúng ta có giờ hỗ trợ đặc biệt. Một lần nữa, 3 giờ, từ 3 đến 5 giờ, ở Gates, tầng năm. Homework 6 cũng hạn nộp vào Chủ nhật này.
We will then release the solutions to it on Monday, the prep for the exam, which is going to be on December 11th at 1 p.m., not here, but in the student university center of the Maine Autonium.
Sau đó thầy sẽ công bố lời giải vào thứ Hai, để các em chuẩn bị cho kỳ thi, kỳ thi sẽ diễn ra vào ngày 11 tháng 12 lúc 1 giờ chiều, không phải ở đây, mà ở trung tâm sinh viên của Maine Autonium.
So, again, we'll cover that immediately after this slide. And then if you want a TA next semester for this class, since we're not teaching 721, please sign up here.
Vậy nên, thầy sẽ nói về phần đó ngay sau slide này. Và nếu các em muốn làm trợ giảng cho lớp này vào học kỳ sau, vì chúng ta không dạy 721, hãy đăng ký ở đây.
All right, any questions about Project 4, the final exam, or the homework? Yes. The question is, for Project 4, can you use late days? Yes. Other questions?
Được rồi, có câu hỏi nào về Project 4, kỳ thi cuối kỳ hay bài tập về nhà không? Vâng, mời em. Câu hỏi là, với Project 4, có thể dùng ngày nộp muộn không? Có. Còn câu hỏi nào khác không?
All right, let's plow through this. All right, so I will post this on Piazza. I will have additional office hours on the Wednesday before the exam, in the morning and in the afternoon.
Được rồi, ta làm nhanh phần này. Thầy sẽ đăng cái này lên Piazza. Thầy sẽ có thêm giờ hỗ trợ vào thứ Tư trước kỳ thi, vào buổi sáng và buổi chiều.
All the TAs will have their regular office hours up until this Saturday inclusive. Then after that, they won't be available.
Tất cả các trợ giảng sẽ có giờ hỗ trợ bình thường cho đến hết thứ Bảy này. Sau đó, họ sẽ không rảnh nữa.
If you can't meet this time with me, please send me an e-mail, and we'll try to make an arrangement.
Nếu các em không thể gặp thầy vào giờ này, hãy gửi e-mail cho thầy, và chúng ta sẽ cố gắng sắp xếp.
And then I think Will also will be in town as well, and I'll see whether he can be available on Monday or Tuesday, depending on his schedule.
Và thầy nghĩ Will cũng sẽ có mặt ở thành phố, và thầy sẽ xem bạn ấy có rảnh vào thứ Hai hoặc thứ Ba không, tùy theo lịch của bạn ấy.
So, as I said, the final exam is going to be this next Thursday coming up. You need to bring your CMU ID.
Như thầy đã nói, kỳ thi cuối kỳ sẽ diễn ra vào thứ Năm tuần tới. Các em cần mang theo thẻ CMU.
You need to bring a pencil and an eraser, calculator, cell phone is okay, right, do basic logs and things like that.
Các em cần mang bút chì, tẩy, máy tính bỏ túi, điện thoại cũng được, để tính log cơ bản và những thứ tương tự.
And then just like the midterm, you can write on a regular eight and a half, I love my sheet of paper, handwritten notes about whatever you want in the study.
Và cũng giống như kỳ thi giữa kỳ, các em được viết trên một tờ giấy khổ tám rưỡi, thầy rất thích tờ giấy đó, ghi chú viết tay về bất cứ điều gì các em muốn khi ôn tập.
And then there's a practice exam that's available that I posted on Piazza this week and also available on the website here. You can bring food if you want. I think that's allowed.
Và có một đề thi thử thầy đã đăng trên Piazza tuần này và cũng có trên trang web ở đây. Các em có thể mang đồ ăn nếu muốn. Thầy nghĩ điều đó được phép.
Just don't bring weird shit like one year somebody brought wet laundry. Don't do that. Somebody brought candles one year. Don't do that.
Chỉ đừng mang những thứ kỳ quặc như năm nọ có người mang quần áo ướt. Đừng làm thế. Có năm có người mang nến. Đừng làm thế.
I had a friend in another school, somebody brought a therapy snake to an exam. Don't do that, right. Be reasonable, okay.
Thầy có một người bạn ở trường khác, có người mang một con rắn trị liệu đến buổi thi. Đừng làm thế nhé. Hãy hợp lý, được chứ.
So the stuff that you need to be aware of that we covered throughout the semester, sorry, before the midterm, but we obviously need to build upon it throughout everything we talk about after the midterm, are listed here.
Những nội dung các em cần nắm, mà chúng ta đã học suốt học kỳ, xin lỗi, trước kỳ thi giữa kỳ, nhưng rõ ràng chúng ta cần xây dựng tiếp trên đó trong suốt mọi thứ chúng ta nói sau kỳ thi giữa kỳ, được liệt kê ở đây.
You obviously can't, we will not ask you an in-depth SQL question in the same way that we did in the midterm.
Rõ ràng các em không thể, thầy sẽ không hỏi các em câu SQL chuyên sâu giống như chúng ta đã làm trong kỳ thi giữa kỳ.
You obviously need to be able to understand what select star from table does, right. Especially in the context of understanding the query processing models.
Chắc chắn các bạn cần hiểu được câu select star from table làm gì, đúng không. Đặc biệt là trong bối cảnh hiểu các mô hình xử lý truy vấn.
In terms of how window functions are implemented or how window functions are, like the SQL syntax work.
Còn về cách các hàm cửa sổ được cài đặt, hay các hàm cửa sổ, cú pháp SQL của chúng hoạt động ra sao.
I don't, so I have not written the final exam yet. So I don't plan to write a window function question yet. They're not hard.
Tôi chưa viết đề thi cuối kỳ. Nên tôi chưa định ra câu hỏi về hàm cửa sổ. Chúng không khó.
It's just a group by. It's weird, but it's like, it's a group by.
Nó chỉ là một group by. Hơi lạ, nhưng thực chất nó là một group by.
Again, the idea of the midterm is to see if you understand the semantics of what the window function is actually doing. That's not what we've covered since the midterm.
Một lần nữa, mục đích của kỳ thi giữa kỳ là xem các bạn có hiểu ngữ nghĩa của việc hàm cửa sổ thực sự làm gì hay không. Đó không phải là những gì chúng ta đã học từ sau giữa kỳ.
We've covered how to build all the stuff to actually run transactions and run queries. All right. And then basic understanding of BusTub.
Chúng ta đã học cách xây dựng tất cả những thứ để thực sự chạy giao dịch và chạy truy vấn. Được rồi. Và sau đó là hiểu biết cơ bản về BusTub.
Again, something very light, because obviously we can't have you write code and try to compile and debug it in the middle of the final exam.
Một lần nữa, chỉ ở mức rất nhẹ, vì rõ ràng chúng tôi không thể bắt các bạn viết code rồi biên dịch và gỡ lỗi ngay giữa kỳ thi cuối kỳ.
This is just to get a rough understanding of, you know, did you actually do the projects? Right. Again, we can't ask you, like, what is it on this file? What is this line?
Phần này chỉ để nắm sơ bộ là các bạn có thực sự làm các dự án hay không. Đúng vậy. Chúng tôi không thể hỏi kiểu: trong tệp này có gì? Dòng này là gì?
What's this line of code? We're not going to ask you those things. It's more conceptual things. Okay. All right.
Dòng code này là gì? Chúng tôi sẽ không hỏi những thứ đó. Chủ yếu là các vấn đề khái niệm. Được rồi.
So the main things we covered since before the midterm, we had the one class before the, on the Monday before the midterm, we talked about join algorithms.
Vậy những nội dung chính chúng ta đã học từ trước giữa kỳ, có một buổi học trước, vào thứ Hai trước giữa kỳ, chúng ta nói về các thuật toán join.
And we talked about the three basic nested loop join algorithms you can have. The naive one where you just go and get a block for every single tuple.
Và chúng ta nói về ba thuật toán nested loop join cơ bản. Cách ngây thơ là với mỗi tuple lại đi lấy một block.
That's stupid. Don't do that. But we talked about block nested loop join, index nested loop join. Talked about sort-merge join, depending upon the external merge sort stuff we talked about before.
Cách đó ngớ ngẩn. Đừng làm vậy. Nhưng chúng ta đã nói về block nested loop join và index nested loop join. Nói về sort-merge join, dựa trên phần external merge sort mà chúng ta đã học trước đó.
Hash joins, the simple case, the partition case, and the hybrid hash join where you keep one hash table for the hot, sort of hot partition in memory, and then you let everything else spill to disk.
Hash join, trường hợp đơn giản, trường hợp phân vùng, và hybrid hash join, trong đó bạn giữ một bảng băm cho phân vùng nóng trong bộ nhớ, còn mọi thứ khác thì để tràn xuống đĩa.
And then basic optimizations for using Bloom filters and how to cost the joins in general. All right. So we're given a set of tuples and a set of pages. All right.
Rồi các tối ưu hóa cơ bản bằng Bloom filter và cách tính chi phí của các phép join nói chung. Được rồi. Chúng ta được cho một tập tuple và một tập trang.
And again, an amount of memory buffers. Can you cost how much it would take to run the join with, you know, sort-merge join versus a hash join?
Và cả lượng bộ đệm bộ nhớ nữa. Bạn có thể tính chi phí để chạy phép join bằng sort-merge join so với hash join không?
All right. Then we talk about query execution. We need to talk about graph optimization. Actually, I'm missing a slide here. Graph optimization, we talked about the basic high-level architecture of, like, top-down versus bottom-up.
Được rồi. Sau đó chúng ta nói về thực thi truy vấn. Chúng ta cần nói về tối ưu hóa đồ thị. Thật ra tôi đang thiếu một slide ở đây. Về tối ưu hóa đồ thị, chúng ta đã nói về kiến trúc cấp cao cơ bản, như top-down so với bottom-up.
Again, we can't ask you anything real in depth, But we also spent time talking about how to cost or estimate the cardinality and selectivity of predicates, right, and using basic histograms.
Một lần nữa, chúng tôi không thể hỏi gì quá chuyên sâu, Nhưng chúng ta cũng dành thời gian nói về cách tính chi phí hay ước lượng cardinality và selectivity của các vị từ, đúng không, và dùng các histogram cơ bản.
So you can expect to see a question like that. Again, it's not that difficult. You just look at the predicate, and then we can't ask you anything too in-depth on this.
Vì vậy các em có thể gặp một câu hỏi như thế. Một lần nữa, nó không khó lắm. Các em chỉ cần nhìn vào vị từ, và chúng tôi cũng không thể hỏi quá sâu về phần này.
So don't freak out about it. For the query execution, we talked about the three different execution models: iterator, or the Volcano model. It's calling get next, getting a single tuple at a time.
Nên đừng quá lo lắng về nó. Về thực thi truy vấn, chúng ta đã nói về ba mô hình thực thi khác nhau: iterator, hay còn gọi là mô hình Volcano. Nó gọi get next, lấy từng tuple một tại mỗi thời điểm.
Materialization is sending all the tuples from an operator up to the next operator. And then vectorized, or batch, is sending, you know, a batch of tuples instead of one at a time.
Materialization là gửi toàn bộ các tuple từ một toán tử lên toán tử kế tiếp. Còn vectorized, hay batch, là gửi đi, một lô các tuple thay vì từng tuple một.
And then we talked about the difference between a push versus pull query processing model.
Rồi chúng ta cũng nói về sự khác biệt giữa mô hình xử lý truy vấn kiểu push và kiểu pull.
Am I going to invoke at the root, call get next, and have that percolate down and pull tuples up, or to start at the leaf nodes, run those operators, and send the data up the plan?
Tôi sẽ gọi từ gốc, gọi get next, để lời gọi đó lan xuống dưới và kéo các tuple lên, hay bắt đầu từ các nút lá, chạy các toán tử đó, rồi đẩy dữ liệu lên trên kế hoạch?
We talked about the different access methods: sequential scan, the types of optimizations, some of them we'll cover again today; index scan, being able to take a single index or multiple indexes and run value predicates; and then how to handle update queries in our system.
Chúng ta đã nói về các phương thức truy cập khác nhau: sequential scan, các kiểu tối ưu hóa, một số trong đó hôm nay chúng ta sẽ nói lại; index scan, tức là dùng một chỉ mục hoặc nhiều chỉ mục để chạy các vị từ giá trị; và cách xử lý các truy vấn cập nhật trong hệ thống của chúng ta.
We talked a little bit about expression evaluation. Again, we'll talk about it again today.
Chúng ta cũng nói một chút về đánh giá biểu thức. Một lần nữa, hôm nay chúng ta sẽ nói lại về nó.
Just like, what does the tree look like, and how would you actually apply that on a per-tuple basis when you run your queries?
Chẳng hạn, cây biểu thức trông như thế nào, và thực tế các em sẽ áp dụng nó trên từng tuple ra sao khi chạy truy vấn?
For query execution, we talked about the process models. There is a single process per worker, single thread per worker. What are the pros and cons of those?
Về thực thi truy vấn, chúng ta đã nói về các mô hình tiến trình. Có mô hình một tiến trình cho mỗi worker, và một luồng cho mỗi worker. Ưu và nhược điểm của chúng là gì?
We talked about the different variations of doing parallel query execution, right? Inter-query parallelism means that I can run multiple queries at the same time.
Chúng ta đã nói về các biến thể khác nhau của thực thi truy vấn song song, đúng không? Song song giữa các truy vấn nghĩa là tôi có thể chạy nhiều truy vấn cùng lúc.
Intra-query parallelism means that I can have, for a single query, multiple workers working together to process it.
Song song trong một truy vấn nghĩa là với một truy vấn duy nhất, tôi có thể có nhiều worker cùng phối hợp để xử lý nó.
And then the difference between the horizontal versus vertical: the horizontal is when I have the multiple instances of the operator running on different workers to read or process data for different subsets of a table, or subsets of the input data.
Và sự khác biệt giữa chiều ngang và chiều dọc: chiều ngang là khi tôi có nhiều thể hiện của toán tử chạy trên các worker khác nhau để đọc hoặc xử lý dữ liệu của các tập con khác nhau của một bảng, hoặc các tập con của dữ liệu đầu vào.
I can partition it on ranges. I can have different workers work on different ranges.
Tôi có thể phân vùng theo khoảng giá trị. Tôi có thể cho các worker khác nhau xử lý các khoảng khác nhau.
And then vertical partitioning is more, not as common, but this is where you could have one operator running, doing some processing, and then they're streaming data up to the next operator.
Còn phân vùng theo chiều dọc thì ít phổ biến hơn, đó là khi bạn có một toán tử đang chạy, xử lý một phần, rồi truyền dữ liệu lên toán tử kế tiếp.
You can run a parallel at the same time. And then we briefly talked about IO parallelism, where we talked about, what does the data system see when it has multiple disks?
Bạn có thể chạy song song chúng cùng lúc. Rồi chúng ta cũng nói ngắn gọn về song song IO, khi chúng ta bàn về việc hệ thống dữ liệu nhìn thấy gì khi có nhiều đĩa?
Could it be abstracted away with RAID or an appliance? Or should the data system be specifically aware of, here's the different disks that I have and how to take advantage of them?
Liệu có thể che giấu chúng bằng RAID hay một thiết bị chuyên dụng không? Hay hệ thống dữ liệu nên nhận biết cụ thể rằng đây là các đĩa tôi có và cách tận dụng chúng?
The most obvious thing is, we didn't talk about it at the time when we talked about IO parallelism, but with write-ahead logging, a very common approach systems use is they have one disk for the regular tables and then another really fast disk for the write-ahead log.
Điều rõ ràng nhất là, lúc nói về song song IO chúng ta đã không đề cập đến, nhưng với ghi nhật ký ghi trước (write-ahead logging), một cách tiếp cận rất phổ biến mà các hệ thống dùng là có một đĩa cho các bảng thông thường và một đĩa khác thật nhanh cho write-ahead log.
Because I want to get data out to the write-ahead log as fast as possible, commit transactions, and then tell the outside world that I committed.
Vì tôi muốn ghi dữ liệu ra write-ahead log càng nhanh càng tốt, commit các giao dịch, rồi báo cho thế giới bên ngoài biết là tôi đã commit.
So I want my fastest disk to be for the logging. OK. So I do have a slide. It's out of order. Sorry. I've already said this already.
Nên tôi muốn đĩa nhanh nhất dành cho việc ghi log. OK. Tôi có một slide về chuyện này. Nó bị sai thứ tự. Xin lỗi. Tôi đã nói điều này rồi.
Query optimization, basic heuristics we can apply, predicate pushdown, projection pushdown.
Tối ưu hóa truy vấn, những heuristic cơ bản mà ta có thể áp dụng, predicate pushdown, projection pushdown.
We won't focus too much on that. We won't ask you anything about nested subqueries. Don't worry about that.
Chúng ta sẽ không tập trung nhiều vào phần đó. Chúng tôi sẽ không hỏi gì về các truy vấn con lồng nhau. Đừng lo về phần đó.
But statistics, cardinality estimations, looking at histograms, sketches, how to be able to say, for a given predicate on my table, here's some summarization of the data. What's the selectivity estimate for our predicate?
Nhưng về thống kê, ước lượng cardinality, xem histogram, sketch, cách để có thể nói rằng, với một predicate cho trước trên bảng của tôi, đây là bản tóm tắt nào đó của dữ liệu. Ước lượng selectivity cho predicate của chúng ta là bao nhiêu?
Again, we can't ask you anything really complicated because we can't give you a giant, huge histogram.
Một lần nữa, chúng tôi không thể hỏi bạn điều gì thật sự phức tạp vì chúng tôi không thể đưa cho bạn một histogram khổng lồ.
And then we spent a lot of time talking about transactions. We spent a whole lecture talking about the basics of ACID: atomicity, consistency, isolation, durability.
Rồi chúng ta đã dành nhiều thời gian nói về giao dịch. Chúng ta dành cả một bài giảng nói về những điều cơ bản của ACID: atomicity, consistency, isolation, durability.
So understand what all those four attributes mean, what are those guarantees the system is trying to apply or provide for applications. We talked about conflict serializability.
Vậy hãy hiểu cả bốn thuộc tính đó có nghĩa là gì, những đảm bảo đó là gì mà hệ thống đang cố áp dụng hoặc cung cấp cho các ứng dụng. Chúng ta đã nói về conflict serializability.
So how do we want to check for correctness to say that a schedule is going to be conflict serializable for the transactions that are inside of it?
Vậy ta muốn kiểm tra tính đúng đắn như thế nào để nói rằng một schedule là conflict serializable đối với các giao dịch nằm trong nó?
And how can we check whether two schedules are considered equivalent or conflict equivalent? View serializability is, again, a more fuzzy idea, fuzzy concept of serializability.
Và làm sao để kiểm tra xem hai schedule có được coi là tương đương hay conflict equivalent không? View serializability, một lần nữa, là một ý niệm mơ hồ hơn, một khái niệm serializability mơ hồ.
We just understand what are the distinctions between view serializability and conflict serializability. So which one's more flexible, conflict serializability or view serializability? View.
Chỉ cần hiểu những điểm khác biệt giữa view serializability và conflict serializability. Vậy cái nào linh hoạt hơn, conflict serializability hay view serializability? View.
But how to be able to identify that at runtime is impossible unless you understand what the application actually wants.
Nhưng việc nhận diện được điều đó tại thời điểm chạy là bất khả thi trừ khi bạn hiểu ứng dụng thực sự muốn gì.
So just being able to understand that some schedules may be still serializable, but they'll be view serializable and not conflict serializable. And a real system couldn't actually provide that.
Vậy chỉ cần hiểu rằng một số schedule vẫn có thể serializable, nhưng chúng sẽ là view serializable chứ không phải conflict serializable. Và một hệ thống thực tế không thể cung cấp điều đó.
Then we talked about the isolation levels. The main ones in the ANSI SQL standard, serializable is at the top. Then you have repeatable read.
Sau đó chúng ta nói về các mức cô lập. Các mức chính trong chuẩn ANSI SQL, serializable ở trên cùng. Rồi đến repeatable read.
And below that, you have read committed. And below that, you have read uncommitted. And then snapshot isolation is this other thing on the side that provides certain guarantees that the other ones don't.
Bên dưới là read committed. Và bên dưới nữa là read uncommitted. Còn snapshot isolation là một thứ khác nằm riêng bên cạnh cung cấp một số đảm bảo mà các mức kia không có.
So what are the main anomalies that can occur for transactions on these different isolation levels? Again, could occur. Doesn't mean they always will, but they could occur.
Vậy các anomaly chính là gì có thể xảy ra với các giao dịch ở những mức cô lập khác nhau này? Một lần nữa, là có thể xảy ra. Không có nghĩa lúc nào cũng xảy ra, nhưng có thể xảy ra.
And what are the mechanisms you would use to protect them?
Và bạn sẽ dùng những cơ chế nào để bảo vệ chống lại chúng?
Say it again?
Bạn nói lại được không?
The question is, can we ever say that anomaly will occur on our isolation level?
Câu hỏi là: liệu chúng ta có bao giờ khẳng định được rằng dị thường đó sẽ xảy ra ở mức cô lập của mình không?
So basically, you're asking whether it could be predicted for a given isolation level and a set of transactions actually running that you will incur these things. Oftentimes, it's like a race condition.
Về cơ bản, bạn đang hỏi liệu có thể dự đoán được, với một mức cô lập nhất định và một tập giao dịch đang thực sự chạy, rằng bạn sẽ gặp những điều này hay không. Thường thì nó giống như một race condition.
In a real system, be able to say, if I run this, Maybe one transaction will get paused because of a disk read or write or something, and then it gets stalled.
Trong một hệ thống thực tế, khó mà nói được là nếu tôi chạy cái này, có thể một giao dịch sẽ bị tạm dừng vì một thao tác đọc hoặc ghi đĩa nào đó, rồi nó bị đình trệ.
And therefore, it won't see certain anomalies. But if that disk stall isn't there, then it does see it. There's a bunch of layers.
Và do đó, nó sẽ không thấy một số dị thường. Nhưng nếu không có sự đình trệ do đĩa đó thì nó lại thấy. Có rất nhiều tầng như vậy.
It's hard to be able to predict this, and that's why it says it may occur.
Rất khó dự đoán điều này, và đó là lý do người ta nói là nó có thể xảy ra.
Because if I run a read uncommitted, but I only run one transaction at a time, then it's technically serializable.
Bởi vì nếu tôi chạy ở mức read uncommitted, nhưng mỗi lúc chỉ chạy một giao dịch, thì về mặt kỹ thuật nó là serializable.
There's some theory work on how to determine after the fact whether a transaction saw something that it shouldn't have seen, and then try to then understand what are the long-term implications of that for data.
Có một số công trình lý thuyết về cách xác định sau sự việc liệu một giao dịch có thấy điều mà lẽ ra nó không được thấy hay không, rồi cố gắng hiểu những hệ quả lâu dài của việc đó đối với dữ liệu là gì.
If my transaction does incur an anomaly, but I write something to the database, then technically, anybody that comes along later that reads and writes based on what I wrote is now kind of incorrect as well, the butterfly effect.
Nếu giao dịch của tôi gặp một dị thường, nhưng tôi vẫn ghi một thứ gì đó vào cơ sở dữ liệu, thì về mặt kỹ thuật, bất kỳ ai đến sau đọc và ghi dựa trên những gì tôi đã ghi thì cũng trở nên không chính xác, đó là hiệu ứng cánh bướm.
And how to measure that is impossible.
Và việc đo lường điều đó là không thể.
Then we spent a lecture talking about transactions in the context of two-phase locking. The idea of two-phase locking is that I acquire locks, either shared locks or exclusive locks, while in the growing phase.
Sau đó chúng ta dành một bài giảng để nói về các giao dịch trong bối cảnh khóa hai pha. Ý tưởng của khóa hai pha là tôi lấy các khóa, khóa chia sẻ hoặc khóa độc quyền, trong pha mở rộng.
And then as soon as I release one lock, then I automatically end up in the shrinking phase.
Và ngay khi tôi nhả một khóa, thì tôi tự động chuyển sang pha thu hẹp.
But as we said, in SQL and real systems, there isn't an explicit call to unlock locks or give your locks back.
Nhưng như đã nói, trong SQL và các hệ thống thực tế, không có lời gọi tường minh nào để mở khóa hay trả lại khóa.
And so most systems are going to run either with strict 2PL or strong strict 2PL.
Vì vậy hầu hết các hệ thống sẽ chạy với strict 2PL hoặc strong strict 2PL.
Strict 2PL just means that I'm going to hold my exclusive locks until the very end and give them up all when I commit.
Strict 2PL nghĩa là tôi sẽ giữ các khóa độc quyền cho đến tận cuối và nhả tất cả khi tôi commit.
But I'm allowed to release the shared locks earlier, just during the shrinking phase, assuming I can know how to get into that shrinking phase or that I'm in the shrinking phase.
Nhưng tôi được phép nhả các khóa chia sẻ sớm hơn, chỉ trong pha thu hẹp, giả sử tôi biết cách vào pha thu hẹp đó hoặc biết là mình đang ở pha thu hẹp.
And then strong strict 2PL, which I think the textbook might also call this rigorous 2PL, this just says that I'm going to hold all my shared locks and exclusive locks to the very end.
Còn strong strict 2PL, mà tôi nghĩ sách giáo trình cũng có thể gọi là rigorous 2PL, chỉ có nghĩa là tôi sẽ giữ tất cả khóa chia sẻ và khóa độc quyền cho đến tận cuối.
So technically, There isn't a shrinking phase. Just the whole thing is a growing phase.
Vì vậy về mặt kỹ thuật, không có pha thu hẹp. Toàn bộ chỉ là một pha mở rộng.
All right, we talked about the cascading abort problem. They instruct strong strict 2PL can avoid this because I'm not going to release my exclusive lock until I commit.
Được rồi, chúng ta đã nói về vấn đề hủy dây chuyền (cascading abort). Strong strict 2PL có thể tránh được điều này vì tôi sẽ không nhả khóa độc quyền cho đến khi commit.
So therefore, no other transaction can read my dirty read. And therefore, I won't have a cascading abort. We talked about how to handle deadlocks, either through deadlock detection or deadlock prevention.
Do đó, không giao dịch nào khác có thể đọc dữ liệu bẩn của tôi. Và vì vậy, sẽ không có cascading abort. Chúng ta đã nói về cách xử lý bế tắc, bằng cách phát hiện bế tắc hoặc ngăn ngừa bế tắc.
Deadlock detection was just identifying of cycles in the wait-for graph and killing some transaction to break the deadlock. You may end up having to kill multiple transactions to make that happen.
Phát hiện bế tắc chỉ là xác định các chu trình trong đồ thị chờ (wait-for graph) và hủy một transaction nào đó để phá vỡ bế tắc. Bạn có thể phải hủy nhiều transaction mới làm được điều đó.
And then deadlock prevention was the wound-wait and wait-die approach, where you order the, ordering based on the priority of their timestamp determines whether they can wait or not wait for another transaction that holds the lock that they want, and whether you're allowed to kill that other transaction and take their lock,
Còn ngăn ngừa bế tắc thì có hai cách tiếp cận là wound-wait và wait-die, trong đó bạn sắp xếp, thứ tự dựa trên độ ưu tiên của timestamp sẽ quyết định transaction có được chờ hay không được chờ một transaction khác đang giữ khóa mà nó muốn, và liệu bạn có được phép hủy transaction kia để lấy khóa của nó,
or you kill yourself.
hay là bạn tự hủy chính mình.
Then we talked about the multiple granularity locking. So these are intention locks. Like in the hierarchy I have at my top, I have a lock to my database or a lock to my tables.
Sau đó chúng ta nói về khóa đa mức độ chi tiết (multiple granularity locking). Đó chính là các khóa ý định (intention lock). Chẳng hạn trong phân cấp, ở trên cùng tôi có khóa trên cơ sở dữ liệu hoặc khóa trên các bảng.
And below that, I have a lock for pages or tuples or even single attributes.
Và bên dưới đó, tôi có khóa cho các trang, các tuple, hoặc thậm chí từng thuộc tính đơn lẻ.
So understand when you want to use intention locks or shared intention exclusive locks to minimize the amount of back and forth I have between my transaction and the lock manager, but also still maximize the amount of parallelism I would allow in the system.
Vì vậy hãy hiểu khi nào bạn muốn dùng khóa ý định hoặc khóa chia sẻ ý định độc quyền (shared intention exclusive) để giảm thiểu việc trao đổi qua lại giữa transaction của tôi và bộ quản lý khóa (lock manager), nhưng vẫn tối đa hóa mức độ song song mà hệ thống cho phép.
So the intention locks are the hints for us at the higher part of the hierarchy to say what's going on down below.
Như vậy, khóa ý định là những gợi ý cho chúng ta ở phần cao hơn của phân cấp để biết điều gì đang diễn ra ở bên dưới.
Then we talked about timestamp ordering transactions, or optimistic concurrency control. So understand what are the three phases in OCC.
Sau đó chúng ta nói về sắp xếp transaction theo timestamp, hay kiểm soát đồng thời lạc quan (optimistic concurrency control). Vì vậy hãy hiểu ba pha của OCC là gì.
You have the read phase, where I'm reading and writing to the database, but I'm making changes to my private workspace. And then when the transaction goes to commit, there's a validation phase.
Có pha đọc, trong đó tôi đọc và ghi vào cơ sở dữ liệu, nhưng các thay đổi được thực hiện trong không gian làm việc riêng của tôi. Rồi khi transaction đi đến commit, có một pha xác thực (validation).
And assume that for simplicity, you're going to run this in a single thread, and there's a single global latch that you take in the database to do this validation step to avoid weird conflicts and make your life easier.
Và để đơn giản, giả sử bạn chạy việc này trong một luồng duy nhất, và có một latch toàn cục duy nhất mà bạn lấy trong cơ sở dữ liệu để thực hiện bước xác thực này, nhằm tránh các xung đột kỳ lạ và làm mọi việc dễ dàng hơn.
But understand what the differences are between backwards validation and forwards validation.
Nhưng hãy hiểu sự khác nhau giữa xác thực lùi (backwards validation) và xác thực tiến (forwards validation).
Backwards is looking back to see transactions that previously committed to determine whether they wrote something that you didn't read, and therefore that would violate serializable ordering and kill yourself.
Xác thực lùi là nhìn lại các transaction đã commit trước đó để xác định xem chúng có ghi thứ gì mà bạn chưa đọc hay không, và do đó sẽ vi phạm thứ tự khả tuần tự hóa (serializable) và bạn tự hủy mình.
And then forwards validation would be: did a transaction that hasn't committed yet write to something that, sorry, read something that I'm going to write to, or try to write to?
Còn xác thực tiến thì hỏi: có transaction nào chưa commit đã ghi vào thứ mà, xin lỗi, đã đọc thứ mà tôi sắp ghi, hoặc đang cố ghi vào không?
And therefore, since they didn't see my update, if I commit, then again, that would violate the serializable ordering. Then we spent time talking about MVCC, multi-version concurrency control.
Và do đó, vì họ không thấy cập nhật của tôi, nên nếu tôi commit, thì một lần nữa, điều đó sẽ vi phạm thứ tự khả tuần tự hóa. Sau đó chúng ta dành thời gian nói về MVCC, kiểm soát đồng thời đa phiên bản.
Talked about the different ways to store the versions. There's the append-only approach, the time travel table, and then the delta records. So understand the trade-offs, the implications of these three different approaches.
Chúng ta đã nói về các cách lưu trữ các phiên bản khác nhau. Có cách chỉ nối thêm (append-only), bảng du hành thời gian (time travel table), và các bản ghi delta. Vì vậy hãy hiểu những đánh đổi và hệ quả của ba cách tiếp cận khác nhau này.
Then the way you would actually maintain the version chain: you go oldest to newest or newest to oldest. Your append-only can go both directions. And what are the pros and cons of those?
Rồi cách bạn thực sự duy trì chuỗi phiên bản: đi từ cũ nhất đến mới nhất hoặc từ mới nhất đến cũ nhất. Append-only có thể đi cả hai hướng. Và ưu nhược điểm của chúng là gì?
Delta storage typically goes newest to oldest, because the old version goes in that rollback segment or the delta storage area.
Lưu trữ delta thường đi từ mới nhất đến cũ nhất, vì phiên bản cũ được đưa vào rollback segment hoặc vùng lưu trữ delta.
Understand what happens in garbage collection, how we find the tuples that are reclaimable and remove them. What happens when we remove tuples and need to update indexes? When does that happen?
Hãy hiểu điều gì xảy ra trong garbage collection, cách chúng ta tìm ra các tuple có thể thu hồi và xóa chúng. Điều gì xảy ra khi chúng ta xóa tuple và cần cập nhật các chỉ mục? Việc đó xảy ra khi nào?
And how do we make sure that we don't have any conflicts when we do those things? And then there was a question on Piazza asking about MVCC with 2PL.
Và làm sao để đảm bảo không có xung đột khi chúng ta thực hiện những việc đó? Sau đó có một câu hỏi trên Piazza về MVCC với 2PL.
So I'm going to quickly just go over that again. I think the textbook is saying one thing, and I'm saying something else. So this is the setup we had before.
Vì vậy tôi sẽ nhanh chóng xem lại phần đó. Tôi nghĩ giáo trình nói một đằng, còn tôi nói một nẻo. Đây là thiết lập chúng ta đã có trước đó.
We have two transactions, T1 and T2, and they get timestamps in the beginning. T1 is going to read on A, and then it's going to write on A.
Chúng ta có hai giao dịch, T1 và T2, và chúng nhận timestamp ngay từ đầu. T1 sẽ đọc A, rồi sau đó ghi A.
And so the way this works is that there's no, you don't take shared locks on tuples, because you want to allow a writing transaction to create a new version.
Và cách hoạt động ở đây là không có, bạn không lấy khóa chia sẻ trên các tuple, vì bạn muốn cho phép một giao dịch ghi tạo ra một phiên bản mới.
But you can only allow one transaction to create a new version at a time. So there's an exclusive lock, but it's on the new version that's being created.
Nhưng bạn chỉ cho phép một giao dịch tạo phiên bản mới tại một thời điểm. Vậy nên có một khóa độc quyền, nhưng nó nằm trên phiên bản mới đang được tạo.
So this transaction, T1, is going to create a new version here, add to this. And we set the begin timestamp to our current timestamp. The end timestamp is currently infinity.
Giao dịch T1 này sẽ tạo một phiên bản mới ở đây, thêm vào chỗ này. Và chúng ta đặt begin timestamp bằng timestamp hiện tại của mình. End timestamp hiện tại là vô cực.
And since the previous timestamp, since we're going oldest to newest, is also infinity, we'll set that to be our timestamp. This is sort of bounding the visibility of this record.
Và vì timestamp trước đó, do chúng ta đi từ cũ nhất đến mới nhất, cũng là vô cực, nên ta sẽ đặt nó bằng timestamp của mình. Điều này giới hạn phạm vi hiển thị của bản ghi này.
So now if any transaction comes along with a timestamp less than 1, they would be able to read A0.
Vậy nếu bây giờ có giao dịch nào đến với timestamp nhỏ hơn 1, nó sẽ đọc được A0.
So then we do a context switch. T2 starts running. It reads A. And again, since this timestamp is 2, it's in the future. Logically, it's in the future from T1.
Sau đó ta chuyển ngữ cảnh. T2 bắt đầu chạy. Nó đọc A. Và một lần nữa, vì timestamp này là 2 nên nó nằm ở tương lai. Về mặt logic, nó nằm ở tương lai so với T1.
So therefore, it can't see the update yet, because T1 hasn't committed yet. So it's going to be able to read A0 because, again, readers don't block the writers.
Do đó nó chưa thấy được bản cập nhật, vì T1 chưa commit. Vậy nó sẽ đọc được A0 vì, một lần nữa, người đọc không chặn người ghi.
And then when it tries to write to it, it wants to try to get the exclusive lock on creating the new physical version for the single logical tuple.
Và khi nó cố ghi vào đó, nó muốn lấy khóa độc quyền để tạo phiên bản vật lý mới cho một tuple logic duy nhất.
And therefore, it has to stall and wait, assuming we're doing 2PL with deadlock detection.
Và do đó nó phải dừng lại và chờ, giả sử chúng ta dùng 2PL với phát hiện bế tắc.
If it was doing 2PL with wound-wait or wait-die, again, T2 could potentially steal the lock from T1, and it had to roll back its changes.
Nếu dùng 2PL với wound-wait hoặc wait-die, một lần nữa, T2 có thể giành khóa từ T1, và T1 phải rollback các thay đổi của nó.
But assume we're just doing simple 2PL with deadlock detection. So then now when T1 comes back and reads A, it'll read its own write that it did before.
Nhưng giả sử chúng ta chỉ dùng 2PL đơn giản với phát hiện bế tắc. Vậy khi T1 quay lại và đọc A, nó sẽ đọc chính bản ghi nó đã ghi trước đó.
That's fine. When it goes ahead and commits, then now Its status in the transaction table gets updated. It's now committed.
Điều đó ổn. Khi nó tiến hành commit, thì trạng thái của nó trong bảng giao dịch được cập nhật. Giờ nó đã được commit.
So now it would know that anybody coming along should be able to read this if they wanted to.
Vậy bây giờ hệ thống biết rằng bất kỳ ai đến sau đều có thể đọc phiên bản này nếu muốn.
And then now in this case here, it can create the new version. So to your point here, yes. And this here would be an example of a, what's that?
Và lúc này, trong trường hợp này, nó có thể tạo phiên bản mới. Vậy theo ý của bạn thì đúng, có. Và đây sẽ là một ví dụ về... gì nhỉ?
So it's technically write skew because I'm reading something that in the past, they were both seeing the same thing.
Về mặt kỹ thuật đó là write skew, vì tôi đọc một thứ mà trước đó cả hai giao dịch đều thấy cùng một giá trị.
But then I was allowed to overwrite it. What's that? There is an anomaly. Yeah, there is an anomaly. Yes, yes. And that's the whole point.
Nhưng sau đó tôi lại được phép ghi đè lên nó. Gì vậy? Có một anomaly. Đúng, có một anomaly. Vâng, vâng. Và đó chính là mấu chốt.
To make it fully serializable, the extra step would then be identify that you're trying to write the same thing.
Để đạt được tính khả tuần tự hóa đầy đủ, bước bổ sung sẽ là xác định rằng bạn đang cố ghi cùng một thứ.
And then you read something in the past that you should have read the other version. And you have to go kill that transaction.
Và bạn đã đọc một thứ trong quá khứ trong khi lẽ ra bạn phải đọc phiên bản khác. Và bạn phải hủy giao dịch đó.
So if you want to get full serializability, there's a dependency you have to maintain as well. That's what Postgres does.
Vì vậy, nếu muốn có tính khả tuần tự hóa đầy đủ, bạn cũng phải duy trì một quan hệ phụ thuộc. Đó là điều Postgres làm.
In this example, no. Even with regular MVCC without, yeah. With snapshot isolation, without the extra check, you need to make sure, am I violating the write skew anomaly?
Trong ví dụ này thì không. Ngay cả với MVCC thông thường mà không có, vâng. Với snapshot isolation, nếu không có bước kiểm tra bổ sung, bạn cần đảm bảo rằng mình có vi phạm write skew anomaly hay không?
You're not serializable. The fact you incur the write skew anomaly means you're not serializable.
Bạn không khả tuần tự hóa. Việc bạn gặp write skew anomaly nghĩa là bạn không khả tuần tự hóa.
The question is, what is the effect of MVCC have on 2PL? What is the performance overhead of maintaining versions?
Câu hỏi là MVCC có tác động gì đến 2PL? Chi phí hiệu năng của việc duy trì các phiên bản là gì?
There's pros and cons. The fact that I can read something without having to, I can read an older version. I have my readers not be blocked by the writers. There's advantage to that.
Có ưu điểm và nhược điểm. Việc tôi có thể đọc một thứ mà không cần, tôi có thể đọc một phiên bản cũ hơn. Các thao tác đọc của tôi không bị các thao tác ghi chặn. Đó là một lợi thế.
So is that worth it versus paying the overhead of maintaining the rollback segments and things like that? Or maintaining the different versions? You still have to maintain versions.
Vậy điều đó có đáng không so với việc phải trả chi phí để duy trì các rollback segment và những thứ tương tự? Hoặc duy trì các phiên bản khác nhau? Bạn vẫn phải duy trì các phiên bản.
With regular 2PL, I've got to maintain versions anyway. But it's almost like MVCC, where it's my private workspace. Because I have to have my undo buffer.
Với 2PL thông thường, dù sao tôi cũng phải duy trì các phiên bản. Nhưng nó gần giống MVCC, nơi đó là không gian làm việc riêng của tôi. Vì tôi phải có undo buffer của mình.
If I'm overwriting because it's a single version, I've got to be able to go back and remove that. So I've got to store the old version somewhere anyway.
Nếu tôi ghi đè, vì chỉ có một phiên bản, tôi phải có khả năng quay lại và loại bỏ thay đổi đó. Vì vậy dù sao tôi cũng phải lưu phiên bản cũ ở đâu đó.
And so you could store that in the write-ahead log.
Và bạn có thể lưu nó trong write-ahead log.
But then now, if that gets flushed to disk and I don't have it in memory, now when I abort and rollback, I have to go back to disk, read back the write-ahead log, and replay it.
Nhưng khi đó, nếu nó bị flush xuống đĩa và tôi không còn nó trong bộ nhớ, thì khi tôi hủy và rollback, tôi phải quay lại đĩa, đọc lại write-ahead log và phát lại nó.
There's no free lunch.
Không có bữa trưa nào miễn phí.
The question is, the statement is, the textbook says that, yeah, I saw that. The textbook says that MVCC with 2PL always uses strict 2PL.
Câu hỏi là, phát biểu là, sách giáo khoa nói rằng, vâng, tôi đã thấy. Sách giáo khoa nói rằng MVCC với 2PL luôn dùng strict 2PL.
So I think the textbook is wrong. So I'll post it on Piazza. So I'm going by, there's this famous textbook on nothing but transactions from Jim Gray and Reuter.
Tôi nghĩ sách giáo khoa sai. Nên tôi sẽ đăng lên Piazza. Tôi dựa vào cuốn sách giáo khoa nổi tiếng này chỉ nói về giao dịch của Jim Gray và Reuter.
The guy that coined ACID and Jim Gray, the attorney Reuter, are from the 80s that talk about how they do MVCC. And their definition doesn't have to be strict.
Người đặt ra thuật ngữ ACID là Jim Gray, còn Reuter, từ những năm 80, nói về cách họ làm MVCC. Và định nghĩa của họ không nhất thiết phải là strict.
The question is, should we assume strict? Any question on the exam will be very explicit on what the protocol it is to avoid any ambiguities.
Câu hỏi là, chúng ta có nên giả định là strict không? Mọi câu hỏi trong đề thi sẽ nêu rất rõ ràng giao thức nào, để tránh mọi sự mơ hồ.
But Postgres does MVCC with 2PL. I'm pretty sure they're not using strict 2PL.
Nhưng Postgres thực hiện MVCC với 2PL. Tôi khá chắc là họ không dùng strict 2PL.
SQL Server does strong strict, I think.
Tôi nghĩ SQL Server dùng strong strict.
Yeah, I'll post a link afterwards.
Vâng, lát nữa tôi sẽ đăng một đường liên kết.
Again, the main takeaway is, for any question, I would be very explicit about, it's this protocol with this versioning, and this concurrency stream, and this, like, this versioning.
Một lần nữa, điểm cần nhớ chính là, với bất kỳ câu hỏi nào, tôi sẽ nêu thật rõ: đây là giao thức này với cách quản lý phiên bản này, và cơ chế kiểm soát đồng thời này, và, kiểu như, cách quản lý phiên bản này.
Here's the version chain ordering. We'll lay out things in full detail. So it's not like, oh, it could be this. But if it's this, I want to avoid all that.
Đây là thứ tự của chuỗi phiên bản. Chúng tôi sẽ trình bày mọi thứ thật chi tiết. Nên sẽ không kiểu như, ồ, có thể là cái này. Mà nếu là cái này thì, tôi muốn tránh hết những chuyện đó.
All right, then after transactions, we talk about how to recover our transactions if there's a crash. We talked about the two main policies you have in your buffer pool implementation, steal versus no steal.
Được rồi, sau phần giao dịch, chúng ta nói về cách khôi phục các giao dịch nếu xảy ra sự cố hỏng hệ thống. Chúng ta đã nói về hai chính sách chính trong việc cài đặt buffer pool, steal so với no steal.
Steal means that I can write out dirty pages from transactions I haven't committed yet out to disk. No steal says you cannot.
Steal nghĩa là tôi có thể ghi xuống đĩa các trang dirty của những giao dịch chưa commit. No steal thì nói rằng không được.
Force says that when a transaction commits, all its dirty pages that are in the buffer pool have to be written to disk before you tell the outside world your transaction's committed.
Force nói rằng khi một giao dịch commit, tất cả các trang dirty của nó trong buffer pool phải được ghi xuống đĩa trước khi bạn báo ra bên ngoài rằng giao dịch đã commit.
No force says you don't have to do that. So write-ahead log is using what?
No force nói rằng bạn không cần làm vậy. Vậy write-ahead log dùng cái nào?
Steal, no force, right?
Steal, no force, đúng không?
Because write-ahead log allows us to flush out the dirty pages from uncommitted transactions, as long as the log records that correspond to the changes to the pages, as long as that's flushed to disk, then that's okay.
Vì write-ahead log cho phép ta ghi xuống đĩa các trang dirty của những giao dịch chưa commit, miễn là các bản ghi log tương ứng với những thay đổi trên các trang đó đã được ghi xuống đĩa, thì như vậy là ổn.
We talked about shadow paging. Again, I was saying the pros and the cons of this approach relative to write-ahead logging.
Chúng ta đã nói về shadow paging. Một lần nữa, tôi đã nói về ưu điểm và nhược điểm của cách tiếp cận này so với write-ahead logging.
And then we talked about, again, how write-ahead log, the notion of these log sequence numbers permeate all throughout our implementation of our database system, including the buffer pool manager.
Và rồi chúng ta lại nói về việc với write-ahead log, khái niệm số thứ tự log (LSN) len vào khắp mọi phần trong việc cài đặt hệ quản trị cơ sở dữ liệu, bao gồm cả buffer pool manager.
And it's what I just said: I can't flush a dirty page until the page LSN, or the newest LSN that modified that page, until that's been written out to disk.
Và đúng như tôi vừa nói: tôi không thể ghi một trang dirty xuống đĩa cho đến khi page LSN, tức LSN mới nhất đã sửa trang đó, được ghi xuống đĩa.
And once that's flushed, then I can flush the dirty page.
Và khi nó đã được ghi rồi, thì tôi mới có thể ghi trang dirty.
Then we talked about how to handle crash recovery, again, based on write-ahead logging. There's nothing to recover in shadow paging. There's nothing to do.
Sau đó chúng ta nói về cách xử lý khôi phục sau sự cố, một lần nữa, dựa trên write-ahead logging. Với shadow paging thì không có gì để khôi phục. Không phải làm gì cả.
When you come back, the database is guaranteed to be in a consistent state, so you don't do anything. It's just write-ahead logging, we need to do extra work.
Khi hệ thống chạy lại, cơ sở dữ liệu được đảm bảo ở trạng thái nhất quán, nên bạn không phải làm gì. Còn với write-ahead logging thì ta cần làm thêm việc.
And we choose to use write-ahead logging over shadow paging because the runtime performance is faster with write-ahead logging versus shadow paging. But if you care about instant recovery, then you would do shadow paging.
Và ta chọn dùng write-ahead logging thay vì shadow paging vì hiệu năng lúc chạy nhanh hơn với write-ahead logging so với shadow paging. Nhưng nếu bạn quan tâm đến khôi phục tức thì, thì bạn sẽ dùng shadow paging.
We talked about the different notions of checkpoints, so fuzzy versus non-fuzzy, right?
Chúng ta đã nói về các khái niệm khác nhau của checkpoint, tức fuzzy so với non-fuzzy, đúng không?
And then within the fuzzy checkpoints, we talked about the dirty page table, the active transaction table, all the components we need to do the ARIES-based recovery based on checkpoints and the write-ahead log.
Và trong các fuzzy checkpoint, chúng ta đã nói về bảng trang bẩn (dirty page table), bảng giao dịch đang hoạt động (active transaction table), tất cả các thành phần cần có để thực hiện khôi phục dựa trên ARIES dựa trên các checkpoint và nhật ký ghi trước (write-ahead log).
Then, again, we went through very quickly at the end of the semester talking about distributed databases. So, again, we can't ask you too many, too low-level details.
Sau đó, một lần nữa, chúng ta đã đi rất nhanh qua phần cuối học kỳ nói về cơ sở dữ liệu phân tán. Vì vậy, một lần nữa, chúng tôi không thể hỏi quá nhiều chi tiết quá cấp thấp.
It's the high-level concepts that we care about. So what are the different system architectures? Basically, shared disk versus shared nothing. How we can do replication: multi-primary versus primary-replica, or leader-follower.
Điều chúng tôi quan tâm là các khái niệm ở mức cao. Vậy các kiến trúc hệ thống khác nhau là gì? Về cơ bản là shared disk so với shared nothing. Cách chúng ta thực hiện nhân bản: multi-primary so với primary-replica, hay leader-follower.
Different partitioning schemes, horizontal partitioning. Then we talked about two-phase commit and Paxos. And, again, that was last class. We obviously went through it pretty quickly, so we can't ask you any low-level detail questions.
Các sơ đồ phân vùng khác nhau, phân vùng ngang. Sau đó chúng ta nói về two-phase commit và Paxos. Và, một lần nữa, đó là buổi học trước. Rõ ràng là chúng ta đã đi qua khá nhanh, nên chúng tôi không thể hỏi các câu về chi tiết cấp thấp.
How we do query execution, in particular, how we do distributed joins in our system. And then the semi-join optimization, just passing along Bloom filters instead of the actual entire dataset.
Cách thực thi truy vấn, cụ thể là cách thực hiện phép nối phân tán trong hệ thống của chúng ta. Và tiếp theo là tối ưu hóa semi-join, chỉ truyền đi các Bloom filter thay vì toàn bộ tập dữ liệu thực sự.
So last class, there was a question about, in the context of Paxos, in comparison with two-phase commit, how do we handle integrity constraint violations?
Vậy ở buổi học trước, có một câu hỏi về Paxos, so với two-phase commit, chúng ta xử lý các vi phạm ràng buộc toàn vẹn như thế nào?
And what I sort of messed up in the description of it is the thing to understand about two-phase commit is that you can have all of the...
Và điều tôi đã giải thích chưa tốt là điều cần hiểu về two-phase commit là bạn có thể có tất cả...
In two-phase commit, all the nodes have to agree, the participants have to agree that we want to commit this transaction. And in Paxos, you need the majority.
Trong two-phase commit, tất cả các nút phải đồng ý, các bên tham gia phải đồng ý rằng chúng ta muốn commit giao dịch này. Còn trong Paxos, bạn cần đa số.
That means that if you're going to use Paxos or Raft, you have to have the decision of whether this transaction has violated any integrity constraints.
Điều đó có nghĩa là nếu bạn dùng Paxos hoặc Raft, thì quyết định về việc giao dịch này có vi phạm ràng buộc toàn vẹn nào hay không phải được xác định trước khi bạn bắt đầu quá trình commit.
It has to be figured out before you begin the commit process.
So another way to think about it is it has to be a deterministic operation that we want to do this yes or no.
Nói cách khác, đó phải là một thao tác có tính xác định, rằng chúng ta muốn làm điều này, có hoặc không.
And it can't be any ambiguity between the different nodes to say, like, one guy says no because they're checking things at the moment after I've started the commit process.
Và không được có sự mơ hồ giữa các nút khác nhau, kiểu như một nút nói không vì nó kiểm tra các thứ vào thời điểm sau khi tôi đã bắt đầu quá trình commit.
So in two-phase commit, again, everyone has to agree to commit.
Vì vậy trong two-phase commit, một lần nữa, mọi người đều phải đồng ý commit.
So when this guy says, hey, we're going to go to commit, prepare, and this guy says okay, and this guy says not okay, this is allowed to happen under two-phase commit because every node can independently decide whether this thing is allowed to commit or not.
Khi nút này nói, này, chúng ta sẽ commit, prepare, và nút này nói được, còn nút này nói không được, điều này được phép xảy ra trong two-phase commit vì mỗi nút có thể tự quyết định một cách độc lập liệu giao dịch này có được phép commit hay không.
And so this is where you would check for integrity constraint violations.
Và đây là chỗ bạn sẽ kiểm tra các vi phạm ràng buộc toàn vẹn.
In Paxos, what would happen, or Raft, what would happen is The coordinator node, or I think the proposer node, or the leader, they would determine at that point when we begin the commit process, this transaction has not violated any of the integrity constraints, therefore I'm allowed to commit.
Trong Paxos, hay Raft, điều xảy ra là nút điều phối, hoặc tôi nghĩ là nút proposer, hay leader, sẽ xác định ngay tại thời điểm chúng ta bắt đầu quá trình commit rằng giao dịch này không vi phạm bất kỳ ràng buộc toàn vẹn nào, do đó tôi được phép commit.
And therefore, you're just getting everyone else to agree that this is the order in which we're going to commit this transaction that has already passed our validation steps.
Và vì vậy, bạn chỉ đang khiến mọi nút khác đồng ý rằng đây là thứ tự mà chúng ta sẽ commit giao dịch này, giao dịch vốn đã vượt qua các bước kiểm tra hợp lệ của chúng ta.
When we have a particular participant on a board, if somebody else tries to commit another transaction and says, "I want to go next in the log," so again, it's a state machine.
Khi chúng ta có một thành viên nhất định trên bảng, nếu có ai khác cố commit một transaction khác và nói: "Tôi muốn đi tiếp theo trong log", vậy nên, một lần nữa, đây là một máy trạng thái.
You're just trying to order the commits, and if there's like a split brain where there's a network partition, each side wants to start committing transactions on their own, and then when they form back together and it gets reconnected, somebody else thinks they're the leader and they try to propose to commit a transaction.
Bạn chỉ đang cố sắp xếp thứ tự các lần commit, và nếu có hiện tượng split brain khi mạng bị phân vùng, mỗi bên đều muốn tự bắt đầu commit các transaction, rồi khi hai bên hợp lại và được kết nối trở lại, có một nút khác nghĩ rằng mình là leader và cố đề xuất commit một transaction.
But now you would have, if you allow that to happen, then one node would say it's transaction one followed by two, another one would say it's two followed by one.
Nhưng nếu bạn cho phép điều đó xảy ra, thì một nút sẽ nói thứ tự là transaction một rồi đến hai, còn một nút khác sẽ nói là hai rồi đến một.
You can't allow that to happen, and that's why you have to determine, you have to be deterministic in the decision that this thing's allowed to commit at the moment you commit.
Bạn không thể cho phép điều đó xảy ra, và đó là lý do bạn phải xác định, bạn phải có tính xác định trong quyết định rằng transaction này được phép commit ngay tại thời điểm bạn commit.
Yes?
Bạn hỏi gì?
The question is, if the constraints are very complicated, aren't the nodes going to have to coordinate with each other to, which would just be the same amount of overhead of running Paxos?
Câu hỏi là, nếu các ràng buộc rất phức tạp, thì các nút chẳng phải sẽ phải phối hợp với nhau để, và như vậy chi phí chẳng phải bằng chi phí chạy Paxos sao?
So the dirty secret is in distributed systems, oftentimes they don't have the full integrity and referential constraints that a single node system would have.
Sự thật ít ai nói là trong các hệ phân tán, thường thì chúng không có đầy đủ các ràng buộc toàn vẹn và ràng buộc tham chiếu như một hệ thống đơn nút.
Oftentimes you don't get foreign key constraints in a distributed database because that checking is expensive. What's that? The question is, what about Spanner? I think Spanner gives you primary keys.
Thường thì bạn không có ràng buộc khóa ngoại trong cơ sở dữ liệu phân tán vì việc kiểm tra đó rất tốn kém. Sao cơ? Câu hỏi là còn Spanner thì sao? Tôi nghĩ Spanner có khóa chính.
Spanner gives you unique keys. I think they'll give you also foreign keys as well. What's that? Say it again? Would they check it for you? Oh, the check keyword in SQL.
Spanner có khóa duy nhất. Tôi nghĩ họ cũng có cả khóa ngoại. Sao cơ? Em nói lại được không? Họ có kiểm tra giúp bạn không? À, từ khóa check trong SQL.
I mean, like check not null? Sure, right?
Ý tôi là như check not null ấy? Có chứ, đúng không?
You're talking about what we call, like, ALTER TABLE, CREATE TABLE? Those checks aren't that complicated, though. I mean, you can't, it's the asserts. That's what nobody supports.
Bạn đang nói về cái mà ta gọi là ALTER TABLE, CREATE TABLE phải không? Nhưng những kiểm tra đó không phức tạp lắm. Ý tôi là, đó là các assert. Đó là thứ không ai hỗ trợ.
You can do a global assert that says anytime I commit to this table, run this full query, and if it returns, I think, if it returns anything, then I think it's a violation.
Bạn có thể đặt một assert toàn cục nói rằng mỗi khi tôi commit vào bảng này, hãy chạy toàn bộ truy vấn này, và nếu nó trả về, tôi nghĩ, bất cứ thứ gì thì coi như vi phạm.
So as long as the query returns null, then my constraint's not violated. Nobody supports that in a distributed environment because that could just be a broadcast query to everyone.
Vậy miễn là truy vấn trả về null thì ràng buộc của tôi không bị vi phạm. Không ai hỗ trợ điều đó trong môi trường phân tán vì nó có thể trở thành một truy vấn broadcast tới tất cả mọi nút.
For every single transaction I actually commit. So no one does that. With Spanner, I think, we can double check.
Cho từng transaction mà tôi thực sự commit. Nên không ai làm vậy. Với Spanner, tôi nghĩ chúng ta có thể kiểm tra lại.
Spanner's gonna be foreign keys, primary keys, basic check constraints, but oftentimes the foreign keys is the first thing to go in most systems in distributed environments.
Spanner sẽ có khóa ngoại, khóa chính, các ràng buộc check cơ bản, nhưng thường thì khóa ngoại là thứ đầu tiên bị bỏ đi trong hầu hết các hệ thống ở môi trường phân tán.
Yeah, because Spanner, they have foreign keys, like that.
Vâng, vì Spanner có khóa ngoại, như vậy.
The statement is, Spanner has foreign keys that involve some internet communication. Depends on how the, how the tables are partitioned. Yeah.
Ý em là Spanner có khóa ngoại cần một số giao tiếp qua mạng. Còn tùy cách các bảng được phân vùng. Vâng.
If, like, if you have a student table and you have ID, and then I have a enroll table with student ID and the foreign key references the student ID, if I partition both tables so that, like, student ID 1, 2, 3 and enrolled records with student ID 1, 2, 3 are in the same box, that's not a big deal.
Ví dụ, nếu bạn có một bảng student và bạn có ID, và rồi tôi có một bảng enroll với student ID và khóa ngoại tham chiếu đến student ID, nếu tôi phân vùng cả hai bảng sao cho student ID 1, 2, 3 và các bản ghi đăng ký với student ID 1, 2, 3 nằm trong cùng một máy, thì không có vấn đề lớn.
It's the broadcast ones that cause problems. For partitioning over the foreign keys.
Những trường hợp phải broadcast mới gây ra vấn đề. Đối với việc phân vùng theo khóa ngoại.
Yeah. So, like, oftentimes some systems will say, like, if you don't partition, if you don't set the partition key to be the same as the foreign key, we're not gonna check it for you.
Vâng. Nên thường thì một số hệ thống sẽ nói, nếu bạn không phân vùng, nếu bạn không đặt khóa phân vùng giống với khóa ngoại, thì chúng tôi sẽ không kiểm tra giúp bạn.
And they're, you know, whether or not it's okay for your application depends on your system. Okay. All right.
Và họ, bạn biết đấy, việc điều đó có chấp nhận được với ứng dụng của bạn hay không tùy thuộc vào hệ thống của bạn. Được rồi. Nào.
So, again, quickly, the things that aren't gonna be exam, any of the flash talks, any of the seminar talks we've had on Mondays or Tuesdays, those aren't the final exams.
Vậy nhắc lại nhanh, những thứ sẽ không có trong đề thi: các flash talk, các buổi seminar mà chúng ta đã có vào các thứ Hai hoặc thứ Ba, những thứ đó không nằm trong đề thi cuối kỳ.
And then, like, again, sometimes I go off the rails and we just had this, you know, diatribe about Spanner. No, no, no, it's fine. I mean, Spanner is a fascinating system. It's, like, I...
Và, nhắc lại, đôi khi tôi đi lạc đề và vừa rồi chúng ta có một tràng chỉ trích dài về Spanner. Không, không, không sao đâu. Ý tôi là, Spanner là một hệ thống rất hấp dẫn. Kiểu như, tôi...
I'm not gonna cover it today, but, like, we can talk about it another time.
Hôm nay tôi sẽ không đề cập đến nó, nhưng chúng ta có thể nói về nó vào dịp khác.
But anything that, like, oh, SQL Server does this or MySQL does that, Postgres does that, that's obviously not gonna be an exam.
Nhưng bất cứ điều gì kiểu như SQL Server làm thế này hay MySQL làm thế kia, Postgres làm thế nọ, thì rõ ràng sẽ không có trong đề thi.
Because, again, that's just, like, an example of an implementation of the concepts that we talked about throughout the semester. Okay? All right. Any final questions about the final?
Bởi vì, nhắc lại, đó chỉ là một ví dụ về cách triển khai của những khái niệm mà chúng ta đã học suốt học kỳ. Được chứ? Nào. Còn câu hỏi cuối cùng nào về kỳ thi cuối kỳ không?
Okay. So, let's try to get through 721 in, we have, what, 45 minutes? Let's see what we can do. Okay.
Được rồi. Vậy hãy cố gắng học xong 721 trong chúng ta còn, khoảng 45 phút nhỉ? Hãy xem chúng ta làm được gì. Được rồi.
So, I showed this slide, I think, in lecture 13 or so, where I said, here's all the ways you can make sequential scans go faster. Right? We've covered all of these.
Tôi đã chiếu slide này, tôi nghĩ là ở bài giảng 13 hay gần đó, khi tôi nói, đây là tất cả các cách để làm cho quét tuần tự chạy nhanh hơn. Đúng không? Chúng ta đã học hết những cách này.
Except for materialized views and result caching.
Trừ materialized view và result caching.
Result caching basically says, if my same SQL query shows up multiple times and the data hasn't changed, I just cache the result and give it back to you.
Về cơ bản result caching nghĩa là, nếu cùng một truy vấn SQL xuất hiện nhiều lần và dữ liệu không thay đổi, tôi chỉ cần lưu đệm kết quả và trả lại cho bạn.
So I don't actually run the query, I just give you back a cache result. And some systems will do that. Materialized view, these are more complicated if you want to do incremental maintenance.
Vậy là tôi không thực sự chạy truy vấn, mà chỉ trả lại kết quả đã lưu đệm. Và một số hệ thống sẽ làm vậy. Materialized view, những cái này phức tạp hơn nếu bạn muốn bảo trì gia tăng.
This is like, if I define a materialized view, I define a SQL query, I want to cache the result, but then anytime the data changes, rather than just re-running the entire query, I can do, like, an incremental update.
Nghĩa là, nếu tôi định nghĩa một materialized view, tôi định nghĩa một truy vấn SQL, tôi muốn lưu đệm kết quả, nhưng rồi mỗi khi dữ liệu thay đổi, thay vì chạy lại toàn bộ truy vấn, tôi có thể cập nhật gia tăng.
For some things it's easy. Like a count with a group by, or a key, every time I add a new key for that, I increment the count by one.
Với một số thứ thì dễ. Như count với group by, hoặc một khóa, mỗi lần tôi thêm một khóa mới, tôi tăng count lên một.
It's the joins are when things are complicated. Yes.
Phép join mới là chỗ phức tạp. Vâng, bạn hỏi đi.
The question is, will the exam take four or three hours? No.
Câu hỏi là: bài thi sẽ kéo dài bốn hay ba giờ? Không.
You can sit around for three hours, if you want, but it'll be the same, roughly the same length of material as the midterm. So hour one of 20.
Nếu muốn, các em có thể ngồi ba giờ, nhưng nó sẽ như nhau, lượng nội dung có độ dài gần bằng bài thi giữa kỳ. Vậy là giờ thứ nhất trong 20.
And I would say the, because we chart this, because I love data, there does not seem to be a correlation between how long it takes somebody to complete the exam and their grade.
Và tôi có thể nói là, vì chúng tôi vẽ biểu đồ cái này, vì tôi yêu dữ liệu, dường như không có mối tương quan nào giữa thời gian một người làm xong bài thi và điểm của họ.
So the person usually finishes first, sometimes it gets the highest grade, sometimes it gets the lowest grade.
Người thường nộp bài đầu tiên, đôi khi đạt điểm cao nhất, đôi khi lại thấp nhất.
And the person that finishes fast, the one year the person got a perfect score, and they finish at the very end. So, you take as long as you want. Say that again?
Và người làm xong nhanh, có một năm người đó được điểm tuyệt đối, và họ nộp bài ở phút cuối cùng. Vì vậy, các em cứ làm bao lâu tùy thích. Em nói lại được không?
Like, we would write on the exam when someone does it. Yeah. Um, okay, so again, these are all things we talked about the entire semester. Again, materialized views, again, these are hard to do.
Kiểu như, chúng tôi sẽ ghi lên bài thi khi nào ai đó làm xong. Đúng vậy. Ừm, được rồi, một lần nữa, đây đều là những thứ chúng ta đã nói suốt cả học kỳ. Lại nói về materialized view, những thứ này khó thực hiện.
Like in Postgres, when you declare a materialized view, it won't increment it for you, you got to call manually refresh, right? In some systems that can actually maintain them incrementally.
Ví dụ trong Postgres, khi em khai báo một materialized view, nó sẽ không tự cập nhật tăng dần cho em, em phải gọi refresh thủ công, đúng không? Trong một số hệ thống thì thực sự có thể duy trì chúng theo kiểu tăng dần.
So, I want to focus on this down here. So we're, 721 is typically about analytical systems, how to make a, how to build a system that run OLAP queries as fast as possible.
Vậy nên tôi muốn tập trung vào phần ở dưới này. Môn 721 thường nói về các hệ thống phân tích, cách để xây dựng một hệ thống chạy các truy vấn OLAP nhanh nhất có thể.
So let's talk about code specialization and compilation. Alright, so they, we have a really simple select query like this.
Vậy hãy nói về code specialization và compilation. Được rồi, giả sử ta có một truy vấn select rất đơn giản như thế này.
Select star from table where key is greater than low value, and key is less than high value.
Select star from table where key lớn hơn giá trị thấp, và key nhỏ hơn giá trị cao.
So the first thing is like, how do we organize our code to make this run as fast as possible without doing any special hardware tricks, right?
Điều đầu tiên là, làm sao tổ chức code để truy vấn này chạy nhanh nhất có thể mà không dùng mẹo phần cứng đặc biệt nào, đúng không?
And so we will be mindful of what modern CPUs look like and what they do for us, and then we can actually design and write code in such a way that maybe is not intuitive for us as humans to write, but actually turns out to be the best thing to do for a modern superscalar CPU, right?
Và ta sẽ lưu ý các CPU hiện đại trông như thế nào và chúng làm gì cho ta, rồi ta có thể thiết kế và viết code theo cách mà có thể không trực quan với con người khi viết, nhưng thực ra lại là điều tốt nhất cho một CPU superscalar hiện đại, đúng không?
So this is, you know, rough code that you would have seen in BusTub, right?
Đây là đoạn code sơ lược mà các em đã thấy trong BusTub, đúng không?
Get it for every single tuple on the table, Go look up the key, and then apply our predicate here, right?
Với mỗi tuple trong bảng, đi tra key, rồi áp dụng predicate của ta ở đây, đúng không?
And if the key satisfies our predicate, then we'll copy the tuple into our output buffer. Assume we're doing vectorized query processing, right?
Và nếu key thỏa mãn predicate, thì ta sẽ sao chép tuple vào output buffer. Giả sử ta đang xử lý truy vấn theo kiểu vectorized, đúng không?
But, you know, if you've taken an architecture class, there's a problem here, right? Assume I have a billion tuples, I'm ripping through this.
Nhưng, nếu các em đã học môn kiến trúc máy tính, thì ở đây có một vấn đề, đúng không? Giả sử tôi có một tỉ tuple và đang chạy ào qua chúng.
What's gonna be the slow thing for us? Branching, the if clause, right? Because how does a super scalar CPU work?
Điều gì sẽ làm ta chậm? Rẽ nhánh, mệnh đề if, đúng không? Vì CPU superscalar hoạt động như thế nào?
It tries to predict, whenever it sees a jump, right, or a branch, it tries to predict what branch you're gonna go down, right? Is this thing gonna satisfy, true or not?
Mỗi khi thấy một lệnh nhảy, hay một nhánh, nó cố dự đoán xem em sẽ đi vào nhánh nào, đúng không? Điều này sẽ thỏa mãn, đúng hay không?
And then it speculatively executes the instructions, because they're all within, you know, within its pipeline, and it speculatively executes instructions assuming you're gonna go down a certain path in the branch.
Rồi nó thực thi suy đoán các lệnh, vì chúng đều nằm trong đường ống của nó, và nó thực thi suy đoán các lệnh với giả định bạn sẽ đi theo một nhánh nhất định.
Right? And if you get it wrong, it's like OCC: you abort the changes you made, roll back, and then re-execute things again, but you gotta flush your pipeline to roll it back.
Đúng không? Và nếu dự đoán sai, nó giống như OCC: bạn hủy các thay đổi đã thực hiện, rollback, rồi thực thi lại, nhưng bạn phải xả đường ống (pipeline) để rollback.
So what you wanna write in a modern DBMS for super scalar CPUs is code like this, where I go get every single tuple in my table, and the first thing I'm gonna do is I'm gonna copy it into my output buffer, right?
Vì vậy, thứ bạn nên viết trong một DBMS hiện đại cho các CPU siêu vô hướng là đoạn mã như thế này, trong đó tôi lấy từng tuple một trong bảng, và việc đầu tiên tôi làm là sao chép nó vào bộ đệm đầu ra, đúng không?
And then later on, I'm gonna check my predicate, and now I'm just gonna do a ternary operation, and between ones and zeros, and that's gonna determine if both of these are satisfied, they're true, then delta is equal to one, and that's gonna increment my counter of where I'm writing to my output buffer by one.
Sau đó, tôi kiểm tra vị từ (predicate), và giờ tôi chỉ thực hiện một phép toán ba ngôi, giữa các giá trị một và không, và nó sẽ quyết định: nếu cả hai điều kiện này đều thỏa mãn, tức là đúng, thì delta bằng một, và điều đó sẽ tăng bộ đếm vị trí tôi ghi vào bộ đệm đầu ra lên một.
Right?
Đúng không?
I'm ignoring things when you break out of the loop, like, check to see where the last thing should even be there or not, but like, you know, that's true of a code to write too.
Tôi đang bỏ qua phần khi thoát khỏi vòng lặp, kiểu như kiểm tra xem phần tử cuối cùng có nên nằm ở đó hay không, nhưng bạn biết đấy, mã thật cũng phải viết như vậy.
Uh, yeah, like this question: why, why do you need a ternary to do key less than one, zero? And it, yes, it would give you one and zero.
Ừ, như câu hỏi này: tại sao, tại sao cần phép ba ngôi để làm key nhỏ hơn một, không? Và đúng, nó sẽ cho bạn một và không.
Just being, just being more explicit. The compiler will, will take care of that, yes. Question: are you still branching? No. Assume the compiler gets rid of that. Right?
Chỉ là viết tường minh hơn thôi. Trình biên dịch sẽ lo việc đó, đúng. Câu hỏi: bạn vẫn còn rẽ nhánh chứ? Không. Giả sử trình biên dịch loại bỏ nó. Đúng không?
Right?
Đúng không?
And again, this seems counterintuitive to us as humans, like, I'm, I'm copying every single time, and then check to see whether I should have copied the last thing I copied, and then if it doesn't satisfy to true, then I loop back around and just overwrite the last one.
Và một lần nữa, điều này có vẻ phản trực giác với con người chúng ta, kiểu như, tôi sao chép mọi lần, rồi kiểm tra xem lẽ ra có nên sao chép thứ vừa sao chép không, và nếu nó không thỏa mãn điều kiện đúng, thì tôi lặp lại và chỉ ghi đè lên phần tử trước.
And again, when I break out of the loop, I gotta check the, the delta of the last one to see whether I should keep it or not.
Và khi thoát khỏi vòng lặp, tôi phải kiểm tra delta của phần tử cuối để xem có nên giữ nó hay không.
The question is, the copy might be really expensive as well. Again, assuming I'm operating on vectors of data on, in a columnar format, I'm ripping through columns.
Câu hỏi là, việc sao chép cũng có thể rất tốn kém. Một lần nữa, giả sử tôi đang xử lý các vectơ dữ liệu ở định dạng cột, tôi quét rất nhanh qua các cột.
So, this is a, a graph from a, from the paper from the, the CWI guys from a few years ago, but this is showing you the, the, the performance difference between these two approaches.
Đây là một đồ thị từ bài báo của nhóm CWI vài năm trước, nhưng nó cho bạn thấy sự khác biệt hiệu năng giữa hai cách tiếp cận này.
So, it's kind of hard to see the blue line that loops at the top, that's the branching one. And the y-axis, sorry, the x-axis here is the, is the selectivity of a predicate.
Hơi khó nhìn thấy đường màu xanh nằm ở trên cùng, đó là cách dùng rẽ nhánh. Và trục y, xin lỗi, trục x ở đây là độ chọn lọc (selectivity) của vị từ.
Right?
Đúng không?
So, when the selectivity is zero or less than five, five percent, then most of the tuples aren't satisfying my predicate and the CPU's branch predictor is doing a good job figuring out I'm not gonna need to go down to the branch.
Khi độ chọn lọc bằng không hoặc dưới năm phần trăm, thì hầu hết các tuple không thỏa vị từ và bộ dự đoán nhánh của CPU làm rất tốt việc nhận ra rằng tôi sẽ không cần đi vào nhánh đó.
But then above some threshold, as it goes up, as the selectivity goes up, it's getting more predictions wrong and so now you're paying this overhead of having to, you know, roll back the changes in your pipeline and go back.
Nhưng khi vượt qua một ngưỡng nào đó, khi độ chọn lọc tăng lên, nó dự đoán sai nhiều hơn và lúc này bạn phải chịu chi phí phụ của việc phải bạn biết đấy, phải hoàn tác các thay đổi trong đường ống của mình và quay lại.
And whereas the red line, the no branching one, it's a fixed cost.
Còn đường màu đỏ, cách không rẽ nhánh, thì là chi phí cố định.
So no matter what, I'm doing that copy, assuming I can do that efficiently, and then I don't pay the penalty of any branch or jumps because I'm just always doing it.
Nên dù thế nào đi nữa, tôi vẫn thực hiện phép sao chép đó, giả sử tôi làm được một cách hiệu quả, và rồi tôi không phải trả cái giá của bất kỳ nhánh hay lệnh nhảy nào, vì lúc nào tôi cũng cứ làm như vậy.
And whether or not I overwrite the last one or not depends on whether the predicate gets satisfied to true. All right? So we're gonna design code in this way.
Còn việc tôi có ghi đè lên phần tử cuối cùng hay không thì phụ thuộc vào việc vị từ có được thỏa mãn, tức là đúng, hay không. Được chứ? Vậy chúng ta sẽ thiết kế mã theo cách này.
Again, it seems counterintuitive as humans, and the compiler isn't gonna do this for you. This is something, you know, we would have to write.
Một lần nữa, với con người thì điều này có vẻ phản trực giác, và trình biên dịch sẽ không làm điều này giúp bạn. Đây là thứ mà chúng ta phải tự viết.
And most of the modern OLAP systems are gonna do this. All right.
Và hầu hết các hệ thống OLAP hiện đại đều sẽ làm như vậy. Được rồi.
So the next thing we gotta do is, how can we speed this up even further, taking advantage of modern CPU instructions, SIMD?
Điều tiếp theo cần làm là, làm sao tăng tốc thêm nữa, bằng cách tận dụng các lệnh CPU hiện đại, SIMD?
Who here doesn't know what SIMD is? Who here knows what SIMD is? All right, everyone does. Good. All right. So here's our simple branchless version of the code before.
Ở đây ai chưa biết SIMD là gì? Ai biết SIMD là gì? Được rồi, mọi người đều biết. Tốt. Được rồi. Đây là phiên bản không rẽ nhánh đơn giản của đoạn mã lúc nãy.
And then now I'm gonna vectorize it using SIMD. Right? And again, this is pseudocode, but whatever, like you load in a vector of tuples.
Và bây giờ tôi sẽ vector hóa nó bằng SIMD. Đúng không? Và một lần nữa, đây là mã giả, nhưng thôi kệ, ví dụ bạn nạp vào một vectơ các tuple.
I load them into my SIMD registers, and then I'm gonna apply my predicate. I mean, I'm not defining how I'm gonna do this in SIMD. I'll do that in a second.
Tôi nạp chúng vào các thanh ghi SIMD, rồi áp dụng vị từ của mình. Tôi chưa định nghĩa cách làm việc này trong SIMD. Lát nữa tôi sẽ nói.
And then I'm gonna take the output of that, those predicates that are sitting in SIMD registers, and I'm gonna convert that back into something I can put in my output buffer.
Và sau đó tôi sẽ lấy đầu ra của nó, những kết quả vị từ đang nằm trong các thanh ghi SIMD đó, và chuyển ngược lại thành thứ có thể đặt vào bộ đệm đầu ra của tôi.
Right? So, give a more specific example here. So say that I wanna run this query, select star from table with keys greater than N and less than U.
Đúng không? Tôi đưa ra một ví dụ cụ thể hơn ở đây. Giả sử tôi muốn chạy truy vấn này, select star from table với các khóa lớn hơn N và nhỏ hơn U.
And then my table looks like this, like a simple vector. So what I'm gonna do is I'm gonna take the keys I wanna evaluate. I'm gonna load them into a SIMD register.
Và bảng của tôi trông thế này, như một vectơ đơn giản. Việc tôi làm là lấy các khóa cần đánh giá. Tôi nạp chúng vào một thanh ghi SIMD.
And there's instructions explicitly to do that. And there's different sizes of SIMD registers. 1024 or, New AVX 10 or whatever from Intel gives a 1024. AVX 512 is probably more common, so 512 bits.
Và có những lệnh dành riêng để làm việc đó. Và có nhiều kích thước thanh ghi SIMD khác nhau. 1024, hay AVX 10 mới của Intel hay gì đó cho 1024. AVX 512 có lẽ phổ biến hơn, tức là 512 bit.
But you can say I'm storing, you know, I can store either four byte values, eight byte values. Sometimes they go down to two byte values. Right?
Nhưng bạn có thể nói là tôi lưu, bạn biết đấy, tôi có thể lưu giá trị 4 byte hoặc 8 byte. Đôi khi xuống tới giá trị 2 byte. Đúng không?
I have different lanes I can store things in. Right? So I'm gonna do my SIMD compare based on the constant that I'm trying to look up here. I'm gonna get a mask.
Tôi có các làn (lane) khác nhau để lưu dữ liệu. Đúng không? Vậy tôi sẽ thực hiện phép so sánh SIMD dựa trên hằng số mà tôi đang cố tra cứu ở đây. Tôi sẽ nhận được một mặt nạ (mask).
It's a big bit vector that says, here's the, you know, for each lane in my SIMD register, whether the predicate evaluated to true or not.
Đó là một vectơ bit lớn cho biết, với mỗi làn trong thanh ghi SIMD của tôi, vị từ có cho kết quả đúng hay không.
So I'll do that for the first part where key is greater than or equal to N. And I'll do that same thing for now the second part, the key less than zero.
Tôi làm vậy cho phần đầu, khi khóa lớn hơn hoặc bằng N. Và tôi làm điều tương tự cho phần thứ hai, khóa nhỏ hơn không.
Now I have two bit vectors that correspond to whether the predicate evaluated true. So both of these are gonna be sitting in SIMD registers.
Bây giờ tôi có hai vectơ bit tương ứng với việc vị từ có đúng hay không. Cả hai đều đang nằm trong các thanh ghi SIMD.
And now I have a SIMD instruction to do an AND, again across the lanes. Right? And then that's gonna determine now which offsets in my input vector satisfied the predicate.
Và giờ tôi có một lệnh SIMD để thực hiện phép AND, cũng trên các làn. Đúng không? Và từ đó sẽ xác định được những offset nào trong vectơ đầu vào của tôi thỏa mãn vị từ.
So then now I need, again, I need to convert this to something I can then use for identifying which tuples in my input vector satisfy the predicate.
Vậy bây giờ, tôi lại cần chuyển cái này thành thứ mà tôi có thể dùng để xác định những tuple nào trong vectơ đầu vào thỏa mãn vị từ.
So I'll just maintain a vector of offsets, like in this case here it's zero to seven, which just corresponds to offsets here in my input data.
Nên tôi sẽ duy trì một vectơ các offset, như trong trường hợp này là từ không đến bảy, tương ứng với các offset trong dữ liệu đầu vào của tôi ở đây.
And then now I use a SIMD compress instruction that converts basically the, for any of the ones, or any one that's set to true in my input vector mask, that corresponds to the offset into my offset array.
Rồi sau đó tôi dùng một lệnh SIMD compress, về cơ bản là chuyển đổi với bất kỳ vị trí nào có giá trị một, hay bất kỳ vị trí nào được đặt là true trong mặt nạ vectơ đầu vào của tôi, thì nó tương ứng với offset trong mảng offset.
And then now I get an aligned vector that tells me here's the offsets that satisfy the predicate. So I can rip through this super fast.
Và bây giờ tôi có được một vectơ được căn chỉnh cho tôi biết đây là những offset thỏa mãn vị từ. Nhờ vậy tôi có thể xử lý cái này cực nhanh.
So now, again, that's now why I want to do the vectorized query processing model. The name is bad, right?
Đó chính là lý do tôi muốn dùng mô hình xử lý truy vấn vectorized. Cái tên này không hay, đúng không?
I'm using vectorized instructions to do this vectorized processing, but I'm gonna also do this in the vector, vectorized query processing model, or the batch model.
Tôi dùng các lệnh vectorized để thực hiện xử lý vectorized này, nhưng tôi cũng sẽ làm điều này trong mô hình xử lý truy vấn vectorized, hay còn gọi là mô hình batch.
So I can take a batch of these tuples, rip through it with SIMD. So my, my predicates can all be SIMDified. And I can do this very, very quickly.
Tôi có thể lấy một batch các tuple này và xử lý nhanh bằng SIMD. Nên các vị từ của tôi đều có thể SIMD hóa. Và tôi làm được việc này rất, rất nhanh.
And this is what, this is what the, the, the co-founder of Snowflake, this is one of the cool, the big things that he helped develop when he built the system called VectorWise that came out of CWI, again, same place where DuckDB is.
Và đây chính là điều mà người đồng sáng lập Snowflake, đây là một trong những điều hay ho, một trong những điều lớn mà ông ấy đã giúp phát triển khi ông xây dựng hệ thống VectorWise xuất phát từ CWI, một lần nữa, cùng nơi với DuckDB.
And then VectorWise got bought by Ingres for like pennies. And then he, so he, he quit that. And then he hooked up with the two dudes from Oracle and they, they found a Snowflake.
Rồi VectorWise bị Ingres mua với giá rẻ mạt. Và rồi ông ấy bỏ đi. Sau đó ông bắt tay với hai anh chàng từ Oracle và họ thành lập Snowflake.
And Snowflake is doing, Snowflake is sort of, was one of the leading systems that did this, but everyone does this now. All right.
Và Snowflake là một trong những hệ thống dẫn đầu làm điều này, nhưng bây giờ ai cũng làm vậy. Được rồi.
So another cool thing you can do with SIMD is all the different operations we talked about throughout this semester. There's SIMD versions of them.
Vậy một điều hay ho khác bạn có thể làm với SIMD là tất cả các phép toán khác nhau mà chúng ta đã nói suốt học kỳ này. Đều có phiên bản SIMD của chúng.
Not all of them are as good at, not all of them can be easily vectorized with SIMD, because oftentimes when you fall out of the CPU cache, things get super slow because you have to go through loads and stores to get memory.
Không phải cái nào cũng dễ vectơ hóa bằng SIMD, vì thường khi bạn rơi ra khỏi bộ nhớ đệm của CPU, mọi thứ trở nên cực chậm vì phải qua các lệnh load và store để lấy bộ nhớ.
But there's, if you can align things nicely, you can, you can do a lot of cool things. All right.
Nhưng nếu bạn căn chỉnh dữ liệu cho tốt, bạn có thể làm được rất nhiều điều hay ho. Được rồi.
So we talked, we talked about how to do probing in a hash table before, right? So the scalar version, the, the scalar version for a single key, hash it, then do a single probe.
Trước đây chúng ta đã nói về cách thực hiện probe trong hash table, đúng không? Phiên bản scalar, với một khóa đơn, ta băm nó, rồi thực hiện một lần probe.
And there's, you can just do a linear scan till we find our match, right? So if you want to SIMD this, SIMD, if I vectorize it, this is using what's called horizontal vectorization.
Và bạn chỉ cần quét tuyến tính cho đến khi tìm thấy kết quả khớp, đúng không? Nếu bạn muốn SIMD hóa cái này, nếu tôi vectơ hóa nó, thì đây là cái gọi là vectơ hóa theo chiều ngang.
There's a vertical one where you sort of look at things top to down, but this one's more common.
Còn có cách theo chiều dọc, nơi bạn nhìn mọi thứ từ trên xuống dưới, nhưng cách này phổ biến hơn.
So now I'm going to have in my hash table, with every single sort of row, I'm going to have four keys that are packed together.
Vậy bây giờ trong bảng băm của tôi, ở mỗi hàng, tôi sẽ có bốn khóa được đóng gói cùng nhau.
And I'm going to have my four values and the keys themselves.
Và tôi sẽ có bốn giá trị cùng với chính các khóa đó.
I can store the, you know, I need to have the original key because I have to do my check to see whether this thing matches when I land in my hash table.
Tôi có thể lưu, bạn biết đấy, tôi cần có khóa gốc vì tôi phải kiểm tra xem nó có khớp hay không khi tôi đến một vị trí trong bảng băm.
But since you have variable length keys, oftentimes what you would do is also store, as another vector in here, actually the fingerprint of the hash. Your hash might be 32 bits or 64 bits.
Nhưng vì các khóa có độ dài thay đổi, nên thường thì người ta còn lưu thêm một vectơ khác ở đây, đó là dấu vân tay của giá trị băm. Giá trị băm của bạn có thể là 32 bit hoặc 64 bit.
Maybe I'll keep it like eight bits around. So I can just do in SIMD very quickly: is my eight-bit prefix of my hash match the eight-bit prefix of this other hash?
Có thể tôi chỉ giữ lại khoảng tám bit. Như vậy tôi có thể làm rất nhanh bằng SIMD: tiền tố tám bit của giá trị băm của tôi có khớp với tiền tố tám bit của giá trị băm kia không?
That's a single, you can do that very quickly. It's just integer comparison. If it doesn't match, then you know the full key is never going to match anyway.
Đó chỉ là một phép so sánh số nguyên, làm rất nhanh. Nếu không khớp thì bạn biết khóa đầy đủ chắc chắn cũng không bao giờ khớp.
So you just ignore it. So now when I want to do a lookup here, I'll take my single key, hash it just like before.
Nên bạn cứ bỏ qua nó. Vậy bây giờ khi tôi muốn tra cứu ở đây, tôi lấy khóa đơn của mình, băm nó giống như trước.
But then now when I land in a slot in my hash table, I'm getting back four keys in my example here.
Nhưng bây giờ khi tôi đến một slot trong bảng băm, tôi nhận về bốn khóa trong ví dụ này.
And now I just use SIMD to do the comparison I did before, get back a bit mask because it tells me which one is matched.
Và bây giờ tôi chỉ dùng SIMD để thực hiện phép so sánh như trước, nhận về một bit mask cho biết khóa nào khớp.
And then based on those, I can then go find the thing that I'm actually looking for. Why is this faster? So the question is, why is this faster?
Và rồi dựa trên đó, tôi có thể đi tìm thứ mà tôi thực sự cần. Tại sao cách này nhanh hơn? Câu hỏi là tại sao nó nhanh hơn?
Because when I go probe in the hash table, You know, that's a cache line lookup. I'm going to go get 64 bytes, right?
Vì khi tôi dò tìm trong bảng băm, đó là một lần tra cứu cache line. Tôi sẽ lấy về 64 byte, đúng không?
And so for that 64 bytes, if I can put more things in there, then do SIMD comparison instead of having to do, you know, a for loop one at a time, this is way faster.
Và với 64 byte đó, nếu tôi nhét được nhiều thứ hơn vào, rồi so sánh bằng SIMD thay vì phải làm, bạn biết đấy, vòng lặp for từng phần tử một, thì nhanh hơn nhiều.
Because otherwise it's like, say if it's a SISD loop, like a for loop, I'm going to go for each element.
Vì nếu không thì, giả sử là vòng lặp SISD, như vòng lặp for, tôi sẽ duyệt qua từng phần tử.
Let's say I need to look at four keys. I got to look at each key separately. That's one instruction. Whereas in SIMD, I can do all four in a single instruction.
Giả sử tôi cần xem bốn khóa. Tôi phải xem từng khóa riêng biệt. Đó là một lệnh. Trong khi với SIMD, tôi làm cả bốn chỉ trong một lệnh.
Yes, you have to load in registers, right?
Đúng, bạn phải nạp vào các thanh ghi.
But like, also too, I'm showing like four, you know, four lanes, but AVX 512, assuming you have like 32 bit integers, you can put a lot more, right?
Nhưng ngoài ra, tôi đang minh họa bốn làn thôi, còn với AVX 512, giả sử là số nguyên 32 bit, bạn có thể nhét nhiều hơn rất nhiều.
This would be like 120 bit registers, which is like Intel had in the 90s.
Cái này sẽ giống như thanh ghi 120 bit, loại mà Intel có từ những năm 90.
The question is, like, you're advertising the cost because all, most of these are fail? Yes.
Câu hỏi là, bạn đang quảng cáo cái chi phí đó vì hầu hết các lần đều thất bại phải không? Đúng.
It's like, it's way faster, way faster to use SIMD versus SISD for this.
Dùng SIMD nhanh hơn, nhanh hơn rất nhiều so với SISD cho việc này.
Again, the trick is instead of trying to, like my example, I was trying to match, going back here, I'm trying to match on the, on single keys at a time, right?
Một lần nữa, mẹo ở đây là thay vì cố gắng, như ví dụ của tôi, tôi đã cố khớp, quay lại chỗ này, tôi đang cố khớp từng khóa đơn một, đúng không?
Or single elements of a key, like a single character. So my keys might be kind of large.
Hoặc từng phần tử đơn của một khóa, như một ký tự. Nên các khóa của tôi có thể khá lớn.
So I, instead of doing the SIMD comparison on the full key, which if they're variable length may not be the same for every, you know, for all the elements in my, I fucking afford it.
Vì vậy, thay vì thực hiện so sánh SIMD trên toàn bộ khóa, mà nếu có độ dài thay đổi thì có thể không giống nhau cho mọi phần tử trong bảng của tôi, tôi không thể chịu nổi cái giá đó.
I'm getting within the slot. I use the hash prefix and that guarantees they're always this fixed length. All right.
Tôi đang xét bên trong slot. Tôi dùng tiền tố băm và điều đó đảm bảo chúng luôn có độ dài cố định như thế này. Được rồi.
So what I've shown so far of how we take the data out from one operator, one sort of step of an operator and pass along to the next one, this is called using what are called selection vectors, Right?
Vậy những gì tôi đã trình bày cho đến giờ về cách lấy dữ liệu ra từ một toán tử, một bước của một toán tử, rồi chuyển sang toán tử tiếp theo, được gọi là dùng selection vector, đúng không?
And the idea here is that when the operator is going to spit out, it would be offsets into my input vectors that correspond to, these are the tuples that I want to pass up to the next operator, right?
Và ý tưởng ở đây là khi toán tử xuất kết quả ra, nó sẽ là các offset trong các vectơ đầu vào của tôi tương ứng với những tuple mà tôi muốn chuyển lên toán tử tiếp theo, đúng không?
So the, like, fixed-length offsets within my input array, right? You can also, some systems will do bitmaps instead.
Tức là các offset có độ dài cố định trong mảng đầu vào của tôi, đúng không? Một số hệ thống sẽ dùng bitmap thay thế.
So think of this as like there's a one or zero corresponding to whether a tuple within a batch that's being passed up, one operator to the next, whether they've satisfied the predicate and they should be continued processing as you go up.
Hãy hình dung là có một bit 1 hoặc 0 tương ứng với việc một tuple trong một batch đang được chuyển từ toán tử này sang toán tử tiếp theo có thỏa mãn vị từ hay không và có nên tiếp tục được xử lý khi đi lên hay không.
So maybe the case, and you saw this in the BusTub projects, maybe the case I pass up a vector and I apply some predicate, but only one of them is going to match.
Có thể có trường hợp, và các bạn đã thấy trong các dự án BusTub, tôi chuyển lên một vectơ và áp dụng một vị từ nào đó, nhưng chỉ có một tuple khớp.
So I need a way to represent how I then pass up that batch and say, ignore all the other ones that don't match because they didn't match down below, only look at this one.
Vậy tôi cần cách biểu diễn việc chuyển batch đó lên và nói rằng: hãy bỏ qua tất cả các tuple còn lại không khớp vì chúng không khớp ở bên dưới, chỉ nhìn vào tuple này thôi.
And then sometimes what you want to do is have a staging buffer to say, I get, you know, I get up 1024 tuples, but only one of them matches.
Và đôi khi bạn muốn có một staging buffer để nói rằng, tôi nhận lên 1024 tuple, nhưng chỉ có một tuple khớp.
So instead of me passing up a 1024 tuple, or 1024 buffer that only has one tuple matching, I'll just wait for more things to come below me, then fill up the buffer and then send up a dense buffer going up.
Thay vì chuyển lên 1024 tuple, hay một buffer 1024 mà chỉ có một tuple khớp, tôi sẽ chờ thêm dữ liệu từ bên dưới đến, rồi lấp đầy buffer và sau đó gửi lên một buffer dày đặc.
And different systems do different things. There's trade-offs for all of these. Yes, question. Are there systems that do this adaptively?
Các hệ thống khác nhau làm khác nhau. Cách nào cũng có đánh đổi. Vâng, mời bạn hỏi. Có hệ thống nào làm việc này một cách thích ứng không?
No, you could, but like you basically have to implement two of them, two implementations. All right.
Không, bạn có thể làm được, nhưng về cơ bản bạn phải cài đặt cả hai, tức là hai bản cài đặt. Được rồi.
So that's using SIMD and, you know, modern hardware to speed things up. We don't talk about GPUs. We, in the previous version, 721, that is actually becoming a hot area.
Vậy đó là việc dùng SIMD và phần cứng hiện đại để tăng tốc. Chúng ta không nói về GPU. Ở phiên bản trước, 721, đó thực sự đang trở thành một lĩnh vực nóng.
Now there was a bunch of GPU databases last decade. They kind of didn't go anywhere because they had to store all of them.
Đã có một loạt cơ sở dữ liệu GPU trong thập kỷ trước. Chúng không đi đến đâu vì phải lưu toàn bộ dữ liệu.
You had to store the entire database down in the GPU card, right? With NVLink, as some of the newer stuff NVIDIA is doing in newer versions of PCIe, this is changing.
Bạn phải lưu toàn bộ cơ sở dữ liệu trên card GPU, đúng không? Với NVLink, cùng một số thứ mới NVIDIA đang làm trong các phiên bản PCIe mới hơn, điều này đang thay đổi.
And I can't say too much, but there's some major things happening within the next year. You'll see a bunch of GPU, more GPU databases coming out.
Tôi không thể nói nhiều, nhưng sẽ có những chuyện lớn xảy ra trong năm tới. Các bạn sẽ thấy nhiều cơ sở dữ liệu GPU hơn ra mắt.
So, but, well, basically it's the same principles we talked about; SIMD will apply in the GPU world as well. That's what I mentioned. All right.
Nên, nhưng mà, về cơ bản vẫn là những nguyên lý chúng ta đã nói; SIMD cũng sẽ áp dụng trong thế giới GPU. Đó là điều tôi đã đề cập. Được rồi.
So I'll talk about how we do code specialization now through code generation. So the, you know, in BusTub, the way it works is like, you're given a query plan.
Bây giờ tôi sẽ nói về cách chúng ta thực hiện chuyên biệt hóa mã thông qua sinh mã. Vậy, bạn biết đấy, trong BusTub, cách nó hoạt động là: bạn được cho một kế hoạch truy vấn.
You basically walk the tree. And then within that, you get an expression tree. And you have to walk that to produce, you know, evaluate predicates and so forth.
Về cơ bản bạn duyệt cây đó. Và bên trong đó, bạn có một cây biểu thức. Và bạn phải duyệt cây này để, bạn biết đấy, đánh giá các vị từ và những thứ tương tự.
Right?
Đúng không?
So there was a very famous project called HIQUE out of the University of Edinburgh in the early 2010s, where for a given SQL query, they would generate the plan and then they would convert that plan tree into actual machine code, so C code.
Có một dự án rất nổi tiếng tên là HIQUE của Đại học Edinburgh vào đầu những năm 2010, trong đó với một truy vấn SQL cho trước, họ sẽ tạo ra kế hoạch và sau đó chuyển cây kế hoạch đó thành mã máy thực sự, tức là mã C.
They would then invoke GCC to then compile that function for the query into a shared object, link it in, and then invoke that.
Sau đó họ gọi GCC để biên dịch hàm cho truy vấn đó thành một shared object, liên kết nó vào, rồi gọi thực thi.
So you don't do that in the interpretation you would do in BusTub, however, like focus on other systems.
Vậy là bạn không làm kiểu thông dịch như trong BusTub, tuy nhiên, hãy tập trung vào các hệ thống khác.
Now I basically have a hard coded program that executes exactly what my query wants to do. And that's going to be way faster because I don't have to do jumping.
Giờ về cơ bản tôi có một chương trình được mã hóa cứng thực thi chính xác những gì truy vấn của tôi muốn làm. Và điều đó sẽ nhanh hơn nhiều vì tôi không phải nhảy qua nhảy lại.
I don't have to do traversals or follow pointers in a query plan tree. It's hard coded, built for doing exactly what the query wants.
Tôi không phải duyệt cây hay lần theo con trỏ trong cây kế hoạch truy vấn. Nó được mã hóa cứng, xây dựng để làm đúng những gì truy vấn cần.
So here's what, again, this is what BusTub would normally look like. If I scan through my table, I gotta go get a tuple. I don't know what the tuple looks like.
Đây, một lần nữa, là dáng vẻ thông thường của BusTub. Nếu tôi quét qua bảng, tôi phải đi lấy một tuple. Tôi không biết tuple trông như thế nào.
I go to the catalog, get some stuff, and then I apply my predicate by running all these steps.
Tôi đến catalog, lấy một vài thông tin, rồi áp dụng vị từ bằng cách chạy tất cả các bước này.
So instead, what I want to do is I want to have a program that basically hard codes in: here's the tuples I'm looking at, here's the predicates I want to consider, here's the offsets to go find the attributes that I want.
Thay vào đó, điều tôi muốn là có một chương trình mã hóa cứng sẵn: đây là các tuple tôi đang xét, đây là các vị từ tôi muốn xem xét, đây là các offset để tìm các thuộc tính tôi muốn.
And then now I'm just running CPU instructions to do these computations and not worry about, like, you know, trying to interpret what's the size of the table or what size of a tuple.
Và khi đó tôi chỉ chạy các lệnh CPU để thực hiện các phép tính này và không phải bận tâm về việc, bạn biết đấy, cố diễn giải kích thước của bảng là bao nhiêu hay kích thước của một tuple.
And I jump to my slotted page arrays to find things that I want. I can rip through things way more efficiently this way. What's that?
Và tôi nhảy qua các mảng slotted page để tìm thứ tôi muốn. Làm theo cách này tôi có thể xử lý nhanh hiệu quả hơn nhiều. Gì vậy?
The question is, can we just use an off the shelf compiler, GCC? The example, yes. In most database systems, for the Germans, they're going to use an off the shelf compiler.
Câu hỏi là liệu ta có thể dùng một trình biên dịch có sẵn như GCC không? Ví dụ này thì có. Trong hầu hết các hệ cơ sở dữ liệu, với nhóm người Đức, họ sẽ dùng một trình biên dịch có sẵn.
The question is, is this fast enough? No. So we'll fix that in a second. So maybe we can jump to that now. Yes. Question.
Câu hỏi là, thế có đủ nhanh không? Không. Nên ta sẽ khắc phục điều đó ngay sau đây. Vậy có lẽ ta có thể chuyển sang phần đó luôn. Vâng. Câu hỏi.
Is any system trying to use a JIT system? The Germans, yes. And what they do, I know it's like, I should have told you this.
Có hệ thống nào thử dùng JIT không? Nhóm người Đức thì có. Và những gì họ làm, tôi biết, lẽ ra tôi nên nói với các bạn điều này.
What they do is, the first version, when HyPer, they would, create shows up, instead of emitting C++ code or C code, they would emit LLVM IR.
Những gì họ làm là, ở phiên bản đầu tiên, khi HyPer, xuất hiện, thay vì sinh mã C++ hay mã C, họ sinh LLVM IR.
And then they would let the LLVM compile that into machine code and run that.
Rồi họ để LLVM biên dịch nó thành mã máy và chạy.
Cause it was, you know, it was faster to run the degenerate IR rather than C, cause then you're getting above GCC. And that's slow, right?
Vì, bạn biết đấy, chạy IR được sinh ra nhanh hơn là chạy C, vì như vậy bạn vượt lên trên GCC. Và GCC thì chậm, đúng không?
And the newer version in Umbra, which now also is commercialized as CedarDB, and I'll have slides for this, what they do is they emit their own IR.
Còn phiên bản mới hơn là Umbra, hiện cũng được thương mại hóa thành CedarDB, và tôi sẽ có slide cho phần này, cái họ làm là tự phát ra IR của riêng họ.
And then they have another pass that can convert that IR into assembly. That they roll by hand. Then they run the assembler, which is fast and cheap to do.
Rồi họ có thêm một lượt xử lý khác có thể chuyển IR đó thành hợp ngữ. Phần đó họ tự viết bằng tay. Sau đó họ chạy trình hợp dịch, việc này nhanh và rẻ.
And then they start running the query based on the assembled version. Then in the background, they run LLVM to compile their IR into, like, machine code with, like, O3 turned on.
Và rồi họ bắt đầu chạy truy vấn dựa trên phiên bản đã được hợp dịch. Sau đó ở chế độ nền, họ chạy LLVM để biên dịch IR của mình thành kiểu như mã máy, với tùy chọn O3 được bật.
But that can take, you know, seconds or milliseconds. And the idea is that if the query finishes with the assembled version, then you're done, right?
Nhưng việc đó có thể mất vài giây hoặc vài mili giây. Và ý tưởng là nếu truy vấn chạy xong bằng phiên bản hợp dịch, thì xong rồi, đúng không?
But if it's still running by the time LLVM finishes, then they slide out the assembled version and plop in their compiled shared object.
Nhưng nếu đến lúc LLVM biên dịch xong mà truy vấn vẫn đang chạy, thì họ rút phiên bản hợp dịch ra và thay vào đó đối tượng chia sẻ đã biên dịch của họ.
Like, how does it, like, the way they orchestrate the system to get worked on, like, the schedule tasks. Like, when it goes, it says, all right, I want to run this task.
Cách họ điều phối hệ thống để thực hiện công việc, tức là lập lịch các tác vụ. Khi chạy, nó nói: được rồi, tôi muốn chạy tác vụ này.
It would say, all right, I need to do this operation on this piece of data. Is my compiled version ready? If yes, invoke that. If not, invoke the assembler.
Nó sẽ nói: được rồi, tôi cần thực hiện thao tác này trên phần dữ liệu này. Phiên bản đã biên dịch của tôi sẵn sàng chưa? Nếu rồi, gọi nó. Nếu chưa, gọi trình hợp dịch.
Insane, right? So this sounds amazing. I would say though, we built an LLVM-based query engine that did this just-in-time compilation stuff. It's a nightmare to debug.
Điên rồ, đúng không? Nghe thì tuyệt vời. Nhưng tôi phải nói là, chúng tôi từng xây dựng một engine truy vấn dựa trên LLVM làm kiểu biên dịch just-in-time này. Gỡ lỗi nó là một cơn ác mộng.
And we'll see this when we talk about Databricks in a second. Like, you got to have people that know about compilers. And they got to know about the databases.
Và chúng ta sẽ thấy điều này khi nói về Databricks ngay sau đây. Bạn phải có những người am hiểu về trình biên dịch. Và họ cũng phải hiểu về cơ sở dữ liệu.
And then now when you crash in these systems, because it's, it's, like, dynamic code being generated for a query, you're not landing in, like, well, if you generate C, you can do this.
Và rồi khi hệ thống bị crash, vì đó là mã động được sinh ra cho một truy vấn, bạn không dừng ở, ừm, nếu sinh ra C thì bạn có thể làm điều này.
But, like, if you're doing the JIT compilation, going directly for LLVM IR, then compiling that, when you crash, you land there with, with symbols.
Nhưng nếu bạn làm biên dịch JIT, đi thẳng sang LLVM IR, rồi biên dịch cái đó, thì khi crash, bạn rơi vào đó với, với các ký hiệu.
Sorry, without symbols to know exactly, here's the line of code in your C++ application that generated this IR that causes this crash. It's a nightmare to debug. So the... Huh? What generated the IR?
Xin lỗi, không có ký hiệu để biết chính xác dòng mã nào trong ứng dụng C++ của bạn đã sinh ra IR gây ra vụ crash này. Gỡ lỗi là một cơn ác mộng. Vậy nên... Hả? Cái gì sinh ra IR ư?
That's the part you got to fix. From the dataset, right?
Đó là phần bạn phải sửa. Từ tập dữ liệu, đúng không?
And so the Germans, they wrote their own debugger, so that they can reverse back, based on Mozilla RR, to reverse back, like, here's the line of code that generated this IR for me.
Và người Đức, họ đã tự viết trình gỡ lỗi riêng, dựa trên Mozilla RR, để có thể lần ngược lại, lần ngược xem dòng mã nào đã sinh ra IR này cho tôi.
Like, you would think the guy's on cocaine, but he's not. It's insane, right? Like his vice is apple juice. Right? And it's one guy. It's, I mean, sorry.
Bạn sẽ nghĩ anh chàng này dùng cocaine, nhưng không. Điên rồ, đúng không? Thói xấu của anh ấy là nước ép táo. Đúng không? Và đó chỉ là một người. Ý tôi là, xin lỗi.
Right. So, to the point, like, is this compilation thing expensive? Yes. This is actually not a new idea. IBM did this back in the 1970s with System R.
Đúng. Vậy quay lại vấn đề, việc biên dịch này có tốn kém không? Có. Thực ra đây không phải ý tưởng mới. IBM đã làm vậy từ những năm 1970 với System R.
They would generate the assembly for a query plan, and they would run that. But again, they had the same problem.
Họ sinh ra hợp ngữ cho một kế hoạch truy vấn rồi chạy nó. Nhưng một lần nữa, họ gặp cùng một vấn đề.
Anytime that the system crashed, you had to go figure out what assembly created this assembly, to figure out what was the mistake.
Bất cứ khi nào hệ thống bị crash, bạn phải đi tìm xem hợp ngữ nào đã tạo ra hợp ngữ này, để xác định lỗi sai nằm ở đâu.
Actually, I think System R was written in C. So, yeah, the same idea.
Thực ra tôi nghĩ System R được viết bằng C. Vậy nên, đúng, cùng một ý tưởng.
Or the other problem is, every single time you change the API, the storage system, then you got to go change all the compiler code, right?
Hoặc một vấn đề khác là, mỗi lần bạn thay đổi API, hệ thống lưu trữ, thì bạn lại phải sửa toàn bộ mã của trình biên dịch, đúng không?
Because again, it was early days. They didn't have good abstractions. So, an alternative is what Vectorwise came up with.
Vì như tôi nói, đó là thời kỳ đầu. Họ chưa có các lớp trừu tượng tốt. Vậy một giải pháp thay thế là cái mà Vectorwise đã nghĩ ra.
And again, what Snowflake does, and what a lot of systems follow along, is do what are called pre-compiled primitives.
Và một lần nữa, điều mà Snowflake làm, và cũng là điều mà rất nhiều hệ thống khác làm theo, là dùng cái gọi là các primitive biên dịch trước (pre-compiled primitives).
And the idea is that, in your data system source code, in your repository, you pre-bake and automatically generate all these primitives for different predicates you may evaluate, and for any particular query.
Ý tưởng là, trong mã nguồn hệ thống dữ liệu của bạn, trong kho mã của bạn, bạn dựng sẵn và tự động sinh ra tất cả các primitive này cho những vị từ khác nhau mà bạn có thể phải đánh giá, và cho bất kỳ truy vấn cụ thể nào.
Like, integer column equals integer. Integer column less than integer. Right?
Ví dụ: cột số nguyên bằng một số nguyên. Cột số nguyên nhỏ hơn một số nguyên. Đúng không?
Think of all those separate operations, a separate function, that you then have, you can automate, generate all these through templates, in your code base.
Hãy nghĩ đến tất cả những phép toán riêng biệt đó, mỗi phép là một hàm riêng, mà bạn có thể tự động hóa, sinh ra tất cả chúng bằng template trong cơ sở mã của bạn.
And then when you compile the binary, then that binary itself is now all these different primitives that you then stitch together at runtime, Based on what the, the query wants to do.
Và khi bạn biên dịch ra tệp nhị phân, thì chính tệp nhị phân đó giờ chứa tất cả các primitive khác nhau này, mà bạn sẽ ghép lại với nhau lúc chạy, dựa trên việc truy vấn muốn làm gì.
And then now you don't worry about jitting things, because you have basically things all together, and you're kind of assembling the, the building blocks for a query plan just through pointers.
Và như vậy bạn không còn phải lo về việc JIT nữa, vì về cơ bản mọi thứ đã có sẵn cùng nhau, và bạn chỉ đang lắp ráp các khối xây dựng cho một kế hoạch truy vấn thông qua các con trỏ.
The statement is, the orchestration cost can be high. Yeah, so the jump call is expensive. Aha. But if you do batches of tuples, then that amortizes the jump call.
Nhận định là chi phí điều phối có thể cao. Đúng, lệnh nhảy (jump call) tốn kém. À há. Nhưng nếu bạn xử lý theo lô tuple thì chi phí của lệnh nhảy được chia đều ra.
That's how you get, if it's doing a tuple at a time, no.
Còn nếu xử lý từng tuple một thì không được.
If it's, if it's a batch of tuples, again, what the, what the Snowflake guy would, he, he figured out, like this, this is how you can do this.
Còn nếu là một lô tuple, thì như người của Snowflake đã, anh ấy đã tìm ra, đây là cách bạn có thể làm điều này.
All right, so say my query is like this. Again, I'm doing a string column lookup on ABC, an integer column lookup on four, right?
Được rồi, giả sử truy vấn của tôi như thế này. Một lần nữa, tôi tra cứu cột chuỗi với giá trị ABC, và cột số nguyên với giá trị 4, đúng không?
So I would have a separate primitive to do a, take a vector of tuples in, to do string column equals something, you know, constant.
Vậy tôi sẽ có một primitive riêng nhận vào một vectơ các tuple, để xét cột chuỗi bằng một thứ gì đó, một hằng số.
And in this case here, I would have another one for the integer column.
Và ở đây, tôi sẽ có một primitive khác cho cột số nguyên.
But now you see it, now I'm passing along the positions offset, so I can, I can chain these things together, take the output of one, then feed it into another one.
Nhưng giờ bạn thấy đấy, tôi đang truyền theo các vị trí (offset), nên tôi có thể xâu chuỗi chúng lại, lấy đầu ra của cái này, rồi đưa vào cái tiếp theo.
And then they would know that, you know, should I, should I, if this position thing is, is, if it's not in my position vector, then I know I should ignore it in my input column.
Và khi đó chúng sẽ biết là, tôi có nên tôi có nên, nếu vị trí này mà không nằm trong vectơ vị trí của tôi, thì tôi biết là nên bỏ qua nó trong cột đầu vào.
So even though the number of, a couple, the number of possible permutations you can have in a query plan for these predicates is infinite, in actuality it's actually a finite number, right?
Vì vậy, dù số lượng, một vài, số hoán vị có thể có trong một kế hoạch truy vấn cho các vị từ này là vô hạn, thì trên thực tế nó là một con số hữu hạn, đúng không?
There's only like so many different data types, so many different things you can do with them, right? Something equals something, something less than something, and so forth, right?
Chỉ có chừng ấy kiểu dữ liệu khác nhau, và chừng ấy việc bạn có thể làm với chúng, đúng không? Cái này bằng cái kia, cái này nhỏ hơn cái kia, và cứ thế, đúng không?
Something equals a column, two columns are the same, right? So this is what, this is what Snowflake does. This is what, This is what Photon does in Databricks, right?
Cái này bằng một cột, hai cột giống nhau, đúng không? Đây chính là điều Snowflake làm. Đây cũng là điều Photon làm trong Databricks.
The current research says this is the right way to build your systems, not do the JIT, JIT compilation stuff. Yes. Question, do you have a CodeGen framework? Yeah, but it's not hard.
Nghiên cứu hiện nay cho rằng đây là cách đúng để xây dựng hệ thống của bạn, chứ không phải làm kiểu biên dịch JIT. Vâng. Câu hỏi là bạn có một framework CodeGen không? Có, nhưng nó không khó.
No, it's not like, like here's two right here, right? Like something equals something, something less than something.
Không, nó không phải kiểu, như ở đây có hai cái này, đúng không? Kiểu như cái này bằng cái kia, cái này nhỏ hơn cái kia.
It's not, you, again, you only have a certain number of data types, and the reason why this is better than JIT compilation, because now if there's a bug in this primitive, if it crashes, then I'm, I'm in, you know, I can go to the GDB or whatever, you know, walk through and figure out how to reproduce the crash.
Nó không phải, bạn thấy đấy, bạn chỉ có một số lượng kiểu dữ liệu nhất định, và lý do cách này tốt hơn biên dịch JIT, là vì giờ nếu có lỗi trong primitive này, nếu nó bị crash, thì tôi có thể dùng GDB hay công cụ nào đó, đi từng bước và tìm cách tái hiện lỗi crash đó.
All right, we got 10 minutes. I can't cover all of these. Let's do a vote. We'll pick two. Okay, I'm going to keep count.
Được rồi, còn 10 phút. Tôi không thể trình bày hết chúng. Hãy bỏ phiếu. Ta sẽ chọn hai cái. Được, tôi sẽ đếm.
Raise your hand if you want BigQuery. Raise your hand if you want Snowflake. A little more. Raise your hand if you want Redshift. Very few, okay. Raise your hand if you want Yellowbrick.
Giơ tay nếu bạn muốn BigQuery. Giơ tay nếu bạn muốn Snowflake. Nhiều hơn chút. Giơ tay nếu bạn muốn Redshift. Rất ít, được rồi. Giơ tay nếu bạn muốn Yellowbrick.
I might override you because Yellowbrick is insane. Raise your hand if you want Databricks Photon. All right, that's a clear winner. And raise your hand if you want ClickHouse.
Tôi có thể bỏ qua phiếu của các bạn vì Yellowbrick quá điên rồ. Giơ tay nếu bạn muốn Databricks Photon. Được rồi, đó là người thắng rõ ràng. Và giơ tay nếu bạn muốn ClickHouse.
All right, we'll do, we'll do Databricks. Oh, shit.
Được rồi, ta sẽ học Databricks. Ôi, trời.
All right, we'll do Databricks, Yellowbrick, and I'll try to get ClickHouse quickly. ClickHouse is a quick thing to mention. ClickHouse people already gave a talk.
Được rồi, ta sẽ học Databricks, Yellowbrick, và tôi sẽ cố nói nhanh về ClickHouse. ClickHouse chỉ cần nhắc qua. Những người ở ClickHouse đã có buổi nói chuyện rồi.
All right, let me show you one thing about Snowflake. The dude that wrote, I keep mentioning this guy, Marcin, who like invented all this stuff, invented like the vector stuff, that SIMD stuff.
Được rồi, để tôi cho các bạn xem một điều về Snowflake. Anh chàng đã viết, tôi cứ nhắc đến người này, Marcin, người đã phát minh ra tất cả những thứ này, như phần vectơ, phần SIMD đó.
This is how hardcore he is about databases. This is a photo I took, and this is his leg. He got the Snowflake tattoo because he loves his database so much.
Đây là mức độ cuồng cơ sở dữ liệu của anh ấy. Đây là bức ảnh tôi chụp, và đây là chân anh ấy. Anh ấy xăm hình Snowflake vì yêu cơ sở dữ liệu của mình đến thế.
That's how serious people are about these things. And you think I'm crazy about databases. Like, he's in there with me. Okay, Databricks. So, Databricks is based on Spark. What was Spark written in?
Người ta nghiêm túc với những thứ này đến vậy đấy. Và các bạn nghĩ tôi điên vì cơ sở dữ liệu. Anh ấy cũng cùng hội với tôi. Được rồi, Databricks. Databricks dựa trên Spark. Spark được viết bằng gì?
Anybody know? What query language, or sorry, what programming language? Scala. What does Scala run in? JVM. JVM is terrible. Don't use it. Right?
Có ai biết không? Ngôn ngữ truy vấn, à xin lỗi, ngôn ngữ lập trình nào? Scala. Scala chạy trên cái gì? JVM. JVM thì tệ lắm. Đừng dùng nó. Đúng không?
So, they had this problem where they had this original version of this thing, Spark SQL, that was doing the JIT compilation stuff.
Vậy nên họ gặp vấn đề với phiên bản ban đầu của Spark SQL, vốn làm việc biên dịch JIT.
They would emit Scala bytecode that would then compile to the JVM, but then they found themselves struggling with getting good performance because you gotta get people that can, who know compilers and know databases, and also know how to deal with the JVM.
Họ sinh ra Scala bytecode rồi biên dịch trên JVM, nhưng sau đó họ thấy khó đạt hiệu năng tốt vì bạn phải tìm người vừa biết trình biên dịch, vừa biết cơ sở dữ liệu, lại còn biết xử lý JVM.
So, they spent more time trying to modify the code to generate the, you know, do instrumentation in the JVM rather than making the query engine go faster. Right?
Vì thế họ tốn nhiều thời gian hơn để sửa mã nhằm sinh ra, bạn biết đấy, làm instrumentation trong JVM thay vì làm cho query engine chạy nhanh hơn. Đúng không?
Because again, Spark was originally written as a tuple-at-a-time, row-based system. And obviously, again, with Snowflake and all the other stuff we talked about this past semester, we know we don't want to do this.
Bởi vì, Spark ban đầu được viết là một hệ thống theo hàng, xử lý từng tuple một. Và rõ ràng, với Snowflake và mọi thứ khác ta đã nói trong học kỳ này, ta biết là không nên làm như vậy.
So, what Photon is, is a runtime written in C++ that integrates, connects into the JVM through JNI, the Java Native Interface, and then at certain points when they execute a query, they recognize, I have a C++ version of the thing you want to do.
Vậy Photon là một runtime viết bằng C++, tích hợp, kết nối vào JVM qua JNI, Java Native Interface, và rồi ở một số thời điểm khi thực thi truy vấn, họ nhận ra rằng: tôi có một phiên bản C++ cho việc bạn muốn làm.
Like, something equals something. They can then hand it off to the C++ code, who then could do the, run that more efficiently, and then send the data back into the JVM.
Ví dụ như, cái này bằng cái kia. Khi đó họ có thể chuyển nó sang mã C++, và mã C++ sẽ chạy việc đó hiệu quả hơn, rồi gửi dữ liệu trở lại JVM.
Right? So, there's a paper called Photon. I'm just pointing out here, there's a bunch of my former students, and students who have taken 721, or sorry, 445, like you guys.
Đúng không? Có một bài báo tên là Photon. Tôi chỉ muốn chỉ ra ở đây là có khá nhiều sinh viên cũ của tôi, và những sinh viên đã học 721, à xin lỗi, 445, như các bạn.
They're all, a lot of students at Snowflake, a lot of people work on this project. All right, so, what is Photon?
Họ đều, có rất nhiều sinh viên đang ở Snowflake, nhiều người làm việc trong dự án này. Được rồi, vậy Photon là gì?
It's shared-disk, reactive storage, it's doing pull-based vectorized processing, pre-compiled primitives, expression functions we talked about before, We won't talk about the query about it too much.
Nó dùng shared-disk, lưu trữ reactive, nó xử lý vectorized theo kiểu pull-based, các primitive biên dịch trước, các hàm biểu thức mà chúng ta đã nói trước đó. Chúng ta sẽ không nói quá nhiều về truy vấn của nó.
But again, the core idea that Photon is doing is this, these pre-compiled operator primitives, or kernels, the same thing I just talked about with Vectorwise and Snowflake, right?
Nhưng một lần nữa, ý tưởng cốt lõi của Photon là thế này, các primitive toán tử được biên dịch trước này, hay kernel, giống hệt những gì tôi vừa nói về Vectorwise và Snowflake, đúng không?
They generate all the possible things you would want to do on data, they pre-compile them, and then at runtime they're stitching them together and recognize, these are the things I can, and fall out into the C++.
Họ sinh ra tất cả những thao tác có thể muốn làm trên dữ liệu, biên dịch trước chúng, rồi lúc chạy họ ghép chúng lại với nhau và nhận ra: đây là những thứ tôi làm được, và chuyển sang mã C++.
And if they don't have a C++ version of it, then it just falls back and runs the regular, the JVM version as they normally would.
Còn nếu họ không có phiên bản C++ của nó, thì nó chỉ quay lại và chạy phiên bản thông thường, phiên bản JVM như bình thường.
And they comment how, again, in their experience it was much, much easier to build a, this C++ based engine, that these pre-compiled primitives, than it was to instrument the JVM and do just-in-time compilation.
Và họ nhận xét rằng, theo kinh nghiệm của họ thì xây dựng một engine dựa trên C++ này dễ hơn nhiều, với các primitive biên dịch trước này, so với việc can thiệp vào JVM và làm biên dịch just-in-time.
So even though the first version of this, of their implementation, wasn't as fast as the JIT version was, but they spent all that time, you know, actually making the, the pre-compiled stuff, actually faster, and they can get, they would get, they'd get bigger improvements and got faster than, than they would have if they were still mucking around the JVM.
Vì vậy dù phiên bản đầu tiên trong triển khai của họ không nhanh bằng phiên bản JIT, nhưng họ đã dành toàn bộ thời gian, bạn biết đấy, để làm cho phần biên dịch trước đó thực sự nhanh hơn, và họ có thể đạt được, họ đạt được cải thiện lớn hơn và nhanh hơn so với nếu họ vẫn loay hoay với JVM.
I don't know for the numbers here, I mean, it's quite significant.
Tôi không nhớ các con số ở đây, nhưng nó khá đáng kể.
There's other tricks they do, like, if you, they assume that, you know, even though column may not be declared as not null, sorry, column might be declared as supporting nulls, they assume maybe it doesn't, it's not null, so there's a bunch of checks they avoid, and then if they get it wrong, they roll back.
Họ còn dùng những mẹo khác, chẳng hạn họ giả định rằng, dù cột có thể không được khai báo là not null, xin lỗi, cột có thể được khai báo là cho phép null, họ giả định có lẽ nó không có null, nên họ bỏ qua được nhiều lần kiểm tra, và nếu đoán sai thì họ rollback.
There's some things like that they do as well.
Họ cũng làm một số việc tương tự như vậy.
The question is, can I just keep it in the summary table that I don't see any nulls?
Câu hỏi là: tôi có thể lưu trong bảng tóm tắt rằng tôi không thấy null nào không?
If I'm reading much Parquet files or CSV files that I've never seen before, I don't have that. So I, I gotta guess. There's other tricks you can do with, like, JSON.
Nếu tôi đọc nhiều tệp Parquet hay CSV mà tôi chưa từng thấy, thì tôi không có thông tin đó. Nên tôi phải đoán. Còn có những mẹo khác với, ví dụ, JSON.
Like, JSON's untyped or barely typed.
Kiểu như JSON không có kiểu, hoặc gần như không có kiểu.
You can say, oh, I know that, like, most of these times in this field, it's gonna be an integer, and then only if you see a string, then you fall back and do something else.
Bạn có thể nói: ồ, tôi biết là phần lớn các lần trong trường này, giá trị sẽ là số nguyên, và chỉ khi thấy một chuỗi thì mới quay lại xử lý theo cách khác.
All right, so they're gonna do a technique called also expression fusion. So this is, we talked about operator fusion before.
Được rồi, họ còn dùng một kỹ thuật gọi là expression fusion. Trước đây chúng ta đã nói về operator fusion.
We can kind of take the, you know, if I have like a scan with a predicate, instead of having them be two separate operators, I can put the predicate inside the scan operator, right?
Chúng ta có thể lấy, bạn biết đấy, nếu tôi có một phép scan kèm một predicate, thay vì để chúng là hai toán tử riêng biệt, tôi có thể đặt predicate vào bên trong toán tử scan, đúng không?
So that's operator fusion. They're doing expression fusion because they're doing these predefined, these precompiled primitives.
Đó là operator fusion. Họ làm expression fusion vì họ dùng các primitive được định nghĩa và biên dịch sẵn này.
So instead of having the two functions I showed before, where one predicate is doing the check on the, you know, on the first part of the conjunct and the second one's in the second part, they can just pregenerate a bunch of these ones that can do both together.
Vì vậy, thay vì có hai hàm như tôi đã cho xem trước đó, trong đó một predicate kiểm tra vế đầu của phép hội còn predicate kia kiểm tra vế thứ hai, họ có thể sinh sẵn nhiều hàm có thể làm cả hai việc cùng lúc.
They could rewrite this query into being a between clause, and then now it's one less function call to go process all the data, right?
Họ có thể viết lại truy vấn này thành mệnh đề between, và như vậy ít hơn một lần gọi hàm để xử lý toàn bộ dữ liệu, đúng không?
Another cool thing they do with the shovel phase that we talked about before is that they can determine whether one partition gets too full because the data is skewed, then they can, after the shovel completes, they can go back and repartition it again.
Một điều hay khác họ làm với pha shovel mà chúng ta đã nói trước đó là họ có thể xác định xem một partition có bị đầy quá do dữ liệu bị lệch hay không, và sau khi shovel hoàn tất, họ có thể quay lại và phân vùng lại lần nữa.
Kind of like the recursive partition we talked about with hash joins. So say that I have my worker filling up all these partitions, right?
Giống như phân vùng đệ quy mà chúng ta đã nói với hash join. Giả sử worker của tôi đang lấp đầy tất cả các partition này, đúng không?
And then I recognize that these two guys, these three partitions are underutilized and the one in the middle over there and the one in the end are kind of getting too full.
Rồi tôi nhận ra hai partition này, ba partition này đang dùng chưa hết, còn partition ở giữa đằng kia và partition ở cuối thì đang gần đầy quá.
So what I can do is I can dynamically say, all right, I'm going to start rewriting The data that I have in these guys into this other one to fill that up, and then just pass it along the, the next, the next three.
Vậy tôi có thể linh hoạt nói rằng: được rồi, tôi sẽ bắt đầu ghi lại dữ liệu đang có ở các partition này sang partition kia để lấp đầy nó, rồi chuyển tiếp sang ba partition kế tiếp.
So then I can down, I can sort of automatically downsize or upsize the number of workers I have after each shovel phase based on the data I see going in.
Như vậy tôi có thể tự động giảm bớt hoặc tăng số lượng worker sau mỗi pha shovel, dựa trên dữ liệu tôi thấy đi vào.
All right, let me talk about Yellowbrick just because I find it super, again, this is super fascinating. So it's a new engine written in C++.
Được rồi, để tôi nói về Yellowbrick, chỉ vì tôi thấy nó cực kỳ, một lần nữa, cực kỳ hấp dẫn. Đây là một engine mới viết bằng C++.
They forked it about 10 years ago, and I said this in a class, I, I said this about them in one of these lectures at some point and I forgot I said it, and then when I went to go visit them in London a few months ago, they told me what I said, and then their marketing people love it because they, they actually sell it to customers based on what I said.
Họ đã fork nó khoảng 10 năm trước, và tôi đã nói điều này trong một lớp, tôi đã nói về họ trong một bài giảng nào đó và tôi quên mất là mình đã nói, rồi khi tôi đến thăm họ ở London vài tháng trước, họ kể lại cho tôi điều tôi đã nói, và bên marketing của họ rất thích vì họ thực sự bán sản phẩm cho khách hàng dựa trên điều tôi nói.
So, Yellowbrick does things like the Germans, you would only do if you were on cocaine.
Yellowbrick làm những việc mà người Đức chỉ làm khi đang phê cocaine.
The amount of system optimization they're doing, you would not want to do if you're a brand new startup, but this is what they did. So, what is it?
Lượng tối ưu hóa hệ thống mà họ làm là thứ bạn sẽ không muốn làm nếu là một startup mới toanh, nhưng họ đã làm vậy. Vậy nó là gì?
It's a shared-disk, shared-storage system doing push-based vectorization.
Đó là một hệ thống shared-disk, shared-storage, thực hiện vectorization theo kiểu push-based.
They're doing translation, the, the code gen stuff we talked about, but instead of generating LLVM IR, they're generating C++ and then GCC compiling that, but they can, they can hash that.
Họ làm phần dịch mã, tức là phần sinh mã mà chúng ta đã nói, nhưng thay vì sinh ra LLVM IR, họ sinh ra C++ rồi dùng GCC để biên dịch, và họ có thể băm (hash) đoạn mã đó.
But then the engineering stuff they do is insane.
Nhưng phần kỹ thuật họ làm thì thật điên rồ.
So, it's, so they have a row store that's based on Postgres at the front end, query shows up, they have the cached query plan, they reuse it, otherwise they'll, they'll compile in the background and then run it when it's available.
Họ có một row store dựa trên Postgres ở phía front end, khi một truy vấn đến, nếu đã có kế hoạch truy vấn được lưu đệm, họ sẽ tái sử dụng nó, nếu không thì họ sẽ biên dịch ở chế độ nền rồi chạy khi nó sẵn sàng.
What's insane though is the, the communication channels that they have in between the, the object store, which is like S3, and the different workers themselves.
Nhưng điều điên rồ là các kênh giao tiếp mà họ xây dựng giữa object store, giống như S3, và chính các worker khác nhau.
So, these guys said that the, like, The NVMe drivers and the, the hardware drivers that Linux gives you or the hardware vendors give you were way too slow.
Những người này nói rằng các driver NVMe và các driver phần cứng mà Linux hay nhà sản xuất phần cứng cung cấp đều quá chậm.
So not only did they have to build the runtime engine for the database system, they wrote their own kernel drivers for the NVMe drives they were running on and for the NICs.
Vì vậy họ không chỉ phải xây dựng công cụ thực thi cho hệ quản trị cơ sở dữ liệu, mà còn tự viết driver kernel cho các ổ NVMe mà họ chạy trên đó và cho cả các card mạng (NIC).
And then TCP was too slow, so they rewrote, they wrote their own network protocol based on UDP to make that go fast.
Rồi TCP cũng quá chậm, nên họ tự viết giao thức mạng riêng dựa trên UDP để chạy nhanh hơn.
But then copying data from the NIC down, you know, down the hardware through the kernel up into user space, that's too slow too, because the kernel is slow for us.
Nhưng việc sao chép dữ liệu từ NIC xuống, đi qua phần cứng, qua kernel rồi lên không gian người dùng, cũng quá chậm, vì kernel chậm đối với chúng ta.
So they're going to use what's called SPDK or DPDK to do kernel bypass, where basically they're managing their own TCP/IP stack in user space and don't let the OS do anything.
Nên họ dùng thứ gọi là SPDK hoặc DPDK để bỏ qua kernel (kernel bypass), về cơ bản là họ tự quản lý ngăn xếp TCP/IP của mình trong không gian người dùng và không để hệ điều hành làm gì cả.
So when Yellowbrick turns on, they call malloc, get a bunch of memory, take control of the hardware, and they never talk to the operating system ever again, because the operating system is going to ruin your life.
Khi Yellowbrick khởi động, họ gọi malloc, lấy một lượng lớn bộ nhớ, giành quyền kiểm soát phần cứng, và không bao giờ nói chuyện với hệ điều hành nữa, vì hệ điều hành sẽ phá hỏng cuộc đời bạn.
And these guys took that to the extreme, right? If you're a brand new startup, you would not do this. This is insane.
Và những người này đã đẩy điều đó đến cực đoan, đúng không? Nếu bạn là một startup mới toanh thì bạn sẽ không làm vậy. Điên rồ thật.
This is what they did 10 years ago because they were coming from the FinTech world. Question, how's that different from RDMA?
Họ làm điều này cách đây 10 năm vì họ đến từ thế giới FinTech. Câu hỏi: nó khác RDMA ở điểm nào?
RDMA is sort of the same thing, but you need specialized hardware for this. For DPDK and SPDK, you don't need specialized hardware, right? You can run that on Amazon, yes.
RDMA cũng gần giống vậy, nhưng bạn cần phần cứng chuyên dụng. Còn với DPDK và SPDK thì bạn không cần phần cứng chuyên dụng, đúng không? Bạn có thể chạy nó trên Amazon, đúng vậy.
Question real quick, there's another one from Stanford as well, but they did this 10 years ago. It's not standard, but if you need specialized hardware, you're not going to work on the cloud, right?
Hỏi nhanh một câu, còn một hệ thống khác từ Stanford nữa, nhưng họ làm điều này từ 10 năm trước. Nó không phải tiêu chuẩn, nhưng nếu bạn cần phần cứng chuyên dụng, thì bạn sẽ không chạy được trên đám mây, đúng không?
You can do UDP everywhere. All right, the last one you guys wanted was ClickHouse. All right, so I wanted to say quickly about ClickHouse. So this came out of Yandex.
Còn UDP thì chạy ở đâu cũng được. Được rồi, hệ thống cuối cùng mà các bạn muốn nghe là ClickHouse. Tôi muốn nói nhanh về ClickHouse. Nó xuất phát từ Yandex.
I think they started building actually in 2009, and when the guy came and gave a talk, as I said, When this came, I thought it was fake.
Tôi nghĩ họ thực ra bắt đầu xây dựng từ năm 2009, và khi anh ấy đến thuyết trình, như tôi đã nói, lúc nó xuất hiện, tôi tưởng nó là giả.
Not because it was Russian, but because the things that they were listing they were doing were actually kind of at par or a little more advanced than what Snowflake was doing at the time, back in like 2016.
Không phải vì nó là của Nga, mà vì những thứ mà họ liệt kê họ làm thực ra ngang ngửa hoặc tiên tiến hơn một chút so với những gì Snowflake đang làm vào thời điểm đó, hồi khoảng năm 2016.
And it seemed insane that this company I've never heard of, or sorry, I heard of Yandex, but the system I've never heard of, just showed up on the block having all these amazing features.
Và có vẻ thật điên rồ khi một công ty mà tôi chưa từng nghe đến, à xin lỗi, Yandex thì tôi có nghe, nhưng hệ thống này thì tôi chưa từng nghe, lại đột nhiên xuất hiện với toàn những tính năng tuyệt vời như vậy.
But again, it's something they've been working on for a while. So again, they're doing pull-based vector query processing. There's a shared-nothing architecture, although you can support the cloud stuff, the S3 stuff, as well.
Nhưng một lần nữa, đó là thứ họ đã phát triển từ khá lâu. Vậy nên, họ xử lý truy vấn vectơ theo kiểu pull-based. Có kiến trúc shared-nothing, dù bạn cũng có thể hỗ trợ các thứ trên đám mây, như S3.
They'll compile the expressions the same way Postgres does. Their query optimizer is not very good. They know this, they publicly say this: it's something we're working on. Their query optimizer is actually terrible.
Họ biên dịch các biểu thức giống như cách Postgres làm. Bộ tối ưu hóa truy vấn của họ không tốt lắm. Họ biết điều này, họ còn nói công khai: đó là thứ chúng tôi đang cải thiện. Bộ tối ưu hóa truy vấn của họ thực ra rất tệ.
The Postgres one is probably better, but for the things they're doing, single table queries, it's okay. It's the joins that cause the problems.
Của Postgres có lẽ tốt hơn, nhưng với những việc họ làm, tức truy vấn một bảng, thì cũng ổn. Chính các phép join mới gây ra vấn đề.
I want to talk about what they do for hash joins, but in particular on the hash tables. So Clickhouse comes with 24 different implementations of hash tables. Nobody does that in their system.
Tôi muốn nói về những gì họ làm cho hash join, nhưng cụ thể là về các bảng băm. Clickhouse có tới 24 cách cài đặt bảng băm khác nhau. Không ai làm vậy trong hệ thống của mình.
Even the Yellowbrick guys aren't that crazy, right, because they have specialized hash tables for every single possible data type that you have. So I'm going to show one graph here.
Ngay cả nhóm Yellowbrick cũng không điên đến thế, đúng không, vì họ có những bảng băm chuyên biệt cho từng kiểu dữ liệu có thể có. Tôi sẽ cho xem một biểu đồ ở đây.
This is doing a join with a group by. This is from a paper from a few years ago, but this ended up making it into the real Clickhouse system.
Đây là một phép join kèm group by. Nó lấy từ một bài báo cách đây vài năm, nhưng cuối cùng nó đã được đưa vào hệ thống Clickhouse thực tế.
It's just showing that, like, they have all these different, actually they don't have all of these, but the one that they added here is, like, if you're trying to join on strings, a linear probe hash table, just off the shelf one, is not going to perform that well.
Nó chỉ cho thấy là, họ có rất nhiều loại khác nhau, à thực ra họ không có hết đâu, nhưng loại họ thêm vào đây là, nếu bạn join trên chuỗi, một bảng băm linear probe, loại có sẵn thông thường, sẽ không chạy tốt lắm.
But if you have different hash table implementations, think of, like, you know, doing composite Optimization, how to pack the data into the slots based on different sizes, whether you exceed a cache line or not.
Nhưng nếu bạn có nhiều cách cài đặt bảng băm khác nhau, hãy nghĩ như là tối ưu hóa kết hợp, cách đóng gói dữ liệu vào các ô tùy theo kích thước khác nhau, xem có vượt quá một cache line hay không.
Then you can get much, much better performance. So this is sort of like the pre-compiled primitives that we saw.
Thì bạn có thể đạt hiệu năng tốt hơn rất nhiều. Điều này khá giống các primitive biên dịch sẵn mà ta đã thấy.
Like, if I'm doing a comparison on like this key or this type with this constant, I can have a specialized version of that function to do that comparison.
Ví dụ, nếu tôi so sánh khóa này hoặc kiểu này với hằng số này, tôi có thể có một phiên bản chuyên biệt của hàm để thực hiện phép so sánh đó.
They're basically doing the same thing but for hash tables, for all the different possible data types and the lookups you want to do on that. And that part's super amazing.
Về cơ bản họ làm điều tương tự nhưng cho bảng băm, cho mọi kiểu dữ liệu có thể có và các phép tra cứu bạn muốn thực hiện trên đó. Và phần đó thật sự tuyệt vời.
They do a bunch of SIMD stuff as well, where they try to have different versions of different operators that are SIMDified for different versions of SIMD on Intel.
Họ cũng làm khá nhiều thứ với SIMD, khi họ cố có nhiều phiên bản khác nhau của các toán tử được SIMD hóa cho các phiên bản SIMD khác nhau trên Intel.
So there's AVX-512, AVX-256. Sometimes the 512 one is not as fast as the 256 one, because the older CPUs would actually throttle down the frequency because they overheated.
Như AVX-512, AVX-256. Đôi khi bản 512 không nhanh bằng bản 256, vì các CPU đời cũ thực ra sẽ giảm xung nhịp xuống do bị quá nhiệt.
So they would be able to detect and say, I'm going to run the AVX-2 version, the 256 version, instead of the 512, based on what hardware they're running on.
Nên họ có thể phát hiện và quyết định: tôi sẽ chạy phiên bản AVX-2, bản 256, thay vì bản 512, tùy vào phần cứng mà họ đang chạy.
It's amazing. All right, so let me switch over to the high speaker. Wherever time.
Thật tuyệt vời. Được rồi, giờ tôi xin chuyển sang diễn giả khách mời. Lúc nào cũng được.
But again, the main takeaway from all this that I want you guys to get is that these systems are doing, you know, amazing stuff, and trying to get things to run as fast as possible is really challenging to do.
Nhưng một lần nữa, điều chính mà tôi muốn các bạn rút ra từ tất cả những điều này là các hệ thống này đang làm những việc rất đáng kinh ngạc, và việc cố gắng làm cho mọi thứ chạy nhanh nhất có thể là rất khó.
Got it. All right, so remember the Haiku system we talked about before, they did that early compilation stuff. This is the same school. They're very strong in databases.
Rõ rồi. Được rồi, các bạn còn nhớ hệ thống Haiku mà chúng ta đã nói trước đây không, họ đã làm phần biên dịch sớm đó. Đây là cùng một trường. Họ rất mạnh về cơ sở dữ liệu.
Leiden, thank you so much for being here. The floor is yours. Go for it. Okay, so I'm starting right? Yes, go for it. Yeah, okay.
Leiden, cảm ơn bạn rất nhiều vì đã có mặt. Xin mời bạn. Bắt đầu thôi. Được, vậy tôi bắt đầu nhé? Vâng, mời bạn. Vâng, được.
Right, okay, so do we understand SQL, and if not, why?
Được rồi, vậy chúng ta có hiểu SQL không, và nếu không thì tại sao?
Right, okay, so I'm spending just a little tour, a couple of things about myself, so I'm spending Most of my time at Relational AI, and I represent Relational AI Paris, and I'm also part-time at the University of Edinburgh, where I was full-time for two decades prior to Relational AI.
Được rồi, trước hết tôi xin giới thiệu qua vài điều về bản thân, tôi dành phần lớn thời gian ở Relational AI, và tôi đại diện cho Relational AI Paris, đồng thời tôi cũng làm bán thời gian tại Đại học Edinburgh, nơi tôi làm toàn thời gian suốt hai thập kỷ trước khi đến Relational AI.
Okay, okay. So last time Relational AI was here, you know, presented in CMU, so we talked about Rel, which is a programming language that we developed in Relational AI.
Được rồi. Lần trước Relational AI đến đây, trình bày tại CMU, chúng tôi đã nói về Rel, một ngôn ngữ lập trình do chúng tôi phát triển tại Relational AI.
It's a programming language for relational data.
Đó là ngôn ngữ lập trình cho dữ liệu quan hệ.
If you're interested in that, you can see there was a recorded talk by Martin, about 10-15 minutes, and also there was a paper in SIGMOD with details of the language.
Nếu các bạn quan tâm đến nó, có một bài nói chuyện được ghi hình của Martin, khoảng 10-15 phút, và cũng có một bài báo ở SIGMOD với các chi tiết về ngôn ngữ này.
But we did not, in that talk, we didn't fully explain what were the SQL problems that we tried to fix, and that by itself would require a very long talk.
Nhưng trong bài nói đó, chúng tôi đã không giải thích đầy đủ những vấn đề của SQL mà chúng tôi muốn khắc phục, và riêng điều đó đã cần một bài nói chuyện rất dài.
But what I'll try to do today, in the short time that I have, I'll try to give you a taste of SQL problems that we are, that we are trying to fix.
Nhưng hôm nay, trong khoảng thời gian ngắn ngủi mà tôi có, tôi sẽ cố gắng cho các bạn thấy sơ qua những vấn đề của SQL mà chúng tôi đang cố gắng khắc phục.
Okay, so you all know what SQL is, right? Okay, so it's like the language for relational database. It was a standard since 86, international standards since 87, implemented all over the place.
Được rồi, các bạn đều biết SQL là gì, đúng không? Đó là ngôn ngữ dành cho cơ sở dữ liệu quan hệ. Nó là chuẩn từ năm 86, chuẩn quốc tế từ năm 87, và được triển khai ở khắp nơi.
If you look at the top programming languages according to IEEE, so this year it's at number four.
Nếu nhìn vào các ngôn ngữ lập trình hàng đầu theo IEEE, thì năm nay nó đứng thứ tư.
If you look at the job ads, and which, which jobs require knowledge of SQL, last year it was number one, this year it's spelled just below Python at number two.
Nếu nhìn vào các tin tuyển dụng, xem công việc nào yêu cầu biết SQL, năm ngoái nó đứng thứ nhất, năm nay nó đứng thứ hai, ngay dưới Python.
Right, so now SQL has been with us since 86.
Vậy là SQL đã đồng hành cùng chúng ta từ năm 86.
It was standardized and there were like several standard several iterations, 92 was when it was basically reached its current shape, and after that we now live with SQL 2023.
Nó đã được chuẩn hóa và có nhiều phiên bản chuẩn kế tiếp nhau, năm 92 là lúc về cơ bản nó đạt đến hình dạng hiện nay, và sau đó chúng ta đang dùng SQL 2023.
We are on the way to produce SQL 2027. There are a whole bunch of additions in between. It's not free; if you want to buy it, it will make you about $2,000 poorer.
Chúng ta đang trên đường tiến tới SQL 2027. Ở giữa có cả một loạt phần bổ sung. Nó không miễn phí; nếu muốn mua, bạn sẽ nghèo đi khoảng 2.000 đô la.
And it consists of 11 parts, which are numbered by random numbers between 1 and 16, so don't expect it to be consecutive. There are actually reasons for this, but not for this talk.
Và nó gồm 11 phần, được đánh số bằng những con số ngẫu nhiên từ 1 đến 16, nên đừng mong chúng liên tiếp nhau. Thực ra có lý do cho việc này, nhưng không phải cho buổi nói chuyện này.
And what ultimately makes us implement is essentially the core, which is the part two that's called SQL foundation.
Và thứ cuối cùng mà chúng ta triển khai về cơ bản là phần lõi, tức là phần hai, gọi là SQL foundation.
There are some discrepancies, plus something else from the standard, plus something else not from the standard, but that's the work we live in. All right, who designs it?
Có một vài điểm không khớp, cộng thêm một số thứ khác từ chuẩn, cộng thêm một số thứ không thuộc chuẩn, nhưng đó là thế giới mà chúng ta đang làm việc. Được rồi, ai thiết kế nó?
It's a committee with this fantastic name: ISO IEC JTC 1 SC 32 WG 3. Again, each part of this name actually has a meaning.
Đó là một ủy ban với cái tên tuyệt vời này: ISO IEC JTC 1 SC 32 WG 3. Một lần nữa, mỗi phần trong cái tên này thực ra đều có ý nghĩa.
So that's the picture of the committee from its last meeting in Barcelona just a couple months ago, right?
Đây là ảnh chụp ủy ban trong cuộc họp gần nhất ở Barcelona chỉ vài tháng trước, đúng không?
And the way it works is that, so most of the technical work happens inside another organization called INCITS, which stands for International Committee on Information Technology Standards.
Và cách nó vận hành là, phần lớn công việc kỹ thuật diễn ra bên trong một tổ chức khác gọi là INCITS, viết tắt của International Committee on Information Technology Standards.
Despite the name international in it, it's actually very US-centric, though half of the committee is from Europe and Asia, but you only can be in this committee if you're representing a registered entity.
Dù có chữ quốc tế trong tên, nó thực ra rất thiên về Hoa Kỳ, dù một nửa ủy ban đến từ châu Âu và châu Á, nhưng bạn chỉ có thể tham gia ủy ban này nếu đại diện cho một tổ chức đã đăng ký.
So discussions in this committee lead to papers that are then forwarded to the international committee that meets a few times a year.
Các thảo luận trong ủy ban này dẫn đến các bài báo rồi được chuyển lên ủy ban quốc tế, họp vài lần mỗi năm.
Then basically decisions are made in that committee, people vote first in the committee, and then the papers get incorporated into draft standards, and then the national body, so each nation will have its own standards committee, they'll vote to approve those standards.
Sau đó các quyết định về cơ bản được đưa ra ở ủy ban đó, mọi người bỏ phiếu trước trong ủy ban, rồi các bài báo được đưa vào các bản dự thảo chuẩn, và sau đó là các cơ quan quốc gia, mỗi quốc gia sẽ có ủy ban tiêu chuẩn riêng, họ sẽ bỏ phiếu phê duyệt các chuẩn đó.
This vote happens in several stages, and eventually, that's why there is such a block, usually four, five years between additions of standards, and eventually one day the standard is approved, and then the fun begins.
Việc bỏ phiếu này diễn ra qua nhiều giai đoạn, và rốt cuộc, đó là lý do có một độ trễ như vậy, thường là bốn, năm năm giữa các lần bổ sung chuẩn, và cuối cùng một ngày chuẩn được phê duyệt, rồi trò vui bắt đầu.
Okay, let's start with a little fun, you know, something that you all know about SQL or learn about SQL.
Được rồi, hãy bắt đầu bằng một chút vui vẻ, một điều mà các bạn đều biết hoặc đã học về SQL.
I have two relations, R and S, so both have simple attribute A, and I ask you to compute the difference within these two relations.
Tôi có hai quan hệ, R và S, cả hai đều có một thuộc tính đơn giản A, và tôi yêu cầu các bạn tính hiệu của hai quan hệ này.
Let's not worry about multisets, let's not worry about bag semantics, let's say everything is A set. Okay, there are three ways you can do it.
Đừng bận tâm đến multiset, đừng bận tâm đến ngữ nghĩa bag, cứ coi mọi thứ là một tập hợp. Được rồi, có ba cách để làm.
You can just directly use the SQL EXCEPT operator to compute the difference, or you can use the subquery.
Bạn có thể dùng trực tiếp toán tử EXCEPT của SQL để tính hiệu, hoặc có thể dùng truy vấn con.
You can say, give me everything in the relation R that's not in the relation S, or you can use EXISTS for a subquery.
Bạn nói: hãy cho tôi mọi thứ trong quan hệ R mà không có trong quan hệ S, hoặc bạn có thể dùng EXISTS cho một truy vấn con.
You say, give me everything from relation R such that it does not exist something in the relation S that's equal to it.
Bạn nói: hãy cho tôi mọi thứ từ quan hệ R sao cho không tồn tại thứ gì trong quan hệ S bằng với nó.
So if we ask you, use students, to write this type of query, you will write one of those, and you would expect to get full marks because you run it over the set and say, okay, well, same answer, they're equivalent queries.
Vậy nếu chúng tôi yêu cầu sinh viên viết loại truy vấn này, các bạn sẽ viết một trong những cách đó, và các bạn sẽ mong được điểm tối đa vì chạy nó trên tập hợp và nói rằng, Được rồi, cùng một kết quả, chúng là các truy vấn tương đương.
In fact, lots of SQL programming things say that they're equivalent queries. But let me change a little bit.
Thực ra, rất nhiều tài liệu lập trình SQL đều nói rằng chúng là các truy vấn tương đương. Nhưng để tôi thay đổi một chút.
Let me replace two with a null in this query, and then suddenly what I get is three different answers, right?
Tôi thay số hai bằng null trong truy vấn này, và đột nhiên tôi nhận được ba kết quả khác nhau, đúng không?
And I can assure you that a huge number of people who never write SQL queries, they fall into similar traps, right?
Và tôi có thể đảm bảo rằng rất nhiều người, kể cả những người không bao giờ viết truy vấn SQL, cũng rơi vào những cái bẫy tương tự, đúng không?
You know, the change NOT IN, NOT EXISTS, and, you know, suddenly you can see that there's a very dramatic difference between the writing, is NOT IN and NOT EXISTS.
Bạn đổi giữa NOT IN và NOT EXISTS, và đột nhiên bạn có thể thấy có một sự khác biệt rất lớn giữa cách viết NOT IN và NOT EXISTS.
All right, so we have a bit of a problem, right? But let me tell you that we have an even bigger problem, understanding SQL. What is simpler in SQL than SELECT stuff, right?
Được rồi, vậy là chúng ta có một vấn đề nhỏ, đúng không? Nhưng tôi xin nói rằng chúng ta còn có một vấn đề lớn hơn, đó là việc hiểu SQL. Trong SQL có gì đơn giản hơn SELECT cái gì đó chứ?
The first thing that you do, like you learn SQL, SELECT stuff FROM R, right, from some table, you see the table.
Điều đầu tiên bạn làm khi học SQL, SELECT cái gì đó FROM R, tức là từ một bảng nào đó, bạn nhìn vào bảng.
Okay, so I'll make a claim that the absolute majority of SQL programmers actually don't know what SELECT star does, right? So let me explain this on an example.
Được rồi, vậy tôi xin khẳng định rằng đại đa số những người lập trình SQL thực ra không biết SELECT * làm gì, đúng không? Để tôi giải thích bằng một ví dụ.
So, okay, so let's say we have a relation R again, a single attribute A, value one, and I write this query like, repeat attribute A twice in the output, right?
Giả sử chúng ta lại có một quan hệ R, với một thuộc tính A, giá trị là một, và tôi viết truy vấn này, lặp lại thuộc tính A hai lần trong kết quả, đúng không?
Okay, so that's going to give me this relation with attribute A repeated twice. Every DBMS will give you the same thing.
Được rồi, nó sẽ cho tôi quan hệ này với thuộc tính A xuất hiện hai lần. Hệ quản trị CSDL nào cũng sẽ cho bạn kết quả như vậy.
Now I say this: let's use it as a subquery and say, let's select star from that subquery.
Bây giờ tôi nói thế này: hãy dùng nó làm truy vấn con và nói rằng, hãy select * từ truy vấn con đó.
Like, I literally plug this query Q from above, I just plug it into this line, and from, and I ask you what this query returns.
Tức là tôi chèn nguyên văn truy vấn Q ở trên vào dòng này, vào mệnh đề FROM, và tôi hỏi bạn truy vấn này trả về gì.
And in my experience, actually, of talking to people directly, I ask this, and even like talking to students when I teach in front of the class, people start guessing and say, well, maybe it will return the same as before, maybe not, maybe it will give an error.
Và theo kinh nghiệm của tôi khi trực tiếp nói chuyện với mọi người, tôi hỏi câu này, kể cả khi nói chuyện với sinh viên lúc tôi giảng trước lớp, mọi người bắt đầu đoán và nói, ừm, có thể nó trả về giống như trước, có thể không, có thể nó báo lỗi.
What's going to happen? I mean, this is a one line query. We select star, the relation has one tuple, and people start scratching their heads.
Chuyện gì sẽ xảy ra? Ý tôi là, đây chỉ là truy vấn một dòng. Chúng ta select *, quan hệ có một bộ, và mọi người bắt đầu gãi đầu.
And there's a very good reason why they scratch their heads, because the answer to this question is: it depends on which system you run this query on.
Và có một lý do rất chính đáng khiến họ gãi đầu, bởi vì câu trả lời cho câu hỏi này là: nó phụ thuộc vào hệ thống mà bạn chạy truy vấn này.
Postgres and SQLite will give you one star, will give you basically as above, but Oracle, SQL Server, MySQL and DB2 will all give a compile time error, and DuckDB now will also give a compile time error.
Postgres và SQLite sẽ cho bạn một cột, về cơ bản giống như ở trên, nhưng Oracle, SQL Server, MySQL và DB2 đều báo lỗi lúc biên dịch, và giờ đây DuckDB cũng báo lỗi lúc biên dịch.
Okay, already, like, one line queries, so let's start, we are getting into trouble. But now let's get into more trouble.
Được rồi, mới chỉ là những truy vấn một dòng thôi mà chúng ta đã gặp rắc rối. Nhưng bây giờ hãy xem rắc rối lớn hơn.
Okay, I ask, okay, let's run this query: give me everything from R where the condition is that this query Q prime, the one that I've just saw that sometimes runs, sometimes gives a compile time error, and when this query returns something, what will this do?
Được rồi, tôi hỏi, hãy chạy truy vấn này: cho tôi mọi thứ từ R với điều kiện là truy vấn Q phẩy này, truy vấn tôi vừa cho các bạn thấy, có lúc chạy được, có lúc báo lỗi lúc biên dịch, và khi truy vấn này trả về một cái gì đó, thì nó sẽ làm gì?
It will return something. So let's run this. You know, most people say, oh, well, probably, no, it will give you R if it runs on Postgres and SQLite, maybe compile time error.
Nó sẽ trả về một cái gì đó. Vậy hãy chạy thử. Bạn biết đấy, hầu hết mọi người sẽ nói: ồ, có lẽ là không, nó sẽ trả về R nếu chạy được trên Postgres và SQLite, hoặc có thể là lỗi biên dịch.
If it runs, if it doesn't run, the answer is no, it will always give it irrationally, right?
Nếu chạy được, hoặc nếu không chạy được, thì câu trả lời là không, nó sẽ luôn trả về kết quả một cách phi lý, đúng không?
So you see, the thing is that, like, with this super, super simple queries, I can get, uh, I can start, like, with super simple devices in SQL, I can start writing queries that even experienced SQL programmers will Start questioning what's going on.
Vậy là bạn thấy đấy, chỉ với những truy vấn cực kỳ đơn giản, tôi có thể, tôi có thể bắt đầu từ những cấu trúc rất đơn giản trong SQL, tôi có thể bắt đầu viết ra những truy vấn mà ngay cả những lập trình viên SQL giàu kinh nghiệm cũng bắt đầu thắc mắc chuyện gì đang xảy ra.
Okay, let's come back, move on. Business: let's say I have a database that has orders and payments.
Được rồi, quay lại và đi tiếp nhé. Tình huống kinh doanh: giả sử tôi có một cơ sở dữ liệu gồm đơn hàng và thanh toán.
All right, we have orders, and we know that sometimes some of the orders have been paid, and I ask you to write a query: give me unpaid orders.
Được rồi, ta có các đơn hàng, và ta biết rằng đôi khi một số đơn hàng đã được thanh toán, và tôi yêu cầu bạn viết một truy vấn: cho tôi các đơn hàng chưa thanh toán.
Okay? Give me all the orders for which there is no payment. Fine. You know, this is a very, very simple query. You know, let's run it in SQL. What are we going to get?
Được chứ? Cho tôi tất cả các đơn hàng không có khoản thanh toán nào. Tốt. Bạn biết đấy, đây là một truy vấn rất, rất đơn giản. Hãy chạy nó trong SQL. Ta sẽ nhận được gì?
Well, in this database we are going to get that order two and order three are not paid, right? We know intuitively it's wrong, because we know that there are two payments, right?
Trong cơ sở dữ liệu này, ta sẽ nhận được kết quả là đơn hàng hai và đơn hàng ba chưa được thanh toán, đúng không? Theo trực giác ta biết là sai, vì ta biết có hai khoản thanh toán, đúng không?
It's, uh, you know, how do we know that both of these, order two and order three, are not paid? We don't know this.
Làm sao ta biết được cả hai đơn này, đơn hàng hai và đơn hàng ba, đều chưa thanh toán? Ta không biết điều đó.
It's quite possible that one of them is, uh, is actually paid, but SQL will tell you that order two and order three are unpaid.
Hoàn toàn có thể một trong hai đơn thực ra đã được thanh toán, nhưng SQL sẽ nói với bạn rằng đơn hàng hai và đơn hàng ba chưa thanh toán.
Imagine then you go and chase the customer and say, "You didn't pay," the customer says, "I paid," and then, you know, the customer never comes back. So we get what's called false positives, right?
Hãy tưởng tượng bạn đi đòi tiền khách hàng và nói: "Anh chưa thanh toán", khách hàng nói "Tôi đã trả rồi", và rồi khách hàng không bao giờ quay lại nữa. Vậy ta có cái gọi là dương tính giả, đúng không?
So an answer that we know is not true, and actually these false positives, they're fairly common, right?
Tức là một câu trả lời mà ta biết là không đúng, và thực ra các dương tính giả này khá phổ biến, đúng không?
So we tried to experiment a little bit with TPC-H-like queries and populate the database with nulls, and these false positives pop up all the time, right?
Chúng tôi đã thử nghiệm một chút với các truy vấn giống TPC-H và điền các giá trị null vào cơ sở dữ liệu, và các dương tính giả này xuất hiện liên tục, đúng không?
And, uh, yeah, I also would like to point out that, you know, most of the time you see graphs coming from SIGMOD papers, but this is a very unusual creature: it's a graph that comes from a PODS paper, from a Ceresco paper.
Và, vâng, tôi cũng muốn chỉ ra rằng, bạn biết đấy, phần lớn thời gian bạn thấy các biểu đồ từ các bài báo SIGMOD, nhưng đây là một sinh vật rất khác thường: đó là biểu đồ từ một bài báo PODS, từ một bài của Ceresco.
Okay, so nulls are all over the place, right?
Được rồi, vậy null có mặt ở khắp nơi, đúng không?
You know, if you are European and you want to go to Texas and you ask for the weather, they tell you, don't ask about Celsius, only Fahrenheit.
Bạn biết đấy, nếu bạn là người châu Âu và muốn đến Texas rồi hỏi về thời tiết, họ sẽ bảo đừng hỏi độ Celsius, chỉ có Fahrenheit thôi.
You know, you can be asked for a payment on your multiple nulls, and this is actually a screenshot of a real database of a big retailer, right?
Bạn biết đấy, bạn có thể bị yêu cầu thanh toán với nhiều giá trị null, và đây thực ra là ảnh chụp màn hình của một cơ sở dữ liệu thật của một nhà bán lẻ lớn, đúng không?
And you can see the lab nulls, and nulls cause problems.
Và bạn có thể thấy các null ở phần nhãn, và null gây ra vấn đề.
Like, you know, they're like all the stories about, actually, it's a real story about a person whose last name is null and who cannot do anything in this life anymore, now that everything has to be recorded in the database in the not null fields.
Chẳng hạn, có đủ loại câu chuyện, thực ra là một câu chuyện có thật về một người có họ là null và không thể làm gì được nữa trong cuộc sống này, vì giờ mọi thứ đều phải được ghi vào cơ sở dữ liệu trong các trường not null.
And uh, so when nulls appear, you know that things kind of go bad, right?
Và vậy nên, khi null xuất hiện, bạn biết là mọi thứ có phần trở nên tồi tệ, đúng không?
You know, like in textbooks that are that you know, well, null treatments is fundamentally at odds with the way the world behaves.
Bạn biết đấy, như trong các sách giáo khoa thì, ừm, cách xử lý null về cơ bản mâu thuẫn với cách thế giới vận hành.
Books for sick database professionals tell you you get wrong answers to queries, you cannot trust answers, and like they're even like headlines, like, you know, this is this is from BBC, that children heart surgery halted by incomplete data, right?
Những cuốn sách dành cho dân chuyên cơ sở dữ liệu "đau khổ" sẽ bảo bạn rằng bạn nhận được câu trả lời sai cho các truy vấn, bạn không thể tin vào kết quả, thậm chí còn có cả những tiêu đề báo, bạn biết đấy, cái này là của BBC, rằng ca phẫu thuật tim cho trẻ em bị đình hoãn do dữ liệu không đầy đủ, đúng không?
So it could be quite dramatic. Okay, uh, so there's one other question I want to briefly address, and this is how standard is the standard, all right?
Nên hậu quả có thể khá nghiêm trọng. Được rồi, còn một câu hỏi nữa tôi muốn nói qua một chút, đó là chuẩn này có thực sự chuẩn đến mức nào, được chứ?
We have the standard, we assume that everybody has to do the same stuff, but actually if we run multiple queries on different databases, we we know sort of from experience that some of them will give you different results.
Chúng ta có chuẩn, và ta giả định rằng ai cũng phải làm giống nhau, nhưng thực ra nếu chạy nhiều truy vấn trên các cơ sở dữ liệu khác nhau, thì chúng ta biết, phần nào từ kinh nghiệm, rằng một số cơ sở dữ liệu sẽ cho kết quả khác nhau.
So we try to quantify that, and from a random query generator, about two percent of queries for the most basic fragment, they behave differently.
Vì vậy chúng tôi thử định lượng điều đó, và với một bộ sinh truy vấn ngẫu nhiên, khoảng hai phần trăm số truy vấn thuộc phần cơ bản nhất có hành vi khác nhau.
Some issues, admittedly, are just minor and very syntactic, but some some are serious. So I'll give you two examples of serious issues, right, of things that could be unexpected.
Phải thừa nhận một số vấn đề chỉ nhỏ và thuần về cú pháp, nhưng một số thì nghiêm trọng. Tôi sẽ đưa ra hai ví dụ về các vấn đề nghiêm trọng, tức là những điều có thể nằm ngoài dự đoán.
We're kind of a little over time. We're over time, sorry. Ah, okay, it's 10 minutes. Okay, I'll uh yeah, I'll just I'll just I'll just wrap up with this, right?
Hình như chúng ta hơi quá giờ rồi. Quá giờ rồi, xin lỗi. À, được rồi, còn 10 phút. Được rồi, tôi sẽ kết thúc bằng điều này nhé.
So and basically I say, you know, why we find these questions problematic in SQL, because SQL standard has been growing crazily, right?
Về cơ bản, tôi muốn nói vì sao chúng tôi thấy những vấn đề này là rắc rối trong SQL, vì chuẩn SQL đã phình to một cách chóng mặt, đúng không?
It started with 10 page codes papers and 100 pages per SQL standard. Now we had 4500 pages.
Nó bắt đầu từ các bài báo của Codd dài 10 trang và chuẩn SQL 100 trang. Giờ thì nó đã dài 4500 trang.
There is not a single person in the world who knows everything, and what we are trying to do in relation is to have a different approach: to have a small, well-defined core language with a clear semantics, and then extended by libraries.
Không có một ai trên thế giới biết hết mọi thứ trong đó, và điều chúng tôi đang cố làm trong relation là có một cách tiếp cận khác: có một ngôn ngữ lõi nhỏ gọn, được định nghĩa rõ ràng với ngữ nghĩa minh bạch, rồi mở rộng bằng các thư viện.
So this is what this is our approach. This is what language hero is. All right, so again, for the two things, again, this is the last class. See you guys on Thursday next week.
Đây là cách tiếp cận của chúng tôi. Đây là điều mà ngôn ngữ hero hướng tới. Được rồi, vậy về hai việc này, đây là buổi học cuối cùng. Hẹn gặp các bạn vào thứ Năm tuần sau.
Uh, and then the last thing also too is that we got an announcement from Farnam this morning, and the good news is that DJ Cash won Most Dank DJ at Carnegie Mellon University this year.
Ừm, và điều cuối cùng nữa là chúng ta vừa nhận được một thông báo từ Farnam sáng nay, và tin vui là DJ Cash đã giành danh hiệu Most Dank DJ của Carnegie Mellon University năm nay.
Give a round of applause. Can you get a photo here?
Mọi người vỗ tay nào. Bạn chụp một tấm ảnh ở đây được không?
So here, yeah, you got it. Awesome, awesome. All right, guys, give a round of applause to DJ Cash. Thank you, Lennon. And then good luck with your final exams, everything else.
Đây, đúng rồi, được rồi đấy. Tuyệt vời. Nào mọi người, vỗ tay chúc mừng DJ Cash nào. Cảm ơn Lennon. Và chúc các bạn may mắn với các kỳ thi cuối kỳ và mọi thứ khác.
And then again, Saturday office hours, Sunday project due, Thursday next week is the final exam.
Nhắc lại, giờ hỗ trợ vào thứ Bảy, Chủ nhật là hạn nộp dự án, thứ Năm tuần sau là thi cuối kỳ.
Okay, slow great.
Được rồi, tuyệt lắm.
Đă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.