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ả.
All right, then round of applause for DJ Cash. Glad you made it a little late. Yeah, I was busy getting money.
Được rồi, một tràng pháo tay cho DJ Cash nào. Mừng là bạn cũng đến, dù hơi muộn. Ừ, tôi bận kiếm tiền.
Again, like, yes, your money. I understand you want money a lot, but, like, focus on databases, focus on your DJ skills, not just, like, trying to raise money.
Lại nữa, ý tôi là, đúng, tiền của các bạn. Tôi hiểu là các bạn rất muốn có tiền, nhưng hãy tập trung vào cơ sở dữ liệu, tập trung vào kỹ năng DJ của bạn, đừng chỉ cố gây quỹ.
All right. We have a lot to cover, so I want to get through everything.
Được rồi. Chúng ta có rất nhiều nội dung, nên tôi muốn đi hết tất cả.
So today, again, before we jump into the course material, a reminder that homework two and project one are out, and they're both going to be due in the coming weeks.
Hôm nay, trước khi vào nội dung môn học, xin nhắc là bài tập về nhà 2 và dự án 1 đã được đăng, và cả hai sẽ đến hạn trong vài tuần tới.
So homework two will be due this upcoming Sunday. I'm trying to light, sorry.
Bài tập về nhà 2 sẽ đến hạn vào Chủ nhật này. Tôi đang cố làm nhẹ, xin lỗi.
Yeah, homework two will be due this Sunday coming up, and then project one will be due the following week. Those days don't match up. 21st, 29th. Whatever the Sundays are, go by the Sundays.
Vâng, bài tập về nhà 2 đến hạn vào Chủ nhật sắp tới, còn dự án 1 sẽ đến hạn vào tuần sau đó. Những ngày này không khớp nhau. Ngày 21, ngày 29. Dù ngày nào, cứ tính theo các ngày Chủ nhật.
The recitation for project one will be tomorrow night over Zoom. Go check on Piazza. And again, this will be a recorded session over Zoom.
Buổi thảo luận về dự án 1 sẽ diễn ra vào tối mai qua Zoom. Hãy xem trên Piazza. Và đây sẽ là buổi được ghi hình qua Zoom.
But if you have questions and you want live answers, we encourage you to join and ask them.
Nhưng nếu bạn có câu hỏi và muốn được trả lời trực tiếp, chúng tôi khuyến khích bạn tham gia và hỏi.
And again, this is not, like, you shouldn't ask basic things like, you know, how do I compile my C++ code?
Và lưu ý, bạn không nên hỏi những điều cơ bản như, kiểu làm sao để biên dịch code C++ của tôi?
It should be like, I've started the project and I want to understand a bit more about what this component means, or what this file means, what this class means.
Câu hỏi nên kiểu như: tôi đã bắt đầu dự án và muốn hiểu rõ hơn thành phần này có nghĩa là gì, hoặc tệp này, lớp này có ý nghĩa gì.
OK, so again, don't treat this as, like, teaching you, here's how to start the very beginning of the project. More like we'll give you some high level overview of what the ARC algorithm is.
Nên đừng xem đây là buổi hướng dẫn cách bắt đầu từ bước đầu tiên của dự án. Đúng hơn là chúng tôi sẽ đưa ra tổng quan ở mức cao về thuật toán ARC là gì.
We'll go over that in more detail than I did in class, and some other parts of the system.
Chúng tôi sẽ đi vào chi tiết hơn so với trên lớp, và một số phần khác của hệ thống.
But then if you have more detailed questions about the implementation, this is the opportunity to do that. OK, it'll be recorded and we'll post the slides on Box later, later, later that evening.
Nhưng nếu bạn có câu hỏi chi tiết hơn về cách triển khai, thì đây là cơ hội để hỏi. Buổi này sẽ được ghi hình và chúng tôi sẽ đăng slide lên Box sau, muộn hơn, vào tối hôm đó.
OK, that's again, that's tomorrow night over Zoom, not anywhere in person.
Vậy, đó là tối mai qua Zoom, không phải trực tiếp ở đâu cả.
For the upcoming database talks, as I said last class, today and today and tomorrow are our visit days from all our industry friends.
Về các buổi nói chuyện về cơ sở dữ liệu sắp tới, như tôi đã nói ở buổi trước, hôm nay và ngày mai là những ngày ghé thăm của các bạn bè trong ngành.
So we have two sessions or three sessions in the morning tomorrow starting at 9:30. Everything will be in the Gates, Gates building.
Sáng mai có hai hoặc ba buổi, bắt đầu lúc 9:30. Tất cả sẽ diễn ra ở tòa nhà Gates.
So you can see here again, I know we asked you to select what companies you want to go visit. That wasn't like a contract saying, "I'm going to meet this company at this time."
Như các bạn thấy ở đây, tôi biết chúng tôi đã nhờ các bạn chọn công ty muốn đến gặp. Đó không phải là cam kết kiểu "tôi sẽ gặp công ty này vào giờ này".
It was more like we want to know what your preferences and availability was.
Mà đúng hơn là chúng tôi muốn biết sở thích và thời gian rảnh của các bạn.
So then we ran this through a stable marriage algorithm, optimizer algorithm, and it generated the optimal schedule that tries to meet the most people's requests and demands.
Sau đó chúng tôi chạy dữ liệu qua một thuật toán stable marriage, một thuật toán tối ưu hóa, và nó tạo ra lịch trình tối ưu cố gắng đáp ứng yêu cầu và nhu cầu của nhiều người nhất.
OK, there was one big announcement last Wednesday when we had class. So actually, while we were presenting in class, one of these companies got acquired. Anybody know which one it was? What's that?
Được rồi, có một thông báo lớn hôm thứ Tư tuần trước khi chúng ta có lớp. Thực ra, ngay khi chúng ta đang thuyết trình trên lớp, một trong các công ty này đã bị mua lại. Có ai biết là công ty nào không? Gì cơ?
The guy actually speaking, Joy Joe from SingleStore, while he was talking, his company got acquired by Vector Capital. So as he said, SingleStore has been around for a while.
Chính người đang nói, Joy Joe của SingleStore, trong lúc anh ấy đang nói, công ty của anh ấy đã bị Vector Capital mua lại. Như anh ấy nói, SingleStore đã có mặt được một thời gian rồi.
It was originally called MemSQL. That's first how I met these guys in 2012, 2011. We can talk a little offline about what the initial incarnation of MemSQL looked like.
Ban đầu nó có tên là MemSQL. Đó là lần đầu tiên tôi quen những người này, vào năm 2012, 2011. Chúng ta có thể nói chuyện riêng một chút về việc phiên bản đầu tiên của MemSQL trông như thế nào.
They had one very, very famous investor who did pretty well from last week's announcement. That is Ashton Kutcher.
Họ có một nhà đầu tư rất, rất nổi tiếng, người đã được lợi khá nhiều từ thông báo của tuần trước. Đó là Ashton Kutcher.
Believe it or not, Ashton Kutcher was an early investor in MemSQL, or now SingleStore. I don't know how they met him. I don't know how Ashton Kutcher even knows anything about databases.
Tin hay không tùy bạn, Ashton Kutcher từng là nhà đầu tư ban đầu của MemSQL, hay bây giờ là SingleStore. Tôi không biết họ quen anh ta bằng cách nào. Tôi cũng không biết sao Ashton Kutcher lại biết gì đó về cơ sở dữ liệu.
But this tweet is real from 10 years ago. So yeah, congrats to those guys. Although none of them are there anymore, right? Eric Frenkiel left.
Nhưng dòng tweet này là thật, từ 10 năm trước. Vậy nên, xin chúc mừng những người đó. Dù giờ không còn ai trong số họ ở đó nữa, đúng không? Eric Frenkiel đã rời đi.
Nikita, I mentioned, he left SingleStore and went to Neon that got bought by Databricks for a billion. So whatever, they're fine. All right.
Nikita, tôi đã nhắc, anh ấy rời SingleStore và sang Neon, công ty đã bị Databricks mua với giá một tỉ đô. Nên thôi, họ ổn cả. Được rồi.
So last class, we talked about an alternative to the tuple-oriented storage we saw before with slotted pages. And we said it isn't the only way you have to store data, store tuples in pages.
Vậy ở buổi trước, chúng ta đã nói về một giải pháp thay thế cho cách lưu trữ hướng tuple mà ta thấy trước đó với slotted page. Và chúng ta nói rằng đó không phải cách duy nhất để lưu dữ liệu, lưu tuple trong các trang.
And we looked at mostly the log-structured storage scheme, where instead of actually storing maybe the entire tuple, and every time it gets updated, overwriting the existing tuple, we're just appending to these log files that get written out to disk.
Chúng ta chủ yếu xem xét lược đồ lưu trữ log-structured, trong đó thay vì lưu toàn bộ tuple, và mỗi lần cập nhật lại ghi đè lên tuple hiện có, ta chỉ nối thêm vào các tệp log được ghi xuống đĩa.
And then in the background, there's some compaction mechanism. We talked about level compaction or universal compaction to combine them together to reduce redundant information and compress the sizes.
Rồi ở chế độ nền, có một cơ chế compaction nào đó. Chúng ta đã nói về level compaction hoặc universal compaction để gộp chúng lại với nhau nhằm giảm thông tin dư thừa và nén kích thước.
Index-organized storage, the idea was it looks basically like the slotted page approach, but instead of having this heap file where I'm jumping to unordered pages to find the data I'm looking for, I'm actually going to use a tree-based data structure, like a B+tree, which we'll discuss in a few weeks, and traverse down the tree to find the data I'm looking for.
Với lưu trữ index-organized, ý tưởng là nó trông về cơ bản giống cách tiếp cận slotted page, nhưng thay vì có tệp heap này nơi tôi nhảy qua các trang không có thứ tự để tìm dữ liệu cần tìm, tôi sẽ dùng một cấu trúc dữ liệu dạng cây, như B+tree, mà chúng ta sẽ bàn trong vài tuần tới, và duyệt xuống cây để tìm dữ liệu cần tìm.
And then in the leaf nodes, rather than being a pointer to where the data exists in a heap page, it's actually the data itself. MySQL does this, SQLite does this.
Và ở các nút lá, thay vì là con trỏ tới nơi dữ liệu nằm trong một trang heap, thì đó chính là dữ liệu. MySQL làm vậy, SQLite cũng làm vậy.
Again, each of these approaches has pros and cons, but ideally we saw that they were better for doing update-heavy or write-heavy workloads, where you're ingesting a lot of new information from the outside world.
Một lần nữa, mỗi cách tiếp cận đều có ưu và nhược điểm, nhưng lý tưởng thì chúng ta thấy chúng tốt hơn cho các khối lượng công việc nặng về cập nhật hoặc nặng về ghi, nơi bạn nạp rất nhiều thông tin mới từ thế giới bên ngoài.
Most of the queries that exist in the real world, though, are not going to be write queries. Most of the queries are going to be read queries or select queries.
Tuy nhiên, hầu hết các truy vấn trong thế giới thực sẽ không phải là truy vấn ghi. Hầu hết các truy vấn sẽ là truy vấn đọc, hay truy vấn select.
In fact, for certain read queries that are maybe looking at a lot of data or trying to do more complex things, these approaches are actually going to be terrible.
Thực tế, với một số truy vấn đọc có thể xem xét rất nhiều dữ liệu hoặc cố gắng làm những việc phức tạp hơn, thì các cách tiếp cận này thực sự sẽ rất tệ.
Even the heap file, sorry, the tuple-oriented storage we talked about before, the slotted pages, that's going to be terrible for analytical queries.
Ngay cả heap file, xin lỗi, ý tôi là lưu trữ hướng tuple mà chúng ta đã nói trước đây, tức các slotted page, thì cũng sẽ rất tệ cho các truy vấn phân tích.
And the SingleStore talk that he gave last class is actually the introduction for this class, This today's lecture, because a lot of things he was saying maybe didn't make any sense, and why you want to use a column store, that's what we're going to talk about today.
Và bài nói của SingleStore mà anh ấy trình bày ở buổi trước thực ra chính là phần giới thiệu cho bài giảng hôm nay, vì có nhiều điều anh ấy nói có thể nghe chưa hợp lý, và tại sao bạn nên dùng column store, đó là điều chúng ta sẽ nói đến hôm nay.
So I'm going to briefly go over again what the SingleStore guy talked about last class, and talk about the different types of workloads that are out there for databases and how we can design our database system to account for these workloads and come up with more optimal schemes.
Vì vậy tôi sẽ điểm lại ngắn gọn những gì người của SingleStore đã trình bày ở buổi trước, và nói về các loại workload khác nhau đang tồn tại đối với cơ sở dữ liệu, cũng như cách chúng ta có thể thiết kế hệ cơ sở dữ liệu để phù hợp với các workload này và đưa ra những lược đồ tối ưu hơn.
And then the beauty of SQL and the relational model, with the separation between the logical layer and the physical layer, is that I can still expose a relational table interface to the application.
Và vẻ đẹp của SQL và mô hình quan hệ, với sự tách biệt giữa tầng logic và tầng vật lý, là tôi vẫn có thể cung cấp cho ứng dụng một giao diện bảng quan hệ.
Like, I'll call CREATE TABLE and I'll write my SQL queries on that, but underneath the covers we can use one of these alternative storage models to come up with a more optimized scheme for our data to make queries run faster.
Chẳng hạn, tôi gọi CREATE TABLE và viết các truy vấn SQL trên đó, nhưng bên dưới, chúng ta có thể dùng một trong những mô hình lưu trữ thay thế này để có một lược đồ tối ưu hơn cho dữ liệu, giúp truy vấn chạy nhanh hơn.
And not just a little bit faster, I mean orders of magnitude faster.
Và không chỉ nhanh hơn một chút, mà là nhanh hơn nhiều cấp độ.
Think of going, like, in the early days of column stores, I had a friend who worked at one of the ones called Vertica.
Hãy nghĩ đến thời kỳ đầu của column store, tôi có một người bạn làm ở một hệ có tên là Vertica.
They told me that there was some Australian telephone company, they had queries that would take days, and then when they switched over to a column store system, which we'll talk about today, it went to, like, minutes.
Họ kể với tôi rằng có một công ty điện thoại của Úc, có những truy vấn chạy mất nhiều ngày, rồi khi họ chuyển sang một hệ thống column store, mà hôm nay chúng ta sẽ nói đến, thì chỉ còn khoảng vài phút.
Their minds were blown. And we'll see why that's the case here.
Họ vô cùng kinh ngạc. Và chúng ta sẽ thấy vì sao lại như vậy.
So we're going to talk about different storage models, and then we'll talk about techniques to actually make this run even faster by compressing the data.
Vì vậy chúng ta sẽ nói về các mô hình lưu trữ khác nhau, rồi sau đó nói về các kỹ thuật để thực sự làm cho việc này chạy nhanh hơn nữa bằng cách nén dữ liệu.
So this is a bit of a repeat of what, again, the SingleStore guy talked about, but I want to put it in my own words. There's roughly three categories of database workloads.
Phần này hơi lặp lại những gì người của SingleStore đã nói, nhưng tôi muốn diễn đạt bằng lời của mình. Có khoảng ba loại workload của cơ sở dữ liệu.
There's OLTP, OLAP, and the last one is HTAP, hybrid transaction processing. OLTP is what people typically start with when they're building a brand-new application. If you're a brand-new startup, you don't have any data.
Có OLTP, OLAP, và loại cuối cùng là HTAP, xử lý giao dịch lai. OLTP là thứ mà người ta thường bắt đầu khi xây dựng một ứng dụng hoàn toàn mới. Nếu bạn là một startup mới toanh, bạn chưa có dữ liệu nào.
You're going to build some kind of app that people can connect to, interact with, and then you'll be ingesting new data from updates from the outside world. That's an OLTP application.
Bạn sẽ xây một ứng dụng nào đó để mọi người kết nối vào và tương tác, rồi bạn sẽ nạp dữ liệu mới từ các cập nhật đến từ thế giới bên ngoài. Đó là một ứng dụng OLTP.
You're taking new data, again, from the outside world, but the amount of data that you're taking for every single operation, for every single query, is going to be small.
Bạn tiếp nhận dữ liệu mới, một lần nữa, từ thế giới bên ngoài, nhưng lượng dữ liệu bạn nhận cho mỗi thao tác, cho mỗi truy vấn, là nhỏ.
Think of posting a message on Reddit, a comment on Reddit. You typing in the box and hitting send, the amount of data they're storing for that one comment request is actually not that big.
Hãy nghĩ đến việc đăng một tin nhắn trên Reddit, một bình luận trên Reddit. Bạn gõ vào ô nhập rồi nhấn gửi, lượng dữ liệu họ lưu cho một yêu cầu bình luận đó thực ra không lớn.
Your username, a timestamp, and then the text field. Or think of buying something on Amazon. You put something in your cart, that updates the database.
Tên người dùng, một timestamp, và trường văn bản. Hoặc hãy nghĩ đến việc mua hàng trên Amazon. Bạn bỏ một món vào giỏ hàng, thao tác đó cập nhật cơ sở dữ liệu.
It's like your user account information, a timestamp, the item you want to buy, and then the quantity. It's not that much data.
Nó giống như thông tin tài khoản người dùng của bạn, một dấu thời gian, món hàng bạn muốn mua, rồi đến số lượng. Lượng dữ liệu này không nhiều.
We're going to do a lot of this, and we want to try this very, very quickly.
Chúng ta sẽ làm rất nhiều thao tác như vậy, và chúng ta muốn làm chúng thật, thật nhanh.
OLAP is once you have a lot of data, existing data, then you want to run analytical operations on them, basically asking questions about that data to extract new knowledge based on the aggregate data that you have.
OLAP là khi bạn đã có rất nhiều dữ liệu, dữ liệu sẵn có, và bạn muốn chạy các thao tác phân tích trên chúng, về cơ bản là đặt câu hỏi về dữ liệu đó để rút ra tri thức mới dựa trên dữ liệu tổng hợp mà bạn có.
Going back to the Amazon example, OLTP would be like, again, someone buying one item. For every person buying one item, that's a small amount of data per person.
Quay lại ví dụ về Amazon, OLTP sẽ là, một lần nữa, ai đó mua một món hàng. Với mỗi người mua một món hàng, đó là một lượng dữ liệu nhỏ cho mỗi người.
But the total amount of data that they're generating across all the orders, across all people using Amazon, is actually quite a lot.
Nhưng tổng lượng dữ liệu mà họ tạo ra trên tất cả các đơn hàng, của tất cả những người dùng Amazon, thì thực ra rất lớn.
Now when you want to run analytical queries, you can answer questions like, what's the number one item bought in the city of Pittsburgh this day in September when the temperature was above this degree or that degree, and so forth.
Giờ khi bạn muốn chạy các truy vấn phân tích, bạn có thể trả lời những câu hỏi như: món hàng nào được mua nhiều nhất ở thành phố Pittsburgh vào ngày này của tháng 9 khi nhiệt độ cao hơn mức này hay mức kia, và vân vân.
That's an analytical query because you're asking a question about looking across multiple entities, multiple entries in the database, in the tables.
Đó là một truy vấn phân tích vì bạn đang đặt một câu hỏi liên quan đến việc xem xét nhiều thực thể, nhiều bản ghi trong cơ sở dữ liệu, trong các bảng.
And so these queries are going to be more complex than we do in OLTP. We'll be joining multiple tables, doing window function aggregations, all the kind of stuff you did in homework one.
Vì vậy các truy vấn này sẽ phức tạp hơn những gì chúng ta làm trong OLTP. Chúng ta sẽ kết nối nhiều bảng, thực hiện các phép tổng hợp với hàm cửa sổ, tất cả những thứ mà các bạn đã làm trong bài tập về nhà một.
You typically see them in the OLAP workloads.
Bạn thường thấy chúng trong các khối lượng công việc OLAP.
HTAP, or Hybrid Transaction Analytical Processing, this is like the holy grail for systems, but it doesn't always pan out, where you want to be able to do fast transactions or do fast OLTP operations.
HTAP, hay Hybrid Transaction Analytical Processing, là một dạng chén thánh đối với các hệ thống, nhưng không phải lúc nào cũng thành công, ở chỗ bạn muốn có thể thực hiện giao dịch nhanh, tức các thao tác OLTP nhanh.
You can just view data very quickly. But then you also want to ask questions about that data, where it exists in that database, without slowing down the rest of the workload.
Bạn có thể xem dữ liệu rất nhanh. Nhưng bạn cũng muốn đặt câu hỏi về dữ liệu đó, ngay tại nơi nó nằm trong cơ sở dữ liệu, mà không làm chậm phần còn lại của khối lượng công việc.
SingleStore is trying to push this. TiDB is another one to do this.
SingleStore đang cố thúc đẩy hướng này. TiDB là một hệ thống khác làm điều này.
This one is going to be a bit hit or miss, because oftentimes it isn't the best OLTP system, and it isn't the best OLAP system.
Hướng này sẽ có lúc được lúc không, vì thường nó không phải là hệ thống OLTP tốt nhất, cũng không phải là hệ thống OLAP tốt nhất.
And if you're in a big company, the people that care about OLTP, they want the best ones, they'll pick something else. And the people that want the best OLAP system, they'll pick something else.
Và nếu bạn ở một công ty lớn, những người quan tâm đến OLTP muốn hệ thống tốt nhất, họ sẽ chọn thứ khác. Còn những người muốn hệ thống OLAP tốt nhất thì cũng sẽ chọn thứ khác.
But this is the market segment that doesn't exist. AI is kind of separate from this, and it's kind of what comes after OLAP.
Nhưng đây là phân khúc thị trường không tồn tại. AI hơi tách biệt khỏi những thứ này, và nó là thứ đến sau OLAP.
So in OLAP, you can ask questions about what was this, what was that, based on the data you have.
Vậy trong OLAP, bạn có thể hỏi cái này là gì, cái kia là gì, dựa trên dữ liệu bạn có.
The AI stuff that's starting to come out is starting to ask questions about why things work a certain way.
Những thứ về AI bắt đầu xuất hiện là bắt đầu đặt câu hỏi về lý do vì sao mọi thứ hoạt động theo một cách nào đó.
Why was this item the number one bought item in Pittsburgh at this date and time? And what aspects of it make it interesting for people in a certain demographic and so forth?
Vì sao món hàng này là món được mua nhiều nhất ở Pittsburgh vào ngày giờ này? Và những khía cạnh nào của nó khiến nó hấp dẫn đối với những người thuộc một nhóm nhân khẩu học nhất định, và vân vân?
Those are the kind of things AI cares about, and we'll see how we handle that later on in vector indexes.
Đó là những điều mà AI quan tâm, và chúng ta sẽ xem cách xử lý chúng sau này trong phần chỉ mục vectơ.
But it smells enough like OLAP that we don't have to show it as a separate category here.
Nhưng nó đủ giống OLAP nên ở đây chúng ta không cần tách nó thành một loại riêng.
So a really simple quad chart to understand the distinction between these two categories of workloads is looking at whether the workload is write-heavy versus read-heavy, And whether the operation of the query that you're trying to execute in the database system is going to be simple or complex.
Vậy một biểu đồ bốn góc phần tư rất đơn giản để hiểu sự khác biệt giữa hai loại khối lượng công việc này là xem khối lượng công việc thiên về ghi hay thiên về đọc, và xem thao tác của truy vấn mà bạn muốn thực thi trong hệ cơ sở dữ liệu là đơn giản hay phức tạp.
And complexity is not really a scientific term or something we can measure a query in based on. It's usually something like, how many tables does it join?
Và độ phức tạp không thực sự là một thuật ngữ khoa học hay thứ mà ta có thể dùng để đo một truy vấn. Thường là kiểu như: nó join bao nhiêu bảng?
Does it do aggregations? How many group bys? How many nested queries? In OLTP, queries are pretty simple. SELECT * FROM table users WHERE username equals Andy.
Có thực hiện phép tổng hợp không? Bao nhiêu group by? Bao nhiêu truy vấn lồng nhau? Trong OLTP, các truy vấn khá đơn giản. SELECT * FROM table users WHERE username bằng Andy.
You're going to get one thing, doing a lookup on an index. So you can roughly divide the workloads like this. So on one end, on the bottom corner, you have OLTP.
Bạn sẽ lấy về một bản ghi, bằng cách tra cứu trên một chỉ mục. Vậy có thể chia đại khái các khối lượng công việc như thế này. Ở một đầu, góc dưới, bạn có OLTP.
These workloads are considerably more write-heavy than OLAP because, again, you're ingesting new data from the outside world, although most of the times, even in an OLTP system, most of the operations are read queries.
Các khối lượng công việc này thiên về ghi hơn đáng kể so với OLAP vì, như đã nói, bạn đang nạp dữ liệu mới từ thế giới bên ngoài, mặc dù phần lớn thời gian, kể cả trong một hệ OLTP, hầu hết các thao tác là truy vấn đọc.
And then the queries you're actually running are pretty simple, like go select Andy's record, bank account information, go get Andy's orders from the last year. OLAP is the other end up here.
Và các truy vấn bạn thực sự chạy khá đơn giản, như chọn bản ghi của Andy, thông tin tài khoản ngân hàng, lấy các đơn hàng của Andy trong năm ngoái. OLAP là đầu còn lại, ở trên này.
And the workloads are typically almost always more read-heavy, and the queries are more complex. So OLAP is... OLTP is an older term. It goes back to like the 80s.
Và các khối lượng công việc thường hầu như luôn thiên về đọc hơn, và các truy vấn phức tạp hơn. OLTP là một thuật ngữ cũ hơn, có từ khoảng thập niên 80.
OLAP came out of the 90s. It was actually invented by this very famous database researcher called Jim Gray. He won the Turing Award for databases in the 1990s.
OLAP xuất hiện từ thập niên 90. Nó thực ra do một nhà nghiên cứu cơ sở dữ liệu rất nổi tiếng là Jim Gray đặt ra. Ông nhận Giải Turing về cơ sở dữ liệu vào thập niên 1990.
He invented a lot of stuff we're going to talk about in this class, like two-phase locking and other techniques as we go along.
Ông phát minh ra rất nhiều thứ mà chúng ta sẽ học trong môn này, như khóa hai pha và các kỹ thuật khác khi học tiếp.
Famously, he got lost at sea in 2007 when he was sailing his boat in the San Francisco Bay.
Nổi tiếng là ông mất tích trên biển năm 2007 khi đang chèo thuyền ở vịnh San Francisco.
And he was so famous, they actually moved satellites to go back over the San Francisco Bay to actually look for his body or his ship, and they never found him.
Ông nổi tiếng đến mức người ta đã chuyển hướng vệ tinh quay lại vịnh San Francisco để tìm thi thể hay con thuyền của ông, và họ không bao giờ tìm thấy ông.
So he's considered lost at sea.
Nên ông được coi là mất tích trên biển.
Truth is, though, when he invented this OLAP term, he was actually doing it on the behest of another company that was trying to sell a new product and say, "Hey, look, here's this brand new category of systems called OLAP."
Tuy nhiên, sự thật là khi ông đặt ra thuật ngữ OLAP này, ông làm vậy theo yêu cầu của một công ty khác đang muốn bán một sản phẩm mới và nói: "Này, nhìn xem, đây là một loại hệ thống hoàn toàn mới gọi là OLAP."
So he wrote a paper like, "Hey, look, there's this thing called OLAP. This is why it matters." And then when people found out he got paid to write the article, he got retracted.
Thế là ông viết một bài báo kiểu như: "Này, có thứ gọi là OLAP. Đây là lý do nó quan trọng." Rồi khi mọi người phát hiện ông được trả tiền để viết bài đó, bài báo bị rút lại.
Other than that, other than that little snafu, I never met him. He was considered a good guy, though. And then HTAP will be somewhere here in the middle, right?
Ngoài chuyện đó, ngoài cái sự cố nhỏ ấy ra, tôi chưa từng gặp ông. Tuy vậy ông được coi là người tốt. Và HTAP sẽ nằm đâu đó ở giữa đây, đúng không?
Again, this is not a scientific chart. This is trying to say, like, again, how to roughly think about the different workloads. So for today's class, we're going to use an example actually from Wikipedia.
Một lần nữa, đây không phải là biểu đồ khoa học. Biểu đồ này muốn nói, một lần nữa, cách nghĩ đại khái về các loại khối lượng công việc khác nhau. Với buổi học hôm nay, chúng ta sẽ dùng một ví dụ lấy từ Wikipedia.
So this is actually based on the Wikipedia schema. It's open source. It's written in PHP. They run off MySQL. It's one of the largest MySQL clusters, I think, around.
Ví dụ này dựa trên schema của Wikipedia. Nó là mã nguồn mở. Nó được viết bằng PHP. Họ chạy trên MySQL. Tôi nghĩ đó là một trong những cụm MySQL lớn nhất hiện có.
Actually, they might have switched to MariaDB by now when Oracle bought them. But this is roughly what the schema looks like. So we're going to have a user account table.
Thực ra bây giờ có thể họ đã chuyển sang MariaDB rồi, từ khi Oracle mua lại họ. Nhưng schema đại khái trông như thế này. Chúng ta sẽ có một bảng tài khoản người dùng.
Again, that's your login information. We'll have articles or pages that define, like, here's an article on Star Wars or whatever.
Tức là thông tin đăng nhập của bạn. Chúng ta sẽ có các bài viết hay các trang, để định nghĩa kiểu như, đây là một bài viết về Star Wars chẳng hạn.
And then we'll have a revisions table where we're going to put all the new versions of the pages that come along, right? Or new versions of an article, right?
Và rồi sẽ có một bảng revisions nơi chúng ta đưa vào tất cả các phiên bản mới của các trang được tạo ra, đúng không? Hay các phiên bản mới của một bài viết, đúng không?
And what I'm showing here is actually the content is inside of this table here, the revisions. And actually, the real schema, they put it at the separate table, right?
Và cái tôi đang cho thấy ở đây là nội dung nằm bên trong bảng này, bảng revisions. Còn trong schema thật, họ đặt nó ở một bảng riêng, đúng không?
Because they don't want to have a giant blob in the page itself. But we can ignore that. But you can see here, there's foreign key references all around.
Vì họ không muốn có một blob khổng lồ nằm ngay trong trang. Nhưng ta có thể bỏ qua chuyện đó. Nhưng các bạn có thể thấy ở đây có các tham chiếu khóa ngoại khắp nơi.
Wikipedia is a sore subject for me because a few years ago, somebody actually wrote a Wikipedia article about me.
Wikipedia là một đề tài hơi nhạy cảm với tôi vì vài năm trước, có người đã viết một bài Wikipedia về tôi.
But then they put this line in that I used to have in my bio somewhere. It said I was born and raised in the streets of Baltimore, which is true.
Nhưng họ lại thêm vào một câu mà trước đây tôi từng để trong tiểu sử của mình ở đâu đó. Câu đó nói rằng tôi sinh ra và lớn lên trên đường phố Baltimore, và điều đó là thật.
I was born in Baltimore, But obviously not in the streets. And then Wikipedia got, they flagged that and said, "In the streets", it's not scientific or encyclopedic enough.
Tôi sinh ra ở Baltimore, nhưng dĩ nhiên không phải ngoài đường. Rồi Wikipedia đánh dấu câu đó, họ nói "trên đường phố", nghe không đủ khoa học hay mang tính bách khoa.
And then it got flagged, and it got taken down. And then, whatever.
Rồi nó bị đánh dấu, rồi bị gỡ xuống. Và thôi, kệ.
And then since then, I get emails basically every three months from these scammers saying, "Hey, give us money, we'll write your article for you," right?
Và từ đó đến nay, cứ khoảng ba tháng tôi lại nhận email từ mấy kẻ lừa đảo nói rằng: "Này, đưa tiền đây, chúng tôi sẽ viết bài về anh cho," đúng không?
All right, so if anybody's watching this, was I born in Baltimore? Yes. Was I born in the streets of Baltimore? No. Right? That should go without saying. Okay. Yes.
Thôi được, nếu ai đang xem cái này, tôi có sinh ra ở Baltimore không? Có. Tôi có sinh ra trên đường phố Baltimore không? Không. Đúng không? Chuyện đó khỏi cần nói. Được rồi. Mời bạn.
The question is, why are we separating, why are we making a distinction right now between OLAP and OLTP? At this point, I'm only contrasting the workloads.
Câu hỏi là, tại sao chúng ta tách ra, tại sao ngay bây giờ lại phân biệt giữa OLAP và OLTP? Lúc này tôi chỉ đang đối chiếu các khối lượng công việc.
And then we'll see how we'll design a system for those different workloads. And then at the end of the class, we'll finish up and say, okay, well, do I have separate systems?
Rồi chúng ta sẽ xem thiết kế một hệ thống cho các khối lượng công việc khác nhau đó như thế nào. Và cuối buổi học, chúng ta sẽ kết lại và hỏi, được rồi, mình có các hệ thống riêng biệt không?
And how do I get data from one to the other? Or can I have a single system handle both? So we'll cover that. I think that'll answer your question. Other questions?
Và làm sao đưa dữ liệu từ hệ thống này sang hệ thống kia? Hay có thể để một hệ thống duy nhất xử lý cả hai? Chúng ta sẽ bàn đến. Tôi nghĩ vậy sẽ trả lời được câu hỏi của bạn. Còn câu hỏi nào khác không?
Other than me being from Baltimore. Okay.
Ngoài chuyện tôi đến từ Baltimore. Được rồi.
So again, I said this at the beginning, the relational model is beautiful because it says, hey, this is what the data should look like, how to represent it at a high level.
Vậy, như tôi đã nói lúc đầu, mô hình quan hệ rất đẹp vì nó nói rằng, này, dữ liệu nên trông như thế này, biểu diễn nó ở mức cao như thế này.
It doesn't say anything about how we actually store and represent that data as physical bits or bytes we're gonna store on the underlying storage medium. All right.
Nó không nói gì về việc chúng ta thực sự lưu trữ và biểu diễn dữ liệu đó thành các bit vật lý hay byte mà chúng ta sẽ lưu trên phương tiện lưu trữ bên dưới. Được rồi.
So there's nothing about the relational model that says, just because you declare a table and the table has these attributes, that those attributes have to be stored contiguously on a disk page or in memory.
Vì vậy, mô hình quan hệ không hề nói rằng, chỉ vì bạn khai báo một bảng và bảng đó có các thuộc tính này, thì các thuộc tính đó phải được lưu liền kề nhau trên một trang đĩa hay trong bộ nhớ.
In fact, we already saw that we could break that before, break that notion, when we had the oversized values. We talked about the TOAST table or the external storage, like in Postgres.
Thực tế, chúng ta đã thấy trước đây rằng có thể phá vỡ quan niệm đó, khi nói về các giá trị quá khổ. Chúng ta đã nói về bảng TOAST hay lưu trữ ngoài, như trong Postgres.
If I have a really large text field, I don't store that in my slotted page. I have a separate page where I store that and then store a pointer to it.
Nếu tôi có một trường văn bản rất lớn, tôi không lưu nó trong slotted page. Tôi dùng một trang riêng để lưu nó, rồi lưu một con trỏ trỏ tới đó.
And then now when I run queries on it, underneath the covers, the DBMS is gonna stitch that table back together by following the pointer.
Và khi tôi chạy truy vấn trên đó, ở bên dưới, DBMS sẽ ghép bảng lại bằng cách lần theo con trỏ.
But to the application, you don't know that things have been separated.
Nhưng với ứng dụng, bạn không biết dữ liệu đã bị tách ra.
So it turns out for some workloads, particularly OLAP workloads, storing things contiguously is actually gonna be not the best way to do it.
Hóa ra với một số workload, đặc biệt là workload OLAP, lưu liền kề thực ra không phải cách tốt nhất.
So for OLTP, as I said, the queries are simple and they're accessing a small amount of data. And this, again, this is what people normally build when they first build a new application.
Với OLTP, như tôi đã nói, các truy vấn đơn giản và chỉ truy cập một lượng dữ liệu nhỏ. Và đây là thứ người ta thường xây dựng khi mới làm một ứng dụng mới.
If you're a new startup or whatever, new project, this is what you end up building. So here's some three sort of simple examples of OLTP queries in Wikipedia.
Nếu bạn là startup mới hay dự án mới, đây là thứ bạn sẽ xây. Đây là ba ví dụ đơn giản về truy vấn OLTP trong Wikipedia.
So one is going to get the latest revision for a given page by looking up the page ID.
Truy vấn đầu tiên lấy phiên bản mới nhất của một trang bằng cách tra theo page ID.
So there'll be an index on page ID, because if it's a primary key, there'll be an index on that and we can do a lookup.
Sẽ có một chỉ mục trên page ID, vì nếu nó là khóa chính, sẽ có chỉ mục trên đó và ta có thể tra cứu.
Another one is someone actually logs in, so we'll update the last login timestamp with the current timestamp, whatever hostname they used to log in.
Truy vấn khác là khi ai đó đăng nhập, ta sẽ cập nhật dấu thời gian đăng nhập gần nhất bằng dấu thời gian hiện tại, cùng với hostname mà họ dùng để đăng nhập.
And again, we'll do a lookup based on the user ID. So again, that'll be another index lookup. That's very fast.
Và ta lại tra cứu dựa trên user ID. Đó lại là một lần tra cứu chỉ mục. Rất nhanh.
And the last one is like inserting a new entry into the revisions table, right?
Và truy vấn cuối là chèn một mục mới vào bảng revisions.
So if we store things contiguously for a single tuple, well, most of these queries, all these queries here are touching, well, the bottom two are touching one tuple.
Nếu ta lưu liền kề cho mỗi tuple, thì hầu hết các truy vấn này, tất cả các truy vấn ở đây, à, hai truy vấn dưới chỉ chạm vào một tuple.
The top one can touch at least two tuples, because whatever the current page is, or for a given page, and then what are the latest revision is.
Truy vấn trên cùng chạm ít nhất hai tuple, vì có trang hiện tại, hoặc với một trang cho trước, rồi đến phiên bản mới nhất.
An OLAP query looks something like this, where I'm trying to get the count, the number of times someone has logged in for a, For, to, you know, logged into the service where their hostname ended with the .gov IP address or namespace, right?
Một truy vấn OLAP trông như thế này, trong đó tôi muốn lấy số lượng, số lần ai đó đã đăng nhập vào, dịch vụ mà hostname của họ kết thúc bằng .gov, địa chỉ IP hay không gian tên.
This is actually an example from a real scandal 15 years ago where a bunch of Congress people were having their staff who were on government, you know, salaries log into Wikipedia and update their, the entry for the Congress person, saying like, "Look how great they are," or "Here's them doing, you know, charity work," right?
Đây thực ra là ví dụ từ một vụ bê bối có thật cách đây 15 năm, khi một loạt nghị sĩ Quốc hội bắt nhân viên của họ, những người hưởng lương nhà nước, đăng nhập vào Wikipedia và cập nhật mục về vị nghị sĩ đó, kiểu như "Xem họ tuyệt vời thế nào," hay "Đây là họ đang làm từ thiện," đúng không?
So you're basically paying government employees to go put out propaganda on Wikipedia. So you could use this query. This is basically roughly the query they did to find it.
Về cơ bản là trả tiền cho nhân viên nhà nước để đi tuyên truyền trên Wikipedia. Vậy bạn có thể dùng truy vấn này. Đại khái đây là truy vấn mà họ đã dùng để phát hiện ra chuyện đó.
So in this example here, again, now we're not looking at a single record. We're not looking at one person logging in.
Vậy trong ví dụ này, một lần nữa, giờ chúng ta không xét một bản ghi đơn lẻ. Chúng ta không xét một người đăng nhập.
We're looking at all the entries of logins to try to find a match here. Right?
Chúng ta xét tất cả các bản ghi đăng nhập để tìm ra kết quả khớp. Đúng không?
So a bunch of people, there's a bunch of people got busted for this. Joe Biden did this. Mike Pence got busted for this, right? Basically all of them are doing it.
Có cả một loạt người đã bị phát hiện vì chuyện này. Joe Biden đã làm vậy. Mike Pence cũng bị bắt quả tang, đúng không? Về cơ bản là ai cũng làm vậy.
So the thing we haven't talked about yet is the storage model, which again is a way we're going to physically represent data that's in our database in tables.
Điều chúng ta chưa nói đến là mô hình lưu trữ, tức là cách chúng ta biểu diễn vật lý dữ liệu nằm trong các bảng của cơ sở dữ liệu.
And it basically can tell us how we're going to organize things either in memory or on disk.
Và về cơ bản nó cho biết chúng ta sẽ tổ chức dữ liệu như thế nào, trong bộ nhớ hay trên đĩa.
And as I said, based on the workload, the different storage models we could use, it's going to have wildly different performance because it's going to depend on what the data is actually needed and how it's going to be used by the query.
Và như tôi đã nói, tùy theo khối lượng công việc, các mô hình lưu trữ khác nhau mà ta có thể dùng sẽ cho hiệu năng khác nhau rất xa, vì nó phụ thuộc vào dữ liệu thực sự cần dùng là gì và truy vấn sẽ sử dụng nó như thế nào.
So there's two basic approaches: the n-ary storage model, or the row storage. This is probably what we're most familiar with, and this is what we'll be seeing in our examples.
Có hai cách tiếp cận cơ bản: mô hình lưu trữ n-ary, hay lưu trữ theo hàng. Đây có lẽ là cái chúng ta quen thuộc nhất, và là cái chúng ta sẽ thấy trong các ví dụ.
And then the column store one is the one we've been alluding to, where actually we're going to store things, instead of row-based, we'll store it as column-based. We'll see why that matters.
Còn column store là cái mà nãy giờ chúng ta hay nhắc tới, trong đó chúng ta sẽ lưu trữ dữ liệu, thay vì theo hàng thì lưu theo cột. Chúng ta sẽ thấy vì sao điều đó quan trọng.
And then the last one, this hybrid storage model, also known as PAX. This is the way most systems actually implement their column stores.
Và cuối cùng là mô hình lưu trữ lai, còn gọi là PAX. Đây là cách hầu hết các hệ thống thực sự cài đặt column store của mình.
So if a system comes out and says, "Yeah, we're a column store," they don't actually mean the second one; they're going to mean this third one here.
Nên nếu một hệ thống ra mắt và nói: "Vâng, chúng tôi là column store", thì họ không thực sự có ý nói cái thứ hai; họ muốn nói cái thứ ba này.
So I'll explain what that looks like, what the difference is.
Tôi sẽ giải thích nó trông như thế nào và khác nhau ở đâu.
So the N-ary storage model, or NSM, this is the academic term, but if you say "I have a row store," this is what they mean and everyone will understand what you're talking about.
Vậy mô hình lưu trữ N-ary, hay NSM, là thuật ngữ học thuật, nhưng nếu bạn nói "tôi có một row store", thì đó là ý của nó và ai cũng hiểu bạn đang nói về cái gì.
This basically says that for a given tuple in our database, in a table, we're going to store all its attributes contiguously within a page, assuming they fit.
Về cơ bản nó nói rằng với một tuple trong cơ sở dữ liệu, trong một bảng, chúng ta sẽ lưu tất cả thuộc tính của nó liền kề nhau trong một trang, giả sử chúng vừa với trang.
If we have to spill to an overflow page or oversize page, that's a separate issue.
Nếu phải tràn sang một trang tràn hoặc trang quá khổ thì đó là một vấn đề riêng.
The idea is that all the data for a given tuple are stored right next to each other within that page.
Ý tưởng là toàn bộ dữ liệu của một tuple được lưu ngay cạnh nhau trong trang đó.
And then the next tuple that we're storing on the page doesn't start until we finish whatever tuple we're writing out the data for. All right?
Và tuple tiếp theo mà chúng ta lưu trên trang sẽ không bắt đầu cho đến khi ta ghi xong dữ liệu của tuple hiện tại. Được chứ?
And this is going to be great for OLTP workloads because the kind of queries we're going to run are either update queries, where we need to have the whole tuple updated anyway, or insert, where we're just inserting the tuple in its entirety, or our select queries are going to be only accessing one tuple, and oftentimes they need all the data within that tuple.
Và điều này rất tốt cho các khối lượng công việc OLTP vì các loại truy vấn chúng ta chạy hoặc là truy vấn cập nhật, khi mà dù sao cũng cần cập nhật cả tuple, hoặc là chèn, khi chúng ta chèn nguyên cả tuple, hoặc các truy vấn select chỉ truy cập một tuple, và thường chúng cần toàn bộ dữ liệu trong tuple đó.
So you want all the attributes. So I'm going to skip this. Let's go through quickly, but this is basically the slotted page that we stored before.
Tức là bạn muốn tất cả thuộc tính. Nên tôi sẽ bỏ qua phần này. Chúng ta đi qua nhanh thôi, đây về cơ bản là trang có khe (slotted page) mà chúng ta đã lưu trước đó.
I'm showing this so we see the distinction later on when we talk about the column store. So within our database page we have our header. Then we have the slot array at the top.
Tôi cho xem cái này để thấy sự khác biệt về sau khi chúng ta nói đến column store. Vậy trong trang cơ sở dữ liệu của chúng ta, ta có phần header. Rồi ở phía trên là mảng slot.
And again, now as we scan down through the data we want to store up above, we're just going to write it from the end to the beginning.
Và một lần nữa, khi ta quét qua dữ liệu muốn lưu ở phía trên, ta sẽ ghi nó từ cuối trang về đầu trang.
And add pointers and offsets for the different locations of the tuples, and we keep going as we scan down over and over again.
Đồng thời thêm các con trỏ và offset cho những vị trí khác nhau của các tuple, và ta cứ tiếp tục như vậy khi quét xuống, lặp đi lặp lại.
All right? So this is just rehashing from the things we talked about, right? Until you fill it up and then you run out of space.
Được chứ? Đây chỉ là nhắc lại những gì chúng ta đã nói, đúng không? Cho đến khi trang đầy và hết chỗ trống.
So let's go back to one of these queries on the Wikipedia. So say here I'm trying to get the user information for one account. So this is somebody logging in.
Vậy hãy quay lại một trong những truy vấn trên Wikipedia. Giả sử ở đây tôi muốn lấy thông tin người dùng của một tài khoản. Tức là có ai đó đang đăng nhập.
So I'm going to pass in the username and then a hashed password. I don't want to store...
Vậy tôi sẽ truyền vào tên người dùng và một mật khẩu đã được băm. Tôi không muốn lưu...
Whenever you see data breaches, they always say your password got leaked because they store raw passwords unencrypted in the database. Don't do that.
Mỗi khi bạn thấy các vụ rò rỉ dữ liệu, họ luôn nói mật khẩu của bạn bị lộ vì họ lưu mật khẩu gốc, không mã hóa, trong cơ sở dữ liệu. Đừng làm vậy.
Do all that encryption stuff outside in the application, and then the database just stores the encrypted data. This is basically the query you would run.
Hãy thực hiện toàn bộ việc mã hóa ở bên ngoài, trong ứng dụng, còn cơ sở dữ liệu chỉ lưu dữ liệu đã mã hóa. Về cơ bản đây là truy vấn bạn sẽ chạy.
So now for this username, I'm going to have some kind of index that I'm going to use to help me find the record ID that I want.
Vậy với tên người dùng này, tôi sẽ có một loại chỉ mục nào đó để dùng giúp tìm ra record ID mà tôi cần.
Now I'm not going to explain what this index is. That's in two weeks when we talk about indexes.
Giờ tôi sẽ không giải thích chỉ mục này là gì. Việc đó để hai tuần nữa, khi ta nói về chỉ mục.
But think of like a hash map or a B+tree or some data structure that says for a given username, here's the record ID where to go find it.
Nhưng hãy hình dung như một hash map, một B+tree hay một cấu trúc dữ liệu nào đó cho biết với một tên người dùng cho trước thì record ID cần tìm nằm ở đâu.
And then now my database system is going to go look in its page directory and says, okay, well you want record one, two, three, four.
Sau đó hệ cơ sở dữ liệu sẽ tra trong page directory và nói: được rồi, bạn muốn bản ghi một, hai, ba, bốn.
That's on page five. That's location in my database file.
Nó nằm ở trang năm. Đó là vị trí trong tệp cơ sở dữ liệu của tôi.
I bring that into memory, and I know how to then use a slot array to jump to the offset that I want, and lo and behold, there's the tuple that I was looking for.
Tôi đưa trang đó vào bộ nhớ, rồi tôi biết cách dùng mảng slot để nhảy tới offset mình muốn, và kìa, tuple mà tôi đang tìm đây rồi.
And I'm happy. And then now if I want to do an insert, same thing. I use some, I have some free space map that says, okay, here's a page that has free data.
Và tôi hài lòng. Còn nếu muốn chèn dữ liệu thì cũng tương tự. Tôi dùng, tôi có một free space map cho biết: đây là một trang còn chỗ trống.
All I need to do is go make sure that page is in memory, Jump to some offset and just write it out from beginning to end.
Tôi chỉ cần đảm bảo trang đó đã có trong bộ nhớ, nhảy tới một offset nào đó và ghi dữ liệu ra từ đầu đến cuối.
But now let's do that OLAP query before where we say, give me all the, count the number of times people have logged in per month from a .gov hostname.
Nhưng giờ hãy làm truy vấn OLAP lúc trước, nơi ta nói: hãy cho tôi tất cả, đếm số lần người dùng đăng nhập mỗi tháng từ hostname có đuôi .gov.
So in this case here, there isn't a lookup on any single predicate. I want to, single primary key or discriminating key.
Vậy trong trường hợp này, không có việc tra cứu theo một điều kiện đơn lẻ nào. Tôi muốn, một khóa chính đơn hoặc một khóa phân biệt.
I got to look at all the pages, because I don't know where any .gov hostnames are going to be.
Tôi phải xem tất cả các trang, vì tôi không biết các hostname .gov nằm ở đâu.
So I'm going to scan all the pages and I'm going to bring them in one by one. And now this is the row store.
Nên tôi sẽ quét tất cả các trang và đưa từng trang vào bộ nhớ. Và đây là row store.
So the first thing I got to do is run my where clause, where I say find me all the hostnames that end with .gov.
Việc đầu tiên tôi phải làm là chạy mệnh đề where, nơi tôi nói hãy tìm tất cả các hostname kết thúc bằng .gov.
So I got to look at all these values in here.
Vậy tôi phải xem tất cả các giá trị ở đây.
And then once I find matches, then I got to run my extract clause to convert the last login into the hostname, sorry, the month number, month name, so then I can then compute my aggregations.
Và khi đã tìm được các bản ghi khớp, thì tôi phải chạy mệnh đề extract để chuyển last login thành hostname, xin lỗi, thành số tháng, tên tháng, rồi sau đó tôi mới có thể tính các phép tổng hợp.
So then I got to look at this data, and I got to look at this data over here.
Vậy là tôi phải nhìn vào phần dữ liệu này, và cả phần dữ liệu ở bên này nữa.
So what's the problem with this data? The other three attributes. Did this query need it? No. Did we have to read it from disk and put it into memory? Yes.
Vậy vấn đề với dữ liệu này là gì? Ba thuộc tính còn lại. Truy vấn này có cần chúng không? Không. Chúng ta có phải đọc chúng từ đĩa và đưa vào bộ nhớ không? Có.
So because this is a row store, whatever is attached to the query, whatever columns, attributes, a query, sorry, tuple has, they come along for the ride because they're in the page with all the other data that I do need.
Vì đây là row store, bất cứ thứ gì gắn với truy vấn, bất kể những cột, thuộc tính nào, à xin lỗi, mà một tuple có, thì chúng đều đi kèm theo vì chúng nằm trong cùng page với những dữ liệu khác mà tôi thực sự cần.
Right?
Đúng không?
So in this case here, I'm not showing the size of the data, but like roughly, say about over 50% of the data that we needed, sorry, 50% of the data for a tuple was actually not needed for this query at all, but I still had to go to disk and go read it.
Trong trường hợp này, tôi không hiển thị kích thước dữ liệu, nhưng đại khái, giả sử hơn 50% dữ liệu mà chúng ta cần, xin lỗi, 50% dữ liệu của một tuple thực ra hoàn toàn không cần cho truy vấn này, nhưng tôi vẫn phải xuống đĩa để đọc nó.
So this is why row stores aren't going to be great for doing analytical queries, because most of the time, analytical queries, I don't need all the attributes.
Đó là lý do row store không phù hợp để xử lý các truy vấn phân tích, vì phần lớn thời gian, với truy vấn phân tích, tôi không cần tất cả các thuộc tính.
You don't see SELECT * queries in analytical queries very often, or analytical workloads, right?
Bạn không hay thấy các truy vấn SELECT * trong truy vấn phân tích, hay các khối lượng công việc phân tích, đúng không?
Like, you shouldn't run SELECT * anyway, but in general you don't really see that unless someone's trying to do a bulk export, and even then there's faster ways to do that than SELECT *.
Dù sao thì bạn cũng không nên chạy SELECT *, nhưng nói chung bạn không thực sự thấy điều đó, trừ khi ai đó muốn xuất hàng loạt dữ liệu, và kể cả khi đó cũng có những cách nhanh hơn SELECT *.
So for the row stores, it can be great for fast inserts, updates and deletes. It's great for queries that need the entire tuple.
Còn với row store, nó rất tốt cho việc chèn, cập nhật và xóa nhanh. Nó rất tốt cho các truy vấn cần toàn bộ tuple.
I need all the attributes for a small number of tuples, and I can do a bunch of tricks, like the index organized storage, all the clustering techniques we'll cover later on, to make this go really, really fast.
Tôi cần tất cả thuộc tính của một số ít tuple, và tôi có thể dùng nhiều mẹo, như index organized storage, tất cả các kỹ thuật phân cụm mà chúng ta sẽ học sau, để làm cho việc này chạy cực kỳ nhanh.
I'm only reading the exact single page I need to go get the data that I want.
Tôi chỉ đọc đúng một page cần thiết để lấy dữ liệu mình muốn.
There's other tricks you can put a bunch of data in the index as well, so maybe I only need to traverse the index, even if I'm not using index organized storage, and all my data is in the index, I don't even need to touch the tuples.
Còn có những mẹo khác, bạn cũng có thể đưa nhiều dữ liệu vào index, nên có thể tôi chỉ cần duyệt index, kể cả khi không dùng index organized storage, và toàn bộ dữ liệu của tôi nằm trong index, tôi thậm chí không cần chạm tới các tuple.
We'll cover that later.
Chúng ta sẽ học phần đó sau.
This can be bad for analytical queries because we'll have a lot more pressure in our buffer pool, because now we're copying in pages with data that we don't even need for this particular query.
Cách này có thể không tốt cho các truy vấn phân tích vì buffer pool của chúng ta sẽ chịu nhiều áp lực hơn rất nhiều, vì lúc này chúng ta sao chép vào các page chứa dữ liệu mà truy vấn cụ thể này thậm chí không cần.
So the alternative is the decomposition storage model. You think of like two opposite ends of the spectrum.
Vậy phương án thay thế là decomposition storage model. Bạn có thể hình dung như hai đầu đối lập của một phổ.
So the n-ary or the row storage, like putting all the data for a tuple contiguous to each other.
Một bên là n-ary hay row storage, tức là đặt toàn bộ dữ liệu của một tuple liền kề nhau.
In a decomposition storage model, which is the academic name, or the column store, we're actually going to split up all the data for each tuple and store their attributes separately.
Trong decomposition storage model, đây là tên gọi học thuật, hay column store, chúng ta sẽ tách toàn bộ dữ liệu của mỗi tuple và lưu các thuộc tính của nó riêng rẽ.
But now we're going to, within our pages, we're just going to have the data for one attribute within the table. All those are going to be contiguous across multiple tuples.
Nhưng lúc này, bên trong các page của chúng ta, chúng ta chỉ có dữ liệu của một thuộc tính trong bảng. Tất cả chúng sẽ nằm liền kề nhau qua nhiều tuple.
So this can be better for analytical queries because, if I'm only going to access a small number of the attributes for a given tuple, I don't bring in pages that have data that I don't need.
Cách này có thể tốt hơn cho các truy vấn phân tích vì, nếu tôi chỉ truy cập một số ít thuộc tính của một tuple, tôi sẽ không phải nạp những trang chứa dữ liệu mà tôi không cần.
I only get exactly the data that I do need. Of course, now what's the challenge to this? What's the problem? Faster reads, slow for what? Writes. Because what do I need to do?
Tôi chỉ lấy đúng dữ liệu mà tôi cần. Tất nhiên, vậy thách thức ở đây là gì? Vấn đề là gì? Đọc nhanh hơn, nhưng chậm với việc gì? Ghi. Vì tôi cần làm gì?
If I insert a tuple, I have a thousand columns and I've got to break it up into a thousand different pieces and write out, to write to a thousand different pages.
Nếu tôi chèn một tuple, tôi có một nghìn cột và tôi phải tách nó thành một nghìn phần khác nhau rồi ghi ra, ghi vào một nghìn trang khác nhau.
And again, he was sort of asking about this, we'll see how to handle that later in today's lecture. So let's go back to our table here before.
Và như bạn ấy đã hỏi về vấn đề này, chúng ta sẽ xem cách xử lý nó ở phần sau của bài giảng hôm nay. Vậy ta quay lại bảng lúc nãy.
So we're going to store essentially all the data within each column; it's going to be fixed length, it's fixed length values stored in basically simple arrays.
Về cơ bản, ta sẽ lưu toàn bộ dữ liệu của mỗi cột; chúng có độ dài cố định, là các giá trị độ dài cố định được lưu trong những mảng đơn giản.
So I'm going to take this first column A, I'll have my first page, there'll be some header that says what's in the page, and then I'll have a null bitmap that's going to correspond to all the data within my, within this column for all the tuples.
Tôi lấy cột A đầu tiên này, tôi có trang đầu tiên, sẽ có một header cho biết trong trang có gì, rồi tôi có một null bitmap tương ứng với toàn bộ dữ liệu trong cột này của tất cả các tuple.
Remember, in the row storage model, every tuple had its own header. Inside that header it had its own little bitmap to say whether certain values are null or not.
Hãy nhớ, trong mô hình lưu trữ theo hàng, mỗi tuple có header riêng. Trong header đó có một bitmap nhỏ riêng để cho biết một số giá trị có null hay không.
So now I don't need to store a header per tuple, I just have a header for the single column, and that's enough to account for all the data within this.
Giờ tôi không cần lưu một header cho mỗi tuple, tôi chỉ có một header cho cả cột, và thế là đủ để quản lý toàn bộ dữ liệu trong đó.
And I'll do the same thing for the next column, and then the same thing for the next column. Right? So we go back now to our example before.
Và tôi làm tương tự với cột tiếp theo, rồi lại tương tự với cột kế tiếp. Đúng không? Giờ ta quay lại ví dụ lúc nãy.
So we take our Wikipedia data, we had for the login information, the user information, and again, instead of storing as a row store where all the data is contiguous across the tuple, we're now going to split it up so that all the hostname data will be in one page, all the login information will be in another page, all the password information will be in another page.
Ta lấy dữ liệu Wikipedia, có thông tin đăng nhập, thông tin người dùng, và một lần nữa, thay vì lưu theo kiểu row store trong đó toàn bộ dữ liệu của tuple nằm liền nhau, giờ ta sẽ tách ra để mọi dữ liệu hostname nằm trong một trang, mọi thông tin đăng nhập nằm trong một trang khác, mọi thông tin mật khẩu nằm trong một trang khác nữa.
Now they're all separate pages.
Giờ tất cả đều là các trang riêng biệt.
So now if I run that query before, where again I'm trying to find all the people logging in with the government hostname, so the first thing we need to do is look, okay, I gotta run this where clause here and I need to look up on the hostname attribute.
Giờ nếu tôi chạy truy vấn lúc nãy, trong đó tôi lại muốn tìm tất cả những người đăng nhập bằng hostname của chính phủ, thì việc đầu tiên cần làm là xem, được rồi, tôi phải chạy mệnh đề where này và cần tra cứu thuộc tính hostname.
So I just go get the one page, or the set of pages, that have that hostname information, go bring that into memory in my buffer pool, and then rip through that and find all my matches.
Vậy tôi chỉ lấy một trang, hoặc một tập các trang, chứa thông tin hostname đó, nạp nó vào bộ nhớ trong buffer pool của tôi, rồi quét nhanh qua và tìm tất cả các kết quả khớp.
Again, I'm not jumping over data that I don't need. I'm not jumping over username information or user ID. The pages I'm bringing in only have the hostname.
Một lần nữa, tôi không phải bỏ qua dữ liệu mà tôi không cần. Tôi không phải nhảy qua thông tin username hay user ID. Các trang tôi nạp vào chỉ có hostname.
So I can do that very efficiently and rip through that very fast.
Nên tôi có thể làm việc đó rất hiệu quả và quét qua rất nhanh.
So then I collect what tuples match my predicate and say, okay well, the next thing you need to do is run the aggregation and run the extract function.
Vậy là tôi thu thập các tuple khớp với vị từ của mình và nói, được rồi, việc tiếp theo cần làm là chạy phép tổng hợp và chạy hàm extract.
That's on the last login attribute.
Hàm đó áp dụng trên thuộc tính last login.
So I go fetch that page that has that information, and then now I know how to then jump into these different offsets, I'll explain that in
Vậy tôi đi lấy trang chứa thông tin đó, và giờ tôi biết cách nhảy tới các offset khác nhau này, Tôi sẽ giải thích điều đó
a little bit.
ngay sau đây.
So let's say I and I have a database and I have
Giả sử tôi và tôi có một cơ sở dữ liệu và tôi có
a database and I have a database and I and I have a and I have a database have
một cơ sở dữ liệu và tôi có một cơ sở dữ liệu và tôi và tôi có một và tôi có một cơ sở dữ liệu có
a database and I have a database and I have a database and I have a database and I have a database and I have a database and I have a and I have a database and I have a database
một cơ sở dữ liệu và tôi có một cơ sở dữ liệu và tôi có một cơ sở dữ liệu và tôi có một cơ sở dữ liệu và tôi có một cơ sở dữ liệu và tôi có một cơ sở dữ liệu và tôi có một và tôi có một cơ sở dữ liệu và tôi có một cơ sở dữ liệu
and I have a database and I database and I have a database have a database and I have
và tôi có một cơ sở dữ liệu và tôi cơ sở dữ liệu và tôi có một cơ sở dữ liệu có một cơ sở dữ liệu và tôi có
a database and I have a database And I have a database waste of money and threw all the code away
một cơ sở dữ liệu và tôi có một cơ sở dữ liệu Và tôi có một cơ sở dữ liệu, lãng phí tiền bạc và vứt hết mã nguồn đi
and started building the parallel data warehouse as a real column store. Actually, that was Jignesh Patel, the other data professor. That was his advisor, Dave DeWitt.
rồi bắt đầu xây dựng parallel data warehouse như một column store thực thụ. Thật ra đó là Jignesh Patel, giáo sư dữ liệu còn lại. Người hướng dẫn của ông ấy là Dave DeWitt.
Microsoft hired him to go take the guys that were doing this and make it actually production ready.
Microsoft thuê ông ấy để dẫn dắt nhóm người đang làm việc này và đưa nó đến mức sẵn sàng cho môi trường production.
He's like, this is total crap, and he told me, you're wasting your money, and they threw it all away. So don't do this. I'm just showing you could do this.
Ông ấy bảo, cái này tệ hết sức, và ông ấy nói với tôi, họ đang phí tiền, và rồi họ vứt bỏ hết. Nên đừng làm thế này. Tôi chỉ cho các bạn thấy là có thể làm vậy.
We want to do this one over here. But now the question is gonna be, okay, well, it only works if things are fixed length. For integers, that's fine. Floats, fixed length, fine.
Chúng ta muốn làm cách ở đằng này. Nhưng giờ câu hỏi là, được rồi, cách này chỉ hoạt động nếu các giá trị có độ dài cố định. Với số nguyên thì ổn. Số thực dấu phẩy động, độ dài cố định, cũng ổn.
The question is, why is this a bad idea? Because now I have to store an extra number for every single value that I'm actually storing.
Câu hỏi là, vì sao đây là ý tưởng tồi? Vì giờ tôi phải lưu thêm một con số cho từng giá trị mà tôi lưu.
Then I need to maintain a separate index in my file that says, here's how to jump to offset three. Because these things can be whatever arbitrary length that they want.
Rồi tôi cần duy trì một chỉ mục riêng trong tệp cho biết cách nhảy tới offset số ba. Vì những giá trị này có thể có độ dài tùy ý.
Because if I'm doing a match, if I'm scanning through, say, column D and I find a match, I'm scanning through the column, I find a match here.
Vì nếu tôi đang đối sánh, nếu tôi đang quét qua, chẳng hạn, cột D và tìm thấy một kết quả khớp, tôi đang quét qua cột và tìm thấy kết quả khớp ở đây.
I need to know, okay, well, this is three, so that when I jump over to column A, I know how to get to the three.
Tôi cần biết, được rồi, đây là vị trí số ba, để khi nhảy sang cột A, tôi biết cách đến vị trí số ba.
It's allowing me to stitch the tuples back together. Don't do this. Alright, so again, if we require all the values in our column be fixed length, how does this work?
Nó cho phép tôi ghép các tuple lại với nhau. Đừng làm thế này. Được rồi, vậy nếu ta yêu cầu mọi giá trị trong cột đều có độ dài cố định, thì điều này hoạt động thế nào?
We have strings. Well, we'll cover more about this in a few more slides, but the basic trick is we're gonna compress the data, convert anything that is variable length to fixed length.
Ta còn có các chuỗi. Ta sẽ nói kỹ hơn về việc này ở vài slide nữa, nhưng mẹo cơ bản là ta sẽ nén dữ liệu, chuyển mọi thứ có độ dài thay đổi thành độ dài cố định.
So we don't have this problem.
Nhờ vậy ta không gặp vấn đề này.
So that means any string is gonna be converted to a fixed length number, and then we'll have, basically, a dictionary lookup to say, okay, for this number, what's the original value?
Nghĩa là mọi chuỗi sẽ được chuyển thành một số có độ dài cố định, và sau đó về cơ bản ta có một phép tra cứu từ điển để cho biết, với con số này thì giá trị gốc là gì?
So we can store that as an auxiliary data structure on the side, But then as we rip through our columns, we're only looking at integers, and that's way faster.
Ta có thể lưu nó như một cấu trúc dữ liệu phụ bên cạnh. Nhưng khi ta quét nhanh qua các cột, ta chỉ nhìn vào các số nguyên, và như vậy nhanh hơn rất nhiều.
The alternative is you could just pad out the, the strings.
Cách khác là bạn có thể đệm thêm vào các chuỗi.
Like if it's a 32 character bar char, just always put a bunch of extra spaces at the end if it's not 32 characters so it always fits. But that's gonna be wasteful as well.
Ví dụ nếu là varchar 32 ký tự, thì luôn thêm một loạt dấu cách ở cuối nếu chuỗi không đủ 32 ký tự để nó luôn vừa. Nhưng cách đó cũng gây lãng phí.
Instead, the answer is gonna be dictionary compression. Again, we'll cover more about that in a few more slides.
Thay vào đó, câu trả lời là nén bằng từ điển (dictionary compression). Một lần nữa, ta sẽ nói kỹ hơn về nó ở vài slide nữa.
So to round out the DSM, to summarize it, the benefit we're gonna get is that we're gonna avoid wasted IO, because we're only gonna get the bare minimum in data we actually need to process the query.
Để khép lại phần DSM, tóm tắt lại, lợi ích ta có được là tránh được IO lãng phí, vì ta chỉ lấy lượng tối thiểu dữ liệu thực sự cần để xử lý truy vấn.
We're gonna bring that in and not bring in any other attributes that we don't care about.
Ta sẽ đưa phần đó vào và không đưa vào các thuộc tính khác mà ta không quan tâm.
The queries themselves are actually gonna execute faster, because now as we're ripping through the columns, we're kind of looking at contiguous data, like as strides in memory, and that's gonna be great for modern CPUs.
Bản thân các truy vấn cũng sẽ thực thi nhanh hơn, vì khi quét nhanh qua các cột, ta nhìn vào dữ liệu liên tục, như các bước nhảy đều trong bộ nhớ, và điều đó rất tốt cho các CPU hiện đại.
I know we said we were gonna talk about CPUs too much, but like Intel CPUs or modern superscalar CPUs, they don't want any branches. They don't want any jumps.
Tôi biết ta đã nói là sẽ không bàn quá nhiều về CPU, nhưng các CPU Intel hay các CPU superscalar hiện đại đều không muốn có rẽ nhánh. Chúng không muốn có các lệnh nhảy.
So if I can avoid if clauses, if I have to jump over things, my CPU is gonna be way faster because I'm not gonna have stalls in my pipeline.
Nên nếu tôi tránh được các mệnh đề if, tránh phải nhảy qua các thứ, CPU sẽ nhanh hơn rất nhiều vì không bị đình trệ trong đường ống.
So if all my data now is all contiguous and it's all in the same value domain, like I'm just looking at, like, looking at integers, then I can rip through that very, very quickly, and we'll see how we handle that in lecture 14.
Vậy nếu giờ toàn bộ dữ liệu liền kề nhau và cùng một miền giá trị, chẳng hạn tôi chỉ nhìn vào các số nguyên, thì tôi có thể quét qua chúng rất, rất nhanh, và ta sẽ xem cách xử lý việc đó ở bài giảng 14.
Furthermore, I can actually compress the data much better than I can in a row store, because now all the data within a page are gonna be in the same domain, right?
Hơn nữa, tôi có thể nén dữ liệu tốt hơn nhiều so với trong row store, vì giờ toàn bộ dữ liệu trong một trang đều thuộc cùng một miền, đúng không?
It's gonna be like, think of like the, if I'm recording the temperature for this room, If I just have my data pages just record temperatures, they're a bunch of integers, I can compress the hell out of that, way better than I could if, like, it had integers and strings and floats and a bunch of random stuff.
Hãy nghĩ như là, nếu tôi ghi lại nhiệt độ của căn phòng này, nếu các trang dữ liệu của tôi chỉ ghi nhiệt độ, tức là một loạt số nguyên, tôi có thể nén chúng cực kỳ hiệu quả, tốt hơn nhiều so với khi có lẫn số nguyên, chuỗi, số thực và đủ thứ linh tinh.
Like, it's thinking, like, trying to compress a JPEG.
Giống như việc cố nén một tệp JPEG vậy.
It doesn't, if you try to run a JPEG through, like, gzip or whatever, it doesn't do a very good job because it's kind of a bunch of random data that's already been compressed.
Nếu bạn thử cho một tệp JPEG qua gzip hay gì đó, nó làm không tốt lắm vì nó là một đống dữ liệu ngẫu nhiên vốn đã được nén rồi.
But if you open a text file and put a bunch of zeros in it and run that through gzip, it's gonna compress the hell out of it.
Nhưng nếu bạn mở một tệp văn bản rồi nhét vào đó một đống số không và cho chạy qua gzip, thì nó sẽ nén cực kỳ hiệu quả.
That's basically what we're gonna get with a column store. Of course, nothing's for free.
Về cơ bản đó là thứ chúng ta sẽ có với column store. Tất nhiên, không có gì là miễn phí.
It's gonna be slow for point queries, doing single tuple lookups, because now I got to stitch all the data back together from multiple pages. Inserts, deletes are gonna have the same problem, right?
Nó sẽ chậm với các truy vấn điểm, tức là tra cứu từng tuple đơn lẻ, vì bây giờ tôi phải ghép toàn bộ dữ liệu lại với nhau từ nhiều trang. Insert và delete cũng sẽ gặp vấn đề tương tự, đúng không?
Because you basically have to redo this stitching and splitting over and over again, okay? Any questions about column stores?
Vì về cơ bản bạn phải làm đi làm lại việc ghép và tách này, được chứ? Có câu hỏi nào về column store không?
So this is gonna be great for, again, if we have queries on tables that are very wide, meaning you have a lot of columns, and I'm only gonna touch a bare minimum number of attributes within that table.
Vậy nên cái này sẽ rất tốt, một lần nữa, nếu có các truy vấn trên những bảng rất rộng, nghĩa là có rất nhiều cột, và tôi chỉ đụng tới số thuộc tính tối thiểu trong bảng đó.
Best case scenario is an OLAP query that touches one column, right? But truth be told, those kind of queries are not that common.
Trường hợp tốt nhất là một truy vấn OLAP chỉ đụng tới một cột, đúng không? Nhưng nói thật thì những truy vấn kiểu đó không phổ biến lắm.
And so at some point, I'm gonna have to stitch my tuple back together, and so if my data is completely broken apart across multiple pages, if I break everything up as columns, then even though I may filter out a lot of data during the query, have a billion tuples, but I end up only needing a thousand tuples,
Và đến một lúc nào đó, tôi sẽ phải ghép tuple của mình lại, nên nếu dữ liệu của tôi bị tách hoàn toàn ra nhiều trang, nếu tôi chia mọi thứ theo cột, thì dù trong truy vấn tôi có thể lọc bỏ rất nhiều dữ liệu, có một tỉ tuple nhưng cuối cùng tôi chỉ cần một nghìn tuple,
I may have to go get all those thousand, for each tuple, a thousand different pages to put that tuple back together. And that's if I break everything up as fully as the column store.
tôi vẫn có thể phải đi lấy cả nghìn tuple đó, với mỗi tuple lại là một nghìn trang khác nhau để ghép tuple đó lại. Và đó là khi tôi chia mọi thứ triệt để như column store.
So what we really want is something that kind of smells like a column store.
Vì vậy, thứ chúng ta thực sự muốn là một cái gì đó hơi giống column store.
We get that benefit of not bringing in pages that we don't need, or looking at data that we don't need, and the data that is in the same column or same attribute is close to each other, so we get great compression.
Chúng ta có được lợi ích là không phải nạp những trang không cần, hay xem những dữ liệu không cần, và dữ liệu nằm trong cùng một cột hay cùng một thuộc tính thì nằm gần nhau, nên ta nén rất tốt.
But if I have to go get data from the other attributes for that tuple, they're close by, relatively close by, where I can go, I either already fetch them in memory, or it's not a big leap for me to go get them.
Nhưng nếu tôi phải lấy dữ liệu của các thuộc tính khác cho tuple đó, thì chúng nằm gần, tương đối gần, để tôi hoặc đã nạp sẵn chúng vào bộ nhớ, hoặc việc đi lấy chúng cũng không quá xa.
So this is what the hybrid storage approach, storage model, called PAX supports. So PAX stands for partition attributes across. This was actually, there's a paper came out in the 2000, 2001.
Đây chính là điều mà cách tiếp cận lưu trữ lai, mô hình lưu trữ có tên PAX, hỗ trợ. PAX là viết tắt của partition attributes across. Thực ra có một bài báo ra đời khoảng năm 2000, 2001.
The first author is Natassa Ailamaki.
Tác giả đầu là Natassa Ailamaki.
She was the database professor here at CMU before I started, and she left for Switzerland, she's brilliant, she left for Switzerland in 2007, and then I was hired to replace her.
Cô là giáo sư cơ sở dữ liệu ở CMU trước khi tôi bắt đầu, và cô chuyển sang Thụy Sĩ, cô ấy rất xuất sắc, cô chuyển sang Thụy Sĩ năm 2007, và sau đó tôi được thuê để thay cô.
So this claims it was, the paper looks like it was came from CMU, but this actually wasn't, the last chapter of the thesis she did at the University of Wisconsin with Dave DeWitt, the guy who, I just told you, told Microsoft they wasted 200 million dollars buying that company.
Bài báo trông như xuất phát từ CMU, nhưng thực ra không phải, đó là chương cuối luận án cô làm ở Đại học Wisconsin với Dave DeWitt, người mà tôi vừa kể, đã nói với Microsoft rằng họ phí 200 triệu đô la khi mua công ty đó.
So she, he was her advisor. He's brilliant.
Ông là người hướng dẫn của cô. Ông ấy rất xuất sắc.
All right, so this approach basically is, the idea is that it's gonna look like a column store, but the data for a single tuple is gonna be close enough to each other, so that I don't have to make a very long, I may have already brought that data into memory, even though I may not need all of it.
Được rồi, vậy cách tiếp cận này về cơ bản là, ý tưởng là nó sẽ trông giống như một column store, nhưng dữ liệu của một tuple đơn lẻ sẽ nằm đủ gần nhau, để tôi không phải thực hiện một lần đọc rất xa, vì có thể tôi đã đưa dữ liệu đó vào bộ nhớ rồi, dù có thể tôi không cần tất cả.
So again, most systems when they say they're gonna use a column store, almost 99 percent of the time they're doing this.
Vậy nên, hầu hết các hệ thống khi nói họ dùng column store, thì gần 99 phần trăm trường hợp là họ làm như thế này.
I can only think of one or two systems that don't do this, but everyone else would do this.
Tôi chỉ nghĩ ra một hoặc hai hệ thống không làm vậy, còn tất cả những hệ thống khác đều làm như thế.
And then these open source file formats, like Parquet and ORC, that you might be familiar with, and now there's modern versions of these, like Nimble from Facebook, or Vortex from the SpiralDB guys, where these are all essentially doing this.
Và rồi các định dạng tệp mã nguồn mở như Parquet và ORC, mà có thể các em đã quen thuộc, và giờ có những phiên bản hiện đại hơn, như Nimble của Facebook, hay Vortex của nhóm SpiralDB, tất cả những thứ này về cơ bản đều làm như vậy.
So if we go back to our diagram here, again, what we're now gonna do, we're going to horizontally partition, horizontally split up the data based on some criteria, like the number of tuples, or the size of the data, right?
Vậy nếu quay lại sơ đồ của chúng ta, giờ chúng ta sẽ phân vùng theo chiều ngang, chia nhỏ dữ liệu theo chiều ngang dựa trên một tiêu chí nào đó, như số lượng tuple, hoặc kích thước dữ liệu, đúng không?
There's some way to say, okay, here's gonna be some chunk of data, or sorry, some region of data.
Có một cách nào đó để nói, được rồi, đây sẽ là một phần dữ liệu, hoặc xin lỗi, một vùng dữ liệu.
And then now, we're gonna then write them out within that region to be a single column store, sorry, in a columnar format.
Và sau đó, chúng ta sẽ ghi dữ liệu bên trong vùng đó thành một column store đơn lẻ, xin lỗi, theo định dạng cột.
But again, within that sort of region, all the data for a single tuple will be located close to each other.
Nhưng một lần nữa, bên trong vùng đó, toàn bộ dữ liệu của một tuple sẽ nằm gần nhau.
So when you create this PAX file, you end up writing the header at the end, and we're gonna do this because, think of like, we're trying to generate, you know, a one gigabyte file, so I don't actually know what all the data is gonna be in before I actually scan it.
Khi tạo tệp PAX này, cuối cùng bạn sẽ ghi header ở cuối tệp, và chúng ta làm vậy vì hãy hình dung là chúng ta đang cố tạo ra, ví dụ, một tệp một gigabyte, nên tôi thực ra không biết toàn bộ dữ liệu sẽ là gì trước khi quét nó.
So I'll keep track of things in memory, and then when I'm finished, I write out the footer that has all this metadata, right? So I'm showing it appearing first.
Vì vậy tôi theo dõi mọi thứ trong bộ nhớ, và khi xong, tôi ghi footer chứa toàn bộ siêu dữ liệu này, đúng không? Ở đây tôi vẽ nó xuất hiện đầu tiên.
This is actually the last thing you would write when you create one of these files. So the first thing, again, I'll break up the, say, the first three tuples, I'll put in some chunk.
Thực ra đây là thứ cuối cùng bạn ghi khi tạo một tệp như thế này. Vậy đầu tiên, tôi sẽ chia nhỏ, giả sử ba tuple đầu tiên, tôi đặt vào một khối nào đó.
I'm gonna call it a block of data. I'm trying to use generic terms. And in Parquet, they call them a row group, that's considered the canonical term.
Tôi gọi nó là một block dữ liệu. Tôi đang cố dùng các thuật ngữ chung. Còn trong Parquet, họ gọi nó là row group, đây được coi là thuật ngữ chuẩn.
Basically, it's, again, it's just some, some set of tuples I'm gonna put together in a single, I don't get it, I don't want to use the word cluster, in a single region within the file.
Về cơ bản, đó chỉ là một tập các tuple mà tôi gom lại với nhau trong một, tôi không muốn dùng từ cluster, trong một vùng duy nhất của tệp.
Again, in Parquet, it's like, I think it's like 1 million tuples. In ORC, it's like, by default, like 100 megs of data.
Trong Parquet, tôi nghĩ là khoảng 1 triệu tuple. Trong ORC, mặc định là khoảng 100 megabyte dữ liệu.
There's different criteria to decide how you, how you partition these things up.
Có nhiều tiêu chí khác nhau để quyết định cách phân vùng những thứ này.
So again, within now my row group, I'll have this, another header that says, here's all the data within it, and then within the, inside of it, you'll see I put all the data for column A together, all the data for column B together, and all the data in column C, right?
Vậy bên trong row group của tôi, sẽ có một header khác cho biết toàn bộ dữ liệu bên trong nó, và rồi bên trong, bạn sẽ thấy tôi đặt toàn bộ dữ liệu của cột A cùng nhau, toàn bộ dữ liệu cột B cùng nhau, và toàn bộ dữ liệu cột C, đúng không?
And I'll call these, sort of, these, these column pieces within the row group, we call these, they're called column chunks. And I'll do the same thing for the next one, right?
Và tôi sẽ gọi những phần cột này bên trong row group, chúng được gọi là column chunk. Và tôi sẽ làm tương tự với row group tiếp theo, đúng không?
And each row group is gonna have their own, again, metadata keeps track of like, I'm compressing this way, or here's the, here's the dictionary you can use to express this data, right?
Và mỗi row group sẽ có riêng, một lần nữa, siêu dữ liệu để theo dõi, kiểu như: tôi đang nén theo cách này, hoặc đây là từ điển bạn có thể dùng để biểu diễn dữ liệu này, đúng không?
So if you go look at, like, any presentation from Databricks, or Snowflake, or other companies, right, when they talk about Parquet organization, it's roughly gonna look like this, and they're talking about packs, right?
Vậy nếu bạn xem bất kỳ bài thuyết trình nào của Databricks, hay Snowflake, hoặc các công ty khác, đúng không, khi họ nói về cách tổ chức Parquet, thì đại khái nó sẽ trông như thế này, và họ gọi chúng là pack, đúng không?
Is this clear?
Chỗ này rõ chưa?
So again, don't think of these as, in, like, in the OLTP world, we talked about, like, the, the page sizes, there's always some multiple of four, like, 4 kilobyte, 8 kilobyte, 16 kilobyte pages.
Nên một lần nữa, đừng nghĩ chúng giống như, trong thế giới OLTP, chúng ta đã nói về kích thước trang, luôn là một bội số của bốn, kiểu như, trang 4 kilobyte, 8 kilobyte, 16 kilobyte.
In the OLAP world, I'm reading large amounts of data, so it's usually these things are, like, organized in the size of, like, S3 buckets, like 8 megabytes or larger.
Trong thế giới OLAP, tôi đọc một lượng dữ liệu lớn, nên thường các thứ này được tổ chức theo kích thước cỡ như các S3 bucket, như 8 megabyte hoặc lớn hơn.
I'm trying to get a lot of data all at once, and so even though I'm saying this row group here might be kind of big, much larger than 48 kilobytes, and maybe I'm bringing in data that I don't actually need, it's still gonna be a big win if I have to stitch things together.
Tôi muốn lấy thật nhiều dữ liệu cùng một lúc, và vì vậy dù tôi nói row group này ở đây có thể khá lớn, lớn hơn nhiều so với 48 kilobyte, và có thể tôi đang đưa vào cả dữ liệu mà thực ra tôi không cần, thì vẫn có lợi lớn so với việc phải ghép các thứ lại với nhau.
The question is, what goes into deciding what the number of rows in a column chunk? Maybe it's a number of rows in a row group.
Câu hỏi là, điều gì quyết định số hàng trong một column chunk? Có lẽ ý bạn là số hàng trong một row group.
I said, like, the default in Parquet is, like, 1 million, and it's just whatever they picked it, and then I think ORC goes by, like, data size.
Tôi đã nói mặc định trong Parquet là khoảng 1 triệu, và đó chỉ là con số họ chọn, còn ORC thì tôi nghĩ tính theo kích thước dữ liệu.
So as I'm writing it out, if I wrote out, like, 100 megs, say, okay, that's it. Make a new row group. But you can tweak those.
Nên khi ghi ra, nếu tôi đã ghi khoảng 100 meg chẳng hạn, thì thôi, đủ rồi. Tạo một row group mới. Nhưng bạn có thể tinh chỉnh các giá trị đó.
Yes. Yes.
Vâng. Vâng.
Statement is, um, your statement is, like, the row group metadata is wasteful?
Ý bạn là siêu dữ liệu của row group gây lãng phí phải không?
The statement is that the metadata across row groups could be repetitive, then we have a lot of wasted data.
Ý bạn là siêu dữ liệu giữa các row group có thể bị lặp lại, nên chúng ta có nhiều dữ liệu bị lãng phí.
For dictionaries, yes, but the metadata is not that big compared to the rest of the data. Like, if it's a kilobyte and your data is, like, 100 megabytes, it's nothing.
Với các từ điển thì đúng vậy, nhưng siêu dữ liệu không lớn so với phần dữ liệu còn lại. Ví dụ nếu nó là một kilobyte còn dữ liệu của bạn khoảng 100 megabyte thì chẳng đáng kể.
Yes.
Vâng.
Yeah, yeah, good, okay. So the statement is, and he's correct, this is my fault. So I'm saying this is a PAX file organization, it is not page organization.
Ừ, đúng, được rồi. Ý bạn là, và bạn nói đúng, đây là lỗi của tôi. Tôi nói đây là tổ chức tệp PAX, chứ không phải tổ chức theo trang.
Yeah, so you could think of, like, here's a file, and then within that I have different pages, and those pages will all be sort of fixed length, right?
Đúng, nên bạn có thể hình dung là, đây là một tệp, và bên trong đó tôi có các trang khác nhau, và các trang đó đều có độ dài cố định, đúng không?
Within the row group, the metadata stuff at the bottom is usually whatever the size is, but you might still organize that in four kilobyte pages.
Bên trong row group, phần siêu dữ liệu ở cuối thường có kích thước tùy ý, nhưng bạn vẫn có thể tổ chức nó thành các trang 4 kilobyte.
But yeah, you can think of, like, I'm not defining what the size of the pages are within a column chunk within a row group, but at the end of the day, when it lands on disk, it's still gonna be four kilobytes, but the database might perceive it as, like, what, eight megabytes or one megabyte or something like that, like a larger size.
Nhưng đúng vậy, bạn có thể hình dung là tôi không định nghĩa kích thước của các trang bên trong một column chunk trong một row group, nhưng cuối cùng thì, khi nó nằm trên đĩa, nó vẫn sẽ là bốn kilobyte, nhưng hệ cơ sở dữ liệu có thể nhìn nhận nó như là, kiểu như, tám megabyte hay một megabyte gì đó, tức là một kích thước lớn hơn.
It's not, everything is, you always just split in pages. Yes. But the way, typically, in a Parquet file systems address it, it would be at the row group level.
Không phải vậy, mọi thứ, lúc nào bạn cũng chỉ chia thành các trang. Vâng, mời bạn. Nhưng cách mà thông thường các hệ thống dùng file Parquet xử lý việc này, là ở mức row group.
So then you have to read the row group header, because that's what's gonna tell you what the offsets are for the column chunks.
Vì vậy bạn phải đọc phần header của row group, bởi vì chính nó sẽ cho bạn biết các offset của những column chunk.
So you can do things like, if I only need column A from this row group, I could go read this, that tells me where the starting point is for each row group, and then I could jump to get the header for that row group, and with that, I can then get the offset to the column chunk that I want.
Nhờ đó bạn có thể làm những việc như, nếu tôi chỉ cần cột A từ row group này, tôi có thể đọc phần này, phần này cho tôi biết điểm bắt đầu của từng row group, rồi tôi có thể nhảy tới để lấy header của row group đó, và từ đó, tôi lấy được offset của column chunk mà tôi muốn.
You could store that down here, but then that makes this thing kind of bigger. Now we're getting into implementation details, but in the case of Parquet, this is implemented as protobuf.
Bạn có thể lưu thông tin đó ở dưới này, nhưng như vậy sẽ làm phần này lớn hơn. Giờ chúng ta đang đi vào các chi tiết cài đặt, nhưng với Parquet, phần này được cài đặt bằng protobuf.
The protobuf, you can't deserialize incrementally, it deserializes the whole thing.
Với protobuf, bạn không thể giải tuần tự hóa từng phần, nó giải tuần tự hóa toàn bộ.
So if I have all my metadata inside this, and this thing's like 10 megabytes, I gotta decompress 10 megs, even though I only need like 10 bytes out of it.
Nên nếu toàn bộ metadata của tôi nằm trong này, và nó nặng cỡ 10 megabyte, thì tôi phải giải nén 10 megabyte, dù tôi chỉ cần khoảng 10 byte trong đó.
That's in the weeds.
Đó là chuyện quá chi tiết rồi.
The newer file formats replace protobuf with FlatBuffers from Google. That's the right way to do it. Okay. All right. So let's try to plow through compression real quickly.
Các định dạng file mới hơn thay protobuf bằng FlatBuffers của Google. Đó mới là cách làm đúng. Được rồi. Okay. Giờ chúng ta thử đi thật nhanh qua phần nén dữ liệu.
So at the end of the day, the I/O bottleneck for this class here, what we're talking about in this semester, the I/O cost is always going to be the main bottleneck when you actually want to run queries.
Rốt cuộc thì, nút thắt cổ chai I/O đối với môn học này, tức là những gì chúng ta nói đến trong học kỳ này, chi phí I/O luôn là nút thắt cổ chai chính khi bạn thực sự muốn chạy truy vấn.
In the advanced class, we'll start working on cache lines and other things, but for this class, we'll assume it's always disk, right?
Trong lớp nâng cao, chúng ta sẽ bắt đầu làm việc với cache line và những thứ khác, nhưng với lớp này, ta sẽ giả định lúc nào cũng là đĩa, đúng không?
And especially if you're running in the cloud and the disk is like some box running over the network, that can get slow. And again, that's going to be a problem.
Và đặc biệt là nếu bạn chạy trên đám mây và đĩa là một máy nào đó chạy qua mạng, thì có thể sẽ chậm. Và đó lại là một vấn đề.
So what we want to be able to do is that we want to compress our pages when we write them out to disk, so that when we read them back in in compressed form, the amount of useful data we're getting from one I/O increases.
Vì vậy điều chúng ta muốn làm là nén các trang của mình khi ghi chúng xuống đĩa, để khi đọc lại ở dạng đã nén, lượng dữ liệu hữu ích nhận được từ một lần I/O tăng lên.
So if, like, a page is uncompressed, I can put 10 tuples in it, but if I can compress it and I can put 100 tuples in it, now for the same I/O with compressed data, I can get 100 tuples and bring them to memory.
Ví dụ, nếu một trang không nén thì tôi chỉ chứa được 10 tuple, nhưng nếu nén được và chứa được 100 tuple, thì với cùng một lần I/O trên dữ liệu đã nén, tôi lấy được 100 tuple và đưa chúng vào bộ nhớ.
Now I have the space for it for memory to deal with it. In some cases, you actually don't need to decompress it. We'll see how to handle that.
Lúc này tôi có đủ chỗ trong bộ nhớ để xử lý chúng. Trong một số trường hợp, bạn thậm chí không cần giải nén. Chúng ta sẽ xem cách xử lý việc đó.
But the main trade-off we're going to face here is sort of classic computer science, where it'd be speed versus, or compute versus, storage.
Nhưng sự đánh đổi chính mà chúng ta sẽ gặp ở đây là một kiểu kinh điển của khoa học máy tính, đó là tốc độ so với, hay tính toán so với, lưu trữ.
So I can pay more CPU costs to compress my data and decompress it when I need to access it, in exchange for having a lower storage overhead and lower I/O cost to get data in and out.
Tôi có thể trả thêm chi phí CPU để nén dữ liệu và giải nén khi cần truy cập, để đổi lấy chi phí lưu trữ thấp hơn và chi phí I/O thấp hơn khi đưa dữ liệu vào và ra.
So the things we're going to want in our compression scheme in our data system is, number one, we have to make sure that our values, or our compression scheme, always can produce fixed-length values.
Vậy những điều chúng ta muốn có ở một lược đồ nén trong hệ thống dữ liệu là, thứ nhất, phải đảm bảo rằng các giá trị của chúng ta, hay lược đồ nén của chúng ta, luôn tạo ra các giá trị có độ dài cố định.
So we need that in order for the offset mechanism to work to address tuples within a column.
Chúng ta cần điều đó để cơ chế offset có thể hoạt động khi định vị các tuple trong một cột.
Because if now, if I'm taking, like, 32-bit integers and I compress them and now they're like some are 16-bit, some are 24-bits, I have no way to know how to jump to offset 1, 2, 3 to find the data that I'm looking for.
Vì nếu bây giờ tôi lấy các số nguyên 32-bit rồi nén chúng, và giờ có cái là 16-bit, có cái là 24-bit, thì tôi không có cách nào biết cách nhảy tới offset 1, 2, 3 để tìm dữ liệu mà tôi đang cần.
I got to then use an index, and I don't want to have to do that. So all our data needs to be fixed-length.
Khi đó tôi phải dùng một index, và tôi không muốn phải làm vậy. Vì thế toàn bộ dữ liệu của chúng ta cần có độ dài cố định.
Variable-length data, we're going to store as a separate pages or a separate storage pool. And that we can run whatever compression scheme you want on that, and let that be variable-length.
Còn dữ liệu có độ dài thay đổi, chúng ta sẽ lưu trong các page riêng hoặc một vùng lưu trữ riêng. Và trên đó bạn có thể chạy lược đồ nén nào tùy thích, và để nó có độ dài thay đổi.
We don't care about that. Not entirely true, but for our class, yes.
Chúng ta không quan tâm đến phần đó. Không hoàn toàn đúng, nhưng với lớp này thì đúng.
Another thing we want to be able to do is Postpone when we actually have to decompress data in order to be able to use it or give it back to the user as part of the result of the query.
Một điều nữa chúng ta muốn làm được là trì hoãn thời điểm thực sự phải giải nén dữ liệu để có thể dùng nó hoặc trả lại cho người dùng như một phần kết quả của truy vấn.
So that means that we want to be able to run queries directly on compressed data and then not have to decompress it to figure out what's actually inside that compressed data.
Nghĩa là chúng ta muốn chạy truy vấn trực tiếp trên dữ liệu đã nén mà không phải giải nén để biết bên trong dữ liệu đã nén đó thực sự có gì.
And the last one should be sort of obvious, but that we want to make sure that whatever compression scheme we're using is considered lossless. What does that mean? Like lossy versus lossless? Yes.
Và điều cuối cùng có lẽ khá hiển nhiên, đó là chúng ta muốn đảm bảo rằng bất kỳ lược đồ nén nào mình dùng đều được coi là không mất mát (lossless). Điều đó nghĩa là gì? Lossy so với lossless là sao? Mời bạn.
You said, yeah, basically if you compress data and then you decompress it, I get the exact same data back. I get exact same bits. That's considered a lossless scheme.
Bạn nói đúng, về cơ bản nếu bạn nén dữ liệu rồi giải nén, tôi nhận lại đúng dữ liệu y như cũ. Tôi nhận lại đúng từng bit. Đó là lược đồ không mất mát.
A lossy scheme would be something like MP4, MP3, where I can take a video file or a sound file and compress that in such a way that it's not perceptible as humans, either through our eyes or through our ears, because we can't detect things that are throwing away.
Lược đồ có mất mát (lossy) thì giống như MP4, MP3, nơi tôi có thể lấy một tệp video hay âm thanh và nén theo cách mà con người không nhận ra được, dù bằng mắt hay bằng tai, vì chúng ta không phát hiện được những thứ bị loại bỏ.
But it's not an exact copy of the data we had before. So we don't want to do any lossy compression. We only do lossless.
Nhưng nó không phải bản sao chính xác của dữ liệu trước đó. Vì vậy chúng ta không dùng nén có mất mát. Chúng ta chỉ dùng nén không mất mát.
You can do lossy compression on data systems, but this is something a human has to tell us to do.
Bạn có thể nén có mất mát trong các hệ thống dữ liệu, nhưng đó là việc con người phải yêu cầu chúng ta làm.
So an example I always like to use is, say I'm recording the temperature in this room at one second granularity for an entire year.
Một ví dụ tôi luôn thích dùng là, giả sử tôi ghi nhiệt độ trong căn phòng này với độ chi tiết một giây trong suốt cả năm.
But maybe a year from now, I don't need to know exactly what is the temperature at this time, at this exact moment, at this given second.
Nhưng có thể một năm sau, tôi không cần biết chính xác nhiệt độ vào lúc này là bao nhiêu, vào đúng thời điểm này, ở giây cụ thể này.
I maybe can bucket the data within 10-minute aggregations. So if I do that and delete the one-second data, that's a lossy scheme, because now I'm throwing away the original data.
Có lẽ tôi có thể gom dữ liệu thành các tổng hợp theo khoảng 10 phút. Nếu làm vậy và xóa dữ liệu một giây, đó là lược đồ có mất mát, vì giờ tôi đã bỏ đi dữ liệu gốc.
But for my use case, that might be good enough. So data systems will do lossy compression for you, but you have to tell it you want to do that.
Nhưng với trường hợp sử dụng của tôi, như vậy có thể là đủ tốt. Vì thế các hệ thống dữ liệu sẽ nén có mất mát cho bạn, nhưng bạn phải nói với nó rằng bạn muốn làm vậy.
There's even other techniques where you can actually keep the data in its original form, but then run lossy algorithms on them to compute queries, called approximate query execution, where you get estimates of things that sometimes give you bounds.
Thậm chí còn có những kỹ thuật khác cho phép ta giữ nguyên dữ liệu ở dạng gốc, nhưng sau đó chạy các thuật toán có mất mát trên đó để tính toán truy vấn, gọi là thực thi truy vấn xấp xỉ (approximate query execution), trong đó ta nhận được các ước lượng, và đôi khi có cả các cận.
But again, we'll worry about that later. For this class, this lecture today, we can't lose data. So there's four different choices we have to compress things.
Nhưng một lần nữa, chúng ta sẽ bàn đến chuyện đó sau. Với môn học này, với bài giảng hôm nay, chúng ta không được làm mất dữ liệu. Vậy có bốn lựa chọn khác nhau để nén dữ liệu.
The first is the block level and the page level, where basically it's taking a page of data and we're going to compress it.
Lựa chọn đầu tiên là mức khối và mức trang, về cơ bản là lấy một trang dữ liệu và nén nó lại.
The tuple level, we're going to take the entire tuple itself and compress that, and you can only really do this in a column store.
Mức tuple thì ta lấy toàn bộ tuple và nén nó, và thực sự chỉ làm được điều này trong column store.
The attribute would take a single value within a single column for a single tuple, and we'll compress that individually. We saw that before with the overflow pages for large varchars and text fields.
Mức thuộc tính thì lấy một giá trị đơn lẻ trong một cột của một tuple, và nén riêng từng giá trị đó. Chúng ta đã thấy điều này trước đây với các trang tràn cho varchar lớn và các trường text.
Postgres will store it in this thing called TOAST. It's separate pages that then runs like gzip on that and compresses that, but it'll only do that for a single attribute.
Postgres sẽ lưu chúng trong thứ gọi là TOAST. Đó là các trang riêng, rồi chạy gzip trên đó để nén, nhưng nó chỉ làm vậy cho một thuộc tính đơn lẻ.
And the last one is going to be columnar compression, and we'll spend most of our time on that, but that will get the biggest win for using DSM or PAX.
Và lựa chọn cuối cùng là nén theo cột, và chúng ta sẽ dành phần lớn thời gian cho nó, vì nó mang lại hiệu quả lớn nhất khi dùng DSM hoặc PAX.
So pretty much every system today that's using a column store is going to use this bottom one. The subsystems will give you the third one. The second one is pretty rare.
Hầu như mọi hệ thống ngày nay dùng column store đều dùng lựa chọn cuối cùng này. Các hệ thống con sẽ cung cấp cho bạn lựa chọn thứ ba. Lựa chọn thứ hai khá hiếm.
I know one system out of China called Terark. They got bought by ByteDance, and the guy was unhappy with having it at ByteDance, and he has a new startup.
Tôi biết một hệ thống từ Trung Quốc tên là Terark. Họ được ByteDance mua lại, và anh chàng đó không hài lòng khi làm ở ByteDance nên anh ấy lập một startup mới.
I forget what it's called, but they can do tuple level compression. His website has him complaining about a parking ticket or something.
Tôi quên tên nó rồi, nhưng họ có thể nén ở mức tuple. Trang web của anh ấy có đoạn anh ấy phàn nàn về một vé phạt đỗ xe hay gì đó.
It's in Chinese. I can't read it, but I can post it on Piazza. And then block level, we'll talk about real quickly. This is rare, but to me, this is interesting too.
Nó bằng tiếng Trung. Tôi không đọc được, nhưng tôi có thể đăng lên Piazza. Còn mức khối thì chúng ta sẽ nói qua thật nhanh. Cái này hiếm, nhưng với tôi thì nó cũng thú vị.
So for this, we're going to use what I'll call a naive compression scheme or a general purpose one, where it's: pick your off-the-shelf algorithm, Gzip, Zstandard, LZ4, Snappy, whatever.
Với lựa chọn này, chúng ta sẽ dùng thứ mà tôi gọi là sơ đồ nén ngây thơ (naive) hay sơ đồ đa dụng, tức là: chọn một thuật toán có sẵn, Gzip, Zstandard, LZ4, Snappy, gì cũng được.
Just take your block of data, run it through the compression scheme, and you get a compressed block out.
Chỉ cần lấy khối dữ liệu của bạn, cho chạy qua sơ đồ nén, và bạn nhận được một khối đã nén.
And it's going to be variable length, and we'll have to account for that in a second.
Và nó sẽ có độ dài thay đổi, chúng ta sẽ phải xử lý điều đó ngay sau đây.
But in general, this is going to be just take whatever data you want and throw it at it, right?
Nhưng nhìn chung, cách này là cứ lấy dữ liệu nào bạn muốn rồi ném vào đó, đúng không?
Oracle, of course, has their own compression scheme that's patented, so nobody else can use it, called OZip.
Dĩ nhiên Oracle có sơ đồ nén riêng được cấp bằng sáng chế, nên không ai khác dùng được, gọi là OZip.
But again, the trade-off is going to be, as with any compression scheme, how fast we can encode and decode and how good our compression scheme is going to be.
Nhưng một lần nữa, sự đánh đổi, như với bất kỳ sơ đồ nén nào, sẽ là chúng ta mã hóa và giải mã nhanh đến đâu và sơ đồ nén của chúng ta tốt đến mức nào.
So let me show you what MySQL does in InnoDB. So with MySQL, you have compressed pages on disk, and these are going to be at some multiple.
Giờ để tôi cho các bạn xem MySQL làm gì trong InnoDB. Với MySQL, bạn có các trang nén trên đĩa, và kích thước của chúng sẽ là một bội số nào đó.
The size of these pages is going to be some multiple of eight. By default, InnoDB has 16 kilobyte page sizes, but if you compress them, it'll be within one of these ranges.
Kích thước của các trang này sẽ là bội số của tám. Theo mặc định, InnoDB có kích thước trang là 16 kilobyte, nhưng nếu bạn nén chúng, kích thước sẽ nằm trong một trong các khoảng này.
So if you compress your page and it's like 900 bytes, they'll just pad it up and round it up to be one kilobyte, right? Pick whatever the greatest size is.
Vậy nếu bạn nén trang và nó chỉ còn khoảng 900 byte, họ sẽ đệm thêm và làm tròn lên thành một kilobyte, đúng không? Chọn kích thước lớn nhất phù hợp.
And then on top of every page, in the header, there's this thing called the mod log, where it's like the write-ahead log, where you're going to record any changes that you make to the page, but that you haven't applied, because you wanted to keep the data compressed.
Và ở trên cùng của mỗi trang, trong phần header, có một thứ gọi là mod log, giống như nhật ký ghi trước (write-ahead log), nơi bạn ghi lại mọi thay đổi mà bạn thực hiện lên trang, nhưng chưa áp dụng, vì bạn muốn giữ dữ liệu ở dạng nén.
So now if I go to access a page, just like before, my buffer pool goes out, or uses the disk scheduler, goes out and gets it from disk, brings it into memory, and it starts off in compressed form.
Giờ nếu tôi truy cập một trang, cũng như trước, buffer pool của tôi sẽ đi ra, hoặc dùng bộ lập lịch đĩa, lấy nó từ đĩa, đưa vào bộ nhớ, và ban đầu nó ở dạng nén.
So now if I have a write operation that wants to make a change to the tuple that's in this compressed page, Assuming I have an index to tell me how to get there, then in some cases, I don't actually have to decompress the data.
Giờ nếu tôi có một thao tác ghi muốn thay đổi tuple nằm trong trang nén này, giả sử tôi có một chỉ mục cho biết cách tìm tới đó, thì trong một số trường hợp, tôi thực sự không phải giải nén dữ liệu.
But if I'm updating the login field for someone logging in on Wikipedia, I don't need to know what the old value was in order to make that write.
Ví dụ nếu tôi cập nhật trường đăng nhập khi ai đó đăng nhập vào Wikipedia, tôi không cần biết giá trị cũ là gì để thực hiện việc ghi đó.
I just overwrite whatever the old one was. So I can put a log record in the mod portion that says, "Hey, for this tuple, update it with this new value for this attribute."
Tôi chỉ ghi đè lên giá trị cũ. Vì vậy tôi có thể đặt một bản ghi log vào phần mod, nói rằng: "Này, với tuple này, hãy cập nhật thuộc tính này bằng giá trị mới này."
I can do much more writes to my mod log. At some point, the mod log gets full, and I'll have to decompress it and apply the changes.
Tôi có thể ghi thêm nhiều lần nữa vào mod log. Đến một lúc nào đó, mod log đầy, và tôi sẽ phải giải nén rồi áp dụng các thay đổi.
But for some updates, I don't have to. But now if I want to do a read, it's the write-ahead log.
Nhưng với một số cập nhật, tôi không phải làm vậy. Nhưng giờ nếu tôi muốn đọc, thì đó là write-ahead log.
Remember how in the LSM, we just had these records that say update this, put that, right? Same thing. Write-ahead log, and we'll cover this later.
Nhớ lại trong LSM, chúng ta có các bản ghi nói là cập nhật cái này, đặt cái kia, đúng không? Tương tự. Write-ahead log, và chúng ta sẽ học phần này sau.
It's basically the operations that change the data. Yes.
Về cơ bản đó là các thao tác làm thay đổi dữ liệu. Vâng, mời bạn.
The question is, does a mod log exist only if you have log storage? No. NDB is not log storage, but it has it here.
Câu hỏi là, mod log chỉ tồn tại nếu bạn dùng lưu trữ kiểu log phải không? Không. NDB không phải lưu trữ kiểu log, nhưng vẫn có nó ở đây.
And we'll see this again when we talk about a DeltaStore.
Và chúng ta sẽ gặp lại điều này khi nói về DeltaStore.
It's a common approach where you have an area where you can put fast inserts of changes that actually may be applying them to the data, because that's really fast to do that.
Đây là cách tiếp cận phổ biến, trong đó bạn có một vùng để chèn nhanh các thay đổi mà thực ra có thể là áp dụng chúng vào dữ liệu, vì làm vậy rất nhanh.
And then you have some background process fix it up. That's a common approach in systems. Yes.
Rồi sau đó có một tiến trình nền sửa lại cho gọn. Đó là cách tiếp cận phổ biến trong các hệ thống. Vâng.
You said the word level. Don't think of log structure as storage. Just think of every page has its own mod log. And I could put changes in there.
Bạn đã nói từ "level". Đừng coi cấu trúc log là lưu trữ. Chỉ cần nghĩ mỗi trang có mod log riêng, và tôi có thể đặt các thay đổi vào đó.
And at some point, if the mod log is full, I have to decompress and apply it and clear out the mod log.
Và đến một lúc nào đó, nếu mod log đầy, tôi phải giải nén, áp dụng nó rồi xóa sạch mod log.
It's just a way to absorb updates to a page, if I can, without having to decompress it.
Đó chỉ là một cách để hấp thụ các cập nhật cho một trang, nếu có thể, mà không phải giải nén nó.
The question is, will this stall writes if I have to write the mod log to apply the mod log? Absolutely. Yes. No free lunch. Yeah. All right. Yes.
Câu hỏi là, liệu việc này có làm đình trệ các thao tác ghi không, nếu tôi phải ghi mod log để áp dụng mod log? Chắc chắn rồi. Có. Không có bữa trưa nào miễn phí. Vâng. Được rồi. Có.
Yes. Question is, is mod log storing disk? Yes. I want to keep this data compressed as long as I can.
Có. Câu hỏi là, mod log có được lưu xuống đĩa không? Có. Tôi muốn giữ dữ liệu này ở dạng nén càng lâu càng tốt.
So if I'm going to flush it out and write it out to disk without applying the changes, I'll go ahead and do that. All right. Why not? All right.
Vì vậy nếu tôi cần flush nó ra và ghi xuống đĩa mà không áp dụng các thay đổi, thì tôi cứ làm như vậy. Được rồi. Tại sao không? Được rồi.
So now if I have to do a read, if the read is like, go get me for this tuple, like my example, I was updating that login field, where I just do a blind write without actually reading the data.
Bây giờ nếu tôi phải thực hiện một thao tác đọc, giả sử thao tác đọc đó là lấy cho tôi tuple này, như ví dụ của tôi, tôi đang cập nhật trường login đó, trong đó tôi chỉ ghi mù mà không thực sự đọc dữ liệu.
If the read can be serviced by the mod log, fantastic. I just access there.
Nếu mod log có thể phục vụ thao tác đọc thì tuyệt vời. Tôi chỉ cần truy cập ở đó.
But if I have to actually look what the values are inside the tuple, then I decompress it, apply whatever changes I have in my mod log.
Nhưng nếu tôi thực sự phải xem các giá trị bên trong tuple là gì, thì tôi giải nén nó, rồi áp dụng mọi thay đổi có trong mod log.
And when I decompress it, it's always going to end up being 16 kilobytes, because that's the default size in InnoDB.
Và khi giải nén, kết quả luôn có kích thước 16 kilobyte, vì đó là kích thước mặc định trong InnoDB.
Apply my changes to my mod log, still keep the compressed version around, because if I didn't make any changes, maybe I don't want to...
Áp dụng các thay đổi từ mod log, vẫn giữ lại phiên bản nén, vì nếu tôi không thực hiện thay đổi nào thì có thể tôi không muốn...
If there was no mod log updates to apply, then I can just always throw it away if I need to free a page.
Nếu không có cập nhật nào trong mod log cần áp dụng, thì tôi luôn có thể vứt bản giải nén đi khi cần giải phóng một page.
But the idea is, again, if I had to know something was inside of it, then I decompress it. Yes.
Nhưng ý tưởng là, một lần nữa, nếu tôi cần biết bên trong nó có gì, thì tôi giải nén nó. Vâng.
This question is, is there a way to have the compressed page only compress the data that you need? So in this scheme of MySQL, no.
Câu hỏi này là, liệu có cách nào để page nén chỉ nén phần dữ liệu mà bạn cần không? Với cơ chế này của MySQL thì không.
That would be choice number two, the tuple level compression. Like I said, there's only one system that does that. It's basically you want to have to be able to do incremental decompression.
Đó sẽ là lựa chọn thứ hai, nén ở mức tuple. Như tôi đã nói, chỉ có một hệ thống làm vậy. Về cơ bản bạn muốn có khả năng giải nén tăng dần.
Gzip, Snappy, all those guys can't do that. You have to sort of decompress the whole stream to jump to send any one offset. There are algorithms to do that.
Gzip, Snappy, những thứ đó không làm được. Bạn phải giải nén cả luồng thì mới nhảy tới một offset bất kỳ. Có những thuật toán làm được việc đó.
The tuple-level one, that Terrac1 is the only one that I know that actually did that. I don't think anybody else does. Hold on, hold on.
Còn loại ở mức tuple, Terrac1 là hệ thống duy nhất mà tôi biết thực sự làm vậy. Tôi nghĩ không ai khác làm. Khoan, khoan.
SQL Server can do it too, but I forget how they do it. And I don't know why they give them by default. I don't think they say how they do it.
SQL Server cũng làm được, nhưng tôi quên mất họ làm bằng cách nào. Và tôi không biết tại sao họ không bật nó theo mặc định. Tôi nghĩ họ không nói rõ họ làm bằng cách nào.
SQL Server and this forker box DB called Terrac1. I can follow up on Piazza with the links to that.
SQL Server và cái DB fork có tên Terrac1 này. Tôi có thể đăng các đường dẫn về chúng trên Piazza sau.
I don't want to spend too much time on this because it's MySQL and they're the ones that do it.
Tôi không muốn dành quá nhiều thời gian cho phần này vì đây là MySQL và họ là bên làm điều đó.
I just want to say, if you want to run Snappy, Gzip, this is how roughly you could do it. And actually, I actually think this is a good idea. Postgres can't do this.
Tôi chỉ muốn nói rằng, nếu bạn muốn chạy Snappy, Gzip, thì đại khái bạn có thể làm như thế này. Và thực ra tôi nghĩ đây là một ý tưởng hay. Postgres không làm được điều này.
Postgres can't do any compression except for those TOAST tables, those separate overflow attributes. All right.
Postgres không thể nén gì cả, ngoại trừ các bảng TOAST, tức là các thuộc tính overflow tách riêng. Được rồi.
So the big thing to point out is, in this case here, the compression algorithm we're using, whether it's Gzip or Snappy or Zstandard, it's considered an opaque box to the database system.
Vậy điểm quan trọng cần chỉ ra là, trong trường hợp này, thuật toán nén mà chúng ta đang dùng, dù là Gzip, Snappy hay Zstandard, đều được coi là một hộp đen đối với hệ quản trị cơ sở dữ liệu.
Meaning, I have a bunch of compressed bytes. The database doesn't know anything about what those bytes actually mean.
Nghĩa là, tôi có một loạt byte đã nén. Cơ sở dữ liệu không biết gì về ý nghĩa thực sự của những byte đó.
The only way it can get back to the original data is if it runs, the decoder runs the decompression algorithm to put it back into its original form.
Cách duy nhất để quay lại dữ liệu gốc là chạy, bộ giải mã chạy thuật toán giải nén để đưa nó trở về dạng ban đầu.
The compression schemes also don't understand the high-level meaning or semantics of the data, so it doesn't know it should maybe pack certain pages together and compress them because they're going to be related to each other.
Các lược đồ nén cũng không hiểu ý nghĩa cấp cao hay ngữ nghĩa của dữ liệu, nên nó không biết rằng có thể nên gom một số trang lại với nhau rồi nén chúng vì chúng có liên quan đến nhau.
It just says, here's the data you want to compress, go for it, and here's the output.
Nó chỉ nói: đây là dữ liệu bạn muốn nén, cứ làm đi, và đây là kết quả.
So what we really want to be able to do is have our database be able to operate on compressed data without decompressing it.
Vì vậy, điều chúng ta thực sự muốn là để cơ sở dữ liệu có thể xử lý trực tiếp trên dữ liệu nén mà không cần giải nén.
So this is a high-level example. I'll show you how we're doing in a second. But the basic idea is this. Say I have a simple table with names and salaries.
Đây là một ví dụ ở mức tổng quan. Lát nữa tôi sẽ cho các bạn thấy cách làm. Nhưng ý tưởng cơ bản là thế này. Giả sử tôi có một bảng đơn giản gồm tên và lương.
I want to run some compression algorithm and convert this data into compressed form. I'm showing this with two tuples because it fits in PowerPoint.
Tôi muốn chạy một thuật toán nén nào đó và chuyển dữ liệu này sang dạng nén. Tôi chỉ minh họa hai tuple vì nó vừa với PowerPoint.
Always think in extremes. What if I have a trillion tuples? I can store this now in much, much less space than I would if it was uncompressed.
Hãy luôn nghĩ đến trường hợp cực đoan. Nếu tôi có một nghìn tỉ tuple thì sao? Giờ tôi có thể lưu nó với dung lượng ít hơn rất, rất nhiều so với khi chưa nén.
Then now that my query shows up, SELECT * FROM users WHERE name = 'Andy'. I'm not going to say how I'm going to do this yet.
Rồi giờ truy vấn của tôi xuất hiện, SELECT * FROM users WHERE name = 'Andy'. Tôi chưa nói là sẽ làm điều này như thế nào.
What I want to be able to do is convert whatever constant I'm doing a lookup on for a given tuple, like name equals Andy, somehow convert that into its compressed form.
Điều tôi muốn là chuyển đổi hằng số mà tôi đang tra cứu trên một tuple nào đó, như name bằng Andy, bằng cách nào đó sang dạng nén của nó.
So now, when I do my comparison, instead of comparing two strings, does Andy equal Andy, does Andy equal Ganesh, I'm taking whatever this XXX thing, assuming it's an integer or something, and now I'm doing a faster comparison on those.
Như vậy, khi tôi thực hiện phép so sánh, thay vì so sánh hai chuỗi, Andy có bằng Andy không, Andy có bằng Ganesh không, tôi lấy giá trị XXX này, giả sử nó là một số nguyên hay đại loại vậy, và giờ tôi so sánh nhanh hơn trên các giá trị đó.
And if I'm doing integer comparisons, there's instructions on CPUs to do that really, really fast versus having to jump over bytes to do string matching.
Và nếu tôi so sánh số nguyên, CPU có các lệnh để làm việc đó rất, rất nhanh, so với việc phải nhảy qua từng byte để so khớp chuỗi.
So this is the goal. This is what we want to be able to do. And because we're the database system, we can control everything. We can do this.
Đây chính là mục tiêu. Đây là điều chúng ta muốn làm được. Và vì chúng ta là hệ quản trị cơ sở dữ liệu, chúng ta kiểm soát được mọi thứ. Chúng ta làm được điều này.
Whereas an off-the-shelf compression scheme can't do that.
Trong khi một lược đồ nén có sẵn thì không thể.
Even though they're actually going to be doing a lot of the same techniques that I'm going to talk about here in a second, like gzip and snappy, they're basically doing the same thing.
Dù thực ra chúng cũng sẽ dùng nhiều kỹ thuật giống nhau mà lát nữa tôi sẽ nói đến, như gzip và snappy, về cơ bản chúng làm cùng một việc.
They don't expose any of that to you on the outside. So they're doing dictionary encoding, but they don't expose the dictionary to you so that you can then do more fine-grained lookups.
Chúng không để lộ bất kỳ điều gì trong đó ra bên ngoài cho bạn. Chúng thực hiện dictionary encoding, nhưng không để lộ từ điển cho bạn để bạn có thể thực hiện các tra cứu chi tiết hơn.
So going back here, we're going to be doing this, again, in the column store because Now that our data within a single attribute is all contiguous to each other, they're all within the same value domain.
Quay lại đây, chúng ta sẽ làm điều này, một lần nữa, trong column store vì giờ dữ liệu trong một thuộc tính đơn lẻ nằm liền kề nhau, tất cả đều thuộc cùng một miền giá trị.
We see a lot of repeated values, a lot of values that are very close to each other, and we can exploit that in our algorithms.
Chúng ta thấy nhiều giá trị lặp lại, nhiều giá trị rất gần nhau, và chúng ta có thể khai thác điều đó trong các thuật toán của mình.
So here's a rough smattering of the main compression schemes, and I'll go through these one by one. Obviously, the usefulness of these depends on the data set. It depends on the workload.
Đây là một số sơ đồ nén chính, nói sơ lược, và tôi sẽ đi qua từng cái một. Rõ ràng là mức độ hữu ích của chúng phụ thuộc vào tập dữ liệu. Nó phụ thuộc vào khối lượng công việc.
In general, the dictionary encoding one is going to be the most common. I think ORC, they dictionary encode everything in their files, and obviously for var length and EBs.
Nói chung, dictionary encoding sẽ là cái phổ biến nhất. Tôi nghĩ ORC mã hóa từ điển mọi thứ trong các tệp của họ, và dĩ nhiên là cả với dữ liệu độ dài biến đổi và EB.
But a lot of these other ones, if they can fit the domain you're trying to work in, you can get a big win, much better than you can with dictionary encoding.
Nhưng với nhiều cách khác, nếu chúng phù hợp với miền dữ liệu bạn đang làm việc, bạn có thể thu được lợi ích lớn, tốt hơn nhiều so với dictionary encoding.
So run-length encoding, RLE, is when you have repeated values within a column.
Run-length encoding, RLE, dùng khi bạn có các giá trị lặp lại trong một cột.
So instead of storing that value over and over again and repeating it, we're just going to store, hey, I have this value, I'm at this offset within my column, and then here's how many times it's been repeated.
Thay vì lưu đi lưu lại giá trị đó nhiều lần, chúng ta chỉ lưu rằng: tôi có giá trị này, tôi đang ở offset này trong cột, và đây là số lần nó được lặp lại.
And I'll just store that triplet in succession, rather than the original values over and over again.
Và tôi chỉ lưu bộ ba đó nối tiếp nhau, thay vì lưu các giá trị gốc lặp đi lặp lại.
So obviously, to make this work, you got to sort your data in such a way that you can exploit this, because otherwise, you may end up ballooning the size of the compressed data.
Rõ ràng, để cách này hoạt động, bạn phải sắp xếp dữ liệu sao cho có thể khai thác được nó, vì nếu không, bạn có thể làm phình kích thước dữ liệu đã nén.
So let's say I have a really simple table that has some people information, where I have some ID of the person, and then a flag to say whether they're dead or not, like a Boolean flag, yes or no.
Giả sử tôi có một bảng rất đơn giản chứa thông tin về người, trong đó có ID của người đó, và một cờ cho biết họ đã chết hay chưa, như một cờ Boolean, có hoặc không.
So as you can see, in this Boolean flag, is dead, I have a lot of repeated values.
Như bạn thấy, trong cờ Boolean is dead này, tôi có rất nhiều giá trị lặp lại.
So what I can do is, now instead of storing the original value over and over again, I'll just store some value, what offset I'm in, because that's going to help me jump around if I need to find a match at a given offset, And then the length of the run.
Vậy điều tôi có thể làm là, thay vì lưu giá trị gốc lặp đi lặp lại, tôi chỉ lưu giá trị, và offset mà tôi đang ở, vì điều đó giúp tôi nhảy đến vị trí cần thiết nếu cần tìm một kết quả khớp tại một offset nhất định, và sau đó là độ dài của đoạn lặp.
So if I have queries like this, select the number of people that are dead and the number of people that are alive, I can just operate directly on this is dead part here in compressed form, and compute that very, very efficiently.
Nếu tôi có các truy vấn như thế này, chọn số người đã chết và số người còn sống, tôi có thể thao tác trực tiếp trên phần is dead này ở dạng nén, và tính toán rất, rất hiệu quả.
Whereas now the challenge is going to be, I have alternating values. So here we have no, followed by yes, followed by no.
Còn thách thức bây giờ là khi các giá trị xen kẽ nhau. Ở đây ta có no, rồi yes, rồi lại no.
So that's the worst case scenario for us, because now the size of the run is one for those three tuples, or three values, and the size of the compressed data is actually larger than the original data.
Đó là trường hợp xấu nhất đối với chúng ta, vì lúc này độ dài của đoạn lặp là một cho ba tuple, hay ba giá trị này, và kích thước dữ liệu nén thực ra lớn hơn dữ liệu gốc.
So if I sort the table based on the column I want to compress, and I got to update all the other columns, because I make sure my offsets match now, going across horizontally.
Vậy nếu tôi sắp xếp bảng theo cột mà tôi muốn nén, thì tôi phải cập nhật tất cả các cột khác, vì tôi phải đảm bảo các offset khớp nhau khi đi theo chiều ngang.
Now you see I have all the yeses followed by all the noes, and now I can store this column as a single, or just two values.
Giờ bạn thấy tất cả yes đứng trước, theo sau là tất cả no, và bây giờ tôi có thể lưu cột này chỉ bằng một, hay đúng hơn là hai giá trị.
So again, I'm only showing nine tuples here. Think in trillions or billions, this would be a huge, huge win.
Một lần nữa, ở đây tôi chỉ cho thấy chín tuple. Hãy nghĩ đến hàng nghìn tỉ hay hàng tỉ, đây sẽ là một lợi ích rất, rất lớn.
And we'll see in a second, we can combine RLE with other compression schemes. These things are actually multiplicative. I can compress in one form and compress it again in another form.
Và chút nữa ta sẽ thấy, ta có thể kết hợp RLE với các sơ đồ nén khác. Những thứ này thực ra có tác dụng nhân lên. Tôi có thể nén theo một cách rồi nén tiếp theo một cách khác.
The statement is, doesn't this mess up, I don't have my tuple ID? This is actually, this is not an internal ID, this is like the application's, I have this column called ID.
Câu hỏi là: như vậy có làm rối lên không, vì tôi không còn tuple ID của mình? Thật ra đây không phải là ID nội bộ, mà là ID của ứng dụng, tức là tôi có một cột gọi là ID.
This is like their social security number, email address. I'm just showing ID as a simple number. All the other columns would be sorted based on whatever the columns you're sorting on.
Nó giống như số an sinh xã hội hay địa chỉ email của họ. Tôi chỉ minh họa ID bằng một con số đơn giản. Tất cả các cột còn lại sẽ được sắp xếp dựa trên cột nào mà bạn chọn để sắp xếp.
Correct, and he's right. This might be good for one of the columns, but suck for the other ones. Absolutely, yes. So how do you pick what the best sorting scheme is?
Đúng vậy, và bạn ấy nói đúng. Cách này có thể tốt cho một cột, nhưng lại tệ cho những cột khác. Chính xác. Vậy làm sao chọn được cách sắp xếp tốt nhất?
And it'd be hard.
Việc đó sẽ khó.
All right, next one is bit packing. So again, in SQL, you call CREATE TABLE, you say these are the columns I have, you have to define the data type for them.
Được rồi, kỹ thuật tiếp theo là bit packing. Trong SQL, khi bạn gọi CREATE TABLE, bạn nói những cột mình có, và phải định nghĩa kiểu dữ liệu cho chúng.
And oftentimes, people declare things to be much larger than they actually need. Like, I have an age column, I'll define that as an integer. That's a 32-bit integer or four-byte integer in SQL.
Và người ta thường khai báo lớn hơn nhiều so với mức thực sự cần. Ví dụ, tôi có cột age, tôi sẽ định nghĩa nó là integer. Đó là số nguyên 32 bit, hay số nguyên bốn byte trong SQL.
But if most of my values aren't going to be hitting up the max size of a 32-bit integer, I've got a bunch of wasted space storing a bunch of zeros that don't mean anything for the tuples.
Nhưng nếu hầu hết giá trị của tôi sẽ không chạm tới kích thước tối đa của số nguyên 32 bit, thì tôi lãng phí rất nhiều chỗ để lưu hàng loạt số không vốn chẳng có ý nghĩa gì với các tuple.
But because they declared it to be 32 bits, I'm going to store 32 bits.
Nhưng vì họ khai báo là 32 bit, nên tôi sẽ lưu 32 bit.
So if the database system can recognize that you've oversubscribed or over-allocated the amount of storage space for your data, they can actually throw things away.
Vì vậy, nếu hệ quản trị cơ sở dữ liệu nhận ra bạn đã cấp phát dư hoặc quá mức dung lượng lưu trữ cho dữ liệu của mình, thì nó thực sự có thể bỏ bớt đi.
So if I'm storing all these values here, again, as 32-bit integers, you see we have these visualized 200 bits. But the only data that matters is this side over here.
Giả sử tôi lưu tất cả các giá trị này dưới dạng số nguyên 32 bit, bạn thấy ở đây có 200 bit được minh họa. Nhưng dữ liệu thật sự quan trọng chỉ nằm ở phía bên này.
Everything on this side is all wasted space with a bunch of zeros.
Mọi thứ ở phía này đều là chỗ lãng phí với toàn số không.
So with bit packing, you basically say, I'm going to store this in a compressed form, throw away those other 24 bits, and only store the 8 bits that actually matter.
Vì vậy với bit packing, về cơ bản bạn nói rằng: tôi sẽ lưu ở dạng nén, bỏ 24 bit còn lại, và chỉ lưu 8 bit thực sự có ý nghĩa.
And now we get this down, for this example here, we go from 256 bits to 64 bits with no loss of precision. And they're all fixed length because they're all 8-bit integers.
Và giờ, trong ví dụ này, ta giảm từ 256 bit xuống 64 bit mà không mất độ chính xác. Và tất cả đều có độ dài cố định vì đều là số nguyên 8 bit.
So now I can easily jump to whatever the offset is that I need for a given tuple. What's the challenge with this?
Nhờ vậy tôi có thể dễ dàng nhảy tới offset cần thiết cho một tuple bất kỳ. Thách thức ở đây là gì?
What if someone comes along and inserts a value now that isn't just 8 bits? It's something larger. So this is called patching. Or if you're using Amazon Redshift, they call this mostly encoding.
Nếu có ai đó chèn vào một giá trị không vừa trong 8 bit thì sao? Một giá trị lớn hơn. Cách xử lý này gọi là patching. Hoặc nếu dùng Amazon Redshift, họ gọi đây là mostly encoding.
And the idea here is that most of the values are going to be stored. I can bit pack into a smaller form.
Ý tưởng ở đây là hầu hết các giá trị sẽ được lưu bằng bit packing ở dạng nhỏ hơn.
But for the outliers that are maybe too big, I just have a little special marker to say, "All right, this value is actually not in line here with the rest of the values.
Nhưng với các giá trị ngoại lai có thể quá lớn, tôi chỉ đặt một dấu hiệu đặc biệt nhỏ để nói rằng: "Được rồi, giá trị này thực ra không nằm trực tiếp ở đây cùng các giá trị khác.
Go jump to some patch table that will tell you what the real value should be." So if I add this large number, 999999, it doesn't fit within 8 bits.
Hãy nhảy tới một bảng patch nào đó, nó sẽ cho bạn biết giá trị thật là gì." Vậy nếu tôi thêm số lớn này, 999999, nó không vừa trong 8 bit.
I'll store everything else as 8 bits. And again, in Redshift, you call this mostly 8.
Tôi sẽ lưu mọi giá trị còn lại bằng 8 bit. Và một lần nữa, trong Redshift, bạn gọi cái này là mostly 8.
And then I have this patch table here that says, if you scan along and find this bit sequence XXX, think of all the bits are true or 1, then I know that offset.
Và rồi tôi có bảng patch này, nó nói rằng, nếu bạn quét dọc và tìm thấy chuỗi bit XXX này, hãy hiểu là tất cả các bit đều là true hay 1, thì tôi biết đó là offset cần tra.
I go look up in this table, and I find what the original value is. So in this case here, instead of storing this as 256 bits, I store all my values as 8 bits.
Tôi đi tra trong bảng này, và tìm ra giá trị gốc là gì. Vậy trong trường hợp này, thay vì lưu thế này bằng 256 bit, tôi lưu tất cả các giá trị bằng 8 bit.
But then I have that lookup table, which I can get down to maybe just 48 bits to store that. Yes.
Nhưng sau đó tôi có bảng tra cứu đó, mà tôi có thể giảm xuống có lẽ chỉ còn 48 bit để lưu nó. Vâng, mời bạn.
This question is, how do I differentiate between a value that's a sentinel to say, go look at the patch table, which is the original value?
Câu hỏi là, làm sao phân biệt một giá trị là giá trị đánh dấu (sentinel) để nói rằng hãy đi xem bảng patch, đâu mới là giá trị gốc?
So for that one, if you set all the bits to 1, then you can't let anything be that value. You just have that be special cased.
Với trường hợp đó, nếu bạn đặt tất cả các bit bằng 1, thì bạn không thể để bất kỳ giá trị nào khác mang giá trị đó. Bạn chỉ cần xử lý nó như một trường hợp đặc biệt.
Correct. His statement is correct. If you had a value that was actually that special case, then you have to store that in the patch table. Yes.
Đúng vậy. Nhận định của bạn ấy là đúng. Nếu bạn có một giá trị thực sự trùng với trường hợp đặc biệt đó, thì bạn phải lưu nó trong bảng patch. Vâng, mời bạn.
But a trick you can also do is like, and here I'm showing offset 3, 999.
Nhưng bạn cũng có thể dùng một mẹo, ở đây tôi đang cho thấy offset 3, 999.
But if you have that repeated value that's a sentinel value over and over again, you only need to store that once in the patch table.
Nhưng nếu bạn có giá trị lặp đi lặp lại là giá trị đánh dấu đó, bạn chỉ cần lưu nó một lần trong bảng patch.
You reuse the entry. So it's not like you need to store that repeatedly.
Bạn dùng lại mục đó. Nên không cần phải lưu nhiều lần.
How do you store the offsets? Just a fixed length array.
Lưu các offset thế nào ư? Chỉ cần một mảng có độ dài cố định.
All right. Bitmap encoding. For this one, instead of storing the value themselves, we're going to store, for every unique value you have in your name, we're going to maintain a bitmap for it.
Được rồi. Mã hóa bitmap. Với cách này, thay vì lưu chính các giá trị, với mỗi giá trị duy nhất trong cột của bạn, chúng ta sẽ duy trì một bitmap cho nó.
And then you just have a one set within that bitmap at an offset, whether the value at the tuple of that offset is that value within your bitmap.
Và rồi bạn chỉ đặt một bit 1 trong bitmap đó tại một offset, cho biết giá trị của tuple tại offset đó có phải là giá trị ứng với bitmap của bạn hay không.
I'm going to do this kind of quickly. We only have 10 minutes left.
Tôi sẽ làm phần này khá nhanh. Chúng ta chỉ còn 10 phút.
But this would be fantastic if the cardinality of the value is low, meaning the number of unique values you can have for a given attribute is low.
Nhưng cách này sẽ rất tuyệt nếu lực lượng (cardinality) của giá trị thấp, nghĩa là số lượng giá trị duy nhất của một thuộc tính nào đó là thấp.
Like one example is dead? Yes, no. Anybody's either dead or not dead. There's only two possible choices.
Một ví dụ là is dead? Có, không. Ai cũng hoặc là đã chết hoặc là chưa chết. Chỉ có hai lựa chọn khả dĩ.
And this is going to work really great for that. So we go back to this. Is dead? Yes, no. So I'll maintain one bitmap for my yeses, one bitmap for nos.
Và cách này sẽ hoạt động rất hiệu quả cho trường hợp đó. Vậy ta quay lại ví dụ này. Is dead? Có, không. Tôi sẽ duy trì một bitmap cho các giá trị có, một bitmap cho các giá trị không.
And as you see at the different offsets, it's only going to be one or zero in either one.
Và như bạn thấy ở các offset khác nhau, giá trị chỉ là một hoặc không ở mỗi bitmap.
And then now if I run my queries, I can just rip through, find me all the matches where somebody's dead.
Và bây giờ nếu tôi chạy truy vấn, tôi có thể duyệt rất nhanh, tìm cho tôi tất cả các kết quả khớp mà ai đó đã chết.
I only need to scan through the is dead yes column, and I only need to look at the other bitmap. So the original size of this was 64 bits.
Tôi chỉ cần quét qua cột is dead có, và chỉ cần nhìn vào bitmap còn lại. Vậy kích thước ban đầu của phần này là 64 bit.
Assuming I can store these instead of yes, no as single bits, I can get this down to 16 bits. Yes? Is it better to do the store for one bitmap?
Giả sử tôi có thể lưu chúng bằng các bit đơn thay cho có, không, tôi có thể giảm xuống còn 16 bit. Vâng? Có tốt hơn không nếu chỉ lưu một bitmap?
The question is, why would you ever want to do this? Was it better to store is dead? In this example, yes. Is it better to store just like one number?
Câu hỏi là, tại sao bạn lại muốn làm như vậy? Lưu is dead có tốt hơn không? Trong ví dụ này thì có. Có tốt hơn không nếu chỉ lưu một con số?
This question is... If there's four unique values, then you can do a bit number and a bitmap. Basically, should you do something like RLE-ish? Like what?
Câu hỏi này là... Nếu có bốn giá trị duy nhất, thì em có thể dùng một số bit và một bitmap. Về cơ bản, có nên làm kiểu như RLE không? Ví dụ như gì?
Like you're saying do RLE? Or there's basically a store like, if I have... Yeah, the statement is, could you represent the bit sequence as just a number, store the number?
Ý em là dùng RLE ạ? Hay là lưu kiểu như, nếu em có... Vâng, ý của câu hỏi là, liệu có thể biểu diễn chuỗi bit chỉ bằng một con số, rồi lưu con số đó không?
Yes. For two columns, I'm trying to show an example, example. Yes.
Vâng. Với hai cột, tôi đang cố đưa ra một ví dụ, ví dụ minh họa. Vâng.
So I said, why would this ever be a good idea? Well, if the thing you're storing isn't binary?
Vậy tôi hỏi, tại sao việc này lại là một ý hay? Chà, nếu thứ em lưu không phải là nhị phân thì sao?
Yes.
Vâng.
Is it better to have a small number represent a value within my columnatron and compress, rather than do one-hot encoding?
Liệu có tốt hơn không nếu dùng một số nhỏ để biểu diễn một giá trị trong cột của tôi rồi nén, thay vì dùng mã hóa one-hot?
Well, no, because I can rip through bitmaps very, very quickly. Much faster than I can rip through integers. Right? Find me all the...
À không, vì tôi có thể duyệt qua bitmap cực kỳ nhanh. Nhanh hơn nhiều so với duyệt qua các số nguyên. Đúng không? Tìm cho tôi tất cả...
Find me all the... You need this simple example here. Find me all the... This example is not good, because I could store isDead in a bitmap column.
Tìm cho tôi tất cả... Các em cần ví dụ đơn giản này. Tìm cho tôi tất cả... Ví dụ này không hay, vì tôi có thể lưu isDead trong một cột bitmap.
Correct, yes.
Đúng, vâng.
Because there's a bunch of bit-shifting tricks I can do in modern CPUs, that I can take in a whole vector of bits, and then a single instruction, find all the matches, versus integers, it would take a lot more.
Vì có rất nhiều mẹo dịch bit mà tôi có thể làm trên các CPU hiện đại, tôi có thể nạp cả một vectơ bit, rồi chỉ với một lệnh duy nhất, tìm tất cả các kết quả khớp, còn với số nguyên thì sẽ tốn nhiều hơn nhiều.
Your statement is bitmap would be faster? Yeah, for aggregation, yes. Okay, my example here, yes, no, it's binary.
Ý em là bitmap sẽ nhanh hơn? Vâng, với phép tổng hợp thì đúng vậy. Được rồi, ví dụ của tôi ở đây, có hoặc không, là nhị phân.
So you could just store just this array here, or this array here would be the same thing as storing isDead. So I'm showing two examples, because it's on PowerPoint.
Nên em có thể chỉ lưu mảng này ở đây, hoặc mảng này ở đây sẽ giống như lưu isDead. Tôi cho xem hai ví dụ, vì nó nằm trên PowerPoint.
But if you have more, it would not be a good idea. All right.
Nhưng nếu có nhiều giá trị hơn thì đó sẽ không phải là ý hay. Được rồi.
Let me quickly show why it's a bad idea. So if you have a lot of columns...
Để tôi nhanh chóng cho thấy tại sao đó là ý tồi. Nếu có rất nhiều cột...
Sorry, a lot of unique values, like number of zip codes, then the storage space, if you just do the naive scheme, would be terrible.
Xin lỗi, rất nhiều giá trị duy nhất, như số lượng mã bưu chính, thì dung lượng lưu trữ, nếu chỉ dùng cách đơn giản ngây thơ, sẽ rất tệ.
All right. So you don't want to bitmap and code everything. There are tricks to compress this further using part of roaring bitmaps.
Được rồi. Vậy nên đừng mã hóa bitmap mọi thứ. Có những mẹo để nén thêm, dùng một phần của roaring bitmap.
We don't have time to cover that. Just think of compressed bitmaps for... It's a way to compress sparse bitmaps.
Chúng ta không có thời gian để đề cập. Cứ hiểu đó là bitmap nén cho... Đó là cách nén các bitmap thưa.
So I have a bunch of zeros, roaring bitmaps is the right way to do that, and a bunch of systems use that. All right.
Nên nếu tôi có cả loạt số không, roaring bitmap là cách đúng đắn để làm việc đó, và nhiều hệ thống dùng nó. Được rồi.
Let me get through the last two compression schemes, delta encoding and dictionary compression.
Để tôi đi nốt hai phương pháp nén cuối cùng, mã hóa delta và nén từ điển.
So delta coding, the idea is that if I'm storing values that are very close to each other repeatedly, then I don't need to store the actual absolute value for each of those measurements or whatever I'm trying to record.
Với mã hóa delta, ý tưởng là nếu tôi lưu các giá trị rất gần nhau một cách lặp đi lặp lại, thì tôi không cần lưu giá trị tuyệt đối thực sự cho từng phép đo đó, hay bất cứ thứ gì tôi đang ghi lại.
I just store a diff or delta from either the previous value or some global value at the top of the beginning of the page.
Tôi chỉ lưu độ chênh lệch, hay delta, so với giá trị trước đó hoặc so với một giá trị chung ở đầu trang.
And then now the delta I'm storing is going to be much less than storing the full value.
Và khi đó delta mà tôi lưu sẽ nhỏ hơn nhiều so với việc lưu toàn bộ giá trị.
So again, if I'm storing the temperature in this room at a one-minute granularity, and hopefully not this room, 99 would be a lot, but if I'm recording over and again the same temperature over and again, there aren't going to be wild fluctuations in the temperature from one measurement to the next.
Ví dụ, nếu tôi lưu nhiệt độ trong phòng này theo từng phút, và hy vọng không phải phòng này, vì 99 độ thì nóng lắm, nhưng nếu tôi ghi đi ghi lại cùng một nhiệt độ nhiều lần, thì nhiệt độ sẽ không có những biến động quá lớn từ lần đo này sang lần đo tiếp theo.
So instead, what I can do is just, or same with the time, the time is always incrementing by one minute.
Vì vậy, thay vào đó, tôi có thể chỉ cần, hoặc tương tự với thời gian, thời gian luôn tăng thêm một phút.
So instead, I'll just store at the top of the column some base value, and then I'll store the delta from the previous value.
Vì vậy, tôi chỉ lưu một giá trị cơ sở ở đầu cột, rồi lưu độ chênh lệch (delta) so với giá trị trước đó.
So now as I'm scanning along, I know how to apply those changes to get back whatever value it is that I wanted.
Như vậy khi tôi quét dọc theo cột, tôi biết cách áp dụng các thay đổi đó để lấy lại giá trị mà tôi cần.
So we can compress this further because we notice, in this case here, the time column, what do we have?
Chúng ta có thể nén thêm nữa vì nhận thấy rằng, trong trường hợp này, ở cột thời gian, chúng ta có gì?
A bunch of plus ones. So we don't need to store one, one, one all over again. We can RLE that again.
Một loạt các +1. Vậy nên không cần lưu 1, 1, 1 lặp đi lặp lại. Chúng ta có thể áp dụng RLE thêm lần nữa.
And now we get the multiplicative compression, where I restore, we have plus one repeated four times. Some of these compression schemes are composable.
Và giờ ta có hiệu quả nén theo kiểu nhân lên, trong đó ta lưu lại +1 lặp lại bốn lần. Một số phương pháp nén này có thể kết hợp với nhau.
So the benefit we're going to get is the original data in this example here is 320 bits.
Lợi ích mà ta nhận được là dữ liệu gốc trong ví dụ này có 320 bit.
If I just do delta encoding, I get 128 bits, but if I do RLE plus delta encoding, I can get it down to 96 bits.
Nếu chỉ dùng mã hóa delta, ta được 128 bit, nhưng nếu dùng RLE cộng với mã hóa delta, ta có thể giảm xuống còn 96 bit.
Again, we're talking bits here. Always think in larger scales. This will matter when you get the gigabyte and petabyte scale.
Lưu ý là ở đây ta đang nói về bit. Hãy luôn nghĩ ở quy mô lớn hơn. Điều này sẽ quan trọng khi bạn làm việc ở quy mô gigabyte và petabyte.
In this example here with delta encoding, I have, at the beginning of the page, that's the base value I'm going to use as the offset when I compute these things.
Trong ví dụ mã hóa delta này, ở đầu trang tôi có giá trị cơ sở, dùng làm độ lệch khi tôi tính các giá trị này.
There's another approach called frame of reference. And basically, you have a global min value that you use across multiple pages. But the basic idea is the same thing.
Còn có một cách tiếp cận khác gọi là frame of reference. Về cơ bản, bạn có một giá trị nhỏ nhất toàn cục dùng chung cho nhiều trang. Nhưng ý tưởng cơ bản thì giống nhau.
All right, the last one I want to get through is dictionary encoding.
Được rồi, phương pháp cuối cùng tôi muốn nói là mã hóa từ điển (dictionary encoding).
And the idea here is that we're going to replace frequent values that we see in our data set within a column with some kind of small, fixed-length integer code.
Ý tưởng ở đây là ta thay các giá trị xuất hiện thường xuyên trong tập dữ liệu của một cột bằng một mã số nguyên nhỏ, có độ dài cố định.
And then we'll store those integer codes contiguously in memory. And then we'll have a separate data structure called the dictionary, which is oftentimes just a fixed-length array.
Sau đó ta lưu các mã số nguyên này liên tiếp nhau trong bộ nhớ. Và ta có một cấu trúc dữ liệu riêng gọi là từ điển, thường chỉ là một mảng có độ dài cố định.
Sorry, an array that we jump to offsets. That if I ever need to go back to the original value, I can use that dictionary to do that conversion.
Xin lỗi, là một mảng mà ta nhảy tới các vị trí độ lệch. Khi cần quay lại giá trị gốc, tôi có thể dùng từ điển đó để chuyển đổi.
So typically, most implementations are going to have one code, dictionary code per value. So if I have a one-megabyte block of text, I can convert that down to a single 32-bit integer.
Thông thường, hầu hết các cách triển khai sẽ có một mã, mã từ điển, cho mỗi giá trị. Vì vậy nếu tôi có một khối văn bản một megabyte, tôi có thể chuyển nó thành một số nguyên 32 bit duy nhất.
And then I have a dictionary to store that entire block of text later. You could start doing more fine-grained things like coupling coding.
Và sau đó tôi có một từ điển để lưu toàn bộ khối văn bản đó. Bạn có thể bắt đầu làm những việc chi tiết hơn như coupling coding.
But as far as I know, no system does that in production. This is also basically what LZ4 and ZStandard and all those other compression schemes are doing underneath the covers.
Nhưng theo tôi biết, không hệ thống nào làm vậy trong môi trường thực tế. Về cơ bản, đây cũng là điều mà LZ4 và ZStandard cùng các phương pháp nén khác đang làm ở bên dưới.
They just don't expose the dictionary to you.
Chỉ là chúng không để lộ từ điển cho bạn.
So this would be great for both doing point queries and range queries, because I can rely on that dictionary to do fast comparisons on the data in compressed form without having to go decompress it.
Vì vậy cách này rất phù hợp cho cả truy vấn điểm lẫn truy vấn khoảng, vì tôi có thể dựa vào từ điển để so sánh nhanh trên dữ liệu ở dạng đã nén mà không cần giải nén.
So look at a simple example like this. So here's my original data. I have a bunch of integer strings that are all different lengths.
Hãy xem một ví dụ đơn giản như thế này. Đây là dữ liệu gốc của tôi. Tôi có một loạt chuỗi số nguyên với độ dài khác nhau.
So then when I compress it, I convert the name column into these compressed integers. Then I have this dictionary-size structure over here that, for any given value, here's the corresponding code for it.
Vậy khi tôi nén nó, tôi chuyển cột name thành những số nguyên đã nén này. Rồi tôi có cấu trúc kích thước từ điển ở bên này, với mỗi giá trị cho trước, đây là mã tương ứng của nó.
And I have a way to actually go both directions in my dictionary. So if we're given a code, give me the original value, and for an original value, give me the code.
Và tôi có cách để đi theo cả hai chiều trong từ điển. Nếu được cho một mã, hãy trả về giá trị gốc, và với một giá trị gốc, hãy trả về mã.
So I need to support both operations.
Vì vậy tôi cần hỗ trợ cả hai thao tác.
And this dictionary is actually sorted based on the values that we're compressing, because now we can still apply certain comparison operators when we run queries on the compressed data and still get all the order-preserving guarantees we want, because the data has actually been sorted.
Và từ điển này thực sự được sắp xếp theo các giá trị mà chúng ta đang nén, vì như vậy chúng ta vẫn có thể áp dụng một số toán tử so sánh khi chạy truy vấn trên dữ liệu đã nén và vẫn có được mọi đảm bảo bảo toàn thứ tự mà ta muốn, bởi vì dữ liệu thực sự đã được sắp xếp.
So now I can do some tricks like this.
Giờ tôi có thể dùng một vài mẹo như thế này.
If I have find users where the name starts with the prefix A-N-D, I can take my query, extract out the constant I'm doing the lookup on, basically apply that LIKE clause to my dictionary, which is going to be way smaller than the original data, convert now my boundaries to dictionary codes, in this case 10 and 20.
Nếu tôi có truy vấn tìm những người dùng có tên bắt đầu bằng tiền tố A-N-D, tôi có thể lấy truy vấn của mình, trích ra hằng số mà tôi đang tra cứu, về cơ bản là áp dụng mệnh đề LIKE đó lên từ điển của tôi, vốn nhỏ hơn nhiều so với dữ liệu gốc, rồi chuyển các biên của tôi thành mã từ điển, trong trường hợp này là 10 và 20.
Now in my rewritten query, I can rip through the name column with that BETWEEN clause and now just do comparisons on integers, which is way faster, to find all my matches.
Bây giờ trong truy vấn đã viết lại, tôi có thể quét nhanh qua cột name với mệnh đề BETWEEN đó và chỉ cần so sánh trên số nguyên, nhanh hơn rất nhiều, để tìm tất cả các kết quả khớp.
So I still had to do some string lookups, but I did that on the dictionary, and I have a lot of repeated values.
Vậy là tôi vẫn phải tra cứu chuỗi, nhưng tôi làm việc đó trên từ điển, và tôi có rất nhiều giá trị lặp lại.
And this is fantastic, because I'm not going to have to look at all the data, and then I can rip through the original data very efficiently.
Điều này thật tuyệt, vì tôi sẽ không phải xem toàn bộ dữ liệu, rồi sau đó tôi có thể quét qua dữ liệu gốc rất hiệu quả.
So this is what the order-preserving guarantees of maintaining the dictionaries in sorted order give us.
Đó chính là những gì đảm bảo bảo toàn thứ tự khi duy trì từ điển theo thứ tự đã sắp xếp mang lại cho chúng ta.
So if I have a query like this, like SELECT name FROM users WHERE name LIKE A-N-D, I'm still going to have to do a scan on the original table, because I still have to get back the original value for the two of those that match.
Nếu tôi có một truy vấn như thế này, SELECT name FROM users WHERE name LIKE A-N-D, tôi vẫn sẽ phải quét bảng gốc, vì tôi vẫn phải lấy lại giá trị gốc của hai bản ghi khớp đó.
In this case here, if I only get the distinct name, that one I only have to go look up in the dictionary, because I need to find whatever that one match that I have.
Trong trường hợp này, nếu tôi chỉ lấy distinct name, thì tôi chỉ cần tra trong từ điển, vì tôi cần tìm bất kể kết quả khớp duy nhất đó là gì.
And then I'm done. Yes?
Và thế là xong. Bạn có câu hỏi?
The question is, how do I handle deletes? How do I delete from the dictionary? Deletes are easy, because you could just delete the value from the dictionary and it doesn't have any gaps.
Câu hỏi là, xử lý việc xóa như thế nào? Làm sao xóa khỏi từ điển? Xóa thì dễ, vì bạn chỉ cần xóa giá trị khỏi từ điển và nó không để lại khoảng trống nào.
Inserting is more tricky, because if I have to insert something between 10 and 11, and I don't have a value in between, I've got to recompress things.
Chèn thì phức tạp hơn, vì nếu tôi phải chèn thứ gì đó vào giữa 10 và 11, mà không có giá trị nào ở giữa, tôi phải nén lại dữ liệu.
The great thing about OLAP is that the data is mostly immutable. So it's not really an issue.
Điều hay của OLAP là dữ liệu phần lớn là bất biến. Nên đó thực ra không phải vấn đề.
This question is, if someone says you're using dictionary compression, does that mean by default they're using order preserving?
Câu hỏi này là, nếu ai đó nói bạn đang dùng dictionary compression, thì mặc định có nghĩa là họ đang dùng order preserving không?
Typically, yes. Are there compression schemes that are not order preserving? Yes. Most of them are. I just wanted to highlight that benefit we get. OK. We're out of time here.
Thường là có. Có lược đồ nén nào không bảo toàn thứ tự không? Có. Hầu hết đều không. Tôi chỉ muốn nhấn mạnh lợi ích mà chúng ta có được. OK. Chúng ta hết giờ rồi.
So I'll pick up on how we handle OLAP and OLAP together next class. And then we'll have the guest speaker from Ucabite. And then again, the recitation is tomorrow night.
Vậy lần sau tôi sẽ nói tiếp về cách xử lý OLAP và OLAP kết hợp với nhau. Và sau đó sẽ có diễn giả khách mời đến từ Ucabite. Và một lần nữa, buổi thảo luận là vào tối mai.
And then all the database company talks are all tomorrow morning as opposed to Piazza. OK? Hit it.
Và sau đó tất cả các buổi nói chuyện của các công ty cơ sở dữ liệu đều diễn ra vào sáng mai, chứ không phải trên Piazza. OK? 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.