Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
Alright, let's get started. Round of applause for DJ Cash. Welcome back everyone. You did a bunch of tablets over the break, went to LA and San Francisco.
Được rồi, bắt đầu thôi. Mọi người vỗ tay chào DJ Cash nào. Chào mừng mọi người quay trở lại. Trong kỳ nghỉ, bạn đã chơi khá nhiều tablet, còn đến LA và San Francisco nữa.
Did you do any shows out there, or are you just hanging out? Oh yeah, DJing a little bit here and there. Did you livestream it? My friend wanted to, but we didn't.
Ở đó bạn có biểu diễn buổi nào không, hay chỉ đi chơi thôi? Ồ có, cũng DJ chỗ này chỗ kia một chút. Bạn có livestream không? Bạn em muốn livestream, nhưng bọn em không làm.
Alright, so hopefully everyone had a good break. I did what I, because I only care about databases, I visited a bunch of database companies.
Được rồi, hy vọng mọi người đã có một kỳ nghỉ vui vẻ. Còn thầy thì làm đúng việc của mình, vì thầy chỉ quan tâm đến cơ sở dữ liệu, thầy đã ghé thăm khá nhiều công ty cơ sở dữ liệu.
We went to Snowflake, we went to Supabase, we went to PlanetScale, we went to Microsoft. We talked about databases, it was awesome.
Thầy đã đến Snowflake, đến Supabase, đến PlanetScale, rồi đến Microsoft. Bọn thầy trao đổi về cơ sở dữ liệu, tuyệt lắm.
And when we talk about query optimization next week, I can share what I think is, from Microsoft, one of the most brilliant ideas I've heard in the entire year of how they're going to prove two SQL queries are the same, and they're going to use the query optimizer for that.
Và khi nói về tối ưu hóa truy vấn vào tuần tới, thầy có thể chia sẻ điều mà thầy nghĩ là, từ Microsoft, một trong những ý tưởng xuất sắc nhất thầy được nghe trong cả năm, về việc họ sẽ chứng minh hai truy vấn SQL là tương đương nhau như thế nào, và họ sẽ dùng bộ tối ưu hóa truy vấn để làm việc đó.
So next week we'll see how, it's not, you know, kind of, you need to understand what the query optimizer is first, but when they told me what they were doing, I was like, oh, that's pure genius, because it's taking a SQL query, rewriting it with an LLM, and then you need to prove that it's the same and use the query optimizer for it.
Vậy tuần tới chúng ta sẽ thấy cách làm, nó không phải là, bạn biết đấy, trước hết các em cần hiểu bộ tối ưu hóa truy vấn là gì, nhưng khi họ kể cho thầy họ đang làm gì, thầy đã thốt lên: ồ, đúng là thiên tài, vì họ lấy một truy vấn SQL, viết lại nó bằng một LLM, rồi cần chứng minh hai truy vấn là như nhau và dùng bộ tối ưu hóa truy vấn cho việc đó.
Sorry, I'm getting way ahead of myself, because I think the idea is awesome, but we can talk about it briefly next week.
Xin lỗi, thầy nói đi quá xa rồi, vì thầy thấy ý tưởng này tuyệt vời, nhưng chúng ta sẽ nói ngắn gọn về nó vào tuần tới.
Today we're going to talk about how we're going to actually execute queries. Alright, so for everyone, Project 2 is coming up, due this Sunday. Again, the recitation video is available on Box, on Piazza.
Hôm nay chúng ta sẽ nói về việc thực sự thực thi các truy vấn như thế nào. Được rồi, thông báo cho cả lớp, Project 2 sắp đến hạn, hạn nộp là Chủ nhật này. Một lần nữa, video buổi thảo luận có trên Box và trên Piazza.
I think AWS is down this morning, so everything's broken, so you couldn't probably get to Gradescope and to AWS, but it should be up now. I haven't checked, but it was broken this morning.
Thầy nghĩ sáng nay AWS bị sập, nên mọi thứ đều hỏng, nên có lẽ các em không vào được Gradescope và AWS, nhưng giờ chắc đã hoạt động lại. Thầy chưa kiểm tra, nhưng sáng nay nó bị hỏng.
And then we're having a special office hours this Saturday on the 25th at 3 o'clock, same location on the fifth floor. And then for the midterm grades, they've been posted on Gradescope on Canvas.
Và chúng ta sẽ có một buổi office hours đặc biệt vào thứ Bảy này, ngày 25, lúc 3 giờ, cùng địa điểm ở tầng năm. Còn điểm giữa kỳ thì đã được đăng trên Gradescope và Canvas.
And then if you want to view your graded exam with the solution, come to my office hours on Wednesdays and you can sit down with it and look at it.
Và nếu muốn xem bài thi đã chấm cùng lời giải, hãy đến office hours của thầy vào các thứ Tư, các em có thể ngồi xuống xem bài.
Who here has not started Project 2? Really? Okay, wow. Alright.
Ai ở đây chưa bắt đầu Project 2? Thật sao? Ồ, trời. Được rồi.
It's not going to be good. That's not good. I warned you. Alright, Project 2 is much harder than Project 1, so please start immediately after class. Alright, so other things going on.
Sẽ không ổn đâu. Như vậy không tốt. Thầy đã cảnh báo rồi. Project 2 khó hơn Project 1 nhiều, nên hãy bắt đầu ngay sau buổi học. Được rồi, còn những việc khác đang diễn ra.
So today after class, we have the guys from Columnar who are building this thing called Apache Arrow. Think of it like it's a file format similar to Parquet or Oracle Vortex, but it's in-memory.
Hôm nay sau giờ học, chúng ta có các bạn từ Columnar, những người đang xây dựng thứ gọi là Apache Arrow. Hãy nghĩ nó như một định dạng tệp tương tự Parquet hoặc Oracle Vortex, nhưng nằm trong bộ nhớ.
So this is a way to transfer data quickly between different systems. Arrow is used everywhere. And then they have this Arrow Database Connectivity API.
Đây là cách để truyền dữ liệu nhanh giữa các hệ thống khác nhau. Arrow được dùng ở khắp nơi. Và họ có API gọi là Arrow Database Connectivity.
It's a layer that sits in front of your application and the database server, so you can send data back and forth between your application and the database server much more quickly.
Đó là một lớp nằm giữa ứng dụng của bạn và máy chủ cơ sở dữ liệu, để bạn có thể gửi dữ liệu qua lại giữa ứng dụng của bạn và máy chủ cơ sở dữ liệu nhanh hơn nhiều.
This is used in pretty much every single modern system. So that'll be our talk today at 4:30. Tomorrow, I'll post this on Piazza when it comes back online.
Cách này được dùng trong hầu như mọi hệ thống hiện đại. Đó sẽ là buổi nói chuyện của chúng ta hôm nay lúc 4:30. Ngày mai, em sẽ đăng cái này lên Piazza khi nó hoạt động trở lại.
We have the guys from Astronomer coming to give a tech talk on the eighth floor at noon. So there'll be pizza here for this one. Astronomer is the main company building Airflow.
Các anh bên Astronomer sẽ đến trình bày một buổi tech talk trên tầng tám vào buổi trưa. Nên sẽ có pizza ở đây cho buổi này. Astronomer là công ty chính xây dựng Airflow.
This is like an orchestration layer for sending data from one system to the other. And I know we posted for internships and jobs from those guys on Piazza.
Nó giống như một lớp điều phối để gửi dữ liệu từ hệ thống này sang hệ thống khác. Và tôi biết chúng tôi đã đăng tin thực tập và việc làm của các anh ấy trên Piazza.
So they're coming on campus tomorrow to give a talk about that.
Ngày mai họ sẽ đến trường để nói về chuyện đó.
And then I'll follow up with people if you want to meet with them to have like a small group session about discussing internships and jobs.
Sau đó tôi sẽ liên hệ lại với các bạn nào muốn gặp họ để có một buổi nhóm nhỏ trao đổi về thực tập và việc làm.
We'll arrange that in the afternoon before they fly out.
Chúng ta sẽ sắp xếp vào buổi chiều trước khi họ bay về.
And then next week, same time, will be on Monday, the seminar series will be the guy from SingleStore to expand upon what he talked about in this class.
Còn tuần sau, cùng giờ, vào thứ Hai, chuỗi seminar sẽ có anh đến từ SingleStore để nói sâu hơn về những gì anh ấy đã trình bày trong lớp này.
Again, all this is optional. And I'll post about the Astronomer stuff on Piazza later today.
Một lần nữa, tất cả những điều này đều không bắt buộc. Và lát nữa hôm nay tôi sẽ đăng về phần của Astronomer trên Piazza.
All right, so last class before the break, we were discussing different join algorithms, join operator implementations: nested loop joins, sort-merge joins, and hash joins.
Được rồi, buổi học cuối trước kỳ nghỉ, chúng ta đã bàn về các thuật toán join khác nhau, các cách cài đặt toán tử join: nested loop join, sort-merge join và hash join.
So now at this point, we've covered the basic building blocks you need to be able to run queries. We know how to sort data, whether it's in memory or out of memory.
Vậy đến lúc này, chúng ta đã học xong các khối cơ bản cần có để chạy truy vấn. Chúng ta biết cách sắp xếp dữ liệu, dù nằm trong bộ nhớ hay ngoài bộ nhớ.
We know how to do aggregations. We know how to do joins.
Chúng ta biết cách làm aggregation. Chúng ta biết cách làm join.
And so starting today and for the next two weeks, now we'll put all these pieces together in a conceptual system we'll describe as we go along. But now we can actually start executing queries.
Vì vậy, bắt đầu từ hôm nay và trong hai tuần tới, chúng ta sẽ ghép tất cả các mảnh này lại với nhau trong một hệ thống mang tính khái niệm mà ta sẽ mô tả dần. Nhưng giờ chúng ta thực sự có thể bắt đầu thực thi truy vấn.
So we can take the buffer pool that we built. We can take the page layouts we've designed. We can take now these operator implementations.
Chúng ta có thể lấy buffer pool đã xây dựng. Chúng ta có thể lấy các page layout đã thiết kế. Giờ chúng ta có thể lấy các cách cài đặt toán tử này.
We're going to mash them all together into a single system and actually start executing queries. So that's what really today is about and the next class will be about.
Chúng ta sẽ trộn tất cả lại thành một hệ thống duy nhất và thực sự bắt đầu thực thi truy vấn. Đó chính là nội dung của hôm nay và của buổi học tiếp theo.
Next week, we'll jump on the query optimizer, and that'll be how to take a SQL query and convert it into a physical plan that we're going to talk about how to execute today.
Tuần sau, chúng ta sẽ chuyển sang query optimizer, tức là cách lấy một truy vấn SQL và chuyển nó thành một physical plan mà hôm nay chúng ta sẽ nói về cách thực thi.
So again, as a reminder, the query plan in a relational database system is going to be a DAG of operators. Ideally, it's a DAG.
Vậy xin nhắc lại, query plan trong một hệ quản trị cơ sở dữ liệu quan hệ sẽ là một DAG gồm các toán tử. Lý tưởng thì nó là một DAG.
Most systems implement a tree, but a tree is a subset of a DAG. The idea still holds. And the idea is that we're going to be moving data up, logically.
Hầu hết các hệ thống cài đặt một cây, nhưng cây là một tập con của DAG. Ý tưởng vẫn đúng. Và ý tưởng là chúng ta sẽ chuyển dữ liệu lên trên, về mặt logic.
And I'll explain what I mean by logically versus physically in a second. We're moving data logically between these different operators until we get to the root of the query plan.
Và lát nữa tôi sẽ giải thích ý tôi về logic so với vật lý. Chúng ta chuyển dữ liệu một cách logic giữa các toán tử khác nhau này cho đến khi tới gốc của query plan.
And that's the final output that we send back to whoever requested the query. Whether it's an internal query, we keep the data for ourselves, or an application, or somebody sitting at a terminal.
Và đó là kết quả cuối cùng mà ta gửi lại cho bên đã yêu cầu truy vấn. Dù đó là truy vấn nội bộ, ta giữ dữ liệu lại cho mình, hoặc một ứng dụng, hoặc ai đó đang ngồi ở một terminal.
The root is always going to be the final output that we send out outside the system. Now we need to slice up this query plan a little bit further and talk about pipelines.
Gốc luôn là đầu ra cuối cùng mà chúng ta gửi ra bên ngoài hệ thống. Bây giờ chúng ta cần chia nhỏ thêm một chút kế hoạch truy vấn này và nói về các đường ống (pipeline).
And pipelines are just these logical boundaries we're going to use to denote that we have a sequence of operators where tuples can flow continuously between the operators, going from the bottom to the top.
Pipeline chỉ là những ranh giới logic mà chúng ta dùng để chỉ ra rằng ta có một chuỗi các toán tử mà các tuple có thể chảy liên tục giữa các toán tử, đi từ dưới lên trên.
And we can keep going across these operators, and we don't have to stop or wait for more results.
Và chúng ta có thể tiếp tục đi qua các toán tử này, mà không phải dừng lại hay chờ thêm kết quả.
And a pipeline breaker will be the operator that's going to be at the root or the top of one of these pipelines that can't finish or can't give any output to whatever's above it until it gets all the input of its children.
Còn pipeline breaker là toán tử nằm ở gốc hay đỉnh của một pipeline như vậy, không thể hoàn thành hay đưa ra bất kỳ đầu ra nào cho toán tử phía trên cho đến khi nó nhận được toàn bộ đầu vào từ các con của nó.
So in my case here, say we're doing a hash join, although in this plan, again, it's just the join symbol.
Trong ví dụ này, giả sử ta đang làm hash join, mặc dù trong kế hoạch này, một lần nữa, chỉ có ký hiệu join.
We're not saying what the actual algorithm is. But say we're doing a hash join. We're going to scan R and build a hash table on that.
Ta không nói thuật toán thực sự là gì. Nhưng giả sử đó là hash join. Ta sẽ quét R và xây dựng một bảng băm từ đó.
Well, that's the pipeline we really only can have. We have the scanning R, populate some hash, the hash table, and then we can't execute anything else until this pipeline finishes.
Đó chính là pipeline mà ta thực sự chỉ có thể có. Ta quét R, điền dữ liệu vào bảng băm, và sau đó không thể thực thi gì khác cho đến khi pipeline này kết thúc.
Because we can't do the join and start probing the hash table until we know that the hash table's been populated. Because we could get false negatives. So you'll see this also in sorting.
Vì ta không thể thực hiện join và bắt đầu dò bảng băm cho đến khi biết bảng băm đã được điền đầy đủ. Vì ta có thể gặp các kết quả âm tính giả. Bạn cũng sẽ thấy điều này trong sắp xếp.
I can't have my sort operator produce any output until I sort my data. Because I can't tell you what the order is going to be until I sorted everything.
Toán tử sort không thể tạo đầu ra nào cho đến khi tôi sắp xếp xong dữ liệu. Vì tôi không thể cho bạn biết thứ tự là gì cho đến khi sắp xếp xong tất cả.
So these pipeline breakers are going to be a way we're going to denote the boundaries of where we can do as much work as we can on single tuples or batches of tuples.
Vì vậy các pipeline breaker sẽ là cách để ta xác định ranh giới của phần mà ta có thể làm nhiều việc nhất có thể trên từng tuple hoặc từng lô tuple.
And we don't have to get more data until we reach one of these pipeline breakers at the top.
Và ta không cần lấy thêm dữ liệu cho đến khi ta chạm tới một trong các pipeline breaker ở phía trên.
The reason why it's called pipeline, because it's the old days in the 70s, was the idea was like, it's so expensive to go get a tuple from disk.
Lý do nó được gọi là pipeline, vì từ thời xưa, những năm 70, ý tưởng là, việc lấy một tuple từ đĩa rất tốn kém.
So one of these bottom scan operators on my tables, I'll get one tuple and I'll write it up as far as I can up into my pipeline.
Vì thế với một trong các toán tử quét ở dưới cùng trên các bảng của tôi, tôi sẽ lấy một tuple và đẩy nó lên xa nhất có thể trong pipeline.
And don't go back and get the next tuple until I reach my pipeline breaker.
Và không quay lại lấy tuple tiếp theo cho đến khi tôi chạm tới pipeline breaker.
I'm going to do as much work as I can with data that I bring into memory as I can, and not have to write things out to disk unnecessarily.
Tôi sẽ làm nhiều việc nhất có thể với dữ liệu đã đưa vào bộ nhớ, và không phải ghi dữ liệu ra đĩa một cách không cần thiết.
So that's the high-level model of what we're dealing with today.
Đó là mô hình ở mức tổng quan của những gì chúng ta bàn hôm nay.
And the reason why I was trying to be careful of saying logically versus physically moving data, because going back here, it's clear from this diagram, it looks like data is being pushed up.
Và lý do tôi cố gắng cẩn thận khi nói về việc di chuyển dữ liệu theo logic so với theo vật lý, là vì quay lại đây, nhìn sơ đồ này thì rõ ràng có vẻ như dữ liệu đang được đẩy lên trên.
But most systems don't do that. Actually, data is actually pulled up physically. So that'll be the processing models. We'll cover that first.
Nhưng hầu hết các hệ thống không làm vậy. Thực tế, về mặt vật lý dữ liệu được kéo lên. Đó sẽ là các mô hình xử lý. Chúng ta sẽ học phần này trước.
Then we'll talk about access methods. What are the actual leaves of the query plan? How are we actually getting data from our tables? Because that's something we haven't really talked about in detail.
Sau đó ta nói về các phương thức truy cập. Các lá thực sự của kế hoạch truy vấn là gì? Thực ra chúng ta lấy dữ liệu từ các bảng bằng cách nào? Vì đó là điều mà chúng ta chưa thực sự nói chi tiết.
Then we'll talk about how we handle modification queries. So insert, update, delete, merge and upserts.
Sau đó chúng ta sẽ nói về cách xử lý các truy vấn sửa đổi dữ liệu. Tức là insert, update, delete, merge và upsert.
And then we'll finish off talking about how we're actually going to evaluate the expressions we have in our where clauses or join clauses, or whatever it is, to actually produce the matches or do filtering, whatever a query wants.
Và cuối cùng, chúng ta sẽ kết thúc bằng việc nói về cách thực sự đánh giá các biểu thức trong mệnh đề where hoặc mệnh đề join, hay bất kể nó là gì, để tạo ra các kết quả khớp hoặc lọc dữ liệu, tùy theo truy vấn cần gì.
Okay? You good? Okay. That's your... All right.
Được chứ? Ổn chứ? Được rồi. Đó là... Được rồi.
So the query processing model is going to determine how the system is going to execute a query plan and move data between these different operators in the plan, moving data from one operator to the next.
Vậy mô hình xử lý truy vấn sẽ quyết định cách hệ thống thực thi một kế hoạch truy vấn và di chuyển dữ liệu giữa các toán tử khác nhau trong kế hoạch, chuyển dữ liệu từ toán tử này sang toán tử tiếp theo.
And just like we saw when we talked about storage models, Between row store versus column store, there's going to be performance tradeoffs and also engineering tradeoffs between these different processing model approaches.
Và giống như chúng ta đã thấy khi nói về các mô hình lưu trữ, giữa row store và column store, sẽ có những đánh đổi về hiệu năng và cả về kỹ thuật giữa các cách tiếp cận mô hình xử lý khác nhau này.
Right? One's going to be better for OLTP. One's going to be better for OLAP.
Đúng không? Một mô hình sẽ tốt hơn cho OLTP. Một mô hình khác sẽ tốt hơn cho OLAP.
And so each processing model is going to be comprised of these two types of communications or execution paths in our query plan.
Và mỗi mô hình xử lý sẽ gồm hai loại giao tiếp hay đường thực thi này trong kế hoạch truy vấn.
One is going to be the control flow, and that's how the database is going to say or to instruct an operator to execute. Right?
Một là luồng điều khiển (control flow), tức là cách cơ sở dữ liệu ra lệnh cho một toán tử thực thi. Đúng không?
How we're encapsulating what the operator code actually is, whether it's a class or a function or whatever, it doesn't matter.
Tức là cách chúng ta đóng gói mã của toán tử, dù là một lớp hay một hàm hay gì đi nữa, điều đó không quan trọng.
But there's something that's saying, and the database is going to say, hey, go run this operator. Do your work.
Nhưng có một thứ nào đó nói rằng, cơ sở dữ liệu sẽ nói: này, hãy chạy toán tử này. Làm việc của bạn đi.
And then the data flow is going to determine how an operator is going to send data from one operator to the next in our query plan.
Còn luồng dữ liệu (data flow) sẽ xác định cách một toán tử gửi dữ liệu từ toán tử này sang toán tử tiếp theo trong kế hoạch truy vấn.
Logically, I'm showing the directed arrows going up from the bottom to the top. It doesn't necessarily have to be that way.
Về mặt logic, tôi vẽ các mũi tên có hướng đi từ dưới lên trên. Không nhất thiết phải như vậy.
And then the thing that we also need to worry about is what is the output of these operators?
Và điều khác chúng ta cũng cần quan tâm là đầu ra của các toán tử này là gì?
We're sort of loosely saying tuples, but we talked about the difference between early materialization and late materialization before.
Chúng ta đang nói khá lỏng lẻo là các tuple, nhưng trước đây chúng ta đã nói về sự khác biệt giữa early materialization và late materialization.
We said sometimes we're in late materialization, maybe you just pass along the bare minimum columns you need, and then a record ID so that if some part of the query plan needs more data, it knows how to go get it.
Chúng ta đã nói rằng đôi khi với late materialization, có thể bạn chỉ truyền đi số cột tối thiểu cần thiết, cùng với một record ID để nếu có phần nào của kế hoạch truy vấn cần thêm dữ liệu, nó biết cách đi lấy.
In early materialization, you basically instantiate the entire tuple. You may throw things away with projections, but that's fine. But basically, you never go back to the tables and get more data.
Với early materialization, về cơ bản bạn tạo ra toàn bộ tuple. Bạn có thể loại bỏ bớt bằng phép chiếu, nhưng không sao. Nhưng về cơ bản, bạn không bao giờ quay lại các bảng để lấy thêm dữ liệu.
Everything you need is being moved up to the query plan. So the three basic approaches are the iterator model, materialization model, and the vectorized or the batch model.
Mọi thứ bạn cần đều được chuyển lên trong kế hoạch truy vấn. Vậy ba cách tiếp cận cơ bản là iterator model, materialization model, và vectorized model hay còn gọi là batch model.
For the last one, the original papers referred to it as the vectorized model.
Với mô hình cuối cùng, các bài báo gốc gọi nó là mô hình vectorized.
Of course, now if you Google vector databases or vectorized databases, You're going to get all the RAG vector index stuff or even the SIMD stuff. But just think of this in batches.
Dĩ nhiên, bây giờ nếu bạn google vector database hay vectorized database, bạn sẽ ra toàn những thứ về chỉ mục vectơ cho RAG, hoặc thậm chí là SIMD. Nhưng hãy chỉ nghĩ về nó theo từng lô (batch).
And the way to think of this, as we see this go along, the iterator model is going to be sending the smallest amount of data from one operator to the next.
Và cách để hình dung, khi chúng ta đi tiếp, là mô hình iterator sẽ gửi lượng dữ liệu nhỏ nhất từ toán tử này sang toán tử tiếp theo.
The materialization model is going to be sending all the data from one operator to the next. And then the batch model is going to be sending a subset.
Mô hình materialization sẽ gửi toàn bộ dữ liệu từ toán tử này sang toán tử tiếp theo. Còn mô hình batch sẽ gửi một tập con.
In terms of how common these are in the real world, most data systems you know about and can think about are going to be using the first approach: Postgres, MySQL, SQLite.
Về mức độ phổ biến của chúng trong thực tế, hầu hết các hệ thống dữ liệu mà bạn biết và nghĩ đến đều dùng cách tiếp cận đầu tiên: Postgres, MySQL, SQLite.
The OLAP systems like the DuckDBs, the Redshifts, the Firebolts, the ClickHouses, those guys are going to be using the bottom one. The middle one is actually very rare.
Các hệ thống OLAP như DuckDB, Redshift, Firebolt, ClickHouse, những hệ thống đó sẽ dùng mô hình ở dưới cùng. Mô hình ở giữa thực ra rất hiếm.
There's maybe five or six systems that actually use it. Two of them I wrote, so there's not that many.
Có lẽ chỉ có năm hay sáu hệ thống thực sự dùng nó. Hai trong số đó do tôi viết, nên cũng không có nhiều lắm.
But we'll go along each of these one by one and we'll see the advantages and disadvantages of all three models as we go along.
Nhưng chúng ta sẽ đi qua từng mô hình một và thấy các ưu điểm và nhược điểm của cả ba mô hình.
So the most basic model, the simplest model, the most common model is the iterator model. This is sometimes called the Volcano model. Because remember that guy that invented or wrote the book on B+trees?
Vậy mô hình cơ bản nhất, đơn giản nhất, và phổ biến nhất là mô hình iterator. Đôi khi nó được gọi là mô hình Volcano. Vì còn nhớ người đã phát minh ra hay viết cuốn sách về B+tree không?
He had a very famous project in the late 80s, early 90s called Volcano that defined not only how you do this iterator model, but also how you parallelize it.
Ông ấy có một dự án rất nổi tiếng vào cuối thập niên 80, đầu thập niên 90 tên là Volcano, định nghĩa không chỉ cách làm mô hình iterator này, mà cả cách song song hóa nó.
We'll see that next class. And also how you build a query optimizer, all in one project. It was very influential. That was also called Volcano. We'll see that next week as well.
Chúng ta sẽ thấy điều đó ở buổi học sau. Và cả cách xây dựng bộ tối ưu truy vấn, tất cả trong một dự án. Nó rất có ảnh hưởng. Bộ tối ưu đó cũng được gọi là Volcano. Tuần sau chúng ta cũng sẽ thấy nó.
But it's not to say that this thing didn't exist before this guy wrote the paper in the late 80s. All the systems in the 70s and 80s were doing this.
Nhưng không có nghĩa là thứ này chưa tồn tại trước khi ông ấy viết bài báo đó vào cuối thập niên 80. Tất cả các hệ thống trong thập niên 70 và 80 đều làm như vậy.
Which is now, You could call it the Volcano model, and someone who's familiar with the research area would know what you're talking about. But the textbook, I think, defines this as the iterator model.
Giờ đây, bạn có thể gọi nó là mô hình Volcano, và ai quen thuộc với lĩnh vực nghiên cứu này sẽ hiểu bạn đang nói về điều gì. Nhưng giáo trình, tôi nghĩ, định nghĩa nó là mô hình iterator.
So in our database system, every query plan operator is going to implement a next function.
Vậy trong hệ cơ sở dữ liệu của chúng ta, mỗi toán tử trong kế hoạch truy vấn sẽ cài đặt một hàm next.
And the contract the next function has is that when one operator calls next on another operator's next function, invokes the next function, that operator's next function either returns back the next tuple up the query plan, or like a null or end of file to indicate there are no more tuples.
Và quy ước của hàm next là khi một toán tử gọi hàm next của toán tử khác, tức là kích hoạt hàm next đó, thì hàm next của toán tử đó hoặc trả về tuple tiếp theo lên phía trên kế hoạch truy vấn, hoặc trả về null hay end of file để cho biết không còn tuple nào nữa.
And at which point the calling operator will never call next again, because you know there's no more data that could arrive or could be used below you at that point in the query plan.
Và lúc đó toán tử gọi sẽ không bao giờ gọi next nữa, vì bạn biết là không còn dữ liệu nào có thể đến hay có thể được dùng bên dưới bạn tại điểm đó trong kế hoạch truy vấn.
There's obviously also an open and close function. Think of it like a constructor-deconstructor in C++. Basically saying, hey, I'm going to tell the operator, hey, I'm going to go read some data.
Dĩ nhiên cũng có hàm open và close. Hãy xem nó như hàm khởi tạo và hàm hủy trong C++. Về cơ bản là ta nói với toán tử rằng, này, tôi sắp đi đọc một ít dữ liệu.
Get ready. Maybe you instantiate an iterator on an index or open a file handle, whatever. And then the close is basically saying, close up whatever, free up whatever ephemeral memory you've allocated for this.
Hãy sẵn sàng. Có thể bạn khởi tạo một iterator trên một chỉ mục hoặc mở một file handle, gì cũng được. Còn close về cơ bản là nói rằng hãy đóng lại mọi thứ, giải phóng bộ nhớ tạm thời mà bạn đã cấp phát cho việc này.
And again, this is also called the pipeline model because it's in the simplest form of this. It's moving things up in a pipeline.
Và một lần nữa, đây cũng được gọi là mô hình đường ống vì ở dạng đơn giản nhất của nó, dữ liệu được chuyển dần lên trên theo một đường ống.
So I normally don't like to show code in class, but for this, it's pretty simple, and I don't think this would be too taxing for you guys. But here's our query plan.
Thường thì tôi không thích đưa mã vào lớp học, nhưng với phần này thì khá đơn giản, và tôi nghĩ nó sẽ không quá nặng với các bạn. Đây là kế hoạch truy vấn của chúng ta.
And you can think of each of these operators are going to have their own operator implementation that is going to have this sort of pseudo Python code here.
Và bạn có thể hình dung mỗi toán tử này sẽ có cách cài đặt toán tử riêng của nó, với kiểu mã giả Python như thế này.
And so think of each of these functions as blocks of code as implementing the next function for the different operators.
Vậy hãy coi mỗi hàm này như các khối mã cài đặt hàm next cho từng toán tử khác nhau.
And to keep this simple, we're going to number them from one starting at the top and going to the bottom.
Và để cho đơn giản, ta sẽ đánh số chúng từ một, bắt đầu từ trên cùng đi xuống dưới.
So the way you start executing a query in the iterator model is you start the database system's Sort of runtime engine, the thing that's actually scheduling queries to execute, will invoke next on the root.
Cách bắt đầu thực thi một truy vấn trong mô hình iterator là hệ quản trị cơ sở dữ liệu khởi động engine thực thi của nó, thành phần thực sự lên lịch thực thi các truy vấn, sẽ gọi next trên nút gốc.
And the next function is the next implementation for that top operator, which is the projection.
Và hàm next ở đây là cài đặt next của toán tử trên cùng, tức là phép chiếu.
It knows that it has some number of children that it can call next on to go get data that it needs. So the top next function calls next on the next guy.
Nó biết mình có một số toán tử con mà nó có thể gọi next để lấy dữ liệu cần thiết. Vậy hàm next trên cùng gọi next của toán tử kế tiếp.
And this is our hash join here. And so we have the left side and the right side. So on the left side, we've got to build the hash table.
Và đây là phép hash join của ta. Ta có nhánh trái và nhánh phải. Ở nhánh trái, ta phải xây dựng bảng băm.
So it's going to call next on its left child. And that gets down now to the scan operator on table R.
Nên nó sẽ gọi next trên con bên trái. Và giờ ta đi xuống toán tử scan trên bảng R.
And now you see inside this, we just have this for loop iterating every single tuple in R. I'm obviously hiding, like, how do we get it from the buffer pool?
Và bây giờ bạn thấy bên trong đây, ta chỉ có vòng lặp for duyệt qua từng tuple trong R.
How do we find the pages? We know how to do that from earlier lectures. But inside that for loop, we just have this emit function.
Dĩ nhiên tôi đang giấu đi việc làm sao lấy nó từ buffer pool, làm sao tìm các trang. Ta đã biết cách làm từ các bài giảng trước. Nhưng bên trong vòng lặp for đó, ta chỉ có hàm emit này.
And that's basically, like, returning the next tuple up to whoever called next on this operator. If you've ever written, like, a Python generator, there's, like, a yield function.
Về cơ bản nó trả tuple tiếp theo lên trên cho bất kỳ ai đã gọi next trên toán tử này. Nếu bạn từng viết một generator trong Python, thì có hàm yield.
So I'm not showing how we're freezing state inside of our for loop. Think of the same sort of way you would do this in Python.
Tôi không trình bày cách ta đóng băng trạng thái bên trong vòng lặp for. Hãy hình dung giống như cách bạn làm trong Python.
And obviously, in C++, it's the more complicated, the more machinery you've got to do. So in operator 2, it's calling next, next, next over the left child.
Còn trong C++ thì dĩ nhiên phức tạp hơn, bạn phải làm nhiều thao tác hỗ trợ hơn. Vậy ở toán tử 2, nó gọi next, next, next trên con bên trái.
And down below, we're just feeding up tuples from table R. And then inside the for loop for the left child in operator 2, I'm building my hash table.
Và ở phía dưới, chúng ta chỉ đang đẩy các tuple từ bảng R lên. Và rồi bên trong vòng lặp for của con bên trái trong toán tử 2, tôi đang xây dựng bảng băm của mình.
And at some point, the operator 3 says, I don't have any more tuples for you. And at which point, operator 2 knows, I never need to call 3 again.
Và đến một lúc nào đó, toán tử 3 nói: tôi không còn tuple nào cho anh nữa. Lúc đó, toán tử 2 biết rằng: mình không bao giờ cần gọi 3 nữa.
So now let me go down my right side of my branch, my tree, And call next on my child, my right child. That has its own for loop that calls next on this child.
Bây giờ tôi đi xuống nhánh bên phải của cây, và gọi next trên con của mình, tức là con bên phải. Nó có vòng lặp for riêng, gọi next trên con của nó.
Now, this is just scanning tuples from S and emitting them up to do the probe inside the hash table.
Ở đây, nó chỉ quét các tuple từ S và đẩy chúng lên để thực hiện bước dò (probe) trong bảng băm.
Right? And then if I have a match when I'm doing my join, then I emit that up into my projection operator, which then can emit that up to whoever called or invoked the query.
Đúng không? Và nếu khi thực hiện phép join mà có một kết quả khớp, thì tôi đẩy nó lên toán tử phép chiếu, rồi toán tử này đẩy nó lên cho bất kỳ ai đã gọi hay kích hoạt truy vấn.
So the pipeline for this is that we have one on the right side here, pipeline 1, because I can call next on my left child in operator 2, and I keep ripping through tuples in R until I don't get any more.
Vậy đường ống ở đây là ta có một đường ở phía bên phải này, đường ống 1, vì tôi có thể gọi next trên con bên trái trong toán tử 2, và cứ thế lấy các tuple trong R cho đến khi không còn nữa.
And at which point, I can then switch over and start executing pipeline 2.
Lúc đó, tôi có thể chuyển sang và bắt đầu thực thi đường ống 2.
And then if you kind of think about it, for one tuple that I pull out of S at 5, I could pass it up to 4, check to see whether the predicate values are true.
Và nếu bạn suy nghĩ một chút, với một tuple tôi lấy ra từ S ở toán tử 5, tôi có thể đưa nó lên 4, kiểm tra xem giá trị của vị từ có đúng không.
If yes, I pass it up to 2, then it checks to see whether, if I probe the hash table, I have a match. If it does, then I pass it up to 1.
Nếu đúng, tôi đưa nó lên 2, rồi nó kiểm tra xem, nếu dò trong bảng băm thì có khớp hay không. Nếu có, thì tôi đưa nó lên 1.
It does projection, and then it produces its final output. So I've sort of pipelined the entire, all the processing for the tuple on this side of the tree.
Nó thực hiện phép chiếu, rồi tạo ra kết quả đầu ra cuối cùng. Như vậy tôi đã xử lý theo kiểu đường ống toàn bộ phần xử lý cho tuple ở phía này của cây.
So the great thing about this model is that it's a pretty simple interface. It's just open, next, close.
Điểm tuyệt vời của mô hình này là giao diện của nó khá đơn giản. Chỉ có open, next, close.
So I'm not even defining how we're actually doing the scan here at these leaf nodes.
Tôi thậm chí không định nghĩa việc quét thực sự được thực hiện như thế nào ở các nút lá này.
In some systems, I may actually want to scan the entire table, materialize it in memory buffer, and just keep track of a cursor.
Ở một số hệ thống, tôi có thể muốn quét toàn bộ bảng, vật lý hóa (materialize) nó trong bộ đệm bộ nhớ, và chỉ theo dõi một con trỏ.
Every time you call next, what's the next tuple I want to hand out? Or you could do it sort of eagerly.
Mỗi lần bạn gọi next, tuple tiếp theo tôi muốn đưa ra là gì? Hoặc bạn có thể làm theo kiểu eager.
Anytime you call next, go get the next tuple on the page, and then if it's that page's, if I've already scanned that page, go get the next page.
Mỗi khi bạn gọi next, đi lấy tuple tiếp theo trên trang, và nếu trang đó, nếu tôi đã quét xong trang đó rồi, thì đi lấy trang tiếp theo.
So I could do everything all at once and just materialize the output and wait to pass it up one by one, or I could do it one at a time.
Vậy tôi có thể làm mọi thứ cùng một lúc và materialize đầu ra, rồi chờ đẩy lên từng tuple một, hoặc tôi có thể làm từng tuple một.
It doesn't matter, and the rest of the implementation of the other operators doesn't have to care.
Điều đó không quan trọng, và phần triển khai còn lại của các toán tử khác không cần quan tâm.
Wait, say it again?
Khoan, bạn nói lại được không?
Yeah, so his statement is, and he's correct, like, well, let's not talk about parallel execution, right?
Vâng, nhận định của bạn ấy là đúng, kiểu như, à, chúng ta đừng bàn về thực thi song song nhé.
Just the notion is that I can't go down the, here, I can't go down the right side of the tree until I finish scanning the left side.
Ý chính là tôi không thể đi xuống, ở đây, tôi không thể đi xuống nhánh bên phải của cây cho đến khi tôi quét xong phía bên trái.
Now, there is a technique called symmetric hash joins where you actually kind of do both, but we don't need, nobody does that.
Tuy nhiên, có một kỹ thuật gọi là symmetric hash join trong đó thực ra bạn làm cả hai bên cùng lúc, nhưng ta không cần, không ai làm vậy cả.
Say it again? Yeah, if you're in a merge sort join, like, you'd have to scan and sort everything.
Bạn nói lại được không? Vâng, nếu là merge sort join thì, bạn sẽ phải quét và sắp xếp toàn bộ.
Well, yeah, so his point is, if I was doing a merge sort join, I could scan and sort both of these guys in parallel, then once they're both done, then combine them.
Ừ, ý bạn ấy là, nếu tôi dùng merge sort join, tôi có thể quét và sắp xếp cả hai bên này song song, rồi khi cả hai xong thì kết hợp chúng lại.
That's next class. Keep it simple, keep it single-threaded. But your intuition is correct.
Đó là bài sau. Cứ giữ cho đơn giản, chạy đơn luồng. Nhưng trực giác của bạn là đúng.
All right, so hopefully this shouldn't be, like, mind-bending for everyone. It's, again, it's pretty basic. You know, this is what BusTub is using, so you'll see this in project three, right?
Được rồi, hy vọng phần này không quá khó hiểu với mọi người. Một lần nữa, nó khá cơ bản. BusTub đang dùng mô hình này, nên bạn sẽ gặp nó trong project ba, nhé?
It's easy to implement. It's easy to debug because I just hook up GDB or pick your favorite debugger and just walk through all the next functions and see how things move around, right?
Nó dễ cài đặt. Nó dễ gỡ lỗi vì tôi chỉ cần gắn GDB hoặc trình gỡ lỗi bạn thích và đi qua từng hàm next để xem dữ liệu di chuyển thế nào, đúng không?
And like I said, it's easy to run as a single-threaded model. Next class, we'll see how to parallelize it, right?
Và như tôi đã nói, nó dễ chạy theo mô hình đơn luồng. Bài sau, ta sẽ xem cách song song hóa nó, nhé?
And the advantage is that I can pipeline a bunch of data all the way through my operators without having to go get the next tuple.
Ưu điểm là tôi có thể đưa một lượng dữ liệu đi xuyên suốt qua các toán tử theo đường ống mà không phải quay lại lấy tuple kế tiếp.
So I want to go as far as I can up until I'm done. And some systems go, take this to, like, the next level.
Nên tôi muốn đi xa nhất có thể cho đến khi xong. Và một số hệ thống còn đẩy điều này lên mức cao hơn.
And I'm just talking about keeping things in, like, you know, our memory.
Tôi mới chỉ nói về việc giữ dữ liệu trong bộ nhớ thôi.
And other systems with this pipelining model, they'll try to keep things in CPU caches, or, like, the Germans try to keep things in CPU registers, because that's the fastest memory you can have all the way up.
Còn các hệ thống khác với mô hình đường ống này, sẽ cố giữ dữ liệu trong cache của CPU, hoặc người Đức thì cố giữ dữ liệu trong thanh ghi của CPU, vì đó là loại bộ nhớ nhanh nhất có thể có.
And that's really fast. But for that, we don't need to worry about that.
Và nó thực sự rất nhanh. Nhưng ta không cần lo về điều đó.
All right, so the iterator model, it's been great for OLTP because it's going to get one tuple at a time, because most of your queries only need a small number of tuples.
Được rồi, vậy mô hình iterator rất tốt cho OLTP vì nó lấy từng tuple một, bởi hầu hết truy vấn của bạn chỉ cần một số ít tuple.
So the overhead of this is actually pretty small, right?
Nên chi phí phát sinh của nó thực ra khá nhỏ, nhé?
Another nice thing about this model, too, is that for, like, limit functions or, sorry, limit operators, like, going back here, like, if I only need the first 10 tuples that come out of this, it's really easy for me to implement that, because I just put the limit above one or, sorry, above two.
Một điểm hay nữa của mô hình này là với các hàm limit, à xin lỗi, các toán tử limit, quay lại đây, nếu tôi chỉ cần 10 tuple đầu tiên từ kết quả này, thì rất dễ cài đặt, vì tôi chỉ đặt limit phía trên toán tử một, à xin lỗi, phía trên toán tử hai.
And I just stop calling next when I have enough tuples for my output, right?
Và tôi chỉ ngừng gọi next khi đã đủ tuple cho đầu ra, nhé?
So I'm sort of blending the control and the data flow all sort of in one channel, but it does make certain things easier than it would be for other things.
Tức là tôi gộp luồng điều khiển và luồng dữ liệu vào một kênh, nhưng điều đó làm một số việc dễ hơn so với các cách khác.
Of course, there's a bunch of downsides. Like, the function calls in next can be expensive, especially if you're trying to rip through a billion tuples.
Dĩ nhiên cũng có nhiều nhược điểm. Chẳng hạn, các lời gọi hàm next có thể tốn kém, đặc biệt khi bạn phải xử lý hàng tỉ tuple.
Like, a function call doesn't seem like that much, but, like, in modern CPUs, that's expensive. And if you do this for a billion tuples, that's going to start to add up.
Một lời gọi hàm nghe có vẻ chẳng đáng là bao, nhưng với CPU hiện đại thì nó tốn kém. Và nếu làm điều này cho hàng tỉ tuple thì chi phí sẽ cộng dồn lại.
All right, so another approach is called the materialization model. And it's basically the same thing, but it's the iterator model.
Được rồi, một cách tiếp cận khác gọi là mô hình materialization. Về cơ bản nó giống vậy, nhưng đây là mô hình iterator.
But instead of passing up one tuple, I'm going to pass up all the tuples from an operator.
Nhưng thay vì đẩy lên từng tuple một, tôi sẽ đẩy lên tất cả các tuple từ một toán tử.
And at which point, I'm basically calling next once, and I never go back and ask for more data, because I know I've gotten everything I could ever want, right?
Và lúc đó, về cơ bản tôi chỉ gọi next một lần, và không bao giờ quay lại để hỏi thêm dữ liệu, vì tôi biết mình đã có mọi thứ mình có thể cần, đúng không?
Of course, the problem with this is, like, if I only need a subset of the data, like, if I have a limit clause, then I don't want to have to pass up a billion tuples between different operators just to get to the limit at the top that says, "Oh, I only need 10 out of these billion," right?
Tất nhiên, vấn đề ở đây là nếu tôi chỉ cần một tập con của dữ liệu, chẳng hạn nếu tôi có mệnh đề limit, thì tôi không muốn phải đẩy một tỉ tuple qua lại giữa các toán tử khác nhau chỉ để đến được limit ở trên cùng, nơi nó nói: "Ồ, tôi chỉ cần 10 trong số một tỉ này thôi", đúng không?
And so we'll see this in a second. You basically do operator fusion, where you can kind of start merging down logic that would normally be up above in the query plan.
Và chúng ta sẽ thấy điều này ngay sau đây. Về cơ bản bạn dùng operator fusion, tức là bạn có thể gộp dần xuống phần logic mà thông thường nằm ở phía trên trong kế hoạch truy vấn.
You start putting it as low as possible or embedding it inside of operators so that I'm not doing much redundant work or passing around data that I end up throwing away or don't need.
Bạn đặt nó càng thấp càng tốt hoặc nhúng nó vào bên trong các toán tử để tôi không phải làm nhiều việc dư thừa hay chuyển đi những dữ liệu mà cuối cùng bị bỏ đi hoặc không cần đến.
And then just like before with the iterator model, right, the data I'm passing could either be the entire tuple, could be late materialization with a record ID and some columns, or a subset of the columns.
Và sau đó, giống như trước đây với mô hình iterator, dữ liệu tôi chuyển đi có thể là toàn bộ tuple, có thể là late materialization với một record ID và một số cột, hoặc một tập con của các cột.
There's tricks of what you want to do, and it's like, try to reduce how much data you're sending up.
Có nhiều mẹo để bạn có thể làm, và ý tưởng là cố giảm lượng dữ liệu bạn gửi lên.
And that matters a lot in the materialization model because, again, I'm sending all the data up. So this technique was developed in the 1990s.
Và điều đó rất quan trọng trong mô hình materialization vì, một lần nữa, tôi đang gửi lên toàn bộ dữ liệu. Kỹ thuật này được phát triển vào những năm 1990.
It was a system called MonetDB that came out of CWI.
Đó là một hệ thống tên MonetDB xuất phát từ CWI.
CWI is basically where DuckDB comes from, or the co-founder of Snowflake did his PhD there, and he invented, basically, they looked at this, saw this was terrible in MonetDB, and then the guy built a better system, but then he went off and co-founded Snowflake that fixed this.
CWI về cơ bản là nơi DuckDB ra đời, hoặc người đồng sáng lập Snowflake đã làm tiến sĩ ở đó, và ông ấy đã phát minh ra, họ nhìn vào đây, thấy điều này tệ trong MonetDB, rồi anh ấy xây dựng một hệ thống tốt hơn, nhưng sau đó anh ấy ra đi và đồng sáng lập Snowflake, nơi đã khắc phục điều này.
DuckDB fixes this too, but we'll see this in a second. So now in our operator implementations, we still have these for loops. We're calling get next. We're calling output on our children.
DuckDB cũng khắc phục điều này, nhưng chúng ta sẽ thấy ngay sau đây. Vậy bây giờ trong các cài đặt toán tử, chúng ta vẫn có các vòng lặp for này. Chúng ta gọi get next. Chúng ta gọi output trên các nút con.
But now in these operator implementations, I don't call a yield or an emit to send things in piecemeal.
Nhưng bây giờ trong các cài đặt toán tử này, tôi không gọi yield hay emit để gửi từng phần một.
I just have this output function that I'm returning, their out buffer, and return back all the tuples to whoever asked me for it.
Tôi chỉ có hàm output này trả về out buffer của chúng, và trả lại tất cả các tuple cho bất kỳ ai đã yêu cầu.
So at the very top of the projection, we call down into this join. Join then calls down to its leaf node.
Vậy ở trên cùng, phép chiếu gọi xuống phép join này. Join sau đó gọi xuống nút lá của nó.
Again, I'm just going to scan through R, just add all the tuples in my output buffer, return that up to the join operator. It then builds the hash table.
Một lần nữa, tôi sẽ quét qua R, thêm tất cả các tuple vào output buffer của mình, và trả kết quả đó lên toán tử join. Sau đó nó xây dựng bảng băm.
Then it calls on the right side down its children, goes down the tree, and then sends back up the tuples in their entirety, computes the join, and produces the final output.
Rồi nó gọi các nút con ở phía bên phải, đi xuống cây, và gửi ngược lên toàn bộ các tuple, tính phép join, và tạo ra đầu ra cuối cùng.
So again, if you think about always thinking in extremes, if table S has a billion tuples, and you look at the side of the pipeline, what am I doing?
Vậy nên, nếu bạn nghĩ về nó, hãy luôn nghĩ ở các trường hợp cực đoan, nếu bảng S có một tỉ tuple, và bạn nhìn vào nhánh bên của đường ống, tôi đang làm gì?
I'm scanning S, putting every single tuple in a buffer, and passing that to the filter operator. But then it's going to look to see which one of those tuples I want to throw away.
Tôi quét S, đưa từng tuple một vào một buffer, rồi chuyển nó cho toán tử lọc. Nhưng sau đó nó sẽ xem trong số các tuple đó, tuple nào tôi muốn loại bỏ.
So again, if you have a billion tuples, but I only need 10 of them, I don't have to pass a billion tuples up just to find out I need 10.
Vậy nên, nếu bạn có một tỉ tuple, mà tôi chỉ cần 10 tuple trong số đó, thì tôi không cần chuyển một tỉ tuple lên chỉ để biết rằng mình cần 10 tuple.
So with operator fusion, the basic idea is that you combine together the operators in the query plan so that as I'm scanning the table, I can then apply my filter and throw things away.
Vậy với operator fusion, ý tưởng cơ bản là bạn kết hợp các toán tử trong kế hoạch truy vấn lại với nhau để trong lúc tôi đang quét bảng, tôi có thể áp dụng bộ lọc và loại bỏ những thứ không cần.
This is basically how you can do the same thing in iterator model or the vectorized model, but it's a big deal in the materialization model just because you're passing along so much data.
Về cơ bản, bạn cũng có thể làm điều tương tự trong mô hình iterator hoặc mô hình vectorized, nhưng nó quan trọng hơn nhiều trong mô hình materialization vì bạn phải chuyển đi một lượng dữ liệu rất lớn.
Seems crazy, but why would you ever want to do this? Let me take a guess. What's that? You said they're stupid? No.
Nghe có vẻ điên rồ, nhưng tại sao bạn lại muốn làm vậy? Để tôi đoán thử. Gì cơ? Bạn nói họ ngốc à? Không.
The guy who invented this is probably, he's dead, but he's one of the best data researchers of all time. So no, he's not stupid.
Người phát minh ra cái này, có lẽ ông ấy mất rồi, nhưng ông là một trong những nhà nghiên cứu dữ liệu giỏi nhất mọi thời đại. Vậy nên không, ông ấy không ngốc.
If you always need a lot of data, or if it's the guy who invented this, it was an OLAP system in MonetDB.
Nếu bạn luôn cần nhiều dữ liệu, hoặc nếu là người đã phát minh ra cái này, thì đó là một hệ thống OLAP trong MonetDB.
They assumed that you would need all the data within a column, but not all the columns.
Họ giả định rằng bạn cần toàn bộ dữ liệu trong một cột, nhưng không cần tất cả các cột.
So they would do projections as operator fusion and throw away a bunch of these columns, and just the columns you don't need, and only pass up the columns you do need.
Nên họ thực hiện phép chiếu như một dạng operator fusion và loại bỏ một loạt cột, tức là những cột bạn không cần, và chỉ chuyển lên những cột bạn cần.
And then now you don't pay the overhead of calling getNext, getNext, getNext just to get all the columns from one operator to the next.
Và như vậy bạn không phải trả chi phí gọi getNext, getNext, getNext chỉ để lấy tất cả các cột từ toán tử này sang toán tử kế tiếp.
The same bit is, if you do operator fusion and you fuse everything together, which you can't, you can fuse things in pipelines, but not always, then it's kind of just one giant program.
Cũng vậy, nếu bạn dùng operator fusion và hợp nhất mọi thứ lại với nhau, điều mà bạn không thể làm được hết, bạn có thể hợp nhất trong các đường ống, nhưng không phải lúc nào cũng được, thì nó trở thành gần như một chương trình khổng lồ duy nhất.
Again, if you have a pipeline, I can't fuse together. For some things, I can fuse together. For some things, I can't. And the Germans are very good at fusing almost all together.
Một lần nữa, nếu bạn có một đường ống, tôi không thể hợp nhất chúng lại. Có thứ tôi hợp nhất được, có thứ thì không. Và người Đức rất giỏi trong việc hợp nhất gần như mọi thứ lại với nhau.
You can fuse everything within a pipeline. But as soon as I have to go cross pipelines, I can't do that. So for OLAP, no one does this, except for, again, a very few systems.
Bạn có thể hợp nhất mọi thứ trong một đường ống. Nhưng ngay khi phải đi xuyên qua nhiều đường ống, tôi không thể làm vậy. Vì vậy với OLAP, không ai làm thế này, trừ một số rất ít hệ thống.
This actually works in OLTP systems, because most of the time, you're not getting a lot of data.
Cách này thực sự hiệu quả trong các hệ thống OLTP, vì phần lớn thời gian, bạn không lấy nhiều dữ liệu.
So the overhead of having to call getNext, getNext, getNext, if you can fuse everything together, because you probably can only have one pipeline, then it collapses down and becomes way more efficient.
Nên chi phí phải gọi getNext, getNext, getNext, nếu bạn có thể hợp nhất mọi thứ lại với nhau, vì có lẽ bạn chỉ có một đường ống, thì nó sẽ thu gọn lại và hiệu quả hơn rất nhiều.
Again, this is for in-memory systems. It matters a lot, because I'm not worried about fetching things from disk. I'm trying to reduce the number of function calls I have to make.
Một lần nữa, điều này dành cho các hệ thống in-memory. Nó rất quan trọng, vì tôi không lo việc lấy dữ liệu từ đĩa. Tôi đang cố giảm số lần gọi hàm mà tôi phải thực hiện.
For OLTP, this makes a huge difference. But in most systems, OLAP systems don't do this. HyPer was an experimental system out of Germany that started implementing with this approach.
Với OLTP, điều này tạo ra sự khác biệt rất lớn. Nhưng trong hầu hết các hệ thống, các hệ thống OLAP không làm điều này. HyPer là một hệ thống thử nghiệm đến từ Đức đã bắt đầu cài đặt theo cách tiếp cận này.
And then in the rewrite, they got rid of it and switched over to the vectorized model. We'll see it in the next slide. Then RavenDB is a document database system.
Và sau đó, khi viết lại, họ bỏ nó đi và chuyển sang mô hình vectorized. Chúng ta sẽ thấy điều đó ở slide tiếp theo. Còn RavenDB là một hệ quản trị cơ sở dữ liệu tài liệu.
It's like MongoDB, but out of Israel. And again, they're doing OLTP. So it makes sense in that environment. It's a simple model, easy to code, easy to debug.
Nó giống MongoDB, nhưng đến từ Israel. Và một lần nữa, họ làm OLTP. Nên nó hợp lý trong môi trường đó. Đây là một mô hình đơn giản, dễ viết code, dễ gỡ lỗi.
And it's not bad until you start getting with really large data set sizes or intermediate results. Then it falls apart.
Và nó không tệ cho đến khi bạn gặp những tập dữ liệu hoặc kết quả trung gian có kích thước rất lớn. Lúc đó nó sụp đổ.
So the best approach for OLAP is going to be the vectorized model, a vectorization model. And that's going to be somewhere in between the iterator model and the materialization model.
Vì vậy cách tiếp cận tốt nhất cho OLAP sẽ là mô hình vectorized, mô hình vector hóa. Nó nằm ở khoảng giữa mô hình iterator và mô hình materialization.
So instead of passing along a single tuple or all the tuples, I pass along a subset or a batch of them. And different systems have different batch sizes. I think DuckDB is like 1024.
Vậy thay vì truyền lên một tuple đơn lẻ hoặc tất cả các tuple, tôi truyền lên một tập con, hay một batch của chúng. Và mỗi hệ thống có kích thước batch khác nhau. Tôi nghĩ DuckDB là khoảng 1024.
It's not going to be in the millions. It's going to be some multiple of a power of 2, like 1024 or 2048, something like that. So you're still going to have a next function.
Nó sẽ không lên đến hàng triệu. Nó sẽ là một bội số của lũy thừa của 2, như 1024 hoặc 2048, đại loại thế. Vậy bạn vẫn sẽ có một hàm next.
But again, instead of passing along a single tuple, you're going to pass along a batch or a vector.
Nhưng một lần nữa, thay vì truyền lên một tuple đơn lẻ, bạn sẽ truyền lên một batch hay một vectơ.
We're not going to go into too much detail for this course. But there's a bunch of logic. There's different ways to handle the case where I know my batch sizes are 2048.
Chúng ta sẽ không đi quá sâu chi tiết trong khóa học này. Nhưng có khá nhiều logic ở đây. Có nhiều cách xử lý trường hợp tôi biết kích thước batch là 2048.
But if I start filtering things out in a batch as I go up, do I wait to get more data down below to fill that batch up back to 2048 or 1024?
Nhưng nếu tôi bắt đầu lọc bớt dữ liệu trong batch khi đi lên trên, thì tôi có chờ lấy thêm dữ liệu từ bên dưới để làm đầy batch trở lại 2048 hoặc 1024 không?
Or do I just pass along whatever I have up the query plan and just let it be sparse as you go up? There's pros and cons to each of the approaches.
Hay tôi cứ truyền lên kế hoạch truy vấn bất cứ thứ gì đang có và để nó thưa dần khi đi lên? Mỗi cách tiếp cận đều có ưu và nhược điểm.
But for this class, we don't need to worry about it. It's more about, how do we keep track of this? How do we actually implement the basic idea of this?
Nhưng với lớp này, chúng ta không cần lo về điều đó. Quan trọng hơn là, làm sao ta theo dõi việc này? Làm sao ta thực sự cài đặt ý tưởng cơ bản này?
So again, going back to our approach here, or our example here, now in our operator functions or our next implementations, now we see that instead of passing along, Instead of calling emit immediately when we have a tuple as our output, we are maintaining an output buffer.
Vậy quay lại cách tiếp cận của chúng ta ở đây, hay ví dụ của chúng ta, giờ trong các hàm toán tử hay các cài đặt next, giờ ta thấy rằng thay vì truyền lên, thay vì gọi emit ngay khi có một tuple làm đầu ra, chúng ta duy trì một output buffer.
But it's not the full. It's not going to be some large chunk of memory that we would have in the materialization model.
Nhưng nó không đầy. Nó sẽ không phải là một vùng nhớ lớn như ta có trong mô hình materialization.
But now we check to see, anytime that our output buffer is full, then we emit it up.
Nhưng giờ ta kiểm tra, bất cứ khi nào output buffer đầy thì ta emit nó lên.
So now, again, down here, I'm going to scan through table R, add a tuple to my output buffer, and then only if the size of the output buffer is greater than n, where n is my batch size or target batch size, then I pass up the tuple batch.
Vậy giờ, ở dưới đây, tôi sẽ quét qua bảng R, thêm một tuple vào output buffer, và chỉ khi kích thước của output buffer lớn hơn n, trong đó n là kích thước batch hay kích thước batch mục tiêu, thì tôi mới truyền batch tuple đó lên.
And I do the same thing down below over here.
Và tôi làm điều tương tự ở phía dưới bên này.
Pretty straightforward. So this idea seems obvious. It's only existed since, like, 2006, 2007.
Khá đơn giản. Ý tưởng này nghe có vẻ hiển nhiên. Nhưng nó chỉ mới xuất hiện từ khoảng năm 2006, 2007.
Even in the OLAP systems that were around in the 90s or 1980s, they were still doing the iterator model. In the case of MonetDB, they were doing the materialization model.
Ngay cả trong các hệ thống OLAP có từ thập niên 90 hay thập niên 1980, người ta vẫn dùng mô hình iterator. Với MonetDB, họ dùng mô hình materialization.
And like I said, the guy that was a co-founder of Snowflake was at CWI, saw MonetDB do the materialization model, thought of a better way of doing it in this batch approach.
Và như tôi đã nói, người đồng sáng lập Snowflake từng ở CWI, đã thấy MonetDB dùng mô hình materialization, và nghĩ ra một cách tốt hơn là cách tiếp cận theo lô này.
And then he did a startup that got bought by Ingres, which was one of the first relational databases. But then they killed off that project.
Sau đó anh ấy lập một công ty khởi nghiệp và được Ingres mua lại, một trong những cơ sở dữ liệu quan hệ đầu tiên. Nhưng rồi họ đã khai tử dự án đó.
And then he went and founded Snowflake with two guys from Oracle. And then Snowflake is the behemoth that it is today.
Và anh ấy đi sáng lập Snowflake cùng hai người từ Oracle. Và Snowflake giờ trở thành gã khổng lồ như ngày nay.
But pretty much every new database system that does OLAP, targeting OLAP workloads in the last 10 years, is going to be doing this approach. And again, the size of the batch will vary.
Nhưng hầu như mọi hệ quản trị cơ sở dữ liệu mới làm OLAP, nhắm tới các khối lượng công việc OLAP trong 10 năm qua, đều dùng cách tiếp cận này. Và kích thước của lô sẽ khác nhau.
1024 is probably, anecdotally, I would say, probably the most common one. There's a bunch of other optimizations that you can do now because you're dealing with batches that we're not going to talk about.
Theo kinh nghiệm thì tôi nghĩ 1024 có lẽ là giá trị phổ biến nhất. Giờ có một loạt tối ưu hóa khác bạn có thể làm vì bạn đang xử lý theo lô, nhưng chúng ta sẽ không nói tới.
But if you know what SIMD is, or Single Instruction Multiple Data items, Now that I'm operating on a column of data that's all the same, that it's going to be lined together in memory, I can shove that in my SIMD registers and do a bunch of processing in parallel.
Nhưng nếu bạn biết SIMD, tức Single Instruction Multiple Data, giờ tôi đang xử lý một cột dữ liệu toàn các giá trị cùng loại, được xếp liền nhau trong bộ nhớ, tôi có thể đưa nó vào các thanh ghi SIMD và xử lý song song hàng loạt.
It's really, really fast. Or I can shove things down to a GPU if I wanted to and do processing in parallel on those batches as well.
Nó cực kỳ nhanh. Hoặc tôi có thể đẩy dữ liệu xuống GPU nếu muốn và xử lý song song trên các lô đó.
So the data system is going to have really efficient implementations for now these operator kernels because there's ripping through these arrays, or these vectors, very efficiently.
Vì vậy hệ thống dữ liệu sẽ có các cài đặt rất hiệu quả cho các operator kernel này, vì chúng quét qua các mảng hay các vectơ này rất hiệu quả.
And you're basically doing the same amount of work for a bunch of tuples all together. And that's the best thing for a modern CPU because I don't have a bunch of branches or conditionals.
Và về cơ bản bạn làm cùng một lượng công việc cho cả loạt tuple cùng lúc. Và đó là điều tốt nhất cho một CPU hiện đại vì tôi không có hàng đống nhánh hay câu lệnh điều kiện.
I'm taking a batch of data. I hang a tight for loop to do whatever processing I want on it and then pass it up.
Tôi lấy một lô dữ liệu. Tôi chạy một vòng lặp for chặt chẽ để thực hiện bất cứ xử lý nào tôi muốn trên nó rồi chuyển lên trên.
And again, there's probably way more systems than I'm showing here. But every system that does OLAP nowadays is going to use this approach.
Và có lẽ có nhiều hệ thống hơn nhiều so với những gì tôi trình bày ở đây. Nhưng mọi hệ thống làm OLAP ngày nay đều dùng cách tiếp cận này.
And even systems that started off with the iterator model abandon it and switch over to the vectorized model.
Và ngay cả những hệ thống ban đầu dùng mô hình iterator cũng bỏ nó và chuyển sang mô hình vectorized.
All right, so we have this iterator model, the materialization model, and the vectorization model.
Được rồi, vậy ta có mô hình iterator, mô hình materialization, và mô hình vectorization.
In all the examples I showed now, we assume that there's this next function that I kick off the query processing for a given query plan by starting at the root, calling next, and then that sort of percolates its way down the tree and data starts moving towards the top.
Trong tất cả các ví dụ tôi đã cho, ta giả định có hàm next này để tôi khởi động việc xử lý truy vấn cho một kế hoạch truy vấn bằng cách bắt đầu từ gốc, gọi next, rồi nó lan dần xuống cây và dữ liệu bắt đầu di chuyển lên phía trên.
So I'm essentially pulling data from the top of the query plan by calling next. I'm sort of pulling it up between the operators up into the query plan to reach the top.
Vậy về bản chất tôi đang kéo dữ liệu từ đỉnh của kế hoạch truy vấn bằng cách gọi next. Tôi kéo dữ liệu đi qua các operator lên trên trong kế hoạch truy vấn để tới đỉnh.
Now, this is how most data systems are going to implement this. So this is sort of independent of whether I'm doing vectorization or iterator model.
Đây là cách hầu hết các hệ thống dữ liệu cài đặt điều này. Điều này khá độc lập với việc tôi dùng vectorization hay mô hình iterator.
In all three of those different processing models, I can have this next function extraction and do that pulling of the data up.
Trong cả ba mô hình xử lý đó, tôi đều có thể có hàm next này và kéo dữ liệu lên trên.
We would call this the plan processing direction. And so the first approach is what I just said, what I've been showing so far, is, again, calling next, pulling data up.
Chúng ta gọi đây là hướng xử lý kế hoạch (plan processing direction). Cách tiếp cận đầu tiên chính là điều tôi vừa nói, điều tôi đã trình bày cho đến giờ, tức là, một lần nữa, gọi next và kéo dữ liệu lên.
But there's a whole other approach where you actually start with the bottom and push data up.
Nhưng còn một cách tiếp cận hoàn toàn khác, trong đó bạn thực sự bắt đầu từ dưới cùng và đẩy dữ liệu lên trên.
And this is why I was trying to be careful saying like, "Oh, when I showed the query plan at the beginning of that lecture, I'm saying, oh, this is logically how data is going to flow."
Và đây là lý do tôi đã cố nói cẩn thận kiểu như: "À, khi tôi cho xem kế hoạch truy vấn ở đầu bài giảng đó, tôi nói rằng về mặt logic thì dữ liệu sẽ chảy như thế này."
But the implementation, the physical implementation, could actually be different. So in the push-based model, it is kind of like, again, thinking at how the diagram is drawn in the logical plan.
Nhưng phần triển khai, tức là triển khai vật lý, thực ra có thể khác. Vì vậy trong mô hình đẩy (push-based), nó giống như là, một lần nữa, hãy nghĩ theo cách sơ đồ được vẽ trong kế hoạch logic.
Like, I'm going to start at the leaf nodes, and then I'm going to do whatever processing I have on them and then move data up.
Tôi sẽ bắt đầu từ các nút lá, rồi thực hiện mọi xử lý cần làm trên chúng và sau đó đẩy dữ liệu lên trên.
So I don't even start at the root and call next down low. There is really no next function.
Vậy là tôi thậm chí không bắt đầu từ gốc rồi gọi next xuống dưới. Thực sự không có hàm next nào cả.
There's some higher-level scheduler that says, "Here's all the operators I need to execute," or "Here are the pipelines I need to execute."
Có một bộ lập lịch (scheduler) ở mức cao hơn nói rằng: "Đây là tất cả các toán tử tôi cần thực thi," hoặc "Đây là các đường ống tôi cần thực thi."
And it knows how to invoke them individually, which may not be sort of the same bottom-to-top order.
Và nó biết cách gọi từng cái riêng lẻ, có thể không theo cùng thứ tự từ dưới lên trên.
It can decide on its own how to reorder the pipelines to execute based on what it thinks is the most efficient strategy.
Nó có thể tự quyết định sắp xếp lại thứ tự thực thi các đường ống dựa trên chiến lược mà nó cho là hiệu quả nhất.
So let me show what I mean by this. So we have these two pipelines here. And, again, each of them will have their own operator implementations.
Để tôi minh họa ý này. Ở đây chúng ta có hai đường ống. Và, một lần nữa, mỗi đường ống sẽ có cách triển khai toán tử riêng.
The first pipeline here, we're just going to be scanning table R. And then we'll build some hash table.
Ở đường ống đầu tiên, chúng ta chỉ quét bảng R. Rồi xây dựng một hash table nào đó.
And then for our second pipeline, we're going to take all the tuples in S and probe whatever hash table got built down below us and then emit them if there's a match.
Còn với đường ống thứ hai, chúng ta lấy tất cả các tuple trong S và dò (probe) hash table đã được xây dựng ở bên dưới rồi phát ra chúng nếu có khớp.
So I'm doing operator fusion here within my pipeline because it's just take one tuple and run it through those individual operators until I produce my output. But there's no direct connection.
Vậy là tôi đang thực hiện operator fusion ở đây trong đường ống vì chỉ cần lấy một tuple và cho chạy qua từng toán tử đó cho đến khi tạo ra kết quả. Nhưng không có kết nối trực tiếp nào.
There's no emit function anymore or next invocation between these different pipelines. I just know I have these two pieces of code. They're going to get data from somewhere. They're going to write data somewhere.
Không còn hàm emit hay lời gọi next nữa giữa các đường ống khác nhau này. Tôi chỉ biết rằng mình có hai đoạn mã này. Chúng sẽ lấy dữ liệu từ đâu đó. Chúng sẽ ghi dữ liệu ra đâu đó.
And then now I have a high-level scheduler that can say, well, here's all the tasks I need to execute for this query.
Và bây giờ tôi có một bộ lập lịch mức cao có thể nói rằng, đây là tất cả các tác vụ tôi cần thực thi cho truy vấn này.
It can then decide the order in which it wants to execute them. But it knows the dependencies of the data between these different pipelines.
Sau đó nó có thể quyết định thứ tự muốn thực thi chúng. Nhưng nó biết các phụ thuộc dữ liệu giữa các đường ống khác nhau này.
So no, it can't run pipeline 2 until pipeline 1 finishes populating the hash table. So it would invoke pipeline 1 first. And then now there'll be part of this task that we're executing here.
Vì vậy không, nó không thể chạy đường ống 2 cho đến khi đường ống 1 hoàn tất việc điền dữ liệu vào hash table. Vậy nên nó sẽ gọi đường ống 1 trước. Và bây giờ sẽ có một phần của tác vụ mà chúng ta đang thực thi ở đây.
There'll be some notion of there's a location of where I can write my data to as I produce my results.
Sẽ có một khái niệm về vị trí mà tôi có thể ghi dữ liệu vào khi tôi tạo ra kết quả.
So as I build my hash table, I could just be allocating pages in my buffer pool and writing my hash table out to there.
Vì vậy khi xây dựng bảng băm, tôi có thể cứ cấp phát các trang trong buffer pool và ghi bảng băm của mình ra đó.
And then when I get full, I can get more pages. And then when my operator 1 is finished, the scheduler says, oh, well, 1 is finished.
Và khi đầy, tôi có thể lấy thêm trang. Và khi toán tử 1 của tôi hoàn thành, bộ lập lịch sẽ nói: à, 1 đã xong.
But I know task 2 was waiting for task 1 to produce results. So I can now schedule to execute task 2.
Nhưng tôi biết tác vụ 2 đang chờ tác vụ 1 tạo ra kết quả. Nên bây giờ tôi có thể lập lịch để thực thi tác vụ 2.
And oh, by the way, task 2, here's the location of the data that the first task wrote to. So if you need to go get its output, here's where to go find it.
Và nhân tiện, tác vụ 2 này, đây là vị trí của dữ liệu mà tác vụ đầu tiên đã ghi vào. Nên nếu cần lấy đầu ra của nó, thì đây là chỗ để tìm.
And then it can do the same thing. It's going to do some output that it has when it does the join and the projection. It writes to that output buffer.
Và rồi nó có thể làm điều tương tự. Nó sẽ tạo ra một số đầu ra khi thực hiện phép join và phép chiếu. Nó ghi vào bộ đệm đầu ra đó.
When the task finishes, the scheduler knows, here's the final location of the data that this second operator produced, or second task produced.
Khi tác vụ kết thúc, bộ lập lịch biết rằng đây là vị trí cuối cùng của dữ liệu mà toán tử thứ hai này tạo ra, hay tác vụ thứ hai tạo ra.
And it knows that's the result that one sends back to whoever asked for the query to execute.
Và nó biết đó là kết quả mà nó gửi trả lại cho bên đã yêu cầu thực thi truy vấn.
So now I'm separating the notion of the control flow and the data flow, meaning the scheduler is saying, execute this task, execute that task.
Vậy là bây giờ tôi tách biệt khái niệm luồng điều khiển và luồng dữ liệu, nghĩa là bộ lập lịch nói: thực thi tác vụ này, thực thi tác vụ kia.
And it's not trying to piggyback off that next function to say, all right, this guy calls this guy, calls this guy. Because that's basically the same scheduling mechanism.
Và nó không cố dựa vào hàm next đó để nói rằng, được rồi, cái này gọi cái này, rồi cái này gọi cái kia. Vì về cơ bản đó cũng là cơ chế lập lịch như nhau.
But it's implicitly happening because of the way the next thing propagates down. But now I have these discrete tasks. And I can have a more global view of what's going on in my query.
Nhưng nó diễn ra ngầm định do cách lời gọi next lan truyền xuống dưới. Còn bây giờ tôi có các tác vụ rời rạc này. Và tôi có thể có cái nhìn toàn cục hơn về những gì đang diễn ra trong truy vấn.
And I can make better decisions how I want to schedule things. Again, the push model, because I would schedule the leaf nodes first.
Và tôi có thể đưa ra quyết định tốt hơn về cách lập lịch. Một lần nữa, đó là mô hình push, vì tôi sẽ lập lịch các nút lá trước.
And they're sort of pushing data up rather than me starting at the top and working my way down and pulling data to the top.
Và chúng đẩy dữ liệu lên trên, thay vì tôi bắt đầu từ trên cùng rồi đi dần xuống và kéo dữ liệu lên đỉnh.
So there's pros and cons to all of these. Again, it's way easier to implement the top to the bottom, the pull-based approach. And most systems are going to do this.
Vậy nên mọi cách đều có ưu và nhược điểm. Một lần nữa, cách từ trên xuống dưới dễ triển khai hơn nhiều, tức là cách tiếp cận dựa trên pull. Và hầu hết các hệ thống sẽ làm theo cách này.
We talked before, it's easy to control the output for my limit clauses. Because I know how to basically stop calling next when I know I have enough data.
Như đã nói trước đây, rất dễ kiểm soát đầu ra cho các mệnh đề limit. Vì về cơ bản tôi biết cách ngừng gọi next khi tôi biết mình đã có đủ dữ liệu.
In the case of the bottom to the top of the push-based model, you can have a better implementation of these operators that can be more careful about where they're putting data.
Còn với mô hình push từ dưới lên trên, bạn có thể có cách triển khai các toán tử này tốt hơn, cẩn thận hơn về nơi chúng đặt dữ liệu.
I'm trying to write it to generic output buffers. But you can start doing things like, within my fused pipelines, put things in registers. And then make sure that the next task is scheduled.
Tôi đang cố ghi nó vào các bộ đệm đầu ra chung. Nhưng bạn có thể bắt đầu làm những việc như, trong các pipeline đã hợp nhất, đặt dữ liệu vào các thanh ghi. Rồi đảm bảo rằng tác vụ tiếp theo được lập lịch.
And then maybe read those registers or something. For some operators, it can be difficult to implement a sort merge join. Because I have to sort two things separately.
Và sau đó có thể đọc các thanh ghi đó hoặc tương tự. Với một số toán tử, việc triển khai sort merge join có thể khó. Vì tôi phải sắp xếp hai thứ một cách riêng biệt.
And then run a task that then does the join. Whereas I could have a single, if I'm doing the pull-based model, I could have a single pipeline.
Và sau đó chạy một tác vụ thực hiện phép join. Trong khi đó, nếu dùng mô hình pull-based, tôi có thể có một đường ống duy nhất.
Assume that the first result was sorted. Then sort the second one. And then just feed things up through that way. But that's a little bit of detail you don't need to worry about.
Giả sử kết quả đầu tiên đã được sắp xếp. Rồi sắp xếp kết quả thứ hai. Và sau đó cứ thế đẩy dữ liệu lên trên theo cách đó. Nhưng đó là một chút chi tiết mà các em không cần bận tâm.
So the top one is way more common. The second one, I would say, is rare-ish. The most famous system that probably started implementing this approach was Hyper from the Germans.
Vậy cách ở trên phổ biến hơn nhiều. Cách thứ hai thì tôi sẽ nói là khá hiếm. Hệ thống nổi tiếng nhất có lẽ đã bắt đầu triển khai cách tiếp cận này là Hyper của những người Đức.
And then this found its way into Umbra, the second version of Hyper. But DuckDB started off actually using the top one. And then they realized that was a mistake.
Và sau đó nó được đưa vào Umbra, phiên bản thứ hai của Hyper. Nhưng thực ra DuckDB ban đầu dùng cách ở trên. Và rồi họ nhận ra đó là một sai lầm.
Or they realized that it was a better idea to do the second one, the bottom one here. So they switched to that. But they originally didn't start this way.
Hoặc họ nhận ra rằng làm theo cách thứ hai sẽ tốt hơn, tức là cách ở dưới này. Nên họ đã chuyển sang cách đó. Nhưng ban đầu họ không bắt đầu như vậy.
ClickHouse does this. CedarDB is a commercial fork of Umbra. Firebolt does this. Snowflake does this. The major OLAP systems all do this approach, in combination with the vectorization model.
ClickHouse làm như vậy. CedarDB là một bản fork thương mại của Umbra. Firebolt làm như vậy. Snowflake cũng làm như vậy. Các hệ thống OLAP lớn đều dùng cách tiếp cận này, kết hợp với mô hình vectorization.
But again, those two design choices are independent. So I could do vectorization model with the pull-based approach. DataFusion does this. A bunch of other systems do this.
Nhưng một lần nữa, hai lựa chọn thiết kế đó độc lập với nhau. Nên tôi có thể dùng mô hình vectorization với cách tiếp cận pull-based. DataFusion làm như vậy. Nhiều hệ thống khác cũng thế.
But the second one has a bunch of advantages, which you maybe don't realize until you actually implement the first one. Yes.
Nhưng cách thứ hai có nhiều ưu điểm, mà có lẽ các em không nhận ra cho đến khi thực sự triển khai cách thứ nhất. Vâng.
This question is, could a database system support different processing models? So not the plan direction, but the processing model. So iteration, materialization, and vectorization. Yes. In theory, yes.
Câu hỏi là: một hệ quản trị cơ sở dữ liệu có thể hỗ trợ nhiều mô hình xử lý khác nhau không? Tức là không phải hướng của kế hoạch, mà là mô hình xử lý. Tức là iteration, materialization và vectorization. Vâng. Về lý thuyết thì có.
Nobody does that. Because now you've got to implement everything, a bunch of different things. And it makes it harder now to potentially compose things together.
Không ai làm vậy cả. Vì khi đó em phải triển khai mọi thứ, rất nhiều thứ khác nhau. Và điều đó khiến việc ghép các thành phần lại với nhau trở nên khó hơn.
I mean, you basically can get the iterator model if you implement vectorization, or actually really all of these, by just having your vector size be one. It's the same thing.
Ý tôi là, về cơ bản em có thể có mô hình iterator nếu triển khai vectorization, hay thực ra là tất cả các mô hình này, chỉ bằng cách đặt kích thước vectơ là một. Nó là như nhau.
It could be less efficient, because you're going to put things in an output buffer, versus just passing along a single tuple. But it's basically the same.
Có thể sẽ kém hiệu quả hơn, vì em phải đưa dữ liệu vào một bộ đệm đầu ra, thay vì chỉ truyền đi một tuple duy nhất. Nhưng về cơ bản thì giống nhau.
But nobody would do that, because now you're maintaining different variations of the same thing. And that becomes an engineering nightmare. It's just not worth it.
Nhưng sẽ không ai làm vậy, vì khi đó em phải duy trì nhiều biến thể khác nhau của cùng một thứ. Và điều đó trở thành cơn ác mộng về kỹ thuật. Không đáng chút nào.
Yes. So his question is, so let's say you go back to iterator model and then the vectorization model. So in this slide here, I'm showing Oracle. I'm showing SQL Server.
Vâng. Vậy câu hỏi của bạn là, giả sử em quay lại mô hình iterator và sau đó là mô hình vectorization. Trên slide này, tôi đang cho thấy Oracle. Tôi đang cho thấy SQL Server.
Let's focus on those two, or DB2 as well. But then when I jump over now to the vectorization model, Oracle's here, DB2's there, and SQL Server's there.
Hãy tập trung vào hai hệ thống đó, hoặc cả DB2 nữa. Nhưng khi tôi chuyển sang mô hình vectorization, thì Oracle ở đây, DB2 ở kia, và SQL Server ở đó.
So in the case of Oracle, we didn't get to talk about this, but they actually run dual engines.
Còn với Oracle, chúng ta chưa có dịp nói về điều này, nhưng thực ra họ chạy hai engine song song.
So they'll have a column store engine and a row store engine, all within the same binary. But they're separate code bases. So technically, they support both.
Họ sẽ có một engine column store và một engine row store, tất cả nằm trong cùng một tệp nhị phân. Nhưng chúng là các codebase riêng biệt. Nên về mặt kỹ thuật, họ hỗ trợ cả hai.
Same with SQL Server. They have a column store engine. So basically, Oracle, SQL Server, DB2, all these systems are from the 1980s or 1970s.
SQL Server cũng vậy. Họ có một engine column store. Về cơ bản, Oracle, SQL Server, DB2, tất cả các hệ thống này đều có từ những năm 1980 hoặc 1970.
And so they're all row-based pull iterator model implementations. And then when column stores and all that stuff became more common, they realized, oh, our implementation is not efficient.
Và vì thế chúng đều là các triển khai theo mô hình pull iterator dựa trên hàng. Rồi khi column store và những thứ đó trở nên phổ biến hơn, họ nhận ra rằng, ồ, cách triển khai của mình không hiệu quả.
Vectorization model's better. Let's ignore the push-based thing. Vectorization model's better, and being a column store is better. So they had separate engines that can use these different approaches.
Mô hình vectorization tốt hơn. Hãy bỏ qua kiểu push-based. Mô hình vectorization tốt hơn, và dùng column store cũng tốt hơn. Nên họ có các engine riêng biệt có thể dùng những cách tiếp cận khác nhau này.
But within one engine itself, it won't switch. That would just be a nightmare to maintain. OK, cool.
Nhưng bên trong một engine thì nó sẽ không chuyển đổi. Làm vậy thì bảo trì sẽ là một cơn ác mộng. Được rồi, tuyệt.
All right, so now we're going to talk about access methods. So now we know conceptually how we're going to move data up from the different operators or move between different operators.
Được rồi, bây giờ chúng ta sẽ nói về các phương thức truy cập (access method). Vậy là giờ chúng ta đã biết về mặt khái niệm cách chuyển dữ liệu lên từ các toán tử khác nhau hoặc chuyển giữa các toán tử khác nhau.
OK, I don't mean to use direction, but I think you understand the different approaches now. All right, so the access method is going to be how you get data from the leaf nodes.
Được rồi, tôi không có ý dùng chữ "hướng", nhưng tôi nghĩ giờ các bạn đã hiểu các cách tiếp cận khác nhau. Được rồi, phương thức truy cập là cách bạn lấy dữ liệu từ các nút lá.
Because in relational algebra, there wasn't a definition. We didn't say, oh, here's a sequential scan operator or here's an index operator.
Bởi vì trong đại số quan hệ, không có định nghĩa nào về điều này. Chúng ta không nói, ồ, đây là toán tử sequential scan hay đây là toán tử index.
It was just like, I do a filter or a projection or a select on a relation, but I didn't define how I'm actually going to get the data.
Nó chỉ là kiểu, tôi thực hiện một phép lọc, phép chiếu hoặc phép chọn trên một quan hệ, nhưng tôi không định nghĩa thực sự sẽ lấy dữ liệu bằng cách nào.
So now in our implementation, we actually have to worry about that. So there's three basic approaches. You either do a sequential scan. That's the fallback approach.
Còn bây giờ trong triển khai của chúng ta, chúng ta thực sự phải bận tâm đến điều đó. Có ba cách tiếp cận cơ bản. Hoặc bạn thực hiện sequential scan. Đó là cách dự phòng.
Like, no matter what, I can always sequential scan the data. But if I have an index, then there's a bunch of ways I could go at this.
Kiểu như, dù thế nào tôi cũng luôn có thể quét tuần tự dữ liệu. Nhưng nếu tôi có một chỉ mục, thì có nhiều cách để tôi tiếp cận.
And I can either choose one index and do an index scan. Or in some systems, I have multiple indexes.
Tôi có thể chọn một chỉ mục và thực hiện index scan. Hoặc ở một số hệ thống, tôi có nhiều chỉ mục.
I can do index scans on all of them or some portion of them and then be clever about how I combine the results and put it together.
Tôi có thể quét chỉ mục trên tất cả hoặc một phần trong số chúng rồi khéo léo kết hợp các kết quả và ghép chúng lại với nhau.
All right, so we're really focusing right now on how do we actually do this bottom part here. And like I said, the sequential scan is the easiest thing to implement.
Được rồi, vậy là hiện giờ chúng ta đang tập trung vào việc thực sự làm phần dưới cùng này như thế nào. Và như tôi đã nói, sequential scan là thứ dễ triển khai nhất.
Assume you're doing a heap-based system.
Giả sử bạn đang làm một hệ thống dựa trên heap.
It's just going to the page directory, getting whatever the first page is, scanning it, finding tuples, and then emitting them or putting them in a buffer or however it's actually implemented.
Nó chỉ việc đến page directory, lấy trang đầu tiên, bất kể đó là trang nào, quét nó, tìm các tuple, rồi phát chúng ra hoặc đưa vào một buffer hoặc tùy cách nó thực sự được triển khai.
It doesn't matter. I'm going page by page and reading data out and shoving it up to the next operator. And basically, the data system or the operator implementation will maintain its own cursor.
Điều đó không quan trọng. Tôi đi từng trang một và đọc dữ liệu ra rồi đẩy nó lên toán tử tiếp theo. Và về cơ bản, hệ thống dữ liệu hay phần triển khai của toán tử sẽ duy trì con trỏ (cursor) riêng của nó.
And it keeps track of where it left off in the last page or the last tuple that it looked at, so that if it calls next again or has to require more results, it knows where to pick it up where it left off before.
Và nó theo dõi vị trí mà nó đã dừng lại ở trang cuối hoặc tuple cuối cùng mà nó đã xem, để nếu nó gọi next lần nữa hoặc cần thêm kết quả, thì nó biết cần tiếp tục từ vị trí mà lần trước nó đã dừng.
And alternatively, you could just materialize everything, scan all the pages, put it in a buffer, and then scan through that or iterate through that and shove tuples up.
Hoặc cách khác, bạn có thể materialize toàn bộ dữ liệu, quét tất cả các trang, đưa vào một buffer, rồi quét hoặc duyệt qua buffer đó và đẩy các tuple lên trên.
But that obviously has problems because if it's a large table, I've got to put it somewhere in memory. And it may not be the most efficient way to do this.
Nhưng cách này rõ ràng có vấn đề, vì nếu bảng lớn thì tôi phải đặt nó ở đâu đó trong bộ nhớ. Và đó có thể không phải là cách hiệu quả nhất.
So again, sequential scan is the fallback choice. It seems like, again, if I have no index, there's no other way to get data, I can always just read the pages one by one.
Vậy nên, sequential scan là lựa chọn dự phòng. Có vẻ như nếu tôi không có chỉ mục, không còn cách nào khác để lấy dữ liệu, thì lúc nào tôi cũng có thể đọc từng trang một.
So this seems like this would be terrible and very inefficient, except that we've already talked about a bunch of different ways to make this go fast.
Nghe có vẻ như cách này sẽ rất tệ và kém hiệu quả, ngoại trừ việc chúng ta đã nói về nhiều cách khác nhau để làm cho nó chạy nhanh.
We've already covered a lot of these things in previous lectures, like data encoding compression. What was that?
Chúng ta đã đề cập nhiều điều trong số này ở các bài giảng trước, như nén và mã hóa dữ liệu. Đó là gì nhỉ?
That was taking data and converting it into a different binary form that exploits repeated values, repeated data, so that when I go fetch a page from disk to do my Scratchless Scan, I'm reading more tuples than I would otherwise if it was uncompressed.
Đó là lấy dữ liệu và chuyển nó sang một dạng nhị phân khác tận dụng các giá trị lặp lại, dữ liệu lặp lại, để khi tôi lấy một trang từ đĩa cho sequential scan của mình, tôi đọc được nhiều tuple hơn so với khi dữ liệu không được nén.
We talked about how to do prefetching or scan shedding. I think we skipped bufferful bypass, basically direct copy things into memory space for a worker. But prefetching was a big deal.
Chúng ta đã nói về prefetching hay scan sharing. Tôi nghĩ chúng ta đã bỏ qua buffer pool bypass, về cơ bản là sao chép trực tiếp vào không gian bộ nhớ của một worker. Nhưng prefetching thì rất quan trọng.
I was like, if I know I'm going to scan the data sequentially, go fetch a bunch of pages ahead of time, bring them in memory, so that when I need them, I don't stall waiting for disk.
Ý là, nếu tôi biết mình sẽ quét dữ liệu tuần tự, thì hãy lấy trước một loạt trang, đưa chúng vào bộ nhớ, để khi cần, tôi không phải dừng chờ đĩa.
They're right there available for me. Task parallelization, multithreading, we'll see that next class.
Chúng đã có sẵn ngay đó cho tôi. Song song hóa tác vụ, đa luồng, chúng ta sẽ thấy ở buổi sau.
Clustering and sorting, again, if I'm doing, I can do binary search over sorted data, or I can do sort-merge joins over sorted data much more efficiently than if it was unsorted.
Về clustering và sắp xếp, nếu tôi đang làm, tôi có thể tìm kiếm nhị phân trên dữ liệu đã sắp xếp, hoặc thực hiện sort-merge join trên dữ liệu đã sắp xếp hiệu quả hơn nhiều so với khi dữ liệu chưa được sắp xếp.
Materialized views, or sorry, name materialization we've already talked about, like passing along the bare minimum data I need. Materialized views and result caching we won't cover this semester.
Materialized view, à xin lỗi, late materialization chúng ta đã nói rồi, tức là chỉ truyền đi lượng dữ liệu tối thiểu mà tôi cần. Materialized view và result caching thì chúng ta sẽ không đề cập trong học kỳ này.
Result caching basically is like, if I execute the same query over and over again, and if the data hasn't changed, why execute the query again?
Result caching về cơ bản là nếu tôi thực thi cùng một truy vấn lặp đi lặp lại, và dữ liệu không thay đổi, thì tại sao phải thực thi lại truy vấn?
Just give you back the last result. That is rare. Most systems don't do that. Materialized views is where the application tells it, hey, I'm going to execute the same query over and over again.
Cứ trả về kết quả lần trước. Điều đó hiếm gặp. Hầu hết các hệ thống không làm vậy. Materialized view là khi ứng dụng nói với hệ thống rằng này, tôi sẽ thực thi cùng một truy vấn lặp đi lặp lại.
And so pre-compute the results and give it back to me, you know, the cache results when I run the same query, or a query that could be answered by the materialized view.
Vì vậy hãy tính trước kết quả và trả lại cho tôi, tức là kết quả được cache khi tôi chạy cùng truy vấn đó, hoặc một truy vấn có thể được trả lời bằng materialized view.
Of course, the challenge is how do you maintain the freshness of that materialized result? The high-end systems can incrementally update the materialized view.
Tất nhiên, thách thức là làm sao duy trì độ mới của kết quả được materialize đó? Các hệ thống cao cấp có thể cập nhật materialized view theo kiểu tăng dần.
Like every single time, if I'm computing the sum of a column, every single time I insert a new tuple, I don't have to scan all the tuples and recompute the sum.
Chẳng hạn mỗi lần, nếu tôi đang tính tổng của một cột, mỗi lần tôi chèn một tuple mới, tôi không phải quét tất cả các tuple và tính lại tổng.
I can just increment or decrement based on what new value gets inserted or updated, right? Postgres can't do that. Postgres can't even do it automatically.
tôi chỉ cần tăng hoặc giảm dựa trên giá trị mới được chèn hoặc cập nhật, đúng không? Postgres không làm được điều đó. Thậm chí Postgres còn không thể tự động làm việc này.
You have to tell it when you want to refresh the materialized view. So we're not going to cover that this semester.
Bạn phải bảo nó khi nào bạn muốn làm mới materialized view. Vì vậy, chúng ta sẽ không đề cập đến phần đó trong học kỳ này.
And admittedly, to do the sophisticated materialized views, that's the part of data systems I know the least about, because it's really tricky. And very few systems do this.
Và phải thừa nhận rằng, với các materialized view phức tạp, đó là phần của hệ thống dữ liệu mà tôi biết ít nhất, vì nó thực sự rất khó. Và rất ít hệ thống làm được điều này.
Data skipping is basically what we'll cover in a second. Data parallelization and vectorization we'll see in the next class.
Data skipping về cơ bản là phần chúng ta sẽ học ngay sau đây. Song song hóa dữ liệu và vector hóa chúng ta sẽ xem ở buổi học tới.
Code specialization and compilation, I'll talk briefly about this at the end of the class here. I'll show what Postgres does.
Chuyên biệt hóa mã và biên dịch, tôi sẽ nói ngắn gọn về phần này ở cuối buổi học hôm nay. Tôi sẽ cho các bạn xem Postgres làm gì.
It's basically saying, well, if I know I'm going to be executing this query, rather than me interpret that and walk through that query plan tree, let me just generate a program that does exactly what the query wants to do, compile that, and that's going to be way faster than interpreting.
Về cơ bản nó nói rằng, nếu tôi biết mình sắp thực thi truy vấn này, thay vì diễn dịch và duyệt qua cây kế hoạch truy vấn đó, hãy sinh ra một chương trình làm đúng những gì truy vấn muốn làm, biên dịch nó, và cách đó sẽ nhanh hơn nhiều so với diễn dịch.
So Postgres will do this for the where clause. They won't do it for the whole thing. The Germans do it for the whole thing. And we'll cover that at the end of this class.
Postgres làm điều này cho mệnh đề where. Họ không làm cho toàn bộ truy vấn. Người Đức thì làm cho toàn bộ. Và chúng ta sẽ nói về điều đó ở cuối buổi học này.
All right, so I'm going to go through data skipping, because, again, this allows us to avoid reading data that we don't actually need if we know we don't need it ahead of time.
Được rồi, bây giờ tôi sẽ đi qua data skipping, bởi vì, một lần nữa, nó cho phép chúng ta tránh đọc dữ liệu mà thực sự không cần, nếu ta biết trước là không cần.
And then we'll cover these other ones in a second. So there's two ways to do data skipping. The first is not that common. It's called approximate queries.
Còn những phần khác chúng ta sẽ học sau. Có hai cách để làm data skipping. Cách đầu tiên không phổ biến lắm. Đó là truy vấn xấp xỉ.
Basically, it says, well, if I don't really need an exact answer, don't read all the data to compute the exact answer.
Về cơ bản, nó nói rằng nếu tôi không thực sự cần câu trả lời chính xác, thì đừng đọc toàn bộ dữ liệu để tính ra kết quả chính xác.
If I want to get the number of visitors on my website for a given month, do I really need to know the exact count of the number of visitors?
Nếu tôi muốn biết số lượt truy cập trang web của mình trong một tháng, liệu tôi có thực sự cần biết con số chính xác về số lượt truy cập không?
If I round it to the nearest thousand, if my website is getting millions of views, that's good enough.
Nếu tôi làm tròn đến hàng nghìn gần nhất, khi trang web có hàng triệu lượt xem, như vậy là đủ tốt.
So in the high-end systems, there are, in addition to all the aggregate functions that we talked about before, like count, min, max, sum, average, there's approximate count, approximate min, approximate max.
Vì vậy, trong các hệ thống cao cấp, có ngoài tất cả các hàm tổng hợp mà chúng ta đã nói trước đây, như count, min, max, sum, average, còn có approximate count, approximate min, approximate max.
They're basically doing sampling. And the better systems can give you sort of statistical guarantees about how accurate the sample is. Because if I really need the full answer, I'll just do a complete scan.
Về cơ bản chúng thực hiện lấy mẫu. Và các hệ thống tốt hơn có thể cho bạn những đảm bảo thống kê về độ chính xác của mẫu. Vì nếu thực sự cần câu trả lời đầy đủ, tôi sẽ quét toàn bộ.
Zone maps is way more common. Most systems do this. Most file formats support this.
Zone map phổ biến hơn nhiều. Hầu hết các hệ thống đều làm vậy. Hầu hết các định dạng tệp đều hỗ trợ.
Basically, it's like a pre-computed aggregation on a column so that, depending on my query, if I know that I don't need, if I can look at the zone map and see that the data that the zone map represents can't be satisfied for my predicate, I don't bother reading it.
Về cơ bản, nó giống như một phép tổng hợp tính trước trên một cột, để tùy vào truy vấn của tôi, nếu tôi biết rằng không cần, nếu tôi có thể nhìn vào zone map và thấy rằng dữ liệu mà zone map đó đại diện không thể thỏa mãn vị từ của tôi, thì tôi không cần đọc nó.
It's like a filter. It can't tell me where the data actually, can't tell me where the data I may want is.
Nó giống như một bộ lọc. Nó không thể cho tôi biết dữ liệu thực sự nằm ở đâu, không cho tôi biết dữ liệu tôi có thể cần nằm ở đâu.
It can tell me where in a block of data we didn't have the data that I'm looking for. And this is super common, and pretty much every system uses this.
Nó chỉ cho tôi biết trong một khối dữ liệu, chỗ nào không có dữ liệu mà tôi đang tìm. Và cách này cực kỳ phổ biến, gần như hệ thống nào cũng dùng.
So say we have a simple column like this, a single column with integer value.
Giả sử ta có một cột đơn giản như thế này, một cột duy nhất chứa giá trị số nguyên.
So my zone map could say, for this set of values, here's the min, here's the max, here's the average, here's all the aggregations I may want to compute on this.
Zone map của tôi có thể ghi, với tập giá trị này, đây là min, đây là max, đây là giá trị trung bình, đây là tất cả các phép tổng hợp mà tôi có thể muốn tính trên đó.
Sometimes you can also use the number of null values, basic statistics. Min, max, and number of null values are the number of distinct values, the most common ones.
Đôi khi bạn cũng có thể dùng số lượng giá trị null, các thống kê cơ bản. Min, max, số lượng giá trị null và số lượng giá trị phân biệt là những thứ phổ biến nhất.
But you can pretty much throw anything in there. And pretty much all the file formats: Parquet, ORC, the Vortex one from last week, that talk.
Nhưng bạn gần như có thể nhét bất cứ thứ gì vào đó. Và gần như mọi định dạng tệp: Parquet, ORC, cái Vortex từ tuần trước, buổi nói chuyện đó.
I think the guy's giving a talk this Wednesday as well. They all support basically the same kind of thing in their file formats.
Tôi nghĩ anh ấy cũng có một buổi nói chuyện vào thứ Tư này. Về cơ bản, tất cả đều hỗ trợ cùng một kiểu như vậy trong định dạng tệp của mình.
So now my query shows up: SELECT * FROM table WHERE value > 600. So say, and I'm only showing five tuples here. Say again, think in large terms. I have a billion tuples.
Giờ truy vấn của tôi xuất hiện: SELECT * FROM table WHERE value > 600. Giả sử, và ở đây tôi chỉ hiển thị năm tuple. Nhắc lại, hãy nghĩ ở quy mô lớn. Tôi có một tỉ tuple.
So I can look in this zone map and say, well, I only want to look for values that are greater than 600.
Vậy tôi có thể nhìn vào zone map này và nói rằng, tôi chỉ muốn tìm các giá trị lớn hơn 600.
So I look in the zone map, and the zone map says, well, my max value in this block of data is 400.
Tôi nhìn vào zone map, và zone map cho biết, giá trị max trong khối dữ liệu này là 400.
So I know there can never be a match for me in this block of data. So I don't even go bother reading it. I read the zone map, and that's smaller.
Vậy tôi biết sẽ không bao giờ có kết quả khớp nào trong khối dữ liệu này. Nên tôi không buồn đọc nó. Tôi đọc zone map, và nó nhỏ hơn.
Yes.
Vâng.
Question is, how do you choose what approach you want to do in terms of going back here? So the first one is lossy, right? So you're going to get wrong results. Is that OK?
Câu hỏi là, làm sao bạn chọn cách tiếp cận mình muốn khi quay lại slide này? Cách đầu tiên là có mất mát, đúng không? Tức là bạn sẽ nhận kết quả sai. Như vậy có chấp nhận được không?
Well, the data system doesn't know. It doesn't know what you care about. It's your company, your organization, your startup, whatever. So maybe for certain queries, that's OK.
Hệ thống dữ liệu không biết. Nó không biết bạn quan tâm điều gì. Đó là công ty của bạn, tổ chức của bạn, startup của bạn, gì cũng được. Nên có thể với một số truy vấn nhất định, điều đó là chấp nhận được.
The data system can't infer that, because that's an externality it can't know about. So you have to say, I want approximate this, approximate that. Right?
Hệ thống dữ liệu không thể suy ra điều đó, vì đó là yếu tố bên ngoài mà nó không thể biết. Nên bạn phải nói rõ, tôi muốn xấp xỉ cái này, xấp xỉ cái kia. Đúng không?
You always do the bottom one, because it's always a huge win.
Cách ở dưới thì lúc nào bạn cũng làm, vì nó luôn mang lại lợi ích rất lớn.
Right? If it's your bank account, do you want to have approximate count on your sum on your balance? No. Right? The data system can't know that. All right. So there's a paper.
Đúng không? Nếu đó là tài khoản ngân hàng của bạn, bạn có muốn số dư của mình được tính tổng bằng một phép đếm xấp xỉ không? Không. Đúng không? Hệ thống dữ liệu không thể biết điều đó. Được rồi. Có một bài báo.
So the Oracle term is called zone maps. Sometimes you see these called SMAs, or Small Materialized Aggregates. And it's a paper from '98. It basically defines it in this way.
Thuật ngữ của Oracle là zone maps. Đôi khi bạn thấy chúng được gọi là SMA, tức Small Materialized Aggregates. Và đó là một bài báo từ năm 98. Về cơ bản nó định nghĩa như vậy.
Again, it seems kind of obvious, but it didn't really come out until the 1990s. And this guy here, Guido, he's a German.
Một lần nữa, có vẻ khá hiển nhiên, nhưng mãi đến thập niên 1990 nó mới xuất hiện. Và ông này, Guido, là người Đức.
So this is the PhD advisor of the number one German that does the Umbra and Hyper stuff that we talk about many times.
Ông là người hướng dẫn tiến sĩ của người Đức số một làm về Umbra và Hyper mà chúng ta đã nhắc đến nhiều lần.
So this is his PhD advisor. So the Germans are ridiculous. All right. So that's pretty much how everything you do with sequential scan.
Đó là người hướng dẫn tiến sĩ của anh ấy. Mấy người Đức này thật quá đáng. Được rồi. Vậy đó gần như là cách mọi thứ bạn làm với quét tuần tự.
We'll talk about compilation or code specialization at the end of the class. So let's talk about index scans. Again, we know what indexes are being used for, right?
Chúng ta sẽ nói về biên dịch hay chuyên biệt hóa mã vào cuối môn học. Bây giờ hãy nói về index scan. Một lần nữa, chúng ta biết index được dùng để làm gì, đúng không?
We saw this before, how to figure out, like, how to use a B+tree or a skip list or whatever the data structure we want to find the tuples that match whatever we want to satisfy in our predicates in our query.
Chúng ta đã thấy điều này trước đây, cách xác định xem làm thế nào để dùng một B+tree hay một skip list hoặc bất kỳ cấu trúc dữ liệu nào để tìm các tuple khớp với những gì chúng ta muốn thỏa mãn trong các predicate của truy vấn.
Now, the challenge is going to be, how do we determine which index to use?
Thách thức ở đây là: làm sao xác định nên dùng index nào?
Like, if I have a bunch of indexes I can use on my tables that are available to me, and my WHERE clause actually references a bunch of columns that are being managed or referenced by a bunch of indexes, which one is going to be the best one for me to use?
Chẳng hạn, nếu tôi có nhiều index có thể dùng trên các bảng của mình, và mệnh đề WHERE của tôi tham chiếu đến nhiều cột đang được quản lý hoặc tham chiếu bởi nhiều index, thì index nào sẽ là tốt nhất để dùng?
That's a hard problem. And that's what we'll cover next week. So for now, we're going to ignore how do we pick what the best index to use is.
Đó là một bài toán khó. Và chúng ta sẽ học nó vào tuần sau. Nên bây giờ, chúng ta sẽ bỏ qua việc chọn index tốt nhất để dùng như thế nào.
So assume somebody, some Oracle has, not Oracle the system, but a company, some oracle has figured out this is the best one to use.
Cứ giả sử có ai đó, một oracle nào đó, không phải Oracle là hệ thống, mà là một "nhà tiên tri", đã xác định được đây là index tốt nhất để dùng.
So now we can talk about how we actually want to go ahead and use it.
Vậy giờ ta có thể bàn về việc thực sự dùng nó như thế nào.
So the way to think of this challenge is like, we're trying to reduce the amount of work we have to do.
Cách nghĩ về thách thức này là chúng ta đang cố giảm lượng công việc phải làm.
And it's going to depend heavily on what the data looks like and what our predicate looks like. So say we have a query here.
Và điều đó phụ thuộc rất nhiều vào dữ liệu trông như thế nào và predicate của chúng ta ra sao. Giả sử chúng ta có một truy vấn thế này.
We want to get all the students that are less than 30 that are in the CS department and come from the US. But I have an index on age and department.
Chúng ta muốn lấy tất cả sinh viên dưới 30 tuổi thuộc khoa CS và đến từ Mỹ. Nhưng tôi có một index trên tuổi và khoa.
So one scenario: there is 99 people under the age of 30, but there's only two people in the CS department.
Một kịch bản: có 99 người dưới 30 tuổi, nhưng chỉ có hai người ở khoa CS.
But the flip side could be there's 99 people in the CS department, but only two of them are under the age of 30. Is that me? Shit, sorry. Yeah. My lawyer.
Còn kịch bản ngược lại có thể là có 99 người ở khoa CS, nhưng chỉ hai người trong số đó dưới 30 tuổi. Là tôi à? Chết, xin lỗi. Vâng. Luật sư của tôi.
All right. Right. So in this case here, it's kind of obvious, right?
Được rồi. Vậy trong trường hợp này khá hiển nhiên, đúng không?
So if I have more students that are in the CS department, but only two people that are under the age of 30, then I want to use that age index, because I can quickly go get those one, two students that are age 30, and then just go check to see whether they are in the CS department or not.
Nếu tôi có nhiều sinh viên hơn ở khoa CS, nhưng chỉ có hai người dưới 30 tuổi, thì tôi muốn dùng index trên tuổi, vì tôi có thể nhanh chóng lấy một, hai sinh viên dưới 30 tuổi đó, rồi chỉ cần kiểm tra xem họ có thuộc khoa CS hay không.
On the flip side, if I have more people that are under the age of 30, I want to use the department one, because that's more selective.
Ngược lại, nếu có nhiều người dưới 30 tuổi hơn, tôi muốn dùng index trên khoa, vì nó có tính chọn lọc cao hơn.
So this is basically what the DBMS is going to try to figure out for us.
Về cơ bản đây là điều mà DBMS sẽ cố xác định giúp chúng ta.
And then once we figure out, this is the index I want to use, based on the API that's available to us that the index exposes, then we just invoke that API in our operator to get the data that we want.
Và khi đã xác định được đây là index tôi muốn dùng, dựa trên API mà index cung cấp cho chúng ta, thì ta chỉ cần gọi API đó trong operator để lấy dữ liệu mình muốn.
Right? In a B+tree, or a skip list, or a trie, I can do range scans. But I can't do that in a hash index.
Đúng không? Với B+tree, skip list hay trie, tôi có thể thực hiện range scan. Nhưng tôi không thể làm vậy với hash index.
So the DBMS also has to figure out, all right, my predicate has an inequality or a less than. So my SQL query has a less than for age, but it equals for department.
Vì vậy DBMS cũng phải xác định, được rồi, predicate của tôi có một bất đẳng thức, tức là nhỏ hơn. Truy vấn SQL của tôi có nhỏ hơn cho tuổi, nhưng bằng cho khoa.
So if I have a hash index on age, I can't use that to satisfy this query. So it'll pick another index.
Nên nếu tôi có hash index trên tuổi, tôi không thể dùng nó để thỏa mãn truy vấn này. Nên nó sẽ chọn một index khác.
And then we just invoke the API to get the data we want out of it.
Và rồi ta chỉ cần gọi API để lấy dữ liệu mình muốn từ đó.
The cool thing is that we may not always have to make a single choice of, What's the one index I want to use out of all my indexes?
Điều hay là không phải lúc nào chúng ta cũng chỉ phải đưa ra một lựa chọn duy nhất: Index duy nhất tôi muốn dùng trong tất cả các index của mình là gì?
Some systems let you use all the indexes, or as many indexes as you want. And then you just do the probes, or do the lookups, on those indexes.
Một số hệ thống cho phép dùng tất cả các chỉ mục, hoặc bao nhiêu chỉ mục tùy ý. Sau đó bạn chỉ cần thực hiện các thao tác dò tìm, hay tra cứu, trên các chỉ mục đó.
You get back the record IDs that match whatever your predicate is.
Bạn nhận về các record ID khớp với vị từ của mình.
And then you just do either a union or an intersection between the results of different indexes to find the tuples that you want. So some systems will call these multi-index scans.
Rồi bạn chỉ cần thực hiện phép hợp hoặc phép giao giữa kết quả của các chỉ mục khác nhau để tìm ra các tuple mà bạn muốn. Một số hệ thống gọi đây là multi-index scan.
Postgres calls this the bitmap scan, because it's going to build a bitmap and then do intersections on the bitmaps. MySQL calls these an index merge. They're all basically doing the same thing.
Postgres gọi đây là bitmap scan, vì nó sẽ xây dựng một bitmap rồi thực hiện phép giao trên các bitmap. MySQL gọi đây là index merge. Về cơ bản tất cả đều làm cùng một việc.
And if the predicates in your WHERE clause across the different indexes are conjunctions, AND clauses, then I just take the intersection of the two sets.
Và nếu các vị từ trong mệnh đề WHERE trên các chỉ mục khác nhau là phép hội, tức các mệnh đề AND, thì tôi lấy giao của hai tập.
Or if I'm doing an OR, a disjunction, then I take the union of two sets. Then I have all the record IDs that match what are the predicates across all my indexes.
Còn nếu là OR, tức phép tuyển, thì tôi lấy hợp của hai tập. Khi đó tôi có tất cả các record ID khớp với các vị từ trên toàn bộ các chỉ mục của mình.
And then I go fetch them from the table to go get, actually, the results I need. So we're going back here to our example again.
Và sau đó tôi lấy chúng từ bảng để có được kết quả thực sự cần. Vậy ta quay lại ví dụ ban nãy.
So we're doing a lookup of all the students that are aged less than 30 in the computer science department in the US.
Ta đang tra cứu tất cả sinh viên dưới 30 tuổi thuộc khoa khoa học máy tính ở Mỹ.
Assuming I have an index on age and department, and they're both equally as good, so I'll do a lookup on the age index to get all the tuples that are less than 30.
Giả sử tôi có chỉ mục trên age và department, và cả hai đều tốt như nhau, thì tôi tra cứu trên chỉ mục age để lấy tất cả các tuple có tuổi dưới 30.
Sorry, tuples where the age is less than 30. And I'll do another probe on the CS department and get all those tuples that are in that department. And then I take their intersection.
Xin lỗi, các tuple mà tuổi nhỏ hơn 30. Và tôi dò thêm một lần trên khoa CS để lấy tất cả các tuple thuộc khoa đó. Rồi tôi lấy giao của chúng.
And then I go get the tuples that match the intersection, or that are still in my intersection result. Then go to see whether their country is US. So visually, this looks like this.
Sau đó tôi lấy các tuple khớp với kết quả giao, hay còn nằm trong kết quả giao của tôi. Rồi kiểm tra xem quốc gia của chúng có phải US không. Trực quan thì nó trông như thế này.
Probe the first index, get all the records that are less than 30. Probe this index, get all the records where the department is computer science.
Dò chỉ mục đầu tiên, lấy tất cả các record dưới 30 tuổi. Dò chỉ mục này, lấy tất cả các record có khoa là khoa học máy tính.
Take the middle part, the region here, the intersection, fetch those records. Then just do an additional lookup to see whether the country is US, because there's no index for me to do that.
Lấy phần ở giữa, vùng giao ở đây, rồi lấy các record đó. Sau đó chỉ cần tra cứu thêm để xem quốc gia có phải US không, vì không có chỉ mục nào để làm việc đó.
Pretty straightforward.
Khá đơn giản.
So we now do selects. We do either index scan, a sequential scan, or a multi-index scan. The basic idea is the same.
Vậy là giờ ta đã xử lý các câu select. Ta dùng index scan, sequential scan, hoặc multi-index scan. Ý tưởng cơ bản đều giống nhau.
Depending on our processing model, we're either batching a bunch of tuples or sending one tuple at a time. It doesn't matter.
Tùy vào mô hình xử lý của ta, ta hoặc gom nhiều tuple thành lô, hoặc gửi từng tuple một. Điều đó không quan trọng.
For tuples that modify the database, insert, update, delete, we're basically going to piggyback off of the basic access methods that we have and all the other operators we have to modify these database so that we don't have to re-implement, like in the case of a delete or an update,
Với các câu lệnh sửa đổi cơ sở dữ liệu như insert, update, delete, về cơ bản ta sẽ tận dụng các phương thức truy cập cơ bản đã có và mọi toán tử khác để sửa đổi cơ sở dữ liệu này để không phải cài đặt lại, chẳng hạn với delete hay update,
we don't have to re-implement scan operators to go find tuples that match our predicates. We just reuse the scans we used for selects.
ta không phải cài đặt lại các toán tử scan để tìm các tuple khớp với vị từ của mình. Ta chỉ cần dùng lại các phép scan đã dùng cho select.
And then now the output of those scan operators are then used to then do whatever the update or delete.
Và đầu ra của các toán tử quét đó sau đó được dùng để thực hiện việc cập nhật hoặc xóa.
For insert, the basic idea is that you decide whether you want to materialize the result as a separate operator or within the insert operator. I'll show that next slide.
Với insert, ý tưởng cơ bản là bạn quyết định xem muốn vật chất hóa kết quả trong một toán tử riêng hay ngay trong toán tử insert. Tôi sẽ cho xem ở slide tiếp theo.
For other operations like upserts, merges, truncates, truncates are easy. You just drop the table and then add it back. Upserts are basically scans followed by updates if there's a match or insert.
Với các thao tác khác như upsert, merge, truncate, thì truncate rất dễ. Bạn chỉ cần xóa bảng rồi thêm lại. Về cơ bản upsert là quét, rồi cập nhật nếu có khớp, hoặc chèn nếu không.
They all basically work the same way.
Về cơ bản tất cả đều hoạt động theo cùng một cách.
So update, delete, we're just going to use all the scan operators, access methods we talked about before, and as they pass up the record IDs, that's what's been used inside of these modifying operators to then change the data as we need.
Vậy với update và delete, ta sẽ dùng tất cả các toán tử quét, các phương thức truy cập đã nói trước đó, và khi chúng chuyển lên các record ID, thì chính các ID đó được dùng bên trong những toán tử sửa đổi này để thay đổi dữ liệu theo nhu cầu.
We've got to be careful, though, to keep track of any tuples that we may see before, because if, we'll see in the next slide, if we start scanning data on an index and we start modifying data and we physically put it somewhere back in the table or an index that the iterator hasn't got to yet, then it comes across it again, and we don't want to have to modify it or delete it multiple times.
Tuy nhiên, ta phải cẩn thận để theo dõi những tuple mà ta có thể đã gặp trước đó, vì nếu ta sẽ thấy ở slide tiếp theo, nếu ta bắt đầu quét dữ liệu trên một chỉ mục và bắt đầu sửa dữ liệu rồi đặt nó về một vị trí vật lý nào đó trong bảng hoặc chỉ mục mà iterator chưa quét tới, thì nó sẽ gặp lại tuple đó lần nữa, và ta không muốn phải sửa hay xóa nó nhiều lần.
For inserts, again, you either materialize the tuple inside of the insert operator itself or you materialize it on the outside, and if you do the last one, then you can do select into, you can do create tables, all the select statements.
Với insert, một lần nữa, bạn có thể vật chất hóa tuple ngay bên trong chính toán tử insert hoặc vật chất hóa ở bên ngoài, và nếu chọn cách sau, thì bạn có thể làm select into, có thể tạo bảng, tất cả các câu lệnh select.
It's easy to compose these things together because the insert operator doesn't know, doesn't care how tuples are coming into it from down below it in the query plan.
Rất dễ ghép các thứ này lại với nhau vì toán tử insert không biết, không quan tâm các tuple đến từ bên dưới nó trong kế hoạch truy vấn bằng cách nào.
It just says, take this and put it into this table. I can do that.
Nó chỉ nói: lấy cái này và đưa vào bảng này. Tôi làm được việc đó.
So, but again, we have that decoupling of the concerns or the logic for populating tuple buffers, then we can have whatever went below us in the query plan generate tuples, the longest in the right form that we expect following our API.
Vậy nên, một lần nữa, ta có sự tách biệt các mối quan tâm hay logic để điền vào các bộ đệm tuple, rồi phần nằm dưới ta trong kế hoạch truy vấn có thể sinh ra tuple, đúng theo dạng mà ta mong đợi, tuân theo API của ta.
The insert operator can insert anything from anywhere. You can do temp tables and everything using this as well. All right, so let's see this problem about updating things multiple times.
Toán tử insert có thể chèn bất cứ thứ gì từ bất cứ đâu. Bạn cũng có thể làm bảng tạm và mọi thứ khác bằng cách này. Được rồi, hãy xem vấn đề cập nhật nhiều lần này.
All right, say we have a table of people and we want to keep track of their salary. And I want to run a query. We're going to update everyone's salary.
Giả sử ta có một bảng người và muốn theo dõi mức lương của họ. Và tôi muốn chạy một truy vấn. Ta sẽ cập nhật lương của mọi người.
I'm going to add $100 bonus or increase their salary $100 and then the end of the year, if they make less than $1,100.
Tôi sẽ cộng thêm khoản thưởng $100 hay tăng lương của họ $100 vào cuối năm, nếu họ kiếm được ít hơn $1,100.
So assuming we're going with the iterator model, going from a pull-based approach from top to the bottom, I start at the top. I'm going to start scanning all the tuples from my child.
Giả sử ta dùng mô hình iterator, theo cách kéo từ trên xuống dưới, tôi bắt đầu từ trên cùng. Tôi sẽ bắt đầu quét tất cả các tuple từ toán tử con.
It goes down below, and now in this second operator down here, Then I'm going to do my index scan and it's going to instantiate an iterator that's going to scan across all the leaf nodes and find tuples and then emit them up to the next operator.
Nó đi xuống dưới, và giờ ở toán tử thứ hai ở dưới này, tôi sẽ thực hiện quét chỉ mục và nó sẽ khởi tạo một iterator để quét qua tất cả các nút lá và tìm các tuple rồi phát chúng lên toán tử tiếp theo.
So the first thing it finds is me and I make $999. So that gets passed up now to the operator above it.
Thứ đầu tiên nó tìm thấy là tôi, và tôi kiếm được $999. Vậy là nó được chuyển lên toán tử phía trên.
We then go inside the for loop, do the update, add $100 to it and then write it back out to the index. Right?
Sau đó ta đi vào vòng lặp for, thực hiện cập nhật, cộng thêm $100 rồi ghi ngược lại vào chỉ mục. Đúng không?
So then, now, we go back down to column next on the child operator again.
Rồi bây giờ, ta lại quay xuống gọi next trên toán tử con một lần nữa.
We scan across even further and then now we come across me again with my updated salary and then now I'm going to update it twice.
Ta quét tiếp xa hơn và lần này lại gặp tôi một lần nữa với mức lương đã cập nhật, và thế là tôi sẽ bị cập nhật hai lần.
That's obviously bad. But what's happening here?
Rõ ràng điều đó là sai. Nhưng chuyện gì đang xảy ra ở đây?
Changing the physical location of data in whatever data structures are being used at the leaf operators, right? I'm moving, you know, my record.
Vị trí vật lý của dữ liệu bị thay đổi trong cấu trúc dữ liệu đang được dùng ở các toán tử lá, đúng không? Tôi đang di chuyển bản ghi của mình.
Andy used to be over here because this is indexed on my salary, but when my salary got updated it got moved to another physical location on the leaf nodes and then the iterator goes along and then it finds it again.
Andy trước đây nằm ở đây vì chỉ mục được xây dựng trên lương của tôi, nhưng khi lương của tôi được cập nhật thì bản ghi bị chuyển sang một vị trí vật lý khác trên các nút lá rồi iterator đi tiếp và tìm thấy nó một lần nữa.
So this is a very famous problem from IBM. It's called the Halloween problem. Next week is Halloween, so I always like to bring this up. Right?
Đây là một vấn đề rất nổi tiếng từ IBM. Nó được gọi là vấn đề Halloween. Tuần sau là Halloween nên tôi luôn thích nhắc đến nó. Đúng không?
So it's an anomaly in a database system implementation that occurs when the physical location of a tuple changes that causes an access method or a scan operator, whether it's an index scan or a sequential scan, to come across or see the same logical tuple multiple times because its physical location has changed.
Đó là một dị thường trong việc hiện thực hệ cơ sở dữ liệu, xảy ra khi vị trí vật lý của một tuple thay đổi, khiến một phương thức truy cập hay một toán tử quét, dù là quét chỉ mục hay quét tuần tự, gặp hoặc nhìn thấy cùng một tuple logic nhiều lần vì vị trí vật lý của nó đã thay đổi.
Like, logically there's only one Andy, you know, in the world or whatever.
Chẳng hạn, về mặt logic chỉ có một Andy trên thế giới này thôi.
There's one logical Andy, but physically in my database, during the execution of this query, it physically moved different locations, so it doesn't know.
Có một Andy logic, nhưng về mặt vật lý trong cơ sở dữ liệu của tôi, trong lúc thực thi truy vấn này, nó đã di chuyển sang các vị trí khác nhau, nên hệ thống không biết.
The simplistic implementation, a naive implementation, wouldn't know that it's seeing the same logical thing. It just sees distinct physical tuples.
Một cách hiện thực đơn giản, ngây thơ, sẽ không biết rằng nó đang thấy cùng một thực thể logic. Nó chỉ thấy các tuple vật lý khác nhau.
So this was discovered by the IBM researchers in the 1970s, 1976, when they were building System R, which is one of the first relational systems ever built.
Vấn đề này được các nhà nghiên cứu của IBM phát hiện vào những năm 1970, năm 1976, khi họ đang xây dựng System R, một trong những hệ quan hệ đầu tiên từng được xây dựng.
Right? It has nothing to do with Halloween. The original use case wasn't Halloween.
Đúng không? Nó chẳng liên quan gì đến Halloween cả. Trường hợp sử dụng ban đầu không phải là Halloween.
They discovered this problem on a Friday, late Friday afternoon, when they were building System R, and they were like, "Oh, this is hard.
Họ phát hiện ra vấn đề này vào một ngày thứ Sáu, chiều thứ Sáu muộn, khi đang xây dựng System R, và họ nói: "Ồ, cái này khó đây.
What do we do?" And they were like, "Oh, I don't know. It's Halloween, let's figure it out on Monday. Let's go out and drink."
Giờ làm sao?" Rồi họ nói: "Ồ, tôi không biết. Halloween rồi, thứ Hai hãy tìm cách giải quyết. Đi uống thôi."
And they just left the problem and they solved it the next week. So it just happened that they discovered this on Halloween and went drinking and didn't solve it that day.
Và họ bỏ vấn đề đó lại rồi giải quyết nó vào tuần sau. Chuyện là họ tình cờ phát hiện ra nó đúng dịp Halloween rồi đi uống và không giải quyết nó trong ngày hôm đó.
That's why it's called the Halloween problem. And there's a Wikipedia article that explicitly, you know, calls this out. So again, the way to handle this is sort of obvious.
Đó là lý do nó được gọi là vấn đề Halloween. Và có một bài viết trên Wikipedia nêu rõ điều này. Vậy nên, cách xử lý vấn đề này khá hiển nhiên.
You want to keep track of, like, have I seen this logical tuple, you know, multiple times, or did I modify this tuple I'm looking at, to know that I don't need to modify it again.
Bạn cần theo dõi xem mình đã thấy tuple logic này nhiều lần chưa, hoặc xem mình đã sửa tuple đang xét chưa, để biết rằng không cần sửa nó lần nữa.
It's sort of obvious how to do this. You have to handle it in project three.
Cách làm điều này khá hiển nhiên. Các em sẽ phải xử lý nó trong project ba.
I'm only bringing this up to say, like, there's a bunch of logic that I'm not really showing here inside of my scan operators, where I'm keeping track of what I actually am modifying.
Thầy chỉ nhắc đến chuyện này để nói rằng có một loạt logic mà thầy không thực sự trình bày ở đây bên trong các toán tử scan của mình, nơi mình theo dõi xem mình thực sự đang sửa những gì.
And the way you keep track of, like, here's the things I modified, is in a separate buffer, or you record in the header of the tuple, like, this thing was modified by me, therefore don't look at it again.
Và cách để theo dõi xem đây là những thứ mình đã sửa là dùng một buffer riêng, hoặc ghi vào header của tuple rằng tuple này đã được mình sửa rồi, vì vậy đừng xét nó lần nữa.
There's a bunch of different ways you can implement this, and you will see this in two weeks when we start to talk about how to handle it.
Có rất nhiều cách khác nhau để cài đặt việc này, và các em sẽ thấy điều đó sau hai tuần nữa, khi chúng ta bắt đầu nói về cách xử lý nó.
All right. So for the end of this class, I want to talk about how we actually handle expressions.
Được rồi. Vậy ở phần cuối của buổi học này, thầy muốn nói về cách chúng ta thực sự xử lý các biểu thức.
So it's sort of obvious we have these WHERE clauses that we want to Evaluate to determine whether tuples match, you know, whether there's a join or a filter or whatever it is.
Rõ ràng là chúng ta có các mệnh đề WHERE mà ta cần đánh giá để xác định các tuple có khớp hay không, tức là liệu có phép join, bộ lọc hay bất cứ thứ gì.
So now we have to talk about how do you actually execute these things. And the way you represent this is just another tree.
Vậy giờ ta phải nói về cách thực thi những thứ này. Và cách biểu diễn chúng cũng chỉ là một cây khác.
So within our query plan tree, each operator could have its own trees that represent the expressions that they're responsible for at that sort of level or that point in the tree.
Như vậy, bên trong cây kế hoạch truy vấn của chúng ta, mỗi toán tử có thể có các cây riêng biểu diễn những biểu thức mà nó chịu trách nhiệm ở cấp độ hay vị trí đó trong cây.
So for our join clause, where R.id equals S.id, and the where clause S.value is greater than 100, well, this is just a conjunction between the join clause on the two tuples, the two tables, and then the evaluation on the value based on whether it's greater than some constant here, right?
Với mệnh đề join của chúng ta, where R.id bằng S.id, và mệnh đề where S.value lớn hơn 100, thì đây chỉ là một phép hội giữa mệnh đề join trên hai tuple, hai bảng, và phép đánh giá trên value dựa vào việc nó có lớn hơn một hằng số nào đó ở đây hay không, đúng không?
So basically, while a query is executing, as you're scanning the data, you have to evaluate this tree to determine whether the predicate matches, or whatever the operator wants to do, whether it satisfies this expression defined in this tree, to determine whether you'd be moving tuples up to the next operator, to the next stage in the query plan.
Về cơ bản, khi một truy vấn đang chạy và ta quét dữ liệu, ta phải đánh giá cây này để xác định xem vị từ có khớp hay không, hoặc bất cứ điều gì toán tử muốn làm, xem nó có thỏa mãn biểu thức được định nghĩa trong cây này hay không, để quyết định có chuyển các tuple lên toán tử tiếp theo hay không, tức là sang giai đoạn kế tiếp trong kế hoạch truy vấn.
So let's look at a similar example like this. So we haven't talked about prepared statements, but think of it like a macro. I can have it declared in SQL.
Hãy xem một ví dụ tương tự như vậy. Chúng ta chưa nói về prepared statement, nhưng hãy hình dung nó như một macro. Tôi có thể khai báo nó trong SQL.
So I have PREPARE xxx AS, then I have my SELECT clause, and now you can see inside this, my SELECT clause, I have WHERE S.value equals dollar sign one, so parameter one plus nine, right?
Tôi viết PREPARE xxx AS, rồi đến mệnh đề SELECT của tôi, và giờ các em thấy bên trong mệnh đề SELECT này, tôi có WHERE S.value bằng dấu đô la một, tức tham số một cộng chín, đúng không?
And so I call PREPARE on my application and I say, hey, I'm going to execute this query a lot, give it a name xxx, and then now when I want to execute it again, instead of calling that entire SELECT query, I can say EXECUTE and treat it like a function, say EXECUTE query xxx and pass in the parameters 999, and that'll get substituted in dollar one up there.
Và tôi gọi PREPARE trong ứng dụng và nói rằng, tôi sẽ thực thi truy vấn này rất nhiều lần, hãy đặt tên là xxx, và giờ khi muốn thực thi lại nó, thay vì gọi cả câu truy vấn SELECT đó, tôi có thể dùng EXECUTE và coi nó như một hàm, tức là EXECUTE truy vấn xxx và truyền vào tham số 999, và giá trị đó sẽ được thay vào $1 ở trên kia.
Some systems would...
Một số hệ thống sẽ...
the basic idea is, like, instead of me having to run the query optimizer every single time I'm going to build this query, I can prepare it ahead of time, cache it, and then reuse the query plan over and over again.
ý tưởng cơ bản là thay vì tôi phải chạy bộ tối ưu hóa truy vấn mỗi lần tôi xây dựng truy vấn này, Tôi có thể chuẩn bị nó trước, lưu vào bộ nhớ đệm, rồi tái sử dụng kế hoạch truy vấn đó lặp đi lặp lại.
Of course there's trade-offs, so whether it's a good idea or not, like, depending on some values I may pass in, because I don't know all the values when I call prepare, some might have one query plan versus another, right?
Dĩ nhiên cũng có đánh đổi, nên liệu đó có phải ý hay hay không, thì còn tùy vào một số giá trị mà tôi có thể truyền vào, vì tôi không biết hết các giá trị khi gọi prepare, nên có thể có giá trị dùng kế hoạch truy vấn này, có giá trị lại dùng kế hoạch khác, đúng không?
There's no free lunch. Sometimes it's a good idea, sometimes it's a bad idea, and different systems do different things.
Không có bữa trưa nào miễn phí. Có lúc đó là ý hay, có lúc đó là ý dở, và mỗi hệ thống làm một kiểu khác nhau.
Postgres will automatically generate these prepare statements for you when you run the same query five times, right? Other systems don't do that.
Postgres sẽ tự động tạo các câu lệnh prepare này cho bạn khi bạn chạy cùng một truy vấn năm lần, đúng không? Các hệ thống khác thì không làm vậy.
All right, so as I'm scanning my data, my operator, I'm going to have this execution context that's going to keep track of, like, what's the tuple I'm looking at, what are the parameters that are passed in when I built this query, and what's the schema of the table I'm looking at.
Được rồi, vậy khi tôi quét dữ liệu, với toán tử của mình, tôi sẽ có một ngữ cảnh thực thi (execution context) để theo dõi tuple mà tôi đang xem là gì, các tham số được truyền vào khi tôi xây dựng truy vấn này là gì, và lược đồ của bảng tôi đang xem là gì.
So now when I evaluate my tree, different operators in my expression tree are going to need different information from the different context, so all that I want to have ahead of time so that I'm not doing these lookups every single time, because I'm trying to rip through this expression tree as fast as possible.
Vậy bây giờ khi tôi đánh giá cây của mình, các toán tử khác nhau trong cây biểu thức sẽ cần những thông tin khác nhau từ các ngữ cảnh khác nhau, nên tôi muốn có sẵn tất cả những thứ đó từ trước để không phải tra cứu mỗi lần, vì tôi đang cố duyệt qua cây biểu thức này nhanh nhất có thể.
Because I'm doing this on a per tuple basis, I have a billion tuples, I got to walk this tree a billion times, and I want this to go as fast as possible.
Vì tôi làm việc này trên từng tuple, có một tỉ tuple, tôi phải duyệt cây này một tỉ lần, và tôi muốn nó chạy nhanh nhất có thể.
So you basically are doing depth first search, right? I'm going to start at the top for depth first traversal, my equal sign here.
Về cơ bản bạn đang thực hiện tìm kiếm theo chiều sâu, đúng không? Tôi sẽ bắt đầu từ trên cùng để duyệt theo chiều sâu, ở dấu bằng này.
I know I want to go down to the left side, so I want to get the value for the attribute s.val.
Tôi biết mình muốn đi xuống phía bên trái, nên tôi muốn lấy giá trị của thuộc tính s.val.
So I again look up in my execution context and say, oh well, I know that I need s .val, my current tuple, and it's at that offset based on the schema, so I can just again extract out the value, a thousand here.
Vậy tôi lại tra trong ngữ cảnh thực thi và nói, à, tôi biết mình cần s.val, của tuple hiện tại, và nó nằm ở vị trí offset đó dựa trên lược đồ, nên tôi chỉ việc trích xuất giá trị ra, ở đây là một nghìn.
Then I traverse down to the next side of the tree and I say, alright, well, this leaf node here, what's parameter $1?
Sau đó tôi đi xuống nhánh tiếp theo của cây và nói, được rồi, nút lá này, tham số $1 là gì?
I look at my execution context, see that I'm being passed in 991 as that parameter, and then I go down to this side here, I just materialize this constant 9, come back up to the addition operator, add these two values together, get a thousand, and then come back to the root and say, does a thousand equal a thousand?
Tôi xem ngữ cảnh thực thi, thấy tham số được truyền vào là 991, rồi tôi đi xuống phía bên này, chỉ cần tạo ra hằng số 9, quay lên toán tử cộng, cộng hai giá trị này lại, được một nghìn, rồi quay về gốc và hỏi, một nghìn có bằng một nghìn không?
If yes, emit true, otherwise emit false. Then whoever invoked this tree to do this evaluation here takes the output and decides, okay, as I'm scanning this data, does the tuple match this predicate?
Nếu có, trả về true, nếu không thì trả về false. Sau đó bất cứ thứ gì đã gọi cây này để thực hiện phép đánh giá này sẽ lấy kết quả đầu ra và quyết định, được rồi, khi tôi quét dữ liệu này, tuple có khớp với vị từ này không?
And the tree tells me whether it does or not.
Và cây sẽ cho tôi biết nó có khớp hay không.
Do you think this is a good idea or a bad idea? It works.
Bạn nghĩ đây là ý hay hay ý dở? Nó chạy được.
It's what, it's good. Why?
Nó là gì, nó tốt. Tại sao?
Alright, you know what, I can't, yeah, I'll take that. Yeah, can we do better? Say compile it? Yes, and we'll see that in a second. Yes?
Được rồi, thôi, tôi không nghe rõ, ừ, tôi chấp nhận câu đó. Ừ, chúng ta có làm tốt hơn được không? Biên dịch nó ư? Đúng, và chúng ta sẽ thấy điều đó ngay sau đây. Bạn nào?
So it's terrible for the CPU, because I just made a big point about how, like, the materialization model was trying to, or the vectorization processing model was trying to remove all the overhead of calling next, next, next, but now, within, you know, even if I'm passing along a batch of tuples to remove those next calls, I got to evaluate that tree, and that's going to have a bunch of indirection for these function, sorry, for these operator pointers, right?
Vì nó rất tệ đối với CPU, vì tôi vừa nhấn mạnh rằng mô hình materialization đang cố gắng, hay đúng hơn là mô hình xử lý vectorization đang cố gắng loại bỏ toàn bộ chi phí của việc gọi next, next, next, nhưng giờ, bên trong, bạn biết đấy, dù tôi có truyền một lô tuple để loại bỏ các lần gọi next đó, tôi vẫn phải đánh giá cái cây đó, và nó sẽ có hàng loạt tầng gián tiếp cho các hàm, xin lỗi, cho các con trỏ toán tử này, đúng không?
And that's going to be really slow.
Và điều đó sẽ chạy rất chậm.
And so what I really want to be able to do is just evaluate the expression directly and not have to traverse the tree, because it's pretty simple when I actually, what we're doing here, right?
Vì vậy điều tôi thực sự muốn là đánh giá trực tiếp biểu thức mà không phải duyệt cây, vì thực ra những gì ta đang làm ở đây khá đơn giản, đúng không?
So my Example where s.value equals one, and I have my tree form of this. Well, that's really just a function called check that returns true if value equals one.
Ví dụ của tôi là s.value bằng một, và tôi có dạng cây của nó. Thực ra đó chỉ là một hàm tên là check trả về true nếu value bằng một.
So if I can avoid that overhead of traversing the tree and just invoke this function, then it'd be way faster.
Nên nếu tôi tránh được chi phí duyệt cây và chỉ cần gọi hàm này, thì sẽ nhanh hơn rất nhiều.
And if I'm running on a batch of tuples, like the vectorization, the vectorized model, I can hope my compiler will automatically auto-vectorize it using SIMD, or if not, I can use intrinsics to write it myself.
Và nếu tôi chạy trên một lô tuple, như trong vectorization, mô hình vectorized, tôi có thể hy vọng trình biên dịch sẽ tự động vector hóa bằng SIMD, hoặc nếu không, tôi có thể dùng intrinsics để tự viết.
But now I can pass along, instead of a single tuple, I can pass a batch of tuples.
Nhưng giờ tôi có thể truyền đi, thay vì một tuple đơn lẻ, một lô tuple.
They're all just checking whether the value equals one, and that's going to go super fast on SIMD instructions.
Tất cả chỉ kiểm tra xem value có bằng một hay không, và điều đó sẽ chạy cực nhanh với các lệnh SIMD.
And then their suggestion was to compile it into machine code, and some systems will compile actually the whole query plan. Systems like Postgres will compile a portion of it.
Và gợi ý của bạn ấy là biên dịch nó thành mã máy, và một số hệ thống thực sự biên dịch toàn bộ kế hoạch truy vấn. Các hệ thống như Postgres thì biên dịch một phần của nó.
So let's do a quick demo of that. I'll turn off the light so you guys can see better.
Vậy hãy làm một demo nhanh về điều đó. Tôi sẽ tắt đèn để các bạn nhìn rõ hơn.
So, all right, so this is gonna run Postgres. Login. So I made a simple table called fake data, with, as you'd expect, fake data, right?
Được rồi, cái này sẽ chạy Postgres. Đăng nhập. Tôi đã tạo một bảng đơn giản tên là fake data, chứa, đúng như bạn nghĩ, dữ liệu giả, đúng không?
And it's just, just, sorry, thank you.
Và nó chỉ là, xin lỗi, cảm ơn.
There we go. Okay, sorry about that. All right, so it's a table with a bunch of fake data, right? There's nothing fancy about it, right? And I think there is 50 million records.
Được rồi. Xin lỗi về chuyện đó. Vậy đây là một bảng chứa một đống dữ liệu giả, đúng không? Không có gì cầu kỳ cả, đúng không? Và tôi nghĩ có 50 triệu bản ghi.
Yeah, okay.
Vâng, được rồi.
So the first thing I'm going to do is I'm going to run this special function in Postgres called pg_prewarm that basically just does a special scan.
Việc đầu tiên tôi sẽ làm là chạy hàm đặc biệt này trong Postgres tên là pg_prewarm về cơ bản chỉ thực hiện một lần quét đặc biệt.
It brings everything from the table into the buffer pool, right? So I'm going to turn off the just-in-time compilation for the WHERE clauses in Postgres.
Nó đưa mọi thứ từ bảng vào buffer pool, đúng không? Tôi sẽ tắt biên dịch just-in-time cho các mệnh đề WHERE trong Postgres.
I'm also going to turn off parallel scans, because we'll cover that next class.
Tôi cũng sẽ tắt quét song song, vì ta sẽ học ở buổi sau.
And then I'm going to run some query that produces I'm going to run some query that does some kind of computation where there's a where clause.
Và sau đó tôi sẽ chạy một truy vấn tạo ra... tôi sẽ chạy một truy vấn nào đó thực hiện một phép tính toán nào đó, trong đó có mệnh đề WHERE.
I'm doing a match, but I don't have an index on this, so I basically have to scan everything to see whether I have a match.
Tôi đang so khớp, nhưng tôi không có chỉ mục trên cột này, nên về cơ bản tôi phải quét toàn bộ để xem có khớp hay không.
So without doing any just-in-time compilation, it's going to take a few seconds. And so, this notice how I put EXPLAIN and then ANALYZE, and then I have my parentheses.
Vậy nếu không dùng biên dịch just-in-time, nó sẽ mất vài giây. Và các bạn để ý là tôi gõ EXPLAIN rồi đến ANALYZE, rồi sau đó là cặp dấu ngoặc đơn.
I want it to give me the explain output. ANALYZE tells it to actually run it and produce the time it takes to actually run it.
Tôi muốn nó cho tôi kết quả explain. ANALYZE bảo nó chạy thật sự câu truy vấn và cho biết thời gian thực tế để chạy nó.
And then BUFFERS just tells me, tells me like, tell me whether you, how many pages you read from the buffer pool versus how many pages you read from disk.
Còn BUFFERS thì cho tôi biết là nó đã đọc bao nhiêu trang từ buffer pool so với bao nhiêu trang đọc từ đĩa.
And so it's just for my own sanity, I'm making sure that everything in this table is in memory.
Đây chỉ là để tôi yên tâm, tôi muốn chắc chắn rằng mọi thứ trong bảng này đều nằm trong bộ nhớ.
So it says shared hit equals whatever, the 200,000 pages, so I know everything's being read from memory. So this query executed in roughly four seconds.
Nó ghi shared hit bằng một con số nào đó, 200.000 trang, nên tôi biết mọi thứ đều được đọc từ bộ nhớ. Truy vấn này chạy mất khoảng bốn giây.
If I run it again, it'll take about the same.
Nếu chạy lại, nó sẽ mất xấp xỉ như vậy.
The planning time is telling you how long it takes in the query optimizer, so it takes about 200 milliseconds, and then the query is always going to take four seconds, right?
Planning time cho biết thời gian nó tốn trong bộ tối ưu hóa truy vấn, khoảng 200 mili giây, còn truy vấn thì lúc nào cũng mất bốn giây, đúng không?
So now if I turn on just-in-time compilation, Postgres added this five or six years ago, so what this is going to do, it's going to take the where clause, generate the instructions in LLVM IR for actually executing exactly that where clause.
Bây giờ nếu tôi bật biên dịch just-in-time, Postgres đã thêm tính năng này cách đây năm sáu năm, thì điều nó sẽ làm là lấy mệnh đề WHERE và sinh ra các lệnh bằng LLVM IR để thực thi đúng mệnh đề WHERE đó.
So instead of having this like traversing the tree, I basically flatten the tree and generate the instructions to do exactly the work that the tree wants to do, right?
Thay vì phải duyệt cây, về cơ bản tôi làm phẳng cây và sinh ra các lệnh để làm đúng công việc mà cây đó muốn thực hiện, đúng không?
And now if I run it, it should be, yeah, there we go. So now it takes 2.7 seconds, right? Whereas before it was taking four seconds, so I've saved about a second.
Giờ nếu tôi chạy, nó sẽ... vâng, được rồi. Giờ nó mất 2,7 giây, đúng không? Trong khi trước đó mất bốn giây, nên tôi đã tiết kiệm được khoảng một giây.
If you notice here, there's this extra output here where it says JIT functions equals four, and then it has the time it takes to do generation, inlining, and the optimization.
Nếu để ý, ở đây có thêm phần kết quả ghi JIT functions bằng bốn, cùng với thời gian để sinh mã, inlining và tối ưu hóa.
So it looks like it added about 381 seconds to do the JIT compilation.
Có vẻ nó tốn thêm khoảng 381 giây để biên dịch JIT.
So it's paying an overhead up front before it executes the query to do this compilation, but in the end it made the query run a lot faster, so it was a good trade-off.
Tức là nó phải trả một khoản chi phí ban đầu trước khi thực thi truy vấn để thực hiện việc biên dịch này, nhưng rốt cuộc truy vấn chạy nhanh hơn nhiều, nên đây là một sự đánh đổi đáng giá.
And Postgres has its own cost model to determine, you know, it knows roughly how long it takes to JIT things.
Và Postgres có mô hình chi phí riêng để xác định, nó biết đại khái mất bao lâu để JIT mọi thứ.
It has an estimate how long it's going to take to execute the query, so they can decide whether to actually JIT things or not, whether it's worth the trade-off to pay that extra cost, right?
Nó có ước lượng về thời gian thực thi truy vấn, nên có thể quyết định có thực sự JIT hay không, xem việc trả thêm chi phí đó có đáng để đánh đổi hay không, đúng không?
But Postgres is a row-based system that's doing a pool-based, sorry, doing an iterated model with a pool-based approach.
Nhưng Postgres là hệ thống hướng hàng, dùng cách tiếp cận dựa trên pull, xin lỗi, dùng mô hình lặp (iterator model) với cách tiếp cận dựa trên pull.
So with JIT compilation on, and I'm not doing parallel execution here but it wouldn't make that big of a difference, Postgres' best effort here can run this query on this data in 2.7 seconds.
Vậy khi bật biên dịch JIT, và ở đây tôi không chạy thực thi song song nhưng điều đó cũng không tạo ra khác biệt quá lớn, nỗ lực tốt nhất của Postgres là chạy truy vấn này trên dữ liệu này trong 2,7 giây.
If we cut over to DuckDB, and it's the same data, actually the same query, just explain and analyze.
Nếu chuyển sang DuckDB, với cùng dữ liệu, thực ra là cùng một truy vấn, chỉ là explain và analyze.
So with DuckDB, DuckDB is not going to do any query compilation, not JIT compilation. It's going to be doing a push-based column store with a vectorization model, right?
Vậy với DuckDB, DuckDB sẽ không biên dịch truy vấn, không có biên dịch JIT. Nó dùng column store theo hướng push-based với mô hình vector hóa, đúng không?
It completes the query in half a second, or sorry, less than a second, right?
Nó hoàn thành truy vấn trong nửa giây, à xin lỗi, chưa đến một giây, đúng không?
So all the extra machinery that Postgres is doing to JIT things, which is not a trivial thing to write, it's in debug, right?
Vậy là toàn bộ cơ chế bổ sung mà Postgres dùng để JIT vốn không hề đơn giản để viết, nó đang ở chế độ debug, đúng không?
That's a major engineering effort to add that, DuckDB still crushes it, right? I'm pretty sure this is, make sure this is single-threaded, right? Single-threaded, right? Less than a second.
Thêm vào đó là một nỗ lực kỹ thuật rất lớn, vậy mà DuckDB vẫn vượt xa, đúng không? Tôi khá chắc là, cần chắc chắn là nó chạy đơn luồng, đúng không? Đơn luồng, đúng không? Chưa đến một giây.
So again there's engineering trade-offs because Postgres is a column, sorry, row store, and it's using the iterator model, you know, it's going to be great for OLTP, not so great for OLAP.
Vậy nên một lần nữa, đây là sự đánh đổi trong kỹ thuật vì Postgres là column, xin lỗi, là row store, và nó dùng mô hình iterator, bạn biết đấy, nên sẽ rất tốt cho OLTP, nhưng không tốt lắm cho OLAP.
But if you design a system specifically for OLAP, you know, you can do way better, and that's what DuckDB does. Fireball, Clickhouse would all have similar results.
Nhưng nếu bạn thiết kế một hệ thống riêng cho OLAP, bạn có thể làm tốt hơn nhiều, và đó là điều DuckDB làm. Fireball, Clickhouse đều sẽ cho kết quả tương tự.
Alright, so quickly to finish up for, there are some additional optimizations we can do in our, in our expression trees other than just compiling it. So you do simple things like constant folding.
Được rồi, để kết thúc nhanh phần này, chúng ta còn một số tối ưu hóa bổ sung có thể làm trên cây biểu thức, ngoài việc chỉ biên dịch nó. Ví dụ những việc đơn giản như constant folding.
If you've ever taken a compiler class, it's, it's all the same tricks, but now we're, you know, it's in the context of databases, so it matters more.
Nếu bạn từng học môn trình biên dịch thì đều là những mẹo giống nhau, nhưng giờ nằm trong ngữ cảnh cơ sở dữ liệu nên nó quan trọng hơn.
Alright, so if I say, if I see that I'm going to be calling the upper function on the string wutang over and over again, you know, if I have a billion tuples, I'm going to call this function a billion times for this constant.
Được rồi, giả sử tôi thấy mình sẽ gọi hàm upper trên chuỗi wutang lặp đi lặp lại, nếu tôi có một tỉ tuple, tôi sẽ gọi hàm này một tỉ lần cho hằng số đó.
So I just say, recognize that, okay, well, I only need to actually execute this once, compute it once, and then inject that as a constant, and I never have to call it again.
Vì vậy tôi chỉ cần nhận ra rằng, thực ra tôi chỉ cần thực thi nó một lần, tính một lần, rồi chèn kết quả vào như một hằng số, và không bao giờ phải gọi lại nữa.
Alright, common subexpression elimination is another simple thing you can do, right?
Được rồi, loại bỏ biểu thức con chung là một việc đơn giản khác bạn có thể làm.
If I see that in my query I have a conjunction that's basically computing the same thing, or sorry, disjunction, computing the same thing, right, this string position on x within a column.
Nếu tôi thấy trong truy vấn có một phép hội về cơ bản đang tính cùng một thứ, à xin lỗi, phép tuyển, đang tính cùng một thứ, đó là vị trí chuỗi của x trong một cột.
Alright, so this whole portion of the subtree over here is the same as this subtree over here, so rather than me executing it over again, over and over again for every single tuple duplicatively, I can recognize that they're actually the same, just rewrite the expression tree to be able to reuse the results of the calculation as it occurs over there.
Được rồi, vậy toàn bộ phần của cây con ở đây giống với cây con ở đây, nên thay vì thực thi lại hết lần này đến lần khác cho từng tuple một cách trùng lặp, tôi có thể nhận ra rằng chúng thực chất giống nhau, rồi viết lại cây biểu thức để tái sử dụng kết quả của phép tính khi nó được thực hiện ở bên kia.
Alright, and the DBMS can do this for you automatically, you don't have to rewrite your SQL.
Được rồi, và DBMS có thể tự động làm việc này cho bạn, bạn không phải viết lại SQL của mình.
Alright, it can try to figure out the best way to actually execute these expressions in the same way it's going to try to figure out the best way to execute your query, and we'll see that next week.
Được rồi, nó có thể cố tìm ra cách tốt nhất để thực thi các biểu thức này giống như cách nó sẽ cố tìm ra cách tốt nhất để thực thi truy vấn của bạn, và chúng ta sẽ xem điều đó vào tuần sau.
Okay, did I say it again?
Ồ, tôi lại nói nữa rồi à?
So his statement is, and he's correct, like if I'm saying like the LLVM is going to do this, GCC is going to do this, Clang is going to do this, why do I still want to do this in my database system even if the compiler is going to do it?
Vậy ý của bạn ấy là, và bạn ấy đúng, kiểu như nếu tôi nói LLVM sẽ làm việc này, GCC sẽ làm việc này, Clang sẽ làm việc này, thì tại sao tôi vẫn muốn làm việc này trong hệ quản trị cơ sở dữ liệu dù trình biên dịch sẽ làm rồi?
So in case of Postgres, they didn't... the JIT thing was added six years ago, and not every query is going to get the JIT capabilities, so you still don't want to do this.
Với Postgres thì họ không... phần JIT được thêm vào cách đây sáu năm, và không phải truy vấn nào cũng có khả năng JIT, nên bạn vẫn cần làm việc này.
There are some systems where they try to use a compiler for everything.
Có một số hệ thống cố dùng trình biên dịch cho mọi thứ.
There's an experimental system from the Germans where they will use a compiler, like a classical compiler, to optimize the query plan itself, and also, you know, optimize all the expressions as well.
Có một hệ thống thử nghiệm của những người Đức trong đó họ dùng một trình biên dịch, một trình biên dịch cổ điển, để tối ưu chính kế hoạch truy vấn, và đồng thời cũng tối ưu tất cả các biểu thức.
You do all at once.
Bạn làm tất cả trong một lần.
The, I don't want to say the big Germans, but the HyPer Germans, the Umbra Germans, they will do this as well, but then the LLVM will do its own sort of passive optimization as well.
Tôi không muốn nói là những người Đức lớn, nhưng những người Đức của HyPer, của Umbra, họ cũng làm vậy, nhưng sau đó LLVM vẫn sẽ tự thực hiện một số tối ưu hóa riêng của nó.
The reason why they do this separately is because the way they do compilation is they do it in two stages.
Lý do họ làm riêng như vậy là vì cách họ biên dịch gồm hai giai đoạn.
So they'll take your query plan, generate assembly, so they generate x86 assembly, run that in an assembler, that's super fast to generate, run that, and then in the background they invoke LLVM to start compiling your query on that assembly.
Họ lấy kế hoạch truy vấn của bạn, sinh ra mã assembly, cụ thể là mã assembly x86, chạy nó trong một trình hợp dịch, việc sinh ra này cực nhanh, rồi chạy, và trong nền họ gọi LLVM để bắt đầu biên dịch truy vấn của bạn từ mã assembly đó.
And then when, if the compilation finishes before the query finishes, then they slide in the compiled shared object to replace that.
Và khi quá trình biên dịch xong trước khi truy vấn kết thúc, thì họ chèn shared object đã biên dịch vào để thay thế.
So in the assembled version, the assembled version, if you want that to run fast, you still have to do this, but doing this is not, it's not, it's not hard to figure this out.
Vậy với phiên bản assembly, phiên bản được hợp dịch, nếu muốn nó chạy nhanh thì bạn vẫn phải làm việc này, nhưng làm việc này không khó, không khó để tìm ra.
All right, so the, the, sorry, I was making sure I was still recording.
Được rồi, xin lỗi, tôi đang kiểm tra xem mình vẫn đang ghi hình.
All right, so I hope I conveyed today that like the same query, like the same SQL query, can be executed a bunch of different ways, whether it's index scans or sequential scans, using top-down versus bottom-up, right?
Được rồi, tôi hy vọng hôm nay tôi đã truyền đạt rằng cùng một truy vấn, cùng một truy vấn SQL, có thể được thực thi theo rất nhiều cách khác nhau, dù là index scan hay sequential scan, dùng top-down hay bottom-up, đúng không?
And different data centers do different things, and depending on what your workload is and the environment is that you're trying to target, you're going to choose one versus another.
Và các trung tâm dữ liệu khác nhau làm những việc khác nhau, và tùy vào khối lượng công việc của bạn và môi trường mà bạn nhắm tới, bạn sẽ chọn cái này thay vì cái kia.
In general, for OLAP you want to do a, definitely do the vectorization model, and then depending on your engineering tolerance, you could do a push-based model versus a pull-based model, right?
Nhìn chung, với OLAP bạn chắc chắn nên dùng mô hình vectorization, và sau đó tùy vào mức chịu đựng về kỹ thuật của bạn, bạn có thể dùng mô hình push-based hoặc mô hình pull-based, đúng không?
I can't say definitively there's not one better than another, because there's a bunch of trade-offs for all of them. For OLTP, you want to use index scans as much as possible.
Tôi không thể khẳng định cái nào tốt hơn hẳn cái nào, vì tất cả đều có nhiều đánh đổi. Với OLTP, bạn nên dùng index scan càng nhiều càng tốt.
So therefore, if you know you're not going to read a lot of data and everything's going to be in memory, then materialization model probably is going to be the better way to go, right?
Vì vậy, nếu các em biết là mình sẽ không đọc nhiều dữ liệu và mọi thứ sẽ nằm trong bộ nhớ, thì mô hình materialization có lẽ sẽ là cách tốt hơn, đúng không?
The expression trees are a nice abstraction for the, for to represent expressions, and as I said, they're good because they work, but there's ways to make those go faster.
Cây biểu thức là một abstraction rất hay để biểu diễn các biểu thức, và như tôi đã nói, chúng tốt vì chúng hoạt động được, nhưng vẫn có cách để làm cho chúng chạy nhanh hơn.
Okay. All right, so this is all single-threaded execution.
Được rồi. Vậy đây đều là thực thi đơn luồng.
Next class we'll say, how do we take the same things we talked about today and now add multiple workers, and how do we combine them, results, produce the final result?
Buổi học tới chúng ta sẽ xem, làm thế nào để lấy những thứ đã nói hôm nay rồi thêm vào nhiều worker, và làm thế nào để kết hợp các kết quả của chúng thành kết quả cuối cùng?
Okay. All right, hit it.
Được rồi. Nào, bắt đầu thôi.
Đă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.