are DJ Shivam. He and I are both from Bombay and while the music was playing, how much did the population of Bombay go up by in that two minutes? Yeah, something like that. It's like a city of what, 15, 20 million. Every time I go back every few years, there's like a million more. And I don't know how they how they keep packing all of that stuff up, but that's great. All right. 20 million. 20 million. They stop counting. Yeah. Yeah. That makes sense. So great. All right. Today, we are going to talk about very execution. We'll start with a couple announcements. The first one is that you already know homework three is due on October 8 and project three is due on October 29. The big thing is the midterms. Hopefully none of you are surprised is the next lecture in class. The material for that is everything that we covered till last week, including the two lectures from last week. So today's lecture is not material for the midterm, but it's obviously material for the final exam. So don't stop paying attention today. But you don't have to worry excessively about this lecture just yet. You worry about it during your final exam questions on the midterm. Okay. All right. So we'll get started and look at, yeah. For the midterm, do you get a cheat sheet? Yes. I was going to announce that all in the end. The quick answer is yes, you get a cheat sheet that you can write on both sides, but handwritten. So you don't put in like six point font and come in binoculars and stuff like that. So ultimately, look, my philosophy is that if you need a cheat sheet just to have to get yourself from worry about what formulas I need to remember, that's what a cheat sheet is for. It should not stop you. It should not be the way you say, I'm going to pass the exam. It would be a pretty bad idea. We really want you to understand the material in this course so that if you're in an interview or talking to someone who understands databases and they ask you questions, you don't say, wait a minute, I need to get my two-page handwritten cheat sheet before I answer that question. Okay. So that's not the goal. It's just a safety measure. It's not the way you pass the exam. And I'll talk more about it when we get to that portion of the talk towards the after we finish today's material. Okay. All right. And some of you in the classroom, I know you like to talk with each other. That's great. If you do, if you intend to talk to each other a lot, at least in the back room, being a student a long time ago, I know if someone in front of you is talking a lot, the people behind you get disturbed. So if you think you're going to talk a lot, then just stay in the back seat. It's just easier. And I'm okay with that as long as you don't disturb everyone else. Okay. Great. We'll talk about processing models today, which is how does a query get processed? We'll dig into the details of the different methods and mechanisms. Then talk about these things called access methods, which is the way in which the query operators will stop touching the data sitting in memory or in disks for the first time before it feeds into the rest of the query. Then you talk about things that you might have to make changes to when you worry about deletes and update types of queries. We look at expression evaluation, then do a very quick midterm review, and hopefully we'll have enough time for that. Okay. All right. So the processing model is what defines how a database system implements the execution of the different queries. And the best way to think about the processing model is to say, if I were to write a database engine from scratch, and you're already working with bus stops so you know a whole bunch of how that works, but imagine you had to start writing something from scratch and say, how do I execute a query, which as we know from previous lectures comes in the form of a relational algebraic operator plan tree, and data is going to float from the bottom and the results come out at the top. So how would I write that code? How would I write that code for that operator to make all of that happen? Because the shape of the tree can be arbitrary, but the code you're going to write for each operator and code specific algorithms like a hash join for a join operator, or a sort merge join, or an index nested loops, or a block nested loops. And the inputs for that operator, when it's running either one of these algorithms, is going to be some other portion of the query plan that's doing its own thing. You're assembling this flow on the fly, and what are the different ways in which you can bring it together? So really the best way to understand these processing models is to say, how would I write the code for a database engine from scratch if I had to do that? That's the best way to try and understand the operator model. And hopefully you'll get that appreciation in a bit. There are three different operator models. We'll go through each one of those in turn. The iterator model is the simplest, and we'll look at an example next. It has three functions. Imagine defining a canonical function definition for each of these operators, whether it's a scan that reads a file, or an index selection, or a join, or an aggregate, or a projection, all the stuff that you know from what are nodes in an operator tree. Each of those operators, we want them to have the same signature. The code is there, is going to be dependent upon the algorithm that it implements, but you want the signature to be the same so you can mix and match. What does that signature look like? The three key components of the signature are there's an open and close, start the operator, close it, like a constructor and destructor for a class. And the key component of that, the main part, that's how it interacts with everything else, is going to be this next. This next call in the iterator model, which is the first of the three models we are looking at, is simply going to say, I'm doing whatever I'm doing. If I'm a selection operation, I'm trying to look at the data, apply the predicate, see if it passes that predicate, and if so, I'm going to do something with it. Next is basically saying, what's the next record that I send to someone else who needs that input, who needs my output as their input? So next, you can cast all of this in very much like the iterators that you see in C++ and other languages. You are iterating over a range of values, except in the operator model, you're iterating over the records that are getting produced. You don't know where the start and end is. That's going to be dependent on the semantics of that operator and what it does. So it's sort of predefined. You don't know how many next functions are going to be called, but you know, you'll keep calling next. If I'm talking to an operator and consuming from it, you keep calling next till the operator returns an end of file saying, I don't have anything else, I'm done processing everything I need, and that's your end of iterator model. The open and close are just to tear up and tear down stuff as you need to. So the next function is bringing in data or is it returning? Next function is bringing in data. And then of course, the person who's implementing it has to output the data for the function to call. So as an implementer, the next is to output the record. As someone calling next, it's to consume that. And of course, operators will take things from other operators and output the stuff. So they'll call nest next, and they will also go and have the nest function. So it'll all become clear in this slide. So imagine a very simple query, which we're going to use as a running example. So let's get to know it. It's got two tables, RNS, that's a sequel. This is the relational algebraic representation for that query. Now, hopefully all these operators are very familiar to you. If not, you've got less than 48 hours to brush it up before you have a midterm exam. You'll apply a selection here where the criteria is value is greater than 100 to a natural join between the RNS records, produce the join records and only key the two IDs. Now, of course, an optimizer, which we'll see later on, is going to try and do other types of things like merge the projection, pull it down and stuff like that, ignore all of that. Today, we're just going to try and run this query with these three different processing models. So start by opening up all these operators. So what just happened is we just initiated each of the operator instances. So we just called new on the operator whose code implements each one of that. Let's see what each of the code looks like. Let's start with the simplest one here, which is a simple scan. What this is saying is for each record, t, tuple in the relation s, so that's the database file, it will open up and it's simply going to emit t. So it's just reading from the file, consuming from it and outputting that. This operator is saying, and we'll connect all of it in a second, is saying, I'm going to read from here to this loop where I'm going to call the next on the child. So that's the question that you just asked. And I'm going to evaluate that predicate, which is a selection. And this is effectively the next call it implements that next call calls the next for his child. Okay. So imagine now we've opened all of it. And I'm not going to show how the connections are made. We'll talk about the scheduler towards the end of the lecture and we'll make that a little bit more explicit. So all opens have been called. And as part of the open calls, it's been set up that the root node has one child. The child has two operator instances it's talking to the left and the right. And this over here has one more entry. Okay. So the tree have been set up and effectively you can think about the top node having a function pointer to this when the open happened. And in turn that open called this open that open called this open and that second open for it called this. Okay. So the open set up all that pointer. So implicit in this diagram is that these things have been set up in the order in which we did that. Right. So watch this again. Start with the top. It opens, opens another one, open, open, open. And all of those things are called up. So now at runtime in your system, you've got the top corresponding to the root of this tree. And as you'll see in a little bit, the database engine is just going to call next on that one is going to invoke the next function on that, which in turn will apply the next call all the way down to go and start evaluating this graph. Okay. Does this make sense so far as to what we just did? We just opened the connections that set up the function connections has the same shape as the tree. And now we get started. We are ready now. So is this function or the next function? The open function was implicit when this the boxes came up. So this you can think of what's shown over here as the implementation of the next function. Okay. The main part, the open happened as the boxes opened up and the pointers were set up. Okay. And the close will be tear down. I'm not even going to show the close. Anyone that allocated intermediate structure remove it. Typically the operator themselves written as classes, if you've written it in a language like C plus class, so you'll call the D structure of that class, which implements usually the closed function. But often there's a separate closed function for cleanup, but that's details. You talk about that in the advanced class if you want to keep some of these running, especially if you're in the streaming environment, but that's a side note. There are sometimes in some database systems in streaming environments, you might keep them around forever. Okay. And just close it, but keep the state around. All right. Other questions? Child represents its child, right? So for being child basically says I'm going to call the next of my child, which is this node here. Does that make sense? And this has basically a left and a right, which are the left and the right children. So look at that hash code. It says a hash join implementation is what's shown here. It's going to say get everything from the site on which I'm going to build the hash table. So it has to first read everything from this site. Then once the hash table is built, it has to go and read from this site, which in turn will call all of this stuff and then produce the program. Okay. And then it can send it stuff out. So here's the animation for it. So we'll start by calling the top post next function gets called at the very top that in turn calls the next function here. Okay. That code starts to run for T1 building left next. So it's going to call the next year, right? And now when it calls that next year, it goes and so that call, that call calls this next year. So we are here. Everyone with me as to what's happened so far, right? All of this is set up in memory, function state has been set up. Now for the first time we start touching data. This starts reading records from the table, all right? It starts to run and starts emitting the record as soon as it finds it. It returns back the next as soon as it finds the record. Okay. Internally to keep track for where it is in that relational. So the next time it's called, it'll fetch the next one. Haven't shown all that state stuff, but you can imagine that state is kept here. So now one record has been fetched from the bottom and then it returns that. So in this simple iterator model, each next call returns one record. Okay. Now it comes back up over there and obviously the hash point code can't do anything else to the first two lines are run, which is building the hash table. So guess what's going to happen? Can someone help me? What will happen next in this code flow? Yeah. Yeah, call three again. So this will loop and this will loop till how long? Someone from this side of the room. I've noticed in the class most of the hands are raised here. So I'm going to try and spread this load out and maybe next time you can shuffle around. Yeah. Read the entire table. Exactly. All the R records will be read and eventually then end of file indicator will come through this loop over here at which point the code is allowed to proceed to that second for loop. Okay. So that will go on till you get to that. But one record at a time and then this part gets invoked. Now we start touching data for the first time on the S side and same thing happens. But this time that loop goes up to that next child, the record gets selected. If it passes that predicate and if it does, it goes in there and the query runs till it's done. Eventually now if something hits in the hash table, it gets outputted there. So that next call that was called from the root a long time ago now gets its first result after entire hash table has been built and the probe side has been fed to it. That selected a record that passed the selection and hit in the hash table. Okay. And what does it get as output at the root one record? The first record from the output relation. Okay. All right. So this is the simplest model. All databases started by implementing this. Many of the database is that we see today had the older ones had the roots in the 1970s and 80s. And as you can imagine as a programmer, this was the easiest thing to do. And the single record at the time interface was not a big deal because you were pretty much at that time, the memories weren't that large. Your buffer pools was really swell, 1,000 pages, 10,000 pages, pretty tiny. Most of the time you were going out to disk. And so the cost for this was very reasonable. And this was such an easy implementation. You can see as a programmer, it's a very easy code to write. Okay. Now, what do you think are the downsides of this? What do you think is inefficient about this? It seems like it's because you have an iterator on everything. You can't really parallelize super easy. You can't parallelize super easy. That's true. Though if the tree were a bushy tree, then you could start the left side, right side. You could do stuff like that, but you're right. It's not super easy to parallelize. But hold on, hold on. Yep. I'm coming to you guys next. So start thinking. Might have redundant operations, which are like at the base of the tree, but because you have to keep running this whole thing, you can't do these kinds of optimizations. You mean like the S has been scanned multiple times for different parts of the tree? Yes. Yeah. For example, like if you do like multiple where causes or different sides of the tree, you aren't able to actually like just quote less than you could want. Yeah. Yeah. That's true. That will happen in all the models, but that's a good thought. Hold on to that thought when you talk about the expressions, but you're right. There's certain optimizations you could do when there are patterns spread across the different trees, but that will be true for all the other models, right? There's an even bigger problem here. Okay. Is it that you can't use a static hash table? You can use a static hash table, but the bigger problem is that most operator, I'll go to that part over here and then come back to the previous slide, is that you are, oops. You're going to be calling a lot of these function calls over and over again. And what's the sequence that's happening in this iterator model? I call a function, do a work, get one record back. So how many times do you think I'm switching context between these operators? Like take this flow here. This code runs, goes all the way down, function switched over to a different function that needs to be run. Then that function ran, it did its stuff, and then one record got awkward. So in this stack, there were a billion records flying. It'll be billion times three loops to that one record at a time. So that's slow. A, lots of function calls. They can be pretty expensive, especially if your data fits in memory. All of a sudden, that's a cost that adds up. Second is sometimes if you have lots of functions being called, other queries running, stuff like that, your function code is not getting a chance to stay in the instruction cache. It's getting swapped up. So instruction cache is where your code that is being run stays in the highest level of the processor cache. Too many functions switches is generally not good for it. So there are lots of reasons why this is inefficient. It's for every little thing you have to go back to. It's too low level. Every record involves going through a loop that you are seeing in this call. So it starts to get really inefficient. And as I said, most database systems have that. In fact, you see a list of database systems over here, some that are massively big database systems, billion-dollar companies are more, and they still have this model because it's super easy to implement and reason about. Also pretty easy to debug the code because you know at any point as to what's happening, it's a much more easier flow to reason about. All right. So all of this made sense in the 1980s or so, but then memory started to get bigger. And there are other models that were developed. This is a second model, which is called the materialization model. And what this says is that I'm going to, when an operator is called, imagine the next saying, what I'm going to do in my next stuff is produce the entire output and then return it back up to my caller. So that way, each operator is getting called once at the base of the tree, of the operator tree, returns this whole output, and then it's done. So here's what it looks like. Same tree as before. The code looks a little different now, but the code component of it is still the same. And the main part, which you can see is now this is out. So this scan on R is adding to an internal area. Think of it as getting in memory, but sometimes it can be spilled to this too. For the focus of the lecture, we'll just say it's kept in memory. And then once it is done, returns the whole array, which is all the records in the table R. So it's a copy of the table R in an array that is sent to the parent. So the flow now looks like this. Same way, set things up. This gets called a return, which is all the records. That's it. That loop is going to be run. That two, three loop is run once. Okay. Not once per record. Once per record in the R table is just run once for the query. Okay. All right. Now, as you can imagine, then the second piece of that hash join code, hash join is a blocking operator. It needs to see everything from one side before it can do anything else. As you can see, I've called the hash even in this scenario, the next card called to it a long time ago. It still has to get all of this stuff, then start processing the other side before it can do that. Unlike something like this, which can start doing its work as soon as it's called. It's not dependent on anything. It can just stream through it. It doesn't have a blocking component. Hash joins, sorting, aggregates are naturally blocking. They have to see all or most of the input for the hash join. It has to see all of the left side before it can start emitting anything else to its parent. Okay. Same thing here. No rocket science here. All arrows flowing up, ascending entire tables for the results of that operator. Okay. Now, where does it work well? This works well when your queries don't have large tables that need to be sent across, which happens in OLTP environment that are transactional workloads. I'm updating a record or you log into Amazon and you have a customer ID. It just needs to look up your profile information to start populating the webpage, stuff like that. So very few records have passed along that entire query plan tree. So the tables that are in between are relatively small, in which case this is a pretty easy implementation and it requires the least number of calls that you need to make to these operators, because the operators get called once, they do all their work and send stuff out. It's pretty efficient for the short queries that happens in these OLTP environment where the workload largely consists of small transactional stuff that touch on very small fraction of the data, either to read a few records from a gigantic table or to basically update a few records. And we'll talk about updates in a little bit. One of the databases that you see here, WorldDB, Andy had worked on that before and from what I understand, he wrote one of the first operator models based on the materialization approach. It's also pretty easy code-based to reason about. You could put a breakpoint in any operator and look at what the input output is to say, hey, did the logic below work well? So easier to implement. This was a life till about two decades ago when processors started to get really fancy before there's still the late 90s. It was in the 90s that processors started to have caches. And then you could start to do all kinds of interesting things where you had to worry about the caches and the costs started to become different where the CPU cycles started to become more and more precious and memories were starting to grow. So now your data is coming from memory into the processor, not disk, which is three orders of magnitude away at times from memory. And so the CPU cost and other components and the switching costs started to become a big deal. So one of the earliest examples of switching over to this is a vectorization model that came through was to basically recognize that there are two things we want to play on. One is we want the intermediate ground between fetching all the records between each of these operator calls or fetching just one tuple to get something a little bit smaller. And also, if I can get a batch of records, not the entire result, but not one, batch being more than one, I can also vectorize that. So if I'm doing a selection, so let's just go through with an example here. Same thing as before, slightly different code base where you now start to see mod of output, which is the way database people say, what's the size of that output in terms of number of records is greater than n than a mx. So it's saying my batch size is n. So we'll start doing this here, start doing that. Now that return call will return a batch of records. So this loop will get called as many times as there are batches to be provided. So if I've got 1,000 records and my batch is 100, this will be 1,000 divided by 100. This loop will be called 10 times. Not 1,000 times, not once. So it's that little balance in between. And the other advantage of that, especially when you're doing things like that operator 4, is that if I get 100 records here, I can take this inner part, like the predicate eval portion and evaluate that using these instructions that are started to show up in a lot of machines where you could do multiple... How many of you have heard of SIMD, single instruction multiple data? So that type of hardware which says, I'm going to add one to every number. You could write a simple loop that says add one if I've got four numbers and that loop will run four times. But there are instructions, there are architectures in which you can say if you can upload four numbers together, you get that in an array. In one instruction, you can add four to each one independent. Single instruction on multiple data, you can apply that parallelism in one cycle. So all of that hardware does very well with vectorization because if that operation is to do things like compare a predicate, I can vectorize that. If my vector size is eight, then in one cycle, I can evaluate eight values and decide whether the predicate applies or not. And you'll see techniques like that in subsequent classes when we go a little bit deeper into some of this. But that plus finding that middle ground between how big the batch is, because with the full materialization model, if one of this input, for example, even this output of four was a billion rows, now I need to allocate that billion rows in memory and that's a lot of space. Where is that space going to come from? It's the same memory pool that's competing for the buffer pool and stuff like that. If I just start allocating that, my buffer pool is going to get squeezed and I can start running into trouble. Okay, I could put it in the buffer pool but I'm taking space away from something else. Okay, so the vectorization model has that nice balanced ground. Yep. In what cases would the materialization model, like I understand it's better for URL to be, but why? Is it like function call overhead? Yeah, the materialization model is better when you have very small, so the question was when's the materialization model better? It's when the records are, the tables are relatively small and you're just materializing the whole thing. So you could argue, why don't I vectorize it even for that? You could potentially, and that's a very relevant question to ask, say, if my batch size is big enough, do I need the materialization model or can I just do the vectorization model? The short answer is vectorization gives you a nice middle ground between the best of both worlds and you can always control the vector size if the database implementer has given you that option and you can span that spectrum. So making good point that could cover the case where materialization is better. So what I'm trying to ask is, why is this ever faster than the iterator model? Why is this ever faster than the iterator model, the materialization model? Yes. It's because if I have 100, each of these arrows, two, three, if it had to be run, let's say a thousand times, versus to be run only once, it's probably better for me to just run that three function once, pass that three thousand values to the join operator in that build site and I'm not making all these thousand function calls over and over again and not switching those functions as much. So if you were able to inline the lower functions, would it? Yeah, we've come to that, not in this class, a lot gets discussed in the other one. These things I've done at runtime, so inlining is difficult, but there are methods that say, so the question was, can I inline all these functions and there are methods that now say, can I take the entire query and convert that into code at runtime with all types of inlining? I'll briefly talk about in 30 seconds in a little bit, we'll talk about, but the advanced database class talks about that. So that's a good way to think about, can I do something special for stuff like that and absolutely people are playing those games. Okay, I have one other question. Yep. For the latter two models, does that stop you from like, let's say we're part of the way through a query and we discovered that we have enough? Does that, does like, materialization refreeze the entire thing? Does that sort of is an inefficiency with the model that you have to read everything even if we have like some filter and we have like some like only read 10 of them that match this filter, right? Does it like stop us from not reading the entire table if we find- Which model? Which model are you referring to? Kind of both, like materialization or vectorization, if it had a big enough vector size. Yeah, so the question is, if in materialization of the vectorized model, if the vector is big enough, should you stop and make that, are you asking in the vectorization model, let's be more specific, in the vectorization model, would it benefit to make the vector size dynamic? I guess what I'm asking is like, does it stop us from checking like, if you had a really big vector size, let's say we read a thousand tuples, but we only needed to read 10 of them and then we would have been like, we have a thing in our query, this is only read up to 10. Oh, I see, I see. So the question is, if I had a limit clause at the top, what can I do? Yes, if there's a limit clause at the top of the query, in many cases, you can push that down, but if it's limit 10, that doesn't mean you could say limit 10 at the bottom level. You can do limit 10 in this case at the hash joint level, but you may still have to read, even with the limit clause, you'll still have to do the entire build site here. Yeah, but something like the iterator model, if we have a limit clause and we have a like a where clause, then it can find 10 that match it. Yes, absolutely. So if there's a limit clause, that's an optimization problem where the optimizer could make the code 2, 3, and 4 to be different so that it doesn't have to read, the next can return end of file sooner when it is at the safe boundary. Absolutely. Yeah. Thank you. Yep. There was a question here. Is that still on the table? Okay. So that's great. You guys are getting that. There's all kinds of optimization you can do. The main thing I want you to get across is that the vectorization model has this nice balance ground and if you were to do a new engine from scratch, my recommendation would be to do this vectorization model, that batch size. Okay. All right. A little minor detail. I mentioned the open call sets up the tree. Now that tree could be set up in a top down fashion or you could choose to set it up in a bottom up fashion. It's more natural if you're writing the iterator model or any of these models to set it up in a top down fashion, but you can also do it in the other way. So nothing really dramatic over here, but you have to set up the tree and that could be a top down versus a bottom up approach. Now, one advantage of the bottom up approach is that as you're setting things up, there might be opportunities for some optimization, putting in special optimization tricks that you could do, but we'll talk about that in the scheduler. Those things become more interesting and relevant if you do it at the scheduler level. The main point over here is that you can set up the tree top down or bottom up. There's a set up cost which hopefully you got from that earlier discussion. Okay. That's setting up that function pointers across as to when I call next, what am I calling? Right. Because that hash joins next on one side was calling the file scan. The other side was calling something that was looking at the predicate and evaluating that predicate. Right. At you don't know what your operator is till you start, till that query is run, right? And that same hash join code sometimes is children are different operators, right? So it depends on the context of the query. In every tree, at the bottom, the root nodes of the operator tree are the places where you go access the actual data. Everything else is feeding stuff up from intermediate data that's been produced. So concerning that bottom part of that tree, we have to decide how are we going to access the records in that underlying file? And the technical term for that is called access method. It comes from system R, which was one of the earliest relational systems that was built by IBM in the 1970s. At the early days of the relational model after God proposed this model, IBM started to work on the relational system called system R. A lot of the optimization and things like that we'll talk about come from system R. And at the same time, Stonebreaker in Berkeley, IBM was in San Jose, Berkeley is on the other side and Stonebreaker and Steam were implementing Ingress and that Ingress eventually became Postgres, right? So the access method term comes from the system R days. It's a way of saying, how am I going to access that underlying file? And the dominant methods are a sequential scan as you saw the left node in the tree that we saw. Or it could be an index scan, which is to say I've got an index on this predicate that I need to apply. Let me use the index because it's a more efficient way to fetch the records and hence the name access, right? The query has to access these records from this and hence the name access methods. And we'll talk about this multi-index scan if I've got multiple predicates on the same table. Can I do something more interesting? Use two different indices and combine that. Okay, so it's concerns. How are we fetching data from that? How are we accessing the base records in the base tables? All right, no rocket science here in this case. We've already seen that the access method term applies to the R and S, those two operators. Sequential scan pretty straightforward. We already saw that with the R relation in the previous example. Just go and fetch one page from the table that you're trying to scan. Start reading all the records on that page. Once you're done, go fetch the next page. That operator, the sequential scan operator needs to keep some state around, which is to say, which page have I read? So that the next time it is called, it knows, do I still read in this page or do I go to that next page? So it has to keep track of something called the cursor, which basically says which record on which page am I reading? And that record ID is typically a combination of the page ID and some offset in that page ID. You've seen that from the buffer pool, right? That record ID is what it has to keep track of. And every time if it's in the iterator model, the state tells you which record are you at. So the next time it's called, you're fetching the next record, right? You don't want to repeat and send back again to the consumer of that operator, of the sequential scan operator, a record that's already fetched. The query result would be wrong, right? So for correctness, there's some state that is kept in that sequential scan operator, okay? And you'll hear this term cursor, which is a way to say I've got a marker on the record position in a file, and I can advance the cursor. This notion of a marker, a cursor on a file, also applies when you're consuming the output of a SQL query as a database programmer, right? That was one of your projects.  What you'll get back from the ORM layer is a cursor object which allows you to fetch the next record, the next record, the next record. So that next idea also applies all the way into the application space, and the cursor is just a way of keeping track of which record you're at, okay? So you just get the result, and each record in the result only once, and not multiple times for correct semantics. So it's here that word cursor also applied in that application space and in how people refer to code inside the database system. Same concept. Does that make sense? Okay. So now sequential scan can be optimized, and we've already seen some of this optimization. So even if I'm scanning the data sequentially, you could pre-fetch the next page, right? When you're waiting and processing records on that page, we've seen that before in lecture six, you could do buffer pool bypass. Next class, we'll talk about parallelism, where you could do fetch multiple records in parallel. You've seen deep clustering in lecture eight and big materialization, which you just saw in the last class, right? Don't fetch the, don't materialize the record, just keep the record IDs and fetch the values corresponding to the record IDs later. So there are all kinds of optimization you could do with that, right? Sequential scan, go return the value, or do a materialized slate, just return the record IDs, and there are interesting trade-offs. But the one that you haven't seen or won't see that you have to talk about today is the data skipping component. And the data skipping component is basically a way to execute, and you can do this in one of two different ways. One is this approximate queries, which is last lesson, the other one is using zone maps. And so the lossy approach gets used in examples like Bing TV and Redshift and stuff like that, is to execute the queries on the subset of the entire table to produce an approximate result. And that's used in cases where approximate results are okay, right? So typically not in the environments that you've seen. So I'm going to find an average sales amount across all the products. All I don't run the whole query. I'm okay if you give me some sort of an approximation. And there are ways to go do that and talk about that in the advanced database class. We'll talk about where you're trying to get the correct result, but do that faster using these things called the zone map, okay? And I'll just talk about it with an example and walk through that. So imagine I've got a column with integer values here. And on this, imagine I'm going to be asking a lot of selection queries. I'm looking for values, let's say between 100 and 200. Another query might look for values that are less than 400. So I've got lots of scan predicates coming on this integer column, okay? If I'm just doing a sequential scan, I have to scan everything every time, okay? And now my data is broken up into pages, right? So now you can generalize that to say I'm going to organize my file into zones. That zone could be a page, often in many systems as this notion of a block, which is typically much bigger, many megabytes big. And so in many systems, you'll have that much bigger concept. But regardless of what you divide that data, you take that whole file, break it up into parts horizontally, call them zones. And now before scanning all the records in a zone, you can create certain aggregates on it, certain pieces of information on it that give you effectively an idea as to what is the value in that zone for the records in that zone. So here we can create what we call as a zone map and say in this zone of five values, the minimum is 100, max is 400, here's the average, here's the sum, and here's the color. Of course, to make it fit on the slide, there are five values, but you can imagine, there may be 5,000 or 50,000 values depending upon what you set up as a zone size. Now, if someone says, find me everything that is greater than 400, all you need to do is fetch this zone map and say I don't even need to look at the actual values. So by looking at the zone map, you can decide whether it is worth looking at the actual values. Let me finish this slide. I'll take your question in a second. And this obviously is implemented in many systems and as you can see, value greater than 600. I will only look at the zone map now. The zone maps are much smaller. So in this case, the zone map has just got five integer values. And as I said, for this example, the data also has five values, but imagine it is 5,000 values or 50,000 values. So this is many orders of magnitude smaller in size and that allows you to go and filter stuff out. Now, the zone maps can sometimes be kept with the zone page itself, the zone data itself, in which case you have to fetch the data to filter it. So you don't get the IO benefit, but you get the CPU benefit, but you could also keep the zone map outside and you have to make sure if updates happen here, the zone map has also been updated. Okay. And there are two different ways of doing that. The external method is harder to keep track, to keep synchronized, but it's obviously much more efficient because you don't need to actually fetch the data. You could just skip it. You can get both IO and CPU optimization. All right, question. So does the user of the database set this up more? No, usually it is set up by the DBMS. You, as a DBMS implementer, will decide whether to implement zone maps or not. And then sometimes the system may have certain options when you create the table or set up the database to say, what type of zone maps to build? Should you only do min max, which is the most common? It's the smallest number of, smallest zone map that you could create that has a maximum value. Average and other things have less utility, but they do in some cases, right? So it depends upon whether it is automatic or whether control is given, but the implementer will implement that and then provide some ways to set this up. And it could be fully automated or the database administrator could provide hints to it. Sometimes when you're creating the tables, you might set up what the zone map, how aggressive the zone map should be. So it's all over the place in there. It's not a SQL standard. It's something that will get exposed to the database programmer, depending upon that system. But a lot of systems use it, including Oracle, DB2, and pretty much all the modern systems use it, including your snowflakes and data bricks. So now zone maps, this is really hard to see. I don't know why it looks great on my screen here, but this is a paper that's from more than 20 years ago by this guy called Guido for Quinto, and he's an amazing German researcher. And this tells you more than a decade after he wrote the paper to say why zone maps are important and why you should use it, it took the industry to go and implement it. So research on this was way ahead of where it started to show up in products. It's a beautiful paper, and if you are interested in it and can't find the paper, let me know. The research term for that is small materialized aggregate. It's what a beautiful name, right? It's a materialized aggregate. You're doing min-max, some count stuff. It's an aggregate and they are small. SMAs is what it is called. So very tourist name, very memorable name, yep. But the industry guys had to call it zone maps because they have to market it differently. So I don't know why they didn't call it SMAs. Yeah, good question. So you would have one zone map per zone and how big is the zone depends again on the database implementation. So the question was how big is the zone map? The zone map is one map per zone. So if I've got a file, let's say I'm building it at the page level relating back to Buster, I could build a zone map at the page level if my file has 100 pages, I'd have 100 zone maps. Now where do I keep that zone map? I could keep it in a page in some place or I could keep it outside the page and I have to keep it synchronized. It's pretty small. Even for a small 4K, 8K page, you can see the utility of this being really high. Yes? You certainly, as a database implementer, you could do whatever. So you can safely do minmax on anything that is sortable, including strings. And for strings, you have to be careful about collation order. I think Andy talked about that, right? Collation order says what's the right way to sort a string, especially if you have a product that's international. The sort order for English language is different than for Mandarin, that's different from Kanji and stuff like that. So anything that is sortable, strings are sortable with the right correlation order. You could do minmax on and then you could decide if in the minmax for strings, you want to keep the entire minstring and the max string or just a prefix and then use it in a safe way. As a user of the system, can I make those decisions? Most likely not. Most systems will give you the ability to tell you that turn on zone maps or not. Most systems do this automatically, internally. Can zone maps be implemented alongside indices? Absolutely. In fact, they often are what zone maps do is reduce the need for indexing on extremely large datasets. That's why they become so popular, especially on the very large OLAP stuff because now the need for index is a lot less. And so yes, if the zone maps are outside, you're taking a maintenance problem, it's like an index problem. And if I've got a zone map, if I've got 10 columns in the table, I'll keep, I could decide to pick a zone map on five of the columns. What's super interesting is I could decide I'm creating a zone map only on the first 100 pages that have been loaded. The last 100 pages that were just loaded don't have a zone maps. So if you don't find a zone map, you're going to fetch the file. So it's not zero or nothing. You could do all kinds of interesting things, especially if you've got data coming in.  Okay, it's beautiful. Yep. Let's assume for the sake of argument that I hate indexes or something. Yeah. So could I just do only zone map? So the question is, if I hate indices, with the student in the first row seems to hate indices. No, I'm just kidding. Absolutely. And systems, some of the newer systems like Snowflake are very aggressive users of zone maps. Does reduce the need for them to index as much. Is there ever like something you can only do with indexing or can you just eliminate it? Certainly with the indices, you can get much finer values. Right. If I said, by the way, there's nothing, there are systems and there's a research system called Quickstep that we built in which we use zone maps at the top level and indices inside the zone. You could do that too. And maybe you can come talk to me later. I don't know if anyone else that does it. It was a research prototype, but that's an open question where you can combine that. If people are doing it, I at least don't know that right now. But you could combine stuff. What are the types of edges they do? Is there, how do they decide what ones to keep in the drones? Yeah. Because it's based on usage. It's based on usage and experience, but pretty much everyone will keep MinMax. And then maybe some, it depends upon, you know, how often does some get count? You could argue like average is probably not that important because if I have a selection followed by an average aggregate, then the average is useless, right? Because I have to do the selection first. So it will depend, but MinMax is typically used. And sometimes you'll hear the term MinMax indices. And that's used for just saying that version of the zone maps or SMAs with just the MinMax portion. Okay. So this is crazy, right? As I said, this is like more than a 20 year old ideas. Only in the last 10 years, people started to get excited about zone maps, but academics have known that this is a very good idea a long time ago. Okay. Yep. Those zone maps are built once a month and then discarded for the termines. Just like an index, you have to update it if you want to keep it around. So zone maps, if I update that page, I would have to update that. Many systems, what they do and update to a page is marked as a delete on the page. When you get to transactions, you'll see that new records get put over here. So this is just marked as you are no longer valid. And so in that case, if it's like that notion of a block of a zone being immutable and only gets updated when you merge things together, for that there are other models that apply. So LSM trees, you remember when you guys talked about LSM data structure where they grow in one direction, there's a merge phase. So you could start to do interesting stuff with it. So it depends upon what's your underlying storage model is, whether updates are in place or somewhere else. And that'll have implications for indices in general, zone maps will have the same thing. They're like indices, but a very interesting different type of indices. Right. And as I said, you could keep the zone map outside the zone and then it looks different. Okay. It looks like an index. All right. Okay. Let's keep moving. So index scan is basically a scan. I've got a predicate. Let's just look at it with an example. I've got this query where on a table, I've got a predicate on age, department and country. And imagine I've got indices built on age and department. So obviously I could do a file scan and apply each of those predicates. And that's one way. But if I've got an index on age and department, I could decide what I want to do with it. So if there are 99 people under the age of 30, but only two people in the CS department, if you have the department index, you probably want to use the department index for that. You only have two records on which you need to check the rest of the predicates. Right. And vice versa, if the scenario are different, then you can flip the index around. The question, of course, is do I, I don't know this distribution when I want to use the index. So that again is something that an optimizer typically tries to decide when to use an index, what to use an index statically. And it has statistics to keep track of it. We'll talk about that when we discuss the optimization work. But assume that you know that you can see how you might switch between which index to use. You want to use the most selective index first because that reduces the predicate evaluation for the rest of the predicates because you only will apply to the ones that pass through first. Now, if you have multiple indices, like we do in that case, there's something else that you can also do. It's called a multi-index scan. I can apply both predicates only on the index, which is pretty small. I can do that check. I won't fetch the records. I'll just look at the index. So I haven't reached the data pages yet. And then I'll merge the hits I get from both indices to then fetch which records I need to go and build out. It gets called by different names, like multi-index scan, bitmap scan, and index merge. And basically the way it works, if you look at this example, is you're going to start with it and then look at both of these cases. We'll look at the first index on H and retrieve the record IDs that hit. We haven't fetched the records yet. So delay that. Don't retrieve it just yet. Then go and get the record IDs from the blue side in this case, where department is equal to CS. Merge those record IDs. You could represent the record IDs as a set and merge it, or you could represent that as a bitmap and use bitmaps to filter stuff up. Those details don't really, they matter in the implementation, but essentially you're trying to do some sort of set intersection. And then only the common record IDs is the one that you will go and use to retrieve back from the system. Okay. So you can use multiple indices to go and make that search better. All right. Questions? And for some reason, my camera has started to misbehave. Let me just go reset that here. There we go. Huh. It stops tracking after a little while, which you'll only notice in the video recording. But all right. Yep. Question. But question about multi-index can be. Yeah. How would you use one of those selected ones first? Like once you have the record IDs, what do you do that with? So the question is, what do I do with the record IDs in this multi-index scan? Like after, like if you're using the more selected index. Yeah. So in this case, we'll use the most selective index first. It won't matter. If I'm using, if I decide I'm going to use both the red and the blue index for doing this multi-index scan, assume the optimizer said, please use both indices. Somehow it knew. Then you'll do the red index search first, then the blue index search next. I could have flipped the order. Costs will be the same. I find the intersection, and then it's only those record IDs that I fetch. Okay. So the thing that you described if you're only using one index. That's correct. Yep. Yeah. So if I were to use only one index, the question was, when does the index selectivity matter? So if I were to decide and use only one index, then I will need to know whether the red index is selective or the blue index is selective and pick that one. Okay. Yep. Why is this more efficient than using the most selective index? So imagine age, less than 30 is the most selective index and department greater than CS is less selective. The first fetches a million record IDs. The second fetches 10 million record IDs, but the intersection is only two. Okay. Because they could be independent. So if both the predicates are completely correlated, then it wouldn't matter. You're right. But if they're not correlated, then it'll matter a lot. Good question. I'm going to ask two. Obviously, like, why would you ever want to use? Like, if you have an index on both of them, why would you ever only use one? Yeah. Because the opposite. So I'll flip around. Yeah. So the question is, why would I use when could this be worse? It's the opposite, right? So it depends on whether they're correlated or not correlated. And so now you could ask the question is, how do you know they're correlated or not correlated? That's one of the big reasons the optimizers don't quite work. We'll talk about that in query optimization. In the advanced class, we'll talk about why the optimizations fail all the time. And Andy and I are trying to start a new project in which we make optimization even less important. If you're interested in what you can do to make optimization less important because optimizers make these mistakes all the time, go to my webpage at the top is a paper that talks about how if you do adaptiveness, it's better than trying to spend cycles in developing optimization. But that's the point of view. I could be wrong, but that's the current point of view that I have. So these are great questions. Optimizer, you're assuming it knows how to do this correlation, okay? Questions? All right. Now there's a little tricky situation that you have to consider when you're looking at modification queries. And you've seen that in SQL. They are your insert, delete, and update queries. And there are two components we have to consider about. One is what is it that gets returned by the query? So imagine I say insert into and a full SQL sentence below it. That SQL is going to run, produce a bunch of records that I'm inserting into a new table, okay? That SQL query that is run, the operator that is producing that final output, of course, there's a full operator tree below that, could decide to say, I'm only going to pass materialize the entire record. So for inserts, you could materialize the entire records inside the operator and then pass that along or the operator inserts any record passed to it from the child operator. You're basically getting it to that next call. So it's very similar to what we talked about that materialization versus inserts, and you have that similar type of choice that you need to make. Okay? Now the more interesting part which is very subtle is that when you're doing updates, you have to keep track of the record IDs for the target tuples. And this is to avoid a problem that is called the Halloween problem. Which was discovered by IBM decades ago. IBM was at the front-runner for many of these relational systems on Halloween nights. So here is the query. So I'll let you assimilate that a little bit. What we have here is an index on salary. And we are updating all the people whose salary is less than $1,100, giving them a $100 salary raise. Okay? Now this query, the operator tree for that, as you can see at the bottom, is using the index to retrieve the appropriate records. The appropriate records are those where the salary is less than $1,100. So now we start here and fetch the records, go apply that. So imagine we fetch the first record and that happens to be Andy. I'm using Andy's slide. As you can see, he's trying to do something sneaky here. Always watch out for that. But he also made this slide to say watch out for this slide. So that gets called. Imagine you're using the iterator model, one record at a time. And now Andy has $100 raise. But that is inserted back into the table, right? It's updated. So it now goes into the index a few distance away, where the new salary is $1,100 and $1,009. And now what happens as the index keeps getting called at some point that record is going to get fetched again, the 1099 record, the new update. This is what he just updated the record to. And now that will get another $100 raise. So Andy is really honest. So he doesn't want that. So he said, we should not make this happen. He'd rather have the $200 raise declared upfront to him. And so this is the type of stuff that happened. As you can imagine, in the first implementation, people didn't think about it. And so it was buggy code. People started to realize, whoops, someone's getting a lot of raises. And that was the Halloween problem. There's a whole Wikipedia article associated with it that you can look at. Yep, question. This wouldn't happen if materialization was in place. That is correct. If everything were materialized, completely a new level went back. You had all the record IDs from the index produced once and sent across. This wouldn't happen. This seems like those against all concurrency rules. We're modifying some data structure, but we're not actually holding... Yes, correct. So the question is, does it... It seems like we are going against all kinds of concurrency rules. We are modifying a data but not holding a lock on it. That is true. A lock would be too expensive. So you'll see what we'll do is a little bit simpler. That's right. That's exactly right. It is something that you would end up having to do. So what you end up doing is the following, is you keep track of the solution is pretty simple. Keep track of all the modified record IDs. And if you're updating in place that record ID is the same for the old and the new record. And so if you see that new record again, you say, oh, I've already processed it. I'm just going to skip over it. Even though as you scan the index, that new record ID is now in a different location, you are going to simply skip that. Or if everything were materialized, you would not have this problem as was just pointed out. You're not going back again to the index scan. The index scan happened only once. You've got everything. Then you're going to be fine too. And then you put everything back as the updated values. And then when you talk about transactions, you'll see we'll do other things so that if there are concurrent requests happening to the index, they don't interfere with each other. Here, we're just trying to make a single queries action, not interfere with itself. And transactions will deal with the other problem of multiple queries interfering with each other. Okay. Question? Yep. I have a question about two choices in this test about how to insert. One is materialize people across the inside of the top paper. Another is how to insert and the other is how to do it. Could you explain the difference? Yeah. So the question is when I materialize the tuples inside the operator, do I bring all of the tuples together like the join has to bring the tuples together, materialize it before I send it across, or I'm just going to pass that tuple across and do that. So it's very similar to what we talked about with the different ways. Yep. Just the iterator versus materialization. Yeah. Yeah. Yep. Yeah. Good question. How do you track the record IDs? You could just keep it in memory. As I said, each operator has a state. So you can imagine the insert operator has a state which says here are the record IDs. Now typically inserts don't, you know, even if I've got a billion rows, I'm not changing all the billion rows. So it's usually small. So that's, that's often okay. Okay. All right. We've got to keep moving a little bit. Sorry to rush a little bit up. I'll pause again for questions in a few minutes. So expression evaluation. This question was asked, you know, when we started talking about efficiency in the vectorization model, here's a query which has a bunch of expressions in it. The query when it is formed by the SQL parser is going to get converted into the expression portion of it will get converted into something that looks like this. There's an and on one side is a join cause, the join predicate. The other one is a selection predicate. And so that's what these expression trees look like. Why are they important is because evaluating this tree can take time. It's done for each record. So here I'm looking at the simple expression tree where value is equal to one. I'm just checking that predicate. Pull up a record. I'll instantiate the attribute value. Then the constant is always set for this query and I'm going to evaluate the operator. So as you can imagine, if I just implement this in the expression tree form, it's a whole bunch of function calls for the equal operator that has to look at its left side, bind it to the value for the record at hand, then compare it and do that. There's this technique called just in time compilation which says this expression tree is constant for the whole query instead of running this code in this form which is a whole bunch of code that is generic for the query take that convert it into an instruction type instruction code effectively materialize a function on the fly just for this predicate and call that function which is going to be a lot more efficient. Okay, I'm not going to go into a ton of detail. The advanced database class talks about that a fair amount. But over here, just want to be aware that this just in time compilation push for ships with it allows you to evaluate each expression efficiently because otherwise put it there the billion records the traditional way of doing it is going to be so because it's a generic equality operator that is getting called as opposed to one for just that value for just that column type. Okay, and so that code is going to be a lot fewer instructions per record. So it's like compiling the predicate code on the fly and running the compile code but that compilation is happening as the queries issue. We can postgres hazard so you can play around with it and take a look at it. Database systems also have this notion of I've got a query that's run over and over again. So here's a query that is adding nine values. So it's like here's some additional incentive that's given to new account holders we add $9 to their account. It's a query that's going to be run for every new account creation. And so instead of saying I'm going to issue that query every time that button is pressed in the application. You can say I know this query template is the same. All I might change is the account value $1. So it's kind of like saying I've got the function SQL query is now like a function. Everything in the function is known except for one parameter that $1. And I'm going to compile that entire query and it's called a prepared statement. It has a name let's call it XXX. And when that button is pressed we just call the function XXX and pass in the value 991. 991 will then get bound to the $1 value because that's the account value and it gets evaluated. So essentially it's pre-compiling the whole query now not just an expression and then calling that whole query so it's and that pre-compiled query could be pre-optimized all of that stuff but at runtime when the user is calling that function it doesn't have to pay all that extra cost it's a much efficient piece of code. And you can actually do the just-in-time compilation to generate a lower level assembly language code for that entire query too and this JIT idea applies to entire queries too. Again there are full lectures in the advanced database class where we talk about this stuff but here just want you to know that the performance game has now moved on to where this just-in-time compilation is pretty prevalent databases that care about performance and Postgres has it and you can play with it. So that's just saying instead of doing this traverse the tree on every record this is all going to be very tight code and that's just going to be right. So I'm going to very quickly talk about something called a scheduler and if you open up pretty much any database textbook it will not talk about the scheduler at all which to me is one of the most interesting things that you have to explicitly pay attention to for a good runtime system and most people hack and scheduler without knowing they built a scheduler but keeping it as a separate system infrastructure in a system is super important and only some of the new modern systems are starting to do that. So why is a scheduler important as an explicit module? So far everything we've talked about is a data flow right? Records flowing in and we are talking about whether the records flow one record at a time or entire tables or in batches. We very briefly talked about the control flow and even when we talked about the control flow we said that the control flow is like once at the start of the query then you take it out. But if you have a scheduler then you can start to do really interesting things and I'll talk about this research prototype that we had built called QuickStep and some companies are now starting to look at it and say should we be building explicit schedulers and some companies do but they haven't really brought that out very clearly. So here's the traditional data flow graph that we've seen before. So I've got two selections in this query and the join and records are going to flow through that's what we've been talking about since the beginning of the lecture today. And imagine there are two pages in R and the selection makes it only one page of output and that goes to the join four pages on the green side two pages at the end of selection they get joined the output has two pages but the records are much bigger right there combined. So if you have an explicit scheduler then typically what gets done is it works well with this batch mode especially the vectorization model and then the scheduler is explicit it will create something called a scheduling component of in quick stuff we called it work orders but there are other ways to call it and so you'll bring the data into the buffer pool buffer pool operates under normal conditions and now you are not calling that operator tree from top to bottom but instead what you're doing is you're walking the tree and putting scheduling work in the scheduler queue with that black portion here which is a pending queue. So you start walking the tree and say I need to apply a selection on all the records in page R1. So that's the work that's been put on the scheduler queue and you can fill up the scheduler queue with all the work that needs to be done as you're walking through the tree whichever operator is ready to work and then the worker threads are effectively stateless and they just run select code and join code whatever they don't remember much so that way you can distribute that you can they could be spread across different machines and you can be very flexible about who does what and it's very lambda like in its execution for each operator and then you send it across whatever network that a worker picks up and applies the first selection it fetches the records and then when it does it produces its output in this case R prime you know it's a sample page worth of data let's say puts it into the buffer pool and goes on. So the scheduler is at any point in time just filled up with stuff that needs to be pulled up anyone can pull it so it's very dynamic and allows the system to go execute that so this filled up that first blue page and so on and jumping ahead a little bit once the selections are done which is the bottom of the tree is now done you now put work orders to say go build the hash table on R prime the output of that first scan on R that gets scheduled hash table gets built in quick step we built it in the buffer pool too so there's only one pool to manage and then you go and apply put into the scheduler saying now I'm ready to schedule the probe operators and you put that in so effectively this becomes a very different way of putting explicit breakpoints in the control flow the data flow is through the vectorization model but with this control flow what you can now do is you can start to say all kinds of interesting things like I've got four queries running in the system query one is already halfway through but query four just came in and it's a very high priority and all you do is take all of query four's work and put it to the front of the queue and the high priority queries just start to take over the entire system and come down furthermore if the pool of workers is just let's say I've got 10 threads there I want to grow it to 40 the system will elastically scale back and forth and you don't have to do anything in the traditional way of starting the operators when you start the operator you'll say ah I'm gonna run you as a two-way parallelism but once I start that operator let's say the hash join operator till it's done I can't change it here the workers are all stateless so very elastic you can do all kinds of fun stuff with priorities and stuff like that that provides a much cleaner abstraction and again I'm not going to go into the details of this the advanced database class talks about that but if you're talking about query execution you want to know about what schedulers do and the modern way to do that is to make the scheduler explicit and put a ton of smarts in that that is student whose entire thesis was on scheduler and so I'll just leave it at that you can basically see diagrams in the paper that talk about here are two queries in the system the green query comes in it takes over all the resources and everything just picks up automatically you don't have to write any extra code the system just magically adjusts in this elastic and flexible way all right I'm going to skip that part so hopefully what we talked about today makes sense in terms of how do queries actually execute inside database engines and you went from different processing models to all kinds of optimizations associated with it including doing just in time compilation for just the predicate portion or the entire query so I'm going to take the next few minutes to talk about the next class we'll talk about parallel query execution which is going back to the big thing on everyone's mind the midterm two days from now in this classroom at this time you you must have seen the midterm guide with sample questions and answers so please take a look at that bring your ID you will check your ID don't send your friend to take your exam we will catch it you can bring a calculator if you need a calculator you don't you shouldn't need a calculator but bring it if you really want to one 8.5 by 11 age paper on which you can hand write double-sided again as I talked earlier this is just a way for you to feel comfortable that you don't have to memorize a bunch of stuff but don't be the way in which you're going to study for the exam right this is just a way for you to feel comfortable you should still have the knowledge in your in your head okay Andy told me that in previous classes some kids some students brought in live animals if you need a pet to calm down work with your pet before you get into the classroom don't bring your pet in I've been told that some one time someone brought in wet laundry and candles don't do all of that stuff right just come with your calculator your ID and your two-page stuff and drink a bunch of coffee if that works for you the material is everything that we've talked about so far in class including the relational model relational algebra integrity constraints how they form the foundation of what is SQL in its declarative form then the core parts of SQL including the different operators select insert update delete you want you to know what the SQL query looks like we want you to be able to look at a SQL query and tell what it does right you're not going to test you in intricate details and try to tell you to write a 10 level nested SQL query okay so that's not what we are trying to do but you shouldn't have to say oh I don't know what a having clause is or I don't know what a nested query looks like you should be able to look at query and write simple queries in the class okay without needing a debugger to go and figure things out not checking for detailed syntax and stuff like that just want to know how you think and at least read queries correctly you should be aware of joins aggregates CTEs and window functions okay all the stuff that you've talked about is advanced components in SQL you built a buffer manager so hopefully that part of the exam will be easy for you you need to know about different replacement policies what are the pros and cons right what works better when know about the disk layout and the different methods we talked about slotted pages LSNS someone asked this question earlier about this merging stuff so revise that from the discussion from the log structured file system different types of hashing that we've discussed in class right and the pros and cons for each one of those linear probing Robin Hood and Cougou hashing and then the dynamic hashing structures we looked at to extendable hashing and linear hashing and you have a project on one of that so I'm sure you're getting to know that well too B trees in search deletes you started with the try stuff as your first assignment so you kind of already have been spending a fair amount of time on tree structures so B trees are this magical balanced logarithmic cost data structures in search deletions there's specific algorithms for that so learn that well I know there was a question on Piazza that was asking about some of the key rotations so read that well it's very logical but you have to read it to get that into your head what happens on splits and merges the difference with the older B trees and latch grabbing and coupling to make all of that work well in concurrent environments we looked at sorting two different types of sorting external merge sort the general merge sort you know the n-way tree what were we trying to do with the different optimizations to that with double buffering and all of that stuff last lecture you looked at different join algorithms from very simple ones nested loop types sort merge different types of hash joins what are the pros and cons of those and the execution cost right that's basically what's the cost of each of those under different circumstances and this is not query processing models is what we talked about today it's not in the exam so I think Matt announced last time that joins is the last thing correct is that right is that what he announced yep okay so ignore this part then we'll talk about parallel query execution I checked with Matt if he didn't announce that then query processing model will be part of that I'll send in Piazza message about that I think he announced that it's not in the class so go with that as a default unless we post something otherwise all right questions last minute questions okay all right go for it oh you could call me dominican black skelly black leather black suede timmelins my all black dirty haters send you to the pearly gates you get gizama trying to skate and that's your first mistake I ain't lying for that cake if I'm a seawake my grand's is heavy weight and ran through every stake when they asking how I'm living I tell them I'm living great


Hi. So, in today's capsule we are going to now introduce the Fourier transform. We are going to extend the definition of Fourier transform to all tempered distributions. Remember the class of tempered distributions is quite huge any LP function is a tempered distribution. Functions which grow like a polynomial they are tempered distributions. Things which are not functions Dirac delta derivatives of Dirac delta they are also tempered distributions. So, the class of entities for which the Fourier transform is defined has suddenly become pretty huge and this is possible because of this duality results. So, before we take up the definition of Fourier transform of a tempered distribution we proved a little lemma last time. Let us recall what this lemma says look at the slide theorem 112. If f and g are in the Schwarz space S of r then f hat g pairing is the same as f g hat pairing that is a straight forward application of Fibonni's theorem the proof simply writes itself out. Now f and g were in the Schwarz space. Now look at equation 10.8 now what we are going to do is that we are going to take the right hand side as the definition. Now what if f is not in the Schwarz space? What if f happens to be in S prime of r? What if f happens to be a tempered distribution? The right hand side of 10.8 would make perfect sense why because f is a tempered distribution and g was in the Schwarz class. So, g hat is also in the Schwarz class. So, u triangular bracket u with g hat makes perfect sense. So, let us now get to the formal definition of the Fourier transform of a tempered distribution. Suppose u is a tempered distribution then the map g going to triangular bracket u g hat is a tempered distribution where g varies over the Schwarz class. The tempered distribution given by 10.9 is denoted by u hat and is called the Fourier transform of u.  Left hand side is object that we are trying to define right hand side is the definition. We have to check that 10.9 is a tempered distribution that means that we have to check that the map 10.9 is continuous and this will follow from the previous result that the Fourier transform is continuous as an operator from S r to S r ok. So, g n is a sequence in S r converging to g then g n hat will converges to g hat g n converges to g in a very strong sense S of r. So, g n hat will converge to g hat in a very strong sense again in S of r, but u our original tempered distribution was continuous from S r to the scalars. So, u paired with g n hat will converge to u paired with g hat by continuity. So, we conclude from this that if g n converges to g the pairing u g n hat converges to u g hat proving the sequential continuity of 10.9. So, 10.9 does define a tempered distribution. So, let us calculate some tempered distribution. The most basic example is you take a function which is in l 1 of r. So, because u is in l 1 of r in chapter 4 we define the Fourier transform of u directly as an integral and we got a function which is in l infinity. Now, will that function represent the same distribution as the one that we have defined now. u is in l 1 so u is a distribution. So, we have the Fourier transform of u as a distribution and we have the Fourier transform of u as an l infinity function. Do these two things match? Is there a consistency in the definition? There had better be a consistency in the definition in order for the theory to go through. So, what are the distributional meaning of u hat? The distributional meaning of u hat is that u hat is a distribution g maps to the pairing u g hat.  So, what is this pairing u g hat? It is simply the integral u y g hat y d y put the definition of g hat because g hat is a nice function. So, the Fourier transform of g hat is a simply given by integral g x e to the power minus i x y dx. Now, a simple application of Fubini will enable you to switch the order of integration. So, this right hand side now simplifies to integral over r g x dx integral over r u y e to the power minus i x y d y. This inside integral is been called capital U. This inside integral is being called capital U. Capital U is Fourier transform of u in the classical sense. Capital U is the Fourier transform of u in the classical sense. The Fourier transform of u in the classical sense agrees with the Fourier transform of u in the sense of distribution. What is the RHS again?   So, u hat and capital U, they describe the same distribution, the same generalized function and so the definition is certainly consistent. So, we establish the consistency of the two definitions. Now, let us take up the Dirac delta. The Dirac delta is a favorite distribution. What is its Fourier transform? What is the definition of Fourier transform? Delta hat paired with g is by definition delta paired with g hat. But what is delta paired with g hat? It is g hat evaluated at the origin. But what is the Fourier transform evaluated at the origin? It is simply integral g x dx. But what is integral g x dx? It is one paired with g. The distribution 1, the l infinity function 1, when regarded as a distribution is exactly this. And the l infinity function 1 regarded as a distribution is simply one paired with g. So, delta naught hat paired with g is one paired with g. So, delta naught hat equal to 1. That is an important conclusion that the Fourier transform of the Dirac delta is the constant function 1. Now, what are the Fourier inversion theorems say? If f is the Schwarz class, then f hat hat is simply 2 pi times f of minus x. There is a reflection. Remember, when you take the Fourier transform twice, the Fourier transform is not a period 2 map, it is a period 4 map. You must remember that. So, when you take the Fourier transform twice, there is going to be an inversion in sign. So, if the inversion theorem were to hold for tempered distributions also, then I will apply one more hat to this equation. And I will get one hat equal to delta naught hat hat. And delta naught hat hat is supposed to be 2 pi times delta naught at minus x. But since the Dirac delta is at the origin, the inversion in sign does not matter. So, the inversion theorem were to hold, then we will get that the Fourier transform of 1 is 2 pi times delta naught. But we are not proved the inversion theorem yet. We are going to do it later. So, this equation 10.10 should now be established from first principles. Namely, we must use a definition of Fourier transform. So, one hat applied to g is by definition one applying to g hat. One applying to g hat is simply integral g hat y dy over the real numbers. How do I evaluate this integral? You have to use the e to the power minus epsilon y squared trick. So, write this as limit as epsilon goes to 0 outside integral g hat y e to the power minus epsilon y squared. First step, second step, put the definition of g hat as an integral. We will get two integrals, switch the order of integration and finish the job.  That calculation will come in and you will get the final answer to be 2 pi times g 0 and you would have verified 10.10. That is a second example on Fourier transform calculation. More examples on Fourier transform calculation. What is the Fourier transform of e to the power i x? What is the Fourier transform of cos x? What is the Fourier transform of sin x? After all cos x is e to the power i x plus e to the power minus i x upon 2. If you calculate the Fourier transform of e to the power minus i x a where a is real, when a is real that is a L infinity function. So, it is a tempered distribution. So, if you can calculate calculate the Fourier transform of this then you can calculate the Fourier transform of sin x and cos x. How do you calculate the Fourier transform of this?  But before you do that make sure to throw in the e to the power minus epsilon y squared use the e to the power minus epsilon y squared trick to do the job and you will get the Fourier transform. Use the e to the power minus epsilon y squared trick to compute the Fourier transform of the signum function what is the signum function this x upon mod x if you like. So, compute the Fourier transform of the signum function the signum function is h x minus h of minus x where h is a heavy side function. So, you can use the heavy side function to create signum function and I want you to calculate the Fourier transform of the signum function.  So, u hat is given by the prescription g maps to integral 0 to infinity g hat chi minus g hat of minus chi d chi.  It is a extremely important calculation and please do this as it is going to be very useful it is going to be is going to teach many things. Now, in chapter 4 we have seen that the Fourier transform exchanges differentiation and multiplication by the coordinate variable or to use a physicist's lingo the momentum and the position operators are dual operators with respect to the Fourier transform it converts the momentum operator into the position operator and vice versa. Of course, there is a minus sign floating around and you must do the bookkeeping carefully. Now, the question is will that formula carry over to tempered distributions remember if I have a tempered distribution I can differentiate. So, 1 upon id dx can be applied to a tempered distribution if I have a tempered distribution I can multiplied by a polynomial in particular I can multiplied by a coordinate variable. So, what is the story it is summarized as theorem 114 suppose you use a tempered distribution then as distributions we have the following equalities the you take the distribution you differentiate throw in the I and then take the Fourier transform that is same as first taking the Fourier transform and multiplying by the coordinate variable that is the first identity the second identity says that take the tempered distribution multiply by the polynomial x and then take the Fourier transform that is same as taking the Fourier transform first and then applying the 1 upon id dx except that here you will find a minus sign. So, you have to prove these two results the proofs are very routine and they follow immediately from the definition of Fourier transform of a tempered distribution and of course we will have to use this corresponding formulas for the Schwartz class that we established in chapter 4. So, we have to use those formulas in chapter 4 to derive these formulas let us do the first one and I leave the second one as an exercise to the audience. So, pick an element in the Schwartz class S of r it is a rapidly decreasing function and I want to calculate 1 upon id dx u hat applied to g by definition it is just put the hat on the other side and take 1 upon id dx u applied to g hat and now push the derivative of the other side how do I differentiate it distribution you simply throw the derivative of the other side and put a minus sign. So, it is u paired with minus 1 upon id dx g hat, but use the formula in chapter 4 g is the Schwartz class is rapidly decreasing. So, minus 1 upon id dx applied to g hat is the same as multiplying g by chi and then taking the Fourier transform. So, so far we have come here, but now again apply the definition of the Fourier transform of a tempered distribution. So, put the hat on the other factor u hat. So, it is u hat paired with chi g, but how do I pair u hat with chi g it is the same as chi u hat paired with g remember the rule for multiplying a distribution of the polynomial simply you can put the polynomial over here on the other side and you can take it from the other side on the left hand side whichever way. So, here we first put the hat on u by the definition of the Fourier transform and put the polynomial chi on the left hand side and you get this. So, we see that 1 upon id dx u hat paired with g is the same as chi u hat paired with g in other words 1 upon id dx u hat is the same as chi times u hat and the other equation 10.12 is proved in exactly the same way there is no change only changes are cosmetic. Now we have ready to prove the inversion theorem.  So, what do I mean by switching the sign in a distribution what exactly is the definition of that and that is clarified by theorem 115 suppose u is a distribution and g is a Schwarz function then u hat hat there is a tempered distribution how does it act on g the way it acts on g is 2 pi times u acting on the reflected function g of minus x. So, this is the avatar of the Fourier inversion theorem for distributions. So, the same thing carries over for tempered distributions also. So, let us look at the left hand side the left hand side is u hat hat paired with g that will be first put the hat on the other side. So, it will be u hat paired with g hat put the hat again on the right hand side will be u paired with g hat hat, but g is the Schwarz class. So, we are back to chapter 4. So, g hat hat as per chapter 4 is 2 pi times g of minus x the 2 pi being a scalar comes out innocently. So, it will be u paired with g of minus x and that is the right hand side and we have finished proving the theorem as an immediate corollary we get a very important result. Suppose I give you an L1 function suppose I give you an L1 function you know that the Fourier transform is in L infinity the Fourier transform may not be in L1. Example take the characteristic function of minus 1 1 take the characteristic function of minus 1 1 that is certainly in L1 take its Fourier transform what is the Fourier transform 2 times sin chi by chi sin chi by chi is not in L1. So, the Fourier transform of an L1 function may not be in L1, but now I am giving you more hypothesis I am telling you that u is in L1 and u hat is also in L1 under this additional hypothesis I can take u hat hat this u hat hat is going to be 2 pi times u of minus x how do I prove this. So, from this theorem 115 we immediately conclude that if u is in L1 and u hat is in L1 then u hat hat is simply 2 pi times u of the reflected variable and that completes the theorem on Fourier version. Now, so far we have been talking about tempered distributions of one variable what happens about tempered distributions in several variables go back to chapter 4. In chapter 4 we develop the Schwarz class S of r in one variable for notational simplicity and at the end we simply indicated how to discuss Schwarz class in several variables and we even talked about radial functions and therefore, a transform is also radial and all those things we proved in chapter 4. Here again we have been confining ourselves to the one variable case for notational simplicity how do I discuss the tempered distributions in several variables well we should start with a Schwarz space in several variables S of r in and I have to put a topology in a Schwarz space exactly as we did earlier. Only thing is that now instead of K and L we will have to take multi indices I will have to take a multi index alpha which is alpha 1 alpha 2 alpha n and I want to differentiate with respect to x 1 x 2 x n correspond into this multi index. So, del del x 1 alpha 1 times del del x 2 alpha 2 times that are del del x n alpha n times so that is the kind of a mixed partial derivative that we need to take. So, when does a sequence f nu converge to f in the Schwarz space you take the difference and you take the alpha derivative where alpha is a specified multi index and you multiplied by any polynomial whatsoever q x you can take a monomial if you like x to the power beta but does not matter you can take a polynomial as an equivalent definition. So, supremum over r in and that must go to 0 for every choice of multi index alpha and for every choice of polynomial q x if this happens then we say that f nu converges to f in the Schwarz class as it happens the one variable case the several variables also S of r n is a complete metric space and this notion of convergence arises from a complete metric as in the one variable case this is not going to be a normal space as in the one variable case it is going to be a locally convex topological vector space and hence the dual space which is a rich space S prime of r n is a space of tempered distributions in several variables. In other words the tempered distribution in several variables is simply a continuous linear map from S of r n to a scalars. So, it is a linear transformation with a target space a scalars and this linear transformation should be continuous. So, there are no new ideas there are just cosmetic changes in passing from one variable to several variables as far as the definitions are concerned the same thing is true for Fourier transform to define the Fourier transform you simply use the same prescription as before use a tempered distribution and u hat is its Fourier transform I will tell you what u hat does to g. So, the pairing of u hat with g is simply u paired with g hat this prescription g maps to u paired with g hat is a continuous map from S of r n to the scalars. So, this also defines a tempered distribution the support of a tempered distribution of several variables is defined exactly as in the one variable case it is the smallest closed set outside which the distribution is 0 and I leave it to you to formulate precisely the definition of a support just the same thing simply carries forward verbatim. So, now the theorem on point supports theorem 117 a tempered distribution whose support is a single point origin what kind of distribution is it of course the Dirac delta will be supported the origin the derivatives of the Dirac delta now the derivatives are multidimensional derivatives del del x 1 to the power alpha 1 del del x 2 to the power alpha 2 del del x n to the power alpha and that kind of differentiation you have to take on the Dirac delta they those will also have point support namely the origin and their finite linear combinations will have point support the converse is true and that is theorem 117 suppose if u is a tempered distribution whose support is a single point namely the origin then this distribution is a linear combination of finitely many derivatives of Dirac delta. So, namely u equals summation c alpha delta naught to the power alpha mod alpha less than or equal to 1 there are finitely many derivatives of Dirac delta and its linear combination. So, this theorem is extremely important we are not proved this for one variable case we are not we are not going to prove it for several variables also in the next capsule we are going to give a nice application of theorem 117 to prove Lieuweil's theorem which is a generalization of the Lieuweil's theorem for complex analysis in elementary complex analysis you proved a Lieuweil's theorem we are going to generalize it to harmonic functions but we are going to use distribution theory to dispose of the proof quickly and efficiently. I think this will be a very good place to stop this capsule we will continue this next time. Thank you very much.