CMU Database Group · 1:25:57 · https://www.youtube.com/watch?v=fr5lIchF6pw
0:00 Official members bounce bust off the chrome. Realize it's real hell where we call home. Official members bounce bust off the chrome. Realize it's real hell where we call the heart inside one. I vision fat licks and m clips. The chrome make the average imitator do back flips. You lack a pistol. to put a vest around the issue. Blockchain for blockchain for databases is is a bad idea. Let's not do that.
0:30 All right. You're out of jail. You're right. Yes. Yes. That guy. All right. Um All right. All right. So much to cover. So much to cover. All right. Um All right. All right. So, uh project four is due uh this this Sunday. And again the the I don't have it listed here on Saturday. Again we have the TA session in in 5207 that'll be from 3 to 5. And then again I bumped homework 6 to be due on an extra day on Monday December 9th the day after project 4.
1:06 And then for some of you that that are planning to use your late days I need to have everything submitted by midnight on on Monday the 16th. Right? In theory you you could go longer with like the 10 10 late days plus the four late days you're given right without penalty. But I in order for me to get grades in because people need to graduate, right? Uh please get everything in by by December 16th. Okay.
1:29 All right. Um other sort of administrative things. So J Nash is teaching uh 445 645 next semester. Uh so if you're really interested in this kind of stuff and some of you have already talked about this and you want to be a TA, uh please sign up. We'd love to have you. And then if you're hanging around in the winter and you can't get enough of bus stop or you think bus stop is terrible and you have strong opinions how you want to fix it.
1:51 Um you know we have had TAs uh who are going to be TAs in the spring stick around in the winter break or wherever remotely and actually clean up some of the source code clean up some of the projects in particular project three and four uh that if you want to go fix up Bus Hub and make it look better for the next batch of students um then please let us know any this would be a paid position.
2:12 So I I think I posted this on uh Piaza, but I'll do it again if I haven't. Uh you can go sign up to BTA here next year. Okay. All right. And then uh for the Corsy vows, right? I say this every year. We actually look at your feedback and listen to it. Uh now the the the undergrads are very brutal and they'll tell you what stinks and I appreciate that. Master students, you guys just love everything.
2:35 I get I get I get straight fives. Please don't do that. Well, if you want to do that, it's fine. um because then the dean doesn't complain. But uh but I mean honestly give give give your true opinions like what didn't work, what you didn't like about the projects, what you didn't like about the homeworks, the exams, anything because again we actually will listen to them. Um yes. Uh going back to the uh Monday, December 16th, can we take late days past that or is that like a harsh?
3:00 No, I'm saying like I got to get final grades in. So like don't go past this. Okay. Yeah. If if you really I mean if you go past this then I got to get like fill out a form and get there's a whole process of get change a grade because you would get incomplete and I got to go with the dean. So let's avoid that because then that won't get processed until people come back in January and then so if you're trying some people are graduating and trying to go start their jobs and need proof of graduation then they'll be blocked this. Let's not do that. Okay. Um all right. Yeah.
3:31 So uh yeah get feedback on anything. Again, we it's anonymous. I don't care. One year, somebody gave me a psych psych psychiatric evaluation. Uh that was nice. Uh but by means, yeah, please please tell us what you don't like and don't like and don't like um for office hours. So, I'm having my regular office hours today at 3:30 immediately after class. Uh next week, I will also have on on the Wednesday class or sorry, Wednesday, even though we don't have a class, I'll have office hours, but then I'll have additional office hours on Thursday, the day before the final exam, uh at 3:00 in my office.
4:02 And if you're not able to meet these times or you want to chat on the weekend or for whatever reason, send me an email and we can try to make an appointment to talk on Zoom or come at another time. And then uh my number one PG student will who the TA who's the TA uh he'll be having office hours on his regular time on Wednesday, December 11th. But all the other TAs will be finished uh you know finished on this Saturday after the the the Saturday session because they have their own finals and things to finish up as well.
4:28 Okay. And then the people will be around to help on on PISA. Um but again don't assume you know past uh you know you know the past the week people are going to be immediately responsive. Okay. All right. So final exam. All right. Who has to take it? Everyone who's in the class. Uh they it could be in Baker Hall 851. They actually gave us two rooms. If you look at the the exam schedule, we get two rooms.
4:54 But show up to this one first and then we'll we'll figure out where you need to go. And then as I posted on piaza last night, uh the final study guide is available along with a you know what's going to be on on the on the exam which I'll cover in this class as well, but also like a practice exam with solutions. Okay. And then if you need accommodations, which again I don't think anybody does uh at this point, but
5:15 if if you haven't contacted me yet and you need accommodations, please do that as soon as possible so we can make make arrangements. All right. So as I said, we have two rooms. show up to 8:51 first and then you'll be signed at a random location and then uh Will and the other TAs will be in one room and then I will and other people will be another room and I'll sort of bounce through uh and answer any questions and clarifications as we go along.
5:34 Just like the midterm, bring your CMU ID, a pencil and eraser, a calculator, but you can use your phone. That's okay. Uh and then you're allowed one uh one sheet of handwritten notes double-sided. Don't take the the slides or the lecture notes and try to zoom them down. If you want to write in your iPad and then print that out, that's fine. I don't care. Uh just, you know, we want we don't at least be handwritten. Okay. All right.
5:59 Uh so what's going to be on the Oh, sorry. What's going to be on the final? So the stuff that you have to need to be aware of, again, maybe not know the exact details of certain things, but like you have to obviously know SQL because if you see SQL queries and you can't read it, you have problems. uh but the the the basic what the architecture of the data systems we've been talking about and the different techniques and methods prior to the midterm uh those are all in you know fair game and then just as a as a warning for everyone like because we know chatb can be used to write all the projects at least not well but it can some of them uh there will be one question that has some basics of of
6:39 understand require you to understand some basics of busub right so there'll be a little bit of code you have to read and answering your question but it's obviously not like what does this line of code do it's more like conceptual things right and again it's it's it's a paper exam so we can't you know it's not going to be that much code
6:54 yes do we need to remember the API or value no it's not it's not like what does this function do what does this header file do no it's just like it'll be bus tub code that you can pretty much figure out yes it's not again it's it's not meant to like what what does this what does this file and this line number say Don't don't if you've done well if you've written the projects you'll be fine okay I'm not saying that you do any additional work just a warning for people like oh I'm going to do chat GPT for everything uh
7:24 there'll be something here okay all right so uh the major topics that we c covered again this is basically what we've we we've gone through since the the midterm so we spent a class talking about create optimization and again that was a really quick overview of of the the basic ideas of it but just be aware of like what does it mean to use horistics to do predicate get pushed down, projection, push down. How do we handle nested sub queries?
7:44 Uh what does it mean to collect statistics on on data as you see them? How can you use that for cardality estimation? We don't go through the formulas in this in this class, right? Like but obvious things like you know something's a unique key and your your your wear clause is something equals something, right? You should know the selectivity of that is just one over the number of rows or yeah number uh tupils, right? So basic information uh how we keep track of things histograms and then understand when we did the plan enumeration or doing costbased search we saw two methods the the bottoms up approach from system R where you sort of start with nothing and you add use a dynamic programming technique to add uh edges to figure out the join order and the top down approach was starting with the goal and then you traverse down to do a a branch bound search to try to build the query plan.
8:31 So I understand again that the trade-offs of these two different ideas and there's a question on the practice exam uh that gives you a rough outline of the kind of stuff we care about. We spend a lot of times a lot of time talking about transactions. So obviously be aware asset is uh understand what conflict serializability means. What does it mean to have uh to check for correctness or to say that one schedule is conflict equivalent to another schedule or serial ordering.
8:55 We didn't go too deep into view serializability but to understand that like there are relaxations that you could do to get additional parallelism uh under view serializability but you can't do under conflict serializability but of course again no system can actually support this or implement this and just understand again the high level reasoning on why you couldn't just do this automatically. We spent time talking about isolation levels, right? Uh and the anomalies that can occur, right?
9:23 Phantom reads, uh unre repeatable reads, dirty reads, right? Uh lost updates, right? Skew on a multi version control to be unaware what does that mean in the context of a schedule and what are the implications of that and what the isol isolation levels could expose a transaction to. And then we spent time talking about the current studio protocols.
9:43 So we talked about two-phase locking. We talked about how the sort of the regular version of it uh where you you have the two phases and then strong strict where you hold all the the locks until the very very end to you actually commit right there was a relaxation of that called strict two two-phase locking instead of a strong strict strict that was you hold all the right locks till the end but you can release the read locks during the the um the unlocking phase the second phase we looked at multi multi-granularity locking this idea of these intention locks I traverse this hierarchy and say as I'm as I'm acquiring locks in the uh uh in my in my database system, I can acquire locks at a really granular level like the entire database, entire table.
10:24 But instead of doing that, I can have these intention locks that give hints to other transactions about what you're doing down below. So we understand it was uh intention exclusive, intent in attentive shared and shared intention exclusive understand how how those fit into the hierarchy.
10:41 Then we talked about OCC optimistic currency control protocol and the main thing we spent a lot of time on is understanding uh the validation phase right and I think in the lecture we did we did backwards validation uh but there's also the forwards validation right backwards is when you're looking back at previously committed transactions and see whether they wrote something that you missed and then forward validation is looking at the currently active transactions and seeing whether you wrote something that they missed that would violate again the serial ordering based on timestamps. Understand that under OTC you assign the time stamp when a transaction enters the valation phase not when it starts.
11:12 What does it mean to copy stuff in the during the read phase into your private workspace and then how you write it back and then the right phase. Then we spent a whole lecture on multi version control which is very similar to uh OC but instead of having a private workspace we're making new versions in sort of global database
11:34 and we talked about how there's different ways you could store the versions like you do the postgress style just append new tupils you could do the time travel table you just copy things into a separate table uh that's linked to the the master one and then the the best one is going is be the delta versioning right I just take diffs of the the changes I'm making and append them out to a version chain. We talk about garbage collection, how to clean things up, how to do index maintenance.
11:58 Uh right, this is for secondary indexes. How do I keep track of if if I my version chain is changing depending by the newest newest to oldest to oldest and newest. Do I have to update my secondary indexes every time I insert a new record? How to keep track of find the the version chain or just understand what the implications of how all that fit together. Then we finish up with with uh well we switch to crash recovery.
12:20 So understand what the different buffer pool policies you can have steel versus no steel right what does steel mean when action commits uh sorry you're allowed to evict dirty pages from the buffer pool before a transaction commits no steel says you can't and then force no force force says that when a transaction commits you have to flush all dirty pages before you tell the outside world that a transaction is committed no force says that you don't so with right ahead logging what is right ahead logging using steel versus no steel I heard steel. Yes, steel.
12:53 And then is he using force or no force? Exactly. Right. So understand how right ahead logging, which is the dominant architecture everyone uses, how that's going to relate to the policies up above. Don't worry too much about shadow paging, but just be aware of like how does that fit into the bufferable policies as well. Um, and then we talked a little bit about the logging schemes, physical versus logical. Just understand like again the trade-offs with the these different approaches.
13:16 Most systems are going to use physical or physiological logging uh because getting the ordering for logical logging upon recovery is tricky especially at lower isolation levels but that's that's lowle details that you don't have to worry about. Then we talk about how to how to handle crashes. So we talk about checkpoints with uh fuzzy and fuzzy non-fuzzy and fuzzy checkpoints, right? Aries is going to be using fuzzy checkpoints, right? You have a checkpoint begin, checkpoint end, and you keep track of what occurs during that time.
13:42 Then understand what Aries the Aries recover protocol looks like or what it does. There's the the analyze phase where you read the right headlog. Where do you start in the red headlog to figure out what was going on, you know, before the crash? The redo phase is reapplying all the changes that you see in in the red head log to make sure that they're actually occurring or that they land on the pages. And then the undo phase is undoing any transaction that did not commit before the crash.
14:03 Understand what's going to be in the the dirty page table, how this gets updated. Same thing with the active transaction table. And then understand what CLRs are, right? The compensation log records as I'm recovering the database and I'm undoing aborted transactions. uh actually you need you need to see without aborting or sorry without uh recovery for aborted transactions but as I'm undoing the transactions and reverse the changes I I add CLRs to the right head log
14:32 and then the last one is uh distributed databases and again we didn't go too much details on this there was a homework on it but obviously you didn't build anything in bus hub uh so the you know so the high level understanding of what the different system architectures you can have and we'll see a lot of this today when we talk about the different systems share shared disk uh shared everything and then high level understanding what replication looks like the different partitioning schemes you can have like like horizontal partitioning versus vertical partitioning and then the basics of two-phase commit and I think there's again a homework question that asks you about these things right we're not going to ask you to prove the correctness of paxos or raft or anything like that okay
15:12 so the things that aren't on the exam uh will be any of the flash talks we had from the the the friends in industry any of the seminar talks and then anything about like oh postgress does this my SQL does that like all those slides are just for your general education understand how this all relates to real world systems but it's not meant to be like hey what does Postgress do because what kind of test is that right and anything about my life troubles is not not worth discussing okay any questions oh what the all right and so that's the most important you guys know need to know for the final exam.
15:48 Okay, any more questions? Okay, let's try to do this. So, 7:21 from spring 2024. I'm going to try to speedrun, go as fast as possible, uh, and again, interrupt and ask questions as we go along. We're try to cover again the core things you you won't need to understand from sort of high performance analytical data systems. Okay, so we showed this slide I think in lecture 13 or 12 when we talk about query execution and we said for for sequential scan
16:20 right at the end of the day you got to go through it and just read data right there isn't any magic to to to avoid necessarily doing that and there's I said there's a bunch of these optimizations that uh you can do right like encoding and compressing prefetching scan sharing yada yada so forth right so we've covered all of these except for materialized views result caching Um, mature views are very complicated. I can't I I don't fully understand this myself how it actually do incremental updates, but it's just like if I have a query, I can set it as a as a as a view and it gets computed and every time there's an update, I could just rerun the entire query and use that cache result or the the smarter systems can do incremental updates. That's really hard.
16:59 We're not going to cover that. Result caching just like, hey, have things changed since the last time I ran this query? If if no, here's the result. All right? Some systems do that. What I want to talk about today is down here code specialization and compilation. Um because this is what's going to be this is what's going to separate again the the sort of the the the analytical systems on the modern era versus what people were doing you know 101 15 years ago.
17:22 Okay. All right. So the first thing we got to cover is how do we design our database system to run analytics more efficiently based on modern hardware based on modern CPUs. Right? So say we have a simple query like this. select star from table where key is greater than than some low value and key less than some high value. So in bus tub or any sort of generic system like postgress whatever you'd probably write your code like this right
17:48 I don't like to I don't like to show show code but for this topics here you kind of have to so we're going to go for every single tuple in a table go grab the key we're trying to do a look up one and then we have an if if clause says if the key is you know greater than this or key less than that then we're going to copy that tube and put it in our output buffer right so this is actually the bad thing to do on modern CPUs and I'm going to say guess Why?
18:15 In a supercalar architecture, what happens? It sees the branch and what does it try to do? Tries to predict, right? But now if your data is this like completely intermixed uh and you know every other key or every other tubo is going to satisfying this predicate, it's going to do branch prediction and get it wrong. And what does it do when it gets wrong? It has to it specly executes and has to roll back all its changes, flush the pipeline and restart it and it's really slow.
18:42 So it turns out on a modern CPU, you actually want to write code that looks like this in your database system, right? So in here, the first thing we're going to do is always copy the tupole in our output buffer. Even if it doesn't match yet, always copy it in. Then we're going to run that uh the the check for us whether key P greater than low or less than high.
19:03 And then we're basically doing an and operation on on one. So if it matches on one of them, it's set to one. And it both matches and it's set to one, then the the the delta is set to one. And then now we have this this uh this offset here where we're keeping track of where we're writing into our output buffer. And if it's set to one, then that means that we're going to iterate the output buffer by one more position and keeps whatever we just put back we put into our when we copied in the buffer earlier up above.
19:29 If it's zero, then when we come back around, we're just going to overwrite it again. So this seems kind of insane, right? this seems like, you know, as a human, you look at this, say, "This seems like the wrong thing to do because I'm I'm blindly copying something over and over again."Uh, and then I go check to see whether I actually need it or not. And obviously, I'm missing a little code down here below that says like when you come out of the for loop, check whether the last delta was one or zero to be aware whether you want to get rid of the the last thing you just copied in.
19:55 But we can ignore that. But again, like from a from a human, the first way seems like more the better way to go. But from a modern CPU, you want the second one, right? Because that's just going to be now there's no indirection in the for loop. It's a tight kernel where you can just rip through very very quickly just trying to feed all the data in uh and just you doing this quick and dirty evaluation, right?
20:17 And so there's a bunch of experiments uh from 10 years ago that shows this phenomenon. So this is actually from the the vector wise guys um the people that were out of CWI were were ductb and came from in the co uh snowflake snowflake co-ounder. So the the blue line is the branching code and then the the the x-axis here is the selectivity of the predicate right. So when it's 0% then none of the tuples match when 100% all tuples matches.
20:43 So when it's 0% that's the great thing for the CPU like it's it's it's not doing that extra copy unnecessarily. it predicts that you're you're never going to fall into that if if clause. So the CPU, you know, this is fantastic. This is great. But then as you increase the selectivity and you see you basically peak around 50% where like 50% of the the tupils are going to match and 50% don't match, then the CPU is burning cycles undoing its the B branch predictor uh you know can't do anything to to to make this really work well.
21:12 Uh just keep getting it wrong and wrong. But the red line is is the the non- branching the branchless version I showed you. And its performance is basically the same because no matter what the selectivity of the predicate is, you're always going to copy every single tuple. It doesn't matter whether you're going to overwrite the last one you looked at or not. So its performance is basically the same no matter what. So yes, it seems wasteful that you're doing more work, but it's better for the modern CPU.
21:36 And that's what the modern OLAP systems are going to be really really good at that like a Postgress is not going to be or my SQL is not going to be right for analytics that these guys are really have tuned the the the kernels themselves that are doing these these these scans. We'll see how to optimize this even further. All right.
21:54 Does everyone know what SIMD is? Who here does not know what CID is? Okay. I have one quick slide. Uhhuh. All right. SMD stands for single instruction multiple data. Uh I thought I had slide. Hold up. I do. Yes. Here we go. All right.
22:18 So say you have this this you want to do X plus Y equals Z and say X and Y and Z are just matrices or vectors, right? So again, the way you would normally write this code in like CS10 and one, you have a simple for loop for every every single element in in in the in the three arrays or two arrays X and Y, assuming they're the same length. I'm just going to loop through add X I plus Yi and put it in ZI, right?
22:43 So if you do this with cy single instruction, single data, how you know most code is runs, right? You're going to again go through this loop one by one, add all these these these the elements together and write it out to the to this buffer. So in this case here we're doing we had what eight elements. So we're doing say eight addition instructions right cmd is allows you to do the same operation in parallel across multiple data items at the same time.
23:08 So in this case here assume I'm doing uh these are 32-bit uh integers. So I have 128 bit uh SIMD registers. They can be up to 512 or 1024 but we ignore that. So I can put four elements into a single SIMD register. Right? And then now it's a single cindy instruction to go take all the the you know the the first offset for this this array and the first offset of the sec second array add them together and then write them out to the the first offset in my output output register.
23:37 So now I do it for the first batch of four and then for the second batch of four. So before I was doing eighty instructions to add these numbers together ignoring loads and stores just deal with the addition operation. I can now do this in two. Get it? So there's addition, multiplication, subtraction. There's a bunch of other crazy tricks you can do. Uh but for now, we we can all ignore that. All right. So we talked about vectorized execution in terms of query processing. And it's an unfortunate name because you can people often times say when I'm doing vectorized query execution, they mean SIMD.
24:15 So now because I am doing the batch or the vectorzed execution we saw before of the query processing model where I'm taking a batch of tupils and then passing them up to the next operator. Uh so now I have a vector of things I could I could process simultaneously with SIMD. So
24:32 now I can I now for for basically all my query operators I can use SIMD to to run this these things in in sort of in parallel. Right? So again so here's that simple scan we had before but this was again the the branchless version. So I can now replace this with a SIMD version. Again, it's crappy pseudo code. This is not how you would really write this, but it's fine for now. Where I'm going to take a vector of tupils in the table.
24:54 Then I'm going to load them into my SIM registers based on the key or pulling the key out. And then I'm going to do a vectorzed comparison of these different uh of you know of of of the values that I'm looking for. That's going to produce SIMD registers with ones and zeros based on whether I match. And then I can take that and use that to decide which elements of my vector that I'm processing in this iteration of the for loop do I want to produce in my output buffer.
25:21 And how you get all aligned and everything like that. We could ignore that for now. So let's change this query to be like for for for looking for a key, right? Based on a a uh on a string, right? So say this is my table. I have I have a tupal ID column and I have a key. So I'm going to load in the the key into a single vector. again assuming that I can store uh eight eight characters right so the first thing going to do is that cd compare and what this what this is going to produce for me is a a bit vector or it's sometimes called a selection vector that says you know 01 based on whether the the the the element in that cindy lane then also within the cd register whether it matches my predicate.
26:03 So I can do that for the first uh for the first part key greater than equal n. I can do for the second part key less than equal to zero or sorry less than equal to the u. And then now I can just take those two uh mask registers or and then just do sim and on them that runs in parallel that just just doing you know a binary bitwise operation to produce you know ones and zeros where the at the at any given lane are both elements one.
26:27 Then I take the uh then I generate a simple array just has 0 to 7, right? That's corresponding to the offsets of the of the tupils just in in your where they would exist in in in the array. And then I just do a CID compress operation that just says if anyone if any value in the in one lane matches to one then just take whatever value is in there and produce it in the first output lane.
26:50 So now I get my offset matches 146 and that corresponds to the 14 the offsets 146 in my input vector that told me how to do this uh do this match right so you can do again this is just simple selection scans but you can do this for a bunch of different operators we talked about the semester all with SIMD right this again this is what snowflake's going to do what click house is going to do click house is even crazier because they have different uh for different uh there's like different size registers like 5126 like different versions that Intel puts out of Cindy.
27:22 They have all different variations of this because sometimes they're faster, sometimes they're slower. Um, but most most systems are going to target like AVX 256, AVX2. Um, and they'll write the right intrinsics by hand. All right. So, SIMD is one one optimization you can do. Another optimization you can do for code specialization is actually compile your queries into machine code. So there was a very old project uh in 2010 14 years ago out of Edinburgh uh and I think Amazon basically bought this guy and he was built this at at Amazon I think or Google one of the two.
27:56 Um so for given SQL query remember we run through the optimizer we get out a a physical query plan you can then take that physical query plan and then codegen like create C or C++ code that does exactly what that query wants to do. So instead of like in the bus tub code where you're interpreting the plan and then you you you invoke the operator and the operator has to go look at the plan figure out what to do, right?
28:16 You literally bake a you you you bake a a C code that does exactly what your query wants to do. Then you compile that and then you run that and that's like in the fastest you could possibly have because it's like it's a hardcoded program that does exactly what your query wants to do. So the bus way would be like this interpreted plan. So you got to go look at you have this this pseudo code you have this get tupal function you got to go get the schema for the catalog figure out the offsets of the tupal size based on what the the data types are return a pointer then you do evaluations
28:49 predicate and we saw that predicate tree before we have to traverse down and like the equal clause and clause figure out what whatever the you know whether the predicate is going to evalate to true and then if it does then then you return true or false. So instead you for a given query plan you can generate some templated code like this where you're now just going to fill in whatever the values and the that you have in your query and then you have you basically injecting that directly into this query plan.
29:12 You then compile this using GCC or clang or whatever your favorite one is right and then now you instead of invoking the interpreter for the query plan you just invoke a function that ex executes exactly your query. Does everyone understand this? Yes.
29:32 Is a compiled code expected to run multiple times? His question is compile code expected to run multiple times? Good point. Give me a sec. So his point his question is is you expect the pile code to run multiple times? Well, how many different ways can you write a wear clause? How many data types there are? Right?
29:51 How many uh like how many different variations could you have of a query plan in SQL? Isn't that infinite? No. Well, in theory it's infinite, but like in in actuality, no. So like think of like where select star from fu where ID equals four. ID equals some number. ID is an integer and I'm trying to compare against an integer. That's super super common. That's like, you know, that's probably 99% applications are going to be doing that that exact query.
30:19 So instead of compiling on the fly like I showed before, I could just pre-ompile what we'll call primitives of all these different var variations of the most common uh query patterns. And then I now at runtime when my query shows up, it says, oh, it's select star from table where ID equals 4. I have a pre-ompile primitive for integer equals integer. And I just invoke that instead of having to compile things. Compiling can actually take some time, right?
30:48 How long it take to run GCC? Well, bus stop is a big program. It'll take a while. Again, seconds. Uh, but for your query, again, you can take 500 milliseconds or a second. That's a long time, right? You don't want to be compiling your query for for a thousand milliseconds if the query is only going to run for 10 milliseconds. It's a bad idea. So, if you pre-ompile everything, then all now you're doing at runtime is figuring out here's the things you're going to invoke.
31:13 I built a little wrapper program around that just makes function calls into these things and I have all the the the pre-ompiled stuff for me. And of course now function calls aren't cheap, right? Jumps are going to be bad. We talked in supercal architectures that's bad. But if we do vectorized execution, we're passing a batch of tupils. Now our function call is on on a batch of tupils rather than one tupil at a time. And now that advertises the jump cost, right?
31:37 So again, here's here's a simple query. I have a a predicate on a string column, a predicate on an integer column. So I have a pre-ompiled primitive that says for a selection on a on a vector of strings and does does tell me what tell me the offsets of the t the tupils in my input vector that match some input string. Then I have the same thing for selection on a on an integer column for you know a 32-bit integer.
32:01 But now in this case here now I'm passing in the positions uh array that was the the offset array that was generated by the first function. I can pass this now to the second function. So then now when this function returns the offsets, it produces exactly the answer that I'm looking for. So there's there's basically two approaches to doing this this compilation stuff.
32:20 You can actually code gen exactly the query on the fly as you come along or in the case of like snowflake and duct DB, they pre-generate all these different permutations you could have because there's only so many uh and then you sort of stitch them together at runtime. And we'll see one system that we'll talk about today will actually do both. Okay, so this 15 minutes to cover the basics of how you do optimized query execution in analytical system.
32:45 Let's now go through a bunch of these systems and see what they're actually doing. Okay. All right. Google bitquery. This is so one of the original ones that came in the space and actually BigQuery started before Snowflake or the internal project. The internal project was called Dremel. This is somebody built in 2006 to to basically uh do data processing and run SQL queries on top of a bunch of files sitting in in GFS like CSV files and so forth.
33:12 Um it was originally a shared nothing system meaning you had to copy the data that was sitting in your your shared disk or your object store into the uh compute node. Then you can run queries on it. uh and then they end up rewriting the whole thing in in 2010 to now support Jared uh shared disc on top of GFS which is the now it's Colossus whatever the Google's internal file system right
33:34 and so you know we talked this before but Google was the without saying they're explicitly you know we're a NoSQL company but they were sort of the first ones like that were putting out papers say you don't need SQL like this is you know you want to be doing this other stuff um and then Dremel was was sort of seen as the thing that made SQL popular again at Google and then Spanner and others came along came along later.
33:58 Right? So they released this as as a commercial product called BigQuery in 2012. If you don't know what Dremel is, Dremel is like it's like a the it's a company. They make a like a power drill, right? I don't know why any like if I was Google lawyers, I would never let them announce that we named our internal system after some other company. You're just asking to get sued. Uh so that's why the product is called BigQuery, but internally it's called Dremel.
34:17 If you read the papers about it, it's called it's it's called Dremel. All right. So for all these systems I'm going to provide sort of basic overview like this or say here's the high level points about what these systems are actually doing and then now again this is you can start putting together all the things we talked about this semester and see okay now I know we spent a whole lecture talking about vectorized query processing now you know what that is and you understand what these systems are doing at a high level right they're all
34:42 slight nuances slightly different in in for the the the lowle details but a high level you know saying they're doing vectorized query processing you know enough about what they're All right. So, BigQuery is a shared disc disagregated storage doing vectorzed query processing. They have a shuffle operator that we talked about last class, but we'll see it again in a second. There they have their own internal file format at Google. I think it's called capacitor. There isn't isn't public of what they're actually doing, but if you talk to them, they basically say it more or less smells like parquet and orc, but it's PAX columnar storage.
35:12 They're doing the zone maps, the filters, uh, bloom filters, dictionary, and re compression. The only uh additional indexes they support are the inverted indexes that we talked about before. This allows you to find like keys within like a document like JSON or a tech text field. They only support hash joins. So no sort merge joins and they're only going to be doing uh the query optimizer is a combination of a heristic key a rulebased optimization but then they have additional optimizations while the query is actually running because of the shuffle phase. they can dynamically change or adapt the query plan on the fly as the data as they see the data.
35:44 So I want to talk a little bit about this because this is this is one of the key things that that BigQuery does that Snowflake doesn't do. Uh so BigQuery is always going to have explicit shuffle phase. So between every single pipeline they're going to run shuffle and they have dedicated hardware with custom silicon. They have custom I think FPJs or something that like that are doing the shuffle as efficiently as possible. Yes. Are these shovels like pipeline breakers? Question question is these shovels like pipeline breakers? Yes.
36:15 Right. Because it's data you got to send to somewhere else that you can't just you can't process locally, right? Because you need data from somebody else needs to do additional processing somewhere else. So the shuffle gives you a couple things. Gives you the the fault tolerance because now if a worker dies uh the results would always be sitting in this inmemory shuffle uh service.
36:31 So you can just spin up another worker and and uh that order worker can resume based on getting data at the shovel phase. But it also can allow them to do dynamic scaling of what they're using to compute queries because now um now you sort of have this pause between the pipeline breakers the shovel phase. You can say all right we we don't have enough nodes or we're unbalanced or we need more nodes. You can reorganize things.
36:56 So we saw this diagram before, right? Right. The workers are producing output that goes to the shuffle phase or show the shuffle service. And say that for whatever reason this guy here is super slow, he's falling behind. So all the other workers finish, but this guy doesn't, we just go ahead and kill him. And then you you then assign the work to this other worker who produces the results. And because it's always going to the inmemory shuffle and not some dedicated node or other node, there's nobody else, you know, immediately waiting for, you know, blocking this guy here, right?
37:22 They know, everyone else knows to pull from the shuffle service. All right. So this guy can then finish this up. We then they then maintain internal statistics about what the data looks like, right? It's not just a blind key value store. You're actually looking like because you're hashing into the these these these buffers and saying all right which partitions is getting full or which which partitions are underutilized. And then based on these statistics you can then say at the next stage before you even start processing the query at the next stage you say do I have enough workers or not?
37:48 And you can dynamically scale this up and down based on the data that that you're seeing. Right? So the number of workers between one stage to the next doesn't need to be the same. Another trick they can do is that they can dynamically load balance a single partition uh if it becomes too full and they're doing this as you're actually filling in the the the the partitions in in the shuffle phase.
38:10 So say I have two workers that producing output. They're both writing to these two partitions. And say partition two is is getting too full. So when this happens the shuffle phase goes to some coordinator says, "Hey, here's here's what's happening. I'm getting too full. this is bad. The coordinator says, "Okay, well, let's do more partitions."
38:26 So then now what happens is you send a notification to the other workers and say, "Okay, instead of for anything that would go to partition two, just do that recursive partitioning we talked about with with the grace hash join, right? When when when one bucket got too full, you would do another round partitioning for just that bucket. You do the same thing here. Partition two is getting too full, do another round of hashing for anything that gets uh you add to it.
38:48 Fill things up in there. Then now when when you finish the shuffle phase, you got to get things back out of partition two and fill it back up the other two partitions. So you just feed the data back in to another worker who then does another the same repartitioning again and then signs it to the the new partitions there, right?
39:05 And you just you just kill the kill the other one here. So BigQuery makes heavy use of the shovel phase to do a bunch of uh dynamic optimizations that you couldn't do otherwise without it. It would be very difficult to engineer that. And then now what happens also too because you always have this explicit shovel phase. It makes it very easy to scale up and out the different operators and each operator implementation does not need to be aware of like oh I'm going to be a scan on these number of nodes.
39:27 It just says I need to scan this data produce my output here and the shuffle phase hides all that complexity of of the scaling out and scaling down. All right, Snowflake. Snowflake is uh I said it was one of the the original if not the original cloudnative data warehouse, right? Uh that was you know really designed from the beginning to be something sold in the public whereas like Dremel was in internal and they said oh this is a good idea but they they exposed it to BigQuery.
39:55 So it is a managed uh OLAP data system written in C++ be shared disk with expense a very aggressive comput side caching right because Snowflake is paying for the reads to go to to S3 right so if they can do caching on local uh local discs on the EC2 nodes uh of the data you don't have to worry about you don't have to end up paying Amazon for that over and over again so one thing that's interesting is that they wrote everything from scratch they didn't borrow any components from any any system it's very common now to take the post front end parser right and reuse that and then build a new system underneath it.
40:29 Yugobyte did this uh or cockroach DB started with Rox DB as the internal storage like they wrote everything from scratch including their own custom SQL dialect and and network protocols which is very rare today. Nobody would do this and uh I always like to show this. So again we know that the Snowflake co-founders uh and I said I was I was in Amsterdam with him a few weeks ago. He's this hardcore about databases. So he has a snowflake tattoo on his leg.
40:55 Uh that's that's how much people care about databases. Okay. All right. So of course he's he did okay. He's fine. All right. So what is Snowflake? Cloud native lab system. We already discussed this shared disc. They're doing pushbased vectorzed query processing. Uh so the vectorzed query query processing model. That's what the snowflake tattoo guy invented at CWI and vector wise and then he later been built in in uh in Snowflake. The pushbased model came from the Germans.
41:21 Uh but they're sort of combining a bunch of different techniques together to make this all work. We'll see and see duct DB switches from pullbased to pushbased later on. They're doing pre-ompile operator primitives which again that came from the vector wise project. Uh they're separating the data table from the metadata. Basically they run foundation DB internally as the catalog rather than just like in Postgress they store the the catalog data in with the the table data all together to the same database.
41:46 They're now storing them separately. They don't have a buffer pool, right? So they're not worried about spilling the disk. It just is is seeing my cache yes or no. And they have a separate service to handle all that. They have their internal file format that that basically looks like packs uh clar storage. But again, they also can read uh read data from parket and other things as well. That's new. All right. So they're doing pre-ompiled primitives as we talked about.
42:08 They're just using C++ templates for all the different possible data types you could have. uh and then they just compile that and that gets linked into the project at runtime or the binary when when you run it. they only use LL uh they only use on the-fly just in time compilation for one part uh and that's if you're if you're serializing dializing data between workers then they will then codegen with LLVM
42:32 uh the the program that says I know how to take this data and and serialize dialize is if you ever use protocol buffers from Google or protobuffs they that's basically doing the same thing you define a schema and then it generates the code for you that to to read and write the data they don't support partial query retries as far as I know I don't think it's changed So their argument is they're so fast that if a worker fails then who cares just restart it again they're not paying for that you are.
42:54 So from engineering perspective it's just easier for them. So one of the cool things that that snowflake can do one of the optimizations for adaptivity is they can push down aggregations if they determine that the amount of data you're shoving up is through the query plan is going to be expensive. So what'll happen is as you're doing like I say a table scan on this side of the join if you recognize that this thing is producing a lot of data and all you're really going to do is aggregate it up above after the join
43:22 then you can basically turn on an aggregation sort of an early aggregation of the data still do the join on it and then you just change the query plan at the top and say okay I know how to put this in the form that I would actually need right so they run it without the the the aggregation push down but if they notice your data is changing uh your data is larger than they expected then to go ahead and push that down.
43:44 I always like to bring this up because one of my students who also took 4465 many years ago, he's still at Snowflake. Uh he worked on this and he wrote a blog article about it, but he was a good dude and he still and he came when Snowflake came to visit a few weeks ago. He came back to visit. He's a good dude. All right. One of the things they can also do because now in the cloud,
44:03 what you can't do if you're on prem uh or at least not very easily, is that because on the cloud it's it's elastic, you can kind of throw more nodes in to if your query's running slower than expected. And we saw this in the case of adding more workers in in um in in Google like that that's just running Kubernetes or Borg which is their version of of Kubernetes right they can just add more workers and that's no big deal.
44:27 Uh but if you're on prem it's very hard to do but one of the things that that Snowflake will do is that if they recognize that you're you have a really large scan here that's going to start running slowly. So then then they'll change the query plan to to pull out some portion of it of it. Then they run that on spare nodes aka idle nodes.
44:46 So if you're customer A and you're not running queries now, customer B comes along and they need some extra extra resources, they'll borrow yours. You don't know, you don't care. You're still paying for it. That's fine. And you know, if your query needs to run and they need extra resources, you can borrow from somebody else. So they they have this the notion of like a bullpen. have sort of spare resources based on idle customers they can then reuse to make your query run faster and they don't charge you extra for that.
45:11 So you scale, they call it flexible compute. You scale out some extra stuff here. And then now uh since this is running on somebody else's hardware or somebody else's machines, this will materialize the output just to to storage like that'll be like a local cache that they have. If it's too big for that S3, whatever. And then now the this all gets computed. This can die at any time. If if they need resources, that's fine. But then the they rewrite the query plan to now do a table scan on this materialized result as if it was like a native table even though it actually got produced from another query running on somebody else's hardware. Right?
45:47 And again you can do this in the cloud because the the the resources are fungeible. Most machines are idle like your laptop right now. You're not doing anything on it. Uh and so like it could be doing could be could could be running queries. Okay. Redshift.
46:05 Redshift is uh Amazon's flagship OLAP system. They have a bunch of other products. They they have this thing called Athena. That's just Presto DB that they change the name on and slap it up and sell it. Amazon is notorious for taking other systems, rebranding it, putting it up and then seeing whether it makes any money and if it does then then they then they put the energy into it. That's what Redshift was. Redshift is a fork of is based on Parkell.
46:26 Parkell was a a fork of Postgress. It was a distributed version of Postgress. Park Excel was was backed by VCs. Uh they didn't really get a lot of traction. Amazon bought a license of the source code to them for $20 million. Uh and then basically ACT bought Parkell later on for I think less than that and Parkell basically died. So Amazon only paid $20 million to get get a start on Redshift and it makes billion dollars a year.
46:52 Now they spent you know millions of dollars to like rewrite all the code but that's how originally started. They just said we need a we need a OLAP system. They bought a license to park, slapped it up, called it redshift. Why is it called red shift? No.
47:06 Well, it's yes, but what shipping? Boom. There shifting Oracle. What is Oracle's color? Red. There you go. So, uh it's so originally it was a shared nothing system based on Postgress. They've added this this this serverless piece that had this thing called Spectrum. Now you can read like a lakehouse system. You can read from S3 and so forth, right? Their big goal was to remove as much administration and configuration choices from users as possible. I don't know.
47:33 I don't think they've succeeded in that in the same way that Snowflake has. Uh I think Snowflake does a very good job of hiding all that from you. I I haven't used BigQuery, so I I don't know how well it does, right? So it's more of a it was originally started as a more classic data warehouse where like it wants to manage all your storage for you. Uh I mean Snowflake sort of does that originally started that way as well, but since over time they've expanded to support reading things from S3.
47:54 So all the things we talked about before shared disc aggregate storage pushbased vectorzed query processing the things I want to cover though is that they're going to be doing both compilation techniques that I talked about before that they're going to do the codegen or the holistic query compilation where they generate the query plan then they're going to compile that but for the parts that are going to be common reusable they're still going to do the pre-ompile primitives that we saw in snowflake uh and and vector from earlier right
48:23 we want to talk about all the caching stuff and the sorting stuff uh but I just want to bring up the also have additional uh they they have accelerated hardware in the same way that Google BigQuery has hardware to make the in-memory shuffle go faster. They had this thing called Aqua that would make actually your scans go faster. This is dead. They changed it. We'll cover that in a second. All right. So, they're going to be doing compilation for for queries.
48:45 So, a query shows up, they're going to generate C code and then they're going to invoke GCC to compile it. GCC is expensive. So, what happens when you call GCC? It's got a bunch of config files, right? Then it's got to actually, you know, parse your parse your your your code, then actually run all the compilation steps, right? GCC 0302 is expensive even if even if the program is really small. And as he as he said before, as I said to him before, like there's not that many var variations in queries.
49:10 And also, if you're a cloud vendor, you see all the queries. So what they do is they'll they'll have they'll have um they generate a query plan then they check a cache to see have you run this query before. There's a paper that came out from uh Amazon this year or last year that says I think 96% of the queries in Red Shift are exactly the same like not just the same SQL with different parameters literally the same SQL with the same parameters.
49:35 So people running because it's like a dashboard you're running the same thing over and over again. The data changes but the queries are the same. So they're going to check their cache to see whether for you have you run this query before? If yes, then they use the cache query that's already compiled. They use the shared object and just invoke that. If you don't have it in your local cache, then they take a global cache for the entire fleet of all Red Shift customers, right?
49:55 This is insane. Every every query anyway's ever actually ran, they have a cache query plan for that. And then if you if you if you run a new query you never that you've never run, you can get the you get the clash version from somebody else. And then because it's SQL, there is no proprietary information that you're leaking from one customer to the next. Right? And if I call select star from table where ID equals 4 on on my my data and you call basically select star from data from table where ID equals six and they're both integers on your table.
50:26 Again the query plan doesn't have any specific data in it. It's just the query plan. I can reuse that from one customer to the next. And at Amazon scale like you know for for the the billions of queries they're running per day not having to compile every single one saves them a ton of money. your query runs faster so you're happy but then they save a ton like millions of dollars a year by re by having this cash.
50:48 I had one of my students did an internship where they had u they worked a project where every time a new version of red shift came out they had basically a job that would go through and and take the query all the query plans and recompile them right so that you always had you made sure you run the right version of red shift because the data alignment might change and so forth so I think this is public I can say this the cache hit rate for them is 99.95%.
51:12 So any query shows up with a 99.95% they've seen it before. So you're not you're not unique, right? And then the uh that's for the glo that's for the local cache. Then for the um if doesn't ex exist locally, I think it's like 87 88 89% it's going to be in the global cache, right?
51:34 So 90% of the queries handle local cache and then 80% of the queries that don't handle local cache will be handled by the global cache. Yes. So then does it take does it just take less time to go get it from the cache for like all these different queries even have to go to the global cache than just compiling it then and there. Question is is it faster going from the cache and then compiling it? Uh I mean potentially yes but then like the the compilation the compilation is CPU CPU intensive right?
52:01 So again for one query no big deal for billions of queries at their scale it's a huge and that's going to save them a ton of money. Absolutely. All right. As I said, so I said said before, so they had this thing called Aqua that came out in 2021 that it was basically doing predicate pushdown on FPGAAS running on a layer above S3. So your query shows up and wants to read some data from the block, you always go to this thing called Aqua first.
52:29 And this knew how to get data from the the from from the storage, but it could do a predicate push down. So it' say uh go get the blocks you would need from storage, bring them up into the aqua layer, and then that had FPGAAS that could run your wear claws super fast in in uh in hardware and then it produced the filter results up above. Now that idea is not new. Uh there's a thing called NTZA came out in two 989 that was had FPJs running inside of Postgress.
53:01 IBM bought them. I think it still exists today, but you you can't get it with the FPJs. I might be wrong about that. Uh Oracle does this with exodata. not with FPJs but basically they have they have a shared disc architecture and exodata but they have uh you can do predicate push down and run the wear clauses on where the data actually exists right so they quietly killed this uh in a year last year two two ago and what they changed is that now uh they have uh on the nicks
53:30 on the actual uh the storage storage nodes themselves you can do predicate push down and run queries uh inside of the nicks themselves right it's this thing called Nitro. It's it's it's their um it's their hypervisor. It's the cards. It's all sort of the all the specialized hardware that Amazon fabs and builds running in in their data center. And they can do this because at their scale like $150 million for R&D to to go fab hardware is a drop in the bucket because you're going to save, you know, save well over that and charge people a lot of money for it, right?
54:00 So Harvard's going to get weird, gonna get wild in the next next uh 10 years. Uh if it if it isn't already actually wild, but it's all going to be the big cloud vendors like like Nvidia is going to do it thing of course, but like Microsoft, Google, I mean they've been doing this for a while. They they fab their own hardware, the TPUs, the the Aqua stuff, and so it can be very hard to get the kind of performance that they're going to get because they control the whole stack and they can fab things.
54:26 All right, so that's Red Ship. All right, so next one I'm going to bring up is yellow brick. This is not a well-known system, but I like it because it's it's pretty wild what they're doing. This is hardcore engineering and they hate the operating system as much as I do, which is fantastic, right? So, this is a fork of Postgress 9.5. It was all written in C++ and they basically retain the Postgress front end. So, queries show up and it's that that part is all still Postgress.
54:51 Oop, sorry. the um but then now when you actually run the queries all that's going to be custom code and that that's a very common setup like Yugabyte does the same thing as I said before um so they originally started as an on-prem appliance that ran with FPJ acceleration like like I just talked about so they had you'd buy like a a rack unit that had the storage had all the data and then when you ran queries it ran fast with the with the FPGAs but they switched to a database service now and you get it in the cloud we're not going to talk about this too much but one of the cool things they do use uh is that they use for the control plane, they use Kubernetes for everything.
55:24 So instead of having to write your own like distributed cluster manager and uh the control plane to keep keep track of whether nodes are up and the coordination of of who's getting what data and when, they just rely on Kubernetes for everything. And they actually expose like a SQL interface to you can change uh change Kubernetes configurations through SQL through yellow brick. I think it's kind of cool. All right, so what are they doing?
55:46 So they have shared disc storage like everyone else doing pushbased vectorized query processing. they're going to do a the the full query compilation or the holistic query compilation by generating C++ code and then then invoking that with GCC but of course then need to cache that to make you know to make sure that you're not spending the cost to doing that over again. Um I want to talk about that compilation piece and then all the crazy engineering that they could do to make this thing run as fast as possible. Right? So this is what the highlight basic archite is postgress queries show up through here.
56:18 They then hand it off to this compiler service that runs asynchronously that's going to start compiling the the C++ code for your query uh in the background and then they have thisuler here that again distributes out the the requests to the different worker nodes who can then pull data from S S3 or the object store as needed. to avoid uh since you need to get data into the system. So they're not going to be like uh a lakehouse system where you just read you write a bunch of parquet files and object store and and and read them.
56:43 They're going to have this you have to it's a managed service or manage storage. You have to you have to insert data through the database system. So if you go through postgress that's going to be really slow. someone's like bulk loading gigabytes or terabytes of data. So they have a they have a sort of sidecar method to get data into the system that can just bypass uh it bypasses postgress front end and just can store things directly into it.
57:04 So what's wild about what they do is that when the system boots up, they call Maloc, get as much memory as they can, and they never make a CIS call again, right? They they they they allocate all of the uh the threads that they need, allocate all the memory they need and then never talk to the OS. This is actually very common in embedded systems. Uh but these guys, you know, for data system, these guys are doing doing it right.
57:30 So that means that there's a bunch of stuff they had to get crazy performance. They wrote their own everything. So they don't use TCP. They they run their own uh network protocol on top of UDP. They don't use uh they don't use the built-in drivers in Linux to talk to MV MVME devices. They wrote their own MVM MVME uh drivers. They wrote their own SSD drivers for the DB system, right? They don't use the the Amazon SDK for communicating with S3.
58:02 They wrote their own drivers for that, right? They're doing uh kernel bypass. Uh so they're not letting the OS copy buffers from TCP or the the nick into putting user space. They hand manage all that themselves. Yes. What does it mean that the row store and the object store are separate? What's the difference? All right. So question is what does it mean the ro store and the com store is that? So going back here. Oh, up here. Sorry. Yeah. Yeah.
58:22 So very common that what you would do in in these OLAP systems if you want to support uh like transactions again we talked before with unis store you not at like the high end like million transactions a second but like I want to do I want to get data into this thing so it's expensive to store data to write it out as a column store especially if you don't have all of it yet to put it into a giant file so you just have a little buffer space in the row store you just it's like a think like log structure storage append depend append depend I can do that very fast when the the me table was full.
58:53 Then I compact it, convert it to a column store file, write it out of disk. So the object store is the column. Yeah. Yeah. The all the colometer data is in the object store. The row store is like the most recent data and then some background job will put that in there. All right.
59:08 So uh they're doing pushbased query query processing. Um and they're support you know row and columnary data as we talked about. They're doing the complete query compilation again taking your your query plan generating C++ code and then forking GCC. Right? We won't talk about this too much, but like they're the way they design their their compilation service like the code that they're generating is it wants to have really really tight kernels so that at any given time you're you're reading data from your your least CPU caches like going to memory is even too slow for these guys.
59:36 They always want to be reading from from L3 as I said before they allocate all the memory that they need. uh they are using mop but m map but it's anonymous pages but they use mlock on it to prevent the OS from paging it out right and they claim that their allocator is 100x faster than malo that one I that's not surprising I don't know how much faster they are than J Malik but again like think of like J Mal is trying to support any possible application if you know exactly what the kind of data blocks you're going to be you're going to be allocating and you know what you're going to be freeing them you can do way better than than existing systems yes
1:00:13 how would it work if it's using Map because I think we mentioned using MAPAP is like question MAP is bad but MAPAP with when you call Mal is basically MAPAP right but I'm saying if you use MAPAP to allocate to MAP to manage the movement of data in and out from disk into memory that's bad don't do that they're just calling MAPAP to allocate a bunch of bunch of data using huge pages we've been talking about like instead of getting like a 4 kilobyte page from the OS you can get like a I think it's 2 megabytes or or one gigabyte page you basically get huge strides of memory and you call mlock on to say tell the OS never page this out with virtual memory.
1:00:50 So it's basically like turning off Map's paging mechanism in in the OS because the OS is going to try to screw you over, right? So they again they make a use of a bunch of custom components like kernel bypass and everything to make this run as fast as possible. They're using the the MySQL style LRUKs that we talked about before to to store cache data files and and evict them.
1:01:10 I've never seen anybody do this, at least publicly talk about it, which is seems insane, but like they're like, "Oh yeah, the crap you get from from from from Linux for for NVME and and and uh internet nicks or Ethernet nicks, they're too slow, so we're going to write our own drivers uh and load that into the kernel."And so again, these are the numbers that they're showing. They're not like insanely better.
1:01:37 Uh, it's better, but like it's not like you're getting like a 10x better. I like it because they did it. Uh, but I'm saying it this is probably if you're a new database company, this is probably not the first thing you should consider. All right. Anyway, just just showing again people care that much about performance and databases that these guys are willing to write their own kernel drivers, right? There are some people that that want to basically switch to a unicel.
1:02:02 You basically write the OS to run nothing but the data system. People tried that in the 80s. It's coming back in vogue now. We'll see. All right, got 16 minutes. Let's go through data bricks. Okay, so data bricks is based on spark. Uh but spark is is yes quickly. Can you go back to yellow? You mentioned that the cloud version uses kubernetes for our components. Yes. Doesn't that create another like set of constraints that slows down the question is the if you're using kubernetes
1:02:30 doesn't create a bunch of constraints that slow down the system like why would that do that right? because it's not a virtual it's not a virtual machine like the the container the the the process just running inside a container but it can still talk directly to the hardware
1:02:43 right like you don't have it's it's just a way to say it's a way to have a global management of the processes that are running on a bunch of different nodes but it's not like a VM where there's a hypervisor that that's that's slowing you down because course now you're running in if you're running off EC2 there is a hypervisor there the firecracker stuff or whatever that like the Amazon controls but like that they've optimized pretty pretty much but you still like if you get the bare metal machines on EC2 you can talk directly to hardware
1:03:12 all right data bricks data bricks is is a um originally based on Apache Spark uh but it turns out if if you're running queries in Spark for OLAP it's actually really slow because it's a it was a row based system and it was written in Java or Scala which runs in the JVM and the JVM like the OS is do a bunch stuff that's going to be get in the way from your your beautiful database system.
1:03:34 So, they end up having to build this this additional um it's not a it's not a standalone engine, but it's an enhancement to this to the Spark runtime called Photon that basically is going to be a bunch of C++ uh code that when the Java code starts running your query, it says, "Oh, I have a C++ Photon version of this this operator of this kernel that I want to run and it invokes that in in instead of running the slower Java version." Right?
1:04:00 So there's a bunch of things about about uh the spark that we don't really need to get into but like they basically had an earlier version of spark was SQL that was based on it's called shark was based on the hive stuff we talked about when you take a SQL query converted map produce jobs so they had the SQL query show up and then convert it into um to map produce jobs running in spark but that was slow and they they built a custom engine uh on top of their spark SQL and then that was all based on Scala that was doing uh they were doing code generation but it was generating Scala code and then for really big tables and really big queries the JVM would freak out and say I can't compile this for you and either fall back to this low interpretive version.
1:04:37 So photon is trying to avoid all of that by going directly into seamless laws for the certain operators. So there's a paper came out a few years ago that uh discusses photon and then the students I'm highlighting here uh these are students that that have taken 445 65 or 721 uh or this is my former PG student Brashant Ryan Johnson got his PhD from CMU uh before I started so many years ago. There's a lot of CMU people working on data bricks and working on photon. All right.
1:05:02 So what is photon along with spark SQL? What are they actually doing? So again shared disc storage all the things we talked about before. The one I want to cover here is the pullbased vectorzed query processing and then how photon fits into that uh fits fits into this. So photon is going to be a pullbased vectorzed engine that's going to use pre-ompiled operator primitives that we talked about before where the at when the query shows up you generate the query plan you then identify which portions of that query plan could be offloaded to a uh to a photon perimeter photon operator and then now you're making passes over through JNI the Java native interface going from Java world into C++ world and letting that run as fast as possible.
1:05:41 So now datab bricks had previously built a uh a code compilation engine that we talked about before. They would actually take the again the entire query plan generate scola code or or scollet bite code or whatever it was called and then compile that the JVM. And as I said it didn't work out great because the JVM would freak out when things were too big and then it turns out they struggled a lot getting good performance because you kind of need to know databases to to to
1:06:08 build this kind of query engine but you also need to know the internals of the JVM. and understand what that's trying to do for you or or trying to not do for you when you're on your query plans. And so that they had struggle finding engineers to work on this and they spent a lot of time just trying to get this to work. And then when you actually want to start um well they they found themselves
1:06:30 basically running a bunch of tools and and and mechanism to get data out of the engine to understand what the GBM is doing rather than spending time to make the query engine just run faster by itself. So when they built Photon, they switched over to running everything C++ because as you guys know in this class, you know, working on bustop, there's a lot more people running that know C++ and database systems than people know JVM internals.
1:06:52 So it made they even though initially the the first prototype they were building with the C++ engine was not as fast as maybe the previous one, they were able to iterate it more quickly and have a more agile development process and get better performance and and and take advantage of Cindy and all the other things that we've been talking about so far. So one of the things they they do slightly different than um in some of the other stuff we've seen before is they have this notion of expression fusion.
1:07:16 So we talked about operator fusion before we said like if I have a like a predicate and a scan clause I can combine those two operators together right and you can do this in a codegen engine because you say the the the scan is just a for loop and you just put the the the predicate be in inside of that that for loop and so they don't want to do we'll call that vertical uh fusion. They don't want to do that because there's there's like from usability standpoint, it's hard to understand maybe what's going on for certain things.
1:07:43 So instead, they're going to do what I call horizontal fusion where within multiple predicates within a single wear clause or filter, they'll combine that into a single function or single uh compile primitive. So say you have a query like this where you have a between calls on a date, right? So normally in a in a pre-ompiled primitive system that you would have separate functions to do like the less or greater than equal to on the date and less than equal to the date and you would invoke these both separately at runtime and just take again the output of one and feed into the other.
1:08:11 So instead what they're going to do is they identify these patterns when you see the same predicates over and over again and they'll combine them into a single function right because then now when I make my call into uh to these different functions I'm only making one function call and again because it's a cloud service you see all the queries you know what all the different patterns you could possibly have and so you know there's there's yes it's infinite what you could generate but like in in actuality it's finite and it's reasonably sized all All right.
1:08:41 So, we talked about other tricks you can do when you have uh with the shovel phase and identify when you're running out of space. So, one of the things that they do is that they recognize that if these these partitions are underutilized, then they just have a separate an extra step after the initial shuffle phase to go take the data from the the underutilized ones and then fill them up into uh to another one. So again, it's like recursive partitioning but in the reverse.
1:09:06 Instead of splitting up further, they're just combining it when you recognize things are are idle. All right, two more. DuctTB duct is the opposite of all this. DUTDB is not a a a highly paralyzable scale scaleout system. It is a parallel data system, but it doesn't run on multiple nodes. It's running on, you know, on a single machine. So it's a shared everything system. They support the Postgress dialect. uh and they have a bunch of changes they made to the SQL to through the SQL interface to make it your life easier like you know like queries or select star from from table
1:09:42 you can actually do from table select star you can actually change the order of these things right breaks the SQL standard but like they it makes people happy so they they do it right and it's really designed to be an embedded system that allow you get uh data in and out of other applications and then process them in in ductb very very quickly so think of like I my Python uh notebook or Jupyter notebook. I want to I have some data.
1:10:05 I want to make some do some processing with that notebook. Instead of you know instead of doing a complete separate system to do that, I can make a call into duct DB. It then passes arrow buffers in memory uh basically columnar storage that like that the the Python notebook knows how to understand and and ductb knows how to understand. So without having to do extra copies, I can just pass data back and forth between the Python world and ductb world without making extra copies and things run really fast. it's nearly entirely custom C++ code.
1:10:31 Uh their big thing is that they don't require any thirdparty libraries or dependencies. Uh like I don't think they even support SSL or if it is is a separate extension. Um and then this makes it really easy for them to then kapal was and you can run ductb in the browser and all these other weird locations.
1:10:50 So, this seems kind of weird that we just spent the last half an hour talking about all these like super expensive big scale out systems like Snowflake, BigQuery, Data Bricks, uh, and Redshift. And Duckb says, "Oh, no, you don't need that. You can run on your single laptop."Well, it turns out that most queries, most people don't have a lot of data.
1:11:09 So, this is a survey that or it's a collection of computed by this guy who's CEO of Fiverr. figure five is like the we talk about ETL like they're moving data from the from one front end system to to another back end of data warehouse and they just looked at he looked at analyzed a bunch of data put out by red shift and snowflake what queries actually look like and most of them are only processing about you know less than a gig of data right so most of the queries running red shift and snowflake are not in the the pabytes or terabytes
1:11:38 it's one gig that's on your phone right it's nothing so ductb is basically saying the argument like okay Well, most people don't need a lot of data. Why go spend a lot of money for something like Snowflake and Redshift where when your laptop can do just fine or a small machine can do just fine, right? And I I think I think there's a lot of merit to that, right? Most people probably don't need a Snowflake, right?
1:12:00 Now, there's other things that Snowflake and those guys can do that like DuckB can't do in terms of like sharing data, generating reports. Like there there's a lot of value to that that if you're running on a single box, you can't can't do. Uh but for quick and dirty data processing, duct DB should be, you know, default choice for a lot of people. All right, all the stuff we talked about before, we have we didn't talk about morsels and stuff like that.
1:12:22 We could have talked about that. It's a way to basically break up work and hand it off to to uh to workers for execution. Um that comes from the Germans. Uh actually a lot of these ideas come from the Germans. So they do pre-ompile primitives from uh like we saw in vector wise, but the pushbased vector create processing is super fascinating because they started off doing pullbased processing, right? They were originally a full-based system with still with pre-cloud primitives and then in 2021 they did a complete rewrite and you can go see the PR here from Mark where basically talks about here's all the design decisions of why they're switching to a pushbased model instead of pullbased and one of the big things they talk about is in their world where like when you do the get next get next in a poolbased system uh that like if now in a leaf node it's got to go read something over the network like go read from S3 you don't have an easy way to then pop up the stack and say, "Okay, I this I'm doing this read.
1:13:14 Call me later on, but you can go do other stuff right now." But it's a pushbased model. You have a centralized view of what all the the various jobs that are running and you can make better decisions about who gets scheduled or not gets scheduled. So again, they they start off pool based and they rewrote everything. It's fascinating. We didn't really talk about what the inmate data looks like for these vectorzed systems. Like in Bus Hub, when you pass data up, it's just like here's the rope, it goes up, right?
1:13:37 There's not really any magic to it. just make popping things as you go up. But in a in a vectorzed system if you see repetition in data you actually can do some lightweight compression as you move data from one operator to the next and avoid having copying entire tupils entire records right so say I have a single column of data if I know uh my data is completely unimpressed looks the same same way but if I have special cases like if it's a if it's a it's a vector where all the values are the same
1:14:06 why copy that why copy up data with that you know the value repeated multiple times I'll just have a special vector that says hey look you have one here's one value and repeat it x times it's like the run length encoding you can do do same thing for dictionaries you can do the same thing for the delta encoding like if you know if you're reading a primary key column again rather passing 1 2 3 4 5 six you just pass you know I have six values increment by one
1:14:28 right so they're basically doing encoding uh to compress data as they're moving from one to the next do this on the fly and that's speed things up a lot and you use less memory but then now the challenge is going to be how do I make how do I have a uh for all these pre-ompiled primitives you don't want have to generate a for every single you know possible variations you can have like less than greater than all the the wear clause options you could have you don't have then another pre-ompile primitive for every single possible vector you could be sending up.
1:14:54 So they had this unified data format uh where all the vectors basically can look the same and you just have some best some additional metadata to keep track of like what kind of vector it is and how to interpret the data. So if it's uncompressed, you have the data you you keep track of the data and then you have this thing called a selection vector and it's just basically telling you what values should be set, right?
1:15:12 Or you know what offset would correspond to these different values. So if I had the constant one, you just say here's the selection vector that I pass along say they're all they're all basically the same thing. So he's basically saying like as I move data from one vector to the next, all the vectors are going to look the same or have the same basic layout of of of data. just there's an extra flag to tell you what the type is and you can just reuse the same pre-ompiled primitives that we saw before. All right, let me talk about the last system, Tab DB.
1:15:43 When I this is probably the one system in in in my career when I found out about it, I was like, damn, this is a great idea. I wish I invented it. It's pure genius. So, Tab DB is a relational database system that runs in your browser and they store data in the titles of your tabs in your browser. So, it's actually running SQLite. Uh, we'll bring up a demo.
1:16:05 It's running SQLite compiled with uh uh incripting. I'll make it a little bigger. Right. So, let me get rid of this tab. So what we're going to do is uh we're going click this and add a bunch of tabs. Then we come down here and do create table. Run that. And then now you see that in the titles of the tabs that's your data. So now I do an insert. Boom. That updated some stuff.
1:16:34 Now I can run a select and I get results. And basically what SQLite is doing says in the browser says here's my tabs, right? Look at the titles. Here's the data. Genius. What's the max of the title? Uh, I don't know. Looks like 100 characters.
1:16:54 Oh, 100 characters. Yeah. So, we got some more there. Right. Done that. So, if I sort like a super long thing, it's just going to open more tabs. Uh, no. I I don't think I want to open it. Right. If I do, you want to do like this.
1:17:20 Let's do Yeah. Like this. Let's see what happens. Oh, yeah. I took it. Oh, look at it. Truncated, right? Oh, no, no, no. It's took it. Let's do update. So, update. What is this? People. I hate typing on this thing. Update people.
1:17:54 What is What was the first column? Name. name equals name plus name. Oh, where's the table name? Sorry. Oh, thank you. Let's run a few more times. See what happens. Now, now we're not going to know whether it's correct not though, right? cuz like I got truncated. There you go. Right.
1:18:34 Genius. I tried to get this guy to come to give a talk at CMU and then I was going to try to get it be like a distinguished lecture and make it like pretend it was like a big deal that he was coming to talk about Tab DB and try to get like the mayor's officers to come and like see. Anyway, all right. Genius. Uh, all right. So, that's it for the semester. Okay. So, hopefully I I convey to you guys how awesome Davises are.
1:18:55 Uh again as I said earlier today you guys were discussing oh about uh uh you know data in the real world in the cloud computing class um like again even if you don't go off and build database systems as a job I guarantee you in your life even if you're not in computer science in tech you're going to come across databases and at some point someone's going to say to you hey this query is slow this database sucks like and you're going to be like what's going on and you guys will now be in a better position to understand what data systems are trying to do for you And are you working against them or are you working with them? Right?
1:19:28 I would say that also too if you if you go off and do a startup or or you know try to build a a new project, new application, you want to avoid making premature optimizations and assuming that oh my database is going to be huge therefore I got to choose this snowflake or choose one of these big scaleout systems. your first choice should be posgress and then after that probably should be at this point duct db right and that'll get you maybe like you know uh 99% of the way there
1:19:57 right and at some point if posgress or ductb starts falling apart then at that point you probably have money right nonprofits whatever that's harder but like at some point you'll have money to say okay now I can hire somebody to go build a a large scale system or switch over to a larger system but you avoid doing premature obsations at the very beginning postgress will for nine out of 10 people is going to be Good enough.
1:20:17 Okay. Any final questions or comments? Talk about mother uh mother duck. You're talking about mother duck. Wait, what's in a second? Yes. Is there some practical guide you would recommend in terms of backuping datas in Postgress? These are very specific. Okay. Uh his question is like what should be the how should you back back up data in Postgress? Yeah. Uh there's PG backup. There's an extension that does that, right? Isn't it just dumps a huge single SQL file?
1:20:48 I think it can do delta discs. I think I think the Yeah, you do that. Just append those back. I mean, so I mean that's basically what I do for like my my the data my website for for DB.io is like not that big. That's what I do every night. Uh if you're running like an RDS like Amazon whoever the cloud service provider will do that all for you. But PG backup if you're just running location should be good enough.
1:21:11 Yeah. Wouldn't it be simpler if you could just have like lots of replicas? Wouldn't you have a bunch of replicas? What are you running? Are you running a real website? You just running like your local blog? No, I'm not I'm not trying to like belittle you. Maybe it's something like a little bit big but like not too big. How how big?
1:21:33 100 gigs or And how many how many active users do you have? No, just a hypothetical. Oh, okay. Right? You can get by in the very beginning Postgress with PG backup writing it out to external storage that will be good enough for a long time. Right? And and then there's I think there's more sophisticated ways to do deltas. Now for high availability, you do want to do replicas, right? And Postgress has gotten better at that. So yeah, you want to have a standby replica.
1:22:04 Now you got to start managing that crap yourself. Again, if you're a startup, you're probably better off just using a hosted provider like Neon will give you whatever the the first first the you could start off free. Yes. Like, do you recommend managed DB or just manage the DB on yourself? This question, do I recommend using a manage DB service or managing yourself? Again, it depends on how much money you have and what you're what you care about, right?
1:22:28 If if you're how to say this, if like if you're if you're trying to sell if if you're trying to do a new startup, which I'm happy to talk to you guys about, if you're trying to do a new startup and like no one's going to care, oh, I'm running on Postgress and it's backed up and it's like versus running yourself, then like you're better off spending the time making the application better. So then yeah, offload it to a managed service.
1:22:51 Let them handle that for you. Like I said, I'm not trying to shell for Neon, but like I think they offer like a the free tier for like like and it's pretty generous, right? Uh your question was about Mother Duck. Yeah. So Mother Duck is the a commercial offshoot of DuckDB.
1:23:06 It's not wasn't founded by the original Duckb guys. It's actually was founded by the the guy that helped big bigquery, right? And he has a blog art says basically the slide I showed before like most data isn't that big. So he ran BigQuery for 10 years and basically said, "Yeah, most people don't need BigQuery. DuctTDB is good enough."And so what mother duck is, as far as I know, is that it's a way to offload computation in a in a ductb query to the cloud.
1:23:32 So say I'm running ductb my laptop and some of my data is on my laptop, but I have much much S3 files that uh that in in the cloud. If I connect to the with the duckb extension, I run my query. DuctB can recognize uh okay or mother duck recognizes the extension recognizes okay well the data you want is over here. You have a you have a mother duck account. Let me send that portion of the query plan over up to mother duck.
1:23:56 They run duct dbd in the cloud for you on the data that's local instead of copying it all back down and then send you back for results. So, so it's a it's actually kind of nice because it's like a seamless integration that you can say again it sounds like I'm shilling for him but like you can say I you pay for the ductb the motheruck cloud but then without having to actually change a query the same SQL query can then offload some piece to to to the cloud as needed.
1:24:17 I don't know whether they're trying to make ductb scale out across multiple nodes. A bunch of VCs asked me that like before before Mark and Hanist did uh DuctTB Labs, which is like like the the services consultancy company for for DuctTB. I mean, that's where they're mostly building. A bunch of VCs like, "Hey, look, we if we if we go give money to Mark and Hannis to do a ductb startup, can they make it the next snowflake?
1:24:41 What would it take to make ductb turn into a snowflake?"I'm like, "That's a major rewrite."And I don't think Mark and Hannis want to do that, right? And they didn't, which I think is smart. All right. Any final riff? random questions. All right, guys. Good.
1:24:56 Good luck with your classes. Uh, good luck for the rest of semester. And for those you graduating, congrats. Uh, but I'll see everyone next Friday, 8:30 a.m. Come early. There'll be coffee, donuts, and cigarettes. Okay, see you. I need something refreshing when I can finish manifesting. Too cold, a whole bowl like sniffing. One court and my thoughts hip hop related. Write a rhyme in my pants intoxicated. Lyrics are quicker with a simple mold record since I'm a city slicker.
1:25:21 Play waves are picker rhymes I create rotate at a way too quick to duplicate. Fill a breeze as a skate mahrenheit when I hold it real tight. When I'm in flight then we ignite blood starts to boil. I heat up the party for you. Let a girl run by me. My mic down for oil record still turns with third degree burn from one man. I heat up your brain give it a suntan. So just cool. Let the temperature rise to cool it off with same odds.